I have the following problem which I'm trying to solve by dual simplex method:

$$min -6x_1-14x_2-13x_3$$ s.t $$0.5x_1+2x_2+x_3 \le 24$$ $$x_1+2x_2+4x_3 \le 60$$ $$x_1+x_2 \ge 40$$ $$x_1, x_2, x_3 \ge 0$$

I change the constraints into equality as: $$0.5x_1+2x_2+x_3+s_1 = 24$$ $$x_1+2x_2+4x_3+s_2 = 60$$ $$-x_1-x_2+s_3=-40$$ The problem is that in the initial tableau the reduced costs are $-6, -14, -13, 0, 0, 0$ which violate the non-negativity clause for the reduced costs in dual simplex method.

Similarly there could be another type of problem with atleast 1 initial reduced cost as negative, such as:

$$min x_1-8x_2$$ s.t $$x_1+x_2 \ge 1$$ $$-x_1+6x_2 \le 3$$ $$x_1 \le 2$$ $$x_1, x_2, x_3 \ge 0$$

Again, I change the constraints into equality as: $$-x_1-x_2+s_1 = -1$$ $$-x_1+6x_2+s_2 = 3$$ $$x_1+s_3= 2$$ Here my initial reduced cost is $(1, -8, 0, 0)$. If I try solving the above two questions without taking the negativity of reduced costs into consideration, I stop at some intermediate solution when my $ B^{-1} b$ becomes $\ge 0$ which is not optimal solution and my reduced vector is still not $\ge 0$. How should I then proceed with such problem if my reduced costs are negative?


1 Answer 1


As far as I know, in the dual simplex method, we start from a dual feasible (or primal optimal where all elements in the objective row are nonnegative in a maximization problem) and in each iteration, we try to achieve primal feasibility (or dual optimality where all elements of the right-hand side are nonnegative).

If you think about the conditions for dual simplex as described above, then you can see that in your first example, you still have primal optimality and just need to get to primal feasibility (btw, one obvious answer is to increase x1 as much as 3rd constraint allows).

In your second example, you have both primal and dual infeasibility. I think in this situation, you better use the generalized simplex algorithm.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .