[数学]运筹学04-对偶问题.ppt

* * * * * * cj 2 -1 1 0 0 0 B-1b θ cB xB x1 x2 x3 x4 x5 x6 0 x4 3 1 1 1 0 0 60 20 0 x5 1 -2 2 0 1 0 10 10 0 x6 1 1 -1 0 0 1 20 20 σj 2 -1 1 0 0 0 0 0 x4 0 7 -5 1 -3 0 30 30/7 2 x1 1 -2 2 0 1 0 10 0 x6 0 3 -3 0 -1 1 10 10/3 σj 0 3 -3 0 -2 0 20 0 x4 0 0 2 1 -2/3 -7/3 20/3 2 x1 1 0 0 0 1/3 2/3 50/3 -1 x2 0 1 -1 0 -1/3 1/3 10/3 σj 0 0 0 0 -1 -1 30 * * * * * * 例3 解： * * cj 2 3 -5 -M 0 -M B-1b θ cB xB x1 x2 x3 x4 x5 x6 -M x4 1 1 1 1 0 0 7 7 -M x6 2 -5 1 0 -1 1 10 5 σj 3M+2 -4M+3 2M-5 0 M 0 -17M -M x4 0 7/2 1/2 1 1/2 -1/2 2 4/7 2 x1 1 -5/2 1/2 0 -1/2 1/2 5 σj 0 7M/2+8 M/2-6 M/2+1 0 -3M/2-1 10-2M 3 x2 0 1 1/7 1/7 2/7 -1/7 4/7 2 x1 1 0 6/7 -1/7 5/7 1/7 45/7 σj 0 0 -50/7 -1/7 -M-16/7 -M+1/7 102/7 * * (P) * * * * 单位产品消耗的资源(吨/件)) 4.4 影子价格 (1) 原始问题是利润最大化的生产计划问题 总利润(元) 产品产量(件) 单位产品的利润(元/件) 消耗的资源(吨) 剩余的资源(吨) 资源限量(吨) * * (2) 对偶问题 对偶问题是资源定价问题，对偶问题的最优解y1、y2、...、ym称为m种资源的影子价格（Shadow Price） 原始和对偶问题都取得最优解时，最大利润 Max z=Min w 总利润(元) 资源限量(吨) 资源价格(元/吨) * * (3) 资源影子价格的性质 影子价格越大，说明这种资源越是相对紧缺 影子价格越小，说明这种资源相对不紧缺 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0 * * 0 X2 X1 X= (15,7.5) Z=975 X= (15.5,7.25) Z=982.5 X= (14.5,8.25) Z=992.5 * * y1 y2 ym (4) 产品的机会成本 机会成本 表示减少一件产品所节省的资源可以增加的利润 增加单位资源可以增加的利润 减少一件产品可以节省的资源 * * 机会成本 利润 差额成本 (5) 产品的差额成本（Reduced Cost） 差额成本=机会成本 - 利润 * * (6) 互补松弛关系的经济解释 在利润最大化的生产计划中 （1）边际利润大于0的资源没有剩余 （2）有剩余的资源边际利润等于0 （3）安排生产的产品机会成本等于利润 （4）机会成本大于利润的产品不安排生产 * * 4.5 对偶单纯形法 定义：设A=(B N)，其中B是一个非奇异的m× m阶方阵，对应地C=(CB CN)，则YB=CB的解Y*=CBB-1称为对偶问题(D)的一个基本解；若Y*还满足Y*N≧CN，则称Y*为(D)的一个基可行解；若有Y*NCN，则称Y*为非退化的基可行解，否则称为退化的基可行解。 (1) 对偶单纯形法的基本原理 定义：如果原问题(P)的一个基本解X与对偶问题(D)的基可行解Y对应的检验数向量满足条件 则称X为原问题(P)的一个正则解。 原问题(P)的正则解X与对偶问题(D)的基可行解Y一一对应 原问题(P)的基本解X与对偶问题(D)的 基 本 解Y一一对应 原问题(P)的最优解X*与对偶问题(D)的最优解Y*一一对应 * * 原问题解空间 对偶问题解空间 可行解 可行解 基本解 基本解 正则解 正则解 基可行解 基可行解 最优解 * * 对偶单纯形法的基本思想 从原规划的一个基本解出发，此基本解不一定可行(正则解)，但它对应着一个对偶基可行解（检验数非正），所以也可以说是从一个对偶基可行解出发；然后检验原规划的正则解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个正则解，此正则解对应着另一个对偶基可行解（检验数非正）。 如果得到的正则解的分量皆非负则该正则解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的正则解由不可行逐步变为可行，当同时得到对偶规划与原规划