组运筹学课程设计PPT演示文稿

运筹学的发展历程
80%
起源
运筹学起源于二战时期的军事战 略和资源优化问题，当时称为“ 运作研究”。
100%
发展
随着数学方法和计算机技术的进 步，运筹学逐渐发展成为一个独 立的学科领域。
80%
应用
现代运筹学已经广泛应用于各个 领域，如物流、金融、医疗、交 通等，成为决策支持的重要工具 。
02
线性规划
模型
多目标规划的数学模型通常由决策变 量、目标函数和约束条件组成。目标 函数表示需要优化的多个目标，约束 条件包括等式约束和不等式约束。
多目标规划的求解方法
权重法
给定一组权重因子，将多目标问题转化为单目标问题，通 过求解单目标问题的最优解得到多目标问题的近似解。
层次分析法
将多目标问题分解为若干个子问题，分别求解子问题的最优解 ，然后根据子问题的最优解逐步逼近多目标问题的最优解。
在需要时进行查找。
02
自顶向下法
从原问题开始，逐步将问题分解为更小的子问题，并求解子问题直到达
到基本的最小单元。这种方法需要在递归过程中不断更新当前问题的最
优解。
03
迭代法
通过迭代的方式不断逼近最优解，每次迭代中根据当前最优解和状态转
移方程更新状态，直到达到终止条件。这种方法需要设计适当的迭代算
法和终止条件。
线性规划的求解方法
01
02
03
04
单纯形法
单纯形法是线性规划最常用的 求解方法，它通过不断迭代和 变换，寻找最优解。
初始解的确定
在求解线性规划问题时，需要 先确定一个初始解，然后在此 基础上进行迭代和优化。
迭代过程
在单纯形法中，迭代过程包括 检验、换基和迭代三个步骤。

2x3 4 3x3 6
x1 0, x2 0, x3取值无约束
解： z令 z,x1 x1,x3x3 x3 ,其x中 3 ， x3 0， 同时引入 x4和 松剩 弛余 变 x5,标 变 量准 量形式
m z x 1 a 2 x 2 x 3 x 3 3 x 3 0 x 4 0 x 5
案、措施，是问题中要确定的未知量。
2.目标函数:指问题要达到的目的要求，表示为 决策变量的函数。
3.约束条件:指决策变量取值时受到的各种可用 资源的限制，表示为含决策变量的等式或不等 式。
最新版的一般表示形式：
m ax (mm in ) 或 f ( xm ) a cz 1 x 1 c 1 cx x 21 i x 2 c 2 n x 2 ( cn x ) n c n x n
( 4 )无可行解。
目标函数为max z=3x1+x2，约束条件为
x 1 x 2 2 ; 最x 新1 版整 理ppt 2 x 2 6
库存管理。存储论应用于多种物资库存量的管理，确定某些设备的合 理的能力或容量以及适当的库存方式和库存量
运输问题。用运筹学中运输问题的方法，可以确定最小成本的运输线 路、物资的调拨、运输工具的调度以及建厂地址的选择。
人事管理。可以用运筹学方法对人员的需求和获得情况进行预测；确 定合适需要的人员编制；用指派问题对人员合理分配；用层次分析法 等方法来确定一个人才评价体系等。
数为0；
（4）第i 个约束为 型，在不等式左边减去一 个非负的变量，称为剩余变量；同时令该变量在目
标函数中的系数为0；
（5）若 ，x令0 xx
（6）若 无x约束，令 x，x其中x，
x,x0
例3：将下述线性规划模型化为标准形式：

