The Simplex Method II: The Tableau Algorithm

Learning outcomes

Set up the initial simplex tableau from any linear programme.
Execute pivot operations accurately, with three checks after every pivot.
Read the optimal solution, the slack values and the shadow prices from the final tableau.
Verify a solution independently, including the duality check b^Ty = Z*.
Recognise alternate optima, and degeneracy, from the final tableau alone.
Say which cell of the tableau answers each question, and over what range a shadow price stays valid.

Start here

The idea, first

A tableau is your constraint equations written as a grid, with one scoring row underneath. Each row is an equation, each column a variable, the last column the resources you hold. The score row — labelled zⱼ − cⱼ, and built from scratch in section 1 — asks one question of every variable currently sitting at zero: if I let this grow by one unit, what happens to profit? A negative entry means profit would rise, so work remains. When every entry is zero or positive, nothing can improve you and you stop.

A pivot swaps one variable in and one out. Pick a column (the variable promising most), pick a row (the constraint that runs out first), divide that row by the number where they cross, then clear the column everywhere else. That is Gauss–Jordan elimination, which you already know; the only new content is which row and column, and section 2 gives the two rules that decide.

The payoff comes at the end. The finished tableau also says what an extra hour of machine time is worth in rupees, whether an equally good plan exists, and how far a resource can be pushed before the answer changes shape. Section 4 gives the exact cell to read for each of those questions.

1. Setting up the tableau

Everything begins with standard form from L02: every constraint an equation, every right-hand side non-negative. With all ≤ constraints the slack columns form an identity matrix, so the slacks hand you a starting basis at no work at all; when they do not — with ≥ or = constraints — you need the artificial variables of L06.

Definition

Basis, basic and non-basic variables

With m constraints and n variables in standard form, a basis is a choice of m variables whose columns are linearly independent. Those m are the basic variables and they are the ones named in the Basis column of the tableau; the remaining n − m are non-basic and are held at zero. Solving the equations for the basic variables gives the basic feasible solution of L04 — one corner of the feasible region. Each pivot exchanges one basic variable for one non-basic one, which is exactly why the algorithm hops from corner to corner.

Definition

Simplex tableau

A table whose rows are the constraint equations expressed in the current basis, whose columns are the decision and slack variables, and whose last row records zⱼ − cⱼ for every column together with the objective value Z.

cⱼ →		c₁	c₂	⋯	cₙ
Basis	c_B	x₁	x₂	⋯	xₙ	RHS
x_B₁	c_B₁	a₁₁	a₁₂		a₁ₙ	b₁
⋮
x_Bₘ	c_Bₘ	aₘ₁	aₘ₂		aₘₙ	bₘ
zⱼ − cⱼ		Δ₁	Δ₂		Δₙ	Z

The c_B column holds the profit coefficient of whichever variable occupies that basis row, and it is all the score row needs. For column j, zⱼ = Σᵢ c_Bᵢ aᵢⱼ is the profit you would have to give up, inside the current basis, to make room for one unit of xⱼ; cⱼ is the profit that one unit would earn. So zⱼ − cⱼ is given up minus gained, and a negative entry means the trade is worth making. That single sign convention drives the whole algorithm.

At iteration 0 the basic variables are slacks carrying zero profit, so every c_Bᵢ = 0, every zⱼ = 0, and the score row reads simply −cⱼ. The negated objective coefficients you see in a first tableau are therefore a consequence of the formula, not a convention to memorise — a useful thing to know, because it means you can always rebuild the row if you lose track of it.

2. The pivot operation, step by step

With entering column k and leaving row r, the pivot element is p = a_rk and the arithmetic is fixed:

new pivot row = old pivot row ÷ pstep 1

new row i = old row i − a_ik × (new pivot row)step 2, for every other row i

Then replace the basis label in row r by x_k and its c_B entry by c_k, and recompute the score row. Geometrically, as L04 showed, you have walked along one edge of the polytope to an adjacent corner.

