线性问题及图解法课件

《线性问题及图解法课件》由会员分享，可在线阅读，更多相关《线性问题及图解法课件（54页珍藏版）》请在金锄头文库上搜索。

1、,管理运筹学Operations Research,授课教师 余 勇 Telephone: 15390438438 E-mail: ,管理运筹学课程 教学大纲,课时安排：,绪论 历史，性质，应用,20世纪整个世界参与规模最大的事件是什么？ 第二次世界大战！ 整个世界的资源都投入到了第二次世界大战中。 如何才能更好地利用资源，分配有限的资源，这是一个值得研究的问题。 当时在英国军队中率先成立了研究小组运筹小组 来研究这些问题，这就是著名的OR小组.很快美军中 也相继成立了OR小组。 战争 运筹学诞生的温床。,绪论 历史，性质，应用,二战中成功的运筹学案例： 英国防空部门如何布置防空雷达，建立有效

2、的防空警报系统。 英，美空军如何提高对地面目标轰炸的效率。 如何安排反潜飞机的巡逻飞行线路。 深水炸弹的合理爆炸深度，摧毁德军潜艇数增加400%。 商船如何编队，遭潜艇攻击时如何减少损失。 使船只受敌机攻击时，中弹数由47%降到29%。 这些研究大大提高了盟军的作战能力，为反法西斯 战争的最后胜利作出了巨大的贡献！,绪论 历史，性质，应用,战争结束了！ 整个世界投入到了战后的重建国家的经济之中。 运筹学的方法相继在工业，农业，经济，社会问题等各个领域中展开了应用。与此同时，运筹数学有了飞快的发展，并形成了许多运筹学的分支。 线性规划，非线性规划，整数规划，目标规划，动态规划，图与网络分析，统筹

3、方法，排队论，存储论，对策论，决策论，多目标决策。,绪论 历史，性质，应用,运筹学的性质和特点 一种哲学方法论; 研究“事”而非“物”; 科学性，实践性，系统性，综合性; 模型的特点系统优化模型。 运筹学 为决策机构在对其控制下业务活动进行决策时，提供以数量化为基础的科学方法。 运筹学 一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题。 运筹学 是一种给出问题坏的答案的艺术，否则问题的结果会更坏。,绪论 历史，性质，应用,运筹学的工作步骤 运筹学在解决大量实际问题的过程中形成了自己的工作步骤： 提出和形成问题。 即弄清问题的目标，可能的约束，问题的可控变量以及有关

4、参数，搜集有关资料; 建立模型。 即把问题中可控变量，参数和目标与约束之间的关系用一定的模型表示出来; 求解。用各种手段（主要是数学方法，也可用其他方法）将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要可由求决策者提出。,绪论 历史，性质，应用,运筹学的工作步骤 解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题； 解的控制。通过控制解的变化过程决定是否要作一定的改变； 解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改。,绪论 历史，性质，应用,运筹学的模型 运筹学在解决问题时，按研究对象

5、不同可构造各种不同的模型。模型是研究者对客观现实经过思维抽象后用文字、图表、符号、关系以及实体模样描述所认识到的客观对象。模型的有关参数和关系式是较容易改变的，这样是有助于问题的分析和研究。利用模型可以进行一定预测、灵敏度分析等。 模型的三种基本形式： （1）形象模型，（2）模拟模型，（3）符号或数学模型。 构造模型是一种创造性劳动，成功的模型往往是科学和艺术的结晶，构造模型的方法和思路通常有以下几种：,绪论 历史，性质，应用,直接分析法 按研究者对问题内在机理的认识直接构造出模型。运筹学中已有不少现存的模型，如线性规划模型、投入产出模型、排队模型、存储模型、决策和对策模型等等。这些模型都有很

6、好的求解方法及求解软件，但用这些现成的模型研究问题时，应注意不能生搬硬套。 类比法 有些问题可以用不同方法构造出模型；而这些模型的结构性质是类同的，这就可以互相类比。如物理学中的机械系统、气体动力学系统、水力学系统、热力学系统及电路系统之间就有不少彼此类同的现象。甚至有些经济、社会系统也可以用物理系统来类比。在分析有些经济、社会问题时，不同国家之间也可以找出某些类比的现象。,绪论 历史，性质，应用,数据分析法 对有些问题的机理尚未了解清楚，若能搜集到与此问题密切有关的大量数据，或通过某些试验获得大量数据，这就可以用统计分析法建摸。 试验分析法 有些问题的机理不清，又不能作大量试验来获得数据，这

7、时只能通过做局部试验的数据加上分析来构造模型。 想定（构想）法 当有些问题的机理不清，又缺少数据，又不能作试验来获得数据时，例如有些社会、经济、军事问题，人们只能在已有的知识、经验和某些研究的基础上，对于将来可能发生的情况给出逻辑上合理的设想和描述。然后用已有的方法构造模型，并不断修正完善，直至比较满意为止。,绪论 历史，性质，应用,运筹学的主要应用 二次大战后运筹学的应用迅速转向了民用，下面对某些重要领域给于简述。 市场销售-广告预算和媒介选择、竞争性定价、新品开发、销售计划的制订。（美）杜邦公司在五十年代起就非常重视将运筹学用于如何做好广告工作、产品定价、新品引入。 生产计划-从总体确定生

