Linear Programming (2D)

2-variable LP: feasible region, corner-point optimization

Worked example — Linear Programming (2D)

Maximize	3x + 2y

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

A feasible region is not a promise of an answer 🖖

The corner rule has a precondition that is easy to skip: an optimum has to exist at all. Load the unbounded preset — maximise 2x + y subject to x ≥ 0, y ≥ 0, x + y ≥ 2 — and the feasible region is perfectly non-empty, yet no corner is best, because you can walk north-east forever and keep improving. So this tool returns one of three verdicts rather than one: optimal, infeasible, or unbounded. It reaches the third by testing for an improving recession direction, not by failing to find a vertex. Switch that same preset to minimise and a finite answer appears immediately at (0, 2). Feasibility and solvability are separate questions.

Best answers hide at the corners 🖖

In plain terms, you are juggling limited resources under several rules at once, and each inequality slices off part of the plane. Where all the rules overlap is the feasible region, and every point inside it is a valid plan. Because a straight objective keeps improving in one direction, the best plan lands at a corner where constraints meet. The takeaway: to optimize, you never test every point — just the handful of corners.

How a diet problem foreshadowed Simplex 🖖

In 1945 economist George Stigler tackled the cheapest diet meeting all nutritional needs, a linear program with 77 foods. Lacking an algorithm, he guessed cleverly and got about $39.93 per year (1939 prices). When Dantzig's Simplex method solved it exactly in 1947, the true minimum was $39.69 — Stigler's hand estimate was off by only about 24 cents a year. Dry economics thus became one of the founding case studies of linear programming.

LINEAR PROGRAMMING — WHY YOU ONLY EVER CHECK THE CORNERS

Which Linear Programming Case Are You In?

Every linear program asks the same thing: push a straight-line objective as far as it will go across a region fenced in by straight-line constraints. Because both are straight, the best point can only ever be a corner — which is why the method is to list the corners and compare. Which case you are in depends on whether that region pens the objective in at all, and whether the corner it hands you is a number you can actually use.

A bounded region — the optimum sits on a corner z = 10 → (2, 2)

The best corner is fractional — and that is a different problem z = 24 → (8/3, 8/3)

An unbounded region with a bounded answer min z = 13

No finite optimum — and checking corners will not tell you z → ∞

A bounded region — the optimum sits on a corner

What you know: An objective to maximise and enough ≤ constraints to close the region off. The feasible set is a polygon.

What to check: z = 10 → (2, 2)

Worked example: Maximise 3x + 2y over x + y ≤ 4, x ≤ 2, y ≤ 3. The corners are (0,0), (2,0), (2,2), (1,3), (0,3), and z = 10 at (2,2) beats all of them.

Open this case: Diet problem

The objective line slides up and to the right until it is just touching the polygon at a single corner.

The best corner is fractional — and that is a different problem

What you know: A bounded region again, but the corner the objective picks does not land on whole numbers.

What to check: z = 24 → (8/3, 8/3)

Worked example: Maximise 5x + 4y over 2x + y ≤ 8, x + 2y ≤ 8, x ≤ 4, y ≤ 4. The optimum is z = 24 at (8/3, 8/3) — about (2.67, 2.67).

Open this case: Factory output

The best corner is fractional — and that is a different problem. The two binding constraints cross away from the grid lines, so the best corner has fractional coordinates. A bounded region again, but the corner the objective picks does not land on whole numbers. — The two binding constraints cross away from the grid lines, so the best corner has fractional coordinates.

An unbounded region with a bounded answer

What you know: Minimising against ≥ constraints. The feasible region runs off to infinity, but the objective still has a floor.

What to check: min z = 13

Worked example: Minimise 2x + 3y over x + y ≥ 6, x ≥ 2, y ≥ 1. The region is infinite, yet the minimum is z = 13 at (5,1).

Open this case: Min cost

An unbounded region with a bounded answer. The region extends away from the origin without limit, but the objective is minimised at a corner near it. Minimising against ≥ constraints. The feasible region runs off to infinity, but the objective still has a floor. — The region extends away from the origin without limit, but the objective is minimised at a corner near it.

No finite optimum — and checking corners will not tell you

What you know: The objective improves along a direction the constraints never block. There is no best point.

What to check: z → ∞

