📂Optimization

Proof of the Uniqueness of Base Solubility

Theorem ¹

$$ \begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix} $$

Given a matrix $A \in \mathbb{R}^{m \times n}$ and $\mathbf{b} \in \mathbb{R}^{m \times 1}$ and $\mathbf{c} \in \mathbb{R}^{n}$, if the linear programming problem is expressed in the form of equations as above, the basic feasible solution is uniquely determined by the basis $B$.

---

• $\mathbf{c}^{T}$ means the transpose.
• A feasible solution refers to a solution that satisfies the constraints regardless of optimization.
• $[n] = \left\{ 1, \cdots , n \right\}$ is the set of natural numbers from $1$ to $n$.
• $A_{B}$ is a square matrix taken only from the columns listed in the set $B$ of the matrix $A$.
• A basic feasible solution $\mathbf{x} \in \mathbb{R}^{n}$ exists if there is a set $B \subseteq [n]$ with a cardinality of $m$ such that $\exists A_{B}^{-1}$ and $x_{j} = 0 \forall j \notin B$, with $\mathbf{x} = \left( x_{1} , \cdots , x_{n} \right)$ being called the basic feasible solution. This set $B$ is called the basis.

Proof

Assuming that the feasible solution $\mathbf{x}$ satisfied $A \mathbf{x} = \mathbf{b}$ by definition, by defining the set of non-basis indices $N := [n] \setminus B$, $A \mathbf{x}$ can be expressed as follows: $$ A \mathbf{x} = A_{B} \mathbf{x}_{B} + A_{N} \mathbf{x}_{N} $$ According to condition (ii) of the basis $B$, all components of $\mathbf{x}_{N}$ are $0$, and thus $$ \mathbf{b} = A \mathbf{x} = A_{B} \mathbf{x}_{B} $$ The vector $\mathbf{x}_{B}$ satisfies $A_{B} \mathbf{x}_{B} = \mathbf{b}$, and since condition (i) of the basis $B$ guarantees the existence of $A_{B}^{-1}$, the equation $A_{B} \mathbf{x}_{B} = \mathbf{b}$ has a unique solution.

• If all components of this unique solution are greater than or equal to $0$, then there is exactly one basic feasible solution according to $B$.
• Otherwise, the solution does not satisfy $\mathbf{x} \ge 0$.

In conclusion, the basic feasible solution according to the given linear programming problem and basis $B$ either does not exist or has a unique solution.

Explanation

The summary confirmed that a basis determines only one basic feasible solution, but one basic feasible solution can be obtained from several different basis.

See Also

Fundamental Theorem of Linear Programming

This theorem is used in the proof of the fundamental theorem of linear programming.