Visual walkthrough — Linear programming — simplex method (intro)

4.10.21 · D2 · Maths › Advanced Topics (Elite Level) › Linear programming — simplex method (intro)

---

Step 1 — Playground draw karo (feasible region)

KYA. Humein yeh problem di gayi hai $z=\underset{\text{profit per }{x}_1}{\underbrace{3}}{x}_1+\underset{\text{profit per }{x}_2}{\underbrace{2}}{x}_2$ jise hum jitna bada ho sake banana chahte hain, aur do rules jo pair $(x_1,x_2)$ ko maanne padte hain: $\underset{\text{rule A}}{\underbrace{x_1+x_2\le 4}},\underset{\text{rule B}}{\underbrace{x_1+3x_2\le 6}},\underset{\text{pehle quadrant mein raho}}{\underbrace{x_1\ge 0,x_2\ge 0}}.$

Yahan $x_1$ aur $x_2$ bas do dials hain jo tum ghuma sakte ho — inhe decision variables kaho. Donon dials ki har ek choice ek flat map par ek point hai. Har "$\le$" rule kehta hai "ek seedhi line ke ek taraf raho". Saare allowed sides ko overlap karo aur tumhe ek shape milti hai.

YEH KYUN PEHLE. Kisi bhi algebra se pehle, humein legal choices ki space ko dekhna hai. Ek "$\le$" inequality plane ko do hisson mein kaatti hai — ek half-plane — aur ek half rakhti hai. Chaar rules = chaar half-planes. Unka common overlap feasible region hai: har woh point jo koi rule nahi todta.

PICTURE. Neeche shaded region wahi overlap hai — ek chaar-kona fenced field. Uske corners marked hain. Maximum sirf unhi corners par ho sakta hai (hum Step 2 mein prove karte hain kyun).

---

Step 2 — Prize corner par kyun baithta hai

KYA. Objective $z=3x_1+2x_2$ har point par ek value leta hai. $z$ ki same value share karne wale points ek seedhi line par hote hain: $3x_1+2x_2=c$ set karo kisi fixed number $c$ ke liye aur tumhe ek line milti hai. $c$ badlo aur line slide karti hai — apne aap ke parallel. Yeh $z$ ki level lines hain.

YEH TOOL KYUN. Hum sabse bada $z$ chahte hain, toh hum poochte hain: sliding line "zyada profit" direction mein kitni door ja sakti hai aur field ko touch karti rahe? Steepest increase ki direction gradient $\nabla z=(3,2)$ hai — ek arrow jo dikhata hai kahan $z$ sabse tezi se chadhta hai. Kyunki $z$ linear hai, har level line seedhi hai aur sab parallel hain. Line ko gradient ke upar slide karo jab tak woh field chhodne wali na ho: contact ka aakhri point ek corner hai (ya, tie mein, ek poora edge — lekin edge mein hamesha corners hote hain). Toh humein kabhi interior points ki zaroorat nahi.

PICTURE. Dekho dashed level lines $(3,2)$ direction mein field par aage badh rahi hain. Aakhri wali corner $(4,0)$ ko brush karti hai — winner.

$\underset{\text{climb direction}}{\underbrace{\nabla z}}=\left(\underset{=3}{\underbrace{\frac{\partial z}{\partial x_1}}},\underset{=2}{\underbrace{\frac{\partial z}{\partial x_2}}}\right)=(3,2).$

Yahan $\frac{\partial z}{\partial x_1}$ ka matlab bas yeh hai ki "$z$ har unit $x_1$ par kitna badhta hai" — yeh $3$ hai kyunki term $3x_1$, $x_1$ ek badhne par $3$ add karta hai. Isi idea se $x_2$ ke liye $2$ milta hai.

---

Step 3 — "Less-than" rules ko clean equations mein badlo (slack)

KYA. $x_1+x_2\le 4$ jaisi inequality mein spare room hoti hai. Agar tum apne $4$ ke budget mein se sirf $x_1+x_2=3$ use kar rahe ho, toh $1$ bacha hua hai. Us leftover ko $s_1\ge 0$ naam do: $\underset{\text{used}}{\underbrace{x_1+x_2}}+\underset{\text{leftover}}{\underbrace{s_1}}=\underset{\text{budget}}{\underbrace{4}},\underset{\text{used}}{\underbrace{x_1+3x_2}}+\underset{\text{leftover}}{\underbrace{s_2}}=\underset{\text{budget}}{\underbrace{6}}.$

Naye variables $s_1,s_2$ slack variables hain: har ek measure karta hai ki us rule ka kitna hissa unused hai.

