全校性公选课-绪论课件

1、( Operations Research )运运 筹筹制定策略、策划制定策略、策划“夫夫运筹运筹帷幄之中，决胜于千里之外帷幄之中，决胜于千里之外”史记史记高祖本纪高祖本纪 参考资料参考资料 教材：教材： 钱颂迪钱颂迪. . 运筹学（本科版）运筹学（本科版）. . 清华大学出版社清华大学出版社 胡运权胡运权. .运筹学教程（第二版）运筹学教程（第二版）. . 清华大学出版社清华大学出版社 刁在筠等刁在筠等. . 运筹学（第三版）运筹学（第三版）. .高等教育出版社高等教育出版社 软件：软件： MatlabMatlab LingoLingo LindoLindo ExcelExcel要求要求第一

2、章第一章 绪论绪论运筹学的简史运筹学的简史运筹学的性质和特点运筹学的性质和特点运筹学的工作步骤运筹学的工作步骤运筹学的模型运筹学的模型运筹学的应用运筹学的应用运筹学的展望运筹学的展望1 运筹学的简史运筹学的简史二战以前二战以前萌萌芽芽二战期间二战期间产产生生五六十年代五六十年代发发展展七八十年代七八十年代成成熟熟 第二次世界大战期间，英国为了应用雷达探测第二次世界大战期间，英国为了应用雷达探测德国飞机对英国本土的空袭，组成了由物理学家、德国飞机对英国本土的空袭，组成了由物理学家、数学家、天文学家、生物学家和军官参加的作战研数学家、天文学家、生物学家和军官参加的作战研究小组。第一次应用了究小组。

3、第一次应用了 Operational Research 这这个名词。因研究成果显著，后又从空军扩展到海军个名词。因研究成果显著，后又从空军扩展到海军和陆军。在英国成立这种研究小组不久，美国也建和陆军。在英国成立这种研究小组不久，美国也建立了类似的小组，但称之为立了类似的小组，但称之为s ，简称简称 第二次世界大战之后，在英、美军队中相继成第二次世界大战之后，在英、美军队中相继成立了正式运筹研究组织，以兰德公司（立了正式运筹研究组织，以兰德公司（LAND）为）为首的一些部门开始着重研究战略性问题。例如，为首的一些部门开始着重研究战略性问题。例如，为美国空军评价各种轰炸机系统，讨论未来的武器系美国

4、空军评价各种轰炸机系统，讨论未来的武器系统和未来战争的战略等；研究苏联的军事能力及未统和未来战争的战略等；研究苏联的军事能力及未来的预报等。总的来说，在这段时间里运筹学的研来的预报等。总的来说，在这段时间里运筹学的研究与应用范围主要是与战争相关的战略、战术方面究与应用范围主要是与战争相关的战略、战术方面问题。问题。 由于运筹学适应时代的要求，在近六十年中，由于运筹学适应时代的要求，在近六十年中，它无论从理论上还是应用上都得到了快速的发展。它无论从理论上还是应用上都得到了快速的发展。在应用方面，今天运筹学已经涉及到了服务、管在应用方面，今天运筹学已经涉及到了服务、管理、规划、决策、组织、生产、建

5、设等诸多方面，理、规划、决策、组织、生产、建设等诸多方面，甚至可以说，很难找出它涉及不到的领域。甚至可以说，很难找出它涉及不到的领域。 20世纪世纪50年代中期，我国著名的科学家钱学年代中期，我国著名的科学家钱学森、许国志等将运筹学从西方引入我国，并结合森、许国志等将运筹学从西方引入我国，并结合我国的特点在国内推广应用。自从引入以来，运我国的特点在国内推广应用。自从引入以来，运筹学在我国已有四十多年的历史。经过这四十多筹学在我国已有四十多年的历史。经过这四十多年，运筹学在我国有了很大的发展，确立了它在年，运筹学在我国有了很大的发展，确立了它在经济建设中的地位。但是，运筹学在我国的发展经济建设中