Key idea Three checks after every pivot: (1) the pivot column reads (0, …, 0, 1, 0, …, 0)^T with the 1 in the pivot row; (2) every RHS value is ≥ 0; (3) Z has improved — or held exactly steady, which is legal and is explained in section 5. Run these three every time and simplex errors become rare. A failure of check 1 means you eliminated with the wrong multiple; a failure of check 2 means you chose the wrong row.

Common trap Work in fractions, never decimals. Tableaus routinely throw up 2/3 and 5/14; rounding accumulates and eventually corrupts the sign of a zⱼ − cⱼ entry — at which point the method stops at a non-optimal tableau, with nothing in the output to warn you.

3. A complete trace: max Z = 5x₁ + 4x₂

This is the problem solved graphically in L03, so we know the destination: (3, 1.5) with Z = 21. Watching the algebra arrive there is the best confidence check on the machinery.

max Z = 5x₁ + 4x₂subject to 6x₁ + 4x₂ ≤ 24, x₁ + 2x₂ ≤ 6, x₁, x₂ ≥ 0

6x₁ + 4x₂ + s₁ = 24, x₁ + 2x₂ + s₂ = 6standard form, with Z = 5x₁ + 4x₂ + 0s₁ + 0s₂

Iteration 0. Basis {s₁, s₂}, so x₁ and x₂ are non-basic and equal zero: this is the origin, with s₁ = 24, s₂ = 6 and Z = 0. Every c_B is 0, so the score row is just −cⱼ, namely (−5, −4, 0, 0), and x₁ enters on the most negative entry, −5. The ratio test divides each row's RHS by that row's entry in the x₁ column, over strictly positive entries only: 24 ÷ 6 = 4 and 6 ÷ 1 = 6. The smaller is 4, in row 1, so s₁ leaves and the pivot element is the 6 where the x₁ column meets row 1.

Iteration 1. Row 1 ÷ 6 gives (1, 4/6, 1/6, 0 | 24/6) = (1, 2/3, 1/6, 0 | 4). Row 2 has a 1 in the x₁ column, so row 2 ← row 2 − 1 × (new row 1): x₂ becomes 2 − 2/3 = 4/3, s₁ becomes 0 − 1/6 = −1/6, s₂ stays 1, and the RHS becomes 6 − 4 = 2. Now c_B = (5, 0), so z₂ = 5(2/3) + 0(4/3) = 10/3 and z₂ − c₂ = 10/3 − 4 = −2/3, while the s₁ column gives 5(1/6) + 0(−1/6) − 0 = 5/6. The objective is Z = 5(4) + 0(2) = 20 — the corner (4, 0) of L03. The −2/3 is still negative, so x₂ enters; ratios 4 ÷ (2/3) = 6 and 2 ÷ (4/3) = 3/2, so s₂ leaves on a pivot of 4/3.

Iteration 2. Dividing row 2 by 4/3 means multiplying it by 3/4: x₂ becomes 1, s₁ becomes (−1/6)(3/4) = −1/8, s₂ becomes (1)(3/4) = 3/4, and the RHS becomes 2 × 3/4 = 3/2. So the new row 2 is (0, 1, −1/8, 3/4 | 3/2). Row 1 carries 2/3 in the x₂ column, so row 1 ← row 1 − (2/3) × (new row 2): s₁ becomes 1/6 − (2/3)(−1/8) = 1/6 + 1/12 = 2/12 + 1/12 = 1/4, s₂ becomes 0 − (2/3)(3/4) = −1/2, and the RHS becomes 4 − (2/3)(3/2) = 4 − 1 = 3.

Finish the score row with c_B = (5, 4). The two decision columns are basic and so score 0 automatically. For the slacks, z_s₁ − c_s₁ = 5(1/4) + 4(−1/8) − 0 = 5/4 − 1/2 = 3/4 and z_s₂ − c_s₂ = 5(−1/2) + 4(3/4) − 0 = −5/2 + 3 = 1/2. Both are positive, so no column can raise the objective and the tableau is optimal at Z = 5(3) + 4(3/2) = 15 + 6 = 21. Those two fractions, 3/4 and 1/2, are worth remembering: section 4 shows they are the price of the two resources.

