 |
Suppose arc AD with flow is added to the feasible spanning tree. The unique
undirected cycle in this case is AD-DB-BC-CA. The above network shows next
to each arc the resulting incremental flow (in parentheses) and the cost
per unit flow (to the left of the parentheses). |
When ,
the resulting overall increment in total cost ( )
is |
= 5(1) + 3(-1) + 2(1) + 4(-1) = 0. |
Hence, the rate of change of
as
is increased is 0. |