Engineering Optimization: Theory and Practice, Fourth Edition

188 Linear Programming II: Additional Topics and Extensions

Table 4.6 Detached Coefficients of the Original System

Admissible variables

x 1 x 2 x 3 x 4 x 5 x 6 −f Constants

2 1 − 1 1 0 0 2

2 − 1 5 0 1 0 6

4 1 1 0 0 1 6

− 1 − 2 − 1 0 0 0 1 0

Table 4.7 Tableau at the Beginning of Cycle 0

Columns of the canonical form

Basic variables x 4 x 5 x 6 −f

Value of the basic

variable (constant) x 2 a

x 4 1 0 0 0 2 a 42 = 1
Pivot element
x 5 0 1 0 0 6 a 52 = − 1
x 6 0 0 1 0 6 a 62 = 1
Inverse of the basis=[βij]
−f 0 0 0 1 0 c 2 = − 2
aThis column is entered at the end of step 5.

Step 2The iterative procedure (cycle 0) starts withx 4 , x 5 , x 6 , and −f as basic vari-

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

and the constant terms as shown in Table 4.7. Since the basis matrix isB=

I, its inverseB−^1 =[βij] =I.The row corresponding to −f in Table 4.7

gives the negative of simplex multipliersπi, i= 1 , 2 , 3. These are all zero

in cycle 0. The entries of the last column of the table are, of course, not yet

known.

Step 3The relative cost factorscjare computed as

cj=cj−πTAj=cj, j= 1 to 6

since allπiare zero. Thus

c 1 =c 1 = − 1

c 2 =c 2 = − 2

c 3 =c 3 = − 1

c 4 =c 4 = 0

c 5 =c 5 = 0

c 6 =c 6 = 0

These cost coefficients are entered as the first row of a tableau (Table 4.8).