Lesson 5: The Simplex Method II: The Tableau Algorithm¶
5.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Set up the initial simplex tableau from an LP.
- Execute pivot operations accurately and efficiently.
- Read the optimal solution, slack values and shadow prices from the final tableau.
- Verify a solution independently.
- Recognise alternate optima from the final tableau.
5.2 Setting Up the Tableau¶
The recipe.
1. Convert to standard form (L02): all constraints '=', all b_i >= 0
2. Identify an initial basis -- the slack variables, if all constraints were <=
3. Build the table: Basis | c_B | all variable columns | RHS
4. Compute the z_j - c_j row
Layout convention used throughout this course.
| \(c_j \to\) | \(c_1\) | \(c_2\) | \(\cdots\) | \(c_n\) | ||
|---|---|---|---|---|---|---|
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(\cdots\) | \(x_n\) | RHS |
| \(x_{B_1}\) | \(c_{B_1}\) | \(a_{11}\) | \(a_{12}\) | \(a_{1n}\) | \(b_1\) | |
| \(\vdots\) | ||||||
| \(x_{B_m}\) | \(c_{B_m}\) | \(a_{m1}\) | \(a_{m2}\) | \(a_{mn}\) | \(b_m\) | |
| \(z_j - c_j\) | \(\Delta_1\) | \(\Delta_2\) | \(\Delta_n\) | \(Z\) |
5.3 The Pivot Operation, Step by Step¶
Given pivot element p = a[r][k] (row r, column k):
1. New pivot row = old pivot row / p
2. For every other row i:
new row i = old row i - a[i][k] x (new pivot row)
3. Replace the basis label in row r by x_k, and c_B by c_k
4. Recompute z_j - c_j
Three checks after every pivot — do these every time and errors become rare:
- The pivot column now reads \((0,\ldots,0,1,0,\ldots,0)^T\) with the 1 in the pivot row.
- All RHS values are \(\ge 0\).
- \(Z\) has improved (or stayed the same, under degeneracy).
Work in fractions, not decimals. Simplex tableaus produce values like \(2/3\) and \(5/14\); decimal rounding accumulates and eventually corrupts the \(z_j-c_j\) signs, causing wrong termination.
5.4 Worked Example — Complete Trace¶
(This is the problem solved graphically in L03; the optimum is \((3, 1.5)\) with \(Z = 21\).)
Standard form.
Iteration 0¶
| Basis | \(c_B\) | \(x_1\) (5) | \(x_2\) (4) | \(s_1\) (0) | \(s_2\) (0) | RHS | Ratio |
|---|---|---|---|---|---|---|---|
| \(s_1\) | 0 | 6 | 4 | 1 | 0 | 24 | \(24/6 = 4\) ← |
| \(s_2\) | 0 | 1 | 2 | 0 | 1 | 6 | \(6/1 = 6\) |
| \(z_j-c_j\) | −5 ↑ | −4 | 0 | 0 | 0 |
Reading it. Basis \(\{s_1, s_2\}\), so \(x_1 = x_2 = 0\) — this is the origin, \(Z = 0\).
Since \(c_B = (0,0)\), every \(z_j = 0\) and \(z_j - c_j = -c_j\).
Entering: \(x_1\) (most negative, \(-5\)). Ratios: \(\{4, 6\}\); minimum is 4 in row 1. Leaving: \(s_1\). Pivot = 6.
Iteration 1¶
Divide row 1 by 6; then row 2 ← row 2 − 1×(new row 1).
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | RHS | Ratio |
|---|---|---|---|---|---|---|---|
| \(x_1\) | 5 | 1 | \(2/3\) | \(1/6\) | 0 | 4 | \(4 \div \frac23 = 6\) |
| \(s_2\) | 0 | 0 | \(4/3\) | \(-1/6\) | 1 | 2 | \(2 \div \frac43 = 3/2\) ← |
| \(z_j-c_j\) | 0 | \(-2/3\) ↑ | \(5/6\) | 0 | 20 |
Reading it. \(x_1 = 4\), \(s_2 = 2\), \(Z = 20\) — the corner \((4, 0)\) from L03 ✓.
Check the \(z_j-c_j\) row: \(z_2 = 5(\frac23)+0(\frac43) = \frac{10}{3}\), so \(z_2-c_2 = \frac{10}{3}-4 = -\frac23\) ✓.
Not optimal (\(-2/3 < 0\)). Entering: \(x_2\). Leaving: \(s_2\). Pivot = \(4/3\).
Iteration 2¶
Row 2 ← row 2 ÷ \(\frac43\), giving \((0,\ 1,\ -\frac18,\ \frac34,\ \frac32)\). Row 1 ← row 1 − \(\frac23\)×(new row 2).
Row 1 detail: \(s_1\): \(\frac16 - \frac23(-\frac18) = \frac16+\frac{1}{12} = \frac14\); \(s_2\): \(0 - \frac23(\frac34) = -\frac12\); RHS: \(4 - \frac23(\frac32) = 3\).
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | RHS |
|---|---|---|---|---|---|---|
| \(x_1\) | 5 | 1 | 0 | \(1/4\) | \(-1/2\) | 3 |
| \(x_2\) | 4 | 0 | 1 | \(-1/8\) | \(3/4\) | 3/2 |
| \(z_j-c_j\) | 0 | 0 | \(3/4\) | \(1/2\) | 21 |
All \(z_j - c_j \ge 0\) ⟹ OPTIMAL.
Exactly matching the graphical answer of L03 ✓.
5.5 Reading the Final Tableau¶
The final tableau contains far more than the answer.
The optimal solution¶
Basic variables take their RHS values; non-basic variables are zero:
Both slacks are zero ⟹ both constraints are binding, so both resources are fully consumed.
Shadow prices (dual values)¶
Interpretation. One additional unit of resource 1 raises the optimum by ₹0.75; one additional unit of resource 2 raises it by ₹0.50.
Verification. Change \(b_1\) from 24 to 25 and re-solve: the new intersection of \(6x_1+4x_2 = 25\) and \(x_1+2x_2 = 6\) is \(x_1 = 13/4\), \(x_2 = 11/8\), giving
The shadow price is exact. This tells management the maximum they should pay for an extra unit of each resource — one of the most commercially valuable outputs of an LP.
The dual solution¶
The shadow prices \((y_1, y_2) = (0.75, 0.5)\) are the optimal solution of the dual problem (L07). Note
— strong duality, verified numerically.
Detecting alternate optima¶
Here \(s_1\) and \(s_2\) have \(z_j-c_j = \frac34, \frac12 > 0\) — both strictly positive — so this optimum is unique, agreeing with L03's slope analysis.
5.6 Solved Problems¶
Problem 1 — Full simplex on the furniture problem¶
Solve \(\max\ Z = 450x_1+300x_2\) s.t. \(5x_1+3x_2\le120\), \(2x_1+4x_2\le90\), \(x_1,x_2\ge0\) by simplex, and extract the shadow prices.
Solution.
Standard form. \(5x_1+3x_2+s_1 = 120\), \(2x_1+4x_2+s_2 = 90\).
Iteration 0.
| Basis | \(c_B\) | \(x_1\) (450) | \(x_2\) (300) | \(s_1\) | \(s_2\) | RHS | Ratio |
|---|---|---|---|---|---|---|---|
| \(s_1\) | 0 | 5 | 3 | 1 | 0 | 120 | \(24\) ← |
| \(s_2\) | 0 | 2 | 4 | 0 | 1 | 90 | \(45\) |
| \(z_j-c_j\) | −450 | −300 | 0 | 0 | 0 |
Entering \(x_1\); ratios \(120/5 = 24\) and \(90/2 = 45\); leaving \(s_1\); pivot 5.
Iteration 1. Row 1 ÷ 5; row 2 ← row 2 − 2(new row 1).
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | RHS | Ratio |
|---|---|---|---|---|---|---|---|
| \(x_1\) | 450 | 1 | \(3/5\) | \(1/5\) | 0 | 24 | \(40\) |
| \(s_2\) | 0 | 0 | \(14/5\) | \(-2/5\) | 1 | 42 | \(15\) ← |
| \(z_j-c_j\) | 0 | −30 | 90 | 0 | 10 800 |
Check: \(z_2 = 450(\frac35) = 270\), so \(z_2-c_2 = 270-300 = -30\) ✓.
This is the corner \((24, 0)\) with \(Z = 10{,}800\) ✓ (matching L03's table).
Entering \(x_2\); ratios \(24 \div \frac35 = 40\) and \(42\div\frac{14}{5} = 15\); leaving \(s_2\); pivot \(14/5\).
Iteration 2. Row 2 ÷ \(\frac{14}{5}\) gives \((0,\ 1,\ -\frac17,\ \frac{5}{14},\ 15)\). Row 1 ← row 1 − \(\frac35\)(new row 2): \(s_1\): \(\frac15 - \frac35(-\frac17) = \frac15+\frac{3}{35} = \frac{10}{35} = \frac27\); \(s_2\): \(0 - \frac35\cdot\frac{5}{14} = -\frac{3}{14}\); RHS: \(24 - \frac35(15) = 15\).
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | RHS |
|---|---|---|---|---|---|---|
| \(x_1\) | 450 | 1 | 0 | \(2/7\) | \(-3/14\) | 15 |
| \(x_2\) | 300 | 0 | 1 | \(-1/7\) | \(5/14\) | 15 |
| \(z_j-c_j\) | 0 | 0 | \(600/7\) | \(75/7\) | 11 250 |
All \(z_j-c_j \ge 0\) ⟹ OPTIMAL.
Shadow prices.
Management interpretation. Carpentry hours are worth 8× more than finishing hours at the margin. If overtime carpentry can be bought for less than ₹85.71/hour, buy it; if finishing overtime costs more than ₹10.71/hour, do not.
Duality check. \(120(600/7) + 90(75/7) = \frac{72000+6750}{7} = \frac{78750}{7} = 11{,}250 = Z^{*}\) ✓.
Iteration count. 2 pivots for a 2-constraint problem — consistent with the \(2m\)–\(3m\) rule of L04.
Problem 2 — A three-variable problem¶
Solve \(\max\ Z = 3x_1+5x_2+4x_3\) s.t. \(2x_1+3x_2\le8\), \(2x_2+5x_3\le10\), \(3x_1+2x_2+4x_3\le15\).
Solution.
Iteration 0. Basis \(\{s_1,s_2,s_3\}\), \(Z=0\); \(z_j-c_j = (-3,-5,-4,0,0,0)\).
Entering \(x_2\) (most negative, \(-5\)). Column \(x_2 = (3, 2, 2)^T\); ratios \(\frac83 = 2.67\), \(\frac{10}{2}=5\), \(\frac{15}{2}=7.5\). Minimum in row 1 ⟹ \(s_1\) leaves, pivot 3.
Iteration 1. Row 1 ÷ 3: \((\frac23,\ 1,\ 0,\ \frac13,\ 0,\ 0\ |\ \frac83)\).
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | \(s_3\) | RHS | Ratio |
|---|---|---|---|---|---|---|---|---|---|
| \(x_2\) | 5 | \(2/3\) | 1 | 0 | \(1/3\) | 0 | 0 | \(8/3\) | — |
| \(s_2\) | 0 | \(-4/3\) | 0 | 5 | \(-2/3\) | 1 | 0 | \(14/3\) | \(14/15\) ← |
| \(s_3\) | 0 | \(5/3\) | 0 | 4 | \(-2/3\) | 0 | 1 | \(29/3\) | \(29/12\) |
| \(z_j-c_j\) | \(1/3\) | 0 | −4 | \(5/3\) | 0 | 0 | \(40/3\) |
Entering \(x_3\); minimum ratio \(14/15\) in row 2 ⟹ \(s_2\) leaves, pivot 5.
Iteration 2. Row 2 ÷ 5: \((-\frac{4}{15},\ 0,\ 1,\ -\frac{2}{15},\ \frac15,\ 0\ |\ \frac{14}{15})\). Row 3 ← row 3 − 4(new row 2).
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | \(s_3\) | RHS |
|---|---|---|---|---|---|---|---|---|
| \(x_2\) | 5 | \(2/3\) | 1 | 0 | \(1/3\) | 0 | 0 | \(8/3\) |
| \(x_3\) | 4 | \(-4/15\) | 0 | 1 | \(-2/15\) | \(1/5\) | 0 | \(14/15\) |
| \(s_3\) | 0 | \(41/15\) | 0 | 0 | \(-2/15\) | \(-4/5\) | 1 | \(89/15\) |
| \(z_j-c_j\) | \(-11/15\) | 0 | 0 | \(17/15\) | \(4/5\) | 0 | \(256/15\) |
Check \(z_1-c_1\): \(z_1 = 5(\frac23)+4(-\frac{4}{15})+0 = \frac{10}{3}-\frac{16}{15} = \frac{50-16}{15} = \frac{34}{15}\), so \(z_1-c_1 = \frac{34}{15}-3 = -\frac{11}{15}\) ✓.
Not optimal. Entering \(x_1\); ratios: row 1 \(\frac{8/3}{2/3} = 4\); row 2 has a negative entry (skip); row 3 \(\frac{89/15}{41/15} = \frac{89}{41} \approx 2.17\) ← minimum. Leaving \(s_3\).
Iteration 3. Pivot on \(\frac{41}{15}\). Row 3 ÷ \(\frac{41}{15}\); then eliminate.
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | \(s_3\) | RHS |
|---|---|---|---|---|---|---|---|---|
| \(x_2\) | 5 | 0 | 1 | 0 | \(15/41\) | \(8/41\) | \(-10/41\) | \(50/41\) |
| \(x_3\) | 4 | 0 | 0 | 1 | \(-6/41\) | \(5/41\) | \(4/41\) | \(62/41\) |
| \(x_1\) | 3 | 1 | 0 | 0 | \(-2/41\) | \(-12/41\) | \(15/41\) | \(89/41\) |
| \(z_j-c_j\) | 0 | 0 | 0 | \(45/41\) | \(24/41\) | \(11/41\) | \(765/41\) |
All \(z_j-c_j \ge 0\) ⟹ OPTIMAL.
Independent verification. Substitute into the original constraints:
All three binding — as expected with 3 constraints and 3 variables at a non-degenerate optimum.
Problem 3 — Recognising alternate optima in the tableau¶
A final tableau shows \(z_j - c_j = (0, 0, 0, 5/2, 0)\) where columns 1 and 2 are basic and columns 3, 4, 5 are non-basic. What do you conclude, and how do you find the second optimum?
Solution.
Diagnosis. Columns 3 and 5 are non-basic yet have \(z_j - c_j = 0\).
Why. Bringing \(x_3\) (or \(x_5\)) into the basis changes \(Z\) by \(-(z_j-c_j)\cdot\theta = 0\) — the objective is unchanged. So a different corner achieves the same optimal value.
Finding the second optimum. Perform one more pivot with \(x_3\) entering:
- Apply the minimum-ratio test to column 3 to find the leaving variable.
- Pivot as usual.
- The new tableau has the same \(Z\) but a different basic solution — the second optimal corner.
Describing all optima. With optimal corners \(\vec x^{(1)}\) and \(\vec x^{(2)}\), every point
is optimal, by the linearity argument of L03, Problem 3.
A caution. If the minimum-ratio test on column 3 gives no positive entries, then \(x_3\) can increase without limit at constant \(Z\) — the optimal set is an unbounded ray, not a bounded edge. The objective is still bounded; only the optimal set is infinite in extent.
Why report alternate optima. They give the decision-maker freedom to satisfy criteria the model omitted — supplier relationships, workforce stability, ease of implementation — at zero cost. A report that hides them gives away that freedom.
Problem 4 — Degeneracy in action¶
Solve \(\max\ Z = 3x_1+9x_2\) s.t. \(x_1+4x_2\le8\), \(x_1+2x_2\le4\), \(x_1,x_2\ge0\), noting the degeneracy.
Solution.
Iteration 0.
| Basis | \(c_B\) | \(x_1\) (3) | \(x_2\) (9) | \(s_1\) | \(s_2\) | RHS | Ratio |
|---|---|---|---|---|---|---|---|
| \(s_1\) | 0 | 1 | 4 | 1 | 0 | 8 | \(8/4 = 2\) ← |
| \(s_2\) | 0 | 1 | 2 | 0 | 1 | 4 | \(4/2 = 2\) ← |
| \(z_j-c_j\) | −3 | −9 | 0 | 0 | 0 |
A TIE in the minimum ratio (\(2 = 2\)) ⟹ degeneracy will occur.
Take row 1 (arbitrary choice); \(s_1\) leaves, pivot 4.
Iteration 1. Row 1 ÷ 4: \((\frac14,\ 1,\ \frac14,\ 0\ |\ 2)\). Row 2 ← row 2 − 2(new row 1): \((\frac12,\ 0,\ -\frac12,\ 1\ |\ 0)\).
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | RHS |
|---|---|---|---|---|---|---|
| \(x_2\) | 9 | \(1/4\) | 1 | \(1/4\) | 0 | 2 |
| \(s_2\) | 0 | \(1/2\) | 0 | \(-1/2\) | 1 | 0 ← degenerate |
| \(z_j-c_j\) | \(-3/4\) | 0 | \(9/4\) | 0 | 18 |
\(s_2 = 0\) while basic ⟹ DEGENERATE BFS.
Not optimal (\(z_1-c_1 = -\frac34\)). Entering \(x_1\); ratios: row 1 \(2\div\frac14 = 8\); row 2 \(0\div\frac12 = \mathbf{0}\) ← minimum. Leaving \(s_2\), pivot \(\frac12\).
Iteration 2. Row 2 ÷ \(\frac12\): \((1,\ 0,\ -1,\ 2\ |\ 0)\). Row 1 ← row 1 − \(\frac14\)(new row 2): \((0,\ 1,\ \frac12,\ -\frac12\ |\ 2)\).
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | RHS |
|---|---|---|---|---|---|---|
| \(x_2\) | 9 | 0 | 1 | \(1/2\) | \(-1/2\) | 2 |
| \(x_1\) | 3 | 1 | 0 | \(-1\) | 2 | 0 |
| \(z_j-c_j\) | 0 | 0 | \(3/2\) | \(3/2\) | 18 |
OPTIMAL. \(Z = 18\) — unchanged from iteration 1.
What happened — a degenerate pivot. The ratio was \(\theta = 0\), so the entering variable came in at value zero. The basis changed, but the point did not move and \(Z\) did not improve. This is a stalling step.
Geometrically. Three lines pass through \((0,2)\): \(x_1+4x_2 = 8\), \(x_1+2x_2 = 4\) and \(x_1 = 0\). With three constraints meeting at a corner in 2-D, the corner is over-determined and corresponds to multiple bases — exactly what degeneracy means.
Why cycling is the theoretical risk. If a chain of such zero-improvement pivots returned to a previously seen basis, the algorithm would loop forever. Here it terminated after one degenerate pivot; Bland's rule (L04) guarantees this in general.
Practical note. Degeneracy is very common — every transportation problem with a degenerate basic solution (L09) exhibits it — but harmless. Recognise it, do not fear it.
Problem 5 — Using shadow prices for a business decision¶
From the furniture problem's optimal tableau, \(y_1 = ₹85.71\) per carpentry hour and \(y_2 = ₹10.71\) per finishing hour. A supplier offers 10 extra carpentry hours for ₹700 total. Should the firm accept? What about 20 extra finishing hours for ₹150?
Solution.
Offer 1 — carpentry.
But check the validity range. Shadow prices hold only while the basis stays optimal. From the final tableau, the \(s_1\) column is \((\frac27,\ -\frac17)^T\). Increasing \(b_1\) by \(\Delta\) changes the basic variables to
Feasibility requires \(x_2 \ge 0\):
\(\Delta = 10\) is well within range ✓, so the ₹85.71 rate applies fully.
Confirming: new plan \(x_1 = 15+\frac{20}{7} = 17.857\), \(x_2 = 15-\frac{10}{7} = 13.571\), giving
Offer 2 — finishing.
Range check. The \(s_2\) column is \((-\frac{3}{14},\ \frac{5}{14})^T\). Increasing \(b_2\) by \(\Delta\):
\(\Delta = 20\) is within range ✓.
A crucial caveat if both offers are accepted together. Shadow prices are marginal rates valid for one-at-a-time changes. Simultaneous changes require the 100 % rule:
Since the fractions sum to less than 1, the basis remains optimal and both shadow prices remain valid, so the combined gain of ₹157.14 + ₹64.29 = ₹221.43 is correct.
This is the kind of concrete, defensible recommendation that makes LP valuable to management, and it comes entirely from the final tableau at no extra computational cost.
5.7 Practice Problems¶
- Solve by simplex: \(\max\ 4x_1+3x_2\) s.t. \(2x_1+x_2\le10\), \(x_1+3x_2\le15\). [Ans: \(x_1=3,x_2=4\), \(Z=24\)]
- From the L05 example's final tableau, what is the shadow price of constraint 2? [Ans: 1/2]
- Perform one pivot on: pivot element 3 in row 2, column 1, with row 2 \(= (3, 6, 1, 0 \mid 9)\).
- A final tableau has \(z_j-c_j = (0,0,4,0)\) with column 4 non-basic. Interpret.
- Verify the duality check \(\vec b^{T}\vec y = Z^{*}\) for Problem 1 of §5.
- Solve \(\max\ 2x_1+3x_2\) s.t. \(x_1+x_2\le4\), \(x_1+3x_2\le6\) and identify any degeneracy.
- If a shadow price is 0, what does that tell you about the constraint?
5.8 Summary¶
- Build the tableau from standard form with the slacks as the initial basis; work in fractions.
- Pivot: divide the pivot row by the pivot element, then eliminate the pivot column from every other row. Check the unit column, non-negative RHS and improved \(Z\) each time.
- Read from the final tableau: optimal values (basic RHS), slacks (zero ⟹ binding), and shadow prices in the slack columns' \(z_j-c_j\) entries.
- Shadow price = the marginal value of one extra unit of a resource; it is exactly the dual variable, and \(\vec b^T\vec y = Z^{*}\) (strong duality).
- A non-basic variable with \(z_j-c_j = 0\) at optimality signals alternate optima — always report them.
- Degeneracy (a basic variable equal to zero, arising from a tie in the ratio test) causes a \(\theta = 0\) pivot that changes the basis but not the solution. Common and harmless in practice.
- Shadow prices are valid only within a range; simultaneous changes are checked by the 100 % rule (the fractions of the allowable ranges must sum to at most 1).
Next lesson: L06 — Big-M and two-phase methods, and the special cases.
Practise now: unit1-lp-lab.html → Simplex Stepper: enter any LP and step through the tableaus
one pivot at a time, with the entering/leaving choices and ratios highlighted.