Answer to Question #96163 in Operations Research for Gamaliel Negron

Question #96163
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
1
Expert's answer
2019-10-09T13:18:44-0400

"Z=-x_1+2x_2+x_3\\\\\n\\begin{cases} 3x_2+x_3\\le120 \\\\\n x_1-x_2-4x_3\\le80\\\\\n -3x_1+x_2+2x_3\\le100\n\\end{cases}\\\\\nx_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\\\\\n\\begin{cases} 0x_1+3x_2+1x_3+1x_4+0x_5+0x_6=120 \\\\\n 1 x_1-1x_2-4x_3+0x_4+1x_5+0x_6=80\\\\\n -3x_1+1x_2+2x_3+0x_4+0x_5+1x_6=100\n\\end{cases}\\\\"

write data to the matrix

"\\def\\arraystretch{1.5}\n \\begin{array}{c|c|c|c|c|c|c|}\n X & x_1 & x_2 &x_3&x_4 &x_5&x_6&x^*\\\\ \\hline\n x_4 & 0 & 3& 1&1&0&0&120 \\\\\n \\hline\nx_5 & 1& -1&-4&0&1&0&80\\\\\n\\hline\nx_6 & -3&1&2&0&0&1&100\\\\\n\\hline\nZ&1&-2&-1&0&0&0&0\\\\\n\\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}\n \\begin{array}{c|c|c|c|c|c|c|}\n X & x_1 & x_2 &x_3&x_4 &x_5&x_6&x^*\\\\ \\hline\n x_2 & 0 & 1& 1\/3&1\/3&0&0&40 \\\\\n \\hline\nx_5 & 1& 0&-11\/3&1\/3&1&0&120\\\\\n\\hline\nx_6 & -3&0&5\/3&-1\/3&0&1&60\\\\\n\\hline\nZ&1&0&-1\/3&2\/3&0&0&80\\\\\n\\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}\n \\begin{array}{c|c|c|c|c|c|c|}\n X & x_1 & x_2 &x_3&x_4 &x_5&x_6&x^*\\\\ \\hline\n x_2 & 3\/5 & 1& 0&2\/5&0&-1\/5&28 \\\\\n \\hline\nx_5 & -28\/5& 0&0&-2\/5&1&11\/5&252\\\\\n\\hline\nx_3 &-9\/5&0&1&-1\/5&0&3\/5&36\\\\\n\\hline\nZ&2\/5&0&0&3\/5&0&1\/5&92\\\\\n\\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\\\\\nZ=-1*0+2*28+1*36=92" .

Answer:92


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS