Given linear program: $$ \text{min } x_1 - x_2 + 2 x_3 $$ s.t.: $$ -3x_1 + x_2 + x_3 = 4 $$ $$ x_1 - x_2 + x_3 = 3 $$ $$ x_i \geq 0; i = \{1,2,3\} $$

solution by simplex method (with double pass) is not possible, because pivot column is negative. However matlab linprog gives me nice looking solution:


$$ x=(0,\ 0.5,\ 3.5) $$ $$ fval = 6.5 $$

Is it because simplex method is weaker than method that matlab uses? Is set of programmes that can be solved by simplex smaller than set of programmes by other methods?

  • 2
    $\begingroup$ No, this program is solvable with the simplex method, and actually at the end of phase 1 one obtains $(0,0.5,3.5)$. And more generally the simplex method solves all linear programs, it is not weaker than, say, the ellipsoid method. $\endgroup$ – zarathustra Dec 24 '13 at 12:20
  • $\begingroup$ Wow! Thank you, i have overlooked that. How is it possible that simplex method ended with result even when A has no standard basis in it? $\endgroup$ – Filip Dec 24 '13 at 12:35
  • $\begingroup$ Is $A$ the program you described? If you are familiar with the two-phase simplex, then taking ($x_1,x_2,x_3,t_1,t_2$) as variables in the first phase, you can use $t_1,t_2$ as a starting basis with values $(4,3)$. $\endgroup$ – zarathustra Dec 24 '13 at 13:33
  • $\begingroup$ @Filip: Try zweigmedia.com/RealWorld/simplex.html, it will give you the Tableau and converges to your soultion with no changes to the specifications. Regards $\endgroup$ – Amzoti Dec 24 '13 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.