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

Question 3, Part 3, August 2011

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

The Fundamental Theorem of Linear Programming that one of the basic feasible solutions is an optimal solution. So we generate all possible basic feasible solutions and select from them the optimal one.

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

$ \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 $   $ \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{This solution is not using the Fundamental Theorem of Linear Programming} $

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

$ \color{blue} \text{Related Problem: Solve 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 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_{1} & a_{3} \end{pmatrix} $

         $ \text{The corresponding basic solution is } x^{\left( 1 \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^{\left( * \right)}= \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