3.3.
The Operational
Policy Problem (Problem
III)
87
Dual Problem
Minimize
γ = Σ
u iftn — Σ Ufia
(3.io)
A
A
subject to
*i - try + 7i*y - 5y > bn
for each (t, j) ζ A
(3.11)
Yy > 0, δα > 0
for each (i,j) e A
(3.12)
The π variables are unrestricted in sign, since these dual variables are
associated with equality constraints in the primal formulation.
At the optimum, the values of the primal and dual objective functions
are equal. The relationships between the primal and dual variables that
force such an equality have been termed the complementary slackness
conditions. These conditions are:
Yy > 0 =» fa = ua for each
6 A (3.13)
δα > 0 => fa = la for each
€ A (3.14)
TTI — TJ + Hi — ί»7 = 6y =» Zy < /y < Uy
(3.15)
where =* designates "it follows that."
The OKA is so efficient because it takes advantage of the above relationships and the special structure of the minimum-cost circulation problem in
order to examine only a relatively small subset of the primal and dual
variables in search of a "best" or optimal value of Eq. (3.5). The efficiency
is achieved by defining three quantities
?y = 7Γ* — vj — ba
(3.16)
Yy = max (0, -gy)
(3.17)
δα = max (0, qa)
(3.18)
so that Yy and 5y continually satisfy conditions (3.11) and (3.12). Thus
the values of τη may be freely chosen without disrupting dual feasibility.
By comparing Eqs. (3.13)-(3.15) with the definitions in Eqs. (3.16)(3.18), the complementary slackness conditions may be reformulated:
qa < 0
fa = ua
(3.19)
qa > 0
=*
fa - In
(3.20)
qa = 0
=*
In < fn < w (3.21)