Basic feasible solutions

Remark

Here, we consider a linear optimization problem in standard form, where and we assume .

As noted about linear optimization problems, their feasible regions are simply intersections of half-planes, i.e. convex polygons. Note that since we know that moving in the opposite direction of decreases the cost. This means that the optimal solution is the point of in the feasible region that furthest in the -direction. It is thus obvious that the optimal solution cannot be strictly inside the feasible region. More importantly, whenever we consider a non-corner surface point, we see that at least one of the corners connected to the surface must have the same or lower cost; moving in the opposite direction reverses the cost change, so some direction must be in a nonnegative cost direction. It follows that an optimal solution must be a corner.

When considering the linear optimization in standard form, the feasible region is an intersection of a solution to a linear equation, i.e. an affine subspaces, with the region given by . Corners can thus only happen when sufficiently many coordinates are zero, forcing the rest of the coordinates to a unique solution. The idea is to consider sets of indices representing the only nonzero coordinates.

Definition: Basic indices, basic variables

Let be a selection of distinct coordinates of , and let be the remaining distinct coordinates.

and is a basic (resp. non-basic) index tuple consisting of basic (resp. non-basic) indices.

and is the basic (resp. non-basic) variable vector consisting of basic (resp. non-basic) variables, corresponding to .

and is the basic (resp. non-basic) matrix, corresponding to .

Definition: Basic solution, basic feasible solution

Let be a basic index tuple.

A solution to is a basic solution whenever .

A solution is a basic feasible solution whenever it is basic and feasible.

A solution is called degenerate whenever some coordinate of is zero, otherwise non-degenerate.

We can now formalize and prove our initial intuition.

Theorem: The fundamental theorem of linear programming
  1. If there exists a feasible solution, then there exists a basic feasible solution.
  2. If there exists an optimal solution, then there exists an optimal basic feasible solution.

Proof:

  1. Let be a feasible solution. Let be the distinct indices of the nonzero coordinates of . If we are done. Suppose . Then cannot be injective. Take some nonzero and WLOG, assume some coordinate of is negative (otherwise, we could negate to get such a vector). Then there is some smallest such that has some zero coordinate. Since we choose the smallest such , the rest of the coordinates of remain nonnegative. Thus is another feasible solution with one more zero coordinate than . Repeat until .
  2. Starting from an optimal solution , the exact same algorithm works. Notice that if , then , but then there exists a with a feasible solution and meaning contradicting the optimality of . Thus we must always have and so at no step of the algorithm does the cost change.