单纯形法的灵敏度分析与对偶.ppt

《单纯形法的灵敏度分析与对偶.ppt》由会员分享，可在线阅读，更多相关《单纯形法的灵敏度分析与对偶.ppt（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、单纯形法的灵敏度分析与对偶 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第六章*单纯形法的灵敏度分析与对偶v如何利用最优单纯形表进行灵敏度分析。单纯形表-求解结果：迭代次数基变量CBx1X2s1s2S3b比值501000000 x1501010-150S2000-21150 x210001001250Zj5010050050Z=2750000-500-50第1节 单纯形表的灵敏度分析一.目标函数中变量系数 Ck灵敏度分析现要利用单纯形表法来进行Ck 的灵敏度分析

2、。由于目标函数变量分为基与非基变量，故讨论时,分两类来讨论。1.在最终的单纯形表里,xK 非非基变量.2.在最终的单纯形表里,xK 基变量基变量.第1节 单纯形表的灵敏度分析1.在最终的单纯形表里,xK 非基变量。由于约束条件（方程）系数增广矩阵在迭代中只是其本身的行的初等变换与CK 没有任何关系，所以当CK 变为CK+CK 时，在最终单纯形表中其系数的增广矩阵不变，又因为xK 是非基变量，所以基变量的目标函数的系数不变，即CB 不变，可知ZK 也不变，只是CK 变为CK+CK 。这时K=CK ZK 变成了CK+CK ZK=K+CK.要使得原来的最优解仍为最优解，只要K+CK 0 即可，也就是

3、 CK K 即可。第1节 单纯形表的灵敏度分析.在最终的单纯形表里,xK 为基变量。由于约束条件（方程）系数增广矩阵在迭代中只是其本身的行的初等变换与CK 没有任何关系，所以当CK 变为CK+CK 时，在最终单纯形表中其系数的增广矩阵不变，但基变量在目标函数的系数CB变了，则Zj 也变了，相应地，也变了。变化规律为：目目标标函数：函数：maxmaxz=50 xz=50 x1 1+100 x+100 x2 2x x1 1+x+x2 23003002x2x1 1+x+x2 2400400 x x1 1 0,x0,x2 200s.t.s.t.x x2 2250250maxmaxz=50 xz=50

4、x1 1+100 x+100 x2 2x x1 1+x+x2 2+s+s1=1=3003002x2x1 1+x+x2 2+s2=400+s2=400 x x1 1 0,x0,x2 20,0,si0si0s.t.s.t.x x2 2+s3 =250+s3 =250一、线性规划问题解的基本概念基及基本解:maxmaxz=50 xz=50 x1 1+100 x+100 x2 2+0s1+0s2+0s3+0s1+0s2+0s31x1x1 1+1 x+1 x2 2+1s+1s1+0s2+0s3 =1+0s2+0s3 =3003002x2x1 1+1 x+1 x2 2+0s1+1s2+0s3=400+0s

5、1+1s2+0s3=400 x x1 1 0,x0,x2 20,0,s10s10，s20s20，s30s30s.t.s.t.0 x1+1x0 x1+1x2 2+0s1+0s2+1s3=250+0s1+0s2+1s3=250表解形式的单纯形法v例子:初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000002x1501010-150S2000-21150 x210001001250Zj5010050050Z=2750000-500-50（）先分析非基变量s1:c3 3 由于是非基变量，故套用公式（1）当C3-3,时最优解不变;已知3=-50,C3（50）=50；c=c+C0,不会破

6、坏最优解。（B）aij0，要使原线性规划最优解不变条件：必须保证该非基变量的检验数仍小于0，即cj-Zj0第2节 线性规划的对偶问题某工厂在计划安排I,II两种产品,III资源限制设备A11300台时设备B21400设备C01250生产I可获得50元,II可获得100元,如何安排生产,获得MAX?模型v目标:max z=50 x1+100 x2vS.t.x1+x2=300v 2x1+x2=400v x2=0假设现在有一个公司要租用工厂设备，那么工厂获取利润有两种方法，一是自己生产，二是出租设备资源。自己生产已有模型。那么，如果出租，那么如何构建模型？设备价格为Ay1,By2,Cy3;则目标:m

7、in f=300y1+400y2+250y3 s.t.y1+2y2=50 y1+y2+y3100 y1,y2,y3=0目标:min f=300y1+400y2+250y3 s.t.Y1+2y2=50 y1+y2+y3100 y1,y2,y3=0v目标:max z=50 x1+100 x2vS.t.v x1+x2=300v 2x1+x2=400v x2=0原问题对偶问题1.求目标函数最大问题中有n个变量,m个约束条件,它的约束条件都是小于等于不等式;其对偶则是m个变量,n个约束条件,并且是大于等于不等式;2.原问题的目标函数系数C是对偶问题中的约束条件B ci=bi3.原问题右边系数B成为对偶问

