Engineering Optimization: Theory and Practice, Fourth Edition

4.2 Revised Simplex Method 187

Table 4.5 Tableau at the Beginning of Cyclek+ 1

Columns of the canonical form
Basic variables xn+ 1 · · · xn+m −f −w Value of the basic variable xsa

xj 1 β 11 −a 1 sβ∗r 1 · · · β 1 m−a 1 sβ∗rm b 1 −a 1 sbr∗

..

.

xs βr∗ 1 · · · βrm∗ br∗

..

.

xj m βm 1 −amsβ∗r 1 · · · βmm−amsβ∗rm bm−amsb∗r

−f −π 1 −csβr∗ 1 · · · −πm−csβ∗rm 1 −f 0 −csb∗r

−w −σ 1 −dsβr∗ 1 · · · −σm−dsβrm∗ 1 −w 0 −dsb

∗

r

βri∗=

βri

ars

(i=1 tom) and b

∗

r=

br
ars
aThis column is blank at the start of the cycle.

4 x 1 +x 2 +x 3 ≤ 6

x 1 ≥ 0 ,x 2 ≥ 0 ,x 3 ≥ 0

SOLUTION This problem can be stated in standard form as (making all the constants

bipositive and then adding the slack variables):

Minimize

f = −x 1 − 2 x 2 −x 3 (E 1 )

subjectto

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

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

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

xi≥ 0 , i=1 to 6

(E 2 )

wherex 4 , x 5 , andx 6 are slack variables. Since the set of equations (E 2 ) re in canonicala

form with respect tox 4 , x 5 , andx 6 , xi= ( 0 i= 1 , 2 ,3) andx 4 = 2 ,x 5 = , and 6 x 6 = 6

can be taken as an initial basic feasible solution and hence there is no need for phase I.

Step 1All the equations (including the objective function) can be written in canonical

form as

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

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

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

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

(E 3 )

These equations are written in tableau form in Table 4.6.