Worked examples — Linear programming — simplex method (intro)

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

Shuru karne se pehle, parent note ki vocabulary ka ek reminder, kyunki hum ise har example ki pehli line mein use karenge:

Recall Woh paanch words jo hum har jagah reuse karte hain

• Decision variables $x_1,x_2,\dots$ — woh numbers jo tum choose kar sakte ho.
• Slack variable $s_i\ge 0$ — woh "unused room" jo $a\cdot x\le b$ ko $a\cdot x+s=b$ mein turn karta hai.
• Basic variable — jise hum actually solve karte hain; non-basic — jise hum $0$ par force karte hain.
• Tableau — equation coefficients ki woh grid jis par hum pivot karte hain.
• Optimal (maximizing ke liye) — tab reach hota hai jab $z$-row mein har number $\ge 0$ ho.

---

The scenario matrix

Simplex method ko teen moving parts wali machine samjho: entering rule, ratio test, stopping rule. Har part ka ek "normal" behaviour hai aur kai "surprising" behaviours hain. Neeche ka grid har combination list karta hai jisse hum survive karna jaante hain. Yahan ten cells (A–J) hain, aur neeche ke naau worked examples sab dus ko cover karte hain — Example 7 deliberately do cells ek saath handle karta hai ($\ge$ constraint ko minimization ke roop mein solve kiya), toh 9 examples $=$ 10 cells. Har example apne cell(s) apni heading mein announce karta hai.

Cell	Is case mein kya unusual hai	Covered by
A. Clean run	Kuch nahi — ek seedha raasta seedha top tak	Example 1
B. Tie in entering column	Do $z$-row entries equally negative	Example 2
C. Tie in ratio test (degeneracy)	Do rows smallest ratio share karti hain; ek basic variable $0$ ho jaata hai	Example 3
D. Unbounded objective	Entering column mein koi positive entry nahi; $z\to +\infty$	Example 4
E. Multiple optima	End mein ek non-basic $z$-row coefficient $0$ ke barabar; poori edge optimal hai	Example 5
F. Degenerate start / zero RHS	Ek constraint ka $b=0$ hai; corner shuruaat se hi ek wall par baitha hai	Example 6
G. $\ge$ constraint	Ulti inequality; surplus + artificial variables chahiye	Example 7
H. Minimization	Hum sabse chhota $z$ chahte hain; $-z$ maximize karo	Example 7
I. Word problem	Numbers ek story + units mein chhupe hain; model banao, phir solve karo	Example 8
J. Exam twist	"Ek coefficient kitna change ho sakta hai answer move hone se pehle?"; sensitivity	Example 9

Cell count reconciled: 10 cells, 9 examples, kyunki Example 7 = Cells G + H saath mein.

---

Example 1 — Cell A: the clean run (baseline, with geometry)

Forecast: Aage padhne se pehle, optimal corner guess karo. "Profit per unit" $x_1$ par zyada steep hai ($4$ vs $3$), toh bet karo winner large $x_1$ ki taraf lean karega. Apna guess likh lo.

Pehle figure padho. Do constraint lines draw ki gayi hain — solid line labelled "$2x_1+x_2=10$" aur dashed line labelled "$x_1+3x_2=15$" (har line figure mein words mein bhi likhi hai, toh tumhe unhe distinguish karne ke liye colour ki zarurat nahi). Hatched region feasible set hai; iske chaar corners (jahan lines cross hoti hain) dots se mark hain aur unke $z$-values ke saath labelled hain. Bada arrow "$z$ increases" top corner $(3,4)$ ki taraf point karta hai — yahi woh corner hai jis ki taraf machine crawl karegi.

1. Slacks add karo. Yeh step kyun? Machine sirf equations khaati hai, toh har $\le$ mein bachi hui jagah ko naam do: $2x_1+x_2+s_1=10,x_1+3x_2+s_2=15,z-4x_1-3x_2=0.$

2. $(0,0)$ par shuru karo. Kyun? $x_1=x_2=0$ set karne se $s_1=10,s_2=15\ge 0$ milta hai — ek legal corner (origin, jahan do axes cross hoti hain, feasible hai), $z=0$.

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

