单纯形法求解maxz=4X1+3X2+6X3S.T.3X1+X2+3X3≤30；2X1+2X2+3X3≤40；X1,X2,X3≥0

Question

单纯形法求解 max z =4X1+3X2+6X3 S.T.3X1+X2+3X3≤30；2X1+2X2+3X3≤40；X1,X2,X3≥0

Answer 1

3x1+x2+3x3≤30 (1')
2x1+2x2+3x3≤40 (2')
x1≥0 (3')
x2≥0 (4')
x3≥0 (5')
3x1+x2+3x3=30 (1)
2x1+2x2+3x3=40 (2)
x1=0 (3)
x2=0 (4)
x3=0 (5)
case 1:
from (1) ,(2), (3), x1=0
x2 +3x3=30
2x2+3x3=40
x2 =10, x3= 20/3
satisfy (4') and (5')
(x1,x2,x3) = (0,10, 20/3)
z =4x1+3x2+6x3
=30+40
=70
case 2:
from (1) ,(2), (4), x2=0
3x1+3x3=30
2x1+3x3=40
x1 =-10, does not satisfy (3')
rejected case 2
case 3:
from (1) ,(2), (5), x3=0
3x1+x2=30
2x1+2x2=40
x1=5, x2=15
satisfy (3') and (4')
(x1,x2,x3) = (5,15, 0)
z =4x1+3x2+6x3
=20+45
=65
case 4:
from (1) ,(3), (4), x1=x2=0
3x1+x2+3x3=30
x3=10
2x1+2x2+3x3≤40 (2')
satisfy (2') and (5')
(x1,x2,x3) = (0,0, 10)
z =4x1+3x2+6x3
=60
case 5:
from (1) ,(3), (5), x1=x3=0
3x1+x2+3x3=30
x2=30
2x1+2x2+3x3≤40 (2')
does not satisfy (2')
rejected case 5
case 6:
from (1) ,(4), (5), x2=x3=0
3x1+x2+3x3=30
x1=10
2x1+2x2+3x3≤40 (2')
satisfy (2') and (3')
(x1,x2,x3) = (10,0, 0)
z =4x1+3x2+6x3
=40
case 7:
from (2) ,(3), (4), x1=x2=0
2x1+2x2+3x3=40
x3=40/3
3x1+x2+3x3≤30 (1')
does not satisfy (1')
rejected case 7
case 8:
from (2) ,(3), (5), x1=x3=0
2x1+2x2+3x3=40
x2=20
3x1+x2+3x3≤30 (1')
satisfy (1') and (4')
(x1,x2,x3) = ( 0,20,0)
z =4x1+3x2+6x3
=60
case 9:
from (2) ,(4), (5), x2=x3=0
2x1+2x2+3x3=40
x1=20
3x1+x2+3x3≤30 (1')
does not satisfy (1')
rejected case 9
ie max z = case 1=70