About the Dual Simplex Method

Question

I have a question about the Dual Simplex Method (for minimization problem).

While we are solving the method, when we obtain a non-negative $\bar b$, we stop the algortihm. But in addition to $\bar b \ge0$ , let's have that $z_j-c_j\le0$ for some $j$ do NOT hold anymore.

Then we cannot conclude we have a optimal solution. What can we do to find a optimal solution in this case?

Note: $\bar b=B^{-1}b$

Answer 1

This should not happen. When you use the dual simplex method, you move from unfeasible extreme point to unfeasible extreme point until you find a feasible one, while maintaining your reduced costs to positive values (for a minimization problem).

Your leaving variable should be the one for which $\bar{b}$ is the most negative (the most unfeasible in some sense), and your entering variable should be the one that minimizes the impact on the objective function, through the reduced costs. The reduced costs always remain positive.

However, if for some reason you are back on a feasible extreme point with a negative reduced cost, you can use the primal simplex to reach the optimum.