Suppose we have a linear program which has exactly three non-negative decision variables
x1, x2, x3 and exactly three functional constraints, each containing a single variable: xi ≤ 1,
i ∈ {1, 2, 3}.
How do we find the number of basic and feasible solutions exactly and check for degeneracy?
Best Answer
At most one of $x_i\ge0$ and $x_i\le1$ can be tight for each $i$. To get a basic solution, with three tight constraints, we have to choose for each variable which of the two constraints is tight – exactly one for each variable. This gives us $2^3=8$ basic solutions. They may all be easily checked to be feasible and non-degenerate.