[工学]运筹学04-对偶问题.pptVIP

y1 y2 ym (4) 产品的边际（机会）成本 机会成本 表示减少一件产品所节省的资源可以增加的利润 增加单位资源可以增加的利润 减少一件产品可以节省的资源 边际成本 利润 差额成本 (5) 产品的差额成本（Reduced Cost） 差额成本=边际成本 - 利润 (6) 互补松弛关系的经济解释 在利润最大化的生产计划中（完全信息市场假设下） （1）边际利润大于0的资源没有剩余 （2）有剩余的资源边际利润等于0 （3）安排生产的产品边际成本等于利润（差额成本=0） （4）边际成本大于利润的产品不安排生产（差额成本0） 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一一对应 对偶单纯形法的基本思想 从原规划的一个基本解出发，此基本解不一定可行(正则解)，但它对应着一个对偶基可行解（检验数非正），所以也可以说是从一个对偶基可行解出发；然后检验原规划的正则解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个正则解，此正则解对应着另一个对偶基可行解（检验数非正）。 如果得到的正则解的分量皆非负则该正则解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的正则解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。 (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 C 2 3 -5 -M 0 CB XB b X1 X2 X3 X4 X5 -M X4 7 1 1 1 1 0 0 X5 -10 -2 5 -1 0 1 -Z 7M 2+M 3+M -5+M 0 0 3 X2 7 1 1 1 1 0 0 X5 -45 -7 0 -6 -5 1 -Z -21 -1 0 -8 -M-3 0 3 X2 4/7 0 1 1/7 2/7 1/7 2 X1 45/7 1 0 6/7 5/7 -1/7 -Z -102/7 0 0 -50/7 -M-16/7 -1/7 是 是 是 是 否 否 否 否 所有 所有 得到 最优解 计算 计算 典式对应原规划的基本解是可行的 典式对应原规划的基本解的检验数小于0 所有 所有 计算 计算 以为中心元素进行迭代 以为中心元素进行迭代 停 没有最优解 没有最优解 单纯形法 对偶单纯形法 第四章作业 1（1，2）、2、6、9（1，2） 第四章 线性规划的对偶理论 4.1 对偶问题 4.2 对偶问题的基本性质 4.3 对偶问题的解 4.4 影子价格 4.5 对偶单纯形法 4.1 对偶问题 (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 目标函数 约束条件 如果因