运 筹 学
(Operations Research)
西安建筑科技大学管理学院
1
绪 论
运 筹 学 的 定 义
运筹学的主要特点
运筹学的工作步骤
运 筹 学 的 模 型
1
运筹学的定义
运筹学(Operations Research)直译为“运作研究”。
运筹学是运用科学的方法(如分析、试验、量化等)来决定如何最佳地运营和设计各种系统的一门学科。
运筹学能够对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。通常以最优、最佳等作为决策目标，避开最劣的方案。
1
运筹学的特点
运筹学研究和解决问题的基础是最优化技术并强调系统最优
运筹学研究和解决问题的优势是应用各学科交叉的方法，具有综合性
运筹学研究和解决问题的方法具有显著的系统性特征，建立模型和利用计算机求解
运筹学研究和解决问题的效果具有连续性
运筹学具用强烈的实践性和应用的广泛性
1
运筹学的工作步骤
提出问题：弄清问题的目标、可能的约束、可控变量及其参数等
建立模型：将变量、参数、目标及约束关系用模型表示出来
求解：用各种手段对模型求解，解可以是最优解、次优解和满意解
解的检验：求解步骤和程序有无错误、解是否能反映实际
解的控制：根据要求可作改变
解的实施：主要是应用过程中需考虑的问题
1
运筹学的模型
模型的
基本形式
形象模型
模拟模型
符号或数学模型
1
运筹学的模型
直接分析法
类比分析法
数据分析法
试验分析法
想定（构思）法
机理清楚
机理不清楚
方法和思路
构建模型的
1
运筹学的模型
模型的一般形式
目标评价准则：V = f （ xi , yj , §k ）
约 束 条 件： g （xi , yj ,§k ）≥ 0
其中：
xi 为可控变量；
yj 为已知参数；
§k 为随机因素
1
运筹学的模型
或：max (或min ) Z = f ( x1 , x2 , . . . ,xn )
其中：xj ( i = ……n )为决策变量
Z 为目标函数
gi ( x1 . x2 . . . . . .xn ) ≤0 和
hj (x1 . x2 . . . . . .xn ) = 0 为约束条件
gi ( x1 , x2 , . . . , xn ) ≤ ( ≥ 或 ＝ ) 0 ( i = 1,2,…,m )
hj (x1 , x2, . . . , xn ) = 0 ( j = 1,2,…,n )
.
1
运筹学的分支
线性规划
整数规划
非线性规划
多目标规划
动态规划
对策论
决策论
存储论
排队论
图论
1
运筹学的应用
主要方面：
生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等。
库存管理：多种物资库存量管理，库存方式、库存量等。
运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等。
人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。
市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。
财务会计：包括预测、贷款、成本分析、定价、证券管理、现金管理等。
其 他：设备维修、更新，项目选择、评价，工程优化设计与管理等。
1
线性规划
线性规划问题及其数学模型
线性规划问题的基本原理
线性规划的图解法
线性规划的单纯形法
单纯形法的进一步讨论
线性规划模型的应用
1
线性规划问题
待建模的线性规划问题需满足的条件：
所求问题的目标能表示为最大化或最小化问题
问题一定要具备有达到目标的不同方法，即必须要有选择的可能性
要达到的目标是有限制条件的
问题的目标和约束都能表示为线性式
1
资源利用问题
设某建筑公司的预制厂利用沙石灰三种原料 来生产两种产品和，已知该厂各种原料的现有数量，每单位产品对各种原料的消耗量及所获利润如下表所示。在这些现有的资源条件下，如何分配产品的生产，才使公司取得利润最大。
45
1
1
A3
80
1
2
A2
4
3
B2
5
单位利润（百元）
90
1
A1
原料现有数（M3）
B1
单
产
原 料
品
位
消
产
品
耗
1
资源利用问题
确定未知变量:设x1表示B1的生产数量, x2表示B2的生产数量
设立目标函数:要求公司取得最大利润，所以设利润函数为f(x)
则 f(x)=5 x1 +4 x2 (百元)
归纳1，2，3式得出该问题为:
求满足约束函数并使f(x)=5 x1 +4 x2 最大的一组数 (x1， x2)T
建立约束函数:问题的约束资源限制为各种原料的现有数，则有关系式
1
投资计划问题
某企业拥有20万资金，拟在今后五年内对下列项目投资。已知：
项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%；
项目B：第三年年初需要投资，到第五年末能回收本利125%，但规定最大投资不超过8万元；
项目C：第二年初需要投资，到第五年末能回收本利140%，但规定最大投资额不超过6万元；
项目D：五年内每年年初可购买公债或定期储蓄，于当年末归还，并加利息9%。
如何确定项目每年的投资额，可使第五年末投资本利总额最大。
1
投资计划问题
确定未知变量:
设xiA, xiB, xiC, xiD 分别表示第 i 年投资到项目 A, B, C, D的投资额
资金流转分析:
第一年投资 : x1A+ x1D = 20000
第一年回收 : x1D
第二年投资 : x2A+ x2C + x2D = x1D
第二年回收 : + x2D
第三年投资 : x3A+ x3B+ x3D = + x2D
第三年回收 : + x3D
第四年投资 : x4A+ x4D = + x3D
第四年回收 : + x4D
第五年投资 : x5D = + x4D
第五年回收 : + + + x5D
1
投资计划问题
该投资问题的模型为:
求 xiA, xiB, xiC, xiD 并满足
并使 f = + + + x5D 最大
1
线性规划标准形式
目标函数：
①
约束条件：
②
③
非负条件:
1
模型转换
目标转换
求最小可以等价成求负的最大
约束转换
变量转换
令自由变量
为自由变量
1
模型转换实例
例 ：将下列线性规划问题化为标准形式
为无约束（无非负限制）
1
模型转换实例
解: 用 替换 ，且 ，
将第3个约束方程两边乘以（－1）
将极小值问题反号，变为求极大值
标准形式如下：
引入变量
1
线性规划解的概念
⑴可行解：满足约束条件②、③的解为可行解。所有解的集合为可行解的集或可行域。
⑵最优解：目标函数达到最大值的可行解。
⑶ 基： B是矩阵A中m×n阶非奇异子矩阵（∣B∣≠0），则B是一个基。
则称Pj ( j=1,2,…,m) 为线性规划的基向量。
与基向量对应的决策变量称为线性规划的基变量，否则为非基变量。
1
线性规划解的概念
⑷ 基本解：满足条件②，但不满足条件③的所有解，最多有Cnm个。
⑸基本可行解：满足非负约束条件③的基本解，称为基本可行解。
⑹基本最优解：使目标函数极大的基本可行解，称为基本最优解。
非可行解
可
行
解
基
本
解
基本可行解
1
线性规划解的基本定理
定理1: 线性规划问题的可行域是凸集
凸集
凸集
不是凸集
顶 点
定理2: 最优解一定是在凸集的某一顶点实现（顶点数目不超过Cnm个）
1
线性规划的图解法
0
1 2 3 4 5 6 7 8
1 2 3 4 5 6
⑴
⑵
⑶
⑷
∴ 最 优 解：x1 = 4 x2 = 2
线性规划有唯一最优解，Z = 14
x2
x1
(4 2)
例 1
1
线性规划的图解法
⑴
⑵
⑶
∴ 线性规划有无穷多最优解
x1
x2
例 2
1
线性规划的图解法
⑴
⑵
x1
x2
例 3
∴ 线性规划有无界解
1
线性规划的图解法
⑴
⑵
x1
x2
例 4
∴ 线性规划无可行解
1
线性规划的图解法
线性规划的可行域和最优解的情况
可行域为封闭的有界区域
有唯一的最优解
有无穷多个最优解
可行域为封闭的无界区域
有唯一的最优解
有无穷多个最优解
目标函数无界
可行域为空集
没有可行解，原问题无最优解
1
单纯形法基本思想
将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基本可行解，并判断是否是最优。如果是，获得最优解；如果不是，转换到另一个基本可行解，当目标函数达到最大时，得到最优解。
1
单纯形法
例 1
变成标准型
1
单纯形法
约束方程的系数矩阵
为基变量
为非基变量
I 为单位矩阵且线性独立
1
单纯形法
令：
则：
∴ 基本可行解为（0 ,0 ,12, 8, 16 ,12）
此时，Z = 0
然后，找另一个基本可行解。即将非基变量换入基变量中，但保证其余的非负。如此循环下去，直到找到最优解为止。
注意：为尽快找到最优解，在换入变量时有一定的要求。如将目标系数大的先换入等。
1
单纯形法
找出一个初始可行解
是否最优
转移到另一个目标函数
（找更大的基本可行解）
最优解
是
否
循
环
直到找出为止，核心是：变量迭代
结束
1
单纯形法
当 时， 为换入变量
确定换出变量
为换出变量
接下来有下式：
1
单纯形法
用高斯法，将 的系数列向量换为单位列向量，其步骤是：
结果是：
1
单纯形法
代入目标函数：
有正系数表明：还有潜力可挖，没有达到最大值；
有负系数表明：若要剩余资源发挥作用，就必须支付附加费用。当 时，即不再利用这些资源。
此时：令 得到另一个基本可行解
（0，3，6，2，16，0）
如此循环进行，直到找到最优为止。
本例最优解为： (4，2，0，0，0，4）
1
单纯形表
1
单纯形表
判定标准：
若求
或
例 2
1
单纯形表
0
-Z
2 2 1 0 0 0
1 2 0 1 0 0
4 0 0 0 1 0
0 4 0 0 0 1
12
8
16
12
x3
x4
x5
x6
0
0
0
0
x1 x2 x3 x4 x5 x6
b
xB
cB
2 3 0 0 0 0
cj
2 3 0 0 0 0
12/2
8/2
－
12/4
-Z
4 0 0 0 1 0
16
x3
x4
x5
0
0
0
x1 x2 x3 x4 x5 x6
b
xB
cB
2 3 0 0 0 0
cj,
3
x2
3
0
1
0
0
0
1/4
2
6
2
0
1
0
0
-1/2
1
0
0
1
0
-1/2
1
单纯形表
-9
-Z
2 0 1 0 0 -1/2
1 0 0 1 0 -1/2
4 0 0 0 1 0
0 1 0 0 0 1/4
6
2
16
3
x3
x4
x5
x2
0
0
0
3
x1 x2 x3 x4 x5 x6
b
xB
cB
2 3 0 0 0 0
cj
2 0 0 0 0 -3/4
6/2
2
16/4
－
0 0 0 -2 0 1/4
-13
-Z
4
－
4
12
0 0 1 -2 0 1/2
1 0 0 1 0 -1/2
0 0 0 -4 1 2
0 1 0 0 0 1/4
2
2
8
3
x3
x1
x5
x2
0
2
0
3
x1 x2 x3 x4 x5 x6
b
xB
cB
2 3 0 0 0 0
cj
1
单纯形表
0 0 -1/2 -1 0 0
-14
-Z
0 0 2 -4 0 1
1 0 1 -1 0 0
0 0 -4 4 1 0
0 1 -1/2 1 0 0
4
4
0
2
x6
x1
x5
x2
0
2
0
3
x1 x2 x3 x4 x5 x6
b
xB
cB
2 3 0 0 0 0
cj
0 0 0 -2 0 1/4
-13
-Z
4
－
4
12
0 0 1 -2 0 1/2
1 0 0 1 0 -1/2
0 0 0 -4 1 2
0 1 0 0 0 1/4
2
2
8
3
x3
x1
x5
x2
0
2
0
3
x1 x2 x3 x4 x5 x6
b
xB
cB
2 3 0 0 0 0
cj
1
单纯形表
0 0 0 -3/2 -1/8 0
-14
-Z
0 0 1 -1 -1/4 0
1 0 0 0 1/4 0
0 0 0 -2 1/2 1
0 1 0 1/2 -1/8 0
0
4
4
2
x3
x1
x6
x2
0
2
0
3
x1 x2 x3 x4 x5 x6
b
xB
cB
2 3 0 0 0 0
cj
0 0 0 -2 0 1/4
-13
-Z
4
－
4
12
0 0 1 -2 0 1/2
1 0 0 1 0 -1/2
0 0 0 -4 1 2
0 1 0 0 0 1/4
2
2
8
3
x3
x1
x5
x2
0
2
0
3
x1 x2 x3 x4 x5 x6
b
xB
cB
2 3 0 0 0 0
cj
1
单纯形法的进一步讨论
（一）模型情况
变 量：xj≥0 xj≤0 xj 无约束 结
1、组成 约束条件：≥ = ≤b
目标函数： max min 果
2 、变量 xj≤0 令 xj′= -xj ， xj′≥0
xj≥0 不处理
xj 无约束 令xj = xj′－ xj″, xj′≥0 , xj″≥0
唯一最优
无穷最优
无界解
无可行解
3、约束
条件：
加入松弛变量
加入人工变量
先减去 再加上
1
单纯形法的进一步讨论
例 3
1
单纯形法的进一步讨论
4、目标函数：max , min
设规划模型约束条件为 ，需加入人工变量 ，而得到一个m×m的单位矩阵，即基变量组合。因人工变量为虚拟变量，且存在于初始基本可行解中，需要将它们从基变量中替换出来。若基变量中不含有非零的人工变量，表示原问题有解。若当 ，而还有人工变量（非零）时，则表示原问题无可行解。
加入人工变量后，目的是找到一个单位向量，叫人工基。其目标价值系数要确定，但不能影响目标函数的取值。一般可采用两种方法处理：大M法和两阶段法。
1
大M法
即假定人工变量在目标函数中的系数为M（任意大正数），如果是求极大值，需加-M；如果是求极小值，需加M。如基变量中还存在M，就不能实现极值。
1
大M法
0
0
M
0
1-3M
1-M
-3+6M
-Z
1
1
0
0
0
1
0
-2
1
x7
M
3/2
0
1
-1
0
2
1
-4
3
x6
M
11
0
0
0
1
1
-2
1
11
x4
0
x7
x6
x5
x4
x3
x2
x1
b
xB
cB
M
M
0
0
1
1
-3
cj
3M-1
0
M
0
0
1-M
-1
-Z
－
1
0
0
0
1
0
-2
1
x3
1
1
-2
1
-1
0
0
1
0
1
x6
M
－
-1
0
0
1
0
-2
3
10
x4
0
x7
x6
x5
x4
x3
x2
x1
b
xB
cB
来判断
计算过程如下：用
0
³
-
j
j
z
c
1
大M法
M+1
M-1
1
0
0
0
-1
-2
-Z
－
1
0
0
0
1
0
-2
1
x3
1
－
-2
1
-1
0
0
1
0
1
x2
1
4
-5
2
-2
1
0
0
3
12
x4
0
x7
x6
x5
x4
x3
x2
x1
b
xB
cB
M
M
0
0
1
1
-3
cj
M-2/3
M-1/3
1/3
1/3
0
0
0
2
-Z
-7/3
4/3
-4/3
2/3
1
0
0
9
x3
1
-2
1
-1
0
0
1
0
1
x2
1
-5/3
2/3
-2/3
1/3
0
0
1
4
x1
-3
x7
x6
x5
x4
x3
x2
x1
b
xB
cB
∴最优解为（4 , 1, 9, 0 , 0 , 0 , 0），Z = －2
1
两阶段法
用计算机处理数据时，只能用很大的数代替M,可能造成计算机上的错误，故多采用两阶段法。
第一阶段：在原线性规划问题中加入人工变量，构造如下模型：
1
两阶段法
对上述模型求解（单纯形法），若W=0,说明问题存在基本可行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。
第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。
例 4
1
两阶段法
0
0
1
0
-3
-1
6
4
-Z
1
1
0
0
0
1
0
-2
1
x7
1
3/2
0
1
-1
0
2
1
-4
3
x6
1
11
0
0
0
1
1
-2
1
11
x4
0
x7
x6
x5
x4
x3
x2
x1
b
xB
cB
1
1
0
0
0
0
0
cj
3
0
1
0
0
-1
0
1
-Z
－
1
0
0
0
1
0
-2
1
x3
0
1
-2
1
-1
0
0
1
0
1
x6
1
－
-1
0
0
1
0
-2
3
10
x4
0
1
1
0
0
0
0
0
0
-Z
0
0
0
0
1
0
-2
1
x3
0
-2
1
-1
0
0
1
0
1
x2
0
-5
2
-2
1
0
0
3
12
x4
0
1
两阶段法
1
0
0
0
-1
-2
-Z
－
0
0
1
0
-2
1
x3
1
－
-1
0
0
1
0
1
x2
1
4
-2
1
0
0
3
12
x4
0
x5
x4
x3
x2
x1
b
xB
cB
0
0
1
1
-3
cj
1/3
1/3
0
0
0
2
-Z
-4/3
2/3
1
0
0
9
x3
1
-1
0
0
1
0
1
x2
1
-2/3
1/3
0
0
1
4
x1
-3
∴最优解为（4, 1, 9, 0, 0），目标函数 Z = -2
1
线性规划小结
-M
0
令
z′=- Z
minZ
=－
max z′
不
处
理
减
去
xs
加入
xa
加入人工变量xa
加松弛变量xs
约束条件两端同乘以-1
不
处
理
令 xj =
- xj
令
xj = xj′ - xj″
xj′ ≥0
xj″ ≥0
不
处
理
单纯形法
图解法、
单纯形法
求解
xa
xs
minZ
maxZ
≥
=
≤
bi < 0
bi ≥0
xj ≤ 0
xj无
约束
xj≥0
三个
以上
两
个
新加变量系数
极大或极小
等式或
不等式
右 端 项
取 值
个 数
建
立
模
型
根据上表列出初始单纯形表 A
1
线性规划小结
A
1