Worked example: Maximise 2x + y over x + y ≥ 2, x ≥ 0, y ≥ 0. Travel along increasing x forever and the objective grows forever; the answer is unbounded.

Open this case: Unbounded

No finite optimum — and checking corners will not tell you. The shaded region is open to the upper right, and the objective keeps improving along it forever. The objective improves along a direction the constraints never block. There is no best point. — The shaded region is open to the upper right, and the objective keeps improving along it forever.

References (3)

The diet problem in the history block: Stigler, G. J. (1945). "The Cost of Subsistence." Journal of Farm Economics 27(2), 303.
Simplex, and the vertex theorem it relies on: Dantzig, G. B. Linear Programming and Extensions. Princeton University Press, 1963.
Unboundedness and recession directions, the tool’s third verdict: Boyd, S. & Vandenberghe, L. Convex Optimization. Cambridge University Press, 2004, §2.5. ISBN 978-0-521-83378-3.

Problem solved in full

The Diet problem to maximise Z = 3x + 2y 5 steps
Which corner wins, and what is the corner next to it worth? This is Diet problem: maximise Z = 3x + 2y subject to x + y ≤ 4, x ≤ 2 and y ≤ 3, with x and y both at least 0.
1. Take any two feasible points and walk the straight segment between them. A linear objective along that walk is a weighted average of its two end values, and a weighted average never exceeds the larger end. So no point strictly between two others can be the unique best, and applying that in every direction in turn strands the optimum at a corner.
  
  $Z (λ A + (1 - λ) B) = λ Z (A) + (1 - λ) Z (B) \leq max {Z (A), Z (B)}, 0 \leq λ \leq 1$
2. A corner is where two boundary lines cross, so the candidates come from taking the five lines two at a time. Ten pairs, two of them parallel, and only five of the remaining eight satisfy the constraints they were not built from — x + y = 4 meets x = 0 at (0, 4), which breaks y ≤ 3.
  
  ${x + y = 4, x = 2} \Rightarrow (2, 2); {x + y = 4, y = 3} \Rightarrow (1, 3); (0, 0), (2, 0), (0, 3)$
3. Five arithmetic evaluations and one comparison, and the search is finished. There is no interior left to test and no edge left to walk.
  
  $Z = 3 x + 2 y : 0, 6, 10, 9, 6 ⟹ (x^{*}, y^{*}) = (2, 2), Z^{*} = 10$
4. At the winning corner x + y = 4 and x = 2 are both tight, while y = 2 sits a full unit under its ceiling of 3. A constraint with room to spare is limiting nothing, so relaxing it changes nothing; the other two are worth re-solving with one more unit each.
  
  $b_{1} : 4 \to 5 \Rightarrow (2, 3), Z = 12, y_{1} = 2; b_{2} : 2 \to 3 \Rightarrow (3, 1), Z = 11, y_{2} = 1; y^{*} = 2 < 3 \Rightarrow y_{3} = 0$
5. Weight each of those three prices by how much of that resource the problem was given.
  
  $b_{1} y_{1} + b_{2} y_{2} + b_{3} y_{3} = 4 (2) + 2 (1) + 3 (0) = 10 = Z^{*}$
Answer

The tool prints x* = 2, y* = 2 and Z* = 10, the third of the five corner values. The numbers from step 4 — 2, 1 and 0 — are the shadow prices, and they answer a question the chart cannot: one more unit of the x + y budget is worth twice one more unit of x, and one more unit of y is worth nothing at all. Step 5 is strong duality, and it is not an accident of these figures; the prices weighted by the supplies always reproduce the optimum, which is exactly what makes them prices. A shadow price also comes with an expiry date. The x + y budget pays 2 per unit only as far as 5, where the corner reaches (2, 3), the other two constraints go tight and Z sticks at 12 — past that point the price is 0 and every extra unit bought is wasted.

$max {c^{⊤} x : A x \leq b, x \geq 0} = min {b^{⊤} y : A^{⊤} y \geq c, y \geq 0} = 10$

By the 42Math team · Updated 2026-08-17

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Statistics & Finance lessons →

Example problems

Diet problem - Classic bounded maximization: optimum occurs at a feasible corner.
Factory output - Intersecting capacity constraints create a polygonal feasible region.
Min cost - Minimization over lower-bounded constraints picks the closest feasible corner to origin in objective direction.
Unbounded - Feasible region can be unbounded, so objective may not have a finite optimum.