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?
Best Answer
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.