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

1、第六章* 单纯形法的灵敏度分析与对偶,单纯形表的灵敏度分析 线性规划的对偶问题 对偶单纯形法,第六章* 单纯形法的灵敏度分析与对偶,如何利用最优单纯形表进行灵敏度分析。,单纯形表-求解结果：,第1节 单纯形表的灵敏度分析,一. 目标函数中变量系数 Ck灵敏度分析 现要利用单纯形表法来进行Ck 的灵敏度分析。由于目标函数变量分为基与非基变量，故讨论时,分两类来讨论。 1.在最终的单纯形表里, xK 非基变量. 2.在最终的单纯形表里, xK 基变量.,第1节 单纯形表的灵敏度分析,1.在最终的单纯形表里, xK 非基变量。 由于约束条件（方程）系数增广矩阵在迭代中只是其本身的行的初等变换与CK

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

3、系数CB变了，则Zj 也变了， 相应地，也变了。变化规律为：,目标函数： maxz=50 x1+100 x2,x1+ x2300,2x1+x2400,x1 0, x20,s.t.,x2250,maxz=50 x1+100 x2,x1+ x2+s1=300,2x1+x2+s2=400,x1 0, x20, si0,s.t.,x2+s3 =250,一、线性规划问题解的基本概念,基及基本解:,maxz=50 x1+100 x2+0s1+0s2+0s3,1x1+1 x2+1s1+0s2+0s3 =300,2x1+1 x2+0s1+1s2+0s3 =400,x1 0, x20, s10， s20， s3

4、0,s.t.,0 x1+1x2+0s1+0s2+1s3 =250,表解形式的单纯形法,例子:,初始单纯形表,（）先分析非基变量s1: c3 3 由于是非基变量，故套用公式（1）,当C3 -3, 时最优解不变;已知3=-50, C3 （50）=50；c=c+C=0+50=50 最优解不变。,（2）再分析基变量的系数分析：,从表中获得了: a11=1, a12=0, a13=1, a14=0, a15=-1,例如对基变量X1的系数C1进行灵敏度分析：,单纯形表灵敏度分析,故，max-50C1 min50，左半径和右半径 保证区间半径最小 则当-50C1 50时最优解不变，即x1的目标函数系数C有：

5、 50-50=c1+ L C=C1+C1 c1+R=50+50， 0C100时，最优解不变。,*最优解如下* 目标函数最优值为 : 27500 变量 最优解 相差值 - - - x1 50 0 x2 250 0 约束 松弛/剩余变量 对偶价格 - - - 1 0 50 2 50 0 3 0 50 目标函数系数范围 : 变量 下限 当前值 上限 - - - - x1 0 50 100 x2 50 100 无上限 常数项数范围 : 约束 下限 当前值 上限 - - - - 1 250 300 325 2 350 400 无上限 3 200 250 300,LP OPTIMUM FOUND AT S

6、TEP 2 OBJECTIVE FUNCTION VALUE 1) 27500.00 VARIABLE VALUE REDUCED COST X1 50.000000 0.000000 X2 250.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 50.000000 3) 50.000000 0.000000 4) 0.000000 50.000000 NO. ITERATIONS= 2 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARI

7、ABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 50.000000 50.000000 50.000000 X2 100.000000 INFINITY 50.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 300.000000 25.000000 50.000000 3 400.000000 INFINITY 50.000000 4 250.000000 50.000000 50.000000,二、基于

8、单纯形法的约束方程右边常数灵敏度分析,二、约束方程右边常数灵敏度分析,从上页表中我们,知道了右边系数bj的灵敏度,对偶价格不变与bj变化范围. 现要从单纯形表的数据进行分析： Zj的值刚好是对偶价格. 那么，当bj变为bj+b时,非基变量的检验数不变,但基变量的检验数会变。bk允许范围为:,二、约束方程右边常数灵敏度分析,那么，当br变为br+br时,非基变量的检验数不变,但基变量的检验数会变. br 允许范围为:,初始单纯形表,现对b1进行灵敏度分析,先要找出b1的列元素:它就是S1.因为可逆矩阵B的第一列为 S1=(1,-2,0)T Max- 50/1=-50 b1 min-50/-2=2

9、5 -50 b1 +25 那么, 300-50b=b+ b1 300+25 250b=b+ b1 325 练习：分析B3,三、约束方程系数矩阵A灵敏度分析,技术系数aij发生变化时对线性规划最优解结构的影响比较复杂。从下式中可知，非基变量的检验数和基变量XB的值都与技术系数有关。,通常把技术系数aij的灵敏度分析分为如下三类： （1）对应基变量的AIJ，且资源BI已全部用完； （2）对应基变量的AIJ，但资源BI未用完； （3）对应非基变量的AIJ，且资源BI全部用完或未用完；,三、约束方程系数矩阵A灵敏度分析,线性规划最优解结构不变的条件是 （1）对应基变量的aij，且资源Bi已全部用完，则

10、技术系数变化范围为：aij=0; （2）对应基变量的aij，但资源bi未用完,则技术系数变化范围为：aijXn+i/xj （3）对应非基变量的aij，且资源bi全部用完或未用完,我们要分以下两种情况讨论： （A）aij0, 不会破坏最优解。 （B）aij0，要使原线性规划最优解不变条件：必须保证该非基变量的检验数仍小于0，即cj-Zj0,第2节 线性规划的对偶问题,某工厂在计划安排I,II两种产品,生产I可获得50元,II可获得100元,如何安排生产,获得MAX?,模型,目标:max z=50 x1+100 x2 S.t. x1+x2=0,假设现在有一个公司要租用工厂设备，那么工厂获取利润有两

