Take a breath. Linear Programming is one of the friendliest chapters in Class 12 Maths, and here is the honest reason why: there is exactly one method, and once you can draw a straight line and read off where two lines cross, you can solve almost every question in the chapter. There is no long list of formulas to memorise. No tricky substitutions. Just a graph, a handful of corner points, and a little arithmetic.
The idea behind it is something you already do every day. You have limited time, limited money, limited patience — and you want the best possible result out of them. A shopkeeper has limited shelf space and wants maximum profit. A cook has limited ingredients and wants a meal with enough nutrition at the lowest cost. Linear Programming is simply the mathematics of squeezing the best out of limited resources — the same scarcity-and-choice problem that opens our Introduction to Microeconomics notes. In this chapter we will build that skill from absolute zero: what the words mean, how to shade an inequality, how to draw the region, and how to find the winning corner. Take it slowly, draw every graph yourself on paper, and this chapter will become one of your safest scoring areas.
What You’ll Learn
- What a Linear Programming Problem Actually Is
- The Vocabulary: Objective Function, Decision Variables, Constraints
- Graphing a Linear Inequality: the Half-Plane Idea
- Drawing the Feasible Region
- Corner Point Method: The Rule That Solves Everything
- Bounded Feasible Regions
- Unbounded Feasible Regions and the Extra Check
- When There Is No Solution, or Infinitely Many
- Turning a Word Problem Into an LPP
- Board-Style Full Solutions
Your Game Plan
- Spend one sitting on the vocabulary. If you cannot say what a constraint and an objective function are in your own words, everything after that feels vague.
- Practise shading single inequalities on graph paper until the origin test feels automatic — about ten of them is enough.
- Learn to find corner points by solving pairs of equations. This is really just simultaneous equations from Class 10 — revise that chapter if solving them feels rusty.
- Do the corner point method on bounded regions first. Get comfortable, then move to unbounded ones.
- Only after all that, attempt word problems. The maths is identical; the only new skill is choosing the two variables.
- Finish with the worksheet at the bottom. Draw a fresh graph for every question — never solve an LPP without a picture.
Study Notes
What a Linear Programming Problem Actually Is
Imagine you run a small stall that sells two things: samosas and sandwiches. You have only so much dough, only so much filling, and only so many hours before the school bell rings. Every combination of samosas and sandwiches you could make is a possible plan. Most plans are impossible (you do not have enough dough). Of the plans that are possible, one of them earns you the most money. Finding that plan is a linear programming problem.
Written mathematically, a Linear Programming Problem (LPP) asks you to make a linear expression as large as possible, or as small as possible, while a set of linear inequalities holds true. That is the whole definition. The word programming here is old-fashioned English for planning — it has nothing to do with computer coding.
The word linear is doing serious work, though. It means every variable appears only to the first power. No squares, no products of two variables, no square roots, nothing under a fraction bar. So 5x + 7y is linear; x² + y, xy and √x are not. This is what guarantees that every boundary you draw is a straight line, and straight lines are what make the whole graphical method possible.
subject to linear inequalities in x and y (at most three of them beyond the axes),
and x ≥ 0, y ≥ 0.
Only two variables. Only straight-line boundaries. That is the entire universe of this chapter.
(a) Maximise Z = 5x + 7y subject to 2x + 3y ≤ 12, x ≥ 0, y ≥ 0.
(b) Maximise Z = x² + y subject to x + y ≤ 4, x ≥ 0, y ≥ 0.
(c) Minimise Z = 3x + 2y subject to xy ≤ 6, x ≥ 0, y ≥ 0.
Solution. (a) is a proper LPP: the objective 5x + 7y is linear and the constraint 2x + 3y ≤ 12 is linear.
(b) is not an LPP. The term x² makes the objective function non-linear, so its level curves are parabolas, not straight lines.
(c) is not an LPP either. The constraint xy ≤ 6 contains a product of the two variables, so its boundary xy = 6 is a hyperbola, not a line.
The second thing to get straight from day one is the difference between a plan that works and a plan that does not. Any pair of values (x, y) that satisfies every single constraint is called a feasible solution. If it breaks even one constraint, it is an infeasible solution. There is no partial credit here — one violated inequality is enough to throw the point out.
For the constraints x + 2y ≤ 10, 3x + y ≤ 12, x ≥ 0, y ≥ 0, decide whether (2, 3) and (5, 1) are feasible solutions.
Solution. Test (2, 3) in each constraint one at a time.
x + 2y = 2 + 6 = 8, and 8 ≤ 10. ✓
3x + y = 6 + 3 = 9, and 9 ≤ 12. ✓
x = 2 ≥ 0 and y = 3 ≥ 0. ✓ All four hold, so (2, 3) is a feasible solution.
Now (5, 1): x + 2y = 5 + 2 = 7 ≤ 10 ✓, but 3x + y = 15 + 1 = 16, and 16 is not ≤ 12. ✗
One failure is enough, so (5, 1) is infeasible. It does not matter that it passed the other three tests.
The Vocabulary: Objective Function, Decision Variables, Constraints
Examiners love asking you to name the parts of an LPP, and marking schemes give marks for using the right word. So let us slow down and fix the vocabulary properly. Think of it as learning the names of the pieces before you play the game.
Decision variables are the quantities you are allowed to choose — usually written x and y. They are the things you actually control: how many chairs to make, how many kilograms of feed to buy. Everything else in the problem is fixed by the situation.
The objective function, always called Z, is the quantity you are trying to push to its best value. It is a linear expression Z = ax + by. If Z stands for profit you want it as large as possible; if Z stands for cost you want it as small as possible. Deciding which one is asked for is the first thing you should write down.
Constraints are the linear inequalities that say what is and is not allowed — the limited machine hours, the minimum vitamin requirement, the maximum budget. The two special constraints x ≥ 0 and y ≥ 0 have their own name: the non-negative restrictions. They are there because you cannot make −3 chairs.
Optimisation is just the umbrella word for the whole activity: finding the maximum or the minimum of Z. And the particular feasible point that achieves it is called the optimal feasible solution, with the value of Z there called the optimal value.
| Term | What it means | In the example below |
|---|---|---|
| Decision variables | The quantities you choose | x and y |
| Objective function | The linear expression Z you optimise | Z = 7x + 9y |
| Constraints | The linear inequalities that limit you | 2x + 3y ≤ 18, x + y ≤ 8 |
| Non-negative restrictions | Variables cannot be negative | x ≥ 0, y ≥ 0 |
| Feasible solution | A point satisfying every constraint | (3, 4) |
| Infeasible solution | A point breaking at least one constraint | (9, 1) |
| Feasible region | The set of all feasible solutions | The shaded polygon |
| Optimal feasible solution | The feasible point that gives the best Z | A corner point |
For: Maximise Z = 7x + 9y subject to 2x + 3y ≤ 18, x + y ≤ 8, x ≥ 0, y ≥ 0 — name the objective function, the decision variables, the constraints, and check whether (3, 4) and (9, 1) are feasible.
Solution. Decision variables: x and y. Objective function: Z = 7x + 9y, to be maximised.
Constraints: 2x + 3y ≤ 18 and x + y ≤ 8. Non-negative restrictions: x ≥ 0, y ≥ 0.
At (3, 4): 2(3) + 3(4) = 6 + 12 = 18 ≤ 18 ✓, and 3 + 4 = 7 ≤ 8 ✓, both coordinates non-negative ✓. So (3, 4) is a feasible solution, and there Z = 21 + 36 = 57.
At (9, 1): 2(9) + 3(1) = 21, which is not ≤ 18. ✗ So (9, 1) is infeasible — we do not even bother computing Z there.
A stationery shop stocks two kinds of notebook. It earns a profit of ₹12 on a ruled notebook and ₹18 on a graph notebook. Write the decision variables and the objective function.
Solution. Let x = number of ruled notebooks stocked and y = number of graph notebooks stocked. Notice the phrasing: number of. Always define the variable as a quantity with a unit, never vaguely as "ruled notebooks".
Total profit = 12x + 18y, so the objective function is Z = 12x + 18y, to be maximised.
And because you cannot stock a negative number of notebooks, we always add x ≥ 0, y ≥ 0.
Graphing a Linear Inequality: the Half-Plane Idea
Everything in this chapter rests on one small skill, so let us make it rock solid. A straight line cuts the plane into two pieces. Mathematicians call each piece a half-plane. An inequality like 3x + 2y ≤ 12 is satisfied by every point of exactly one of those two halves, plus the line itself. Your job is to work out which half.
The method has three steps, and it never changes:
- Replace the inequality sign by = and draw that straight line. The easiest way is to find where it cuts the axes: put x = 0 to get the y-intercept, put y = 0 to get the x-intercept (the same intercept trick from Coordinate Geometry, Class 10), then join them with a ruler.
- Pick a test point that is not on the line. Use the origin (0, 0) whenever the line does not pass through it — the arithmetic is trivial.
- Substitute the test point into the original inequality. If the statement comes out true, shade the side containing the test point. If it comes out false, shade the other side.
Why does one test point settle the whole half-plane? Because the expression ax + by can only change from "less than c" to "greater than c" by passing through the value c — that is, by crossing the line. So the sign of ax + by − c is the same at every point on one side. Test one point and you have tested them all. That is the entire logic, and it is worth understanding rather than memorising.
Step 1. Draw 3x + 2y = 12. Put x = 0: 2y = 12, so y = 6, giving (0, 6). Put y = 0: 3x = 12, so x = 4, giving (4, 0). Join (4, 0) and (0, 6) with a solid line (solid because the sign is ≤, so the line itself is included).
Step 2. The line does not pass through the origin, so test (0, 0).
Step 3. 3(0) + 2(0) = 0, and 0 ≤ 12 is true.
So shade the side of the line that contains the origin — the region between the line and the origin. Together with x ≥ 0 and y ≥ 0 this gives the triangle with vertices (0, 0), (4, 0) and (0, 6).
Step 1. Draw 2x − y = 2. Put y = 0: 2x = 2, so x = 1, giving (1, 0). Put x = 0: −y = 2, so y = −2, giving (0, −2). A second convenient point inside the first quadrant is x = 3, y = 4, since 6 − 4 = 2.
Step 2 and 3. Test the origin: 2(0) − 0 = 0, and 0 ≥ 2 is false.
So shade the side away from the origin — the region below and to the right of the line. Notice how a ≥ with a positive right-hand side very often pushes you away from the origin.
Rewrite as 2x − y ≤ 0. The line 2x − y = 0, that is y = 2x, passes through (0, 0) and (1, 2). Because the line passes through the origin, the origin is useless as a test point — it sits on the boundary.
Choose any other convenient point instead, say (1, 0): 2(1) − 0 = 2, and 2 ≤ 0 is false. So (1, 0) is not in the region.
Check the opposite side with (0, 1): 2(0) − 1 = −1, and −1 ≤ 0 is true. So shade the side containing (0, 1) — the region above the line y = 2x.
Drawing the Feasible Region
A single inequality gives you a half-plane. An LPP gives you several at once, and you have to satisfy all of them simultaneously. So shade each one, and then look for the patch of paper that ended up shaded by every constraint. That common patch is the feasible region: the complete collection of feasible solutions. Anything outside it is an infeasible solution.
Feasible regions come in two flavours, and telling them apart matters later. A region is bounded if you can draw a circle big enough to enclose it entirely — it is a closed polygon, fenced in on every side. It is unbounded if it stretches away forever in some direction, like an open field with a fence on only two or three sides. Constraints of the type ≤ with x, y ≥ 0 usually pen you in and give a bounded region; constraints of the type ≥ usually leave the region open at the top right.
The points where two boundary lines meet at the edge of the region are the corner points, also called vertices. You find them exactly the way you solved simultaneous equations in Class 10: take the two lines that cross there and solve them together. Never read a corner off the graph by eye — graphs are for seeing, algebra is for accuracy.
Constraints: 2x + y ≤ 10, x + 2y ≤ 14, x ≤ 4, x ≥ 0, y ≥ 0.
O is where x = 0 meets y = 0, so O = (0, 0).
A is where y = 0 meets x = 4, so A = (4, 0). Check: 2(4) + 0 = 8 ≤ 10 ✓ and 4 + 0 = 4 ≤ 14 ✓.
B is where x = 4 meets 2x + y = 10. Substituting, 8 + y = 10, so y = 2 and B = (4, 2). Check: 4 + 2(2) = 8 ≤ 14 ✓.
C is where 2x + y = 10 meets x + 2y = 14. Double the first: 4x + 2y = 20. Subtract the second: 3x = 6, so x = 2, and then y = 10 − 4 = 6. So C = (2, 6). Check: 2 ≤ 4 ✓.
D is where x = 0 meets x + 2y = 14, giving 2y = 14, y = 7, so D = (0, 7). Check: 2(0) + 7 = 7 ≤ 10 ✓.
The corner points are therefore O(0, 0), A(4, 0), B(4, 2), C(2, 6) and D(0, 7), and the region is bounded.
(a) x + y ≤ 5, x ≥ 0, y ≥ 0. (b) x + y ≥ 5, x ≥ 0, y ≥ 0.
(a) The origin test on x + y ≤ 5 gives 0 ≤ 5, true, so we shade towards the origin. Combined with the two axes we get the triangle with vertices (0, 0), (5, 0) and (0, 5). It is closed on all three sides, so the region is bounded.
(b) Now the origin test gives 0 ≥ 5, false, so we shade away from the origin. The region is the whole slab of the first quadrant lying above the line x + y = 5. Nothing stops it growing: the point (1000, 1000) is in it. The region is unbounded, with only two corner points, (5, 0) and (0, 5).
Together with x ≥ 0, y ≥ 0, find all corner points of the feasible region.
Solution. The line x + 2y = 8 cuts the axes at (8, 0) and (0, 4). The line 3x + 2y = 12 cuts them at (4, 0) and (0, 6). Both origin tests pass (0 ≤ 8 and 0 ≤ 12), so both regions face the origin.
On the x-axis the tighter limit is x ≤ 4, so the corner there is (4, 0), not (8, 0). On the y-axis the tighter limit is y ≤ 4, so the corner there is (0, 4), not (0, 6).
Where the two lines cross: subtract x + 2y = 8 from 3x + 2y = 12 to get 2x = 4, so x = 2, and then 2 + 2y = 8 gives y = 3. The crossing point is (2, 3), and it satisfies both x ≥ 0 and y ≥ 0.
Corner points: (0, 0), (4, 0), (2, 3), (0, 4) — a bounded quadrilateral.
Corner Point Method: The Rule That Solves Everything
Here is the beautiful fact that makes this whole chapter easy. The feasible region usually contains infinitely many points, so you might expect that checking them all is hopeless. It is not, because of this:
So you only ever need to test the corners — never the interior, never the middle of an edge.
Why does the best value hide in a corner? Picture the family of parallel lines ax + by = k, one for each value of k. As k increases, the whole family slides across the page in one fixed direction without ever turning. Sliding it as far as it will go while still touching the shaded region, the last contact must happen at an extreme point of that region — and the extreme points of a polygon are its corners. If the sliding line happens to lie flat along a whole edge at that moment, then every point of that edge is equally good, which is the "infinitely many solutions" case we meet later.
Maximise Z = 4x + 5y subject to 2x + y ≤ 10, x + 2y ≤ 14, x ≤ 4, x ≥ 0, y ≥ 0.
Solution. From Example 8 the corner points are O(0, 0), A(4, 0), B(4, 2), C(2, 6) and D(0, 7), and the region is bounded. Evaluate Z at each:
At O(0, 0): Z = 4(0) + 5(0) = 0.
At A(4, 0): Z = 4(4) + 5(0) = 16.
At B(4, 2): Z = 4(4) + 5(2) = 16 + 10 = 26.
At C(2, 6): Z = 4(2) + 5(6) = 8 + 30 = 38.
At D(0, 7): Z = 4(0) + 5(7) = 35.
The largest of 0, 16, 26, 38, 35 is 38. Since the region is bounded, the Corner Point Theorem applies directly: the maximum value of Z is 38, attained at (2, 6). (The minimum, if it were asked, would be 0 at the origin.)
Maximise Z = 3x + 4y subject to x + y ≤ 4, x ≥ 0, y ≥ 0.
Solution. The line x + y = 4 cuts the axes at (4, 0) and (0, 4), and the origin test 0 ≤ 4 is true, so the region is the triangle with corners (0, 0), (4, 0), (0, 4). It is bounded.
At (0, 0): Z = 0. At (4, 0): Z = 12. At (0, 4): Z = 16.
Maximum Z = 16 at (0, 4). Notice that y carries the bigger coefficient, so the optimum leans towards making y as large as possible — a useful sanity check, though never a substitute for the table.
Maximise Z = 5x + 3y subject to x + y ≤ 5, x + 3y ≤ 9, x ≥ 0, y ≥ 0.
Solution. x + y = 5 meets the axes at (5, 0) and (0, 5); x + 3y = 9 meets them at (9, 0) and (0, 3). Both origin tests pass, so both half-planes face the origin. On the y-axis the tighter cap is y ≤ 3, so the corner is (0, 3). On the x-axis the tighter cap is x ≤ 5, so the corner is (5, 0).
Crossing point: subtract x + y = 5 from x + 3y = 9 to get 2y = 4, so y = 2 and x = 3. That gives (3, 2).
Corners: (0, 0), (5, 0), (3, 2), (0, 3). Now the table: Z(0, 0) = 0; Z(5, 0) = 25; Z(3, 2) = 15 + 6 = 21; Z(0, 3) = 9.
Maximum Z = 25 at (5, 0). This is worth noticing: students often assume the answer must be at the point where the two slanted lines cross. It is not. Test every corner, every time.
Bounded Feasible Regions
A bounded feasible region is the comfortable case, and it is worth saying clearly why. Because the region is closed and fenced in on every side, the objective function is guaranteed to reach a highest value and a lowest value somewhere inside it — and by the Corner Point Theorem both of those happen at corners. So there is nothing to worry about and nothing extra to check. Build the table, read off the biggest number for the maximum and the smallest for the minimum, and write your conclusion.
How do you recognise a bounded region on sight? Look for a closed polygon: every direction you try to walk in, you eventually hit an edge. If the shaded area has an open mouth heading off the page, it is not bounded.
Find the maximum and minimum of Z = 3x + 4y subject to x + 2y ≤ 12, 2x + y ≤ 12, x + y ≥ 4, x ≥ 0, y ≥ 0.
Step 1 — the lines. x + 2y = 12 passes through (12, 0) and (0, 6). 2x + y = 12 passes through (6, 0) and (0, 12). x + y = 4 passes through (4, 0) and (0, 4).
Step 2 — the shading. Origin tests: 0 ≤ 12 true (shade towards O), 0 ≤ 12 true (shade towards O), 0 ≥ 4 false (shade away from O). So the region is squeezed between the line x + y = 4 below and the other two lines above. It is a closed pentagon, hence bounded.
Step 3 — the corners.
x + y = 4 with y = 0 gives (4, 0); check x + 2y = 4 ≤ 12 ✓ and 2x + y = 8 ≤ 12 ✓.
2x + y = 12 with y = 0 gives (6, 0); check x + 2y = 6 ≤ 12 ✓ and x + y = 6 ≥ 4 ✓.
x + 2y = 12 with 2x + y = 12: adding gives 3x + 3y = 24 so x + y = 8; subtracting gives x − y = 0 so x = y, hence x = y = 4, giving (4, 4).
x + 2y = 12 with x = 0 gives (0, 6); check 2x + y = 6 ≤ 12 ✓ and x + y = 6 ≥ 4 ✓.
x + y = 4 with x = 0 gives (0, 4); check x + 2y = 8 ≤ 12 ✓ and 2x + y = 4 ≤ 12 ✓.
Step 4 — the table. Z(4, 0) = 12; Z(6, 0) = 18; Z(4, 4) = 12 + 16 = 28; Z(0, 6) = 24; Z(0, 4) = 16.
The region is bounded, so we may read off both answers at once: maximum Z = 28 at (4, 4) and minimum Z = 12 at (4, 0). Note that the origin is not a corner here, because x + y ≥ 4 excludes it.
Maximise Z = 7x + 3y over the region of Example 10, namely x + 2y ≤ 8, 3x + 2y ≤ 12, x ≥ 0, y ≥ 0.
Solution. The corners were found there: (0, 0), (4, 0), (2, 3) and (0, 4), and the region is bounded.
Z(0, 0) = 0. Z(4, 0) = 28 + 0 = 28. Z(2, 3) = 14 + 9 = 23. Z(0, 4) = 0 + 12 = 12.
Maximum Z = 28 at (4, 0), and the minimum is 0 at the origin. Compare this with Example 10 in reverse: the region has not changed at all, only the objective function — and that alone moved the winning corner.
Unbounded Feasible Regions and the Extra Check
Now the case that trips people up. When the region runs off to infinity, the Corner Point Theorem no longer guarantees anything. Think about it physically: if you can walk forever in a direction that keeps increasing Z, there is no largest value at all. So for an unbounded region the corner table gives you a candidate, and you must run one extra test before you may call it the answer.
• M is the maximum of Z only if the open half-plane ax + by > M has no point in common with the feasible region.
• m is the minimum of Z only if the open half-plane ax + by < m has no point in common with the feasible region.
If the open half-plane does meet the region, then Z has no maximum (or no minimum) at all.
In practice the test is easy: draw the dashed line ax + by = M (or = m) on the same axes and look. If the dashed line only touches the region at the candidate corner and the rest of the region lies entirely on the safe side, you are done. If any bit of shading pokes across the dashed line, there is no optimum. A useful shortcut for the common school case where a, b, x and y are all non-negative: an unbounded region opening upwards and to the right will always have a minimum but almost never a maximum.
Minimise Z = 3x + 5y subject to x + y ≥ 6, 2x + y ≥ 8, x ≥ 0, y ≥ 0. (This is the figure above.)
Step 1. x + y = 6 joins (6, 0) and (0, 6). 2x + y = 8 joins (4, 0) and (0, 8). Both origin tests fail (0 ≥ 6 is false, 0 ≥ 8 is false), so both regions face away from the origin. The common region is open at the top right, so it is unbounded.
Step 2 — corners. On the y-axis the binding constraint is 2x + y ≥ 8, giving P(0, 8). Where x + y = 6 meets 2x + y = 8, subtracting gives x = 2, hence y = 4, giving Q(2, 4). On the x-axis the binding constraint is x + y ≥ 6, giving R(6, 0).
Step 3 — table. Z(0, 8) = 40; Z(2, 4) = 6 + 20 = 26; Z(6, 0) = 18. The smallest is m = 18 at R(6, 0).
Step 4 — the extra check. Draw 3x + 5y = 18, which passes through (6, 0) and (0, 3.6). Does the open half-plane 3x + 5y < 18 contain any feasible point? Every feasible point has x + y ≥ 6, so 3x + 5y ≥ 3(x + y) ≥ 18, with equality only when y = 0 and x + y = 6, that is only at (6, 0) itself. So no feasible point makes 3x + 5y less than 18.
Minimum Z = 18 at (6, 0).
Maximise Z = x + y subject to x + 2y ≥ 4, x ≥ 0, y ≥ 0.
Solution. x + 2y = 4 joins (4, 0) and (0, 2). The origin test 0 ≥ 4 is false, so we shade away from the origin. The region is unbounded with just two corners, (4, 0) and (0, 2).
Table: Z(4, 0) = 4 and Z(0, 2) = 2, so the largest corner value is M = 4.
Now the check: does x + y > 4 contain a feasible point? Try (5, 0). It satisfies x + 2y = 5 ≥ 4 ✓, x ≥ 0 ✓, y ≥ 0 ✓, so it is feasible — and there Z = 5, which is greater than 4. The open half-plane does meet the region.
Therefore Z has no maximum value. Indeed taking (t, 0) for larger and larger t keeps Z growing without limit. Writing "maximum = 4" here would lose you the marks; the correct answer is that no maximum exists.
Minimise Z = 5x + 7y subject to x + y ≥ 8, 3x + y ≥ 12, x ≥ 0, y ≥ 0.
Solution. x + y = 8 joins (8, 0) and (0, 8); 3x + y = 12 joins (4, 0) and (0, 12). Both origin tests fail, so the region is unbounded and lies up and to the right.
On the y-axis the binding constraint is 3x + y ≥ 12, so the corner is (0, 12). Where the lines meet: subtract x + y = 8 from 3x + y = 12 to get 2x = 4, so x = 2 and y = 6, giving (2, 6). On the x-axis the binding constraint is x + y ≥ 8, so the corner is (8, 0).
Table: Z(0, 12) = 84; Z(2, 6) = 10 + 42 = 52; Z(8, 0) = 40. Candidate m = 40 at (8, 0).
Check: for any feasible point, 5x + 7y ≥ 5x + 5y = 5(x + y) ≥ 5(8) = 40, and equality forces y = 0 with x + y = 8, i.e. the point (8, 0). So 5x + 7y < 40 has no feasible point.
Minimum Z = 40 at (8, 0).
When There Is No Solution, or Infinitely Many
Most LPPs have exactly one optimal point. But two other things can happen, and questions are set on both, so let us look at them calmly.
Case 1: infinitely many optimal solutions. Sometimes two adjacent corners give the same value of Z. That happens when the objective line ax + by = k is parallel to the edge joining them. When the sliding line finally leaves the region it does not leave through a single point but along that whole edge, so every point on the edge is optimal. Your answer should say so: the optimal value is such-and-such, attained at every point of the segment joining those two corners.
Case 2: no feasible solution at all. If the constraints contradict one another, the shaded areas never overlap and the feasible region is empty. There is then nothing to optimise, and the honest answer is "the LPP has no feasible solution". Do not invent a corner point to put in a table.
A quick way to spot how to tell the difference: parallel objective and edge gives you too many answers; contradictory constraints give you none. The first is detected in the table (a tie for the best value); the second is detected on the graph (no overlap anywhere).
Maximise Z = 4x + 6y subject to 2x + 3y ≤ 12, x + y ≤ 5, x ≥ 0, y ≥ 0.
Step 1. 2x + 3y = 12 joins (6, 0) and (0, 4). x + y = 5 joins (5, 0) and (0, 5). Both origin tests pass, so both half-planes face the origin and the region is a bounded quadrilateral.
Step 2 — corners. On the x-axis the tighter cap is x ≤ 5, giving (5, 0); check 2(5) = 10 ≤ 12 ✓. On the y-axis the tighter cap is y ≤ 4, giving (0, 4); check 0 + 4 = 4 ≤ 5 ✓. Where the lines meet: from x + y = 5 we get x = 5 − y, so 2(5 − y) + 3y = 12, that is 10 + y = 12, y = 2 and x = 3, giving (3, 2). And of course (0, 0).
Step 3 — table. Z(0, 0) = 0; Z(5, 0) = 20; Z(3, 2) = 12 + 12 = 24; Z(0, 4) = 0 + 24 = 24.
Two corners tie at 24. And no wonder: Z = 4x + 6y is exactly twice 2x + 3y, so the objective line is parallel to the edge 2x + 3y = 12, which is precisely the edge joining (3, 2) and (0, 4).
Maximum Z = 24, attained at every point of the line segment joining (0, 4) and (3, 2). Check a middle point to be sure: at (1.5, 3), Z = 6 + 18 = 24. ✓
Maximise Z = 9x + 4y subject to 2x + y ≤ 6, x + y ≥ 8, x ≥ 0, y ≥ 0.
Solution. The first constraint (origin test 0 ≤ 6 true) shades the small triangle near the origin with vertices (0, 0), (3, 0), (0, 6). The second (origin test 0 ≥ 8 false) shades everything beyond the line x + y = 8, far away from the origin.
Argue it algebraically to be certain. In the first quadrant, 2x + y ≤ 6 forces x + y ≤ 2x + y ≤ 6, so x + y can never exceed 6. But the second constraint demands x + y ≥ 8. Since 6 < 8, the two demands cannot both hold.
The two shaded areas have no point in common, so the feasible region is empty. The LPP has no feasible solution, and therefore no maximum value of Z.
Turning a Word Problem Into an LPP
Here is the reassuring news: the mathematics does not change at all. Once the word problem has been turned into "maximise Z = ax + by subject to …", you are back on familiar ground — graph, corners, table, answer. The only new skill is the translation, and there is a reliable routine for that.
- Name the two variables. Read the question and ask, "what am I actually deciding?" Write "Let x = number of … and y = number of …", with units.
- Write Z. Find the sentence about money, profit, cost or nutrition value. Multiply each per-unit figure by its variable and add.
- Turn each resource into one inequality. A resource that is available or at most gives ≤. A requirement that is at least or a minimum gives ≥.
- Add x ≥ 0, y ≥ 0, always.
- Solve graphically and finish with a sentence in the language of the problem, not just numbers.
A tidy habit that saves marks: before you graph anything, lay the data out in a small table with one row per resource and one column per product. Every row of that table becomes exactly one constraint. It makes double-counting almost impossible.
A small workshop makes wooden trains and wooden buses. Each train needs 2 hours of cutting and 1 hour of painting. Each bus needs 1 hour of cutting and 2 hours of painting. In a month there are 100 cutting hours and 80 painting hours available. The profit is ₹60 on a train and ₹50 on a bus. How many of each should be made for maximum profit?
Step 1. Let x = number of trains made and y = number of buses made in the month.
Step 2. Profit Z = 60x + 50y, to be maximised.
Step 3. Cutting hours used = 2x + y, and only 100 are available, so 2x + y ≤ 100. Painting hours used = x + 2y, and only 80 are available, so x + 2y ≤ 80. Also x ≥ 0, y ≥ 0.
Step 4 — the graph. 2x + y = 100 joins (50, 0) and (0, 100); x + 2y = 80 joins (80, 0) and (0, 40). Both origin tests pass, so the region hugs the origin and is bounded.
Step 5 — the corners. On the x-axis the tighter cap is x ≤ 50, giving (50, 0). On the y-axis the tighter cap is y ≤ 40, giving (0, 40). Where the lines cross: double the first to get 4x + 2y = 200 and subtract x + 2y = 80 to get 3x = 120, so x = 40 and y = 100 − 80 = 20, giving (40, 20). Plus the origin (0, 0).
Step 6 — the table. Z(0, 0) = 0; Z(50, 0) = 3000; Z(40, 20) = 2400 + 1000 = 3400; Z(0, 40) = 2000.
The region is bounded, so the maximum is the largest entry: ₹3400, at x = 40, y = 20. In words: the workshop should make 40 trains and 20 buses for a maximum monthly profit of ₹3400. Sanity check on the resources: cutting = 2(40) + 20 = 100 hours (all used) and painting = 40 + 2(20) = 80 hours (all used). Nothing is wasted, which is typical of an optimal corner.
A shopkeeper blends two powders, P and Q. One kilogram of P supplies 3 units of protein and 1 unit of iron; one kilogram of Q supplies 1 unit of protein and 2 units of iron. The blend must supply at least 12 units of protein and at least 9 units of iron. P costs ₹40 per kg and Q costs ₹30 per kg. Find the cheapest blend.
Step 1. Let x = kilograms of P and y = kilograms of Q in the blend.
Step 2. Cost Z = 40x + 30y, to be minimised.
Step 3. Protein supplied = 3x + y ≥ 12. Iron supplied = x + 2y ≥ 9. And x ≥ 0, y ≥ 0. Notice the ≥ signs: these are requirements, not limits.
Step 4 — the graph. 3x + y = 12 joins (4, 0) and (0, 12); x + 2y = 9 joins (9, 0) and (0, 4.5). Both origin tests fail, so both regions face away from the origin and the feasible region is unbounded.
Step 5 — the corners. On the y-axis the binding requirement is protein, giving (0, 12). Where the lines meet: from 3x + y = 12 we get y = 12 − 3x, so x + 2(12 − 3x) = 9, that is 24 − 5x = 9, x = 3 and y = 3, giving (3, 3). On the x-axis the binding requirement is iron, giving (9, 0).
Step 6 — the table. Z(0, 12) = 360; Z(3, 3) = 120 + 90 = 210; Z(9, 0) = 360. Candidate minimum m = 210 at (3, 3).
Step 7 — the extra check (the region is unbounded, so this is compulsory). Adding the two constraints gives (3x + y) + (x + 2y) ≥ 12 + 9, that is 4x + 3y ≥ 21. Multiplying by 10, 40x + 30y ≥ 210 for every feasible point. So the open half-plane 40x + 30y < 210 contains no feasible point.
Cheapest blend: 3 kg of P and 3 kg of Q, costing ₹210. Check the requirements: protein = 9 + 3 = 12 ✓ and iron = 3 + 6 = 9 ✓, both exactly met.
Board-Style Full Solutions
Board questions on this chapter are usually worth five or six marks and are marked step by step. Below are two complete answers written the way you should write yours: constraints listed, lines and intercepts stated, region identified as bounded or unbounded, a corner table, and a concluding sentence. Copy the layout, not just the answer.
Solve the following LPP graphically: Maximise Z = 12x + 10y subject to x + y ≤ 30, 2x + y ≤ 50, x ≥ 0, y ≥ 0.
The lines. x + y = 30 meets the axes at (30, 0) and (0, 30). 2x + y = 50 meets them at (25, 0) and (0, 50).
The shading. At the origin, 0 ≤ 30 is true and 0 ≤ 50 is true, so both half-planes contain the origin. With x ≥ 0 and y ≥ 0 the feasible region is a closed quadrilateral, hence bounded.
The corners. Origin (0, 0). On the x-axis the tighter cap is x ≤ 25 from 2x + y ≤ 50, so (25, 0); check 25 ≤ 30 ✓. On the y-axis the tighter cap is y ≤ 30 from x + y ≤ 30, so (0, 30); check 30 ≤ 50 ✓. Where the lines cross: subtract x + y = 30 from 2x + y = 50 to get x = 20, then y = 10, giving (20, 10).
The table. Z(0, 0) = 0; Z(25, 0) = 300; Z(20, 10) = 240 + 100 = 340; Z(0, 30) = 300.
Conclusion. The feasible region is bounded, so by the Corner Point Theorem Z attains its maximum at a corner. Maximum Z = 340 at the point (20, 10). Interesting detail: the two non-optimal corners both give 300, but neither is the answer — another reminder to compute all of them.
Minimise Z = 6x + 10y subject to 2x + y ≥ 12, x + y ≥ 8, x + 3y ≥ 12, x ≥ 0, y ≥ 0.
The lines. 2x + y = 12 meets the axes at (6, 0) and (0, 12). x + y = 8 meets them at (8, 0) and (0, 8). x + 3y = 12 meets them at (12, 0) and (0, 4).
The shading. At the origin all three statements are false (0 ≥ 12, 0 ≥ 8, 0 ≥ 12), so all three half-planes point away from the origin. The feasible region is open towards the top right, hence unbounded.
The corners. On the y-axis we need y ≥ 12, y ≥ 8 and y ≥ 4 all at once, so the strictest is y ≥ 12, giving (0, 12). Where 2x + y = 12 meets x + y = 8: subtracting gives x = 4, so y = 4, giving (4, 4); check x + 3y = 4 + 12 = 16 ≥ 12 ✓. Where x + y = 8 meets x + 3y = 12: subtracting gives 2y = 4, so y = 2 and x = 6, giving (6, 2); check 2x + y = 14 ≥ 12 ✓. On the x-axis we need x ≥ 6, x ≥ 8 and x ≥ 12, so the strictest is x ≥ 12, giving (12, 0).
(The crossing of 2x + y = 12 and x + 3y = 12 is at x = 24/5, y = 12/5, where x + y = 36/5 = 7.2, which is less than 8. It fails the second constraint, so it is not a corner of the feasible region and is discarded.)
The table. Z(0, 12) = 120; Z(4, 4) = 24 + 40 = 64; Z(6, 2) = 36 + 20 = 56; Z(12, 0) = 72. The smallest value is m = 56 at (6, 2).
The compulsory check. For any feasible point, 4(x + y) + 2(x + 3y) = 6x + 10y, and since x + y ≥ 8 and x + 3y ≥ 12 we get 6x + 10y ≥ 4(8) + 2(12) = 32 + 24 = 56. So the open half-plane 6x + 10y < 56 has no point in common with the feasible region.
Conclusion. Minimum Z = 56 at the point (6, 2).
Practice Worksheet
Ten questions, arranged roughly easy to board level. Draw a graph for every single one, even the short ones — that habit alone is worth several marks in the exam. Try each fully before opening the answer.
Q1. Shade the region 2x + 5y ≤ 20, x ≥ 0, y ≥ 0. State the intercepts of the boundary line and the corner points of the region, and say whether it is bounded.
Show Answer
Q2. Find all corner points of the feasible region given by x + y ≤ 6, 2x + y ≤ 8, x ≥ 0, y ≥ 0.
Show Answer
On the x-axis the tighter cap is x ≤ 4, so the corner is (4, 0), not (6, 0). On the y-axis the tighter cap is y ≤ 6, so the corner is (0, 6), not (0, 8).
Crossing point: subtract x + y = 6 from 2x + y = 8 to get x = 2, then y = 4.
Corner points: (0, 0), (4, 0), (2, 4), (0, 6). The region is bounded.
Q3. Maximise Z = 6x + 4y subject to x + y ≤ 9, 2x + y ≤ 14, x ≥ 0, y ≥ 0.
Show Answer
Corners: (0, 0); on the x-axis the tighter cap gives (7, 0); on the y-axis the tighter cap gives (0, 9); and subtracting x + y = 9 from 2x + y = 14 gives x = 5, hence y = 4, giving (5, 4).
Table: Z(0, 0) = 0; Z(7, 0) = 42; Z(5, 4) = 30 + 16 = 46; Z(0, 9) = 36.
Maximum Z = 46 at (5, 4).
Q4. Minimise Z = 4x + 6y subject to 2x + y ≥ 10, x + 2y ≥ 8, x ≥ 0, y ≥ 0. Show the check that your answer really is the minimum.
Show Answer
Corners: on the y-axis the binding constraint is 2x + y ≥ 10, giving (0, 10). Doubling the first constraint line, 4x + 2y = 20, and subtracting x + 2y = 8 gives 3x = 12, so x = 4 and y = 2, giving (4, 2). On the x-axis the binding constraint is x + 2y ≥ 8, giving (8, 0).
Table: Z(0, 10) = 60; Z(4, 2) = 16 + 12 = 28; Z(8, 0) = 32. Candidate m = 28.
Check: 2(2x + y) + 8(x + 2y) = 12x + 18y = 3(4x + 6y). Since 2x + y ≥ 10 and x + 2y ≥ 8, we get 3(4x + 6y) ≥ 2(10) + 8(8) = 84, so 4x + 6y ≥ 28 for every feasible point. The open half-plane 4x + 6y < 28 therefore meets nothing.
Minimum Z = 28 at (4, 2).
Q5. Maximise Z = 3x + 2y subject to x + y ≥ 4, x ≥ 0, y ≥ 0.
Show Answer
Table: Z(4, 0) = 12; Z(0, 4) = 8, so the largest corner value is M = 12.
Check: does 3x + 2y > 12 contain a feasible point? Take (10, 0): it satisfies x + y = 10 ≥ 4, and there Z = 30 > 12. The open half-plane does meet the region.
Z has no maximum value. (Its minimum, by contrast, is 8 at (0, 4), since 3x + 2y ≥ 2(x + y) ≥ 8 for all feasible points.)
Q6. Maximise Z = 6x + 4y subject to 3x + 2y ≤ 18, x + y ≤ 7, x ≥ 0, y ≥ 0. Describe the solution set fully.
Show Answer
Corners: (0, 0); on the x-axis the tighter cap is x ≤ 6, giving (6, 0); on the y-axis the tighter cap is y ≤ 7, giving (0, 7); and from x + y = 7 we get x = 7 − y, so 3(7 − y) + 2y = 18 gives 21 − y = 18, y = 3 and x = 4, giving (4, 3).
Table: Z(0, 0) = 0; Z(6, 0) = 36; Z(4, 3) = 24 + 12 = 36; Z(0, 7) = 28.
Two corners tie at 36, because Z = 6x + 4y is exactly twice 3x + 2y, so the objective line is parallel to that edge.
Maximum Z = 36, attained at every point of the segment joining (6, 0) and (4, 3) — for instance at (5, 1.5), Z = 30 + 6 = 36.
Q7. A tailor makes shirts and trousers. A shirt needs 1 metre of cloth and 2 hours of work; a pair of trousers needs 3 metres of cloth and 1 hour of work. He has 30 metres of cloth and 20 hours of working time. He earns ₹50 on a shirt and ₹80 on a pair of trousers. How many of each should he make to earn the most, and what is that amount?
Show Answer
x + 3y = 30 joins (30, 0) and (0, 10); 2x + y = 20 joins (10, 0) and (0, 20). Both origin tests pass, so the region is bounded.
Corners: (0, 0); on the x-axis the tighter cap is x ≤ 10, giving (10, 0); on the y-axis the tighter cap is y ≤ 10, giving (0, 10). Crossing point: from x + 3y = 30 we get x = 30 − 3y, so 2(30 − 3y) + y = 20, that is 60 − 5y = 20, y = 8 and x = 6, giving (6, 8).
Table: Z(0, 0) = 0; Z(10, 0) = 500; Z(6, 8) = 300 + 640 = 940; Z(0, 10) = 800.
He should make 6 shirts and 8 pairs of trousers, for a maximum earning of ₹940. Check: cloth used = 6 + 24 = 30 m and time used = 12 + 8 = 20 h, both fully used.
Q8. For the constraints 2x + 3y ≤ 20, x + y ≤ 6, x ≥ 0, y ≥ 0, decide whether (3, 4) and (2, 3) are feasible solutions. Justify each answer.
Show Answer
At (2, 3): 2x + 3y = 4 + 9 = 13 ≤ 20 ✓; x + y = 5 ≤ 6 ✓; x = 2 ≥ 0 ✓; y = 3 ≥ 0 ✓. All four hold, so (2, 3) is a feasible solution.
Q9. Find both the maximum and the minimum of Z = 2x + 5y subject to x + y ≤ 8, x + y ≥ 3, x ≤ 5, x ≥ 0, y ≥ 0.
Show Answer
Corners: x + y = 3 with y = 0 gives (3, 0); x = 5 with y = 0 gives (5, 0); x = 5 with x + y = 8 gives (5, 3); x + y = 8 with x = 0 gives (0, 8); x + y = 3 with x = 0 gives (0, 3).
Table: Z(3, 0) = 6; Z(5, 0) = 10; Z(5, 3) = 10 + 15 = 25; Z(0, 8) = 40; Z(0, 3) = 15.
Maximum Z = 40 at (0, 8); minimum Z = 6 at (3, 0). Both are read straight off because the region is bounded.
Q10. Maximise Z = x + 3y subject to x + y ≤ 4, 2x + 3y ≥ 18, x ≥ 0, y ≥ 0.
Show Answer
Algebraic proof that they cannot overlap: in the first quadrant, 2x + 3y ≤ 3x + 3y = 3(x + y) ≤ 3(4) = 12. So no feasible point can make 2x + 3y reach 18, since 12 < 18.
The two shaded areas have no point in common, so the feasible region is empty. The LPP has no feasible solution, and hence Z has no maximum.
Kaizen: aim for one more correct question than yesterday. That’s it. One more.