3.3. The Operational
Policy Problem (Problem III)
91
3.3.5. Scanned
Nodes and the Flow-Augmenting
Path
Suppose that arc (i, j) is out of kilter and that node i has been labeled.
The aim is to find a flow-augmenting path form i to j in such a way that
in-kilter arcs in the path will not be driven out of kilter. Consider each
arc that originates or terminates at a labeled node (node i is the first
Table 3.6
Labeling Process Through a Forward Arc
©
H3)
fa
qu = 7Tj — vj — bn
Suppose that i is labeled {j
± , e(i) ]; can j be labeled? (Never label j from i if an increase
in the flow/,,- will make the arc more out of kilter.)
State of
arc
fa
In
kilter?
Can j" be
labeled?
Why?
A
3
0
= I
Yes
No
Flow increase makes arc out of
kilter
Β
Q
0
u
u
Yes
Yes
Yes
No
Flow may be increased to «,·,·
Flow cannot be increased
C
Q
0
u
Yes
No
Flow cannot be increased
Ax
9
0
I
No
Yes
Flow may be increased to Uj
Βχ
3 = 0
I
No
Yes
Flow may be increased to ω,·,·
?
0
u
No
Yes
Flow may be increased to 1/,·,·
A 2
?
0
I
No
No
Flow increase makes arc more out
of kilter
B 2
? == 0
u
No
No
Flow increase makes arc more out
of kilter
c 2
?
0
u
No
No
Flow increase makes arc more out
of kilter
Summary
Label j
e(j)].
If qu > 0 and/*,- < Ui, then e(j) = min[e(i), (Uj —
If Qu < 0 and fa < ua , then e(j) = min[e({), (ua — /.·,·)].