线性规划01-线性问题及图解法.ppt

管理运筹学OperationsResearch 授课教师余勇Telephone 88061330E mail yuy 管理运筹学 课程教学大纲 课时安排 绪论历史 性质 应用 20世纪整个世界参与规模最大的事件是什么 第二次世界大战 整个世界的资源都投入到了第二次世界大战中 如何才能更好地利用资源 分配有限的资源 这是一个值得研究的问题 当时在英国军队中率先成立了研究小组 运筹小组来研究这些问题 这就是著名的OR小组 很快美军中也相继成立了OR小组 战争 运筹学诞生的温床 绪论历史 性质 应用 二战中成功的运筹学案例 英国防空部门如何布置防空雷达 建立最有效的防空警报系统 英 美空军如何提高对地面目标轰炸的命中率 如何安排反潜飞机的巡逻飞行线路 深水炸弹的合理爆炸深度 摧毁德军潜艇数增加400 商船如何编队 遭潜艇攻击时如何减少损失 使船只受敌机攻击时 中弹数由47 降到29 这些研究大大提高了盟军的作战能力 为反法西斯战争的最后胜利作出了巨大的贡献 绪论历史 性质 应用 战争结束了 整个世界投入到了战后的重建国家的经济之中 运筹学的方法相继在工业 农业 经济 社会问题等各个领域中展开了应用 与此同时 运筹数学有了飞快的发展 并形成了许多运筹学的分支 线性规划 非线性规划 整数规划 目标规划 动态规划 图与网络分析 统筹方法 排队论 存储论 对策论 决策论 多目标决策 绪论历史 性质 应用 运筹学的性质和特点一种哲学方法论 研究 事 而非 物 科学性 实践性 系统性 综合性 模型的特点 系统优化模型 运筹学 为决策机构在对其控制下业务活动进行决策时 提供以数量化为基础的科学方法 运筹学 一门应用科学 它广泛应用现有的科学技术知识和数学方法 解决实际中提出的专门问题 运筹学 是一种给出问题坏的答案的艺术 否则问题的结果会更坏 绪论历史 性质 应用 运筹学的工作步骤运筹学在解决大量实际问题的过程中形成了自己的工作步骤 提出和形成问题 即弄清问题的目标 可能的约束 问题的可控变量以及有关参数 搜集有关资料 建立模型 即把问题中可控变量 参数和目标与约束之间的关系用一定的模型表示出来 求解 用各种手段 主要是数学方法 也可用其他方法 将模型求解 解可以是最优解 次优解 满意解 复杂模型的求解需用计算机 解的精度要可由求决策者提出 绪论历史 性质 应用 运筹学的工作步骤解的检验 首先检查求解步骤和程序有无错误 然后检查解是否反映现实问题 解的控制 通过控制解的变化过程决定是否要作一定的改变 解的实施 是指将解用到实际中必须考虑到实施的问题 如向实际部门讲清解的用法 在实施中可能产生的问题和修改 绪论历史 性质 应用 运筹学的模型运筹学在解决问题时 按研究对象不同可构造各种不同的模型 模型是研究者对客观现实经过思维抽象后用文字 图表 符号 关系以及实体模样描述所认识到的客观对象 模型的有关参数和关系式是较容易改变的 这样是有助于问题的分析和研究 利用模型可以进行一定预测 灵敏度分析等 模型的三种基本形式 1 形象模型 2 模拟模型 3 符号或数学模型 构造模型是一种创造性劳动 成功的模型往往是科学和艺术的结晶 构造模型的方法和思路通常有以下几种 绪论历史 性质 应用 直接分析法按研究者对问题内在机理的认识直接构造出模型 运筹学中已有不少现存的模型 如线性规划模型 投入产出模型 排队模型 存储模型 决策和对策模型等等 这些模型都有很好的求解方法及求解软件 但用这些现成的模型研究问题时 应注意不能生搬硬套 类比法有些问题可以用不同方法构造出模型 而这些模型的结构性质是类同的 这就可以互相类比 如物理学中的机械系统 气体动力学系统 水力学系统 热力学系统及电路系统之间就有不少彼此类同的现象 甚至有些经济 社会系统也可以用物理系统来类比 在分析有些经济 社会问题时 不同国家之间也可以找出某些类比的现象 绪论历史 性质 应用 数据分析法对有些问题的机理尚未了解清楚 若能搜集到与此问题密切有关的大量数据 或通过某些试验获得大量数据 这就可以用统计分析法建摸 试验分析法有些问题的机理不清 又不能作大量试验来获得数据 这时只能通过做局部试验的数据加上分析来构造模型 想定 构想 法当有些问题的机理不清 又缺少数据 又不能作试验来获得数据时 例如有些社会 经济 军事问题 人们只能在已有的知识 经验和某些研究的基础上 对于将来可能发生的情况给出逻辑上合理的设想和描述 然后用已有的方法构造模型 并不断修正完善 直至比较满意为止 绪论历史 性质 应用 运筹学的主要应用二次大战后运筹学的应用迅速转向了民用 下面对某些重要领域给于简述 市场销售 广告预算和媒介选择 竞争性定价 新品开发 销售计划的制订 美 杜邦公司在五十年代起就非常重视将运筹学用于如何做好广告工作 产品定价 新品引入 生产计划 从总体确定生产 存储和劳动力的配合等计划适应波动的需求计划 巴基斯坦一重型制造厂用线性规划安排生产计划 节省10 的生产费用 运输问题 涉及空运 水运 公路 铁路运输 管道运输等 公路网的设计和分析 市内公共汽车路线的选择和行车时刻表的安排 出租车的调度等 绪论历史 性质 应用 人事管理 需求估计 教育和培训 人员分配 各种指派问题 合理利用 人才评价等 设备维修 更新和可靠性等 计算机和信息系统 内存分配研究 网络设计分析等 城市管理 紧急服务系统的设计和运用 区域布局规划 管道网络设计等 美 曾用排队论确定纽约市紧急电话站的值班人数 加 设计城市警车配置和负责范围 指挥接警后的行走路线等 对策研究 价格竞争 中央与地方政府投资分配博弈 工会与雇主间的博弈 绪论历史 性质 应用 国际运筹与管理科学协会 INFORMS 及其下属的管理科学实践学会每年主持评定弗兰茨 厄德曼奖 FranzEdelman 以奖励为运筹学在管理中的应用的卓越成就者 一般会授予六位优胜者 其获奖项目的文章都在第二年发表在著名刊物Interface的新年第一期上 下表列写出了部分发表在该期刊上的获奖项目 绪论历史 性质 应用 第二章 线性规划及图解法 问题的提出解决有限资源在有竞争的使用方向中如何进行最佳分配 线性规划是运筹学的一个重要分支 也是运筹学中应用最广泛的方法之一 自1947年旦茨基 G B Dantzig 提出了一般线性规划问题求解的方法 单纯形法 simplexmethod 之后 线性规划已被广泛应用于解决经济管理和工业生产中遇到的实际问题 调查表明 在全球500家最大的企业中 有85 的企业都曾使用线性规划解决经营管理中遇到的复杂问题 线性规划的使用为应用者节约了数以亿万计的资金 线性规划LinearProgramming LP 本讲中我们将讨论什么是线性规划问题 线性规划问题的数学表示 基本概念和图解方法 线性规划问题是什么样的一类问题呢 请看案例 线性规划LinearProgramming LP 线性规划LinearProgramming LP 曾几何时长江水 哺育华夏代代人 谁知后代疏珍惜 清清江水黑如泥 案例河流污染治理规划问题 线性规划LinearProgramming LP 曾几何时长江水 哺育华夏代代人 谁知后代疏珍惜 清清江水黑如泥 工厂2 工厂3 工厂1 工厂4 工厂5 工厂6 工厂9 工厂8 工厂7 案例河流污染治理规划问题 线性规划LinearProgramming LP 曾几何时长江水 哺育华夏代代人 谁知后代疏珍惜 清清江水黑如泥 今日认识未为晚 吾辈齐心治环境 线性规划大有用 定让江水绿如蓝 工厂2 工厂3 工厂1 工厂4 工厂5 工厂6 工厂9 工厂8 工厂7 案例河流污染治理规划问题 线性规划LinearProgramming LP 今日认识未为晚 吾辈齐心治环境 线性规划大有用 定让江水绿如蓝 曾几何时长江水 哺育华夏代代人 谁知后代疏珍惜 清清江水黑如泥 工厂2 工厂3 工厂1 工厂4 工厂5 工厂6 工厂9 工厂8 工厂7 案例河流污染治理规划问题 线性规划LinearProgramming LP 案例河流污染治理规划问题背景资料 长江流域某区域内有9化工厂 各厂每月产生的工业污水量如表 1 流经各化工厂的河流流量如表 2 各化工厂治理工业污水的成本如表 3 上游厂排放的污水流到相邻下游厂以前 有20 可自然净化 根据环保标准河流中此种工业污水的含量不应超过0 2 从该区域整体考虑 各化工厂应该分别处理多少工业污水才能既满足环保要求 又使9化工厂治理工业污水的总费用最少 背景资料 线性规划LinearProgramming LP 表 1污水产生量单位 万m3 表 2流经各化工厂的河流流量单位 万m3 表 3治理工业污水的成本单位 百万元 万m3 线性规划LinearProgramming LP 1 9 4 5 8 2 6 3 7 问题分析 区域污染治理的决策 各个化工厂应处理的工业污水量 或应排放的工业污水量 区域污染治理的约束 即满足环保要求排放工业污水 区域内河流中任何点检测都应符合环保标准 区域污染治理的目标 总治理成本最少 线性规划LinearProgramming LP 1 9 4 5 8 2 6 3 7 建立模型 建模三步曲 1 决策变量 设定 分析 设第i个化工厂应处理的工业污水量为Xi万m3 则根据问题描述的情况以化工厂1 2 9加以分析则可得如下近似关系式2 环境约束 限制 分析 对化工厂2应有 1 X2 300 0 2 对化工厂8应有 0 8 X8 200 0 2 线性规划LinearProgramming LP 1 9 4 5 8 2 6 3 7 对化工厂1应有 1 2 X1 0 8 1 X2 0 8 X8 500 0 2 对化工厂9应有 1 5 X9 700 0 2 对化工厂7应有 2 X7 0 8 1 5 X9 1200 0 2 此外显然还应有Xi 0 i 1 2 3 8 9 综上所述决策者所需考虑的区域内各个化工厂应处理的工业污水量Xi应满足上述所有不等式方程 我们将这些不等式方程构成的方程组称为污水治理的约束条件 线性规划LinearProgramming LP 1 9 4 5 8 2 6 3 7 3 决策目标 确定 分析 另一方面污水治理的总成本可表示为Z 单位 百万元 Z 3X1 5X2 2X3 4X4 5X5 6X6 1X7 2X8 3X9而决策者的目标是确定满足约束条件的Xi使得Z取得最小值 因此决策目标可表示为 MinZ 3X1 5X2 2X3 4X4 5X5 6X6 1X7 2X8 3X9将上述分析归纳后即可得如下数学符合模型 线性规划LinearProgramming LP 河流污染治理规划问题数学模型 整理之后 线性规划LinearProgramming LP 线性规划模型 LinearProgrammingModel或LinearOptimizationModel用线性规划方法解决实际经济与管理问题的第一步是分析建立能够完整描述和反映实际问题的线性规划模型 线性规划LinearProgramming LP 通常建立LP模型有以下几个基本步骤 确定决策变量 决策变量是模型要确定的未知变量 也是模型最重要的参数 是决策者解决实际问题的控制变量 确定目标函数 目标函数决定线性规划问题的优化方向 是模型的重要组成部分 实际问题的目标可表示为决策变量的一个线性函数 并根据目标函数的实质确定优化方向 一般可为最大化 max 或最小化 min 线性规划LinearProgramming LP 通常建立LP模型有以下几个步骤 确定约束方程 一个正确的线性规划模型应能通过约束方程来描述和反映一系列客观条件或环境的限制 这些限制通过一系列线性等式或不等式方程组来描述 变量取值限制 一般情况下 决策变量取正值 非负值 因此 模型中应有变量的非负约束即Xj 0 但要注意也存在例外的情形 线性规划LinearProgramming LP 线性规划的一般形式 此模型的两大基本特征 1 目标函数为决策变量的线性函数 2 约束方程为决策变量的线性不等式或等式方程 线性规划LinearProgramming LP 线性规划问题的标准形式1 目标函数极大化 max 2 等式约束条件 且右端常数bi非负3 变量非负 xj 0 线性规划LinearProgramming LP 化标准形式的一般步骤目标函数极小化 极大化 约束条件的右端项bi 0 bi 0 约束条件为不等式 或 取值无约束 自由 变量 非负变量 取值非正变量 非负变量 线性规划问题的标准形式的作用 为单纯形法求解作准备 线性规划LinearProgramming LP 线性规划问题的求解 图解 如何求解一般的线性规划呢 下面我们分析一下简单的情况 只有两个决策变量的线性规划问题 这时可以通过图解的方法来求解 图解法具有简单 直观 便于初学者窥探线性规划基本原理和几何意义等优点 线性规划LinearProgramming LP 图解法例1 maxz 2x1 x25x2 15s t 6x1 2x2 24x1 x2 5x1 x2 0 线性规划LinearProgramming LP 图解法 唯一最优解X 9 2 3 2 D 可行域 目标函数等值线 z 0 2x1 x2 x1 x2 线性规划LinearProgramming LP 图解法例maxZ 2X1 X2X1 1 9X2 3 8X1 1 9X2 3 8s t X1 1 9X2 10 2X1 1 9X2 3 8X1 X2 0 线性规划LinearProgramming LP 图解法maxZ 2X1 X2 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 4 2X1 X2 20 2X1 X2 17 2 2X1 X2 11 2X1 X2 Lo 0 2X1 X2 7 6 2 D maxZ minZ 此点是唯一最优解 且最优目标函数值maxZ 17 2 可行域 线性规划LinearProgramming LP 图解法maxZ 3X1 5 7X2 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 7 6 2 D L0 0 3X1 5 7X2 maxZ minZ 3 8 4 34 2 3X1 5 7X2 红色线段上的所有点都是最优解这种情形为有无穷多最优解 但是最优目标函数值maxZ 34 2是唯一的 可行域 线性规划LinearProgramming LP 图解法minZ 5X1 4X2 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 D L0 0 5X1 4X2 maxZ minZ 8 5X1 4X2 43 5X1 4X2 0 2 可行域 此点是唯一最优解 线性规划LinearProgramming LP 图解法maxZ 5X1 4X2 x1 x2 o D 可行域 maxZ minZ 最优解目标值Z趋于无穷 线性规划LinearProgramming LP 图解法maxZ 5X1 4X2 x1 x2 o 线性规划LinearProgramming LP 图解法图解法的启示线性规划问题解的可能情况a 唯一最优解b 无穷多最优解c 无解 没有有界最优解 无可行解 若线性规划问题的可行域非空