三、教学难点：算法分析的方法；线性表的基本操作；平 均时间复杂度的分析方法；算法设计训练。 四、教学过程：
§1.4 算法和算法分析 §1.4.1 算法的定义及特性
算法(Algorithm)是对指定问题求得步骤的一种描述，是为了 解决某类问题而规定的一个有限长的操作(指令)序列。 算法的五个重要特性：
for(k=1;k<=n;k++)
//n(n+1)
//n*n //n*n*(n+1)
c[i][j]=c[i][j]+a[i][k]*b[k][j]； //n*n*n
}
}
T(n)2n33n22n1
T(n)是矩阵阶数n的函数。
TKS 7 18:45
2、问题规模和算法的时间复杂度 算法求解问题的输入量称为问题的规模，一般用整数n表示。 对于例1.4的乘积算法，当n趋向无穷大时，显然有
例2：英文字母表（A, B, C, D, E Z）。
例3：某单位的电话号码簿。 姓 名 电话号码
蔡颖
63214444
刘建平
63216666
王小林
63218888
张力
63215555
...
TKS 15 18:45
3、说明和特点
(1) 线性表的数据元素可以是各种各样的，但同一线性表中的元 素必须是同一类型的； (2) 在表中 ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱， ai+1是ai的直接后继； (3) 在线性表中，存在唯一一个被称作第一个元素和最后一个元 素，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继。
TKS 14 18:45
§2.1 线性表的类型定义
§2.1.1线性表的定义和特点

它涉及到的问题包括最短路径、 最小生成树、最大流等。
图论与网络优化在计算机科学、 交通运输、通信网络等领域有 广泛应用，如路由算法、网络 设计等。
03 运筹学在现实生活中的应 用
生产与库存管理
01
02
03
生产计划
运筹学通过数学模型和算 法，帮助企业制定生产计 划，优化资源配置，提高 生产效率。
库存控制
Excel Solver的特点
Excel Solver易于使用
它提供了一个直观的用户界面，用户可以通过简单的拖放操作来定义问题。
Excel Solver具有广泛的适用性
它可以处理各种类型的优化问题，包括线性规划、整数规划、目标规划、非线性规划等。
Excel Solver具有高效性
它使用了多种优化算法，可以快速求解大规模问题。
它使用了高效的算法和优化的数据结构，可以快速地处理大规模数据和计算任务。
05 案例分析与实践
生产计划优化案例
总结词
生产计划是企业管理中的重要环节，通过优化生产计划可以提高企业的生产效率 和资源利用率。
详细描述
生产计划优化案例主要涉及如何根据市场需求、产品特性、生产能力等因素制定 合理的生产计划，以实现生产效益的最大化。具体包括对生产计划的制定、执行 、调整等环节进行优化，提高生产计划的准确性和灵活性。
运筹学的重要性
01
提高效率
降低成本
02
03
增强决策科学性
运筹学能够通过优化资源配置和 流程，提高系统的效率和生产力。
通过合理的资源配置和计划安排， 运筹学可以帮助企业降低成本和 资源消耗。
运筹学提供的数据分析和模型预 测等方法，有助于增强决策的科 学性和准确性。

Page 4
运筹学的主要内容
数学规划（线性规划、整数规划、目标规划、 数学规划（线性规划、整数规划、目标规划、动态 规划等） 规划等） 图论 存储论 排队论 对策论 排序与统筹方法 决策分析
Page 5
本课程的教材及参考书
选用教材 《运筹学基础及应用》胡运权主编 哈工大出版社 运筹学基础及应用》 参考教材 《运筹学教程》胡运权主编 （第2版）清华出版社 运筹学教程》
线性规划问题的数学模型
约束方程的转换：由不等式转换为等式。 约束方程的转换：由不等式转换为等式。
Page 23
∑a x
ij
j
≤ bi
∑a
ij
x j + xn+i = bi
称为松弛变量
xn+i ≥ 0
∑a x
ij
j
≥ bi
∑a x
ij
j
− xn+i = bi
称为剩余变量
xn+i ≥ 0
变量x
j
≤ 0 的变换
线性规划问题的数学模型
（2）如何化标准形式 目标函数的转换
Page 22
则可将目标函数乘以( 1)， 如果是求极小值即 min z = ∑ c j x j ，则可将目标函数乘以(-1)， 可化为求极大值问题。 可化为求极大值问题。 即
max z ′ = − z = −∑ c j x j
也就是： 可得到上式。 也就是：令 z ′ = − z ，可得到上式。 变量的变换 若存在取值无约束的变量 x j ，可令 x j = x′j − x′j′ 其中： 其中：x ′j , x ′j′ ≥ 0
运筹学在工商管理中的应用涉及几个方面： 运筹学在工商管理中的应用涉及几个方面：

