6
$\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$
4
  • $\begingroup$ Are you sure about your solution to the dual problem ? It doesn´t meet the third condition, among others. $\endgroup$ Commented Apr 8, 2015 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$ Commented Apr 8, 2015 at 23:41
  • $\begingroup$ Thanks, I corrected the inequality signs. $\endgroup$ Commented Apr 9, 2015 at 2:12
  • $\begingroup$ I was not sure, that you could manage to change the Latex-Code. But you have done it. Nice. $\endgroup$ Commented Apr 9, 2015 at 4:47

1 Answer 1

Reset to default
8
$\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$
1
  • 1
    $\begingroup$ @LaísMinchillo You are welcome. $\endgroup$ Commented Apr 9, 2015 at 4:02

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.