Engineering Optimization: Theory and Practice, Fourth Edition

3.9 Simplex Algorithm 145

Thusx 2 enters the next basic set. To obtain the new canonical form, weselect the pivot
elementa′′rssuch that
b′′r
a′′rs

= min

a′′is> 0

(

b′′i

a′′is

)

In the present case,s=2 anda 1 ′′ 2 anda′′ 32 are ≥ 0. Sinceb′′ 1 /a 1 ′′ 2 = 2 / 1 andb′′ 3 /a 3 ′′ 2 =
6 / 1 ,xr=x 1. By pivoting ana′′ 12 , the new system of equations can be obtained as

2 x 1 + 1 x 2 −x 3 +x 4 = 2

4 x 1 + 0 x 2 + 4 x 3 +x 4 +x 5 = 8

2 x 1 + 0 x 2 + 2 x 3 −x 4 +x 6 = 4

3 x 1 + 0 x 2 − 3 x 3 + 2 x 4 −f = 4

(E 3 )

The basic feasible solution corresponding to this canonical form is

x 2 = 2 , x 5 = 8 , x 6 = 4 (basic variables)

x 1 =x 3 =x 4 = 0 (nonbasic variables) (E 4 )

f=− 4

Sincec′′ 3 = − 3 , the present solution is not optimum. Asc′′s in=m (ci′′< 0 )=c′′ 3 ,xs=x 3
enters the next basis.
To find the pivot elementar′′s, we find the ratiosb′′i/ai′′sforai′′s>0.In Eqs.(E 3 ),
onlya′′ 23 anda 3 ′′ 3 are > 0 , and hence

b′′ 2

a 2 ′′ 3

=

8

4

and

b′′ 3

a′′ 33

=

4

2

Since both these ratios are same, we arbitrarily selecta′′ 23 as the pivot element. Pivoting
ona′′ 23 gives the following canonical system of equations:

3 x 1 + 1 x 2 + 0 x 3 +^54 x 4 +^14 x 5 = 4

1 x 1 + 0 x 2 + 1 x 3 +^14 x 4 +^14 x 5 = 2

0 x 1 + 0 x 2 + 0 x 3 −^32 x 4 −^12 x 5 +x 6 = 0

6 x 1 + 0 x 2 + 0 x 3 +^114 x 4 +^34 x 5 − f = 10

(E 5 )

The basic feasible solution corresponding to this canonical system is given by

x 2 = 4 , x 3 = 2 , x 6 = 0 (basic variables)

x 1 =x 4 =x 5 = 0 (nonbasic variables) (E 6 )

f=− 10

Since allc′′i are ≥ 0 in the present canonical form, the solution given in(E 6 ) ill bew
optimum. Usually, starting with Eqs.(E 1 ) all the computations are done in a tableau,