Is the 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\} $$
a solution by simplex method (with double pass) is not possible, because pivot column is negative. However Matlab's $\texttt{linprog}$ function 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?
 A: At the time when this question was asked (around December $2013$), the $\texttt{linprog}$ MatLab function actually used the Revised Simplex method (with two-phase and dual) to solve linear models given to it. This is supported by the past documentation in which the methods and references are those for the mentioned algorithm. This is why $\texttt{linprog}$ is able to find the correct solution of $x^T=(0,\frac{1}{2},\frac{7}{2})$ with the objective function output of $\frac{13}{2}$. Thus, the Simplex Method is not weaker than other methods compared to $\texttt{linprog}$ as the function actually uses the Simplex method itself. $[1]$
$$$$
Back to the original model, the model provided is able to be solved via the Two-Phase or Big-M approach. For simplicity sake, lets solve this model by hand using the Big-M approach. Thus, let’s standardize the model as such:
$$\min\quad z-x_1+x_2-2x_3-M(a_1+a_2)=0$$
$$\text{Subject to: }\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad$$
$$-3x_1+x_2+x_3+a_1=4$$
$$x_1-x_2+x_3+a_2=3$$
$$x_1,x_2,x_3,a_1,a_2\ge0$$
With $M$ being the “largest” number in $\Bbb R$.
This would look like the following in the initial tableau:
\begin{array} {|c|c|}
\hline BV & z & x_1 & x_2 & x_3 & a_1 & a_2 & RHS & RT \\
\hline z & 1 & -1 & 1 & -2 & -M & -M & 0 & - \\
       ? & 0 & -3 & 1 & 1 & 1 & 0 & 4 & - \\
       ? & 0 & 1 & -1 & 1 & 0 & 1 & 3 & - \\ \hline
\end{array}
After solving for our basic variables:
\begin{array} {|c|c|}
\hline BV & z & x_1 & x_2 & x_3 & a_1 & a_2 & RHS & RT \\
\hline z & 1 & -2M-1 &  1 & 2M-2 & 0 & 0 & 7M & - \\
     a_1 & 0 &    -3 &  1 &    1 & 1 & 0 &  4 & 4 \\
     a_2 & 0 &     1 & -1 &    1 & 0 & 1 &  3 & 3 \\ \hline
\end{array}
After pivoting the $x_3$ column with the $a_2$ row we get:
\begin{array} {|c|c|}
\hline BV & z & x_1 & x_2 & x_3 & a_1 & a_2 & RHS & RT \\
\hline z & 1 & -4M+1 &  2M-1 & 0 & 0 & -2M+2 & M+6 & - \\
     a_1 & 0 &    -4 &     2 & 0 & 1 &    -1 &  1 & 1/2 \\
     x_3 & 0 &     1 &    -1 & 1 & 0 &     1 &  3 & \infty \\ \hline
\end{array}
Pivoting the $x_2$ column with the $a_1$ row we get:
\begin{array} {|c|c|}
\hline BV & z & x_1 & x_2 & x_3 & a_1 & a_2 & RHS & RT \\
\hline z & 1 & -1 &  0 & 0 & -M+\frac{1}{2} & -M+\frac{3}{2} & \frac{13}{2} & - \\
     x_2 & 0 & -2 &  1 & 0 &    \frac{1}{2} & -\frac{1}{2} &  \frac{1}{2} & - \\
     x_3 & 0 & -1 &  0 & 1 &    \frac{1}{2} & \frac{1}{2} & \frac{7}{2} & - \\ \hline
\end{array}
Which is our final tableau with:
$$x^*_1=0$$
$$x^*_2=\frac{1}{2}$$
$$x^*_3=\frac{7}{2}$$
$$z^*=\frac{13}{2}$$
Which is exactly what MatLab’s $\texttt{linprog}$ function got.

$[1]$ As of the year $2022$, there are current solvers that are generally better than most the most of the basic solvers used in the past (in the $2013$ era), like the open-source HiGHS solver, or the closed source CPLEX solver. They use various optimization techniques that build upon the simplex-method that makes the algorithmic process much faster, but done at a more nuanced level.
