Revision as of 12:02, 27 June 2012

ECE Ph.D. Qualifying Exam: Automatic Control (AC)- Question 3, August 2011

 $ \color{blue}\text{2. } \left( \text{20 pts} \right) \text{ Use the simplex method to solve the problem, } $

               maximize        x₁ + x₂

               $ \text{subject to } x_{1}-x_{2}\leq2 $
                                        $ x_{1}+x_{2}\leq6 $                                         

                                        $ x_{1},-x_{2}\geq0. $

$ \color{blue}\text{Solution 1:} $

   min    − x₁ − x₂ 
   subject to    x₁ − x₂ + x₃ = 2 
                     x₁ + x₂ + x₄ = 6 

                     $ x_{1},x_{2},x_{3},x_{4}\geq 0 $

$ \begin{matrix} 1 & -1 & 1 & 0 & 2\\ 1 & 1 & 0 & 1 & 6 \\ -1 & -1 & 0 & 0 & 0 \end{matrix} \Rightarrow \begin{matrix} 1 & -1 & 1 & 0 & 2\\ 0 & 2 & -1 & 1 & 4 \\ 0 & -2 & 1 & 0 & 2 \end{matrix} \Rightarrow \begin{matrix} 1 & 0 & \frac{1}{2} & \frac{1}{2} & 4\\ 0 & 1 & -\frac{1}{2} & \frac{1}{2} & 2 \\ 0 & 0 & 0 & 1 & 6 \end{matrix} $

$ \Rightarrow x_{1}=4, x_{2}=2, \text{the maximum value } x_{1}+x_{2}=6 $

$ \color{blue}\text{Solution 2:} $

Get standard form for simplex method   min    − x₁ − x₂

                                                           subject to    x₁ − x₂ + x₃ = 2

                                                                             x₁ + x₂ + x₄ = 6

                                                                             $ x_{i}\geq0 i=1,2,3,4 $

$ \begin{matrix} & a_{1} & a_{2} & a_{3} & a_{4} & b\\ & 1 & -1 & 1 & 0 & 2\\ & 1 & 1 & 0 & 1 & 6 \\ c^{T} & -1 & -1 & 0 & 0 & 0 \end{matrix} \Rightarrow \begin{matrix} 1 & -1 & 1 & 0 & 2\\ 1 & 1 & 0 & 1 & 6 \\ 0 & 0 & 0 & 1 & 6 \end{matrix} $      $ \Rightarrow \begin{matrix} 1 & -1 & 1 & 0 & 2\\ 0 & 2 & -1 & 1 & 4 \\ 0 & 0 & 0 & 1 & 6 \end{matrix} \Rightarrow \begin{matrix} 1 & 0 & \frac{1}{2} & \frac{1}{2} & 4\\ 0 & 1 & -\frac{1}{2} & \frac{1}{2} & 2 \\ 0 & 0 & 0 & 1 & 6 \end{matrix} $

$ \therefore \text{the optimal solution to the original problem is } x^{*}= \begin{bmatrix} 4\\ 2 \end{bmatrix} $

<span class="texhtml" />The maximum value for   x₁ + x₂ is 6

Back to ECE Qualifying Exams (QE) page