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$
  • 2
    $\begingroup$ Your solution of the primal is not feasible. First constraint: $0-3=-3\ngeq 1$ . $\endgroup$ – callculus Nov 4 '15 at 14:08
  • $\begingroup$ Ooops. I made a mistake in simplex method. x2=-3. Thank you. $\endgroup$ – DistribuzioneGaussiana Nov 4 '15 at 15:04
  • $\begingroup$ But you know, that the condition is $x_i \geq 0$ to apply the simplex method. $\endgroup$ – callculus Nov 4 '15 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$ – DistribuzioneGaussiana Nov 5 '15 at 10:45
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$

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.