100
3. A Procedure for Solving the Optimal Expansion
Problem
Iteration 6
Arc
*·»
-τ,·
-6 <; ·
?<>·
/«
State In kilter?
(1, 2)
0
-2
2
0
2 = «κ B
Yes
(1, 3)
0
-5
5
0
0 = lx,
Yes
(2, 3)
2
-5
1
-2
1 = «23 C
Yes
(2, 4)
2
-5
3
0
1 > ^4
Β
Yes
(3, 2)
5
-2
1
4
0 = ί ί2
A
Yes
(3, 4)
5
-5
6
6
1 = *18
A
Yes
(4, 1)
5
-0
0
5
2 < Ul
Ax
No
1. Arc (2, 4) has been brought into kilter.
2. Arc (4, 1) is out of kilter.
3. State of the arc is A\ ; increase / 4 i to Z41.
4. Find path from arc 1 to arc 4 by labeling procedure.
Labeling procedure
Node
Label
1
(4+1)
2
Cannot be labeled: arc (1, 2) is in kilter
3
(1
+ , 1)
4
Cannot be labeled: arc (3, 4) is in kilter
Nonbreakthrough has occurred.
X = (1, 3), X = (2, 4), Μ = {(3, 2), (3, 4)}, Μ = (2, 3), D - min
(4, 6) = 4, D = min(2) = 2, D f = 2.
New τ values: ττχ = 0, π 2 = 4, x 3 = 5,7r 4 = 7.
Recompute state of each arc.