96
3. A Procedure for Solving the Optimal Expansion
Problem
Iteration 2
Arc
-5Γ,·
-&<,·
QH
State In kilter?
(1, 2)
0
-2
2
0
0 = hi
B
Yes
(1, 3)
0
-2
5
3
2
?1»
A 2
No
(2, 3)
2
-2
1
1
0 = ^23 A
Yes
(2, 4)
2
-2
3
3
2
hi
A 2
No
(3, 2)
2
-2
1
1
2
lz2 A 2
No
(3, 4)
2
-2
6
6
0
Zs.
A,
No
(4, 1)
2
0
0
2
2
hi
A,
No
1. Arc (1, 2) is still in kilter but its state has changed from 4 to B;
therefore, flow can be increased in (1,2) without driving it out of kilter.
2. State of arc (1, 3) is A 2 ; decrease/i 3 to l xz .
3. Find path from node 1 to node 3 by the labeling procedure.
Labeling procedure
Node
Label
1
(3", 2) [Decrease flow in arc (1, 3)]
2
(1
+ , 2) [Increase flow in arc (1, 2)]
3
(2~, 2) [Decrease flow in arc (3, 2)]
Breakthrough has occurred.
Change flow in the cycle as indicated by labels.
Recompute state of each arc.