运筹学第7讲：对偶问题的基本概念续及影子价格

《运筹学第7讲：对偶问题的基本概念续及影子价格》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7讲：对偶问题的基本概念(续)及影子价格浙江工业大学经贸管理学院曹柬定理5(互补松弛定理):设X*和Y*分别是(P)和(D)的可行解，则它们分别是最优解的充要条件是：Y*(b－AX*)=0(Y*A－C)X*=0运筹学第7讲：对偶问题的基本概念(续)及影子价格Y*(b－AX*)=0(Y*A－C)X*=0上述两个式子称为(P)和(D)的互补松弛关系。若记其中，Pj表示A的第j列，Ri表示A的第i行，则有yi*(bi－RiX*)=0(Y*Pj－Cj)Xj*=0称某一可行点(X*或Y*)处的严格不等式约束为松约束

2、，严格等式约束为紧约束。对于X*和Y*而言，松约束的对偶为紧约束。运筹学第7讲：对偶问题的基本概念(续)及影子价格例1：已知LP问题minZ=3x1+4x2+2x3+5x4s.t.x2+x3－5x4≥2x1+x2－x3+x4≥3x1,x2,x3,x4≥0若不采用单纯形法，求该问题的解运筹学第7讲：对偶问题的基本概念(续)及影子价格例2：已知原问题X*=[0,0,4]T，Z*=12，试求其对偶问题的最优解。maxZ=x1+4x2+3x3s.t.2x1+3x2－5x3≤23x1－x2+6x3≥1x1+x2+x3

3、＝4x1≥0,x2≤0,x3无约束运筹学第7讲：对偶问题的基本概念(续)及影子价格根据经验，单纯形法的迭代次数大约是约束条件数量m的1～1.4倍，当m远大于n时，采用对偶方法求解较好求“min”型的对称形式LP问题时，可先求其对偶问题的解，再用对偶理论对其求解，可省缺由于添加剩余变量、人工变量带来的麻烦运筹学第7讲：对偶问题的基本概念(续)及影子价格习题3-1某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗和各种资源的限制量，如下表所示。该工厂每生产一件甲产品

4、可获利2元，每生产一件乙产品可获利3元，问应如何安排计划使该工厂获利最多？甲乙资源限量设备(台时)128原材料A(kg)4016原材料B(kg)0412运筹学第7讲：对偶问题的基本概念(续)及影子价格习题3-2对于例1，假设该工厂的决策者决定不生产甲、乙两种产品，而是将所有资源外售。你作为一个收购者，该如何决策来购买这些资源？运筹学第7讲：对偶问题的基本概念(续)及影子价格给定原问题(P)及其对偶问题(D)，若两者都存在可行解，则满足：式中bi表示第i种资源的拥有量；yi*表示在资源最优利用条件下对单位第i

5、种资源的估价这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而做的估价，称为影子价格(P42)对偶问题的经济解释：影子价格运筹学第7讲：对偶问题的基本概念(续)及影子价格习题3-1和3-2计划期内相关生产信息如下表所示，问：问如何安排生产计划，使得总利润最大？如果该厂的决策者拟打算将厂里的资源用于接受外来的加工任务，他该如何给每种资源制定收费标准？表中列出新产品丙、丁相关情况，试决定它们是否值得投产？如果生产工艺得到改进，使煤炭节约2％，问能增加多少收益？产品甲乙丙(新)丁(新)资源限制消耗定额资

6、源钢材5312170煤炭2321100设备台时1534150单件利润(万元)1018109例3(习题3-9)影子价格：可认为是某种资源的边际价值例如，在习题3-9中，我们得到钢材、煤炭和设备台时的影子价格分别为：0(万元/单位)，32/7(万元/单位)，6/7(万元/单位)。这意味着，在现有资源的基础上：增加一单位煤炭，总利润可增加32/7万元增加一单位设备台时，总利润可增加6/7万元增加一单位钢材，总利润不增加，钢材过剩运筹学第7讲：对偶问题的基本概念(续)及影子价格影子价格的作用指示企业内部挖潜的方向为

7、新产品开发、投资决策作参考分析工艺改变后对资源及总利润的影响分析产品价格变动后对资源及总利润的影响灵敏度分析运筹学第7讲：对偶问题的基本概念(续)及影子价格对偶问题的另一求解方法以习题3-9为例进行说明。若(P)是max型，(D)是min型，则(P)的变量与(D)的剩余变量数量相同，(P)的松弛变量与(D)的变量数量相同(P)的松弛变量对应的-δj，即为(D)的变量最优解(P)的第i个变量对应于(D)的第i个剩余变量，(D)的第j个变量对应于(P)的第j个松弛变量可以直接从最终单纯形表中看出资源的影子价格，

8、即-δj反之，若(P)为min型，则(P)的变量对应于(D)的松弛变量，(P)的剩余变量对应于(D)的变量运筹学第7讲：对偶问题的基本概念(续)及影子价格作业：习题3-6,习题3-7