So i just started with the linear programming topic in my university. And while I was practicing, I found the next question: $$\min Z=3x_1+4x_2-x_3$$ $$\text{Subject to: }x_1+3x_2-x_3\ge1$$ $$2x_1+x_2+\frac{1}{2}x_3\ge4$$ $$x_1, x_2, x_3\ge0$$
I asked my teacher about it and he told me that we can solve this problem with simplex using the "dual method". I have been trying to do it, but I am not really getting the right answer. My approach is the following:
But, as I said, I am not getting the right solution this way. Could anyone give anymore clarification if this is indeed correct and if so, why am I getting the wrong answer.
Thanks!
The issue you’re having is due to the fact that you’re trying to convert the model instead of solving/working with it as it was given. The Dual Simplex method (another example) assumes the following:
Thus, we’ll have to make the given model infeasible like so:
$$\min z=3x_1+4x_2-x_3$$ $$\text{Subject to: }-x_1-3x_2+x_3\le-1$$ $$-2x_1-x_2-\frac{1}{2}x_3\le-4$$ $$x_1, x_2, x_3\ge0$$
Which we can standardize like such:
$$\min z=3x_1+4x_2-x_3$$ $$\text{Subject to: }-x_1-3x_2+x_3+s_1=-1$$ $$-2x_1-x_2-\frac{1}{2}x_3+s_2=-4$$ $$x_1, x_2, x_3, s_1, s_2\ge0$$
Which we’ll put into our tableau like so:
\begin{array}{|c|c|}\hline BV & z & x_1 & x_2 & x_3 & s_1 & s_2 & RHS\\\hline z & 1 & -3 & -4 & 1 & 0 & 0 & 0\\ \hline s_1 & 0 & -1 & -3 & 1 & 1 & 0 & -1\\ \hline s_2 & 0 & -2 & -1 & -\frac{1}{2} & 0 & 1 & -4 \\ \hline \text{Ratio Test} \\\hline \end{array}
Since $x_3$ is still a valid possible pivot in the original Simplex method, we’ll row reduce that column to get:
\begin{array}{|c|c|}\hline BV & z & x_1 & x_2 & x_3 & s_1 & s_2 & RHS\\\hline z & 1 & -2 & -1 & 0 & -1 & 0 & 1\\ \hline x_3 & 0 & -1 & -3 & 1 & 1 & 0 & -1\\ \hline s_2 & 0 & -\frac{5}{2} & -\frac{5}{2} & 0 & \frac{1}{2} & 1 & -4\frac{1}{2} \\ \hline \text{Ratio Test} & - & \frac{4}{5} & \frac{2}{5} & \infty & \infty & \infty & - \\\hline \end{array}
From here since there are no improving, feasible columns, we can proceed via the Dual Simplex method. From here, we’ll pick the $s_2$ row to be our pivoting row as it is the most negative row, and we’ll divide this row with the current objective row to get the Minimum Ratio Test as shown at the bottom of the above tableau. From here, we’ll pick the $x_2$ column to become our next pivot column.
After this, we should get the following optimal solution: $$z=\frac{14}{5}\quad x_1=0,\quad x_2=\frac{9}{5}\quad x_3 = \frac{22}{5}$$ $$s_1=0, s_2=0$$
If we put the original model in a LP solver, we’ll get the exact same solution as the above, which confirms that the Dual Simplex method works.