(8 intermediate revisions by one other user not shown)
Line 1: Line 1:
−
 
+
[[Category:ECE]]
 +
[[Category:QE]]
 +
[[Category:CNSIP]]
 +
[[Category:problem solving]]
 +
[[Category:automatic control]]
 +
[[Category:optimization]]
  
 
=QE2012_AC-3_ECE580-4=
 
=QE2012_AC-3_ECE580-4=
  
 +
:[[QE2012_AC-3_ECE580-1|Part 1]],[[QE2012_AC-3_ECE580-2|2]],[[QE2012_AC-3_ECE580-3|3]],[[QE2012_AC-3_ECE580-4|4]],[[QE2012_AC-3_ECE580-5|5]]
 +
 +
<br> Solution:
 +
 +
        We can transfer the problem to the following standard form:
 +
        <span class="texhtml">''Mnimize''</span>'''    <span class="texhtml"> − ''x''<sub>1</sub> − 2''x''<sub>2</sub></span>'''
 +
        <span class="texhtml">''Sbject to''</span>'''    <span class="texhtml"> − 2''x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>3</sub> = 2</span>'''
 +
                        <span class="texhtml"> − ''x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>4</sub> = 3</span>
 +
                        <span class="texhtml">''x''<sub>1</sub> + ''x''<sub>5</sub> = 3</span>
 +
                        <math>x_1, x_2, x_3, x_4, x_5 \ge 0.</math>
 +
 +
        We form the corresponding tableau for the problem
 +
      <math>\begin{matrix}
 +
  a_1 & a_2 & a_3 & a_4 & a_5 & b \\
 +
  -2 & 1& 1 &0& 0& 2 \\
 +
  -1& 1& 0 &1 &0 &3\\
 +
  1 &0& 0& 0& 1& 3\\
 +
  -1& -2 &0& 0& 0& 0
 +
\end{matrix}</math>
 +
     
 +
Since it is already in canonical form. Because <span class="texhtml">''r''<sub>2</sub> =  − 7</span>, we bring <span class="texhtml">''a''<sub>2</sub></span> into the basis.
 +
 +
      After computing the ratios, we pivot about the (1,2) element of the tableau to obtain
 +
      <math>\begin{matrix}
 +
  a_1 & a_2 & a_3 & a_4 & a_5 & b \\
 +
  -2 & 1& 1 &0& 0& 2 \\
 +
  1& 0& -1 &1 &0 &1\\
 +
  1 &0& 0& 0& 1& 3\\
 +
  -5& 0 &2& 0& 0& 4
 +
\end{matrix}</math>
 +
 +
      Similarly, we pivot about the (2,1) element to obtain
 +
      <math>\begin{matrix}
 +
  a_1 & a_2 & a_3 & a_4 & a_5 & b \\
 +
  0 & 1& -1 &2& 0& 4 \\
 +
  1& 0& -1 &1 &0 &1\\
 +
  0 &0& 1& -1& 1& 2\\
 +
  0& 0 &-3& 5& 0& 9
 +
\end{matrix}</math>
 +
 +
      Similarly, we pivot about the (3,3) element to obtain
 +
      <math>\begin{matrix}
 +
  a_1 & a_2 & a_3 & a_4 & a_5 & b \\
 +
  0 & 1& 0 &1& 1& 6 \\
 +
  1& 0& 0 &0 &1 &3\\
 +
  0 &0& 1& -1& 1& 2\\
 +
  0& 0 &0& 2& 3& 15
 +
\end{matrix}</math>
 +
 +
      Therefore, <span class="texhtml">''x''<sub>1</sub> = 3,</span> <span class="texhtml">''x''<sub>2</sub> = 6,</span> maximize the function.
 +
 +
Solution 2:
 +
 +
The standard form for this problem is
 +
        <span class="texhtml">''Mnimize''</span>'''    <span class="texhtml"> − ''x''<sub>1</sub> − 2''x''<sub>2</sub></span>'''
 +
        <span class="texhtml">''Sbject to''</span>'''    <span class="texhtml"> − 2''x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>3</sub> = 2</span>'''
 +
                        <span class="texhtml"> − ''x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>4</sub> = 3</span>
 +
                        <span class="texhtml">''x''<sub>1</sub> + ''x''<sub>5</sub> = 3</span>
 +
                        <math>x_1, x_2, x_3, x_4, x_5 \ge 0.</math>
 +
 +
<math>\begin{matrix}
 +
  a_1 & a_2 & a_3 & a_4 & a_5 & b \\
 +
  -2 & 1& 1 &0& 0& 2 \\
 +
  -1& 1& 0 &1 &0 &3\\
 +
  1 &0& 0& 0& 1& 3\\
 +
  -1& -2 &0& 0& 0& 0
 +
