Engineering Optimization: Theory and Practice, Fourth Edition

3.9 Simplex Algorithm 147

SOLUTION Introducing the slack variablesx 3 ≥ and 0 x 4 ≥ , the given system of 0
equations can be written in canonical form as

x 1 −x 2 + x 3 = 1

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

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

(E 1 )

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

x 3 = 1 , x 4 = 6 (basic variables)

x 1 =x 2 = 0 (nonbasic variables) (E 2 )

f= 0

Since the cost coefficients corresponding to the nonbasic variables are negative, the
solution given by Eq.(E 2 ) s not optimum. Hence the simplex procedure is applied toi
the canonical system of Eqs.(E 1 ) tarting from the solution, Eqs.s (E 2 ) The computa-.
tions are done in tableau form as shown below:

Basic Variables b
′′
i/a
′′
isfor
variables x 1 x 2 x 3 x 4 −f b′′i ais′′> 0

x 3 1

Pivot

element

− 1 1 0 0 1 1 ←Smaller value

(x 3 leaves the

basis)

x 4 3 − 2 0 1 0 6 2

−f − 3 − 2 0 0 1 0

↑

Most negativec′′i(x 1 enters the next basis)

Result of pivoting:

x 1 1 − 1 1 0 0 1

x 4 0 1

Pivot

element

− 3 1 0 3 3 (x 4 leaves the

basis)

−f 0 − 5 3 0 1 3

↑

Most negativec′′i(x 2 enters the next basis)

Result of pivoting:

x 1 1 0 − 2 1 0 4 Botha′′isare

negative (i.e.,

no variable

leaves the basis)

x 2 0 1 − 3 1 0 3

−f 0 0 − 12 5 1 18

↑

Most negativec′′i(x 3 enters the basis)