Can we apply Simplex Method if one or more of the constraints are equal to zero. Tell me full criteria my question example is as follows:
Maximize: $z=135x+50y$, subject to: $$\begin{align} 2x+\frac{1}{2}y&=32 \\ 4x-y&=0 \\ 4x+y&=64 \\ \end{align}$$
Tell me its full criteria to solve it, I want to confirm it now .
For simplicity’s sake, notice how the first constraint is exactly the same as the second constraint if we were to multiply it by a factor of two. Thus, since it’s a duplicate constraint we can remove it without effecting our model. Now, before we start looking into standardizing our model, we should see what this model looks like graphically:
$\hspace{4cm}$
Since our constraints are two lines, their intersection will be where our basic feasible optimal solution lives. Others in the comments have pointed out that we can do Gaussian Elimination with the constraints to find out the solution, but for the question’s sake we’ll proceed as if we weren’t allowed to do that and absolutely had to use the Simplex method.
Thus, our standard form of the model in terms of the Big-M method becomes:
$$\text{max$\quad$}z -135x-50y+M(a_1+a_2)=0$$ Subject to: $$4x-y+a_1=0$$ $$4x+y+a_2=64$$ $$x,y, a_1, a_2\ge0$$
After finding our initial basic variables in the tableau, we’ll get this initial start:
\begin{array} {|c|c|}\hline BV & z & x & y & a_1 & a_2 & RHS & RT \\ \hline z & 1 & -8M-135 & -50 & 0 & 0 & -64M & - \\ \hline a_1 & 0 & 4 & -1 & 1 & 0 & 0 & 0/4=0 \\ \hline a_2 & 0 & 4 & 1 & 0 & 1 & 64 & 64/4=16 \\ \hline \end{array}
Since $M$ is the largest possible value in $\Bbb R$, we’ll choose the $x$ column to pivot and do the minimum ratio test as already shown in the tableau above. Then, we’ll get the following tableau:
\begin{array} {|c|c|}\hline BV & z & x & y & a_1 & a_2 & RHS & RT \\ \hline z & 1 & 0 & -2M-\frac{325}{4} & 2M+\frac{135}{4} & 0 & -64M & - \\ \hline x & 0 & 1 & -1/4 & 1/4 & 0 & 0 & \frac{0}{-1/4}=-\infty \\ \hline a_2 & 0 & 0 & 2 & -1 & 1 & 64 & 64/2=32 \\ \hline \end{array}
From here, we’ll choose the $y$ column and pivot, but something is off here as the minimum ratio test is $\frac{0}{-1/4}=-\infty$. The reason this was done was to prevent an infinite cycle where Simplex keeps going back to previous tableaus after each pivot. In other words, to prevent Simplex from cycling infinitely. Thus, this is why we chose it to be equal to negative infinity than make it equal to zero. There exist three rules that can prevent infinite cycles in Simplex:
From here, we should be able to pivot the $y$ column and get the optimal solution:
\begin{array} {|c|c|}\hline BV & z & x & y & a_1 & a_2 & RHS & RT \\ \hline z & 1 & 0 & 0 & M-\frac{65}{8} & M+\frac{335}{8} & 2680 & - \\ \hline x & 0 & 1 & 0 & 1/8 & 1/8 & 8 & - \\ \hline y & 0 & 0 & 1 & -1/2 & 1/2 & 32 & - \\ \hline \end{array}
Thus, we are done.