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$
3
  • $\begingroup$ Why do you have only 4 constraints although there are 5 variables at the primal problem ? The third constraint is missing. $\endgroup$ Commented Apr 22, 2016 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$ Commented Apr 22, 2016 at 17:09
  • $\begingroup$ @callculus, you were right, one line is missing in the dual $\endgroup$ Commented Apr 23, 2016 at 16:36

1 Answer 1

Reset to default
2
$\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$
11
  • $\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$ Commented Apr 23, 2016 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$ Commented Apr 23, 2016 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$ Commented Apr 23, 2016 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$ Commented Apr 26, 2016 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$ Commented Apr 26, 2016 at 13:15

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.