1
$\begingroup$

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

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

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.


enter image description here

Remark

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – ThePassenger Apr 23 '16 at 16:40
  • $\begingroup$ 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. $\endgroup$ – callculus Apr 23 '16 at 17:03
  • $\begingroup$ 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. $\endgroup$ – callculus Apr 23 '16 at 17:10
  • $\begingroup$ 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... $\endgroup$ – ThePassenger Apr 26 '16 at 11:31
  • $\begingroup$ @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$ ? $\endgroup$ – callculus Apr 26 '16 at 13:15

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.