北京交通大学《运筹学》课件-第0章 绪论

运筹帷幄之中决胜千里之外运筹学OperationsResearch第

0

章绪论

北京交通大学本课程的教材及参考书选用教材《运筹学基础及应用》（第六版），胡运权等，高等教育出版社参考教材《运筹学》（第3版），钱颂迪主编，清华出版社《运筹学教程》（第3版），胡运权主编，清华出版社运筹学导论：初级篇（第八版），HamdyA.Taha著，薛毅等译，人民邮电出版社现代应用数学手册－运筹学与最优化卷，马振华主编，清华大学出版社。。。本课程授课方式与考核课程总成绩平时成绩（30％）课堂考勤（10％）作业（20％）专题研讨成绩（10％）讲授为主，结合习题作业期末成绩（60％）本学期上课安排每周三下午14:10-16:00、每周三上午14:10-16:00在前三周，以线上授课为基本教学手段腾讯会议（考勤、回答问题等）备用平台：腾讯课堂、雨课堂、微信、学校课程平台课程拟布置4-5次左右不设置中期考试课程中期将布置学生开展专题研讨第

1章绪论

学习目标了解运筹学课程的意义理解运筹学产生发展的概况与发展趋势理解运筹学性质、特点与学科地位理解运筹学主要学习内容与方法了解运筹学与其他学科的关系一、运筹学概况简述运筹学的称谓：

英文：

OperationsResearch

缩写：OR在日本译作“运用学”在香港、台湾译为“作业研究”我国学者从古语“运筹帷幄之中，决胜千里之外”取“运筹”二字，充分体现了这门学科运心筹谋、策略取胜的精髓。译作“运筹学”运筹学中的“筹”字指的是什么意思？筹划、谋划竹、木等制成的小棍或小片筹码沙盘没有一个统一明确的定义：

《大英百科全书》释义：运筹学是一门应用于管理有组织系统的科学，运筹学为掌管这类系统的人提供决策目标和数量分析的工具《辞海》释义：运筹学主要研究经济活动与军事活动中能用数量来表达有关运用、筹划与管理方面的问题。他根据问题的要求，通过数学的分析与运算，作出综合性的合理安排，以达到较经济较有效的使用人力、物力什么是运筹学？是一门应用学科，它广泛应用现有的科学技术知识和数学方法解决实际中提出的专门问题，为决策者选择最优决策提供量化依据。 系统工程最重要的理论基础之一，在美国有人把运筹学称之为管理科学(ManagementScience)。运筹学所研究的问题，可简单地归结为

“依照给定条件和目标，从众多方案中选择最佳方案”故有人称之为最优化技术（Optimization）。运筹学的历史与发展运筹学思想的出现可以追溯到很早，如“田忌赛马”。齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负一千金。田忌在好友、著名的军事谋略家孙膑的指导下，进行以下安排：齐王 上 中 下 田忌 下 上 中 二、运筹学发展概况

丁谓的皇宫修复工程北宋年间，丁谓负责修复火毁的开封皇宫。

他的施工方案是：先将皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。使用挖出的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；修复工程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。

丁谓将取材、运输及清废用“一沟三用”巧妙地解决了，体现了系统规划的思想。二战以前萌芽二战期间产生五六十年代发展七八十年代成熟近代运筹学发展历程二战前国际上运筹学的思想可追溯到1914年，当时的兰彻斯特提出了军事运筹学的作战模型。1917年，丹麦工程师埃尔朗在研究自动电话系统中通话线路与用户呼叫的数量关系问题时，提出了埃尔朗公式，研究了随机服务系统中的系统排队与系统拥挤问题。存储论的最优批量公式是在20世纪20年代初提出的。二战中

“运作研究(OperationalResearch)小组”:解决复杂的战略和战术问题。如：如何合理运用雷达有效地对付德军的空袭对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。1948年美国麻省理工学院把运筹学作为一门课程介绍；1947年丹齐克(G.B.Danzig)在研究美国空军资源的优化配置时提出了线性规划及其通用解法——

