Understanding complementary slackness

Question

I've chosen a simple example to help me understand duality and complementary slackness. Suppose we have linear program:

$$Maximize\quad 5x_1+x_2\quad s.t$$ $$2x_1+x_2 \le 6$$ $$x_1+x_2 \le 4$$ $$2x_1+10x_2 \le 20$$ $$x_1,x_2 \ge 0$$

$$Solution \quad is \quad (3,0)$$

Now we have a dual $$Maximize\quad 6y_1+4y_2+20y_3\quad s.t$$ $$2y_1+y_2+2y_3 \ge 5$$ $$y_1+y_2+10y_3 \ge 1$$ $$y_1,y_2 \ge 0$$

In what way can the solution of the first problem help us find the solution to the dual.

$$\texttt{Maximize}\quad x_1+2x_2+3x_3\quad s.t$$ $$x_1+2x_2 +x_3 \le 1$$ $$x_1+x_2 +3x_3 \le 2$$ $$x_1,x_2,x_3 \ge 0$$ $$Optimal solution is (0,\frac{1}{5},\frac{3}{5})$$

$$\texttt{Minimize}\quad y_1+2y_2\quad s.t$$ $$y_1+y_2 \ge 1$$ $$2y_1+y_2 \ge 2$$ $$y_1+3y_2 \ge 3 $$ $$y_1,y_2 \ge 0$$

$$\texttt{Maximize}\quad x_1+2x_2+3x_3\quad s.t$$ $$x_1+2x_2 +x_3 +s_1= 1$$ $$x_1+x_2 +3x_3+s_2= 2$$ $$x_1,x_2,x_3,s_1,s_2 \ge 0$$

$$\texttt{Minimize}\quad y_1+2y_2\quad s.t$$ $$y_1+y_2 -z_1= 1$$ $$2y_1+y_2 -z_2=2$$ $$y_1+3y_2 -z_3= 3 $$ $$y_1,y_2,z_1,z_2,z_3 \ge 0$$

$x_j\cdot z_j=0 \ \forall \ \ j=1,2, \ldots , n \quad (\color{blue} I)$

$y_i\cdot s_i=0 \ \forall \ \ i=1,2, \ldots , m \quad (\color{blue}{ II})$

$x_2=\frac{2}{5}$ so $x_2*z_2=0$ therefore $z_2=0$. Going through and doing this gives me values of $0$ for $y_1$ and $y_2$ since the $x_1,x_2$ have zero slack so what am I doing wrong?

Answer 1

Firstly you can write in both cases the constraints as equalities by introducing slack-/surplus variables at the primal problem ($s_i$) and at the dual problem ($z_j$).

$$\texttt{Maximize}\quad 5x_1+x_2\quad s.t$$ $$2x_1+x_2 +s_1= 6$$ $$x_1+x_2 +s_2= 4$$ $$2x_1+10x_2 +s_3= 20$$ $$x_1,x_2,s_1,s_2,s_3 \ge 0$$

$$\texttt{Minimize}\quad 6y_1+4y_2+20y_3\quad s.t$$ $$2y_1+y_2+2y_3 -z_1= 5$$ $$y_1+y_2+10y_3 -z_2= 1$$ $$y_1,y_2,z_1,z_2 \ge 0$$

$\small{\texttt{Outline: The dual problem has to be minimized if the primal is maximized.}}$

Using the complementary slackness conditions:

---

$x_j\cdot z_j=0 \ \forall \ \ j=1,2, \ldots , n \quad (\color{blue} I)$

$y_i\cdot s_i=0 \ \forall \ \ i=1,2, \ldots , m \quad (\color{blue}{ II})$

---

You know that $x_1=3$. Looking at $I$ you get the equation: $3\cdot z_1=0$. Thus $z_1=0$. At the dual program the first constraint becomes $2y_1+y_2+2y_3 = 5 \quad (\color{blue}{III})$

Going back to the primal problem. You know the values of $x_1$ and $x_2$. With this information you can evaluate the values of the $s_i$´s.

$2\cdot 3+0 +s_1= 6\Rightarrow s_1=0$

$3+0 +s_2= 4\Rightarrow s_2>0$

$2\cdot 3+0 +s_3= 20\Rightarrow s_3>0$

Now you can use $II$ to evaluate the values of $y_2$ and $y_3$. It is obvious that $y_2=y_3=0$

Now you insert these values into $III$

$2y_1+0+2\cdot 0 = 5\Rightarrow y_1=\frac52$

And the optimal value of the dual problem is $6\cdot \frac52=15$

It is the same optimal value as in the primal progam. This is what one would expect.