Flashcards
Answer
Polyhedra and Basic Solutions
Polyhedra and basic solutions connect the geometry of linear programming with the algebra used by simplex.
A feasible region has vertices. In standard form, those vertices are represented by basic feasible solutions.
Map of the Section
- Polyhedra: feasible regions described by linear constraints.
- Active Constraints: constraints that are tight at a point.
- Vertices and Extreme Points: the corner points where LP optima live.
- Basic Solutions and Basic Feasible Solutions: algebraic versions of vertices.
- Basis Matrices: the selected columns of $A$ that define a basic solution.
- Degenerate Basic Feasible Solutions: BFSs with zero basic variables.
- Adjacent Basic Solutions: neighboring BFSs connected by a simplex pivot.
Standard-Form Feasible Set
For
\[\min c^Tx\]subject to
\[Ax=b, \qquad x\ge 0,\]the feasible set is
\[P=\{x\in\mathbb{R}^n\mid Ax=b,\ x\ge 0\}.\]This set is a polyhedron. The simplex method searches this set through its basic feasible solutions.
Geometry to Algebra
| Geometry | Algebra |
|---|---|
| feasible region | polyhedron $P$ |
| corner point | vertex / extreme point |
| active boundary | active constraint |
| vertex of $P$ | basic feasible solution |
| edge between vertices | adjacent basic feasible solutions |
| move to next corner | simplex pivot |
Basis Construction
Choose $m$ linearly independent columns of $A\in\mathbb{R}^{m\times n}$:
\[B=[A_{B(1)}\ A_{B(2)}\ \cdots\ A_{B(m)}].\]Set nonbasic variables to zero:
\[x_N=0.\]Solve for basic variables:
\[x_B=B^{-1}b.\]If $x_B\ge 0$, the result is a basic feasible solution.
Main Theorem Intuition
If a linear program has a finite optimum and the feasible polyhedron has vertices, at least one optimum can be found at a vertex.
That is why simplex can solve LPs by moving from one basic feasible solution to another instead of checking infinitely many feasible points.
Checklist
You should be able to:
- describe a polyhedron as an intersection of linear constraints
- identify active constraints
- construct a basis matrix
- compute a basic solution
- test feasibility of a basic solution
- explain why simplex moves between adjacent BFSs
See Also
- Standard Form
- Canonical Form
- Simplex Method
-
Reduced Costs
Added exam practice
- Verifying a Given Vector as BFS
- BFS After Adding Slack and Surplus Variables
- All Basic Feasible Solutions in 2D
- BFS and Reduced Cost Drill Set
Exam checkpoint
For BFS questions, convert to standard form before checking the point. A candidate in original variables must be lifted with slack and surplus variables before testing basis columns.