YEH KYUN KARO. Computers aur clean linear algebra ko equations pasand hain, inequalities nahi. Slacks ke saath, har "$\le$" ban jaata hai "$=$", aur ab row-reduction cheezein solve kar sakti hai. Bonus meaning: $s_1=0$ matlab rule A tight hai — tum bilkul us fence line par khade ho.

PICTURE. Har fence ka ek coloured "slack bar" hai jo unused amount dikhata hai. Boundary par bar zero ho jaata hai.

---

Step 4 — Starting corner ko ek table ke roop mein likho (tableau)

KYA. Donon slack equations aur objective ($z-3x_1-2x_2=0$ ke roop mein rearrange karke) ko ek grid mein stack karo. Har row ek equation hai; har column ek variable ke coefficients hai.

Basis	$x_1$	$x_2$	$s_1$	$s_2$	RHS
$s_1$	1	1	1	0	4
$s_2$	1	3	0	1	6
$z$	$-3$	$-2$	0	0	0

YAHAN KYUN, AB KYUN. Humein kisi legal corner se shuru karna hai. $x_1=x_2=0$ set karne par (donon dials off) $s_1=4,s_2=6$ milta hai — dono positive, toh yeh legal hai. Yeh corner $(0,0)$ hai jahan $z=0$ hai. Yeh safe launch pad hai kyunki budgets $\mathbf{b}=(4,6)$ non-negative hain.

PICTURE. Tableau hi corner $(0,0)$ hai ek table ke roop mein draw kiya gaya. Bottom row secretly $z=3x_1+2x_2$ store karti hai (negatives ko paar karo).

Bottom row ko term-by-term padhte hue: $\underset{\text{profit}}{\underbrace{z}}-\underset{\text{gain per }{x}_1}{\underbrace{3}}{x}_1-\underset{\text{gain per }{x}_2}{\underbrace{2}}{x}_2=0.$ Kisi column ke neeche negative number ka matlab hai "woh dial upar karna $z$ ko badhata hai" — improve karne ka mauka.

---

Step 5 — Choose karo kaun enter kare (steepest improvement)

KYA. Sirf $z$-row dekho: $x_1$ ke neeche $-3$, $x_2$ ke neeche $-2$. Sabse negative $-3$ hai. Toh $x_1$ basic banega — yeh enter karta hai.

KYUN. Har negative us dial ki profit rate hai. $-3$ beats $-2$: $x_1$ badhana $3$ per unit deta hai, jo available sabse steep climb hai. Sabse negative chunna greedy "sabse steep fence-edge par chado" move hai.

PICTURE. Corner $(0,0)$ se, do edges nikalty hain — ek $x_1$-axis ke saath, ek $x_2$ ke saath. $x_1$-edge profit mein steeper hai, toh hum uski taraf kadam rakhte hain.

---

Step 6 — Choose karo kaun leave kare (ratio test)

KYA. Hum $x_1$ ko uske edge ke saath slide karte hain. Lekin ek fence hamein rokegi. $x_1$ column mein positive entry wali har row ke liye, $\text{RHS}÷(\text{woh entry})$ compute karo: $\text{row }{s}_1:\frac{4}{1}=4,\text{row }{s}_2:\frac{6}{1}=6.$ Sabse chhota ratio, $4$, jeet jaata hai: row $s_1$ binding fence hai, toh $s_1$ basis leave karta hai.

KYUN SIRF POSITIVE ENTRIES, KYUN SABSE CHHOTA. Jaise $x_1$ badhta hai, har slack $-(\text{column entry})\times x_1$ se badalta hai. Agar entry positive hai, woh slack ghatta hai aur $x_1=\text{RHS}/\text{entry}$ par $0$ ho jayega — wahan tum fence se takraate ho. Pehli fence jo milti hai (sabse chhota ratio) limit hai; usse aage jaana ek slack ko negative kar deta hai = illegal. Negative ya zero entry ka matlab hai woh slack is direction mein kabhi khatam nahi hota, toh woh tumhe kabhi nahi rokta — use skip karo.

PICTURE. Red arrow par $x_1$-axis ke saath saware ho. Fence A (rule A se) tumhe $x_1=4$ par rokta hai; fence B sirf $x_1=6$ par rokta. Tum paas wale par rukते ho, $x_1=4$.

---

Step 7 — Pivot: $x_1$ ko basic banao (row-reduce)

KYA. Pivot (row $s_1$, column $x_1$) wali entry $=1$ hai. Hum row operations use karke uske poore column ko ek unit column $(1,0,0)$ bana dete hain:

