86
3. A Procedure for Solving the Optimal Expansion
Problem
(dj) of passing one unit of water through each arc. The flow in arc (i, j) is
fa. The problem is to minimize the cost of passing a feasible flow in the
directed network, if one exists.
This is a linear programming (minimum-cost circulation) problem with
the special feature that a number of equality constraints exist; each equality
constraint corresponds to a mass balance at each node [Eq. (3.7) ]. Fulkerson treated the equality constraints in a special way in his algorithm.
Computational results for some large-scale problems [Texas Water Development Board, 1969] show the OKA to produce a solution in one twentieth to one fiftieth the time of standard linear programming codes for two
reasons: (1) all operations are additive (i.e., no multiplication or division
takes place), and (2) no matrix inversion is necessary.
It is convenient to express the problem in linear programming notation
so that the relationship between the primal and dual variables may be
demonstrated:
(3-5)
for each (t, j) € A
(3.6)
Primal Problem
i
fn > 0
for each i € Ν
for each (i, j) 6 A
for each (i, j) ζ A
(3.7)
(3.8)
(3.9)
Maximize
svbject to
Note that maximizing Ζ is the same as minimizing 2 = Σ*' Σ* °υίϋ so
that each 6« is a negative coefficient and equals (—dj). From the duality
theory of linear programming, there is a dual variable associated with each
primal constraint, and a dual constraint associated with each primal
variable. Let x t * denote the dual variable associated with the ith primal
conservation-of-flow equation [from the set of equations of (3.7)] for
each node i € N. Let
denote the dual variable associated with the
upper-bound constraint of arc (i, j) from the set of primal inequalities
represented by Eq. (3.6). Let δ,/ denote the dual variable associated with
the lower-bound constraint of arc (i, j) from the set of primal inequalities
represented by Eq. (3.8). The mathematical statement of the dual problem
is as follows.
3. A Procedure for Solving the Optimal Expansion
Problem
(dj) of passing one unit of water through each arc. The flow in arc (i, j) is
fa. The problem is to minimize the cost of passing a feasible flow in the
directed network, if one exists.
This is a linear programming (minimum-cost circulation) problem with
the special feature that a number of equality constraints exist; each equality
constraint corresponds to a mass balance at each node [Eq. (3.7) ]. Fulkerson treated the equality constraints in a special way in his algorithm.
Computational results for some large-scale problems [Texas Water Development Board, 1969] show the OKA to produce a solution in one twentieth to one fiftieth the time of standard linear programming codes for two
reasons: (1) all operations are additive (i.e., no multiplication or division
takes place), and (2) no matrix inversion is necessary.
It is convenient to express the problem in linear programming notation
so that the relationship between the primal and dual variables may be
demonstrated:
(3-5)
for each (t, j) € A
(3.6)
Primal Problem
i
fn > 0
for each i € Ν
for each (i, j) 6 A
for each (i, j) ζ A
(3.7)
(3.8)
(3.9)
Maximize
svbject to
Note that maximizing Ζ is the same as minimizing 2 = Σ*' Σ* °υίϋ so
that each 6« is a negative coefficient and equals (—dj). From the duality
theory of linear programming, there is a dual variable associated with each
primal constraint, and a dual constraint associated with each primal
variable. Let x t * denote the dual variable associated with the ith primal
conservation-of-flow equation [from the set of equations of (3.7)] for
each node i € N. Let
denote the dual variable associated with the
upper-bound constraint of arc (i, j) from the set of primal inequalities
represented by Eq. (3.6). Let δ,/ denote the dual variable associated with
the lower-bound constraint of arc (i, j) from the set of primal inequalities
represented by Eq. (3.8). The mathematical statement of the dual problem
is as follows.