运 筹 学
黑龙江工程学院数学系
吴 昶
课程简介
课程名称,运筹学
英文名称,Operations Research(缩写 O.R.)
运筹学,主要研究经济活动与军事活动中
能用数量来表达有关运用、筹划与管理方
面的问题，它根据问题的要求，通过数学
的分析与运算，作出综合性的合理安排，
以达到较经济较有效地使用人力。
运筹帷幄之中，决胜千里之外
教学内容,
第一章 线性规划及单纯形法
第二章 线性规划的对偶理论
第三章 运输问题
第四章 整数规划与分配问题
第五章 目标规划
第八章 动态规划
教学时数,3× 13=39
教材及主要参考书,
教材,胡运权，运筹学，哈尔滨工业大学
出版社。
参考书,运筹学教材编写组，运筹学，清
华大学出版社。
§ 1．一般线性规划问题的数学模型
§ 2．图解法
§ 3．单纯形法原理
§ 4．单纯形法的计算步骤
§ 5．单纯形法的进一步讨论
§ 6．改进单纯形法
§ 7．应用举例及 Matlab求解方法
第一章 线性规划及单纯形法
一、问题的提出
某企业计划生产 Ⅰ, Ⅱ 两种产品。这两种产
品都要分别在 A,B,C,D四种不同设备上加工。
生产每件产品 Ⅰ 需占用各设备分别为 2,1,4、
0h，生产每件产品 Ⅱ,需占用各设备分别为 2,2、
0,4h。已知各设备计划期内用于生产这两种产
品的能力分别为 12,8,16,12h，又知每生产一
件产品 Ⅰ 企业能获得 2元利润，每生产一件产品
Ⅱ 企业能获得 3元利润，问企业应安排生产两种
产品各多少件，使总的利润收入为最大。
§ 1．一般线性规划问题的数学模型
产品 Ⅰ 产品 Ⅱ 计划期内 生产能力
A 2 2 12
B 1 2 8
C 4 0 16
D 0 4 12
利润 2 3 MAX
需满足条件,
实现目的,
?
?
?
?
?
?
?
?
?
?
?
?
??
??
0,
12 4
16 4
82
1222
21
2
1
21
21
xx
x
x
xx
xx
m a x 32 21 ??? xxz
二、线性规划问题的数学模型
三个组成要素,
1.决策变量,是决策者为实现规划目标采取
的方案、措施，是问题中要确定的未知量。
2.目标函数,指问题要达到的目的要求，表
示为决策变量的函数。
3.约束条件,指决策变量取值时受到的各种
可用资源的限制，表示为含决策变量的等式
或不等式。
一般线性规划问题的数学模型,
?
?
?
?
?
?
?
?
?
?
??????
??????
??????
0,,,
,
,
,
21
2211
22222121
11212111
n
mnmnmm
nn
nn
xxx
bxaxaxa
bxaxaxa
bxaxaxa
?
?
????????????
?
?
）（或
）（或
）（或
目标函数,
约束条件,
nn xcxcxcz ???? ?2211m i nm a x ）（或
简写形式,
?
?
?
?
?
??
????
?
?
?
?
?
），，（
），，（），（或
）（或
njx
mibxa
xcz
j
i
n
j
jij
n
j
jj
?
?
1 0
1
m inm a x
1
1
矩阵形式表示为,
?
?
?
?
???
?
0
m i nm a x
X
AX
CXz
），（或
）（或
其中,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
nnnn
n
n
aaa
aaa
aaa
A
?
???
?
?
21
22221
11211? ?
ncccC,,,21 ??
? ?TnxxxX,,,21 ??
? ?Tnbbbb,,,21 ??
三、线性规划问题的标准形式
标准形式,
?
?
?
?
?
??
??
?
?
?
?
?
），，（
），，（
njx
mibxa
xcz
j
i
n
j
jij
n
j
jj
?
?
1 0
1
m a x
1
1
标准形式特点,
4,决策变量取值非负。
1,目标函数为求极大值；
2,约束条件全为等式；
3,约束条件右端常数项全为非负值；
一般线性规划问题如何化为标准型,
1,目标函数求极小值,
?
?
?
n
j
jj xcz
1
m in
令：,即化为,zz ??'
? ???
??
????
?????
n
j
jj
n
j
jj xcxc
zzz
11
m in)m a x (m a x
2,约束条件为不等式,
（ 1）当约束条件为,≤”时
如,1222
21 ?? xx
可令：, 显然
1222 321 ??? xxx 03 ?x
（ 2）当约束条件为,≥”时
如,181210
21 ?? xx
可令：, 显然 0
4 ?x181210 421 ??? xxx
称为 松弛变量。
3x
称为 剩余变量 。 4x
松弛变量和剩余变量统称为松弛变量
（ 3）目标函数中松弛变量的系数
由于松弛变量和剩余变量分别表示未被充分利
用的资源以及超用的资源，都没有转化为价值和利
润，因此 在目标函数中系数为零 。
3,取值无约束的变量
如果变量 x 代表某产品当年计划数与上
一年计划数之差，显然 x 的取值可能是正也
可能是负，这时可令,
xxx ?????
其中,00 ????? xx,
令
4,变量 xj≤0
jj xx ???
，显然
0??jx
例, 将下述线性规划模型化为标准型
?
?
?
?
?
?
?
??
????
????
????
???
取值无约束
321
321
321
321
321
,0,0
6323
42 3
9 2
32m i n
xxx
xxx
xxx
xxx
xxxz
解,令,，
11 xxzz ??????
? ?00 33333 ?????????? xxxxx,，
得标准形式为,
?
?
?
?
?
?
?
?????
????????
?????????
?????????
???????????
0
6 3323
4 22 3
9 2
00332m a x
543321
3321
53321
43321
543321
xxxxxx
xxxx
xxxxx
xxxxx
xxxxxxz
，，，，，
四、线性规划问题的解
可行解,满足约束条件的解称为 可行解,可行解的集
合称为 可行域 。
最优解,使目标函数达到最大值的可行解。
基,约束方程组的一个满秩子矩阵称为规划问题的一
个 基,基中的每一个列向量称为 基向量,与基向量对应
的变量称为 基变量,其他变量称为 非基变量 。
基解,在约束方程组中，令所有非基变量为 0，可以
解出基变量的唯一解，这组解与非基变量的 0共同构成
基解 。
基可行解,满足变量非负的基解称为 基可行解
可行基,对应于基可行解的基称为 可行基
求解线性规划问题,
就是从满足约束方程组和约束不等式的决策变量取
值中，找出使得目标函数达到最大的值。
?
?
?
?
?
??
??
?
?
?
?
?
），，（
），，（
njx
mibxa
xcz
j
i
n
j
jij
n
j
jj
?
?
1 0
1
m a x
1
1
为了便于建立 n 维空间中线性规划问题的
概念及便于理解求解一般线性规划问题的单纯
形法的思路，先介绍图解法。
求解下述线性规划问题,
?
?
?
?
?
?
?
?
?
?
?
?
??
??
0,
12 4
16 4
82
1222
21
2
1
21
21
xx
x
x
xx
xx
21 32m a x xxz ??
§ 2,线性规划问题的图解法
画出线性规划问题的可行域,
目标函数的几何意义,
最优解的确定,
图解法的步骤,
1,建立坐标系，将约束条件在图上表示；
2,确立满足约束条件的解的范围；
3,绘制出目标函数的图形；
4,确定最优解。
无穷多最优解的情况,
目标函数与某个约束条件恰好平行
无界解（或无最优解）的情况,
可行域上方无界
无可行解的情况,
约束条件不存在公共范围
图解法的启示,
1,求解线性规划问题时，解的情况有：唯一最
优解，无穷多最优解，无界界，无可行解；
2,若线性规划问题可行域存在，在可行域是一
个凸集；
3,若线性规划问题最优解存在，在最优解或最
优解之一一定能够在可行域的某个顶点取得；
4,解题思路是，先找凸集的任一顶点，计算其
目标函数值。比较其相邻顶点函数值，若更
优，则逐点转移，直到找到最优解。
§ 3．单纯形法原理
凸集,如果集合 C 中任意两个点,其连线上
的所有点也都是集合 C 中的点。
21,XX
上图中（ 1）（ 2）是凸集，（ 3）（ 4）不是凸集
顶点,如果对于凸集 C 中的点 X,不存在 C 中的任
意其它两个不同的点,使得 X 在它们的连线上，
这时称 X 为凸集的顶点。
21 XX,
一、线性规划问题基本定理
定理一 若线性规划问题存在可行解，则问题的可行
域是凸集。
定理二 线性规划问题的基本可行解 X 对应线性规划
问题可行域（凸集）的顶点。
定理三 若线性规划问题有最优解，一定存在一个基
可行解是最优解。
从上述三个定理可以看出，要求线性规划问
题的最优解，只要比较可行域（凸集）各个
顶点对应的目标函数值即可，最大的就是我
们所要求的最优解。
二、确定初始基可行解
线性规划问题的最优解一定会在基可行解中取得，我
们先找到一个初始基可行解。然后设法转换到另一个
基可行解，直到找到最优解为止。
设给定线性规划问题,
?
?
?
?
?
??
??
?
?
?
?
?
），，（
），，（
njx
mibxa
xcz
j
i
n
j
jij
n
j
jj
?
?
1 0
1
m a x
1
1
因此约束方程组的系数矩阵为,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
100
010
001
21
22221
11211
??
????????
??
??
mnmm
n
n
aaa
aaa
aaa
由于该矩阵含有一个单位子矩阵，因此，一这个单位
阵做基，就可以求出一个基可行解,
? ?TmbbX,,,0,,0 1 ???
其标准形为,
?
?
?
?
?
??
???
??
?
??
?
??
），，（
），，（
njx
mibxxa
xxcz
j
isi
n
j
jij
m
i
si
n
j
jj
?
?
1 0
1
0m a x
1
11
三、从初始基可行解转换为
另一个基可行解
对初始可行解的系数矩阵进行初等行
变换，构造出一个新的单位矩阵，其各列
所对应的变量即为一组新的基变量，求出
其数值，就是一个新的基可行解。
四、最优性检验和解的判别
设基可行解 ? ?
T
nxxxX
00
2
0
1
)0(,,,??
令 ?
?
??
m
i
ijijj acc
1
?,其中 随基的改变而改变 ija
lj
l
ij
ij
i
i a
xa
a
x 00 0m in ?
??
?
?
?
??
?
?
?
???
1,当所有 时，现有顶点对应的基可行解即为最
优解。
2,当所有 时，又对某个非基变量 有
且可以找到,则该线性规划问题有无穷多最
优解。
3,如果存在某个,又 向量的所有分量,
对任意,恒有,则存在无界解。
0?j?
0?j? ix 0?i?
0??
0?j? jP 0?ija
0?? ? ? 00 ?? iji ax ?
§ 4．单纯形法的计算步骤
第一步：求初始可行解，列初始单纯形表
1,表中最上端一行是各变量在目标函数中的系数,
最左端一列是各基变量在目标函数中的系数值。
2,表中最后一行就是检验数 。
j?
第二步：进行最优性检验
如果表中，所有检验数,则表中
的基可行解就是问题的最优解，计算到此为
止，否则转入下一步。
0?j?
第三步：转换到新的基可行解,
构造新单纯形表
1,确定换入变量
取使得 ? ?
0m a x ?? jjjk ???
所对应的 作为换入基的变量。
kx
2,确定换出变量
取使得
lk
l
ik
ik
i
a
ba
a
b ?
?
?
?
?
?
?
?? 0m a x?
所对应的 作为换入基的变量。
lx
3,用换入变量替换换出变量，做新单纯形表
（ 1）
klll abb ?? ? ?lia
a
bbb
ik
kl
l
ii ?????
（ 2）
kljljl aaa ?? ? ?lia
a
a
aa ik
kl
jl
ijij ?????
（ 3）检验数 的求法与初始单纯形表中求法相同
j?
第四步：重复第二、三步直到计算结束
例 5 用单纯形法求解线性规划问题
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
0,
124
16 4
82
1222
32m a x
21
2
1
21
21
21
xx
x
x
xx
xx
xxz
解,将原线性规划问题化为标准型
?
?
?
?
?
?
?
?
?
?
??
??
???
???
??????
0,
12 4
16 4
8 2
12 22
000032m a x
21
62
51
421
321
654321
xx
xx
xx
xxx
xxx
xxxxxxz
第一步,
取系数矩阵中单位阵部分为基，得初始基可行解
? ?TX 12,16,8,12,0,0?
列出初始单纯形表
第二步,
由于,都大于零，因此，目前没有得
到最优解。
32 ?? 21 ??
在大于零的检验数中，由于,且 3
2 ?? 21 ?? 12
?? ?
所以 为换入变量。
2x
第三步,
由于
3412412,,28,812m i n ???
?
??
?
? ???
所以确定 为换出变量
6x
1,确定换入变量
2,确定换出变量
3,作新单纯形表
第四步,由于还存在检验数,因此重复上述步骤。 0
1 ??
由于上表中所有检验数都小于等于零，因此已经
得到最优解，最优解为,
400024 654321 ?????? xxxxxx,，，，，
代入目标函数得最优值,14?z
当计算检验数有相同值的时候，可从中任选一个变量
作为换入变量。
当计算 值出现相同时，也可以从中任选一个作为换
出变量
?
注意,
§ 5．单纯形法的进一步讨论
一、人工变量法
考察上一节例 5中的线性规划问题,
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
0,
124
16 4
82
1222
32m a x
21
2
1
21
21
21
xx
x
x
xx
xx
xxz
化标准形为,
?
?
?
?
?
?
?
?
?
?
??
??
???
???
??????
0,
12 4
16 4
8 2
12 22
000032m a x
21
62
51
421
321
654321
xx
xx
xx
xxx
xxx
xxxxxxz
它的系数矩阵是,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
100040
010004
001021
000122
由于 系数矩阵中存在单位阵,很容易找到初始可行
基。但存在着不同的情况，考察下面的线性规划问题,
化为标准型,
?
?
?
?
?
?
?
?
??
?????
????
?????
0,,,,
9 3
1 2
4
003m a x
54321
32
5321
4321
5431
xxxxx
xx
xxxx
xxxx
xxxxz
?
?
?
?
?
?
?
?
??
????
???
???
0,,
93
1 2
4
3m a x
321
32
321
321
31
xxx
xx
xxx
xxx
xxz
例 6
该问题的系数矩阵为,
?
?
?
?
?
?
?
?
?
?
???
00130
10112
01111
54321
PPPPP
这个矩阵中不含有单位矩阵，因此很难找到初始基。
对于这种线性规划问题的系数矩阵不含有单位
矩阵的情况，我们往往采用添加 人工变量 的方法，
来认为构造一个单位矩阵。这样的方法就是 人工
变量法 。
为了构造出单位矩阵，在系数矩阵中添加两列单位
列向量，系数矩阵变为,
?
?
?
?
?
?
?
?
?
?
???
1000130
0110112
0001111
7654321
PPPPPPP
线性规划问题的约束条件就变为,
?
?
?
?
?
?
?
?
???
?????
????
0,,,,,,
9 3
1 - 2
4
7654321
732
65321
4321
xxxxxxx
xxx
xxxxx
xxxx
因为, 是人为添加的，因此其对应的变量,
称为 人工变量 。
6P 7P 6x 7x
目标函数中人工变量的系数,
添加人工变量前，在线性规划问题的标准形中，
各约束条件已经是等式约束了，因此为了保证等式约
束满足不变，在最优解中，人工变量的取值必须为 0。
为此，令目标函数中人工变量的系数为 任意大的
一个负值,用,”来表示，这样，只要人工变量
取值不为零，则目标函数就不能达到极大化。
M?
目标函数变为,
765431 003m a x MxMxxxxxz ???????
添加 M 来处理人工变量的方法，称为大 M 法
求解过程,
因此最优解为,T
X ?
?
??
?
?? 0,0,0,0,
2
3,
2
5,0
2
3m a x ?z
二、两阶段法
用大 M 处理人工变量时，用计算机求解会出现
错误，由此产生了两阶段法。
第一阶段：先求解一个目标函数中只含有人工
变量的线性规划问题。
即令目标函数中其它变量的系数取零，人工变
量的系数取某个正的常数（一般取 1），在保持原问
题约束条件不变的情况下求这个目标函数极小化时
的解。
第二阶段：从第一阶段的最终单纯形表出发，
去掉人工变量，按原问题的目标函数，继续寻找原
问题的最优解。
三、关于解的判别
1,当所有 时，又对某个非基变量 有
且可以找到,则该线性规划问题有无穷
多最优解。
0?j? ix 0?i?
0??
例 7,求解线性规划问题
?
?
?
?
?
?
?
?
?
?
?
?
??
??
0,
12 4
16 4
82
1222
21
2
1
21
21
xx
x
x
xx
xx
21 42m a x xxz ??
解,在图解法中，我们知道这个问题有无穷多解。
它的标准形为,
? ??
?
?
?
?
?
?
?
?
??
??
??
???
???
6,,2,10
12 4
16 4
8 2
12 22
62
51
421
321
?jx
xx
xx
xxx
xxx
j
654321 000042m a x xxxxxxz ??????
用单纯形法计算，得到最终单纯形表为,
从表中可以得到最优解,? ?
TX 0,8,0,2,3,21 ?
它对应的目标函数值为,14?z
在上表中，非基变量 的检验数为 0，如果将
换入基变量，得,6x6x
从表中可以得到新的最优解,? ?
TX 4,0,0,0,2,42 ?
它对应的目标函数值为,14?z
因此 和 连线上所有的点都是最优解，该
问题有无穷多最优解。
1X 2X
例 8,求解线性规划问题
?
?
?
?
?
0,
16 4
21
1
xx
x
21 32m a x xxz ??
解：用图解法求解时知道该问题有无界解,
它的标准形为,
?
?
?
?
??
0,,
16 4
321
31
xxx
xx
321 032m ax xxxz ???
用单纯形表求解过程如下,
表中,但 列数字为零，因此 的取
值可无限增大，所以目标函数值也可随之无限增
大，说明问题的解无界。
02 ?? 2x
例 9,求解线性规划问题
?
?
?
?
?
?
??
??
0,
142
1222
21
21
21
xx
xx
xx
21 32m a x xxz ??
解：利用图解法，我们已经知道该问题无可行解,
将其化为标准形,
? ???
?
?
?
??
????
???
5,4,3,2,10
14 2
12 22
5421
321
jx
xxxx
xxx
j
54321 0032m ax Mxxxxxz ?????
该问题单纯形法求解如下,
当所有 时，人工变量 仍然留在基变量中，
而且不为零，故问题无可行解。
0?j? 5x
四、单纯形法小结
1,对给定的线性规划问题应首先化为标准形式；
2,选取或构造一个单位矩阵作为基；
3,求出初始可行解并列出初始单纯形表；
4,计算检验数，判断是否最优解；
5,寻找换入及换出变量，构造新的单纯形表；
6,求出最优解。
化为标准形式、构造基及单纯形法计算步
骤见教材 。
28P
§ 6．改进单纯形法
用矩阵形式描述线性规划的标准形式为,
?
?
?
?
?
?
0
m a x
X
bAX
CXz
由于在转化成标准形时，总可以构造一个单位矩
阵作为初始单纯形表中的基。
因此将矩阵 A 分成作为 初始基的单位矩阵 I 和
非基变量系数矩阵 N 两块。
把 新单纯形表中的基（新表中的 I ），对应的
初始单纯形表中的那些向量 抽出来，单独列成一块，
用 B 表示。
初始单纯形表可以改写为,
单纯形法的迭代计算实际上就是对约束方程系数矩阵
实施的初等变换 。 对矩阵 （ b | B | N | I） 实施初等变
换时, 当 B 变为 I, I 将变换为 B-1。 因此, 上述矩阵
变为 （ B-1 b | I | B-1 N | B-1 ）,新单纯形表可写为,
显然,bBb
1???
NBN 1???
jj PBP 1???
? ? 111 0,,?? ???????? BCBCyyY BBm?
NBCCNCC BNBNN 1????????
jBjjBjj PBCcPCc 1????????
01 ???? ? BBCC BBI?
利用这些公式，我们来研究改进单纯形法
改进单纯形法的步骤,
1,在下一步迭代的基变量确定后，新基可行解为,
2,计算非基变量的检验数 和
3,产生 列的数字，有,如,线
性规划问题有无界解，计算结束。否则寻找换出
变量,
4,用非基变量 替换基变量,的出下一步中的
基变量。
5,重复上述步骤，直到计算结束。
bBX B 1??
NBCC BNN 1?????
1???? BCY BkP?
kk PBP 1??? 0??kP
? ?
? ? ? ?
? ?
? ? lk
l
ik
ik
i
i PB
bBPB
PB
bB
1
1
1
1
1
0m in ?
?
?
?
?
?
??
?
?
?
??
?
?
?
???
kx lx
B-1的求法,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
10
010
01
1
??
???
??
???
??
lkmk
lk
lkk
aa
a
aa
D
令
将 D 左乘迭代前的基的逆矩阵,就得到迭
代后基的逆矩阵 。
1?oldB
1?newB
例 10,用改进单纯形法求解
?
?
?
?
?
?
?
?
??
??
???
??
0,
15 3
9
62
24m a x
21
21
21
21
21
xx
xx
xx
xx
xxz
解：其标准形为
?
?
?
?
?
?
?
?
???
???
????
?????
0,,
15 3
9
6 2
00024m a x
51
521
421
321
54321
xx
xxx
xxx
xxx
xxxxxz
?
因此
?
?
?
?
?
?
?
?
?
?
?
?
?
13
11
21
N
?
?
?
?
?
?
?
?
?
?
?
15
9
6
b
（ 1）确定初始解
? ? ? ?0,0,0,,543 ?? cccC B
? ? ? ?2,4,21 ?? ccC N
找出约束条件中的单位矩阵 I 作为基，初始解,
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
15
9
6
5
4
3
b
x
x
x
X B
,
非基变量检验数,? ? ? ?
2,4,21 ???? ??? NCC BNN
因此 是换入变量,且
?
?
?
?
?
?
?
?
?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
3
1
1
31
21
11
1
a
a
a
P1x 1?k
5315315,19,m in ??
??
?
??
? ???由于
因此 是换出变量,。
5x 3?l
且 3
31 ?? aa lk
在基变量中,表示的是第三行。
5x
（ 2）第一次迭代
新的基变量,? ?T
B xxxX 143,,?
逆矩阵
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
3100
3110
3101
100
010
001
3100
3110
3101
100
010
001
100
10
01
31
3121
3111
1
a
aa
aa
B
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
?
?
?
?
?
?
?
?
?
? ?
5
4
11
15
9
6
3100
3110
3101
1
1
4
3
2
BB XB
x
x
x
X
? ? ? ?4,0,0,,1432 ?? cccC B
N’ 中只对应变元,因此
2x
? ?
3
10
1
1
2
3100
3110
3101
4,0,02
2
1
2
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
???
?
PBCc
BN
?
? ?
3
4
31
31
31
4,0,051 ??
?
?
?
?
?
?
?
?
?
?
?????? ? PBCY B
最大正检验数为 10/3，即 为换入变量，又 2x
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
??
31
34
35
1
1
2
3100
3110
3101
2P
3,3,
5
33m in ?
??
?
??
? ???
所以 为换出变量。
4x
（ 3）第二次迭代
新的基变量为,
? ?TB xxxX 1233,,?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
??
41410
41430
43451
3100
3110
3101
1410
0430
0451
1B
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
6
3
6
15
9
6
41410
41430
43451
1
2
3
3
x
x
x
X B
? ?4,2,0?BC 0
2
1,
4
10 ??
?
??
?
? ???
N?
因为所有检验数为零，所以最优解为,? ?
0,0,6,3,6?X
§ 7,应用举例及 Matlab求解法
例 11,工业原料的合理利用
要制作 100套钢筋架子，每套有长 2.9m,2.1m和
1.5m的钢筋各一根。已知原料长 7.4m，应如何切割，
使用原料最节省（仍掉的料头最小）。
考察如下方案的综合使用,
解,该问题的线性规划数学模型如下
? ??
?
?
?
?
?
?
??
????
???
???
????
5,,10
1 0 03 2 3
1 0 0 22
1 0 0 2
8.03.02.01.0m in
5321
543
421
5432
?jx
xxxx
xxx
xxx
xxxxz
j
该问题要用单纯形法求解，需要添加人工变量,
? ??
?
?
?
?
?
?
??
?????
????
????
????????
8,,10
1 0 0 3 2 3
1 0 0 22
1 0 0 2
8.03.02.01.0m a x
85321
7543
6421
8765432
?jx
xxxxx
xxxx
xxxx
MxMxMxxxxxz
j
下面我们考虑如何用 Matlab 语言来求解线性规划问题
在 Matlab 语言中，标准输入形式要求目标函数为极
小，约束条件为等于或小于等于，并使用矩阵或列向量
的形式给出，其标准形为,
?
?
?
?
?
??
?
?
UXL
BXA
BXA
XC
T
22
11
m i n
利用大 M 法求解，得到,
? ?TX 0,0,0,0,50,0,10,30? 16m i n ?z
上述线性规划问题,
? ??
?
?
?
?
?
?
??
????
???
???
????
5,,10
1 0 03 2 3
1 0 0 22
1 0 0 2
8.03.02.01.0m in
5321
543
421
5432
?jx
xxxx
xxx
xxx
xxxxz
j
用 Matlab 语言来改写，则有,
? ?8.0,3.0,2.0,1.0,0?TC ? ?TB 100,100,1001 ?
?
?
?
?
?
?
?
?
?
?
?
30213
12200
01021
A
? ?TxxxxxX 54321,,,,?
在 Matlab 语言中，以矩阵作为基本计算单位，向量
可以看作是矩阵的特殊情况，用“；”表示矩阵的
分行，用“，”表示两个元素的分隔，用,[ ]”表示
矩阵整体。
利用 Matlab 进行线性规划问题求解的命令格式为,
X=lp(c,A,b,XLB,XUB,x0,nEq)
在上述式子中,
c 是目标函数中的系数向量；
A 为约束方程组（不等式组）的系数矩阵；
b 为约束方程组（不等式组）的右端列向量；
XLB 为决策向量 X 的下限；
XUB 为决策向量 X 的上限；
x0 为决策向量 X 的初值；
nEq 为约束方程中等式的个数。
各参量在 Matlab 命令中使用的名称可以根据
需要而不同，但是出现的顺序不能发生改变。
对于前述的线性规划问题，我们已经给出
了 c,A,b，并且我们知道约束条件中等式有
三个，即 nEq=3，但是我们还没有给出决策向
量的上限、下限和初值。
决策向量的上限、下限和初值我们可以根
据实际情况自己进行估计，在该问题中，我们
可以设上限为每种方案最多使用 100根钢筋，
最少使用 0根，初值可以设为全都取 0。
因此我们输入的屏幕显示为,
回车后得到计算结果,? ?TX 0,20,30,40,0?
这个数据似乎与前面结果不同，但是仍然有 min
z=16这时我们认为两个结果是等效的。
例 12,混合配料问题
某糖果厂用原料 A,B,C 加工成三种不同牌号的
糖果甲、乙、丙。已知各种牌号糖果中 A,B,C 含量，
原料成本，各种原料的每月限制用量，三种牌号糖果的
单位加工费及售价如下表，问该厂每月生产这三种牌号
糖果各多少千克，使该厂获利最大，试建立该问题的线
性规划数学模型。
解,用 i = 1,2,3 分别代表原料 A,B,C，用 j = 1,2,
3 分别代表甲、乙、丙三种糖果。设 xij 为生产第 j 种
糖果使用的第 i 种原料的质量，则问题的数学模型可
归结为,
目标函数
? ?? ? ? ?? ?
? ?? ? ? ?
? ? ? ?
332313
322212312111
333231232221
131211332313
322212312111
95.045.005.0
45.195.045.09.14.19.0
0.11, 5 0
0.230.025.2
40.085.250.040.3m a x
xxx
xxxxxx
xxxxxx
xxxxxx
xxxxxxz
??
???????
?????
???????
?????????
约束条件为
? ?
? ?
? ?
? ?
? ?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
???
???
???
???
???
?
?
?
?
?
???
???
???
含量要求条件
原料供应限制
3,2,1;3,2,10
6.0
5.0
3.0
2.0
6.0
1 2 0 0
2 5 0 0
2 0 0 0
33231333
32221232
32221212
31211131
31211111
333231
232221
131211
jix
xxxx
xxxx
xxxx
xxxx
xxxx
xxx
xxx
xxx
ij
例 13,投资项目的组合问题
兴安公司有一笔 30 万元的资金，考虑今后三年内
用于下列项目的投资,
1,三年内的每年年初均可投入，每年获利为投资
额的 20%，其本利可一起用于下一年的投资；
2,只允许第一年初投入，于第二年年末收回，本
利合计为投资额的 150%，但此类投资限额 15万以内；
3,允许于第二年初投入，于第三年末收回，本利
合计为投资额的 160%，但限额投资 20万元以内；
4,允许于第三年初投入，年末收回，可获利 40%，
但限额为 10万元以内；
试为该公司确定一个使第三年末本利总和为最大
的投资组合方案。
解,用 xij 表示第 i 年初投放到 j 项目的资金数，则可
投资的变量表如下
由于第三年末收回的本利只包含第三年初项目一
的投资、第二年初项目三的投资和第三年初项目四的
投资，因此目标函数为,
342331 4.16.12.1m ax xxxz ???
第一年初投资总额为 30万，因此有,
0 0 0 3 0 01211 ?? xx
第二年初的投资额与第一年末收回的本利总额相同,
112321 2.1 xxx ??
第三年初投资额与第二年末收回的本利总额相同,
12213431 5.12.1 xxxx ???
再考虑各项目的投资限额，得到该问题的线性规
划模型如下,
? ?
?
?
?
?
?
?
?
?
?
?
?
???
?
?
?
???
??
??
???
4,3,2,1;3,2,10
000 100
000 200
000150
5.12.1
2.1
000 300
4.16.12.1m a x
34
23
12
12213431
112321
1211
342331
jix
x
x
x
xxxx
xxx
xx
xxxz
ij
黑龙江工程学院数学系
吴 昶
课程简介
课程名称,运筹学
英文名称,Operations Research(缩写 O.R.)
运筹学,主要研究经济活动与军事活动中
能用数量来表达有关运用、筹划与管理方
面的问题，它根据问题的要求，通过数学
的分析与运算，作出综合性的合理安排，
以达到较经济较有效地使用人力。
运筹帷幄之中，决胜千里之外
教学内容,
第一章 线性规划及单纯形法
第二章 线性规划的对偶理论
第三章 运输问题
第四章 整数规划与分配问题
第五章 目标规划
第八章 动态规划
教学时数,3× 13=39
教材及主要参考书,
教材,胡运权，运筹学，哈尔滨工业大学
出版社。
参考书,运筹学教材编写组，运筹学，清
华大学出版社。
§ 1．一般线性规划问题的数学模型
§ 2．图解法
§ 3．单纯形法原理
§ 4．单纯形法的计算步骤
§ 5．单纯形法的进一步讨论
§ 6．改进单纯形法
§ 7．应用举例及 Matlab求解方法
第一章 线性规划及单纯形法
一、问题的提出
某企业计划生产 Ⅰ, Ⅱ 两种产品。这两种产
品都要分别在 A,B,C,D四种不同设备上加工。
生产每件产品 Ⅰ 需占用各设备分别为 2,1,4、
0h，生产每件产品 Ⅱ,需占用各设备分别为 2,2、
0,4h。已知各设备计划期内用于生产这两种产
品的能力分别为 12,8,16,12h，又知每生产一
件产品 Ⅰ 企业能获得 2元利润，每生产一件产品
Ⅱ 企业能获得 3元利润，问企业应安排生产两种
产品各多少件，使总的利润收入为最大。
§ 1．一般线性规划问题的数学模型
产品 Ⅰ 产品 Ⅱ 计划期内 生产能力
A 2 2 12
B 1 2 8
C 4 0 16
D 0 4 12
利润 2 3 MAX
需满足条件,
实现目的,
?
?
?
?
?
?
?
?
?
?
?
?
??
??
0,
12 4
16 4
82
1222
21
2
1
21
21
xx
x
x
xx
xx
m a x 32 21 ??? xxz
二、线性规划问题的数学模型
三个组成要素,
1.决策变量,是决策者为实现规划目标采取
的方案、措施，是问题中要确定的未知量。
2.目标函数,指问题要达到的目的要求，表
示为决策变量的函数。
3.约束条件,指决策变量取值时受到的各种
可用资源的限制，表示为含决策变量的等式
或不等式。
一般线性规划问题的数学模型,
?
?
?
?
?
?
?
?
?
?
??????
??????
??????
0,,,
,
,
,
21
2211
22222121
11212111
n
mnmnmm
nn
nn
xxx
bxaxaxa
bxaxaxa
bxaxaxa
?
?
????????????
?
?
）（或
）（或
）（或
目标函数,
约束条件,
nn xcxcxcz ???? ?2211m i nm a x ）（或
简写形式,
?
?
?
?
?
??
????
?
?
?
?
?
），，（
），，（），（或
）（或
njx
mibxa
xcz
j
i
n
j
jij
n
j
jj
?
?
1 0
1
m inm a x
1
1
矩阵形式表示为,
?
?
?
?
???
?
0
m i nm a x
X
AX
CXz
），（或
）（或
其中,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
nnnn
n
n
aaa
aaa
aaa
A
?
???
?
?
21
22221
11211? ?
ncccC,,,21 ??
? ?TnxxxX,,,21 ??
? ?Tnbbbb,,,21 ??
三、线性规划问题的标准形式
标准形式,
?
?
?
?
?
??
??
?
?
?
?
?
），，（
），，（
njx
mibxa
xcz
j
i
n
j
jij
n
j
jj
?
?
1 0
1
m a x
1
1
标准形式特点,
4,决策变量取值非负。
1,目标函数为求极大值；
2,约束条件全为等式；
3,约束条件右端常数项全为非负值；
一般线性规划问题如何化为标准型,
1,目标函数求极小值,
?
?
?
n
j
jj xcz
1
m in
令：,即化为,zz ??'
? ???
??
????
?????
n
j
jj
n
j
jj xcxc
zzz
11
m in)m a x (m a x
2,约束条件为不等式,
（ 1）当约束条件为,≤”时
如,1222
21 ?? xx
可令：, 显然
1222 321 ??? xxx 03 ?x
（ 2）当约束条件为,≥”时
如,181210
21 ?? xx
可令：, 显然 0
4 ?x181210 421 ??? xxx
称为 松弛变量。
3x
称为 剩余变量 。 4x
松弛变量和剩余变量统称为松弛变量
（ 3）目标函数中松弛变量的系数
由于松弛变量和剩余变量分别表示未被充分利
用的资源以及超用的资源，都没有转化为价值和利
润，因此 在目标函数中系数为零 。
3,取值无约束的变量
如果变量 x 代表某产品当年计划数与上
一年计划数之差，显然 x 的取值可能是正也
可能是负，这时可令,
xxx ?????
其中,00 ????? xx,
令
4,变量 xj≤0
jj xx ???
，显然
0??jx
例, 将下述线性规划模型化为标准型
?
?
?
?
?
?
?
??
????
????
????
???
取值无约束
321
321
321
321
321
,0,0
6323
42 3
9 2
32m i n
xxx
xxx
xxx
xxx
xxxz
解,令,，
11 xxzz ??????
? ?00 33333 ?????????? xxxxx,，
得标准形式为,
?
?
?
?
?
?
?
?????
????????
?????????
?????????
???????????
0
6 3323
4 22 3
9 2
00332m a x
543321
3321
53321
43321
543321
xxxxxx
xxxx
xxxxx
xxxxx
xxxxxxz
，，，，，
四、线性规划问题的解
可行解,满足约束条件的解称为 可行解,可行解的集
合称为 可行域 。
最优解,使目标函数达到最大值的可行解。
基,约束方程组的一个满秩子矩阵称为规划问题的一
个 基,基中的每一个列向量称为 基向量,与基向量对应
的变量称为 基变量,其他变量称为 非基变量 。
基解,在约束方程组中，令所有非基变量为 0，可以
解出基变量的唯一解，这组解与非基变量的 0共同构成
基解 。
基可行解,满足变量非负的基解称为 基可行解
可行基,对应于基可行解的基称为 可行基
求解线性规划问题,
就是从满足约束方程组和约束不等式的决策变量取
值中，找出使得目标函数达到最大的值。
?
?
?
?
?
??
??
?
?
?
?
?
），，（
），，（
njx
mibxa
xcz
j
i
n
j
jij
n
j
jj
?
?
1 0
1
m a x
1
1
为了便于建立 n 维空间中线性规划问题的
概念及便于理解求解一般线性规划问题的单纯
形法的思路，先介绍图解法。
求解下述线性规划问题,
?
?
?
?
?
?
?
?
?
?
?
?
??
??
0,
12 4
16 4
82
1222
21
2
1
21
21
xx
x
x
xx
xx
21 32m a x xxz ??
§ 2,线性规划问题的图解法
画出线性规划问题的可行域,
目标函数的几何意义,
最优解的确定,
图解法的步骤,
1,建立坐标系，将约束条件在图上表示；
2,确立满足约束条件的解的范围；
3,绘制出目标函数的图形；
4,确定最优解。
无穷多最优解的情况,
目标函数与某个约束条件恰好平行
无界解（或无最优解）的情况,
可行域上方无界
无可行解的情况,
约束条件不存在公共范围
图解法的启示,
1,求解线性规划问题时，解的情况有：唯一最
优解，无穷多最优解，无界界，无可行解；
2,若线性规划问题可行域存在，在可行域是一
个凸集；
3,若线性规划问题最优解存在，在最优解或最
优解之一一定能够在可行域的某个顶点取得；
4,解题思路是，先找凸集的任一顶点，计算其
目标函数值。比较其相邻顶点函数值，若更
优，则逐点转移，直到找到最优解。
§ 3．单纯形法原理
凸集,如果集合 C 中任意两个点,其连线上
的所有点也都是集合 C 中的点。
21,XX
上图中（ 1）（ 2）是凸集，（ 3）（ 4）不是凸集
顶点,如果对于凸集 C 中的点 X,不存在 C 中的任
意其它两个不同的点,使得 X 在它们的连线上，
这时称 X 为凸集的顶点。
21 XX,
一、线性规划问题基本定理
定理一 若线性规划问题存在可行解，则问题的可行
域是凸集。
定理二 线性规划问题的基本可行解 X 对应线性规划
问题可行域（凸集）的顶点。
定理三 若线性规划问题有最优解，一定存在一个基
可行解是最优解。
从上述三个定理可以看出，要求线性规划问
题的最优解，只要比较可行域（凸集）各个
顶点对应的目标函数值即可，最大的就是我
们所要求的最优解。
二、确定初始基可行解
线性规划问题的最优解一定会在基可行解中取得，我
们先找到一个初始基可行解。然后设法转换到另一个
基可行解，直到找到最优解为止。
设给定线性规划问题,
?
?
?
?
?
??
??
?
?
?
?
?
），，（
），，（
njx
mibxa
xcz
j
i
n
j
jij
n
j
jj
?
?
1 0
1
m a x
1
1
因此约束方程组的系数矩阵为,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
100
010
001
21
22221
11211
??
????????
??
??
mnmm
n
n
aaa
aaa
aaa
由于该矩阵含有一个单位子矩阵，因此，一这个单位
阵做基，就可以求出一个基可行解,
? ?TmbbX,,,0,,0 1 ???
其标准形为,
?
?
?
?
?
??
???
??
?
??
?
??
），，（
），，（
njx
mibxxa
xxcz
j
isi
n
j
jij
m
i
si
n
j
jj
?
?
1 0
1
0m a x
1
11
三、从初始基可行解转换为
另一个基可行解
对初始可行解的系数矩阵进行初等行
变换，构造出一个新的单位矩阵，其各列
所对应的变量即为一组新的基变量，求出
其数值，就是一个新的基可行解。
四、最优性检验和解的判别
设基可行解 ? ?
T
nxxxX
00
2
0
1
)0(,,,??
令 ?
?
??
m
i
ijijj acc
1
?,其中 随基的改变而改变 ija
lj
l
ij
ij
i
i a
xa
a
x 00 0m in ?
??
?
?
?
??
?
?
?
???
1,当所有 时，现有顶点对应的基可行解即为最
优解。
2,当所有 时，又对某个非基变量 有
且可以找到,则该线性规划问题有无穷多最
优解。
3,如果存在某个,又 向量的所有分量,
对任意,恒有,则存在无界解。
0?j?
0?j? ix 0?i?
0??
0?j? jP 0?ija
0?? ? ? 00 ?? iji ax ?
§ 4．单纯形法的计算步骤
第一步：求初始可行解，列初始单纯形表
1,表中最上端一行是各变量在目标函数中的系数,
最左端一列是各基变量在目标函数中的系数值。
2,表中最后一行就是检验数 。
j?
第二步：进行最优性检验
如果表中，所有检验数,则表中
的基可行解就是问题的最优解，计算到此为
止，否则转入下一步。
0?j?
第三步：转换到新的基可行解,
构造新单纯形表
1,确定换入变量
取使得 ? ?
0m a x ?? jjjk ???
所对应的 作为换入基的变量。
kx
2,确定换出变量
取使得
lk
l
ik
ik
i
a
ba
a
b ?
?
?
?
?
?
?
?? 0m a x?
所对应的 作为换入基的变量。
lx
3,用换入变量替换换出变量，做新单纯形表
（ 1）
klll abb ?? ? ?lia
a
bbb
ik
kl
l
ii ?????
（ 2）
kljljl aaa ?? ? ?lia
a
a
aa ik
kl
jl
ijij ?????
（ 3）检验数 的求法与初始单纯形表中求法相同
j?
第四步：重复第二、三步直到计算结束
例 5 用单纯形法求解线性规划问题
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
0,
124
16 4
82
1222
32m a x
21
2
1
21
21
21
xx
x
x
xx
xx
xxz
解,将原线性规划问题化为标准型
?
?
?
?
?
?
?
?
?
?
??
??
???
???
??????
0,
12 4
16 4
8 2
12 22
000032m a x
21
62
51
421
321
654321
xx
xx
xx
xxx
xxx
xxxxxxz
第一步,
取系数矩阵中单位阵部分为基，得初始基可行解
? ?TX 12,16,8,12,0,0?
列出初始单纯形表
第二步,
由于,都大于零，因此，目前没有得
到最优解。
32 ?? 21 ??
在大于零的检验数中，由于,且 3
2 ?? 21 ?? 12
?? ?
所以 为换入变量。
2x
第三步,
由于
3412412,,28,812m i n ???
?
??
?
? ???
所以确定 为换出变量
6x
1,确定换入变量
2,确定换出变量
3,作新单纯形表
第四步,由于还存在检验数,因此重复上述步骤。 0
1 ??
由于上表中所有检验数都小于等于零，因此已经
得到最优解，最优解为,
400024 654321 ?????? xxxxxx,，，，，
代入目标函数得最优值,14?z
当计算检验数有相同值的时候，可从中任选一个变量
作为换入变量。
当计算 值出现相同时，也可以从中任选一个作为换
出变量
?
注意,
§ 5．单纯形法的进一步讨论
一、人工变量法
考察上一节例 5中的线性规划问题,
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
0,
124
16 4
82
1222
32m a x
21
2
1
21
21
21
xx
x
x
xx
xx
xxz
化标准形为,
?
?
?
?
?
?
?
?
?
?
??
??
???
???
??????
0,
12 4
16 4
8 2
12 22
000032m a x
21
62
51
421
321
654321
xx
xx
xx
xxx
xxx
xxxxxxz
它的系数矩阵是,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
100040
010004
001021
000122
由于 系数矩阵中存在单位阵,很容易找到初始可行
基。但存在着不同的情况，考察下面的线性规划问题,
化为标准型,
?
?
?
?
?
?
?
?
??
?????
????
?????
0,,,,
9 3
1 2
4
003m a x
54321
32
5321
4321
5431
xxxxx
xx
xxxx
xxxx
xxxxz
?
?
?
?
?
?
?
?
??
????
???
???
0,,
93
1 2
4
3m a x
321
32
321
321
31
xxx
xx
xxx
xxx
xxz
例 6
该问题的系数矩阵为,
?
?
?
?
?
?
?
?
?
?
???
00130
10112
01111
54321
PPPPP
这个矩阵中不含有单位矩阵，因此很难找到初始基。
对于这种线性规划问题的系数矩阵不含有单位
矩阵的情况，我们往往采用添加 人工变量 的方法，
来认为构造一个单位矩阵。这样的方法就是 人工
变量法 。
为了构造出单位矩阵，在系数矩阵中添加两列单位
列向量，系数矩阵变为,
?
?
?
?
?
?
?
?
?
?
???
1000130
0110112
0001111
7654321
PPPPPPP
线性规划问题的约束条件就变为,
?
?
?
?
?
?
?
?
???
?????
????
0,,,,,,
9 3
1 - 2
4
7654321
732
65321
4321
xxxxxxx
xxx
xxxxx
xxxx
因为, 是人为添加的，因此其对应的变量,
称为 人工变量 。
6P 7P 6x 7x
目标函数中人工变量的系数,
添加人工变量前，在线性规划问题的标准形中，
各约束条件已经是等式约束了，因此为了保证等式约
束满足不变，在最优解中，人工变量的取值必须为 0。
为此，令目标函数中人工变量的系数为 任意大的
一个负值,用,”来表示，这样，只要人工变量
取值不为零，则目标函数就不能达到极大化。
M?
目标函数变为,
765431 003m a x MxMxxxxxz ???????
添加 M 来处理人工变量的方法，称为大 M 法
求解过程,
因此最优解为,T
X ?
?
??
?
?? 0,0,0,0,
2
3,
2
5,0
2
3m a x ?z
二、两阶段法
用大 M 处理人工变量时，用计算机求解会出现
错误，由此产生了两阶段法。
第一阶段：先求解一个目标函数中只含有人工
变量的线性规划问题。
即令目标函数中其它变量的系数取零，人工变
量的系数取某个正的常数（一般取 1），在保持原问
题约束条件不变的情况下求这个目标函数极小化时
的解。
第二阶段：从第一阶段的最终单纯形表出发，
去掉人工变量，按原问题的目标函数，继续寻找原
问题的最优解。
三、关于解的判别
1,当所有 时，又对某个非基变量 有
且可以找到,则该线性规划问题有无穷
多最优解。
0?j? ix 0?i?
0??
例 7,求解线性规划问题
?
?
?
?
?
?
?
?
?
?
?
?
??
??
0,
12 4
16 4
82
1222
21
2
1
21
21
xx
x
x
xx
xx
21 42m a x xxz ??
解,在图解法中，我们知道这个问题有无穷多解。
它的标准形为,
? ??
?
?
?
?
?
?
?
?
??
??
??
???
???
6,,2,10
12 4
16 4
8 2
12 22
62
51
421
321
?jx
xx
xx
xxx
xxx
j
654321 000042m a x xxxxxxz ??????
用单纯形法计算，得到最终单纯形表为,
从表中可以得到最优解,? ?
TX 0,8,0,2,3,21 ?
它对应的目标函数值为,14?z
在上表中，非基变量 的检验数为 0，如果将
换入基变量，得,6x6x
从表中可以得到新的最优解,? ?
TX 4,0,0,0,2,42 ?
它对应的目标函数值为,14?z
因此 和 连线上所有的点都是最优解，该
问题有无穷多最优解。
1X 2X
例 8,求解线性规划问题
?
?
?
?
?
0,
16 4
21
1
xx
x
21 32m a x xxz ??
解：用图解法求解时知道该问题有无界解,
它的标准形为,
?
?
?
?
??
0,,
16 4
321
31
xxx
xx
321 032m ax xxxz ???
用单纯形表求解过程如下,
表中,但 列数字为零，因此 的取
值可无限增大，所以目标函数值也可随之无限增
大，说明问题的解无界。
02 ?? 2x
例 9,求解线性规划问题
?
?
?
?
?
?
??
??
0,
142
1222
21
21
21
xx
xx
xx
21 32m a x xxz ??
解：利用图解法，我们已经知道该问题无可行解,
将其化为标准形,
? ???
?
?
?
??
????
???
5,4,3,2,10
14 2
12 22
5421
321
jx
xxxx
xxx
j
54321 0032m ax Mxxxxxz ?????
该问题单纯形法求解如下,
当所有 时，人工变量 仍然留在基变量中，
而且不为零，故问题无可行解。
0?j? 5x
四、单纯形法小结
1,对给定的线性规划问题应首先化为标准形式；
2,选取或构造一个单位矩阵作为基；
3,求出初始可行解并列出初始单纯形表；
4,计算检验数，判断是否最优解；
5,寻找换入及换出变量，构造新的单纯形表；
6,求出最优解。
化为标准形式、构造基及单纯形法计算步
骤见教材 。
28P
§ 6．改进单纯形法
用矩阵形式描述线性规划的标准形式为,
?
?
?
?
?
?
0
m a x
X
bAX
CXz
由于在转化成标准形时，总可以构造一个单位矩
阵作为初始单纯形表中的基。
因此将矩阵 A 分成作为 初始基的单位矩阵 I 和
非基变量系数矩阵 N 两块。
把 新单纯形表中的基（新表中的 I ），对应的
初始单纯形表中的那些向量 抽出来，单独列成一块，
用 B 表示。
初始单纯形表可以改写为,
单纯形法的迭代计算实际上就是对约束方程系数矩阵
实施的初等变换 。 对矩阵 （ b | B | N | I） 实施初等变
换时, 当 B 变为 I, I 将变换为 B-1。 因此, 上述矩阵
变为 （ B-1 b | I | B-1 N | B-1 ）,新单纯形表可写为,
显然,bBb
1???
NBN 1???
jj PBP 1???
? ? 111 0,,?? ???????? BCBCyyY BBm?
NBCCNCC BNBNN 1????????
jBjjBjj PBCcPCc 1????????
01 ???? ? BBCC BBI?
利用这些公式，我们来研究改进单纯形法
改进单纯形法的步骤,
1,在下一步迭代的基变量确定后，新基可行解为,
2,计算非基变量的检验数 和
3,产生 列的数字，有,如,线
性规划问题有无界解，计算结束。否则寻找换出
变量,
4,用非基变量 替换基变量,的出下一步中的
基变量。
5,重复上述步骤，直到计算结束。
bBX B 1??
NBCC BNN 1?????
1???? BCY BkP?
kk PBP 1??? 0??kP
? ?
? ? ? ?
? ?
? ? lk
l
ik
ik
i
i PB
bBPB
PB
bB
1
1
1
1
1
0m in ?
?
?
?
?
?
??
?
?
?
??
?
?
?
???
kx lx
B-1的求法,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
10
010
01
1
??
???
??
???
??
lkmk
lk
lkk
aa
a
aa
D
令
将 D 左乘迭代前的基的逆矩阵,就得到迭
代后基的逆矩阵 。
1?oldB
1?newB
例 10,用改进单纯形法求解
?
?
?
?
?
?
?
?
??
??
???
??
0,
15 3
9
62
24m a x
21
21
21
21
21
xx
xx
xx
xx
xxz
解：其标准形为
?
?
?
?
?
?
?
?
???
???
????
?????
0,,
15 3
9
6 2
00024m a x
51
521
421
321
54321
xx
xxx
xxx
xxx
xxxxxz
?
因此
?
?
?
?
?
?
?
?
?
?
?
?
?
13
11
21
N
?
?
?
?
?
?
?
?
?
?
?
15
9
6
b
（ 1）确定初始解
? ? ? ?0,0,0,,543 ?? cccC B
? ? ? ?2,4,21 ?? ccC N
找出约束条件中的单位矩阵 I 作为基，初始解,
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
15
9
6
5
4
3
b
x
x
x
X B
,
非基变量检验数,? ? ? ?
2,4,21 ???? ??? NCC BNN
因此 是换入变量,且
?
?
?
?
?
?
?
?
?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
3
1
1
31
21
11
1
a
a
a
P1x 1?k
5315315,19,m in ??
??
?
??
? ???由于
因此 是换出变量,。
5x 3?l
且 3
31 ?? aa lk
在基变量中,表示的是第三行。
5x
（ 2）第一次迭代
新的基变量,? ?T
B xxxX 143,,?
逆矩阵
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
3100
3110
3101
100
010
001
3100
3110
3101
100
010
001
100
10
01
31
3121
3111
1
a
aa
aa
B
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
?
?
?
?
?
?
?
?
?
? ?
5
4
11
15
9
6
3100
3110
3101
1
1
4
3
2
BB XB
x
x
x
X
? ? ? ?4,0,0,,1432 ?? cccC B
N’ 中只对应变元,因此
2x
? ?
3
10
1
1
2
3100
3110
3101
4,0,02
2
1
2
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
???
?
PBCc
BN
?
? ?
3
4
31
31
31
4,0,051 ??
?
?
?
?
?
?
?
?
?
?
?????? ? PBCY B
最大正检验数为 10/3，即 为换入变量，又 2x
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
??
31
34
35
1
1
2
3100
3110
3101
2P
3,3,
5
33m in ?
??
?
??
? ???
所以 为换出变量。
4x
（ 3）第二次迭代
新的基变量为,
? ?TB xxxX 1233,,?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ?
??
41410
41430
43451
3100
3110
3101
1410
0430
0451
1B
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
6
3
6
15
9
6
41410
41430
43451
1
2
3
3
x
x
x
X B
? ?4,2,0?BC 0
2
1,
4
10 ??
?
??
?
? ???
N?
因为所有检验数为零，所以最优解为,? ?
0,0,6,3,6?X
§ 7,应用举例及 Matlab求解法
例 11,工业原料的合理利用
要制作 100套钢筋架子，每套有长 2.9m,2.1m和
1.5m的钢筋各一根。已知原料长 7.4m，应如何切割，
使用原料最节省（仍掉的料头最小）。
考察如下方案的综合使用,
解,该问题的线性规划数学模型如下
? ??
?
?
?
?
?
?
??
????
???
???
????
5,,10
1 0 03 2 3
1 0 0 22
1 0 0 2
8.03.02.01.0m in
5321
543
421
5432
?jx
xxxx
xxx
xxx
xxxxz
j
该问题要用单纯形法求解，需要添加人工变量,
? ??
?
?
?
?
?
?
??
?????
????
????
????????
8,,10
1 0 0 3 2 3
1 0 0 22
1 0 0 2
8.03.02.01.0m a x
85321
7543
6421
8765432
?jx
xxxxx
xxxx
xxxx
MxMxMxxxxxz
j
下面我们考虑如何用 Matlab 语言来求解线性规划问题
在 Matlab 语言中，标准输入形式要求目标函数为极
小，约束条件为等于或小于等于，并使用矩阵或列向量
的形式给出，其标准形为,
?
?
?
?
?
??
?
?
UXL
BXA
BXA
XC
T
22
11
m i n
利用大 M 法求解，得到,
? ?TX 0,0,0,0,50,0,10,30? 16m i n ?z
上述线性规划问题,
? ??
?
?
?
?
?
?
??
????
???
???
????
5,,10
1 0 03 2 3
1 0 0 22
1 0 0 2
8.03.02.01.0m in
5321
543
421
5432
?jx
xxxx
xxx
xxx
xxxxz
j
用 Matlab 语言来改写，则有,
? ?8.0,3.0,2.0,1.0,0?TC ? ?TB 100,100,1001 ?
?
?
?
?
?
?
?
?
?
?
?
30213
12200
01021
A
? ?TxxxxxX 54321,,,,?
在 Matlab 语言中，以矩阵作为基本计算单位，向量
可以看作是矩阵的特殊情况，用“；”表示矩阵的
分行，用“，”表示两个元素的分隔，用,[ ]”表示
矩阵整体。
利用 Matlab 进行线性规划问题求解的命令格式为,
X=lp(c,A,b,XLB,XUB,x0,nEq)
在上述式子中,
c 是目标函数中的系数向量；
A 为约束方程组（不等式组）的系数矩阵；
b 为约束方程组（不等式组）的右端列向量；
XLB 为决策向量 X 的下限；
XUB 为决策向量 X 的上限；
x0 为决策向量 X 的初值；
nEq 为约束方程中等式的个数。
各参量在 Matlab 命令中使用的名称可以根据
需要而不同，但是出现的顺序不能发生改变。
对于前述的线性规划问题，我们已经给出
了 c,A,b，并且我们知道约束条件中等式有
三个，即 nEq=3，但是我们还没有给出决策向
量的上限、下限和初值。
决策向量的上限、下限和初值我们可以根
据实际情况自己进行估计，在该问题中，我们
可以设上限为每种方案最多使用 100根钢筋，
最少使用 0根，初值可以设为全都取 0。
因此我们输入的屏幕显示为,
回车后得到计算结果,? ?TX 0,20,30,40,0?
这个数据似乎与前面结果不同，但是仍然有 min
z=16这时我们认为两个结果是等效的。
例 12,混合配料问题
某糖果厂用原料 A,B,C 加工成三种不同牌号的
糖果甲、乙、丙。已知各种牌号糖果中 A,B,C 含量，
原料成本，各种原料的每月限制用量，三种牌号糖果的
单位加工费及售价如下表，问该厂每月生产这三种牌号
糖果各多少千克，使该厂获利最大，试建立该问题的线
性规划数学模型。
解,用 i = 1,2,3 分别代表原料 A,B,C，用 j = 1,2,
3 分别代表甲、乙、丙三种糖果。设 xij 为生产第 j 种
糖果使用的第 i 种原料的质量，则问题的数学模型可
归结为,
目标函数
? ?? ? ? ?? ?
? ?? ? ? ?
? ? ? ?
332313
322212312111
333231232221
131211332313
322212312111
95.045.005.0
45.195.045.09.14.19.0
0.11, 5 0
0.230.025.2
40.085.250.040.3m a x
xxx
xxxxxx
xxxxxx
xxxxxx
xxxxxxz
??
???????
?????
???????
?????????
约束条件为
? ?
? ?
? ?
? ?
? ?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
???
???
???
???
???
?
?
?
?
?
???
???
???
含量要求条件
原料供应限制
3,2,1;3,2,10
6.0
5.0
3.0
2.0
6.0
1 2 0 0
2 5 0 0
2 0 0 0
33231333
32221232
32221212
31211131
31211111
333231
232221
131211
jix
xxxx
xxxx
xxxx
xxxx
xxxx
xxx
xxx
xxx
ij
例 13,投资项目的组合问题
兴安公司有一笔 30 万元的资金，考虑今后三年内
用于下列项目的投资,
1,三年内的每年年初均可投入，每年获利为投资
额的 20%，其本利可一起用于下一年的投资；
2,只允许第一年初投入，于第二年年末收回，本
利合计为投资额的 150%，但此类投资限额 15万以内；
3,允许于第二年初投入，于第三年末收回，本利
合计为投资额的 160%，但限额投资 20万元以内；
4,允许于第三年初投入，年末收回，可获利 40%，
但限额为 10万元以内；
试为该公司确定一个使第三年末本利总和为最大
的投资组合方案。
解,用 xij 表示第 i 年初投放到 j 项目的资金数，则可
投资的变量表如下
由于第三年末收回的本利只包含第三年初项目一
的投资、第二年初项目三的投资和第三年初项目四的
投资，因此目标函数为,
342331 4.16.12.1m ax xxxz ???
第一年初投资总额为 30万，因此有,
0 0 0 3 0 01211 ?? xx
第二年初的投资额与第一年末收回的本利总额相同,
112321 2.1 xxx ??
第三年初投资额与第二年末收回的本利总额相同,
12213431 5.12.1 xxxx ???
再考虑各项目的投资限额，得到该问题的线性规
划模型如下,
? ?
?
?
?
?
?
?
?
?
?
?
?
???
?
?
?
???
??
??
???
4,3,2,1;3,2,10
000 100
000 200
000150
5.12.1
2.1
000 300
4.16.12.1m a x
34
23
12
12213431
112321
1211
342331
jix
x
x
x
xxxx
xxx
xx
xxxz
ij
