# Recovering the optimal primal solution from dual solution

I'm having trouble finding the optimal primal solution of a particular problem from its dual solution.

Primal:

$\texttt{Maximize} \ \ 10 x_1 + 24 x_2 + 20 x_3 + 20 x_4 + 25 x_5$

Subject to

$x_1 + x_2 + 2 x_3 + 3 x_4 + 5 x_5 \leq 19$

$2 x_1 + 4 x_2 + 3 x_3 + 2 x_4 + x_5 \leq 57$

$x_1, x_2, x_3, x_4, x_5 \geq 0$

Dual:

$\texttt{Minimize} \ \ 19 u_1 + 57 u_2$

Subject to

$u_1 + 2 u_2 \geq 10$

$u_1 + 4 u_2 \geq 24$

$2 u_1 + 3 u_2 \geq 20$

$3 u_1 + 2 u_2 \geq 20$

$5 u_1 + u_2 \geq 25$

$u_1, u_2 \geq 0$

Optimal solution to the dual problem: (4,5).

Then, since all the slack variables except for second are not zero, $x_1=x_3=x_4=x_5=0$.

Substituting this we have: $x_2 \leq 19$ and $4 x_2 \leq 57$

But I can't seem to find the answer to the maximization problem.

• Are you sure about your solution to the dual problem ? It doesn´t meet the third condition, among others. – callculus Apr 8 '15 at 23:27
• For the dual restrictions, you have written the wrong inequality-signs. They have to be $\geq$ instead of $\leq$. Then it makes sense. – callculus Apr 8 '15 at 23:41
• Thanks, I corrected the inequality signs. – Laís Minchillo Apr 9 '15 at 2:12
• I was not sure, that you could manage to change the Latex-Code. But you have done it. Nice. – callculus Apr 9 '15 at 4:47

## 1 Answer

The following condition must hold:

$(A^T\cdot u^*-c)^T\cdot x^*=0$

Inserting the given values:

$\left[ \left( \begin{array}{} 1&2 \\ 1&4 \\ 2&3 \\ 3&2 \\ 5&1 \end{array} \right) \cdot \left( \begin{array}{} 4 \\ 5 \end{array} \right)-\left( \begin{array}{} 10 \\ 24 \\ 20 \\ 20 \\ 25 \end{array} \right)\right]^T\cdot \left( \begin{array}{} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{array} \right)=0$

$\left[ \left( \begin{array}{} 14 \\ 24 \\ 23 \\ 22 \\ 25 \end{array} \right) -\left( \begin{array}{} 10 \\ 24 \\ 20 \\ 20 \\ 25 \end{array} \right)\right]^T\cdot \left( \begin{array}{} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{array} \right)=0$

$\left[ \left( \begin{array}{} 4 \\ 0 \\ 3 \\ 2 \\0 \end{array} \right)\right]^T\cdot \left( \begin{array}{} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{array} \right)=0$

Thus the equation is $4x_1+0x_2+3x_3+2x_4+0x_5=0$

All $x_i$ are greater or equal to zero. Then $x_1=x_3=x_4=0$.

And the condition $s_i\cdot u_i=0 \ \ \forall i \in \{1,2\}$ must hold. Both $u_i$ have a positive value. Thus $s_1=s_2=0$

$s_i$ are the slack variables of the primal problem.

The equations are:

$x_2+5x_5=19$

$4x_2+x_5=57$

I think you can solve this little equation system on your own.

• @LaísMinchillo You are welcome. – callculus Apr 9 '15 at 4:02