Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 38 ยท Simplex Method

The Geometry of Linear Programs

Understand why LP optima sit at vertices: convex sets, polyhedra, extreme points, basic feasible solutions, adjacency and the fundamental theorem, with Python checks.

The graphical method shows that the optimum of a two-variable LP lies at a corner. In higher dimensions we cannot draw, but the same story holds, and it is exactly what makes the simplex method possible. This lesson states the geometry precisely and verifies it numerically, so the simplex algorithm in the next lessons looks like a natural consequence.

Convex sets and polyhedra

A set S is convex if for any two points p, q in S, the whole segment ฮปp + (1-ฮป)q (with 0 <= ฮป <= 1) is also in S. A half-space {x : a . x <= b} is convex, and an intersection of convex sets is convex. So the feasible region {x : Ax <= b, x >= 0} is a convex polyhedron. If it is bounded, it is called a polytope.

A point of a convex set is an extreme point (vertex) if it cannot be written as a strict combination ฮปp + (1-ฮป)q of two other points of the set. Geometrically: a corner. Three facts hold for a polyhedron in standard form {x : Ax = b, x >= 0}:

  1. Extreme points are exactly the basic feasible solutions of standard form.
  2. There are finitely many of them (at most C(n, m)).
  3. A polytope is the convex hull of its extreme points: every feasible point is a mix of vertices.
Python Every feasible point is a mix of vertices

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The gap is never negative: a weighted average of numbers cannot exceed the largest of them, and the objective of a mixture is the same weighted average of the vertex objectives. That one-line argument is the entire proof of the next theorem.

The fundamental theorem of linear programming

If an LP in standard form has an optimal solution, then it has an optimal solution at a basic feasible solution (a vertex).

The proof sketch: if the optimum is a mixture of vertices, its objective is the average of the vertex objectives, so at least one vertex is at least as good. Therefore it is enough to search the finite set of vertices. If the region contains no line (true for non-negative variables), a bounded-below LP always attains its optimum at a vertex.

This also explains ties: if two adjacent vertices tie, every point on the edge between them ties.

Adjacent vertices

Two vertices are adjacent if they share an edge. In terms of bases: two basic feasible solutions are adjacent when their bases differ in exactly one column (one variable leaves the basis, one enters). The simplex method moves along edges, from a vertex to an adjacent one with a better objective, and stops when no neighbour is better.

Python Neighbouring bases of the bakery LP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each vertex of this 2D polygon has two neighbours, as expected for a polygon (a vertex of a polygon touches two edges). Starting from the origin {s1,s2,s3} the simplex path might be origin, then (40, 0), then (40, 20), then (20, 60): every step is along an edge and the profit increases.

Optimality from the vertex's point of view

At a vertex you can ask: is there an edge leaving this vertex along which the objective improves? If no edge improves, the vertex is globally optimal, because the region is convex and the objective is linear (there are no local optima that are not global). This is a distinctive property of LP, and it is why a greedy "move to a better neighbour" algorithm is guaranteed to find the true optimum.

flowchart LR
  O["(0,0) profit 0"] --> A["(40,0) profit 1600"]
  A --> B["(40,20) profit 2200"]
  B --> C["(20,60) profit 2600 optimal"]
  O --> D["(0,80) profit 2400"]
  D --> C

Two possible simplex paths on the bakery problem. Either way profit increases at every step.

How many vertices are there?

For m equations and n variables there can be up to C(n, m) bases. For n = 40, m = 20 that is 137 billion. The Klee-Minty cubes show that some pivot rules can in theory visit exponentially many vertices, yet in practice simplex typically needs only about 2m to 3m pivots. (Interior-point methods, mentioned later in the track, have polynomial guarantees.) The next lessons show how simplex chooses a good path without enumerating all vertices.

Python Vertex counts explode

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Rays and unboundedness

If the polyhedron extends to infinity there are also extreme rays, directions d with Ad = 0, d >= 0 along which you can travel forever without leaving the region. The LP is unbounded exactly when an extreme ray improves the objective (c . d < 0 for minimization). Simplex detects this when the entering variable has no positive entry in its column, which is the subject of the unbounded and infeasible lesson.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which statement about the LP feasible region is true?

    It is an intersection of half-spaces, hence a convex polyhedron.
  2. 2. An extreme point is

    Corners cannot be written as a strict combination of two distinct feasible points.
  3. 3. Two basic feasible solutions are adjacent when their bases

    One variable leaves and one enters, moving along a single edge.
  4. 4. Why can a greedy move-to-a-better-neighbour method find the global optimum in LP?

    For a convex region with a linear objective, a vertex with no improving edge is globally optimal.

Summary

  • The feasible region is a convex polyhedron; its corners are the basic feasible solutions.
  • Fundamental theorem: if an LP has an optimum, some vertex is optimal.
  • Adjacent vertices differ by one basic variable; simplex walks along edges.
  • No local optima other than global ones, so greedy pivoting is correct.
  • The number of vertices is huge, so simplex avoids enumerating them.

Next: The Simplex Method by Hand: Tableaux