运筹学06-线性规划的灵敏度分析与对偶.ppt

1、第六章 单纯型法灵敏度分析与对偶,6.1 单纯型表的灵敏度分析 6.2 线性规划的对偶问题 6.3 对偶规划的基本性质 6.4 对偶单纯型法,上表中6个常数 a1 , a2 , a3 , b , 1 , 2 取值在什么范围可使 1、现可行解最优，且唯一？何时不唯一？ 2、现基本解不可行； 3、问题无可行解； 4、无有限最优解； 5、现基本解可行，由 x1 取代 x6 目标函数可改善。,线性规划标准形式,(1)、参数A，b，C在什么范围内变动，对当前方案无影响？,(2)、参数A，b，C中的一个(几个)变动，对当前方案影响？,(3)、如果最优方案改变，如何用简便方法求新方案？,当线性规划问题中的一

2、个或几个参数变化时，可以用单纯形法从头计算，看最优解有无变化，但这样做既麻烦又没有必要。,灵敏度分析一词的含义是指对系统或事物因周围条件变化显示出来的敏感程度的分析。,灵敏度分析的步骤： 1将参数的改变通过计算反映到最终单纯形表上来； 2检查原问题的解是否仍为可行解； 3检查原问题的最优解是否仍为最优解； 4按下表所列情况得出结论决定继续计算的步骡。,6.1.1 目标函数系数的灵敏度分析,考虑检验数,(1) 若ck是非基变量的系数：,例,解：最优单纯形表,试求 c3 在多大范围内变动时，原最优解保持不变。,从表中看到3= c3+c3-(c2a13+c1a23 ) 可得到c3 9/5 时，原最优

3、解不变。,(2) 若 ck 是基变量的系数,例,求c2在什么范围内变动时，原最优解保持不变。,例: 下表为最优单纯形表,考虑基变量系数c2发生变化,从表中看到 可得到 -3c21 时，原最优解不变。,设分量 br 变化为 br + br ，根据前面的讨论： 最优解的基变量 xB = B-1b，那么只要保持 B-1(b + b) 0 ， 则最优基不变，即基变量保持，只有值的变化； 否则，需要利用对偶单纯形法继续计算。,6.1.2 右端项的灵敏度分析,例,求当b1在由16变动为20时，原最优解是否保持不变，若变动求出新的最优解。,解: 下表为最优单纯形表,将b代入原最优单纯形表中，运用对偶单纯形法

4、计算最优解。,经一次迭代后，求得新的最优解: ( 4 0 2 0 0 )T,(1) 增加一个变量 增加一个变量，相当于系数矩阵增加一列。 增加变量 xn+1 则有相应的pn+1 ,cn+1 。 那么 计算出B-1pn+1 , n+1=cn+1-cB pn+1 填入最优单纯形表, 若 n+1 0 则 最优解不变； 否则，进一步用单纯形法求解。,6.1.3 约束系数的灵敏度分析,例:前例增加x6 , p6=( 2, 6, 3 )T, c6=5 计算得到,用单纯形法进一步求解，可得： x* = ( 1,1.5,0,0,0,2 )T f* = 16.5,(2) 增加一个约束条件 增加一个约束条件相当于

5、系数矩阵中增加一行。 增加一个约束条件之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。,例:前例增加3x1+ 2x215，原最优解不满足这个约束。于是,经对偶单纯形法迭代一步，可得： 最优解为（3.5, 2.25, 0, 0, 3, 2 )T，最优值为 13. 75,(3) 技术系数改变 (计划生产的产品工艺结构改变) 非基变量xj工艺改变 只影响单纯形表Pj 列， j . 关键看 j 0? 还

6、是0? . 用增加新变量类似方法解决。 基变量xj工艺改变，复杂，在此暂不予讨论。,最优单纯形表为,（1）P3由(-1 3)T改为(-1 2)T （2）P1由(-1 2)T改为(1 1)T,解：（1）P3由(-1 3)T改为(-1 2)T 由最优单纯形表可知,所以原最优解不变,（2）P1由(-1 2)T改为(1 1)T 由最优单纯形表可知,代入最优单纯形表，用P1代替P1,6.2 线性规划的对偶问题,(1) 对偶问题的提出,例1、生产组织与计划问题,A, B各生产多少, 可获最大利润?,可用资源,煤 劳动力 仓库,A B,1 2 3 2 0 2,单位利润,40 50,30 60 24,Max

7、Z= 40 x1 +50 x2,x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0,s.t,目标函数,约束条件,如果因为某种原因，不愿意自己生产，而希望通过将现有资源承接对外加工来获得收益，那么应如何确定各资源的使用价格？,两个原则,所得不得低于生产的获利 要使对方能够接受,设三种资源的使用单价分别为 y1 , y2 , y3,y1 y2 y3,生产单位产品A的资源消耗所得不少于单位产品A的获利,生产单位产品B的资源消耗所得不少于单位产品B的获利,y1 +3 y2 40,2y1 + 2 y2 + 2y3 50,通过使用所有资源对外加工所获得的收益,W = 30y1