.
16
p
min
ck x
LP(xˆ) : s.t.
k 1
ck x ck xˆ
(k 1,L , p)
Ax b
x0
结论：
若 ˆx为 LP 的最优解，则必为有效解
若 ˆx不是 LP 的最优解，而是 y，则 y 即是有效解
.
17
例 已知一个多目标决策问题（Max问题）
max z 1=x 1 -x 2 +x 3
.
14
有效解判别方法之一
若 xˆX，则它是有效解的充要条件是 xˆ 为
p
min fk (x) k1
s.t. xX fk (x) fk (xˆ) (k 1,L , p)
的最优解
.
15
对多目标线性规划
min (c1x,L , c p x) s.t. A x b
x0
如何判断一个可行解 ˆx是否为有效解？
.
11
mifn(x)(f1(x) , ,fp(x)) s.t. xX
设 xˆX 。若不存在 xX使得 fk (x ˆ ) fk (x )( k 1 ,L ,p )
且至少有一个是严格不等式，则的有效解
z2 x2
P3(10,40)
0 P1 (10,0)
x1
m in/m axf(x)(f1(x),L,fp(x)) s.t. xX
其中
X { x R n g i(x ) 0 ,i 1 , ,m }
.
7
多目标决策问题的共同特点
目标之间的不可公度性：指各个目标一般没有统一的衡量 标准，因而很难进行比较
目标之间的冲突性：大部分多目标决策问题存在着冲突。 即如果采用某种方案去改进一个目标值，很可能会使另一 目标值变坏

2
第2页/共73页
数学规划中的模型都是线性函数时，称线性规划。 线性规划 (Linear Programming ——LP)
是数学规划的一个分支，是一种解决在线性约 束条件下追求最大或最小的线性目标函数的方 法。一般可以表达成以下两个问题中的一个： 1. 当资源给定时，要求完成的任务最多； 2. 当任务给定时，要求为完成任务所消耗的资源 最少。
LP解的可能情况：
有可行解
有最优解
唯一解 无穷多解
无最优解（可行域为无界）
无可行解（无解）
若LP问题有最优解，则要么最优解唯一，要么 有无穷多最优解。
9
第9页/共73页
x2
③
①
4, 6
②
多重解举例
Max Z=3X1+4X2
X1 ≤8 ①
2X2 ≤12
②
3X1+4X2≤36 ③
X1﹑X2≥0
963
4
x1 x2 x3 x4 x5 基本变量 非基变量
1 0 1 0 0 x1x2x3 x4x5
0 2 0 1 0 令x4,x5=0，得：
3
4
0
0
1
X=(4 6 4 0 0) z=42
5
x1 x2 x3 x4 x5 基本变量 非基变量
1 0 1 0 0 x1x3x4 x2x5
0 2 0 1 0 令x2,x5=0，得：
0 2 0 1 0 令x3,x4=0，得：
34001
X=(8 6 0 0 -12)
z=54
8
x1 x2 x3 x4 x5 基本变量 非基变量
1 0 1 0 0 x2x4x5 x1x3 0 2 0 1 0 ∵ 000 3 4 0 0 1 2 1 0 =0

线性规划问题的数学模型
4. 建模步骤
(1) 确定决策变量：即需要我们作出决策或选择的量。一般 情况下，题目问什么就设什么为决策变量；
(2) 找出所有限定条件：即决策变量受到的所有的约束； (3) 写出目标函数：即问题所要达到的目标，并明确是max 还是 min。
线性规划问题的数学模型
5. 线性规划数学模型的一般形式
2x1 + 2x2 ≤ 12
A 2
B 1
C 4
D 0
利润 （元）
Ⅰ
2
Ⅱ
有效台时
2
12
2
8
0
16
4
12
3
x1 + 2x2 ≤ 8
4x1 ≤ 16 4x2 ≤ 12 x1 ≥ 0 , x2 ≥ 0
线性规划问题的数学模型
例1.4 某厂生产三种药物， 这些药物可以从四种不同的 原料中提取。下表给出了单 位原料可提取的药物量
项目 设备 A（h） 设备 B（h） 调试工序（h） 利润（元） Ⅰ 0 6 1 2 Ⅱ 5 2 1 1 每天可用能力 15 24 5
解： 1.决策变量：设产品I、II的产量
分别为 x1、x2
2.目标函数：设总利润为z，则有： max z = 2 x1 + x2 3.约束条件： 5x2 ≤ 15 6x1+ 2x2 ≤ 24 x1+ x2 ≤ 5 x1， x2≥0
9、决策分析(Decision Analysis) ：主要研究定量化决策。
本课程的教材及参考书
选用教材

