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

第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*)处的严格不等式约束为松约束，严格等式约束为紧约束。对于X*和Y*而言，松约束的对偶为紧约束。运筹学第7讲：对偶问题的基本概念(续)及影子价格例2：已知原问题X*=[0,0,4]T，Z*=12，试求其对偶问题的最优解。maxZ=x1+4x2+3x3s.t.2x1+3x2－5x3

≤

23x1－x2+6x3

≥1

x1+x2+x3＝4

x1≥0,x2

≤0,x3无约束运筹学第7讲：对偶问题的基本概念(续)及影子价格根据经验，单纯形法的迭代次数大约是约束条件数量m的1～1.4倍，当m远大于n时，采用对偶方法求解较好求“min”型的对称形式LP问题时，可先求其对偶问题的解，再用对偶理论对其求解，可省缺由于添加剩余变量、人工变量带来的麻烦运筹学第7讲：对偶问题的基本概念(续)及影子价格习题3-1某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗和各种资源的限制量，如下表所示。该工厂每生产一件甲产品可获利2元，每生产一件乙产品可获利3元，问应如何安排计划使该工厂获利最多？甲乙资源限量设备(台时)128原材料A(kg)4016原材料B(kg)0412运筹学第7讲：对偶问题的基本概念(续)及影子价格给定原问题(P)及其对偶问题(D)，若两者都存在可行解，则满足：式中bi表示第i种资源的拥有量；yi*表示在资源最优利用条件下对单位第i种资源的估价这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而做的估价，称为影子价格(P42)对偶问题的经济解释：影子价格运筹学第7讲：对偶问题的基本概念(续)及影子价格习题3-1和3-2计划期内相关生产信息如下表所示，问：问如何安排生产计划，使得总利润最大？如果该厂的决策者拟打算将厂里的资源用于接受外来的加工任务，他该如何给每种资源制定收费标准？表中列出新产品丙、丁相关情况，试决定它们是否值得投产？如果生产工艺得到改进，使煤炭节约2％，问能增加多少收益？产品甲乙丙(新)丁(新)资源限制消耗定额资源钢材5312170煤炭2321100设备台时1534150单件利润(万元)1018109例3(习题3-9)影子价格：可认为是某种资源的边际价值例如，在习题3-9中，我们得到钢材、煤炭和设备台时的影子价格分别为：0(万元/单位)，32/7(万元/单位)，6/7(万元/单位)。这意味着，在现有资源的基础上：增加一单位煤炭，总利润可增加32/7万元增加一单位设备台时，总利润可增加6/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)