how do we know from a degenerate simplex tableau of an LP problem if the current basic feasible solution is optimal?

307 Views Asked by At

(simplex method) In degenerate cases, the current basic feasible solution with positive reduced cost coefficient can also be an optimal solution (in non-degenerate cases, the optimal solution is optimal if and only if all the reduced cost coefficient are nonpositive), but how can we know we have already reached that optimal solution without cycling and get the same optimal value.

1

There are 1 best solutions below

0
On

As far as I know, the answer is: you can't. To find the optimal solution keep pivoting until all reduced costs are non-positive using a method such as Bland's rule to guarantee that cycling cannot happen.