3. Entering variable. Kyun? $-4$ sabse zyada negative hai, toh $x_1$ ko push karna sabse fast gain deta hai. $x_1$ enters.

4. Ratio test. Kyun? RHS ko positive column entries se divide karo: $10/2=5$, $15/1=15$. Sabse chhota $5$ hai (row 1) — aage jaao toh $s_1$ negative ho jaayega. $s_1$ leaves.

5. $2$ par Pivot karo. Pivot kyun? Pivoting entering column ko unit vector banata hai, toh $x_1$ basic (solved for) ho jaata hai jabki $s_1$ out ho jaata hai — yeh exactly next corner par hop karne ka algebra hai. Row1 $÷2$; Row2 $-$ Row1(new); $z$-row $+4\cdot$Row1(new):

   Basis	$x_1$	$x_2$	$s_1$	$s_2$	RHS
   $x_1$	1	$\frac{1}{2}$	$\frac{1}{2}$	0	5
   $s_2$	0	$\frac{5}{2}$	$-\frac{1}{2}$	1	10
   $z$	0	$-1$	2	0	20

6. $x_2$ ke neeche abhi bhi $-1$ hai → optimal nahi. $x_2$ enters. Ratios: $5/\frac{1}{2}=10$, $10/\frac{5}{2}=4$. Sabse chhota $4$ → $s_2$ leaves. $\frac{5}{2}$ par pivot kyun? Same reason: $x_2$ column ko unit vector banana $x_2$ ko basic banata hai aur hum edge ke saath next, higher corner ki taraf move karte hain.

   Basis	$x_1$	$x_2$	$s_1$	$s_2$	RHS
   $x_1$	1	0	$\frac{3}{5}$	$-\frac{1}{5}$	3
   $x_2$	0	1	$-\frac{1}{5}$	$\frac{2}{5}$	4
   $z$	0	0	$\frac{9}{5}$	$\frac{2}{5}$	24

7. Saare $z$-row entries $\ge 0$ → optimal. Corner $(3,4)$, $z=24$.

Verify: Constraints check karo: $2(3)+4=10\le 10$ ✓ (tight), $3+3(4)=15\le 15$ ✓ (tight). Dono tight hain, toh $(3,4)$ ek genuine corner hai (do lines cross ho rahi hain). $z=4(3)+3(4)=24$ ✓. Corners compare karo $(0,0)=0$, $(5,0)=20$, $(0,5)=15$, $(3,4)=24$ — max confirmed, aur yahi woh corner hai jis par figure mein arrow point kar raha tha.

---

Example 2 — Cell B: enters ke liye ek tie

Forecast: Dono variables ka identical profit hai ($5$ each) aur region symmetric hai. Guess: answer symmetry line $x_1=x_2$ par baitha hai.

1. Initial $z$-row: $-5,-5$. Tie: dono "most negative" hain. Tie kyu matter nahi karta? Koi bhi choice phir bhi $z$ increase karegi; simplex dono taraf se converge karta hai. Bland's rule apply karo (top par stated): tie ko lowest index se break karo, toh $x_1$ enters.

2. $x_1$ enters. Ratios $8/1=8$, $8/2=4$ → row 2 leaves ($s_2$). $2$ par pivot kyun? $x_1$ column ko unit vector banana, $x_1$ ko basic banana — corner-hop step:

   Basis	$x_1$	$x_2$	$s_1$	$s_2$	RHS
   $s_1$	0	$\frac{3}{2}$	1	$-\frac{1}{2}$	4
   $x_1$	1	$\frac{1}{2}$	0	$\frac{1}{2}$	4
   $z$	0	$-\frac{5}{2}$	0	$\frac{5}{2}$	20

