# Solving a PL using complementary slackness conditions - dual

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.

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

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