运筹学导论第八版--1绪论

In our classes, all the mobile phones should be switched off !
肖鹏
E-mail:
办公室：逸夫楼813
决胜千里之外 运筹帷幄之中
绪论
Introduction
运筹学发展简介 运筹学性质、特点与地位 运筹学工作步骤 运筹学的模型 运筹学的应用 运筹学的主要内容
❖人事管理：对人员的需求和使用的预测， 确定人员编制、人才的开发即培训、人员 合理分配，主要是各种指派。建立人才评 价体系、工资和津贴的确定等
运筹学的应用
❖财务和会计：这涉及预算、贷款、成本 分析、定价、投资、证券及现金管理等
❖设备维修、更新，项目选择、评价，工 程优化设计与管理等
❖城市管理：各种紧急服务系统的设计和 运用；城市垃圾的清扫、搬运和处理；城 市供水和污水系统的规划等。
运筹学的模型
• 模型要素
变量—可控因素 目标—优化的动力和依据 约束—内部条件和外部约束
•模型的基本形式
形象模型 模拟模型 符号或数学模型
运筹学的应用
❖早期的运筹学主要用于军事,二战后,运 筹学的应用逐渐转向民用，1957年开始用 于建筑业和纺织业.1958年开始用于交通运 输、工业、农业、水利建设、邮电等各个 领域。这里介绍几种最简单的应用。
•系统与整体性
--从全局考察问题
•应用性
--源于实践、为了实践、服务于实践
运筹学性质、特点与地位
•跨学科性
--涉及经济、管理、数学、工程和 系统等 多学科
•开放性
--不断产生新的问题和学科分支
•多分支
--问题的复杂和多样性
运筹学性质、特点与地位
运筹学
基础理论

