most recent 30 from http://mathoverflow.net 2013-05-18T13:21:58Z http://mathoverflow.net/feeds/question/32356 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/32356/simplex-algorithm-optimality Julian 2010-07-18T13:03:03Z 2010-07-18T13:38:08Z

<p>Hello there,</p> <p>got a question about the simplex algorithm.</p> <p>Is the optimized objective function after applying the Simplex Algorithm the optimum?</p> <p>Example:</p> <pre><code>max. -4x_2 - 5x_3 -2x_4 subject to -x_1 - 2x_2 - 3x_3 &lt;= -8 x1 - 2x_2 - 2x_3 - x_4 &lt;= -3 x &gt;= 0 </code></pre> <p>The Simplex Algorith (In this case the Dual-Simplex Algorithm) says: Choose a row r with b_i &lt; 0.</p> <p>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.</p> <p>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.</p> <p>An online simplex tool calculated -11, too. It seems that both solutions are feasible.</p> <p>I always thought that the Simplex Algorithm calculates the optimum. But -30 is not the optimum because -11 is also feasible.</p>

http://mathoverflow.net/questions/32356/simplex-algorithm-optimality/32361#32361 Franklin 2010-07-18T13:38:08Z 2010-07-18T13:38:08Z

<p>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.</p>