Visual walkthrough — Linear programming — simplex method (intro)

---

Step 1 — Draw the playground (the feasible region)

WHAT. We are given the problem $z=\underset{\text{profit per }{x}_1}{\underbrace{3}}{x}_1+\underset{\text{profit per }{x}_2}{\underbrace{2}}{x}_2$ which we want to make as big as possible, and two rules the pair $(x_1,x_2)$ must obey: $\underset{\text{rule A}}{\underbrace{x_1+x_2\le 4}},\underset{\text{rule B}}{\underbrace{x_1+3x_2\le 6}},\underset{\text{stay in first quadrant}}{\underbrace{x_1\ge 0,x_2\ge 0}}.$

Here $x_1$ and $x_2$ are just two dials you can turn — call them decision variables. Every choice of the two dials is a point on a flat map. Each "$\le$" rule says "stay on one side of a straight line". Overlap all the allowed sides and you get a shape.

WHY start here. Before any algebra, we need to see the space of legal choices. A "$\le$" inequality carves the plane into two halves — a half-plane — and keeps one half. Four rules = four half-planes. Their common overlap is the feasible region: every point that breaks no rule.

PICTURE. The shaded region below is that overlap — a four-cornered fenced field. Its corners are marked. Those corners are the only places the maximum can live (we prove why in Step 2).

---

Step 2 — Why the prize sits at a corner

WHAT. The objective $z=3x_1+2x_2$ takes a value at each point. Points sharing the same value of $z$ lie on a straight line: set $3x_1+2x_2=c$ for a fixed number $c$ and you get one line. Change $c$ and the line slides — parallel to itself. These are the level lines of $z$.

WHY this tool. We want the largest $z$, so we ask: how far can the sliding line move in the "more profit" direction and still touch the field? The direction of steepest increase is the gradient $\nabla z=(3,2)$ — an arrow pointing where $z$ climbs fastest. Because $z$ is linear, every level line is straight and they are all parallel. Slide the line up the gradient until it is about to leave the field: the last point of contact is a corner (or, in a tie, a whole edge — but an edge always includes corners). So we never need interior points.

PICTURE. Watch the dashed level lines march up the field in the $(3,2)$ direction. The last one to touch grazes the corner $(4,0)$ — the winner.

$\underset{\text{climb direction}}{\underbrace{\nabla z}}=\left(\underset{=3}{\underbrace{\frac{\partial z}{\partial x_1}}},\underset{=2}{\underbrace{\frac{\partial z}{\partial x_2}}}\right)=(3,2).$

Here $\frac{\partial z}{\partial x_1}$ just means "how much $z$ rises per unit of $x_1$" — it's $3$ because the term $3x_1$ adds $3$ each time $x_1$ goes up by one. Same idea gives $2$ for $x_2$.

---

Step 3 — Turn "less-than" rules into clean equations (slack)

WHAT. An inequality like $x_1+x_2\le 4$ has spare room. If you're using only $x_1+x_2=3$ of your budget of $4$, there's $1$ left over. Name that leftover $s_1\ge 0$: $\underset{\text{used}}{\underbrace{x_1+x_2}}+\underset{\text{leftover}}{\underbrace{s_1}}=\underset{\text{budget}}{\underbrace{4}},\underset{\text{used}}{\underbrace{x_1+3x_2}}+\underset{\text{leftover}}{\underbrace{s_2}}=\underset{\text{budget}}{\underbrace{6}}.$

The new variables $s_1,s_2$ are slack variables: each measures how much of that rule is unused.

WHY do this. Computers and clean linear algebra love equations, not inequalities. With slacks, every "$\le$" becomes "$=$", and now row-reduction can solve things. Bonus meaning: $s_1=0$ means rule A is tight — you're standing right on that fence line.

PICTURE. Each fence has a coloured "slack bar" showing the unused amount. On the boundary the bar shrinks to zero.

---

Step 4 — Write the starting corner as a table (the tableau)

WHAT. Stack the two slack equations and the objective (rearranged as $z-3x_1-2x_2=0$) into a grid. Each row is one equation; each column is one variable's coefficients.

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

WHY here, why now. We must start at some legal corner. Setting $x_1=x_2=0$ (both dials off) leaves $s_1=4,s_2=6$ — both positive, so it's legal. That's the corner $(0,0)$ with $z=0$. This is the safe launch pad because the budgets $\mathbf{b}=(4,6)$ are non-negative.

PICTURE. The tableau is the corner $(0,0)$ drawn as a table. The bottom row secretly stores $z=3x_1+2x_2$ (move the negatives across).

Reading the bottom row term-by-term: $\underset{\text{profit}}{\underbrace{z}}-\underset{\text{gain per }{x}_1}{\underbrace{3}}{x}_1-\underset{\text{gain per }{x}_2}{\underbrace{2}}{x}_2=0.$ A negative number under a column means "turning that dial up raises $z$" — a chance to improve.

---

Step 5 — Choose who enters (steepest improvement)

WHAT. Look only at the $z$-row: $-3$ under $x_1$, $-2$ under $x_2$. The most negative is $-3$. So $x_1$ will become basic — it enters.

