运筹学对偶灵敏.ppt

《运筹学对偶灵敏.ppt》由会员分享，可在线阅读，更多相关《运筹学对偶灵敏.ppt（42页珍藏版）》请在三一办公上搜索。

1、第3章 对偶理论和灵敏度分析,对偶理论(Dual Theory)灵敏度分析(Sensitivity Analysis),s.t,用矩阵形式表示原问题：,s.t,对偶问题：,min=YbAYCY0,max Z=CXAXbX0,原问题与对偶问题的关系在形式上可归结为表,3.4 对偶问题的基本性质,s.t,原问题：,s.t,对偶问题：,min=YbAT YCT Y0,max Z=CXAXbX0,(1).对称性：对偶问题的对偶问题是原问题。即原问题和对偶问题之间是互为对偶的。证明：（略）,(2).弱对偶性：设X#、Y#分别是原问题和对偶问题的可行解，则有CX#Y#b。证明：（略）从弱对偶性可知，原问题

2、(极大化问题)的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。对偶问题(极小化问题)的任意一个可行解所对应的目标函数值是其原问题最优目标函数值的一个上界。原问题任一可行解对应的目标函数值不大于其对偶问题的任一可行解对应目标函数值。,(3).无界性：若原问题可行，但目标函数无上界，则对偶问题无可行解。若对偶问题可行，但目标函数无下界，则原问题无可行解。证明：（略）(4).最优性：设X#、Y#分别是原问题和对偶问题的可行解，则当CX#=Y#b时，X#、Y#分别为原问题和对偶问题的最优解X*、Y*。证明：（略）,(5).强对偶性：若原问题和对偶问题之一有最优解，则另一个问题也

3、一定有最优解，且目标函数值相等。证明：（略）从强对偶性可知，若原问题有一个对应于基B的最优解，则CBB-1就是对偶问题的一个最优解，并且两个问题的最优值相等。另外，原问题获得最优解时，其松弛变量对应的检验数的相反数CBB-1，就是对偶问题的最优解。该性质常被称为主对偶定理。CBB-1称为单纯形乘子。,(6).互补松弛性：该性质常被称为对偶问题的松紧定理。(7).对应性：原问题对应其可行基的检验数的相反数是对偶问题的一个基解。证明：（略）从性质7可知，用单纯形法求解LP问题时，迭代的每一步在得到原问题的一个基可行解的同时，其检验数行的各检验数对应于对偶问题的一个基解，它们之间仅差一个负号。在单纯

4、形表中，原问题的松弛变量对应于对偶问题的变量，对偶问题的剩余变量对应于原问题的变量；这些互相对应的变量，如果在一个问题的解中是基变量，则在另一个问题的解中是非基变量。,原问题与对偶问题之间的变量对应关系见表3-5。,表3-5的进一步说明：用单纯形法求解LP问题时，原问题的检验数行的各检验数对应于对偶问题的一个基解，它们之间仅差一个负号。在单纯形表中，原问题的松弛变量(Xs)对应于对偶问题的变量(-Y)，对偶问题的剩余变量(-Ys1、-Ys2)分别对应于原问题的变量(XB、XN)利用这种对应关系，只需求解其中一个问题，就可以从原问题最终单纯形表中同时得到其对偶问题的最优解，而不须求解过程。,以上

5、这些互相对应的变量，如果在一个问题的解中是基变量，则在另一个问题的解中是非基变量。根据上述的一些性质，互为对偶的两个LP问题之间的解有以下几种情况，见表3-6。,例3-4：求解下列LP问题。max Z=x1+x2,s.t.,-x1+x2+x3 2-2x1+x2-x3 1x1，x2，x3 0,解：由于X=(0,0,0)T满足s.t.，所以X=(0,0,0)T为可行解。现写出其对偶问题如下 min=2y1+y2,s.t.,-y1-2y2 1 x10 y1+y2 1 x20 y1-y2 0 x30 y1，y2 0 第i个约束条件,(1),(2),由于第一个约束条件-y1-2y21是矛盾不等式，所以对

6、偶问题(2)无可行解。根据对偶问题的强对偶性可知，若原问题(1)有最优解，则对偶问题(2)一定也有最优解。因此，原问题(1)不可能有最优解，但是，原问题(1)有可行解，所以原问题(1)无有限最优解，即目标函数无上界。,对偶问题的解在经济学上称为原问题的资源的影子价格，为什么呢？单纯形表中目标值为：z=CBB-1b检验数为：N=CNCBB-1N其中都有乘子Y=CBB-1，Y的经济学意义是什么？,第5节 影子价格（shadow price）,假设X*和Y*分别是原问题和对偶问题的最优解，由主对偶定理，相应的目标函数值相等，即：z*=CX*=Y*b=*,因此，y*i实际上表示原问题约束条件中第i种资

