 |
Suppose arc EC with flow is added to the feasible spanning tree. The unique
undirected cycle in this case is EC-CB-BD-DE. 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 |
= -3(1) + 2(-1) + 3(1) + 4(1) = 2. |
Hence, the rate of change of
as
is increased is 2. |