1
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – callculus Mar 8 '15 at 18:57
  • $\begingroup$ I edited the question to add the dual problem, I don't know how to add a picture in a comment, sorry.. $\endgroup$ – Farah Mar 8 '15 at 19:10
  • $\begingroup$ Similar? math.stackexchange.com/a/1775218/140308 $\endgroup$ – BCLC May 7 '16 at 10:23
3
$\begingroup$

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$

Additional

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.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Farah Mar 9 '15 at 10:27
  • $\begingroup$ Similar? math.stackexchange.com/a/1775218/140308 $\endgroup$ – BCLC May 7 '16 at 10:23
  • $\begingroup$ @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. $\endgroup$ – ALannister Oct 15 '17 at 19:16
  • $\begingroup$ @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. $\endgroup$ – callculus Oct 15 '17 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.