运筹学01-绪论-11

1、运筹学运筹学 华东理工大学商学院 管理科学与工程系 夏海洋 第第1讲讲 绪论绪论 1.1 运筹学的定义 1.2 运筹学研究的系统过程 1.3 运筹学的产生与发展 1.4 运筹学的主要分支 1.1 1.1 运筹学的定义运筹学的定义 o 运筹学一词的由来 nOperations Research (美) nOperational Research (英国) n作业研究(台湾)，运用学运筹学(1957年) n作战研究：operation(军事行动，作战), research(研究) n二战期间，英美等国为了解决作战中遇到的错综复杂的 战略、战术问题而成立了由科学家、工程师等组成的关 于作战的科学研究

2、小组。1938年，波德塞科学小组的负 责人A.P. Rowe把他们从事的工作称为“operational research”(作战研究)，他被认为这一词汇的创始人。 School of Business ECUST o 运筹学的定义 n运筹学研究的两位先驱莫斯(P. M. Morse)和金博尔(G.E. Kimball)的定义是：“运筹学是在实行管理的领域，运用运筹学是在实行管理的领域，运用 数学方法，对需要进行管理的问题统筹规划，作出决策数学方法，对需要进行管理的问题统筹规划，作出决策 的一门应用科学。的一门应用科学。” n辞海中对运筹学作的解释是：20世纪世纪40年代开始形年代开始形 成的

3、一门学科，主要研究经济活动和军事活动中能用数成的一门学科，主要研究经济活动和军事活动中能用数 量来表达的有关运用、筹划与管理方面的问题。它根据量来表达的有关运用、筹划与管理方面的问题。它根据 问题的要求，通过数学分析的运算，作出综合性的合理问题的要求，通过数学分析的运算，作出综合性的合理 安排，以达到较经济、较有效地使用人力、物力。安排，以达到较经济、较有效地使用人力、物力。 n另一较有代表性的定义是，运筹学是一门应用科学，它运筹学是一门应用科学，它 广泛应用现有的科学技术知识和数学方法，解决实际提广泛应用现有的科学技术知识和数学方法，解决实际提 出的专门问题，为决策者选择最优决策提供定量依据

4、。出的专门问题，为决策者选择最优决策提供定量依据。 o 关于运筹学定义的总结：关于运筹学定义的总结： n运筹学是一门应用科学，它是面向实践的，它的研究对运筹学是一门应用科学，它是面向实践的，它的研究对 象是实践中的决策问题，并且要将研究结果应用于实象是实践中的决策问题，并且要将研究结果应用于实 践；践；(运筹学的实践性运筹学的实践性) n运筹学研究是基于数量化的方法和技术，同时对这些数运筹学研究是基于数量化的方法和技术，同时对这些数 量化方法和技术的研究也构成了运筹学的重要组成；量化方法和技术的研究也构成了运筹学的重要组成；(数数 学分支，最优化技术学分支，最优化技术) n运筹学研究的目标是对

5、现实决策问题进行求解或评估，运筹学研究的目标是对现实决策问题进行求解或评估， 以达到优化决策的目的。以达到优化决策的目的。(方法论方法论vs决策科学决策科学) School of Business ECUST 现实中的决策问题现实中的决策问题 数量化的方法与技术 解决解决 运筹学(OR) School of Business ECUST 1.2 1.2 运筹学研究的系统过程运筹学研究的系统过程 定义现实中的问题 建立数学模型 对模型进行求解 对解进行验证， 必要时修正模型 结果的实施 School of Business ECUST 示例示例1.1 1.1 下料问题下料问题 o 某工厂要做某工

6、厂要做100套三角钢架，每套用长为套三角钢架，每套用长为2.9m、2.1m和和 1.5m的圆钢各一根。已知原料每根长的圆钢各一根。已知原料每根长7.4m，问应如何，问应如何 下料，可使所用原料最省。下料，可使所用原料最省。 o （1）分析问题）分析问题 n最简单的做法是：最简单的做法是： n还有没有其他裁剪方案？还有没有其他裁剪方案？ 1.52.12.9 7.4 0.9 School of Business ECUST n经过分析，我们可以制定下列经过分析，我们可以制定下列5种方案可供裁剪：种方案可供裁剪： n问题转换为：各种截法分别为多少根，使得在完成问题转换为：各种截法分别为多少根，使得在

7、完成100套钢架套钢架 任务的条件下，使所用总的原料根数最少？任务的条件下，使所用总的原料根数最少？ 方案方案 长度长度 截法截法 x1 截法截法 x2 截法截法 x3 截法截法 x4 截法截法 x5 2.912010 2.100221 1.531203 合计合计7.47.37.27.16.6 料头料头00.10.20.30.8 School of Business ECUST o （2）建立模型）建立模型 设按设按，截法下料的原材料根数分别为截法下料的原材料根数分别为x1， x2，x3，x4，x5，可列出下面的数学模型。，可列出下面的数学模型。 目标函数：目标函数： min z= x1+x2

8、+x3+x4+x5 约束条件：约束条件： x1+ 2x2 +x4 100 2x3 + 2x4+ x5 100 3x1 + x2+ 2x3 +3x5 100 x1，x2，x3，x4，x5 0 x1=30，x2=10，x3=0，x4=50，x5=0 数学模型 解 求求 解解 School of Business ECUST o 在建立数学模型的过程中，需要明确： n决策变量是什么？求解的对象 n决策的目标是什么？ 目标函数 n有哪些限制条件？ 约束条件 例1.2 城市更新模型( Taha, 运筹学导论第8版) o A市面临着严重的财政收入不足问题，为了寻求一种长 期解决方案，市政府决定征用一块内城

