Exercises — Linear programming — simplex method (intro)

(a) Choices hain $x_1,x_2$ → 2 decision variables. (b) Har $\le$ constraint ke liye ek slack (na ki $x\ge 0$ ke liye, kyunki woh variables ko non-negative rakhke handle hota hai). Do constraints → 2 slacks $s_1,s_2$. (c) Total = decisions + slacks $=2+2=4$.

Non-basic $x_1=x_2=0$, toh corner ==origin $(0,0)$== hai. Phir $z=5(0)+4(0)=0$. Slacks $s_1=24,s_2=6$ bas yeh kehte hain ki "origin par saara resource abhi bhi unused hai" — dono constraints slack hain, koi bhi tight nahi hai.

Slacks: $x_1+s_1=4,2x_2+s_2=12,3x_1+2x_2+s_3=18$. $z$-row hai $z-3x_1-5x_2=0$, yani coefficients $(-3,-5)$. Enter: sabse zyada negative $-5$ hai $x_2$ ke neeche → $x_2$ enters (per unit $x_2$ badhane se $z$ sabse tezi se badhta hai). Ratio test — sirf woh rows jahaan $x_2$-column entry positive ho:

• Row $s_1$: $x_2$-entry hai $0$ → skip (ek $0$ kabhi increase ko bound nahi karta).
• Row $s_2$: $12/2=6$.
• Row $s_3$: $18/2=9$.

Sabse chhota ratio $6$ hai → $s_2$ leaves. $x_2$ ko $6$ tak push karne se $s_2=0$ ho jaata hai (constraint $2x_2\le 12$ tight ho jaata hai) jabki baaki $\ge 0$ rehte hain. Naya corner: $x_1=0,x_2=6$, toh $(0,6)$ aur $z=3(0)+5(6)=30$.

Pehle pivot ke baad, $x_2$ basic hai ($=6$), aur $z$-row mein $x_1$ ke neeche abhi bhi negative hai, toh hum dobara pivot karte hain. Row-reduction ko completion tak le jaana (enter $x_1$, ratio test $3x_1+2x_2\le 18$ row choose karta hai) humein $2x_2=12$ aur $3x_1+2x_2=18$ ke intersection par le jaata hai: $2x_2=12\Rightarrow x_2=6,3x_1+2(6)=18\Rightarrow 3x_1=6\Rightarrow x_1=2.$ Corner $(2,6)$, aur $z=3(2)+5(6)=6+30=36$. $z$-row ab sab $\ge 0$ hai → optimal. Raaste mein teesra constraint check karo: $x_1=2\le 4$ ✓, dono sensibly use ho gaye. Neeche figure mein corner walk dekho.

$z$-row equation hai $z=2x_1+7x_2-4s_2$ (negatives ko doosri taraf le jaao). Toh $\partial z/\partial x_2=7$, sabse bada positive rate. $x_2$ enters — ise badhane se $z$ per unit $7$ badhta hai, $x_1$ ke $2$ se zyada; $s_1,s_2$ columns ($0$ aur $+4$) ya toh kuch nahi karte ya $z$ kam kar dete hain, toh hum unhe kabhi nahi badhaaenge. "$z$-row mein sabse zyada negative" exactly "sabse bada positive rate of gain" hai.

Haan — optimal hai, kyunki har $z$-row coefficient $\ge 0$ hai. $z=\text{(const)}-3x_2-1s_1-5(\cdot )$ padhne par: kisi bhi currently-non-basic variable ko badhane se $z$ sirf kam ho sakta hai (ek $0$ ise unchanged rakhta hai). Improvement ki koi direction nahi bachi, toh hum top corner par baithe hain. Yeh parent note ka optimality test ek picture ki tarah hai: objective ramp ab kisi bhi feasible direction mein upar ki taraf nahi jhukti.

