Linear programming — simplex method (intro): Question bank

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

Shuru karne se pehle, woh words aur standing assumptions jinhe hum baar baar use karte hain, plain language mein:

Definition Quick vocabulary refresh

Decision variables $x_{1}, \dots, x_{n}$ woh quantities hain jo hum choose karte hain. Standard-form LP ka standing rule: har original decision variable non-negative hoti hai, $x \geq 0$ . Koi bhi $x_{i}$ kabhi zero se neeche jaane ki permission nahi hai — yahi woh cheez hai jo ratio test quietly protect kar raha hota hai.
$b = (b_{1}, \dots, b_{m})$ right-hand-side vector hai — constraints $A x \leq b$ ki right side par "resource limits". Jab hum $b \geq 0$ likhte hain toh matlab hai har $b_{i} \geq 0$ .
Feasible region ka ek vertex (corner) woh point hai jahan itni constraint-boundaries cross karti hain ki woh point uniquely pin ho jaaye — geometrically polytope ka ek "sharp corner".
Ek constraint tight (active) hoti hai jab hum exactly uski boundary line par baithe hote hain, yaani uska slack variable $0$ ke barabar hota hai. Woh slack hoti hai jab hmare paas room hota hai, yaani uska slack $> 0$ hota hai.

Neeche do pictures hain jo sab kuch anchor karti hain: ek corner kya hota hai, aur kya galat hota hai jab easy starting corner field ke andar bhi nahi hoti.

Figure — Linear programming — simplex method (intro)

Red dot woh corner hai jo objective pick karta hai; black dots woh doosre corners hain jinhein simplex traverse kar sakta hai. Dekho kaise optimum ek sharp corner par baitha hai, kabhi flat interior mein nahi.

True or false — justify

Non-negativity rule

x \geq 0

sirf ek convenience hai jise hum drop kar sakte hain.

False — yeh ek load-bearing assumption hai. Poora starting corner

(0, 0)

, ratio test, aur "non-basic variables ko

0

set karo" — sab variables ke zero se neeche na jaane par rely karte hain; ise drop karo aur corner-hopping logic collapse ho jaati hai.

Har feasible LP ka maximum kisi vertex par attain hota hai.

Generally False — agar region improving direction mein unbounded hai toh maximum

+ \infty

hai (koi maximizer nahi). True tab hota hai jab ek finite maximum exist karta hai: ek linear objective hamesha koi bhi finite optimum kisi vertex par achieve karta hai.

Simplex method polytope ke har vertex ko examine karta hai.

False — yeh corner-to-corner improving edges ke along hop karta hai aur jaldi stop kar leta hai. Zyaadatar vertices kabhi visit nahi hote; yahi skipping exactly woh reason hai kyun yeh brute force se better hai.

Agar saare objective-row coefficients

\geq 0

hain, toh current corner optimal hai.

True for a maximization tableau — koi bhi non-basic variable

z

increase karne ke liye raise nahi ki ja sakti, toh koi bhi neighbouring corner better nahi hai, aur convexity se iska matlab globally optimal hai.

Ek slack variable ka zero hona matlab LP ka koi solution nahi hai.

False — zero slack ka matlab sirf yeh hai ki woh ek constraint tight hai (hum uski boundary par baithe hain). Yeh ek normal, feasible situation hai aur actually har vertex par un constraints ke liye hota hai jo ise define karti hain.

\geq

constraint ko

- 1

se multiply karna change kar deta hai ki kaun se points feasible hain.

False — ek inequality aur uska

- 1

multiple exactly same set of points describe karte hain; sirf "

\leq

" vs "

\geq

" symbol flip hota hai. Isliye standard form koi generality nahi khoata.

Most-negative entering rule guarantee karta hai sabse kam pivots.

False — yeh per unit of the entering variable improvement maximize karta hai (best slope), total gain nahi. Yeh hand-work ke liye ek solid heuristic hai lekin step-optimal nahi hai.

Har basic feasible solution ek vertex hai, aur har vertex ek basic feasible solution hai.

True (standard form mein polytope ke liye) —

n

non-basic variables ko

0

set karna aur

m

basic ones ke liye solve karna algebraically waisa hi hai jaise enough boundary constraints ko intersect karna, jo ki ek corner define karta hai.

Slack variables add karna LP ki optimal value change kar deta hai.

False — slacks sirf

\leq

=

mein rewrite karte hain leftover room ko name dekar; inhe objective ke coefficient mein

0

forced kiya jaata hai aur koi cost add nahi hota. Feasible original variables aur optimum

z

untouched rehte hain.

Pivot column mein non-positive entries wala ek tableau column optimality signal karta hai.

False — yeh unboundedness signal karta hai: entering variable bina kisi constraint ke forever grow kar sakta hai, toh

z \to + \infty

