Linear Programming and the Simplex Algorithm: Primal-Dual Theory and Polyhedral Geometry

Linear Programming (LP) is the mathematical discipline of maximizing or minimizing a linear objective function subject to a system of linear equality and inequality constraints. First developed during World War II by Leonid Kantorovich and George Dantzig, LP serves as the bedrock of global supply chain optimization, airline flight crew scheduling, energy grid dispatch, and quantitative financial arbitrage.

This guide provides comprehensive technical coverage of Standard Form Formulations, Polyhedral Geometry (Extreme Point Invariants), the Simplex Tableau Algorithm, and the Strong Duality Theorem.

1. Quick-Reference: LP Algorithm Benchmark

+-----------------------------------------------------------------------------------------------------------------------+
|                                           LINEAR PROGRAMMING SOLVERS                                                  |
+-----------------------------------------------------------------------------------------------------------------------+
| Solver Algorithm       | Worst-Case Complexity                  | Practical Performance      | Constraint Geometry    |
+------------------------+----------------------------------------+----------------------------+------------------------+
| Primal Simplex (Dantzig)| Exponential (O(2^N) Klee-Minty Cube)   | Ultra-Fast (O(M) pivots)   | Traverses Polytope Vert|
| Dual Simplex           | Exponential                            | Optimal for Branch & Bound | Infeasible to Feasible |
| Barrier (Interior Point)| Polynomial (O(N^3.5 L) Karmarkar)      | Fast for Massive Matrices  | Cuts through interior  |
+-----------------------------------------------------------------------------------------------------------------------+

2. Standard Form and Polyhedral Geometry

Every linear program can be converted into Standard Equality Form:

Minimize $c^T x$ subject to $A x = b$ and $x \ge 0$ .

where $x \in R^n$ is the vector of decision variables, $c \in R^n$ is the objective cost vector, $A \in R^{m imes n}$ is the constraint matrix, and $b \in R^m$ is the right-hand side vector ( $b \ge 0$ ).

                         Feasible Convex Polytope
                                   v_2
                                  /   \
                                 /     \
                              v_1       v_3  <-- Optimal Vertex Found by Simplex!
                                \     /
                                 \   /
                                   v_4

The Fundamental Theorem of Linear Programming

If the feasible region $P = \{x \ge 0 \mid A x = b\}$ is non-empty and bounded, an optimal solution exists.
The optimal solution occurs at an Extreme Point (Vertex / Basic Feasible Solution) of the convex polytope $P$ .

3. The Simplex Tableau and Pivot Mechanics

The Simplex algorithm navigates along the edges (1-dimensional faces) of the convex polytope from vertex to adjacent vertex, strictly improving the objective function until optimality conditions are satisfied:

Basic Variables ( $x_B$ ): Set of $m$ linearly independent columns of $A$ .
Non-Basic Variables ( $x_N$ ): The remaining $n-m$ variables set to zero.
Reduced Cost Vector:
c_N^T - c_B^T A_B^{-1} A_N
- Optimality Condition: If reduced cost is non-negative, the current basic solution is globally optimal.
- Entering Variable: Select non-basic variable $x_j$ with most negative reduced cost.
- Leaving Variable: Determine minimum ratio to maintain non-negativity.

4. Duality Theory: The Primal-Dual Relationship

Every Primal Linear Program induces a symmetric Dual Linear Program:

Primal Program:                       Dual Program:
Minimize:  c^T x                      Maximize:  b^T y
Subject to: A x >= b                  Subject to: A^T y <= c
            x >= 0                                y >= 0

The Strong Duality Theorem

If the primal program has an optimal solution $x^*$ , then the dual program also has an optimal solution $y^*$ , and their objective values are identical:

c^T x^* = b^T y^*

Dual variables $y^*$ are the Shadow Prices, quantifying the marginal increase in profit achieved by relaxing constraint $b_i$ by one unit.

References

Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.
Bertsimas, D., & Tsitsiklis, J. N. (1997). Introduction to Linear Optimization. Athena Scientific.
Karmarkar, N. (1984). A New Polynomial-Time Algorithm for Linear Programming. Combinatorica, 4(4), 373-395.