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