1
$\begingroup$

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.

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

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.

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

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.