单纯形法;50年代初用电子计算机求解线性规划获得成功;1951年莫尔斯(P.M.Morse)和金博尔(G.E.Kimball)合著的“运筹学方法”一书正式出版。1．从1945年到50年代初，被称为创建时期。特点：从事研究的人数不多，范围较小，人员从军事转为民用。所有这些，标志运筹学这门学科的基本形成。二战后50年代末，美国大约有半数的大公司在自己的经营管理中应用运筹学，如用于制订生产计划、物资储备、资源分配、设备更新等方面的决策。有更多刊物、学会出现。1957年在英国牛律大学召开了第一次国际运筹学会议。1959年成立国际运筹学联合会（IFORS）。

2．50年代初到50年代末，被认为是其成长时期。特点：电子计算机技术的迅速发展，使得运筹学中一些方法如单纯形法、动态规划方法等，得以用来解决实际管理系统中的优化问题．促进了运筹学的推广应用。

3．自60年代以来，是其迅速发展和开始普及的时期。第三代电子数字计算机的出现，促使运筹学得以用来研究一些大的复杂的系统，如城市交通、环境污染、国民经济计划等。发现并挖掘线性规划在经济中应用的意义。其中阿罗、萨谬尔逊、西蒙、多夫曼和胡尔威茨等都获得了诺贝尔奖。特点：运筹学进一步细分为各个分支，专业学术团体的迅速增多，更多期刊的创办，运筹学书籍的大量出版以及更多学校将运筹学课程纳入教学计划之中。

中国于上世纪50年代开始研究运筹学50年代中期由钱学森、许国志等教授由西方引入；1958年提出了图上作业法，山东大学的管梅谷教授提出了“中国邮递员问题”并给出了一个解法。1970年，在华罗庚教授的直接指导下，在全国范围内推广统筹方法和优选法。中国运筹学会于1980年成立，1982年作为正式成员加入了国际运筹学联合会（IFORS）。运筹学已经作为主干课程进入高校之中运筹学的未来发展趋势成熟的学科分支向纵深发展新的研究领域产生与新的技术结合与其他学科的结合加强传统优化观念不断变化国际：ManagementScience,OperationsResearch,Interfaces……国内：运筹学学报，运筹与管理，系统工程学报，系统科学与数学……

国内外主要刊物三、运筹学研究基本特点系统的整体最优化把相互影响的各方面作为一个统一体，从总体利益出发，寻找优化协调方案多学科的配合来自不同学科领域的专家共同配合，探索解决问题的途径模型方法的应用运筹学研究的系统往往不能搬到实验室来，因此需建立问题的数学和模拟模型数学建模四、运筹学的工作流程分析与表述问题弄清要解决的问题明确实现目标分析所处的环境和约束条件取得统计数据资料

对研究的问题进行分析，归纳出决策的目标及相关限制建立数学模型

确定决策变量建立目标函数构造约束方程

模型表达了问题中可控的决策变量、不可控变量、工艺技术条件及目标有效度量之间的相互关系。对问题求解即用数学方法或其它工具对模型求解。对模型和由模型导出的解进行检验将实际问题的数据资料代入模型，找出的精确的或近似的解且要进行检验。用各种手段（数学方法和其它方法）将模型求解，解可以是最优解、次优解、满意解复杂模型求解需用计算机精度由决策者提出检查求解步骤和程序是否有错检查解是否反映现实问题敏感度检验：改变模型及其输入－观察输出建立起对解的有效控制任何模型都有一定的适用范围，模型的解是否有效要首先注意模型是否继续有效，并依据灵敏度分析的方法，确定最优解保持稳定时的参数变化范围。方案的实施只有实施方案后，研究成果才能有收获。依据灵敏度确定参数的变化范围对模型和导出解进行修正解的实施实施最优解分析与表述问题建立模型

对模型和由模型导出的解进行检验建立起对解的有效控制对问题求解

方案实施不满意满意流程图：五、运筹学的主要分支线性规划

如何有效地利用现有人力物力财力完成更多的任务，或在预定的任务目标下，如何耗用最少的人力物力财力去实现。非线性规划上述模型中目标函数或约束条件不全是线性的为非线性规划决策变量目标函数约束条件目标函数或约束条件均为线性时称为线性规划的模型。

