Linear programming — simplex method (intro): Foundations

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

Yeh page assume karta hai ke aapne parent note ki koi bhi notation pehle nahi dekhi. Hum har letter, arrow, aur symbol ko scratch se banate hain, ek aisi sequence mein jahan har cheez sirf unhi cheezon par depend karti hai jo pehle aa chuki hain. Kuch bhi use hone se pehle draw kiya jaata hai.

0. "Bahut saari cheezon" ki vocabulary — subscripts aur $x_{1}, x_{2}$

Kisi bhi equation se pehle, hume kai unknowns ko ek saath naam dene ka tarika chahiye.

Socho ek machine par do dials hain. Dial 1 ghumaane se $x_{1}$ set hota hai; dial 2 ghumaane se $x_{2}$ set hota hai. Subscript dial par laga hua sticker hai.

Topic ko yeh kyun chahiye. Ek real problem ("kitni kursiyan $x_{1}$ aur kitne tables $x_{2}$ banaayein?") mein decide karne ke liye kai quantities hoti hain. Subscripts hume un sab ke baare mein ek letter aur ek number se baat karne dete hain.

1. Points aur plane — ek solution "kahaan rehta hai"

Figure — Linear programming — simplex method (intro)

Figure dekho: horizontal line $x_{1}$ -axis hai, vertical line $x_{2}$ -axis hai. $(3, 2)$ par dot ka matlab hai "3 steps daayein, 2 steps upar". "Kitni kursiyan, kitne tables" ka har possible choice is map par ek dot hai.

Topic ko yeh kyun chahiye. Ek decision (3 kursiyan banao, 2 tables) exactly ek point hai. Sabse achha decision dhundna matlab is map par search karna hai.

Figure mein wo region shaded hai: sirf top-right quarter allowed hai.

2. Seedhe fences — linear inequalities

Ab hum map ko fence karte hain.

Figure mein line $x_{1} + x_{2} = 4$ magenta mein draw ki gayi hai; rakhi gayi side ( $x_{1} + x_{2} \leq 4$ ) shaded hai. $(1, 1)$ jaisa point $1 + 1 = 2 \leq 4$ ✓ (andar) deta hai. $(3, 3)$ jaisa point $3 + 3 = 6$ deta hai, jo 4 se zyaada hai, isliye yeh baahr hai.

"Linear" kyun? Har constraint yahan ek seedhi line hai, kabhi curve nahi. "Linear" ka literally matlab hai line jaisi shape. Seedhe fences hi hain jo poori method ko kaam karne dete hain — ek curved fence corner trick ko kharaab kar deta.

3. Fences stack karna — feasible region

Figure mein shape dekho: do tirche fences plus do axes ek bahut-sided flat shape kaat dete hain. Us shape ko convex polytope kehte hain (2D mein, ek polygon).

Topic ko yeh kyun chahiye. Har valid decision is region mein ek point hai. Poori search is shape ke andar hoti hai, aur — punch line — sabse achha jawab iske corners mein se ek par baithega. Dekho Convex Sets and Polytopes ki convex shapes ki yeh friendly property kyun hoti hai.

4. Tirchi floor — objective function

Humare paas ek fenced field hai. Ab hum floor tilate hain.

Figure feasible region ko dashed lines of equal height ke saath dikhata hai (points jahan $z$ same value hai). Yeh level sets hain. Jab tum dashed line ko "uphill" direction mein slide karte ho (arrow), region ka aakhri point jise wo touch karti hai ek corner hai — yahan $(4, 0)$ with $z = 12$ . Dekho Gradient and Level Sets us uphill arrow ki geometry ke liye.

5. Shorthand: vectors, $c^{⊤} x$ , aur $A x \leq b$

$3 x_{1} + 2 x_{2}$ baar baar likhna thakaa deta hai. Mathematicians lists ko vectors mein pack karte hain.

Topic ko yeh kyun chahiye. Ek ek letter ke saath, poora problem ban jaata hai "maximize $c^{⊤} x$ subject to $A x \leq b$ , $x \geq 0$ " — standard form jo parent note use karta hai.

6. Fences ko equations mein badalna — slack variables

Simplex machine equalities chahti hai, $\leq$ nahi. Yeh raha trick.

Topic ko yeh kyun chahiye. Equations ko Gaussian Elimination ki tidy row-reducing machinery se solve kiya ja sakta hai. Inequalities ko same tarah "solve" nahi kiya ja sakta — isliye hum unhe convert karte hain aur har corner ko kuch variables ke $0$ set hone se correspond karne dete hain.

Prerequisite map

Equipment checklist

Main keh sakta/sakti hoon

x_{1}

aur

x_{2}

ka kya matlab hai aur subscript power kyun nahi hai

Yeh pehle aur doosre decision variables ke labels hain;

x_{2}

hai "variable two", "

x

squared" nahi.

Main ek point

(3, 2)

plot kar sakta/sakti hoon aur donon axes naam le sakta/sakti hoon

x_{1}

-axis par 3 daayein,

x_{2}

-axis par 2 upar.

Main explain kar sakta/sakti hoon

x_{1} \geq 0, x_{2} \geq 0

map ke saath kya karta hai

Yeh hume first quadrant (top-right quarter) tak restrict karta hai.

Main

x_{1} + x_{2} \leq 4

ko ek shaded half-plane mein badal sakta/sakti hoon

Line

x_{1} + x_{2} = 4

draw karo; wo side rakho jahan sum 4 ya kam ho.

Main feasible region describe kar sakta/sakti hoon

Saare half-planes aur first quadrant ka overlap — ek convex polytope.

Main keh sakta/sakti hoon "convex" aur "vertex" ka kya matlab hai

Convex = koi dent nahi (koi bhi chord andar rehti hai); vertex ek corner hai jahan fences cross karti hain.

Main

c^{⊤} x

padh sakta/sakti hoon aur use expand kar sakta/sakti hoon

Yeh dot product

3 x_{1} + 2 x_{2}

hai, objective

z

Main

A x \leq b

ko inequalities mein unpack kar sakta/sakti hoon

A

ki har row

b

ki matching entry ke saath ek fence deti hai.

Main explain kar sakta/sakti hoon hum slack variables kyun add karte hain

\leq

=

mein badalne ke liye taaki row reduction se solve kar sakein; slack unused resource naapti hai.

Main core idea ek sentence mein keh sakta/sakti hoon

Ek straight-edged convex region par ek linear (ramp) objective apna maximum ek corner par achieve karta hai.

Connections

Yeh note Hinglish mein →
Convex Sets and Polytopes — feasible region ke flat sides aur corners kyun hote hain.
Gaussian Elimination — pivoting ke peeche row-reduction engine.
Gradient and Level Sets — uphill arrow aur §4 ki equal-height lines.
Duality in Linear Programming — partner problem, jab tum yahan fluent ho jaao.
Optimization (Lagrange Multipliers) — curved-constraint cousin.
Integer Programming — kya badalta hai jab variables whole numbers hone chahiye.