7、源增加一个单位时，目标函数最优值的改变量。,这就是说，影子价格就是对系统中的各个资源的使用价值的一个定量分析，它是原问题目标函数对某种资源的一阶偏导数。从最终单纯形表可知，第i种资源的影子价格就是对应的原问题松弛变量的检验数的相反数。,第2章例1的最终单纯形表(P41)max z=2x1+3x2,从最终单纯形表可知，第i种资源的影子价格就是对应的原问题松弛变量的检验数的相反数。即y1*=3/2，y2*=1/8，y3*=0。,x1+2x2 84x1 16 4x2 12x10，x2 0,max Z=2x1+3x2,x1+2x2 84x1 16 4x2 12x10，x2 0,s.t.,x2,x1,O

8、,1,1,2,2,3,3,4,4,x1+2x2=8,4x1=16,4x1=12,Q1,Q2,Q3,Q4,图2-1，y1*=3/2，y2*=1/8，y3*=0。,x1+2x2=9,2x1+3x2=14,2x1+3x2=15.5,Q2,。,。,max Z=2x1+3x2,x1+2x2 84x1 16 4x2 12x10，x2 0,s.t.,x2,x1,O,1,1,2,2,3,3,4,4,x1+2x2=8,4x1=16,4x1=12,Q1,Q2,Q3,Q4,图3-1，y1*=3/2，y2*=1/8，y3*=0。,2x1+3x2=14,2x1+3x2=14.125,Q2”,4x1=17,。,。,以上可

9、知，资源的影子价格是针对具体生产或具体企业而言的；它对于拥有资源的决策者有非常重要的作用：(1)影子价格ri 0，可增加这种资源来收益，或降低这种资源的消耗来收益。企业内部可以挖潜的方向。(2)对企业外部，按影子价格制定外协加工的收费标准。(3)当某种资源的影子价格ri高于资源的市场价格时，生产活动具有经济效益，并可购买增加这种资源来收益。否则，可出售这种资源，从而在生产上获得利润。,第6节 对偶单纯形法,对偶单纯形法并不是解对偶问题的单纯形法，而是根据对偶问题的特点和对称性，设计出的一种解法。对偶问题的对应性告诉我们，原问题可行基所对应的检验数的相反数=对偶问题的一个基解。但这个基解不一定是

10、可行解。经过迭代，当原问题在单纯形表上的全部检验数变成非正时，得到原问题的最优解。这时，检验数的相反数即是对偶问题的一个基可行解。由主对偶定理可知，这个对偶问题的基可行解就是对偶问题的最优解。,对偶单纯形法的基本思路：基于对偶问题的对称性，在每次迭代中保持对偶问题的解是可行解，而不管原问题所获得的基解是否为可行解。但是，当原问题所获得的基解为可行解时，则这个基可行解就是原问题最优解。在具体求解过程中，对偶单纯形法是在原问题的单纯形表上进行对偶处理的。这种解法对于需要引入人工变量构造基进行求解是一种改进，因为它可以不用引入人工变量就能求得解，因此计算简便。,例2-g：用对偶单纯形法求解下列LP问

11、题。min=y1+3y2,s.t.,1/3y1+1/3y2 2 1/3y1+4/3y2 3 1/3y1+7/3y2 1y1，y2 0,max=-y1-3y2-1/3y1-1/3y2+y3=-2-1/3y1-4/3y2+y4=-3-1/3y1-7/3y2+y5=-1y1，y2，y3，y4，y5 0,s.t.,解：,原问题的对偶问题：max Z=2x1+3x2+x31/3x1+1/3x2+1/3x311/3x1+4/3x2+7/3x33x1,x2,x3 0,max=-y1-3y2-1/3y1-1/3y2+y3=-2-1/3y1-4/3y2+y4=-3-1/3y1-7/3y2+y5=-1y1，y2，

12、y3，y4，y5 0,例2-6：用对偶单纯形法求解下列LP问题。min=2x1+3x2+4x3 x1+2x2+x3 3 2x1-x2+3x3 4 x1,x2,x3 0,上述LP问题的对偶问题：max z=3y1+4y2 y1+2y2 2 2y1-y2 3 y1+3y24 y1,y20,从求解过程可知，对偶单纯形法的优点：(1)当原问题的初始解是非可行解，且相应的检验数都是非正时，这时不需要引入人工变量，简化计算。(2)当变量个数多于约束条件个数时，用对偶单纯形法求解，可以减少计算工作量。因此，对变量少，约束条件多的LP问题，可先将它变换成对偶问题，然后用对偶单纯形法求解其对偶问题，再根据其对偶

13、问题最优解时的检验数，写出原问题的最优解。,当aij，bi，cj这些参数中的某一个发生变化时，问题的最优解会有什么变化呢？,第7节 灵敏度分析(Sensitivity Analysis),max z=c1x1+c2x2+cnxn,s.t.,a11x1+a12x2+a1n xn=b1 a21x1+a22x2+a2n xn=b2 am1x1+am2x2+amn xn=bmx1,x2,xn0,灵敏度分析(Sensitivity Analysis)是对系统因环境变化显示出来的敏感程度的分析。在线性规划中讨论灵敏度分析，目的是描述一种能确定模型结构中元素变化对问题最优解影响的分析方法。,灵敏度分析主要回

