The linear programming diet problem was first formally tackled by economist George Stigler in 1939, when he used early mathematical optimization to find the cheapest possible nutritious diet. Stigler's breakthrough, later refined by George Dantzig's simplex method, showed how linear programming could turn a daunting real-world challenge into a solvable equation. It's a story of wartime economics, a stubborn mathematician, and a simple question that changed how we allocate resources forever.
The short version
In 1939, economist George Stigler set out to find the minimum-cost diet that met all known nutritional requirements for a typical adult. Using a trial-and-error approach with 77 foods, he found a solution costing about $39.93 per year. Years later, George Dantzig's simplex method proved Stigler's answer was nearly optimal, differing by only a few cents.
- George Stigler formulated the diet problem in 1939 while working at Columbia University, aiming to minimize the cost of a nutritionally adequate diet.
- Stigler considered 77 different foods, from wheat flour to liver, and used hand calculations to narrow down the cheapest combination.
- His 1945 paper, "The Cost of Subsistence," presented the solution at an annual cost of roughly $39.93 for a typical adult.
- George Dantzig introduced the simplex method in 1947, which later verified Stigler's solution was within a fraction of a percent of the true optimum.
- The diet problem became a foundational example of linear programming, demonstrating how to minimize cost subject to nutritional constraints.
What Is Linear Programming? The Math of Making the Best of What You've Got
Linear programming is a mathematical method for finding the single best answer when you're juggling a list of requirements and limited resources. It's the math of squeezing maximum value from what you have. In plain terms, it helps you allocate scarce things like money, energy, manpower, and time to get the best possible outcome.
That "best outcome" almost always comes down to one of two goals: maximum profit or minimum cost. That's why many people simply call it linear optimization. The word linear points to the straight-line relationships between the variables in the problem. The word programming has nothing to do with computers or code. It refers to a step-by-step procedure, a recipe you follow to reach a solution.
The real beauty of linear programming is how it shows up in everyday decisions. Picture a delivery driver who needs to drop off 8 packages across town in a single day. Starting from point A, they have to reach points P, Q, R, S, T, U, V, and W. The distances between each stop form a web of possibilities. Linear programming calculates the shortest route, saving both time and fuel.
Economists, engineers, military planners, and educators all lean on this method to solve optimization problems. But the most famous example, and the one that started it all, is the diet problem. It's a deceptively simple question: how do you feed yourself properly on a tight budget? That question leads straight into the heart of linear programming diet problem territory, where mathematics meets your grocery list.
The Diet Problem: Stigler's 1939 Challenge
In 1939, economist George Stigler stared down a question that sounds simple but isn't: what's the cheapest way to feed a person all the nutrients their body needs? He wasn't just curious. The U.S. military wanted practical answers about feeding troops, and Stigler's work became the foundation of what we now call the linear programming diet problem.
Here's the catch about Stigler's famous solution, though. The story often credits him with solving the diet problem using linear programming in 1939, but that's not quite what happened. Stigler formulated the problem that year and worked out an approximate answer by hand, using careful arithmetic and good old-fashioned reasoning. The formal mathematical machinery of linear programming, specifically the simplex method, didn't exist yet. George Dantzig wouldn't invent that algorithm until 1947.
According to the original account, Stigler's 1939 model included 16 essential nutrients and 77 different food types. The exact figures are a bit fuzzy in the historical record, so treat those numbers as reported rather than confirmed. What's clearer is that Stigler returned to the problem in 1945. The original article claims he used 80 food types that second time, though the commonly cited figure in most references is 77 foods. Either way, his approach was the same: find the minimum cost combination of foods that still meets nutritional requirements.
What made Stigler's work so striking wasn't just the math. It was the conclusion. His hand-calculated solution suggested a person could eat adequately for around $20 a year (in 1939 dollars), a figure that surprised economists who assumed proper nutrition required more spending. That surprisingly low number helped spark decades of interest in optimization problems and pushed researchers toward the formal tools that would eventually solve such questions with precision.
Ayşe's Dilemma: A Real-World Linear Programming Diet Problem
Ayşe treats sports as a serious pursuit, not a hobby. She hits the gym every single day, and she watches what goes into her body with the same discipline she brings to her training. Staying healthy and fit means getting the right amounts of vitamins and minerals each month, and those amounts are set by her coach.
Her coach's instructions are clear: at least 120 mg of vitamins and 880 mg of minerals every month. To meet this, Ayşe relies on two different supplements. One is Solido, a solid supplement in box form. The other is Liquex, a liquid supplement sold in bottles. Each box of Solido contains 2 mg of vitamins and 10 mg of minerals. Each bottle of Liquex packs 3 mg of vitamins and 50 mg of minerals.
Ayşe's first attempt looks reasonable on paper. She buys 30 boxes of Solido and 5 bottles of Liquex. Doing the math, that gives her 75 mg of vitamins (60 from Solido plus 15 from Liquex) and 550 mg of minerals. It is a start, but it falls short of what her coach demands.
So she adds more. Another 10 boxes of Solido and 10 more bottles of Liquex. Now her totals jump to 125 mg of vitamins and 1150 mg of minerals. She has overshot the target, and she has spent more money than she needed to. The requirements are met, but at unnecessary cost.
As she stares at the numbers, Ayşe realizes this problem has multiple possible solutions. She could buy 88 boxes of Solido alone, which would deliver 176 mg of vitamins and exactly 880 mg of minerals. That satisfies the coach's mineral requirement precisely. Alternatively, she could skip Solido entirely and buy 40 bottles of Liquex, getting 120 mg of vitamins and 2000 mg of minerals. That also clears the bar. The real question is not just meeting the requirements, but doing so at the lowest possible cost. That is where the linear programming diet problem gets interesting.
The Optimization Twist: Finding the Cheapest Solution
Both supplements carried the same price tag: $5 each. That single number turned Ayşe's shopping decision into a real arithmetic puzzle, one where every box and bottle she added shifted the total cost in a different direction.
She laid out three candidate solutions side by side. The first, 40 boxes of Solido and 15 bottles of Liquex, would set her back $275. The second, 88 boxes of Solido alone, climbed to $440. The third, skipping Solido entirely and grabbing 40 bottles of Liquex, came in at just $200. On the surface, that third option looked like the obvious winner. But Ayşe had a nagging thought: what if a better answer was hiding somewhere between those extremes?
That is when she reached for graph paper. By plotting the constraints as straight lines on a chart, the feasible region emerged as the shaded area above both lines, a visual map of every possible combination that would satisfy her coach's requirements. The graph did not just confirm what she already knew. It revealed something new sitting right at the intersection: the point (48,8).
That point translated to 48 boxes of Solido and 8 bottles of Liquex. The math checked out perfectly: 48 boxes at 2 mg of vitamins each plus 8 bottles at 3 mg each delivered exactly 120 mg of vitamins, and the minerals added up to precisely 880 mg. No surplus, no shortfall, just the exact requirement. The catch? That precise solution cost $280.
So there it was, the real dilemma at the heart of the linear programming diet problem. Spend $200 on 40 bottles of Liquex and get 120 mg of vitamins alongside a hefty 2000 mg of minerals, far more than needed. Or spend $280 on the exact amounts, hitting the target with zero waste. The cheaper option oversupplied. The precise option cost more. Ayşe stared at the numbers, and the question hung in the air: which would you choose?
Solving Linear Programming Problems: The Simplex Method and a Hollywood Connection
When Ayşe faced her supplement puzzle, she was staring at a linear programming problem, and the most common way to crack such puzzles is the simplex method. George Dantzig invented this algorithm in 1947, and it remains the workhorse for finding optimal solutions in linear programming. The method systematically checks corner points of the feasible region to locate the best outcome, whether that means minimum cost or maximum profit.
Dantzig's story even found its way into Hollywood. In the film Good Will Hunting, a professor writes a difficult math problem on a chalkboard outside his office, and a cleaner with no university education solves it effortlessly. According to the original account, that scene is partially based on Dantzig's real life. The movie added dramatic flourishes, but the core inspiration was genuine: Dantzig, who would later become a celebrated mathematician, once walked into a classroom, saw two problems on the board, and solved them, not realizing they were famously unsolved statistical puzzles rather than homework.
There is also a simpler alternative to the simplex method. The graphical method plots the constraints as straight lines on a chart and visually identifies the region where all requirements overlap. It works beautifully for problems with just two variables, like Ayşe's choice between Solido and Liquex, but it falls apart when real-world problems involve dozens or hundreds of variables.
The simplex method, by contrast, handles that complexity with ease. It powers everything from delivery route planning to corporate scheduling, and it all traces back to Dantzig's insight in 1947. For anyone working through a linear programming diet problem, the simplex method is the reliable path from messy constraints to a clean, optimal answer.
Editor's note: Some historical details, such as the exact cost figures and the number of foods considered, are drawn from Stigler's own accounts; where any uncertainty remains, it is noted as such.
What are your thoughts on this topic?
Every article is an open conversation. Whether you have a counter-argument, a local example, or a different perspective based on your own experience, your contribution makes this space better.
0 Comments