The Simplex Idea: Walking Vertex to Vertex

The simplex method is the workhorse algorithm for solving linear programs. Its central idea exploits a geometric fact: when an LP has an optimal solution, at least one optimum lies at a vertex of the feasible region.

Rather than enumerating every vertex -- a hopeless task when the feasible region has thousands of vertices -- the simplex method walks along the edges of the feasible region, hopping from one vertex to an adjacent vertex, and at each step moving to a neighbor whose objective value is better. The walk halts the instant no neighbor offers improvement.

To illustrate, consider the LP

$$\max\ z = 3x_1 + 5x_2$$

subject to $x_1 \le 4,\ \ 2x_2 \le 12,\ \ 3x_1 + 2x_2 \le 18,\ \ x_1, x_2 \ge 0.$

The feasible region is a pentagon whose vertices and objective values are

$$\begin{array}{c|c} \text{vertex} & z \\ \hline (0,0) & 0 \\ (4,0) & 12 \\ (4,3) & 27 \\ (2,6) & 36 \\ (0,6) & 30 \end{array}$$

Starting from $(0,0),$ simplex might walk

$$(0,0)\ \longrightarrow\ (0,6)\ \longrightarrow\ (2,6),$$

with objective values $0 \to 30 \to 36.$ From $(2,6),$ the adjacent vertices are $(0,6)$ (where $z=30$) and $(4,3)$ (where $z=27$); neither beats $36,$ so the walk stops. The optimum is $z^* = 36$ at $(x_1,x_2)=(2,6).$