Answer to Question #218929 in Operations Research for ANU

Question

Use dual Simplex method to solve the following LPP.

Max Z= -3X1-2X2

Subject to x1+x2>1

X1+X2<7

X1+2X2>10

X2<3

X1,X2>0

Answer 1

Solution.

Finding the optimal plan for a linear programming problem using the simplex method:

$$Z=-3x_1-2x_2\to max,\newline \begin{Bmatrix} x_1+x_2>1 \\ x_1+x_2<7\\ x_1+2x_2>10\\ x_2<3 \end{Bmatrix}.$$

We transform inequalities into equalities by adding non-negative variables:

$Z=-3x_1-2x_2+0x_3+0x_4+0x_5+0x_6\to max,\newline \begin{Bmatrix} 1 x_1+1x_2-1x_3+0x_4+0x_5+0x_6=1 \\ 1 x_1+1x_2+0x_3+1x_4+0x_5+0x_6=7\\ 1x_1+2x_2+0x_3+0x_4-1x_5+0x_6=10\\ 0x_1+1x_2+0x_3+0x_4+0x_5+1x_6=3 \end{Bmatrix}.,\newline x_i\geq 0.$

Since the number of basis vectors should be 4, we add artificial variables, and add these variables multiplied by −M to the objective function, where M is a very large number:

$Z=-3x_1-2x_2+0x_3+0x_4+0x_5+0x_6-Mx_7-Mx_8\to max,\newline \begin{Bmatrix} 1 x_1+1x_2-1x_3+0x_4+0x_5+0x_6+1x_7+0x_8=1 \\ 1 x_1+1x_2+0x_3+1x_4+0x_5+0x_6+0x_7+0x_8=7\\ 1x_1+2x_2+0x_3+0x_4-1x_5+0x_6+0x_7+1x_8=10\\ 0x_1+1x_2+0x_3+0x_4+0x_5+1x_6+0x_7+0x_8=3 \end{Bmatrix}\newline x_i\geq 0.$

Making a simplex table. Column x ₀ records the right side of the constraints. On the right side, the matrix of coefficients A is written . The last two lines are the objective function multiplied by −1 and split in two. The last line is a line with artificial variables:

The base vectors are x ₇ , x ₄ , x ₈ , x ₆ , therefore all elements in columns x ₇ , x ₄ , x ₈ , x ₆ below the horizontal line must be zero.

Zero all the elements in column x ₇ , except for the pivot . To do this, add line 6 with line 1 multiplied by -1. Zero all the elements in column x ₈ except the pivot . To do this, add line 6 with line 3 multiplied by -1.

The simplex table will look like this:

Step 1

Let's write down the current baseline plan:

$X=\begin{pmatrix} 0& 0&0&7&0&3&1&10 \\ \end{pmatrix}$

This baseline plan is not optimal because there are negative elements at the intersection of row 6 and columns x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , x ₆ . The largest negative element in absolute value ( -3 ), therefore the vector x ₂ is included in the basis . Determine which vector leaves the basis. To do this, calculate min ( a _{i , 0} / a _{i , 2} ), for a _{i , 2} > 0, i = min(1: 1, 7: 1, 10: 2, 3: 1) = 1 corresponds to row 1. Vector x ₇ emerges from the basis . Let's make a Gaussian elimination for column x ₂ , given that the pivot corresponds to row 1. Zero all the elements of this column, except for the pivot. To do this, add rows 2, 3, 4, 5, 6 with row 1 multiplied by -1, -2, -1, -2, 3, respectively.

The simplex table will look like this:

Step 2

Let's write down the current baseline plan:

$X=\begin{pmatrix} 0& 1&0&6&0&2&0&8 \\ \end{pmatrix}$

This baseline plan is not optimal because there are negative elements at the intersection of row 6 and columns x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , x ₆ . The largest negative element in absolute value ( -2 ), therefore, the vector x ₃ is included in the basis . Determine which vector leaves the basis. To do this, calculate min ( a _{i , 0} / a _{i , 3} ), for a _{i , 3} > 0, i = 1, ... 4.min (6: 1, 8: 2, 2: 1) = 2 corresponds to line 4. Vector x ₆ emerges from the basis . Let's make a Gaussian elimination for column x ₃ , given that the pivot corresponds to row 4. Zero all the elements of this column, except for the pivot. To do this, add rows 1, 2, 3, 5, 6 with row 4 multiplied by 1, -1, -2, -2, 2, respectively.

The simplex table will look like this:

Step 3

Let's write down the current baseline plan:

$X=\begin{pmatrix} 0& 3&2&4&0&0&0&4 \\ \end{pmatrix}$

This baseline plan is not optimal because there are negative elements at the intersection of row 6 and columns x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , x ₆ . The largest negative element in absolute value ( -1 ), therefore, the vector x ₁ is included in the basis . Determine which vector leaves the basis. To do this, calculate min ( a _{i , 0} / a _{i , 1} ), for a _{i , 1} > 0, i = 1, ... 4.min (4: 1, 4: 1) = 4 corresponds to line 2. Vector x ₄ emerges from the basis . Let's make a Gaussian elimination for column x ₁ , given that the pivot corresponds to row 2. Zero all the elements of this column, except for the pivot. To do this, add rows 3, 4, 5, 6 with row 2 multiplied by -1, 1, -3, 1, respectively.

The simplex table will look like this:

Step 4

Let's write down the current baseline plan:

$X=\begin{pmatrix} 4& 3&6&0&0&0&0&0 \\ \end{pmatrix}$

The current baseline plan is optimal because line ₆ contains no negative elements under the variables x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , x ₆ . In line 5 there are no negative elements, and if there are such and there is a positive number in this column in line 6, then this column does not participate in the iteration.

The solution to the canonical problem without artificial variables can be written as follows:

$X_0^*=\begin{pmatrix} 4& 3&6&0&0&0&0&0\\ \end{pmatrix}.$

Solution to the original problem:

$X^*=\begin{pmatrix} 4 & 3 \end{pmatrix},$

or $x_1=4,x_2=3.$

The value of the objective function at the optimal point:

$F=-3*4-2*3=-18.$

Answer. -18.