Negate kyun? Simplex loop maximize karne ke liye bana hai. $z$ minimize karna same hai jaise $w=-z=x_1+3x_2$ maximize karna, kyunki $\min z=-\max (-z)$. Slacks: $x_1+x_2+s_1=5,x_1+2x_2+s_2=8$. $w$-row coefficients hain $(-1,-3)$. Pivot 1 — enter $x_2$ (most negative $-3$). Ratios: $5/1=5$, $8/2=4$ → $s_2$ leaves. Naya corner: line $x_1+2x_2=8$ par $x_1=0$ ke saath → $x_2=4$, giving $(0,4)$, $w=3(4)=12$. $w$-row abhi bhi $x_1$ ke neeche negative dikhata hai, toh continue karo. Pivot 2 — enter $x_1$. Binding pair hai $x_1+x_2=5$ aur $x_1+2x_2=8$. Solve: $\text{subtract: }(x_1+2x_2)-(x_1+x_2)=8-5\Rightarrow x_2=3,x_1=5-3=2.$ Corner $(2,3)$: $w=2+3(3)=2+9=11$? Dono objectives carefully check karo: $w=x_1+3x_2=2+9=11$. $(0,4)$ se compare karo: $w=12$. Kyunki $12>11$, corner $(0,4)$ actually $w$ ke liye behtar hai — $x_1$ column yahan $w$ improve nahi karega, toh $w$-row pivot 1 ke baad already sab $\ge 0$ hai. Optimum: $(0,4)$, $w=12$. Isliye $\min z=-w=-12$ at $(0,4)$. (Moral: hamesha evaluate karo — ratio/entering rules ek move propose karte hain, lekin optimality test hi confirm karta hai ki aap pahunch gaye hain.)

Strong duality se, dual ka optimal (ek minimization) primal ke optimal ke barabar hota hai. Toh dual optimum hai $36$. Usefulness: simplex se primal finish karne ke baad, $36$ value wala koi bhi feasible dual solution compute karna prove karta hai ki aap true optimum par pahunche — "z-row sab non-negative ho gayi" se pare ek doosra, independent certificate. Isliye tableau ke final $z$-row entries slack columns ke neeche exactly dual variable values hoti hain.

Tie ka matlab hai entering variable exact same value par do constraints hit karta hai — ek corner se $m$ se zyada constraints guzarti hain. Woh corner degenerate hai (over-determined). Practical danger: ek pivot basis variables swap kar sakta hai jabki $z$ nahi badalta (ek "stall"), aur rare cases mein method ek basis par cycle back kar sakta hai jo woh pehle visit kar chuka hai, kabhi terminate nahi karta. Fixes: Bland's rule (smallest index wala variable choose karke ties break karo) termination guarantee karta hai. Geometrically vertex theek hai; bookkeeping ko bas ek anti-cycling tie-break chahiye.

Slack: $x_1-x_2+s_1=1$. $z$-row hai $(-1,-1)$; maano $x_2$ enter karta hai. Sirf ek constraint row mein uska column entry hai $-1$ (negative). Ratio test sirf positive entries use karta hai — yahan koi nahi hai. Matlab: $x_2$ badhne par, $s_1=1-x_1+x_2$ bhi badhta hai, toh koi constraint kabhi $x_2$ ko nahi rokti. Hum $x_2$ (aur $z$) bina kisi limit ke badha sakte hain → LP unbounded hai, $z\to +\infty$. Tableau mein signal: ek negative $z$-row entry jiske poore column mein koi positive entry nahi = unbounded objective. (Figure dekho — feasible region upar hamesha ke liye khulti hai.)

$\ge$ convert karo: $x_1+x_2\ge 5\Rightarrow -(x_1+x_2)\le -5$, jiska RHS $-5<0$ hai. Basic starting solution $x_1=x_2=0$ slack $=-5<0$ deta hai → feasible nahi, toh origin ek valid starting corner nahi hai; plain simplex ko $\mathbf{b}\ge 0$ chahiye. Ek-line reason ki koi solution exist nahi karta: ek sum dono $\le 2$ aur $\ge 5$ nahi ho sakta, toh feasible region empty hai (dono half-planes kabhi overlap nahi karte). Handle karne ke liye two-phase ya Big-M method chahiye jo pehle ek feasible corner dhoonde — jo yahan infeasibility report karta hai.

Entering variable woh hota hai jiska $z$-row coefficient most negative ho. Leaving variable smallest positive ratio RHS ÷ column entry se choose hota hai. Hum tab rukते hain jab har $z$-row coefficient ==$\ge 0$ ho. Ratio-test column jisme no positive entries hon woh unbounded objective signal karta hai. Ratio test mein tie ek degenerate== vertex signal karta hai aur cycling ka risk hota hai.