| Line 9: | Line 9: | ||
<span class="texhtml">maximize − ''x''<sub>1</sub> − 3''x''<sub>2</sub> + 4''x''<sub>3</sub></span><br> | <span class="texhtml">maximize − ''x''<sub>1</sub> − 3''x''<sub>2</sub> + 4''x''<sub>3</sub></span><br> | ||
| − | <span class="texhtml"><sub></sub></span>subject to <span class="texhtml">''x''<sub>1</sub> + 2''x''<sub>2</sub> − ''x''<sub>3</sub> = 5</span> | + | <span class="texhtml"><sub></sub></span>subject to <span class="texhtml">''x''<sub>1</sub> + 2''x''<sub>2</sub> − ''x''<sub>3</sub> = 5</span> |
| − | <span class="texhtml"> 2''x''<sub>1</sub> + 3''x''<sub>2</sub> − ''x''<sub>3</sub> = 6</span> | + | <span class="texhtml"> 2''x''<sub>1</sub> + 3''x''<sub>2</sub> − ''x''<sub>3</sub> = 6</span> |
| − | <math>x_{1} \text{ free, } x_{2}\geq0, x_{3}\leq0.</math> | + | <math>x_{1} \text{ free, } x_{2}\geq0, x_{3}\leq0.</math> |
===== <math>\color{blue}\text{Solution 1:}</math> ===== | ===== <math>\color{blue}\text{Solution 1:}</math> ===== | ||
| Line 21: | Line 21: | ||
<math>\Rightarrow x_{2}-x_{3}=4</math> | <math>\Rightarrow x_{2}-x_{3}=4</math> | ||
| − | It is equivalent to <math>min x_{1}+3x_{2}-4x_{3} | + | It is equivalent to <math>\text{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</math> | + | =5-2x_{2}+x_{3}+3x_{2}-4x_{3} = x_{2}-3x_{3}+5, x_{2}\geq0, x_{3}\leq0</math> |
| − | <math>x_{2}-3x_{3}+5 = x_{2}-x_{3}-2x_{3}+5=9-2x_{3}\geq9</math> | + | <math>x_{2}-3x_{3}+5 = x_{2}-x_{3}-2x_{3}+5=9-2x_{3}\geq9</math> |
| − | Equicalently, <math>-x_{1}-3x_{2}+4x_{3}\leq-9</math> | + | Equicalently, <math>-x_{1}-3x_{2}+4x_{3}\leq-9</math> |
| − | Equality is satisfied when <math>x_{3}=0, x_{2} =4, x_{1}=5-2\times4=-3</math> | + | Equality is satisfied when <math>x_{3}=0, x_{2} =4, x_{1}=5-2\times4=-3</math> |
<math>\Rightarrow \left\{\begin{matrix} | <math>\Rightarrow \left\{\begin{matrix} | ||
| Line 34: | Line 34: | ||
x_{2}=4\\ | x_{2}=4\\ | ||
x_{3}=0 | x_{3}=0 | ||
| − | \end{matrix}\right.</math> | + | \end{matrix}\right.</math> |
| + | |||
| + | ---- | ||
| + | |||
| + | <math>\color{blue}\text{Solution 2:}</math><br> One of the basic feasible solution is an optimal solution. | ||
| + | |||
| + | The equality constraints can be represented in the form <math>Ax=b, A= \begin{bmatrix} | ||
| + | a_{1}& | ||
| + | a_{2}& | ||
| + | a_{3} | ||
| + | \end{bmatrix}</math> | ||
| + | |||
| + | The fist basis candidate is <math>\begin{pmatrix} | ||
| + | a_{1} & | ||
| + | a_{2} | ||
| + | \end{pmatrix}</math> | ||
| + | |||
| + | <math>\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}</math> | ||
| + | |||
| + | <math>x^{\left( 1 \right)}= \begin{bmatrix} | ||
| + | -3 & 4 & 0 | ||
| + | \end{bmatrix} \text{ is BFS. } f_{1}=-9</math> | ||
| + | |||
| + | The second basis candidate is <math>\begin{pmatrix} | ||
| + | a_{2} & | ||
| + | a_{3} | ||
| + | \end{pmatrix}</math> | ||
| + | |||
| + | <math>\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}</math> | ||
| + | |||
| + | <math>x^{\left( 2 \right)}= \begin{bmatrix} | ||
| + | 0 & 1 & -3 | ||
| + | \end{bmatrix} \text{ is BFS. } f_{2}=-15</math> | ||
| + | |||
| + | The third basis candidate is <math>\begin{pmatrix} | ||
| + | a_{1} & | ||
| + | a_{3} | ||
| + | \end{pmatrix}</math> | ||
| + | |||
| + | <math>\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}</math> | ||
| + | |||
| + | <math>x^{\left( 2 \right)}= \begin{bmatrix} | ||
| + | 1 & 0 & -5 | ||
| + | \end{bmatrix} \text{ is BFS. } f_{3}=-21</math> | ||
| + | |||
| + | <math>\because f_{1}>f_{2}>f_{3}</math> | ||
| + | |||
| + | <math>\therefore \text{The optimal solution is } x^{*}=\begin{bmatrix} | ||
| + | -3 & 4 & 0 | ||
| + | \end{bmatrix} \text{ with objective value } -9</math> | ||
| − | |||
---- | ---- | ||
Revision as of 13:41, 27 June 2012
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 $ \text{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. $
$ \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} a_{1}& a_{2}& a_{3} \end{bmatrix} $
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 $
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 $
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 $