\end{matrix}\Rightarrow
 +
 +
\begin{matrix}
 +
  a_1 & a_2 & a_3 & a_4 & a_5 & b \\
 +
  -2 & 1& 1 &0& 0& 2 \\
 +
  1& 0& -1 &1 &0 &1\\
 +
  1 &0& 0& 0& 1& 3\\
 +
  -5& 0 &2& 0& 0& 4
 +
\end{matrix}
 +
\Rightarrow
 +
\begin{matrix}
 +
  a_1 & a_2 & a_3 & a_4 & a_5 & b \\
 +
  0 & 1& -1 &2& 0& 4 \\
 +
  1& 0& -1 &1 &0 &1\\
 +
  0 &0& 1& -1& 1& 2\\
 +
  0& 0 &-3& 5& 0& 9
 +
\end{matrix}
 +
\Rightarrow
 +
\begin{matrix}
 +
  a_1 & a_2 & a_3 & a_4 & a_5 & b \\
 +
  0 & 1& 0 &1& 1& 6 \\
 +
  1& 0& 0 &0 &1 &3\\
 +
  0 &0& 1& -1& 1& 2\\
 +
  0& 0 &0& 2& 3& 15
 +
\end{matrix}</math>
 +
 +
From the last tableau, we can see that <math>\begin{bmatrix}
 +
  x^{1} = 3\\ x^{2} = 6 
 +
\end{bmatrix}</math>
 +
maximizes the object function. The maximum value is 15
 +
 +
<font color="#0000FF "><span style="font-size: 19px;">
 +
<math>\color{blue}
 +
\text{ It should be noted that, }
 +
\begin{bmatrix}
 +
  x^{1} = 3\\ x^{2} = 6 
 +
\end{bmatrix} \text{actually minimizes the standard form,}
 +
</math>
 +
<math>\color{blue}
 +
\text{which equivalently maximizes the original problem}
 +
</math>
 +
</span></font>
 +
 +
 +
----
 +
----
 +
<font face="serif"></font><math>\color{blue}\text{Related Problem: }</math>
 +
 +
