Theorems in Linear Programming

Several fundamental theorems underpin the theory and practice of linear programming. These theorems provide the theoretical basis for why the graphical and simplex methods work.

Key Theorems

Fundamental Theorem of Linear Programming

If a linear programming problem has an optimal solution, then that optimal solution must occur at a corner point (vertex) of the feasible region. This theorem is crucial because it drastically reduces the search for an optimal solution. Instead of checking every point in the feasible region (which could be infinite), we only need to evaluate the objective function at a finite number of corner points.

Existence of Optimal Solutions

If the feasible region of a linear programming problem is bounded, then both a maximum and a minimum value of the objective function exist. This theorem guarantees that if the feasible region is a polygon (or polyhedron in higher dimensions), there will always be both a best and worst outcome in terms of the objective function.

Unboundedness Theorem

If the feasible region of a linear programming problem is unbounded, then the objective function may be unbounded (i.e., it can increase or decrease without limit). However, if an optimal solution exists in an unbounded region, it will still occur at a corner point. This theorem clarifies what happens when the feasible region isn't enclosed. The objective function might not have a maximum or minimum, but if it does, it's still at a corner.

Convexity of the Feasible Region

The feasible region of a linear programming problem is always a convex set. A convex set has the property that for any two points within the set, the line segment connecting those points is also entirely within the set. This property is essential for the corner point theorem to hold.

Duality Theorem

Every linear programming problem (called the "primal" problem) has a corresponding "dual" problem. The optimal solution of the primal problem provides information about the optimal solution of the dual problem, and vice-versa. If the primal problem has an optimal solution, then the dual problem also has an optimal solution, and the optimal values of the objective functions are equal. Duality is a powerful concept used in sensitivity analysis and understanding the economic interpretation of linear programs (e.g., shadow prices).

Implications for Solving LPPs

These theorems have significant implications for how we solve linear programming problems:

1. Graphical Method: In the graphical method (for two variables), we identify the feasible region and then evaluate the objective function at each corner point. The corner point that gives the best value (maximum or minimum) is the optimal solution, as guaranteed by the Fundamental Theorem.
2. Simplex Method: The simplex method is an algebraic procedure that systematically examines corner points of the feasible region until an optimal solution is found. It relies heavily on the principles established by these theorems.