8、题的目标系数C,bi=ci4.对偶问题的约束条件系数矩阵A是原问题的AT原问题（max,)对偶问题(min,)技术系数矩阵A技术系数矩阵AT价值系数C右端项b右端项b价值系数C第i行约束条件为型对偶变量yi 0第i行约束条件为型对偶变量yi 0第i行约束条件为=型对偶变量yi正负不限决策量xj 0第j行约束条件为 型决策量xj 0第j行约束条件为型决策量xj正负不限第j行约束条件为=型转化例子：Max f=3x1+4x2+6x3+4x4 x1+4x2+2x3-3x435 3x1+x2+5x3+6x445 x1,x2,x3,x40 Min g(y)=35y1+45y2Y1+3y2 34y1+y2

9、 42y1+5y2 6-3y1+6y2 4Y1,y2 0目标:min f=300y1+400y2+250y3 s.t.Y1+2y250 y1+y2+y3100 y1,y2,y3 0v目标:vmax z=50 x1+100 x2vS.t.v x1+x2300v 2x1+x2400v x2250v v x1,x20原问题对偶问题vMax-f=-300y1-400y2-250y3-Ma1v y1+2y2-s1+a1=50v y1+y2+y3-s2=100v y1,y2,y3,s1,s2,a10 对偶单纯形法求解：初始单纯形表迭代次数基变量CBy1y2y3s1s2a1b比值-300-400-25000

10、-M0a1-M120-10150y3-2501110-10100Zj-M-250-2M-250-250M250-M-50M-2500Cj-ZjM-502M-1500-M-2500初始单纯形表迭代次数基变量CBy1y2y3s1s2a1b比值-300-400-25000-M0y2-4001/210-1/201/225y3-2501/2011/2-1-1/275Zj-325-400-25075250-75-28750Cj-Zj2500-75-250-M+75(1/2)初始单纯形表迭代次数基变量CBy1y2y3s1s2a1b比值-300-400-25000-M0y1-300120-10150y3-25

11、00-111-1-150Zj-300-350-25050250-50-27500Cj-Zj0-500-50-250-M+50(1/2)最优解:y1=50,y2=0,y3=50,s1=0,s2=0,a1=0,-f的最大值为-27500,即目标f的最小值为:27500A设备租金为50元,B设备租金为0元,C设备租金为50元;v二.任意形式的对偶问题 max Z=3x1+4x2+6x3 s.t.2x1+3x2+6x3440 6x1-4x2-x3 100 5x1-3x2+x3 =200 x1,x2,x3 0v二.任意形式的对偶问题 max Z=3x1+4x2+6x3 s.t.2x1+3x2+6x344

12、0 -6x1+4x2+x3-100 5x1-3x2+x3 200 5x1-3x2+x3 200 x1,x2,x3 0 5x1-3x2+x3 =200max Z=3x1+4x2+6x3 s.t.2x1+3x2+6x3440 -6x1+4x2+x3-100 5x1-3x2+x3 200 -5x1+3x2-x3 -200 x1,x2,x3 0s.t.2y1-6y2 +5y3-5y4 3 3y1+4y2+3y3-3y4 4 6y1+y2+y3-y4 6 y1,y2,y3,y4 0min f=440y1-100y2+200y3-200y4v二.任意形式的对偶问题v对偶问题v原问题的对偶问题为 min f

13、=440y1-100y2+200y3-200y4 s.t.2y1-6y2 +5y3-5y4 3 3y1+4y2+3y3-3y4 4 6y1+y2+y3-y4 6 y1,y2,y3,y4 0v原问题的对偶问题为 min f=440y1-100y2+200(y3-y4)s.t.2y1-6y2 +5(y3-y4)3 3y1+4y2+3(y3-y4)4 6y1+y2 +(y3-y4)6 y1,y2,y3,y4 0v原问题的对偶问题为 min f=440y1-100y2+200s3 s.t.2y1-6y2 +5s3 3 3y1+4y2+3s3 4 6y1+y2 +s3 6 y1,y2 0,S3无非负限制

14、v练习：vMax f(x)=4x1+5x2vs.t.3x1+2x220 4x1-3x2 10 x1+x2 =5 x20,x1正负不限v练习转换：vMax f(x)=4x11-4x12+5x2vs.t.3x11-3x12+2x220 4x11-4x12-3x2 10 x11-x12+x2 =5 x11,x12,x20v练习转换：vMax f(x)=4x11-4x12+5x2vs.t.3x11-3x12+2x220 4x11-4x12-3x2 10 x11-x12+x2 5 x11-x12+x2 5 x11,x12,x20v练习转换：vMax f(x)=4x11-4x12+5x2vs.t.3x11

