What is linear programming?
You want the best result (most profit, least cost) but you have limits (time, money, material). Linear programming is a method to find that best result.
Decision variables
These are the things you choose, like x = number of cakes and y = number of breads. They cannot be negative, so we always write x ≥ 0, y ≥ 0 (the non-negative constraints).
Constraints
A constraint is a rule written as a linear inequality, for example 2x + y ≤ 10 (oven hours). "Linear" means x and y appear only to the power 1, no xy or x².
Objective function
The quantity to make best is Z = ax + by, for example Z = 50x + 30y (profit in ₹). It is called the objective function.
Optimisation
Making Z as large as possible (maximise) or as small as possible (minimise) is called optimisation. A problem written this way is a linear programming problem (LPP).
How to write an LPP from a word problem
- Name the variables: "Let x = …, y = …".
- Make a small table: each item, what it uses of each resource, and the profit or cost.
- Write one constraint per resource: (use per item × number) ≤ (what is available). Use ≥ for "at least".
- Add x ≥ 0, y ≥ 0.
- Write Z and say "maximise" or "minimise".
Common types in exams: manufacturing (profit), diet (cost), transport (cost) and allocation problems.
Graphical method in two variables
With two variables every point (x, y) on the graph paper is one possible plan.
Step 1: draw each line
Change ≤ or ≥ to = . Find two easy points: put x = 0 to get y, put y = 0 to get x. Join them.
Step 2: shade the correct side
Test a point not on the line, usually (0, 0). If it makes the inequality true, shade its side; if false, shade the other side.
Step 3: find the common region
The part shaded by every constraint (in the first quadrant) is the feasible region.
Step 4: corner point method
Find every corner (vertex). A corner where two lines cross comes from solving the two equations together. Put each corner in Z. Largest value = maximum, smallest value = minimum.
Why corners?
The lines Z = k are all parallel. Sliding such a line outward, the last point of a polygon it leaves is a corner (or a whole edge). That is the corner point theorem. The iso-profit (or iso-cost) line method in step 4 of the 3D shows exactly this.
Feasible and infeasible regions, bounded or unbounded
Feasible region and feasible solution
The common region of all constraints, including x ≥ 0, y ≥ 0, is the feasible region. Every point in it (on the edges too) is a feasible solution. Points outside are infeasible solutions.
Bounded region
If the region can be closed inside a circle, it is bounded. Then Z always has both a maximum and a minimum, and both are at corners.
Unbounded region
If the region goes on forever in some direction, it is unbounded. A max or min may not exist. Rule: find the best corner value M. For a maximum, draw the open half-plane ax + by > M. If it has no point in common with the region, M is the maximum; otherwise there is no maximum. For a minimum use ax + by < m the same way.
Infeasible problem
If no point obeys all constraints (for example x + y ≤ 2 and x + y ≥ 5), the feasible region is empty and the LPP has no solution.
Optimal solutions (up to three constraints)
A point of the feasible region that gives the best Z is the optimal (best) solution, and that Z is the optimal value.
- Unique optimum: only one corner wins.
- Multiple optima: two neighbouring corners give the same best value. Then every point on the edge joining them is optimal too, because Z is parallel to that edge.
- No optimum: unbounded in the wrong direction, or infeasible.
With up to three constraints (plus x, y ≥ 0) the region has at most five corners, so a neat table of corners and Z values is the whole answer. In the board exam the LPP question usually carries 5 marks: about 1 mark for formulation, 2 for the graph and region, 2 for corners, Z and the conclusion.
Try it: a paper and ruler experiment
On squared paper draw x + y = 4 and x + 2y = 6. Shade the region. Now lay a ruler along 3x + 4y = 0 (through (0,0) and (4, −3)). Slide it parallel to itself away from the origin. Mark the last point of the green region it touches. Did you get (2, 2)? Now check it in the free play step of the 3D.
Key formulas and definitions
- LPP: maximise or minimise Z = ax + by, subject to linear constraints and x ≥ 0, y ≥ 0
- Feasible region = common region of all constraints
- Corner point theorem: the optimum (if it exists) is at a corner of the feasible region
- Bounded region → max and min both exist
- Unbounded: M is max only if ax + by > M has no point in common with the region (min: ax + by < m)
- Two corners with equal best Z → every point on the edge joining them is optimal
Worked examples
1. Maximise Z = 3x + 4y subject to x + y ≤ 4, x + 2y ≤ 6, x ≥ 0, y ≥ 0.
Step 1: Line x + y = 4 passes through (4, 0) and (0, 4). Line x + 2y = 6 passes through (6, 0) and (0, 3). Step 2: (0, 0) satisfies both, so shade towards the origin. Step 3: Corners: (0, 0), (4, 0), (0, 3) and the crossing point. Subtract the equations: y = 2, so x = 2, giving (2, 2). Step 4: Z(0,0) = 0, Z(4,0) = 12, Z(2,2) = 6 + 8 = 14, Z(0,3) = 12. Step 5: The region is bounded, so maximum Z = 14 at x = 2, y = 2.
2. Maximise Z = 4x + y subject to x + y ≤ 5, 2x + y ≤ 8, x, y ≥ 0.
Step 1: x + y = 5 meets the axes at (5, 0), (0, 5); 2x + y = 8 at (4, 0), (0, 8). Step 2: Both are ≤, so shade towards the origin. Step 3: Crossing point: subtract first from second: x = 3, y = 2. Corners: (0, 0), (4, 0), (3, 2), (0, 5). Step 4: Z = 0, 16, 14, 5. Step 5: Maximum Z = 16 at (4, 0).
3. A bakery makes cakes and breads. A cake needs 2 hours of oven time and 1 kg flour; a bread needs 1 hour and 1 kg flour. It has 10 oven hours and 7 kg flour a day. Profit is ₹50 per cake and ₹30 per bread. How many of each give the most profit?
Step 1: Let x = cakes, y = breads. Step 2: Oven: 2x + y ≤ 10. Flour: x + y ≤ 7. Also x, y ≥ 0. Maximise Z = 50x + 30y. Step 3: Lines: 2x + y = 10 through (5, 0), (0, 10); x + y = 7 through (7, 0), (0, 7). Crossing: subtract: x = 3, y = 4. Step 4: Corners (0, 0), (5, 0), (3, 4), (0, 7). Z = 0, 250, 150 + 120 = 270, 210. Step 5: Make 3 cakes and 4 breads for the highest profit ₹270.
4. Minimise Z = 2x + 3y subject to x + y ≥ 3, x + 2y ≥ 4, x, y ≥ 0.
Step 1: x + y = 3 through (3, 0), (0, 3); x + 2y = 4 through (4, 0), (0, 2). Step 2: (0, 0) gives 0 ≥ 3, false, so shade away from the origin. The region is open upward: unbounded. Step 3: Corners: (0, 3), (4, 0) and the crossing: subtract: y = 1, x = 2 → (2, 1). Step 4: Z = 9, 8, 7. Smallest corner value m = 7. Step 5: Check the open half-plane 2x + 3y < 7. It lies below the region and has no common point with it. So minimum Z = 7 at (2, 1).
5. Diet problem: Food A costs ₹4 a unit and gives 2 units of vitamin and 1 unit of mineral. Food B costs ₹5 a unit and gives 1 unit of vitamin and 2 units of mineral. A person needs at least 8 units of vitamin and 10 units of mineral. Find the cheapest mix.
Step 1: x = units of A, y = units of B. Minimise C = 4x + 5y. Step 2: Vitamin: 2x + y ≥ 8. Mineral: x + 2y ≥ 10. x, y ≥ 0. Step 3: Lines: 2x + y = 8 through (4, 0), (0, 8); x + 2y = 10 through (10, 0), (0, 5). Crossing: from the first, y = 8 − 2x; x + 16 − 4x = 10 → x = 2, y = 4. Step 4: Corners (0, 8), (2, 4), (10, 0). C = 40, 28, 40. Step 5: Region is unbounded, so check 4x + 5y < 28: no common point with the region. Cheapest: 2 units of A and 4 units of B for ₹28.
6. Maximise Z = x + 2y subject to x + y ≤ 6, x ≤ 4, y ≤ 5, x, y ≥ 0 (three constraints).
Step 1: Lines: x + y = 6, x = 4 (vertical), y = 5 (horizontal). Step 2: All ≤, shade towards the origin. Step 3: Corners: (0, 0), (4, 0), where x = 4 meets x + y = 6 → (4, 2), where y = 5 meets x + y = 6 → (1, 5), and (0, 5). Step 4: Z = 0, 4, 8, 11, 10. Step 5: Maximum Z = 11 at (1, 5).
7. Maximise Z = 2x + 2y subject to x + y ≤ 4, x + 2y ≤ 6, x, y ≥ 0.
Step 1: Same region as Example 1, corners (0, 0), (4, 0), (2, 2), (0, 3). Step 2: Z = 0, 8, 8, 6. Step 3: Two neighbouring corners (4, 0) and (2, 2) both give 8. Step 4: So every point on the segment joining (4, 0) and (2, 2) gives Z = 8. There are infinitely many optimal solutions; maximum Z = 8.
8. Show that Z = x + y has no maximum under x + y ≥ 3, x + 2y ≥ 4, x, y ≥ 0. Also, what happens if the rules are x + y ≤ 2 and x + y ≥ 5?
Part 1: Corners are (0, 3), (2, 1), (4, 0) with Z = 3, 3, 4. The largest corner value is 4. Check the half-plane x + y > 4: the point (10, 10) is in it and also in the feasible region. So Z can grow without limit: no maximum. Part 2: A number cannot be at most 2 and at least 5 at the same time. The shaded parts never overlap, the feasible region is empty, so the LPP is infeasible and has no solution.
Common mistakes
- Forgetting x ≥ 0 and y ≥ 0. Then the region wrongly spreads into negative values.
- Shading the wrong side. Always test (0, 0) (or another point if the line passes through the origin).
- Declaring a maximum for an unbounded region without checking the open half-plane ax + by > M.
- Missing a corner, especially the crossing point of two lines. Solve the two equations together to find it exactly; do not read it roughly from the graph.