x₁* = 3, x₂* = 3/2, Z* = 21matching the graphical solution of L03 exactly

4. Reading the final tableau

You now have a grid of fractions and a claim that it is optimal. This section turns those fractions into answers. Six separate questions can be settled from the last tableau with no further calculation at all, and each answer lives at a fixed address. Learn the six addresses once, and reading a tableau takes seconds.

Question	Where to look	Answer in the tableau above
What should we make?	The RHS column, on each row whose Basis label is a decision variable.	x₁ = 3, x₂ = 3/2
What does it earn?	The RHS entry of the zⱼ − cⱼ row.	Z* = 21
Which resources ran out?	The Basis column. A slack that is not listed is non-basic, hence zero, hence its constraint is binding.	Neither s₁ nor s₂ is listed, so both constraints bind
What is one more unit of resource i worth?	The zⱼ − cⱼ entry in the sᵢ column.	y₁ = 3/4, y₂ = 1/2
Is there another plan just as good?	A zⱼ − cⱼ of exactly 0 in a non-basic column.	3/4 and 1/2, neither zero, so the optimum is unique
Is this corner degenerate?	A 0 in the RHS column on a basic row.	3 and 3/2, neither zero, so it is not

The optimal solution. Basic variables take their RHS values, non-basic variables are zero: x₁ = 3, x₂ = 3/2, s₁ = 0, s₂ = 0. Both slacks vanish, so both constraints are binding and neither resource has spare capacity.

Definition

Binding constraint

A constraint is binding at the optimum when it holds with equality there, which happens exactly when its slack variable is zero. A non-basic slack is zero by construction, so the fastest test is whether sᵢ appears in the Basis column at all: absent means binding and the resource is fully consumed; present means the RHS value on that row is how much is left over.

Definition

Shadow price

The shadow price of constraint i is the zⱼ − cⱼ entry in the column of its slack sᵢ: the rate at which the optimum rises per extra unit of resource i. Shadow prices live in the slack columns only — the score entries under x₁ and x₂ are not prices of anything.

y₁ = 3/4 = 0.75, y₂ = 1/2 = 0.50the two entries you computed at the end of iteration 2

The rate is exact, and you can check it in three lines. Raise b₁ from 24 to 25 and re-solve by hand. Both constraints still bind, so x₁ + 2x₂ = 6 gives x₁ = 6 − 2x₂; substituting into 6x₁ + 4x₂ = 25 gives 36 − 12x₂ + 4x₂ = 25, hence 8x₂ = 11, x₂ = 11/8 and x₁ = 6 − 11/4 = 13/4. The new objective is Z = 5(13/4) + 4(11/8) = 65/4 + 11/2 = 16.25 + 5.50 = 21.75, which is 21 + 0.75 exactly. A shadow price is not an estimate: it is the slope of Z* against b₁, and it tells management the maximum worth paying for one more unit of that resource.

A shadow price of zero. The reverse reading matters just as much. If sᵢ is basic, its column is a unit column and its zⱼ − cⱼ is 0, so resource i has a shadow price of zero — and its RHS entry says how much of it is sitting unused. Buying more of a resource you have not finished using adds nothing, at any price. Scarcity and marginal value are the same fact read from two different columns. (The one exception is a basic slack whose RHS is 0, which is the degenerate case of section 5.)

The dual solution. The pair (y₁, y₂) = (0.75, 0.5) is the optimal solution of the dual problem of L07, and you can already test it:

24 y₁ + 6 y₂ = 24(0.75) + 6(0.5) = 18 + 3 = 21 = Z*strong duality, verified from the tableau

Note Run this check on every problem you solve. Multiply each original right-hand side by its own shadow price, add, and compare with Z*. If b^Ty ≠ Z* there is an arithmetic slip somewhere in your pivots, and the check finds it in ten seconds without your having to redo one.

