4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ it must change to minimization and the inequality signs as well, the numbers 6 and 4 must be 5 and 1 respectively, there are 3 new decision variables... $\endgroup$ – farruhota Jun 7 '17 at 12:02
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I've added a problem above. $\endgroup$ – stackdsewew Jun 17 '17 at 12:36
  • $\begingroup$ @anna_xox The dual problem is fine! Since $ x_2\ \color{red}{\texttt{and}} \ x_3 \geq 0$ it follows that $ z_2\ \color{red}{\texttt{and}} \ z_3 = 0$. Consequently you get the equation system $$2y_1+y_2 = 2$$ $$y_1+3y_2 = 3 $$ $\endgroup$ – callculus Jun 17 '17 at 13:52

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.