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$ 41 Answer
$\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