8、产、存储和劳动力的配合等计划适应波动的需求计划。巴基斯坦一重型制造厂用线性规划安排生产计划，节省10%的生产费用。 运输问题-涉及空运、水运、公路、铁路运输、管道运输等。公路网的设计和分析，市内公共汽车路线的选择和行车时刻表的安排，出租车的调度等。,绪论 历史，性质，应用,人事管理-需求估计，教育和培训，人员分配（各种指派问题），合理利用，人才评价等。 设备维修，更新和可靠性等。 计算机和信息系统-内存分配研究，网络设计分析等。 城市管理-紧急服务系统的设计和运用，区域布局规划，管道网络设计等。（美）曾用排队论确定纽约市紧急电话站的值班人数，（加）设计城市警车配置和负责范围、指挥接警后的行走路

9、线等。 对策研究-价格竞争，中央与地方政府投资分配博弈，工会与雇主间的博弈。,绪论 历史，性质，应用,国际运筹与管理科学协会（INFORMS）及其下属的管理科学实践学会每年主持评定弗兰茨厄德曼奖（Franz Edelman）以奖励为运筹学在管理中的应用的卓越成就者，一般会授予六位优胜者，其获奖项目的文章都在第二年发表在著名刊物Interface的新年第一期上。 下表列写出了部分发表在该期刊上的获奖项目：,绪论 历史，性质，应用,第二章,线性规划及图解法,问题的提出 解决有限资源在有竞争的使用方向中如何进行最佳分配。 线性规划是运筹学的一个重要分支，也是运筹学中应用最广泛的方法之一。自1947年

10、旦茨基（G. B. Dantzig）提出了一般线性规划问题求解的方法单纯形法（simplex method）之后，线性规划已被广泛应用于解决经济管理和工业生产中遇到的实际问题。调查表明，在全球500家最大的企业中，有85%的企业都曾使用线性规划解决经营管理中遇到的复杂问题。线性规划的使用为应用者节约了数以亿万计的资金。,线性规划 Linear Programming（LP）,本讲中我们将讨论什么是线性规划问题，线性规划问题的数学表示，基本概念和图解方法。 线性规划问题是什么样的一类问题呢？ 请看案例-,线性规划 Linear Programming（LP）,线性规划 Linear Progra

11、mming（LP）,曾几何时长江水， 哺育华夏代代人; 谁知后代疏珍惜， 清清江水黑如泥。,案 例 河流污染治理规划问题,线性规划 Linear Programming（LP）,曾几何时长江水， 哺育华夏代代人; 谁知后代疏珍惜， 清清江水黑如泥。,工厂2,工厂3,工厂1,工厂4,工厂5,工厂6,工厂9,工厂8,工厂7,案 例 河流污染治理规划问题,线性规划 Linear Programming（LP）,曾几何时长江水， 哺育华夏代代人; 谁知后代疏珍惜， 清清江水黑如泥。,今日认识未为晚， 吾辈齐心治环境; 线性规划大有用， 定让江水绿如蓝。,工厂2,工厂3,工厂1,工厂4,工厂5,工厂6,

12、工厂9,工厂8,工厂7,案 例 河流污染治理规划问题,线性规划 Linear Programming（LP）,今日认识未为晚， 吾辈齐心治环境; 线性规划大有用， 定让江水绿如蓝。,曾几何时长江水， 哺育华夏代代人; 谁知后代疏珍惜， 清清江水黑如泥。,工厂2,工厂3,工厂1,工厂4,工厂5,工厂6,工厂9,工厂8,工厂7,案 例 河流污染治理规划问题,线性规划 Linear Programming（LP）,案 例 河流污染治理规划问题 背景资料: 长江流域某区域内有9化工厂，各厂每月产生的工业污水量如表-1，流经各化工厂的河流流量如表-2，各化工厂治理工业污水的成本如表-3。上游厂排放的污水

13、流到相邻下游厂以前，有20%可自然净化。 根据环保标准河流中此种工业污水的含量不应超过0.2%。从该区域整体考虑，各化工厂应该分别处理多少工业污水才能既满足环保要求，又使9化工厂治理工业污水的总费用最少。,背景资料:,线性规划 Linear Programming（LP）,表-1 污水产生量 单位：万m3,表-2 流经各化工厂的河流流量 单位：万m3,表-3 治理工业污水的成本 单位：百万元/万m3,线性规划 Linear Programming（LP）,1,9,4,5,8,2,6,3,7,问题分析： 区域污染治理的决策各个化工厂应处理的工业污水量（或应排放的工业污水量）。 区域污染治理的约束

14、即满足环保要求排放工业污水（区域内河流中任何点检测都应符合环保标准）。 区域污染治理的目标总治理成本最少。,线性规划 Linear Programming（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%,线性规划 Linear Programming（LP）,1,9,4,5,8,2,6,3,7,

15、对化工厂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应满足上述所有不等式方程。我们将这些不等式方程构成的方程组称为污水治理的约束条件。,线性规划 Linear Programming（LP）,1,9,4,5,8,2,6,3,7,3、决策目标（确定）分析： 另一方面污水治理的总成本可表示为Z（单位：百万元） Z = 3X1+ 5X2+ 2X3+ 4X4+ 5X5+ 6X6+ 1X7+ 2X8+ 3X9 而决策者的目标是确定满足约束条件的Xi使得Z取得最小值。 因此决策目标可表示为： Min Z = 3X1+ 5X2+ 2X3+ 4X4+ 5X5+ 6X6+ 1X7+ 2X8+ 3X9 将上述分析归纳后即可得如下数学符合模型：,线性规划 Linear Programming（LP）,河流污染治理规划问题 数学模型（整理之后）,线性规划 Linear Programming（LP）,线性规划模型 Linear Programming Mo