Engineering Optimization: Theory and Practice, Fourth Edition

142 Linear Programming I: Simplex Method

xm=b′′m−a′′msxs, b′′m≥ 0

f=f 0 ′′+c′′sxs, c′′s< 0 (3.28)

Sincec′′s < , Eq. (3.28) suggests that the value of 0 xsshould be made as large as

possiblein order to reduce the value offas much as possible. However, in the process

of increasing the value ofxs, some of the variablesxi(i = 1 , 2 ,... , m)in Eqs. (3.27)

may become negative. It can be seen that if all the coefficientsai′′s≤ , 0 i= 1 , 2 ,... , m,

thenxscan be made infinitely large without making anyxi< , 0 i= 1 , 2 ,... , m. In

such a case, the minimum value off is minus infinity and the linear programming

problem is said to have anunbounded solution.

On the other hand, if at least oneai′′sis positive, the maximum value thatxscan

take without makingxi negative isb′′i/ai′′s. If there are more than onea′′is> 0 , the

largest valuex∗s thatxscan take is given by the minimum of the ratiosb′′i/a′′is for

whichai′′s > 0. Thus

xs∗=

b′′r

ar′′s

= inimumm

a′′is> 0

(

bi′′

a′′is

)

(3.29)

The choice ofrin the case of a tie, assuming that allb′′i> 0 , is arbitrary. If anyb′′i

for whicha′′is> 0 is zero in Eqs. (3.27),xscannot be increased by any amount. Such

asolution is called adegenerate solution.

In the case of a nondegenerate basic feasible solution, a new basic feasible solu-

tion can be constructed with a lower value of the objective function as follows. By

substituting the value ofx∗sgiven by Eq. (3.29) into Eqs. (3.27) and (3.28), we obtain

xs=x∗s

xi=b′′i−a′′isx∗s≥ 0 , i= 1 , 2 ,... , m and i=r (3.30)

xr= 0

xj= 0 , j=m+ 1 , m+ 2 ,... , n and j=s

f=f 0 ′′+c′′sxs∗≤f 0 ′′ (3.31)

which can readily be seen to be a feasible solution different from the previous one.

Sincear′′s> 0 in Eq. (3.29), a single pivot operation on the elementa′′rsin the system

ofEqs. (3.21) will lead to a new canonical form from which the basic feasible solution

of Eqs. (3.30) can easily be deduced. Also, Eq. (3.31) shows that this basic feasible

solution corresponds to a lower objective function value compared to that of Eqs. (3.22).

This basic feasible solution can again be tested for optimality by seeing whether all

c′′i> 0 in the new canonical form. If the solution is not optimal, the entire procedure

of moving to another basic feasible solution from the present one has to be repeated.

In the simplex algorithm, this procedure is repeated in an iterative manner until the

algorithm finds either (1) a class of feasible solutions for whichf→ −∞or (2) an

optimal basic feasible solution with allc′′i≥ , 0 i= 1 , 2 ,... , n. Since there are only

a finite number of ways to choose a set ofmbasic variables out ofnvariables, the

iterative process of the simplex algorithm will terminate in a finite number of cycles.

The iterative process of the simplex algorithm is shown as a flowchart in Fig. 3.14.