The Corner That Wins Linear Programming

A furniture dealer has Rs 50,000 to invest and storage space for at most 60 pieces, choosing between two items to stock: tables, costing Rs 2500 each with a profit of Rs 250 per sale, and chairs, costing Rs 500 each with a profit of Rs 75 per sale. Buying only tables, the whole budget stretches to 20 tables (50000 divided by 2500), for a total profit of Rs 5000. Buying only chairs, the budget alone would allow 100 chairs, but the storage limit of 60 pieces caps it at 60 chairs, for a total profit of Rs 4500. A mixed strategy, say 10 tables and 50 chairs, uses the ENTIRE budget (10 times 2500 plus 50 times 500 comes to exactly Rs 50,000) and the entire storage space (10 plus 50 is exactly 60), for a total profit of Rs 6250 -- already better than either pure strategy. With countless other combinations still possible, guessing one at a time is no way to be certain the true best combination has been found; a systematic method is needed, and building one is exactly the business of this chapter.

Calling the number of tables x and the number of chairs y, every real choice must obey x >= 0 and y >= 0 (the non-negative restrictions -- negative furniture makes no sense). The investment limit becomes 2500x + 500y <= 50000, which simplifies by dividing through by 500 to 5x + y <= 100, and the storage limit becomes x + y <= 60. These inequalities are called the constraints of the problem. The dealer's actual goal, maximising profit, is written as a single linear expression, Z = 250x + 75y, called the objective function -- the one quantity the whole problem is built to optimise. The letters x and y themselves, the quantities actually being decided, are called the decision variables. Putting it all together: maximise Z = 250x + 75y subject to 5x + y <= 100, x + y <= 60, x >= 0, y >= 0. Any problem with exactly this shape -- an objective function optimised subject to linear constraints -- is called a linear programming problem.

Plotting the two constraint lines 5x + y = 100 and x + y = 60 on a graph, together with the axes x = 0 and y = 0, marks out a four-sided shaded region with corners at O(0,0), A(20,0), B(10,50) and C(0,60) -- every point inside or on the boundary of this region satisfies ALL four constraints simultaneously, and is called a feasible solution. The whole shaded region OABC is called the feasible region (or solution region) for the problem. The earlier mixed strategy, 10 tables and 50 chairs, is exactly the point B(10,50), confirming it as a genuine feasible solution -- and so are (0,60) and (20,0). A point like (25,40), however, is infeasible: checking the investment constraint, 5(25) + 40 = 165, which is far more than the allowed 100, so this point lies entirely outside the feasible region no matter how reasonable it might look at first glance. Every point outside the shaded region, like this one, is called an infeasible solution.

With infinitely many feasible points inside OABC, checking every one by hand is impossible -- yet two theorems settle the entire question. Theorem 1 states that IF the objective function Z has an optimal (maximum or minimum) value at all, that value must occur at a corner point (vertex) of the feasible region, a point where two boundary lines meet -- never at some point buried in the open interior. Theorem 2 goes further: if the feasible region is bounded (meaning it can be enclosed inside some large enough circle), Z is GUARANTEED to have both a maximum AND a minimum, and each one occurs at a corner point. Since OABC is clearly bounded, evaluating Z = 250x + 75y at just its four corners is enough: Z(O) = 0, Z(A) = 250(20) = 5000, Z(B) = 250(10) + 75(50) = 2500 + 3750 = 6250, and Z(C) = 75(60) = 4500. The largest of these, 6250 at B, is therefore the guaranteed maximum -- the dealer should buy 10 tables and 50 chairs, exactly the combination found earlier by trial, now confirmed as truly optimal rather than merely lucky. This four-step process -- find the corners, evaluate Z at each, then pick the extreme value -- is called the Corner Point Method.

The exact same method, unchanged, finds a MINIMUM instead of a maximum. Consider (dropping the story and working with bare numbers, exactly as the textbook itself does at this point): minimise Z = 200x + 500y subject to x + 2y >= 10, 3x + 4y <= 24, x >= 0, y >= 0. Plotting these constraints gives a bounded feasible region ABC with corners (0,5), (4,3) and (0,6). Evaluating Z at each: Z(0,5) = 2500, Z(4,3) = 200(4) + 500(3) = 800 + 1500 = 2300, and Z(0,6) = 3000. The smallest of these, 2300 at (4,3), is the guaranteed minimum, by the very same Theorem 2 used a moment ago for a maximum. Nothing about the Corner Point Method changes when the goal flips from 'biggest' to 'smallest' -- find the corners, evaluate Z at each, and this time pick the smallest value instead of the largest.

