📂Optimization

Linear Programming Problem Basis Solution

Definition ¹

$$\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 matrices $A \in \mathbb{R}^{m \times n}$, $\mathbf{b} \in \mathbb{R}^{m \times 1}$, and $\mathbf{c} \in \mathbb{R}^{n}$ for a Linear Programming Problem represented in the equation form, a set $B \subseteq [n]$ with cardinality $m$ exists for the feasible solution $\mathbf{x} \in \mathbb{R}^{n}$, satisfying the following two conditions, then $\mathbf{x} = \left( x_{1} , \cdots , x_{n} \right)$ is referred to as the Basic Feasible Solution:

• (i): $\exists A_{B}^{-1}$
• (ii): $x_{j} = 0 \forall j \notin B$

In this case, $x_{j}$ is called the Basic Variable, and the set $B$ is called the Basis. A feasible solution that is a basic feasible solution can be described as being basic.

---

• $\mathbf{c}^{T}$ denotes [transpose].
• A [feasible solution] refers to a solution that satisfies the constraints regardless of optimization.
• $[n] = \left\{ 1, \cdots , n \right\}$ is a set of natural numbers from $1$ to $n$.
• $A_{B}$ is a square matrix formed by taking only the columns listed in set $B$ from matrix $A$.

Explanation

The definition might appear complicated due to its lengthiness, but it’s actually quite straightforward, so there’s no need to be intimidated.

A basic feasible solution is merely a discussion about feasible solutions, so $\mathbf{c} \in \mathbb{R}^{n}$ is completely disregarded.

Example

When it is stated as $$\begin{align*} A =& \begin{bmatrix} 1 & 5 & 3 & 4 & 6 \\ 0 & 1 & 3 & 5 & 6 \end{bmatrix} \\ \mathbf{b} =& \begin{bmatrix} 14 \\ 7 \end{bmatrix} \end{align*}$$, $\mathbf{x} = (0,2,0,1,0)$ is a feasible solution that satisfies two constraints expressed in the equation form $$\begin{align*} 1 x_{1} + 5 x_{2} + 3 x_{3} + 4 x_{4} + 6 x_{5} =& 14 \\ 0 x_{1} + 1 x_{2} + 3 x_{3} + 5 x_{4} + 6 x_{5} =& 7 \end{align*}$$. Here, only $x_{2}, x_{4}$ is used as components of $\mathbf{x}$ , and since $$A_{B} = \begin{bmatrix} 5 & 4 \\ 1 & 5 \end{bmatrix}$$ is nonsingular , the feasible solution $\mathbf{x}$ is a basic feasible solution.

Geometric Explanation

Consider the case of $A \in \mathbb{R}^{1 \times 3}$, i.e., a linear programming problem where there are $m=1$ constraints and the solution space dimension is $n = 3$.

Frankly speaking, basic feasible solutions refer to the vertices (excluding $\mathbf{0}$) in the above pyramid. Although we are currently only considering feasible solutions and not optimal ones, it is logically plausible to assume that the optimal solution would not randomly be located at the center of an edge. Since the objective function isn’t curving in a nonlinear way, if there exists an optimal solution, it would be among those three vertices, abstracting and generalizing the concept of the basic feasible solution.

Moreover, this solution space is essentially a [simplex], leading to the idea behind the [simplex method].

Algebraic Explanation

The existence of the inverse matrix $A_{B}^{-1}$ implies that the column vectors of the square matrix $A_{B}$ are [linearly independent], which means that it’s sufficient to consider exactly $m \le n$ necessary variables out of all $n$ variables. Recalling the geometric explanation, needing only one dimension to represent each of the three vertices fits perfectly with this concept.