224 CHAPTER 11. LINEAR PROGRAMMING

The reason there is a z0 on the bottom right corner is that xF = 0 and(x0

B,x0F ,z

0)T is a

solution of the system of equations represented by the above augmented matrix because it isa solution to the system of equations corresponding to the system of equations representedby 11.6 and row operations leave solution sets unchanged. Note how attractive this is.The z0 is the value of z at the point x0. The augmented matrix of 11.9 is called the simplextableau and it is the beginning point for the simplex algorithm to be described a little later. Itis very convenient to express the simplex tableau in the above form in which the variables

are possibly permuted in order to have

(I0

)on the left side. However, as far as the

simplex algorithm is concerned it is not necessary to be permuting the variables in thismanner. Starting with 11.9 you could permute the variables and columns to obtain anaugmented matrix in which the variables are in their original order. What is really requiredfor the simplex tableau?

It is an augmented m+ 1×m+ n+ 2 matrix which represents a system of equationswhich has the same set of solutions, (x,z)T as the system whose augmented matrix is(

A 0 b−c 1 0

)

(Possibly the variables for x are taken in another order.) There are m linearly independentcolumns in the first m+n columns for which there is only one nonzero entry, a 1 in one ofthe first m rows, the “simple columns”, the other first m+n columns being the “nonsimplecolumns”. As in the above, the variables corresponding to the simple columns are xB,the basic variables and those corresponding to the nonsimple columns are xF , the freevariables. Also, the top m entries of the last column on the right are nonnegative. This isthe description of a simplex tableau.

In a simplex tableau it is easy to spot a basic feasible solution. You can see one quicklyby setting the variables, xF corresponding to the nonsimple columns equal to zero. Thenthe other variables, corresponding to the simple columns are each equal to a nonnegativeentry in the far right column. Lets call this an “obvious basic feasible solution”. If asolution is obtained by setting the variables corresponding to the nonsimple columns equalto zero and the variables corresponding to the simple columns equal to zero this will bereferred to as an “obvious” solution. Lets also call the first m+ n entries in the bottomrow the “bottom left row”. In a simplex tableau, the entry in the bottom right corner givesthe value of the variable being maximized or minimized when the obvious basic feasiblesolution is chosen.

The following is a special case of the general theory presented above and shows howsuch a special case can be fit into the above framework. The following example is rathertypical of the sorts of problems considered. It involves inequality constraints instead ofAx = b. This is handled by adding in “slack variables” as explained below.

The idea is to obtain an augmented matrix for the constraints such that obvious solutionsare also feasible. Then there is an algorithm, to be presented later, which takes you fromone obvious feasible solution to another until you obtain the maximum.

Example 11.2.2 Consider z = x1−x2 subject to the constraints, x1 +2x2 ≤ 10,x1 +2x2 ≥2, and 2x1 + x2 ≤ 6,xi ≥ 0. Find a simplex tableau for a problem of the form x≥ 0,Ax = bwhich is equivalent to the above problem.