. Optimality

z

-row ke baare mein hai, pivot column ke nahi.

Agar kuch

b_{i} < 0

hai, toh hum phir bhi

(0, 0)

se start kar ke simplex normally chala sakte hain.

False — originals ko

0

set karne se slack

s_{i} = b_{i} < 0

milega, jo

s_{i} \geq 0

violate karta hai. Starting "corner" infeasible hai, isliye pehle koi bhi feasible corner dhundhne ke liye Phase I run karna zaroori hai.

Spot the error

x_{1}

ko increase karna yahan bekar hai kyunki uski

z

-row entry

- 3

hai, ek negative — negatives

z

ko shrink karte hain."

Ulta hai.

z

-row store karta hai

z - 3 x_{1} - \dots

, toh

- 3

matlab hai

z = 3 x_{1} + \dots

;

x_{1}

raise karne se

z

increases hota hai

3

per unit. Ek negative

z

-row entry precisely enter karne ka invitation hai.

"Ratio test ke liye main RHS ko har column entry se divide karunga aur minimum lunga:

4/1

6/ - 2

Non-positive entries ko skip karna zaroori hai.

- 2

se divide karne par

- 3

milta hai, jo galat tarike se "smallest" ke roop mein jeet jaayega, lekin ek negative entry kabhi increase ko bound nahi karti — wahan ki variable to

x

badhne par aur zyaada feasible hoti jaati hai.

(x_{1}, x_{2}) = (4, 0)

par constraint

x_{1} + 3 x_{2} \leq 6

violated hai, kyunki

4 \leq 6

theek hai lekin humne ise ignore kiya."

Koi violation nahi —

4 + 3 \cdot 0 = 4 \leq 6

slack

s_{2} = 2 > 0

ke saath hold karta hai. Constraint simply tight nahi hai; feasibility sirf

\leq

require karti hai, equality nahi.

z

minimize karne ke liye, simplex normally run karo aur last

z

-value ko minimum ke roop mein padho."

Simplex sirf maximize karta hai. Minimize karne ke liye

w = - z

maximize karo; answer hai

min z = - max w

. Raw maximized value padhne se galat sign milta hai.

"Pivot ko sirf constraint rows mein entering column ko zero-out karna hai."

Ise

z

-row (aur RHS) bhi update karna hoga.

z

-row skip karne se stale objective coefficients reh jaate hain, toh agla optimality/entering decision galat numbers par liya jaata hai.

"Kyunki pivoting Gaussian elimination hai, koi bhi pivot element kaam karega."

Sirf ratio-test winner ek legal pivot hai. Plain Gaussian Elimination feasibility ignore karta hai; simplex minimum-ratio rule add karta hai taaki koi bhi basic variable negative na ho jaaye.

"Problem mein

b_{i} = - 5

wali constraint hai, toh yeh automatically infeasible hai."

Galat — negative

b_{i}

ka sirf yeh matlab hai ki easy starting corner available nahi hai, region empty nahi hai. Phase I feasibility decide karta hai; region bilkul non-empty ho sakta hai.

Why questions

Feasible region hamesha convex kyun hoti hai?

Har inequality ek half-space carve out karti hai (ek convex set), aur convex sets ka intersection convex hota hai — toh chahe kitni bhi constraints hon, region mein dents nahi aa sakti (dekho Convex Sets and Polytopes).

Linear objective ka optimum boundary par kyun hona chahiye, interior mein nahi?

Uske level sets parallel flat sheets hain aur gradient kabhi vanish nahi hota; tum hamesha improving direction mein aur slide kar sakte ho jab tak ek wall rokti nahi, toh ek interior point kabhi optimal nahi hota.

Hum simplex corner

(0, 0)

(all originals zero) par kyun shuru karte hain?

Sirf tab jab $b \geq 0$ (har resource limit non-negative ho): tab "originals ko

0

set karo, har slack ko uske

b_{i}

ke barabar let karo" non-negative slacks deta hai, ek instantly-feasible basic solution — ek free starting vertex jisme koi kaam nahi lagta. Agar kuch

b_{i} < 0

ho toh yeh shortcut fail ho jaata hai aur Phase I required hai.

Process terminate kyun karta hai?

Finite number of vertices hain aur har pivot strictly

z

improve karta hai (degeneracy ignore karke), toh koi corner repeat nahi hota aur hum corners improve karne ke liye run out ho jaate hain.

Ratio test mein smallest ratio kyun choose karte hain, largest nahi?

Smallest ratio woh pehli constraint hai jo bind karti hai jaise entering variable badhta hai; wahan rokne se saare variables

\geq 0

rehte hain. Larger ratio par jaane se ek earlier-binding variable negative ho jaayegi — infeasible.

Hum actually finish hone ka pata lagane ke liye duality kyun relevant hai?

