Learning Outcomes

• Record a linear program and its slack form in a simplex tableau

• Read the basic feasible solution, objective value, and reduced costs directly from a tableau

• Carry out one simplex pivot as a sequence of elementary row operations

• Recognize the optimality condition in tableau form and read off the optimal solution

Try it out visually!

First put the program in standard form by adding a nonnegative slack variable to each constraint:

We also record the objective as an equation. Moving the cost terms to the left,

so that the objective sits in the table on the same footing as the constraints. This equation is the objective row (or $z$-row); we place it on top.

Each row of the tableau lists the coefficients of one equation, and the final column holds its right-hand side. The leftmost column names the basic variable of that row: the variable that appears with coefficient $1$ in that row and $0$ in every other row. Reading the starting tableau,

the basis is $\{s_1,s_2,s_3\}$. Setting the nonbasic variables $x=y=0$ gives the basic feasible solution $s_1=9,s_2=16,s_3=14$ read directly from the RHS column, with objective value $z=0$ (the RHS of the $z$-row). The entries of the $z$-row, $-2$ and $-3$, record the reduced costs of $x$ and $y$ with the sign flipped: increasing $x$ or $y$ from zero would change $z$ at the rates $+2$ and $+3$, the negatives of the stored entries.

❒ Sign convention.  In the dictionary form we wrote $z=2x+3y$ and increased the variable with the largest positive coefficient. The tableau instead stores the row $z-2x-3y=0$, so the very same coefficients appear negated. The two rules therefore read as mirror images and give identical decisions: in tableau form we bring in the variable with the most negative $z$-row entry, and we stop when every $z$-row entry is nonnegative.

A pivot has three moves, and we color them consistently throughout the book: green chooses the entering variable, orange runs the ratio test to find the leaving variable, and blue marks the pivot element where the two meet.

☞ Entering: $y$ ($z$-row entry $-3$, the most negative). ✏ Leaving: $s_3$ (smallest ratio $7$). ❒ Pivot on the blue element.

The pivot itself is just Gaussian elimination on the pivot column, driving it to a unit column with the $1$ in the pivot row.

☞ Entering.  The $z$-row entries are $-2$ (for $x$) and $-3$ (for $y$). The most negative is $-3$, so $y$ enters: increasing $y$ improves $z$ fastest.

✏ Ratio test.  Divide each constraint’s RHS by its positive entry in the $y$ column:

$$\frac{9}{1}=9,\frac{16}{1}=16,\frac{14}{2}=7(\text{smallest}).$$

The smallest ratio, $7$, occurs in the $s_3$ row, so $s_3$ leaves. The pivot element is the entry where the entering column meets the leaving row, namely $2$.

❒ Pivot.  Scale the pivot row so the pivot element becomes $1$, then clear the $y$ column everywhere else:

$$\begin{array}{ccc}\hfill \text{new }y\text{-row}& \leftarrow \frac{1}{2}(s_3\text{-row})=[\frac{1}{2},1,0,0,\frac{1}{2}\mid 7],\hfill & \hfill \\ \hfill z\text{-row}& \leftarrow z\text{-row}+3(\text{new }y\text{-row}),\hfill \\ \hfill s_1\text{-row}& \leftarrow s_1\text{-row}-1(\text{new }y\text{-row}),\hfill \\ \hfill s_2\text{-row}& \leftarrow s_2\text{-row}-1(\text{new }y\text{-row}).\hfill \end{array}$$

The result is the second tableau, with basis $\{s_1,s_2,y\}$:

☞ Entering: $x$ (only negative $z$-row entry, $-\frac{1}{2}$). ✏ Leaving: $s_1$ (smallest ratio $4$). ❒ Pivot on $\frac{1}{2}$.

Notice the objective value has already climbed from $0$ to $21$. One more pivot on the blue element (scale the $s_1$-row by $2$, then clear the $x$ column) produces the third tableau, with basis $\{x,s_2,y\}$:

Every entry of the $z$-row is now nonnegative, so no variable can enter and improve the objective: the tableau is optimal. We read the solution straight from the RHS column, taking each basic variable equal to its right-hand side and each nonbasic variable equal to zero:

The result matches the dictionary solution exactly, as it must. The nonzero slack $s_2=3$ says the second constraint $2x+y\le 16$ is slack (indeed $2(4)+5=13<16$), while $s_1=s_3=0$ says the first and third constraints are tight at the optimum.

Algorithm: Simplex Method (Tableau Form)

☞ Choose the entering variable Scan the objective row. Pick a nonbasic variable with a negative entry; a common choice is the most negative. If no entry is negative, stop: the current tableau is optimal.

✏ Ratio test for the leaving variable For each row with a positive entry in the entering column, form the ratio $\frac{\text{RHS}}{\text{entering-column entry}}$. The row with the smallest ratio leaves. (If no entry is positive, the problem is unbounded.)

❒ Pivot Scale the pivot row so the pivot element becomes $1$, then add multiples of it to every other row, including the objective row, so the rest of the entering column becomes $0$.

✔ Repeat until optimal Repeat until every objective-row entry is nonnegative. Then read the optimal solution and objective value from the RHS column.