Theorem 2's guarantee of both a max AND a min depends entirely on the feasible region being bounded -- and some feasible regions are not. Consider minimising Z = -50x + 20y subject to 2x - y >= -5, 3x + y >= 3, 2x - 3y <= 12, x >= 0, y >= 0: this feasible region is unbounded, stretching away without end, with corners at (0,5), (0,3), (1,0) and (6,0). Evaluating Z gives 100, 60, -50 and -300 respectively -- the smallest found is -300, at (6,0), but since the region is unbounded, Theorem 2 simply does not apply, and this smallest CORNER value is not automatically the true minimum. The extra check: graph the open half-plane -50x + 20y < -300 and see whether it shares any point with the feasible region. It does -- so points exist in the feasible region giving Z even smaller than -300, and in fact Z can be driven arbitrarily negative by moving far enough along the unbounded direction. The honest conclusion is that Z has NO minimum value at all here, despite -300 looking like a perfectly good answer at first glance.

Occasionally the corner point method produces not one winning corner but two, tied. Consider minimising AND maximising Z = 3x + 9y subject to x + 3y <= 60, x + y >= 10, x <= y, x >= 0, y >= 0: the feasible region ABCD has corners A(0,10), B(5,5), C(15,15) and D(0,20). Evaluating Z gives 90, 60, 180 and 180 -- the minimum, 60, is unique, at B, but the maximum, 180, is shared EXACTLY by both C and D. This is not a coincidence: both C and D happen to sit on the same boundary line, x + 3y = 60, and Z here happens to equal exactly 3 times that same expression (3x+9y = 3(x+3y)), so Z is forced to equal 3(60)=180 at every single point along that entire edge, not just at its two endpoints. Whenever this happens, EVERY point on the line segment joining the two tied corners is equally optimal -- meaning a linear programming problem can have infinitely many correct answers at once, all sharing one optimal value, rather than a single unique best choice.

Sometimes there is no feasible region at all. Consider minimising Z = 3x + 2y subject to x + y >= 8, 3x + 5y <= 15, x >= 0, y >= 0: with x, y both non-negative and x + y forced to be at least 8, the smallest 3x+5y can possibly become (by making y as small as possible, since 5 is bigger than 3) is 3(8) + 5(0) = 24, reached right at the point (8,0) -- and moving away from that point along x+y=8 only makes 3x+5y larger still, never smaller. Since 24 is already far more than the allowed maximum of 15, the two constraints directly contradict each other: no combination of x and y, however chosen, can satisfy both at once. Graphing confirms it -- the two shaded regions from the two constraints simply never overlap. A linear programming problem built from self-contradictory constraints like this one is called infeasible, and correctly reporting 'no feasible solution exists' is itself the right, complete answer, not a sign that something went wrong.

Linear programming's origins are genuinely wartime: during the Second World War, when military operations had to be planned to economise expenditure and maximise damage to the enemy, problems of exactly this shape came to the forefront. The first such problem, now known as the transportation problem, was formulated independently in 1941 by the Russian mathematician L. Kantorovich and the American economist F. L. Hitchcock. In 1945, the English economist G. Stigler described another one: the problem of finding an optimal diet at minimum cost. Then in 1947, the American mathematician G. B. Dantzig invented the simplex method, an iterative procedure capable of solving any linear programming problem, no matter how many variables, in a finite number of steps -- still one of the most consequential algorithms in applied mathematics. Kantorovich, together with the American economist T. C. Koopmans, was awarded the Nobel Prize in Economics in 1975 for this pioneering work on the optimal allocation of resources. What began as a wartime planning tool now runs, quietly, behind airline schedules, delivery routes and factory production lines every single day.

The whole algebra journey began, back in Class 7, with a single letter standing in for one unknown number in one equation. Class 11 widened that idea into inequalities, carving out an entire RANGE of allowed values rather than one exact answer. This chapter widens it once more, into an entire SYSTEM of linear inequalities searched all at once, not merely for a range of acceptable choices but for the genuinely best one available, guaranteed correct by nothing more elaborate than checking a short, finite list of corners. It is a fitting near-final destination for this particular thread of algebra: the same letters-for-unknowns idea, grown up from solving one equation to optimising an entire business decision, still resting on exactly the same underlying logic that made 3x=12 solvable for x in the very first place.