Alternate optima. The rule is a one-liner: a non-basic variable with zⱼ − cⱼ = 0 at optimality implies alternate optima, because bringing that column into the basis changes Z by −(zⱼ − cⱼ)·θ = 0 whatever θ turns out to be. Read it only in the non-basic columns: a basic column always scores 0, and that zero carries no information. Here the two non-basic columns are s₁ and s₂, carrying 3/4 and 1/2, both strictly positive, so this optimum is unique — agreeing with the slope analysis of L03.

Degeneracy. The sixth address in the table is the RHS column. Both basic values here, 3 and 3/2, are strictly positive, so this corner is non-degenerate. What a zero there would have meant is the subject of the next section.

5. Two signals the tableau sends

Two flags are worth spotting instantly. Both are an unexpected zero, but they sit in different places and mean quite different things: a zero in the score row under a non-basic column means alternate optima, while a zero in the RHS column of a basic row means degeneracy. Confusing the two is the most common misreading of a finished tableau, so fix the two addresses in your mind before going further.

Definition

Degenerate basic feasible solution

A basic feasible solution is degenerate when at least one basic variable equals zero — that is, when some row of the tableau names a variable in the Basis column but carries 0 in the RHS column. It arises from a tie in the minimum-ratio test, and the pivot that follows moves a distance of θ = 0: the basis changes, the corner does not, and Z stands still.

Report alternate optima, because they let the decision-maker satisfy criteria the model omitted — supplier relationships, workforce stability, ease of implementation — at zero cost in profit. Quietly picking one of several equally good plans throws that freedom away.

6. Solved problems

1 Full simplex on the furniture problem

Solve max Z = 450x₁ + 300x₂ subject to 5x₁ + 3x₂ ≤ 120, 2x₁ + 4x₂ ≤ 90, x₁, x₂ ≥ 0, and extract the shadow prices.

Step 1 — Standard form and iteration 0

5x₁ + 3x₂ + s₁ = 120 and 2x₁ + 4x₂ + s₂ = 90, where s₁ is spare carpentry and s₂ spare finishing hours. Every c_B is 0, so the score row is (−450, −300, 0, 0) and x₁ enters on −450. Ratios 120 ÷ 5 = 24 and 90 ÷ 2 = 45, so the smaller sends s₁ out on a pivot of 5.

Step 2 — First pivot

Row 1 ÷ 5 gives (1, 3/5, 1/5, 0 | 24). Row 2 holds a 2 in the x₁ column, so row 2 ← row 2 − 2 × (new row 1): x₂ becomes 4 − 6/5 = 14/5, s₁ becomes 0 − 2/5 = −2/5, s₂ stays 1, and the RHS becomes 90 − 48 = 42. This is the corner (24, 0) with Z = 450(24) = 10,800, matching L03 — all 120 carpentry hours used and 42 finishing hours idle. With c_B = (450, 0), z₂ = 450(3/5) + 0(14/5) = 270, so z₂ − c₂ = 270 − 300 = −30 and x₂ must enter. Ratios 24 ÷ (3/5) = 40 and 42 ÷ (14/5) = 42 × 5/14 = 15, so s₂ leaves on a pivot of 14/5.

Step 3 — Second pivot, and where the shadow prices come from

Dividing row 2 by 14/5 means multiplying by 5/14: s₁ becomes (−2/5)(5/14) = −1/7, s₂ becomes 5/14, and the RHS becomes 42 × 5/14 = 15, giving (0, 1, −1/7, 5/14 | 15). Row 1 holds 3/5 in the x₂ column, so row 1 ← row 1 − (3/5) × (new row 2): s₁ becomes 1/5 − (3/5)(−1/7) = 1/5 + 3/35 = 7/35 + 3/35 = 10/35 = 2/7, s₂ becomes 0 − (3/5)(5/14) = −3/14, and the RHS becomes 24 − (3/5)(15) = 24 − 9 = 15.

