Basic Solutions

Introduction

A basic solution (feasible or not) to a standard LP is obtained by fixing \(n-m\) variables to zero and solving the remaining \(m\) equations for the remaining \(m\) variables. Varibles fixed to zero are called nonbasic variables and the remaining variables are called basic variables.

Let’s take Top Brass Tropy example from the textbook [reference 1] to illustrate the concept of basic solutions. The LP model is given below: \[ \begin{align} \max \quad & 12x_1 + 9x_2 & (\text{profit}) \\ \text{s.t.} \quad & x_1 \leq 1000 & (\text{footballs}) \\ & x_2 \leq 1500 & (\text{soccer balls}) \\ & x_1 + x_2 \leq 1750 & (\text{plaques}) \\ & 4x_1 + 2x_2 \leq 4800 & (\text{wood}) \\ & x_1, x_2 \geq 0 \end{align} \]

Adding slack variables, the model main constraints can be written in standard form as follows:

\[ \begin{align} &+ x_1 &+ x_3 & &= 1000 \\ &+ x_2 &+ x_4 & &= 1500 \\ &+ x_1 + x_2 & &+ (0) &= 1750 \\ &+ 4x_1 + 2x_2 & &+ (0) &= 4800 \end{align} \]

Here, we can fix arbitrarily two variables to 0 and solve the system of equations for the remaning 4 variables. Let’s fix \(x_5\) and \(x_6\) to 0 (see the standard LP model above) and solve the system of equations for the remaining 4 variables. Algebraic solution is found by \(A^{-1}b\) assuming \(A\) is non-singular (i.e. the determinant of A is not equal to 0). In other words, a basic solution exists if the columns of basic variables form a basis (largest possible independent set) for the matrix \(A\). See example 5.9 in the textbook [reference 1]. If you question how many basic solutions we can have, the answer is \(C(n,n-m)\) where \(n\) is the number of variables and \(n-m\) is the number of non-basic variables.

A basic feasible solution to a standard LP is a basic solution that satisfies all non-negativity constraints. These are extreme-point (corner point) solutions of the feasible region.

It’s informative to consider both the algebraic and geometric representations. In geometric representation, the feasible region is a convex polyhedron and the basic solutions are the extreme points of the polyhedron. Moreover, each constraint can be represented as a non-negativity constraint of original and slack variables. Then, a basic solution is found by active constraints (non-negativity constraints equels to 0). See example 5.10 in the textbook [reference 1].

References

1: Optimization in OR textbook by R. Rardin