Linear programming — simplex method (intro)

4.10.21 · Maths › Advanced Topics (Elite Level)

Linear program KYA hota hai?

YEH form KYU? Har "≥" constraint $- 1$ se multiply karke "≤" ban jaata hai; equalities do inequalities mein split hoti hain; minimization $- 1 \times$ maximization hoti hai. Toh yeh ek form fully general hai.

HOW: Inequalities ko equations mein kaise convert karein: slack variables

YEH KYU karte hain? Equations linear algebra se aasani se solve hoti hain (Gaussian elimination). Polytope ke corners kuch variables ko $0$ set karke aur baaki solve karke correspond karte hain — slacks humaare paas exactly yahi karne ke liye ek clean bookkeeping system deti hain.

Simplex tableau ko scratch se derive karna

Neeche diye example ko lekar sab kuch haath se banayenge.

Step 1 — Slacks add karo. KYU? Equations paane ke liye. $x_{1} + x_{2} + s_{1} = 4, x_{1} + 3 x_{2} + s_{2} = 6, z - 3 x_{1} - 2 x_{2} = 0.$

Step 2 — Initial tableau. KYU? Basic variables $s_{1}, s_{2}$ hain (set $x_{1} = x_{2} = 0$ ); yeh corner $(0, 0)$ deta hai jahan $z = 0$ — ek valid starting vertex kyunki $b \geq 0$ .

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

Step 3 — Entering variable choose karo. KYU? Bottom row padhti hai $z = 3 x_{1} + 2 x_{2}$ . $x_{1}$ ke neeche negative entry $- 3$ ka matlab hai $x_{1}$ badhane se $z$ badhta hai. Sabse zyada negative pick karo: $x_{1}$ enter karta hai.

Step 4 — Ratio test (leaving variable). KYU? Hum $x_{1}$ ko upar push karte hain, lekin pehle koi constraint bind karega. Compute $RHS / (positive column entry)$ : row 1 $\to 4/1 = 4$ , row 2 $\to 6/1 = 6$ . Sabse chhota ratio $4$ jeet ta hai (row 1) — aage jaane se $s_{1} < 0$ ho jaayega (infeasible). Toh $s_{1}$ nikalta hai.

Step 5 — Pivot $x_{1}$ -row1 entry (=1) pe. KYU? Us column ko unit vector banaao taaki $x_{1}$ basic ban jaaye. Row1 waisi rehti hai; Row2 $\to$ Row2 − Row1; $z$ -row $\to z$ -row $+ 3 \cdot$ Row1.

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

Ab corner $(4, 0)$ hai, $z = 12$ . Bottom row mein koi negative entry nahi → optimal!

Figure — Linear programming — simplex method (intro)

Graphically verify karo: Vertices hain $(0, 0) z = 0$ , $(0, 2) z = 4$ , $(4, 0) z = 12$ , dono lines ka intersection $(3, 1) z = 11$ . Maximum sach mein $12$ hai $(4, 0)$ pe.

Simplex method KYU kaam karta hai (logic ko steel-man karo)

Maximum vertex pe hota hai — Kyunki $z$ linear hai, uske level sets parallel hyperplanes hain; improving direction mein slide karte hue, tum polytope ki boundary pe rukoge, ek corner pe jaake.
Har pivot ek corner-to-corner move hai ek aisi edge ke saath jo $z$ ko increase karta hai.
Finitely many corners ⇒ process terminate hota hai (rare degeneracy ignore karke).

Common mistake Steel-manned pitfalls

"Most negative rule zaroor sabse kam steps mein dega." Sahi lagta hai kyunki ek unit mein sabse badi improvement. Fix: yeh sabse acchi slope choose karta hai, sabse accha total gain nahi; yeh ek accha heuristic hai, step-count mein optimal nahi. Phir bhi hand work ke liye standard hai.
"Sabse chhota entering coefficient lo." Sahi lagta hai (chhota = 0 ke kareeb?). Fix: maximization ke liye hume sabse zyada negative ( $z$ -row) chahiye — wahan badhane se sabse zyada fayda hota hai.
Galat ratio test: negative ya zero column entries se divide karna. Fix: sirf positive entries use karo; ek negative entry kabhi increase ko bound nahi karti.
" $x_{1} = 4, x_{2} = 0$ doosri constraint ko ignore karta hai." Fix: nahi karta — $s_{2} = 2 > 0$ ka matlab hai woh constraint slack hai (tight nahi), bilkul feasible hai.

Ek doosra worked example (minimization negation ke zariye)

Flashcards

LP ki feasible region kaisi shape ki hoti hai?

Ek convex polytope (half-spaces ka intersection).

Linear objective apna optimum kahan attain karta hai?

Feasible region ke ek vertex (corner) pe.

Slack variable kya hota hai?

Ek non-negative variable jo

\leq

constraint ko equality mein convert karne ke liye add ki jaati hai, unused resource measure karta hai.

Max-problem tableau mein kaunsa variable enter karta hai?

Woh non-basic variable jiska

z

-row mein sabse zyada negative coefficient ho.

Leaving variable kaise choose karte hain?

Minimum-ratio test: sabse chhota RHS ÷ (positive entry) pivot column mein.

Simplex method (maximization) mein kab rukna hai?

Jab sab objective-row coefficients

\geq 0

hon.

Ratio test mein sirf positive entries KYU use karte hain?

Negative/zero entries bound nahi karti ki entering variable kitna badh sakta hai bina infeasible hue.

Minimization LP ko kaise handle karte hain?

Objective ka negative maximize karo; min

z = - max (- z)

Basic feasible solution geometrically kya represent karta hai?

Polytope ka ek vertex (

n

non-basic vars ko 0 set karo,

m

basic walo ko solve karo).

\geq

constraint ko standard form mein kaise convert karte hain?

- 1

se multiply karo taaki

\leq

mein flip ho jaaye (phir slack add karo).

Recall Feynman: 12-saal ke bachche ko explain karo

Ek aisa fenced playground imagine karo jo bahut-se-corners wale khet jaisa ho. Tum wahan khade rehna chahte ho jahan zameen sabse oonchi ho, lekin zameen ek ramp ki tarah flatly tilted hai. Ek fenced khet ke andar flat ramp pe sabse oonchi jagah hamesha fence ke corner pe hoti hai. Toh tum ek corner pe shuru karte ho aur tab hi agale corner pe chalte ho jab woh oocha ho. Jab koi bhi neighbouring corner oocha na ho, tum sabse upar khade ho — ho gaya! Fence ke saath-saath yeh chalne wala trick hi simplex method hai.

Connections

Convex Sets and Polytopes — KYU optima vertices pe hote hain.
Gaussian Elimination — pivoting, row reduction hai ek feasibility rule ke saath.
Duality in Linear Programming — har LP ka ek partner hota hai; optimal values match karte hain.
Gradient and Level Sets — KYU linear objectives boundaries ki taraf slide karte hain, uski geometry.
Integer Programming — kya change hota hai jab variables whole numbers hone chahiye.
Optimization (Lagrange Multipliers) — smooth-constraint wala cousin.