# How to test if a feasible solution is optimal - Complementary Slackness Theorem - Linear Programming

I have this linear program

$$\begin{cases} \text{max }z=&5x_1+7x_2-3x_3\\ &2x_1+4x_2-2x_3&\le8\\ &-x_1+x_2+2x_3&\le10\\ &x_1+2x_2-x_3&\le6\\ &x_1,\,x_2,\,x_3\ge0 \end{cases}$$

and a feasible solution of his dual $(D)$ is $y = {7/2,2,0}$.

I need to find an optimal basis of $(P)$ and an optimal basis of $(D)$ using the complementary slackness theorem.

I thought about assuming that $y$ is an optimal solution of $(D)$ and find the optimal solution of $(P)$ and after using the corollary of this theorem to prove that $y$ is an optimal solution (then $x$ also). Is that the method to use? Is there a more appropriate methodology to solve this problem?

The dual problem is

$$\begin{cases} \text{min }&8y_1+10y_2+6y_3\\ &2y_1-y_2+y_3&\ge5\\ &4y_1+y_2+2y_3&\ge7\\ &-2y_1+2y_2-y_3&\ge3\\ &y_1,y_2,y_3\ge0 \end{cases}$$

• Hint: First of all you can eleminate the third constraint. Just divide the first constraint by 2 and compare it with the third constraint. After eleminating the third constraint you will have only two variables in your dual problem. What do you have for the dual problem ? – callculus Mar 8 '15 at 18:57
• I edited the question to add the dual problem, I don't know how to add a picture in a comment, sorry.. – Farah Mar 8 '15 at 19:10
• – BCLC May 7 '16 at 10:23

Your formulation of the dual Problem is right-you forgot the negative sign at the third constraint only. As I said, you can eleminate the third constraint (primal problem).In this case the dual problem is: $$\text{min } 8y_1+10y_2\\ 2y_1-y_2\ge 5\\ 4y_1+y_2\ge 7\\ -2y_1+2y_2\ge -3\\ y_1,y_2\ge0$$

The solution of this problem is $y^T=(y_1,y_2)=(3.5;2)$ Your solution is right. The solution is $y_3=0$, because the third constraint is not necessary.

The compementary slackness condition is $X^TC^*=b^TY^*$

This gives: $\begin{pmatrix}5 & 7 & -3\end{pmatrix}\cdot \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}=\begin{pmatrix} 8 & 10 \end{pmatrix} \cdot \begin{pmatrix} 3.5 \\ 2 \end{pmatrix} \Rightarrow \begin{pmatrix}5 & 7 & -3 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}=48$

The following condition must hold $x_j \cdot z_j=0 \ \ \forall n$

$z_j$ are the slack variables of the dual problem. If you insert the solution for the dual problem, then you will see, that $z_1$ and $z_3$ are zero and $z_2$ is not zero. Thus the equations are (for all n):

$x_1\cdot 0=0$

$x_2\cdot z_2=0$

$x_3\cdot 0=0$

Thus you know for sure, that $x_2=0$

And secondly this equation must hold: $s_i\cdot y_i=0 \ \ \forall m$

$s_i$ are the slack variables of the primal problem. Thus $s_1$ and $s_2$ are zero and so we have the equations:

$2x_1-2x_3=8$

$-x_1+2x_3=10$

Remember, that $x_2=0$

This two equations you can solve.

• Thank you ! Did we prove that the solution y is optimal if we demonstrate that x=(18,0,14) and that $C^{T}X^{∗}=b^{T}Y^{∗}$ ? (then if y is optimal then x is optimal). I have another question... how do we find the basis corresponding to the solution ? – Farah Mar 9 '15 at 10:27
• – BCLC May 7 '16 at 10:23
• @callculus can you help me with this problem: math.stackexchange.com/questions/2473878/… You seem to be one of the few OR people on MSE. – ALannister Oct 15 '17 at 19:16
• @ALannister Thanks that you trust in me. But at the moment I´m little bit stressed. Maybe tomorrow evening (german time) I will have a look at your question. But I hope You will get help earlier. – callculus Oct 15 '17 at 21:37