Now c_B = (450, 300), and the two slack columns give the score entries directly: z_s₁ − c_s₁ = 450(2/7) + 300(−1/7) = (900 − 300)/7 = 600/7, and z_s₂ − c_s₂ = 450(−3/14) + 300(5/14) = (−1350 + 1500)/14 = 150/14 = 75/7. Both are positive and the two decision columns score 0, so the tableau is optimal.

Step 4 — Interpreting the prices, and the duality check

y₁ = 600/7 = ₹85.71 per carpentry hour and y₂ = 75/7 = ₹10.71 per finishing hour. Carpentry is worth 600/75 = 8 times as much at the margin, so buy carpentry overtime at anything below ₹85.71 an hour and refuse finishing overtime above ₹10.71. The duality check confirms the whole tableau in one line: 120(600/7) + 90(75/7) = (72,000 + 6,750)/7 = 78,750/7 = 11,250 = Z* ✓. Had that come out to anything else, one of the pivots above would contain a slip.

x₁* = 15 tables, x₂* = 15 chairs, Z* = ₹11,250; shadow prices ₹85.71 and ₹10.71 per hour

2 A three-variable problem

Solve max Z = 3x₁ + 5x₂ + 4x₃ subject to 2x₁ + 3x₂ ≤ 8, 2x₂ + 5x₃ ≤ 10, 3x₁ + 2x₂ + 4x₃ ≤ 15.

Pivot 1 — x₂ enters

Iteration 0 has basis {s₁, s₂, s₃}, Z = 0 and score row (−3, −5, −4, 0, 0, 0), so x₂ enters on −5. Its column is (3, 2, 2)^T, giving ratios 8/3 ≈ 2.67, 10/2 = 5 and 15/2 = 7.5; row 1 wins, s₁ leaves, pivot 3. Row 1 ÷ 3 gives (2/3, 1, 0, 1/3, 0, 0 | 8/3); rows 2 and 3 each carry 2 in the x₂ column, so both lose twice the new row 1, sending row 2 to (−4/3, 0, 5, −2/3, 1, 0 | 14/3) and row 3 to (5/3, 0, 4, −2/3, 0, 1 | 29/3).

Pivot 2 — x₃ enters

With c_B = (5, 0, 0) the score row becomes (1/3, 0, −4, 5/3, 0, 0 | 40/3), so x₃ enters on −4. Its column is (0, 5, 4)^T: the 0 in row 1 is skipped, because only strictly positive entries yield a ratio, leaving (14/3) ÷ 5 = 14/15 ≈ 0.93 and (29/3) ÷ 4 = 29/12 ≈ 2.42. Row 2 wins, s₂ leaves, pivot 5.

Pivot 3 — x₁ enters

Row 2 ÷ 5 gives (−4/15, 0, 1, −2/15, 1/5, 0 | 14/15), and row 3 ← row 3 − 4 × (new row 2) puts 5/3 + 16/15 = 25/15 + 16/15 = 41/15 in the x₁ column, with RHS 29/3 − 56/15 = 145/15 − 56/15 = 89/15. Now c_B = (5, 4, 0), so z₁ = 5(2/3) + 4(−4/15) + 0 = 50/15 − 16/15 = 34/15 and z₁ − c₁ = 34/15 − 3 = −11/15: x₁ enters. Row 2 carries −4/15 and is skipped; the ratios are (8/3) ÷ (2/3) = 4 and (89/15) ÷ (41/15) = 89/41 ≈ 2.17, so s₃ leaves on a pivot of 41/15.

Reading and verifying the final tableau

The last score row is (0, 0, 0, 45/41, 24/41, 11/41 | 765/41), every entry ≥ 0, so we stop. No slack appears in the Basis column, so all three constraints are binding — and substituting confirms it: 2(2.171) + 3(1.220) = 4.342 + 3.659 = 8.00, then 2(1.220) + 5(1.512) = 2.439 + 7.561 = 10.00, then 3(2.171) + 2(1.220) + 4(1.512) = 6.512 + 2.439 + 6.049 = 15.00. The objective agrees as well: 3(2.171) + 5(1.220) + 4(1.512) = 6.512 + 6.098 + 6.049 = 18.659 = 765/41 ✓.

