Answer to Question #96163 in Operations Research for Gamaliel Negron

Question

Maximize Z = -x1 + 2x2 + x3
Subject To
3x2 + x3 =< 120
x1 - x2 - 4x3 =< 80
-3x1 + x2 + 2x3 =< 100
(no nongeative constraints)
A) Reformulate this problem so tha all variables have nonnegative constraints
B) Work through the simplex method step by step to solve the problem

Answer 1

$Z=-x_1+2x_2+x_3\\ \begin{cases} 3x_2+x_3\le120 \\ x_1-x_2-4x_3\le80\\ -3x_1+x_2+2x_3\le100 \end{cases}\\ x_1\ge0, x_2\ge0,x_3\ge0. \\$

To construct a system of support equations, additional conditions are used (transition to the canonical form).

In the 1st inequality of meaning ($\le$ ), we introduce the basis variable $x_4$ . In the 2nd inequality of meaning ($\le$ ), we introduce the basis variable $x_5$ . In the 3rd inequality of meaning ($\le$ ), we introduce the basis variable $x_6$ .

$Y=-x_1+2x_2+x_3+0x_4+0x_5+0x_6+0\\ \begin{cases} 0x_1+3x_2+1x_3+1x_4+0x_5+0x_6=120 \\ 1 x_1-1x_2-4x_3+0x_4+1x_5+0x_6=80\\ -3x_1+1x_2+2x_3+0x_4+0x_5+1x_6=100 \end{cases}\\$

write data to the matrix

$\def\arraystretch{1.5} \begin{array}{c|c|c|c|c|c|c|} X & x_1 & x_2 &x_3&x_4 &x_5&x_6&x^*\\ \hline x_4 & 0 & 3& 1&1&0&0&120 \\ \hline x_5 & 1& -1&-4&0&1&0&80\\ \hline x_6 & -3&1&2&0&0&1&100\\ \hline Z&1&-2&-1&0&0&0&0\\ \end{array}\Rightarrow$

As the leading element, we select the column corresponding to the variable $x_2$ , since this is the largest coefficient by the absolute value.

We calculate the values of the rows as the quotient of the division, and from them we choose the smallest:

$min(40,-,100)=40$

Therefore, the 1st row is leading.

We form the next part of the simplex table. Instead of the variable $x_4$ , the set will include the variable $x_2$ .

The row corresponding to the variable $x_2$ in set 1 is obtained by dividing all the elements of the row $x_4$ of set 0 by the resolving element. In place of the resolving element, we obtain 1. In the remaining cells of the column $x_2$ , we write zeros.

$\def\arraystretch{1.5} \begin{array}{c|c|c|c|c|c|c|} X & x_1 & x_2 &x_3&x_4 &x_5&x_6&x^*\\ \hline x_2 & 0 & 1& 1/3&1/3&0&0&40 \\ \hline x_5 & 1& 0&-11/3&1/3&1&0&120\\ \hline x_6 & -3&0&5/3&-1/3&0&1&60\\ \hline Z&1&0&-1/3&2/3&0&0&80\\ \end{array}\Rightarrow\\$

As the leading element, we choose the column corresponding to the variable $x_3$, since this is the largest coefficient by the absolute value. And we also do as earlier.

$\def\arraystretch{1.5} \begin{array}{c|c|c|c|c|c|c|} X & x_1 & x_2 &x_3&x_4 &x_5&x_6&x^*\\ \hline x_2 & 3/5 & 1& 0&2/5&0&-1/5&28 \\ \hline x_5 & -28/5& 0&0&-2/5&1&11/5&252\\ \hline x_3 &-9/5&0&1&-1/5&0&3/5&36\\ \hline Z&2/5&0&0&3/5&0&1/5&92\\ \end{array}$

Among the values of the index row there are no negative ones. Therefore, this table determines the optimal set for the task.

$x_1=0, x_2=28, x_3=36\\ Z=-1*0+2*28+1*36=92$ .

Answer:92