| (16 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 2 = | ||
| − | + | :[[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 11: | Line 20: | ||
<math>\text{subject to } x_{1}-x_{2}\leq2</math><font color="#ff0000" face="serif" size="4"><br></font>''' <math>x_{1}+x_{2}\leq6</math>''' | <math>\text{subject to } x_{1}-x_{2}\leq2</math><font color="#ff0000" face="serif" size="4"><br></font>''' <math>x_{1}+x_{2}\leq6</math>''' | ||
| − | <math>x_{1}, | + | <math>x_{1},x_{2}\geq0.</math> |
| − | ===== <math>\color{blue}\text{Solution 1:}</math> | + | ---- |
| + | |||
| + | '''Theorem: ''' | ||
| + | |||
| + | A basic feasible solution is optimal if and only if the corresponding reduced cost coefficeints are all nonnegative. | ||
| + | |||
| + | '''Simplex Method:''' | ||
| + | |||
| + | 1. Transform the given problem into standard form by introducing slack variables <span class="texhtml">''x''<sub>3</sub></span> and <span class="texhtml">''x''<sub>4</sub></span>.<span class="texhtml"><sub></sub></span> | ||
| + | |||
| + | 2. Form a canonical augmented matrix corresponding to an initial basic feasible solution. | ||
| + | |||
| + | 3. Calculate the reduced cost coefficients corresponding to the nonbasic variables. | ||
| + | |||
| + | 4. If <math>r_{j}>\geq0</math> for all <span class="texhtml">''j''</span>, stop. -- the current basic feasible solution is optimal. | ||
| + | |||
| + | 5. Select a <span class="texhtml">''q''</span> such that <span class="texhtml">''r''<sub>''q''</sub> < 0</span> | ||
| + | |||
| + | 6. If no <span class="texhtml">''y''<sub>''iq''</sub> > 0</span>, stop. -- the problem is unbounded; else, calculate ''' <math>p=argmin_{i}\left \{ y_{i0}/y_{iq}:y_{iq}>0 \right \}</math>. ''' | ||
| + | |||
| + | 7. Update the canonical augmented matrix by pivoting about the <span class="texhtml">(''p'',''q'')</span> th element. | ||
| + | |||
| + | 8. Go to step 3. | ||
| + | |||
| + | ---- | ||
| + | |||
| + | <math>\color{blue}\text{Solution 1:}</math> | ||
| − | <span class="texhtml"> min '' '' − ''x''<sub>1</sub> − ''x''<sub>2</sub></span> <br> <span class="texhtml"> subject to ''x''<sub>1</sub> − ''x''<sub>2</sub> + ''x''<sub>3</sub> = 2</span> <br> <span class="texhtml">'' x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>4</sub> = 6</span> | + | <span class="texhtml"> min '' '' − ''x''<sub>1</sub> − ''x''<sub>2</sub></span> <br> <span class="texhtml"> subject to ''x''<sub>1</sub> − ''x''<sub>2</sub> + ''x''<sub>3</sub> = 2</span> <br> <span class="texhtml">'' x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>4</sub> = 6</span> |
| − | <math>x_{1},x_{2},x_{3},x_{4}\geq 0</math> | + | <math>x_{1},x_{2},x_{3},x_{4}\geq 0</math> |
<math>\begin{matrix} | <math>\begin{matrix} | ||
| Line 37: | Line 72: | ||
\end{matrix}</math> | \end{matrix}</math> | ||
| − | <math>\Rightarrow x_{1}=4, x_{2}=2, \text{the maximum value } x_{1}+x_{2}=6</math | + | <math>\Rightarrow x_{1}=4, x_{2}=2, \text{the maximum value } x_{1}+x_{2}=6</math> |
---- | ---- | ||
| − | + | <math>\color{blue}\text{Solution 2:}</math> | |
<span class="texhtml">Get standard form for simplex method min '' '' − ''x''<sub>1</sub> − ''x''<sub>2</sub></span> | <span class="texhtml">Get standard form for simplex method min '' '' − ''x''<sub>1</sub> − ''x''<sub>2</sub></span> | ||
| Line 52: | Line 87: | ||
<math>\begin{matrix} | <math>\begin{matrix} | ||
| − | & | + | & x_{1} & x_{2} & x_{3} & x_{4} & b\\ |
& 1 & -1 & 1 & 0 & 2\\ | & 1 & -1 & 1 & 0 & 2\\ | ||
& 1 & 1 & 0 & 1 & 6 \\ | & 1 & 1 & 0 & 1 & 6 \\ | ||
| Line 77: | Line 112: | ||
<math>\therefore \text{the optimal solution to the original problem is } x^{*}= \begin{bmatrix} 4\\ 2 \end{bmatrix}</math><font face="serif" color="#ff0000" style="font-size: 17px;">'''<br>'''</font> | <math>\therefore \text{the optimal solution to the original problem is } x^{*}= \begin{bmatrix} 4\\ 2 \end{bmatrix}</math><font face="serif" color="#ff0000" style="font-size: 17px;">'''<br>'''</font> | ||
| − | The maximum value for <font face="serif"><span class="texhtml"> ''x''<sub>1</sub> + ''x''<sub>2</sub> is 6</span><br></font> | + | The maximum value for <font face="serif"><span class="texhtml"> ''x''<sub>1</sub> + ''x''<sub>2</sub> is 6.</span><br></font> |
---- | ---- | ||
| + | ---- | ||
| + | <math>\color{blue}\text{Related Problem: Solve the following problem using simplex method}</math> | ||
| − | + | max <span class="texhtml">2''x''<sub>1</sub> + 3''x''<sub>2</sub></span> | |
| + | |||
| + | subject to <math>2x_{1}+x_{2}\leq4</math> | ||
| + | |||
| + | <math>x_{1}+x_{2}\leq3</math> | ||
| + | |||
| + | <math>x_{1},x_{2}\geq0.</math> | ||
| + | |||
| + | <math>\color{blue}\text{Solution:}</math> | ||
| + | |||
| + | Transform to standard form: min <span class="texhtml"> − 2''x''<sub>1</sub> − 3''x''<sub>2</sub></span> | ||
| + | |||
| + | subject to <span class="texhtml">2''x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>3</sub> = 4</span> | ||
| + | |||
| + | <span class="texhtml">''x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>4</sub> = 3</span> | ||
| + | |||
| + | <math>x_{i}\geq0, i=1,2,3,4</math> | ||
| + | |||
| + | <math>\begin{matrix} | ||
| + | & x_{1} & x_{2} & x_{3} & x_{4} & b\\ | ||
| + | & 2 & 1 & 1 & 0 & 4\\ | ||
| + | & 1 & 1 & 0 & 1 & 3 \\ | ||
| + | c^{T} & -2 & -3 & 0 & 0 & 0 | ||
| + | \end{matrix}</math> | ||
| + | |||
| + | We have <span class="texhtml">''r''<sub>1</sub> = − 2 < 0</span> and <span class="texhtml">''r''<sub>2</sub> = − 3 < 0</span>. We introduce <span class="texhtml">''a''<sub>2</sub></span> into the new basis and pivot <span class="texhtml">''y''<sub>22</sub></span>, by calculating the ratios <span class="texhtml">''y''<sub>''i''0</sub> / ''y''<sub>''i''2</sub>,''y''<sub>''i''2</sub> > 0</span>.<sub></sub> | ||
| + | |||
| + | <math>\begin{matrix} | ||
| + | & x_{1} & x_{2} & x_{3} & x_{4} & b\\ | ||
| + | & 2 & 1 & 1 & 0 & 4\\ | ||
| + | & 1 & 1 & 0 & 1 & 3 \\ | ||
| + | c^{T} & 1 & 0 & 0 & 3 & 9 | ||
| + | \end{matrix} \Rightarrow | ||
| + | \begin{matrix} | ||
| + | & x_{1} & x_{2} & x_{3} & x_{4} & b\\ | ||
| + | & 1 & 0 & 1 & -1 & 1\\ | ||
| + | & 1 & 1 & 0 & 1 & 3 \\ | ||
| + | c^{T} & 1 & 0 & 0 & 3 & 9 | ||
| + | \end{matrix}</math> | ||
| + | |||
| + | All the reduced cost coefficients are positive, hence the optimal solution to the problem in standard form is | ||
| + | |||
| + | <math>x^{*}=\begin{bmatrix} | ||
| + | 0 & | ||
| + | 3 & | ||
| + | 1 & | ||
| + | 0 | ||
| + | \end{bmatrix}^{T}.</math> | ||
| + | |||
| + | The optimal solution to the original problem is <math>x^{*}=\begin{bmatrix} | ||
| + | 0 & | ||
| + | 3 | ||
| + | \end{bmatrix}^{T}.</math> and the optimal objective value is 9.<br> | ||
| + | |||
| + | <br> | ||
---- | ---- | ||
| − | [[ECE | + | Automatic Control (AC)- Question 3, August 2011 |
| + | |||
| + | Go to | ||
| + | |||
| + | *Part 1: [[ECE-QE AC3-2011 solusion-1|solutions and discussions]] | ||
| + | *Part 2: [[ECE-QE_AC3-2011_solusion-2|solutions and discussions]] | ||
| + | *Part 3: [[ECE-QE AC3-2011 solusion-3|solutions and discussions]] | ||
| + | *Part 4: [[ECE-QE AC3-2011 solusion-4|solutions and discussions]] | ||
| + | *Part 5: [[ECE-QE AC3-2011 solusion-5|solutions and discussions]] | ||
| + | |||
| + | ---- | ||
| − | [[ | + | [[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 2
$ \color{blue}\text{2. } \left( \text{20 pts} \right) \text{ Use the simplex method to solve the problem, } $
maximize x1 + x2
$ \text{subject to } x_{1}-x_{2}\leq2 $
$ x_{1}+x_{2}\leq6 $
$ x_{1},x_{2}\geq0. $
Theorem:
A basic feasible solution is optimal if and only if the corresponding reduced cost coefficeints are all nonnegative.
Simplex Method:
1. Transform the given problem into standard form by introducing slack variables x3 and x4.
2. Form a canonical augmented matrix corresponding to an initial basic feasible solution.
3. Calculate the reduced cost coefficients corresponding to the nonbasic variables.
4. If $ r_{j}>\geq0 $ for all j, stop. -- the current basic feasible solution is optimal.
5. Select a q such that rq < 0
6. If no yiq > 0, stop. -- the problem is unbounded; else, calculate $ p=argmin_{i}\left \{ y_{i0}/y_{iq}:y_{iq}>0 \right \} $.
7. Update the canonical augmented matrix by pivoting about the (p,q) th element.
8. Go to step 3.
$ \color{blue}\text{Solution 1:} $
min − x1 − x2
subject to x1 − x2 + x3 = 2
x1 + x2 + x4 = 6
$ x_{1},x_{2},x_{3},x_{4}\geq 0 $
$ \begin{matrix} 1 & -1 & 1 & 0 & 2\\ 1 & 1 & 0 & 1 & 6 \\ -1 & -1 & 0 & 0 & 0 \end{matrix} \Rightarrow \begin{matrix} 1 & -1 & 1 & 0 & 2\\ 0 & 2 & -1 & 1 & 4 \\ 0 & -2 & 1 & 0 & 2 \end{matrix} \Rightarrow \begin{matrix} 1 & 0 & \frac{1}{2} & \frac{1}{2} & 4\\ 0 & 1 & -\frac{1}{2} & \frac{1}{2} & 2 \\ 0 & 0 & 0 & 1 & 6 \end{matrix} $
$ \Rightarrow x_{1}=4, x_{2}=2, \text{the maximum value } x_{1}+x_{2}=6 $
$ \color{blue}\text{Solution 2:} $
Get standard form for simplex method min − x1 − x2
subject to x1 − x2 + x3 = 2
x1 + x2 + x4 = 6
$ x_{i}\geq0, i=1,2,3,4 $
$ \begin{matrix} & x_{1} & x_{2} & x_{3} & x_{4} & b\\ & 1 & -1 & 1 & 0 & 2\\ & 1 & 1 & 0 & 1 & 6 \\ c^{T} & -1 & -1 & 0 & 0 & 0 \end{matrix} $ $ \Rightarrow \begin{matrix} 1 & -1 & 1 & 0 & 2\\ 1 & 1 & 0 & 1 & 6 \\ 0 & 0 & 0 & 1 & 6 \end{matrix} \Rightarrow \begin{matrix} 1 & -1 & 1 & 0 & 2\\ 0 & 2 & -1 & 1 & 4 \\ 0 & 0 & 0 & 1 & 6 \end{matrix} \Rightarrow \begin{matrix} 1 & 0 & \frac{1}{2} & \frac{1}{2} & 4\\ 0 & 1 & -\frac{1}{2} & \frac{1}{2} & 2 \\ 0 & 0 & 0 & 1 & 6 \end{matrix} $
$ \therefore \text{the optimal solution to the original problem is } x^{*}= \begin{bmatrix} 4\\ 2 \end{bmatrix} $
The maximum value for x1 + x2 is 6.
$ \color{blue}\text{Related Problem: Solve the following problem using simplex method} $
max 2x1 + 3x2
subject to $ 2x_{1}+x_{2}\leq4 $
$ x_{1}+x_{2}\leq3 $
$ x_{1},x_{2}\geq0. $
$ \color{blue}\text{Solution:} $
Transform to standard form: min − 2x1 − 3x2
subject to 2x1 + x2 + x3 = 4
x1 + x2 + x4 = 3
$ x_{i}\geq0, i=1,2,3,4 $
$ \begin{matrix} & x_{1} & x_{2} & x_{3} & x_{4} & b\\ & 2 & 1 & 1 & 0 & 4\\ & 1 & 1 & 0 & 1 & 3 \\ c^{T} & -2 & -3 & 0 & 0 & 0 \end{matrix} $
We have r1 = − 2 < 0 and r2 = − 3 < 0. We introduce a2 into the new basis and pivot y22, by calculating the ratios yi0 / yi2,yi2 > 0.
$ \begin{matrix} & x_{1} & x_{2} & x_{3} & x_{4} & b\\ & 2 & 1 & 1 & 0 & 4\\ & 1 & 1 & 0 & 1 & 3 \\ c^{T} & 1 & 0 & 0 & 3 & 9 \end{matrix} \Rightarrow \begin{matrix} & x_{1} & x_{2} & x_{3} & x_{4} & b\\ & 1 & 0 & 1 & -1 & 1\\ & 1 & 1 & 0 & 1 & 3 \\ c^{T} & 1 & 0 & 0 & 3 & 9 \end{matrix} $
All the reduced cost coefficients are positive, hence the optimal solution to the problem in standard form is
$ x^{*}=\begin{bmatrix} 0 & 3 & 1 & 0 \end{bmatrix}^{T}. $
The optimal solution to the original problem is $ x^{*}=\begin{bmatrix} 0 & 3 \end{bmatrix}^{T}. $ and the optimal objective value is 9.
Automatic Control (AC)- Question 3, August 2011
Go to
- Part 1: solutions and discussions
- Part 2: solutions and discussions
- Part 3: solutions and discussions
- Part 4: solutions and discussions
- Part 5: solutions and discussions