Return to the linear program

The first constraint needs a surplus variable $e_1$ and an artificial variable $a_1$; the other two take ordinary slacks:

Step 1 — Price the artificial variable out of the objective row.  Writing the objective as $z-2x-3y+M{a}_1=0$ would leave a nonzero entry under the basic variable $a_1$. Subtracting $M$ times the $a_1$-row restores a proper tableau, at the cost of introducing $M$ into the other entries:

☞ Entering: $x$ (its $z$-row entry $-2-2M$ is the most negative for large $M$). ✏ Leaving: $a_1$ (smallest ratio $2.5$). ❒ Pivot on $2$.

The very first pivot drives the artificial variable out of the basis. After pivoting on the blue element we obtain

The artificial variable $a_1$ is now nonbasic, and its objective-row entry $1+M$ is positive, so it will never re-enter: we may delete the $a_1$ column and forget it ever existed. What remains is an ordinary feasible tableau, which we drive to optimality with the plain simplex rules of the previous sections. A few pivots later every objective-row entry is nonnegative:

Reading the optimal tableau gives $x=6$, $y=4$, and $z=24$, with surplus $e_1=11$ on the first constraint and both later constraints tight ($s_2=s_3=0$).

The Big-M method also announces when a problem has no feasible solution: an artificial variable that refuses to leave the basis. Consider

whose first two constraints demand that $2x+y$ be simultaneously at least $22$ and at most $16$. Setting it up exactly as before and pricing out the artificial variable gives the starting tableau

Running the simplex method to optimality of the penalized problem (two pivots suffice) leads to

Every objective-row entry is nonnegative, so this tableau is optimal for the Big-M problem, yet the artificial variable $a_1$ is still basic, at the positive value $a_1=6$. Because a genuine solution of the original problem would let us set every artificial variable to zero, a positive artificial variable in the optimal Big-M tableau is the signal that the original linear program is infeasible. The tell-tale $-6M$ in the objective value $24-6M$ says the same thing: no finite objective can escape the penalty.

Exercise 9.1: Reading a mid-solve tableau

$\star$  The tableau below is the second tableau of this chapter’s running example, reached after one pivot:

1.

Which variables are basic and which are nonbasic?

2.

Read off the basic feasible solution and the objective value.

3.

What are the reduced costs of the nonbasic variables?

4.

Is this tableau optimal? If not, which variable enters next?

Exercise 9.2: Reading a tableau

$\star$  The following tableau arose while solving a maximization problem, with the objective row on top:

Identify the basic and nonbasic variables, state the corresponding basic feasible solution and its objective value, and explain how you can tell from the objective row that this tableau is optimal.

Exercise 9.3: Entering variable, ratio test, and pivot element

$\star$  Consider the tableau

Determine the entering variable, carry out the ratio test showing every ratio, name the leaving variable, and circle the pivot element.

Exercise 9.4: Perform one pivot

Exercise 9.5: Solve a linear program in tableau form

$\star \star$  Use the simplex method in tableau form to solve

Show every tableau, coloring or labelling the entering column, leaving row, and pivot element at each step. State the optimal solution and objective value. (You should reach the optimum in two pivots.)

Exercise 9.6: A full two-pivot solve

$\star \star$  Solve the following linear program in tableau form, using the most-negative-entry rule to choose the entering variable:

Show the starting tableau and each tableau after a pivot, and state the optimal solution, the optimal objective value, and the values of the slack variables at the optimum.

Exercise 9.7: Setting up a Big-M tableau

$\star \star$  Consider the linear program

Introduce a surplus variable $e_1$ and an artificial variable $a_1$ for the first constraint and a slack $s_2$ for the second, and write the objective as $\max 4x+3y-M{a}_1$. Build the initial tableau with the objective row on top, and then price out the artificial variable $a_1$ so that its objective-row entry becomes zero. Which variable enters first, and does the artificial variable leave on the first pivot?

Exercise 9.8: The $z$-row sign convention

Exercise 9.9: From tableau to dictionary

Exercise 9.10: Recognizing an unbounded problem

$\star \star$  While solving a maximization problem you obtain

Which variable should enter? Attempt the ratio test and explain why it fails. What does this tell you about the linear program?

Exercise 9.11: Reading off infeasibility

$\star \star$  Suppose the Big-M method applied to some maximization problem terminates (every objective-row entry nonnegative) with the tableau

Is the tableau optimal for the penalized problem? What is the value of the artificial variable $a_1$, and what does it tell you about the original linear program? Explain the role of the $-3M$ term in the objective value.

Exercise 9.12: Certifying unboundedness from a tableau

$\star \star \star$  Applying the simplex method to

produces, after one pivot, the tableau

1.

Detect the unboundedness: identify the entering variable and show that the ratio test finds no limiting row.

2.

Certify it: letting the entering variable equal $t\ge 0$, write the resulting family of solutions $x(t)$ in all four variables, and verify by direct substitution that $x(t)$ satisfies both original constraints and the nonnegativity conditions for every $t\ge 0$.

3.

Show that $z(t)\to \infty$ as $t\to \infty$, and sketch the feasible region to explain geometrically which direction the certificate ray points in.

Solution