第1章-管理运筹学绪论-重庆三峡学院课件.pptx

1、第第1 1章章 绪论绪论学习指导书学习指导书博客博客 管理运筹学管理运筹学实验指导书实验指导书软件软件 管理运筹学管理运筹学 第第2版版学习学习指导书指导书实验实验指导指导ExcelORM v2.0LINGO v9.0WinQSB v1.0MS project2002Treepan.xla博博客客知识目标知识目标与与技能目标技能目标教材、教辅、软件管理运筹学 第1章 绪论本章主要内容n1.1 运筹学的概念运筹学的概念n1.2 运筹学主要理论的发展路径运筹学主要理论的发展路径n1.3 运筹学在经济管理中的应用运筹学在经济管理中的应用n1.4 运筹学解决问题的步骤运筹学解决问题的步骤n1.5 运筹

2、学的发展趋势运筹学的发展趋势n课时分配课时分配管理运筹学 第1章 绪论1.1 运筹学概念管理运筹学 第1章 绪论运筹学英语全称为运筹学英语全称为Operations Research，简称为，简称为OR，中国科学工作者从，中国科学工作者从史记史记高祖本记高祖本记书中书中“夫运筹于夫运筹于帷幄之中，决胜于千里之外帷幄之中，决胜于千里之外”一语中，摘取一语中，摘取“运筹运筹”作作为为O.R的意译，含义是运用筹划，出谋献策，以策略取的意译，含义是运用筹划，出谋献策，以策略取胜。胜。百科全书运筹学的定义：百科全书运筹学的定义：“运筹学是应用分析、试验、运筹学是应用分析、试验、量化的方法，对经济管理系统

3、中的人力、物力、财力等量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最资源进行统筹安排，为决策者提供有依据的最优方案优方案，实现最有效地管理。实现最有效地管理。”当然，运筹学也适用于其他领域当然，运筹学也适用于其他领域。为表示区别，取名为管理运筹学。为表示区别，取名为管理运筹学。1.2运筹学主要理论发展路径n战国时期田忌赛马战国时期田忌赛马n秦国李冰都江堰水利工程秦国李冰都江堰水利工程n1914年兰彻斯特战斗方程年兰彻斯特战斗方程n1915年美国经济学家哈里斯存储论年美国经济学家哈里斯存储论n1917年丹麦工程师爱尔朗的话务理论年丹麦工程师爱尔朗的话务理

4、论n1928年博弈论正式诞生年博弈论正式诞生n1947年丹捷格单纯形法年丹捷格单纯形法n1947年美籍匈牙利数学家冯年美籍匈牙利数学家冯诺依曼对偶理论诺依曼对偶理论n1951年库恩和图克非线性规划年库恩和图克非线性规划n上世纪上世纪50年代初美国数学家贝尔曼动态规划年代初美国数学家贝尔曼动态规划管理运筹学 第1章 绪论1.2运筹学主要理论发展路径n1954年美国数学家莱基姆对偶单纯形法年美国数学家莱基姆对偶单纯形法n1955年库恩匈牙利法年库恩匈牙利法n1956年年Ford-Fulkerson标号算法标号算法n1958年美国武器局北极星导弹年美国武器局北极星导弹(PERT&CPM)n1959年

5、年Dijkstra标号算法标号算法n1961年美国学者查纳斯和库伯目标规划年美国学者查纳斯和库伯目标规划n1962年中国管梅谷中国邮路问题年中国管梅谷中国邮路问题n1963年柯莫瑞割平面法年柯莫瑞割平面法n1965年达金和兰德年达金和兰德-多伊格分枝定界法多伊格分枝定界法管理运筹学 第1章 绪论1.3 运筹学在管理中的应用n运筹学早期的应用主要集中在军事领域，二次大战之后，运筹学早期的应用主要集中在军事领域，二次大战之后，运筹学的应用转向了民用领域。随着科学技术的发展和生运筹学的应用转向了民用领域。随着科学技术的发展和生产力水平的提高，运筹学的应用呈现出从工程系统日渐向产力水平的提高，运筹学的

6、应用呈现出从工程系统日渐向社会经济系统扩展，得到广泛应用。例如社会经济系统扩展，得到广泛应用。例如:n用排队论帮助人们设置合理的服务设施；用排队论帮助人们设置合理的服务设施；n用线性规划帮助管理者合理排班用线性规划帮助管理者合理排班、混合及下料等、混合及下料等；n由对策论进行具有博弈性质的竞争问题；由对策论进行具有博弈性质的竞争问题；n用用0-10-1规划进行选址等问题的集合覆盖问题；规划进行选址等问题的集合覆盖问题；n用分配问题进行具有指派性质的任务分配；用分配问题进行具有指派性质的任务分配；n用运输问题进行商品流通及非地理性问题的优化；用运输问题进行商品流通及非地理性问题的优化；n由计划评

