# Solving a linear program thanks to complementary slackness theorem

Using the complementary slackness theorem, say if the following basis optimal:

$$x_1*=0=x_5*,x_2*=4/3,x_3*=2/3,x_4*=5/3$$

\begin{cases} \max & 7x_1 &+6x_2&+5x_3&-2x_4&+3x_5\\ &x_1 &+3x_2 & +5x_3 & -2x_4 & +2x_5&\le 4\\ &4x_1 & +2x_2 & -2x_3 & +x_4 & +5x_5&\le 3\\ &2x_1 & +4x_2& +4x_3 & -2x_4 & +5x_5&\le5\\ &3x_1 &+x_2 & +2x_3 & -x_3 &-2x_5&\le 1\\ \forall i, x_i\ge 0 \end{cases}

I know it is feasible because:

\begin{cases} 3*4/3&+5*2/3&-2*5/3&=4, ok\\ 2*4/3&-2*2/3&+5/3&=3,ok\\ 16/3& +8/3&-10/3&=14/3<5,ok\\ 4/3& +14/3&-5/3&=1,ok \end{cases}

I did the dual but I'm definitely not sure about it and I'm looking for the rules related to the dual construction:

\begin{cases} \max & 4y_1 &+3y_2&+5y_3&+y_4&\\ &y_1&+4y_2 &+2y_3& +3y_4&= 7\\ &3y_1&+2y_2&+4y_3&+y_4&=6\\ &5y_1&-2y_2&+4y_3&+2y_4&=2\\ &2y_1&+y_2&+5y_3&-2y_4&= 3\\ \forall i, y_i\ge 0 \end{cases}

I'm not sure about it, and I don't know what to do from here.

Do I have to find all $y_i$?

• Why do you have only 4 constraints although there are 5 variables at the primal problem ? The third constraint is missing. Apr 22 '16 at 17:02
• @callculus, I don't know, it is the way it was given in Linear Programing by Vasek Chvàtal p69, Problem 5.3.a Apr 22 '16 at 17:09
• @callculus, you were right, one line is missing in the dual Apr 23 '16 at 16:36

I use the table below to create the dual problem. If you have any question about the table or other aspects of my answer feel free to ask.

\begin{cases} \min & 4y_1 &+3y_2&+5y_3&+y_4&\\ &y_1&+4y_2 &+2y_3& +3y_4&\geq 7\\ &3y_1&+2y_2&+4y_3&+y_4&\geq6\\ &5y_1&-2y_2&+4y_3&+2y_4&\geq5\\ &-2y_1&+y_1&-2y_3&-y_4&\geq -2\\ &2y_1&+5y_2&+5y_3&-2y_4&\geq 3\\ \forall i, y_i\ge 0 \end{cases}

You have evaluated the values of the slack variables ($s_i$). The result is right. $s_1=s_2=s_4=0$. And $s_3=5-\frac{14}{3}=\frac{1}{3}>0$

Now we can apply the complementary slackness theorem:

$x_j\cdot z_j=0 \ \forall \ \ j=1,2, \ldots , n$

$y_i\cdot s_i=0 \ \forall \ \ i=1,2, \ldots , m$

$s_i \text{ are the slack variables of the primal problem.}$

$z_j \text{ are the slack variabales of the dual problem.}$

Since $s_3 > 0$, we can conclude that $y_3=0$

And $x_2=x_3=x_4> 0 \Rightarrow z_2=z_3=z_4=0$

Now we can take the constraints 2,3,4 from the dual and replace the $\geq$-signs by the equality signs. Additionally we can drop the terms with $y_3$.

\begin{cases} &3y_1&+2y_2&+y_4&=6\\ &5y_1&-2y_2&+2y_4&=5\\ &-2y_1&+y_1&-y_4&= -2\\ \end{cases}

Finally you have to solve this little equation system.

Remark

If the primal problem is a min problem then you read the table from right to left. Et vice versa.

• Thank you for this very insightfull answer! I had two questions, how does the first and last line of the dual disapeared? Second you talked about $s$ and $z$ in your dual theorem but you don't use such variables then, why? Apr 23 '16 at 16:40
• First question: The first and the last constraint are not very helpful here. We can´t get rid of the inequality signs. We know from the primal problem that $x_1=x_5=0$. Therfore $x_1\cdot z_1=0$ and $x_5\cdot z_5=0$. In both cases the product is zero no matter what $z_1, z_5$ is. We cannot be sure, that $z_1$ or $z_2$ are zero. They are both slack variables of the dual problems (constraint 1 and 5). Second question: If we have inequalities then the slack variables are not need. But to transform the inequlities in equalities we need slack variables. Apr 23 '16 at 17:03
• The fifth constraint can be written with an inequality sign or with an equality sign. $2y_1+5y_2+5y_3-2y_4\geq 3\Rightarrow 2y_1+5y_2+5y_3-2y_4-z_5 =3$ The slack variable has a positive value. In combination with the minus sign $z_5$ are subtracted, because the rest of the LHS ($2y_1+5y_2+5y_3-2y_4$) is greater than 3. Apr 23 '16 at 17:10
• First: Since $s_3 > 0$, we can conclude that $x_2=x_3=x_4> 0 \Rightarrow z_2=z_3=z_4=0$, why is it important to say it? We don't use it then, don't we? Second: I tried some linear combination to understand why were the first and the last constraint not useful but I still don't figure it out... Apr 26 '16 at 11:31
• @Marine1 Second question: Now we have a linear equation system of three equations and three variables. This has a unique solution. Thus we dont´have to care about the first and fifth constraint. Have you been able to evaluate the values of $y_1,y_2$ and $y_4$ ? Apr 26 '16 at 13:15