Solving a linear program thanks to complementary slackness theorem

648 Views Asked by At

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

1

There are 1 best solutions below

11
On BEST ANSWER

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.