2.2 Basic feasible solutions
For computation we need an algebraic description of the vertices of \(P = \{x : Ax = b, x \geq 0\}\), where \(A\) is \(m \times n\) of rank \(m\).
Definition 2.2.1. Choose \(m\) linearly independent columns of \(A\), forming the basis matrix \(B\); the corresponding variables are basic, the others non-basic. Setting the non-basic variables to \(0\) and solving \(Bx_B = b\) gives a basic solution. If also \(x_B = B^{-1}b \geq 0\), it is a basic feasible solution (BFS). It is degenerate if some basic variable is \(0\).
Theorem 2.2.2. A point \(x \in P\) is an extreme point of \(P\) if and only if the columns \(A_j\) with \(x_j > 0\) are linearly independent; and this holds if and only if \(x\) is a basic feasible solution.
Proof. Let \(J = \{j : x_j > 0\}\). Suppose the columns \(A_j\), \(j \in J\), are dependent: \(\sum _{j \in J}d_jA_j = 0\) with \(d \neq 0\), \(d_j = 0\) for \(j \notin J\). Then \(Ad = 0\), and for small \(\varepsilon > 0\) both \(x \pm \varepsilon d\) are in \(P\), since their components outside \(J\) are \(0\) and those in \(J\) stay positive. As \(x = \frac 12(x + \varepsilon d) + \frac 12(x - \varepsilon d)\), \(x\) is not extreme.
Conversely, suppose the columns in \(J\) are independent and \(x = \lambda y + (1 - \lambda )z\) with \(y, z \in P\), \(0 < \lambda < 1\). For \(j \notin J\), \(0 = \lambda y_j + (1 - \lambda )z_j\) with \(y_j, z_j \geq 0\) forces \(y_j = z_j = 0\). Then \(A(y - x) = 0\) with \(y - x\) supported in \(J\), and independence gives \(y = x\), and likewise \(z = x\). So \(x\) is extreme.
Finally, independent columns in \(J\) can be extended to a basis of \(m\) columns (since \(A\) has rank \(m\)), and \(x\) is the basic solution for that basis, feasible since \(x \geq 0\); and a BFS has its positive components among independent basic columns. □
At a degenerate BFS, \(J\) has fewer than \(m\) columns and can be extended to a basis in several ways, so one vertex corresponds to several bases. This harmless-looking fact is the source of the difficulties with cycling in the simplex method.
Theorem 2.2.3 (Fundamental theorem of linear programming). Consider the LP: minimise \(c^{\mathsf T}x\) over \(P = \{x : Ax = b, x \geq 0\}\).
- (i)
- If \(P\) is non-empty, it has a basic feasible solution.
- (ii)
- If the LP has an optimal solution, it has an optimal basic feasible solution.
Proof. (ii) Among the optimal solutions choose one, \(x\), with the fewest positive components, and let \(J\) be its support. If the columns in \(J\) were dependent, take \(d \neq 0\) supported in \(J\) with \(Ad = 0\). Then \(x + \varepsilon d\) is feasible for all small \(|\varepsilon |\), so by optimality \(c^{\mathsf T}d = 0\), since otherwise one sign of \(\varepsilon \) would decrease the objective. Replacing \(d\) by \(-d\) if necessary, some \(d_j < 0\); increase \(\varepsilon \) from \(0\) until the first component \(x_j + \varepsilon d_j\) reaches \(0\). The new point is feasible and optimal, since \(c^{\mathsf T}d = 0\), with fewer positive components, a contradiction. So the columns in \(J\) are independent, and \(x\) is a BFS by Theorem 2.2.2. (i) is the same argument with any feasible point of minimal support, without the objective. □
There are at most \(\binom nm\) bases, so an LP could in principle be solved by computing every basic solution and comparing (Software 2.4.3). For \(n = 50\) and \(m = 25\) that is \(\binom {50}{25} = 1.26 \times 10^{14}\) systems: enumeration is hopeless, and the simplex method visits only a few of them. The full structure is given by the representation theorem of Minkowski and Weyl: a polyhedron with at least one vertex is the set of points \(\sum \lambda _iv^i + \sum \mu _jw^j\), with \(\lambda _i \geq 0\), \(\sum \lambda _i = 1\), \(\mu _j \geq 0\), where \(v^i\) are its vertices and \(w^j\) the directions of its unbounded edges (extreme rays). A bounded polyhedron is the convex hull of its vertices.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.