Teaching objectives
And what about problems with so many variables that you cannot draw them any more? This lab picks up where Linear optimization ends: there the optimum was found by looking at the feasible region, and here we build the machinery that finds it without seeing it — the simplex method — and then turn the whole problem inside out to reach shadow prices and the dual problem. The same workshop of tables and chairs runs through the first 23 rooms, and always ends at €36; the last room applies everything to a complete three-product problem, like those in exams. Aimed at University level.
What you learn
- Recall what a linear optimization problem is, what the feasible region is, and why the optimum always sits at a vertex (room 1).
- Turn a problem around so it fits the method: minimizing as maximizing, and ≥ as ≤ (rooms 2 and 5).
- Put a problem in standard form with slack and surplus variables, and tell basic from non-basic variables (rooms 3, 4 and 6).
- Understand why testing every vertex is hopeless: their number grows exponentially with the size of the problem (room 7).
- Build the simplex tableau from a word problem and read it: what is in each row, each column and the Z row (room 8).
- Choose the entering column and the leaving row, and see what that means on the picture: a jump from a vertex to its neighbour (rooms 9 and 10).
- Apply the Gauss-Jordan step to the tableau, first watching it calculation by calculation and then doing it in full, row by row (rooms 11 and 13), having first decided who enters and who leaves (room 12).
- See the simplex method for what it is — a walk across vertices that never steps back — and check that it works exactly the same on a three-variable polyhedron (rooms 14 and 15).
- Solve a complete problem end to end, unaided (room 16).
- Interpret shadow prices: how much one more unit of each resource is worth, and how far that is worth it (room 17).
- Build the dual problem, understand its economic meaning, and check that its solution was already in the final simplex tableau (rooms 18 to 23).
- Answer the analysis questions of a complete problem by reading the final tableau: slacks and exhausted resources, shadow prices, strong duality, whether buying a resource pays, and why a product is not made and above what profit it would pay (room 24).
Key mathematical ideas
- Every
≤constraint becomes an equality by adding a slack variable; every≥, by subtracting a surplus. None of those variables may be negative. - In standard form there are more variables than degrees of freedom: at each vertex, as many variables as there are original variables are zero. Those are the non-basic ones; the rest form the basis.
- Each simplex iteration changes the basis: one variable enters (the most negative coefficient in the Z row) and another leaves (the minimum ratio). Where that row crosses that column sits the pivot.
- The simplex method does not test every vertex: it walks from one to the next, always improving, and that is why it terminates. Since the region is convex, a vertex better than all its neighbours is the best of all — there are no local maxima that are not global.
- The Z row of the final tableau gives more than the optimum: its coefficients under the slacks are the shadow prices of the resources, and they are also the dual's solution.
- The dual problem is built by mechanical rules: one dual variable per constraint, one dual constraint per variable, max for min, and the coefficient matrix transposed. Right-hand sides and objective coefficients swap roles.
- Weak duality: any feasible primal solution is worth less than any feasible dual one. Strong duality: at the optimum they coincide. Complementary slackness: if a resource is left over its price is 0, and if its price is positive that resource is exhausted.
- Under a non-basic variable, the final Z row gives its reduced cost: the shadow-price value of the resources one unit consumes, minus what it earns. It is how much Z would drop per forced unit, and the variable starts to pay off when its objective coefficient rises by that amount. A variable entering the basis at some iteration is no guarantee that it is in the optimum.
Before you start
It helps to have done Linear optimization, or at least to know how to draw a feasible region and find the optimum by looking at it: room 1 recaps that quickly, but it does not teach it from scratch.
Room-by-room contents
Room 1 · What you need to know first
A quick recap of what the previous lab covers, with a direct link to it in case it needs doing first: the three parts of a linear problem (decision variables, objective function and constraints), the table-and-chair workshop that runs through the whole lab, and its feasible region drawn, with the optimum at (2, 6) and Z = 36.
Student tasks
- Identify which of four problems is not linear.
- Define the feasible region and say what shape it can have.
- Recall where the optimum is always reached and what it is worth in the workshop.
Room 2 · Turning the problem around
The method that follows can only maximize and only understands ≤. The room shows the two adjustments that get any problem ready: minimizing W is maximizing −W (the optimal point does not move, only the sign of the value changes), and a ≥ constraint becomes ≤ when multiplied by −1.
Student tasks
- Convert a minimization problem into a maximization one and say what the new optimum is worth.
- Reverse an inequality and check what happens to the coefficients.
Room 3 · Slack gets a name
The gap left at the top of each resource bar — already seen in the previous lab — gets its name: slack variable. The bars move with the point and each one shows its slack as a number, h₁, h₂ and h₃.
Student tasks
- Compute the slack of each resource for a specific plan.
- Recognize what it means for a slack to be 0.
Room 4 · Standard form
A machine does not understand ≤: it can only solve equalities. Each constraint becomes an equality by adding its own slack variable, and all variables — slacks included — are required to be ≥ 0. The whole workshop is then written in standard form.
Student tasks
- Write the standard form of a specific constraint.
- Say how many variables the problem has once the slacks are added.
Room 5 · Standardizing a minimization problem
The awkward case: a diet problem with ≥ constraints. The gap cannot be added — it would end up on the wrong side — so a surplus variable is subtracted; and since, after subtracting, the origin no longer works as a starting point, artificial variables appear.
Student tasks
- Turn a ≥ constraint into an equality with a surplus variable.
- Explain why an artificial variable is needed and what role it plays.
Room 6 · Five dials, two hands
The workshop has 5 variables (x, y, h₁, h₂, h₃) but only 2 degrees of freedom: as soon as x and y are fixed, the three slacks are determined. Dragging the point shows all five dials moving at once, and at each vertex exactly two variables are 0 — the non-basic ones — while the other three form the basis.
Student tasks
- Drag the point and watch the five values move together.
- Count how many variables are 0 at a vertex and say which ones form the basis.
Room 7 · What if we tried them all?
The obvious idea — check every corner — is knocked down with a slider: the number of basic solutions is the binomial coefficient C(n+m, m), and it goes from 10 to more than a hundred quadrillion as the problem grows, with the computing time shown alongside. After that come Dantzig and the simplex method, with its idea of walking from vertex to vertex.
Student tasks
- Compute how many vertices have to be tested for n = 4 and m = 3.
- Estimate the case n = m = 25 in orders of magnitude.
- Explain why it is enough to stop when no neighbour improves.
Room 8 · The simplex tableau
The workshop problem, formalized with every coefficient in view, and its tableau beside it: one row per constraint, one column per variable, the Z row at the bottom with the objective coefficients with their signs changed, and the right-hand column with the constant terms. The coefficients of the main variables are in blue in both the statement and the tableau, so you can see they are the same numbers; the slacks form the identity matrix.
Student tasks
- Say what the last column of the tableau represents.
- Read the value of Z in the initial tableau.
- Build the complete tableau of a new problem, all 15 cells.
Room 9 · Who comes in?
The Z row tells how much the profit grows per unit of each variable, which is why the column with the most negative coefficient enters. The room also explains what it means for one variable to enter the basis and another to leave it. Two buttons make the point travel for two seconds from the origin to the neighbouring vertex, with the level line following it and a profit bar rising.
Student tasks
- Choose which column enters in the initial workshop tableau.
- Compute how much Z grows per unit of y.
- Compute how much the profit rises on reaching the vertex (0, 6).
Room 10 · How far can you go?
The minimum ratio test, with the two ratios in colour — orange for the leaving row, blue for the other — both in the text and in the tableau cells themselves. The slack bars fill as the point advances, and the one that reaches its limit shows that its slack is 0. Where the leaving row crosses the entering column sits the pivot, marked with a ring.
Student tasks
- Decide which variable would leave if the x column entered.
- Explain what would happen if the larger ratio were taken instead of the smaller one.
Room 11 · The Gauss method
The three Gauss-Jordan steps, first explained with an animation on a small example unrelated to the workshop: each step waits four seconds so there is time to read it, then writes one line per cell with the full calculation, filling in the tableau at the same time. Pressing “I get it” hides the explanation, and the student carries out the first iteration on the workshop with guidance: mark the pivot, divide its row and eliminate the others, one per step.
Student tasks
- Watch the whole method, calculation by calculation, and press “I get it”.
- Mark the pivot by clicking on the tableau.
- Divide the pivot row and complete each of the other rows.
Room 12 · The second iteration: who enters and who leaves?
Nothing is done for the student here: with the pivoted tableau in front of them, they decide the second iteration on their own by applying the two rules. At the end, the point jumps from (0, 6) to (2, 6) in a two-second animation, with the profit rising from 30 to 36.
Student tasks
- Choose the entering column by looking at the Z row.
- Compute the two competing ratios.
- Decide which variable leaves the basis.
Room 13 · Finish the second iteration
The same guided pivot as in room 11, now with pivot 3 and with real fractions, which must be written with a slash and no decimals. At the end, the Z row has no negative numbers left: the simplex method stops and the tableau reads x = 2, y = 6, Z = 36. Along the way, the 0, 3, 1 under the slacks are pointed out as a preview of the shadow-price block.
Student tasks
- Mark the pivot of the second iteration.
- Divide the pivot row, writing the fractions.
- Complete the remaining rows and the Z row.
Room 14 · The walk around the corners
Both iterations together: the route (0,0) → (0,6) → (2,6) on the drawing, with the tableau for each stop beside it and a profit thermometer rising 0 → 30 → 36. The point to get across is that Z never goes down and there are finitely many vertices, so the method has to stop.
Student tasks
- Explain why the simplex method always terminates.
- Justify why it cannot get stuck at a local maximum worse than the global one.
Room 15 · With three variables
The same method on a three-variable polyhedron that can be rotated with the mouse, with the x, y, z axes drawn as arrows from the vertex (0,0,0) and the simplex tableau always beside it. The complete route — two edges — is animated automatically, with the Z thermometer rising as the point moves.
Student tasks
- Watch the complete route on the polyhedron and rotate the figure.
- Say what would happen to Z when moving from the optimum to an unvisited neighbour.
- Identify which variables left the basis and which entered.
Room 16 · Simplex from start to finish
The last stop for the method: a factory with max Z = 45x + 60y subject to 4x + 6y ≤ 150 and 8x + 3y ≤ 144, chosen on purpose so that the optimum is not a whole number and trial and error does not work. The student decides which column enters and which row leaves in the two iterations needed.
Student tasks
- Choose the entering column and the leaving row in the first iteration.
- Repeat in the second and read the optimum from the final tableau.
Room 17 · What is one more hour worth?
Three sliders stretch the workshop capacities one at a time, and a graph per resource shows how the profit responds: the slope of that line is the shadow price. Beside it, the final simplex tableau is recomputed live, with the Z row under the slacks marked in red — which is where the shadow prices were all along.
Student tasks
- Compute Z if upholstery goes from 6 to 7 hours.
- Compare the shadow prices of the three resources and explain why one of them is 0.
- Locate the three shadow prices in the final tableau.
Room 18 · The recipe for the objective
Each constraint points in its own direction — (1,0), (0,1) and (3,2) — and so does the objective, (3,5). The dual asks how much of each direction must be added to rebuild the objective: three sliders move three arrows chained tip to tail until the sum lands on the objective.
Student tasks
- Move the three arrows until they rebuild the objective.
- Compute y₂ and y₃ when y₁ = 0.
- Interpret what it means for a multiplier to come out as 0.
Room 19 · The dual, in money
The economic meaning of duality: the primal is the workshop that produces, and the dual is someone who wants to buy its resources at the lowest price the workshop would accept. That is where the ≥ constraints come from (nobody sells for less than they would earn by producing). The two problems appear side by side, with the capacities in blue and the profits in red, and below them the two coefficient matrices: the dual one is the transpose of the primal one.
Student tasks
- Interpret in money what y₂ = 3 means.
- Identify whose problem is the dual of that of a shop buying ham from three suppliers.
- Decide whether it pays to sell one unit of upholstery for €2.
Room 20 · The dual problem
The mechanical rules for building the dual, with the primal and the dual written side by side and every coefficient in view, 1s and 0s included. Hovering over a number lights up its exact partner in the other problem: the constant term 4 with the 4 in the dual objective, the 1 in 1x with the 1 in 1y₁, and a constraint label with the whole column of its dual variable.
Student tasks
- Say what the primal variables correspond to.
- Read a specific coefficient of the dual objective function.
- Choose, from four options, the dual of a new problem.
Room 21 · Build the dual yourself
The big challenge of the block: building, in stages, the dual of a problem that is not the workshop — a bakery with three constraints and two variables, so that the two counts do not match. The dual writes itself in the box on the right as each stage is answered correctly, until it is complete.
Student tasks
- Say what the dual will look like before computing anything.
- Count how many variables and how many constraints it will have.
- Write the coefficients of the objective and those of the two constraints.
Room 22 · Free variables and signs
What to do when a variable can be negative: the trick x = x^+ − x^− with both parts ≥ 0. And the table of sign correspondences between the two problems — ≤ constraint ↔ variable ≥ 0, = constraint ↔ free variable, and vice versa — with the underlying reason: a constraint that binds from one side only gives a price that cannot be negative.
Student tasks
- Say what an equality in the primal becomes in the dual.
- Choose the correct sign in the free-variable trick.
- Split a negative value between x^+ and x^−.
Room 23 · The two meet
The close of the lab: weak duality, strong duality and complementary slackness, each explained separately, with a market reading (the shadow price is the price at which it makes no difference to the workshop whether it sells or produces). An animated graph shows the dual bound coming down and the primal plan going up until the gap closes at 36, with the slack bars following the plan as it advances.
Student tasks
- Watch the gap between the two bounds close.
- Say from what price it pays to sell one unit of upholstery.
- Explain what it means for the difference between the two bounds to reach 0.
- Deduce the shadow price of a resource that is left over.
Room 24 · What the final tableau tells you
The parts that follow «solve it with the simplex method» in an exam problem, on a complete problem with three products and three resources (a toy factory: max 4x₁ + 5x₂ + 9x₃). First the three iterations are stepped through; x₃ enters in the first and leaves again in the third. With the final tableau always in view, students read the slacks (which resources run out and how many hours are left, checked against the constraints), the shadow prices, strong duality (W = Z = 72) and whether buying single hours at a given price pays off. The last block explains why the most profitable product is not made: the number in the Z row under x₃ is its reduced cost, the shadow-price value of the resources it uses minus what it earns, and from it comes the profit above which it would pay. A slider for c₃ checks this by solving the problem again. It ends with a summary of how to answer each part.
Student tasks
- Read the slacks in the final tableau and check them by substituting the optimal plan into a constraint.
- Read the shadow prices and check strong duality by computing the dual objective.
- Decide which purchases of single hours increase profit by comparing with the shadow price.
- Explain why a variable that entered the basis may be absent from the optimum.
- Use the reduced cost to compute the profit with one forced unit and the threshold above which making it pays.
Rooms to project
The most striking ones to show and discuss in class.