6、的地位。但是，运筹学在我国的发展状况与世界其它国家相比，尚有不小的差距，其状况与世界其它国家相比，尚有不小的差距，其中最主要的是认识与基础的问题。中最主要的是认识与基础的问题。都江堰水利工程都江堰水利工程 战国时期（大约公元前战国时期（大约公元前250年）川西太守李冰父年）川西太守李冰父子主持修建。其目标是：利用岷江上游的水资源灌子主持修建。其目标是：利用岷江上游的水资源灌溉川西平原。追求的效益还有防洪与航运。其总体溉川西平原。追求的效益还有防洪与航运。其总体构思是系统思想的杰出运用构思是系统思想的杰出运用。都江堰由三大工程及都江堰由三大工程及120多项配套工程组成：多项配套工程组成：1.“鱼

7、嘴鱼嘴”岷江分水工程：将岷江水有控制地引入内江。岷江分水工程：将岷江水有控制地引入内江。2.“飞沙堰飞沙堰”分洪排沙工程：将泥沙排入外江。分洪排沙工程：将泥沙排入外江。3.“宝瓶口宝瓶口”引水工程：除沙后的江水引入水网干道。引水工程：除沙后的江水引入水网干道。 它们巧妙结合，完整而严密，相得益彰。两千多年来，这它们巧妙结合，完整而严密，相得益彰。两千多年来，这项工程一直发挥着巨大的效益，是我国最成功的水利工程。项工程一直发挥着巨大的效益，是我国最成功的水利工程。丁谓的皇宫修复工程丁谓的皇宫修复工程 北宋年间，丁谓负责修复火毁的开封皇宫。北宋年间，丁谓负责修复火毁的开封皇宫。他的施工方案是：先将

8、工程皇宫前的一条大街他的施工方案是：先将工程皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。使用挖出挖成一条大沟，将大沟与汴水相通。使用挖出的土就地制砖，令与汴水相连形成的河道承担的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；修复工程完成后，实施大沟繁重的运输任务；修复工程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。排水，并将原废墟物回填，修复成原来的大街。丁谓将取材、运输及废墟物的处理用丁谓将取材、运输及废墟物的处理用“一沟三一沟三用用”巧妙地解决了。巧妙地解决了。最终净胜一局，赢得最终净胜一局，赢得10001000金。金。 齐王要与大臣田忌赛马，双方出上、中、下马齐

9、王要与大臣田忌赛马，双方出上、中、下马各一匹，对局三次，每次胜负各一匹，对局三次，每次胜负1000金。田忌在好友、金。田忌在好友、著名的军事谋略家孙膑的指导下，以以下安排：著名的军事谋略家孙膑的指导下，以以下安排：田忌赛马田忌赛马齐王齐王2 2 运筹学的性质和特点运筹学的性质和特点（1）运筹学的定义）运筹学的定义 到目前为止，运筹学还没有一个比较完善的统一到目前为止，运筹学还没有一个比较完善的统一的定义。下面列出一些比较有代表性的看法：的定义。下面列出一些比较有代表性的看法： 英国运筹学学会认为英国运筹学学会认为：运筹学是应用于指导和管：运筹学是应用于指导和管理工商业、政府和国防方面有关人员、

10、设备、物资以理工商业、政府和国防方面有关人员、设备、物资以及资金的大系统中所发生的各种问题的科学方法。及资金的大系统中所发生的各种问题的科学方法。 美国运筹学学会认为美国运筹学学会认为：运筹学是一种进行定量分：运筹学是一种进行定量分析的科学方法，它通过评价一个管理系统中可供选择析的科学方法，它通过评价一个管理系统中可供选择的方案的有关因素，提供改进管理的决策基础。的方案的有关因素，提供改进管理的决策基础。 我国运筹学研究工作者认为我国运筹学研究工作者认为：运筹学是指应用：运筹学是指应用系统的、科学的、数学分析的方法，通过建立、检系统的、科学的、数学分析的方法，通过建立、检验和求解数学模型，而获

