90
3. A Procedure for Solving the Optimal Expansion
Problem
Fig. 3,12 A minimum cost circulation
example: flow values and node numbers
in iteration 3. For each arc the ordered
triple is (Uj, ua, —ha); m and /»·,· are the
node numbers and flow before iteration 1,
{τη} and {fa) are those in iteration 3.
reverse arcs. Figure 3.12 shows the change in the flows values and node
numbers after two complete iterations. Because only a finite number of
arcs may be out of kilter, termination of the algorithm is assured. Durbin
and Kroenke (1967), Ford and Fulkerson (1962), and Fulkerson (1961)
have described a labeling procedure for changing the flow in out-of-kilter
arcs. A description of this procedure follows.
3.3.4. Labeling
Procedure
1. If an arc (i, j) is found in which the flow is to be increased to bring
that arc into kilter, then the arc must be in state A h B\ y or d. Label node
3 P
+ >
Β 0)]· This signifies that node j may receive e(j) units from node i. If
the arc is in state Ai, define e(j) to be (Uj — fij); and if the arc is in state
Bi or Ci, define e(j) to be (u^ — fa). These definitions put arc (i } j) into
kilter with the fewest changes of the original flow pattern.
2. If the flow in arc (i, j) is to be decreased, then the arc must be in state
Ai } 2? 2 , or C2. Label node i
e(i) ], meaning that the flow from node i to
node j can be reduced by e(i). If the arc is in state A 2 or Z? 2 , define e(i) to
be (fa — Uj); if the arc is in state C2, define e(i) to be (/# — wy). An arc
that is in any one of the three possible remaining states, A } B y or C is in
kilter and its flow should not be changed.
Once an out-of-kilter arc (i, j) has been found, the node i or j is labeled
by rule (1) or (2). If the change indicated by the label can be made, the
arc can be brought into kilter. However, as discussed previously, a path
must be found from j to i [which, with the inclusion of arc (i } j), forms a
cycle] so that conservation of flow will not be violated by the proposed
flow change. Each node of the path must be labeled so that the needed
changes can be accounted for.
3. A Procedure for Solving the Optimal Expansion
Problem
Fig. 3,12 A minimum cost circulation
example: flow values and node numbers
in iteration 3. For each arc the ordered
triple is (Uj, ua, —ha); m and /»·,· are the
node numbers and flow before iteration 1,
{τη} and {fa) are those in iteration 3.
reverse arcs. Figure 3.12 shows the change in the flows values and node
numbers after two complete iterations. Because only a finite number of
arcs may be out of kilter, termination of the algorithm is assured. Durbin
and Kroenke (1967), Ford and Fulkerson (1962), and Fulkerson (1961)
have described a labeling procedure for changing the flow in out-of-kilter
arcs. A description of this procedure follows.
3.3.4. Labeling
Procedure
1. If an arc (i, j) is found in which the flow is to be increased to bring
that arc into kilter, then the arc must be in state A h B\ y or d. Label node
3 P
+ >
Β 0)]· This signifies that node j may receive e(j) units from node i. If
the arc is in state Ai, define e(j) to be (Uj — fij); and if the arc is in state
Bi or Ci, define e(j) to be (u^ — fa). These definitions put arc (i } j) into
kilter with the fewest changes of the original flow pattern.
2. If the flow in arc (i, j) is to be decreased, then the arc must be in state
Ai } 2? 2 , or C2. Label node i
e(i) ], meaning that the flow from node i to
node j can be reduced by e(i). If the arc is in state A 2 or Z? 2 , define e(i) to
be (fa — Uj); if the arc is in state C2, define e(i) to be (/# — wy). An arc
that is in any one of the three possible remaining states, A } B y or C is in
kilter and its flow should not be changed.
Once an out-of-kilter arc (i, j) has been found, the node i or j is labeled
by rule (1) or (2). If the change indicated by the label can be made, the
arc can be brought into kilter. However, as discussed previously, a path
must be found from j to i [which, with the inclusion of arc (i } j), forms a
cycle] so that conservation of flow will not be violated by the proposed
flow change. Each node of the path must be labeled so that the needed
changes can be accounted for.