A shop has limited money and limited space. A factory has limited machine hours. A diet must contain enough vitamins at the lowest cost. Linear programming turns each of these into a picture: the rules become lines that fence off a region of possible choices, and the quantity to make as large (or small) as possible becomes a family of parallel lines. The best choice is always found at a corner of the region.
A furniture dealer must decide how many tables and chairs to buy. Which mix earns him the most profit?
| cost | profit | |
|---|---|---|
| one table | Rs 2500 | Rs 250 |
| one chair | Rs 500 | Rs 75 |
Rs 50,000 buys 20 tables.
He could afford 100 chairs but can store only 60.
10 tables and 50 chairs beat both. But which mix is best?
Problems that seek to maximise (or minimise) profit, cost or resources are optimisation problems.
When every relation involved is linear, it is a linear programming problem (LPP). “Programming” means planning.
Turn the story into maths. Name the unknowns, write each rule as an inequality, and write the profit as a formula.
The numbers to be decided are the decision variables. They cannot be negative: these are the non-negative restrictions.
Money: 2500x + 500y ≤ 50000, which is 5x + y ≤ 100 after dividing by 500. Space: at most 60 pieces. These rules are the constraints.
The profit is the objective function. In general a linear objective function is Z = ax + by, with a and b constants.
This is the dealer’s problem, written as an LPP.
The furniture dealer, formulated and solved.
Shade the allowed side of each rule. The part where all the shadings overlap is the feasible region.
A linear inequality like this is a half-plane: all the points on one side of its boundary line, here 5x + y = 100.
The region common to all the constraints, including x ≥ 0 and y ≥ 0, is the feasible region.
How to shade one rule
Every point in the region, boundary included, is a feasible solution. For the dealer, (10, 50) is one.
Any point outside the region is infeasible. For the dealer, (25, 40) is: 25 + 40 = 65 pieces is more than 60.
A feasible point that gives the optimal value of Z is an optimal solution.
There are infinitely many feasible points, but only the corners need checking. If a best value exists, it sits at a corner.
If Z = ax + by has an optimal value on the feasible region R (a convex polygon), it occurs at a corner point (vertex) of R.
If R is bounded (it fits inside a circle), Z has both a maximum and a minimum on R, each at a corner.
For different k these lines are all parallel. Slide one across the region: the last point it touches is a corner.
How to use it: the corner point method
Maximise 4x + y; x + y ≤ 50, 3x + y ≤ 90.
Minimise 200x + 500y; x + 2y ≥ 10, 3x + 4y ≤ 24.
Min and max 3x + 9y; x + 3y ≤ 60, x + y ≥ 10, x ≤ y.
When the region runs on for ever, a best value may not exist. When the rules contradict each other, there is no region at all.
If R is unbounded, a maximum or minimum may not exist. But if it does, it is at a corner.
M is the largest corner value. It is the maximum only if this open half-plane has no point in common with R. Otherwise Z has no maximum.
m is the smallest corner value. It is the minimum only if this open half-plane has no point in common with R. Otherwise Z has no minimum.
If the constraints contradict each other, there is no feasible region, so no solution at all.
In every case the feasible region, when it exists, is convex.
Minimise −50x + 20y on an unbounded region.
x + y ≥ 8 and 3x + 5y ≤ 15.
This chapter has no multiple-choice questions in the textbook, so these twelve test the ideas themselves. Tap an option to check it and see the reasoning.
An LPP finds the optimal (maximum or minimum) value of a linear objective function Z = ax + by, subject to linear constraints and non-negative decision variables.
Each constraint is a half-plane; their common part is the feasible region. Feasible solutions lie in it; the best one is the optimal solution.
Corner point method: find the corners, evaluate Z at each. Bounded region: largest value = maximum, smallest = minimum.
Unbounded region: M is the maximum only if ax + by > M misses the region; m is the minimum only if ax + by < m misses it.
Two corners with the same optimal value: every point of the segment joining them is optimal. Contradictory constraints: no feasible region.
Independently formulated the first linear programming problem: the transportation problem.
Described the optimal diet problem.
Invented the simplex method, which solves any linear programme in a finite number of steps.
Awarded the Nobel prize in economics for their work on linear programming.
Each walkthrough is solved from scratch and drawn as it goes: one boundary line per constraint with the side that satisfies it, the overlap that forms the feasible region, its corner points, the value of Z at each, and the conclusion, with the dashed level line of Z through the optimum. Unbounded regions get the half-plane test in pink. Press Next step (or Play); each step is explained in detail under the controls, and the Try-it slides a level line Z = k across the region.
Words become variables, constraints and an objective; then the corner point method finds the best mix.
A maximum, a minimum with a "≥" constraint, and a tie along a whole edge.
The smallest corner value is not always the minimum.
No point satisfies every constraint.
A bakery with limited flour and oven time, the cheapest healthy diet, a farmer with limited land and water, a delivery truck with weight and space limits, and an advertiser who needs a minimum audience: each is a linear programme. Move the sliders and watch the best corner change.
A bakery makes x cakes and y loaves a day. Flour: 200 g per cake and 100 g per loaf, 5 kg available, so 2x + y ≤ 50. Oven: 25 min per cake and 50 min per loaf, 1000 min available, so x + 2y ≤ 40. Profit: Rs 30 a cake and Rs p a loaf. Change p and see which corner wins.
A diet must contain at least 8 units of vitamin and 6 of mineral. Food F₁ (x units, Rs 4 each) gives 3 vitamin and 1 mineral; food F₂ (y units, Rs c each) gives 1 vitamin and 2 mineral. You can always eat more, so the region is unbounded, but the cost has a minimum.
A farmer plants x acres of wheat and y of rice. Land: x + y ≤ L acres. Water: wheat needs 2 units an acre and rice 4, with 32 units available: 2x + 4y ≤ 32. Profit Rs 3000 an acre of wheat and Rs 4000 of rice. Buy more land and see how far the best corner moves.
A truck carries x boxes of type A (20 kg, 1 m³) and y of type B (10 kg, 2 m³); the limits are 400 kg and 50 m³, and at least 5 boxes of A must go: 2x + y ≤ 40, x + 2y ≤ 50, x ≥ 5. Earnings Z = 10x + 8y. Press Play to sweep the level line Z = k across the region.
An advertiser buys x TV slots and y radio slots. Audience A: 3x + y ≥ 9 (thousands). Audience B: x + 2y ≥ 8. Cost Z = 5x + 3y (thousand rupees). Toggle the test: the half-plane Z < 19 misses the region, so 19 is the minimum; the half-plane Z > 40 overlaps it, so there is no maximum cost.
Decide first, then tap each card.
All 10 questions of Exercise 12.1 have an animated walkthrough (the chapter has no multiple-choice questions). Pick a question from the chips, then press Play or step through with Next. A second player, clearly marked Beyond the book, adds three extra problems: two word problems (a toy maker and a diet) and a tie along an edge.
Bounded and unbounded regions, a fractional corner, ties along an edge, a problem with no maximum and one with no feasible region.
Extra practice, not in this NCERT edition: formulate first, then solve.
Linear programming uses seven ideas from earlier classes: turning a story into inequalities, drawing a straight line, reading an inequality as a half-plane, overlapping several half-planes, finding where two lines meet, the level lines of a linear function, and telling a bounded region from an unbounded one. Every example and exercise links here exactly where you need it, and a button takes you straight back to the problem.
A word problem becomes an LPP in three moves.
| the words | the inequality |
|---|---|
| “at most 60 pieces” | x + y ≤ 60 |
| “at least 8 units of vitamin” | 3x + y ≥ 8 |
| “Rs 2500 each, Rs 50,000 in total” | 2500x + 500y ≤ 50000 |
A linear equation in x and y is a straight line, and two points fix a line. The easiest two are the intercepts.
The point on the y-axis.
The point on the x-axis. Join the two points.
The line passes through the origin, so pick one more point, for example x = 1.
If a = 0 the line is horizontal (y = c/b); if b = 0 it is vertical (x = c/a).
Every point on one side of ax + by = c gives ax + by bigger than c; every point on the other side gives smaller.
This is one whole side (a half-plane) together with the line.
Strict inequalities leave out the line itself.
Which side? Test a point
Each inequality shades a half-plane. A point satisfies all of them only if it is in every shaded half-plane: the overlap. In linear programming this overlap (with x ≥ 0, y ≥ 0) is the feasible region. If the shadings have no common part, the system has no solution.
A corner of the feasible region where two boundary lines cross lies on both lines, so its coordinates satisfy both equations.
Solve them by elimination
Subtract the first equation from the second.
Chapters 3 and 4 give this method too.
Where is Z = 4x + y equal to 40? On the line 4x + y = 40. Equal to 80? On 4x + y = 80.
All these level lines have the same slope −4, so they are parallel, and a bigger k moves the line further out.
Put a polygon on the page and slide the line. It first touches the polygon at a corner, sweeps across, and last touches it at a corner (or along a whole edge, if the edge is parallel to the level lines). That is why the optimum is always at a corner.
Two words describe the shape of a feasible region: bounded (or not) and convex.
A region is bounded if some circle encloses it; otherwise it is unbounded (it goes on for ever in some direction).
A region is convex if the segment joining any two of its points stays inside it. Every half-plane is convex, and an overlap of convex sets is convex, so every feasible region is convex: that is what makes the corner point theorem work.
On a bounded region the level lines must stop somewhere, so Z has a maximum and a minimum; on an unbounded one they may go on for ever.
Leave your email and we will write when a new chapter or a new set of worked solutions is ready. That is all we use it for, and you can ask to be taken off the list at any time.
You are on the list. We will email you when new chapters are added, and for nothing else.