2
$\begingroup$

I have to find the optimal solution of the dual with the complementary slackness conditions.
This is the primal:
$\max \space\space z= x_1 - 2x_2 $
$\text{s.t.}\space\space\space\space\space x_1-x_2\ge 1$
$\space\space\space\space\space\space\space\space\space\space x_1-2x_2\le 6$
$\space\space\space\space\space\space\space\space\space\space 2x_1-x_2\le 6$
$\space\space\space\space\space\space\space\space\space\space x_1\ge0,x_2\le0$

The optimal solution (found with simplex method) is:
$z=6,x_1=0,x_2=3$

Here is the dual of the previous PL:
$\min \space\space \psi= y_1+6y_2+6y_3 $
$\text{s.t.}\space\space\space\space\space y_1+y_2+2y_3\ge1$
$\space\space\space\space\ -y_1-2y_2-y_3\le-2$
$\space\space\space\space\space\space\space\space\space\space y_1\le0,y_2\ge0,y_3\ge0$

The complementary conditions are:
$1)\space\space\space y_1\times(x_1-x_2-1) = 0$
$2)\space\space\space y_2\times(x_1-2x_2-6) = 0$
$3)\space\space\space y_3\times(2x_1-x_2-6) = 0$
$4)\space\space\space x_1\times(1-y_1-y_2-2y_3) = 0$
$5)\space\space\space x_2\times(-2+y_1+2y_2+y_3) = 0$

Now, using the optimal solution of the primal I have:
$(x_1-x_2-1) = -4 \ne 0, y_1=0$
$(x_1-2x_2-6) = -12 \ne 0, y_2=0$
$(2x_1-x_2-6) = -9 \ne 0, y_3=0$

Clearly this is wrong, but I am not able to find the mistake.

$\endgroup$
4
  • 2
    $\begingroup$ Your solution of the primal is not feasible. First constraint: $0-3=-3\ngeq 1$ . $\endgroup$ Nov 4, 2015 at 14:08
  • $\begingroup$ Ooops. I made a mistake in simplex method. x2=-3. Thank you. $\endgroup$ Nov 4, 2015 at 15:04
  • $\begingroup$ But you know, that the condition is $x_i \geq 0$ to apply the simplex method. $\endgroup$ Nov 4, 2015 at 15:43
  • $\begingroup$ Yeah, I set $x_2=x_2^- - x_2^+$ with $x_2^-\ge0,x_2^+\ge0$ and so $x_2\le0$ $\endgroup$ Nov 5, 2015 at 10:45

1 Answer 1

0
$\begingroup$

Since the optimal solution, as you've said, is actually $x_2 = -3$, so everything is correct except the calculations for $y_1,y_2$ and $y_3$ at the bottom.

\begin{alignat}{2} x_1-x_2-1 &= 0 - (-3) - 1 = 2 \ne 0, &\quad y_1 &= 0 \\ x_1-2x_2-6 &= 0 - 2(-3) - 6 = 0, &\quad y_2 &= ? \\ 2x_1-x_2-6 &= 2(0) - (-3) - 6 = -3 \ne 0, &\quad y_3 &= 0 \end{alignat}

In order to find the value of $y_2$, we need to use the complementary slackness condition once more.

$$x_2 = -3 \implies -2+y_1+2y_2+y_3 = 0 \implies y_2 = 1$$

You can substitute $(y_1,y_2,y_3) = (0,1,0)^T$ back to the dual, and you'll find out that $\psi= y_1+6y_2+6y_3 = 0+6(1)+0 = 6$, which is equal to the given optimal value of the primal problem. Hence, by the Strong Duality Theorem, this is the solution of the dual.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .