Linear Programming
Learn Linear Programming with notes, examples, and practice questions.
Chapter Overview
Optimal value of a linear function on a convex polygon always occurs at a corner point of the feasible region.
Linear programming (LPP) optimizes a linear objective function subject to linear inequality constraints. Real uses: production planning, diet problems, resource allocation.
CBSE focuses on graphical method for two variables — feasible region, corner points, optimal value.
Standard Form
Objective
Maximise or minimise Z = ax + by
Constraints
Linear inequalities in x, y (often x≥0, y≥0)
Feasible region
Set of all (x,y) satisfying all constraints
Graphical Method Steps
- Convert each inequality to equation; plot the line
- Determine feasible half-plane (test origin unless line passes through origin)
- Shade feasible region — intersection of all half-planes
- Find corner points (vertices) of feasible polygon
- Evaluate Z at each corner point
- Largest Z = maximum; smallest Z = minimum (if feasible region bounded)
Special Cases
- Unbounded feasible region: max may not exist; min might
- Multiple optimal solutions: Z same at two adjacent corner points → every point on that edge optimal
- No feasible region: constraints inconsistent
- Redundant constraint: does not affect feasible region
Common Constraint Types
- 2x + 3y ≤ 12 → line 2x+3y=12; feasible side toward origin
- x + y ≥ 5 → feasible away from origin
- x ≥ 0, y ≥ 0 → first quadrant only
Solved Examples
Step-by-step solutions — read each step before checking the final answer.
Example 1: Maximise Z
Maximise Z = 3x + 2y subject to x+y≤4, x≥0, y≥0.
- 1Corner points: (0,0), (4,0), (0,4)
- 2Z(0,0)=0, Z(4,0)=12, Z(0,4)=8
- 3Maximum Z = 12 at (4,0)
Answer
Max Z = 12 at (4, 0)
Example 2: Two Constraints
Maximise Z = 5x + 3y: x+y≤6, 2x+y≤8, x,y≥0.
- 1Vertices: (0,0), (4,0), (2,4), (0,6) — check which satisfy both
- 2(2,4): 2+4=6 ✓, 4+4=8 ✓
- 3Z(2,4)=22; compare with other corners
Answer
Check all vertices; typically max at (2,4) with Z=22
Example 3: Minimisation
Minimise Z = 2x + y with x+y≥3, x,y≥0.
- 1Feasible unbounded above-right
- 2Corner (0,3): Z=3; (3,0): Z=6
- 3Minimum Z=3 at (0,3)
Answer
Min Z = 3 at (0, 3)
Key Points to Remember
- ✓ Always list all corner points of feasible region
- ✓ Plot accurately — wrong corner = wrong answer
- ✓ State whether problem is max or min clearly
Exam Tips
- • Shade feasible region neatly in exam
- • Tabulate corner points and Z values
- • Mention 'optimal at corner point' reasoning
- • Check non-negativity constraints x≥0, y≥0
Formula Cheat Sheet
Quick reference — NCERT board exam formulas
Linear Programming
- Objective function: Z = ax + by
- Optimal value occurs at a corner point of the feasible region
- Constraints: linear inequalities + x ≥ 0, y ≥ 0
Practice MCQs — Linear Programming
Test your understanding with topic-wise multiple choice questions. Explanations appear after each answer.
In graphical LPP, optimal value occurs at: