2
$\begingroup$

The question I've got is: Maximise $$2x-y+3z$$ subject to $$2y+z \leq 2$$ $$x+y+z=4$$ $$x-2y+z \geq 3$$ $$x,y,z \geq 0$$

Using the Simplex Tableau method. I know that for $\leq$ constraints you need slack variables, for $\geq$ you need slack and artificial variables, but what are you supposed to do with the equality constraint? I read a lecture online where it said convert it to both a $\leq$ and a $\geq$ constraint, so in this case we would have: $$ x+y+z=4$$ can be written as $x+y+z\leq 4$ and $x+y+z\geq 4$ but then it went onto say that we could just neglect the second constraint which would yield $-x-y-z\leq 4$.

Could anyone give anymore clarification if this is indeed correct and if so, why we get the final result from the two inequalities?

$\endgroup$
4
$\begingroup$

To get an optimal solution, it is necessary to have a basic solution as a starting point. This means, that the number of constraint must be equal to the number of basic variables. Thus every constraint have to have a positive slack variable or a positive artificial variable. If the slack variable is negative or is not needed, then you add an artificial variable.

There are three cases:

$\color{blue}{\leq-\texttt{constraint}}$

If you have a $\leq$-constraint, then you have to add a slack variable for each constraint.

$2y+z \leq 2 \quad \Longrightarrow \quad 2y+z +s_1=2$

$\color{blue}{=\texttt{-constraint}}$

If you have a $=$-constraint, then you do not have to add a slack variable for each constraint. But you have to add an artificial variable for each constraint.

$x+y+z=4 \quad \Longrightarrow \quad x+y+z+a_1=4$

$\color{blue}{\geq-\texttt{constraint}}$

If you have a $\geq$-constraint, then you have to substract a slack variable for each constraint. Additionally you have to add an artificial variable for each constraint.

$x-2y+z \geq 3 \quad \Longrightarrow \quad x-2y+z-s_2+a_2 = 3$

The initial simplex tableau is

$\begin{array}{|c|c|c|c|c|c|c|c|} \hline x & y & z & s_1 & s_2 & a_1 & a_2 & RHS \\ \hline -2 & 1 & -3 & 0 & 0 & 0 & 0 & 0 \\ \hline 0 & 2 & \color{red} 1 & 1 & 0 & 0 & 0 & 2 \\ \hline 1 & 1 & 1 & 0 & 0 & 1 & 0 & 4 \\ \hline 1 & -2 & 1 & 0 & -1 & 0 & 1 & 3 \\ \hline \end{array} $

The coefficients of the objective function have to be multiplied by (-1), because the objective function has to be maximized.

The initial basic solution is $(x, y, z, s_1, s_2, a_1, a_2)=(0, 0, 0, 2, 0, 4, 3)$

The first pivot element is the red One.

$\endgroup$
  • $\begingroup$ What means RHS? $\endgroup$ – FabianoLothor Mar 21 '18 at 1:37
  • $\begingroup$ @FabianoLothor Right hand side. The term of an equation which is located right of the equalitiy sign. $\endgroup$ – callculus Mar 21 '18 at 7:22
  • $\begingroup$ Thanks @callculus! I'm developing an app to resolve simplex problems using the bigM method. $\endgroup$ – FabianoLothor Mar 21 '18 at 17:40

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.