Line 9: Line 9:
 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="texhtml">maximize''x''<sub>1</sub> + ''x''<sub>2</sub></span>  
 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<span class="texhtml">maximize''x''<sub>1</sub> + ''x''<sub>2</sub></span>  
  
−
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<math>\text{subject to  }  x_{1}-x_{2}\leq2</math><font color="#ff0000" face="serif" size="4"><br></font>'''&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<math>x_{1}+x_{2}\leq6</math>''' &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;
+
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<math>\text{subject to  }  x_{1}-x_{2}\leq2</math><font color="#ff0000" face="serif" size="4"><br></font>'''&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<math>x_{1}+x_{2}\leq6</math>''' &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;  
  
 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<math>x_{1},-x_{2}\geq0.</math>  
 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<math>x_{1},-x_{2}\geq0.</math>  
Line 15: Line 15:
 
===== <math>\color{blue}\text{Solution 1:}</math>  =====
 
===== <math>\color{blue}\text{Solution 1:}</math>  =====
  
−
<span class="texhtml">Get standard form for simplex method &nbsp; &nbsp;&nbsp;''m''''i''''n'' − ''x''<sub>1</sub> − ''x''<sub>2</sub></span>  
+
<span class="texhtml">&nbsp; &nbsp;min&nbsp;''&nbsp;&nbsp;'' − ''x''<sub>1</sub> − ''x''<sub>2</sub></span>&nbsp;<br> <span class="texhtml">&nbsp; &nbsp;subject to &nbsp; &nbsp;''x''<sub>1</sub> − ''x''<sub>2</sub> + ''x''<sub>3</sub> = 2</span>&nbsp;<br> <span class="texhtml">''&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>4</sub> = 6</span>&nbsp;
  
−
<span class="texhtml">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; subject to  ''x''<sub>1</sub> − ''x''<sub>2</sub> + ''x''<sub>3</sub> = 2</span>  
+
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<math>x_{1},x_{2},x_{3},x_{4}\geq 0</math>
  
−
<span class="texhtml">''&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>4</sub> = 6</span>  
+
<math>\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}</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 &nbsp; min&nbsp;''&nbsp;&nbsp;'' − ''x''<sub>1</sub> − ''x''<sub>2</sub></span>
 +
 
 +
<span class="texhtml">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;subject to &nbsp; &nbsp;''x''<sub>1</sub> − ''x''<sub>2</sub> + ''x''<sub>3</sub> = 2</span>  
  
−
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;<math>x_{i}\geq0    i=1,2,3,4</math><br>  
+
<span class="texhtml">''&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>4</sub> = 6</span>  
  
 +
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;<math>x_{i}\geq0    i=1,2,3,4</math><br>
  
 +
<br>
  
 
<math>\begin{matrix}
 
<math>\begin{matrix}
Line 49: Line 79:
 
\end{matrix}</math>  
 
\end{matrix}</math>  
  
−
<font color="#ff0000"><span style="font-size: 17px;">'''
+
<font color="#ff0000"><span style="font-size: 17px;" /></font>  
−
'''</span></font>
+
  
−
<math>\therefore \text{the optimal solution to the original problem is } x^{*}= \left[ \begin{bmatrix} 4\\ 2 \end{bmatrix} \right]</math>
+
<math>\therefore \text{the optimal solution to the original problem is } x^{*}= \begin{bmatrix} 4\\ 2 \end{bmatrix}</math>  
  
−
<math>\text{The maximum value for } x_{2} + x_{2} − 2 \text{ is }6</math><font face="serif"><br></font>
+
<font face="serif" color="#ff0000" style="font-size: 17px;">''''''Failed to parse (lexing error): \text{The maximum value for } x_{2} + x_{2} − 2 \text{ is } 6''' <br>'''</font>  
  
 
<br>  
 
<br>  

Revision as of 11:58, 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} $

<span style="font-size: 17px;" />

$ \therefore \text{the optimal solution to the original problem is } x^{*}= \begin{bmatrix} 4\\ 2 \end{bmatrix} $

'Failed to parse (lexing error): \text{The maximum value for } x_{2} + x_{2} − 2 \text{ is } 6'


Back to ECE Qualifying Exams (QE) page

Retrieved from "https://www.projectrhea.org/rhea/index.php?title=ECE-QE_AC3-2011_solusion-2&oldid=51689"
Shortcuts
Help Main Wiki Page Random Page Special Pages Log in
Search

Alumni Liaison

has a message for current ECE438 students.

Sean Hu, ECE PhD 2009