88
3. A Procedure for Solving the Optimal Expansion
Problem
These three conditions, along with the conservation of flow to maintain
primal feasibility, given in Eq. (3.7), determine the sufficient conditions
of optimality for the given problem. The three sufficient conditions may
be used to test whether the tentative values of the variables in arc (i y j)
are optimal.
If a set of values of in and /# can be found that satisfy Eqs. (3.7) and
(3.19)-(3.21) for each arc of G 9 then the values
are the solution to the
minimum-cost circulation problem. Fulkerson named the OKA by noting
that an arc that did not satisfy at least one of the above optimality conditions, Eqs. (3.17)-(3.19), was "out of kilter." The OKA seeks to systematically direct flows and assign values to the π variables so that each
arc is "in kilter."
3.3.2. Significance
of the Dual
Variables
m can be considered the price of a unit of the flow commodity at the
node i; q%j represents the total cost to the system-consumer and distributor
of transporting one unit of flow from node i to node j [Durbin and Kroenke,
1967]; Tiy represents the marginal value of increasing ua by one unit; and
by represents the marginal value of decreasing U, by one unit.
3.3.3. Possible States of an Arc
Nine mutually exclusive "kilter conditions" are possible for each arc as
the algorithm proceeds to seek an optimal solution (Table 3.5). The values
Table 3-5
Possible Kilter Conditions for an Arc
State
9U
In kilter?
A
3 > 0
f = ι
Yes
Β
? = 0 I < f
u
Yes
C
?
0
f = u
Yes
A t
? > 0
f < ι
No
Bi
? = 0
f No
?
0
f < 11
No
A 2
? > 0
f > ι
No
? = 0
f > u
No
c 2
?
0
f > u
No