# Is simplex method weaker than other methods?

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:

linprog(c,[],[],A,b,zeros(1,length(c)))


$$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?

• 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. – zarathustra Dec 24 '13 at 12:20
• 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? – Filip Dec 24 '13 at 12:35
• 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)$. – zarathustra Dec 24 '13 at 13:33
• @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 – Amzoti Dec 24 '13 at 13:38