1
运 筹 学主讲人：叶娟
juanym@163.com
2
什么是运筹学？
主要用数学的方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。
Operation Research,OR
主要研究对象：主要为各种有组织系统的管理问题及其生产经营活动
主要研究方法：定量化和模型化方法
目的：针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能和效益，最终达到系统的最优目标。
3
历史上运筹学的运用
我国：战国时代齐王与田忌赛马
国外,1736年欧拉解决哥尼斯堡七桥问题
4
齐王与田忌赛马
,史记,中有这样一个故事：有一天，齐王要田忌和他赛马，规定每个人从自己的上、中、下三等马中各选一匹来赛；并规定，每次有一匹马来比赛；并约定，每有一匹马取胜可获千两黄金，每有一匹马落后要付千两黄金。当时，齐王的每一等次的马比田忌同样等次的马都要强，因而，如果田忌用自己的上等马与齐王的上等马比，用自己的中等马与齐王的中等马比，用自己的下等马与齐王的下等马比，则田忌要输三次，因而要输黄金三千两。但是结果，田忌没有输，
反而赢了一千两黄金。这是怎么回事呢？
5
在赛马之前，田忌的谋士孙膑给他出了一个主意，
让田忌用自己的下等马去与齐王的上等马比，用自己的上等马与齐王的中等马比，用自己的中等马与齐王的下等马比。田忌的下等马当然会输，但是上等马和中等马都赢了。因而田忌不仅没有输掉黄金三千两，
还赢了黄金一千两。
问题表明，在有双方参加的竞赛或斗争中，策略是很重要的。采用的策略适当，就有可能在似乎一定会失败的情况下取得胜利的结果。
研究这种竞赛策略的数学分支，叫作博奕论，也叫对策论；是运筹学的重要分支。
6
历史上运筹学的运用
我国：战国时代齐王与田忌赛马
国外,1736年欧拉解决哥尼斯堡七桥问题
7
哥尼斯堡七桥问题濒临蓝色的波罗的海，有一座古老而美丽的城市，
叫做哥尼斯堡（今俄罗斯加里宁格勒）。 布勒格尔河的两条支流在这里汇合，然后横贯全城，流入大海。
河心有一个小岛。河水把城市分成了４块，于是，人们建造了７座各具特色的桥，把哥尼斯堡连成一体。
一天又一天，７座桥上走过了无数的行人。不知从什么时候起，脚下的桥梁触发了人们的灵感，一个有趣的问题在居民中传开了,谁能够一次走遍所有的７座桥，而且每座桥都只通过一次？ 这个问题似乎不难，
谁都乐意用它来测试一下自己的智力。可是，谁也没有找到一条这样的路线。连以博学著称的大学教授们，
也感到一筹莫展。“七桥问题”难住了哥尼斯堡的所有居民。哥尼斯堡也因“七桥问题”而出了名。
8
七桥问题的形象描述城市分割成 4个区域：
河的两岸（ A和 B），河中的岛（ C）和两条支流之间的半岛（ D）。七座桥横跨普勒格尔河及其支流，把河岸、半岛和河心岛连接起来。
9
欧拉的解题思路当时的大数学家欧拉没有亲自去哥尼斯堡 测试可能的路线 。事实上，如果沿着所有可能的路线都走一次的话，一共要走 5040次。就算是一天走一次，也需要 13年多的时间，而实际上．欧拉只用了几天的时间就解决了七桥问题。
10
欧拉的解题思路
1、建立模型：
首先把哥尼斯堡的 4个区域分别用点 A,B,C,D
表示，每座连接两个区域的桥用相应两点的连线 a,b、
c,d,e,f,g表示，即把哥尼斯堡七桥的情景转化为一个图。
11
欧拉的解题思路
2、问题转化：在上图中，从任何一点出发，笔不离纸，但又不能重复任何一条边地画出上图，且起点与终点重合，
这样的画法存在吗？（这就是众所周知的,一笔画,游戏）
12
欧拉的解题思路
3、欧拉的结论：
七桥问题中要找的那条路线是不存在的。
网络能否一笔画出来的关键在于这些点。
这些点有两类，如果从一点引出的线是奇数条，就把这个点叫奇点；如果从一点引出的线是偶数条，就把这个点叫偶点。网络中奇点的数是零或二，这个网络就能一笔画出来。
由于七桥问题中的四个点都是奇点，按欧拉的规律，这个网络是一笔画不出来的。
13
欧拉的研究所涉及的学科
图论与网络
拓扑学
14
运筹学学科的形成普遍认为，运筹学作为一门新兴学科起源于二战期间的军事运筹活动。当时英、美都发明和制造了一批新式武器，但如何使用这些武器却远远落后于这些武器的制造。为此，英国军事管理部门召来了一批具有不同学科和专业背景的科学家，在 1940年成立了
,OR”小组。这标志着世界第一次开始正式的运筹学活动。随后，美国也成立了运筹学小组。这些早期的运筹工作，主要是进行战术评价、战术改进、作战计划、战略选择、改进后勤调度和训练计划等方面的研究。不同学科的相互渗透所产生的协同作用，成功的解决了许多重要的问题，为以后运筹学的发展积累了丰富的经验。
15
运筹学的特点运筹学作为一门定量决策科学，利用数学、计算机科学与其它科学的新成就，研究各种系统尤其是经济管理中运行的数量化规律，合理使用与统筹安排人力、物力、财力等资源，为决策者提供有依据的最优方案，以实现最有效的管理并获得满意的经济效益和社会效果，
就其理论与应用意义上归纳，运筹学具有如下一些主要特点：
16
运筹学的特点
1.运筹学研究和解决问题的基础是最优化技术，
并强调系统整体最优。
2,运筹学研究和解决问题的优势是应用各学科交叉的方法，具有综合性。
3.运筹学研究和解决问题的方法具有显著的系统分析特征，其各种方法的运用，几乎都需要建立数学模型和利用计算机进行求解。
4.运筹学研究和解决问题的效果具有连续性。
5.运筹学具有强烈的实践性和应用的广泛性。
17
模型的概念人们在对现实世界进行研究、认识时，
必须对现实世界进行抽象，现实世界才能成为思维的对象。
在解决实际问题时，经常使用一些文字、
数字、符号、公式、图表以及实物，用以描述客观事物的某些特征和内在联系，从而表示或解释某一系统的过程，这就是模型。由此可见，模型是客观世界抽象的描述，能帮助人们认识、分析和解决实际问题。
18
模型的功能
1.模型是实现问题某一主要方面的描述或抽象，比现实本身简单和概括，使人易于认识、理解和操作；
2.模型是由与研究问题有关的主要因素所构成，并表明这些因素的相互关系，从而能够更简明地揭示出问题的本质；
3.通过模型可以进行试验，用以分析和预测所研究事物或系统的特征及性质；
4.利用模型可以在相对短的时间内获得所研究问题的结果；
5.利用模型可以根据过去和现在的信息进行预测，并可用来培训教育人才。
19
模型的分类从建模的方法上分：
1、实物模型
2、数学模型
3、模拟模型从模型中所包含的变量特性分：
1、确定性模型
2、不确定性模型
20
模型的求解
数学的方法
运筹学的推广与计算机的发展分不开，
由于其处理的问题的复杂性，计算机成为求解运筹学模型的有力工具。
21
运筹学的求解步骤
1.提出并形成问题；
2.建立模型；
3.分析并求解模型；
4.检验并评价模型；
5.应用或实施模型的解。
22
运筹学的重要分支数学规划（线性规划、非线性规划、
整数规划、目标规划、动态规划、随机规划等）、图论与网络、排队论（随机服务系统理论）、存贮论、对策论、决策论、维修更新理论、搜索论、可靠性和质量管理等。
23
目录线性规划运输问题图与网络动态规划目标规划
24
运筹学在管理中的典型应用
生产计划问题
运输问题
25
生产计划问题在工厂计划期内要安排生产 A,B两种产品，
已知生产单位产品所需的设备台时及 a,b两种原材料的消耗如下表。
又该工厂每生产一件 A
产品可获利 2元，每生产一件 B产品可获例 3元。
问：如何安排计划使该工厂获利最大？
产品 A 产品 B 资源总数设备 1 2 8台时原材料 a 4 0 16KG
原材料 b 0 4 12KG
单位利润 2 3
26
解,设 A,B两种的产量分别为（决策变量），该问题的数学模型为：
目标函数约束函数
（ Subject To,s.t.）
12max 2 3z x x 12m a x 2 3z x x
12
1
2
12
2 8
4 1 6
4 1 2
,0
xx
x
x
xx
电子表格求解见例 1.xls
27
运输问题两煤矿产的煤运往三个城市销售，各煤矿的供应量、各城市的需求量以及煤矿与城市之间的单位运费如下表。试列出其数学规划模型。
供应量（ t）
90 70 95 200
80 65 75 230
需求量（ t） 100 150 180
1B 2B 3B
1A
2A
28
ijx
1 1 1 2 1 3 2 1 2 2 2 3m i n 9 0 7 0 9 5 8 0 6 5 7 5z x x x x x x
..st
1 1 1 2 1 3
2 1 2 2 2 3
1 1 2 1
1 2 2 2
1 3 2 3
200
230
100
150
180
x x x
x x x
xx
xx
xx
0,1,2 ; 1,2,3,ijx i j
解 设 为第 i煤矿向第 j城市的供应量。
ijx
电子表格求解见例 2.xls
29
请同学们自己动手,尝试为下面的 3个问题建立模型
30
1,某厂为进行生产需采购 A,B两种原材料，单价分别为 70元 /公斤和 50元 /
公斤。现要求购买资金不超过 5000元，
总购买量不少于 80公斤，而 A原材料不少于 20公斤。问如何确定最好的采购方案（即花掉的资金最少 或 购买的总量最大）？
31
2,某纺织厂生产 A,B两种布料，平均生产能力均为 1千米 /小时，工厂正常生产能力是 80小时 /周。又 A布料每千米获利 2500元,B布料每千米获利 1500元。
已知 A,B两种布料每周的市场需求量分别是 70千米和 45千米。试寻找最优的产品组合，使总利润最大。
32
3、某配送公司要将两工厂生产的产品运送到两仓库，工厂 1的产品只能运到仓库 1，数量不限，工厂 2的产品只能运到仓库 2，数量也不限，也可以由工厂将产品运到配送中心，再由配送中心将产品运到仓库，但配送中心一次运入与运出的产品数量有限。该问题的目标是：
如何安排运送，才能使总的运送成本最小？有关数据如下表,
33
至从单位运输成本运出配送中心 仓库 1 仓库 2
工厂 1
工厂 2
配送中心
￥ 300
￥ 200
￥ 600
￥ 200
￥ 800
￥ 400
100单位
120单位每次最多 40单位分配量 80单位 140单位电子表格求解见例 3.xls
34
总结 --本章几个名词
模型：对事物中各因素之间关系的描述和抽象，它应反映事物的多种特征，使人们进行理论思维成为可能。
系统：由相互联系的各个部分组成。
算法：对模型的求解方法。
设计算法 —— 分析算法 —— 编制程序 —— 上机调试 ——
得到解
模拟：原型不能建立数学解析式，用计算机模拟系统行为，采用数据处理的方法求解原型。
运筹学 —— OPERATING RESEARCH。从全局的观点出发，通过建立模型（数学模型或模拟模型），对要求解的问题得到最合理的决策。
运筹学范畴：市场营销、生产计划、库存管理、运输、
财会、人事管理、计算机和信息系统
运筹学分支,LP,NLP、动态规划、多目标规划、图与网络、排队论、存储论、对策论、决策论。
35
本章结束 !
运 筹 学主讲人：叶娟
juanym@163.com
2
什么是运筹学？
主要用数学的方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。
Operation Research,OR
主要研究对象：主要为各种有组织系统的管理问题及其生产经营活动
主要研究方法：定量化和模型化方法
目的：针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能和效益，最终达到系统的最优目标。
3
历史上运筹学的运用
我国：战国时代齐王与田忌赛马
国外,1736年欧拉解决哥尼斯堡七桥问题
4
齐王与田忌赛马
,史记,中有这样一个故事：有一天，齐王要田忌和他赛马，规定每个人从自己的上、中、下三等马中各选一匹来赛；并规定，每次有一匹马来比赛；并约定，每有一匹马取胜可获千两黄金，每有一匹马落后要付千两黄金。当时，齐王的每一等次的马比田忌同样等次的马都要强，因而，如果田忌用自己的上等马与齐王的上等马比，用自己的中等马与齐王的中等马比，用自己的下等马与齐王的下等马比，则田忌要输三次，因而要输黄金三千两。但是结果，田忌没有输，
反而赢了一千两黄金。这是怎么回事呢？
5
在赛马之前，田忌的谋士孙膑给他出了一个主意，
让田忌用自己的下等马去与齐王的上等马比，用自己的上等马与齐王的中等马比，用自己的中等马与齐王的下等马比。田忌的下等马当然会输，但是上等马和中等马都赢了。因而田忌不仅没有输掉黄金三千两，
还赢了黄金一千两。
问题表明，在有双方参加的竞赛或斗争中，策略是很重要的。采用的策略适当，就有可能在似乎一定会失败的情况下取得胜利的结果。
研究这种竞赛策略的数学分支，叫作博奕论，也叫对策论；是运筹学的重要分支。
6
历史上运筹学的运用
我国：战国时代齐王与田忌赛马
国外,1736年欧拉解决哥尼斯堡七桥问题
7
哥尼斯堡七桥问题濒临蓝色的波罗的海，有一座古老而美丽的城市，
叫做哥尼斯堡（今俄罗斯加里宁格勒）。 布勒格尔河的两条支流在这里汇合，然后横贯全城，流入大海。
河心有一个小岛。河水把城市分成了４块，于是，人们建造了７座各具特色的桥，把哥尼斯堡连成一体。
一天又一天，７座桥上走过了无数的行人。不知从什么时候起，脚下的桥梁触发了人们的灵感，一个有趣的问题在居民中传开了,谁能够一次走遍所有的７座桥，而且每座桥都只通过一次？ 这个问题似乎不难，
谁都乐意用它来测试一下自己的智力。可是，谁也没有找到一条这样的路线。连以博学著称的大学教授们，
也感到一筹莫展。“七桥问题”难住了哥尼斯堡的所有居民。哥尼斯堡也因“七桥问题”而出了名。
8
七桥问题的形象描述城市分割成 4个区域：
河的两岸（ A和 B），河中的岛（ C）和两条支流之间的半岛（ D）。七座桥横跨普勒格尔河及其支流，把河岸、半岛和河心岛连接起来。
9
欧拉的解题思路当时的大数学家欧拉没有亲自去哥尼斯堡 测试可能的路线 。事实上，如果沿着所有可能的路线都走一次的话，一共要走 5040次。就算是一天走一次，也需要 13年多的时间，而实际上．欧拉只用了几天的时间就解决了七桥问题。
10
欧拉的解题思路
1、建立模型：
首先把哥尼斯堡的 4个区域分别用点 A,B,C,D
表示，每座连接两个区域的桥用相应两点的连线 a,b、
c,d,e,f,g表示，即把哥尼斯堡七桥的情景转化为一个图。
11
欧拉的解题思路
2、问题转化：在上图中，从任何一点出发，笔不离纸，但又不能重复任何一条边地画出上图，且起点与终点重合，
这样的画法存在吗？（这就是众所周知的,一笔画,游戏）
12
欧拉的解题思路
3、欧拉的结论：
七桥问题中要找的那条路线是不存在的。
网络能否一笔画出来的关键在于这些点。
这些点有两类，如果从一点引出的线是奇数条，就把这个点叫奇点；如果从一点引出的线是偶数条，就把这个点叫偶点。网络中奇点的数是零或二，这个网络就能一笔画出来。
由于七桥问题中的四个点都是奇点，按欧拉的规律，这个网络是一笔画不出来的。
13
欧拉的研究所涉及的学科
图论与网络
拓扑学
14
运筹学学科的形成普遍认为，运筹学作为一门新兴学科起源于二战期间的军事运筹活动。当时英、美都发明和制造了一批新式武器，但如何使用这些武器却远远落后于这些武器的制造。为此，英国军事管理部门召来了一批具有不同学科和专业背景的科学家，在 1940年成立了
,OR”小组。这标志着世界第一次开始正式的运筹学活动。随后，美国也成立了运筹学小组。这些早期的运筹工作，主要是进行战术评价、战术改进、作战计划、战略选择、改进后勤调度和训练计划等方面的研究。不同学科的相互渗透所产生的协同作用，成功的解决了许多重要的问题，为以后运筹学的发展积累了丰富的经验。
15
运筹学的特点运筹学作为一门定量决策科学，利用数学、计算机科学与其它科学的新成就，研究各种系统尤其是经济管理中运行的数量化规律，合理使用与统筹安排人力、物力、财力等资源，为决策者提供有依据的最优方案，以实现最有效的管理并获得满意的经济效益和社会效果，
就其理论与应用意义上归纳，运筹学具有如下一些主要特点：
16
运筹学的特点
1.运筹学研究和解决问题的基础是最优化技术，
并强调系统整体最优。
2,运筹学研究和解决问题的优势是应用各学科交叉的方法，具有综合性。
3.运筹学研究和解决问题的方法具有显著的系统分析特征，其各种方法的运用，几乎都需要建立数学模型和利用计算机进行求解。
4.运筹学研究和解决问题的效果具有连续性。
5.运筹学具有强烈的实践性和应用的广泛性。
17
模型的概念人们在对现实世界进行研究、认识时，
必须对现实世界进行抽象，现实世界才能成为思维的对象。
在解决实际问题时，经常使用一些文字、
数字、符号、公式、图表以及实物，用以描述客观事物的某些特征和内在联系，从而表示或解释某一系统的过程，这就是模型。由此可见，模型是客观世界抽象的描述，能帮助人们认识、分析和解决实际问题。
18
模型的功能
1.模型是实现问题某一主要方面的描述或抽象，比现实本身简单和概括，使人易于认识、理解和操作；
2.模型是由与研究问题有关的主要因素所构成，并表明这些因素的相互关系，从而能够更简明地揭示出问题的本质；
3.通过模型可以进行试验，用以分析和预测所研究事物或系统的特征及性质；
4.利用模型可以在相对短的时间内获得所研究问题的结果；
5.利用模型可以根据过去和现在的信息进行预测，并可用来培训教育人才。
19
模型的分类从建模的方法上分：
1、实物模型
2、数学模型
3、模拟模型从模型中所包含的变量特性分：
1、确定性模型
2、不确定性模型
20
模型的求解
数学的方法
运筹学的推广与计算机的发展分不开，
由于其处理的问题的复杂性，计算机成为求解运筹学模型的有力工具。
21
运筹学的求解步骤
1.提出并形成问题；
2.建立模型；
3.分析并求解模型；
4.检验并评价模型；
5.应用或实施模型的解。
22
运筹学的重要分支数学规划（线性规划、非线性规划、
整数规划、目标规划、动态规划、随机规划等）、图论与网络、排队论（随机服务系统理论）、存贮论、对策论、决策论、维修更新理论、搜索论、可靠性和质量管理等。
23
目录线性规划运输问题图与网络动态规划目标规划
24
运筹学在管理中的典型应用
生产计划问题
运输问题
25
生产计划问题在工厂计划期内要安排生产 A,B两种产品，
已知生产单位产品所需的设备台时及 a,b两种原材料的消耗如下表。
又该工厂每生产一件 A
产品可获利 2元，每生产一件 B产品可获例 3元。
问：如何安排计划使该工厂获利最大？
产品 A 产品 B 资源总数设备 1 2 8台时原材料 a 4 0 16KG
原材料 b 0 4 12KG
单位利润 2 3
26
解,设 A,B两种的产量分别为（决策变量），该问题的数学模型为：
目标函数约束函数
（ Subject To,s.t.）
12max 2 3z x x 12m a x 2 3z x x
12
1
2
12
2 8
4 1 6
4 1 2
,0
xx
x
x
xx
电子表格求解见例 1.xls
27
运输问题两煤矿产的煤运往三个城市销售，各煤矿的供应量、各城市的需求量以及煤矿与城市之间的单位运费如下表。试列出其数学规划模型。
供应量（ t）
90 70 95 200
80 65 75 230
需求量（ t） 100 150 180
1B 2B 3B
1A
2A
28
ijx
1 1 1 2 1 3 2 1 2 2 2 3m i n 9 0 7 0 9 5 8 0 6 5 7 5z x x x x x x
..st
1 1 1 2 1 3
2 1 2 2 2 3
1 1 2 1
1 2 2 2
1 3 2 3
200
230
100
150
180
x x x
x x x
xx
xx
xx
0,1,2 ; 1,2,3,ijx i j
解 设 为第 i煤矿向第 j城市的供应量。
ijx
电子表格求解见例 2.xls
29
请同学们自己动手,尝试为下面的 3个问题建立模型
30
1,某厂为进行生产需采购 A,B两种原材料，单价分别为 70元 /公斤和 50元 /
公斤。现要求购买资金不超过 5000元，
总购买量不少于 80公斤，而 A原材料不少于 20公斤。问如何确定最好的采购方案（即花掉的资金最少 或 购买的总量最大）？
31
2,某纺织厂生产 A,B两种布料，平均生产能力均为 1千米 /小时，工厂正常生产能力是 80小时 /周。又 A布料每千米获利 2500元,B布料每千米获利 1500元。
已知 A,B两种布料每周的市场需求量分别是 70千米和 45千米。试寻找最优的产品组合，使总利润最大。
32
3、某配送公司要将两工厂生产的产品运送到两仓库，工厂 1的产品只能运到仓库 1，数量不限，工厂 2的产品只能运到仓库 2，数量也不限，也可以由工厂将产品运到配送中心，再由配送中心将产品运到仓库，但配送中心一次运入与运出的产品数量有限。该问题的目标是：
如何安排运送，才能使总的运送成本最小？有关数据如下表,
33
至从单位运输成本运出配送中心 仓库 1 仓库 2
工厂 1
工厂 2
配送中心
￥ 300
￥ 200
￥ 600
￥ 200
￥ 800
￥ 400
100单位
120单位每次最多 40单位分配量 80单位 140单位电子表格求解见例 3.xls
34
总结 --本章几个名词
模型：对事物中各因素之间关系的描述和抽象，它应反映事物的多种特征，使人们进行理论思维成为可能。
系统：由相互联系的各个部分组成。
算法：对模型的求解方法。
设计算法 —— 分析算法 —— 编制程序 —— 上机调试 ——
得到解
模拟：原型不能建立数学解析式，用计算机模拟系统行为，采用数据处理的方法求解原型。
运筹学 —— OPERATING RESEARCH。从全局的观点出发，通过建立模型（数学模型或模拟模型），对要求解的问题得到最合理的决策。
运筹学范畴：市场营销、生产计划、库存管理、运输、
财会、人事管理、计算机和信息系统
运筹学分支,LP,NLP、动态规划、多目标规划、图与网络、排队论、存储论、对策论、决策论。
35
本章结束 !