《运筹学教程》胡运权主编 （第3版）清华出版社 《运筹学基础及应用》胡运权主编 哈工大出版社
参考教材

个算法时，可进行时间性能上的比较，以便从中挑选出较优算法。 1、算法的执行时间和语句的频度
一个算法的执行时间大致上等于其所有语句执行时间的总和， 而语句的执行时间则为该条语句的重复执行次数和执行一次所需时 间的乘积。
语句的频度(Frequency Count)：一条语句的重复执行次数。 △ 算法的执行时间=∑原操作(基本操作)的执行次数(频度)× 原操作的执行时间 △ 设每条语句一次执行的时间都是相同的，为单位时间。这 样我们对时间的分析就可以独立于软硬件系统。
lim T(n)/n3 lim (2n33n22n1)/n32
n
n
一个算法的时间复杂度(Time Complexity)是该算法的执行时
间，记作T(n)，T(n)是该算法所求解问题规模n的函数。
当问题的规模趋向无穷大时，T(n)的数量级称为算法的渐近时
间复杂度，记作
T(n)=〇(f(n))
(3) x++;
(4) for(i=1；i<=n；i++)
T(n)=〇(n2)
(5) for(j=1jj<=n；j++)
(6)
y++;
例1.7 变量计数之二
ni j
ni
n
1j i(i1)/2
(1) x=1；
i1 j1 k1 i1 j1
i1
(2) for(i=1；i<=n；i++) [n(n1)(2n1)/6n(n1)/2]/2
它表示随问题规模n的增大，算法执行时间的增长率和f(n)的
增长率相同，简称时间复杂度。我们就是要找这个f(n) 。
例1.5 交换x和y的值。
temp=x;

负指数分布、几何分布、爱尔朗分布等。
服务时间分布
负指数分布、确定型分布、一般分布等。
顾客到达和服务时间的独立性
假设顾客到达和服务时间是相互独立的。
单服务台排队系统
M/M/1排队系统
顾客到达服从泊松分布，服务时间服从负指 数分布，单服务台。
M/D/1排队系统
顾客到达服从泊松分布，服务时间服从确定 型分布，单服务台。
投资组合优化
确定投资组合中各种资产的最 优配置比例，以最大化收益或
最小化风险。
03
整数规划
整数规划问题的数学模型
01
整数规划问题的定 义
整数规划是数学规划的一个分支 ，研究决策变量取整数值的规划 问题。
02
整数规划问题的数 学模型
包括目标函数、约束条件和决策 变量，其中决策变量要求取整数 值。
03
Edmonds-Karp算法
介绍Edmonds-Karp算法的原理、步骤和实现方法，以及其与FordFulkerson算法的比较。
网络最大流问题的应用
列举网络最大流问题在资源分配、任务调度等领域的应用案例。
最小费用流问题
最小费用流问题的基本概 念
介绍最小费用流问题的定义、 分类和应用背景。
Bellman-Ford算法
优点是可以求解较大规模的整数规划问题，缺点是计算量较大，需 要较高的计算精度。
割平面法
割平面法的基本思想
通过添加新的约束条件（割平面）来缩小可行域的范围，从而逼 近最优解。
割平面法的步骤
包括构造割平面、求解子问题和更新割平面三个步骤，通过不断 迭代找到最优解。
割平面法的优缺点
优点是可以处理较复杂的整数规划问题，缺点是构造割平面的难 度较大，需要较高的数学技巧。