• Row $s_1$: pivot ($1$) se divide karo → unchanged.
• Row $s_2$: ${\text{Row}}_2-1\cdot {\text{Row}}_1$ (uske neeche wale $1$ ko khatam karo).
• Row $z$: ${\text{Row}}_z+3\cdot {\text{Row}}_1$ ($-3$ ko khatam karo).

Basis	$x_1$	$x_2$	$s_1$	$s_2$	RHS
$x_1$	1	1	1	0	4
$s_2$	0	2	$-1$	1	2
$z$	0	1	3	0	12

KYUN. Iske baad, table directly padhne par $x_1=4,s_2=2,z=12$ milta hai — hum corner $(4,0)$ par move ho gaye hain. Pivoting exactly yeh hai "equations ko re-solve karo taaki naye corner ki values RHS column mein aa jayein".

PICTURE. Hop: $(0,0)$ se edge ke upar $(4,0)$ tak, profit $0\to 12$ jump karta hai.

Naya $z$-row padhte hue: $z+0\cdot x_1+1\cdot x_2+3\cdot s_1+0\cdot s_2=12$, matlab $z=12-\underset{\ge 0}{\underbrace{1}}{x}_2-\underset{\ge 0}{\underbrace{3}}{s}_1.$ Dono coefficients ab non-negative hain, toh koi bhi off-dial upar karna sirf $z$ ko ghata sakta hai.

---

Step 8 — Rukne ka waqt kab hai (optimality)

KYA. $z$-row ab $0,1,3,0$ hai — koi negative entry nahi bachi. Ruko. Corner $(4,0)$ jahan $z=12$ hai, optimal hai.

KYUN. $z$-row mein negative hamara "improvement available" flag tha. Koi nahi bacha = koi dial upar karke profit nahi kamaaya ja sakta = hum ramp ke top par hain. Yeh Step 2 ki picture se match karta hai: aakhri level line exactly $(4,0)$ ko graze karti thi.

PICTURE. Corner scoreboard — har vertex ki $z$ value dikhaya; $(4,0)$ crown pehanta hai.

Har corner ke against cross-check karo (koi case skip nahi):

Corner	kaise aata hai	$z=3x_1+2x_2$
$(0,0)$	dono dials off	$0$
$(0,2)$	fence B par, $x_1=0$	$4$
$(3,1)$	fences A & B cross	$11$
$(4,0)$	fence A par, $x_2=0$	$12$ ✓

Winner $12$, $(4,0)$ par milta hai — exactly wahan jahan simplex ruka.

---

Ek-tasveer summary

Upar ki sab cheezein ek single frame mein: field, sliding profit lines, corner-hop $(0,0)\to (4,0)$ jo simplex leta hai, aur crowned optimum.

Recall Feynman retelling — poora walk plain words mein

Tum ek bahut-se-corners wale fenced field mein ho (feasible region). Zameen ek flat ramp hai jo "zyada profit" ki taraf jhuki hai (linear objective). Flat ramp par, sabse zyada reachable jagah hamesha ek corner hoti hai, toh tumhe sirf corners visit karne ki zaroorat hai. Fuzzy "$\le$" fences ko exact lines mein badalne ke liye jino par tum compute kar sako, tum har fence ko ek "leftover" measure dete ho — ek slack — jo tab zero hota hai jab tum us fence ko touch karte ho. Tum us easy corner se shuru karte ho jahan sab dials off hain. Tum table padhte ho: bottom row mein koi bhi negative number matlab "yeh dial upar karna profit kamaata hai", toh tum sabse bada earner chuno (enter, sabse negative). Tum us edge par chalo jab tak pehli fence na roke — jo sabse chhote RHS-over-positive-entry ratio se milti hai (leave, smallest ratio). Tum equations re-solve karte ho (pivot) taaki naye corner ke numbers jagah par aa jayein. Repeat karo. Jis pal bottom row mein koi negative nahi bacha, koi dial aur kama nahi sakta — tum sabse unche corner par khade ho. Ho gaya.

---

Connections

• Convex Sets and Polytopes — field ek convex polytope hai; isliye optima corners par rehte hain.
• Gradient and Level Sets — Step 2 ki sliding lines aur $(3,2)$ climb arrow.
• Gaussian Elimination — Step 7 ka pivot exactly guided row reduction hai.
• Duality in Linear Programming — wahi optimum $12$ partner problem se padha gaya.
• Integer Programming — jab dials whole numbers hone chahiye toh kya badalta hai.
• Optimization (Lagrange Multipliers) — is corner-walk ka smooth-constraint cousin.