11、得最优决策的科学。验和求解数学模型，而获得最优决策的科学。 综上所述综上所述：运筹学是运用数学方法研究解决经：运筹学是运用数学方法研究解决经济和工程管理中，资源的有效利用，任务的合理分济和工程管理中，资源的有效利用，任务的合理分配，方案的正确选择的科学，是一门研究如何以有配，方案的正确选择的科学，是一门研究如何以有限的资源，完成最大的任务，取得最优的经济效果限的资源，完成最大的任务，取得最优的经济效果的科学。的科学。 运筹学是一种给出问题坏的答案的艺术，运筹学是一种给出问题坏的答案的艺术，否则的话问题的结果会更坏；否则的话问题的结果会更坏； 这个定义表明运筹学强调最优决策过分理这个定义表明运筹

12、学强调最优决策过分理想，在现实中很难实现，于是用次优、满意想，在现实中很难实现，于是用次优、满意等概念来代替最优。等概念来代替最优。 （2）运筹学的特点）运筹学的特点 第一个特点是第一个特点是从全局的观点看问题，追求总体效果最优。从全局的观点看问题，追求总体效果最优。 第二个特点是第二个特点是通过建立与求解模型，使问题在量化的基础通过建立与求解模型，使问题在量化的基础上得到合理的决策。在建立模型及求解的过程中，要用到一上得到合理的决策。在建立模型及求解的过程中，要用到一些数学方法和技巧，故运筹学工作者必须具有一定的数学基些数学方法和技巧，故运筹学工作者必须具有一定的数学基础。础。 第三个特点是

13、第三个特点是多学科交叉，大而复杂的系统，往往是政多学科交叉，大而复杂的系统，往往是政治、经济、技术、社会、心理、生态等多种因素交织在一治、经济、技术、社会、心理、生态等多种因素交织在一起。起。 第四个特点是第四个特点是与计算机密切相关。历史表明，没有计算与计算机密切相关。历史表明，没有计算机的发展，就没有运筹学的发展。在应用运筹学解决问题机的发展，就没有运筹学的发展。在应用运筹学解决问题时，一般都要借助计算机计算，手算是不现实的。时，一般都要借助计算机计算，手算是不现实的。运用运筹学方法解决问题的一般步骤运用运筹学方法解决问题的一般步骤:1、提出并形成问题提出并形成问题2、建立模型建立模型3、

14、分析并求解模型分析并求解模型4、检验并评价模型检验并评价模型5、应用或实施模型的解应用或实施模型的解最优化技术最优化技术课程重点课程重点3 3 运筹学的工作步骤运筹学的工作步骤 运筹学建模在理论上，应是属于数学建模的一个运筹学建模在理论上，应是属于数学建模的一个部分。因此，运筹学建模所采用的手段、途径与一般部分。因此，运筹学建模所采用的手段、途径与一般在数学建模中所采用的类似。在数学建模中所采用的类似。 经过长期、深入的研究和发展，运筹学处理的问经过长期、深入的研究和发展，运筹学处理的问题归纳成一系列具有较强背景和规范特征的典型问题。题归纳成一系列具有较强背景和规范特征的典型问题。因此，运筹学

15、建模就要把相当的精力放在将实际问题因此，运筹学建模就要把相当的精力放在将实际问题合理地描述为某种典型的运筹模型上。在这个过程中，合理地描述为某种典型的运筹模型上。在这个过程中，一般要求运筹学工作者具有以下几个方面的知识和能一般要求运筹学工作者具有以下几个方面的知识和能力：力：4 4 运筹学的模型运筹学的模型(1)熟悉典型运筹模型的特征和它的应用背景；熟悉典型运筹模型的特征和它的应用背景；(2)有分析、理解实际问题的能力，包括广博的知识、有分析、理解实际问题的能力，包括广博的知识、搜集信息、资料和数据的能力；搜集信息、资料和数据的能力；(3)有抽象分析问题的能力，包括善于抓主要矛盾，有抽象分析问

