92
3. A Procedure for Solving the Optimal Expansion
Problem
labeled node), and in each case attempt to label the node at the arc's connecting end. Labeling a node will be possible only if the arc is in one of the
allowable states (Αχ, B\, C\, A%, B%, and C2); the proper label values for
flow changes in forward and reverse arcs are given and described in Tables
3.6 and 3.7, respectively. After each incident arc has been considered, the
Table 3.7
Labeling Process Through a Reverse Arc
©
fa
Qa —
v i — τ»
—
&/<
Suppose that i is labeled [z*, e (i) ]; can j be labeled? (Never label j from i if a decrease
in the flow/,,- will make the arc more out of kilter.)
State of
arc
fa
In
kilter?
Canjbe
labeled?
Why?
A
3 > 0
= I
Yes
No
Flow decrease would make
out of kilter
arc
Β
3 = 0
VI II
u
I
Yes
Yes
No
Flow can be decreased by /,·,· -
Flow cannot be decreased
- h
C
< 0
- u Yes No Flow cannot be decreased
Ar
? > 0
< I
No
No
Flow decrease would make
more out of kilter
arc
Bi
?
-
0
< I
No
No
Flow decrease would make
more out of kilter
arc
Cl
3 < 0
< u
No
No
Flow decrease would make
more out of kilter
arc
A 2
1 > 0
> I
No
Yes
Flow may be decreased by/,·,· • - lit
B 2
? = 0
> u
No
Yes
Flow may be decreased by/,·,· - hi
c2
3 < 0
> u
No
Yes
Flow maybe decreased by/,·< -- Uji
Summary
Label j [ir, e(j)]
If qa > 0 and/yi > la, then e(j) =» min[e(i), (fa — Z#)].
If qa < 0 and/,. > 11», then e(j) = min[e(i), (fa — u#)].