Linear Programming — Class 12

🏭 Factory ka Dilemma

Ek factory do types ke products banati hai — Type A aur Type B. Type A ke liye 2 hours machine time aur 1 hour labor chahiye. Type B ke liye 1 hour machine aur 2 hours labor. Total 100 hours machine aur 80 hours labor available hai. Type A se ₹300 aur Type B se ₹200 profit milta hai. Factory ko kitna A aur kitna B banana chahiye ki maximum profit ho? Yahi Linear Programming Problem (LPP) hai!

1. LP Problem ke Components

Decision Variables: Jo quantities hum choose karte hain (x, y)

Objective Function: Jo maximize ya minimize karna hai (Z = ax + by)

Constraints: Linear inequalities jo limitations represent karti hain

Non-negativity: x ≥ 0, y ≥ 0 (real quantities negative nahi ho sakti)

Standard LPP Form: Maximize/Minimize: Z = c₁x + c₂y Subject to constraints: a₁x + b₁y ≤ r₁ (ya ≥ ya =) a₂x + b₂y ≤ r₂ ... x ≥ 0, y ≥ 0

2. Graphical Method — Step by Step

Steps to Solve LPP Graphically: 1. Constraints ko equations banao aur graph par plot karo 2. Feasible region identify karo (constraints satisfy karne wala area) 3. Corner points nikalo (vertices of feasible region) 4. Har corner point par Z calculate karo 5. Maximum/minimum Z value → optimal solution Corner Point Theorem: Optimal value Z sirf corner points par milti hai!

3. Worked Example

✅ Maximize Z = 3x + 5y subject to:

x + y ≤ 4, x + 3y ≤ 6, x,y ≥ 0

Corner points: O(0,0), A(4,0), B(3,1), C(0,2)

Z at O = 0, Z at A = 12, Z at B = 3(3)+5(1) = 14, Z at C = 0+10 = 10

Maximum Z = 14 at point B(3,1)

4. Types of Solutions

Unique optimal solution: Exactly ek corner point par maximum/minimum.

Multiple optimal solutions: Agar objective function ki line ek constraint ke saath parallel ho — infinite solutions.

Unbounded solution: Feasible region unbounded aur Z arbitrarily large ho sake.

No solution: Feasible region empty (constraints contradict each other).

5. Practice Questions

Q1. Maximize Z=x+y, subject to x+y≤4, x≥0, y≥0. Answer?

Solution

Feasible region: triangle O(0,0), A(4,0), B(0,4). Z at A=4, Z at B=4 → Multiple optimal solutions. Max Z=4 along line segment AB.

Q2. Minimize Z=3x+2y subject to x+y≥4, 3x+y≥6, x,y≥0.