3.3. The Operational
Policy Problem (Problem
III)
89
of Qij and fij determine whether a given arc is in kilter or, if out of kilter,
what changes are needed in the
and /,·/ values to bring it into kilter.
The value of qu is altered by systematically varying the values of τη and
tj, which can be easily done. However, to change the value of fij is much
more difficult because conservation of flow must be maintained at each
node. The OKA changes flow in such a way as to avoid disruption of the
conservation of flow.
If flow in the arc (i, j) is to be changed, a path must be found from node
j to node i, which, with the inclusion of the
arc, forms a cycle. Changing the flow in this cycle will maintain conservation of flow at all nodes.
The path from node j to node i and the change in flow are chosen in such a
way that (1) no in-kilter arc becomes out of kilter, and (2) no out-of-kiiter
arc becomes more out of kilter. (An arc becomes more out of kilter when its
flow is changed in magnitude so as to increase the deviation from the feasible state of the arc. For example, if an arc (i, j) is in state Αχ (i.e., fa <
Uj) and its flow is reduced further, then the arc becomes more out of kilter.)
For example, consider the minimum-cost circulation problem represented
by Fig. 3.11. The ordered triple (Uj, Uij, — &»/) is shown on each arc. The
original arc flows and node numbers (ir values) appear as underlined numbers. For example, /13 = 2 and ττχ = 0.
Notice that arc (1, 3) is out of kilter and in state A 2 . To bring the arc
into kilter the flow must be reduced to the arc lower bound (0) and also
conservation of flow in the network must be maintained. This can be
achieved by changing flows in the closed path or loop (1, 2), (3, 2), (1, 3).
(See Section 3.3.8, iteration 1). Note that the path is not formed by arcs
whose flows form a directed graph; the rule to remember for reducing flows
in a closed path is to increase flows in forward arcs and to decrease flows in
Fig. 3.11 A minimum cost circulation
example.
(3,3,0), 2
Policy Problem (Problem
III)
89
of Qij and fij determine whether a given arc is in kilter or, if out of kilter,
what changes are needed in the
and /,·/ values to bring it into kilter.
The value of qu is altered by systematically varying the values of τη and
tj, which can be easily done. However, to change the value of fij is much
more difficult because conservation of flow must be maintained at each
node. The OKA changes flow in such a way as to avoid disruption of the
conservation of flow.
If flow in the arc (i, j) is to be changed, a path must be found from node
j to node i, which, with the inclusion of the
arc, forms a cycle. Changing the flow in this cycle will maintain conservation of flow at all nodes.
The path from node j to node i and the change in flow are chosen in such a
way that (1) no in-kilter arc becomes out of kilter, and (2) no out-of-kiiter
arc becomes more out of kilter. (An arc becomes more out of kilter when its
flow is changed in magnitude so as to increase the deviation from the feasible state of the arc. For example, if an arc (i, j) is in state Αχ (i.e., fa <
Uj) and its flow is reduced further, then the arc becomes more out of kilter.)
For example, consider the minimum-cost circulation problem represented
by Fig. 3.11. The ordered triple (Uj, Uij, — &»/) is shown on each arc. The
original arc flows and node numbers (ir values) appear as underlined numbers. For example, /13 = 2 and ττχ = 0.
Notice that arc (1, 3) is out of kilter and in state A 2 . To bring the arc
into kilter the flow must be reduced to the arc lower bound (0) and also
conservation of flow in the network must be maintained. This can be
achieved by changing flows in the closed path or loop (1, 2), (3, 2), (1, 3).
(See Section 3.3.8, iteration 1). Note that the path is not formed by arcs
whose flows form a directed graph; the rule to remember for reducing flows
in a closed path is to increase flows in forward arcs and to decrease flows in
Fig. 3.11 A minimum cost circulation
example.
(3,3,0), 2