Linear programming — simplex method (intro)

WHAT is a linear program?

WHY this form? Every "≥" constraint becomes "≤" by multiplying by $-1$ ; equalities split into two inequalities; minimization is $-1\times$ maximization. So this one form is fully general.

HOW we make inequalities into equations: slack variables

WHY do this? Equations are easy to solve with linear algebra (Gaussian elimination). Corners of the polytope correspond to setting some variables to $0$ and solving the rest — slacks give us a clean bookkeeping system to do exactly that.

Deriving the simplex tableau from scratch

Take the example below to build everything by hand.

Step 1 — Add slacks. Why? To get equations. $x_1+x_2+s_1 = 4,\qquad x_1+3x_2+s_2 = 6,\qquad z-3x_1-2x_2 = 0.$

Step 2 — Initial tableau. Why? The basic variables are $s_1,s_2$ (set $x_1=x_2=0$ ); this gives the corner $(0,0)$ with $z=0$ — a valid starting vertex because $\mathbf b\ge 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 — Choose entering variable. Why? The bottom row reads $z = 3x_1+2x_2$ . A negative entry $-3$ under $x_1$ means increasing $x_1$ raises $z$ . Pick the most negative: $x_1$ enters.

Step 4 — Ratio test (leaving variable). Why? We push $x_1$ up, but a constraint will bind first. Compute $\text{RHS}/(\text{positive column entry})$ : row 1 $\to 4/1=4$ , row 2 $\to 6/1=6$ . The smallest ratio $4$ wins (row 1) — going further makes $s_1<0$ (infeasible). So $s_1$ leaves.

Step 5 — Pivot on the $x_1$ -row1 entry (=1). Why? Make that column a unit vector so $x_1$ becomes basic. Row1 stays; 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

Now corner is $(4,0)$ , $z=12$ . Bottom row has no negative entries → optimal!

Figure — Linear programming — simplex method (intro)

Verify graphically: Vertices are $(0,0)z{=}0$ , $(0,2)z{=}4$ , $(4,0)z{=}12$ , intersection of the two lines $(3,1)z{=}11$ . Maximum is indeed $12$ at $(4,0)$ .

WHY the simplex method works (Steel-man the logic)

Maximum is at a vertex — Because $z$ is linear, its level sets are parallel hyperplanes; sliding in the improving direction, you stop at the polytope's boundary, ending at a corner.
Each pivot is a corner-to-corner move along an edge that increases $z$ .
Finitely many corners ⇒ the process terminates (ignoring rare degeneracy).

A second worked example (minimization via negation)

Worked example Minimize

$z = -x_1 - 2x_2$ s.t. $x_1+x_2\le 4,\ x_2\le 3,\ x\ge0$ . Why negate? Min $z$ = $-$ Max $(-z)$ , so maximize $w=x_1+2x_2$ . Slacks: $x_1+x_2+s_1=4$ , $x_2+s_2=3$ . $w$ -row: $-1,-2$ . Most negative $\Rightarrow x_2$ enters. Ratios: $4/1=4$ , $3/1=3$ → $s_2$ leaves. Pivot → corner $(0,3)$ , $w=6$ . New $w$ -row still has $-1$ under $x_1$ → continue. $x_1$ enters; ratio test → reach $(1,3)$ , $w = 1+6 = 7$ , all coeffs $\ge0$ → optimal. So min $z = -7$ at $(1,3)$ . Why this step (final): $w=7$ corresponds to $z=-w=-7$ .

Flashcards

What shape is the feasible region of an LP?

A convex polytope (intersection of half-spaces).

Where does a linear objective attain its optimum?

At a vertex (corner) of the feasible region.

What is a slack variable?

A non-negative variable added to turn a

\le

constraint into an equality, measuring unused resource.

In a max-problem tableau, which variable enters?

The non-basic variable with the most negative coefficient in the

z

-row.

How do you choose the leaving variable?

Minimum-ratio test: smallest RHS ÷ (positive entry) in the pivot column.

When do you stop the simplex method (maximization)?

When all objective-row coefficients are

\ge 0

Why only use positive entries in the ratio test?

Negative/zero entries don't bound how far the entering variable can grow without going infeasible.

How is a minimization LP handled?

Maximize the negative of the objective; min

z=-\max(-z)

What does a basic feasible solution correspond to geometrically?

A vertex of the polytope (set

n

non-basic vars to 0, solve for

m

basic ones).

How do you convert a

\ge

constraint to standard form?

Multiply by

-1

to flip it to

\le

(then add a slack).

Recall Feynman: explain to a 12-year-old

Imagine a fenced playground shaped like a many-cornered field. You want to stand where the ground is highest, but the ground tilts flatly like a ramp. The highest spot on a flat ramp inside a fenced field is always at a corner of the fence. So you start at one corner and keep walking to the next corner only if it's higher. When no neighbour corner is higher, you're standing on the top — done! That walking-along-the-fence trick is the simplex method.

Connections

Convex Sets and Polytopes — why optima sit at vertices.
Gaussian Elimination — pivoting is row reduction with a feasibility rule.
Duality in Linear Programming — every LP has a partner; optimal values match.
Gradient and Level Sets — geometry of why linear objectives slide to boundaries.
Integer Programming — what changes when variables must be whole numbers.
Optimization (Lagrange Multipliers) — the smooth-constraint cousin.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, Linear Programming ka idea simple hai: tumhe ek profit function (jaise $z=3x_1+2x_2$ ) ko maximize karna hai, lekin kuch constraints (inequalities) ke andar rehkar. Ye saari inequalities milke ek polygon/polytope banati hain — yahi tumhara "feasible region" hai. Sabse important baat: linear objective ka maximum hamesha is region ke kisi corner (vertex) pe milta hai, beech mein kabhi nahi. Isliye humein infinite points check karne ki zaroorat nahi — sirf corners dekhne hain.

Simplex method bas ek smart corner-hopping technique hai. Pehle har $\le$ constraint mein ek slack variable $s$ add karte hain taaki inequality ek clean equation ban jaye ( $s$ ka matlab "bachi hui jagah / unused resource"). Phir hum origin $(0,0)$ se start karte hain (sab slacks basic). Ab entering variable chunte hain — jiska $z$ -row mein coefficient sabse negative ho (kyunki use badhane se profit sabse zyada badhega). Phir ratio test se decide karte hain konsa variable leave karega — sabse chhota RHS÷(positive entry). Pivot karke naye corner pe pahunch jaate hain.

Repeat karte raho jab tak $z$ -row mein koi negative number na bache — uss waqt tum optimal corner pe ho, game over! Common galti: ratio test mein negative ya zero entries use kar dena (sirf positive lo), ya minimization mein bhi most-negative dhoondte rehna — minimization ke liye objective ko $-1$ se multiply karke maximize karo. Exam aur real-life dono mein (cost minimize, profit maximize, resource allocation) ye method gold hai.

Linear programming — simplex method (intro)

WHAT is a linear program?

HOW we make inequalities into equations: slack variables

Deriving the simplex tableau from scratch

WHY the simplex method works (Steel-man the logic)

A second worked example (minimization via negation)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Advanced Topics (Elite Level)

Connections