QE2012_AC-3_ECE580-4
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} $