8、+ 60 y2 + 24y3,根据原则2 ，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：,Min W = 30y1 + 60 y2 + 24y3,y1 + 3y2 40 2y1 + 2 y2 + 2y3 50 y1 , y2 , y3 0,s.t,目标函数,约束条件,原线性规划问题称为原问题，此问题为对偶问题， y1 , y2 , y3 称为影子价格,(2) 对偶问题的形式,定义 设原线性规划问题为 则称下列线性规划问题,为其对偶问题，其中yi (i=1,2,m) 称为对偶变量。,上述对偶问题称为对称型对偶问题。,原问题简记为(P)，对偶问题简记为(D),原始问题 Max

9、 Z=CX s.t. AXb X 0,b,A,C,Max,n,m,对偶问题 Min W=Yb s.t.YATC Y 0,Min,CT,AT,bT,n,m,例2：求线性规划问题的对偶规划,解：由原问题的结构可知为对称型对偶问题,例3：求线性规划问题的对偶规划,解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。,例4：求线性规划问题的对偶规划,解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。,上式已为对称型对偶问题，故可写出它的对偶规划,令,则上式化为,对偶关系对应表,原问题 对偶问题 目标函数类型 Max Min 目标函数系数 目标函数系数 右边

10、项系数 与右边项的对应关系 右边项系数 目标函数系数 变量数与约束数 变量数n 约束数 n 的对应关系 约束数m 变量数m 原问题变量类型与 0 对偶问题约束类型 变量 0 约束 的对应关系 无限制 原问题约束类型与 0 对偶问题变量类型 约束 变量 0 的对应关系 无限制,6.3 对偶问题的基本性质,定理1 对偶问题的对偶就是原问题(对称性),定理2 (弱对偶定理),分别为(P), (D)的可行解，则有C b,，,由 A, C,X,0 有,y A,X C,X,所以,C X ,X ,推论2、(P)有可行解, 但无有限最优解，则(D)无可行解。,推论1、(P), (D)都有可行解，则必都有最优解

11、。,定理3、,分别为(P), (D)的可行解，且,C,=,b, 则它们是(P), (D) 的最优解。,定理4(强对偶性) 若一对对偶问题(P)和(D)都有可行解，则它们都有最优解，且目标函数的最优值必相等。,证明：,(1) 当X*和Y*为原问题和对偶问题的一个可行解,有,原问题目标函数值,对偶问题目标函数值,所以原问题的目标函数值有上界，即可找到有限最优解；对偶问题有下界，也存在有限最优解。,(2) 当X*为原问题的一个最优解，B为相应的最优基,通过引入松弛变量Xs,将问题(P)转化为标准型,令,令,所以Y*是对偶问题的可行解，对偶问题的目标函数值为,X*是原问题的最优解，原问题的目标函数值为

12、,推论： 若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等。,一对对偶问题的关系，有且仅有下列三种： 都有最优解，且目标函数最优值相等； 两个都无可行解； 一个问题无界，则另一问题无可行解。,定理5 （互补松弛性） 若 X , Y分别为(P) , (D)的可行解，则X , Y为最优解的充要条件是：,同时 成立,证: (必要性）,原问题 对偶问题,影子价格,(1) 原始问题是利润最大化的生产计划问题,单位产品的利润（元/件）,产品产量（件）,总利润（元）,资源限量（吨）,单位产品消耗的资源（吨/件）,剩余的资源（吨）,消耗的资源（吨）,(2) 对偶问题,资源限量（吨）

13、,资源价格（元/吨）,总利润（元）,对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格（Shadow Price）,原始和对偶问题都取得最优解时，最大利润 Max Z=Min W,(3) 资源影子价格的性质,影子价格越大，说明这种资源越是相对紧缺 影子价格越小，说明这种资源相对不紧缺 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0,y1 y2 ym,(4) 产品的机会成本,机会成本 表示减少一件产品所节省的资源可以增加的利润,增加单位资源可以增加的利润,减少一件产品可以节省的资源,机会成本,利润,差额成本,(5) 产品的差额成本（Reduced

14、Cost）,差额成本=机会成本 - 利润,(6) 互补松弛关系的经济解释,在利润最大化的生产计划中 （1）边际利润大于0的资源没有剩余 （2）有剩余的资源边际利润等于0 （3）安排生产的产品机会成本等于利润 （4）机会成本大于利润的产品不安排生产,6.5 对偶单纯形法,定义：设A=(B N)，其中B是一个非奇异的m m阶方阵，对应地C=(CB CN)，则YB=CB的解Y*=CBB-1称为对偶问题(D)的一个基本解；若Y*还满足Y*NCN，则称Y*为(D)的一个基可行解；若有Y*NCN，则称Y*为非退化的基可行解，否则称为退化的基可行解。,(1) 对偶单纯形法的基本原理,定义：如果原问题(P)的

15、一个基本解X与对偶问题(D)的基可行解Y对应的检验数向量满足条件 则称X为原问题(P)的一个正则解（基本解不一定可行）。,原问题(P)的正则解X与对偶问题(D)的基可行解Y一一对应,对偶单纯形法的基本思想,从原规划的一个基本解出发，此基本解不一定可行(正则解)，但它对应着一个对偶基可行解（检验数非正），所以也可以说是从一个对偶基可行解出发；然后检验原规划的正则解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个正则解，此正则解对应着另一个对偶基可行解（检验数非正）。 如果得到的正则解的分量皆非负则该正则解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的正则解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解