第四章-对偶规划、灵敏读分析应用运筹学

1、1,第四章 对偶规划、灵敏度分析与应用 Dual Problem and Sensitivity analysis,1单纯型法的矩阵表示 2线性规划的对偶问题 3对偶规划的基本性质 4影子价格（对偶价格） 5对偶单纯形法 6单纯形表的灵敏度分析,2,1 单纯型法的矩阵表示,Max z= CX Max z = CX+0Xs s.t. AXb s.t. AX+IXs =b X0 X0 C=(c1, c2,cn ) A=(p1, p2 , pn ),3,Max z=CBXBCN XN B =(p1 ,p2, pm) s.t. BXBNXN=b 为一个基 XB ,XN0 （A，I）=（B，N） XB=

2、 B-1bB-1NXN N=(pm+1 , pn) z=CBXB CN XN = CBB-1b +( CN CBB-1N ) XN z+ 0XB+(CBB-1N CN) XN = CBB-1b 0 z + XB+ B-1NXN = B-1b -z+ 0XB+(CN CBB-1N) XN = CBB-1b 0 z + XB+ B-1NXN = B-1b,国内书籍,国外书籍,4,迭 代,j =1,n,5,XB= B-1b Z= CBB-1b,6,以第二章例一为例 Max z = 50 x1 + 100 x2 Max z = 50 x1 + 100 x2 s.t. x1 + x2 300 s.t.

3、x1 + x2 + s1 300 2 x1 + x2 400 2 x1 + x2 + s2 400 x2 250 x2 + s3 250 x1 , x2 0 x1 , x2 ，s1 ，s2 ， s3 0,如果,7,单纯型法迭代过程表,8,最终表的矩阵计算（矩阵表示）,9,2 Dual Problem 线性规划的对偶问题,例1. 某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表： 问题：工厂应分别生产多少单位、产品才能使工厂获利最多？,线性规划模型： 目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1

4、 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0 最优解x1 = 50 ， x2 =250， z =27500,10,现在我们从另一个角度来考虑这个问题。假如有另外一家公司要求租用该厂的设备和购买原料A、B用于生产其他商品，那么该公司和该厂的厂长应该如何来确定合理的租金和原材料A、B的价格呢？ 设y1表示设备每台时的租金。y2和y3 分别为原材料A、B的出卖的价格，公司将300台时的设备和400kg原材料A和250kg 原材料B全部租购过来所化的成本为：300 y1 400 y2 250 y3 。显然，公司希望租购的成本最低，故目标函数为 ： Min 300 y

5、1 400 y2 250 y3 下面考虑什么情况下，工厂才愿意租售设备和原材料，而不进行生产。对于工厂来说，租金和出卖价格定义为扣除成本后所能产生的利润。作为工厂来说，把生产单位产品所需的1小时设备的台时和2 kg原材料A租售所得收益应不低于生产一件产品所获的利润50元，即 y12 y2 50；把生产单位产品所需的1小时设备台时、1 kg原材料和1kg原材料B租售所得收益应不低于生产一件产品 所获的利润100元，即 y1 y2 y3 100，这样我们得到了该问题的数学模型 目标函数：Min f = 300 y1 400 y2 250 y3 约束条件：s.t. y12 y2 50 y1 y2 y

6、3 100 y1 , y2 0,11,这样从两个不同的角度来考虑同一个工厂的最大利润的生产计划和租售设备和原材料的销售计划（最小租金）问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题 Primal Problem原问题 Dual Problem 对偶问题 Max z = 50 x1 + 100 x2 Min f = 300 y1400 y2250 y3 s.t. x1 + x2 300 s.t. y12 y2 50 2 x1 + x2 400 y1 y2 y3 100 x2 250 y1 , y2 , y3 0 x1 , x2 0,最优解,12,如果我们

7、用矩阵形式来表示，则有原问题和对偶问题： （） （） 其中A是 矩阵mn，该问题有m个约束条件n个变量， X(x1, x2, , xn) T, b= (b1, b2, , bm) T , C = (c1, c2, , cn) 其中AT是A的转置， bT是b的转置, CT是C的转置, Y= (y1, y2, , ym) T 。现在我们用单纯形法求对偶问题的解。,13,原规划与对偶规划的线性关系,14,2对偶规划的基本性质,对偶规划的基本性质 1对称性。即对偶问题的对偶是原问题。 2弱对偶性。即对于原问题()和对偶问题()的可行解 都有 C bT 。 由弱对偶性，可得出以下推论： （1）原问题任一

8、可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。 （2）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。 （3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,15,3互补解性质：每次单纯型迭代过程中，可以得到原问题的一个基可行解和对偶问题的一个互补的解 见下张PPT 4。最优性

9、。如果 X* 是原问题()的可行解，Y*是对偶问题()的可行解，并且 CX* =bTY* ，则X*和Y*分别为原问题()和对偶问题()的最优解。 Y* =CBB1 (B为最优基),可丛单纯型表中读出。最终单纯型表中Xs对应的检验数去掉负号(Cs=0) 4强对偶性。即若原问题()及其对偶问题()都有可行解，则两者都有最优解；且它们的最优解的目标函数都相等。 5互补松弛性。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零也即 若yi*0,则有 若 ， 则有yi*=0, xn+I =0,xn+i 0,

