Chapter 12 – Linear Programming

🧭

Introduction to Linear Programming

What it is, why it matters, and core terminology

Linear Programming Problem (LPP)○

Objective Function○

Constraints○

Feasible Region○

Optimal Solution○

What is Linear Programming?

Linear Programming (LP) is a mathematical technique used to optimize (maximize or minimize) a linear objective function subject to a set of linear constraints (equalities or inequalities). It is widely used in business, economics, engineering, and resource management.

Definition

Linear Programming Problem (LPP) is the problem of finding the values of variables x and y that optimise (max/min) a linear function Z = ax + by, subject to linear constraints and non-negativity restrictions x ≥ 0, y ≥ 0.

Key Terminology

Term	Meaning
Objective Function	The linear function Z = ax + by to be maximised or minimised.
Decision Variables	The unknowns x, y whose optimal values we seek.
Constraints	Linear inequalities or equations that limit the decision variables.
Non-negativity Restriction	x ≥ 0, y ≥ 0 (quantities can't be negative in real life).
Feasible Region	The common region satisfying ALL constraints including x ≥ 0, y ≥ 0.
Feasible Solution	Any point (x, y) lying in the feasible region.
Optimal Solution	A feasible solution that gives the maximum/minimum value of Z.
Corner Point	A vertex (corner) of the feasible region polygon.
Infeasible Problem	When the feasible region is empty (no solution exists).
Unbounded Problem	When the feasible region extends infinitely and Z has no max (or no min).

⚡ Key Theorem — Corner Point Theorem

If the feasible region is bounded, then the objective function Z attains its maximum and minimum values at the corner points (vertices) of the feasible region. If the feasible region is unbounded, the maximum/minimum may or may not exist — always verify using an open half-plane test.

📌

Board Exam Tip

Always state and label the objective function and constraints clearly in your answer.
For 2–3 mark questions, defining terms like feasible region and optimal solution can earn easy marks.
NCERT-style questions always have a bounded feasible region — check all corner points.

🎯

JEE Tip

JEE mainly tests conceptual understanding and speed. Know the corner point theorem cold.
Quickly sketch the region mentally — identifying corner points fast is the key skill.
Watch for unbounded regions: the problem may ask whether a max or min exists.

General Form of an LPP

Maximise (or Minimise): Z = c₁x₁ + c₂x₂ + … + cₙxₙ

Subject to constraints: a₁₁x₁ + a₁₂x₂ + … ≤ b₁ a₂₁x₁ + a₂₂x₂ + … ≤ b₂ ⋮ x₁, x₂, … ≥ 0

For Class 12, we deal with two decision variables (x, y), making graphical solution possible.

📝

Mathematical Formulation of LPP

Translating real-world problems into mathematical models

Steps to Formulate an LPP

Identify Decision Variables: What quantities can we control? Name them x and y (e.g., units of product A and product B).
Write the Objective Function: Express the quantity to be optimised (profit, cost, distance, etc.) as Z = ax + by.
Identify Constraints: List all restrictions (resources, capacity, demand, time, etc.) as linear inequalities.
Add Non-negativity Constraints: x ≥ 0, y ≥ 0 (physical quantities cannot be negative).
Solve: Use the graphical method to find the feasible region and evaluate Z at corner points.

EXAMPLE 1

Manufacturing Problem — Formulation

A factory manufactures two products A and B. Each unit of A requires 2 hours on machine M₁ and 1 hour on M₂. Each unit of B requires 1 hour on M₁ and 2 hours on M₂. M₁ is available for 10 hours/day and M₂ for 8 hours/day. Profit on A is ₹5/unit and on B is ₹7/unit. Formulate the LPP.

Formulation

Decision variables: Let x = units of A, y = units of B

Objective Function: Maximise Z = 5x + 7y

Constraints:

Machine M₁: 2x + y ≤ 10 Machine M₂: x + 2y ≤ 8 Non-negativity: x ≥ 0, y ≥ 0

Tabular Method for Formulation

Always organise the given data in a table before writing the LPP. This reduces errors significantly.

Resource/Activity	Product A (x)	Product B (y)	Availability
Machine M₁ (hrs)	2	1	≤ 10
Machine M₂ (hrs)	1	2	≤ 8
Profit (₹)	5	7	Maximise Z

EXAMPLE 2

Diet Problem — Formulation

A dietician wants a patient to get at least 80 units of protein and at least 48 units of carbohydrates per day. Food F₁ contains 4 units protein & 2 units carbs per serving; Food F₂ contains 2 units protein & 4 units carbs per serving. F₁ costs ₹3/serving, F₂ costs ₹2/serving. Formulate the LPP to minimise cost.

Formulation

Minimise: Z = 3x + 2y Subject to: 4x + 2y ≥ 80 (protein) 2x + 4y ≥ 48 (carbohydrates) x ≥ 0, y ≥ 0

📌

Board Exam Tip

In formulation-only questions (2 marks), writing the objective function and all constraints correctly earns full marks — you don't need to solve.
Read the problem at least twice before writing variables. Common error: swapping x and y roles.
Explicitly state units (e.g., "x = number of units of Product A").
Don't forget to write x ≥ 0, y ≥ 0 — marks are often lost here!

🎯

JEE Tip

JEE rarely tests pure formulation — focus on quickly identifying constraints and directly computing corner points.
For multiple-choice: if the question gives the formulation, jump straight to graphing or corner point evaluation.

📊

Graphical Method of Solving LPP

Corner point method and iso-profit line method — step by step

The Graphical Method — Overview

Since Class 12 LPPs have only two variables (x and y), we can plot constraints on the xy-plane and find the feasible region graphically. The optimal solution always occurs at one of the corner points of this region.

Step-by-Step Procedure

Convert constraints to equations: Replace ≤ or ≥ with = and plot each line on the graph. Find x and y intercepts for each line.
Determine which side satisfies each inequality: Test the origin (0,0). If it satisfies the inequality, shade that side; otherwise shade the other side.
Identify the Feasible Region: The region satisfying ALL constraints simultaneously (the intersection of all shaded regions), also bounded by x ≥ 0, y ≥ 0 (first quadrant).
Find Corner Points: Identify all vertices of the feasible region polygon. Solve pairs of constraint equations simultaneously to find intersection points accurately.
Evaluate Z at each corner point: Calculate the value of the objective function at every vertex.
Identify the Optimal Value: The largest value of Z gives the maximum; the smallest gives the minimum. State the optimal x, y, and Z.

SOLVED EXAMPLE

Complete Graphical Solution

Problem: Maximise Z = 5x + 7y subject to:

2x + y ≤ 10 x + 2y ≤ 8 x ≥ 0, y ≥ 0

Solution

Step 1 — Find intercepts:

Constraint Line	x-intercept	y-intercept
2x + y = 10	(5, 0)	(0, 10)
x + 2y = 8	(8, 0)	(0, 4)

Step 2 — Test origin for each:
2(0)+0 = 0 ≤ 10 ✓ 0+2(0) = 0 ≤ 8 ✓ → Origin side is feasible for both.

Step 3 — Find intersection of the two lines:
2x + y = 10 and x + 2y = 8 → Subtract: x − y = 2 and add: 3x = 12 → x = 4, y = 2 → Point (4, 2)

Step 4 — Corner Points of feasible region:

Corner Point	Z = 5x + 7y
O(0, 0)	5(0) + 7(0) = 0
A(5, 0)	5(5) + 7(0) = 25
B(4, 2)	5(4) + 7(2) = 20 + 14 = 34
C(0, 4)	5(0) + 7(4) = 28

∴ Maximum Z = 34 at x = 4, y = 2

Types of Feasible Regions

🔷

Bounded Feasible Region

A closed polygon — both maximum and minimum values of Z always exist at corner points. Most Class 12 problems are bounded.

⬚

Unbounded Feasible Region

Extends infinitely in some direction. Maximum may not exist for maximisation, or minimum may not exist for minimisation. Must verify using open half-plane test.

🚫

Empty / Infeasible

No common region satisfies all constraints. No solution exists. The problem is said to be infeasible.

↔️

Multiple Optimal Solutions

If Z has the same value at two adjacent corner points, then all points on the line segment joining them are also optimal solutions.

Unbounded Region — Open Half-Plane Test

Procedure

If the feasible region is unbounded and you get a value M at a corner point:

Draw the half-plane: ax + by > M (for max) or ax + by < M (for min).

• If this half-plane has no point in common with the feasible region → M is indeed the optimal value.
• If it has common points → the problem has no finite maximum (or minimum).

⚡ Iso-Profit Line Method (Alternative)

Draw several lines of the form Z = ax + by = k for increasing values of k. The last such line that still touches the feasible region gives the optimal solution. Less reliable for exams — prefer the corner point method.

📌

Board Exam Tip

Always draw the graph neatly. Label all corner points and shade the feasible region.
Show the table of Z values at each corner point — this earns stepmark in 5-6 mark questions.
State the optimal solution clearly: "Maximum value of Z is ___ attained at x = ___, y = ___".
For minimisation with unbounded region, always perform the open half-plane test.
Common mistake: forgetting to include the origin O(0,0) as a corner point — always check if it's a vertex.

🎯

JEE Tip

For JEE, find corner points algebraically by solving pairs of constraint equations — avoid relying on the graph alone.
If corner points are rational numbers, double-check by substituting back into constraints before computing Z.
In objective-type questions, often only one or two corner points need evaluation if you spot the geometry quickly.

🏭

Different Types of LPP

Manufacturing, Diet, Transportation — with examples and strategies

Classification of LPP Problems

🏭

Manufacturing Problems

Determine quantities of products to manufacture to maximise profit or minimise cost, subject to machine time, labour, or raw material constraints.

🥗

Diet Problems

Find the minimum cost diet that meets nutritional requirements (proteins, vitamins, calories). Usually minimisation problems with ≥ type constraints.

🚚

Transportation Problems

Minimise total transportation cost of shipping goods from sources to destinations. Involves supply constraints (≤) at source and demand constraints (≥) at destination.

📦

Allocation Problems

Allocate limited resources (labour, time, materials) to activities in order to optimise a given objective. Generalisation of manufacturing problems.

MANUFACTURING

NCERT-Style Complete Problem

A company produces two types of furniture: chairs (x) and tables (y). Each chair requires 3 hrs carpentry and 1 hr finishing. Each table requires 5 hrs carpentry and 2 hrs finishing. Available: 15 hrs carpentry, 6 hrs finishing per day. Profit per chair: ₹45, per table: ₹80. How many of each to maximise profit?

Complete Solution

Maximise Z = 45x + 80y Subject to: 3x + 5y ≤ 15 (carpentry) x + 2y ≤ 6 (finishing) x ≥ 0, y ≥ 0

Corner Points:

Point	How Found	Z = 45x + 80y
O(0,0)	Origin	0
A(5,0)	x-intercept of 3x+5y=15	225
B(0,3)	y-intercept of x+2y=6	240
C(0,3)... check intersection	3x+5y=15 ∩ x+2y=6 → x=0, y=3

Solving: from x+2y=6 → x=6-2y; sub: 3(6-2y)+5y=15 → 18-6y+5y=15 → y=3, x=0

Also check (5,0): x+2(0)=5 > 6? No, 5 ≤ 6 ✓. And 3(5)=15 ✓

Maximum Z = 240 at x = 0, y = 3 → Produce 3 tables/day

DIET PROBLEM

Minimisation Example

A person needs at least 10 units of Vitamin A and 12 units of Vitamin C daily. Food P contains 2 units of Vit A and 4 units of Vit C per unit; Food Q contains 4 units of Vit A and 2 units of Vit C per unit. Cost of P: ₹5/unit, Q: ₹3/unit. Minimise cost.

Formulation & Solution

Minimise Z = 5x + 3y Subject to: 2x + 4y ≥ 10 → x + 2y ≥ 5 (Vitamin A) 4x + 2y ≥ 12 → 2x + y ≥ 6 (Vitamin C) x ≥ 0, y ≥ 0

Corner Points (unbounded region):

Point	Z = 5x + 3y
A(5, 0): x+2(0)=5≥5 ✓; 2(5)+0=10≥6 ✓	25
B(7/3, 4/3): intersection of both lines	5(7/3)+3(4/3) = 35/3+4 = 47/3 ≈ 15.67
C(0, 6): 0+2(6)=12≥5 ✓; 0+6≥6 ✓	18

Open half-plane test for min: Draw 5x+3y < 47/3. It has common points with feasible region? Check (0,6): 5(0)+3(6)=18 < 47/3=15.67? No, 18 > 15.67. Check if any feasible point gives Z < 47/3 — intersection point gives minimum.

Minimum Z = 47/3 ≈ ₹15.67 at x = 7/3, y = 4/3

Identifying the Type — Quick Guide

Keyword in Problem	Type	Objective	Constraint Type
Profit, Revenue, Earnings	Manufacturing	Maximise	≤ (resources)
Cost, Expenditure, Minimum cost	Diet/Transport	Minimise	≥ (requirements)
At most, not more than, available	Any	Max/Min	≤
At least, not less than, required	Any	Max/Min	≥
Exactly, equal to	Any	Max/Min	= (equality)

📌

Board Exam Tip

Most 6-mark questions combine formulation + solving. Allocate ~1.5 min for formulation, ~4.5 min for solving.
For diet problems, the feasible region is unbounded above-right. Always do the open half-plane test to confirm the minimum exists.
If you get non-integer corner points in a manufacturing problem, the answer can be fractional — don't panic and round off unless specifically asked.
Re-read the final answer against the question: "maximise profit" → pick the maximum Z value, not minimum.

🎯

JEE Tip

JEE problems on LPP are usually 4-mark questions — test whether the student can identify corner points and evaluate Z quickly.
Common JEE trap: providing an unbounded region and asking for a maximum — the answer may be "does not exist".
Watch for questions that give the objective function value and ask which corner point achieves it (reverse problem).

🧪

Practice MCQs

Test your understanding — click to check answers

🎯 Quick Concept Check

8 questions — Board + JEE level. Click an option to see the answer instantly.

Q1. The feasible region of an LPP is always a ___

Q2. Corner point theorem states the optimal value is attained at a ___

Q3. The objective function Z = 3x + 5y is to be maximised over the feasible region with corner points: (0,0), (6,0), (4,3), (0,5). What is the maximum value?

Q4. If the feasible region for a maximisation LPP is unbounded, then the maximum value of Z ___

Q5. Constraints of an LPP are: x + y ≤ 6, x ≥ 2, y ≥ 2. Which point is NOT in the feasible region?

Q6. The maximum value of Z = x + y, subject to x + y ≤ 5, 3x + y ≤ 9, x ≥ 0, y ≥ 0 is:

Q7. [JEE Level] If the objective function is Z = px + qy and the maximum occurs at both (3,4) and (5,2), then:

Q8. For a minimisation LPP, if the feasible region is unbounded with minimum value M at a corner point, the condition for M to be the true minimum is that the open half-plane ax + by < M should have ___

📋

Formula Sheet & Quick Reference

Everything you need — one page, one glance

⚡ One-Line Summary

LPP = Maximise/Minimise Z = ax + by | subject to linear constraints and x,y ≥ 0 | solved graphically by evaluating Z at all corner points of the feasible region.

General Form

Standard LPP Structure

Optimise Z = ax + by Subject to: a₁x + b₁y ≤ c₁ a₂x + b₂y ≤ c₂ x ≥ 0, y ≥ 0

Replace ≤ with ≥ for minimum/diet type problems.

Corner Point Theorem

Bounded Feasible Region

Z_max = max{Z(A), Z(B), Z(C)...} Z_min = min{Z(A), Z(B), Z(C)...}

Where A, B, C… are corner points (vertices) of the feasible polygon.

Line Intercepts

For line ax + by = c

x-intercept: (c/a, 0) y-intercept: (0, c/b)

Set y=0 for x-intercept; set x=0 for y-intercept.

Intersection Point

Solving Two Constraint Lines

a₁x + b₁y = c₁ ...(i) a₂x + b₂y = c₂ ...(ii) Solve simultaneously

Use substitution or elimination. Verify point satisfies ALL constraints.

Unbounded — Max Test

Open Half-Plane for Maximum

Draw: ax + by > M If no feasible point lies in this half-plane → M is max

If common points exist → no finite maximum.

Unbounded — Min Test

Open Half-Plane for Minimum

Draw: ax + by < M If no feasible point lies in this half-plane → M is min

If common points exist → no finite minimum.

Multiple Optima

Infinite Solutions Condition

If Z(P) = Z(Q) for adjacent corner points P and Q, then every point on PQ is optimal

Occurs when the objective function is parallel to a constraint boundary.

Objective Function Check

Parallel Condition

Z = ax + by is parallel to ax + by = c (a constraint line) when slope of Z = slope of constraint

Slope of ax + by = k is −a/b. If Z has same slope as a binding constraint → multiple optima.

📌 Key Facts — Exam Cheat Sheet

Situation	Conclusion
Feasible region is bounded	Both max and min always exist at corner points
Feasible region is unbounded + maximisation	Max may not exist — do half-plane test
Feasible region is unbounded + minimisation	Min may not exist — do half-plane test
Feasible region is empty	No solution — problem is infeasible
Z same at two adjacent corner points	Infinite solutions along that edge
All constraints are ≤ type (+ x,y ≥ 0)	Origin O(0,0) is always a corner point
All constraints are ≥ type	Origin is NOT in feasible region
Non-negativity restriction is missing	Problem extends to negative quadrants — rare in Class 12

⚠️ Common Mistakes to Avoid

❌ Forgetting non-negativity constraints x ≥ 0, y ≥ 0 → always include them.
❌ Not labelling corner points — show coordinates clearly on graph.
❌ Assuming max = corner with max x or y — always evaluate Z at ALL corners.
❌ Skipping verification of intersection points in original constraints.
❌ Not doing open half-plane test for unbounded regions in minimisation.
❌ Shading wrong region — always test (0,0) first to determine which side satisfies each constraint.

🏆

Board Exam — Last Minute Checklist

✅ Define variables clearly at the start
✅ Write objective function with "Maximise Z = " or "Minimise Z = "
✅ List all constraints including x ≥ 0, y ≥ 0
✅ Draw neat graph — label axes, lines, and region
✅ Find ALL corner points (algebraically — don't guess from graph)
✅ Make a table of Z values
✅ State conclusion: "Maximum/Minimum value of Z is ___ at (___, ___)"

🚀

JEE — Speed Tips

⚡ Identify the binding constraints (those forming corner points) quickly by elimination
⚡ For Z = ax + by, gradient direction (a, b) points toward increasing Z — the optimal corner is in that direction
⚡ For MCQs: plug corner points directly into Z rather than graphing fully
⚡ If Z appears to be constant along a line segment, check if it's parallel to a constraint — multiple optima