| Line 19: | Line 19: | ||
<math>\Rightarrow x_{1}=5-2x_{2}+x_{3}=3-\frac{3}{2}x_{2}+\frac{1}{2}x_{3}</math> | <math>\Rightarrow x_{1}=5-2x_{2}+x_{3}=3-\frac{3}{2}x_{2}+\frac{1}{2}x_{3}</math> | ||
| − | <math>\Rightarrow x_{2}-x_{3}=4</math> | + | <math>\Rightarrow x_{2}-x_{3}=4</math> |
| − | + | <math>\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</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> | ||
| − | + | <math>\text{Equivalently, } -x_{1}-3x_{2}+4x_{3}\leq-9</math> | |
| − | Equality is satisfied when | + | <math>\text{Equality is satisfied when } x_{3}=0, x_{2} =4, x_{1}=5-2\times4=-3</math> |
<math>\Rightarrow \left\{\begin{matrix} | <math>\Rightarrow \left\{\begin{matrix} | ||
| Line 38: | Line 38: | ||
---- | ---- | ||
| − | <math>\color{blue}\text{Solution 2:}</math><br> One of the basic feasible solution is an optimal solution. | + | <math>\color{blue}\text{Solution 2:}</math><br><math>\text{One of the basic feasible solution is an optimal solution.}</math><br> |
| − | The equality constraints can be represented in the form | + | <math>\text{The equality constraints can be represented in the form } Ax=b, A= \begin{bmatrix} |
a_{1}& | a_{1}& | ||
a_{2}& | a_{2}& | ||
a_{3} | a_{3} | ||
| − | \end{bmatrix}</math> | + | \end{bmatrix}</math> |
| − | The fist basis candidate is | + | <math>\text{The fist basis candidate is } \begin{pmatrix} |
a_{1} & | a_{1} & | ||
a_{2} | a_{2} | ||
| − | \end{pmatrix}</math> | + | \end{pmatrix}</math> |
<math>\left [ A|b \right ] =\begin{bmatrix} | <math>\left [ A|b \right ] =\begin{bmatrix} | ||
| Line 57: | Line 57: | ||
1 & 0 & 1 & -3 \\ | 1 & 0 & 1 & -3 \\ | ||
0 & 1 & -1 & 4 | 0 & 1 & -1 & 4 | ||
| − | \end{bmatrix}</math> | + | \end{bmatrix}</math> |
<math>x^{\left( 1 \right)}= \begin{bmatrix} | <math>x^{\left( 1 \right)}= \begin{bmatrix} | ||
-3 & 4 & 0 | -3 & 4 & 0 | ||
| − | \end{bmatrix} \text{ is BFS. } f_{1}=-9</math> | + | \end{bmatrix} \text{ is BFS. } f_{1}=-9</math> |
| − | The second basis candidate is | + | <math>\text{The second basis candidate is } \begin{pmatrix} |
a_{2} & | a_{2} & | ||
a_{3} | a_{3} | ||
| − | \end{pmatrix}</math> | + | \end{pmatrix}</math> |
<math>\left [ A|b \right ] =\begin{bmatrix} | <math>\left [ A|b \right ] =\begin{bmatrix} | ||
| Line 74: | Line 74: | ||
1 & 0 & 1 & -3 \\ | 1 & 0 & 1 & -3 \\ | ||
1 & 1 & 0 & 1 | 1 & 1 & 0 & 1 | ||
| − | \end{bmatrix}</math> | + | \end{bmatrix}</math> |
<math>x^{\left( 2 \right)}= \begin{bmatrix} | <math>x^{\left( 2 \right)}= \begin{bmatrix} | ||
0 & 1 & -3 | 0 & 1 & -3 | ||
| − | \end{bmatrix} \text{ is BFS. } f_{2}=-15</math> | + | \end{bmatrix} \text{ is BFS. } f_{2}=-15</math> |
| − | The third basis candidate is | + | <math>\text{The third basis candidate is } \begin{pmatrix} |
a_{1} & | a_{1} & | ||
a_{3} | a_{3} | ||
| − | \end{pmatrix}</math> | + | \end{pmatrix}</math> |
<math>\left [ A|b \right ] =\begin{bmatrix} | <math>\left [ A|b \right ] =\begin{bmatrix} | ||
| Line 91: | Line 91: | ||
0 & 1 & 1 & 4 \\ | 0 & 1 & 1 & 4 \\ | ||
1 & 1 & 0 & 1 | 1 & 1 & 0 & 1 | ||
| − | \end{bmatrix}</math> | + | \end{bmatrix}</math> |
<math>x^{\left( 2 \right)}= \begin{bmatrix} | <math>x^{\left( 2 \right)}= \begin{bmatrix} | ||
1 & 0 & -5 | 1 & 0 & -5 | ||
| − | \end{bmatrix} \text{ is BFS. } f_{3}=-21</math> | + | \end{bmatrix} \text{ is BFS. } f_{3}=-21</math> |
| − | <math>\because f_{1}>f_{2}>f_{3}</math> | + | <math>\because f_{1}>f_{2}>f_{3}</math> |
<math>\therefore \text{The optimal solution is } x^{*}=\begin{bmatrix} | <math>\therefore \text{The optimal solution is } x^{*}=\begin{bmatrix} | ||
-3 & 4 & 0 | -3 & 4 & 0 | ||
| − | \end{bmatrix} \text{ with objective value } -9</math> | + | \end{bmatrix} \text{ with objective value } -9</math> |
| − | + | ||
| + | <br> | ||
---- | ---- | ||
Revision as of 14:45, 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 $
$ \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:} $
$ \text{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 $
