Foundations — Linear programming — simplex method (intro)

This page assumes you have seen none of the notation in the parent note. We build every letter, arrow, and squiggle from the ground up, in an order where each one leans only on the ones before it. Nothing is used before it is drawn.

0. The vocabulary of "many" — subscripts and $x_1,x_2$

Before any equation, we need a way to name several unknowns at once.

Picture two dials on a machine. Turning dial 1 sets $x_1$; turning dial 2 sets $x_2$. The subscript is the sticker on the dial.

Why the topic needs it. A real problem ("how many chairs $x_1$ and tables $x_2$ to build?") has many quantities to decide. Subscripts let us talk about all of them with one letter and a number.

1. Points and the plane — where a solution "lives"

Look at the figure: the horizontal line is the $x_1$-axis, the vertical line is the $x_2$-axis. The dot at $(3,2)$ means "3 steps right, 2 steps up". Every possible choice of "how many chairs, how many tables" is one dot somewhere on this map.

Why the topic needs it. A decision (make 3 chairs, 2 tables) is exactly one point. Searching for the best decision means searching this map.

In the figure that region is shaded: only the top-right quarter is allowed.

2. Straight-line fences — linear inequalities

Now we fence off the map.

In the figure the line $x_1+x_2=4$ is drawn in magenta; the kept side ($x_1+x_2\le 4$) is shaded. A point like $(1,1)$ gives $1+1=2\le 4$ ✓ (inside). A point like $(3,3)$ gives $3+3=6$, which is more than 4, so it is outside.

Why "linear"? Every constraint here is a straight line, never a curve. "Linear" literally means line-shaped. Straight fences are what make the whole method work — a curved fence would ruin the corner trick.

3. Stacking fences — the feasible region

Look at the shape in the figure: two slanted fences plus the two axes cut out a many-sided flat shape. That shape is called a convex polytope (in 2D, a polygon).

Why the topic needs it. Every valid decision is a point in this region. The whole search happens inside this shape, and — the punchline — the best answer will sit at one of its corners. See Convex Sets and Polytopes for why convex shapes have this friendly property.

4. The tilted floor — the objective function

We have a fenced field. Now we tilt the floor.

The figure shows the feasible region with dashed lines of equal height (points where $z$ is the same value). These are level sets. As you slide the dashed line in the "uphill" direction (arrow), the last point of the region it touches is a corner — here $(4,0)$ with $z=12$. See Gradient and Level Sets for the geometry of that uphill arrow.

5. The shorthand: vectors, ${\mathbf{c}}^{\top }\mathbf{x}$, and $A\mathbf{x}\le \mathbf{b}$

Writing $3x_1+2x_2$ every time is tiring. Mathematicians pack lists into vectors.

Why the topic needs it. With one letter each, the entire problem becomes "maximize ${\mathbf{c}}^{\top }\mathbf{x}$ subject to $A\mathbf{x}\le \mathbf{b}$, $\mathbf{x}\ge 0$" — the standard form the parent note uses.

6. Turning fences into equations — slack variables

The simplex machine wants equalities, not $\le$. Here is the trick.

Why the topic needs it. Equations can be solved by the tidy row-reducing machinery of Gaussian Elimination. Inequalities cannot be "solved" the same way — so we convert them and let each corner correspond to setting some variables to $0$.

Prerequisite map

Equipment checklist

Connections

• Yeh note Hinglish mein →
• Convex Sets and Polytopes — why the feasible region has flat sides and corners.
• Gaussian Elimination — the row-reduction engine behind pivoting.
• Gradient and Level Sets — the uphill arrow and equal-height lines of §4.
• Duality in Linear Programming — the partner problem, once you're fluent here.
• Optimization (Lagrange Multipliers) — the curved-constraint cousin.
• Integer Programming — what changes when variables must be whole numbers.