3.3. The Operational
Policy Problem (Problem HI)
85
Notation Used in Section 3.3
Symbol
Significance
Units
A
A subset of ordered pairs from a collection of Ν elements
hi
Benefit of passing one unit of flow through the arc (I, j)
$/acre-ft
Cxi
Cost of passing one unit of flow through the arc (I, j)
$/acre-ft
fa
Flow in the arc (i, j)
acre-ft
G
A directed network {N; A}
Ui
Lower flow capacity of arc (i, j)
acre-ft
Ν
A collection of elements
Qu
Total cost to the system-consumer and distributor of transporting
one unit of flow from node i to node j
$/acre-ft
Uij
Upper flow capacity of arc (I, j)
acre-ft
in
Marginal value of decreasing /,·,· by one unit
$/acre-ft
yn
Marginal value of increasing
by one unit
$/acre-ft
*3
Price of one unit of water at the node (j)
$/acre-ft
feasibility of applying nonlinear programming to the OP problem is poor
for realistically sized water resources systems.
The OP problem sketched in Fig. 3.9 is in the form of a network flow
problem. Fulkerson [1961] developed the out-of-kilter algorithm to solve
this type of problem, provided the objective function is linear or can be
approximated by a piecewise linear function (e.g., convex cost functions
or concave revenue functions). We will first examine the strategy of the
out-of-kilter algorithm and then see how it can be applied to the OP
problem.
3.3.1. The Out-of-Kilter
Algorithm
To clarify the concepts introduced in this section, some new notation is
presented in Table 3.4. The out-of-kilter algorithm (OKA) was developed
by Fulkerson [1961] to solve the following problem. Define a directed
network G = {N; A} that consists of a collection of Ν nodes {1, 2,. , . , N}
together with a subset A of the ordered pairs {i } j) of elements taken from
N. See Fig. 3.10. The pairs {i, j} are referred to as arcs. Associated with
each arc is an upper (μ^) and a lower (Z
flow capacity and also the cost
Fig. 3.10 Part of a directed network
/O)
^ Γ7)
^C^)
representing the flow of water.
^—J
fa
fjk
Table 3.4