| (27 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| − | + | [[Category:ECE]] | |
| + | [[Category:QE]] | ||
| + | [[Category:CNSIP]] | ||
| + | [[Category:problem solving]] | ||
| + | [[Category:automatic control]] | ||
| + | [[Category:optimization]] | ||
| + | |||
| + | = [[ECE PhD Qualifying Exams|ECE Ph.D. Qualifying Exam]] in "Automatic Control" (AC) = | ||
| + | |||
| + | = [[ECE-QE_AC3-2011|Question 3, August 2011]], Part 3 = | ||
| − | + | :[[ECE-QE AC3-2011 solusion-1|Part 1]],[[ECE-QE AC3-2011 solusion-2|2]],[[ECE-QE_AC3-2011_solusion-3|3]],[[ECE-QE AC3-2011 solusion-4|4]],[[ECE-QE AC3-2011 solusion-5|5]] | |
---- | ---- | ||
| Line 9: | Line 18: | ||
<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> | ||
| Line 15: | Line 24: | ||
<math>x_{1} \text{ free, } x_{2}\geq0, x_{3}\leq0.</math> | <math>x_{1} \text{ free, } x_{2}\geq0, x_{3}\leq0.</math> | ||
| − | + | ---- | |
| + | |||
| + | '''Theorem:''' | ||
| + | |||
| + | The '''Fundamental Theorem of Linear Programming''' that one of the basic feasible solutions is an optimal solution. | ||
| + | |||
| + | ---- | ||
| + | |||
| + | <math>\color{blue}\text{Solution 1:}</math> | ||
| − | <math>\Rightarrow x_{1}=5-2x_{2}+x_{3}=3-\frac{3}{2}x_{2}+\frac{1}{2}x_{3}</math> | + | <math>\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}</math> | ||
<math>\Rightarrow x_{2}-x_{3}=4</math> | <math>\Rightarrow x_{2}-x_{3}=4</math> | ||
| − | It is equivalent to | + | <span class="texhtml">It is equivalent to min ''x''<sub>1</sub> + 3''x''<sub>2</sub> − 4''x''<sub>3</sub> = 5 − 2''x''<sub>2</sub> + ''x''<sub>3</sub> + 3''x''<sub>2</sub> − 4''x''<sub>3</sub> = ''x''<sub>2</sub> − 3''x''<sub>3</sub> + 5,</span> |
| − | =5 | + | |
| − | <math>x_{2} | + | <math>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>\color{green} \text{constrain: } x_{3}\leq0 \Rightarrow x_{3}=0</math> | |
| − | Equality is satisfied when | + | <math>\text{Equivalently, } -x_{1}-3x_{2}+4x_{3}\leq-9</math> |
| + | |||
| + | <math>\text{Equality is satisfied when } x_{3}=0, x_{2} =4+0=4, x_{1}=5-2\times4=-3</math> | ||
<math>\Rightarrow \left\{\begin{matrix} | <math>\Rightarrow \left\{\begin{matrix} | ||
| Line 34: | Line 55: | ||
x_{2}=4\\ | x_{2}=4\\ | ||
x_{3}=0 | x_{3}=0 | ||
| − | \end{matrix}\right.</math> | + | \end{matrix}\right.</math> <math>\color{green} \text{The answer is correct.}</math> |
| + | |||
| + | <math>\color{green} \text{But, this solution is NOT using the Fundamental Theorem of LP.}</math> | ||
---- | ---- | ||
| − | <math>\color{blue}\text{Solution 2:}</math> | + | <math>\color{blue}\text{Solution 2:}</math> |
| − | The equality constraints can be represented in the form | + | One of the basic feasible solution is an optimal solution.<br><font face="serif"></font><span class="texhtml">The equality constraints can be represented in the form ''A'''x'''''<b> = ''b'',</b></span> |
| + | |||
| + | <math>A=\begin{bmatrix} | ||
| + | 1 & 2 & -1\\ | ||
| + | 2 & 3 & -1 | ||
| + | \end{bmatrix}=\begin{bmatrix} | ||
a_{1}& | a_{1}& | ||
a_{2}& | a_{2}& | ||
a_{3} | a_{3} | ||
| − | \end{bmatrix}</math> | + | \end{bmatrix}; b=\begin{bmatrix} |
| + | 5\\ | ||
| + | 6 | ||
| + | \end{bmatrix}</math> | ||
| − | The | + | <math>\text{The first 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} |
1 & 2 & -1 & 5 \\ | 1 & 2 & -1 & 5 \\ | ||
2 & 3 & -1 & 6 | 2 & 3 & -1 & 6 | ||
| Line 57: | Line 88: | ||
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}^{T} \text{ is a 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} |
1 & 2 & -1 & 5 \\ | 1 & 2 & -1 & 5 \\ | ||
2 & 3 & -1 & 6 | 2 & 3 & -1 & 6 | ||
| Line 74: | Line 105: | ||
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}^{T} \text{ is a 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} |
1 & 2 & -1 & 5 \\ | 1 & 2 & -1 & 5 \\ | ||
2 & 3 & -1 & 6 | 2 & 3 & -1 & 6 | ||
| Line 91: | Line 122: | ||
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}^{T} \text{ is a BFS. } f_{3}=-21</math> |
| − | <math>\because f_{1}>f_{2}>f_{3}</math> | + | <math>\because f_{1}>f_{2}>f_{3} \text{ , where } f_{1}=-9 \text{ is maximal.}</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> |
| + | <math>\color{green} \text{This solution use the Fundamental Theorem of Linear Programming. }</math> | ||
| + | <math>\color{green} \text{All possible basic feasible solutions are generated }</math> | ||
| + | |||
| + | <math>\color{green} \text{ and from which the optimal one is selected.}</math> | ||
---- | ---- | ||
| − | [[ECE | + | <math>\color{blue} \text{Related Problem: Solve the following linear programming problem,}</math> |
| + | |||
| + | minimize <span class="texhtml">3''x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>3</sub></span> | ||
| + | |||
| + | subject to <span class="texhtml">''x''<sub>1</sub> + ''x''<sub>3</sub> = 4</span> | ||
| + | |||
| + | <span class="texhtml">''x''<sub>2</sub> − ''x''<sub>3</sub> = 2</span> | ||
| + | |||
| + | <math>x_{1}\geq0,x_{2}\geq0,x_{3}\geq0,</math> | ||
| + | |||
| + | <math>\color{blue}\text{Solution :}</math> | ||
| + | |||
| + | <span class="texhtml">The equality constraints can be represented in the form ''A'''x'''''<b> = ''b'',</b></span>'''<br> ''' | ||
| + | |||
| + | <math>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}</math> | ||
| + | |||
| + | <math>\text{The first basis candidate is } \begin{pmatrix} | ||
| + | a_{1} & | ||
| + | a_{2} | ||
| + | \end{pmatrix}</math><br> | ||
| + | |||
| + | <math>\text{The corresponding basic solution is } x^{\left( 1 \right)}= \begin{bmatrix} | ||
| + | 4 & 2 & 0 | ||
| + | \end{bmatrix}^{T} \text{ is a BFS.}</math><br> | ||
| + | |||
| + | <span class="texhtml">The objective function value is ''f''<sub>1</sub> = 14</span> | ||
| + | |||
| + | <math>\text{The second basis candidate is } \begin{pmatrix} | ||
| + | a_{1} & | ||
| + | a_{3} | ||
| + | \end{pmatrix}</math><br> | ||
| + | |||
| + | <math>\text{The corresponding basic solution is } x^{\left( 2 \right)}= \begin{bmatrix} | ||
| + | 6 & 0 & -2 | ||
| + | \end{bmatrix}^{T} \text{, which is NOT a BFS.}</math> | ||
| + | |||
| + | <math>\text{The third basis candidate is } \begin{pmatrix} | ||
| + | a_{2} & | ||
| + | a_{3} | ||
| + | \end{pmatrix}</math> | ||
| + | |||
| + | <math>\text{The corresponding basic solution is } x^{\left( 3 \right)}= \begin{bmatrix} | ||
| + | 0 & 6 & 4 | ||
| + | \end{bmatrix}^{T} \text{, which is a BFS.}</math> | ||
| + | |||
| + | <span class="texhtml">The objective function value is ''f''<sub>3</sub> = 10</span> | ||
| + | |||
| + | <font color="#ff0000"><span style="font-size: 17px;">'''<math>\therefore \text{ the optimal solution is } x^{ * }= \begin{bmatrix} 0 & 6 & 4 \end{bmatrix}^{T}</math>'''</span></font> | ||
| + | |||
| + | <br> | ||
| + | |||
| + | ---- | ||
| + | |||
| + | Automatic Control (AC)- Question 3, August 2011 | ||
| + | |||
| + | Go to | ||
| + | |||
| + | *Problem 1: [[ECE-QE AC3-2011 solusion-1|solutions and discussions]] | ||
| + | *Problem 2: [[ECE-QE AC3-2011 solusion-2|solutions and discussions]] | ||
| + | *Problem 3: [[ECE-QE_AC3-2011_solusion-3|solutions and discussions]] | ||
| + | *Problem 4: [[ECE-QE AC3-2011 solusion-4|solutions and discussions]] | ||
| + | *Problem 5: [[ECE-QE AC3-2011 solusion-5|solutions and discussions]] | ||
| + | |||
| + | ---- | ||
| − | [[ | + | <br> [[ECE PhD Qualifying Exams|Back to ECE Qualifying Exams (QE) page]] |
Latest revision as of 09:10, 13 September 2013
ECE Ph.D. Qualifying Exam in "Automatic Control" (AC)
Question 3, August 2011, Part 3
$ \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. $
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 x1 + 3x2 − 4x3 = 5 − 2x2 + x3 + 3x2 − 4x3 = x2 − 3x3 + 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 3x1 + x2 + x3
subject to x1 + x3 = 4
x2 − x3 = 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 f1 = 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 f3 = 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