9、的住宅区域，进 行一项现代化的房地产开发项目，以增加税收来源。 o 改造工程分为两个阶段：(一)拆除不符合标准的住宅， 为新的开发提供土地；(二) 建设新的建筑。下面是情况 概要： n(1) 最多可拆除300套不符合标准的旧住宅，每套住宅占 地0.25英亩，拆除一套征地住宅的成本是2000美元。 n(2) 新建设的单、双、三和四户型住宅的占地面积分别为 0.18、0.28、0.4和0.5英亩。街道、开阔地和公共设施占 可利用面积总量的15%。 n(3) 在新的开发项目中，三户型和四户型的住宅单元数的 总和至少占住宅单元总量的25%；单户型住宅单元数至 少应占总单元数的20%，双户型住宅单元数至

10、少占总单 元数的10%。 n(4) 对于单、双、三和四户型住宅，每个单元的征税额分 别为1000美元、1900美元、2700美元和3400美元。 n(5) 对于单、双、三和四户型住宅，每个单元的建筑成本 分别为50000美元、70000美元、130000美元和160000美 元。通过当地银行筹措资金总计最高达到1500万美元。 o 问：各种户型的住宅单元分别应建多少套，可使税收总 额达到最大？ 数学模型的建立数学模型的建立 o 除了确定建造每种类型住宅单元的数量外，我们还需要 确定有多少套旧房屋必须拆除，为新的开发项目提供场 地。因此，问题的变量可定义如下： nx1-建造单户型住宅的单元数 n

11、x2-建造双户型住宅的单 nx3-建造三户型住宅的单元数 nx4-建造四户型住宅的单元数 nx5-拆除旧住宅的单元数 o 目标函数是从新建的四类住宅中获得的税收最大，即 o 问题的第一个约束是土地可用量： n用于新建住宅的面积 = 总单元数量的20% n双户型住宅数量 = 总单元数量的10% n三户型和四户型住宅数量之和 = 总单元数量的25% n这些约束可表示为 11234 21234 341234 0. 2 0. 1 0. 25 xxxxx xxxxx xxxxxx o 还剩下一个约束就是要保证拆除和建设的总费用在允许 的预算内 n以1000美元表示费用的单位，可表示为 12345 507

12、0130160215000 xxxxx 12.34 12345 5 11234 21234 341234 12345 m ax1000190027003400 0. 180. 280. 40. 50. 25115% 300 0. 2 .0. 1 0. 25 5070130160215000 0,1,2,. . . ,5 j zxxxx xxxxx x xxxxx st xxxxx xxxxxx xxxxx xj 1.3 1.3 运筹学的产生与发展运筹学的产生与发展 o 我国古代朴素的运筹学思想 n战国时期，李冰父子修建的都江堰水利工程 n北宋时期的丁渭修皇宫 n春秋时期的田忌赛马 o 运筹学产

13、生的渊源 n兰彻斯特方程：1914年英国工程师兰彻斯特(F.W. Lanchester)在英国工程杂志上发表了一篇论文, 文中 建立的描述作战双方兵力变化过程的数学方程被称为兰 彻斯特方程，对集中兵力这一重要的军事原则作出了科 学的论证。这是最早将数学定量分析方法应用于军事作 战研究的文献之一，是运筹学产生的重要渊源。 n丹麦工程师A.K. Erlang在二十世纪初发展的排队论 n数理经济学派的研究: o 运筹学的产生 n二战期间，英、美等国组建的作战研究(operational research)小组进行的关于战略、战术的研究工作。 nBawdsey雷达站的研究工作 负责人A.P. Rowe

14、提出立即进行整个防空作战系统运行的研 究。所研究的具体问题有：设计将雷达信息传送给指挥系 统及武器系统的最佳方式；雷达与防空武器的最佳配置； 由于对探测、信息传递、作战指挥、战斗机与防空火力协 调等获得成功，大大提高了英国本土的防空能力，不久以 后在对抗德国对英伦三岛的狂轰滥炸中发挥了极大的作用 。 Bawdsey也被称为运筹学的发源地。 n大西洋反潜战(1942年) 1942年，应英国要求美国派麻省理工学院的Morse教授率领 一个小组去协助进行反潜战的作战研究工作 。Morse小组 经过多方实地考察，最后提出了两条重要建议: (1) 将反潜攻击由反潜潜艇投掷水雷，改为飞机投掷深水炸弹。 起

15、爆深度由100米左右改为25米左右。即当潜艇刚下潜时攻击效 果最佳。(提高效率4-7倍) (2) 运送物资的船队及护航舰队编队，由小规模多批次，改为加大 规模、减少批次，这样，损失率将减少。（25%下降到10%） 丘吉尔采纳了MORSE的建议，最终成功地打破封锁，并重创了德 国潜艇。MORSE同时获得英国和美国的最高勋章。 o 运筹学的发展 n二战之后，二战期间成立的运筹学小组成员把在战争中积累的 丰富经验与理论方法转向了民用问题，运筹学开始进入工业部 门和管理领域。运筹学作为一门学科逐步发展起来： 1947年，Dantzig提出线性规划的单纯形法 19501956年间，线性规划对偶理论诞生 1951年 ，Knhn-Tuker定理奠定了非线性规