Linear Programming 📊

Formulation se solution tak — step-by-step samjho

1. Linear Programming — Parichay

LP ek mathematical technique hai resources ko optimally allocate karne ke liye — maximize profit ya minimize cost, subject to constraints.

General LP Problem: Maximize/Minimize: Z = c₁x₁ + c₂x₂ + ... + cₙxₙ (Objective Function) Subject to: a₁₁x₁ + a₁₂x₂ ≤ b₁ a₂₁x₁ + a₂₂x₂ ≤ b₂ (Constraints) x₁, x₂ ≥ 0 (Non-negativity)

2. LP Formulation — Ek Manufacturing Problem

Problem Statement

Ek factory do products A aur B banati hai.
Product A: Profit ₹5/unit, Machine time 2 hrs, Labour 4 hrs
Product B: Profit ₹4/unit, Machine time 5 hrs, Labour 2 hrs
Available: Machine 180 hrs, Labour 160 hrs

Formulate LP to maximize profit.

Let x = units of A, y = units of B
Maximize: Z = 5x + 4y
Subject to:
2x + 5y ≤ 180 (Machine hours)
4x + 2y ≤ 160 (Labour hours)
x, y ≥ 0

3. Graphical Method

Constraints ko graph par plot karo (boundary lines)

Non-negativity constraints: x≥0 (Y-axis) aur y≥0 (X-axis)

Feasible region identify karo (saari constraints satisfy hoti hain)

Corner points (vertices) nikalo — feasible region ke corners

Har corner point par Z evaluate karo

Maximum/Minimum Z wala corner point = Optimal Solution

Graphical Solution: Above Problem

Corner Point (x,y)	Z = 5x + 4y
O (0, 0)	0
A (40, 0)	200
B (25, 26)	229 ← Maximum!
C (0, 36)	144

B(25, 26) par Z = 5(25) + 4(26) = 125 + 104 = 229 → Maximum Profit

💡 Fundamental Theorem: Optimal solution (if exists) corner point par hoga. Infinite solutions possible hain jab 2 corners same Z value dete hain (edge is optimal).

3.1 Special Cases

Case	Description
Unbounded Solution	Maximization mein feasible region bounded nahi — Z can go to ∞
Infeasible	Constraints contradict each other → no feasible region
Multiple Optimal	2 corner points dono optimal → infinite solutions on that edge
Degenerate	Corner point mein ek constraint active nahi (slack=0 for more constraints than variables)

4. Transportation Problem

Kisi commodity ko multiple sources se multiple destinations tak minimum cost mein transport karna.

Find xᵢⱼ (units from source i to destination j) Minimize: Σᵢ Σⱼ cᵢⱼ xᵢⱼ Subject to: Σⱼ xᵢⱼ = aᵢ (supply), Σᵢ xᵢⱼ = bⱼ (demand), xᵢⱼ ≥ 0

4.1 North-West Corner Method (Initial Solution)

Udaharan: Transportation Table

	D1	D2	D3	Supply
S1	2	3	5	20
S2	4	1	6	30
S3	3	5	2	10
Demand	15	25	20	60

NW Corner: x₁₁=15 (min(20,15)), x₁₂=5, x₂₂=20, x₂₃=10, x₃₃=10
Total cost = 15×2 + 5×3 + 20×1 + 10×6 + 10×2 = 30+15+20+60+20 = ₹145

4.2 Vogel's Approximation Method (Better Initial Solution)

Step 1: Row aur column penalties nikalo (2nd lowest − lowest cost in that row/col) Step 2: Highest penalty wali row/col mein minimum cost cell ko allocate karo Step 3: Supply/demand adjust karo aur repeat Step 4: Jab tk sab allocations done nahi hote

🎮 Interactive Lab Kholein →