Suppose that a linear programming problem has the following property:
its initial dictionary is not degenerate and, when solved by the simplex
method, there is never a tie for the choice of the leaving variable.
(a) Can such a problem have degenerate dictionaries?
(b) Can such a problem cycle?

From Robert J. Vanderbei - Linear Programming: Foundations and Extensions

My attempt:

For part(b), cycling depends on what method are used to choose the entering and leaving variable. So, using Bland's rule/Lexicographic method, we will never get a cycle.

For part(a), no tie for the choice of leaving variable means the values of basic variables can't cancel each other. So, it seems that such a problem can't have degenerate dictionaries.

I'm not sure with my answer by the way. Any correction/suggestion/hint is appreciated



You must log in to answer this question.

Browse other questions tagged .