3. $x_2$ ke neeche $-\frac{5}{2}$ → $x_2$ enters. Ratios $4/\frac{3}{2}=\frac{8}{3}$, $4/\frac{1}{2}=8$ → row 1 leaves. $\frac{3}{2}$ par pivot kyun? Same rule: $x_2$ column ko unit-vector karo, next corner par hop karo:

   Basis	$x_1$	$x_2$	$s_1$	$s_2$	RHS
   $x_2$	0	1	$\frac{2}{3}$	$-\frac{1}{3}$	$\frac{8}{3}$
   $x_1$	1	0	$-\frac{1}{3}$	$\frac{2}{3}$	$\frac{8}{3}$
   $z$	0	0	$\frac{5}{3}$	$\frac{5}{3}$	$\frac{80}{3}$

4. Sab $\ge 0$ → optimal at $(\frac{8}{3},\frac{8}{3})$, $z=\frac{80}{3}\approx 26.67$.

Verify: $x_1=x_2=\frac{8}{3}$ ✓ symmetry forecast se match karta hai. $x_1+2x_2=\frac{8}{3}+\frac{16}{3}=\frac{24}{3}=8$ ✓ tight; $2x_1+x_2=8$ ✓ tight. $z=5\cdot \frac{8}{3}+5\cdot \frac{8}{3}=\frac{80}{3}$ ✓. Agar hum tie doosri taraf break karte, hum same corner par land karte — Cell B ka lesson yahi hai.

---

Example 3 — Cell C: ek ratio-test tie (degeneracy)

Forecast: Teen lines $x_1=2$, $x_2=2$, $x_1+x_2=4$ sab $(2,2)$ se guzarti hain. Teen walls, ek corner: woh corner "over-determined" hai. Guess: optimum $(2,2)$ hai lekin machine ek "stalled" step le sakti hai jahan answer improve nahi hota.

1. Slacks: $x_1+s_1=2$, $x_2+s_2=2$, $x_1+x_2+s_3=4$. Initial tableau ($(0,0)$ par shuru karo):

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