10、16,S*,17,3 影子价格（对偶价格）,y*表示在其它条件不变情况下，z*对第i种资源的变化率，称为第i种资源的影子价格或边际价格，说明在资源最优利用条件下，每增加(减少)一个单位第i种资源，目标函数z*的增加(减少)量。 资源的市场价格是已知的，而影子价格有赖于资源的利用情况，是未知数，随着系统内资源数量bj、技术系数aij和价值系数ci的变化而变化，是动态的 影子价格反映了资源在系统内的稀缺程度。当系统达到最优时，如果某种资源的影子价格yi*0，则资源已完成耗尽，是稀缺资源。如果资源供大于求，则影子价格为0。设备和原材料B为稀缺资源，A为非稀缺资源,18,影子价格实际是一种机会成本，是

11、增加一个单位资源时，系统所能支付的最大成本量，是高于正常成本的量，当市场上设备1小时的租金高于50元时，应该出租设备，否则应该租进设备进行生产，当市场上资源B的价格高于 18(采购价)+50=68元/kg时，应该出售原料B。 一般说，线性规划问题的求解是确定资源的最优分配方案；而对偶问题的求解则是对资源的恰当估价，这种估价直接涉及资源的最有效利用。如在一个大公司内部，可以借助影子价格来确定资源的内部结算价格。对社会上一些最紧缺的资源，通过影子价格确定资源使用需上缴利润,19,4 The dual simplex method对偶单纯形法,对偶单纯型法的思路 单纯型法的迭代过程：在始终保持原问题

12、解可行的条件下(bj0) ，将对偶问题的解由不可行(0)向可行解转化，一旦其对偶问题解可行时 (0)，原问题解为最优解。 对偶单纯行法的思路：在始终保持对偶问题解可行的条件下(0 ) ，将原问题的解由不可行(bj 0)向可行解转化，一旦原问题解可行时 (bj 0 )，则其解达到最优解。 正则解：检验数均非正(0 ) 所对应的基解X称为正则解 对偶单纯形法的计算步骤如下： 1. 设有初始正则解X(0) = (XB (0), XN (0) )T = (b1, , bm ,0, ,0)T 2. 若XB (0),0，则X(0) = X*最优，否则，转Step 3。 3. 由 确定r行上的基变量x Br

13、为出基变量。,20,Step 4. 若ar j 0 (j = 1, 2, , n)，则无最优解；否则，由 确定x k为入基变量。 Step 5. 作旋转运算，以x k取代x Br ，得新正则解，转Step 2。 简化计算是对偶单纯形法的优点，但是它在使用上有很大的局限，这主要是大多数线性规划问题很难找到初始解为正则解。但是在灵敏度分析中，有时需要对偶单纯形法，这样可以简化处理,21,例 Max z = x13 x2 Max z = x13 x2 s.t. -2x1 x2 3 s.t. -2x1 x2 x3 3 -3x1 2x2 4 -3x1 2x2 x4 4 -x1 2x2 1 -x1 2x2

14、 x5 1 x1 , x2 , 0 x1 , , x5 0,X (0)(0,0, 3, 4, 1)T为正则解, x4为出基变量,22,x1为入基变量, 3为主元,23,例： Max z = 50 x1 + 50 x2 + 0 s1 +0 s2 + 0 s3 s.t. x1 +s1 s3 100 2s1 + s2 + s3 50 x2 + s3 250 x1 , x2 , s1, s2 , s3 0 1.写出单纯型表，确定出基变量，在常数列中找一个最小的负常量，把这个常量所在行作为出基变量,24,2. 确定出基变量：b2= -50，故s2为出基变量。 3. 确定入基变量：第二行只有a23=-2,

15、 故s1为入基变量，迭代得：,最优解为：x1=50, x2=250, s1=25, s2=50, s3=0， 最优值：z*=28750,25,5 单纯形表的灵敏度分析,线性规划的灵敏度分析；在线性规划求出最优解后，研究线性规划的系数ci，aij, bj变化对最优解产生什么影响。它包括两个方面 （1）模型中这些数据在什么范围内变化时，最优解不变？ （2）当最优解发生变化时，最优解和最优值如何变化，如何求出新的最优解？ 灵敏度分析是非常重要的：线性规划的参数ci，aij, bj都是估计值和预测值，不一定非常精确；其次这些参数会随着市场的变化而变化，有了灵敏度分析，不必随着参数的变化而不断求解，也可

