天津大学运筹学2对偶理论与灵敏度分析.ppt

1、第二章 对偶理论与灵敏度分析Dual Theory and Sensitivity Analysis,运 筹 学Operations Research,2.1 线性规划的对偶理论 2.2 灵敏度分析,2.1 线性规划的对偶理论,一、对偶问题的提出与模型,1、对偶问题的提出 例1 第一章中的例1。,例2 这时有另厂提出要购买A、B、C全部资源，在原厂可接受的条件下，单价多少可使另厂付费最低？,例1称为例2的原问题，记为(P),例2称为例1的对偶问题，记为(D),2、对偶模型的一般形式 以例2为例，原问题为： (P)：,记 Y(y1, y2, y3)，则对偶问题为： (D)：,这是最常见的对偶模型

2、形式，称为对称式对偶模型。二者间具有十分对称的对应关系。,对偶模型的特点： （1）P为max型，D为min型 （2）P的变量个数D的约束个数 （3）P的约束个数D的变量个数 （4）P的目标函数系数 D的资源限制向量 （5）P的资源限制向量 D的目标函数系数 （6）P的技术系数矩阵 D的技术系数矩阵转置,(P)：,(D)：,（7）若P的某个约束为“=”型，则D的相应变量为自由； 若P的某个变量为自由，则D的相应约束为“=”型。,令 y3y3- y4, ，则有：,3、如何写出LP模型的对偶模型,（1）若LP为max型，则尽量化成(P)形式。（等式、自由变量不用转换）,(P),(D),（2）若LP为

3、min型，则尽量化成(D)形式。（等式、自由变量不用转换）,例3 写出下面线性规划的对偶规划模型。,解：设对偶变量为y1, y2, y3，对偶目标为w，则其对偶规划模型为：,练习 写出下面LP的对偶模型。,对偶模型为：,二、对偶性质与定理,1、对称性：（P）与（D）互为对偶。,2、弱对偶性,设X、Y 分别为（P）、（D）的任一可行解，则,由此可推出： 3、无界性 若（P）为无界解，则（D）无可行解； 若（D）为无界解，则（P）无可行解。,4、解的最优性,5、对偶定理,若（P）有最优解，则（D）也有最优解，且二者最优值相等。,则,设 分别为（P）、（D）的可行解，且,问题： （1）由性质5可知，

4、对偶问题最优解的表达式Y* =？ Y*= CB B-1 ；其中B为原问题的最优基。 （2）求Y*是否有必要重新求解（D）？,Y*即为（P）终表的XS的检验数的负值； 若无XS，则用Y*= CB* (B*)-1计算。,例4 已知求解下列LP模型的单纯形终表如下， 求其对偶模型的最优解。,X*=（2，0）T ; z*=5 Y*=（0，0.5）; w*=5,6、松紧定理（互补松弛性）,说明： 在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式； 另一方面，如果约束条件取严格不等式，则其对应的对偶变量一定为零。,设 分别为（P）、（D）的可行解，则有：,原问题的变量

5、X,在一对变量中，其中一个大于0，另一个一定等于0。,松弛变量Xs,松弛变量Ys,对偶问题的变量Y,例5 已知线性规划问题,已知其对偶问题的最优解为： y1*=4/5，y2*=3/5，z*=5 试用对偶理论找出原问题的最优解。,练习 已知线性规划问题,已知原问题的最优解为：x1*=2，x2*=2， x3*=4， x4*=0 试用对偶理论找出对偶问题的最优解。,练习 写出下面LP的对偶模型。,对偶模型为：,三、对偶问题的经济解释,1、对偶最优解的经济解释 资源的影子价格（Shadow Price）,Y*=(y1* , y2* ,， ym* ）为DP的最优解，则yi* 表示 LP某资源bi 变化1

6、个单位对目标产生的影响，称 yi* 为 bi的影子价格。,CBB-1对偶问题的最优解买主的最低出价 原问题资源的影子价格 当该资源增加1单位时引起的总收入的增量 卖主的内控价格。,例6 例1的单纯形终表如下：,请指出资源A、B、C的影子价格，并解释其经济意义。,影子价格在管理决策中的作用： （1）影子价格市场价格,若,影子价格市场价格，则应,影子价格市场价格，则应,买进该资源,卖出该资源,（2）影子价格反映了资源的稀缺性，影子价格 越高，则越稀缺。,例如：资源C的影子价格为0，则表明有剩余。,影子价格的历史：,1939年，前苏联数学家康特罗维奇提出了线性规划方法，计算得出一些副产品数字，可以作

7、为核算价格使用，他称为“分解乘数”。后来被美国经济学家库普曼斯称为“影子价格”。 二战时期库普曼斯看到, 竞争经济中的资源分配可以看成解一个巨大的线性规划问题，在竞争经济中技术效率基本上与价格系统和资源分配相联系。 康特罗维奇对影子价格指出：它被称为客观决定的评价, 是对一个给定问题内在决定的、货物和要素等价物的价值指标，并表示在极值状态波动中如何能交换货物和要素。 他们一致得出结论，影子价格的利用，创造了生产决策分散化的可能性。 1975年他们同时获得诺贝尔经济学奖。,例7影子价格的应用：合理利用资源,2、对偶约束的经济解释 产品的机会成本（Opportunity Cost）,机会成本：是指

8、为了得到某种东西而所要放弃另一些东西的最大价值。 机会成本小的具有比较优势，即把一定资源投入某一用途后所放弃的在其他用途中所能获得的最大利益。 例如：某块土地如果选择养某种家禽就不能选择养其他家禽。假设养猪可以获得9万元，养鸡可以获得7万元，养鸭可以获得8万元，那么： 养猪的机会成本是8万元； 养鸡的机会成本为9万元； 养鸭的机会成本也为9万元。,机会成本 表示减少一件产品所节省的资源可以增加的利润,y1 y2 ym,产品的机会成本：,3、对偶松弛变量的经济解释 产品的差额成本（Differential Cost）,差额成本机会成本利润,机会成本,差额成本,利润,4、互补松弛关系的经济解释,在

9、利润最大化的生产计划中： （1）影子价格大于0的资源没有剩余； （2）有剩余的资源影子价格等于0； （3）安排生产的产品机会成本等于利润； （4）机会成本大于利润的产品不安排生产。,2.2 灵敏度分析,任务： 讨论模型的系数或变量发生小的变化时对解的影响（如它们在何范围内变化时可使原最优解或最优基不变？） 主要讨论A、b、C和变量结构变化时对解的影响。,1、资源数量b变化时的分析（只影响解的可行性）,问题：b在何范围变化时，不影响最优基？ 方法：,（1）B资源的影子价格是多少？ （2）使最优基仍适用的B资源的变化范围为何？（b2在何范围变化时，不影响最优基？） （3）若有人愿以每kg 0.1元的价格向该厂供应25kg B资源，是否值得接受？,2、价格系数C变化时的分析,价格从cj变为cj +cj时，只影响最优性，分两种情况讨论：,（1） cj是非基变量xj的价格系数：,（2） cj是基变量xj的价格系数：,乙产品的价格c2在何范围变化时，最优解不变？,3、技术系数A变化时的分析,方法：,（1）增加新变量xn+1 经济意义：第n+1种新产品是否应当投产； 数学意义： xn+1是否应进基。,经济意义：,利润,影子价*资源单耗,若现又考虑一新产品丙，其资源单耗为2，6，3，售价为5，问该产品是否可投产？,（2）技术系数aij变化 约束系数