Simplex Method with negative R.H.S

Question

Question:

Maximize $2x_1 - 6x_2$

Subject to

\begin{align*} -x_1 - x_2 - x_3 &\leq -2 \\ 2 \, x_1 - x_2 + x_3 &\leq 1 \end{align*}

My Process:

I create an auxiliary problem:

Maximize $-x_0$

Subject to

$-x_1 - x_2 - x_3 -x_0 \leq -2 \\ 2x_1 - x_2 + x_3 -x_0 \leq 1 $

Introduce slack variables:

$w_1 = -2 + x_1 + x_2 + x_3 + x_0 \\ w_2 = 1 - 2x_1 + x_2 - x_3 + x_0 \\ P = -x_0 \\ $

$x_0$ enters basis, $w_1$ leaves.

$x_0 = 2 - x_1 - x_2 - x_3 + w_1 \\ w_2 = 3 - 3x_1 - 2x_3 + w_1 \\ P = -2 + x_1 + x_2 + x_3 - w_1 $

$x_1$ enters basis, $x_0$ leaves.

$x_1 = 2 - x_2 - x_3 + w_1 - x_0 \\ w_2 = -3 + 3x_2 + x_3 - 2w_1 + 3x_0 \\ P = 0 - x_0 $

I'm not sure what to do here. Since $w_2 = -3$ but $P = 0 - x_0$ meaning the solution to the auxiliary problem is optimal, but not feasible. Have I made an arithmetic error? Or am I doing this wrong.

I would like to solve this using the auxiliary problem method as discussed in my text. I'm not supposed to use a tableau.

Answer 1

I figured out my error. I forget to apply one Minimum Ratio Test and should have applied a pivot to $x_0$ instead of $w_2$. Since choosing $w_2$ to leave the basis provides a tighter bound.

for $x_0$ to be $\geq 0$

$x_0 \leq 2 - x_1 \implies x_1 \leq 2$

for $w_2$ to be $\geq 0$

$w_2 \leq 3 - 3x_1 \implies x_1 \leq 1$

Answer 2

Based on Thomas Ferguson's Linear Programming: A Concise Introduction, I would solve it like this:

First, construct the simplex tableau. \begin{align*} \begin{array}{c | rrr | r} & x_1 & x_2 & x_3\\ \hline y_1 & -1 & -1 & -1 & -2\\ y_2 & 2 & -1 & 1 & 1\\ \hline & -2 & 6 & 0 & 0 \end{array} \end{align*}

Using case 2 ($b_i\leq 0$) from p. 24, pivot on entry $(2,1)$. \begin{align*} \begin{array}{c | rrr | r} & y_2 &x_2 & x_3\\ \hline y_1 & \frac{1}{2}& -\frac{3}{2} & -\frac{1}{2} & -\frac{3}{2}\\ x_1 & \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} & \frac{1}{2}\\ \hline & 1 & 5 & 1 & 1 \end{array} \end{align*}

Then, using case 1 from the minimizing problem ($-\mathbf{c}\geq \mathbf{0}$) p. 26, pivot on entry $(1,2)$. \begin{align*} \begin{array}{c | rrr | r} & y_2 &y_1 & x_3\\ \hline x_2 & -\frac{1}{3}& -\frac{2}{3} & \frac{1}{3} & 1\\ x_1 & \frac{1}{3} & -\frac{1}{3} & \frac{2}{3} & 1\\ \hline & \frac{8}{3} & \frac{10}{3} & -\frac{2}{3} & -4 \end{array} \end{align*}

Finally, we use case 1 ($\mathbf{b}\geq\mathbf{0}$) from p. 23 and pivot on entry $(2,3)$. \begin{align*} \begin{array}{c | rrr | r} & y_2 &y_1 & x_1\\ \hline x_2 & -\frac{1}{2}& -\frac{1}{2} & -\frac{1}{2} & \frac{1}{2}\\ x_3 & \frac{1}{2} & -\frac{1}{2} & \frac{3}{2} & \frac{3}{2}\\ \hline & 3 & 3 & 1 & -3 \end{array} \end{align*}

Since both $\mathbf{c}$ and $\mathbf{b}$ are positive, the solution can be read off as $x_2=\frac{1}{2}$, $x_3=\frac{3}{2}$ and the rest of the variables zero. The maximum value $-3$ is in the lower right corner.

EDIT: After looking at the given link, I'll add a solution using the slack-variables for future reference.

Adding the slack-variables, we get the following problem \begin{align*} \text{Max }z=2x_1-6x_2,\quad&\text{s.t.}\\ -x_1-x_2-x_3+w_1&=-2\\ 2x_1-x_2+x_3+w_2&=1\\ x_i,w_j&\geq 0. \end{align*}

First, a feasible solution must be found. Since the right-hand side is negative, we cannot simply choose $x_i=0$, since this would contradict $w_1\geq 0$. Instead, it may be seen that letting $x_1=x_3=w_1=0$ and thus $x_2=2$ and $w_2=3$ is a feasible solution to the problem. Therefore, we obtain the system \begin{align*} x_2 &= 2+w_1-x_1-x_3\\ w_2 &= 3-3x_1+w_1-2x_3\\ z &= -12+ 8x_1-6w_1+6x_3. \end{align*}

Looking at $z$, it may be increased by adding either $x_1$ or $x_3$ to the solution. Normally we would add $x_1$ since this will have the greatest effect on the value of $z$, but since I already know that $x_1=0$ in the optimal solution, I choose $x_3$ (otherwise, we would remove $x_1$ from the solution in a later step). This gives a new system by isolating $x_3$ in the second equation and substituting in the expression for $x_2$. \begin{align*} x_3 &= \frac{3}{2} -\frac{3}{2}x_1+\frac{1}{2}w_1-\frac{1}{2}w_2\\ x_2 &= \frac{1}{2} + \frac{1}{2}w_1+\frac{1}{2}x_1+\frac{1}{2}w_2\\ z &= -3 -x_1-3w_1-3w_2. \end{align*}

Since all the coefficients in $z$ are negative, adding $x_1, w_1$ or $w_2$ to the solution would lower the value. Thus, we set $x_1=w_1=w_2=0$ and obtain the solution $x_2=\frac{1}{2}$ and $x_3=\frac{3}{2}$. The optimal value is $z=-3$.