运筹学教学教材第3章_对偶规划.ppt

管理运筹学课件 管理运筹学课件 第3章 对偶规划 辽宁工业大学 韩宇鑫 管理运筹学课件 * 教学目标与要求 【教学目标】 通过对本章的学习，理解对偶定义和性质及影子价格的含义；了解对偶单纯形法；会根据最终单纯形表对于资源项、目标系数变动进行敏感性分析。 【知识结构】 管理运筹学课件 * 本章主要内容 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 增加新的约束条件的分析 本章小结 管理运筹学课件 * 导入案例——出租还是自己组织生产？ 第2章导入案例中的数学模型 任何一个线性规划问题都存在一个伴生的线性规划问题，我们称之为“对偶”。本章将讨论对偶问题模型的建立、影子价格及敏感性分析。 现在换个角度讨论这个问题。 假若由于某种原因，该企业打算放弃生产产品的项目，而将所有设备出租，收取租金。那么，在考虑到设备出租市场竞争条件下，如何确定三种设备单位台时的租金，才能使企业不至于蚀本。 问题： 1. 如何建立该问题的数学模型？ 3. 用什么方法对该问题模型求解？ 管理运筹学课件 * 3.1.1 对偶问题 原始规划 设：两种设备单位台时租金分别为 y1,y2 由于承租方是理智的，会把租金压至最低。故出租方在满足上述二约束情况下，至少出租总收入（目标函数）为 约束一：生产甲产品的利润不大于放弃生产而出租的租金收入 约束二：生产乙产品的利润不大于放弃生产而出租的租金收入 对偶规划 称（2）为（1）的对偶，也称（1）为（2）的对偶。 管理运筹学课件 * 3.1.2 对偶问题的数学模型 （1）对称形式对偶问题 原问题 对偶问题 管理运筹学课件 * 3.1.2 对偶问题的数学模型 （2）非对称形式对偶问题 【例3.1】 写出下列线性规划的对偶规划。 对偶模型： 管理运筹学课件 * 3.1.3 对偶问题的基本性质 管理运筹学课件 * 3.2 对偶单纯形法简介 标准化 （若≥乘-1） 计算检验数 所有σ≤0? Yes 所有b≥0? 不符合对偶单纯形法条件，改用大M法 No 结束 Yes 找到最优解 No 找出最小bkxk为离去变量 所有akj≥0? θs=min{akj/σj|σj0}，xs入基，迭代得新单纯形表 No 无可行解 Yes 管理运筹学课件 * 3.2 对偶单纯形法简介 【例3.2】用对偶单纯形法解 解 标准化 初始单纯形表 第1次迭代 第2次迭代 最优解 最优值20 管理运筹学课件 * 3.2 对偶单纯形法简介 【例3.3】用对偶单纯形法解 B20 A2j≥0 无可行解 产品(公斤/件) 单位利润 资源 甲 乙 现有资源 3.3 影子价格 （甲资源） （乙资源） （利润） 则求原始规划的最优解就是求在有限资源的配置下的最佳效益； 设原始问题及其对偶问题分别为如下形式 　那么，此时相应的对偶规划的最优解，即变量y的取值对于原问题来说有何经济意义呢？ 设 是原问题的最优基， 和 分别为原问题和对偶问题的最优解， 和 分别是原问题和对偶问题的最优值，则有 其中， 是第i种资源的现有总量， 可以看成是每一个单位第i 种资源对经济效益所做的贡献； 或者说成是每一个单位第i 种资源在原生产安排的机会中所创造的价值； 称为第i种资源的影子价格. （1）影子价格不是资源的市场价格，而是对资源在生产中所做的贡献的估价. 由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。 这说明，在给定的条件下,每增加一个单位第i 种资源的用量,目标函数值(即总收益)的增量就等于影子价格． 例 某厂用甲、乙、丙三种原料生产Ａ、Ｂ两种产品，线性规划模型如下 例 某厂用甲、乙、丙三种原料生产Ａ、Ｂ两种产品，线性规划模型如下 甲的用量： 乙的用量： 丙的用量： 有剩余 用完 用完 在对偶问题的互补松弛性质中有 这表明生产过程中如果某种资源 未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。 (2)影子价格反映了供求关系和资源的稀缺性：影子价格为零，说明供大于求，影子价格越高则资源越稀缺． (3)影子价格告诉企业的经营管理者，增加哪 种资源对提高