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$
1
  • $\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
    Commented Jun 7, 2017 at 12:02

1 Answer 1

4
$\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$
2
  • $\begingroup$ I've added a problem above. $\endgroup$ Commented Jun 17, 2017 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$ Commented Jun 17, 2017 at 13:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .