2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thank you, however my text doesn't discuss this method. It only discusses solving the auxiliary problem. $\endgroup$ – Quaxton Hale Feb 7 '15 at 17:09
  • $\begingroup$ @QuaxtonHale I know you figured it out by yourself, but for the sake of completeness, I have added a solution using the slack-variables. $\endgroup$ – René B. Christensen Feb 8 '15 at 10:46
  • $\begingroup$ And I'll award you for your answer. $\endgroup$ – Quaxton Hale Feb 8 '15 at 11:02
  • $\begingroup$ Thanks for the link. It helped me immensely. $\endgroup$ – Salil Feb 18 at 2:42
  • $\begingroup$ "First, construct the simplex tableau." , why haven't you included $y_1,y_2$ in the initial tableau @RenéB.Christensen? $\endgroup$ – baxx Feb 22 at 0:22
1
$\begingroup$

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$

$\endgroup$

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.