管理运筹学第3章 对偶规划.ppt

第3章对偶规划 管理运筹学课件 2 27 03 2020 教学目标与要求 教学目标 通过对本章的学习 理解对偶定义和性质及影子价格的含义 了解对偶单纯形法 会根据最终单纯形表对于资源项 目标系数变动进行敏感性分析 知识结构 管理运筹学课件 3 27 03 2020 本章主要内容 3 1线性规划的对偶模型3 1 1对偶问题3 1 2线性规划对偶模型3 1 3对偶问题的基本性质3 2对偶单纯形法简介3 3影子价格3 4灵敏度分析3 4 1价值系数的变化分析3 4 2右端常数的变化分析3 4 3增加一个新变量的分析3 4 4增加新的约束条件的分析3 5如何看计算机求解报告本章小结 管理运筹学课件 4 27 03 2020 导入案例 出租还是自己组织生产 第2章导入案例中的数学模型 任何一个线性规划问题都存在一个伴生的线性规划问题 我们称之为 对偶 本章将讨论对偶问题模型的建立 影子价格及敏感性分析 现在换个角度讨论这个问题 假若由于某种原因 该企业打算放弃生产产品的项目 而将所有设备出租 收取租金 那么 在考虑到设备出租市场竞争条件下 如何确定三种设备单位台时的租金 才能使企业不至于蚀本 问题 1 如何建立该问题的数学模型 3 用什么方法对该问题模型求解 管理运筹学课件 5 27 03 2020 3 1 1对偶问题 原始规划 设 两种设备单位台时租金分别为y1 y2 由于承租方是理智的 会把租金压至最低 故出租方在满足上述二约束情况下 至少出租总收入 目标函数 为 约束一 生产甲产品的利润不大于放弃生产而出租的租金收入 约束二 生产乙产品的利润不大于放弃生产而出租的租金收入 对偶规划 称 2 为 1 的对偶 也称 1 为 2 的对偶 管理运筹学课件 6 27 03 2020 3 1 2对偶问题的数学模型 1 对称形式对偶问题原问题对偶问题 管理运筹学课件 7 27 03 2020 3 1 2对偶问题的数学模型 2 非对称形式对偶问题 例3 1 写出下列线性规划的对偶规划 对偶模型 管理运筹学课件 8 27 03 2020 3 1 3对偶问题的基本性质 管理运筹学课件 9 27 03 2020 3 2对偶单纯形法简介 管理运筹学课件 10 27 03 2020 3 2对偶单纯形法简介 标准化 若 乘 1 管理运筹学课件 11 27 03 2020 3 2对偶单纯形法简介 例3 2 用对偶单纯形法解 解标准化 初始单纯形表 第1次迭代 第2次迭代 最优值20 管理运筹学课件 12 27 03 2020 3 2对偶单纯形法简介 例3 3 用对偶单纯形法解 无可行解 管理运筹学课件 13 27 03 2020 3 3影子价格 导入案例原问题的解如图 对偶问题的解 管理运筹学课件 14 27 03 2020 3 3影子价格 原问题 bi代表第i种资源拥有量yi代表第i种资源的估价 该估价并非市价格 而是在生产中的单位贡献所做的估价 称为影子价格 其含义 1 资源的市场价格由供求关系决定 而它的影子价格则有赖于资源的利用情况 2 影子价格是一种边际价格 3 资源的影子价格实际上又是一种机会成本 4 当影子价格为0时 表明该种资源未得到充分利用 当影子价格不为0时 表明该种资源已耗费完毕 5 在一个大公司内部 可借助资源的影子价格确定一些内部结算价格 以便控制有限资源的使用和考核下属企业经营的好坏 对偶问题 管理运筹学课件 15 27 03 2020 3 4灵敏度分析 线性规划的各个参数A C b往往是根据统计数据测算的 不可能完全准确 而且随着实际情况变化 灵敏度分析是指各参数变化对最优解的影响 管理运筹学课件 16 27 03 2020 3 4 1价值系数cj的变化分析 由式3 7可知 cj变化仅影响检验数 敏感性分析是求检验数符号不变 最优基不变 时cj的允许变化范围 例3 4 由下述模型的最终单纯形表求最优基不变的c2允许变化范围 令c2 4 c 有 若保持检验数非正 要求 即c2的允许变化范围 2 5 5 管理运筹学课件 17 27 03 2020 3 4 2右端项bi的变化分析 设由式3 8 若则最优基保持不变 例3 5 由 例3 4 最终单纯形表求最优基不变的b3允许变化范围 即b3的允许变化范围 40 50 管理运筹学课件 18 27 03 2020 3 4 3增加一个新变量的分析 管理运筹学课件 19 27 03 2020 3 4 3增加一个新变量的分析 在操作上 由若大于0应安排生产 例3 6 在例3 4中增加一个新产品是否可行 其消耗系数列向量p6 3 2 1 1 2 及价值系数c6 3 管理运筹学课件 20 27 03 2020 3 4 4增加一个新的约束分析 增加一个新的约束后 线性规划的可行域只会变小 不会变大 最优值只能变差 不会变的更好 因此如果原最优解X 满足新的约束条件 则X 仍然是最优解 否则继续进行迭代 例3 7 在例3 4中增加一个新的约束引入松弛变量添加到最终单纯形表中 将基向量变成单位向量 管理运筹学课件 21 27 03 2020 3 5如何看计算机求解报告 例3 8 Globaloptimalsolutionfound Objectivevalue 35 00000Totalsolveriterations 2VariableValueReducedCostX 1 5 0000000 000000X 2 0 0000002 000000X 3 5 0000000 000000RowSlackorSurplusDualPrice135 000001 00000020 0000000 200000030 0000000 6000000Rangesinwhichthebasisisunchanged ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX 1 3 0000001 8000000 6000000X 2 1 0000002 000000INFINITYX 3 4 0000001 0000001 500000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecrease255 0000025 0000015 00000340 0000015 0000012 50000 最优值 迭代次数 松弛或剩余变量 SlackorSurplus 反映了资源的利用情况 若松弛变量为0 表示该资源已耗费完毕 若大于0 表示尚有剩余 本例2个约束的松弛变量 第2 3行 均为0 表示两种资源均已耗费完毕 而第1行是生产一个单位产品所消耗的各项资源的影子价格的总和 称为产品的隐含成本 影子价格 DualPrice 的含义见节3 3 当松弛变量为0时 影子价格大于0 目标系数当前值 保持最优基不变时允许增量 保持最优基不变时允许减量 管理运筹学课件 22 27 03 2020 本章小结 本章主要内容包括线性规划对偶问题 线性规划原模型与对偶模型之间的结构关系 基于线性规划对偶问题的资源影子价格的含义 各参数变化的敏感性分析 对偶单纯形法 原始规划的解与对偶规划的解之间有一些重要的关系 这些基本性质统称为对偶定理 包括对称性定理 弱对偶定理 最优性准则定理 主对偶定理 对偶变量表示一个单位第i种资源的估价 这种估价不是资源的市场价格 而是根据资源在生产中作出的贡献而作的估价 为区别起见 称为影子价格 Shadowprice 线性规划的灵敏度分析就是研究参数变化时对最优解的影响 具体来