Maximize cookies with limited ingredients! Must make at least 0.5 batches of each type.
A Linear Programming adventure for young mathematicians! Scroll down to learn how it works.
š Scroll down to learn how this math magic works! š
Select 2 variables to plot. Others are fixed at slider values.
š¤ Why doesn't the optimal look like a corner? This graph shows only 2 cookie types at a time, but our problem has 4! The optimal IS at a "corner" in 4D space, but when we slice down to 2D (holding the other cookies fixed), that corner might land along an edge instead. It's like how a corner of a 3D cube can look like it's on an edge when you draw its shadow!
š What the columns mean:
The ' means "extra beyond minimum 0.5". So S'=2 means Sugar batches = 0.5 + 2 = 2.5 total. The "s" variables track leftover ingredients - when s1=0, you've used ALL your flour!
š Current Corner (what we're making):
š Look at the graph above! The blue dot shows this corner. Each simplex step moves to a new corner with more cookies! (Tip: Change the graph axes to see how different cookie types change!)
What's Happening:
We start at a corner where we make just the minimum cookies. Then we "hop" to better corners by looking at the bottom row - negative numbers show us paths to MORE cookies! We keep hopping until there's nowhere better to go. That's the best answer!
| Ingredient | Sugar | Ginger | Pepper | Choco | On Hand |
|---|---|---|---|---|---|
| Flour | 2 | 4 | 2.5 | 2 | 15 |
| Powdered Sugar | 3 | - | 3 | - | 8 |
| White Sugar | 1.5 | 0.5 | 2 | 1 | 6.5 |
| Brown Sugar | - | 1 | - | 0.5 | 5 |
| Eggs | 1 | - | 2 | 1 | 12 |
| Yield (cookies) | 60 | 30 | 48 | 54 |
Learn the secrets behind finding the BEST cookie combo!
Imagine you're planning a pizza party, but you only have limited money, time, and ingredients. Linear Programming (we call it "LP" for short) is like having a super-smart helper that figures out the BEST way to use what you have!
In our cookie problem:
LP helps us find the "sweet spot" where we make the MOST cookies without running out of anything!
Think of this like a treasure map! We're going to draw a picture that shows us where the "treasure" (best cookie combo) is hiding.
Each ingredient limit creates a line on our map. If you make too many cookies, you cross the line and run out! The colored lines on the graph above show these limits.
The green shaded area is the "safe zone" where you don't run out of ANYTHING. Any point inside this zone is a valid cookie combo!
The dashed green lines show combos that make the same number of cookies. Lines further from the corner = more cookies!
Here's the magic: The best answer is ALWAYS at a corner of the safe zone! Push the profit line as far as possible while staying in the green.
š¤ Why corners? Imagine pushing a book across your desk until it hits the edge. It always stops at a corner! Math works the same way - the farthest you can go is always at a corner.
The Simplex method is like playing a video game where you hop from corner to corner, always trying to get a higher score!
We start at a corner where we're making the minimum (0.5 batches of each). This is our "home base" - safe but not many cookies yet!
At each corner, we check all the paths. The green numbers in the table tell us "go this way for more cookies!" We pick the path that helps the most.
We "pivot" (that's the math word for "hop") to the next corner. The yellow highlighted cell shows where we're pivoting!
We keep hopping until there's nowhere better to go. When all the numbers in the bottom row are zero or positive (no more green), we've found the best corner!
The "RHS" column (right side) tells us how many batches of each cookie to make. The bottom-right number is our total cookies!
š® Think of it like this: You're climbing a mountain in the fog. You can't see the top, but you can feel which way is "up" from where you stand. You keep walking uphill until every direction goes down - that's when you know you're at the peak!
These represent our cookie types. The little ' mark means we subtracted 0.5 (the minimum) so the math is easier. S' = Sugar batches minus 0.5.
These are "slack" variables - they track how much of each ingredient is LEFT OVER. If s1 = 3, you have 3 cups of flour unused!
"Right Hand Side" - shows either how much ingredient is left OR how many batches we're making of a cookie type (when it enters the "Basic" column).
This tracks our total cookies! Negative numbers = "we want more of this!" When all numbers are ā„ 0, we've maximized!
The Simplex finds the mathematically perfect answer, but we can only make cookies in half-batch steps!
1. Perfect Math Answer (Continuous): 314 cookies
S=0.5, G=1.08, P=0.5, C=4.21 batches
This is what Simplex finds - but 1.08 batches isn't real!
2. If You Just Round: 300 cookies š±
G=1.08 rounds to 1.0, C=4.21 rounds to 4.0
This is WORSE! Rounding doesn't give the best answer!
3. Best Real Answer (0.5 steps): 312 cookies ā
S=0.5, G=0.5, P=0.5, C=4.5 batches
This is actually different from rounding! You need special math to find it.
š The Integrality Gap = 314 - 312 = 2 cookies
This is the difference between the perfect math answer and the best real-world answer. Notice that just rounding (300) gives you a much worse answer than the true best (312)! Finding the REAL best discrete answer requires a different technique called "Integer Programming" - you can't just round!
š Used Everywhere: Airlines use LP to schedule flights, delivery trucks use it to plan routes, and factories use it to decide what to make!
š Birthday: The Simplex method was invented in 1947 by George Dantzig - that's over 75 years ago!
š Nobel Prize: Scientists who improved LP won the Nobel Prize in Economics!
šŖ Super Fast: Modern computers can solve LP problems with MILLIONS of variables in seconds!
(This is how mathematicians write our cookie problem - don't worry if it looks confusing!)
Maximize: Z = 60S + 30G + 48P + 54C (total cookies)
Subject to:
2S + 4G + 2.5P + 2C ā¤ 15 (flour limit)
3S + 3P ā¤ 8 (powdered sugar limit)
1.5S + 0.5G + 2P + C ā¤ 6.5 (white sugar limit)
G + 0.5C ā¤ 5 (brown sugar limit)
S + 2P + C ā¤ 12 (eggs limit)
S, G, P, C ā„ 0.5 (must make at least half a batch!)
S = Sugar cookie batches, G = Gingerbread batches, P = Peppermint batches, C = Chocolate batches