WHY. Each negative is the rate of profit gained per unit of that dial. $-3$ beats $-2$: raising $x_1$ pays $3$ per unit, the steepest climb available. Picking the most negative is the greedy "go up the steepest fence-edge" move.

PICTURE. From corner $(0,0)$, two edges leave — one along the $x_1$-axis, one along $x_2$. The $x_1$-edge is steeper in profit, so we step onto it.

---

Step 6 — Choose who leaves (the ratio test)

WHAT. We slide $x_1$ up along its edge. But a fence will stop us. For each row with a positive entry in the $x_1$ column, compute $\text{RHS}÷(\text{that entry})$: $\text{row }{s}_1:\frac{4}{1}=4,\text{row }{s}_2:\frac{6}{1}=6.$ The smallest ratio, $4$, wins: row $s_1$ is the binding fence, so $s_1$ leaves the basis.

WHY only positive entries, why the smallest. As $x_1$ grows, each slack changes by $-(\text{column entry})\times x_1$. If the entry is positive, that slack shrinks and will hit $0$ at $x_1=\text{RHS}/\text{entry}$ — that's where you slam into the fence. The first fence you meet (smallest ratio) is the limit; going past it drives a slack negative = illegal. A negative or zero entry means that slack never runs out in this direction, so it never stops you — skip it.

PICTURE. Ride the red arrow up the $x_1$-axis. Fence A (from rule A) blocks you at $x_1=4$; fence B would only block at $x_1=6$. You stop at the nearer one, $x_1=4$.

---

Step 7 — Pivot: make $x_1$ basic (row-reduce)

WHAT. The pivot is the entry at (row $s_1$, column $x_1$) $=1$. We make its whole column into a unit column $(1,0,0)$ using row operations:

• Row $s_1$: divide by pivot ($1$) → unchanged.
• Row $s_2$: ${\text{Row}}_2-1\cdot {\text{Row}}_1$ (kill the $1$ above… below it).
• Row $z$: ${\text{Row}}_z+3\cdot {\text{Row}}_1$ (kill the $-3$).

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

WHY. After this, reading the table off directly gives $x_1=4,s_2=2,z=12$ — we've moved to the corner $(4,0)$. Pivoting is exactly "re-solve the equations so the new corner's values sit in the RHS column".

PICTURE. The hop: from $(0,0)$ up the edge to $(4,0)$, profit jumping $0\to 12$.

Reading the new $z$-row: $z+0\cdot x_1+1\cdot x_2+3\cdot s_1+0\cdot s_2=12$, i.e. $z=12-\underset{\ge 0}{\underbrace{1}}{x}_2-\underset{\ge 0}{\underbrace{3}}{s}_1.$ Both coefficients are now non-negative, so turning any off-dial up can only lower $z$.

---

Step 8 — Know when to stop (optimality)

WHAT. The $z$-row is now $0,1,3,0$ — no negative entries left. Stop. The corner $(4,0)$ with $z=12$ is optimal.

WHY. A negative in the $z$-row was our "improvement available" flag. None left = no dial can be raised to gain profit = we're at the top of the ramp. This matches the picture from Step 2: the last level line grazed exactly $(4,0)$.

PICTURE. Corner scoreboard — every vertex's $z$ value shown; $(4,0)$ wears the crown.

Cross-check against every corner (no case skipped):

Corner	how it arises	$z=3x_1+2x_2$
$(0,0)$	both dials off	$0$
$(0,2)$	on fence B, $x_1=0$	$4$
$(3,1)$	fences A & B cross	$11$
$(4,0)$	on fence A, $x_2=0$	$12$ ✓

The winner $12$ appears at $(4,0)$ — exactly where simplex stopped.

---

The one-picture summary

Everything above in a single frame: the field, the sliding profit lines, the corner-hop $(0,0)\to (4,0)$ that simplex takes, and the crowned optimum.

Recall Feynman retelling — the whole walk in plain words

You're in a many-cornered fenced field (the feasible region). The ground is a flat ramp tilting toward "more profit" (the linear objective). On a flat ramp, the highest reachable spot is always a corner, so you only ever need to visit corners. To turn the fuzzy "$\le$" fences into exact lines you can compute with, you give each fence a "leftover" measure — a slack — that hits zero when you touch that fence. You start at the easy corner where all dials are off. You read the table: any negative number in the bottom row means "turning this dial up earns profit", so you pick the biggest earner (enter, most negative). You walk up that edge until the first fence stops you — found by the smallest RHS-over-positive-entry ratio (leave, smallest ratio). You re-solve the equations (pivot) so the new corner's numbers slide into place. Repeat. The instant the bottom row has no negatives left, no dial can earn more — you're standing on the highest corner. Done.

---

Connections

• Convex Sets and Polytopes — the field is a convex polytope; that's why optima live at corners.
• Gradient and Level Sets — Step 2's sliding lines and the $(3,2)$ climb arrow.
• Gaussian Elimination — the pivot in Step 7 is exactly guided row reduction.
• Duality in Linear Programming — the same optimum $12$ read from the partner problem.
• Integer Programming — what changes when the dials must be whole numbers.
• Optimization (Lagrange Multipliers) — the smooth-constraint cousin of this corner-walk.