Struggling on how to go about performing the Simplex Method with mixed constraints

linear programmingsimplex method

I am struggling to understand how to perform the Simplex Method when the constraints are not what is expected. For example, the problem

min $-6x-4y+2z$

subject to

$x + y + 4z \leq 20$

$-5y + 5z \leq 100$

$x + 3y + z \leq 400$

$x,y,z \geq 0$

Since this is a minimization problem you would expect the constraints to be $\geq$ and not $\leq$. How would you go about solving this using the Simplex Method?

When converting to canonical form, do I subtract a slack variable on each inequality and turn it into an equation, or do I subtract a slack and add an artificial variable? Different websites online have conflicting resolutions. Some just say arbitrarily choose a variable to switch into the basis which I am dead against trying because it is not a mathematical method by any stretch of the imagination.

Can someone please explain what to do?

Best Answer

You just add slack variables for every single $\leq$-constraint.

min $-6x-4y+2z$

subject to

$x + y + 4z +s_1= 20$

$-5y + 5z +s_2= 100$

$x + 3y + z +s_3= 400$

$x,y,z \geq 0$

Then the initial tableau is

$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline x & y & z & s_1 & s_2 & s_3 & \textrm{RHS} \\ \hline \color{red} 1 & 1 & 4 & 1 & 0 & 0 & 20 \\ \hline 0 & -5 & 5 & 0 & 1 & 0 & 100 \\ \hline 1 & 3 & 1 & 0 & 0 & 1 & 400 \\ \hline -6 & -4 & 2 & 0 & 0 & 0 & 0 \\ \hline\end{array}$$

The last row of the table is represents the objective function, which needs to be minimized. That is the reason why the coefficients of the objective function are not multiplied by $(-1)$. The basic feasible solution is $(x,y,z,s_1,s_2,s_3)=(0,0,0,1,1,1)$. To find the pivot element we have to choose the pivot column. The most negative coefficient is at column x. Then the the minimum of the corresponding ratios is $\min \{\frac{20}{1},\frac{400}{1}\}=20$. So the red marked cell is the pivot element. The next tableau is

$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline x & y & z & s_1 & s_2 & s_3 & \textrm{RHS} \\ \hline 1 & 1 & 4 & 1 & 0 & 0 & 20 \\ \hline 0 & -5 & 5 & 0 & 1 & 0 & 100 \\ \hline 0 & 2 & -3 & -1 & 0 & 1 & 380 \\ \hline 0 & 2 & 26 & 6 & 0 & 0 & 120 \\ \hline\end{array}$$

Since all coefficients of the objective function are non-negative we are finished. The optimal solution is $(x^*,y^*,z^*)=(20,0,0)$, where the optimal value of the objective function is $\color{red}{-120}$.