全校性公选课—绪论.ppt

运运 筹筹 学学 孙滢 北方民族大学 信息与计算科学学院 ( Operations Research ) 运 筹 制定策略、策划 “夫运筹帷幄之中，决胜于千里之外” 史记高祖本纪 参考资料 教材： 钱颂迪. 运筹学（本科版）. 清华大学出版社 胡运权.运筹学教程（第二版）. 清华大学出版社 刁在筠等. 运筹学（第三版）.高等教育出版社 软件： Matlab Lingo Lindo Excel 要求 第一章 绪论 运筹学的简史 运筹学的性质和特点 运筹学的工作步骤 运筹学的模型 运筹学的应用 运筹学的展望 1 运筹学的简史 二战以前 萌 芽 二战期间 产 生 五六十年代 发 展 七八十年代 成 熟 第二次世界大战期间，英国为了应用雷达探测 德国飞机对英国本土的空袭，组成了由物理学家、 数学家、天文学家、生物学家和军官参加的作战研 究小组。第一次应用了 Operational Research 这 个名词。因研究成果显著，后又从空军扩展到海军 和陆军。在英国成立这种研究小组不久，美国也建 立了类似的小组，但称之为OperationOperations Research Research ，简称OR.OR. 第二次世界大战之后，在英、美军队中相继成 立了正式运筹研究组织，以兰德公司（LAND）为 首的一些部门开始着重研究战略性问题。例如，为 美国空军评价各种轰炸机系统，讨论未来的武器系 统和未来战争的战略等；研究苏联的军事能力及未 来的预报等。总的来说，在这段时间里运筹学的研 究与应用范围主要是与战争相关的战略、战术方面 问题。 由于运筹学适应时代的要求，在近六十年中 ，它无论从理论上还是应用上都得到了快速的发 展。在应用方面，今天运筹学已经涉及到了服务 、管理、规划、决策、组织、生产、建设等诸多 方面，甚至可以说，很难找出它涉及不到的领域 。 20世纪50年代中期，我国著名的科学家钱学 森、许国志等将运筹学从西方引入我国，并结合 我国的特点在国内推广应用。自从引入以来，运 筹学在我国已有四十多年的历史。经过这四十多 年，运筹学在我国有了很大的发展，确立了它在 经济建设中的地位。但是，运筹学在我国的发展 状况与世界其它国家相比，尚有不小的差距，其 中最主要的是认识与基础的问题。 都江堰水利工程 战国时期（大约公元前250年）川西太守李冰父 子主持修建。其目标是：利用岷江上游的水资源灌溉 川西平原。追求的效益还有防洪与航运。其总体构思 是系统思想的杰出运用。 都江堰由三大工程及120多项配套工程组成： 1.“鱼嘴”岷江分水工程：将岷江水有控制地引入内江。 2.“飞沙堰”分洪排沙工程：将泥沙排入外江。 3.“宝瓶口”引水工程：除沙后的江水引入水网干道。 它们巧妙结合，完整而严密，相得益彰。两千多年来，这 项工程一直发挥着巨大的效益，是我国最成功的水利工程。 运筹思想的应用运筹思想的应用 丁谓的皇宫修复工程 北宋年间，丁谓负责修复火毁的开封皇宫 。他的施工方案是：先将工程皇宫前的一条大 街挖成一条大沟，将大沟与汴水相通。使用挖 出的土就地制砖，令与汴水相连形成的河道承 担繁重的运输任务；修复工程完成后，实施大 沟排水，并将原废墟物回填，修复成原来的大 街。丁谓将取材、运输及废墟物的处理用“一沟 三用”巧妙地解决了。 上上中中下下 田忌田忌下下上上中中 最终净胜一局，赢得1000金。 齐王要与大臣田忌赛马，双方出上、中、下马 各一匹，对局三次，每次胜负1000金。田忌在好友 、著名的军事谋略家孙膑的指导下，以以下安排： 田忌赛马 齐王 2 运筹学的性质和特点 （1）运筹学的定义 到目前为止，运筹学还没有一个比较完善的统一 的定义。下面列出一些比较有代表性的看法： 英国运筹学学会认为：运筹学是应用于指导和管 理工商业、政府和国防方面有关人员、设备、物资以 及资金的大系统中所发生的各种问题的科学方法。 美国运筹学学会认为：运筹学是一种进行定量分 析的科学方法，它通过评价一个管理系统中可供选择 的方案的有关因素，提供改进管理的决策基础。 我国运筹学研究工作者认为：运筹学是指应用 系统的、科学的、数学分析的方法，通过建立、检 验和求解数学模型，而获得最优决策的科学。 综上所述：运筹学是运用数学方法研究解决经 济和工程管理中，资源的有效利用，任务的合理分 配，方案的正确选择的科学，是一门研究如何以有 限的资源，完成最大的任务，取得最优的经济效果 的科学。 运筹学是一种给出问题坏的答案的艺术， 否则的话问题的结果会更坏； 这个定义表明运筹学强调最优决策过分理 想，在现实中很难实现，于是用次优、满意 等概念来代替最优。 （2）运筹学的特点 第一个特点是从全局的观点看问题，追求总体效果最优。 第二个特点是通过建立与求解模型，使问题在量化的基础 上得到合理的决策。在建立模型及求解的过程中，要用到一 些数学方法和技巧，故运筹学工作者必须具有一定的数学基 础。 第三个特点是多学科交叉，大而复杂的系统，往往是政 治、经济、技术、社会、心理、生态等多种因素交织在一 起。 第四个特点是与计算机密切相关。历史表明，没有计算 机的发展，就没有运筹学的发展。在应用运筹学解决问题 时，一般都要借助计算机计算，手算是不现实的。 运用运筹学方法解决问题的一般步骤: 1、提出并形成问题 2、建立模型 3、分析并求解模型 4、检验并评价模型 5、应用或实施模型的解 最优化技术 课程重点 3 运筹学的工作步骤 运筹学建模在理论上，应是属于数学建模的一个 部分。因此，运筹学建模所采用的手段、途径与一般 在数学建模中所采用的类似。 经过长期、深入的研究和发展，运筹学处理的问 题归纳成一系列具有较强背景和规范特征的典型问题 。因此，运筹学建模就要把相当的精力放在将实际问 题合理地描述为某种典型的运筹模型上。在这个过程 中，一般要求运筹学工作者具有以下几个方面的知识 和能力： 4 运筹学的模型 (1)熟悉典型运筹模型的特征和它的应用背景； (2)有分析、理解实际问题的能力，包括广博的知识 、搜集信息、资料和数据的能力； (3)有抽象分析问题的能力，包括善于抓主要矛盾， 善于逻辑思维、推理、归纳、联想、类比等形成的 创新能力； (4)有运用各类工具知识的能力，包括运用数学、计 算机、其它自然科学的知识和工程技术等的能力； (5)有试验校正和维护修正模型等的能力。 根据问题本身的情况，运筹学在解决问题时，按 研究对象不同可构造各种不同的模型。模型是研究者 对客观现实经过思维抽象后用文字、图表、符号、关 系式以及实体描述所认识到的客观对象。模型的有关 参数和关系式比较容易改变，这样将有助于问题的分 析和研究。利用模型可以对所研究的问题进行一定预 测及灵敏度分析等。 模型的三种基本形式： 三种基本形式 形象模型 模拟模型 符号或数学模型 建立、构造模型是一种创造性劳动，成功的 模型往往是科学和艺术的结晶，常见的构模方法和 思路有以下几种： 直接分析法 类比分析法 数据分析法 试验分析法 构想（构思）法 机理 清楚 机理 不清楚 五 种 方 法 和 思 路 模型的一般形式 目标评价准则：V = f （ xi , yj , k ） 约 束 条 件： g （xi , yj ,k ） 0 其中：x i 为可控变量；yj 为已知 参数；k 为随机因素 或：max (或min ) Z = f ( x1 . x2 . . . . . .xn ) gi ( x1 . x2 . . . . . .xn ) ( . ) 0 ( i = 1.2m ) hj (x1 . x2 . . . . . .xn ) = 0 ( j = 1.2l ) 其中：xj ( i = 1.2n )为决策变量 Z 为目标函数 gi ( x1 . x2 . . . . . .xn ) 0 和 hj (x1 . x2 . . . . . .xn ) = 0 为约束条件 s.t. 5 运筹学的应用 运筹学在早期的研究主要在军事领域，二次 大战后运筹学的研究转向民用。经过几十年的发展 ，运筹学的研究范围已经涉及到社会、政治、经济 、军事、科学、技术等各个领域，发挥了巨大作用 。这里选择几个管理方面的应用给予简单介绍。 1、生产运作：生产总体计划要求从总体确定 生产、存贮和劳动力的配合规划以适应波动的需求 计划。运筹学的应用主要在生产作业的计划、日程 表的编排、合理下料、配料问题、物料管理等方面 ； 2、物资库存管理：多种物资库存的系统组织 与安排管理，确定某些设备的能力或容量，如停车 场的大小、新增发电设备的容量大小、电子计算机 的内存量、合理的水库容量等。将库存理论与计算 机的物资管理信息系统相结合，确定合理的库存方 式、计算最佳的库存量等 ； 3、物资运输问题：涉及空运、水运、公路运 输、铁路运输、管道运输、厂内运输。常常涉及班 次和人员服务时间安排等，需要确定最小成本的运 输线路、物资的调拨、运输工具的调度等； 4、组织人事管理：对人员的需求和使用方面 的预测，确定人员编制、人员合理分配，建立人 才评价体系、人才开发的规划、激励机制的研究 等； 5、市场营销：广告预算、媒介选择、产品定 价、新产品的引入和开发、销售计划制定、市场 模拟研究等； 6、财务管理和会计：各经济项目的预测、预 算，贷款、成本分析、证券管理、现金管理等。 常使用的方法有统计分析、数学规划、决策分析 、盈亏点分析法、价值分析法等； 7、计算机应用和信息系统开发：运筹学中的 数学规划方法、网络图论、排队论、存储论、模拟 与仿真方法等均起到巨大作用； 8、城市管理：各种紧急服务系统的设计和运 用、城市垃圾的清扫、搬运和处理、城市供水和污 水处理系统的规划、区域规划、市区交通网络的规 划与管理等。 6 运筹学的主要内容 线性规划 非线性规划 整数规划 多目标规划 动态规划 图与网络优化 存储论 排队论 对策论 决策分析 排序与统筹方法 随机规划 预测 智能优化算法简介 7 运筹学的展望 运筹学的理论研究将会得到进一步系统地、深入地发展 运筹学向一些新的研究领域发展 运筹学分散融于其他学科，并结合其他学科一起发展 运筹学沿原有的各学科分支向前发展 运筹学中建立模型的问题将日益受到重视 运筹学的发展将进一步依赖于计算机的应用和发展 e.g.1 婚姻问题 (matching problem) DEF 女儿追求者 A B C E D F 3 27 1 5 10 4 26 28 共有3!=6种 可能 得到分配矩阵： 如何嫁娶， 使获得的礼品 最多？ 7 8 运筹学的例子 DEF 1.贪婪（Greedy) 解一 般不会产生最差解； 2.在某些模型中，贪 婪算法能得到最优解； . 可以使用穷举法， 但是以时间为代价 贪婪解的结果： 28+5+1=34 最优解的结果： 27+4+26=57 Note： 最差解的结果： 3+10+7=20 e.g.2 阿克米自行车的装配问题 工 序紧前工序加工时间工 序紧前工序加工时间 A8FD2 BA7GF2 CA，E7HE，G8 D2IE，G8 ED3JB，C15 由两名熟练工人进行装配，要求装完时间最早。 0 2 5 7 8 9 1516 23 31 P1 P2 AB CEFG HI JD 如果每道工序的加工时间减少1，最优时间表会小 于31吗？ 0 1 3 4 5 7 13 20 27 ABJ DCEFGHI P1 P2 最优耽搁排序 工 序紧前工序加工时间工 序紧前工序加工时间 A7FD1 BA6GF1 CA，E6HE，G7 D1IE，G7 ED2JB，C14 AB CD E F GH I J 0 1 3 4 5 7 1213 18 20 32 P1 P2 最优无耽搁排序 工 序紧前工序加工时间工 序紧前工序加工时间 A7FD1 BA6GF1 CA，E6HE，G7 D1IE，G7 ED2JB，C14 忙碌规则： 凡有工作可做就不能闲着 如果加工时间不变而增加一个装配工人，最优时 间表会小于31吗？ 最优耽搁排序 0 2 4 5 6 8 12 1415 22 30 P1 P2 P3 A DF G EC H B I J 工 序紧前工序加工时间工 序紧前工序加工时间 A8FD2 BA7GF2 CA，E7HE，G8 D2IE，G8 ED3JB，C15 最优无耽搁排序 0 2 4 5 6 8 1415 21 36 P1 P2 P3 A DE F G H I B CJ 工 序紧前工序加工时间工 序紧前工序加工时间 A8FD2 BA7GF2 CA，E7HE，G8 D2IE，G8 ED3JB，C15 e.g.3 旅行商问题 （Traveling Salesman Problem） 共有（ n-1)! 种可能 TSP 有一位旅行售货员要到城市 进行商 品销售，已知： 的距离为 他从 n 个城市的某个城市出发，去每个城市一次且仅 一次（在欧氏距离下）回到出发的城市。问应如何计 划他的旅行路线，使他所走的路线总长度最短？ 设有n个城市（有向图）则有（n-1）！种可 能方案。以计算机1秒可以完成24个城市所有路 径枚举为单位，则 城市数 24 25262728 29 30 31 计计算时间时间 1 1s s 2424s s1010minmin4. 34. 3h h4.94.9d d 136.5136.5d d10.810.8y y 325325y y 若没有现成可直接应用的计算机程序，则需要以 下两步工作： 计算手段的拟定。在模型研制的同时，需要研究如 何用数值方法求解模型。其中包括对问题变量性质(确定 性、随机性、模糊性)、关系特征(线性，非线性)、手段( 模拟，优化)及使用方法(现有的，新构造的)等的确定； 程序明细表的编制。程序设计和调试。对于计算过 程需要编制程序来实现计算机运算，运算学研究应包含算 法过程的描述，计算流程框图绘制。程序的实现及调试可 以交由程序员完成，或会同程序员完成。 (1)直接分析