## [Simplex Algorithm] Optimality [closed]

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.

-
 I'm closing this question, but I'll remark that as long as your feasible set is convex, the simplex algorithm (when implemented correctly) terminates at the optimum. See en.wikipedia.org/wiki/Simplex_algorithm – S. Carnahan♦ Jul 18 2010 at 14:00