📚 What You'll Actually Learn
Each mission introduces a new LP concept. By Mission 7, you'll understand the full Simplex Method.
The Lemonade Tycoon 🍋
It's a hot summer day. You need to mix the perfect drinks to make the most money before the sun goes down!
1 Your Inventory (Variables)
🚫 The Limits (Constraints)
To keep it simple, let's say sugar is unlimited today!
📝 Writing the constraint mathematically:
Each Classic uses 1 lemon, each Pink uses 2 lemons, and total lemons cannot exceed 10:
1x + 2y ≤ 10
We also need: x ≥ 0 and y ≥ 0 (you can't make negative cups!). These are called non-negativity constraints.
🎯 The Goal (Objective Function)
Maximize Profit (Z)
x = Classic cups, y = Pink cups
Why "linear"? Because every term is a constant times a variable (no x², no xy, no sin(x)). The profit graph is a flat plane, and constraints draw straight lines. That's what makes the Simplex method work!
📖 Key Vocabulary (Learn These First!)
Decision Variables (x, y)
The things you control — how many Classic (x) and Pink (y) cups to make.
Objective Function (Z)
The formula you want to maximize (or minimize). Here: Z = 2x + 5y.
Constraint
A rule that limits your choices. Here: x + 2y ≤ 10 (lemons).
Feasible Region
The set of all valid plans — the shape on the graph where every constraint is satisfied.
Corner Point (Vertex)
Where constraint boundaries intersect. The optimal solution always lives at a corner.
Slack Variable
The "leftover" resource. If you use 6 of 10 lemons, slack = 4. Zero slack means the constraint is tight.
💡 Concept Spotlight: Why Corners?
In Linear Programming, the Fundamental Theorem states: if an optimal solution exists, it occurs at a corner point (vertex) of the feasible region. The feasible region is the shape drawn by your constraints on a graph. Simplex doesn't check every possible point — it cleverly hops from corner to corner, always moving uphill, until no better corner exists.
In this mission, the feasible region is a simple line segment on the x-axis (Classic cups) vs y-axis (Pink cups). All valid plans live inside a triangle. The profit is maximized at one of the triangle's corners.
🏆 How to Win (The Algorithm)
The Lazy Start — Origin (0, 0)
Simplex always starts at the origin: make 0 of everything. Profit = $0. This is a valid "corner" of the feasible region, but clearly not optimal.
Pick the Entering Variable
Simplex looks at the objective function Z = 2x + 5y and asks: "Which variable gives the biggest profit-per-unit?"
Answer: y (Pink Lemonade) at $5/cup beats x at $2/cup. So y enters the solution.
This is called the "most positive coefficient" rule — the standard Simplex entry criterion.
The Minimum Ratio Test (How far can we go?)
Before increasing y, Simplex checks: "How much y can we make before violating a constraint?"
With x = 0: 2y ≤ 10 → y ≤ 5
This is the Minimum Ratio Test — it prevents Simplex from jumping out of the feasible region. Here, we can make at most 5 Pink Lemonades before running out of lemons.
Arrive at the Optimal Corner
We jumped from corner (0,0) to corner (0,5). Let's check the profit:
Z = 2(0) + 5(5) = $25
Can Simplex improve further? It checks the remaining variable x. Adding 1 Classic needs 1 lemon, but that means removing ½ a Pink (which needs 2). Net change: +$2 − $2.50 = −$0.50. That's worse!
No improving direction → We are at the optimum! $25 🎉
📐 Graphical View (What Simplex Sees)
On a graph with x (Classic) on the horizontal axis and y (Pink) on the vertical axis:
The Feasible Region (a triangle):
- 📍 Corner A (0, 0) — Origin. Z = $0
- 📍 Corner B (10, 0) — All Classic. Z = $20
- 📍 Corner C (0, 5) — All Pink. Z = $25 ⭐
The line x + 2y = 10 forms the hypotenuse. Every plan inside or on this triangle is "feasible" (uses ≤ 10 lemons).
Simplex's Path:
Simplex jumped directly to the optimal corner in one pivot. In problems with 2+ constraints, it may take multiple hops along the edges.
Key insight: Simplex NEVER checks interior points — only corners. That's what makes it fast even for thousands of variables.
🧪 Try Different Plans (Prove the Corners Win)
Don't trust math blindly — let's test several plans and see which earns the most:
| Plan | Classic (x) | Pink (y) | Lemons Used | Feasible? | Profit (Z) |
|---|---|---|---|---|---|
| Do nothing | 0 | 0 | 0 / 10 | ✓ | $0 |
| All Classic | 10 | 0 | 10 / 10 | ✓ | $20 |
| 50/50 mix | 4 | 3 | 10 / 10 | ✓ | $23 |
| Mostly Pink | 2 | 4 | 10 / 10 | ✓ | $24 |
| All Pink ⭐ | 0 | 5 | 10 / 10 | ✓ | $25 |
| Greedy (too many) | 2 | 5 | 12 / 10 | ✗ | N/A |
| Interior point | 2 | 2 | 6 / 10 | ✓ | $14 |
Pattern: Notice how "All Pink" beats every other plan? Also notice the last row — point (2,2) is inside the triangle but only earns $14. Interior points ALWAYS lose to corners. This is exactly why Simplex only checks corners!
📊 The Simplex Tableau (What the Calculator Does Inside)
When you click "Solve" in the calculator, it builds a table called a tableau. Here's what it looks like for this problem:
Step 1: Initial Tableau (at origin, x=0, y=0)
| Basis | x | y | s1 | RHS | Ratio |
|---|---|---|---|---|---|
| s1 | 1 | 2 | 1 | 10 | 10/2 = 5 |
| Z | -2 | -5 | 0 | 0 | — |
s1 is the slack variable — it represents "unused lemons." Initially s1 = 10 (all lemons unused).
Reading the Z row: The most negative number is -5 (column y). This means increasing y improves profit the most. Column y is the "pivot column."
Ratio test: RHS / pivot column = 10/2 = 5. So y can increase to at most 5. Row s1 is the "pivot row."
Step 2: After Pivot (y enters, s1 leaves)
| Basis | x | y | s1 | RHS |
|---|---|---|---|---|
| y | 0.5 | 1 | 0.5 | 5 |
| Z | 0.5 | 0 | 2.5 | 25 |
Read the solution: y = 5 (read from RHS), x = 0 (not in basis), Z = $25.
Optimality check: All Z-row coefficients are ≥ 0 (x has +0.5, s1 has +2.5). No improvement possible. OPTIMAL!
Bonus insight: The 2.5 under s1 in the Z-row IS the shadow price! Each extra lemon would add $2.50 to profit.
🤔 What If? (Sensitivity Analysis)
Sensitivity analysis answers: "How much can things change before my plan changes?" This is often more valuable than the solution itself.
Q: What if you had 20 lemons instead of 10?
The constraint becomes x + 2y ≤ 20. The optimal moves to (0, 10), profit = 10 × $5 = $50.
Each extra lemon adds $2.50 to profit. That's the shadow price (also called dual value) of lemons. It appears directly in the final tableau's Z-row!
Q: At what price would Classic Lemonade become worth making?
Classic uses 1 lemon and earns $p. Pink uses 2 lemons and earns $5 (i.e., $2.50/lemon). Classic becomes competitive when its profit-per-lemon exceeds Pink's: p > $2.50.
Currently p = $2 < $2.50, so Classic is not worth it. But if Classic profit rose to $3 or more, the optimal plan would shift to a mix of both drinks. This threshold is called the allowable increase in sensitivity reports.
Q: What if Pink Lemonade profit dropped to $2?
Then Z = 2x + 2y. Both drinks earn $2 per cup. The objective function line becomes parallel to the constraint line x + 2y = 10.
Result: the entire hypotenuse becomes optimal — any valid mix that uses all 10 lemons earns $10. This is called multiple optimal solutions (or alternate optima).
Q: What if you added a sugar constraint?
Say each Classic uses 2 cups of sugar, each Pink uses 1, and you have 8 total: 2x + y ≤ 8.
Now the feasible region is a quadrilateral (4 corners instead of 3). The optimal might shift — and that's exactly what Mission 2 explores!
⚠ Common Mistakes Beginners Make
Forgetting non-negativity constraints. You must always include x ≥ 0, y ≥ 0. Without them, Simplex might suggest "make -10 Classic" which is meaningless.
Checking interior points instead of corners. "Let me try x=3, y=2..." — sure, it's feasible, but you're wasting time. The optimal is ALWAYS at a corner.
Confusing "most profitable product" with "best plan." The most expensive product isn't always the best. In Mission 2, the $20 Battle Bot isn't the only thing to make — the best plan is a mix.
Thinking Simplex only works for 2 variables. The graphical method (drawing on paper) only works for 2-3 variables. But the Simplex tableau works for any number — real-world problems have tens of thousands.
🌍 Where You'll See This in Real Life
🏭 Manufacturing
A bakery deciding how many croissants vs. baguettes to bake with limited flour, oven time, and staff. Same structure: maximize revenue subject to ingredient/time constraints.
✈️ Airlines
Airlines solve LP problems with ~100,000 variables to assign planes to routes, maximizing revenue while respecting gate limits, crew schedules, and maintenance windows.
🛒 Retail
Amazon uses LP to decide which products fill each warehouse, minimizing shipping costs while meeting demand forecasts across regions.
🎮 Fun Fact
The Simplex algorithm was invented by George Dantzig in 1947. It's been called one of the top 10 most important algorithms of the 20th century. Every smartphone's GPS uses a descendant of it!
The Lego Master 🧱
You run a toy factory with two products and two limited resources. The greedy approach fails here — you need a mix.
1 Your Blueprints (Variables)
Notice the trade-off: Cars are wheel-heavy (4 wheels each), Bots are brick-heavy (4 bricks each). Neither product dominates on both resources — this is what makes the problem interesting. A greedy "build only the most profitable" strategy will waste one resource.
🚫 The Inventory (Constraints)
📝 Constraints in math:
c + 4b ≤ 16 (bricks)
4c + 2b ≤ 24 (wheels)
c, b ≥ 0
🎯 The Goal (Objective)
Maximize Profit
c = Race Cars, b = Battle Bots
What's new vs Mission 1? Two constraints instead of one. The feasible region is now a quadrilateral (4 corners) instead of a triangle (3 corners). Simplex may need multiple pivots to reach the optimum.
💡 Concept Spotlight: Feasible Region & Multiple Constraints
In Mission 1, one constraint created a triangle. Here, two constraints create a 4-cornered polygon. Each constraint draws a line, and the feasible region is where all lines are satisfied simultaneously.
How the polygon forms:
- Line 1: c + 4b = 16 (slopes down-right)
- Line 2: 4c + 2b = 24 (slopes down steeper)
- Non-negativity: c ≥ 0, b ≥ 0 (axes)
- The overlap of all four half-planes = feasible region
Why more constraints = more interesting:
With 1 constraint, the greedy approach ("make only the most profitable") usually wins. With 2+ constraints, one resource might bottleneck before others — forcing you to consider a mix. This is where LP beats human intuition.
🪜 The Greedy Trap (Why Intuition Fails)
Your gut says: "Bots earn $20 each, cars earn only $10. Build ALL bots!" Let's test that:
Strategy A: All Bots
- Bricks: 4 bots × 4 = 16 ✓ (used all)
- Wheels: 4 bots × 2 = 8 ✓ (16 wasted!)
- Profit: 4 × $20 = $80
⚠ 16 wheels sitting unused = wasted capacity
Strategy B: All Cars
- Wheels: 6 cars × 4 = 24 ✓ (used all)
- Bricks: 6 cars × 1 = 6 ✓ (10 wasted!)
- Profit: 6 × $10 = $60
⚠ 10 bricks sitting unused = even worse
🏆 Simplex Walkthrough (Step-by-Step Pivots)
Start at Origin (0, 0) — Z = $0
No cars, no bots. All resources idle. Simplex scans the objective coefficients: c = 10, b = 20.
b has the largest coefficient (20 > 10), so b enters the basis.
Pivot 1: Hop to Corner (0, 4) — Z = $80
Minimum Ratio Test — "How many bots until a constraint breaks?"
Wheels: 24 / 2 = 12 bots
Bricks run out first at b = 4. The brick constraint becomes tight (slack = 0). Wheels used: 4 × 2 = 8 out of 24.
Score: 4 × $20 = $80. But 16 wheels sit idle...
Simplex now checks: "Can introducing cars improve things?"
Pivot 2: Trade Bots for Cars — Does It Help?
Simplex calculates the reduced cost of introducing a car:
Each car needs 1 brick. But bricks are fully used → must free 1 brick by cutting 1/4 of a bot.
Lost: 1/4 bot × $20 = −$5
Gained: 1 car × $10 = +$10
Net improvement: +$5 per car. Yes, it helps!
Simplex keeps adding cars (and removing fractions of bots) until the second constraint (wheels) also becomes tight. That intersection of both constraint lines is the optimal corner.
Optimal Corner (4.57, 2.86) — Z ≈ $102.86
Both constraints are now binding (zero slack in both):
Verify: Bricks = 4.57 + 4(2.86) = 16 ✓ | Wheels = 4(4.57) + 2(2.86) = 24 ✓
Simplex checks all neighbor corners — no direction improves Z. Optimal confirmed.
📊 The Simplex Tableau (Inside the Calculator)
Here's the actual tableau the calculator builds. Follow along with each pivot:
Initial Tableau (at origin: c=0, b=0)
| Basis | c | b | s1 | s2 | RHS | Ratio |
|---|---|---|---|---|---|---|
| s1 (bricks) | 1 | 4 | 1 | 0 | 16 | 16/4 = 4 ← |
| s2 (wheels) | 4 | 2 | 0 | 1 | 24 | 24/2 = 12 |
| Z | -10 | -20 | 0 | 0 | 0 | — |
Pivot column: b (most negative Z-row value = -20). Pivot row: s1 (min ratio = 4). Pivot element: 4.
After row operations: divide pivot row by 4, eliminate b from other rows.
After Pivot 1 (b enters, s1 leaves) — at corner (0, 4)
| Basis | c | b | s1 | s2 | RHS | Ratio |
|---|---|---|---|---|---|---|
| b | 0.25 | 1 | 0.25 | 0 | 4 | 4/0.25 = 16 |
| s2 | 3.5 | 0 | -0.5 | 1 | 16 | 16/3.5 ≈ 4.57 ← |
| Z | -5 | 0 | 5 | 0 | 80 | — |
Z-row check: c has coefficient -5 (negative = can still improve). Pivot column: c. Pivot row: s2 (min ratio ≈ 4.57). Need one more pivot.
After Pivot 2 (c enters, s2 leaves) — OPTIMAL
| Basis | c | b | s1 | s2 | RHS |
|---|---|---|---|---|---|
| b | 0 | 1 | 2/7 | -1/14 | 20/7 ≈ 2.86 |
| c | 1 | 0 | -1/7 | 2/7 | 32/7 ≈ 4.57 |
| Z | 0 | 0 | 30/7 | 10/7 | 720/7 ≈ $102.86 |
Optimality: All Z-row coefficients ≥ 0 → no further improvement possible. OPTIMAL!
Shadow prices (read from Z-row): s1 = 30/7 ≈ $4.29 (each extra brick adds ~$4.29), s2 = 10/7 ≈ $1.43 (each extra wheel adds ~$1.43).
Insight: Bricks are more valuable than wheels here ($4.29 vs $1.43). If you could buy extra resources, buy bricks first!
📐 All Four Corners Compared
The feasible region has exactly 4 corners. Simplex visited 3 of them (skipping B because it was never on the path):
| Corner | Cars (c) | Bots (b) | Bricks | Wheels | Profit (Z) | Simplex Visit |
|---|---|---|---|---|---|---|
| A (origin) | 0 | 0 | 0 / 16 | 0 / 24 | $0 | Start |
| B | 6 | 0 | 6 / 16 | 24 / 24 | $60 | Skipped |
| C | 0 | 4 | 16 / 16 | 8 / 24 | $80 | Pivot 1 |
| D ⭐ | 4.57 | 2.86 | 16 / 16 | 24 / 24 | $102.86 | Pivot 2 (optimal) |
Pattern: Corner D is the only one where both resources hit 100% usage. No waste = maximum profit. This is the hallmark of a strong LP solution.
🤔 What If? (Sensitivity Analysis)
The shadow prices from the tableau tell us exactly how changes affect profit.
Q: What if you found 7 extra bricks (23 total)?
Shadow price of bricks = $4.29/brick. Extra profit ≈ 7 × $4.29 = +$30. New total ≈ $132.86 (valid as long as the same corner stays optimal).
Q: What if Battle Bot profit changed to $30?
The objective tilts toward bots. At some point, corner C (all bots) becomes optimal instead of the mix. The allowable increase in sensitivity reports tells you exactly when that switch happens.
Q: Why is each extra brick worth $4.29 but each extra wheel only $1.43?
Bricks are the tighter bottleneck. Both constraints are binding, but the brick constraint has more "profit pressure" against it. Loosening the tighter constraint always gives more return. This insight helps factories decide where to invest!
Q: What if you must build whole numbers only?
Then you need Integer Programming (IP). LP gives c ≈ 4.57, b ≈ 2.86. Nearby integers to check: (4,3)=$100, (5,2)=$90, (3,3)=$90. Best integer plan: 4 cars + 3 bots = $100. Not always as simple as "round to nearest"!
⚠ Common Mistakes in Multi-Constraint Problems
"Just build the most profitable item." Greedy strategies ignore resource balance. All-bots earns $80 but wastes 16 wheels. The mix earns $102.86 — a 28% improvement.
Rounding LP solutions carelessly. The LP optimal is (4.57, 2.86). Rounding both up to (5, 3) uses 5+12=17 bricks — violates the 16-brick limit! Always check feasibility after rounding.
Ignoring shadow prices. If bricks cost $2 to buy and the shadow price is $4.29, buying extra bricks is profitable ($4.29 − $2 = $2.29 net gain per brick). Shadow prices drive real business decisions.
🌍 Where You See This in Real Life
🚗 Toyota Production
Toyota decides monthly how many Camrys vs. RAV4s to build. Shared paint lines (like our bricks) and shared engines (like our wheels) create the same multi-constraint structure.
📦 FedEx Cargo
Each plane has a weight limit and volume limit. Different packages have different sizes, weights, and revenues — exactly like metals vs. helium in Mission 6.
🍕 Restaurant Menus
A kitchen has limited oven time and limited prep staff. Each dish uses different amounts of both. LP determines the optimal menu mix each night.
📊 By the Numbers
Major manufacturers solve LP problems with 10,000+ variables and 50,000+ constraints daily. The Simplex method handles them in seconds. Our 2-variable example teaches the same underlying logic.
The Candy Crusher 🍬
You run a high-end chocolate shop with two products sharing one ingredient — but only one product uses caramel. This asymmetric resource structure changes everything.
1 The Menu (Variables)
Key asymmetry: Bars use zero caramel. Truffles use caramel but share chocolate equally with bars. This means caramel only limits truffles, while chocolate limits both. When one constraint applies to only one variable, the LP has a distinctive shape.
🚫 The Pantry (Constraints)
📝 Constraints in math:
x + y ≤ 20 (chocolate)
2y ≤ 12 (caramel)
x, y ≥ 0
🎯 The Goal (Objective)
Maximize Profit
x = Crunchy Bars, y = Gooey Truffles
What's new vs Mission 2? One variable (x) has a zero coefficient in the caramel constraint. This creates a constraint that is a horizontal line (y ≤ 6), not a sloped line. The feasible region looks different from Mission 2's quadrilateral.
💡 Concept Spotlight: Zero Coefficients & Constraint Geometry
When a variable has coefficient 0 in a constraint (like x in "2y ≤ 12"), that constraint doesn't restrict that variable at all. It becomes a horizontal or vertical line on the graph.
What the feasible region looks like:
- x + y = 20 → diagonal line (slope = -1)
- 2y = 12 → horizontal line at y = 6
- These form a 4-cornered polygon
- Corners: (0,0), (20,0), (14,6), (0,6)
Why zero coefficients matter in LP:
In large real-world LPs (1000+ variables), most constraints have many zero coefficients — this is called sparsity. Solvers exploit this for speed. Our tiny example introduces the idea: not every constraint involves every variable.
🪜 The Greedy Trap (Why "All Truffles" Fails)
Truffles earn $8 each vs Bars at $5. Your instinct: "Max out truffles!" Let's test:
Strategy A: All Truffles
- Caramel: 6 × 2 = 12 ✓
- Chocolate: 6 × 1 = 6 ✓
- Profit: 6 × $8 = $48
⚠ 14 oz chocolate unused!
Strategy B: All Bars
- Chocolate: 20 × 1 = 20 ✓
- Caramel: 0 ✓
- Profit: 20 × $5 = $100
⚠ All caramel wasted
Strategy C: Optimal Mix
- 14 bars + 6 truffles
- Choc: 14+6 = 20 ✓
- Caramel: 12 ✓
- Profit: 70+48 = $118
✓ Both resources fully used
🏆 Simplex Walkthrough (Step-by-Step Pivots)
Start at Origin (0, 0) — Z = $0
No bars, no truffles. Simplex scans coefficients: x = 5, y = 8.
y has the largest coefficient (8 > 5), so y enters the basis first.
Pivot 1: Hop to Corner (0, 6) — Z = $48
Minimum Ratio Test for y:
Caramel: 12 / 2 = 6 truffles ← smallest!
Caramel runs out first at y = 6. Only 6 oz of chocolate used — 14 oz still free.
Score: 6 × $8 = $48. But 14 oz of chocolate is sitting idle...
Simplex asks: "Can we use that leftover chocolate for bars?"
Pivot 2: Add Bars with Leftover Chocolate
Simplex calculates the reduced cost of introducing a bar (x):
Each bar needs 1 chocolate. Chocolate has leftover capacity (14 oz free).
Does adding a bar force removing any truffles? Let’s check:
• Caramel constraint: 2y ≤ 12. Bars use 0 caramel → no impact on truffles!
• Chocolate constraint: x + y ≤ 20. Adding bars uses slack, not truffles (until chocolate fills up).
Net gain: +$5 per bar with zero trade-off. Pure profit!
Simplex keeps adding bars until the chocolate constraint also becomes tight. That happens when x = 14 (since 14 + 6 = 20).
Optimal Corner (14, 6) — Z = $118 ⭐
Both constraints are binding (zero slack):
Verify: Chocolate = 14 + 6 = 20 ✓ | Caramel = 2(6) = 12 ✓
Simplex checks neighbors — no improving direction. Optimal confirmed.
📊 The Simplex Tableau
Watch how zero coefficients create a simpler pivot structure:
Initial Tableau (at origin: x=0, y=0)
| Basis | x | y | s1 | s2 | RHS | Ratio |
|---|---|---|---|---|---|---|
| s1 (choc) | 1 | 1 | 1 | 0 | 20 | 20/1 = 20 |
| s2 (caramel) | 0 | 2 | 0 | 1 | 12 | 12/2 = 6 ← |
| Z | -5 | -8 | 0 | 0 | 0 | — |
Pivot column: y (most negative = -8). Pivot row: s2 (min ratio = 6). Pivot element: 2.
Key observation: The x column in the s2 row is 0 — meaning the caramel constraint doesn’t interact with bars at all. This makes the pivot cleaner.
After Pivot 1 (y enters, s2 leaves) — at corner (0, 6)
| Basis | x | y | s1 | s2 | RHS | Ratio |
|---|---|---|---|---|---|---|
| s1 | 1 | 0 | 1 | -0.5 | 14 | 14/1 = 14 ← |
| y | 0 | 1 | 0 | 0.5 | 6 | — (0 in column) |
| Z | -5 | 0 | 0 | 4 | 48 | — |
Z-row check: x has coefficient -5 (still negative = can improve). y row has 0 in the x column — meaning adding bars won’t change the number of truffles at all! This is the zero-coefficient effect in action.
Pivot column: x. Pivot row: s1 (ratio = 14). The y row has 0 in the pivot column, so it’s unaffected.
After Pivot 2 (x enters, s1 leaves) — OPTIMAL
| Basis | x | y | s1 | s2 | RHS |
|---|---|---|---|---|---|
| x | 1 | 0 | 1 | -0.5 | 14 |
| y | 0 | 1 | 0 | 0.5 | 6 |
| Z | 0 | 0 | 5 | 1.5 | 118 |
Optimality: All Z-row values ≥ 0 → OPTIMAL!
Shadow prices: s1 = 5 (each extra oz of chocolate adds $5), s2 = 1.5 (each extra oz of caramel adds $1.50).
Insight: Chocolate is worth ~3.3× more than caramel per ounce! This makes sense — bars (which only use chocolate) earn $5 each, so every extra oz of chocolate = one more bar = $5. Extra caramel only helps truffles, and the net gain is smaller because truffles compete with bars for chocolate ($8 − $5 = $3 per truffle, needing 2 oz = $1.50/oz).
📐 All Four Corners Compared
| Corner | Bars (x) | Truffles (y) | Chocolate | Caramel | Profit (Z) | Simplex Visit |
|---|---|---|---|---|---|---|
| A (origin) | 0 | 0 | 0 / 20 | 0 / 12 | $0 | Start |
| B | 20 | 0 | 20 / 20 | 0 / 12 | $100 | Skipped |
| C | 0 | 6 | 6 / 20 | 12 / 12 | $48 | Pivot 1 |
| D ⭐ | 14 | 6 | 20 / 20 | 12 / 12 | $118 | Pivot 2 (optimal) |
Interesting: Corner B (all bars, $100) is better than Corner C (all truffles, $48). The higher per-unit profit of truffles is deceptive because the caramel constraint caps them at only 6 units. The optimal D combines the best of both: max truffles within caramel limits, then fill remaining chocolate with bars.
🤔 What If? (Sensitivity Analysis)
Q: What if you get 5 more oz of chocolate (25 total)?
Shadow price = $5/oz. Extra profit = 5 × $5 = +$25. New total = $143. All extra chocolate goes to bars (5 more bars at $5 each). Truffles stay at 6 because caramel is still the truffle bottleneck.
Q: What if you get 4 more oz of caramel (16 total)?
Shadow price = $1.50/oz. Extra profit = 4 × $1.50 = +$6. You’d make 2 more truffles (y = 8), but each truffle also uses 1 oz chocolate, pushing out bars. Net per truffle: $8(truffle) − $5(lost bar) = $3, and each truffle needs 2 caramel, so $3/2 = $1.50/oz. (The shadow price accounts for this trade-off automatically.)
Q: What if truffle profit dropped to $4?
Below $5, truffles become less profitable than bars even per unit. The optimal would shift to corner B (all bars, x=20, y=0). The critical ratio is when the truffle price equals the bar price — at exactly $5, both Corner B and Corner D are tied (called alternate optima).
Q: What if a third product (Fudge) uses 3 chocolate + 1 caramel and earns $12?
Adding a variable creates a 3D feasible region. The Simplex method handles this seamlessly — just add a column to the tableau. The corner-hopping logic is the same, but now in 3D space. This is how LP scales to any number of products.
⚠ Common Mistakes with Asymmetric Constraints
"Higher profit per unit = better product." Truffles earn $8 vs $5 per unit, but their caramel requirement caps them at 6 units. Total truffle revenue: $48. Total bar revenue (if all bars): $100. Per-unit profit means nothing without considering constraint capacity.
Thinking zero coefficients don’t matter. The 0 in the caramel constraint for bars is crucial — it means bars bypass the caramel bottleneck entirely. This is why bars can absorb leftover chocolate without affecting truffle production.
Confusing shadow prices. Shadow price of chocolate ($5) vs caramel ($1.50). Beginners might think "caramel is cheap, let’s ignore it." But the lower shadow price means caramel is already well-utilized, not that it’s unimportant. It’s fully consumed — just that loosening it yields less profit because of the chocolate trade-off.
🌍 Where You See This in Real Life
🏥 Hospital Staffing
Hospitals schedule nurses and specialists. Some constraints (total staff hours) apply to everyone; others (surgery certification) only apply to specialists. Zero coefficients are everywhere in real scheduling LPs.
📱 App Store Pricing
A company sells a free tier and a premium tier. Server bandwidth limits both, but customer support only applies to premium users. Same "one constraint affects one product" pattern.
🌾 Farming
A farmer grows wheat and soybeans. Both need land, but only soybeans need nitrogen fixation. The "nitrogen" constraint has a zero coefficient for wheat — identical structure to our caramel problem.
📊 LP Sparsity
Real-world LPs with 10,000 variables often have 95%+ zero coefficients in their constraint matrix. Specialized solvers like CPLEX and Gurobi use sparse matrix storage to avoid wasting memory on all those zeros.
The Pixel Farm 🚜
You bought a small farm in Stardew Valley. Two crops share two resources — but both use land equally. When one constraint has identical coefficients, the LP has a special geometric structure.
1 Your Crops (Variables)
Key structure: Both crops use exactly 1 acre per acre. The land constraint is w + c ≤ 100, with identical coefficients (both 1). This makes the land boundary a 45° diagonal line. Only the water constraint differentiates — corn is the "thirsty" crop (2× the water). This mirrors real agriculture: land is shared equally, but irrigation varies by crop.
🚫 The Resources (Constraints)
📝 Constraints in math:
w + c ≤ 100 (land)
w + 2c ≤ 150 (water)
w, c ≥ 0
🎯 The Goal (Objective)
Maximize Farm Profit
w = Wheat acres, c = Corn acres
What's new vs Mission 3? Both constraints share the same variable. In Mission 3, caramel didn’t involve bars (zero coefficient). Here, both land and water limit both crops — but with different ratios. The diagonal land line (slope −1) and the steeper water line (slope −0.5) create a classic LP shape.
💡 Concept Spotlight: Equal Coefficients & Resource Substitution
When both variables have the same coefficient in a constraint (like w + c ≤ 100), that constraint treats them as perfectly substitutable. One acre of wheat and one acre of corn are interchangeable as far as land is concerned.
Why this shapes the solution:
- Land boundary: w + c = 100 (slope = −1, a 45° line)
- Water boundary: w + 2c = 150 (slope = −0.5, shallower)
- They intersect at w = 50, c = 50
- The land line is "steeper" → it cuts off the top-right
Substitution rate:
On the water constraint, replacing 1 acre of corn with 1 acre of wheat saves 1 water unit (2 − 1 = 1). This "substitution rate" is captured by the tableau’s constraint coefficients. Simplex uses these rates to decide whether swapping crops improves profit.
🪜 The Farmer’s Dilemma (Why "All Corn" Fails)
Corn is $800/acre vs wheat at $500. Greedy brain says: "Plant 100 acres of corn!"
Strategy A: All Corn
- Water: 75 × 2 = 150 ✓
- Land: 75 / 100 used
- Profit: 75 × $800 = $60,000
⚠ 25 acres of land empty!
Strategy B: All Wheat
- Land: 100 × 1 = 100 ✓
- Water: 100 / 150 used
- Profit: 100 × $500 = $50,000
⚠ 50 water units wasted
Strategy C: 50/50 Mix ⭐
- Land: 50+50 = 100 ✓
- Water: 50+100 = 150 ✓
- Profit: 25k+40k = $65,000
✓ Both resources fully used!
🏆 Simplex Walkthrough (Step-by-Step Pivots)
Start at Origin (0, 0) — Z = $0
No crops planted. Simplex scans objective: w = 500, c = 800.
c has the largest coefficient (800 > 500), so corn enters the basis first.
Pivot 1: Hop to Corner (0, 75) — Z = $60,000
Minimum Ratio Test for c:
Water: 150 / 2 = 75 acres of corn ← smallest!
Water runs out first at c = 75. All 150 water units consumed but only 75 of 100 land acres used.
Score: 75 × $800 = $60,000. But 25 acres of good farmland sit fallow...
Simplex asks: "Can planting wheat on the empty land help?"
Pivot 2: Plant Wheat on Empty Land
Simplex calculates the reduced cost of introducing wheat:
Each acre of wheat needs 1 water unit. Water is fully used → must free water by removing corn.
1 acre corn removed frees 2 water units. Wheat needs 1 → net: free 1 water unit.
But we also need 1 acre of land for wheat. We have 25 spare → land is available.
Lost: 1 acre corn × $800 = −$800, but we also free 1 acre of land.
Wait — we can plant 2 acres of wheat with the water freed from removing 1 corn:
- Remove 1 corn: −$800, frees 2 water + 1 land
- Add 2 wheat: +$1,000 (2 × $500), uses 2 water + 2 land
- Net land: −1 + 2 = +1 acre needed (from our 25 spare)
Net improvement: +$200 per swap. Yes, trade corn for wheat!
Simplex keeps swapping until the spare land runs out. That happens when w = 50 and c = 50.
Optimal Corner (50, 50) — Z = $65,000 ⭐
Both constraints are binding (zero slack):
Verify: Land = 50 + 50 = 100 ✓ | Water = 50 + 2(50) = 150 ✓
Simplex checks neighbor corners — no improving direction. Optimal confirmed.
📊 The Simplex Tableau
Watch how equal coefficients in the land constraint create a clean swap pattern:
Initial Tableau (at origin: w=0, c=0)
| Basis | w | c | s1 | s2 | RHS | Ratio |
|---|---|---|---|---|---|---|
| s1 (land) | 1 | 1 | 1 | 0 | 100 | 100/1 = 100 |
| s2 (water) | 1 | 2 | 0 | 1 | 150 | 150/2 = 75 ← |
| Z | -500 | -800 | 0 | 0 | 0 | — |
Pivot column: c (most negative = −800). Pivot row: s2 (min ratio = 75). Pivot element: 2.
After Pivot 1 (c enters, s2 leaves) — at corner (0, 75)
| Basis | w | c | s1 | s2 | RHS | Ratio |
|---|---|---|---|---|---|---|
| s1 | 0.5 | 0 | 1 | -0.5 | 25 | 25/0.5 = 50 ← |
| c | 0.5 | 1 | 0 | 0.5 | 75 | 75/0.5 = 150 |
| Z | -100 | 0 | 0 | 400 | 60000 | — |
Z-row check: w has coefficient −100 (negative = can still improve). Each acre of wheat added gains $100 net. Pivot column: w. Pivot row: s1 (ratio = 50).
Key insight: The s1 RHS = 25 is the slack in land (25 empty acres). Wheat enters to fill that idle land.
After Pivot 2 (w enters, s1 leaves) — OPTIMAL
| Basis | w | c | s1 | s2 | RHS |
|---|---|---|---|---|---|
| w | 1 | 0 | 2 | -1 | 50 |
| c | 0 | 1 | -1 | 1 | 50 |
| Z | 0 | 0 | 200 | 300 | 65000 |
Optimality: All Z-row values ≥ 0 → OPTIMAL!
Shadow prices: s1 = 200 (each extra acre of land adds $200) and s2 = 300 (each extra water unit adds $300).
Key insight: Water is more valuable than land ($300 vs $200)! Even though both resources are fully used, the thirsty crop (corn) puts more "profit pressure" on water. Corn earns $800 but needs 2× the water — so freeing up water unlocks more profit than freeing up land.
📐 All Four Corners Compared
| Corner | Wheat (w) | Corn (c) | Land | Water | Profit (Z) | Simplex Visit |
|---|---|---|---|---|---|---|
| A (origin) | 0 | 0 | 0 / 100 | 0 / 150 | $0 | Start |
| B | 100 | 0 | 100 / 100 | 100 / 150 | $50,000 | Skipped |
| C | 0 | 75 | 75 / 100 | 150 / 150 | $60,000 | Pivot 1 |
| D ⭐ | 50 | 50 | 100 / 100 | 150 / 150 | $65,000 | Pivot 2 (optimal) |
Pattern: Only Corner D uses 100% of both resources. Corner C (all-corn) wastes 25 acres; Corner B (all-wheat) wastes 50 water units. The 50/50 mix is the only plan with zero waste.
🤔 What If? (Sensitivity Analysis)
Q: What if you buy 10 more acres of land (110 total)?
Shadow price = $200/acre. Extra profit = 10 × $200 = +$2,000. New optimal: w = 70, c = 40 (more wheat fills the extra land while rebalancing water). If land costs less than $200/acre, buy it.
Q: What if corn profit drops to $500 (same as wheat)?
Both crops earn the same per acre, and both use 1 acre of land. The optimal becomes a line segment between corners B and D — infinitely many solutions! Any split that uses all water is optimal. This is called alternate optima.
Q: What if you install drip irrigation (corn drops to 1.5 water/acre)?
The water constraint becomes w + 1.5c ≤ 150. New intersection: w = 0, c = 100 fits within water (100 × 1.5 = 150). Now all-corn earns 100 × $800 = $80,000. Technology changes the LP structure — reducing a coefficient can shift the optimal to a completely different corner.
Q: What if a drought cuts water to 100 units?
With w + 2c ≤ 100 and w + c ≤ 100: intersection at w = 100, c = 0. The farm becomes all-wheat ($50,000). When water drops dramatically, the thirsty crop (corn) gets eliminated entirely. Shadow price of water would increase, indicating urgent need for irrigation investment.
⚠ Common Mistakes in Resource Allocation
"Maximize the most profitable per acre." Corn is $800/acre but needs 2× the water. The effective "profit per water unit" is $400 for corn vs $500 for wheat. Wheat is actually more water-efficient. When resources differ, you need to compare profit-per-bottleneck-unit, not just profit-per-unit.
"Higher shadow price means harder bottleneck." Water’s shadow price ($300) exceeds land’s ($200) because corn’s water demand is the binding factor. Don’t assume equal resource usage means equal value — the profit gradient determines which constraint is tighter.
Forgetting idle resources indicate suboptimality. At Corner C (all-corn), 25 acres sit idle. Whenever a resource has slack > 0, you’re likely not at the optimum (unless the slack is in a non-binding constraint by design). Simplex always tries to "fill" idle capacity with the next best option.
🌍 Where You See This in Real Life
🌾 California Agriculture
California farms solve enormous LPs each season: which crops to plant across thousands of acres given water allocations from the state. During droughts, LP models shift toward low-water crops — exactly like our "drought scenario" analysis.
⛽ Oil Refineries
Refineries split crude oil into gasoline, diesel, and jet fuel. Each product uses different refinery capacity (like our water) but the same raw material (like our land). LP decides the optimal product mix daily.
☁ Cloud Computing
AWS allocates virtual machines across CPU cores (shared equally, like land) and RAM (variable demands, like water). LP-based schedulers decide the optimal VM mix millions of times per day.
📊 Shadow Price Differences in Practice
When shadow prices differ, managers know which resource to expand first. Here, water ($300) beats land ($200). If expanding either costs $150/unit, water gives $150 net gain vs. land’s $50 — invest in irrigation first!
Fashion Tycoon 🧵
Fashion Week is tomorrow! You have limited fabric and limited hours to sew your collection. Both resources will be pushed to the limit.
1 The Collection (Variables)
Notice: A Gown costs 3× more fabric than a Tee, but earns 3.3× more profit ($50/$15). It also takes 4× longer to sew. The question is: do you have enough of both resources to go all-in on gowns?
🚫 The Studio Limits (Constraints)
📝 Writing the constraints mathematically:
Each Tee uses 1 yd fabric + 1 hr; each Gown uses 3 yds + 4 hrs:
t + 3g ≤ 60 (fabric)
t + 4g ≤ 80 (time)
Plus: t ≥ 0 and g ≥ 0 (can't sew negative garments!).
🎯 The Goal (Objective Function)
Maximize Profit (Z)
t = Tees, g = Gowns
Two resources this time! In Mission 1, we only had lemons. Now fabric AND time compete. The interesting question: will both limits hit at the same time, or will one have leftover?
📖 Key Vocabulary for This Mission
Binding Constraint
A constraint that is used up exactly at the optimal solution (slack = 0). It's "tight" — any more would push you over the limit.
Non-Binding Constraint
A constraint that still has leftover room at the optimum (slack > 0). Relaxing it won't improve profit — something else is the bottleneck.
Degeneracy
When MORE constraints are binding than the minimum needed to define a corner point. In 2D, a corner needs 2 binding constraints; if 3 are binding, it's degenerate.
Degenerate Pivot
A Simplex pivot where a basic variable equals zero. The solution doesn't actually "move" — Simplex changes its bookkeeping without improving Z.
Slack Variable (s)
The unused portion of a resource. Fabric slack s1 = 60 − (t + 3g). If s1 = 0, all fabric is used.
Tied Ratio Test
When two rows give the same minimum ratio during a pivot. This is the hallmark of degeneracy — the Simplex method must break the tie.
💡 Concept Spotlight: Binding vs. Non-Binding Constraints
Imagine you're packing a suitcase (weight limit) for a flight (time limit to board). If your suitcase is exactly 50 lbs at the limit, the weight constraint is binding. If you arrive at the gate with 30 minutes to spare, the time constraint is non-binding — having even more time wouldn't help.
In LP, binding constraints matter enormously: they determine the optimal corner. Shadow prices are only positive for binding constraints. If a constraint is non-binding, getting more of that resource adds zero profit — you aren't using what you already have!
This mission is special: at the optimum, both constraints are binding AND the point sits on the g-axis (t = 0). That means three constraints are tight at one 2D point. Normally only 2 are needed to pin down a corner — having an extra one is called degeneracy. It doesn't break anything, but it can cause Simplex to take an "extra" pivot that doesn't improve profit.
🗺️ Decision Flow
60/3 = 20
80/4 = 20"} C -->|"TIE! Pick row 1"| D["Pivot: g = 20
s₂ = 0 (degenerate!)"] D --> E{"Any negative
in Z-row?"} E -->|"All ≥ 0"| F(("✅ Optimal
Z = $1,000")) style C fill:#F59E0B,color:white style D fill:#8B5CF6,color:white style F fill:#10B981,color:white
The tied ratio (20 = 20) signals degeneracy — both resources run out at the exact same moment.
🏆 How to Win (The Algorithm)
The Lazy Start — Origin (0, 0)
Make 0 Tees and 0 Gowns. Profit = $0. Both slack variables are at maximum: s1 = 60 (all fabric unused), s2 = 80 (all time unused).
Pick the Entering Variable
Simplex checks the objective Z = 15t + 50g: which variable gives the biggest profit-per-unit?
Answer: g (Gala Gown) at $50 beats t at $15. So g enters the solution.
Pivot column = g. (Most positive coefficient rule: pick the column with the most negative Z-row entry, −50.)
The Minimum Ratio Test — TIE! ⚠️
Before increasing g, Simplex asks: "How much can g grow before breaking a constraint?"
Time: t + 4g ≤ 80 → g ≤ 80/4 = 20
Both ratios = 20 — a TIE!
This is the signature of degeneracy. Both resources run out at exactly the same point. In Mission 1, only one constraint was tight at the optimum. Here, both fabric AND time hit zero slack simultaneously.
Simplex breaks the tie by picking one row (say, fabric / row 1) as the pivot row. The other row's basic variable will become zero — a degenerate basic variable.
Arrive at the Optimal Corner
After the pivot, g = 20, t = 0. Let's verify both constraints:
Time: 0 + 4(20) = 80 ≤ 80 ✓ (slack = 0, BINDING)
Also: t = 0 ≥ 0 ✓ (also BINDING!)
Z = 15(0) + 50(20) = $1,000
Simplex checks remaining variable t: adding 1 Tee earns +$15, but requires removing 1/3 of a Gown (−$16.67 profit) for fabric and 1/4 of a Gown (−$12.50) for time. Net effect is negative.
No improving direction → We are at the optimum! $1,000 🎉
📐 Graphical View (What Simplex Sees)
On a graph with t (Tees) on the horizontal axis and g (Gowns) on the vertical axis:
The Feasible Region (a triangle):
- 📍 Corner A (0, 0) — Origin. Z = $0
- 📍 Corner B (60, 0) — All Tees. Z = $900
- 📍 Corner C (0, 20) — All Gowns. Z = $1,000 ⭐
The fabric line (t + 3g = 60) forms the binding edge. The time line (t + 4g = 80) passes through the same optimal corner — both lines meet at (0, 20).
Why is (0, 20) special?
At this corner, three constraints are active simultaneously:
- t + 3g = 60 (fabric tight)
- t + 4g = 80 (time tight)
- t = 0 (on the g-axis)
In 2D, only 2 constraints are needed to "pin" a corner. Having 3 is called degeneracy. Visually, three lines pass through the same point instead of the usual two.
Key insight: At corner B (60, 0), the time constraint is non-binding: 60 + 0 = 60 < 80, leaving 20 hours of slack. That slack tells you time wasn't the bottleneck there.
🧪 Try Different Plans
Test several production plans and check which constraints are binding at each:
| Plan | Tees (t) | Gowns (g) | Fabric | Time | Feasible? | Profit (Z) |
|---|---|---|---|---|---|---|
| Do nothing | 0 | 0 | 0 / 60 | 0 / 80 | ✓ | $0 |
| All Tees | 60 | 0 | 60 / 60 | 60 / 80 | ✓ | $900 |
| Half & half | 12 | 16 | 60 / 60 | 76 / 80 | ✓ | $980 |
| Mostly Gowns | 6 | 18 | 60 / 60 | 78 / 80 | ✓ | $990 |
| All Gowns ⭐ | 0 | 20 | 60 / 60 | 80 / 80 | ✓ | $1,000 |
| Greedy | 10 | 20 | 70 / 60 | 90 / 80 | ✗ | N/A |
| Interior point | 10 | 10 | 40 / 60 | 50 / 80 | ✓ | $650 |
Binding pattern: At the optimal plan, both fabric and time show red (fully used). At "All Tees", only fabric is binding — time has 20 hours of slack. At "Interior point", neither resource is binding, and profit suffers badly. Using all your critical resources = maximum profit.
📊 The Simplex Tableau (Step-by-Step)
Here's what the calculator does under the hood. Watch for the tied ratio — that's the degeneracy signal.
Step 1: Initial Tableau (at origin, t = 0, g = 0)
| Basis | t | g | s1 | s2 | RHS | Ratio |
|---|---|---|---|---|---|---|
| s1 | 1 | 3 | 1 | 0 | 60 | 60/3 = 20 |
| s2 | 1 | 4 | 0 | 1 | 80 | 80/4 = 20 |
| Z | -15 | -50 | 0 | 0 | 0 | — |
Pivot column: g (most negative Z-row entry: −50).
⚠️ Ratio test TIE: Row s1 gives 60/3 = 20. Row s2 gives 80/4 = 20. Both are 20!
This tie means both constraints will be exactly satisfied when g = 20. The constraint that "leaves" the basis will have its slack go to zero, but the other row's slack will also be zero — a degenerate basic variable.
We pick s1 (row 1) as pivot row. Pivot element = 3.
Step 2: After Pivot (g enters, s1 leaves)
| Basis | t | g | s1 | s2 | RHS |
|---|---|---|---|---|---|
| g | 1/3 | 1 | 1/3 | 0 | 20 |
| s2 | −1/3 | 0 | −4/3 | 1 | 0 |
| Z | 5/3 | 0 | 50/3 | 0 | 1000 |
Read the solution: g = 20 (from RHS), t = 0 (not in basis), Z = $1,000.
Optimality check: All Z-row entries are ≥ 0 (t has +5/3, s1 has +50/3). No improvement possible. OPTIMAL!
🔮 Spot the degeneracy: Look at the s2 row — its RHS is 0. That means s2 is a basic variable equal to zero. In a non-degenerate solution, all basic variables would be positive. Zero means the time constraint is exactly met even though s2 is still "in the basis."
What does it mean? If Simplex were to pivot s2 out, it would jump to the same corner (0, 20) again — no actual movement. This is why degeneracy can sometimes cause Simplex to cycle (revisit the same corner). In practice, anti-cycling rules like Bland's Rule prevent this.
💰 Shadow Prices (Reading the Z-Row)
The Z-row values under the slack columns tell you the shadow price of each resource:
🧶 Fabric Shadow Price
$16.67 per extra yard
Z-row under s1 = 50/3 ≈ $16.67. One more yard of fabric would increase profit by this much.
⏱️ Time Shadow Price
$0.00 per extra hour
Z-row under s2 = 0. Extra sewing hours wouldn't help — even though time IS binding!
Wait — time is binding but its shadow price is $0? Yes! This is a consequence of degeneracy. At this degenerate corner, both constraints are tight, but the profit gradient only "pushes against" fabric. Adding time alone doesn't open a path to more profit. You'd need BOTH more fabric and more time to unlock a better corner. This counter-intuitive result is a hallmark of degenerate LP solutions.
🤔 What If? (Sensitivity Analysis)
Exploring how changes in data affect the optimal plan.
Q: What if you had 63 yards of fabric instead of 60?
New fabric constraint: t + 3g ≤ 63. With g only limited by fabric: g ≤ 21 (but time: 4(21) = 84 > 80 ✗).
Now the constraints no longer intersect at the axis. Solve t + 3g = 63 and t + 4g = 80: g = 17, t = 12. Z = 15(12) + 50(17) = $1,030.
Gain = $30 for 3 extra yards = $10/yard. The shadow price actually changed because we left the degenerate corner! This is normal — shadow prices are only valid for small changes within the current basis.
Q: At what price would Tees become worth sewing?
The Z-row entry for t is 5/3 ≈ $1.67. This is the reduced cost. Tees become attractive when their profit rises by more than $1.67 above $15 — that is, above $16.67.
At $16.67+, Simplex would bring t into the basis, and you'd make a mix of Tees and Gowns.
Q: What if Gown profit dropped to $20?
Z = 15t + 20g. Now a Gown earns $6.67/yard of fabric vs. a Tee at $15/yard. Tees win! The optimum shifts to (60, 0) — all Tees, Z = $900. Time becomes non-binding (60 < 80).
The plan completely flips. This shows how sensitive the solution is to profit coefficients near the break-even point.
Q: What if time was 100 hours instead of 80?
Time constraint: t + 4g ≤ 100. At g = 20: 80 ≤ 100 ✓ (now with 20 hrs slack). The optimal stays at (0, 20) with Z = $1,000.
Extra time didn't help at all! Time becomes non-binding, confirming its shadow price of $0 was correct for small increases.
⚠ Common Mistakes in This Mission
Assuming binding = valuable. Time is binding here, yet its shadow price is $0. A binding constraint CAN have zero shadow price in degenerate cases. Don't assume "tight = important" without checking.
Ignoring the ratio tie. When ratios tie, many students just pick one and move on without noting the degeneracy. This can cause confusion later when interpreting shadow prices or sensitivity ranges.
Thinking "all gowns" is obvious. It seems intuitive here, but change the numbers slightly (e.g., fabric to 50) and the optimal becomes a mix. Always solve — don't eyeball.
Confusing degeneracy with infeasibility. Degeneracy is just "extra constraints are tight." The problem is still perfectly solvable — Simplex just might take a redundant pivot step.
🌍 Where You'll See This in Real Life
👗 Actual Fashion
Zara and H&M solve massive LP problems to decide production quantities across thousands of garments, balancing factory capacity, fabric supply, shipping deadlines, and seasonal demand.
🏥 Hospital Scheduling
Hospitals allocate nurses, rooms, and equipment. Often, multiple resource constraints bind simultaneously (staff AND beds at capacity) — classic degeneracy in practice.
📦 Supply Chain
When a warehouse hits its weight limit AND volume limit at the exact same time, planners face the same degenerate corner-point tradeoffs you just solved.
💡 Fun Fact
Degeneracy is extremely common in real-world LP. Models with thousands of variables often have hundreds of degenerate pivots. The Simplex method handles them gracefully — it just takes a few extra (zero-improvement) steps.
Space Tycoon 🚀
You are loading a cargo rocket to Mars. Weight and volume compete against each other — neither product dominates both, so the optimal is always a mix.
1 The Cargo (Variables)
The core trade-off: Metals are heavy but compact ($100/kg, $1000/m³). Helium is bulky but light ($400/kg, $160/m³). Metals max out weight; Helium maxes out space. Neither cargo type can fill the rocket alone without wasting the other dimension. The optimal is a blend that uses both resources fully.
🚫 The Rocket Limits (Constraints)
📝 Writing the constraints mathematically:
Each Metal crate weighs 10 kg and takes 1 m³; each Helium tank weighs 2 kg and takes 5 m³:
10m + 2h ≤ 100 (weight)
m + 5h ≤ 60 (volume)
Plus: m ≥ 0 and h ≥ 0.
🎯 The Goal (Objective Function)
Maximize Cargo Value (Z)
m = Metal crates, h = Helium tanks
Why a mix wins this time: In Missions 1 & 5, one product dominated. Here, Metals have better value-per-crate ($1,000 vs $800), but they eat weight 5× faster. Loading only Metals wastes 50 m³ of empty space. Loading only Helium wastes 76 kg of payload capacity. The sweet spot is where BOTH limits hit simultaneously.
📖 Key Vocabulary for This Mission
Competing Constraints
When two resources "fight" each other: one product stresses Resource A, the other stresses Resource B. Neither product can fill both alone — forcing a mixed solution.
Intersection Point
Where two constraint lines cross. In 2D LP with competing constraints, the optimal usually lives at this intersection rather than on an axis.
Value Density
Profit per unit of resource consumed. Metals: $100/kg but $1,000/m³. Helium: $400/kg but $160/m³. Different rankings on different resources — the hallmark of a non-trivial LP.
Fractional Solution
When the optimal has non-integer values (like 7.92 crates). LP allows fractions; integer solutions require Integer Programming (IP), a harder problem.
Simultaneous Equations
To find the intersection corner, solve both constraint equations at equality: 10m + 2h = 100 AND m + 5h = 60. Two equations, two unknowns → one unique point.
LP Relaxation
Solving the LP and ignoring integer requirements. The LP solution provides an upper bound on the best possible integer solution. Rounding may not give the true integer optimum.
💡 Concept Spotlight: Why a Mix Wins
In previous missions, one product was so good that the optimal was "make only that." Here, the trade-off is multi-dimensional: Metals dominate on one resource (space) but lose on another (weight). Helium is the opposite.
Think of it like packing a suitcase that has BOTH a weight limit AND a size limit. Heavy jewelry fills weight but not space. Fluffy pillows fill space but not weight. The best suitcase packs some of each to use both dimensions fully.
Mathematically, when two products have opposite resource profiles (one heavy-small, one light-bulky), the optimal always lies at the intersection of the two constraint lines — not on any axis. This is the first mission where the optimal corner requires solving simultaneous equations.
🗺️ Decision Flow
Two pivots needed! The first fills weight; the second trades some metal for helium to also fill space.
🏆 How to Win (The Algorithm)
The Lazy Start — Origin (0, 0)
Load 0 Metal and 0 Helium. Value = $0. Both slack variables are at maximum: s₁ = 100 (all weight unused), s₂ = 60 (all space unused). The rocket is completely empty.
Pivot 1: Enter m (Rare Metals)
The Z-row has −1000 under m and −800 under h. Since |−1000| > |−800|, Metals enter first.
Space: 1m ≤ 60 → m ≤ 60
Min ratio = 10 (weight row). Pivot: m enters, s₁ leaves.
Result: m = 10, h = 0. Weight: 100/100 (full!). Space: 10/60 (50 m³ wasted). Z = $10,000.
Good, but 50 m³ of empty space — we're wasting the cargo bay!
Pivot 2: Enter h (Helium Tanks)
After the first pivot, Simplex recalculates the Z-row. Helium's reduced cost is still negative (−600), meaning: "each Helium tank added (after adjusting Metals down) would still improve profit."
→ must remove 0.2 Metal crates to free weight
Net gain: +$800 − 0.2 × $1000 = +$600
Ratio test determines h can go up to 125/12 ≈ 10.42, at which point space fills up completely.
Now BOTH weight and space are fully utilized — the rocket is packed perfectly.
Arrive at the Optimal Corner
After Pivot 2: m = 95/12 ≈ 7.917, h = 125/12 ≈ 10.417. Let's verify:
Space: 95/12 + 5(125/12) = 95/12 + 625/12 = 720/12 = 60 ✓ BINDING
Z = 1000(95/12) + 800(125/12) = 195,000/12 = $16,250
Simplex checks: all Z-row entries are ≥ 0. No further improvement possible.
Optimal cargo loaded! $16,250 🎉
📐 Graphical View (What Simplex Sees)
On a graph with m (Metals) on the horizontal axis and h (Helium) on the vertical axis:
The Feasible Region (a quadrilateral):
- 📍 Corner A (0, 0) — Empty rocket. Z = $0
- 📍 Corner B (10, 0) — All Metals. Z = $10,000
- 📍 Corner C (95/12, 125/12) — The Mix. Z = $16,250 ⭐
- 📍 Corner D (0, 12) — All Helium. Z = $9,600
The feasible region is bounded by the weight line above-right and the volume line below-right. Corner C sits at their intersection.
Simplex's Path (2 hops):
Pivot 1: Jumps along the m-axis (weight fills up). Pivot 2: Slides along the weight constraint line, trading some metal for helium, until the space constraint also binds.
Key insight: The optimal is NOT on any axis — it's the interior intersection of two constraint lines. This only happens when neither product dominates on all resources.
🧪 Try Different Plans
Test several loading plans and see which resources limit each one:
| Plan | Metals (m) | Helium (h) | Weight | Volume | Feasible? | Value (Z) |
|---|---|---|---|---|---|---|
| Empty rocket | 0 | 0 | 0 / 100 | 0 / 60 | ✓ | $0 |
| All Metals | 10 | 0 | 100 / 100 | 10 / 60 | ✓ | $10,000 |
| All Helium | 0 | 12 | 24 / 100 | 60 / 60 | ✓ | $9,600 |
| Naive 50/50 | 5 | 6 | 62 / 100 | 35 / 60 | ✓ | $9,800 |
| Heavy mix | 8 | 10 | 100 / 100 | 58 / 60 | ✓ | $16,000 |
| Optimal mix ⭐ | 7.92 | 10.42 | 100 / 100 | 60 / 60 | ✓ | $16,250 |
| Greedy overload | 10 | 12 | 124 / 100 | 70 / 60 | ✗ | N/A |
| Interior point | 4 | 4 | 48 / 100 | 24 / 60 | ✓ | $7,200 |
Pattern: "All Metals" wastes 50 m³ of space. "All Helium" wastes 76 kg of weight. Only the optimal mix fills BOTH to 100%. The interior point (4,4) uses barely half of each resource and earns the least. Filling every resource = maximum value.
📊 The Simplex Tableau (Step-by-Step)
This problem takes two pivots — the most we've seen so far. Watch Simplex trade metals for helium on the second pivot.
Step 1: Initial Tableau (at origin, m = 0, h = 0)
| Basis | m | h | s₁ | s₂ | RHS | Ratio |
|---|---|---|---|---|---|---|
| s₁ | 10 | 2 | 1 | 0 | 100 | 100/10 = 10 |
| s₂ | 1 | 5 | 0 | 1 | 60 | 60/1 = 60 |
| Z | −1000 | −800 | 0 | 0 | 0 | — |
Pivot column: m (most negative Z-row entry: −1000).
Ratio test: Row s₁: 100/10 = 10. Row s₂: 60/1 = 60. Minimum = 10. s₁ leaves, m enters.
Pivot element = 10 (row s₁, column m).
Step 2: After Pivot 1 (m enters, s₁ leaves)
| Basis | m | h | s₁ | s₂ | RHS | Ratio |
|---|---|---|---|---|---|---|
| m | 1 | 1/5 | 1/10 | 0 | 10 | 10 / (1/5) = 50 |
| s₂ | 0 | 24/5 | −1/10 | 1 | 50 | 50 / (24/5) = 125/12 |
| Z | 0 | −600 | 100 | 0 | 10000 | — |
Read intermediate solution: m = 10, h = 0, Z = $10,000. Weight is full (s₁ left basis). Space slack s₂ = 50 (50 m³ wasted).
Not optimal yet! h has −600 in the Z-row — each helium tank would improve profit. Pivot column = h.
Ratio test: Row m: 10/(1/5) = 50. Row s₂: 50/(24/5) = 125/12 ≈ 10.42. Min = 125/12. s₂ leaves, h enters.
Step 3: After Pivot 2 (h enters, s₂ leaves) — OPTIMAL
| Basis | m | h | s₁ | s₂ | RHS |
|---|---|---|---|---|---|
| m | 1 | 0 | 5/48 | −1/24 | 95/12 |
| h | 0 | 1 | −1/48 | 5/24 | 125/12 |
| Z | 0 | 0 | 87.5 | 125 | 16250 |
Read the solution: m = 95/12 ≈ 7.917, h = 125/12 ≈ 10.417, Z = $16,250.
Optimality check: All Z-row entries are ≥ 0 (s₁ has +87.5, s₂ has +125). No improvement possible. OPTIMAL!
Both variables in basis, both positive — a non-degenerate optimal (unlike Mission 5). This means shadow prices are straightforward and sensitivity ranges are wide.
💰 Shadow Prices (Reading the Z-Row)
The Z-row values under the slack columns reveal the marginal value of each resource:
⚖️ Weight Shadow Price
$87.50 per extra kg
Z-row under s₁ = 87.5. Upgrading the rocket to carry 101 kg would increase value by $87.50.
📦 Volume Shadow Price
$125 per extra m³
Z-row under s₂ = 125. Expanding the cargo bay by 1 m³ would add $125 to the haul.
Volume is more valuable than weight! An extra m³ is worth $125 vs. $87.50 for an extra kg. This makes sense: helium tanks are very bulky, so space is the scarcer resource per dollar of profit. If you could only upgrade one dimension of the rocket, expand the cargo bay.
Compare with Mission 5 where time had a shadow price of $0 due to degeneracy. Here, both resources have positive shadow prices because the solution is non-degenerate.
💡 Concept Spotlight: Fractional Solutions & Integer Programming
The optimal says "load 7.917 metal crates." But you can't cut a crate in half! This is where Integer Programming (IP) comes in. LP gives the relaxed solution — the best possible if fractions are allowed. For integers, you'd need to compare nearby whole-number solutions:
m=7, h=10
Wt: 90 ✓ Vol: 57 ✓
$15,000
m=8, h=10
Wt: 100 ✓ Vol: 58 ✓
$16,000 ⭐
m=8, h=11
Wt: 102 ✗ Vol: 63 ✗
Infeasible
The best integer solution (m=8, h=10, Z=$16,000) earns $250 less than the LP optimum. This gap is called the integrality gap. Simple rounding doesn't always find the integer optimum — that's why IP is a separate (NP-hard) field!
🤔 What If? (Sensitivity Analysis)
Exploring how changes in data affect the cargo plan.
Q: What if the rocket could carry 120 kg instead of 100?
Extra 20 kg × shadow price $87.50/kg = +$1,750 more value (as long as the basis doesn't change). New Z ≈ $18,000.
The mix shifts: more metals (they're heavy), fewer helium tanks needed for balance. Volume becomes the tighter constraint.
Q: What if Helium value rose to $1,200 per tank?
Now both products earn similar value-per-kg (Metals: $100, Helium: $600). The mix shifts heavily toward Helium. At some point, the optimal corner changes to "All Helium" on the volume axis.
The threshold is found from the reduced cost: Helium can increase by up to the amount that makes its Z-row coefficient hit zero. Beyond that, the basis changes.
Q: What if we added a crew-safety constraint: m ≤ 8?
Currently m = 7.917, which already satisfies m ≤ 8. This constraint is non-binding (slack = 0.083). Adding it doesn't change the optimal!
But if the limit were m ≤ 7, it WOULD bind, cutting into profit. This shows how "close" constraints can be without actually affecting the answer.
Q: What if we added a third cargo type: Water (w)?
Say Water earns $500, weighs 5 kg, takes 3 m³. Now we have 3 variables and 2 constraints. LP can handle this — the feasible region becomes a 3D polyhedron, and Simplex hops between 3D corners. The graphical method fails here but the tableau works identically.
⚠ Common Mistakes in This Mission
Loading only the most valuable product. Metals earn $1,000 each but waste 5/6 of the cargo bay. Ignoring the space dimension leaves $6,250 on the table!
Rounding the LP solution to get the integer answer. Rounding m=7.917 to 8 and h=10.417 to 10 gives (8,10): feasible and $16,000. But rounding both UP to (8,11) is infeasible! Always check feasibility after rounding.
Comparing value-per-unit without specifying WHICH resource. Metals are $1000/crate vs. Helium $800/crate. But per kg: Metals = $100, Helium = $400. Per m³: Metals = $1000, Helium = $160. Different rankings! You must consider ALL resources simultaneously.
Forgetting that shadow prices have limits. The $87.50/kg shadow price is valid only for small changes in weight capacity. If you added 1000 kg, the basis would change and the shadow price would be different. Always check the allowable increase/decrease range.
🌍 Where You'll See This in Real Life
🚚 Freight & Logistics
Every shipping container has both a weight limit and a volume limit. FedEx, UPS, and Amazon solve variants of this problem millions of times daily to decide which packages go on which truck.
✈️ Airline Cargo
Passenger planes carry belly cargo. Weight is limited by fuel/safety; volume by physical bay size. Airlines use LP to maximize revenue per flight from the cargo mix.
🏗️ Portfolio Optimization
Financial portfolios balance risk (like "weight") vs. liquidity (like "volume"). High-return assets may be risky; safe assets may tie up capital. The optimal is always a mix — just like our rocket.
🚀 Actual Space
NASA's Mars missions literally solve this problem! The Curiosity rover's payload was optimized across mass, volume, power consumption, and data bandwidth — a multi-constraint LP with hundreds of variables.
Hero Training 🏋️
In previous missions, we wanted MAX money. Here, we want MINIMUM cost to get fit.
1 The Diet (Variables)
📉 The Minimums (Constraints)
Your trainer says you MUST eat at least this much:
🎯 The Goal (Minimize Z)
Minimize Grocery Bill
x = Chicken, y = Rice
Tip: Rice is cheap, but you'd need to eat 18 bowls to get enough protein! Chicken is expensive. Simplex finds the cheapest reliable mix.
📖 Key Vocabulary for This Mission
Minimization
Instead of Max Z, we want Min Z. Simplex still works — it searches for the lowest corner of the feasible region instead of the highest.
≥ Constraints (Greater-Than)
"You MUST eat at least 90g protein" becomes 30x + 5y ≥ 90. The feasible region is above the line, not below. Everything flips!
Surplus Variable
The opposite of a slack variable. Instead of adding unused capacity (slack), we subtract the surplus over the minimum requirement. 30x + 5y - s₁ = 90.
Artificial Variable
With ≥ constraints, the origin (0,0) is infeasible! Simplex can't start there. Artificial variables create a fake starting point that gets pushed out during solving via the Big-M penalty.
Duality
Every Min LP has a "twin" Max LP (its dual). They have the same optimal value! The dual of our Min problem is a standard Max LP that Simplex handles natively.
Unbounded Feasible Region
With ≥ constraints, the feasible region extends to infinity (you can always eat MORE). But the optimal still exists because we're minimizing — we find the corner closest to the origin.
💡 Concept Spotlight: How Minimization Flips Everything
In Missions 1–6, every constraint was “you have AT MOST this much.” The feasible region was a bounded polygon, and we looked for the highest corner. Now everything reverses:
Missions 1–6
≤ constraints (at most)
Bounded region
Maximize Z
Origin IS feasible
↔
REVERSED
Mission 7
≥ constraints (at least)
Unbounded region
Minimize Z
Origin is NOT feasible
Think of it this way: previously, you were locked inside a room and climbing to the ceiling. Now you’re outside the room and digging down to find the lowest point of the terrain.
🗺️ Decision Flow
The Dual Trick: convert Min with ≥ into Max with ≤ — a problem type we already know how to solve!
🏆 How to Win (The Algorithm)
Why Can’t We Start at the Origin?
At (0, 0): Protein = 0g (need ≥ 90g ✗), Carbs = 0g (need ≥ 120g ✗). Eating nothing fails ALL requirements! Unlike Missions 1–6, the origin is outside the feasible region. We need a different starting strategy.
The Dual Trick — Flip the Problem!
Every minimization LP has a twin “dual” that’s a maximization LP. The magic: both have the same optimal value.
30x + 5y ≥ 90, 5x + 40y ≥ 120
Dual (the twin): Max 90u₁ + 120u₂
30u₁ + 5u₂ ≤ 4, 5u₁ + 40u₂ ≤ 1
The dual has ≤ constraints and maximization — exactly what Simplex does natively! We solve the dual, then read the primal answer from it.
Solve the Dual (2 Pivots)
The dual is Max W = 90u₁ + 120u₂ with two ≤ constraints. Standard Simplex from the origin (u₁=0, u₂=0):
Pivot 2: u₁ enters (still negative in W-row). Ratio test gives u₁ = 31/235. Both dual variables now in basis.
Dual optimal: u₁ = 31/235, u₂ = 2/235, W = 606/47 ≈ $12.89.
Read the Primal Answer from the Dual
By the Complementary Slackness Theorem, the primal’s optimal values appear in the dual’s Z-row under the slack columns:
W-row under s₂ = 126/47 → y* = 126/47 ≈ 2.681 rice bowls
Verify: Protein = 30(120/47) + 5(126/47) = 3600/47 + 630/47 = 4230/47 = 90 ✓ BINDING
Carbs = 5(120/47) + 40(126/47) = 600/47 + 5040/47 = 5640/47 = 120 ✓ BINDING
Z = 4(120/47) + 126/47 = 480/47 + 126/47 = 606/47 ≈ $12.89
Cheapest diet found! $12.89 🎉
📐 Graphical View (What Simplex Sees)
On a graph with x (Chicken) horizontal and y (Rice) vertical. The feasible region is above and to the right of both constraint lines — extending to infinity!
The Feasible Region (unbounded!):
- 📍 Corner A (0, 18) — All Rice. Z = $18
- 📍 Corner B (120/47, 126/47) — The Mix. Z = $12.89 ⭐
- 📍 Corner C (24, 0) — All Chicken. Z = $96
The region extends infinitely up-right (you can always eat more), but the minimum cost is at the corner closest to the origin.
Why (3, 0) ISN’T a Corner:
At x=3, y=0: Protein = 90 ✓ but Carbs = 15 ✗ (needs 120). You’d have enough chicken protein but you’d collapse from no energy!
The x-axis corner isn’t at x=3 (where protein barely passes); it’s at x=24 (where carbs finally passes too). That’s why all-chicken costs a whopping $96.
Key insight: Unlike Max problems where the optimal is the farthest corner from the origin, in Min problems it’s the nearest feasible corner.
🧪 Try Different Diet Plans
Test several meal plans. Remember: we want the CHEAPEST that meets BOTH requirements.
| Plan | Chicken (x) | Rice (y) | Protein | Carbs | Feasible? | Cost (Z) |
|---|---|---|---|---|---|---|
| Eat nothing | 0 | 0 | 0 / 90 | 0 / 120 | ✗ | N/A |
| Chicken only (min protein) | 3 | 0 | 90 / 90 | 15 / 120 | ✗ | N/A |
| All Rice | 0 | 18 | 90 / 90 | 720 / 120 | ✓ | $18 |
| All Chicken | 24 | 0 | 720 / 90 | 120 / 120 | ✓ | $96 |
| Balanced mix | 2 | 6 | 90 / 90 | 250 / 120 | ✓ | $14 |
| Integer try | 3 | 3 | 105 / 90 | 135 / 120 | ✓ | $15 |
| Optimal mix ⭐ | 2.55 | 2.68 | 90 / 90 | 120 / 120 | ✓ | $12.89 |
| Overeating | 5 | 10 | 200 / 90 | 425 / 120 | ✓ | $30 |
Pattern: "All Rice" ($18) has enough protein barely, but 6× the carbs needed — wasteful. "All Chicken" ($96) has 8× the protein needed, but costs a fortune. The optimal meets BOTH requirements exactly (both binding) — no waste, minimum cost. Best integer solution: (2, 6) at $14.
📊 The Simplex Tableau (Dual Method)
Instead of wrestling with ≥ constraints directly, we solve the dual (a standard Max LP) and read our diet answer from it. The dual has variables u₁ (protein price) and u₂ (carbs price).
Dual: Max W = 90u₁ + 120u₂ subject to 30u₁ + 5u₂ ≤ 4, 5u₁ + 40u₂ ≤ 1
Step 1: Initial Tableau (u₁ = 0, u₂ = 0)
| Basis | u₁ | u₂ | s₁ | s₂ | RHS | Ratio |
|---|---|---|---|---|---|---|
| s₁ | 30 | 5 | 1 | 0 | 4 | 4/5 = 0.8 |
| s₂ | 5 | 40 | 0 | 1 | 1 | 1/40 = 0.025 |
| W | −90 | −120 | 0 | 0 | 0 | — |
Pivot column: u₂ (most negative: −120). Ratio test: 0.8 vs 0.025. s₂ leaves, u₂ enters.
Step 2: After Pivot 1 (u₂ enters, s₂ leaves)
| Basis | u₁ | u₂ | s₁ | s₂ | RHS | Ratio |
|---|---|---|---|---|---|---|
| s₁ | 235/8 | 0 | 1 | −1/8 | 31/8 | (31/8)/(235/8) = 31/235 |
| u₂ | 1/8 | 1 | 0 | 1/40 | 1/40 | (1/40)/(1/8) = 1/5 |
| W | −75 | 0 | 0 | 3 | 3 | — |
Not optimal yet: u₁ has −75 in W-row. Ratio test: 31/235 ≈ 0.132 vs 1/5 = 0.2. Min = 31/235. s₁ leaves, u₁ enters.
Step 3: After Pivot 2 (u₁ enters, s₁ leaves) — OPTIMAL
| Basis | u₁ | u₂ | s₁ | s₂ | RHS |
|---|---|---|---|---|---|
| u₁ | 1 | 0 | 8/235 | −1/235 | 31/235 |
| u₂ | 0 | 1 | −1/235 | 6/235 | 2/235 |
| W | 0 | 0 | 120/47 | 126/47 | 606/47 |
All W-row entries ≥ 0. Dual optimal!
Read the diet answer (primal): W-row under s₁ = 120/47 → x = 120/47 ≈ 2.55 chicken meals. W-row under s₂ = 126/47 → y = 126/47 ≈ 2.68 rice bowls.
Strong duality: Min Z = Max W = 606/47 ≈ $12.89. The primal and dual always agree at the optimum!
💰 Shadow Prices (Cost of Stricter Requirements)
In minimization, shadow prices tell you how much more expensive the diet gets if requirements increase. They’re the dual variables at optimum:
💪 Protein Shadow Price
$0.132 per extra gram
u₁ = 31/235. If the trainer demands 91g protein instead of 90g, the minimum diet cost rises by ~$0.13. Protein is expensive to add because chicken costs $4.
⚡ Carbs Shadow Price
$0.0085 per extra gram
u₂ = 2/235. If the trainer demands 121g carbs instead of 120g, cost rises by less than a penny. Carbs are cheap because rice only costs $1.
Protein is 15× more expensive than carbs! This makes intuitive sense: chicken ($4/meal) is the main protein source, while rice ($1/meal) covers carbs easily. If you could relax one requirement, relax protein — you’d save much more.
In minimization, shadow prices mean the opposite: in Max problems, a higher shadow price meant "this resource is valuable — get more!" In Min problems, it means "this requirement is costly — relaxing it saves money."
💡 Concept Spotlight: The Beautiful Symmetry of Duality
Duality is one of the deepest ideas in optimization. Every LP has a twin:
Primal (Diet Problem)
• Variables: meal quantities (x, y)
• Objective: Minimize cost
• Constraints: Meet nutrient minimums (≥)
• Shadow prices: nutrient costs (u₁, u₂)
Dual (Pricing Problem)
• Variables: nutrient prices (u₁, u₂)
• Objective: Maximize nutrient value
• Constraints: Don’t overprice any food (≤)
• Shadow prices: meal quantities (x, y)
Strong Duality Theorem: At optimality, Min Z = Max W. Always. The primal and dual are two sides of the same coin — the dual’s shadow prices ARE the primal’s variables, and vice versa. This is why we could read x and y directly from the dual’s Z-row.
🤔 What If? (Sensitivity Analysis)
Exploring how changes affect the cheapest diet.
Q: What if the trainer demands 120g protein instead of 90?
Extra 30g × shadow price $0.132/g = +$3.96. New minimum cost ≈ $16.85. The mix shifts toward more chicken (the protein source) and fewer rice bowls.
Q: What if chicken price dropped to $2 per meal?
Chicken becomes much more competitive. The optimal shifts heavily toward chicken. Eventually, "all chicken" might become optimal if it’s cheap enough to cover both nutrients affordably.
The threshold: the basis changes when chicken’s cost coefficient crosses the allowable decrease range from sensitivity analysis.
Q: What if we added a fat limit: 2x + 8y ≤ 30?
Now we have a mixed problem: two ≥ constraints AND one ≤ constraint. The feasible region gets more restricted (bounded on one side). Currently x=2.55, y=2.68: fat = 2(2.55)+8(2.68) = 26.54 ≤ 30 ✓. This constraint is non-binding, so the optimal doesn’t change.
Q: What if we added a third food: Eggs at $2/meal with 15g protein, 2g carbs?
3 variables, 2 constraints. Eggs have good protein-per-dollar ($2 for 15g vs chicken’s $4 for 30g — same ratio!). But eggs have almost no carbs (2g), so you’d still need rice or a lot of eggs. The optimal might include some eggs to reduce cost while maintaining protein.
⚠ Common Mistakes in This Mission
Treating ≥ like ≤. Writing 30x + 5y ≤ 90 instead of ≥ 90 flips the feasible region entirely. ≤ means "at most" (an upper bound); ≥ means "at least" (a lower bound). The entire solution changes!
Using slack variables for ≥ constraints. Slack variables ADD unused capacity. With ≥, you SUBTRACT the surplus. Use s (surplus), not slack. Getting this wrong makes the initial tableau infeasible.
Forgetting the origin is infeasible. Students often set up the tableau starting at (0,0). But with ≥ constraints, (0,0) violates everything! You need Big-M, Two-Phase, or the Dual method to find a valid starting corner.
Mixing up Min and Max shadow price interpretation. In Max, high shadow price = "get more of this resource!" In Min, high shadow price = "this requirement costs you — relax it to save money." They’re conceptual opposites.
🌍 Where You’ll See This in Real Life
📊 The Original Diet Problem
George Stigler posed the "minimum cost diet" in 1945 — finding the cheapest combination of 77 foods meeting all nutritional needs. He solved it by hand (took weeks!). Dantzig later solved it instantly with Simplex. It’s literally the problem that helped create LP.
🏭 Manufacturing
Factories minimize production cost while meeting quality standards (strength ≥ X, purity ≥ Y). The constraint "at least this good" is a ≥ constraint. Every steel mill and pharmaceutical company solves this daily.
👨⚕️ Healthcare
Hospitals minimize treatment cost while ensuring patients get at least the required doses of medication, minimum hours of therapy, and minimum nutritional intake. Exact same structure as our diet problem.
🚚 Supply Chain
Companies minimize shipping costs while meeting delivery guarantees ("at least 95% on-time," "at least 1000 units per warehouse"). Minimization with ≥ constraints is everywhere in logistics.
🧠 Why does math play games?
The Climber
The Simplex method is like a blind climber. It feels which way is "UP" (more money) and takes a step that way until it hits a wall.
The Walls
Constraints aren't bad! They narrow down the search. The answer is ALWAYS tucked into a "corner" where walls meet.
The Pivot
"Pivoting" is just math-speak for "Changing your mind". If selling LEGO cars isn't working, pivot to Battle Bots!