16、题的能力，包括善于抓主要矛盾，善于逻辑思维、推理、归纳、联想、类比等形成的善于逻辑思维、推理、归纳、联想、类比等形成的创新能力；创新能力； (4)有运用各类工具知识的能力，包括运用数学、计有运用各类工具知识的能力，包括运用数学、计算机、其它自然科学的知识和工程技算机、其它自然科学的知识和工程技术等的能力；术等的能力； (5)有试验校正和维护修正模型等的能力。有试验校正和维护修正模型等的能力。 根据问题本身的情况，运筹学在解决问题时，按根据问题本身的情况，运筹学在解决问题时，按研究对象不同可构造各种不同的模型。模型是研究者研究对象不同可构造各种不同的模型。模型是研究者对客观现实经过思维抽象后用文

17、字、图表、符号、关对客观现实经过思维抽象后用文字、图表、符号、关系式以及实体描述所认识到的客观对象。模型的有关系式以及实体描述所认识到的客观对象。模型的有关参数和关系式比较容易改变，这样将有助于问题的分参数和关系式比较容易改变，这样将有助于问题的分析和研究。利用模型可以对所研究的问题进行一定预析和研究。利用模型可以对所研究的问题进行一定预测及灵敏度分析等。测及灵敏度分析等。模型的三种基本形式：模型的三种基本形式：三种基本形式三种基本形式形象模型形象模型 模拟模型模拟模型符号或数学模型符号或数学模型 建立、构造模型是一种创造性劳动，成功的建立、构造模型是一种创造性劳动，成功的模型往往是科学和艺术

