运筹学绪论
2019/11/21
• 运筹学的概况 • 最优化模型 • 教学计划与方法 • 考试与要求 • 参考文献
绪论
2019/11/21
2
运筹学概况
• 运筹学的由来与发展 • 运筹学的性质与特点 • 运筹学的主要内容 • 运筹学的发展趋势 • 运筹学的学科地位
2019/11/21
3
运筹学的由来与发展
2019/11/21
8
运筹学的学科地位
运筹学
基础理论
应用理论
应用技术
1 在数学学科中的地位 运筹数学
1 在系统科学中的地位 系统工程
1 在管理科学中的地位 管理与运筹学（管理数学）
1 与经济学的关系
问题与方法
1 与工程科学的关系 方法与应用
1 与计算机科学的关系 核心算法与工具
2019/11/21
2019/11/21
12
线性规划（Linear Program）
min 10x1 +12x2 + 8x3 +10x4
s.t. 21x1 + 25x2 + 7x3 +15x4 ≥100
51x1 + 51x2 + 37x3 +15x4 ≥110
18x1 + 32x2 + 21x3 + 6x4 ≥ 200
• 与其他学科的结合加强，共同发展。
– 组合优化 – 最优化方法——使用数学规划（特别是连续优化）解决工程设计
中的问题。 – 博弈论（Game Theory）
• 运筹学的发展进一步依赖于计算机的应用和发展。
– 大容量、高速度的计算机方便了运筹学的应用。 – 计算机学科的发展促进了运筹学的发展。
例如：组合优化，算法图论，算法博弈论。
• 名称的由来
– 最早：来源于英国皇家空军战斗指挥部，称为“Operational Research”。
– 现名：Operations Research
– 我国译名：“运筹学”，取“运筹帷幄”一词，出自《史记》。
• 发展历程
产
萌
生
芽
成
发
熟
展
二
二
五
七
战
战
以
期
前
间
六 十 年 代
八 十 年 代
2019/11/21
询问：怎样配置原材料，才能使得生产单位饲料的费用最小？
2019/11/21
11
建模分析
可控因素：xj——单位饲料中第 j 种原材料的数量。 目标：总费用达到最小 费用函数为：10x1 + 12x2 + 8x3 + 10x4 约束条件：单位饲料中必须保证第 i 种营养成分至少为 bi。
21x1 + 25 x2 + 7x3 +15 x4 ≥100 51x1 + 51x2 + 37 x3 +15 x4 ≥110 18 x1 + 32 x2 + 21x3 + 6x4 ≥ 200
• 线性规划
• 整数规划
• 动态规划
组合优化（Combinatorial Optimization）
• 图和网络优化
• 非线性规划
连续优化（Continuous Optimization）
2019/11/21
7
运筹学的发展趋势
• 成熟的学科分支向纵深发展。 • 新的研究领域产生。
– 如世界问题，国家决策，系统工程等。
4
运筹学的性质与特点
1. 目标：解决各种优化问题。试图系统地研究全局性的优化 问题。
2. 多分支，问题的复杂和多样性。
3. 开放性，不断产生新的问题和学科分支。
4. 源于实践、为了实践、服务于实践，属于应用数学。
5. 交叉学科，涉及经济、管理、数学、工程和系统等多学科。 尤其是近年来，计算机学科的发展大力推动了运筹学的研 究与发展。
14
例3，网络优化模型
例：指派问题（The Assignment Problem） • 实例：现有m个工人，n件任务。工人i完成任务j，可获得
收益wij。 • （约束条件）每个工人只能完成一件任务，每个任务只能
由一个工人完成。 • 询问：如何安排工人完成任务，使总收益最大？
• 解：二分图上的最大匹配问题（Max Matching）。
2019/11/21
5
运筹学的主要内容
1. 线性规划 2. 整数规划 3. 非线性规划 4. 动态规划 5. 多目标规划 6. 图和网络优化
规划论
7. 排队论 8. 对策论（博弈论） 9. 决策论 10. 存储论 11. 可靠性理论 12. 模型论 13. 投入产出分析
2019/11/21
6
组合优化 与 连续优化
2019/11/21
16
课程考核
• 理论方法—笔试 • 应用能力—案例分析 • 计算能力—上机操作
2019/11/21
17
参考教材
• 刁在筠，刘桂真，宿洁，马建华： 《运筹学》。 高等教育出版社， 第1版，1996。 第3版，2007。
2019/11/21
18
参考教材
Christos Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization: Algorithms and Complexity. Dover Publications, Inc., 1998.
2019/11/21
15
教学计划与方法
教学计划 • 数学规划以线性规划和整数规划为教授重点， • 组合优化部分主要讲网络优化， • 而随机优化讲授排队论和对策论， • 其它部分作为选讲内容。 教学方法 • 以授课为主，案例分析与上机实习相结合。 • 而讲课中主要培养用最优化方法解决实际问题的能力。
9
最优化模型
• 模型要素
– 变量(Variables)—可控因素
– 目标(Objective)—优化的动力和依据
– 约束(Constraints)—内部条件和外部约束
建
概
最优
算
灵敏
模
念
性条 件
法
度分 析
• 研究内容 • 实例
2019/11/21
10
例1，线性规划模型
实例：某公司生产混合饲料，该饲料由 3 种营养成分组成。
现有 4 种原材料，每单位原材料可提供营养成分如下表所示。
原料 1 原料 2 原料 3 原料 4
成分 需求
价格
10
12
8
10
成分 1
21
25
7
15
100
成分 2
515137Fra bibliotek15110
成分 3
18
32
21
6
200
在单位饲料中，3 中营养成分的需求分别是 100、110 和 200。
每单位原材料的价格分别是 10、12、8、10。
xi ≥ 0
∀ 1≤i ≤ 4
2019/11/21
13
例2，随机规划模型
特点：约束条件中可以使用概率约束。 例：
min C
[ ] s.t. Pr C - si ≥ vi ≥1 [ ] Pr xi ≥ qi ≥2 [ ] Pr si ≥ smin ≥3
xi ≥ 0, si ≥ 0
1≤i ≤4
2019/11/21