《对偶理论和灵敏度分析》由会员分享，可在线阅读，更多相关《对偶理论和灵敏度分析（68页珍藏版）》请在金锄头文库上搜索。
1、第二章 对偶理论和灵敏度分析,窗含西岭千秋雪，门泊东吴万里船,对偶是一种普遍现象,知识点要求,熟悉对偶问题与原问题的对应关系及对偶问题的经济意义； 理解影子价格的含义，了解影子价格的应用； 熟悉灵敏度分析的概念和内容，掌握灵敏度分析的基本方法。,主要内容,对偶问题的提出 原问题与对偶问题 线性规划对偶定理 影子价格 灵敏度分析 参数线性规划（自学）,1 单纯形法的矩阵描述,例. 一个标准形式的线性规划为：,将系数矩阵分为 B N I 则对应的原变量分为 原目标系数分为,则矩阵形式的 LP 模型为：,可得：,由上可知，若已知 B-1 和 b ，则易得最优解。, ,B N I,Z,b,b,0,B-
2、1 b I B-1 N B-1,由上表可知，最优基 B 的逆 B-1 可在最终表中找到，为初始单位矩阵在最终表中对应的元素。,在表中多次出现 CBB-1 ，则令 Y=CBB-1 ，为单纯型算子。,已知线形规划的最优基变量为XB（x4, x1 ,x2 ) , 即最优基及其逆如下，求最优解,任何线性规划问题都有其对偶问题 对偶问题有其明显的经济含义,Original Problem & Dual Problem,第二节 对偶原理及其经济意义,引例,企业可使用资源A、B生产产品1、2、3、4获利，也可出售资源A、B给商人获利。厂家如何安排4种产品的生产计划，使获利最多？商人如何确定购买价格，使支出最
3、少？,目标函数 min g(y)=25y1+15y2,商人,厂方,产品1资源售卖所得,产品2资源售卖所得,产品3资源售卖所得,产品4资源售卖所得,解题,线性规划原问题与 对偶问题的表达形式(1),原问题,对偶问题,线性规划原问题与 对偶问题的表达形式(2),对偶问题的特点,一个问题中的约束条件个数等于另一个问题中的变量数； 一个问题中目标函数的系数是另一个问题中约束条件的右端项； 约束条件在一个问题中为“”，则在另一问题中为变量“0”； 目标函数在一个问题中是求极大值，在另一问题中则为求极小值,原问题和对偶问题的关系,maxZ= minW,maxZ,原问题,minW,对偶问题,例1 写出下述线
4、性规划的对偶问题,例2,写出上例中对偶问题的对偶，说明原问题与对偶问题的对称关系。,解(1),第一步：将上例中的对偶问题改写为,解(2),第二步：按从原问题写出对偶问题的方法写出上面线性规划问题的对偶问题,解(3),第三步：将约束条件两端均乘上（-1），又因 等价于求 ，得到,这就是例1中原问题， 可见对偶问题与原问题互为对偶。,原问题与对偶问题的对应关系,目标函数 min,目标函数中变量的系数,约束条件右端项,目标函数 max,例. 写出下面LP的对偶规划,第三节线性规划的对偶定理,Dual Theorem of LP,为了便于讨论，下面不妨总是假设,定理 弱对偶性。若 是原问题的可行解,
5、是对偶问题的可行解，则存在,1、弱对偶性,2、最优性,若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0, Y0分别是相应问题的最优解,3、无界性,如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。,4 、强对偶性,如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。,5、互补松弛定理,设X*, Y*分别为原问题和对偶问题的最优解的充要条件如下。 对原问题有 对对偶问题有,例、已知线性规划问题：,要求：（a）写出其对偶问题； (b)已知原问题最优解X*=(2, 2, 4, 0)，试根据对偶理论，直接求出对偶问题的最
6、优解。,解：,解：(a)其对偶规划为：,（b）由互补松弛定理，带入原规划最优解X*=(2, 2, 4, 0)，得 因最后一个约束松弛变量0，则y4=0,又因为x10, x20, x30，所以其中y4=0，求出,目标函数中bi 是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量； 对偶变量yi的意义代表对一个单位第i种资源的估价。 这种估价不是资源的市场价格，而是根据资源在生产中做出的贡献而作的估价，为区别起见，称为影子价格(shadow price)。,总结对偶问题的基本性质可行解为最优解时的性质设X是原问题的可行解，Y是对偶问题的可行解， 当 CX=Yb 时，X和Y为最优解。对偶定理
7、若原问题有最优解，则对偶问题也有最优解，且目标函数值相等。,无界性 若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。,互补松弛定理 Y*Xs=0 YsX*=0,第四节 影子价格,Shadow Price,目标函数中bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量； 对偶变量yi的意义代表对一个单位第i种资源的估价。 这种估价不是资源的市场价格，而是根据资源在生产中做出的贡献而作的估价，为区别起见，称为影子价格(shadow price)。,如果例1中的第个约束条件右端项增加1，变为6xl+2x225，可行域边界线将移至,影子价格实解,代入目标函数得 ，说明第2种资源
8、的边际收入为1/4。又如第个约束条件右端项增加1，可行域的边界线将移至，代人目标函数得z=9，说明第3种资源的边际收入为1/2。,影子价格是一种边际价格， 将中z对bi求偏导数得 这说明yi的值相当于在给定的生产条件下，bi每增加一个单位时目标函数z的增量。,“对偶解” y的定义（也叫“影子价格” Shadow Price） 在其他条件不变的情况下，单位资源 变化所引起的目标函数最优值的变化 ，也 可看作资源在最优决策下的边际价值。,约束方程有三种形式，对应三种对偶解： 1 . “” 资源类约束（上限） y 0 2 . “” 需求类约束（下限） y 0 3 . “” 平衡关系 y不定,影子价格
9、的性质： 资源类约束影子价格反映资源的稀缺程度 需求类约束影子价格反映需求的强制程度 平衡类约束处于平衡状态，摇摆不定 影子价格反映企业的技术、管理水平。,在最优单纯型表中寻找影子价格最优表的检验数对应着影子价格 (最优表） 例. 书P21, 书P23,影子价格的应用,(1)决定投资方向，如果企业有一定的资金用于扩大再生产购买资源，那么很显然应该将有限资金优先购买影子价格较高的资源。(2)决定该企业能够接受某种资源的最高市场价格。因为某资源的市场价格高于影子价格，购买后是会亏损的。,影子价格的应用,(3)可以确定新产品价格，例1.1的影子价格为Y =（0，1.5，0.125，0），现在该单位决
10、定生产一种新产品III消耗A，B，C，D四种资源的数量为（2，2，4，1）单位，则新产品III利润一定要大于（0，1.5，0.125，0）* （2，2，4，1）T=3.5 时才能增加该单位的收益，如产品利润低于3.5的话生产III产品是不合算的。 (4)用于分析技术改造节约资源的效益分析。,例2.10,在例2.8得到例1.1的对偶解 ，现需要进行以下决策： （1）如果决定购入一种资源以扩大生产，应首先选择追加A、B、C、D中的哪种资源？ （2）如果B资源的市场价格为2，是否会决定购入？ （3）现决定生产一种新产品，该产品对A、B、C、D四种资源的消耗量分别为2、2、4、1，则该产品最低定价应是
11、多少？ （4）现有一种工艺改进后，每生产一个产品可以节约1个A资源和1个B资源，实施该工艺，每生产一个产品需要增加2元成本，则该工艺改进是否值得实施？,第五节灵敏度分析(Sensitivity Analysis),一. 灵敏度分析的概念,(1)、参数A，b，C在什么范围内变动，对当前方案无影响？,(2)、如果最优方案改变，如何用简便方法求新方案？,最优解的判别条件： （1）可行性 B-1b 0 （2）最优性 CN -CB B-1N 0,二. Cj 的灵敏度范围 例. 分析目标系数Cj 的灵敏度变化范围,maxZ=4X1 +5X2 +X3 +7X4,8X1+ 4X2 + 6X3+ X4 120X
12、1+ 3X2 + 2X3+ 2X4 30 3X1+ 8X2 + 5X3+ 2X4 150 X1 X4 0,1. CN （非基变量目标系数）的 灵敏度范围,即 CN j,对照判别条件，只影响 CN -CB B-1N 0 ，则,（ CN CN ） CB B-1N 0,可得 CN （CN -CB B-1N）,2. CB （基变量目标系数）的 灵敏度范围,对照判别条件， CB变化影响最优性，则CN - CB B-1N 0 CN (CB + CB)B-1N 0,CBB-1N CN CBB-1N,即 1. ,求C1 ， C4 的灵敏度范围,2. 取 之间的值，即为灵敏 度范围,三. bi 的灵敏度范围,对
13、照判别条件， bi变化影响可行性 (B-1b 0) B-1 ( b + b) 0 B-1 b -B-1 b , 即：,1. ,2. 取 之间的值，即为灵敏度范围,求解步骤：, 试求b1 ， b2 ， b3 的灵敏度范围，并分析当其变化超出灵敏度范围时，对偶解有 何变化？,例6中 ，c2=3，x2的系数向量变为：试分析最优解的变化。,四、aij变化的灵敏度分析,解题,先将其作为一个新的变量x2列入最终单纯形表中,因x2已变换为x2 ，故用单纯形法算法将替换出基变量中的x2 ，并在下一个表中不再保留x2 ，得,表中原问题与其对偶问题均为非可行解，因此通过引进人工变量，将原问题转化为可行解，再用单纯
14、形法继续计算,新的最优解为,经过迭代运算得到最终单纯形表为：,四. 参数变化对最优值的影响（灵敏度范围内变化）,非基变量的目标系数变化最优值有效，且最优值不变,=B-1b Z CB B-1b,2. 基变量的目标系数变化X 不变，,3. 常数项变化X =B-1( b+ b),例. 在上例中的数据，b1的灵敏度 范围为 15b1 240，若b1 现从120增加到135， 试求此时的最优解。,解2： 按对偶解的意义Z= b*y1=15*(1/15)=1Z=Z+ Z=112+1=113,1、P77 2.3,本章强化训练,2、P78 2.4,已知线形规划(如下)，加入松弛变量后，计算得 最终表如下， 试求 1)C1, C2, C3的灵敏度范围；2）b1, b2, b3的灵敏度范围；3）当b1由5增加到7时，求最优值,解：1） C1, C3为基变量目标系数, C2为非基变量目标系数 ，则：,（2）,（3）因b1由5增加到7，在灵敏度范围内变化，最优解有效,则 X*= ( x3, x1, x6) T =B1 （bb)=(5/2, 5/2, 3/2) T +( 1, -1/3, 1/3) T =(7/2, 13/6, 11/6),