18、的结晶，常见的构模方法模型往往是科学和艺术的结晶，常见的构模方法和思路有以下几种：和思路有以下几种：直接分析法直接分析法类比分析法类比分析法 数据分析法数据分析法 试验分析法试验分析法构想（构思）法构想（构思）法机理机理清楚清楚机理机理不清楚不清楚五五种种方方法法和和思思路路模型的一般形式模型的一般形式目标评价准则：目标评价准则：V = f （ xi , yj , k ） 约约 束束 条条 件：件： g （xi , yj ,k ） 0 其中：其中：x i 为可控变量；为可控变量；yj 为已知为已知参数；参数；k 为随机因素为随机因素 或或：max (或或min ) Z = f ( x1 . x

19、2 . . . . . .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 运筹学的应用运筹学的应用 运筹学在早期的研究主要在军事领域，二次运筹学在早期的研究主要在军事领域，二次大战后运筹学的研究转

20、向民用。经过几十年的发展，大战后运筹学的研究转向民用。经过几十年的发展，运筹学的研究范围已经涉及到社会、政治、经济、运筹学的研究范围已经涉及到社会、政治、经济、军事、科学、技术等各个领域，发挥了巨大作用。军事、科学、技术等各个领域，发挥了巨大作用。这里选择几个管理方面的应用给予简单介绍。这里选择几个管理方面的应用给予简单介绍。 1、生产运作、生产运作：生产总体计划要求从总体确定：生产总体计划要求从总体确定生产、存贮和劳动力的配合规划以适应生产、存贮和劳动力的配合规划以适应波动的需求波动的需求计划。运筹学的应用主要在生产作业的计划、日程计划。运筹学的应用主要在生产作业的计划、日程表的编排、合理下

21、料、配料问题、物料管理等方面；表的编排、合理下料、配料问题、物料管理等方面； 2、物资库存管理：、物资库存管理：多种物资库存的系统组织多种物资库存的系统组织与安排管理，确定某些设备的能力或容量，如停车与安排管理，确定某些设备的能力或容量，如停车场的大小、新增发电设备的容量大小、电子计算机场的大小、新增发电设备的容量大小、电子计算机的内存量、合理的水库容量等。将库存理论与计算的内存量、合理的水库容量等。将库存理论与计算机的物资管理信息系统相结合，确定合理的库存方机的物资管理信息系统相结合，确定合理的库存方式、计算式、计算最佳的库存量等最佳的库存量等 ； 3、物资运输问题：、物资运输问题：涉及空运

22、、水运、公路运涉及空运、水运、公路运输、铁路运输、管道运输、厂内运输。常常涉及班输、铁路运输、管道运输、厂内运输。常常涉及班次和人员服务时间安排等，需要确定最小成本的运次和人员服务时间安排等，需要确定最小成本的运输线路、物资的调拨、运输工具的调度等；输线路、物资的调拨、运输工具的调度等； 4、组织人事管理：、组织人事管理：对人员的需求和使用方对人员的需求和使用方面的预测，确定人员编制、人员合理面的预测，确定人员编制、人员合理分配，建立分配，建立人才评价体系、人才开发的规划、激励机制的研人才评价体系、人才开发的规划、激励机制的研究等；究等； 5、市场营销：、市场营销：广告预算、媒介选择、产品广告

23、预算、媒介选择、产品定价、新产品的引入和开发、销售计划制定、市定价、新产品的引入和开发、销售计划制定、市场模拟研究等；场模拟研究等； 6、财务管理和会计：、财务管理和会计：各经济项目的预测、各经济项目的预测、预算，贷款、成本分析、证券管理、现金管理等。预算，贷款、成本分析、证券管理、现金管理等。常使用的方法有统计分析、数学规划、决策分析、常使用的方法有统计分析、数学规划、决策分析、盈亏点分析法、价值分析法等；盈亏点分析法、价值分析法等； 7 7、计算机应用和信息系统开发：、计算机应用和信息系统开发：运筹学中的运筹学中的数学规划方法、网络图论、排队论、存储论、模拟数学规划方法、网络图论、排队论、

24、存储论、模拟与仿真方法等均起到巨大作用；与仿真方法等均起到巨大作用； 8 8、城市管理：、城市管理：各种紧急服务系统的设计和运各种紧急服务系统的设计和运用、城市垃圾的清扫、搬运和处理、城市供水和污用、城市垃圾的清扫、搬运和处理、城市供水和污水处理系统的规划、区域规划、市区交通网络的规水处理系统的规划、区域规划、市区交通网络的规划与管理等。划与管理等。 6 6 运筹学的主要内容运筹学的主要内容线性规划线性规划非线性规划非线性规划整数规划整数规划多目标规划多目标规划动态规划动态规划图与网络优化图与网络优化存储论存储论排队论排队论对策论对策论决策分析决策分析排序与统筹方法排序与统筹方法随机规划随机规

25、划预测预测智能优化算法简介智能优化算法简介7 7 运筹学的展望运筹学的展望运筹学的理论研究将会得到进一步系统地、深入地发展运筹学的理论研究将会得到进一步系统地、深入地发展运筹学向一些新的研究领域发展运筹学向一些新的研究领域发展运筹学分散融于其他学科，并结合其他学科一起发展运筹学分散融于其他学科，并结合其他学科一起发展运筹学沿原有的各学科分支向前发展运筹学沿原有的各学科分支向前发展运筹学中建立模型的问题将日益受到重视运筹学中建立模型的问题将日益受到重视运筹学的发展将进一步依赖于计算机的应用和发展运筹学的发展将进一步依赖于计算机的应用和发展e.g.1 婚姻问题婚姻问题 (matching prob

26、lem)3271510426287AKBCDEF女儿女儿追求者追求者ABCEDF327151042628共有共有3!=63!=6种种可能可能得到分配矩阵：得到分配矩阵：如何嫁娶，如何嫁娶，使获得的礼品使获得的礼品最多？最多？78 8 运筹学的例子运筹学的例子3271510426287AKBCDEF贪婪（贪婪（Greedy) Greedy) 解一解一般不会产生最差解；般不会产生最差解；在某些模型中，贪在某些模型中，贪婪算法能得到最优婪算法能得到最优解；解； . . 可以使用穷举法，可以使用穷举法， 但是以时间为代价但是以时间为代价贪婪解的结果：贪婪解的结果：28+5+1=3428+5+1=34最

