对偶问题与灵敏度分析

1、运筹学第3章 对偶问题与灵敏度分析湖南大学工商管理学院湖南大学工商管理学院本讲内容o 什么是对偶问题o 单纯形法的矩阵描述o 对偶问题的性质o 线性规划的灵敏度分析什么是对偶问题？什么是对偶问题？例1（生产计划问题）：某工厂在计划期内要安排A、B两种产品的生产，已知生产单位产品的利润与所需的劳力、设备台时及原材料消耗，如下：产品A产品B资源限额劳动力设备原材料9434510360工时200台时300公斤单位产品利润70120问：如何安排生产使该厂获利最大？max z=70 x1+120 x2 s.t. 9x14x2360 4x1+5x2200 3x1+10 x2300 x1,x20对偶问题的提

2、出考虑上一讲的考虑上一讲的生产计划问题生产计划问题，若设备和原料都用，若设备和原料都用于对外加工，工厂收取加工费。试问：该厂设备于对外加工，工厂收取加工费。试问：该厂设备工时、劳动力和原料该如何定价？工时、劳动力和原料该如何定价？P需求供给Q均衡点供给-需求函数显然，工厂给这些生产要素定价，既要显然，工厂给这些生产要素定价，既要保证自己的利益保证自己的利益，又要使自己的价格又要使自己的价格具有竞争力具有竞争力价格越高价格越高越好越好价格越低价格越低越好越好一个合理的定价是：收取的加工费不能低于自己一个合理的定价是：收取的加工费不能低于自己生产所得收益，在此前提下使总加工费尽量小。生产所得收益，

3、在此前提下使总加工费尽量小。即：即：Min w=360y1+200y2+300y3s.t. 9y1+4y2+3y370 4y1+5y2+10y3120 y1,y20该线性规划问题与该线性规划问题与原问题原问题互为互为对偶问题对偶问题max z=70 x1+120 x2s.t. 9x14x23604x1+5x22003x1+10 x2300 x1,x20对偶的定义 (LP) Max z = CX (DP) Min w = Yb s.t. AX b s.t. YA C X 0 Y 0 若一个问题的某约束为等式，那么对应的对偶问题的相应变量无非负限制；反之， 若一个问题的某变量无非负限制，那么对应的

4、对偶问题的相应约束为等式。原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量0000= =无约束无约束变变量量n个个n个个约约束束条条件件0000无约束无约束= =约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项建立对偶问题的规则约束条件约束条件变量变量右端项右端项价值系数价值系数对于上表，特别把握以下要点：对于上表，特别把握以下要点：maxmin求求max的对偶问题时，的对偶问题时，变量变量反号反号求

5、求min的对偶问题时，的对偶问题时，约束约束反号反号无限制无限制例例1：写出下列规划问题的对偶问题写出下列规划问题的对偶问题Max z=2x1+2x2-4x3 s.t. X1+3x2+3x330 4x1+2x2+4x380 X1,x2,x30解：min w=30y1+80y2 s.t. y1+4y22 3y1+2y22 3y1+4y2-4 y1,y20 例例2：写出下列规划问题的对偶问题写出下列规划问题的对偶问题min z=2x1+8x2-4x3 s.t. X1+3x2-3x330 -x1+5x2+4x3=80 4x1+2x2-4x350 X10,x20,x3无限制解：max w=30y1+8

6、0y250y3 s.t. y1-y2+4y32 3y1+5y2+2y38 3y1+4y24y3-4 y10,y2无限制,y30 单纯形法的矩阵描述单纯形法的矩阵描述单纯形法的矩阵描述设有线性规划问题设有线性规划问题Max z=CX AXb X0加上松弛变量加上松弛变量XS=(xn+1,xn+2,xn+m),化为标准型化为标准型Max z=CX0Xs AX+IXS=b X0, XS0单纯形法的矩阵描述设设A中存在一可行基中存在一可行基B，相应的变量可分为基变量，相应的变量可分为基变量XB和非基变量和非基变量XN，价值系数也分为，价值系数也分为CB,CN，即，即A=(B,N)X=(XB,XN)TC

