2 The Geometry of Linear Programming

The feasible region of a linear programme is an intersection of half-spaces, a convex polyhedron, and a linear objective is maximised over it at a corner. This one geometric fact is the reason linear programming can be solved exactly: it reduces a search over infinitely many points to a search over finitely many vertices, and the simplex method of the next section is a systematic way of walking from vertex to vertex. This section makes the fact precise, with the algebraic description of vertices as basic feasible solutions, and uses it to solve small problems graphically.

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.