Engineering Optimization: Theory and Practice, Fourth Edition

3.10 Two Phases of the Simplex Method 151

1.Arrange the original system of Eqs. (3.32) so that all constant termsbi are
positiveor zero by changing, where necessary, the signs on both sides of any
of the equations.

2.Introduce to this system a set of artificial variablesy 1 , y 2 ,... , ym(which serve
as basic variables in phase I), where eachyi≥ 0,so that it becomes
a 11 x 1 +a 12 x 2 + · · · +a 1 nxn+y 1 =b 1
a 21 x 1 +a 22 x 2 + · · · +a 2 nxn +y 2 =b 2
..
.
am 1 x 1 +am 2 x 2 + · · · +amnxn +ym =bm
bi≥ 0

(3.34)

Note that in Eqs. (3.34), for a particulari, theaij’s and thebi may be the

negative of what they were in Eq. (3.32) because of step 1.

The objective function of Eq. (3.33) can be written as

c 1 x 1 +c 2 x 2 + · · · +cnxn+ (−f)= 0 (3.35)

3.Phase I of the method. Define a quantitywas the sum of the artificial variables

w=y 1 +y 2 + · · · +ym (3.36)

and use the simplex algorithm to findxi≥ ( 0 i= 1 , 2 ,... , n) andyi≥ ( 0 i=

1 , 2 ,... , m) which minimizewand satisfy Eqs. (3.34) and (3.35). Consequently,

consider the array

a 11 x 1 +a 12 x 2 + · · · +a 1 nxn+y 1 =b 1

a 21 x 1 +a 22 x 2 + · · · +a 2 nxn +y 2 =b 2

..

.

..

.

am 1 x 1 +am 2 x 2 + · · · +amnxn +ym =bm

c 1 x 1 +c 2 x 2 + · · · +cnxn + (−f) = 0

y 1 +y 2 + · · · +ym + (−w)= 0

(3.37)

This array is not in canonical form; however, it can be rewritten as a canonical

system with basic variablesy 1 , y 2 ,... , ym, −f,and−wby subtracting the sum

of the firstmequations from the last to obtain the new system

a 11 x 1 +a 12 x 2 + · · · +a 1 nxn+y 1 =b 1

a 21 x 1 +a 22 x 2 + · · · +a 2 nxn +y 2 =b 2

..

.

..

.

am 1 x 1 +am 2 x 2 + · · · +amnxn +ym =bm

c 1 x 1 +c 2 x 2 + · · · +cnxn + (−f) = 0

d 1 x 1 +d 2 x 2 + · · · +dnxn + (−w)= −w 0

(3.38)