16、以判断参数变化是否会影响到最有解。,26,设问题为：Max z = CX s.t. AX=b X 0,27,一、约束方程中常数项bj的灵敏度分析,当bk 变成bkbkbk时， b变为 bb时， XB=B-1b 变为 X*B=B-1 ，检验向量(所有检验数)不变，X*B为正则解。要使X*B为最优解，只需要使X *B=B-1 0即可：由此可以确定bk的取值范围。,28,例，第二章例1中b1300 350时，进行灵敏度分析 解： b1 50,用对偶单纯型法进行求解，见PPT23,见 PPT16,29,下面我们仍以第二章例1在最终单纯形表上对bj 进行灵敏度分析。最终单纯形表如下所示：,为使最优基不变

17、，求b1 的取值范围,30,即第一约束条件对偶价格不变。实际意义可以描述为：当设备台时数在250与325之间变化，则设备台时数的对偶价格不变，都为每台设备台时50元。 通常我们可以直接计算 X*BB-1bbkPk，令其大于0来确定bk的取值范围。,解得：,31,二非基变量系数的变化 1. cj 变化， xj 为非基变量,只有xj 的检验数发生变化，计算得：,，如果,则原最优解不变，否则，将xj 作为入基变量用单纯形法求新的最优解。,例；Max z = 3 x1 + 5 x2 s.t. x1 4 2 x2 24 3x1 + 2 x2 18 x1 , x2 0 1）当 时，讨论最优解的变化 2）当

18、 时，讨论最优解的变化,32,最终单纯形表为：,1）当,时,，最优解不变,2）当,时,原来最优解不在是最优解，用单纯形法继续求解，得最优解为：,x1=4, x2=3, x3=0, x4=18, x5=0，z*=47,33,Wyndor Case Study 伟恩德公司案例研究,what-if 分析之前，最初伟恩德公司问题电子表格模型及最优解,实际举例,34,修正的伟恩德例子，门的单位利润PD=$300降到PD=$200和增加到PD=$500，最优解不变,伟恩德公司案例研究，单位利润变化的灵敏读分析,35,修正的伟恩德例子，门的单位利润从PD=$300增加到PD=$1000，最优解改变,实际举例

19、,Wyndor Case Study 伟恩德公司案例研究,36,用解的表格进行灵敏读分析 Using Solver Table to do Sensitivity Analysis,37,在伟恩德的例子中系统改变门的单位利润得到数据表,实际举例,38,最初伟恩德模型用Excel Solver产生的灵敏度分析的一部分，其中最后三栏表示了门窗单位利润的最优域。,实际举例,39,允许取值范围的图形表示 Graphical Insight into the Allowable Range,门的单位利润从PD 满足0 PD 750.，最优解不变,40,Range-of-Optimality What-I

20、f Analysis 最优域敏感性分析,如何在不重新求解模型的条件下，确定如果目标函数的几个系数同时变化，可能造成对最优解的影响,如果伟恩德公司两种新产品单位利润的估计值都是不精确的，将会对结果产生怎样的影响？,41,修正的伟恩德问题模型，其中门，窗的单位利润分别被改为PD=$4500,PW$400，但是最优解不变。其中门，窗的单位利润分别被改为PD=$600,PW$300，从而最优解改变,实际举例,伟恩德公司案例研究,42,伟恩德例子中系统改变门，窗单位利润得到的数据表,实际举例,伟恩德公司案例研究,43,百分之百法则 The 100 percent rule,目标函数系数同时变动的百分之百

21、法则(The 100 percent rule for simultaneous changes in objective function coefficients)： 如果目标函数的系数同时变动，计算出每一系数变动量占该系数最优域允许变动量的百分比，而后，将各个系数的变动百分比相加，如果所得的和不超过百分之一百，最优解不会改变，如果超过百分之一百，则不能确定最优解是否改变。 允许增加百分比=实际增加量/允许增加量 允许减少百分比=实际减少量/允许减少量,44,当门，窗的单位利润的估计值分为改为PD$525，PW$350，刚好处在百分百法则所允许的临界点上，（D,W）（2，6）还是最优解，但

22、同时，目标函数直线上在（2，6）（4，3）之间的所有点均为最优解,PD300允许增加450，允许减少300 PW500允许减少300，增加不限。 PD525，增加225，允许增加百分比为：225/450=0.5 PW350，减少150，允许减少百分比为：150/300=0.5 两项相加正好等于100%,45,百分之百法则是判断最优解是否发生变化的充分条件，不是必要条件,当门，窗的单位利润的估计值分为改为 PD = $150 ， PW = $250 (half their original values),允许减少百分比之和超过100%，最优解仍然为 (D, W) = (2, 6) even t

23、hough the 100 percent rule says that the optimal solution might change.,PD允许减少百分比为150/300=0.5 PW允许减少百分比为250/300=0.833 两项相加超过100%,46,资源系数变化的灵敏度分析,工厂2时间由 12增加到 13.每周总利润增加 $150，每小时增加$ 150；由13增加到18时，每周总利润增加 $750，当继续由18增加到20时，总利润不变（最优解不变（0，9）,47,Using the Spreadsheet to do Sensitivity Analysis,The hours available in plant 2 have been further increased from 13 to 18.The total profit increases by $750 per week ($150 per hour added in plant 2).,48,改变工厂2每周可用于生产新产品