# Solving a linear problem using complementary slackness condition

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?

• There is absolutely no reason why this question should have been downvoted.
– user100463
Oct 15, 2017 at 19:14

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.

$$y_1+3y_2+s_5=2$$
• $x_1=10$, $x_2=5$ $x_3=0$ is a solution right? May 11, 2016 at 21:08
• I set $x_3=0$ and solve for $x_1$ and $x_2$. I can also set $x_1=0$ and solve for the other two. And also, set for $x_2=0$ and solve for the rest. May 11, 2016 at 21:15