238 CHAPTER 11. LINEAR PROGRAMMING

row. There is a −1. Use this column. The pivot is the 3. The next tableau is

23

23 0 1 0 − 1

3 0 0 223

13

13 1 0 0 1

3 0 0 83

− 23 − 2

3 0 0 1 13 0 0 2

323

53 0 0 0 − 1

3 1 0 133

− 23

103 0 0 0 1

3 0 1 83

There is still a negative entry, the −2/3. This will be the new pivot column. The pivot isthe 2/3 on the fourth row. This yields

0 −1 0 1 0 0 −1 0 30 − 1

2 1 0 0 12 − 1

2 0 12

0 1 0 0 1 0 1 0 51 5

2 0 0 0 − 12

32 0 13

20 5 0 0 0 0 1 1 7

and the process stops. The maximum for z is 7 and it occurs when x1 = 13/2,x2 = 0,x3 =1/2.

11.4 Finding A Basic Feasible SolutionBy now it should be fairly clear that finding a basic feasible solution can create considerabledifficulty. Indeed, given a system of linear inequalities along with the requirement that eachvariable be nonnegative, do there even exist points satisfying all these inequalities? If youhave many variables, you can’t answer this by drawing a picture. Is there some other wayto do this which is more systematic than what was presented above? The answer is yes. Itis called the method of artificial variables. I will illustrate this method with an example.

Example 11.4.1 Find a basic feasible solution to the system 2x1 + x2− x3 ≥ 3,x1 + x2 +x3 ≥ 2,x1 + x2 + x3 ≤ 7 and x≥ 0.

If you write the appropriate augmented matrix with the slack variables, 2 1 −1 −1 0 0 31 1 1 0 −1 0 21 1 1 0 0 1 7

 (11.18)

The obvious solution is not feasible. This is why it would be hard to get started with thesimplex method. What is the problem? It is those−1 entries in the fourth and fifth columns.To get around this, you add in artificial variables to get an augmented matrix of the form 2 1 −1 −1 0 0 1 0 3

1 1 1 0 −1 0 0 1 21 1 1 0 0 1 0 0 7

 (11.19)

Thus the variables are x1,x2,x3,x4,x5,x6,x7,x8. Suppose you can find a feasible solutionto the system of equations represented by the above augmented matrix. Thus all variables