let's say we have an optimal basic feasible solution for an LP problem solved by simplex method. In this solution, should the RHSs (right hand side) be positive or non-negative?
Because I read that if a RHS is zero (which means a basic variable takes on the value zero) then there is degeneracy. Thus the zero causes degeneracy on the RHS. But in the definition of Simplex Method it says that RHSs sohuld be non-negative. So which one? I am confused.
Best Answer
You cannot choose to avoid degeneracy. Degeneracy is not caused by a particular assignment of the variables. It is part of the given problem (e.g. linear dependency of the given constraints, vertices that are determined by more equations than necessary, linear dependency between constraints and objective function etc.) If you have an optimal basic feasible solution with active variables that take the value zero, this assignment of variables indicates that there is degeneracy, it does not cause it. There is nothing wrong with active variables taking the value zero. (You might have to introduce special handling for those, if you actually implement the simplex method.)