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    − x₁ − 3x₂ + 4x₃

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

                   2x₁ + 3x₂ − x₃ = 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 $

$ \text{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 $

$ \text{Equivalently, } -x_{1}-3x_{2}+4x_{3}\leq-9 $

$ \text{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. $

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

One of the basic feasible solution is an optimal solution.
$ \text{The equality constraints can be represented in the form } Ax=b, A= \begin{bmatrix} a_{1}& a_{2}& a_{3} \end{bmatrix} $

$ \text{The fist basis candidate is } \begin{pmatrix} a_{1} & a_{2} \end{pmatrix} $

$ \left [ A|b \right ] =\begin{bmatrix} 1 & 2 & -1 & 5 \\ 2 & 3 & -1 & 6 \end{bmatrix} = \cdots = \begin{bmatrix} 1 & 0 & 1 & -3 \\ 0 & 1 & -1 & 4 \end{bmatrix} $

$ x^{\left( 1 \right)}= \begin{bmatrix} -3 & 4 & 0 \end{bmatrix} \text{ is BFS. } f_{1}=-9 $

$ \text{The second basis candidate is } \begin{pmatrix} a_{2} & a_{3} \end{pmatrix} $

$ \left [ A|b \right ] =\begin{bmatrix} 1 & 2 & -1 & 5 \\ 2 & 3 & -1 & 6 \end{bmatrix} = \cdots = \begin{bmatrix} 1 & 0 & 1 & -3 \\ 1 & 1 & 0 & 1 \end{bmatrix} $

$ x^{\left( 2 \right)}= \begin{bmatrix} 0 & 1 & -3 \end{bmatrix} \text{ is BFS. } f_{2}=-15 $

$ \text{The third basis candidate is } \begin{pmatrix} a_{1} & a_{3} \end{pmatrix} $

$ \left [ A|b \right ] =\begin{bmatrix} 1 & 2 & -1 & 5 \\ 2 & 3 & -1 & 6 \end{bmatrix} = \cdots = \begin{bmatrix} 0 & 1 & 1 & 4 \\ 1 & 1 & 0 & 1 \end{bmatrix} $

$ x^{\left( 2 \right)}= \begin{bmatrix} 1 & 0 & -5 \end{bmatrix} \text{ is BFS. } f_{3}=-21 $

$ \because f_{1}>f_{2}>f_{3} $

$ \therefore \text{The optimal solution is } x^{*}=\begin{bmatrix} -3 & 4 & 0 \end{bmatrix} \text{ with objective value } -9 $

Automatic Control (AC)- Question 3, August 2011
Problem 1: https://www.projectrhea.org/rhea/index.php/ECE-QE_AC3-2011_solusion
Problem 2: https://www.projectrhea.org/rhea/index.php/ECE-QE_AC3-2011_solusion-2
Problem 4: https://www.projectrhea.org/rhea/index.php/ECE-QE_AC3-2011_solusion-4
Problem 5: https://www.projectrhea.org/rhea/index.php/ECE-QE_AC3-2011_solusion-5

Back to ECE Qualifying Exams (QE) page