ECE Ph.D. Qualifying Exam: Automatic Control (AC)- Question 3, August 2011
$ \color{blue}\text{3. } \left( \text{20 pts} \right) \text{ Solve the following linear program, } $
maximize − x1 − 3x2 + 4x3
subject to x1 + 2x2 − x3 = 5
2x1 + 3x2 − x3 = 6
$ x_{1} \text{ free, } x_{2}\geq0, x_{3}\leq0. $
$ \color{blue}\text{Solution 1:} $
$ \Rightarrow x_{1}=5-2x_{2}+x_{3}=3-\frac{3}{2}x_{2}+\frac{1}{2}x_{3} $
$ \Rightarrow x_{2}-x_{3}=4 $
It is equivalent to $ min x_{1}+3x_{2}-4x_{3} =5-2x_{2}+x_{3}+3x_{2}-4x_{3} = x_{2}-3x_{3}+5, x_{2}\geq0, x_{3}\leq0 $
$ x_{2}-3x_{3}+5 = x_{2}-x_{3}-2x_{3}+5=9-2x_{3}\geq9 $
Equicalently, $ -x_{1}-3x_{2}+4x_{3}\leq-9 $
Equality is satisfied when $ x_{3}=0, x_{2} =4, x_{1}=5-2\times4=-3 $
$ \Rightarrow \left\{\begin{matrix} x_{1}=-3\\ x_{2}=4\\ x_{3}=0 \end{matrix}\right. $