3．注意到了工作、工人和环境之间的相互影响.
27
运筹学发展简史
Henry Ford，1863 - 1947，创造了第一条流水生 产线——汽车流水线，从而提高了整个企业的生 产效率，使成本明显降低. • 福特为了利于企业向大生产发展，进行了多方面 的标准化工作，包括：产品系列化，零件规格化，
工厂专业化，机器及工具专用化，作业专门化.
1999
2003
2006
2010
2014
2
Operations Research
Chapter 1. Introduction
第一章. 绪论
Chapter 1. Introduction
3
What is Operations Research?
Chapter 1. Introduction
4
交通控制问题
问题的确定
控制
分析问题
建立模型 软件求解 实施方案 确定解决方案 结果分析
Chapter 1. Introduction
37
运筹学的模型方法
模型的概念
模型是一件实际事物或情况的代表或抽 象。实际事物是A，若B能够真实地描述 A，则称B为A的模型
运筹学模型的一般形式
F ( X , f ( x1 , x 2 ,..., x m ; 1 , 2 ,..., n )
某些分支的研究达到当时国际水平。
35
What is Data, Model and Decision?
管理者
信息提供
模型
结论 决策
反馈
结果
执行
管理者在组织内制定决策，数据、模型与 决策的目的是在科学、符合逻辑和合理的 基础上制定决策

田忌赛马
齐王要与大臣田忌赛马，双方各出上、 齐王要与大臣田忌赛马，双方各出上、中、下马 各一匹，对局三次，每次胜负1000 1000金 各一匹，对局三次，每次胜负1000金。田忌在 好友、著名的军事谋略家孙膑的指导下， 好友、著名的军事谋略家孙膑的指导下，做以下 安排： 安排： 齐王 上 中 下 田忌 下 上 中 最终净胜一局，赢得千金。 最终净胜一局，赢得千金。
运筹学形成于20 世纪 年代 运筹学形成于 20世纪 30年代（ 第二次 世纪30 年代（
世界大战期间 ） 战斗机搜索潜艇（40年代） 年代） 战斗机搜索潜艇（40年代 军用物质运输（40年代 年代） 军用物质运输（40年代） 苏联著名数学家康托洛维奇：“生产组织与计划中的 苏联著名数学家康托洛维奇： 数学方” 数学方法”中提出合理调配和使用资源以便充分发挥 其效用的研究中所提出的新的数学方法和理论。 其效用的研究中所提出的新的数学方法和理论。
系统工程应用领域： 系统工程应用领域： 宏观经济： 宏观经济： 能源： 能源总体规划、 运输、 能源 ： 能源总体规划 、 运输 、 产 供销： 石油如何分配、 水电、 供销 ： 石油如何分配 、 水电 、 核 电发展规划。 电发展规划。 军事： 武器论证、 反坦克系统、 军事 ： 武器论证 、 反坦克系统 、 高炮系统、 坦克系统、 作战模拟、 高炮系统 、 坦克系统 、 作战模拟 、 陆海空军作战。 陆海空军作战。 农业：农业规划、农业施肥。 农业：农业规划、农业施肥。
交通：全国交通网、城市交通网、 交通：全国交通网、城市交通网、 出租车、公交路线规划、港口选址、 出租车、公交路线规划、港口选址、 驳运、 河运（ 航道堵塞） 驳运 、 河运 （ 航道堵塞 ） 、 空运 空中交通管制ATC） （空中交通管制ATC）、物流 工业企业：企业发展规划、 工业企业：企业发展规划、生产计 库存问题、新设备可行性、 划、库存问题、新设备可行性、下 料问题、全面质量管理、投入产出、 料问题、全面质量管理、投入产出、 生产调度问题、投资问题。 生产调度问题、投资问题。

16
m in z x1 x2 x3 x4 x5 x7 x8
s t x 1 x 2 （1 街 道 A ） x 2 x 3 （1 街 道 B ） 1
街道A
2
街道B
3
街道G 街道H 街道I 街道J 街道K
x 4 x 5 （1 街 道 C ）
x 7 x 8 （1 街 道 D ）
整数线性规划的一种特殊情形是0-1规划，它的变量取 值仅限于0或1。指派问题就是一个0-1规划问题。
运筹学导论第八版整数线性规划
9
8.1 应用实例介绍
1. 资本预算
在个人项目中投资中，既要考虑这些在个人项目中投资的收益， 又要考虑有限的总预算。
例 在一个3年的规划周期内，有5个项目可供选择。下表给出
发射台
覆盖社区
1
1，2
2
2，3，5
3
1，7，9，10
4
4，6，8，9
5
6，7，9，11
6
5，7，10，12，14
7
12，13，14，15
各个社区人口数目
建造费用(百万) 3.6 2.3 4.1 3.15 2.8 2.65 3.1
社区
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
本例还可以用图解法来说明
图中(+) 表示可行整数解。 凑整的(5，0) 不在可行域内，
而C点又不合于条件⑤。
目标函数z的等值线必须向原点平行移动，直到首次遇到带“+”
号B点(x1=4，x2=1)为止。此时，z值就由z=96变到z=90，Δz=9690=6表示利润的降低，这是由于变量的不可分性(装箱)所引起的。
很容易求得最优解为：x1=4.8，x2=0，max z=96

18
1 定义问题 2 识别被选方案 3 制定分析这些被选方案所用的准则 4 评价备选方案 5 选择一个方案 6 决策的实施 7 评价结果，检验是否达到了预期的效果
1.2 定量分析与制定决策
19
决策：决策是人们对未来的行动目标及其实现方案进行合理抉择 的分析、判断过程，它是管理活动的核心。
劳动力 设备 原材料 单位产品利 润（元）
产品A
9 4 3 70
产品B
4 5 10 120
资源限制
360工时 200台时 300公斤
29
生产计划问题
问题：如何安排生产计划，使得获利最多？ 步骤：
1、确定决策变量：设生产A产品x1kg,B产品x2kg
2、确定目标函数：maxZ=70X1+120X2 3、确定约束条件人力约束 9X1+4X2≤360
Max f(xi,yj,uk) G(xi,yj,uk)≤(=≥)0
一些常见模型：
24
抽样检验的样本 飞机模型 舰船模型 磁场悬浮列车模型——上交大研制 建筑模型 葛洲坝水电工程模型 广石化总厂模型 炼油工艺模型 城市规划模型
一些常见模型：
25ቤተ መጻሕፍቲ ባይዱ
用网络图形来描述系统的组成部分以及元素间的相互关系
商船数目M
20
30
交战次数
8
11
护航舰数C
7
7
潜艇数目N
7
5
每次交战商船沉 5
6
没数K
商船损失率K/M 0.25 0.2
39 48
13 7
6
7
6
5
6
5
0.15 0.1
1.0 运筹学的涵义
17

运筹学编写组.运筹学.清华大学出版社 胡运权.运筹学教程.清华大学出版社 杜纲.管理科学基础.天津大学出版社 邓梁成.运筹学的原理和方法.华中科技大学 中国工程项目管理知识体系.建工社 其他：线性代数、管理学及部分杂志
➢ 设备维修和更新 ➢ 项目评价和选择 ➢ 工程优化设计
➢ 计算机和信息系 统
➢ 城市管理 ➢ 发展战略
五、教学及考试说明
➢ 以课本为主教学 ➢ 必要的习题（30～40题） ➢ 考试：采用闭卷 ➢ 平时成绩30％；考试成绩占70％
六、教材和参考书
➢ 教材： ➢ 胡云权.运筹学教程（第三版）.清华大学出版社 ➢ 宋学峰.运筹学.东南大学出版社 ➢ 参考书：
➢ 60年代，相继在工业、农业、经济和社会问题各 领域都得到应用。
➢ 理论飞快发展，形成许多分支：数学规划、图与 网络、排队论、存储论、对策论、决策论等。
➢ 1959年成立国际运筹学联合会。我国1980年成 立运筹学会，1982年加入国际运筹学联合会。
四、运筹学解决问题的思路
➢ 提出问题——用自然语言描述问题。 ➢ 建立数学模型——用变量、函数、方程描述问
题。
➢ 求解——主要用数学方法求出模型的最优解、 次优解、满意解，复杂模型求解要用计算机。
➢ 解的检验——检查模型和求解步骤有无错误， 检查解是否反映现实问题。
➢ 决策实施——决策者根据自己的经验和偏好， 对方案进行选择和修改，作出实施的决定。
五、运筹学的运用
➢ 生产计划 ➢ 市场销售 ➢ 资本运营 ➢ 库存管理 ➢ 运输问题 ➢ 财政和会计 ➢ 人事管理
——近代一些运筹学工作者
一、什么是运筹学
➢ 3、运筹学的三大来源 1）军事
两次世界大战期间的军事运筹研究 2）管理

实用举例
某公司通过市场调研，决定生产高中档新型拉杆箱。 某分销商决定买进该公司3个月内的全部产品。拉杆箱生 产需经过原材料剪裁、缝合、定型、检验和包装4过程。
通过分析生产过程，得出：生产中档拉杆箱需要用 7/10小时剪裁、5/10小时缝合、1小时定型、1/10小时检 验包装；生产高档拉杆箱则需用1小时剪裁、5/6小时缝合、 2/3小时定型、1/4小时检验包装。由于公司生产能力有限， 3月内各部的最大生产时间为剪裁部630小时、缝合部600 小时、定型部708小时、检验包装部135小时。
D {x | Ax b, x (x1,, xi ,, xn ) 0}
是凸集（凸多面体）。
引理2.1：线性规划的可行解 x (x1 ,, xn )T 为基本可行解的 充分必要条件是x的正分量所对应的系数列向量是线性无关的， 即每个正分量都是一个基变量。
定理2.2：线性规划问题的基本可行解x对应于可行域的顶点
通过分析生产过程，得出：生产中档拉杆箱需要用
7/10小时可剪裁以、通5/1过0小线时性缝合规、划1小求时定解型！、1/10小时
检验包装；生产高档拉杆箱则需用1小时剪裁、5/6小时 缝合、2/3小时定型、1/4小时检验包装。由于公司生产 能力有限，3月内各部的最大生产时间为剪裁部630小时、 缝合部600小时、定型部708小时、检验包装部135小时。
x2
L1：x1=6 L3：2x1+3x2=18
B 可行域
L2：x2=4 最优解
x1
4x1+3x2
解的特殊情况——解的特殊情况——无界解
线性规划的基本性质
若线性规划有最 优解，则最优解必在可 行域的顶点上达到。
X
可行域内部的点 • 可行解? 是 • 最优解? 不

非可控输入既可以是非常明确的，也可以是不确定的 、变化的。
如果一个模型的非可控输入都是已知的、不可变的， 这样的模型称为确定模型。
如果一个模型的非可控输入是不确定的、变化的，这 样的模型就称为随机模型或概率模型。
本书主要研究确定型数学模型。
1.2 运筹学问题的求解过程
了解模型的相关概念之后，下一个问题就是如何将一 个现实问题转化为数学模型，也就是建模过程。既然运筹 学模型的几个要素是：目标函数，约束条件（包括自然约 束和强加约束），决策变量。那么根据我们要解决的问题 ，只要我们经常问自己下面这些问题，一个模型的框架是 不难建立的。
1.2 运筹学问题的求解过程
1.2.1 从现实系统到理论模型：模型建立
模型是现实世界的抽象化反映。运筹学的实质在于建 立和使用模型来解决实际问题。尽管模型的具体结构和形 式总是与要解决的问题相联系，但在这里将抛弃模型在外 表上的差别，从最广泛的角度抽象出它们的共性。模型在 某种意义上说是客观事物的简化与抽象，是研究者经过思 维抽象后用文字、图表、符号、关系式以及实体模样对客 观事物的描述。
第1章 绪论
“运筹于帷幄之中，决胜于千里之外”。运筹学 将科学的方法、技术和工具应用到经济管理、工程设计 等领域，以便为人们提供最佳的解决方案。
在这一章里，首先介绍运筹学的基本概况，包括 运筹学的历史和发展，运筹学的性质和特点，运筹学研 究的主要内容和以后的发展趋势。然后从运筹学问题解 决过程的角度，依次介绍建模、求解和实际应用时应该 注意的一些问题，使初学者对运筹学概念和方法有初步 的认识。
我们需要什么目标？ 通过调节哪些因素可以使得我们达到这一目标？ 调节的因素是变动的吗? 要与实际情况相符合有什么 限制条件吗？ 在实现目标的过程中，有哪些约束条件？ 这样建立的模型是相对完备的吗？

第一章 绪论
§1 决策、定量分析与管理运筹学 §2 运筹学的分支 §3 运筹学在工商管理中的应用 §4 学习运筹学必须使用相应的计算机
软件，必须注重于学以致用的原则
1
第一章 绪论
运筹学（Operational Research) 直译为“运作研究”。
➢ 定义：运筹学是应用分析、试验、量化的方法，对经济 管理系统中的人力、物力、财力等资源进行统筹安排， 为决策者提供有依据的最优方案，以实现最有效的管理。
2
§1 决策、定量分析与管理运筹学
问题解决的过程：
1）认清问题；
2）找出一些可供选择的方案；
决 策
3）确定目标或评估方案的标准；
4）评估各个方案：解的检验、敏性分析等；
5）选出一个最优的方案：决策；
6）执行此方案：回到实践中；
7）进行后评估：考察问题是否得到完满解决；
1）2）3）：形成问题； 4）5）：分析问题：定性分析与定量分析。构成决策。
• 本书附有运筹学教学软件，使用方法很简单。必须 尽快学会使用这个运筹学教学软件，并借助它来学 好本课程。
• 虽然教材附带的软件“管理运筹学2.5”可以解决书 上的绝大部分习题，但是，这些习题的计算方法依 然是重点，必须掌握。
11
3
• 线性规划
§2 运筹学的分支
• 对策论
• 整数线性规划 • 目标规划 • 图与网络模型 • 存储论
• 排序与统筹方法 • 决策分析 • 动态规划
• 排队论
• 预测
*** 随机规划、模糊规划等
4
§3 运筹学在工商管理中的应用
• 生产计划：使用运筹学方法从总体上确定适应需求 的生产、 贮存和劳动力安排等计划，追求利润最 大化和成本最小化。