14、答两方面问题：(1)因素有一定量变化时，最优解有什么变化；(2)因素在什么范围内变化时，最优解保持不变。,单纯形表中的基B是最优基，线性规划问题的各系数的变化会引起最优单纯形表的哪些部分改变?,br变化只引起B-1b改变；cj变化只引起=(CN-CBB-1N1，-CBB-1)改变；aij变化时：若aij属于N，则其改变只会引起的改变；若aij属于B，则其改变引起B-1的改变，从而引起=(CN-CBB-1N，-CBB-1)和右端常数项B-1b的同时改变。,其中S2=I,7.1 约束方程右端常数项br发生改变,br的改变只会引起B-1b的改变；,第1章例1的最终单纯形表(P32),max z=2x

15、1+3x2 x1+2x2 84x1 16 4x2 12x10，x2 0,例7 当b1=8+4=12时，,max z=2x1+3x2 x1+2x2 8+44x1 16 4x2 12x10，x2 0,表2-10中b列有负，用对偶单纯形法解得表2-11。,x5换出，x4换入。,用对偶单纯形法解得表2-11：x1*=4，x2*=3，z*=17；由x3*=2可知，设备有2小时未被利用。,(1)cj为非基变量的价值系数其它条件不变，目标函数中非基变量xj的价值系数cj发生变化，要影响到xj所对应的j=cj-CBB-1pj，但并不影响其它变量所对应的检验数，也并不影响xj=B-1b0。因此，要使现行最优基B

16、仍为最优基，只需使改变后的cj仍满足j0。,7.2 目标函数中价值系数cj发生改变,即 cj-CBB-1pj0或 cjCBB-1pj其中，cj为改变后的目标函数中的非基变量价值系数。所以，当改变后的cjCBB-1pj，则现行最优基B仍为最优基，此时，最优解保持不变，目标函数值CBB-1pj也不会改变。如果改变后cjCBB-1pj，即j=cj-CBB-1pj0，则须改变现行最优基，此时，利用现行最终单纯形表，只须改变表中的cj和j，然后继续迭代，直到得到最优解为止。,例2-h(a)：已知LP：max z=5x1+2x2+3x3 x1+2x2+2x38 3x1+4x2+x37 x1,x2,x30若

17、已经求得最终单纯形表，非基变量x2的价值系数c2发在什么范围内变化，最优解不变？,s.t.,(2)cj为基变量的价值参数其它条件不变，基变量的价值参数cj发生变化，要影响到CB，所以要影响到所有的非基变量的检验数，但并不影响xj=B-1b0。因此，要使现行最优基B仍为最优基，只需使改变后的cj仍满足N0。解不等式CB-CBB-1N0，就可得现行最优基B仍为最优基的范围，当cj在此范围内变化，则最优解保持不变，但此时zCBB-1b变化。当cj的改变超出此范围时，则须改变现行最优基，利用现行最终单纯形表，只须改变表中的cj和N，然后继续迭代，直到得到最优解为止。,例8：第1章例1的最终单纯形表(P

18、32),讨论基变量的价值系数c2在什么范围内变化，可以保持最优解不变。,max z=2x1+3x2 x1+2x2 84x1 16 4x2 12x10，x2 0,c2为基变量x2的价值系数，若要保持最优解不变，只要满足N0即可。由单纯形法可知,由N0得不等式组：,解得：0c24,只要c2在上述范围内变化，原最优生产计划就不用改变。但相应的zCBB-1b82c2；,如果c2的变化超出上述范围，则需改变现行最优基。不妨设c2=5，改变c2和N，继续迭代，直到得到最优解为止。因为c2=5，得,40，继续迭代：,最优解X*=(2,3,0,8,0)T；最优值z*=19。,x4换入，x5换出。,7.3 约束

19、条件的系数矩阵中某一个aij发生改变,例9 第1章例1.,max z=2x1+3x2+5x3 x1+2x2+2x384x1+6x316 4x2+3x312x10，x2 0，x3 0,用单纯形法解得表2-13(b)：,x3换入，x5换出。,用单纯形法解得表2-13(b)：x1*=1，x2*=3/2，x3*=2，z*=16.514。,例10 第1章例1.,max z=4x1+3x22x1+2x2 85x1 162x1+4x2 12x10，x2 0,用单纯形法解得表2-15：x1*=3.2，x2*=0.8，z*=15.214。,x1换入，x1换出。,用单纯形法解得表2-15：x1*=3.2，x2*=0.8，z*=15.214。,第8节 参数规划,当aij，bi，cj这些参数中的某一个参数是函数变化时，怎样求出问题的最优解呢？,