主要解决生产计划问题，最优投资问题，合理下料问题等动态规划有些经营管理活动由一系列阶段组成，需在每个阶段依次进行决策。动态规划即研究多阶段决策过程的整体最优化。资源分配问题、生产与存储问题、背包问题、货郎担问题（TSP）等图论与网络把一些研究对象用节点表示，对象间联系用线表示并赋予权重，通过对图与网络性质及优化的研究，解决实际问题。

中国邮递员问题、哥尼斯堡七桥问题、最短路、最大流问题、最小费用流等。整数规划在线性规划的基础上，变量加上整数约束。指派问题等排队论主要研究排队系统中的系统排队和系统拥挤现象，从而评估系统的服务质量。一般会考虑随机因素。博弈论一种用来研究具有对抗局势的模型，参与每一方均有一组策略可供选择，通过博弈论选择对自己最有利的策略。存储论研究在各种供应和需求条件下，应当在什么时间，提出多大的订货指来补充储备，使得用于采购、储存和可能发生的短缺的费用损失的总和为最少等问题。来了客人需要沏茶，为完成这一工作需要四个工序：

一：烧水10分钟

二：刷茶杯2分钟

三：放茶叶1分钟

四：冲茶4分钟完成工作需要多长时间？例1.烧水沏茶六、运筹学典型问题A17分钟B14分钟C12分钟D11分钟E10分钟例2.产品加工问题(线性规划)目标函数约束条件原料供应劳动力时间加工能力非负约束例3.0-1规划问题（整数规划）某公司拟在7个位置(点)Ai

(i=1，2，…，7)建立新厂区。规定：在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点使年利润为最大?解题时先引入0-1变量xi

(=1,2，…，7)要求变量取整数值的线性规划问题称为整数规划问题例4.哥尼斯堡七桥问题(图论)ACBD桥所连接的地区视为点每一座桥视为一条线如何才能在所有桥都恰巧只走一遍的前提下，回到原出发点?A能完成B不能完成例5.最短路问题(动态规划)从A到E要修建一条石油管道，必须在B、C、D处设立加压站。各边上的数为长度，现需要找一条路使总长度最短若最优策略经过某节点，那么这个策略中从某节点到E的一段，必定是该节点到E的所有线路中最短的一条（1）逆序法（2）顺序法例6.洗刷餐具问题(排队论)

一兵营，士兵吃完饭后需要自己洗刷餐具，分为两个步骤，首先在装有洗涤剂的池中洗涤，然后在装有清水的池中漂洗，因人数众多，需要排队，问应该设置多少个洗涤池和清水池？

洗涤剂洗涤剂清水清水排队等候漂洗排队等候洗涤两个小偷甲和乙联手作案，被警方抓住但未获证据。警方将两人分别置于两间房间分开审讯，政策如下：若一人招供但另一人未招，则招供者立即被释放，未招者判入狱10年；若二人都招供，则两人各判刑8年；若两人都不招，则未获证据但因私入民宅各拘留1年，问小偷如何选择？类似的问题：商家价格战、核战争例7.囚徒困境问题(博弈论)

A、B招不招招

-8，-8

0，-10不招

-10，0

-1，-1你的选择：A招供B不招供在一个风雪交加的夜晚,两人驱车相向而来,被一个雪堆所阻,假设铲除这个雪堆使道路通畅需要的代价为c,如果道路通畅则带给每个人的好处量化为b。如果两人一齐动手铲雪,则他们的收益为R=b-c/2;如果只有一人铲雪,虽然两个人都可以回家,但是背叛者逃避了劳动,它的收益为T=b,而合作者的收益为S=b-c;如果两人都选择不合作,两人都被雪堆挡住而无法回家,他们的收益都为P=0。这里假设收益参数满足下面的条件:T>R>S>P

例8.雪堆博弈(snowdriftgame),小鸡博弈(chicken)

A、B

cooperate

defect

cooperateb-c/2b-c

defectb05个海盗ABCDE抢得100枚金币，他们按抽签的顺序依次提方案：首先由1号提出分配方案，然后5人表决，超过半