Engineering Optimization: Theory and Practice, Fourth Edition

182 Linear Programming II: Additional Topics and Extensions

only to illustrate the transformation, and it can be dropped in actual computations. Thus

in practice, we write them+ 1 ×m+2 matrix

           

a 1 s

a 2 s

..

.

D−^1 ars

..

.

ams

cs

           

and carry out a pivot operation onars. The firstm+ 1 columns of the resulting matrix

will give us the desired matrixD−new^1.

Procedure. The detailed iterative procedure of the revised simplex method to solve

a general linear programming problem is given by the following steps.

1.Write the given system of equations in canonical form, by adding the artificial

variablesxn+ 1 , xn+ 2 ,... , xn+m, and the infeasibility form for phase I as shown

below:

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

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

..

.

am 1 x 1 +am 2 x 2 + · · · +amnxn +xn+m =bm

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

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

(4.14)

Here the constantsbi, i = 1 tom, are made nonnegative by changing, if nec-

essary, the signs of all terms in the original equations before the addition of

the artificial variablesxn+i, i = 1 tom. Since the original infeasibility form is

given by

w=xn+ 1 +xn+ 2 + · · · +xn+m (4.15)

the artificial variables can be eliminated from Eq. (4.15) by adding the firstm

equations of Eqs. (4.14) and subtracting the result from Eq. (4.15). The resulting

equation is shown as the last equation in Eqs. (4.14) with

dj= −

∑m

i= 1

aij and w 0 =

∑m

i= 1

bi (4.16)

Equations (4.14) are written in tableau form as shown in Table 4.1.

2.The iterative procedure (cycle 0) is started withxn+ 1 , xn+ 2 ,... , xn+m, −f,and

−was the basic variables. A tableau is opened by entering the coefficients of

the basic variables and the constant terms as shown in Table 4.2. The starting

basis matrix is, from Table 4.1,B=I, and its inverseB−^1 =[βij] can also be