11.2. THE SIMPLEX TABLEAU 225

You add in slack variables. These are positive variables, one for each of the first threeconstraints, which change the first three inequalities into equations. Thus the first threeinequalities become x1 +2x2 + x3 = 10,x1 +2x2− x4 = 2, and

2x1 + x2 + x5 = 6,x1,x2,x3,x4,x5 ≥ 0.

Now it is necessary to find a basic feasible solution. You mainly need to find a positivesolution to the equations,

x1 +2x2 + x3 = 10x1 +2x2− x4 = 22x1 + x2 + x5 = 6

.

the solution set for the above system is given by

x2 =23

x4−23+

13

x5,x1 =−13

x4 +103− 2

3x5,x3 =−x4 +8.

An easy way to get a basic feasible solution is to let x4 = 8 and x5 = 1. Then a feasiblesolution is

(x1,x2,x3,x4,x5) = (0,5,0,8,1) .

It follows z0 = −5 and the matrix 11.2,

(A 0 b−c 1 0

)with the variables kept track of

on the bottom is 1 2 1 0 0 0 101 2 0 −1 0 0 22 1 0 0 1 0 6−1 1 0 0 0 1 0x1 x2 x3 x4 x5 0 0

and the first thing to do is to permute the columns so that the list of variables on the bottomwill have x1 and x3 at the end.

2 0 0 1 1 0 102 −1 0 1 0 0 21 0 1 2 0 0 61 0 0 −1 0 1 0x2 x4 x5 x1 x3 0 0

Next, as described above, take the row reduced echelon form of the top three lines of theabove matrix. This yields  1 0 0 1

212 0 5

0 1 0 0 1 0 80 0 1 3

2 − 12 0 1

 .

Now do row operations to 1 0 0 1

212 0 5

0 1 0 0 1 0 80 0 1 3

2 − 12 0 1

1 0 0 −1 0 1 0