27、优解的结果：最优解的结果：27+4+26=5727+4+26=57Note：最差解的结果：最差解的结果：3+10+7=203+10+7=20e.g.2 阿克米自行车的装配问题阿克米自行车的装配问题工工 序序紧前工序紧前工序加工时间加工时间工工 序序紧前工序紧前工序加工时间加工时间A8FD2BA7GF2CA，E7HE，G8D2IE，G8ED3JB，C15由两名熟练工人进行装配，要求装完时间最早。由两名熟练工人进行装配，要求装完时间最早。0 2 5 7 8 9 1516 23 31P1P2ABCEFGHIJD 如果每道工序的加工时间减少1，最优时间表会小于31吗？0 1 3 4 5 7 13 20

28、 27ABJDCEFGHIP1P2最优耽搁排序最优耽搁排序工工 序序紧前工序紧前工序加工时间加工时间工工 序序紧前工序紧前工序加工时间加工时间A7FD1BA6GF1CA，E6HE，G7D1IE，G7ED2JB，C14ABCD E F GHIJ 0 1 3 4 5 7 1213 18 20 32P1P2最优无耽搁排序最优无耽搁排序工工 序序紧前工序紧前工序加工时间加工时间工工 序序紧前工序紧前工序加工时间加工时间A7FD1BA6GF1CA，E6HE，G7D1IE，G7ED2JB，C14忙碌规则：忙碌规则：凡有工作可做就不能闲着凡有工作可做就不能闲着 如果加工时间不变而增加一个装配工人，最优时间表

29、会小于31吗？最优耽搁排序最优耽搁排序0 2 4 5 6 8 12 1415 22 30P1P2P3ADF GECHBIJ工工 序序紧前工序紧前工序加工时间加工时间工工 序序紧前工序紧前工序加工时间加工时间A8FD2BA7GF2CA，E7HE，G8D2IE，G8ED3JB，C15最优无耽搁排序最优无耽搁排序0 2 4 5 6 8 1415 21 36 P1P2P3ADEF GHIBCJ工工 序序紧前工序紧前工序加工时间加工时间工工 序序紧前工序紧前工序加工时间加工时间A8FD2BA7GF2CA，E7HE，G8D2IE，G8ED3JB，C15e.g.3 旅行商问题旅行商问题（Traveling

30、Salesman Problem）共有共有（n-1)!种可能种可能TSP 有一位旅行售货员要到城市有一位旅行售货员要到城市 进行商进行商品销售，已知：品销售，已知： 的距离为的距离为他从他从 n 个城市的某个城市出发，去每个城市一次且仅个城市的某个城市出发，去每个城市一次且仅一次（在欧氏距离下）回到出发的城市。问应如何计一次（在欧氏距离下）回到出发的城市。问应如何计划他的旅行路线，使他所走的路线总长度最短？划他的旅行路线，使他所走的路线总长度最短？. ( ,1,)ijwi jn12,nv vvijvv 设有n个城市（有向图）则有（n-1）！种可能方案。以计算机1秒可以完成24个城市所有路径枚举

31、为单位，则城市数城市数24 25262728 29 30 31计算时间计算时间 若没有现成可直接应用的计算机程序，则需要以若没有现成可直接应用的计算机程序，则需要以下两步工作：下两步工作： 计算手段的拟定。计算手段的拟定。在模型研制的同时，需要研究如何用数值方法求解模型。其中包括对问题变量性质(确定性、随机性、模糊性)、关系特征(线性，非线性)、手段(模拟，优化)及使用方法(现有的，新构造的)等的确定； 程序明细表的编制。程序明细表的编制。程序设计和调试。对于计算过程需要编制程序来实现计算机运算，运算学研究应包含算法过程的描述，计算流程框图绘制。程序的实现及调试可以交由程序员完成，或会同程序员完成。 (1)直接分析方法。直接分析方法。当我们对问题的内在关系、当我们对问题的内在关系、特征等比较熟悉时，可以根据对问题内在机理的特征等比较熟悉时，可以根据对问题内在机理的认识直接构造出模型。运筹学中已有不少现存的认识直接构造出模型。运筹学中已有不少现存的模型，如线性规划模型、投入产出模型、排队模模型，如线性规划模型、投入产出模型、排队模型、存贮