Optimality par primal aur dual objective values coincide karte hain; inhe match karna answer ko pivoting path se independent tarike se certify karta hai (dekho Duality in Linear Programming).

Phase I (auxiliary) problem ki zaroorat hi kyun hai?

Kyunki simplex sirf feasible corners ke beech walk kar sakta hai — shuru karne ke liye ek feasible starting corner chahiye. Jab

(0, 0)

feasible nahi hota, Phase I ka kaam ek dhundna hai (ya prove karna ki koi exist nahi karta) regular optimization shuru hone se pehle.

Edge cases

Agar ratio test mein do ratios tie karein toh kya hota hai?

Tumhare paas ek degenerate vertex hai; koi bhi choice legal hai lekin tum

z

improve kiye bina pivot kar sakte ho, cycling ka risk hota hai. Anti-cycling rules (jaise Bland's rule) guaranteed termination restore karte hain.

Agar current corner par koi basic variable pehle se

0

ho toh kya?

Woh phir se degeneracy hai — is corner se zyaada minimum number of constraints pass ho rahi hain, toh ek pivot basis move kar sakta hai bina point ya objective ko move kiye.

Agar pivot column mein ek positive entry hai lekin wahan RHS

0

hai toh kya?

Ratio hai

0/ positive = 0

, sabse chhhota possible, toh woh row ratio test jeet leti hai aur entering variable value

0

par enter karta hai — ek degenerate, zero-improvement pivot.

Agar har

z

-row entry negative hai lekin region upward unbounded hai toh kya?

Simplex ek aisi variable enter karne ki koshish karta hai jiske pivot column mein koi positive entry nahi hai; ratio test koi bound nahi dhundta, toh woh correctly unbounded report karta hai (

z \to + \infty

) corner ki jagah.

Agar objective ek poori edge ke along constant hai (optimum par ek non-basic variable par

z

-row zero)?

Multiple optimal solutions exist karte hain — woh variable zero change ke saath

z

mein enter kar sakta hai, equally-optimal points ki poori ek edge (ya face) sweep karta hai, ek unique corner nahi.

Agar initial basic solution infeasible hai kyunki kuch

b_{i} < 0

hai toh kya?

(0, 0)

start ek negative slack deta hai, toh hum Phase I run karte hain: ek obviously-feasible corner build karne ke liye artificial variables introduce karo, phir unka total minimize karo. Agar woh minimum saare artificials ko

0

par drive kar deta hai, toh hum ek genuine feasible corner par pahunch gaye hain aur Phase II (real objective) par switch karte hain. Neeche figure ka right panel dekho — "start" shaded region ke baahir baitha hai jab tak Phase I use andar nahi le jaata.

Simplex kaise certify karta hai ki ek LP mein koi feasible solution nahi hai?

Agar Phase I artificial variables ke minimum total ke saath end hota hai jo strictly greater than

0

hai — koi valid pivot unhe zero tak push nahi kar sakta — toh koi point saari constraints satisfy nahi karta. Woh leftover positive total infeasibility certificate hai: feasible region empty hai (picture mein, constraint half-planes ka koi common point nahi hai).

Agar variables whole numbers hone ke liye forced hain toh kya change hota hai?

Vertex-optimum guarantee toot jaati hai: integer optimum strictly polytope ke andar baith sakta hai, toh simplex alone insufficient hai aur tumhe Integer Programming methods (branch-and-bound, cutting planes) chahiye hote hain.

Agar ek constraint shuru se equality hai,

\leq

nahi?

Tum ordinary slack add nahi kar sakte (use

0

hona padega); instead ise do

\leq

constraints mein split karo ya ek artificial variable introduce karo jo Phase I mein zero par drive ho — smooth-constraint analogue Optimization (Lagrange Multipliers) se handle hoti hai.

Recall One-line self-test

Teen-part rule jo upar ke aadhe traps resolve karti hai, plus do-phase caveat, upar se bolke sunao. Sabse negative $z$ -row entry enter karo; smallest positive-only ratio se leave karo; ruko jab poori $z$ -row $\geq 0$ ho — aur agar $(0, 0)$ feasible nahi hai (kuch $b_{i} < 0$ ), pehle Phase I run karo, "infeasible" declare karo agar artificials $0$ nahi pahunch sakte.

Connections

Parent: Simplex method (intro)
Convex Sets and Polytopes — woh convexity jo optima ko corners par force karti hai.
Gaussian Elimination — pivoting row reduction plus ek feasibility rule hai.
Duality in Linear Programming — woh certificate ki tum correctly ruke ho.
Gradient and Level Sets — kyun flat objectives boundary ki taraf slide karti hain.
Integer Programming — jab vertex guarantee fail ho jaati hai.
Optimization (Lagrange Multipliers) — equality-constraint cousin.