2
$\begingroup$

I want to find the optimal solution to a following linear programming problem: $$8x_1+120x_2+114x_3\to \min$$ $$x_1+7x_2+3x_3\geq 4,$$ $$x_1+5x_2+5x_3\geq 5,$$ $$x_1+3x_2+10x_3\geq 9,$$ $$x_1+2x_2+15x_3\geq11,$$ $$x_1\geq0, \ \ \ x_2\geq 0, \ \ \ x_3\geq0$$ and solution for its dual problem. I already found the dual problem: $$4y_1+5y_2+9y_3+11y_4\to \max$$ $$y_1+y_2+y_3+y_4\leq 8,$$ $$7y_1+5y_2+3y_3+2y_4\leq 120,$$ $$3y_1+5y_2+10y_3+15y_4\leq 114,$$ $$y_1\geq 0, \ \ \ y_2\geq 0 , \ \ \ y_3\geq 0 , \ \ \ y_4\geq 0.$$ I also know that in the primal problem solution $x^*_1>0, \ x^*_3>0$ for $x^*=(x_1^*,x_2^*,x_3^*)$ and $y_1^*=y_2^*=0$ for $y^*=(y_1^*,y_2^*,y_3^*,y_4^*)$. How should I use that information to find other coordinates in the optimal solution?

$\endgroup$
0
$\begingroup$

To use the complementary slackness to solve this LP problem, we first introduce slack variables $x_{s_i}$ and $y_{s_j}$ in each inequality above.

$$8x_1+120x_2+114x_3\to \min$$ \begin{align} x_1+7x_2+3x_3-x_{s_1} &= 4 \\ x_1+5x_2+5x_3-x_{s_2} &= 5 \\ x_1+3x_2+10x_3-x_{s_3} &= 9 \\ x_1+2x_2+15x_3-x_{s_4} &= 11 \end{align} $$x_1\geq0, \ \ \ x_2\geq 0, \ \ \ x_3\geq0, \ \ \ x_{s_1}\geq0, \ \ \ x_{s_2}\geq0, \ \ \ x_{s_3}\geq0, \ \ \ x_{s_4}\geq0$$

$$4y_1+5y_2+9y_3+11y_4\to \max$$ \begin{align} y_1+y_2+y_3+y_4+y_{s_1} &= 8 \\ 7y_1+5y_2+3y_3+2y_4+y_{s_2} &= 120 \\ 3y_1+5y_2+10y_3+15y_4+y_{s_3} &= 114 \end{align} $$y_1\geq 0, \ \ \ y_2\geq 0 , \ \ \ y_3\geq 0 , \ \ \ y_4\geq 0, \ \ \ y_{s_1}\geq0, \ \ \ y_{s_2}\geq0, \ \ \ y_{s_3}\geq0$$

By complementary slackness of the optimal solution, \begin{align} x^*_iy^*_{s_i} &= 0 \,\forall i \in \{1,2,3\} \\ x^*_{s_j}y^*_j &= 0 \,\forall j \in \{1,2,3,4\} \end{align}

It's given that $x^*_1>0, \ x^*_3>0$, so $y^*_{s_1}=0, \ y^*_{s_3}=0$. This means that the first and the third inequalities in the dual problem are in fact equalities. Substituting $y_1^*=y_2^*=0$ into these equalities, we have

\begin{cases} y^*_3+y^*_4 &= 8 \\ 10y^*_3+15y^*_4 &= 114, \end{cases}

which gives $y^*_3=\frac65,y^*_4=\frac{34}{5}$. From this, we further deduce that $x^*_{s_3}=0, \ x^*_{s_4}=0$. Similar to the dual problem, we have a system of simultaneous linear equations.

\begin{cases} x^*_1+3x^*_2+10x^*_3 &= 9 \\ x^*_1+2x^*_2+15x^*_3 &= 11 \tag{*}\label{sys} \end{cases}

This is not enough, so we think about the second inequality in the dual problem. We aim at proving that it's a strict inequality (i.e. $y^*_{s_2} > 0$), so that we can conclude that $x^*_2 = 0$.

\begin{align} y^*_{s_2}&=120-3y^*_3-2y^*_4\\ &=120-3\cdot\frac65-2\cdot\frac{34}{5}\\ &=\frac{514}{5}\\ &>0 \end{align}

Thus the system \eqref{sys} can be rewritten as

\begin{cases} x^*_1+10x^*_3 &= 9 \\ x^*_1+15x^*_3 &= 11, \tag{#}\label{sys1} \end{cases}

which gives $x^*_1=5, x^*_3=\frac25$ as the solution.

Hence, we have $x^*=(x_1^*,x_2^*,x_3^*)=(5,0,\frac25)$ and $y^*=(y_1^*,y_2^*,y_3^*,y_4^*)=(0,0,\frac65,\frac{34}{5})$ as an optimal solution.

$\endgroup$
0
$\begingroup$

Let $e_1,e_2,e_3,e_4$ be the slack variables of the primal, and $f_1,f_2,f_3$ the slack variables of the dual.

By the complementary slackness conditions:

  • $x_1^*>0 \quad \Rightarrow \quad f_1=0$
  • $x_3^*>0 \quad \Rightarrow \quad f_3=0$

And since $y_1^*=y_2^*=0$, it follows that $y_3^*$ and $y_4^*$ satisfy \begin{cases} y_3^*+y_4^*=8 \\ 10y_3^*+15y_4^*=114 \end{cases} Solving for $y_3^*$ and $y_4^*$ yields \begin{cases} y_3^*= \frac{6}{5} \\ y_4^*= \frac{34}{5} \end{cases}

Plugging these values in the second constraint, we get $$ 0+0+3\frac{6}{5}+2\frac{34}{5}+f_2=120\quad \Rightarrow \quad f_2 =\frac{514}{5} $$

Again, by complementary slackness:

  • $y_3^*>0 \quad \Rightarrow \quad e_3=0$
  • $y_4^*>0 \quad \Rightarrow \quad e_4=0$
  • $f_2>0 \quad \Rightarrow \quad x_2^*=0$

Therefore $x_1^*$ and $x_3^*$ satisfy

\begin{cases} x_1^*+0+10x_3^*=9 \\ x_1^*+0+15x_3^*=11 \end{cases} which gives us \begin{cases} x_1^*= 5 \\ x_3^*= \frac{2}{5} \end{cases}

Plugging these values in the two first constraints, we get $e_1=\frac{11}{5}$, $e_2=2$ and finally $y_1^*=y_2^*=0$ by complementary slackness again.

In summary: $$ \boxed{ (x_1^*,x_2^*,x_3^*)=(5,0,\frac{2}{5})\quad \mbox{and}\quad (y_1^*,y_2^*,y_3^*,y_4^*)=(0,0,\frac{6}{5},\frac{34}{5}) }$$

$\endgroup$

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.