Question
$\max \space\space z= 8x_1 + 6x_2 -10x_3+20x_4+2x_5$
$\text{s.t.}\space\space\space\space\space 2x_1+x_2-x_3+2x_4+x_5= 25$
$\space\space\space\space\space\space\space\space\space\space 2x_1+2x_3 -x_4+3x_5= 20$The optimal solution for the dual is given by:
$(y_1^*,y_2^*)= (6,-2), $Use complementary slackness to find optimal solution to the primal problem
My attempt
The dual of the problem is:
$\min \space\space \psi= 25y_1+20y_2 $
$\text{s.t.}\space\space\space\space\space 2y_1+2y_2+s_1 = 8$
$\space\space\space\space\space\space\space\space\space\space y_1 +s_2=6$
$\space\space\space\space\space\space\space\space\space\space -y_1+2y_2+s_3=-10$
$\space\space\space\space\space\space\space\space\space\space2y_1-y_2+s_4 = 20$
$\space\space\space\space\space\space\space\space\space\space y_1+3y_2+s_5=2$
Using complementary slackness I find that $x_4=x_5=0$
Therefore along with strong duality theorem I get the following 3 equations
$$8x_1+6x_2-10x_3=110$$
$$2x_1+x_2-x_3=25$$
$$2x_1+2x_3=20$$
However I cannot solve these equations therefore I must be doing something wrong. Can anyone see where I've gone wrong?
Best Answer
First of all the optimal solution of the dual problem is $(y_1^*,y_2^*)=(10,0)$ and $z^*=250$.
First Option
Use the following equation to evaluate the optimal values of $\mathbf x$:
$\left[c-A^Ty^* \right]^T\cdot x^*=0$
Therefore the equations are
$(8-20)x_1=0 \Rightarrow x_1=0$
$(6-10)x_2=0 \Rightarrow x_2=0$
$(-10+10)x_3=0 \ \Rightarrow x_3 \ \text{ firstly cannot be determined.}$
$(20-20)x_4=0 \ \Rightarrow x_4 \ \text{firstly cannot be determined.}$
$(2-10)x_5=0 \Rightarrow x_5=0$
From the primal problem we get the two equations
$-x_3+2x_4=25$
$2x_3-x_4=20$
Now solve for $x_3$ and $x_4$.
Second Option
Or you can conclude directly from your dual program that $s_3=s_4=0$ and $s_1,s_2$ and $s_5$ are unequal to $0$. Just plug in the values of the optimal solution.
Using
$s_j\cdot x_j=0 \ \ \forall \ j\in \{1,2,3,4,5 \}$
it follows that $x_1=x_2=x_5=0$
It remains to calculate the values of $x_3$ and $x_4$. The equations a equal to the equations of the first option.