📂Optimization

Linear Programming: Proof of the Fundamental Theorem

Theorem

For a linear programming problem in the form of equation form, one of the following three is true:

• (1): If an optimal solution does not exist, then the problem is inherently infeasible or unbounded.
• (2): If a feasible solution exists, then a feasible basic solution also exists.
• (3): If an optimal solution exists, then an optimal basic solution also exists.

Proof

Strategy: Given that it’s named the Fundamental Theorem, it discusses the feasibility of linear programming itself. It’s a collection of various auxiliary theorems excluding an abbreviated proof. The abbreviated proof, although relies too much on intuition and not entirely mathematical reasoning, is not incorrect when approached algorithmically. Claims (1)~(3) incorporate appropriate mixes of Vanderbei and Matousek. Understanding the proof requires at least an understanding of why the simplex method is always successful, i.e., understanding the Bland’s Rule.

Abbreviated ¹

In Phase 1, it is possible to determine if the problem is infeasible or create a basic feasible solution, and in Phase 2, determine if the problem is unbounded or find the optimal basic solution using the simplex method that employs the Bland’s Rule.

(1) ²

Existence of an Optimal Solution in Equation Form: $$ \begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix} $$ For matrices $A \in \mathbb{R}^{m \times n}$, $\mathbf{b} \in \mathbb{R}^{m \times 1}$, and $\mathbf{c} \in \mathbb{R}^{n}$ regarding a linear programming problem represented in equation form, if at least one feasible solution exists and if the set of feasible solutions is bounded above by $\mathbf{c}^{T} \mathbf{x}$, then an optimal solution exists.

According to the contrapositive of the above sublemma, if an optimal solution does not exist, then the set of feasible solutions is either empty or the objective function is unbounded.

(2) ^{3 4}

Uniqueness of the Basic Feasible Solution: When a linear programming problem is represented in equation form, its basic feasible solution is uniquely determined by the basis $B$.

This sublemma primarily demonstrates the uniqueness of the basic feasible solution, but in the process of proof, it also shows its existence.

Bland’s Rule: In the simplex method of linear programming, choosing the smallest index from $\mathcal{N}$ as the index of the entering variable, and the smallest index from $\mathcal{B}$ as the index of the leaving variable is known as Bland’s Rule. According to Bland’s Rule, the simplex method does not enter a cycle.

Cycling: If the simplex method does not end, then the dictionary has entered into a cycle.

According to Bland’s Rule, if one feasible solution exists, the simplex method can find another feasible basic solution without causing cycling.

(3) ⁵

Existence of an Optimal Basic Feasible Solution: If an optimal solution exists for a linear programming problem represented in equation form, then an optimal basic feasible solution also exists.

A closer examination of the meaning behind this sublemma implies that, when an optimal solution exists, one of them must be a basic feasible solution.

■