2. $x_1$ enters ($z$-row tie $-1,-1$ → Bland's rule lowest index $x_1$ choose karta hai). Ratios: $2/1=2$ (row 1), $x_2$-row mein $x_1$ column mein $0$ hai (skip), $4/1=4$ (row 3). Sabse chhota $2$ → $s_1$ leaves. Row-1 $x_1$-entry ($=1$) par pivot kyun? $x_1$ ko basic banana aur corner $(2,0)$ par hop karne ke liye:

   Basis	$x_1$	$x_2$	$s_1$	$s_2$	$s_3$	RHS
   $x_1$	1	0	1	0	0	2
   $s_2$	0	1	0	1	0	2
   $s_3$	0	1	$-1$	0	1	2
   $z$	0	$-1$	1	0	0	2

   Ab $z=2$ at corner $(2,0)$ (jahan $x_2=0$ meets $x_1=2$).

3. $x_2$ ke neeche $-1$ → $x_2$ enters. Ratios: $2/1=2$ (row 2, $s_2$), aur row 3 ab $2/1=2$ bhi deta hai ($s_3$) — ek tie. Kyun matter karta hai: hum jo bhi chunu, doosra basic variable exactly $0$ par land karega — ek degenerate basic feasible solution. Bland's rule ise break karta hai: lowest index wala leaving variable chuno, $s_2$ ($s_3$ se neeche index).

   Figure padho: wall labelled "$x_1=2$", wall labelled "$x_2=2$" aur line labelled "$x_1+x_2=4$" sab ek single marked point $(2,2)$ mein pierce karte hain (har line ek alag dash pattern ke saath draw ki gayi hai aur words mein captioned hai). Teen walls, ek corner — yahi visual over-crowding exactly "degenerate" ka matlab hai, aur yahi wajah hai ki do rows ratio test mein tie karti hain.

4. $s_2$ leaves ($x_2$ ko basic banana ke liye row-2 $x_2$-entry par pivot karo). Hum $(2,2)$ par $z=4$ ke saath pahunchte hain, lekin $s_3=0$ basis mein value 0 par baitha hai. Kyun yeh Cell C ka poora point hai: corner $(2,2)$ ko do alag bases se describe kiya ja sakta hai; simplex un ke beech zero improvement ke saath swap kar sakta hai (ek stall). Bland's lowest-index rule exactly woh hai jo us swap ko forever loop karne se rokta hai.

5. Us pivot ke baad $z$-row check karo: sab $\ge 0$ → optimal, $z=4$.

Verify: $(2,2)$: $x_1=2$ ✓ tight, $x_2=2$ ✓ tight, $x_1+x_2=4$ ✓ tight — ek corner par teen tight constraints exactly "degenerate" ka matlab hai. $z=2+2=4$ ✓.

---

Example 4 — Cell D: unbounded objective (koi maximum nahi)

Forecast: Constraints dekho — dono $x_1$ ko enormously grow karne dete hain jab tak $x_2$ peeche rehta hai. Guess: yeh region ek open wedge hai aur $z$ infinity tak push ho sakta hai.

Pehle figure padho. Do constraint lines (ek solid, ek dashed, dono words mein captioned) ek hatched region bound karti hain jo close nahi hoti — yeh forever upper-right mein flare hoti hai. Bada arrow "$z$ increases" us open channel par ride karta hai: jaise tum us par slide karte ho, dono $x_1$ aur $x_2$ bina limit ke badhte hain, toh $z=x_1+x_2$ ki koi ceiling nahi. Ek closed polygon arrow ko ek corner par trap karta; yeh open wedge kabhi nahi karta.

1. Slacks: $-x_1+x_2+s_1=1$, $x_1-2x_2+s_2=2$. Initial $z$-row $-1,-1$.

2. $x_1$ enters ($z$-row tie $-1,-1$ → Bland's rule $x_1$ pick karta hai). Ratio test ko positive column entries chahiye: column $x_1$ hai $(-1,1)$. Sirf row 2 ka $1$ positive hai → ratio $2/1=2$. $s_2$ leaves. Us $1$ par pivot kyun? $x_1$ column ko unit-vector karne aur $x_1$ ko basic banane ke liye — usual corner-hop:

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

3. $x_2$ ke neeche $-3$ → $x_2$ enters. Column $x_2$ hai $(-1,-2)$ — dono negative! Kyun yeh signal hai: ratio test sirf positive entries accept karta hai, aur yahan koi nahi hain. Matlab hum $x_2$ ko forever raise kar sakte hain bina kisi constraint ke hume rokne ke, aur $z$ bina bound ke rise karta hai.

4. Conclusion: LP UNBOUNDED hai. Koi finite maximum nahi hai.

Verify: $x_2=t$ set karo aur basis follow karo: $x_1=2+2t$, $s_1=3+t$ (sab har $t\ge 0$ ke liye $\ge 0$ rehte hain). Phir $z=x_1+x_2=(2+2t)+t=2+3t\to \infty$ as $t\to \infty$ ✓. Forecast (open wedge) sahi nikla.

---

Example 5 — Cell E: multiple optima (ek poori optimal edge)

Forecast: Objective $z=2x_1+2x_2=2(x_1+x_2)$ $x_1+x_2$ ko jitna bada ho sake banana se maximize hoti hai — lekin $x_1+x_2\le 4$ ise $4$ par cap karta hai. Guess: region ke andar segment $x_1+x_2=4$ par har point $z=8$ deta hai. Ek corner nahi — ek poori edge.

Pehle figure padho. Solid line captioned "$x_1+x_2=4$" dashed "objective level lines" (constant $z$ ki lines) ke parallel hai. Kyunki woh parallel hain, objective region ko ek single corner par nahi touch karti — yeh poori bold edge ke saath flat lie karti hai $(3,1)$ se $(0,4)$ tak. Us bold edge par har point same $z=8$ score karta hai; yahi "multiple optima" kaisi dikhti hai.

1. Slacks: $x_1+x_2+s_1=4$, $x_1+s_2=3$. $z$-row $-2,-2$.

2. $x_1$ enters ($z$-row tie $-2,-2$ → Bland's rule $x_1$ pick karta hai). Ratios $4/1=4$, $3/1=3$ → $s_2$ leaves. Row 2 mein $x_1$-entry $=1$ par pivot kyun? Column ko unit-vector karo, $x_1$ ko basic banao, corner $(3,0)$ par hop karo:

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

3. $x_2$ ke neeche $-2$ → $x_2$ enters. Ratio $1/1=1$ → $s_1$ leaves. Row 1 mein $x_2$-entry $=1$ par pivot kyun? Same rule; corner $(3,1)$ par hop karo:

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

4. Sab $z$-row $\ge 0$ → optimal, $z=8$ at $(3,1)$. Lekin $s_2$ dekho: iska $z$-row coefficient $0$ hai aur $s_2$ non-basic hai. Kyun yeh multiple optima signal karta hai: ek non-basic variable ke neeche $0$ ka matlab hai hum ise basis mein la sakte hain aur $z$ nahi badle ga. Aisa karne se hum doosre corner $(0,4)$ par slide karte hain — same $z=8$, exactly woh bold edge jo figure mein thi.

Verify: Corner $(3,1)$: $z=2(3)+2(1)=8$ ✓. Corner $(0,4)$: $z=2(0)+2(4)=8$ ✓. Edge par midpoint $(1.5,2.5)$: $z=2(1.5)+2(2.5)=8$ ✓ — poora segment optimal hai, exactly forecast ke jaisa.

---

Example 6 — Cell F: degenerate start ($b=0$ constraint)

Forecast: Pehli constraint $x_1\le x_2$ with $b=0$ origin se guzarti hai. Toh starting corner $(0,0)$ already us wall par baitha hai — pehla tableau hi degenerate hai. Guess: pehla pivot "stuck" lag sakta hai (koi visible improvement nahi) cheezein move hone se pehle.

1. Slacks: $x_1-x_2+s_1=0$, $x_1+x_2+s_2=4$. Shuru karo $(0,0)$: $s_1=0$, $s_2=4$. Note karo $s_1=0$ already — degenerate start (origin already wall $x_1-x_2=0$ par lie karta hai).

2. $x_1$ enters ($-3$ most negative). Ratios: row 1 $0/1=0$, row 2 $4/1=4$. Sabse chhota $0$ → $s_1$ leaves. Kyun zero ratio theek hai: iska matlab $x_1$ is step mein $0$ se increase kar sakta hai — ek degenerate pivot jo corner ko physically move kiye bina basis swap karta hai.

3. Row-1 $x_1$-entry ($=1$) par pivot kyun? $x_1$ ko basic banana bhale hi hum physically nahi move karenge — basis-swap exactly woh hai jo agle step ko wall se escape karne deta hai:

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

   Abhi bhi $(0,0)$, $z=0$ — forecast ka predicted stall.

4. $x_2$ ke neeche $-5$ → $x_2$ enters. Ratios: row 1 mein $-1$ hai (skip, negative), row 2 $4/2=2$ → $s_2$ leaves. $2$ par pivot kyun? $x_2$ column ko unit-vector karo, $x_2$ ko basic banao, finally wall se ek new corner tak hop karo:

   Basis	$x_1$	$x_2$	$s_1$	$s_2$	RHS
   $x_1$	1	0	$\frac{1}{2}$	$\frac{1}{2}$	2
   $x_2$	0	1	$-\frac{1}{2}$	$\frac{1}{2}$	2
   $z$	0	0	$\frac{1}{2}$	$\frac{5}{2}$	10

5. Sab $\ge 0$ → optimal, $(2,2)$, $z=10$.

Verify: $x_1-x_2=0\le 0$ ✓ tight; $x_1+x_2=4\le 4$ ✓ tight; $z=3(2)+2(2)=10$ ✓. Degenerate first pivot ne humein ek "empty" step cost kiya lekin sahi answer tak pahuncha — forecast se match karta hai.

---

Example 7 — Cells G + H: ek $\ge$ constraint two-phase simplex ke zariye

Forecast: Positive-cost objective ko minimize karna dono variables ko neeche $0$ ki taraf push karta hai; $\ge 2$ constraint unhe rokti hai. Guess hai ki sabse sasta corner woh hai jahan $x_1+x_2=2$ kisi axis se milti hai.

1. Minimization ko maximization mein turn karo (Cell H). Kyun? Machine maximize karti hai. Min $z$ = $-\max (-z)$, toh $w=-2x_1-3x_2$ maximize karo.

2. $\ge$ ko properly convert karo (Cell G) — surplus + artificial. Sirf $-1$ se multiply kyun nahi? Usse ek negative RHS milega, toh origin infeasible hai aur plain simplex shuru nahi kar sakta. Instead, $x_1+x_2\ge 2$ ke liye ek surplus variable $s_1\ge 0$ (jitni amount se hum $2$ exceed karte hain) subtract karo aur ek artificial variable $a_1\ge 0$ (ek temporary crutch jo hume ek legal starting basis deta hai) add karo: $x_1+x_2-s_1+a_1=2,x_1+2x_2+s_2=6.$ Basis $\{a_1,s_2\}$ ke saath shuru karo: $a_1=2,s_2=6\ge 0$ — legal.

3. Phase 1 — artificial ko zero tak drive karo. Kyun? $a_1>0$ ka matlab hai hum cheating kar rahe hain (real constraint abhi tak satisfied nahi hai). $a_1$ minimize karo, yaani $w_1=-a_1$ maximize karo. $a_1=2-x_1-x_2+s_1$ use karke $w_1$ non-basic terms mein express karo, toh $w_1=-2+x_1+x_2-s_1$; $w_1$-row $x_1,x_2,s_1$ ke neeche $-1,-1,+1$ hai.

   Basis	$x_1$	$x_2$	$s_1$	$a_1$	$s_2$	RHS
   $a_1$	1	1	$-1$	1	0	2
   $s_2$	1	2	0	0	1	6
   $w_1$	$-1$	$-1$	1	0	0	$-2$

   $x_1$ enters ($z$-row tie $-1,-1$ → Bland's rule $x_1$ pick karta hai). Ratios $2/1=2$, $6/1=6$ → $a_1$ leaves. $a_1$-row $x_1$-entry ($=1$) par pivot kyun? $x_1$ ko basic banana aur artificial ko kick out karne ke liye:

   Basis	$x_1$	$x_2$	$s_1$	$a_1$	$s_2$	RHS
   $x_1$	1	1	$-1$	1	0	2
   $s_2$	0	1	1	$-1$	1	4
   $w_1$	0	0	0	1	0	0

   $w_1=0$ with $a_1$ non-basic → Phase 1 done, artificial gone, aur $(x_1,x_2)=(2,0)$ ek legal starting corner hai.

4. Phase 2 — ab real objective $w=-2x_1-3x_2$ optimize karo. $a_1$ column drop karo. $w$ ko non-basic terms mein express karo: $x_1=2-x_2+s_1$ ke saath, $w=-2(2-x_2+s_1)-3x_2=-4-x_2-2s_1$, toh $w$-row $x_2$ ke neeche $-1$ aur $s_1$ ke neeche $-2$ hai:

   Basis	$x_1$	$x_2$	$s_1$	$s_2$	RHS
   $x_1$	1	1	$-1$	0	2
   $s_2$	0	1	1	1	4
   $w$	0	$-1$	$-2$	0	$-4$

   $s_1$ enters ($-2$, most negative). Ratio test $s_1$ column $(-1,1)$ mein positive entries use karta hai: sirf row 2 ka $1$ qualify karta hai → ratio $4/1=4$ → $s_2$ leaves. Us $1$ par pivot kyun? $s_1$ column ko unit-vector karo, $s_1$ ko basic banao, ek new corner par hop karo:

   Basis	$x_1$	$x_2$	$s_1$	$s_2$	RHS
   $x_1$	1	2	0	1	6
   $s_1$	0	1	1	1	4
   $w$	0	1	0	2	4

   Yeh naya corner $(x_1,s_1)=(6,4)$ hai, yaani $(x_1,x_2)=(6,0)$, $w$-row RHS $=4$ ke saath, matlab $-w=4\Rightarrow w=-4$ — pichle tableau jaisa hi $w$. Toh $s_1$ pivot ne $w$ improve nahi kiya: dono tableaux $w=-4$ record karte hain. Stored optimum $w=-4$ at corner $(2,0)$ hai (pre-pivot tableau already optimal tha). Isliye true optimum $w=-4$ hai, yaani $z=-w=4$, at $(2,0)$.

Verify: $(2,0)$ ki feasibility: $2+0=2\ge 2$ ✓ tight, $2+0=2\le 6$ ✓. $\{x_1+x_2\ge 2,x_1+2x_2\le 6,x\ge 0\}$ ke har corner ko cross-check karo: $(2,0)\to z=4$, $(0,2)\to 6$, $(6,0)\to 12$, $(0,3)\to 9$; do lines $x_1=-2<0$ par milti hain (discard). Minimum $z=\min \{4,6,12,9\}=4$ at $(2,0)$ ✓ — two-phase result aur forecast se match karta hai (ek axis par corner).

---

Example 8 — Cell I: ek real-world word problem (with units)

Forecast: Tables per unit zyada earn karte hain lekin carpentry zyaada use karte hain. Guess hai ek mix, "all tables" nahi.

1. Model banao (word problems ka mushkil part). Pehle units define kyun? Taaki constraints balance karein. $x_1=$ chairs/day, $x_2=$ tables/day (dono dimensionless counts).

   \underbrace{2x_1+1x_2\le 8}_{\text{polishing hr}},\quad x_1,x_2\ge0.$$ Objective (dollars/day): $z=20x_1+30x_2$.

2. Slacks $s_1$ (spare carpentry hr), $s_2$ (spare polishing hr). $z$-row $-20,-30$.

3. $x_2$ enters ($-30$ most negative). Ratios $12/3=4$, $8/1=8$ → $s_1$ leaves. $3$ par pivot kyun? $x_2$ column ko unit-vector karo, $x_2$ ko basic banao, next corner par hop karo:

   Basis	$x_1$	$x_2$	$s_1$	$s_2$	RHS
   $x_2$	$\frac{1}{3}$	1	$\frac{1}{3}$	0	4
   $s_2$	$\frac{5}{3}$	0	$-\frac{1}{3}$	1	4
   $z$	$-10$	0	10	0	120

4. $x_1$ ke neeche $-10$ → $x_1$ enters. Ratios $4/\frac{1}{3}=12$, $4/\frac{5}{3}=\frac{12}{5}$ → $s_2$ leaves. $\frac{5}{3}$ par pivot kyun? Same rule: $x_1$ ko basic banao, final corner par hop karo:

   Basis	$x_1$	$x_2$	$s_1$	$s_2$	RHS
   $x_2$	0	1	$\frac{2}{5}$	$-\frac{1}{5}$	$\frac{16}{5}$
   $x_1$	1	0	$-\frac{1}{5}$	$\frac{3}{5}$	$\frac{12}{5}$
   $z$	0	0	8	6	144

5. Sab $\ge 0$ → optimal: $x_1=\frac{12}{5}=2.4$ chairs, $x_2=\frac{16}{5}=3.2$ tables, profit z=\144$/day.

Verify (with units!): Carpentry used $=1\cdot \frac{12}{5}+3\cdot \frac{16}{5}=\frac{12+48}{5}=\frac{60}{5}=12$ hr $\le 12$ ✓ (sab use, tight). Polishing $=2\cdot \frac{12}{5}+1\cdot \frac{16}{5}=\frac{24+16}{5}=\frac{40}{5}=8$ hr $\le 8$ ✓ (sab use, tight). Dono constraints tight ⇒ genuine corner. Profit $z=20\cdot \frac{12}{5}+30\cdot \frac{16}{5}=\frac{240+480}{5}=\frac{720}{5}=144$ ✓. (Sanity: do tight equations $x_1+3x_2=12$, $2x_1+x_2=8$ directly solve karne se same $(\frac{12}{5},\frac{16}{5})$ milta hai.)

---

Example 9 — Cell J: the exam twist (sensitivity)

Forecast: Agar chairs