1

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?

CalcBoy
  • 45
  • Have you drawn out the picture? – Parcly Taxel Apr 22 '20 at 11:38
  • I thought of adding slack variables: x1+s1 = 1, x2+s2=1, x3+s3 = 1 and then you can make one basic feasible solution but not sure how to continue from there finding all and basis for each solution. – CalcBoy Apr 22 '20 at 11:47
  • Since there are 3 variables and 3 constrains btw, does this just mean that there are 3 nCr 3 = 1 solution? – CalcBoy Apr 22 '20 at 11:49

1 Answers1

0

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.

Parcly Taxel
  • 103,344