运筹学
运筹学是高等学校经济管理类专业
本科生所必修的一门专业基础课；是分析和
解决经营管理领域最优化问题的一门方法
论学科；是每个有志于从事现代经营管理工
作的同志所应该掌握的重要数量分析工具。
何谓“运筹学”？
英文名称为“ Operations Research” ,
直译“作业研究”。就是研究在经营管理活
动中如何行动，以尽可能小的代价，获取尽
可能好的结果。 即所谓“最优化”问题。中
国学者 将其 译为“运筹学”，取自古语“运
筹于帷幄之中，决胜于千里之外”，其意为
运算筹划，出谋献策，以最佳策略取胜。这
就极为恰当地概括了 这门学科的精髓。
自人类社会诞生以来，人们一直经历着
运用和筹划的决策过程，而运筹学的一
些朴素思想可以追溯到很久以前，像“孙子
兵法”就是我国古代战争谋略之集大成者；
像诸葛亮更是家喻户晓的一代军事运筹大
师。然而，把“运筹学”真正当成一门学科
来研究，则还只是近几十年来的事。
第二次世界大战中，英美等过抽调各方
面的专家参与各种战略战术的优化研
究工作，获得了显著的成功，大大推进了胜
利的进程。 战后，从事这些活动的许多专家
转到了民用部门，使运筹学很快推广到了工
业企业和政府工作的各个方面，从而促进了
运筹学有关理论和 方法的研究和实践，使得
运筹学迅速发展并逐步成熟起来。
运筹学发展到现在，虽然只有五十多年
的历史，但其内容已经相当丰富，所涉
及的领域也十分广泛。 以《运筹学国际文摘》
收集的各国运筹学论文的内容为例，按技术
分类就有 50 多种。现在这门新兴学科的应
用已深入到国民经济的各个领域，成为促进
国民经济多快好省，健康协调发展的有效方
法。
运筹学的特点： 整体优化、多学科配合、
“浅化”易行、建模求解
运筹学解决问题的方法步骤：
提出问题
建立模型
求解模型
解的检验
解的调整
解的实施
讲授此门课程的目的：
要使同学们系统 地了解运筹学的基本
概念，基本原理，研究方法及应用。掌握运
筹学整体优化的思想和定量分析的优化技
术，并能正确应用各类模型分析和解决实际
问题。
这门课程共 48 课时， 讲授 32 课时，
另有 16 个学时的上机操作。
主要 内容 ：
主要讲授线性规划与单纯形法
对偶理论与灵敏度分析
运输问题
目标规划
动态规划 模型
上机主要运用“ Excel”建模和求解。
第一章 线性规划与单纯形法
线性规划是运筹学的重要分支， 1947
年，美国人丹捷格提出，理论已趋向成熟，
应用日益广泛与深入，几乎各行各业都可以
建立线性规划模型。比如制定企业 最佳经营
计划，确定产品最优配料比，寻找材料的最
优下料方案，研究各种资源的最优分配方案
等等。
由于线性规划模型具有应用的广泛
性，更主要由于它的算法易于在计算机上实
现，实际上“ Excel”的“规划求解”，即可
以用来求解一般的线性规划问题。所以，线
性规划已成为现代管理科学的重要基础和
手段之一。
§ 1 线性规划问题
1.1 线性规划问题的数学模型
线性规划是研究在一组线性不等
式或 等式约束下，使得某一线性目标函数取
得最大（或最小）的极值问题。
例 1.某工厂生产Ⅰ，Ⅱ两种型号计算机，
为了生产一台 Ⅰ型和Ⅱ型计算 机，所需
原料分别为 2 和 3 个单位，需要的工时分别
为 4 和 2 个工时。在计划期内使用的原料为
100 个单位，工时为 120 个单位。已知生产
每台Ⅰ，Ⅱ型计算机可获得利润分别为 6 和
4 个单位，试确定获利最大的生产方案。
建立数学模型
设 12,xx分别表示计划期内产品Ⅰ 、 Ⅱ
的产量，由于条件限制，满足以下约束条件 ：
122 3 1 0 0xx??
124 2 1 2 0xx??
12,0xx ?
一 般满足上述约束方程组的解不是唯
一的。根据题意我们需要的是既满足约束条
件，又使得所获利润最大的方案。 若以 Z 表
示总利润，目标是 12m a x 6 4Z x x??
综上所述，该问题数学模型表示为：
目标函数 12m a x 6 4Z x x??
约束条件
12
12
12
2 3 10 0
4 2 12 0
,0
xx
xx
xx
???
?
???
? ?
?
例 2.某昼夜服务的公交线路，每天各时
间区段内所需司机和乘 务人员数如下：
班次 时间 人数
1 6:00-10:00 60
2 10:00-14:00 70
3 14:00-18:00 60
4 18:00-22:00 20
5 22:00-2:00 20
6 2:00-6:00 30
设司乘人员在各时间段内一开始时上班，并
连续工作 8 小时，问该公司线路至少应配备
多少司乘人员。列出该数学模型。
设 1 2 6,,x x x为各班新上班人数，在每个
时间段工作的人数既包括该时间段新上班
的人，又包括上一个时间段上班的人员， 按
所需人 员最少的需求列出数学模型。
目标函数： 1 2 3 4 5 6m i n Z x x x x x x? ? ? ? ? ?
约束条件 ：
16
12
23
60
70
60
xx
xx
xx
???
?
???
? ??
?
34
45
56
20
20
30
xx
xx
xx
??
??
??
1 2 6, , 0x x x ?
例： 医院为病人配制营养餐，要求每餐
中含有铁不低于 50 单位，蛋白质不低于 40
单位，钙不低于 42 单位。假设只有两种食
品 A 和 B 可供配餐，试问：如何购买两种食
品进行搭配，才能既使病人所需营养达到需
求，又能使总花费最低？
食品
营养含量
A B 单位
铁 10 5 mg
蛋白质 5 8 g
钙 6 5 mg
价格 4 3 元 /kg
例： 工人老张下岗后，打算利用自己的
一技之长生产两种产品 A,B 出售，而手头只
有 12000 元积蓄，为了充分发挥资金的作
用，他找到了您，请您帮忙。
1、工艺数据：生产每单位产品 A 要用到三
种原料 Ⅰ 、 Ⅱ 、 Ⅲ 依次为 2,4,6 个单位，生
产每单位产品 B 的用量依次为 1,3,4 个单
位。
2、成本与利润数据：根据市场原料价
位，以及产品的原料费，运销等杂支，确定
单位产品 A,B 的利润约为 500 元 ， 350 元。
3、总资金 12000 元按原料需求比，分配初
步确定为：购买三种原料依次为 300,600 和
810 个单位，所余资金留作机动。
依据上述数据，希望给出一个生产方案，使
总利润达到最大。
上述题目优化模型，都具有下述特征：
（ 1）每个问题都用一组未知变量 12,, nx x x表
示所求方案，通常这些变量都是非负的，称为
决策变量
（ 2）存在一组约束条件，这些约束条件都可以
用一组线性等式或不等式表示
（ 3）都有一个要求的目标，并且这个目标可表
示为一组决策变量的线性函数 ，称为目标函数。
目标函数可以是求最大，也可以是求最小
具有上述特征的数学模型称为 线性规划模型
线性规划数学模型的一般形式如下：
目标函数： 1 1 2 2m a x ( m i n ) nnZ c x c x c x? ? ?
约束条件 ：
1 1 1 1 2 2 1 1
2 1 1 2 2 2 2 2
1 1 2 2
12
( , )
( , )
( , )
, , 0
nn
nn
m m m n n m
n
a x a x a x b
a x a x a x b
a x a x a x b
x x x
? ? ? ? ??
?
? ? ? ? ?
?
?
?
?
? ? ? ? ?
?
??
?
1.2 图解法
如何求解线性规划模型是本章讨论的
中心问题
首先介绍只有两个决策变量的线性规
划的 图解法
方法： 对于两个决策变量的每一组取值 ，都
可以看作平面直角坐标系中的一个点的坐
标。因此，把满足约束条件的点在平面直角
坐标系中表示出来。
上例得到的最 优解是唯一的，但是线性
规划问题的解还可能出现以下几种情况：
（ 1）无穷多个最优解 .若例 1 目标函数变为
12m a x 4 2Z x x??，就会出现这种情况（与一
条边重合）
（ 2）无可行解 .如果约束中存在互相矛盾的
约束条件，则导致可行域是空集，此时问题
无可行解 .
（ 3）无有限最优解 .如对下述线性规划问题
12m a x Z x x??
12
12
12
4
2
,0
xx
xx
xx
? ? ??
?
???
? ?
?
总结：图解方法
（ 1）具有两个变量的线性规划问题的可行
域是凸多边形
（ 2）若线 性规划存在最优解，它一定在可
行域的某个顶点得到 。
虽然，图解法只能求解包含 2 个变量的
问题，作为算法，没有太大价值，但是上述
结论非常有意义。它将搜索最优解的范围从
可行域的无穷多个点缩小到有限个顶点。单
纯形法在此结论基础上得以推广。
§ 2 线性规划问题的标准型与基解
2.1 线性规划的标准型
标准型如下： 1 1 2 2m a x nnZ c x c x c x? ? ?
1 1 1 1 2 2 1 1
2 1 1 2 2 2 2 2
1 1 2 2
12
( , )
( , )
( , )
, , 0
nn
nn
m m m n n m
n
a x a x a x b
a x a x a x b
a x a x a x b
x x x
? ? ? ? ??
?
? ? ? ? ?
?
?
?
?
? ? ? ? ?
?
??
?
称 ( 1 , 2 , )jc j n?为价值系数 ，
( 1 , 2 , )ib i m? 为资源系数 ，
ija 为技术系数或约束系数
在模型中它们是常数
若记为（向量） ? ?1 , 2 , TnX x x x? ，
? ?12,, nC c c c? ， ? ?12,, Tnb b b b?
12( ) ( , , )ij m n nA a p p p???
则标准型亦可记为（矩阵）
m a x Z C X? ()
0
AX b
X
? ? ??
? ?
?
或
1
m a x
n
jj
j
Z c x
?
? ?
1
( , )
0 1 , 2 ,
n
j j j
j
j
p x b
x j n
?
?
? ? ??
?
? ??
?
?
任何形式的线性规划都可以化为与其
等价的标准形式
（ 1）如果目标函数是 m i n Z C X?,则可令
ZZ??,将目标函数变为 m a x Z C X??
（ 2 ） 如 果 某 约 束 条 件 为 不 等 式 ：
1 1 2 2i i in n ia x a x a x b? ? ? ?，则在约束条件左
端加一个非负变量 nix? ，称为松弛变量。即
可变为等式 1 1 2 2i i i n n n i ia x a x a x x b?? ? ? ? ?
如果某约束条件为不等式
1 1 2 2i i in n ia x a x a x b? ? ? ?
则在约束条件左端减一个非负变量 nix? ，
称为剩余变量或松弛变量。即可变为等式
1 1 2 2i i i n n n i ia x a x a x x b?? ? ? ? ?
如：
1 2 3 1 2 3 42 3 8 2 3 8x x x x x x x? ? ? ? ? ? ? ?
1 2 3 1 2 3 42 3 4 8 2 3 4 8x x x x x x x? ? ? ? ? ? ? ?
（ 3）如果 jx 没有非负限制，即可正可负。
则可令 j j jx x x? ????，其中 ,0jjxx? ?? ?，代入目
标函数及约束条件即可。对 0x? 的情况，令
( 0 )x x x??? ? ?
例 3.将 以下 线性规划 化为标准型
12m i n 3Z x x??
12
12
1
1
1
0
xx
xx
x
???
?
? ? ??
? ?
?
解：令 ZZ??， 2 2 2x x x? ????， 得标准型为
1 2 2m a x 3Z x x x? ??? ? ? ?
1 2 2 3
1 2 2 4
1 2 2 3 4
1
( ) 1
, , , , 0
x x x x
x x x x
x x x x x
? ??? ? ? ? ?
?
? ? ??
? ? ? ? ??
? ? ??
??
?
2.2 线性规划基解的概念
记线性规划问题为
m a x Z C X?
()
0
AX b
L
X
??
? ?
?
基： 设 A 是 mn? 阶约束系数矩阵 ()mn? ，
秩 Am? . ? ?1 , 2 , nA p p p? ，则 A 中一定存在
m 个线性无关的列向量，设为 12,,j j jmp p p，
称可逆矩阵 ? ?12,,j j jmB p p p? 为线性规
划（ L）的一个基 .称 B 中的列向量对应的变量
12,,j j jmx x x为 基变量 ，其余变量为 非基变量 .
基本解： 记基变量为 ? ?12,, TB j j jmX x x x? ，非
基 变 量 构 成 的 列 向 量 记 为 0NX ? , 则有
1
n
j j B
j
AX p x BX b
?
? ? ??， B 可逆，于是有
1BX B b?? ， 0NX ?为线性规划（ L）的一个 基
本解 .
基可行解： 若基本解中 1 0BX B b???，则
称该解为 基可行解 。这时基 B 也称为 可行基 。
决策变量的一组取值称为解，解不一定满
足约束条件，以此区分可行解，非可行解。
非
可
行
解
可
行
解
基 解
基
可
行
解
显然，基可行解的数目 ?基解的数目（基） ? nmC
例 4.求出下面线性规划的所有基本解，
并指出哪些是基可行解。
12m a x 2Z x x??
12
12
12
3 5 1 5
6 2 2 4
,0
xx
xx
xx
???
?
???
? ?
?
解：标准化得 12m a x 2Z x x??
1 2 3
1 2 4
1 2 3 4
3 5 15
6 2 24
, , , 0
x x x
x x x
x x x x
? ? ??
?
? ? ??
? ?
?
系数矩 阵 ? ?1 2 3 4 3 5 1 0, , , 6 2 0 1A p p p p ???? ??
??
秩 2A? ，
15
24
b ??? ??
??
， 24 6mnCC??
取 ? ?1 1 2
35
,
62
B P P ???? ??
??
，
35
0
62
?，
1B 可逆
1 BB X b? ?，
1
2
3 5 15
6 2 24
x
x
??? ? ? ??
??? ? ? ?? ? ? ???
1
1
2
15
3 5 15 2 5 151 4
6 2 24 6 3 24 324
4
x
x
?
??
????? ? ? ? ? ? ? ? ?
? ? ? ? ???? ? ? ? ? ? ? ? ?
?? ? ? ? ? ? ? ??? ??
??
??
4
31
2
15
04
,
30
4
xx
xx
??
?? ???? ??
???? ???? ??
???? ????
??
??
是基可行解
? ?2 1 3 31, 60B P P ???? ??
??
, 1 2
3 4
40,
30
x x
x x
?? ??? ? ? ???
?? ??? ? ? ?? ? ? ????? 是基
可行解
? ?3 1 4 30, 61B P P ???? ??
??
， 21
34
50,
60
xx
xx
???? ? ? ? ???
???? ? ? ? ??? ? ? ??? ??是
基本解
? ?4 2 3 51, 20B P P ???? ????， 2 1
3 4
12 0,
45 0
x x
x x
?? ??? ? ? ???
?? ??? ? ? ??? ? ? ????? 是基本解
? ?5 2 4 50, 21B P P ???? ????， 12
34
30,
18 0
xx
xx
???? ? ? ? ???
???? ? ? ? ?? ? ? ??? ??是基可行
解
? ?6 3 4 10, 01B P P ???? ??
??
， 31
42
15 0,
24 0
xx? ? ? ?? ? ? ???
? ? ? ?? ? ? ?? ? ? ?? ? ? ?是基可
行解
§ 3 线性规划问题的几何意义
定义（凸集） ： 设 K 是 n 维欧氏空间的一个
点集，若任意两点 ( 1 ) ( 2 ),x K x K??的连线上
的一切是 ( 1 ) ( 2 )( 1 ) (0 1 )x x x K? ? ?? ? ? ? ? ?，
则称 K 为凸集。
凸集的 特征 是：连接集合中任意两点的
线段整个地都在集合之中。实心的凸多边
形，凸多面体都是凸集。从直观上讲，凸集
没有凹入部分，其内部没有空洞。
定义（凸组合） ： 设 ( 1 ) ( 2 ) ( ),, kx x x是 n 维
欧氏空间的 k 个点，若存在满足
0 1 , 1 , 2i ik?? ? ?. 且
1
1
k
i
i
?
?
?? . 则称
( 1 ) ( 2 )12 kkx x x x? ? ?? ? ?为 ( 1 ) ( 2 ) ( ),, kx x x的
凸组合 .
定义（顶点） ： 设 K 是凸集， XK? ,若 X 不能
表示成任何 ( 1 ) ( 2 ),x K x K??两点连线的内
点，则称 X 为 K 的一个顶点（或极点）
关于线性规划问题解的性质，介绍以
下几个定理
定 理 （ 3.1 ） 线 性 规 划 的 可 行域
? ?,0D x A x b x? ? ?是一个凸集
证明： 设 ( 1 ) ( 2 ),x D x D??,且 (1 ) ( 2 )xx?
则 ( 1 ) ( 1 ) ( 2 ) ( 2 ), 0 . , 0A x b x A x b x? ? ? ?
令 ( 1 ) ( 2 )( 1 ) (0 1 )x x x? ? ?? ? ? ? ?
则 ( 1 ) ( 2 )( 1 )A x A x A x b??? ? ? ?
所以 xD?
因此，根据凸集的定义， D 是凸集。
引理 1.线性规划的可行解
? ?12,, TnX x x x?
是基可行解的充要条件是： X 的正分量对应
的系数列向量是线性无关的。
定理（ 3.2） x是可行域 ? ?,0D x A x b x? ? ?的
顶点的充要条件是： x 是该线性规划问题的
基可行解。
证明： 反证法
即证明： x不是可行域的顶点 ?x不是基
可行解
先证： x不是可行域的顶点 ?x不是基可行解
设 x 的前 m个分量为正，后 nm? 个分量都为
0.由于 , 0 .A x b x??所以可得
1
m
jj
j
p x b
?
?? ①
由引理 1 知， 1 2 ,, mp p p线性相关。即存在一
组不全为 0 的数 ( 1 , 2 , )i im? ? ，使得有
1 1 2 2 0mmp p p? ? ?? ? ? ②
②式乘上一个不为 0 的数 ? ，得
1 1 2 2 0mmp p p? ? ? ? ? ?? ? ? ③
① +③得
1 1 1 2 2 2( ) ( ) ( ) 0m m mx p x p x p? ? ? ? ? ?? ? ? ? ? ? ?
① -③得
1 1 1 2 2 2( ) ( ) ( ) 0m m mx p x p x p? ? ? ? ? ?? ? ? ? ? ? ?
又 ? 可以选取使得它满足对所有 1 , 2 ,im?
有 0kkx ????
由此 12,x D x D??.
而且 ? ? ( 1 ) ( 2 )12 11,, 22nx x x x x x? ? ?
所以 x不是可行域 D 的顶点 .
再证： x不是可行域的顶点 ?x不是基可行解
设 ? ?12,, nx x x x D??,因为 x 不是可行域的
顶点，因而可以找到可行域内另外两个不同
点 ,y z D?.以及 01???，使得
( 1 )x y z??? ? ?.
或可写成 ( 1 ) , ( 1 , 2 , )i i ix y z i n??? ? ? ?.
因为 01???， ,,x y z D?，
故当 0 , 0i i ix y z? ? ?.不妨设 x的前 r个分量
为正，即 ? ?12, , , 0 , 0 , 0rx x x x? ，则
11
nr
j j j j
jj
p x p x b
??
????
由此可得
11
nr
j j j j
jj
p y p y b
??
???? ④
11
nr
j j j j
jj
p z p z b
??
???? ⑤
④ -⑤得
11
( ) ( ) 0
nr
j j j j j j
jj
p y z p y z
??
? ? ? ???
因 ()jjyz? 不全为零，故 1 2 ,, rp p p线性相关，
即 x 不是基可行解。
引理 2.若 K 是有界凸集，则任何一点
xK? 都可表 示为 K 的顶点的凸组合。
定理 3.3 若可行域非空有界，则线性规划问
题一定可以在可行域的某个顶点上找到最
优解。
重要结论：
线 性 规 划 问 题 的 可 行 域 是 凸 集
（ Th3.1） 。
凸集的每个顶点对应一个基可行解
（ Th3.2），基可行解的个数是有限的，当然
凸集的顶点也是有限的 .
若线性规划有最优解，必在可行域的某
顶点上达到（ Th3.3），亦即在有限个基可行
解中间存在最优解 .
因此，我们可以在有限个基可行解中去
寻找最优解，这就是下节介绍的单纯形法的
理论依据，该方法就是一种在 基可行解中搜
索最优解的算法。
§ 4 单纯形法
单纯形法的基本思想是：从可行域的一
个基可行解（一个顶点）出发，判断该解是
否为最优解，如果不是最优解，就转移到另
一个较好的基可行解。如果目标函数达到了
最优，则已得到最优解，否则继续转移到其
他较好的基可行解。由于基可行解（顶点）
数目有限，所以在基可行解上一定能找到最
优解。
4.1.确定初始基可行解
对于线性规划问题
m a x Z C X?
()
0
AX b
L
X
??
? ?
?
首先介绍求初始基可行解的方法
1.直 接观察法
若给定问题标准化后（且 0b? ），系数矩阵 A
中存在 m 个线性无关的单位列向量，则 从这
m 个单位列向量构成的单位子矩阵作
为初始基 B,则 1 0BX B b b?? ? ?，其余 0jx ?
是基可行解。
例 5： 求例 1 问题的初始基可行解
12m a x 6 4Z x x??
12
12
12
2 3 10 0
4 2 12 0
,0
xx
xx
xx
???
?
???
? ?
?
解： 标准化
12m a x 6 4Z x x??
1 2 3
1 2 4
1 2 3 , 4
2 3 1 0 0
4 2 1 2 0
, , 0
x x x
x x x
x x x x
? ? ? ?
?
? ? ??
? ?
?
2 3 1 0
4 2 0 1A
???
????
取 34
10
( , )
01
pp ??? ??
??
为初始基 B
于是
31
4
100
120B
x
X B b
x
? ????? ? ?
?????? ??，
1
2
0
0N
x
X
x
?? ????
?? ??????
所以 0Z ? .
2.大 M 法（ 人工变量法 ）
若给定问题标准化后（ 0b? ）系数矩阵
中不存在 m 个线性无关的单位列向量，则在
某些约束的左端加一个非负的变量 nix? （人
工变量），使得变化后的系数矩阵中有 m 个
线性无关的的单位列向量，并且在目标
函数中减去这些人工变量与 M 的乘积（ M 是
相当大正数），对于变化后的问题，取这 m
个单位列向量构成的单位子矩阵为初始基，
该基对应的解一定是基可行解。
例 6.求下列问题的初始基可行解
1 2 3m a x 3Z x x x? ? ?
1 2 3
1 2 3
13
1 2 3
2 11
4 2 3
21
, , 0
x x x
x x x
xx
x x x
? ? ??
?
? ? ? ??
?
? ? ?
?
? ?
?
解：标准化后
1 2 3m a x 3Z x x x? ? ?
1 2 3 4
1 2 3 5
13
1 2 3 4 5
2 11
4 2 3
21
, , , , 0
x x x x
x x x x
xx
x x x x x
? ? ? ??
?
? ? ? ? ??
?
? ? ?
?
? ?
?
利用大 M 法后为
1 2 3 6 7m a x 3Z x x x M x M x? ? ? ? ?
1 2 3 4
1 2 3 5 6
1 3 7
1 2 3 4 5 6 7
2 11
4 2 3
21
, , , , , , 0
x x x x
x x x x x
x x x
x x x x x x x
? ? ? ??
?
? ? ? ? ? ??
?
? ? ? ?
?
? ?
?
? ?467
1 0 0
, , 0 1 0
0 0 1
B p p p
??
????
??
??
，
4
1
6
7
11
3
1
B
x
X B b x
x
?
????
????? ? ?
????
?? ??
?? ??
，
1
2
3
4
0
0
0
0
N
x
x
X
x
x
?? ??
?? ??
?? ????
?? ??
?? ??
????
因为 0M ? ,所以无最优解 。
显然，对任意形式的线性规划问题都可
以用这种增加人工变量的方法“凑出”一个
单位子矩阵作为初始可行基，按这种方法变
化得到的线性规划与原规划有如下关系：
（ 1）原问题的任一基可行解都是变化
后的问题基可行解
（ 2）若变化后问题的最优解中不含有
非零的人工变量，则该最优解就是原问题的
最优解
（ 3）若变化后问题的最优解 中含有非
零的人工变量，则原问题无可行解
4.2 最优化检验
设线性规划的可行基 ? ?12, , , mB p p p? ，
记 ? ? ? ? ? ?, , , , , TB N B NA B N C C C X X X? ? ?,
用 1B? 左乘约束方程组两端，得
1 1 1 1( , ) B
BN
N
X
B A X B B N X B NX B b
X
? ? ? ???? ? ? ?
????
即 11BNX B N X B b???? （ 1）
将 11BNX B N X B b????代入目标函数得
? ?
11
,
()
B
BN
N
B N B N
X
Z CX C C
X
C B b C C B N X??
??
?? ??
??
? ? ?
记 1 1 , 2( ) ( , )N N B m m nC C B N? ? ? ?? ??? ? ?
其中， 1 , 1 , 2 ,j j B jC C B p j m m n? ?? ? ? ? ?
即有
11
1
n
B N N B j j
jm
Z C B b X C B b x????
??
? ? ? ? ? （ 2）
分析
1
n
jj
jm
x?
??
?
非基变量 jx 前面的系数 j? ，可以用来判断当
前对应与基 B的基可行解是否为最优解。故
称为变量 jx 对应的检验数。
定理 4.1（最优性判定定理） 对某基可
行解 1BX B b?? ，其余 0jX ? ，若所有检验数
1 0 , 1 , 2 ,j j B jC C B p j m m n? ?? ? ? ? ? ?，则
该解为最优解。
证明： 对一切可行解 nx ，当所有检验数 0j? ?
时， 11
1
n
B j j B
jm
Z C B b x C B b???
??
? ? ??.
而基可行解 1BX B b?? ，其余 0jX ? 对应
的目标函数值恰为 1BC B b?.
所以，基可行解 1BX B b?? ，其余是最优解，
B 为最优基。
定理 4.2（无界解判定定理） 若对某可行基
B,存在，则该问题无有限最优解。
如例 1.标准化后为
12m a x 6 4Z x x??
1 2 3
1 2 4
1 2 3 , 4
2 3 1 0 0
4 2 1 2 0
, , 0
x x x
x x x
x x x x
? ? ? ?
?
? ? ??
? ?
?
取 34
10
( , )
01
pp ??? ??
??
为初始基 B
31
4
100
120B
x
X B b
x
? ????? ? ?
?????? ??， 12 0xx??为初
始基可行解。
因为 1j j B jC C B P? ???，所以
1
1 1 1
2
6 ( 0 , 0) 6 0
4B
C C B P? ? ??? ? ? ? ? ???
??
1
2 2 2
3
4 ( 0 , 0) 4 0
2B
C C B P? ? ??? ? ? ? ? ???
??
所以，该解不是最优解。
4.3 单纯形表
为了便于表达单纯形法的计算过程，将
可行基对应的（ 1），（ 2）式写成系数增广矩
阵，即 11BNE X B N X B b???? （ 1）
1B N NZ C B b X???? （ 2） 11
10
NB
E B N B b
C B b?
??
?
??
?? ?
??
设计成一种特殊表格，称为单纯形表，其形
式如下：
C 1 2 1 . . . . . .m m nC C C C C?
1
2
...
B
m
C
C
C
C
1
2
...
B
m
X
X
X
X
1
10
20
0
...
m
Bb
a
a
a
?
1 2 1
1 1 1
2 1 2
1
... ...
1 0 ... 0 ...
0 1 ... 0 ...
... ... ... ... ... ... ...
0 0 ... 1 ...
m m n
mn
mn
m m m n
X X X X X
aa
aa
aa
?
?
?
?
? 1BC B b?? 10 0 . . . 0 . . . mn???
这里强调两点：
（ 1）对应于基 B 的单纯形表的中间核心
部分实际就是 1 1 1
1 1 1
12
( , ) ( , )
( , , )n
B A B B N E B N
B P B P B P
? ? ?
? ? ?
??
?
即单纯形表中 jx 的系数列向量为 1 jBp? ， jp 为
A 的第 j 列，而基变量的系数列向量为 单位
列向量。再看定理 4.2，若对某可行基 B,存
在 0k? ? ,，且 1 0kBp? ?， 则该问题无有限最
优解。
（ 2 ）把计算非基变量的检验数公式
1N N BC C B N? ???应用于基变量，即可认为
基变量也有检验数，其值为
1 0B B BC C B B? ?? ? ?,
所以单纯形表最后一行可写成矩阵的形式：
1( , )B N BC C B A? ? ? ?? ? ?
4.4 基变换 -(L,K)旋转变换 (换基迭代 )
在单纯形法中，如果得到的基可行解经检
验不是最优解，又不能判定无有限最优解时，
就应该去找一个新的基可行解。
具体做法是从原基可行解中撤换一个列向
量（当然要保证撤换后的各列向量仍线性无
关），得到一个新可行基，这称为基变换。为换
基，先要确定换入变量（进基变量），再确定换
出变量（出基变量），让它们相应的系数列向量
对换，进而便可以求得一个新的基可行解。
（ 1）换入变量的确定：由目标函数表达式
1
1
n
B j j
jm
Z C B b x??
??
?? ?，可以看出，当某个非基
变量 jx 的检验数 0j? ? 时， jx 增加则目标函数值
增大，这时应将 jx 换为基变量。若两个以上的
0j? ? ，为了使目标函数增加得快，直观上一
般选 0j? ? 中最大者对应的非基变量作为换入
变量，即 ? ?m a x 0jk
j ????
.则确定对应的 kx 为
换入变量。此法可称为最大 ?（检验数）规则。
（ 2）换出变量的确定：将基 B 对应的
单纯形表还原成约束方程组：
1 1 1 1 1 1 1 0
1 1 l n 0
1 1 0
m m k k n n
l lm m lk k n l
m m m m m k k m n n m
X a X a X a X a
X a X a X a X a
X a X a X a X a
??
??
??
? ? ? ? ? ??
?
? ? ? ? ? ??
? ? ? ? ? ?
?
?
?
?
??
假设按最大 ? 规则已确定 kX 为换入变量。现
在要从基变量 12,, mX X X中确定一个换出
变量，为了使新的解可行，对换后 ，必须保
证 0 , 1 , 2 ,iX i m??.在上述方程组中，
除 kX 外，其余非基变量仍取 0 值。从而，应
使 0 0 , 1 , 2 ,i i i k kX a a X i m? ? ? ?. 当 0ika ?
时，这是没问题的。因此，只考虑 0ika ? 的
情况，应使 0ik
ik
aX
a? ，故而，当取
00m in 0il
k iki
ik lk
aaXa
aa
??
? ? ???
??
即可 满足 0 , 1 , 2 , ,ix i m??且有
0
00 0
l
l l lk k l lk
lk
aX a a X a a
a
? ? ? ? ?。
由此可见，可按 00m in 0iliki
ik lk
aaa
aa
?
??
? ? ???
??
来确定对应的 lX （单纯形表的第 l 行的基变
量）为换出变量。为此可称为最小 ?（比值）
规则。
从上述讨论可知，这样变换得到的新解
为：
0
0 , 1 , 2 , ,
l
i i ik
lk
aX a a i m i l
a? ? ? ?
00, l
lk
lk
aXX
a
??，其余 0jX ? .
从理论上可以证明，此解仍为基可行解。
4.5 单纯形法计算步骤
步骤 1： 化为标准形（要求 0b? ），确定
初 始 基 ()BE? 和 初 始 基 可 行 解
1 , 0 .BNX B b X???建立初始单纯形表。
步骤 2： 检查非基变量的检验数，若所
有 1 0j j B jC C B P? ?? ? ?，则已得到最优解，
计算停 .否则按 ? ?m a x 0jk
j ????
，确定 kX 为
旋进变量 .
步骤 3： 若对于 0k? ? ,且 1 0kBp? ?（即单
纯形表中 kX 对应的系数列向量非正），则该
问题无有限最优解，计算停；否则转步骤 4.
步骤 4： 计算
? ?11m in ( ) / 0 ( ) /i ik ik l lki B b a a B b a? ??? ? ?
确定单纯形表中第 L行对应的基变量为旋出
变量 .
步骤 5：以 lka 为主元作（ L,K）旋转变换，
得新的单纯形表，转步骤 2.
例 7.计算下列线性规划
12m a x 6 4Z x x??
12
12
12
2 3 10 0
4 2 12 0
,0
xx
xx
xx
???
?
???
? ?
?
解：标准化后 12m a x 6 4Z x x??
1 2 3
1 2 4
1 2 3 , 4
2 3 1 0 0
4 2 1 2 0
, , 0
x x x
x x x
x x x x
? ? ? ?
?
? ? ??
? ?
?
取 34
10
( , )
01
pp ??? ??
??
为 初 始 基 B ，
31
4
100
120B
x
X B b
x
? ????? ? ?
?????? ??， 12 0xx??为初始
基可行解 .按单纯形法计算步骤，计算结果
如下：
C 6 4 0 0
BC BX 1Bb? 1 2 3 4X X X X 0
0
3
4
X
X
100
120 [ 4]
2 3 1 0
2 0 1
? 0 6 4 0 0
0
6
3
1
X
X
40
30
1
0 1
2
11
1 0
2
[ 2]
4
?
由此的最优解： 1 2 3 42 0 , 0X X X X? ? ? ?
最大值： 200Z ?
? -180 30 1 0 - 2
4
6
2
1
X
X
20
20
11
0 1
24
13
1 0 -
48
?
? -200 150 0 - -24
例 8： 计算下列线性规划
1 2 3m a x 3Z x x x? ? ?
1 2 3
1 2 3
13
1 2 3
2 11
4 2 3
21
, , 0
x x x
x x x
xx
x x x
? ? ??
?
? ? ? ??
?
? ? ?
?
? ?
?
解：加入松弛变量及人工变量得
1 2 3 6 7m a x 3Z x x x M x M x? ? ? ? ?
1 2 3 4
1 2 3 5 6
1 3 7
1 2 3 4 5 6 7
2 11
4 2 3
21
, , , , , , 0
x x x x
x x x x x
x x x
x x x x x x x
? ? ? ??
?
? ? ? ? ? ??
?
? ? ? ?
?
? ?
?
? ?467
1 0 0
, , 0 1 0
0 0 1
B p p p
??
????
??
??
，
4
1
6
7
11
3
1
B
x
X B b x
x
?
????
????? ? ?
????
?? ??
?? ??
，
1
2
3
4
0
0
0
0
N
x
x
X
x
x
?? ??
?? ??
?? ????
?? ??
?? ??
????
列出初始单纯形表，并计 算如下：
C 3 1 1 0 0 MM? ? ? ?
BC BX 1Bb? 1 2 3 4 5 6 7X X X X X X X
0
M
M
?
?
4
6
7
X
X
X
11
3
1
1 2 1 1 0 0 0
4 1 2 0 1 1 0
20 [ 1 ] 0 0 0 1
?
??
?
? 4M 3 6 1 1 3 0 0 0M M M M? ? ? ? ? ?
0
1
M?
?
4
6
3
X
X
X
10
1
1
3 2 0 1 0 0 1
0 0 0 1 1 2
2 0 1
[1
0 0 0 1
]
??
??
?
? M+1 1 1 0 0 0 1 3M M M? ? ? ?
0
1
1
?
?
4
2
3
X
X
X
12
1
1
0 0 1 2 2 5
0 1 0 0 1 1 2
2 0 1 0 0 0
[ 3 ]
1
??
??
?
? 2 1 0 0 0 1 1 1MM? ? ? ? ?
3
1
1
?
?
1
2
3
X
X
X
4
1
9
1 2 2 5
1 0 0
3 3 3 3
0 1 0 0 1 1 2
2 4 4 7
0 0 1 - -
3 3 3 3
??
??
? -2 1 1 1 2000 3 3 3 3MM? ? ? ? ? ?
最优解：
1
2
3
4
1
9
x
x
x
?? ??
?? ???
?? ??
????
????
，最优值： 2Z ?
§ 5.单纯形法的进一步讨论
5.1 两阶段法
对于前面介绍的大 M 法，如果计算机求
解时，只能用很大的正数代替 M，这就可能
造成计算上的错误。下面介绍不需要引进相
当大正数 M 的两阶段法。
第一阶段： 求初始基可行解：在约束中
添加人工变量，使 约束矩阵出现单位子矩
阵，然后以这些人工变量之和的相反数 W 求
最大为目标函数，进行求解。
若第一阶段最优解对应的最优值等于
零，则所有人工变量一定都取零值，说明原
问题存在基可行解，可以进行第二阶段计
算，否则原问题无可行解，应停止计算。
第二阶段： 求原问题的最优解。将第一
阶段计算得到的最终表，除去人工变量，恢
复原来的目标函数，并以第一阶段的最优解
为初始基可行解，重新计算检验数，然后用
单纯形法继续求解。
例 9.用两阶段法求解下列线性规划
1 2 3m a x 3Z x x x? ? ?
1 2 3
1 2 3
13
1 2 3
2 11
4 2 3
21
, , 0
x x x
x x x
xx
x x x
? ? ??
?
? ? ? ??
?
? ? ?
?
? ?
?
解： 加入松弛变量及人工变量，给出第一阶
段数学模型：
67m a x W x x? ? ?
1 2 3 4
1 2 3 5 6
1 3 7
1 2 3 4 5 6 7
2 11
4 2 3
21
, , , , , , 0
x x x x
x x x x x
x x x
x x x x x x x
? ? ? ??
?
? ? ? ? ? ??
?
? ? ? ?
?
? ?
?
取 ? ?467,,p p p为初始基 B,列出初始单纯形
表，计算如下：
C 0 0 0 0 0 1 1??
BC BX 1Bb? 1 2 3 4 5 6 7X X X X X X X
0
1
1
?
?
4
6
7
X
X
X
11
3
1
1 2 1 1 0 0 0
4 1 2 0 1 1 0
20 [ 1 ] 0 0 0 1
?
??
?
? -4 6 1 3 0 1 0 0??
0
1
0
?
4
6
3
X
X
10
1
1
3 2 0 1 0 0 1
0 0 0 1 1 2
2 0 1
[1
0 0 0 1
]
??
??
?
? 1 0 1 0 0 1 0 3??
0
0
0
4
2
3
X
X
X
12
1
1
3 0 0 1 2 2 5
0 1 0 0 1 1 2
2 0 1 0 0 0 1
??
??
?
? 0 0 0 0 0 0 1 1??
因为最优解中人工变量均等于零，所以
可以进行第二阶段的运算：
C 3 - 1 - 1 0 0 1 1??
BC BX 1Bb? 1 2 3 4 5 6 7X X X X X X X
0
1
1
?
?
4
2
3
X
X
X
12
1
1
0 0 1 2 2 5
0 1 0 0 1 1 2
2 0 1 0 0 0
[ 3 ]
1
??
??
?
? 2 1 0 0 0 1 1 1? ? ?
3
1
1
?
?
1
2
3
X
X
X
4
1
9
12
1 0 0 -
33
0 1 0 0 1
24
0 0 1 -
33
?
? -2 110 0 0 33??
由此得原问题最优解：
1 2 3 4 54 , 1 , 9 , 0x x x x x? ? ? ? ?
最大值： 2Z ?
5.2 退化与循环
单纯形法计算中，基变量一般都取非零
值，非基变量都取零值，如果某个基可行解
中存在取零值的基变量，则称该解为退化
解。在退化情况下，如果取退化的变量为旋
出变量，则变化后的解仍为退化解，且目标
函数值不变。在以后的迭代中，如果每次都
取退化的基变量为旋出变 量，则迭代可能只
在可行域的几个顶点中反复进行，即出现计
算过程的循环问题，而达不到最优解。
为避免出现循环问题， 1974 年 Bland 提出一种简
便的规则：
（ 1）若 ? ?m in 0jkj ???，则以 kx （脚标最小的非
基变量为旋入变量）
（ 2）计算 ? ?1m in ( ) / 0i ik ikB b a a? ?，当存在两
个或两个以上的比值都等于 ? 时，选取脚标最小的基
变量为换出变量。
可以证明，按 Bland 规则计算时，一定可以避免
循环 。 实际计算中，循环现象极为罕见，目前仅有人
为构造的几个例子会出现循环现象。因此，计算时完
全可以不考虑循环问题。
5.3 标准型的其他形式
有的教材定义线性规划的标准型为：
m in
0
Z CX
A X b
X
?
??
?
??
如仍定义检验数为 1j j B jC C B P? ???，由
目标函数表达式为 1
1
n
B j j
jm
Z C B b x??
??
?? ?
易知，以目标函数极小化为标准型的线
性规划问题的最优性检验规则为：对某基可
行解 1BX B b?? ，其余 0jX ? ， 若所有检验数
1 0 , 1 , 2 ,j j B jC C B P j m m n? ?? ? ? ? ? ?则该
解为最优解。
|
|
