ECE Ph.D. Qualifying Exam in "Automatic Control" (AC)

Question 3, August 2011, Part 3

Part 1,2,3,4,5

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

Theorem:

The Fundamental Theorem of Linear Programming that one of the basic feasible solutions is an optimal solution. 

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

$ \left.\begin{matrix} x_{1}+2x_{2}-x_{3}=5 \\ 2x_{1}+3x_{2}-x_{3}=6 \end{matrix}\right\}\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₁ + 3x₂ − 4x₃ = 5 − 2x₂ + x₃ + 3x₂ − 4x₃ = x₂ − 3x₃ + 5,

                                $ x_{2}\geq0, x_{3}\leq0 $

$ x_{2}-3x_{3}+5 = x_{2}-x_{3}-2x_{3}+5=9-2x_{3}\geq9 $   $ \color{green} \text{constrain: } x_{3}\leq0 \Rightarrow x_{3}=0 $

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

$ \text{Equality is satisfied when } x_{3}=0, x_{2} =4+0=4, x_{1}=5-2\times4=-3 $

$ \Rightarrow \left\{\begin{matrix} x_{1}=-3\\ x_{2}=4\\ x_{3}=0 \end{matrix}\right. $          $ \color{green} \text{The answer is correct.} $

$ \color{green} \text{But, this solution is NOT using the Fundamental Theorem of LP.} $

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

One of the basic feasible solution is an optimal solution.
The equality constraints can be represented in the form Ax = b,

$ A=\begin{bmatrix} 1 & 2 & -1\\ 2 & 3 & -1 \end{bmatrix}=\begin{bmatrix} a_{1}& a_{2}& a_{3} \end{bmatrix}; b=\begin{bmatrix} 5\\ 6 \end{bmatrix} $

$ \text{The first 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}^{T} \text{ is a 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}^{T} \text{ is a 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}^{T} \text{ is a BFS. } f_{3}=-21 $

$ \because f_{1}>f_{2}>f_{3} \text{ , where } f_{1}=-9 \text{ is maximal.} $

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

$ \color{green} \text{This solution use the Fundamental Theorem of Linear Programming. } $

$ \color{green} \text{All possible basic feasible solutions are generated } $

              $ \color{green} \text{ and from which the optimal one is selected.} $

$ \color{blue} \text{Related Problem: Solve the following linear programming problem,} $

minimize   3x₁ + x₂ + x₃

subject to  x₁ + x₃ = 4

                  x₂ − x₃ = 2

                  $ x_{1}\geq0,x_{2}\geq0,x_{3}\geq0, $

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

The equality constraints can be represented in the form Ax = b,

$ A= \begin{bmatrix} 1 & 0 & 1\\ 0 & 1 & -1 \end{bmatrix}=\begin{bmatrix} a_{1}& a_{2}& a_{3} \end{bmatrix}; b=\begin{bmatrix} 4\\ 2 \end{bmatrix} $

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

         $ \text{The corresponding basic solution is } x^{\left( 1 \right)}= \begin{bmatrix} 4 & 2 & 0 \end{bmatrix}^{T} \text{ is a BFS.} $

         The objective function value is f₁ = 14

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

        $ \text{The corresponding basic solution is } x^{\left( 2 \right)}= \begin{bmatrix} 6 & 0 & -2 \end{bmatrix}^{T} \text{, which is NOT a BFS.} $       

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

         $ \text{The corresponding basic solution is } x^{\left( 3 \right)}= \begin{bmatrix} 0 & 6 & 4 \end{bmatrix}^{T} \text{, which is a BFS.} $

         The objective function value is f₃ = 10

$ \therefore \text{ the optimal solution is } x^{ * }= \begin{bmatrix} 0 & 6 & 4 \end{bmatrix}^{T} $

Automatic Control (AC)- Question 3, August 2011

Go to

• Problem 1: solutions and discussions
• Problem 2: solutions and discussions
• Problem 3: solutions and discussions
• Problem 4: solutions and discussions
• Problem 5: solutions and discussions

Back to ECE Qualifying Exams (QE) page