Why the Best Answer to a Linear Programme Always Sits at a Corner

When a linear programming problem has only two variables, every possible plan is a point on a graph. Shading the constraints shows all the allowed plans at once, and a remarkable fact makes the best one easy to find: it always sits at a corner of the shaded region.

This lesson covers the graphical method, feasible and infeasible regions, the existence of optimal solutions, and finding the optimum with up to three constraints.

Draw each constraint's boundary line, shade the side that satisfies it, find the region common to all constraints, list the coordinates of its corner points, and evaluate the objective function at each corner to pick the maximum or minimum.

Corner point theorem. If an optimal value exists, it occurs at a corner point of the feasible region.

Worked example. Maximise $Z=3x+2y$ subject to $x+y\le 4$, $x+3y\le 6$, $x\ge 0$ and $y\ge 0$.

- Corner points: $(0,0)$, $(4,0)$, $(0,2)$ and the intersection of $x+y=4$ with $x+3y=6$, which is $(3,1)$
- Values of Z: 0, 12, 4 and $9+2=11$
- Maximum $Z=12$ at $(4,0)$

An everyday example. A tiffin service choosing how many veg and non-veg meals to cook within limits on cooks and ingredients can plot its options and read the best plan off a corner.

The substance. The optimum can sit where only one resource is fully used — at $(4,0)$ all of the first resource is used, but not all of the second.

The feasible region is the set of points satisfying every constraint; it is bounded if it can be enclosed within a circle and unbounded if it stretches without limit, points outside it form the infeasible region, and if no point satisfies all the constraints the feasible region is empty.

Types of region:

- Bounded — a closed polygon, as for $x+y\le 4$ with $x,y\ge 0$
- Unbounded — open in some direction, as for $x+y\ge 4$ with $x,y\ge 0$
- Empty — contradictory constraints, as for $x+y\le 2$ with $x+y\ge 5$

Worked example. For $x+2y\ge 8$, $3x+2y\ge 12$, $x\ge 0$ and $y\ge 0$, the region lies above both lines and is unbounded. Its corner points are $(0,6)$, $(8,0)$ and the intersection of the two lines, $(2,3)$.

Checking points. $(1,1)$ gives $1+2=3$, which fails $x+2y\ge 8$, so it is infeasible; $(4,4)$ satisfies both constraints and is feasible.

An everyday example. A diet that must supply at least certain amounts of protein and iron has an unbounded feasible region — eating more always stays allowed, even though it costs more.

The substance. An unbounded region does not spoil every problem — a minimum can still exist even when no maximum does.

A feasible solution is any point of the feasible region and an optimal feasible solution is one giving the best value of Z; for a bounded region an optimum always exists, but for an unbounded region you must check whether Z can keep improving, using the half-plane test.

The half-plane test. Let M be the largest corner value of $Z=ax+by$. If the half-plane $ax+by>M$ shares no point with the feasible region, M is the maximum; otherwise there is no maximum. The same test with $<$ and the smallest corner value decides a minimum.

Worked example. Minimise $Z=3x+5y$ over the unbounded region above, with corners $(0,6)$, $(2,3)$ and $(8,0)$.

- $Z(0,6)=30$, $Z(2,3)=6+15=21$ and $Z(8,0)=24$
- The smallest corner value is 21, at $(2,3)$
- The half-plane $3x+5y<21$ contains no feasible point, so 21 is the minimum

No maximum. In this region, $Z=3x+5y$ grows without limit as x or y increases, so no maximum exists.

An everyday example. A hostel mess looking for the cheapest meal plan that meets nutrition targets has a minimum cost, even though it could always spend more.

The substance. Checking only the corners is not enough for an unbounded region — the half-plane test is what proves that an optimum exists.

Plot all the constraints with the non-negativity restrictions, find every corner of the feasible region by solving pairs of boundary equations, evaluate Z at each corner, and choose the best value — checking for unboundedness where needed.

Worked example. A carpenter earns ₹300 per chair and ₹500 per table. Maximise $Z=300x+500y$ subject to $2x+3y\le 60$ (carpentry hours), $x+2y\le 36$ (polishing hours), $y\ge 5$ (orders) and $x\ge 0$.

- Corners: $(0,5)$; $(22.5,5)$ on $2x+3y=60$; $(12,12)$, where the two resource lines meet; and $(0,18)$ on $x+2y=36$
- $Z(0,5)=2500$ and $Z(22.5,5)=6750+2500=9250$
- $Z(12,12)=3600+6000=9600$ and $Z(0,18)=9000$
- Maximum profit: ₹9600, from 12 chairs and 12 tables

An everyday example. A small garment unit in Ludhiana planning next week's output of shirts and trousers uses exactly this corner-by-corner comparison.

The substance. When two corners give the same best value, every point on the edge joining them is optimal — the problem then has infinitely many optimal solutions.