运筹学04-对偶问题课件.ppt

第四章 线性规划的对偶理论 4.1 对偶问题 4.2 对偶问题的基本性质 4.3 对偶问题的解 4.4 影子价格 4.5 对偶单纯形法 4.1 对偶问题 4.2 对偶问题的基本性质 4.3 对偶问题的解 4.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（1，2）、2、6、8、9（1，2） y1 y2 ym (4) 产品的机会成本 机会成本 表示减少一件产品所节省的资源可以增加的利润 增加单位资源可以增加的利润 减少一件产品可以节省的资源 机会成本 利润 差额成本 (5) 产品的差额成本（Reduced Cost） 差额成本=机会成本 - 利润 (6) 互补松弛关系的经济解释 在利润最大化的生产计划中 （1）边际利润大于0的资源没有剩余 （2）有剩余的资源边际利润等于0 （3）安排生产的产品机会成本等于利润（差额成本=0） （4）机会成本大于利润的产品不安排生产（差额成本0） (1) 对偶单纯形法的基本原理 定义：如果原问题(P)的一个基本解X与对偶问题(D)的基可行解Y对应的检验数向量满足条件 则称X为原问题(P)的一个正则解。 原问题(P)的正则解X与对偶问题(D)的基可行解Y一一对应 对偶单纯形法的基本思想 从原规划的一个基本解出发，此基本解不一定可行(正则解)，但它对应着一个对偶基可行解（检验数非正），所以也可以说是从一个对偶基可行解出发；然后检验原规划的正则解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个正则解，此正则解对应着另一个对偶基可行解（检验数非正）。 如果得到的正则解的分量皆非负则该正则解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的正则解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。 (2) 对偶单纯形法的迭代步骤 建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2； 若b’≥0,则得到最优解,停止;否则,若有bk0则选较小的bk所在k行的基变量为出基变量,转3 若所有akj’≥0( j = 1,2,…,n )，则原问题无可行解,停止;否则,若有akj’0 则选 ?=min{?j’ / akj’┃akj’0}=?r’/akr’ 那么xr为进基变量,转4； 以akr’为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。 例 解：将上式标准化 C -2 -3 -4 0 0 CB XB b X1 X2 X3 X4 X5 0 X4 -3 -1 -2 -1 1 0 0 X5 -4 -2 1 -3 0 1 -f 0 -2 -3 -4 0 0 0 X4 -1 0 -5/2 1/2 1 -1/2 -2 X1 2 1 -1/2 3/2 0 -1/2 -f 4 0 -4 -1 0 -1 -3 X2 2/5 0 1 -1/5 -2/5 1/5 -2 X1 11/5 1 0 1/5 -1/5 -2/5 -f 28/5 0 0 -9/5 -8/5 -1/5 * * (1) 对偶问题的提出 例1、生产组织与计划问题 A, B各生产多少, 可获最大利润? 可用资源 煤 劳动力 仓库 A B 1 2 3 2 0 2 单位利润 40 50 30 60 24 Max Z= 40x1 +50x2 x1 + 2x2 ? 30 3x1 + 2x2 ? 60 2x2 ? 24 x1，x2 ? 0 s.t 目标函数 约束条件 如果因为某种原因，不愿意自己生产，而希望通过将现有资源承接对外加工（或出售）来获得收益，那么应如何确定各资源的使用价格？ Max Z= 40x1 +50x2 x1 + 2x2 ? 30 3x1 + 2x2 ? 60 2x2 ? 24 x1，x2 ? 0 s.t 目标函数 约束条件 两个原则 所得不得低于生产的获利 要使对方能够接受 设三种资源的使用单价分别为 y1 , y2 , y3 y1 y2 y3 生产单位产品A的资源消耗所得不少于单位产品A的获利 生产单位产品B的资源消耗所得不少于单位产品B的获利 y1 +3 y2 ? 40 2y1 + 2 y2 + 2y3 ? 50 通过使用所有资源对外加工所获得的收益 W = 30y1 + 60 y2 +