Three variables and three binding constraints is exactly what a non-degenerate optimum in three dimensions should look like. The duality check closes the loop: with shadow prices 45/41, 24/41 and 11/41 read from the slack columns, 8(45/41) + 10(24/41) + 15(11/41) = (360 + 240 + 165)/41 = 765/41 = Z* ✓.

x₁ = 89/41 = 2.171, x₂ = 50/41 = 1.220, x₃ = 62/41 = 1.512, Z* = 765/41 = 18.659

3 Recognising alternate optima

A final tableau shows zⱼ − cⱼ = (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?

Diagnosis

Take the score row entry by entry. Columns 1 and 2 read 0, but they are basic, and a basic column always scores 0 — those two zeros say nothing at all. Column 4 reads 5/2, strictly positive, so nothing there. Columns 3 and 5 are non-basic and yet also read 0, and that is the signature of alternate optima. Bringing x₃ or x₅ into the basis changes Z by −(zⱼ − cⱼ)·θ = 0 for any θ, so a different corner reaches exactly the same value.

Finding it, and describing all optima

Pivot once more with x₃ entering: ratio-test column 3, pivot, and the new tableau has the same Z with a different basic solution. With corners x⁽¹⁾ and x⁽²⁾, every x(λ) = λx⁽¹⁾ + (1 − λ)x⁽²⁾, λ in [0, 1], is optimal, by the linearity argument of L03. Should that ratio test find no positive entry, the optimal set is an unbounded ray, not an edge.

Alternate optima exist; pivot x₃ in for the second corner and report the whole segment between them

4 Degeneracy in action

Solve max Z = 3x₁ + 9x₂ subject to x₁ + 4x₂ ≤ 8, x₁ + 2x₂ ≤ 4, x₁, x₂ ≥ 0, noting the degeneracy.

Iteration 0 — a tie in the ratio test

Every c_B is 0, so the score row is (−3, −9, 0, 0) and x₂ enters on −9. The ratios are 8 ÷ 4 = 2 and 4 ÷ 2 = 2 — a tie, and a tie in the minimum-ratio test guarantees that the next basic feasible solution will be degenerate: both rows hit their limit at once, so whichever one you keep will hold a variable at zero. Take row 1 arbitrarily: s₁ leaves on a pivot of 4.

Iteration 1 — the degenerate basic feasible solution

Row 1 ÷ 4 gives (1/4, 1, 1/4, 0 | 2). Row 2 carries 2 in the x₂ column, so row 2 ← row 2 − 2 × (new row 1): x₁ becomes 1 − 1/2 = 1/2, s₁ becomes 0 − 1/2 = −1/2, s₂ stays 1, and the RHS becomes 4 − 4 = 0. There it is: s₂ is named in the Basis column but its RHS is 0, so this is a degenerate basic feasible solution. With c_B = (9, 0), z₁ = 9(1/4) = 9/4 and z₁ − c₁ = 9/4 − 3 = −3/4, so the score row is (−3/4, 0, 9/4, 0 | 18) and we are not finished.

Iteration 2 — a pivot of length zero

x₁ enters on −3/4. Ratios: 2 ÷ (1/4) = 8 and 0 ÷ (1/2) = 0, so s₂ leaves on a pivot of 1/2. Row 2 ÷ (1/2) means doubling it, giving (1, 0, −1, 2 | 0); row 1 ← row 1 − (1/4) × (new row 2) gives s₁ = 1/4 + 1/4 = 1/2, s₂ = 0 − 1/2 = −1/2 and RHS 2, so row 1 is (0, 1, 1/2, −1/2 | 2). With c_B = (9, 3), z_s₁ − c_s₁ = 9(1/2) + 3(−1) = 3/2 and z_s₂ − c_s₂ = 9(−1/2) + 3(2) = 3/2: optimal, at Z = 9(2) + 3(0) = 18, unchanged from iteration 1. The entering variable arrived at value zero, so the basis changed but the point did not move at all.

The geometry, and how to spot it later

Three lines meet at (0, 2): x₁ + 4x₂ = 8, x₁ + 2x₂ = 4 and x₁ = 0. In two dimensions a corner needs only two constraints to pin it down, so a corner met by three is over-determined and corresponds to several different bases — that is precisely what degeneracy means, and why the simplex method can change basis without changing point. The final tableau still carries the evidence: x₁ is basic with an RHS of 0. Had a chain of such zero-length pivots returned to a basis already visited, the method would loop forever; Bland's rule from L04 rules that out. Degeneracy is common and, in practice, harmless.

x₁* = 0, x₂* = 2, Z* = 18, reached through one degenerate pivot that did not improve Z

5 Using shadow prices for a business decision

From the furniture tableau, y₁ = ₹85.71 per carpentry hour and y₂ = ₹10.71 per finishing hour. A supplier offers 10 extra carpentry hours for ₹700 in total. Accept? And 20 extra finishing hours for ₹150?

Offer 1 — carpentry, and its validity range

Work from the fraction, not the rounded rupee figure: value gained = 10 × 600/7 = 6000/7 = ₹857.14, against a cost of ₹700, so the net gain is 1100/7 = ₹157.14 and the answer is accept.

But a shadow price holds only for as long as the current basis stays optimal, so check the range before quoting it. The s₁ column of the final tableau is (2/7, −1/7)^T, and those two numbers are exactly the rates at which the basic variables respond to b₁: raising b₁ by Δ gives x₁ = 15 + (2/7)Δ and x₂ = 15 − (1/7)Δ. Only x₂ can fall, so feasibility needs 15 − Δ/7 ≥ 0, that is Δ ≤ 105 — the allowable increase. Δ = 10 is well inside it. Confirming directly: x₁ = 15 + 20/7 = 17.857 and x₂ = 15 − 10/7 = 13.571, so Z = 450(17.857) + 300(13.571) = 8,035.7 + 4,071.4 = ₹12,107.1 = 11,250 + 857.14 ✓.

Offer 2 — finishing

Value gained = 20 × 75/7 = 1500/7 = ₹214.29 against ₹150, so the net gain is 450/7 = ₹64.29: accept. Range check the same way: the s₂ column is (−3/14, 5/14)^T, so x₁ = 15 − (3/14)Δ and x₂ = 15 + (5/14)Δ. Here x₁ is the one that falls, and x₁ ≥ 0 forces Δ ≤ 70 — the allowable increase for b₂. Δ = 20 is inside it ✓.

Taking both offers together — the 100 % rule

Each range above was computed on the assumption that only that right-hand side moves. Shadow prices are marginal rates, valid one change at a time, so two accepted offers need one more test. Express each change as a fraction of its own allowable increase and add them: 10/105 + 20/70 = 0.095 + 0.286 = 0.381. Because the fractions sum to at most 1, the basis is guaranteed to stay optimal, both shadow prices stay valid, and the combined gain of ₹157.14 + ₹64.29 = ₹221.43 is exact rather than approximate. That is the 100 % rule: it is a sufficient test, so a sum above 1 does not prove the basis breaks — it only means you must re-solve to find out.

Accept both. Combined net gain ₹221.43, verified by the 100 % rule

7. Where this is used

Electricity markets

Nodal wholesale prices are the shadow prices of grid and generation constraints, recomputed every few minutes.

Refinery blending

Daily crude-slate LPs price each distillation unit, so planners know what an extra throughput hour is worth.

Hospital capacity

Shadow prices rank theatre hours, beds and staff by treated patients per rupee spent.

Airline revenue

Bid prices — shadow prices on seat capacity — decide whether to sell the next seat at the fare offered.

Agricultural planning

Cropping models price irrigation water and land, costing a canal extension in rupees of output.

Cloud capacity

LP relaxations of placement problems price scarce GPU and memory, steering chargeback and purchasing.

8. Common mistakes

Working in decimals. Rounding 2/3 to 0.67 across pivots corrupts the score-row signs and stops the method at the wrong tableau.
Taking the largest ratio. The minimum ratio finds the constraint that runs out first; a larger one gives a negative RHS next tableau — which is why check 2 exists.
Ratio-testing non-positive entries. Only strictly positive entries give ratios; zero and negative entries must be skipped, not counted as zero or as huge.
Forgetting the c_B column. Label and coefficient both change at a pivot; update one but not the other and every later zⱼ − cⱼ is wrong.
Reading a shadow price from the wrong column. Shadow prices live in the slack columns only. The zⱼ − cⱼ entries under x₁ and x₂ are zero at optimality simply because those columns are basic, and they price nothing.
Stopping at a zero without comment. A non-basic column with zⱼ − cⱼ = 0 means alternate optima; reporting one plan hides real flexibility. A zero under a basic column means nothing at all.
Quoting a shadow price outside its range. Compute the allowable increase from the slack column first, and use the 100 % rule when several right-hand sides move together.
Panicking at degeneracy. A zero RHS in a basic row, and a pivot that does not improve Z, are normal.
Skipping the duality check. b^Ty = Z* costs one line and catches most tableau errors at once.

9. Practice problems

Solve by simplex: max 4x₁ + 3x₂ subject to 2x₁ + x₂ ≤ 10, x₁ + 3x₂ ≤ 15. [Ans: x₁ = 3, x₂ = 4, Z = 24]
From the final tableau of the trace in section 3, what is the shadow price of constraint 2, and which column did you read it from? [Ans: 1/2, from the s₂ column of the score row]
Perform one pivot on the pivot element 3 in row 2, column 1, where row 2 = (3, 6, 1, 0 | 9).
A final tableau has zⱼ − cⱼ = (0, 0, 4, 0) with column 4 non-basic. Interpret it.
Verify the duality check b^Ty = Z* for the furniture problem (solved problem 1).
Solve max 2x₁ + 3x₂ subject to x₁ + x₂ ≤ 4, x₁ + 3x₂ ≤ 6, and identify any degeneracy.
If a shadow price is 0, what does that tell you about the constraint?

10. Summary

What you can now do, without help:

Build iteration 0 from standard form — slacks in the basis, and the score row computed from zⱼ = Σ c_Bᵢ aᵢⱼ rather than copied from a remembered sign rule — and keep every entry as a fraction.
Run a pivot end to end: most negative zⱼ − cⱼ picks the column, the minimum ratio over strictly positive entries picks the row, divide the pivot row by the pivot element, eliminate the column from every other row, relabel the basis and c_B, then run the three checks — unit column, RHS ≥ 0, Z no worse.
Say when to stop — every zⱼ − cⱼ ≥ 0 — and read x*, the slack values and Z* straight off the final tableau.
Name the binding constraints from the Basis column alone: a slack that is absent is zero, so its resource is fully consumed.
Quote a shadow price from the zⱼ − cⱼ entry in each slack column, explain it as the most a manager should pay for one more unit, and recognise that a basic slack means a shadow price of zero.
Check your own arithmetic in one line with b^Ty = Z*, knowing that a mismatch means a slipped pivot rather than a failure of the theory.
Tell the two zeros apart: zⱼ − cⱼ = 0 in a non-basic column means alternate optima, which you always report; a 0 in the RHS column of a basic row means degeneracy, which costs one θ = 0 pivot and nothing more.
State the range over which a shadow price is valid, reading it off the slack column, and combine several right-hand-side changes with the 100 % rule.

Next lesson L06 takes on constraints that hand you no free starting basis: the Big-M and two-phase methods, and the special cases of infeasibility, unboundedness and redundancy.