| Line 17: | Line 17: | ||
<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 35: | Line 35: | ||
0 & 1 & -\frac{1}{2} & \frac{1}{2} & 2 \\ | 0 & 1 & -\frac{1}{2} & \frac{1}{2} & 2 \\ | ||
0 & 0 & 0 & 1 & 6 | 0 & 0 & 0 & 1 & 6 | ||
| − | \end{matrix} | + | \end{matrix}</math> |
| − | + | ||
| − | + | ||
| + | <math>\Rightarrow x_{1}=4, x_{2}=2, \text{the maximum value } x_{1}+x_{2}=6</math> | ||
| + | <br> | ||
---- | ---- | ||
| Line 77: | Line 77: | ||
0 & 1 & -\frac{1}{2} & \frac{1}{2} & 2 \\ | 0 & 1 & -\frac{1}{2} & \frac{1}{2} & 2 \\ | ||
0 & 0 & 0 & 1 & 6 | 0 & 0 & 0 & 1 & 6 | ||
| − | \end{matrix}</math> | + | \end{matrix}</math><font color="#ff0000"><br></font> |
| − | <font color="#ff0000" | + | <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> | + | <math>\text{The maximum value for } x_{2} + x_{2} \text{ is } 6</math><br> |
| − | |||
| − | |||
---- | ---- | ||
Revision as of 11:59, 27 June 2012
ECE Ph.D. Qualifying Exam: Automatic Control (AC)- Question 3, August 2011
$ \color{blue}\text{2. } \left( \text{20 pts} \right) \text{ Use the simplex method to solve the problem, } $
maximizex1 + x2
$ \text{subject to } x_{1}-x_{2}\leq2 $
$ x_{1}+x_{2}\leq6 $
$ x_{1},-x_{2}\geq0. $
$ \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} & a_{1} & a_{2} & a_{3} & a_{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} $
$ \text{The maximum value for } x_{2} + x_{2} \text{ is } 6 $
