《对偶问题的基本概念(续)及影子价格》由会员分享，可在线阅读，更多相关《对偶问题的基本概念(续)及影子价格（11页珍藏版）》请在金锄头文库上搜索。
1、第7讲：对偶问题的基本概念(续)及影子价格,浙江工业大学经贸管理学院 曹柬,定理5 (互补松弛定理): 设X*和Y*分别是(P)和(D)的可行解，则它们分别是最优解的充要条件是：,运筹学 第7讲：对偶问题的基本概念(续)及影子价格,上述两个式子称为(P)和(D)的互补松弛关系。 若记,其中，Pj 表示A的第j 列，Ri 表示A的第i 行，则有,称某一可行点(X*或Y*)处的严格不等式约束为松约束，严格等式约束为紧约束。对于X*和Y*而言，松约束的对偶为紧约束。,运筹学 第7讲：对偶问题的基本概念(续)及影子价格,例1：已知LP问题,若不采用单纯形法，求该问题的解,运筹学 第7讲：对偶问题的基本
2、概念(续)及影子价格,例2：已知原问题,X* = 0, 0, 4T，Z* = 12，试求其对偶问题的最优解。,运筹学 第7讲：对偶问题的基本概念(续)及影子价格,根据经验，单纯形法的迭代次数大约是约束条件数量m的11.4倍，当m远大于n时，采用对偶方法求解较好求“min”型的对称形式LP问题时，可先求其对偶问题的解，再用对偶理论对其求解，可省缺由于添加剩余变量、人工变量带来的麻烦,运筹学 第7讲：对偶问题的基本概念(续)及影子价格,给定原问题(P)及其对偶问题(D)，若两者都存在可行解，则满足：,式中bi 表示第i 种资源的拥有量；yi*表示在资源最优利用条件下对单位第i 种资源的估价这种估价
3、不是资源的市场价格，而是根据资源在生产中作出的贡献而做的估价，称为影子价格(P57),对偶问题的经济解释：影子价格,运筹学 第7讲：对偶问题的基本概念(续)及影子价格,习题3-1和3-2,计划期内相关生产信息如下表所示，问：问如何安排生产计划，使得总利润最大？如果该厂的决策者拟打算将厂里的资源用于接受外来的加工任 务，他该如何给每种资源制定收费标准？表中列出新产品丙、丁相关情况，试决定它们是否值得投产？如果生产工艺得到改进，使煤炭节约2，问能增加多少收益？,例3 (习题3-9),影子价格：可认为是某种资源的边际价值,例如，在习题3-9中，我们得到钢材、煤炭和设备台时的影子价格分别为：0(万元/
4、单位)， 32/7(万元/单位)， 6/7(万元/单位)。这意味着，在现有资源的基础上：增加一单位煤炭，总利润可增加32/7万元增加一单位设备台时，总利润可增加6/7万元增加一单位钢材，总利润不增加，钢材过剩,运筹学 第7讲：对偶问题的基本概念(续)及影子价格,影子价格的作用,指示企业内部挖潜的方向为新产品开发、投资决策作参考分析工艺改变后对资源及总利润的影响分析产品价格变动后对资源及总利润的影响,运筹学 第7讲：对偶问题的基本概念(续)及影子价格,对偶问题的另一求解方法,以习题3-9为例进行说明。若(P)是max型，(D)是min型，则(P)的变量与(D)的剩余变量数量相同，(P)的松弛变量与(D)的变量数量相同(P)的松弛变量对应的-j，即为(D)的变量最优解(P)的第i 个变量对应于(D)的第i 个剩余变量，(D)的第j 个变量对应于(P)的第j 个松弛变量可以直接从最终单纯形表中看出资源的影子价格，即-j反之，若(P)为min型，则(P)的变量对应于(D)的松弛变量，(P)的剩余变量对应于(D)的变量,运筹学 第7讲：对偶问题的基本概念(续)及影子价格,作业：习题3-6, 习题3-7,
