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?
2 Answers
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.
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}) }$$
