Engineering Optimization: Theory and Practice, Fourth Edition

186 Linear Programming II: Additional Topics and Extensions

the basic set in the next cycle in place of therth basic variable (rto be found

later), such that

cs= inm (cj< 0 )

5 .Compute the elements of thexscolumn from Eq. (4.9) as

As=B−^1 As=βijAs

that is,

a 1 s=β 11 a 1 s+β 12 a 2 s+ · · · +β 1 mams

a 2 s=β 21 a 1 s+β 22 a 2 s+ · · · +β 2 mams

..

.

ams=βm 1 a 1 s+βm 2 a 2 s+ · · · +βmmams

and enter in the last column of Table 4.2 (if cycle 0) or Table 4.4 (if cyclek).

6.Inspect the signs of all entriesais, i = 1 tom. If allais≤ , the class of 0

solutions

xs≥ arbitrary 0

xj i=bi−ais·xsifxj i is a basic variable, andxj= 0 ifxj is a nonbasic

variable (j=s), satisfies the original system and has the property

f =f 0 +csxs→ −∞ as xs→ +∞

Hence terminate the process. On the other hand, if someais > 0 , select the

variablexrthat can be dropped in the next cycle as

br

ars

= min

ais> 0

(bi/ais)

In the case of a tie, chooserat random.

7.To bringxsinto the basis in place ofxr, carry out a pivot operation on the

elementarsin Table 4.4 and enter the result as shown in Table 4.5. As usual,

the last column of Table 4.5 will be left blank at the beginning of the current

cyclek+1. Also, retain the list of basic variables in the first column of Table 4.5

the same as in Table 4.4, except thatjris changed to the value ofsdetermined

in step 4.

8.Go to step 3 to initiate the next cycle,k+1.

Example 4.1

MaximizeF=x 1 + 2 x 2 +x 3

subject to

2 x 1 +x 2 −x 3 ≤ 2

− 2 x 1 +x 2 − 5 x 3 ≥ − 6