7、审技术与关键路线法进行项目管理等等。由计划评审技术与关键路线法进行项目管理等等。管理运筹学 第1章 绪论1.4 运筹学解决问题的步骤阐明阐明问题问题建立建立模型模型模型模型求解求解解的解的检验检验方案方案实施实施n运筹学建模解决问题的步骤运筹学建模解决问题的步骤管理运筹学 第1章 绪论1.5 运筹学的发展趋势l运筹学融合系统科学运筹学融合系统科学与社会学、经济学、与社会学、经济学、计算机技术、行为科计算机技术、行为科学、人工智能技术以学、人工智能技术以及其他学科的知识，及其他学科的知识，使得运筹学发展进入使得运筹学发展进入一个崭新阶段一个崭新阶段。运筹数学：运筹数学：主要研究运筹学的算法运筹科

8、学：运筹科学：将运筹学、经济学、计算机技术、行为科学等其他学科等学科融合.运筹学应用：运筹学应用：研究运筹学在管理中的应用管理运筹学 第1章 绪论课时分配4%4%63%63%33%33%理论课理论课(30(30课时课时)习题课(2课时)实验课实验课(16(16课时课时)第1章 结论 1课时第2章 线性规划 4课时第3章 对偶规划 4课时第4章 整数规划 3课时第5章 运输问题 3课时第6章 目标规划 3课时第7章 图与网络模型 5课时第8章 PERT&CPM 2课时13章 决策分析 2课时理论课理论课管理运筹学 第1章 绪论齐王齐王上马上马中马中马下马下马田田忌忌上马上马中马中马下马下马 齐王

9、田忌上中下上-111中-1-11下-1-1-1VS田忌赛马管理运筹学 第1章 绪论都江堰水利工程都江堰，位于四川省都都江堰，位于四川省都江堰市城西，是中国古江堰市城西，是中国古代建设并使用至今的大代建设并使用至今的大型水利工程，被誉为型水利工程，被誉为“世界水利文化的鼻祖世界水利文化的鼻祖.都江堰水利工程是由秦都江堰水利工程是由秦国蜀郡太守李冰指挥、国蜀郡太守李冰指挥、于前于前256年左右修建的，年左右修建的，是全世界迄今为止，年是全世界迄今为止，年代最久、唯一留存、以代最久、唯一留存、以无坝引水为特征的宏大无坝引水为特征的宏大水利工程水利工程.都江堰水利工程将泯江都江堰水利工程将泯江出山口一

10、分为二，由鱼出山口一分为二，由鱼嘴分水堤、飞沙堰嘴分水堤、飞沙堰溢洪溢洪道、道、宝瓶口引水口三大宝瓶口引水口三大主体主体工程及一些附属工程及一些附属工工程构成。科学地解决了程构成。科学地解决了江水自动分流、自动排江水自动分流、自动排沙、控制进水流量等问沙、控制进水流量等问题，消除了水患，使川题，消除了水患，使川西平原成为西平原成为“水旱从人水旱从人”的的“天府之国天府之国”。两千。两千多年来，一直发挥着防多年来，一直发挥着防洪灌溉作用。洪灌溉作用。管理运筹学 第1章 绪论兰彻斯特战斗方程令令x(t)表时刻甲军人数表时刻甲军人数,y(t)表时刻乙军人数：表时刻乙军人数：双方军队减员率与双方军队减

11、员率与对方人对方人数数成正比，即：成正比，即：其中其中a 0，b 0均为常数均为常数。两式相除得：两式相除得：积分得积分得：c0乙军胜，乙军胜，c0甲军胜。甲军胜。问题描述：问题描述：两军对垒，现甲军有两军对垒，现甲军有m个士兵，乙军个士兵，乙军有有n个士兵，试计算战斗过程中双方个士兵，试计算战斗过程中双方的死亡情况以及最后哪一方失败？的死亡情况以及最后哪一方失败？在第一次世界大战期间，在第一次世界大战期间，FW兰彻兰彻斯特投身于作战模型的研究，他建立斯特投身于作战模型的研究，他建立了一些可以从中得到交战结果的数学了一些可以从中得到交战结果的数学模型，并得到了一个很重要的模型，并得到了一个很重

12、要的“兰彻兰彻斯特平方定律斯特平方定律”：作战部队的实力同：作战部队的实力同投入战斗的战士人数的平方成正比。投入战斗的战士人数的平方成正比。/dxdtaydydtbx 22aybxcbxdxaydy管理运筹学 第1章 绪论存贮论管理运筹学 第1章 绪论存贮论又称库存理论，是运筹学中发展较早的分支。早在存贮论又称库存理论，是运筹学中发展较早的分支。早在1915年，哈李斯针对银行货币的储备问题进行了详细的研究，建立年，哈李斯针对银行货币的储备问题进行了详细的研究，建立了一个确定性的存贮费用模型，并求得了最佳批量公式，后来了一个确定性的存贮费用模型，并求得了最佳批量公式，后来人们称这个公式为经济订购

13、批量公式（简称为人们称这个公式为经济订购批量公式（简称为EOQ公式）。这公式）。这是属于存贮论的早期工作。存贮论真正作为一门理论发展起来是属于存贮论的早期工作。存贮论真正作为一门理论发展起来还是在上世纪还是在上世纪50年代。年代。1958年威汀年威汀 发表了发表了存贮管理的理论存贮管理的理论一书，随后阿罗等发表了一书，随后阿罗等发表了存贮和生产的数学理论研究存贮和生产的数学理论研究，毛，毛恩在恩在1959年写了年写了存贮理论存贮理论。此后，存贮论成了运筹学中的。此后，存贮论成了运筹学中的一个独立的分支，有关学者相继对随机或非平稳需求的存贮模一个独立的分支，有关学者相继对随机或非平稳需求的存贮模

14、型进行了广泛深入的研究。型进行了广泛深入的研究。排队论管理运筹学 第1章 绪论1910年丹麦电话工程师年丹麦电话工程师A.K.埃尔朗在解决自动电话设计问题时埃尔朗在解决自动电话设计问题时建立了电话统计平衡模型，人们称为话务理论。建立了电话统计平衡模型，人们称为话务理论。20世纪世纪30年代年代苏联数学家苏联数学家.欣钦把处于统计平衡的电话呼叫流称为最简单欣钦把处于统计平衡的电话呼叫流称为最简单流，用数学方法深入地分析了电话呼叫的本征特性，促进了排流，用数学方法深入地分析了电话呼叫的本征特性，促进了排队论的研究。队论的研究。20世纪世纪50年代初，美国数学家关于生灭过程的研年代初，美国数学家关于

15、生灭过程的研究、英国数学家究、英国数学家D.G.肯德尔提出嵌入马尔可夫链理论，以及对肯德尔提出嵌入马尔可夫链理论，以及对排队队型的分类方法，为排队论奠定了理论基础。在这以后，排队队型的分类方法，为排队论奠定了理论基础。在这以后，L.塔卡奇等人又将组合方法引进排队论，使它更能适应各种类塔卡奇等人又将组合方法引进排队论，使它更能适应各种类型的排队问题。型的排队问题。20世纪世纪70年代以来，人们开始研究排队网络和年代以来，人们开始研究排队网络和复杂排队问题的渐近解等，成为研究现代排队论的新趋势。复杂排队问题的渐近解等，成为研究现代排队论的新趋势。博弈论管理运筹学 第1章 绪论博弈论（博弈论（Gam

16、e Theory），亦名），亦名“对策论对策论”、“赛局理论赛局理论”，属应用，属应用数学的一个分支，数学的一个分支，博弈论已经成为经济学的标准分析工具之一。目博弈论已经成为经济学的标准分析工具之一。目前在生物学、经济学、国际关系、计算机科学、政治学、军事战略和前在生物学、经济学、国际关系、计算机科学、政治学、军事战略和其他很多学科都有广泛的应用。其他很多学科都有广泛的应用。近代对于博弈论的研究，开始于策墨洛，波雷尔及冯近代对于博弈论的研究，开始于策墨洛，波雷尔及冯诺伊曼。诺伊曼。1928年，冯年，冯诺依曼证明了博弈论的基本原理，从而宣告了博弈论的诺依曼证明了博弈论的基本原理，从而宣告了博弈论

17、的正式诞生。正式诞生。19501951年，约翰年，约翰福布斯福布斯纳什利用不动点定理证明了均衡点的存纳什利用不动点定理证明了均衡点的存在，为博弈论的一般化奠定了坚实的基础。在，为博弈论的一般化奠定了坚实的基础。单纯形法n单纯形法是一种直接、单纯形法是一种直接、快速的搜索最优值方法，快速的搜索最优值方法，其优点是对目标函数的其优点是对目标函数的解析性没有要求，收敛解析性没有要求，收敛速度快，适用面较广。速度快，适用面较广。美国数学家美国数学家George Dantzig于于1947年首先提年首先提出的。出的。管理运筹学 第1章 绪论对偶理论n研究线性规划中原始问题与对偶研究线性规划中原始问题与对

18、偶问题之间关系的理论。问题之间关系的理论。在线性规在线性规划早期发展中最重要的发现是对划早期发展中最重要的发现是对偶问题，即每一个线性规划问题偶问题，即每一个线性规划问题（称为原始问题）有一个与它对（称为原始问题）有一个与它对应的对偶线性规划问题（称为对应的对偶线性规划问题（称为对偶问题）。偶问题）。1928年美籍匈牙利年美籍匈牙利数学家数学家 冯冯诺伊曼在研究对策论已诺伊曼在研究对策论已发现线性规划与对策论之间存在发现线性规划与对策论之间存在着密切的联系。两零和对策可表着密切的联系。两零和对策可表达成线性规划的原始问题和对偶达成线性规划的原始问题和对偶问题。问题。约翰冯诺伊曼John von

19、 Neumann19031957）管理运筹学 第1章 绪论非线性规划1951年年Harold W.Kuhn(库恩库恩)和和Albert W.Tucker(塔克塔克)发表发表的关于最优性条件的关于最优性条件(后来称为后来称为库恩塔克条件库恩塔克条件)的论文是非的论文是非线性规划正式诞生的一个重线性规划正式诞生的一个重要标志。要标志。50年代末到年代末到60年代年代末出现了许多解非线性规划末出现了许多解非线性规划问题的有效的算法，问题的有效的算法，70年代年代又得到进一步的发展。非线又得到进一步的发展。非线性规划在工程、管理、经济、性规划在工程、管理、经济、科研、军事等方面都有广泛科研、军事等方面

20、都有广泛的应用，为最优设计提供了的应用，为最优设计提供了有力的工具。有力的工具。Harold W.KuhnAlbert W.Tucker管理运筹学 第1章 绪论动态规划n动态规划是研究多段（多步）动态规划是研究多段（多步）决策过程最优化问题的一种决策过程最优化问题的一种数学方法，是最优控制和运数学方法，是最优控制和运筹学的重要数学工具。他将筹学的重要数学工具。他将多阶段决策问题转化成一系多阶段决策问题转化成一系列比较简单的最优化问题。列比较简单的最优化问题。20世纪世纪50年代初年代初,美国数学美国数学家家R.贝尔曼首先提出。贝尔曼首先提出。管理运筹学 第1章 绪论对偶单纯形法n对偶单纯形法（

21、对偶单纯形法（Dual Simplex Method），于），于1954年美国数学家年美国数学家C.莱姆基提出。莱姆基提出。n单纯形法是从原始问题的一个可行解通过迭代转到单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。另一个可行解，直到检验数满足最优性条件为止。n对偶单纯形法对偶单纯形法则在则在迭代过程中始终保持基解迭代过程中始终保持基解的的最优最优性性，而使不可行性逐步消失而使不可行性逐步消失。因此要求初始单纯形。因此要求初始单纯形表的所有检验数非负。因此很少单独使用。表的所有检验数非负。因此很少单独使用。管理运筹学 第1章 绪论匈牙利法匈牙利法（匈牙

22、利法（Hungarian method）是求解极小化指派）是求解极小化指派问题的一种方法，这种方法问题的一种方法，这种方法最初由库恩（最初由库恩（Harold W.Kuhn）提出，后经改进而）提出，后经改进而形成，解法基于匈牙利数学形成，解法基于匈牙利数学家考尼格家考尼格D.Konig给出的一给出的一个定理而得名。个定理而得名。Harold W.Kuhn管理运筹学 第1章 绪论Ford-Fulkerson标号算法nT.E.哈里斯于哈里斯于1955年研究年研究铁路网的最大通过能力时铁路网的最大通过能力时,首先提出在一个给定的网首先提出在一个给定的网络上寻求某两点间的最大络上寻求某两点间的最大运输

23、量问题。运输量问题。1956年，年，L.R.Ford和和D.R.Fulkerson给出了算法，从而建立了给出了算法，从而建立了网络流理论。网络流理论。管理运筹学 第1章 绪论计划评审技术与关键路线法（PERT&CPM）nPERT：计划评核术（：计划评核术（program evaluation and review technique）n美国海军为了北极星飞弹计划而发展美国海军为了北极星飞弹计划而发展n该计划的作业几乎都是从事同有执行这的作业该计划的作业几乎都是从事同有执行这的作业n主要是处理上非确定时间之作业所构成的项目主要是处理上非确定时间之作业所构成的项目nCPM：要径法（：要径法（cri

24、tical path method）n杜邦公司为了安排维修停机等生产作业所发展杜邦公司为了安排维修停机等生产作业所发展n这些作业由于经常执行所以时间是可以正确预估的这些作业由于经常执行所以时间是可以正确预估的n目前两者有许多共通的方法，因此可用目前两者有许多共通的方法，因此可用PERT&CPM代代表表管理运筹学 第1章 绪论Dijkstra标号算法n戴杰克斯特拉算法戴杰克斯特拉算法（Dijkstras algorithm）是由）是由荷兰计算机科学家艾兹赫荷兰计算机科学家艾兹赫尔尔戴克斯特拉提出。是典型戴克斯特拉提出。是典型的单源最短路径算法，用于的单源最短路径算法，用于计算一个节点到其他所有节

25、计算一个节点到其他所有节点的最短路径。主要特点是点的最短路径。主要特点是以起始点为中心向外层层扩以起始点为中心向外层层扩展，直到扩展到终点为止。展，直到扩展到终点为止。Edsger Wybe Dijkstra(1930-2002)管理运筹学 第1章 绪论目标规划n目标规划（目标规划（Goal programming）目标规划是目标规划是线性规划的一种特殊应用，能线性规划的一种特殊应用，能够处理单个主目标与多个目标够处理单个主目标与多个目标并存，以及多个主目标与多个并存，以及多个主目标与多个次目标并存的问题。由美国学次目标并存的问题。由美国学者查恩斯（者查恩斯（A.Charnes）和库）和库伯（

26、伯（W.W.Cooper）在）在1961年年首次提出。首次提出。A.Charnes管理运筹学 第1章 绪论中国邮路问题n中国邮路问题中国邮路问题(Chinese postman problem)：图论中一：图论中一个有重要理论意义和广泛应用背个有重要理论意义和广泛应用背景的问题，它来源于下述实际问景的问题，它来源于下述实际问题：一个邮递员如何选择一条道题：一个邮递员如何选择一条道路，是他能从邮局出发，走遍他路，是他能从邮局出发，走遍他负责送信的所有街道，最后回到负责送信的所有街道，最后回到邮局，并且所走的路程为最短。邮局，并且所走的路程为最短。n我国著名数学家管梅谷教授在我国著名数学家管梅谷教

27、授在1962年提出。年提出。管理运筹学 第1章 绪论割平面法割平面法是割平面法是1958年由美国学者高莫利年由美国学者高莫利(R.E.GoMory)提出的求解全整数规划的一提出的求解全整数规划的一种比较简单的方法。其基本思想是先不考种比较简单的方法。其基本思想是先不考虑变量的取整约束，用单纯形法求解相应虑变量的取整约束，用单纯形法求解相应的线性规划。如果所得的最优解为整数解，的线性规划。如果所得的最优解为整数解，那么它也是原整数规划问题的最优解；如那么它也是原整数规划问题的最优解；如果最优解不是整数解，那么用一张平面果最优解不是整数解，那么用一张平面(不不一定垂直于某个坐标轴一定垂直于某个坐标

28、轴)，将含有最优解的，将含有最优解的点但不含任何整数可行解的那一部分可行点但不含任何整数可行解的那一部分可行域切割掉，再在这个新的整数规划的基础域切割掉，再在这个新的整数规划的基础上增加适当的线性不等式约束，直至求得上增加适当的线性不等式约束，直至求得最优整数解为止。最优整数解为止。R.E.GoMory管理运筹学 第1章 绪论分枝定界法n分枝定界法可用于解纯整数或混合的整分枝定界法可用于解纯整数或混合的整数规划问题，在二十世纪六十年代初由数规划问题，在二十世纪六十年代初由Land Doig和和Dakin等人提出。等人提出。n其基本思想是先不考虑变量的取整约束，其基本思想是先不考虑变量的取整约束，用单纯形法求解相应的线性规划。如果用单纯形法求解相应的线性规划。如果所得的最优解为整数解，那么它也是原所得的最优解为整数解，那么它也是原整数规划问题的最优解；如果最优解不整数规划问题的最优解；如果最优解不是整数，则任取一个取分数值的变量将是整数，则任取一个取分数值的变量将原整数规划分成两枝，将两个平行平面原整数规划分成两枝，将两个平行平面之间的不合有整数解的那一部分可行域之间的不合有整数解的那一部分可行域去掉，以缩小可行域。去掉，以缩小可行域。管理运筹学 第1章 绪论