15、-3x12+2x220 -(4x11-4x12-3x2)-10 -(x11-x12+x2)-5 x11-x12+x2 5 x11,x12,x20v练习转换：vMax f(x)=4x11-4x12+5x2vs.t.3x11-3x12+2x2 20 -4x11+4x12+3x2 -10 -x11+x12-x2 -5 x11-x12+x2 5 x11,x12,x20练习转换：Min f(y)=20y1-10y2-5y3+5y4s.t.3y1-4y2-y3+y4 =4 -3y1+4y2+y3-y4=-4 2y1+3y2-y3+y4 =5 y1,y2,y3,y4=0练习转换：Min f(y)=20y1-

16、10y2-5(y3-y4)s.t.3y1-4y2 -(y3-y4)=4 -3y1+4y2+(y3-y4)=-4 2y1+3y2-(y3-y4)=5 y1,y2,y3,y4=0练习转换：Min f(y)=20y1-10y2-5y3s.t.3y1-4y2 -y3 =4 -3y1+4y2+y3 =-4 2y1+3y2-y3=5 y1,y2=0，y3无限制练习转换：Min f(y)=20y1-10y2-5y3s.t.3y1-4y2 -y3 =4 2y1+3y2-y3=5 y1,y2=0，y3无限制练习转换：Min f(y)=20y1-10y2-5y3+5y4s.t.3y1-4y2-y3+y4 =4 -

17、3y1+4y2+y3-y4=-4 2y1+3y2-y3+y4 =5 y1,y2,y3,y4=0v练习答案：vMin h(y)=20y1+10y2+5y3vs.t.3y1+4y2+y3=4 2y1-3y2+y3 5 y10,y20,y3不限原问题（max,)对偶问题(min,)技术系数矩阵A技术系数矩阵AT价值系数C右端项b右端项b价值系数C第i行约束条件为型对偶变量yi 0第i行约束条件为型对偶变量yi 0第i行约束条件为=型对偶变量yi正负不限决策量xj 0第j行约束条件为 型决策量xj 0第j行约束条件为型决策量xj正负不限第j行约束条件为=型第3节 对偶单纯形法v对偶单纯法和单纯形法一样

18、都是求解原线性规划问题的一种方法.v单纯形法是在保持原问题的所有约束条件的bj都大于0的情况下,通过迭代,使得所有检验数都小于等于0,最后求得最优解;v而对偶单纯形法则是在保持原问题的所有检验数都小于等于0的情况下,通过迭代,使得所有约束条件的常数都大于等于0,最后求得最优解。第3节 对偶单纯形法v例，用对偶单纯形法求解如下线性规划问题：vMin f=x1+5x2+3x4vs.t.v X1+2x2-x3+x46v -2x1-x2+4x3+x44v x1,x2,x3,x4=0第3节 对偶单纯形法v例，用对偶单纯形法求解如下线性规划问题：v将上述线性规划问题变换为如下适合对偶单纯形法的形式：v M

19、ax z=-f=-x1-5x2-3x4v s.t.v -X1-2x2+x3-x4+x5=-6v 2x1+x2-4x3-x4+x6=-4v x1,x2,x3,x4,x5,x6=0v x5,x6为剩余变量初始单纯形表迭代次数基变量CBx1x2x3x4x5x6b比值-1-50-3000 x50-1-21-110-6x6021-4-101-4Zj0000000Cj-Zj-1-50-300X=(0,0,0,0,-6,-4)是基本解，但不是基本可行解，不可行。（1）确定出基变量：minbi|bi0=min-6,-4=-6=b1,所以第L=1行为主行，x5出基变量。（2）入基变量:所以第K=1列为主列，第1

20、列的变量X1为入基变量。迭代次数基变量CBx1x2x3x4x5x6b比值-1-50-3000 x50-1-21-110-6x6021-4-101-4Zj0000000Cj-Zj-1-50-300(-1)迭代次数基变量CBx1x2x3x4x5x6b比值-1-50-3000 x1-112-11-106x600-3-2-321-16Zj-1-21-110-6Cj-Zj0-3-1-2-10(-2)迭代次数基变量CBx1x2x3x4x5x6b比值-1-50-3000 x1-117/205/2-2-1/214x3003/213/2-1-1/28Zj-1-7/20-5/221/2Z=-14Cj-Zj0-3/

21、20-1/2-2-1/2(-2)X=(x1,x2,x3,x4,x5,x6)=(14,0,8,0,0,0)满足可行性检验，所以上述X是原线性规划的最优解。最优值：f=-g(X0=-(-14)=14v对偶单纯形法的步骤：v1。求一个满足最优检验条件的初始基本解，列出初始单纯形表；v2。可行性检验，若所有的右系数均大于0，则已得最优解，停止运算，否则，转3v3。求另一个满足最优检验条件且更接近可行解的基本解；v（1）确定出变量：找出bi中的最小者，确定行号及变量；v（2）确定入变量：最小比原则min(j/aij定出列号；若找不到，则原规划问题的解无界解，停止运算，否则转步骤（3）v（3）以主元alk为中心，迭代，单位化，得到新的基本解，让其接近基本可行解。再转2；