11、种方法，一是自己生产，二是出租设备资源。自己生产已有模型。那么，如果出租，那么如何构建模型？设备价格为Ay1,By2,Cy3;则,目标:min 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 =0,目标:max z=50 x1+100 x2 S.t. x1+x2=0,原问题,对偶问题,1.求目标函数最大问题中有n个变量,m个约束条件,它的约束条件都是小于等于不等式;其对偶则是m个变量,n个约束条件,并

12、且是大于等于不等式;,2.原问题的目标函数系数C是对偶问题中的约束条件B ci=bi 3.原问题右边系数B成为对偶问题的目标系数C,bi=ci 4. 对偶问题的约束条件系数矩阵A是原问题的AT,转化例子： Max f=3x1+4x2+6x3+4x4 x1+4x2+2x3-3x435 3x1+x2+5x3+6x445 x1,x2,x3,x40,Min g(y)= 35y1+45y2 Y1+3y2 3 4y1+y2 4 2y1+5y2 6 -3y1+6y2 4 Y1,y2 0,目标: min f=300y1+400y2+250y3 s.t. Y1+2y250 y1+y2+y3100 y1,y2,y

13、3 0,目标: max z=50 x1+100 x2 S.t. x1+x2300 2x1+x2400 x2250 x1,x20,原问题,对偶问题,Max -f=-300y1-400y2-250y3-Ma1 y1+2y2-s1+a1=50 y1+y2+y3-s2=100 y1,y2,y3,s1,s2,a10,对偶单纯形法求解：,初始单纯形表,初始单纯形表,(1/2),初始单纯形表,(1/2),最优解:y1=50,y2=0,y3=50,s1=0,s2=0,a1=0,-f的最大值为-27500,即目标f的最小值为:27500 A设备租金为50元,B设备租金为0元,C设备租金为50元;,二.任意形式的

14、对偶问题 max Z=3x1+4x2+6x3 s.t. 2x1+3x2+6x3440 6x1-4x2-x3 100 5x1-3x2+x3 = 200 x1,x2,x3 0,二.任意形式的对偶问题 max Z=3x1+4x2+6x3 s.t. 2x1+3x2+6x3440 -6x1+4x2+x3 -100 5x1-3x2+x3 200 5x1-3x2+x3 200 x1,x2,x3 0,5x1-3x2+x3 = 200,max Z=3x1+4x2+6x3 s.t. 2x1+3x2+6x3440 -6x1+4x2+x3 -100 5x1-3x2+x3 200 -5x1+3x2-x3 -200 x1

15、,x2,x3 0,s.t. 2y1-6y2 +5y3-5y4 3 3y1+4y2 +3y3-3y4 4 6y1+y2+y3-y4 6 y1,y2,y3,y4 0,min f=440y1-100y2+200y3-200y4,二.任意形式的对偶问题,对偶问题,原问题的对偶问题为 min f=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 0,原问题的对偶问题为 min f=440y1-100y2+200(y3-y4) s.t. 2y1-6y2 +5(y3-y4

16、) 3 3y1+4y2 +3(y3-y4) 4 6y1+y2 + (y3-y4) 6 y1,y2,y3,y4 0,原问题的对偶问题为 min f=440y1-100y2+200s3 s.t. 2y1-6y2 +5s3 3 3y1+4y2 +3s3 4 6y1+y2 + s3 6 y1,y2 0,S3无非负限制,练习： Max f(x)=4x1+5x2 s.t. 3x1+2x220 4x1-3x2 10 x1+x2 = 5 x20, x1正负不限,练习转换： Max f(x)=4x11-4x12+5x2 s.t. 3x11-3x12+2x220 4x11-4x12-3x2 10 x11-x12+

17、x2 = 5 x11,x12,x20,练习转换： Max f(x)=4x11-4x12+5x2 s.t. 3x11-3x12+2x220 4x11-4x12-3x2 10 x11-x12+x2 5 x11-x12+x2 5 x11,x12,x20,练习转换： Max f(x)=4x11-4x12+5x2 s.t. 3x11-3x12+2x220 -(4x11-4x12-3x2) -10 -(x11-x12+x2) -5 x11-x12+x2 5 x11,x12,x20,练习转换： Max f(x)=4x11-4x12+5x2 s.t. 3x11-3x12+2x2 20 -4x11+4x12+3

18、x2 -10 -x11+x12-x2 -5 x11-x12+x2 5 x11,x12,x20,练习转换： Min f(y)=20y1-10y2-5y3+5y4 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-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-5y3 s.t

19、. 3y1-4y2 - y3 = 4 -3y1+4y2+y3 =-4 2y1+3y2- y3 =5 y1,y2 =0，y3无限制,练习转换： Min f(y)=20y1-10y2-5y3 s.t. 3y1-4y2 - y3 = 4 2y1+3y2- y3 =5 y1,y2 =0，y3无限制,练习转换： Min f(y)=20y1-10y2-5y3+5y4 s.t. 3y1-4y2-y3+y4 =4 -3y1+4y2+y3-y4 =-4 2y1+3y2-y3+y4 =5 y1,y2,y3,y4=0,练习答案： Min h(y)=20y1+10y2+5y3 s.t. 3y1+4y2+y3 =4 2y1-3y2+y3 5 y10, y20, y3不限,第3节 对偶单纯形法,对偶单纯法和单纯形法一样都是求解原线性规划问题的一种方法. 单纯形法是在保持原问题的所有约束条件的bj都大于0的情况下,通过迭代,使得所有检验数都小于等于0,最后求得最优解; 而对偶单纯形法则是在保持原问题的所有检验数都小于等于0的情况下,通过迭代,使得所有约束条件的常数都大于等于0,最后求得最优解。,第3节 对偶单纯形法,例，用对偶单纯形法求解如下线性规划问题： Min f=x1+5x2+3x4 s.t. X1+2x2-x