What this chapter is about
Linear programming is a mathematical method for finding the best possible outcome—maximum profit, minimum cost, or optimal resource use—when you face several restrictions at once. The word "linear" means all relationships involved are straight-line equations or inequalities; "programming" here means planning, not computer code.
A Class 12 student meets this topic because many real decisions (how many items a factory should produce, how to mix ingredients, how to transport goods cheaply) can be modelled with linear constraints and a linear objective. You already know how to graph straight lines and shade regions for inequalities from earlier classes; this chapter combines those skills to solve optimisation problems systematically.
After studying this chapter you should be able to formulate a real-world situation as a linear programming problem, identify the feasible region graphically, locate its corner points, and use those corners to find the maximum or minimum value of the objective function.
Key ideas
- Objective function: A linear expression Z = ax + by (or with more variables) that you want to maximise or minimise.
- Decision variables: The unknowns (usually x and y) whose values you must choose; they typically represent quantities like number of items or amounts of resources.
- Constraints: Linear inequalities (and sometimes equations) that the decision variables must satisfy, arising from limits such as budget, time, raw material, or capacity.
- Non-negativity restrictions: Almost always x ≥ 0 and y ≥ 0, because negative quantities of goods or time make no practical sense.
- Feasible region: The set of all points (x, y) that satisfy every constraint simultaneously; on a graph it appears as a polygon (or unbounded region).
- Corner-point (vertex) method: The optimal value of a linear objective over a bounded convex polygon always occurs at one of the vertices; check Z at each corner to find the best.
- Bounded vs unbounded feasible region: When the region extends to infinity in some direction, a maximum or minimum may not exist; you must examine whether Z can grow (or shrink) without limit.
Formulas and facts to remember
- Item: General form of objective function · Statement: Z = c₁x₁ + c₂x₂ + … + cₙxₙ (linear in decision variables)
- Item: Standard constraints · Statement: a₁x + b₁y ≤ k₁, a₂x + b₂y ≥ k₂, etc., where a, b, k are constants
- Item: Fundamental theorem (corner-point) · Statement: If the feasible region is non-empty and bounded, Z attains its optimal value at a vertex of the region
- Item: Unbounded region rule · Statement: If feasible region is unbounded, check whether Z can increase (or decrease) without limit; if not, the optimum still occurs at a corner
- Item: Graphical solution steps · Statement: (1) Plot each constraint as a line, shade the correct half-plane, (2) identify the common region, (3) list vertices, (4) evaluate Z at each vertex, (5) pick the best
Worked examples
Example 1 – Maximising profit in a small workshop
A carpenter makes chairs and tables. Each chair needs 2 hours of cutting and 3 hours of finishing; each table needs 3 hours of cutting and 2 hours of finishing. Available cutting time is 18 hours; finishing time is 15 hours. Profit is ₹200 per chair and ₹250 per table. How many of each should he make to maximise profit?
Formulation
Let x = number of chairs, y = number of tables.
Objective: Maximise Z = 200x + 250y.
Constraints:
- Cutting: 2x + 3y ≤ 18
- Finishing: 3x + 2y ≤ 15
- Non-negativity: x ≥ 0, y ≥ 0
Graphical solution
Draw lines 2x + 3y = 18 and 3x + 2y = 15 in the first quadrant. Shade the region satisfying both inequalities.
Vertices of the feasible region:
- A(0, 0)
- B(5, 0) — from 3x + 2y = 15 with y = 0
- C at intersection: solve 2x + 3y = 18 and 3x + 2y = 15 simultaneously. Multiply first by 2: 4x + 6y = 36. Multiply second by 3: 9x + 6y = 45. Subtract: 5x = 9, so x = 9/5 = 1.8; substitute: y = (18 − 3.6)/3 = 4.8. So C(1.8, 4.8).
- D(0, 6) — from 2x + 3y = 18 with x = 0
Evaluate Z:
- A: 0
- B: 200 × 5 + 0 = 1000
- C: 200 × 1.8 + 250 × 4.8 = 360 + 1200 = 1560
- D: 250 × 6 = 1500
Maximum Z = ₹1560 at C. However, x = 1.8 and y = 4.8 are not whole items. If integer solutions are required, test nearby lattice points (1, 5), (2, 4), etc., within the region—(2, 4) gives Z = 400 + 1000 = 1400; (1, 5) gives 200 + 1250 = 1450. Among integers, (1, 5) is best with profit ₹1450.
Example 2 – Minimising cost of a diet
A dietician wants to prepare a meal using two foods, P and Q. Each unit of P costs ₹4 and supplies 3 g protein and 2 g fibre. Each unit of Q costs ₹3 and supplies 2 g protein and 4 g fibre. The meal must have at least 12 g protein and at least 16 g fibre. Find the cheapest combination.
Formulation
Let x = units of P, y = units of Q.
Objective: Minimise Z = 4x + 3y.
Constraints:
- Protein: 3x + 2y ≥ 12
- Fibre: 2x + 4y ≥ 16
- x ≥ 0, y ≥ 0
Solution
Convert inequalities to equations for graphing. The feasible region lies above both lines in the first quadrant (unbounded towards larger x, y).
Vertices:
- Intersection of 3x + 2y = 12 with x-axis: (4, 0)
- Intersection of 2x + 4y = 16 with y-axis: (0, 4)
- Intersection of the two lines: solve 3x + 2y = 12 and 2x + 4y = 16. Double first: 6x + 4y = 24; subtract second: 4x = 8, x = 2, y = 3. So vertex (2, 3).
Evaluate Z:
- (4, 0): 16
- (0, 4): 12
- (2, 3): 8 + 9 = 17
The region is unbounded, but Z increases as we move further out, so the minimum does exist and equals ₹12 at (0, 4). The dietician should use 4 units of food Q and none of P.
Example 3 – Recognising an unbounded optimum
Maximise Z = 3x + 2y subject to x − y ≤ 1, x + y ≥ 2, x ≥ 0, y ≥ 0.
Vertices of the feasible region are (1, 0), (2, 0) lies outside x − y ≤ 1, so recalculate carefully:
- x − y = 1 meets x + y = 2 at (1.5, 0.5).
- x + y = 2 meets x = 0 at (0, 2).
- The region extends infinitely upward and to the right.
Since the region is unbounded in a direction where both x and y can grow, Z = 3x + 2y can become arbitrarily large. Therefore no finite maximum exists.
Common mistakes
- Shading the wrong side of a constraint line → substitute a test point (often the origin) to check which half-plane satisfies the inequality.
- Forgetting non-negativity restrictions → always include x ≥ 0, y ≥ 0 when quantities cannot be negative.
- Evaluating Z at points that lie outside the feasible region → verify every candidate vertex satisfies all constraints before using it.
- Assuming an optimum always exists → in an unbounded region, first check whether Z can grow (or shrink) indefinitely.
- Giving fractional answers when whole-number solutions are needed → re-examine integer lattice points near the optimal corner.
Quick revision
- Objective function = what you optimise; constraints = limits you must respect.
- Feasible region = intersection of all half-planes defined by constraints.
- Optimal value of a linear objective on a bounded polygon occurs at a vertex.
- Always test Z at every corner; compare to find max or min.
- If the region is unbounded, verify whether a finite optimum exists before concluding.