Question

Hello there,

got a question about the simplex algorithm.

Is the optimized objective function after applying the Simplex Algorithm the optimum?

Example:

max. -4x_2 - 5x_3 -2x_4 subject to
-x_1 - 2x_2 - 3x_3 <= -8
x1 - 2x_2 - 2x_3 - x_4 <= -3
x >= 0

The Simplex Algorith (In this case the Dual-Simplex Algorithm) says: Choose a row r with b_i < 0.

If I choose the first row with b_1 = -8 and pivot with min.(b_i / A_r,i) for all i € [n] = -3 the resulting objective value is after the second and last pivot step -30.

But If I choose the second row with b_2 = -3 first and pivot with -2 my resulting objective value is -11 at the end.

An online simplex tool calculated -11, too. It seems that both solutions are feasible.

I always thought that the Simplex Algorithm calculates the optimum. But -30 is not the optimum because -11 is also feasible.

Answer 1

I think something should be wrong. If a vertex doesn't give you the maximum then there is a neighboring vertex which improves the objective function and Simplex moves to that position. Maybe you are missing some step in the procedure when you get that -30.