Use any simplex method to solve the following linear program. '''
  
 +
            <span class="texhtml">''Maximize''</span>'''    <span class="texhtml">''7x''<sub>1</sub> + 6''x''<sub>2</sub></span>'''
 +
        <span class="texhtml">''Subject to''</span>'''    <math>2x_1+x_2 \le 3</math>'''
 +
                        <math>x_1+4x_2 \le 4</math>
 +
                        <math>x_1 \ge 0, x_2 \ge 0.</math>
  
−
Put your content here . . .
+
<br>
  
 +
We need to transform the problem into the standard form. The tableau is given as follows:
  
 +
<math>
 +
\begin{matrix}
 +
  a_1 & a_2 & a_3 & a_4 &  b \\
 +
  2 & 1& 1 &0& 3 \\
 +
  1& 4& 0 &1 &4\\
 +
  -7 & -6 &0& 0& 0
 +
\end{matrix}\Rightarrow
 +
\begin{matrix}
 +
  a_1 & a_2 & a_3 & a_4 &  b \\
 +
  1 & 0& 4/7 & -1/7 & 8/7 \\
 +
  0& 1& -1/7 & 2/7 & 5/7\\
 +
  0 & 0 & 22/7 & 5/7 & 86/7
 +
\end{matrix}
 +
</math>
  
 +
<math>
 +
\text{So the minimum point is}
 +
\begin{bmatrix}
 +
  x^{1} = 8/7\\ x^{2} = 5/7 
 +
\end{bmatrix}
 +
</math>
  
 
[[ QE2012 AC-3 ECE580|Back to QE2012 AC-3 ECE580]]
 
[[ QE2012 AC-3 ECE580|Back to QE2012 AC-3 ECE580]]

Latest revision as of 09:12, 13 September 2013


QE2012_AC-3_ECE580-4

Part 1,2,3,4,5


Solution: 

        We can transfer the problem to the following standard form:
        Mnimize     − x1 − 2x2
        Sbject to     − 2x1 + x2 + x3 = 2
                        − x1 + x2 + x4 = 3
                       x1 + x5 = 3
                       $ x_1, x_2, x_3, x_4, x_5 \ge 0. $

       We form the corresponding tableau for the problem
     $ \begin{matrix}   a_1 & a_2 & a_3 & a_4 & a_5 & b \\   -2 & 1& 1 &0& 0& 2 \\   -1& 1& 0 &1 &0 &3\\   1 &0& 0& 0& 1& 3\\   -1& -2 &0& 0& 0& 0  \end{matrix} $
      
Since it is already in canonical form. Because r2 =  − 7, we bring a2 into the basis.

      After computing the ratios, we pivot about the (1,2) element of the tableau to obtain
     $ \begin{matrix}   a_1 & a_2 & a_3 & a_4 & a_5 & b \\   -2 & 1& 1 &0& 0& 2 \\   1& 0& -1 &1 &0 &1\\   1 &0& 0& 0& 1& 3\\   -5& 0 &2& 0& 0& 4  \end{matrix} $

      Similarly, we pivot about the (2,1) element to obtain 
     $ \begin{matrix}   a_1 & a_2 & a_3 & a_4 & a_5 & b \\   0 & 1& -1 &2& 0& 4 \\   1& 0& -1 &1 &0 &1\\   0 &0& 1& -1& 1& 2\\   0& 0 &-3& 5& 0& 9  \end{matrix} $

      Similarly, we pivot about the (3,3) element to obtain 
     $ \begin{matrix}   a_1 & a_2 & a_3 & a_4 & a_5 & b \\   0 & 1& 0 &1& 1& 6 \\   1& 0& 0 &0 &1 &3\\   0 &0& 1& -1& 1& 2\\   0& 0 &0& 2& 3& 15  \end{matrix} $

      Therefore, x1 = 3, x2 = 6, maximize the function.

Solution 2:

The standard form for this problem is 

        Mnimize     − x1 − 2x2
        Sbject to     − 2x1 + x2 + x3 = 2
                        − x1 + x2 + x4 = 3
                       x1 + x5 = 3
                       $ x_1, x_2, x_3, x_4, x_5 \ge 0. $

$ \begin{matrix} a_1 & a_2 & a_3 & a_4 & a_5 & b \\ -2 & 1& 1 &0& 0& 2 \\ -1& 1& 0 &1 &0 &3\\ 1 &0& 0& 0& 1& 3\\ -1& -2 &0& 0& 0& 0 \end{matrix}\Rightarrow \begin{matrix} a_1 & a_2 & a_3 & a_4 & a_5 & b \\ -2 & 1& 1 &0& 0& 2 \\ 1& 0& -1 &1 &0 &1\\ 1 &0& 0& 0& 1& 3\\ -5& 0 &2& 0& 0& 4 \end{matrix} \Rightarrow \begin{matrix} a_1 & a_2 & a_3 & a_4 & a_5 & b \\ 0 & 1& -1 &2& 0& 4 \\ 1& 0& -1 &1 &0 &1\\ 0 &0& 1& -1& 1& 2\\ 0& 0 &-3& 5& 0& 9 \end{matrix} \Rightarrow \begin{matrix} a_1 & a_2 & a_3 & a_4 & a_5 & b \\ 0 & 1& 0 &1& 1& 6 \\ 1& 0& 0 &0 &1 &3\\ 0 &0& 1& -1& 1& 2\\ 0& 0 &0& 2& 3& 15 \end{matrix} $

From the last tableau, we can see that $ \begin{bmatrix} x^{1} = 3\\ x^{2} = 6 \end{bmatrix} $ maximizes the object function. The maximum value is 15

$ \color{blue} \text{ It should be noted that, } \begin{bmatrix} x^{1} = 3\\ x^{2} = 6 \end{bmatrix} \text{actually minimizes the standard form,} $ $ \color{blue} \text{which equivalently maximizes the original problem} $


$ \color{blue}\text{Related Problem: } $

Use any simplex method to solve the following linear program. 

           Maximize    7x1 + 6x2
        Subject to    $ 2x_1+x_2 \le 3 $
                       $ x_1+4x_2 \le 4 $
                       $ x_1 \ge 0, x_2 \ge 0. $


We need to transform the problem into the standard form. The tableau is given as follows:

$ \begin{matrix} a_1 & a_2 & a_3 & a_4 & b \\ 2 & 1& 1 &0& 3 \\ 1& 4& 0 &1 &4\\ -7 & -6 &0& 0& 0 \end{matrix}\Rightarrow \begin{matrix} a_1 & a_2 & a_3 & a_4 & b \\ 1 & 0& 4/7 & -1/7 & 8/7 \\ 0& 1& -1/7 & 2/7 & 5/7\\ 0 & 0 & 22/7 & 5/7 & 86/7 \end{matrix} $

$ \text{So the minimum point is} \begin{bmatrix} x^{1} = 8/7\\ x^{2} = 5/7 \end{bmatrix} $

Back to QE2012 AC-3 ECE580

Retrieved from "https://www.projectrhea.org/rhea/index.php?title=QE2012_AC-3_ECE580-4&oldid=58213"
Shortcuts
Help Main Wiki Page Random Page Special Pages Log in
Search

Alumni Liaison

Ph.D. 2007, working on developing cool imaging technologies for digital cameras, camera phones, and video surveillance cameras.

Buyue Zhang