15单纯形法PPT1( 运筹学).ppt

1
§ 单纯形法
引例
maxZ=40X1 +50X2
X1 +2X2 +X3 =30
3X1 +2X2 +X4 =60
2X2 +X5 =24
X1 … X5 0
2
解:(1)、确定初始可行解
B=(P3 P4 P5)=I
Z =0 +40X1+50X2
X3 =30-( X1+ 2X2 )
X4=60-( 3X1+ 2X2)
X5 =24 -2 X2
令X1 = X2 =0
X(1) =(0, 0, 30, 60, 24)T
Z(1) =0
3
(2)、判定解是否最优
Z=0+40X1+50X2
当X1从0↗或X2从0↗
Z从0↗
∴ X(1) 不是最优解
4
(3)、由一个基可行解→另一个基可行解。
∵ 50> 40 选X2从0↗,X1 =0
X3 =30-2X2 0 X2  30/2
X4 =60-2X2 0 X2  60/2
X5 =24-2X2 0 X2  24/2
X2=min(30/2 , 60/2 , 24/2 ) =12
X2进基变量, X5出基变量。
5
B2=(P3 P4 P2)
Z=0+40X1+50X2 ④
X3 +2X2 =30-X1 ①
X4+2X2 =60-3X1 ②
2X2=24-X5 ③
6
③× 1/2 ,③代入④式, ①-③,②-③
Z=600 +40X1 -25X5
X3 =6 -X1 +X5
X4 = 36-3X1 +X5
X2=12 -1/2X5
令X1 =X5 =0 X(2) =(0, 12, 6, 36, 0)T
Z(2) =600
7
(2)' 判断
∵ 40>0 ∴ X(2)不是。
(3)' 选X1从0↗, X5 =0
X3= 6- X1 0
X4= 36-3X1 0
X2=12 0
X1=min( 6/1 , 36/3 ) =6
X1进基, X3出基。
8
B3 =(P1 P4 P2 )
Z=840-40X3+15X5
X1=6 - X3 + X5
X4= 18+3X3 - 2X5
X2=12 -1/2X5
令X3 =X5 =0
X(3) =(6, 12, 0, 18, 0)T
Z(3) =840
9
(2)" ∵ 15>0 ∴ X(3)不是
(3)" 选X5从0↗, X3 =0
X1=6 +X5 0
X4= 18 -2X5 0
X2=12-1/2 X5 0
X5=min( 18/2 , 12/1/2 ) =9
X5进基, X4出基。
10
B4=(P1 P5 P2 )
Z=975- 35/2X3 - 15/2X4
X1= 15 + 1/2X3 - 1/2X4
X5= 9 + 3/2X3 - 1/2X4
X2= 15/2 -3/4X3 + 1/4X4
令X3 =X4 =0
X(4) =(15, 15/2 , 0, 0 ,9 )T Z(4) =975