Computer Aided Engineering Design

OPTIMIZATION 361

xbiii = , = 1,... , ′ m

ff = 0 ′

xi = 0, i = m+ 1,... , n

The algorithm is intended to move from one basic feasible solution to another using a pivotal
operation. Prior to that we ensure that the current solution is non-optimal by inspecting the values of
ccmm′′+1, + 2,... , .cn′ A basic feasible solution is optimal with a minimum function value f 0 ′ if all
ccmm′′+1, + 2,... cn′ are non-negative. From the last row of Eq. (12.31), we have

fcx cx0+1+1+2+2′′ + mm + ′mm +... + cxfnn′ =

Variables xm+1,xm+2,.. ., xn are all zero in the current basic feasible solution and are constrained to
be non-negative. In the subsequent basic feasible solution, any one of them, say xk,k∈[m+ 1, n]
would enter the set of basic variables by becoming positive. But if ck≥ 0, xk becoming positive will
only increase the function value. Thus, if ccmm′′+1, + 2,... , cn′ are all non-negative, none of the non-
basic variables xm+1,xm+2,... , xn will cause a decrease in the function value by becoming positive
or entering the basic variables set, and therefore, the current solution will be the optimal point.

Inspection of cc′′mm+1, + 2,... , cn′ also reveals if there is a multiple optima. Let ccmm′′+1, ,+ 2...,
cckk′′–1, +1,... , cn′ be all > 0 except for c′k which is equal to zero for some non-basic variable xk.
Thus, if xk enters the basic variable set by becoming positive, no change in the function results in
which case there are multiple optima. We can say therefore that a basic feasible solution is uniquely
optimal if ccmm′′+1, + 2,... , cn′ are all strictly positive (> 0) for the non-basic variables.
In case the current basic feasible solution is not optimal, it may be improved as follows. If at least
oneckk′, belonging to [m + 1, n] is negative, xk can be made the basic variable to decrease ffurther.
In case more than one c′ks are negative, then xs is chosen to be the basic variable such that

cckm ns′′ = min ( k < 0), = + 1,... ,

If there are more than one c′ss having the same minimum value, then any one among them is
arbitrarily chosen. Once xs is chosen, we make it positive by keeping the rest of the non-basic
variables zero and observing the performance of the current basic variables. From Eq. (12.31) we see
that

xbax111, = – ′′s s, b 1 ′ 0 ≥

xbax222, = – ′′s s, b′ 2 0 ≥

...
xbaxmmmss = ′′ – , , b′m 0 ≥

ff cx = + 0 ′′ss cs′ < 0 (12.32)

Thatcs′ < 0 suggests that xs should be made as large as possible to reduce the function f. However,
in the process of increasing xs, some existing basic variables may become negative. It can be seen that
if all aiis′, < 0, = 1,... ,m,xs can be made as large as possible without making any xi,i = 1,... , m
negative in which case the linear programming problem is unbounded. Otherwise, if ais′, > 0, equating
xi to zero in Eqs. (12.32) gives