98
3· A Procedure for Solving the Optimal Expansion
Problem
Iteration 4
Arc
*·,·
—*i
-6
Qu
Su
State In kilter?
(1, 2)
0
-2
2
0
2 = «12 Β
Yes
(1, 3)
0
-3
5
2
0 = Ixz A
Yes
(2, 3)
2
-3
1
0
0 = hz
Β
Yes
(2, 4)
2
-3
3
2
2 > hi
A 2
No
(3, 2)
3
-2
1
2
0 = lii
A
Yes
(3, 4)
3
-3
6
6
0 < hi
Αχ
No
(4, 1)
3
0
0
3
2 < hi
Αχ
No
1. Arc (2, 3) is still in kilter, but its state has changed from A to B;
therefore, flow can be increased in (2, 3) without driving the arc out of
kilter.
2. State of arc (2, 4) is A2; decrease f*i to k*.
3. Find path from node 2 to node 4 by labeling procedure.
Labeling procedure
Node
Label
2
(4- 2)
3
(2+ 1)
4
(3+ 1)
Breakthrough has occurred.
Change flow in the cycle as indicated by labels.
Recompute state of each arc.