72
3. A Procedure for Solving the Optimal Expansion
Problem
Problem 0
Maximize
/<°>(x)
subject to
g
{ f(x)
> 0
i = 1,.. ., m; χ 6 E
n ,
χ > 0
Let us replace Problem 0 with an easier problem, Problem 1, that "bounds"
Problem 0 in the following sense [Lawler and Wood, 1966]:
There exists at least one optimal feasible solution x
(0)
of Problem 0 such
that x<°> is feasible for Problem 1 and/« (x
(0) ) > /
(0) (x
(0) ).
(B)
Here/
(1) (x
(0) ) denotes the objective function for Problem 1, a problem of
similar form to Problem 0 but not necessarily having the same list of constraints. Furthermore, if we find an optimal feasible solution x
(1)
to Problem 1, it can be shown that
If x
(1) satisfies the optimality conditions that (a) x
(1) is a feasible solution
to Problem 0, and (b) /
(1) (x
(1) ) = /
(0) (x
(1) ), then x<
1} is an optimal solution
to Problem 0 as well.
Because it may not be easy for x
(1)
to satisfy requirements (a) and (b),
it generally proves better to replace Problem 1 by a set of problems Ρ =
{2, 3, ...} that bound Problem 0 in the sense that they jointly satisfy the
following bounding property [Lawler and Wood, 1966]:
There exists at least one optimal solution x
(0)
of Problem 0 such that
x
(0)
is feasible for at least one problem j of the set P, and /
(i) (x
(0) ) >
/<°>(x«»).
(BO
If we find an optimal solution x
(i)
for each of the j problems in the set P,
and define x
(A ° such that
/(*)( x <*)) = max[/^(x
(i) )]
UP
it can be shown that x
(A ° is an optimal solution to Problem 0:
If x
(Aj)
satisfies the optimality conditions that (a') x
(k)
is a feasible solution to Problem 0, and (b') /<*>(*<») = /
(0) (x
( *>), then x<*> is an optimal
solution to Problem 0.
To continue in this vein, if x
(A ° does not satisfy the conditions (a') and
(b'), again we replace one of the problems in the bounding set Ρ by a new
set of problems. Suppose we replace Problem k by a set of bounding problems Pk = {Pkt, P*2,...}. In addition to requiring that the union of the
set P, less Problem Jc, with the set Pa satisfy the bounding condition B
; ,
two convergence conditions are imposed.
3. A Procedure for Solving the Optimal Expansion
Problem
Problem 0
Maximize
/<°>(x)
subject to
g
{ f(x)
> 0
i = 1,.. ., m; χ 6 E
n ,
χ > 0
Let us replace Problem 0 with an easier problem, Problem 1, that "bounds"
Problem 0 in the following sense [Lawler and Wood, 1966]:
There exists at least one optimal feasible solution x
(0)
of Problem 0 such
that x<°> is feasible for Problem 1 and/« (x
(0) ) > /
(0) (x
(0) ).
(B)
Here/
(1) (x
(0) ) denotes the objective function for Problem 1, a problem of
similar form to Problem 0 but not necessarily having the same list of constraints. Furthermore, if we find an optimal feasible solution x
(1)
to Problem 1, it can be shown that
If x
(1) satisfies the optimality conditions that (a) x
(1) is a feasible solution
to Problem 0, and (b) /
(1) (x
(1) ) = /
(0) (x
(1) ), then x<
1} is an optimal solution
to Problem 0 as well.
Because it may not be easy for x
(1)
to satisfy requirements (a) and (b),
it generally proves better to replace Problem 1 by a set of problems Ρ =
{2, 3, ...} that bound Problem 0 in the sense that they jointly satisfy the
following bounding property [Lawler and Wood, 1966]:
There exists at least one optimal solution x
(0)
of Problem 0 such that
x
(0)
is feasible for at least one problem j of the set P, and /
(i) (x
(0) ) >
/<°>(x«»).
(BO
If we find an optimal solution x
(i)
for each of the j problems in the set P,
and define x
(A ° such that
/(*)( x <*)) = max[/^(x
(i) )]
UP
it can be shown that x
(A ° is an optimal solution to Problem 0:
If x
(Aj)
satisfies the optimality conditions that (a') x
(k)
is a feasible solution to Problem 0, and (b') /<*>(*<») = /
(0) (x
( *>), then x<*> is an optimal
solution to Problem 0.
To continue in this vein, if x
(A ° does not satisfy the conditions (a') and
(b'), again we replace one of the problems in the bounding set Ρ by a new
set of problems. Suppose we replace Problem k by a set of bounding problems Pk = {Pkt, P*2,...}. In addition to requiring that the union of the
set P, less Problem Jc, with the set Pa satisfy the bounding condition B
; ,
two convergence conditions are imposed.