Chapter 12 — Linear Programming
A workshop has only so many hours, a farmer only so much money, a dietitian only so many ingredients. Linear programming turns every such limit into a straight line, finds the region of all possible plans, and picks the best plan from a handful of corner points.
A small furniture workshop in Jaipur makes tables and chairs. A table earns more than a chair, so why not make only tables? Because every table needs three hours at the carpentry bench, and the workshop has just thirty bench-hours a week; every piece also needs time at the polishing station, which is open only twenty hours. Make too many tables and the carpenters run out of time; make too many chairs and the polishers do. Somewhere among all the possible weekly plans is the one that earns the most — and finding it by trial and error, plan after plan, is slow and never tells you that you have really found the best.
In this chapter you learn a method that settles such questions completely. Each limit — “at most 30 hours”, “at least 8 kg of nitrogen”, “no negative chairs” — becomes a linear inequality in two variables, whose graph is a half-plane. All the limits together cut out a feasible region: the set of every plan that is actually possible. The quantity to be made as large or as small as possible — profit, cost, time — is a linear objective function $Z=ax+by$, and the lines $Z=k$ are parallel. Slide such a line across the region and you will see that the best value is always reached at a corner point. So instead of infinitely many plans you test only a few corners. The same idea, scaled up to thousands of variables, schedules airline crews, blends petrol in refineries and plans power-grid supply every day.
- draw the half-plane of a linear inequality $ax+by\le c$ (or $\lt,\ \ge,\ \gt$) using the boundary line and a test point;
- translate a word problem into a linear programming problem: name the decision variables, write the objective function, the constraints and the non-negative constraints;
- shade the feasible region of a system of linear inequalities and find all its corner points by intersecting the boundary lines;
- solve a linear programming problem by the corner point method, and explain the result with the sliding line $Z=k$;
- decide whether an unbounded feasible region has a maximum or minimum by testing an open half-plane, and recognise problems with no feasible solution or with many optimal solutions;
- answer the Board's 1-mark, 3-mark, 5-mark and case-study questions on linear programming.
Sections in this chapter
Linear Programming Problems and Their Formulation
Half-planes from scratch; the language of LP — objective function, decision variables, constraints; turning word problems into LPPs; the feasible region.
The Graphical Method: Bounded Feasible Regions
Iso-profit and iso-cost lines; the corner point theorems; the corner point method; ties and multiple optimal solutions.
Unbounded and Empty Feasible Regions
When a maximum or minimum fails to exist; the open half-plane test; problems with no feasible solution; minimum-cost mixtures.