7、=(CB,CN)SNBSNBSIXNXBXXXXINBXXIA),(),(Max z=CX0Xs AX+IXS=b X0, XS0bIXNXBXSNB因而因而SNBXBNXBbBX111于是于是Max z=CX0Xs AX+IXS=b X0, XS0SNNBBSNBNBXXCXCXXXCC00),(代入代入XB,目标值目标值SBNBNBXBCXNBCCbBCz111)(检验数检验数),(), 0(1111BCABCCBCNBCCBBBBN)0 , 0 ,(),(1bBXXXXSNB令令XN=0,XS=0,得基可行解得基可行解目标值目标值bBCzB10zIb0CBCBXBCBXNCNXSXBCB

8、XbB1bBCB1NB1NBCCBN11BCB1B矩阵形式描述的单纯形表矩阵形式描述的单纯形表关于对偶问题的基本定理关于对偶问题的基本定理定理1 （弱对偶定理）若若 X(0),Y(0) 分别为（分别为（LP）和（）和（DP）的可）的可行解，那么行解，那么 CX(0) Y(0)b。 (证明证明)该定理说明：如果原问题是最大化问题，则它的任意可行解对应的目标函数值都会小于等于其对偶问题(极小化)的任一可行解对应的目标函数值证明：由证明：由X(0),Y(0) 分别为原问题和对偶问题的可行解分别为原问题和对偶问题的可行解则则, AX(0) b,X(0) 0 Y(0)AC,Y(0) 0因此，因此， Y(

9、0)AX(0) Y(0)b于是，于是， CX(0) Y(0)bMax z=2x1+2x2-4x3 s.t. X1+3x2+3x330 4x1+2x2+4x380 X1,x2,x30min w=30y1+80y2 s.t. y1+4y22 3y1+2y22 3y1+4y2-4 y1,y20 例如例如任意取一些可行解试试看？任意取一些可行解试试看？定理2（无界性）若一个问题无界，则另一个问题不可行若一个问题无界，则另一个问题不可行max z=x1+x2 s.t. -2x1+x2 40 x1-x2 20 x1,x2 0可行域Min w=40y1+20y2s.t. -2y1+y2 1 y1-y2 1

10、y1,y2 0对偶问题显然无可行解！对偶问题显然无可行解！例如例如定理3 （最优性定理）若若 X(0), Y(0) 分别为（分别为（LP）和（）和（DP）的可行解，）的可行解，且且 CX (0) = Y (0) b ，那么，那么 X(0), Y(0)分别为（分别为（LP）和（和（DP）的最优解）的最优解证明证明设设X*是是LP问题的任一可行解，由弱对偶性问题的任一可行解，由弱对偶性CX*Y(0)b=CX(0)从而从而X(0)是最优解是最优解同理同理Y(0)是最优解是最优解定理4 （对偶定理）若其中一个问题有最优解，则另一个问若其中一个问题有最优解，则另一个问题也有最优解，且两者最优值相等题也有

11、最优解，且两者最优值相等证明证明证明：设证明：设X*是是LP问题的最优解，相应的最优基为问题的最优解，相应的最优基为B，则检验数必定满足则检验数必定满足0, 011BCABCCBB令令1*BCYB则有则有0,*YCAY因而因而Y*是对偶问题的可行解是对偶问题的可行解又又*1*CXzbBCbYB因而因而Y*是对偶问题的最优解是对偶问题的最优解0zIb0CBCBXBCBXNCNXSXBCBXbB1bBCB1NB1NBCCBN11BCB1B定理5（互补松弛定理）原问题及其对偶问题的可行解原问题及其对偶问题的可行解X(0)和和Y(0)是是最优解最优解的的充要条件充要条件是：是： Y(0)XS=0，YS

12、X(0)=0XS,YS分别为原问题松弛向量和对偶问题剩余向量分别为原问题松弛向量和对偶问题剩余向量该定理说明：一对对偶问题达到最优，当且仅当松约束对应的对偶变量必定是紧的利用互补松驰定理，可以在知道一个问题的最优解时，利用互补松驰定理，可以在知道一个问题的最优解时，求解其对偶问题的最优解求解其对偶问题的最优解例：例：Min z=2x1+3x2+5x3+2x4+3x5s.t. X1+x2+2x3+x4+3x54 2x1-2x2+3x3+x4+x53 xj 0,j=1,5Max w=4y1+3y2s.t. y1+2y22 y1-2y2 3 2y1+3y2 5 y1+y2 2 3y1+y2 3 y1

13、,y2 0对偶问题对偶问题y1*=4/5,y2*=3/5对偶问题的最优解对偶问题的最优解4/5-2*3/5=-2/50,由互补松弛定理知X(0)ys=0所以x2=0 同理，x3=0,x4=0又y1*0,而Y(0)xs=0,知xs0，即原问题第一个约束取等式同理，第2个约束也取等式定理6若原问题最优解存在，则原问题最优单纯形若原问题最优解存在，则原问题最优单纯形表的检验数行中，表的检验数行中，松弛变量的检验数松弛变量的检验数和和剩余剩余变量的检验数的相反数变量的检验数的相反数即为对偶问题最优解即为对偶问题最优解对偶最优解的经济含义影子价格由对偶定理由对偶定理miiinjjjybxcZ1*1*求求

14、z*对对bi的偏导数的偏导数*iiybz所以对偶最优解为原问题各资源的所以对偶最优解为原问题各资源的影子价格影子价格影子价格非资源的市场价格，而是指系统影子价格非资源的市场价格，而是指系统达到达到最优状态时最优状态时，资源的单位变化引起目标最优值的变化，资源的单位变化引起目标最优值的变化 对偶单纯形法是求解线性规划的另一的基本方法。对偶单纯形法是求解线性规划的另一的基本方法。它是根据对偶原理和单纯形法的原理而设计出来的，它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。问题的单纯形法。 由对

15、偶理论可以知道，对于一个线性规划问题，我由对偶理论可以知道，对于一个线性规划问题，我们能够通过求解它的对偶问题来找到它的最优解。们能够通过求解它的对偶问题来找到它的最优解。什么是对偶单纯形法？ 也就是说，求解原问题（也就是说，求解原问题（LPLP）时，可以从（）时，可以从（LPLP）的）的一个基本解（并不一定是基可行解）开始，逐步迭代，一个基本解（并不一定是基可行解）开始，逐步迭代，使目标函数值（使目标函数值（Z=Y b= CB B-1b =CX）减少，当迭代）减少，当迭代到到XB=B-1b0时，即找到了（时，即找到了（LPLP）的最优解，这就是对）的最优解，这就是对偶单纯形法。偶单纯形法。

16、同原始单纯形求法一样，求解对偶问题（同原始单纯形求法一样，求解对偶问题（DPDP），也），也可以从（可以从（DPDP）的一个基本可行解开始，从一个基本可）的一个基本可行解开始，从一个基本可行解（迭代）到另一个基本可行解，使目标函数值减行解（迭代）到另一个基本可行解，使目标函数值减少。少。例一、用对偶单纯形法求解：例一、用对偶单纯形法求解： )3.2.1(01451232102215129min321321321321jxxxxxxxxxxxxxZj 解：将模型转化为解：将模型转化为 01451232102215129max61632153214321321xxxxxxxxxxxxxxxxZ c

17、j-9-12-15000cBxBbx1x2x3x4x5x60 x4-10-2-2-11000 x5-12-2-3-10100 x6-14-1-1-5001(-9/-1.-12/-1. -15/-5)-Z 0-9-12-15000icj-9-12-15000cBxBbx1x2x3x4x5x60 x4-36/5-9/5-9/5010-1/50 x5-46/5-9/5-14/5001-1/5-15x314/51/51/5100-1/5 (-30/-9.-45/-14 .-15/-1)-Z 42-6-9000-3icj-9-12-15000cBxBbx1x2x3x4x5x60 x4-9/7-9/140

18、01-9/14-1/14-12x223/79/14100-5/141/14(-3/-9.-45/-9. -33/-1)-15x315/71/140101/14-3/14-Z 501/7-3/14000-45/14-33/14cj-9-12-15000cBxBbx1x2x3x4x5x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/9-Z 72000-1/3-3-7/3ii 所以，所以， X*=（2 . 2 . 2 . 0 . 0 . 0），）， Z* =72， 原问题原问题 Z* =72 其对偶问题的最优解为：其对偶问题的最优解为： Y*= (1/3

19、 . 3 . 7/3)，W*= 72 0,43232432min321321321321xxxxxxxxxxxxZ练习：练习： )5 . 4 . 3 . 2 . 1( 04 323 2432max5153214321321jxxxxxxxxxxxxZcj-2-3-400cBxBbx1x2x3x4x50 x4-3-1-2-1100 x5-4-21-301-Z -2-3-400icj-2-3-400cBxBbx1x2x3x4x50 x4-10-5/21/21-1/2-2x121-1/23/20-1/2-Z 0-4-10-1icj-2-3-400cBxBbx1x2x3x4x5-3x22/501-1/

20、5-2/51/5-2x111/5107/5-1/5-2/5-Z 28/500-3/5-8/5-1/5iY=（8/5 . 1/5） X=（2/5 . 11/5 . 0） Z =28/5 为什么要进行灵敏度分析？ 前面对线性规划的讨论，价值系数c，资源系数b和技术系数矩阵A都是已知常数。但现实中，这些系数可能只是估计量，存在误差或随着时间的推移可能有些许变化糟糕！这个月产品市场价格与原计划时发生变化了。年初安排的生产计划还是最优的么？价值系数变化的灵敏度分析设只有一个价值系数cj发生变化，其它系数不变，那么cj在什么范围内变化而最优解不变呢？例(生产计划问题)max z=70 x1+120 x2s

21、.t. 9x14x2360 4x1+5x2200 3x1+10 x2300 x1,x20模型模型价值系数变化的灵敏度分析设只有一个价值系数cj发生变化，其它系数不变，那么cj在什么范围内变化而最优解不变呢？例(生产计划问题)最优单纯形表最优单纯形表cj70 120 0 0 0CBXBbX1 X2 X3 X4 X5 070120X3X1X28420240 0 1 -3.12 1.161 0 0 0.4 -0.20 1 0 -0.12 0.1642800 0 0 -13.6 -5.2考虑考虑C2发生变化发生变化价值系数变化的灵敏度分析设只有一个价值系数cj发生变化，其它系数不变，那么cj在什么范围

22、内变化而最优解不变呢？例(生产计划问题)最优单纯形表最优单纯形表cj70 c2 0 0 0CBXBbX1 X2 X3 X4 X5 070c2X3X1X28420240 0 1 -3.12 1.161 0 0 0.4 -0.20 1 0 -0.12 0.1642800 0 0 -28+0.12c2 14-0.16c2 显然只要-28+0.12c2 014-0.16c2 0 成立，则最优解不变！ 即即 87.5 c2233.33右端项变化的灵敏度分析考察单纯形表考察单纯形表0zIb0CBCBXBCBXNCNXSXBCBXbB1bBCB1NB1NBCCBN11BCB1Bb变化只影响变化只影响 因此，

23、只要因此，只要B-1b0,则最优基不变则最优基不变从而对偶最优解不变，也即影子价格不变从而对偶最优解不变，也即影子价格不变例如生产计划问题例如生产计划问题,考虑考虑b3变化的灵敏度分析变化的灵敏度分析max z=70 x1+120 x2s.t. 9x14x2x3= 3604x1+5x2 +x42003x1+10 x2x5 300 x1,x500 0 0 -13.6 -5.242800 0 1 -3.121.161 0 0 0.4-0.20 1 0 -0.120.16842024X3X1X2070120X1 X2 X3 X4 X5bXBCB70120 0 0 0cj0 0 0 -13.6 -5.

24、242800 0 1 -3.121.161 0 0 0.4-0.20 1 0 -0.120.16842024X3X1X2070120X1 X2 X3 X4 X5bXBCB70120 0 0 0cj最优单纯形表最优单纯形表由此可见，由此可见，(p3,p1,p2)是最优基，即是最优基，即1030540491B16. 012. 002 . 04 . 0016. 112. 311BB-1b0020036016. 012. 002 . 04 . 0016. 112. 313b解得解得 227.586b3400计算机灵敏度分析的例子生产计划问题生产计划问题Excel生产计划问题生产计划问题DM多个参数变化的灵敏度分析百分之百法则百分之百法则：(1)对于所有变化的目标函数系数，当其所有允许增加对于所有变化的目标函数系数，当其所有允许增加百分比和允许减少百分比之和不超过百分比和允许减少百分