?管理与人文学院 忻展红
1999,4
运筹学
Operational Research
运筹帷幄，决胜千里
? 史记, 张良传,
2
目 录
绪 论
第一章 线性规划问题及单纯型解法
第二章 线性规划的对偶理论及其应用
第三章 运输问题数学模型及其解法
第四章 整数规划
第五章 动态规划
第六章 图与网路分析
第七章 随机服务理论概论
第八章 生灭服务系统
第九章 特殊随机服务系统
第十章 存储理论
3
绪 论
一、运筹学的起源与发展
二、运筹学的特点及研究对象
三、运筹学解决问题的方法步骤
四、运筹学的发展趋势
4
一、运筹学的起源与发展
? 起源于二次大战的一门新兴交叉学科
? 与作战问题相关
– 如雷达的设置、运输船队的护航、反潜作战中深水炸弹
的深度、飞行员的编组、军事物资的存储等
– 英国称为 Operational Research
– 美国称为 Operations Research
? 战后在经济、管理和机关学校及科研单位继续研究
– 1952年,Morse 和 Kimball出版, 运筹学方法,
– 1948年英国首先成立运筹学会
– 1952年美国成立运筹学会
– 1959年成立国际运筹学联合会 (IFORS)
– 我国于 1982年加入 IFORS，并于 1999年 8月组织了第 15
届大会
5
二、运筹学的特点及研究对象
? 运筹学的定义
– 为决策机构对所控制的业务活动作决策时，提供以数量
为基础的科学方法 ——Morse 和 Kimball
– 运筹学是把科学方法应用在指导人员、工商企业、政府
和国防等方面解决发生的各种问题，其方法是发展一个
科学的系统模式，并运用这种模式预测，比较各种决策
及其产生的后果，以帮助主管人员科学地决定工作方针
和政策 ——英国运筹学会
– 运筹学是应用分析、试验、量化的方法对经济管理系统
中人力、物力、财力等资源进行统筹安排，为决策者提
供有根据的最优方案，以实现最有效的管理 ——中国百
科全书
– 现代运筹学涵盖了一切领域的管理与优化问题，称为
Management Science
6
二、运筹学的特点及研究对象
? 运筹学的分支
– 数学规划：线性规划、非线性规划、整数规划、动态规
划、目标规划等
– 图论与网路理论
– 随机服务理论：排队论
– 存储理论
– 决策理论
– 对策论
– 系统仿真：随机模拟技术、系统动力学
– 可靠性理论
– 金融工程
7
三、运筹学解决问题的方法步骤
? 明确问题
? 建立模型
? 设计算法
? 整理数据
? 求解模型
? 评价结果
明确问题
建立模型
设计算法
整理数据
求解模型
评价结果
简化？
满意？
Yes
No
No
8
四、运筹学的发展趋势
? 运筹学的危机
– 脱离实际应用，陷入数学陷阱
? IT对运筹学的影响
– MIS,DSS,MRP-II,CIMS,ERP
– OR Dept,--> Dept,Of OR & IS
? 运筹学与行为科学结合
– 群决策和谈判
– 对策理论
– 多层规划
– 合理性分析
? 服务行业中的应用
– 金融服务业
– 信息、电信服务业
– 医院管理
9
四、运筹学的发展趋势
? 软计算
– 面向强复杂系统的计算、实时控制、知识推理
– 智能算法：模拟退火、遗传算法、人工神经网络、戒律
算法等
– 系统仿真
? 面向问题
? 后勤 (Logistics)
– 全球供应链管理
– 电子商务：集成特性
? 随机和模糊 OR
– 问题本身的不确定性
– 人类知识的局限性
10
第一章 线性规划问题及单纯型解法
1.1 线性规划问题及其一般数学模型
1.1.1 线性规划问题举例
例 1、多产品生产问题 （ Max,?）
设 x1,x2 分别代表甲、乙两种电缆的生产量，
.36)(m a x,6,2:
0,
7
8
102
..
46)(m a x:
21
21
2
21
21
21
???
?
?
?
?
?
?
?
?
?
??
??
??
xfxx
xx
x
xx
xx
ts
xxxfO B J
最优解
产量不允许为负值
产量约束
铅资源约束
铜资源约束
11
例 2、配料问题（ min,?)
原料甲 原料乙 最低含量
VA 0, 5 0, 5 2
V B 1 1, 0 0, 3 3
V B 2 0, 2 0, 6 1, 2
VD 0, 5 0, 2 2
单价 0, 3 0, 5
设 x1,x2分别代表每粒胶丸中甲、
乙两种原料的用量
12
例 3、合理下料问题
设 xj 分别代表采用切割方案 1~8的套数，
方案 2, 9 m 2, 1 m 1, 5 m 合计 余料
1 2 0 1 7, 3 0, 1
2 1 2 0 7, 1 0, 3
3 1 1 1 6, 5 0, 9
4 1 0 3 7, 4 0
5 0 3 0 6, 3 1, 1
6 0 2 2 7, 2 0, 2
根，但购买最优解为
则有零料最少若目标函数为使裁剪后
15010,50,100:
0,,,,,
10023
100232
1002
..
2.01.109.03.01.0)(m i n
,
64
654321
6431
6532
4321
654321
???
?
?
?
?
?
?
?
?
????
????
????
??????
O B Jxx
xxxxxx
xxxx
xxxx
xxxx
ts
xxxxxxxf
16 ;90,30,50,10:
0,,,,,
10023
100232
1002
..
)(i n
,
421
654321
6431
6532
4321
654321
但余料为最优解
则有钢筋最少若目标函数为使购买的
????
?
?
?
?
?
?
?
?
????
????
????
??????
O B Jxxx
xxxxxx
xxxx
xxxx
xxxx
t
xxxxxxxf
13
1.1.2 线性规划数学模型的一般表示方式
技术系数右端项价值系数
线性规划问题的规模
约束行数变量个数
,;,;:
:;,;:
0,,,
),(
),(
),(
..
)(m a x ( m i n )
21
2211
22222121
11212111
2211
ijjj
n
mnmnmm
nn
nn
nn
abc
mn
mn
xxx
bxaxaxa
bxaxaxa
bxaxaxa
ts
xcxcxcxf
?
?
?
?
?
?
?
?
?
?
?
??????
??????
??????
????
?
?
?
?
?
?
14
1,和式
?
?
?
?
?
??
??
?
?
?
?
?
njx
mibxa
ts
xcxf
j
i
n
j
jij
n
j
jj
,,2,1,0
,,2,1,
..
)(m a x
1
1
?
?
15
2,向量式
16
3,矩阵式
17
1.1.3 线性规划的图解法
1
1
8
7
6
5
4
3
2
2 x
1
876543
O
10
9
x
2
A B
C
E
D
F
G
H
1
2
3
f
(
x
)
=
0
f
(
x
)
=
12
.36)(m a x
,6,2:
0,
7
8
102
..
46)(m a x
21
21
2
21
21
21
?
??
?
?
?
?
?
?
?
?
?
??
??
??
xf
xx
xx
x
xx
xx
ts
xxxf
最优解
18
线性规划问题的几个特点：
? 线性规划问题的可性解的集合是凸集
? 线性规划问题的基础可行解一般都对应于凸集的极点
? 凸集的极点的个数是有限的
? 最优解只可能在凸集的极点上，而不可能发生在凸集
的内部
19
1.2 线性规划问题的单纯型解法
1.2.1 线性规划问题的标准形式
为了使线性规划问题的解法标准, 就要把一般形式
化为标准形式
?
?
?
?
?
????
????
?
?
?
?
?
njx
mibxa
ts
xcxf
j
i
n
j
jij
n
j
jj
,,2,1 ),,0(0
,,2,1,),(
..
)(m a x ( m i n )
1
1
?
?
不限
?
?
?
?
?
???
??
?
?
?
?
?
?
?
njmixb
mibxa
ts
xcxf
ji
i
mn
j
jij
mn
j
jj
,,2,1,,2,1,0,
,,2,1,
..
)(m a x
1
1
??
?
20
变换的方法：
? 目标函数为 min型，价值系数一律反号。令 f?(x) = -f(x)
= -CX,有 min f(x) = - max [- f(x)] = - max f ?(x)
? 第 i 个约束的 bi 为负值，则该行左右两端系数同时反号，
同时不等号也要反向
? 第 i 个约束为 ?型，在不等式左边增加一个非负的变
量 xn+i, 称为松弛变量；同时令 cn+i = 0
? 第 i 个约束为 ?型，在不等式左边减去一个非负的变
量 xn+i, 称为剩余变量；同时令 cn+i = 0
? 若 xj ?0，令 xj= -xj?,代入非标准型，则有 xj?? 0
? 若 xj ?不限，令 xj= xj? - xj?,xj?? 0,xj?? 0,代入非
标准型
21
变换举例：
?
?
?
?
?
?
?
??
???
???
???
???
0,,
200
40065
300432
..
423)(m i n:
213
321
321
321
321
xxx
xxx
xxx
xxx
ts
xxxxf
不限
原非标准型
?
?
?
?
?
?
?
????
????????
????????
????????
???????????
0,,,,,,
200
400665
3004432
..
0004423)(m a x:
6543321
63321
53321
43321
6543321
xxxxxxx
xxxxx
xxxxx
xxxxx
ts
xxxxxxxxf标准型
22
关于标准型解的若干基本概念：
? 标准型有 n+m 个变量,m 个约束行
?, 基,的概念
– 在标准型中，技术系数矩阵有 n+m 列，即
A = ( P1,P2,…,Pn+m )
– A中线性独立的 m 列，构成该标准型的一个 基,即
B = ( P1 ?,P2 ?,…,Pm ?),| B | ? 0
– P1 ?,P2 ?,…,Pm ?称为 基向量
– 与 基向量 对应的变量称为 基变量,记为
XB = ( x1 ?,x2 ?,…,xm ? )T，其余的变量称为 非基变量,
记为 XN = ( xm+1 ?,xm+2 ?,…,xm+n ? ) T,
故有 X = XB + XN
– 最多有 个基m nmC ?
23
关于标准型解的若干基本概念：
? 可行解 与 非可行解
– 满足约束条件和非负条件的解 X 称为 可行解,满足
约束条件但不满足非负条件的解 X 称为 非可行解
? 基础解
– 令 非基变量 XN = 0，求得 基变量 XB的值称为 基础解
即 XB = B?1 b
– XB 是 基础解 的 必要条件 为 XB 的非零分量个数 ? m
? 基础可行解
– 基础解 XB 的非零分量都 ? 0 时，称为 基础可行解,
否则为 基础非可行解
– 基础可行解 的非零分量个数 < m 时，称为 退化 解
24
线性规划标准型问题解的关系
约束方程的
解空间 基础解可行解
非可行解
基础
可行解
退化解
25
可行解、基础解和基础可行解举例
.36)(m a x
,6,2:
0,,,,
7
8
102
..
46)(m a x
21
54321
52
421
321
21
?
??
?
?
?
?
?
?
?
?
??
???
???
??
xf
xx
xxxxx
xx
xxx
xxx
ts
xxxf
最优解
1
1
8
7
6
5
4
3
2
2 x
1
876543
O
10
9
x
2
A B
C
E
D
F
G
H
1
2
3
f
(
x
)=
3
6
K
非基
变量
基变量
图中的点
解
x
1
,x
2
x
3
= 1 0 x
4
=8 x
5
=7 O 基础可行解
x
1
,x
3
x
2
= 1 0 x
4
= - 2 x
5
= - 3 F 基础解
x
1
,x
4
x
2
=8 x
3
=2 x
5
= - 1 E 基础解
x
1
,x
5
x
2
=7 x
3
=3 x
4
= 1 A 基础可行解
x
2
,x
3
x
1
=5 x
4
=3 x
5
= 7 D 基础可行解
x
2
,x
4
x
1
=8 x
3
= - 6 x
5
= 7 H 基础解
x
3
,x
4
x
1
=2 x
2
=6 x
5
= 1 C 基础可行解
最优解
x
3
,x
5
x
1
= 1, 5 x
2
=7 x
4
= - 0, 5 G 基础解
x
4
,x
5
x
1
=1 x
2
=7 x
3
= 1 B 基础可行解
x
1
= 2,x
2
= 2,x
3
= 4,x
4
= 4,x
5
= 3 K 可行解
26
1.2.2 单纯型法的基本思路
确定初始基础可行解
求最优解的目标函数值
确定改善方向
求新的基础可行解
检查是否为
最优解？
是
否
27
1.2.3 单纯型表及其格式
I V I I I I I I
x
1
x
2
… x
n
x
n+ 1
x
n+ 2
… x
n + m
C
B
X
B
b c
1
c
2
… c
n
c
n+ 1
c
n+ 2
… c
n + m
c
1 ?
= c
n+ 1
x
n+ 1
b
1
a
11
a
12
… a
1 n
1 0 … 0
c
2 ?
= c
n+ 2
x
n+ 2
b
2
a
21
a
22
… a
2 n
0 1 … 0
? ? ? ? ? ? ? ? ? ? ?
c
m ?
= c
n + m
x
n + m
b
m
a
m 1
a
m 2
… a
mn
0 0 … 1
O B J z
1
z
2
… z
n
z
n+ 1
z
n+ 2
… z
n + m
c
1
- z
1
c
2
- z
2
… c
n
-z
n
c
n+ 1
-z
n+ 1
c
n+ 2
-z
n+ 2
… c
n + m
-z
n + m
28
例 1.2.2 试列出下面线性规划问题的初始单纯型表
?
?
?
?
?
?
???
???
???
0,,
1 2 0233
1 0 032
..
244540)(m a x
321
321
321
321
xxx
xxx
xxx
ts
xxxxf
x
1
x
2
x
3
x
4
x
5
C
B
X
B
b 40 45 24 0 0
0 x 4 1 0 0 2 3 1 1 0
0 x 5 1 2 0 3 3 2 0 1
O B J = 0 z
j
? 0 0 0 0 0
c
j
- z
j
? 40 45 24 0 0
29
关于检验数的数学解释
? 设 B 是初始可行基，则目
标函数可写为两部分 (1)
? 约束条件也写为两部分，
经整理得 XB 的表达式 (2)，
注意 XB中含有非基变量作
参数
? 把 XB 代入目标函数，整理
得到 (3)式
? 第 j 个非基变量的机会成
本如 (4)式
? 若有 cj?zj>0,则未达到最优 ( 5 )
( 4 )
)3(
)(
)()(
( 2 ) )(
( 1 ) )(
1 '
jj
m
i ijij
NN
1
BN
1
B
NN
1
BNN
NN
1
B
NNB
BNN
BBNN
zc
acz
XABCCbBC
XAbBCXCxf
XAbBX
XAbBX
bBXXA
XCXCxf
?
?
???
???
??
??
??
??
?
?
??
?
?
检验数
机会成本
30
1.2.4 标准型的单纯型算法
1 找初始基础可行基
– 对于 (max,?)，松弛变量对应的列构成一个单位阵
– 若有 bi<0，则单位阵也不能构成一个可行基
2 检验当前基础可行解是否为最优解
– 所有检验数 cj? zj?0，则为最优解，否则
3 确定改善方向
– 从 (cj? zj) > 0 中找最大者，选中者称为 入变量, xj*
– 第 j*列称为 主列
4 确定 入变量 的最大值和 出变量
– 最小比例原则
(1, 2, 4 ) 0m i n *
* ?
?
?
?
???
? ??
ij
ij
i
i
aa b?
31
1.2.4 标准型的单纯型算法
4 确定 入变量 的最大值和 出变量
– 设第 i* 行使 ? 最小，则第 i* 行对应的基变量称为
出变量,第 i* 行称为 主行
5 迭代过程
– 主行 i* 行与 主列 j* 相交的元素 ai*j* 称为 主元,迭代
以 主元 为中心进行
– 迭代的实质是线性变换，即要将 主元 ai*j*变为 1,主
列 上其它元素变为 0，变换步骤如下：
(1)变换主行
nmjaaa jijiji ???,,2,1**** ?
32
1.2.4 标准型的单纯型算法
5 迭代过程
(2)变换主列
除 主元 保留为 1，其余都置 0
(3)变换非主行、主列元素 aij (包括 bi)
四角算法公式,
数据表示当前单纯型表中的
的数据表示上一个单纯型表中
,
( 1, 2, 5 b )
( 1, 2, 5 a )
**
**
**
**
ij
iji
ji
ijji
ijij
ji
iji
ii
a
ab
a
aa
aa
a
ab
bb
??
??
33
1.2.4 标准型的单纯型算法
5、迭代过程
(4)变换 CB,XB
(5)计算目标函数、机会成本 zj 和检验数 cj ? zj
6,返回步骤 2
a
ij
a
i * j
a
i j *
a
i * j *主行
主
列
主元
四角算法图示
34
表 1.2.4 例 1.2.2 单纯型表的迭代过程
x 1 x 2 x 3 x 4 x 5序
号 C B X B b 40 45 24 0 0 b i / a ij *
0 x 4 100 2 ( 3 ) 1 1 0 ( 3 3, 3 )
0 x 5 120 3 3 2 0 1 40
O B J = 0 0 0 0 0 0
I
初
始
解 c j - z j? 40 45 24 0 0
45 x 2 1 0 0 / 3 2 / 3 1 1 / 3 1 / 3 0 50
0 x 5 20 ( 1 ) 0 1 ? 1 1 ( 2 0 )
O B J = 1 5 0 0 30 45 15 15 0
II
c j - z j? 10 0 9 ? 15 0
45 x 2 20 0 1 ? 1 / 3 1 ? 2 / 3
40 x 1 20 1 0 1 ? 1 1
O B J = 1 7 0 0 40 45 25 5 10
I I I
最
优
解 c j - z j? 0 0 ? 1 ? 5 ? 10
答：最优解为 x1=20,x2=20,x3=0,OBJ=1700
35
单纯型表中元素的几点说明
– 任何时候，基变量对应的列都构成一个单位矩阵
– 当前表中的 b 列表示当前基变量的解值，通过变换
B ?1 b 得到 (资源已变成产品 )
– 当前非基变量对应的向量可通过变换 B ?1 AN 得到，
表示第 j 个变量对第 i 行对应的基变量的消耗率
– 非基变量的机会成本由 给出
– 注意基变量所对应的行
x 1 x 2 x 3 x 4 x 5序
号 C B X B b 40 45 24 0 0 b i / a ij *
45 x 2 1 0 0 / 3 2 / 3 1 1 / 3 1 / 3 0 50
0 x 5 20 ( 1 ) 0 1 ? 1 1 ( 2 0 )
O B J = 1 5 0 0 30 45 15 15 0
I I
c j - z j? 10 0 9 ? 15 0
ija
? ?? mi ijij acz 1 '
36
1.3 人工变量的引入及其解法
1.3.1 当约束条件为, ?” 型，引入剩余变量和人工变
量
? 由于所添加的剩余变量的技术系数为 ?1，不能作为初
始可行基变量，为此引入一个人为的变量（注意，此
时约束条件已为,=”型），以便取得初始基变量，故
称为人工变量
? 由于人工变量在原问题的解中是不能存在的，应尽快
被迭代出去，因此人工变量在目标函数中对应的价值
系数应具有惩罚性，称为罚系数。罚系数的取值视解
法而定
? 两种方法
– 大 M法
– 二阶段法
37
1.3.2 大 M法的求解过程
例 1.3.1
38
表 1.3.1 例 1.3.1的单纯型表迭代过程
x 1 x 2 x 3 x 4 x 5 x 6序
号 C B X B b ? 10 ? 8 ? 7 0 0 ? M b i / a ij *
? M x 6 6 (2) 1 0 ? 1 0 1 (3)
? 7 x 3 4 1 1 1 0 ? 1 0 4
? 6 M ? 28 ? 2 M ? 7 ? M ? 7 ? 7 M 7 ? M
I
初
始
解 c j? z j? 2 M ? 3 M ? 1 0 ? M ? 7 0? 10
x 1 3 1 1 / 2 ? 1 / 2 0 1 / 2 6
? 7 x 3 1 0 ( 1 / 2 ) 1 1 / 2 ? 1 ? 1 / 2 (2)
? 37 ? 10 ? 1 7 / 2 ? 7 3 / 2 7 ? 3 / 2
II
c j? z j? 0 1 / 2 0 ? 3 / 2 ? 7 ? M + 3 / 2
? 10 x 1 2 1 0 ? 1 ? 1 1 1
? 8 x 2 2 0 1 2 1 ? 2 ? 1
? 36 ? 10 ? 8 ? 6 2 6 ? 2
I I I
最
优
解 c j? z j? 0 0 ? 1 ? 2 ? 6 ? M +2
答：最优解为 x1=2,x2=2,x3=0,OBJ=36
39
大 M法的一些说明
– 大 M法实质上与原单纯型法一样,M 可看成一个很
大的常数
– 人工变量被迭代出去后一般就不会再成为基变量
– 当检验数都满足最优条件，但基变量中仍有人工变
量，说明原线性规划问题 无可行解
– 大 M法手算很不方便
– 因此提出了二阶段法
? 计算机中常用大 M法
? 二阶段法手算可能容易
40
1.3.3 二阶段法的求解过程
? 第一阶段的任务是将人工变量尽快迭代出去，从而
找到一个没有人工变量的基础可行解
? 第二阶段以第一阶段得到的基础可行解为初始解，
采用原单纯型法求解
? 若第一阶段结束时，人工变量仍在基变量中，则原
问题无解
? 为了简化计算，在第一阶段重新定义价值系数如下：
?
?
?
?
??
?
?
?
?
?
不是人工变量时当
为人工变量时当
时目标函数为
不是人工变量时当
为人工变量时当
时目标函数为
jj
jj
jj
jj
xc
xc
xc
xc
0
1
m a x
0
1
m i n
41
表 1.3.2 用二阶段法求解例 1.3.1的第一阶段
x 1 x 2 x 3 x 4 x 5 x 6序
号 C B X B b 0 0 0 0 0 ? 1 b i / a ij *
? 1 x 6 6 ( 2 ) 1 0 ? 1 0 1 ( 3 )
0 x 3 4 1 1 1 0 ? 1 0 4
? 6 ? 2 ? 1 0 1 0 ? 1
I
c j? z j? 2 1 0 ? 1 0 0
0 x 1 3 1 1 / 2 0 ? 1 / 2 0 1 / 2
0 x 3 1 0 1 / 2 1 1 / 2 ? 1 ? 1 / 2
0 0 0 0 0 0 0
II
c j? z j? 0 0 0 0 0 ? 1
42
表 1.3.2 用二阶段法求解例 1.3.1的第二阶段
x 1 x 2 x 3 x 4 x 5序
号 C B X B b ? 10 ? 8 ? 7 0 0 b i / a ij *
? 10 x 1 3 1 1 / 2 0 ? 1 / 2 0 6
? 7 x 3 1 0 ( 1 / 2 ) 1 1 / 2 ? 1 ( 2 )
? 37 ? 10 ? 1 7 / 2 ? 7 3 / 2 7
I
c j? z j? 0 1 / 2 0 ? 3 / 2 ? 7
? 10 x 1 2 1 0 ? 1 ? 1 1
? 8 x 2 2 0 1 2 1 ? 2
? 36 ? 10 ? 8 ? 6 2 6
II
c j? z j? 0 0 ? 1 ? 2 ? 6
最优解对应的 B–1在哪？
43
1.5 单纯型法的一些具体问题
1.5.1 关于无界解问题
– 可行区域不闭合 (约束条件有问题 )
– 单纯型表中入变量 xj* 对应的列中所有
0a *ij ?
?
?
?
?
?
?
??
???
??
0,
50
1 0 02
..
)(m a x
1.5.1
21
21
21
21
xx
xx
xx
ts
xxxf
例
f ( x ) =x
1
+x
2
x
1
x
2
50? 50
? 50
1 0 0
x
1
-x
2
=5 0
- 2 x
1
+x
2
=1 0 0
44
表 1.5.1 例 1.5.1 的单纯型表及其迭代过程
x
1
x
2
x
3
x
4序
号
C
B
X
B
b 1 1 0 0 b
i
/ a
ij *
0 x 3 100 ? 2 1 1 0 ??
0 x 4 50 (1) ? 1 0 1 (50)
O B J = 0 0 0 0 0
I
初
始
解 c
j
- z
j
? 1 1 0 0
0 x 3 200 ? ? 1 1 2
1 x 1 50 1 ? 1 0 1
O B J = 5 0 1 ?? 0 1
II
c
j
- z
j
? 0 2 0 ??
?
45
1.5.2 关于退化问题
– 退化问题的原因很复杂，当原问题存在平衡约束时
– 当单纯型表中同时有多个基变量可选作出变量时
– 退化的严重性在于可能导致死循环，克服死循环的
方法有“字典序”法
?
?
?
?
?
?
?
?
??
??
??
??
0,
0
602
40
..
43)(m a x
1, 5, 2
21
21
21
21
21
xx
xx
xx
xx
ts
xxxf
例
x
1
x
2
x
3
x
4序
号
C
B
X
B
b 3 4 0 0 b
i
/ a
ij *
0 x
3
40 ? (2) 1 0 (20)
0 x
4
60 0 ??? 0 1 (20)
3 x
1
0 1 ?? 0 0 ??
O B J = 0 3 ? 3 0 0
II
c
j
- z
j
? 0 7 0 0
4 x
2
20 ? 1 1 / 2 0
0 x
4
0 0 ? ? 3 / 2 1
3 x
1
20 1 ? 1 / 2 0
O B J = 1 4 0 3 ? 3, 5 0
III
c
j
- z
j
? 0 0 ? 3, 5 ?
46
1.5.3 关于多重解问题
– 多个基础可行解都是最优解，这些解在同一个超平
面上，且该平面与目标函数等值面平行
– 最优单纯型表中有非基变量的检验数为 0
– 最优解的线性组合仍是最优解，即 X=aX1+bX2，
a+b=1
?
?
?
?
?
?
???
???
???
0,,
1 2 0233
1 0 032
..
254540)(m a x
1, 5, 3
321
321
321
321
xxx
xxx
xxx
ts
xxxxf
多重最优解例
47
表 1.5.3 例 1.5.3 的单纯型表及其迭代过程
x 1 x 2 x 3 x 4 x 5序
号 C B X B b 40 45 25 0 0 b i / a ij *
0 x 4 100 2 ( 3 ) 1 1 0 ( 3 3, 3 )
0 x 5 120 3 3 2 0 1 40
O B J = 0 0 0 0 0 0
I
初
始
解 c j - z j? 40 45 25 0 0
?
迭代 过程
45 x 2 20 0 1 ? 1 / 3 1 ? 2 / 3 ??
40 x 1 20 1 0 ( 1 ) ? 1 1 ( 2 0 )
O B J = 1 7 0 0 40 45 25 5 10
I I I
最
优
解 c
j - z j? 0 0 0 ? 5 ? 10
45 x 2 2 6,67 1 / 3 1 0 2 / 3 ? 1 / 3
25 x 3 20 1 0 1 ? 1 1
O B J = 1 7 0 0 40 45 25 5 10
I V
最
优
解 c
j - z j? 0 0 0 ? 5 ? 10
48
1.5.4 关于无可行解问题
– 约束条件互相矛盾，无可行域
– 单纯型表达到最优解检验条件时，人工变量仍在基
变量中
?
?
?
?
?
?
?
?
????
???
???
???
0,,
1
2
12
..
2)(m a x
1, 5, 4
321
321
321
321
321
xxx
xxx
xxx
xxx
ts
xxxxf
例
49
表 1.5.4 例 1.5.4 第一阶段的单纯型表
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9序
号 C B X B b 0 0 0 0 0 0 ? 1 ? 1 ? 1 b i / a ij *
? 1 x 7 1 1 1 (2) ? 1 0 0 1 0 0 ( 1 / 2 )
? 1 x 8 2 1 ? 1 ? 1 0 ? 1 0 0 1 0 ?
? 1 x 9 1 ? 1 1 1 0 0 ? 1 0 0 1 1
O B J = ? 4 ? 1 ? 1 ? 2 1 1 1 ? 1 ? 1 ? 1
I
初
始
解
c
j
- z
j
? 1 1 2 ? 1 ? 1 ? 1 0 0 0
? x 3 1 / 2 1 / 2 1 / 2 1 - 1 / 2 0 0 1 / 2 0 0
? 1 x 8 5 / 2 3 / 2 - 1 / 2 ? - 1 / 2 ? 1 0 1 / 2 1 0
? 1 x 9 1 / 2 - 3 / 2 1 / 2 0 1 / 2 0 ? 1 - 1 / 2 0 1
O B J = ? 3 ? ? ? 0 1 1 0 ? 1 ? 1
II
c j - z j? 0 0 0 ? ? 1 ? 1 ? 1 0 0
50
1.4 修正单纯型法
? 原单纯型法迭代所需存储量大
? 原单纯型法有不必要的计算量
1.4.1 修正单纯型的原理
jjBj
NB
N
NB
B
NNN
NNBNB
NNB
PPCz
AC
A
ABC
BC
XACb
XABCCbBCxf
XAbBX
?
?
?
??
??
?
?
?
?
?
???
???
??
?
?
??
?
)(
)()(
)(
1
1
11
1
机会成本分量
机会成本
单纯型因子
51
1.4.1 修正单纯型的原理
? 关键是求新基的逆矩阵 B?1
– 仍然可以采用四角算法
– 混合算法
? 当前基的逆矩阵 B?1 在原单纯型表的什么位置上？
– 在初始可行基向量位置上
( AN | I ) ? ( I | AN?1 )
??
?
?
?
??
?
?
?
?
???
?
?
?
?
0)(
)(
)(
m i n
1
1
1
1
ij*
ij*
i
i
j*
jjjj
PB
PB
bB
PB
Pczc
最小比例原则
主列向量
检验数分量 ?
1999,4
运筹学
Operational Research
运筹帷幄，决胜千里
? 史记, 张良传,
2
目 录
绪 论
第一章 线性规划问题及单纯型解法
第二章 线性规划的对偶理论及其应用
第三章 运输问题数学模型及其解法
第四章 整数规划
第五章 动态规划
第六章 图与网路分析
第七章 随机服务理论概论
第八章 生灭服务系统
第九章 特殊随机服务系统
第十章 存储理论
3
绪 论
一、运筹学的起源与发展
二、运筹学的特点及研究对象
三、运筹学解决问题的方法步骤
四、运筹学的发展趋势
4
一、运筹学的起源与发展
? 起源于二次大战的一门新兴交叉学科
? 与作战问题相关
– 如雷达的设置、运输船队的护航、反潜作战中深水炸弹
的深度、飞行员的编组、军事物资的存储等
– 英国称为 Operational Research
– 美国称为 Operations Research
? 战后在经济、管理和机关学校及科研单位继续研究
– 1952年,Morse 和 Kimball出版, 运筹学方法,
– 1948年英国首先成立运筹学会
– 1952年美国成立运筹学会
– 1959年成立国际运筹学联合会 (IFORS)
– 我国于 1982年加入 IFORS，并于 1999年 8月组织了第 15
届大会
5
二、运筹学的特点及研究对象
? 运筹学的定义
– 为决策机构对所控制的业务活动作决策时，提供以数量
为基础的科学方法 ——Morse 和 Kimball
– 运筹学是把科学方法应用在指导人员、工商企业、政府
和国防等方面解决发生的各种问题，其方法是发展一个
科学的系统模式，并运用这种模式预测，比较各种决策
及其产生的后果，以帮助主管人员科学地决定工作方针
和政策 ——英国运筹学会
– 运筹学是应用分析、试验、量化的方法对经济管理系统
中人力、物力、财力等资源进行统筹安排，为决策者提
供有根据的最优方案，以实现最有效的管理 ——中国百
科全书
– 现代运筹学涵盖了一切领域的管理与优化问题，称为
Management Science
6
二、运筹学的特点及研究对象
? 运筹学的分支
– 数学规划：线性规划、非线性规划、整数规划、动态规
划、目标规划等
– 图论与网路理论
– 随机服务理论：排队论
– 存储理论
– 决策理论
– 对策论
– 系统仿真：随机模拟技术、系统动力学
– 可靠性理论
– 金融工程
7
三、运筹学解决问题的方法步骤
? 明确问题
? 建立模型
? 设计算法
? 整理数据
? 求解模型
? 评价结果
明确问题
建立模型
设计算法
整理数据
求解模型
评价结果
简化？
满意？
Yes
No
No
8
四、运筹学的发展趋势
? 运筹学的危机
– 脱离实际应用，陷入数学陷阱
? IT对运筹学的影响
– MIS,DSS,MRP-II,CIMS,ERP
– OR Dept,--> Dept,Of OR & IS
? 运筹学与行为科学结合
– 群决策和谈判
– 对策理论
– 多层规划
– 合理性分析
? 服务行业中的应用
– 金融服务业
– 信息、电信服务业
– 医院管理
9
四、运筹学的发展趋势
? 软计算
– 面向强复杂系统的计算、实时控制、知识推理
– 智能算法：模拟退火、遗传算法、人工神经网络、戒律
算法等
– 系统仿真
? 面向问题
? 后勤 (Logistics)
– 全球供应链管理
– 电子商务：集成特性
? 随机和模糊 OR
– 问题本身的不确定性
– 人类知识的局限性
10
第一章 线性规划问题及单纯型解法
1.1 线性规划问题及其一般数学模型
1.1.1 线性规划问题举例
例 1、多产品生产问题 （ Max,?）
设 x1,x2 分别代表甲、乙两种电缆的生产量，
.36)(m a x,6,2:
0,
7
8
102
..
46)(m a x:
21
21
2
21
21
21
???
?
?
?
?
?
?
?
?
?
??
??
??
xfxx
xx
x
xx
xx
ts
xxxfO B J
最优解
产量不允许为负值
产量约束
铅资源约束
铜资源约束
11
例 2、配料问题（ min,?)
原料甲 原料乙 最低含量
VA 0, 5 0, 5 2
V B 1 1, 0 0, 3 3
V B 2 0, 2 0, 6 1, 2
VD 0, 5 0, 2 2
单价 0, 3 0, 5
设 x1,x2分别代表每粒胶丸中甲、
乙两种原料的用量
12
例 3、合理下料问题
设 xj 分别代表采用切割方案 1~8的套数，
方案 2, 9 m 2, 1 m 1, 5 m 合计 余料
1 2 0 1 7, 3 0, 1
2 1 2 0 7, 1 0, 3
3 1 1 1 6, 5 0, 9
4 1 0 3 7, 4 0
5 0 3 0 6, 3 1, 1
6 0 2 2 7, 2 0, 2
根，但购买最优解为
则有零料最少若目标函数为使裁剪后
15010,50,100:
0,,,,,
10023
100232
1002
..
2.01.109.03.01.0)(m i n
,
64
654321
6431
6532
4321
654321
???
?
?
?
?
?
?
?
?
????
????
????
??????
O B Jxx
xxxxxx
xxxx
xxxx
xxxx
ts
xxxxxxxf
16 ;90,30,50,10:
0,,,,,
10023
100232
1002
..
)(i n
,
421
654321
6431
6532
4321
654321
但余料为最优解
则有钢筋最少若目标函数为使购买的
????
?
?
?
?
?
?
?
?
????
????
????
??????
O B Jxxx
xxxxxx
xxxx
xxxx
xxxx
t
xxxxxxxf
13
1.1.2 线性规划数学模型的一般表示方式
技术系数右端项价值系数
线性规划问题的规模
约束行数变量个数
,;,;:
:;,;:
0,,,
),(
),(
),(
..
)(m a x ( m i n )
21
2211
22222121
11212111
2211
ijjj
n
mnmnmm
nn
nn
nn
abc
mn
mn
xxx
bxaxaxa
bxaxaxa
bxaxaxa
ts
xcxcxcxf
?
?
?
?
?
?
?
?
?
?
?
??????
??????
??????
????
?
?
?
?
?
?
14
1,和式
?
?
?
?
?
??
??
?
?
?
?
?
njx
mibxa
ts
xcxf
j
i
n
j
jij
n
j
jj
,,2,1,0
,,2,1,
..
)(m a x
1
1
?
?
15
2,向量式
16
3,矩阵式
17
1.1.3 线性规划的图解法
1
1
8
7
6
5
4
3
2
2 x
1
876543
O
10
9
x
2
A B
C
E
D
F
G
H
1
2
3
f
(
x
)
=
0
f
(
x
)
=
12
.36)(m a x
,6,2:
0,
7
8
102
..
46)(m a x
21
21
2
21
21
21
?
??
?
?
?
?
?
?
?
?
?
??
??
??
xf
xx
xx
x
xx
xx
ts
xxxf
最优解
18
线性规划问题的几个特点：
? 线性规划问题的可性解的集合是凸集
? 线性规划问题的基础可行解一般都对应于凸集的极点
? 凸集的极点的个数是有限的
? 最优解只可能在凸集的极点上，而不可能发生在凸集
的内部
19
1.2 线性规划问题的单纯型解法
1.2.1 线性规划问题的标准形式
为了使线性规划问题的解法标准, 就要把一般形式
化为标准形式
?
?
?
?
?
????
????
?
?
?
?
?
njx
mibxa
ts
xcxf
j
i
n
j
jij
n
j
jj
,,2,1 ),,0(0
,,2,1,),(
..
)(m a x ( m i n )
1
1
?
?
不限
?
?
?
?
?
???
??
?
?
?
?
?
?
?
njmixb
mibxa
ts
xcxf
ji
i
mn
j
jij
mn
j
jj
,,2,1,,2,1,0,
,,2,1,
..
)(m a x
1
1
??
?
20
变换的方法：
? 目标函数为 min型，价值系数一律反号。令 f?(x) = -f(x)
= -CX,有 min f(x) = - max [- f(x)] = - max f ?(x)
? 第 i 个约束的 bi 为负值，则该行左右两端系数同时反号，
同时不等号也要反向
? 第 i 个约束为 ?型，在不等式左边增加一个非负的变
量 xn+i, 称为松弛变量；同时令 cn+i = 0
? 第 i 个约束为 ?型，在不等式左边减去一个非负的变
量 xn+i, 称为剩余变量；同时令 cn+i = 0
? 若 xj ?0，令 xj= -xj?,代入非标准型，则有 xj?? 0
? 若 xj ?不限，令 xj= xj? - xj?,xj?? 0,xj?? 0,代入非
标准型
21
变换举例：
?
?
?
?
?
?
?
??
???
???
???
???
0,,
200
40065
300432
..
423)(m i n:
213
321
321
321
321
xxx
xxx
xxx
xxx
ts
xxxxf
不限
原非标准型
?
?
?
?
?
?
?
????
????????
????????
????????
???????????
0,,,,,,
200
400665
3004432
..
0004423)(m a x:
6543321
63321
53321
43321
6543321
xxxxxxx
xxxxx
xxxxx
xxxxx
ts
xxxxxxxxf标准型
22
关于标准型解的若干基本概念：
? 标准型有 n+m 个变量,m 个约束行
?, 基,的概念
– 在标准型中，技术系数矩阵有 n+m 列，即
A = ( P1,P2,…,Pn+m )
– A中线性独立的 m 列，构成该标准型的一个 基,即
B = ( P1 ?,P2 ?,…,Pm ?),| B | ? 0
– P1 ?,P2 ?,…,Pm ?称为 基向量
– 与 基向量 对应的变量称为 基变量,记为
XB = ( x1 ?,x2 ?,…,xm ? )T，其余的变量称为 非基变量,
记为 XN = ( xm+1 ?,xm+2 ?,…,xm+n ? ) T,
故有 X = XB + XN
– 最多有 个基m nmC ?
23
关于标准型解的若干基本概念：
? 可行解 与 非可行解
– 满足约束条件和非负条件的解 X 称为 可行解,满足
约束条件但不满足非负条件的解 X 称为 非可行解
? 基础解
– 令 非基变量 XN = 0，求得 基变量 XB的值称为 基础解
即 XB = B?1 b
– XB 是 基础解 的 必要条件 为 XB 的非零分量个数 ? m
? 基础可行解
– 基础解 XB 的非零分量都 ? 0 时，称为 基础可行解,
否则为 基础非可行解
– 基础可行解 的非零分量个数 < m 时，称为 退化 解
24
线性规划标准型问题解的关系
约束方程的
解空间 基础解可行解
非可行解
基础
可行解
退化解
25
可行解、基础解和基础可行解举例
.36)(m a x
,6,2:
0,,,,
7
8
102
..
46)(m a x
21
54321
52
421
321
21
?
??
?
?
?
?
?
?
?
?
??
???
???
??
xf
xx
xxxxx
xx
xxx
xxx
ts
xxxf
最优解
1
1
8
7
6
5
4
3
2
2 x
1
876543
O
10
9
x
2
A B
C
E
D
F
G
H
1
2
3
f
(
x
)=
3
6
K
非基
变量
基变量
图中的点
解
x
1
,x
2
x
3
= 1 0 x
4
=8 x
5
=7 O 基础可行解
x
1
,x
3
x
2
= 1 0 x
4
= - 2 x
5
= - 3 F 基础解
x
1
,x
4
x
2
=8 x
3
=2 x
5
= - 1 E 基础解
x
1
,x
5
x
2
=7 x
3
=3 x
4
= 1 A 基础可行解
x
2
,x
3
x
1
=5 x
4
=3 x
5
= 7 D 基础可行解
x
2
,x
4
x
1
=8 x
3
= - 6 x
5
= 7 H 基础解
x
3
,x
4
x
1
=2 x
2
=6 x
5
= 1 C 基础可行解
最优解
x
3
,x
5
x
1
= 1, 5 x
2
=7 x
4
= - 0, 5 G 基础解
x
4
,x
5
x
1
=1 x
2
=7 x
3
= 1 B 基础可行解
x
1
= 2,x
2
= 2,x
3
= 4,x
4
= 4,x
5
= 3 K 可行解
26
1.2.2 单纯型法的基本思路
确定初始基础可行解
求最优解的目标函数值
确定改善方向
求新的基础可行解
检查是否为
最优解？
是
否
27
1.2.3 单纯型表及其格式
I V I I I I I I
x
1
x
2
… x
n
x
n+ 1
x
n+ 2
… x
n + m
C
B
X
B
b c
1
c
2
… c
n
c
n+ 1
c
n+ 2
… c
n + m
c
1 ?
= c
n+ 1
x
n+ 1
b
1
a
11
a
12
… a
1 n
1 0 … 0
c
2 ?
= c
n+ 2
x
n+ 2
b
2
a
21
a
22
… a
2 n
0 1 … 0
? ? ? ? ? ? ? ? ? ? ?
c
m ?
= c
n + m
x
n + m
b
m
a
m 1
a
m 2
… a
mn
0 0 … 1
O B J z
1
z
2
… z
n
z
n+ 1
z
n+ 2
… z
n + m
c
1
- z
1
c
2
- z
2
… c
n
-z
n
c
n+ 1
-z
n+ 1
c
n+ 2
-z
n+ 2
… c
n + m
-z
n + m
28
例 1.2.2 试列出下面线性规划问题的初始单纯型表
?
?
?
?
?
?
???
???
???
0,,
1 2 0233
1 0 032
..
244540)(m a x
321
321
321
321
xxx
xxx
xxx
ts
xxxxf
x
1
x
2
x
3
x
4
x
5
C
B
X
B
b 40 45 24 0 0
0 x 4 1 0 0 2 3 1 1 0
0 x 5 1 2 0 3 3 2 0 1
O B J = 0 z
j
? 0 0 0 0 0
c
j
- z
j
? 40 45 24 0 0
29
关于检验数的数学解释
? 设 B 是初始可行基，则目
标函数可写为两部分 (1)
? 约束条件也写为两部分，
经整理得 XB 的表达式 (2)，
注意 XB中含有非基变量作
参数
? 把 XB 代入目标函数，整理
得到 (3)式
? 第 j 个非基变量的机会成
本如 (4)式
? 若有 cj?zj>0,则未达到最优 ( 5 )
( 4 )
)3(
)(
)()(
( 2 ) )(
( 1 ) )(
1 '
jj
m
i ijij
NN
1
BN
1
B
NN
1
BNN
NN
1
B
NNB
BNN
BBNN
zc
acz
XABCCbBC
XAbBCXCxf
XAbBX
XAbBX
bBXXA
XCXCxf
?
?
???
???
??
??
??
??
?
?
??
?
?
检验数
机会成本
30
1.2.4 标准型的单纯型算法
1 找初始基础可行基
– 对于 (max,?)，松弛变量对应的列构成一个单位阵
– 若有 bi<0，则单位阵也不能构成一个可行基
2 检验当前基础可行解是否为最优解
– 所有检验数 cj? zj?0，则为最优解，否则
3 确定改善方向
– 从 (cj? zj) > 0 中找最大者，选中者称为 入变量, xj*
– 第 j*列称为 主列
4 确定 入变量 的最大值和 出变量
– 最小比例原则
(1, 2, 4 ) 0m i n *
* ?
?
?
?
???
? ??
ij
ij
i
i
aa b?
31
1.2.4 标准型的单纯型算法
4 确定 入变量 的最大值和 出变量
– 设第 i* 行使 ? 最小，则第 i* 行对应的基变量称为
出变量,第 i* 行称为 主行
5 迭代过程
– 主行 i* 行与 主列 j* 相交的元素 ai*j* 称为 主元,迭代
以 主元 为中心进行
– 迭代的实质是线性变换，即要将 主元 ai*j*变为 1,主
列 上其它元素变为 0，变换步骤如下：
(1)变换主行
nmjaaa jijiji ???,,2,1**** ?
32
1.2.4 标准型的单纯型算法
5 迭代过程
(2)变换主列
除 主元 保留为 1，其余都置 0
(3)变换非主行、主列元素 aij (包括 bi)
四角算法公式,
数据表示当前单纯型表中的
的数据表示上一个单纯型表中
,
( 1, 2, 5 b )
( 1, 2, 5 a )
**
**
**
**
ij
iji
ji
ijji
ijij
ji
iji
ii
a
ab
a
aa
aa
a
ab
bb
??
??
33
1.2.4 标准型的单纯型算法
5、迭代过程
(4)变换 CB,XB
(5)计算目标函数、机会成本 zj 和检验数 cj ? zj
6,返回步骤 2
a
ij
a
i * j
a
i j *
a
i * j *主行
主
列
主元
四角算法图示
34
表 1.2.4 例 1.2.2 单纯型表的迭代过程
x 1 x 2 x 3 x 4 x 5序
号 C B X B b 40 45 24 0 0 b i / a ij *
0 x 4 100 2 ( 3 ) 1 1 0 ( 3 3, 3 )
0 x 5 120 3 3 2 0 1 40
O B J = 0 0 0 0 0 0
I
初
始
解 c j - z j? 40 45 24 0 0
45 x 2 1 0 0 / 3 2 / 3 1 1 / 3 1 / 3 0 50
0 x 5 20 ( 1 ) 0 1 ? 1 1 ( 2 0 )
O B J = 1 5 0 0 30 45 15 15 0
II
c j - z j? 10 0 9 ? 15 0
45 x 2 20 0 1 ? 1 / 3 1 ? 2 / 3
40 x 1 20 1 0 1 ? 1 1
O B J = 1 7 0 0 40 45 25 5 10
I I I
最
优
解 c j - z j? 0 0 ? 1 ? 5 ? 10
答：最优解为 x1=20,x2=20,x3=0,OBJ=1700
35
单纯型表中元素的几点说明
– 任何时候，基变量对应的列都构成一个单位矩阵
– 当前表中的 b 列表示当前基变量的解值，通过变换
B ?1 b 得到 (资源已变成产品 )
– 当前非基变量对应的向量可通过变换 B ?1 AN 得到，
表示第 j 个变量对第 i 行对应的基变量的消耗率
– 非基变量的机会成本由 给出
– 注意基变量所对应的行
x 1 x 2 x 3 x 4 x 5序
号 C B X B b 40 45 24 0 0 b i / a ij *
45 x 2 1 0 0 / 3 2 / 3 1 1 / 3 1 / 3 0 50
0 x 5 20 ( 1 ) 0 1 ? 1 1 ( 2 0 )
O B J = 1 5 0 0 30 45 15 15 0
I I
c j - z j? 10 0 9 ? 15 0
ija
? ?? mi ijij acz 1 '
36
1.3 人工变量的引入及其解法
1.3.1 当约束条件为, ?” 型，引入剩余变量和人工变
量
? 由于所添加的剩余变量的技术系数为 ?1，不能作为初
始可行基变量，为此引入一个人为的变量（注意，此
时约束条件已为,=”型），以便取得初始基变量，故
称为人工变量
? 由于人工变量在原问题的解中是不能存在的，应尽快
被迭代出去，因此人工变量在目标函数中对应的价值
系数应具有惩罚性，称为罚系数。罚系数的取值视解
法而定
? 两种方法
– 大 M法
– 二阶段法
37
1.3.2 大 M法的求解过程
例 1.3.1
38
表 1.3.1 例 1.3.1的单纯型表迭代过程
x 1 x 2 x 3 x 4 x 5 x 6序
号 C B X B b ? 10 ? 8 ? 7 0 0 ? M b i / a ij *
? M x 6 6 (2) 1 0 ? 1 0 1 (3)
? 7 x 3 4 1 1 1 0 ? 1 0 4
? 6 M ? 28 ? 2 M ? 7 ? M ? 7 ? 7 M 7 ? M
I
初
始
解 c j? z j? 2 M ? 3 M ? 1 0 ? M ? 7 0? 10
x 1 3 1 1 / 2 ? 1 / 2 0 1 / 2 6
? 7 x 3 1 0 ( 1 / 2 ) 1 1 / 2 ? 1 ? 1 / 2 (2)
? 37 ? 10 ? 1 7 / 2 ? 7 3 / 2 7 ? 3 / 2
II
c j? z j? 0 1 / 2 0 ? 3 / 2 ? 7 ? M + 3 / 2
? 10 x 1 2 1 0 ? 1 ? 1 1 1
? 8 x 2 2 0 1 2 1 ? 2 ? 1
? 36 ? 10 ? 8 ? 6 2 6 ? 2
I I I
最
优
解 c j? z j? 0 0 ? 1 ? 2 ? 6 ? M +2
答：最优解为 x1=2,x2=2,x3=0,OBJ=36
39
大 M法的一些说明
– 大 M法实质上与原单纯型法一样,M 可看成一个很
大的常数
– 人工变量被迭代出去后一般就不会再成为基变量
– 当检验数都满足最优条件，但基变量中仍有人工变
量，说明原线性规划问题 无可行解
– 大 M法手算很不方便
– 因此提出了二阶段法
? 计算机中常用大 M法
? 二阶段法手算可能容易
40
1.3.3 二阶段法的求解过程
? 第一阶段的任务是将人工变量尽快迭代出去，从而
找到一个没有人工变量的基础可行解
? 第二阶段以第一阶段得到的基础可行解为初始解，
采用原单纯型法求解
? 若第一阶段结束时，人工变量仍在基变量中，则原
问题无解
? 为了简化计算，在第一阶段重新定义价值系数如下：
?
?
?
?
??
?
?
?
?
?
不是人工变量时当
为人工变量时当
时目标函数为
不是人工变量时当
为人工变量时当
时目标函数为
jj
jj
jj
jj
xc
xc
xc
xc
0
1
m a x
0
1
m i n
41
表 1.3.2 用二阶段法求解例 1.3.1的第一阶段
x 1 x 2 x 3 x 4 x 5 x 6序
号 C B X B b 0 0 0 0 0 ? 1 b i / a ij *
? 1 x 6 6 ( 2 ) 1 0 ? 1 0 1 ( 3 )
0 x 3 4 1 1 1 0 ? 1 0 4
? 6 ? 2 ? 1 0 1 0 ? 1
I
c j? z j? 2 1 0 ? 1 0 0
0 x 1 3 1 1 / 2 0 ? 1 / 2 0 1 / 2
0 x 3 1 0 1 / 2 1 1 / 2 ? 1 ? 1 / 2
0 0 0 0 0 0 0
II
c j? z j? 0 0 0 0 0 ? 1
42
表 1.3.2 用二阶段法求解例 1.3.1的第二阶段
x 1 x 2 x 3 x 4 x 5序
号 C B X B b ? 10 ? 8 ? 7 0 0 b i / a ij *
? 10 x 1 3 1 1 / 2 0 ? 1 / 2 0 6
? 7 x 3 1 0 ( 1 / 2 ) 1 1 / 2 ? 1 ( 2 )
? 37 ? 10 ? 1 7 / 2 ? 7 3 / 2 7
I
c j? z j? 0 1 / 2 0 ? 3 / 2 ? 7
? 10 x 1 2 1 0 ? 1 ? 1 1
? 8 x 2 2 0 1 2 1 ? 2
? 36 ? 10 ? 8 ? 6 2 6
II
c j? z j? 0 0 ? 1 ? 2 ? 6
最优解对应的 B–1在哪？
43
1.5 单纯型法的一些具体问题
1.5.1 关于无界解问题
– 可行区域不闭合 (约束条件有问题 )
– 单纯型表中入变量 xj* 对应的列中所有
0a *ij ?
?
?
?
?
?
?
??
???
??
0,
50
1 0 02
..
)(m a x
1.5.1
21
21
21
21
xx
xx
xx
ts
xxxf
例
f ( x ) =x
1
+x
2
x
1
x
2
50? 50
? 50
1 0 0
x
1
-x
2
=5 0
- 2 x
1
+x
2
=1 0 0
44
表 1.5.1 例 1.5.1 的单纯型表及其迭代过程
x
1
x
2
x
3
x
4序
号
C
B
X
B
b 1 1 0 0 b
i
/ a
ij *
0 x 3 100 ? 2 1 1 0 ??
0 x 4 50 (1) ? 1 0 1 (50)
O B J = 0 0 0 0 0
I
初
始
解 c
j
- z
j
? 1 1 0 0
0 x 3 200 ? ? 1 1 2
1 x 1 50 1 ? 1 0 1
O B J = 5 0 1 ?? 0 1
II
c
j
- z
j
? 0 2 0 ??
?
45
1.5.2 关于退化问题
– 退化问题的原因很复杂，当原问题存在平衡约束时
– 当单纯型表中同时有多个基变量可选作出变量时
– 退化的严重性在于可能导致死循环，克服死循环的
方法有“字典序”法
?
?
?
?
?
?
?
?
??
??
??
??
0,
0
602
40
..
43)(m a x
1, 5, 2
21
21
21
21
21
xx
xx
xx
xx
ts
xxxf
例
x
1
x
2
x
3
x
4序
号
C
B
X
B
b 3 4 0 0 b
i
/ a
ij *
0 x
3
40 ? (2) 1 0 (20)
0 x
4
60 0 ??? 0 1 (20)
3 x
1
0 1 ?? 0 0 ??
O B J = 0 3 ? 3 0 0
II
c
j
- z
j
? 0 7 0 0
4 x
2
20 ? 1 1 / 2 0
0 x
4
0 0 ? ? 3 / 2 1
3 x
1
20 1 ? 1 / 2 0
O B J = 1 4 0 3 ? 3, 5 0
III
c
j
- z
j
? 0 0 ? 3, 5 ?
46
1.5.3 关于多重解问题
– 多个基础可行解都是最优解，这些解在同一个超平
面上，且该平面与目标函数等值面平行
– 最优单纯型表中有非基变量的检验数为 0
– 最优解的线性组合仍是最优解，即 X=aX1+bX2，
a+b=1
?
?
?
?
?
?
???
???
???
0,,
1 2 0233
1 0 032
..
254540)(m a x
1, 5, 3
321
321
321
321
xxx
xxx
xxx
ts
xxxxf
多重最优解例
47
表 1.5.3 例 1.5.3 的单纯型表及其迭代过程
x 1 x 2 x 3 x 4 x 5序
号 C B X B b 40 45 25 0 0 b i / a ij *
0 x 4 100 2 ( 3 ) 1 1 0 ( 3 3, 3 )
0 x 5 120 3 3 2 0 1 40
O B J = 0 0 0 0 0 0
I
初
始
解 c j - z j? 40 45 25 0 0
?
迭代 过程
45 x 2 20 0 1 ? 1 / 3 1 ? 2 / 3 ??
40 x 1 20 1 0 ( 1 ) ? 1 1 ( 2 0 )
O B J = 1 7 0 0 40 45 25 5 10
I I I
最
优
解 c
j - z j? 0 0 0 ? 5 ? 10
45 x 2 2 6,67 1 / 3 1 0 2 / 3 ? 1 / 3
25 x 3 20 1 0 1 ? 1 1
O B J = 1 7 0 0 40 45 25 5 10
I V
最
优
解 c
j - z j? 0 0 0 ? 5 ? 10
48
1.5.4 关于无可行解问题
– 约束条件互相矛盾，无可行域
– 单纯型表达到最优解检验条件时，人工变量仍在基
变量中
?
?
?
?
?
?
?
?
????
???
???
???
0,,
1
2
12
..
2)(m a x
1, 5, 4
321
321
321
321
321
xxx
xxx
xxx
xxx
ts
xxxxf
例
49
表 1.5.4 例 1.5.4 第一阶段的单纯型表
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9序
号 C B X B b 0 0 0 0 0 0 ? 1 ? 1 ? 1 b i / a ij *
? 1 x 7 1 1 1 (2) ? 1 0 0 1 0 0 ( 1 / 2 )
? 1 x 8 2 1 ? 1 ? 1 0 ? 1 0 0 1 0 ?
? 1 x 9 1 ? 1 1 1 0 0 ? 1 0 0 1 1
O B J = ? 4 ? 1 ? 1 ? 2 1 1 1 ? 1 ? 1 ? 1
I
初
始
解
c
j
- z
j
? 1 1 2 ? 1 ? 1 ? 1 0 0 0
? x 3 1 / 2 1 / 2 1 / 2 1 - 1 / 2 0 0 1 / 2 0 0
? 1 x 8 5 / 2 3 / 2 - 1 / 2 ? - 1 / 2 ? 1 0 1 / 2 1 0
? 1 x 9 1 / 2 - 3 / 2 1 / 2 0 1 / 2 0 ? 1 - 1 / 2 0 1
O B J = ? 3 ? ? ? 0 1 1 0 ? 1 ? 1
II
c j - z j? 0 0 0 ? ? 1 ? 1 ? 1 0 0
50
1.4 修正单纯型法
? 原单纯型法迭代所需存储量大
? 原单纯型法有不必要的计算量
1.4.1 修正单纯型的原理
jjBj
NB
N
NB
B
NNN
NNBNB
NNB
PPCz
AC
A
ABC
BC
XACb
XABCCbBCxf
XAbBX
?
?
?
??
??
?
?
?
?
?
???
???
??
?
?
??
?
)(
)()(
)(
1
1
11
1
机会成本分量
机会成本
单纯型因子
51
1.4.1 修正单纯型的原理
? 关键是求新基的逆矩阵 B?1
– 仍然可以采用四角算法
– 混合算法
? 当前基的逆矩阵 B?1 在原单纯型表的什么位置上？
– 在初始可行基向量位置上
( AN | I ) ? ( I | AN?1 )
??
?
?
?
??
?
?
?
?
???
?
?
?
?
0)(
)(
)(
m i n
1
1
1
1
ij*
ij*
i
i
j*
jjjj
PB
PB
bB
PB
Pczc
最小比例原则
主列向量
检验数分量 ?
