MBA 运筹学讲义
运筹学是一门应用科学，它广泛应用现代科学技术知识、用定量分析
的方法，解决实际中提出的问题，为决策者选择最优决策提供定量依据。
运筹学的核心思想是建立在优化的基础上。
例如，在线性规划中体现为两方面：
（1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完
成？
（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务
最多？
运筹学解决问题的主要方法是用数学模型描述现实中提出的决策问题，
用数学方法对模型进行求解，并对解的结果进行分析，为决策提供科学依
据。
随着计算机及计算技术的迅猛发展，目前对运筹学的数学模型的求解
已有相应的软件。因此，在实际求解计算时常可借助于软件在计算机上进
行，这样可以节省大量的人力和时间。
第一部分 线性规划内容框架
LP 问题
基本概念 数学模型 可行解、最优
解
实际问题 LP 问题 解的概念 基本解、基可
行解
提 出 基本最优解
基本方法
图解法
原始单纯形法
单纯形法 大
M 法
人工变量法
对偶单纯形法 两 阶
段法
对偶理论
进一步讨论
灵敏度分析──参数规划*
在经济管理领域内应用
运输问题（转运问题）
特殊的 LP 问题 整数规划
多目标 LP 问题*
第一部分 线性规划（Linear Programming）及其应用
第一章 LP 问题的数学模型与求解
§1 LP 问题及其数学模型
（一）引例 1（生产计划的问题）
某工厂在计划期内要安排生产Ⅰ、Ⅰ的两种产品，已知生产单位产品所
需的设备台时，A、B 两种原材料的消耗以及每件产品可获的利润如下表
所示。问应如何安排计划使该工厂获利最多？
Ⅰ Ⅰ 资源限量
设备 1 2 8(台时)
原材料 A 4 0 16(kg)
原材料 B 0 4 12(kg)
单位产品利润（元） 2 3
该问题可用一句话来描述，即在有限资源的条件下，求使利润最大的
生产计划方案。
解：设 x1,x2 分别表示在计划期内生产产品Ⅰ、Ⅰ的产量。由于资源的
限制，所以有：
机器设备的限制条件：x1+2x2≤8
原材料 A 的限制条件： 4x1≤16 （称为资源约束条件）
原材料 B 的限制条件： 4x2≤12
同时，产品Ⅰ、Ⅰ的产量不能是负数，所以有
x1≥0，x2≥0 （称为变量的非负约束）
显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有
许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产
量 x1，x2 以得到最大的利润，即使目标函数
Z=2x1+3x2 的值达到最大。
综上所述，该生产计划安排问题可用以下数学模型表示：
maxz=2x1+3x2
引例 2. （营养配餐问题）
假定一个成年人每天需要从食物中获取 3000 卡路里热量，55 克蛋白
质和 800 毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热
量和营养成份以及市场价格如下表所示。问如何选择才能满足营养的前提
下使购买食品的费用最小？
序号 食品名称 热量(卡路里) 蛋白质(克) 钙(mg) 价格(元)
1 猪肉 1000 50 400 10
2 鸡蛋 800 60 200 6
3 大米 900 20 300 3
4 白菜 200 10 500 2
解:设 xj(j=1,2,3,4)为第 j 种食品每天的购买量，则配餐问题数学模型为
minz=10x16x23x32x4
（二）LP 问题的模型
上述两例所提出的问题，可归结为在变量满足线性约束条件下，求使
线性目标函数值最大或最小的问题。它们具有共同的特征。
（1）每个问题都可用一组决策变量(x1,x2,…xn)表示某一方案，其具体
的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可对
0
124
164
82
..
21
2
1
21
xx
x
x
xx
ts
)4,3,2,1(0
800500300200400
5510206050
300020090080010000
.
4321
4321
4321
jx
xxxx
xxxx
xxxx
tx
j
变量的取值加以约束，如非负约束。
（2）存在一组线性等式或不等式的约束条件。
（3）都有一个用决策变量的线性函数作为决策目标（即目标函数），
按问题的不同，要求目标函数实现最大化或最小化。
满足以上三个条件的数学模型称为 LP 的数学模型，其一般形式为：
max(或 min)z=c1x1+c2x2+…+cnxn
()
()
或紧缩形式
max(或 min)z=
()
或矩阵形式
max(或 min)z=cx
()
或向量形式：
max(或 min)z=cx
0
),(
),(
),(
.
21
2221
22222221
11212211
n
mnmnmm
nn
nn
xxx
bxaxaxa
bxaxaxa
bxaxaxa
ts
n
j
jj xc
1
0
),,2,1(),(
1
j
n
j
ijj
x
mibxa
0
),(
X
bAX
()
()
其中 C=(c1,c2,…,cn)，称为价值系数向量；
称为技术系数矩阵（并称消耗系数矩阵）
=(p1,p2,…,pn)
称资源限制向量
X=(x1,x2,…,xn)T 称为决策变量向量。
（三）LP 问题的标准型
1.为了讨论 LP 问题解的概念和解的性质以及对 LP 问题解法方便，必
须把 LP 问题的一般形式化为统一的标准型：
maxz= ；
或
maxz=cx
或
),,2,1(0
),(
1
njX
bxp
j
n
j
jj
mnmm
n
n
aaa
aaa
aaa
A
,,
,,
,,
21
22221
11211
mb
b
b
b
2
1
n
j
jj xc
1
),,2,1(0
),,2,1(
1
njx
mibxa
j
n
j
ijj
0X
bAX
),,2,1(0
1
njx
bxp
j
n
j
jj
maxz=cx
标准型的特点：
Ⅰ目标函数是最大化类型
Ⅰ约束条件均由等式组成
Ⅰ决策变量均为非负
Ⅰbi(i=1,2,…,n)
2.化一般形式为标准型
ⅠminzⅠmax(-z)=-cx
Ⅰ“Ⅰ”Ⅰ左边+松驰变量；“Ⅰ”Ⅰ左边－“松驰变量”
Ⅰ变量 xjⅠ0Ⅰ-xjⅠ0 变量 xj 无限制Ⅰ令 xj=xjⅠ－xjⅠ
Ⅰbi<0Ⅰ等式两边同乘以(-1)。
3.模型隐含的假设
Ⅰ比例性假定：决策变量变化的改变量与引起目标函数的改变量成比
例；决策变量变化的改变量与引起约束方程左端值的改变量成比例。此假
定意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是
一个常数。
Ⅰ可加性假定：每个决策变量对目标函数和约束方程的影响是独立于
其它变量的。
Ⅰ连续性假定：决策变量应取连续值。
Ⅰ确定性假定：所有的参数(aij,bi,cj)均为确定，所以 LP 问题是确定型
问题，不含随机因素。
以上 4 个假定均由于线性函数所致。在现实生活中，完全满足这 4 个
假定的例子并不多见，因此在使用 LP 时必须注意问题在什么程度上满足
这些假定。若不满足的程度较大时，应考虑使用其它模型和方法。如非线
性规划，整数规划或不确定型分析方法。
对 LP 标准型，我们还假定 r(A)=m<n。
（四）LP 问题的解的概念
设 LP 问题
maxz= ()
()
()
1.从代数的角度看：
可行解和最优解 满足约束条件()和()的解 X=(x1,x2,…,xn)T 称为
可行解。所有可行解构成可行解集，即可行域 。
而使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最
优值。
求解 LP 问题就是求其最优解和最优值，但从代数的角度去求是困难
的。
2.从 LP 角度看：
基：设 A 为 mxn 矩阵，r(A)=m，B 是 A 中的 mxm 阶非奇异子矩阵
（即|B|Ⅰ0），则称 B 是 LP 问题的一个基。
若 B 是 LP 问题的一个基，则 B 由 m 个线性独立的列向量组成，即
B=(Pr1,Pr2,…,Prm)，其中 Prj=(a1rj,a2rj,…,amrj)T，(j=1,2,…,m)称为基向理。与其
向量 Prj 相对应的变量 xrj 称为基变量，其它变量称为非基变量。显然，对
应于每个基总有 m 个基变量，n－m 个非基变量。
基本解与基可行解 设 B 是 LP 问题的一个基，令其 n－m 个非基变量
n
j
jj xc
1
n
j
ijj nibxa
1
),,2,1(
),,2,1(0 njx j
}0,{ xbAXS x
均为零，所得方程的解称为该 LP 问题的一个基本解。显然，基 B 与基本
解是一一对应的，基本解的个数≤Cmn。在基本解中，称满足非负条件的基
本解为基可行解，对应的基称为可行基。
退化解 如果基解中非零分量的个数小于 m，则称此基本解为退化的，
否则是非退化的。
最优基 如果对应于基 B 的基可行解是 LP 问题的最优解，则称 B
为 LP 问题的最优基，相应的解又称基本最优解。
问题解之间的关系如图所示
Ⅰ
（五）两个变量 LP 问题的图解法
问题解的几何表示。以引例为例说明
maxz=2x1+3x2
按以下顺序进行：
解：（1）画出直角坐标系；
（2）依次做每条约束线，标出可行域的方向，并找出它们共同的
0,0
124
164
82
21
2
1
21
xx
x
x
xx Ⅰ
Ⅰ
Ⅰ
Ⅰ
可
行
解
基本解
基可行解
可行域；
（3）任取一目标函数值作一条目标函数线（称等值线），根据目标
函数（最大或最小）类型，平移该直线即将离开可行域上，则与目标函数
线接触的最终点即表示最优解。
图 1
其中，将目标函数 Z=2x1+3x2 改写为 ，因此，它可
以表示为：以 z 为参数，以 为斜率的一族平行线。位于同一条直线上
的点具有相同的值。
解的几种情况：
（1）此例有唯一解 Q2，即 x1=4,x2=2,z=14
（2）有无穷多最优解（多重解），若将目标函数改为 z=2x1+4x2 则线
段 Q2，Q3 上的点均为最优解。
zxx
3
1
3
2
12
3
2
x2 Ⅰ
Ⅰ
Ⅰ
Q2
Q3Q4
B
Q1 A
x1
3
2
1
0
0 1 2 3 4
（3）无界解
求 max 无界
但求 min 有唯一解
（4）无可行解
可行域与最优解间的关系：
可行域 最优解
空 集 无最优解（无可行解）
有界集 唯一最优解
多重解
无界集 无有限最优解（无界解）
0
x2
x10
x1
x2
结论：（1）LP 问题的可行域是凸集（凸多边形，凸多面体，…）；
（2）LP 问题最优解若存在，则必可在可行域的顶点上得到；
（3）LP 问题的可行域的顶点个数是有限的；
（4）若 LP 问题有两个最优解，则其连线上的点都是最优解。
因此，求解 LP 问题可转化为如何在可行域的顶点上求出使目标函数值达
到最优的点的问题。
2.基可行解的几何意义
对例 1 LP 问题标准化为 maxZ=2x1+3x2
可求得所有的基本解：
x(1)=(0,0,8,16,12)T(0 点),x(2)=(4,0,4,0,12)T(Q1 点)
x(3)=(4,2,0,0,4)T(Q2 点),x(4)=(2,3,0,8,0)T(Q3 点)
x(5)=(0,3,2,16,0)T(Q4 点),x(6)=(4,3,-2,0,0)T(C 点)
x(7)=(8,0,0,-16,12)T(A 点),x(8)=(0,4,0,16,-4)T(B 点)
但 A、B、C 三点是非可行域上的点，即非可行解。因此，x(1)，x(2)，
x(3)，x(4)，x(5)才是基可行解，它们与可行域的顶点相对应。于是还有
结论：（5）对于标准型的 LP 问题，X 是基可行解的充要条件是 X 为
可行域的顶点。
（6）LP 问题可行域顶点的个数=基可行解的个数≤基的个数≤Cmn
3.图解法只适用于两个变量（最多含三个变量）的 LP 问题。
4.求解 LP 问题方法的思考：
Ⅰ完全枚举法，对 m、n 较大时，Cmn 是一个很大的数，几乎不可能；
0,,
124
164
82
51
52
41
321
xx
xx
xx
xxx
Ⅰ从可行域的一个顶点（基可行解）迭代到另一个顶点（基可行解）。
§2 单纯形法与计算机求解
1.解 LP 问题单纯形法的基本思路：
求出一个初始基可行解
y
判别此基可行解是否
最 优 解
N
求出使目标函数值得到
改善的基可行解
2.单纯形法的计算步骤（表格形式）
（1）建立初始单纯形表，假定 B=I，b≥0
设 maxZ=c1x1+c2x2+…+cnxn
将目标函数改写为：-Z+c1x1+c2x2+…+cnxn=0
把上述方程组和目标函数方程构成 n+1 个变量，m+1 个方程的方程组，
并写成增广矩阵的形式：
),,2,1(0
11
221122
111111
njx
bxaxax
bxaxax
bxaxax
j
mnmnmmmm
nnmm
nnmm
停
-Z x1 x2 … xm xm+1… xn
0 1 0 … 0 1m+1 … 1n 1
0 0 1 … 0 2m+1 … 2n 2
0 0 0 … 1 mm+1 … mn m
-1 c1 c2 … cm cm+1… cn 0
以非基变量表示基变量形式 代入 Z 中的基变量,
有
令
于是
因此，上述的增广矩阵就可写成：
Z x1 x2 … xm xm+1… xn
0 1 0 … 0 1m+1 … 1n 1
0 0 1 … 0 2m+1 … 2n 2
0 0 0 … 1 mm+1 … mn m
b
a a b
a a b
a a b
n
j
jijii xabx
1
m
i
n
mj
n
mj
jjjijii xcXabcZ
1 1 1
)(
m
i
m
i
n
mj
n
mj
jjjjiiii xcxacbc
1 1 1 1
)(
m
i
n
mj
jj
m
i
ijiii xcacbc
1 1 1
)(
m
i
m
i
jiijii acZbcZ
1 1
0 ,
n
mj
jjjo xcZZZ
1
)(
b
a a b
a a b
a a b
1 0 0 … 0 … －cn
再令
则上述增广矩阵可写成下面表格形式：即初始单纯形表 T（B）
Cj C1……Cm cm+1……cn
CB xB x1……xm xm+1……xn
Ⅰi
C1 x1 1 1……0 a1m+1……a1n
C2 x2 2 0……0 a2m+1……a2n
： ： ： ： ： ：………：
Cm xm m 0……1 amm+1……amn
Z Z0 0……0 Ⅰm+1……Ⅰn ⅠⅠj 检验数行
上述初始单纯形表可确定初始可行基和初始基可行解：
B=(P1,P2,…,Pm)=I, x=(b1,b2,…,bm, 0……0)T
从初始单纯形表建立的过程可以看到以下事实：
（1）凡 LP 模型中约束条件为“≤”型，在化为标准型后必有 B=I，如
果 b≥0，则模型中约束方程的各数据不改变符号照抄在表中相应的位置。
目标函数非基变量的系数则以相反数填入检验数行各相应位置。
（2）在单纯形表中，凡基变量所在的列向量必是单位列向量，其相应
的检验数均为零。
（3）
更好表现一般规律的在矩阵形式的单纯形表中
1
1
1
m
m
i
imi cac
m
i
iniac
1
m
i
iibc
1
m
i
ijijjjj accZc
1
b
b
b
b
m
i
m
i
jijijjjii nmjcaccZbcZ
1 1
0 ),1(,
设 MaxX=CX MaxZ=CX+0XL
其标准型为
将系数矩阵(A,I)分划为(B,N,I)，其中 B 为可行基，对应于基变量向量
XB,N 对 应 于 XN ， I 对 应 于 XL,(XN,XL) 为 非 基 变 量 向 量 。 于 是
(X,L)T=(XB,XN,XL)T,(C,0)=(CB,CN,0)。因此，矩阵形式的 LP 模型改写为：
Ⅰ
用非基变量向量表示基变量向量，有
XB=B-1b－B-1NXN－B-1XL
代入目标函数中有
Z =CB(B-1b－B－1NXN－B-1XL)+CNXN+0XL
=CBB-1b－CBB-1NXN－CBB-1XL)+CNXN
=CBB-1b－(CBB-1N－CN)XN－CBB-1XL
将
写成对应于基 B 的矩阵形式的单纯形表 T（B）：
CⅠ CB CN CL
XB XN XL
0x
bAx
0, L
Lx
xx
bIxA
LNNBB
L
N
B
NB XXCXCMaxZ
X
X
X
CCMaxZ 0)0,,(
0,,
),,(
LNB
L
N
B
XXX
b
X
X
X
INB
0,, LNB
LNB
XXX
bIXNXBX
bBXBNXBX
bBCXBCXCNBCZ
LNB
BLBNNB
111
111 )(
b
XB 1 B-1N B-1
Z CBB-1b 0 CBB
-1N－CN CBB-1
例如将例 1 化成标准型后如下表 T（B）：
Cj 2 3 0 0 0
CB XB x1 x2 x3 x4 x5
Ⅰi
0 x3 8 1 2 1 0 0
0 x4 16 4 0 0 1 0
0 x5 12 0 4 0 0 1
-Z 0 -2 -3 0 0 0 Ⅰσj
初始可行基 B=(P3,P4,P5)=I, X=(0,0,8,16,12)T
（2）判别最优解
1Ⅰ 在 T(B)中，若所有的检验数σj≥0 (j=1,2,…,n)
则 B 为最优基，相应的基可行解为最优解，停止计算。
2Ⅰ 在 T(B)中，若有σk<0 (1ⅠkⅠn)，且 xk 的系数列向量 PkⅠ0，则该
问题无界，停止计算。否则转入（3）
（3）换基迭代（基变换）
1Ⅰ 先确定入基变量 Xk: k=min{j| Ⅰj<0}
2Ⅰ 按最小比值原则确定出基变量 xL：
3Ⅰ 以 为主元，进行初等行变换（又称旋转变换）即将列向量
变换为单位列向量：
返回（2）。
bB 1
b
Lk
L
ik
ik
i
a
b
a
a
b
0|min
LKa KP
换基迭代的关键在于将换入变量对应的列向量 用初等行变换方法
变换成单位列向量。其中主元 变成 1。即
第 L 个分量
如果在最终表中有非基变量的检验数为 0，则该问题有多重最优解。
3.单纯形法的进一步讨论──用人工变量法求初始基可行解
（一）人工变量法
若对 LP 模型标准化后，不具有 B=I 时，如何办？此时可采用人工变
量法得到初始基可行解。
所谓人工变量法是在原问题不含有初始可行基 B=I 的情况下，人为的
对约束条件增加虚拟的非负变量（即人工变量），构造出含有 B=I 的另一
个 LP 问题后求解。当增加的人工变量全部取值为 0 时，才与原问题等价。
这样，新问题将有一个初始基可行解（以人工变量为基变量），可用单纯形
法进行迭代。经迭代后，若人工变量全部被换成非基变量，则原问题的约
束条件被恢复，同时也得到一个基可行解。在最终表中若不能全部被换出，
则说明原问题无可行解。
因此，该法的关键在于将人工变量全部换出。
人工变量法常见的有大 M 法和两阶段法。
（1）大 M 法（通过下例简略介绍其方法与步骤）
例，用大 M 法求解
KP
LKa
0
:
1
:
0
0
:
:
1
2
1
mk
k
k
k
k
a
a
a
a
P
MinZ=x1+
解：MinZ=x1++++Mx5+Mx6
其中 x3,x4 为松驰变量，x5,x6 为人工变量，M 为任意大的正数。
注意到：Ⅰ分别在约束条件增加人工变量 x5,x6 是为了构成“人工基”
Ⅰ对于 Min 的目标函数采用(+M)，而对于 Max 的目标函数则
采用(-M)作为人工变量的系数,是强加于人工变量的一种惩罚,其目的是为
了强制人工变量由变量转为非基变量，使之恢复原问题，或与原问题等价。
Ⅰ对于 minZ 判别最优性准则应是 Cj－Zj≤0。
Ⅰ大 M 法适合于手算，不适用于计算机求解。
（2）两阶段法
第一阶段：不考虑原问题是否存在基可行解；给原 LP 问题的约束条
件加入人工变量，构造仅含人工变量的目标函数并要求实现最小化（即使
原 LP 问题目标函数是求最大化）的辅助问题：
MinW=xn+1+…+xn+m
0,
2
33
21
21
21
xx
xx
xx
0,,0,,0,
2
33
654321
6421
5321
xxxxxx
xxxx
xxxx
0,1
11
222121
111111
mn
mmnnmnm
nnn
nnn
xx
bxxaxa
bxxaxa
bxxaxa
然后用单纯形法求解（1）。若 WⅠ0，则原问题无可行解，停止计算。
若 W=0，且所有的人工变量均为非基变量，则去掉人工变量后可得到原问
题的基可行解；如果人工变量中含有为 0 的基变量时（即退化解），则可再
进行初等行变换将其换出，从而获得原问题的基可行解。
第二阶段：在第一阶段所得的基可行解的基础上，将最终表中的人工
变量列删去，同时将人工目标函数行换入原问题的目标函数作为第二阶段
计算的初始表。
仍以上例为例用两阶段法求解。
MinZ=x1++0x3+0x4
原问题：
MinW=x5+x6
辅助问题：
书中第 19 页表 和表 的说明：（1）第一阶段的初始表中非基
变量的检验数=人工变量所在行的非基变量相应系数之和，目标函值值=人
工变量所在行相应常数之和。
（2）第二阶段单纯形表中目标函数系数应将非基变量表示基变量后
所得结果填入，或先直接填入原系数，再通过初等行变换使基变量的检验
数为 0。
（3）若 maxZ，则可转化为 minZ1(Z1=-Z)
0,,0,
2
33
4321
421
321
xxxx
xxx
xxx
0,,0,,0,
2
33
654321
6421
5321
xxxxxx
xxxx
xxxx
（二）退化
单纯形法计算中用Ⅰ规则决定换出变量时，有时出现两个以上相同的
最小比值，这样在下一次迭代中就有一个或几个基变量等于 0，出现退化
解，如某个最大化问题的单纯形表为：
Cj 4 0 3 0 0 0
CB XB x1 x2 x3 x4 x5 x6
Ⅰi
0 x5 6 2 0 1 0 1 0 3
0 x4 3 [1] -1 0 1 0 0 3
0 x6 5 1 1 1 0 0 1 5
Z 0 -4 0 -3 0 0 0 ⅠⅠj
0 x5 0 0 [2] 1 -2 1 0 0
4 x1 3 1 -1 0 1 0 0 /
0 x6 3 0 2 1 -1 0 1 1
Z 12 0 -4 -3 4 0 0 ⅠⅠj
在出现退化解后的继续迭代中，有可能出现基循环：
B1ⅠB2Ⅰ……ⅠB1
这样迭代下去便永远得不到最优解。
解决基循环的方法很多，如“摄动法”、“字典序法”等等。
在计算机上常采用“Bland 规则”：
（1）取表中下标最小的非基变量 xk 为换入变量，即
k=min{j | Ⅰj>0}
（2）按Ⅰ规则计算，若存在两个相同以上最小比值时，选取下标最小
的基变量为换出变量 xL，即
b
值得庆幸的是出现基循环是罕见的。
§3 对偶理论与灵敏度分析
一、LP 的对偶问题
1.引例 前已述引例 1 是一个在有限资源的条件下，求使利润最大的
生产计划安排问题，其数学模型为：
maxZ=2x1+3x2
现从另一角度考虑此问题。假设有客户提出要求，租赁工厂的设备台
时和购买工厂的原材料 A、B，为其加工生产别的产品，由客户支付台时
费和材料费，此时工厂应考虑如何为每种资源的定价问题？
解：设 y1,y2,y3 分别表示出租单位设备台时的租金和出售单位原材料 A、
B 的价格（含附加值）
工厂决策者考虑：
（1）出租设备和出售原材料应不少于自己生产产品的获利，否则不如
自己生产为好。因此有
工厂的总收入为 W=8y1+16y2+12y3
（2）价格应尽量低，否则没有竞争力（此价格可成为与客户谈判的底
}0|min{|min ik
ik
i
r aa
b
rL
0,
124
164
82
21
2
2
21
xx
x
x
xx
342
24
31
21
yy
yy
（设备）
（原材料 A）
（原材料 B）
价）
租赁者考虑：希望价格越低越好，否则另找他人。
于是，能够使双方共同接受的是
MinW=8y1+16y2+12y3
上述两个 LP 问题的数学模型是在同一企业的资源状况和生产条件下
产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关。
称这两个 LP 问题是互为对偶的两个 LP 问题。其中一个是另一个问题的对
偶问题。
2.从矩阵形式讨论互为对偶 LP 问题
由例 1 有 maxZ=cx
由矩阵形式的单纯形表中可知：
检验数的表达式为： CBB-1N－CN 和 CBB-1
当
表示 LP 问题已得到最优解
令 Y=CBB-1,且Ⅰ有 YⅠ0
由于基变量 XB 的检验数为 0，可改写成 CBB-1B－CB=0
因此，包括基变量在内的所有检验数可写成
(CBB-1B－CB, CBB-1N－CN)=(CBB-1A－C)= YA－C≥0
0
342
24
.
321
31
21
yyy
yy
yy
ts
0X
bYX
0
0
1
1
BC
CNBC
B
NB Ⅰ
Ⅰ
即 YAⅠC
又对Ⅰ Y=CBB-1，两边右乘 b，有
Yb=CBB-1b=Z
由于 Y 无上界，所以只有最小值，因此有
MinW=Yb
它是原问题 {maxZ=CX| AXⅠb,XⅠ0}的对偶问题
于是，对称形式下两个互为对偶 LP 问题的数学模型为：
MaxZ=CX MinW=Yb
与
任何一个 LP 问题均有一个对偶 LP 问题与之匹配。
对偶理论就是研究 LP 问题及其对偶问题的理论，它是 LP 理论中的重
要内容之一。
二、对偶理论
1.原问题与对偶问题的关系如下表所示
原 始 对 偶 表
原问题 Max（对偶问题） 对偶问题 Min（原问题）
约束条件数=m 变量个数=m
第 i 个约束条件为“”
第 i 个约束条件为“≥”
第 i 个约束条件为“=”
第 i 个变量≥0
第 i 个变量≤0
第 i 个变量无限制
变量个数=m 约束条件个数=n
第 i 个变量≥0
第 i 个变量≤0
第 i 个变量无限制
第 i 个约束条件为“”
第 i 个约束条件为“≥”
第 i 个约束条件为“=”
0Y
CYA
0X
bYX
0Y
CYA
第 i 个约束条件的右端项
目标函第 i 个变量的系数
目标函数第 i 个变量的系数
第 i 个约束条件的右端顶
2.对偶问题的基本性质
MaxZ=CX MinW=Yb
设
（1）（对称性）对偶问题的对偶是原问题；
（2）（弱对偶性）若 是原问题的可行解， 是对偶问题的可行解；
则 ；
（3）（无界性）若原问题（对偶问题）为无界解，则其对偶问题（原
问题）无可行解；
（4）（最优性准则），若 、 分别是互为对偶问题的可行解，且 C
= b，则 、 分别是它们的最优解；
（5）（对偶定理）若互为对偶问题之一有最优解，则另一问题必有最
优解，且它们的目标函数值相等。
从上述性质中，可看到原问题与对偶问题的解必然是下列三种情况之一：
Ⅰ原问题与对偶问题都有最优解，且 CX=Yb；
Ⅰ一个问题具有无界解，则它的对偶问题无可行解；
Ⅰ两个问题均无可行解。
（6）（互补松驰性），若 X*、Y*分别是原问题的对偶问题的可行解，
则 X*、Y*是最优解的充要条件是：Y*XS=0,YSX*=0(其中 XS,YS 分别是原问
题和对偶问题的松驰变量向量)。或，X*、Y*分别是原问题和对偶问题最优
解的充要条件是：
Ⅰ若 y*i>0，则ⅠaijX*j=bi
0X
bYX
0Y
CYA
X Y
bYXC
X Y
X Y X Y
Ⅰ若ⅠaijX*j<b，则 y*i=0
Ⅰ若 X*j>0，则Ⅰaijy*i=cj
Ⅰ若Ⅰaijy*i>cj，则 X*j=0
三、对偶单纯形法
1.单纯形法的重新解释
X*是最大化原 LP 问题最优解的充要条件是同时满足
因此，单纯形法是在保持原始可行下，经过迭代，逐步实现对偶可行，
达到求出最优解的过程。
根据对偶问题的对称性，也可以在保持对偶可行下，经过迭代，逐步
实现原始可行，以求得最优解。对偶单纯形法就是这种思想所设计的。
2.对偶单纯形法的计算步骤：
举例说明
3.对偶单纯形法与单纯形法的不同之点：
Ⅰ不要求模型中 b≥0
Ⅰ先确定换出变量 xL，再确定换入变量 xK
Ⅰ
4.对偶单纯形法适用对象
ⅠmaxZ=CX(C≤0) ⅠmaxZ=CX
（b 无限制），
0
0
1
1
NB CNBC
bB
rk
k
rj
rj
j
j a
a
a
0|min
0X
bAX
),,2,1(
0
)(
)(
rt
X
bAX
tl
t
Ⅰ （称为原始可行条件）
Ⅰ （称为对偶可行条件）
Ⅰ当变量个数（约束个数时，可先转化为其对偶问题，再用单纯形法
或对偶单纯形法解之
Ⅰ进行灵敏度分析时，有时会用到此法
四、对偶解的经济含义和影子价格
1.对偶解 Y*=CBB-1 的经济含义
设互为对偶的 LP 问题
maxZ=CX minW=Yb
(原) (对)
有 Z*=CBB-1b=W* (其中 B 为最优基)
因此
或者说 Z*=y*1b1+y*2b2+y*mbm
则
其含义是：若对原问题右端常数项向量 b 中的某一常数项 bi 增加一个
单位，目标函数的最优值 Z*的变化将是 Yi*。换句话说，Yi*表示当 bi 增加
一个单位时，目标函数最优值的相应增量。实质上 Yi*就是第 i 种资源边际
价值的一种表现，也是对第 i 种资源的一种估价。
事实上，如引例中互为对偶 LP 问题分别描述生产计划问题和资源的
定价问题，其数学模型分别是：
maxZ=2x1+3x2 minW=8y1+16y2+12y3
0X
bAX
0Y
CYA
*
* 1 YBC
b
Z
B
*
*
i
i
y
b
Z
(原问题) (对偶问题)
对原问题用单纯形法求解所得最终表为
C 2 3 0 0 0
CB XB b x1 x2 x3 x4 x5
2 x1 4 1 0 0 1/4 0
0 x5 4 0 0 -2 1/2 1
3 x2 2 0 1 1/2 -1/8 0
Z 14 0 0 0
由此，它们的最优解分别是 X*=(4,2)T 和 Y=(,,0)
Z*=W*=14=8Y1*+16Y2*12Y3*
其中 Y1*= 表示单独对设备台时增加 1 个单位，可使 Z 值增加
个单位的利润；Y2*= 表示单独对原材料 A 增加 1 个单位，可使 Z 值
增加 个单位的利润；而 Y3*=0 表示单独对原材料 B 增加一个单位，
却不使 Z 值增加。这是因为从最终表中可看出，在最优方案中，松驰变量
x5=4，即表示在最优生产方案中，原材料 B 尚有 4 个单位剩余被闲置，不
产生任何经济效益。
2.影子价格的定义
把某一经济结构中的某种资源，在最优决策下的边际价值称为该资源
在此经济结构中的影子价格。
0,
124
164
82
21
2
1
21
xx
x
x
xx
0,0,
342
24
321
31
21
yyy
yy
yy
0
*
*,
*
*,
*
* 3
2
2
1
1
ib
Z
y
b
Z
y
b
Z
y
影子价格是在最优决策下对资源的一种估价，没有最优决策就没有影
子价格，所以影子价格又称“最优计划价格”，“预测价格”等等。
资源的影子价格定量的反映了单位资源在最优生产方案中为总收益应
提供的收益，因此，资源的影子价格也可称为在最优方案中投入生产的机
会成本。
3.影子价格的求法
(1)在非退化情况下：设 B 为 LP 问题的最优基，则
资源的影价=Y*=CBB-1
(2)在退化情况下：
当对偶问题有 K 个最优解，则第 i 种资源的影价= 即影价
的第 i 个分量等于这 K 个对偶解中第 i 个分量的最小值。
例如，设某资源利用问题为
maxZ=3x1+x2
最 终 表
3 1 0 0
XB x1 x2 x3 x4
x1 2 1 1 1 0
x4 0 0 -1 [-3] 1
Z 6 0 2 3 0
x1 2 1 2/3 0 1/3
x3 0 0 1/3 1 -1/3
Z 6 0 1 0 1
}{min )*(kik y
0,
623
2
21
21
21
xx
xx
xx
b
(资源 1 限制)
(资源 2 限制)
Ⅰ 资源 1 的影价
=min{y1*(1),y1*(2)}
=min{3,0}=0
资源 2 的影价=min{y2*(1),y2*(2)}=min{0,1}=0
4.影子价格的参谋作用
（1）指出企业挖潜革新的途径
（2）对市场资源的最优配置起着推进作用
（3）可为企业决策者提供调整最优生产方案的信息
CBB-1Pj－Cj<0 说明第 j 种产品应投产
CBB-1Pj－Cj>0 说明第 j 种产品不应投产
尤其对新产品是否应投产，可按以上两式考虑。
（4）可以预测产品的价格
（5）可作为同类企业经济效益评估指标之一。
五、灵敏度分析
面对市场变化，灵敏度分析的任务是须解决以下两类问题：
（1）当系数 A、b、c 中的某个发生变化时，目前的最优基是否仍最
优（即目前的最优生产方案是否要变化）？
（2）为保持目前最优基仍是最优基，参数 A、b、c 允许变化范围是
什么？
灵敏度分析的方法是在目前最优基 B 下进行的。即当参数 A、b、c 中
的某一个或几个发生变化时，考察是否影响以下两式的成立？
0
0
1
1
NB CNBC
bB
影价>0，说明该资源已耗尽，
成为短线资源。
影价=0，说明该资源有剩余，
成为长线资源。
1.对资源数量 br 变化的分析
当 b 中某个 br 发生改变时，将影响基变量的取值 XB=B-1b。若 br 的变
化仍满足 B-1b≥0，则目前的基 B 仍为最优基，仅在 B-1b 和 CBB-1b 的数量
上有些改变。若 br 的变化使 B-1b 中某些分量小于 0，则目前的基成为非可
行基，为此，可用对偶单纯形法迭代求得新的最优解。
B-1b≥0 给出了使最优基 B 保持不变时Ⅰbr 的允许的变化范围：
由解不等式组
B-1(b+Ⅰb)=B-1b+B-1 可得：
其中 为最终表中 列的第 i 个分量， 为 B-1 中第 r 列的元素。
例
2.对价值系数 Cj 变化的分析
（1）当 CN 中某个 Cj 发生变化时，只影到非基变量 xj 的检验数
由于
若 ，则ⅠCj≤σj。
这就是保持最优基不变下，ⅠCj 的允许变化范围。否则，用单纯形法
继续迭代，求得新的最优解。
（2）当 CB 中某个 Cr 发生变化时，
则会影响到所有非基变量的检验数σN=CBB-1N－CN。
解不等式组 =(CB+ⅠCB)B-1N－CN=(CBB-1N－CN)+ⅠCBB-1N≥
0
0
:
:
0
rb ),2,1(0 mibab riri
}0|/{min}0|/{ iririiriririi aabbaabaxm
ib b ira
jjjjjBj CCCPBC
)()( 1
0j
0
即 (CBB-1N－CN)+(0,…,ⅠCr,…,0)B-1N≥0
得到使最优解不变ⅠCr 的允许变化范围；
例
（3）对增加新产品的分析
设革企业在计划期内，拟议生产新产品 Xn+1，并已知新产品的单位利
润为 Cn+1，消耗系数向量为 Pn+1=(a1,n+1,a2,n+1,…am,n+1)T，此时应如何分析才
能确定该新产品理澡投产？
增加新产品应在不影响企业目前计划期内最优生产的前提下进行。因
此可从现行的最估基 B 出发考虑：
若σn+1=CBB-1Pn+1－Cn+1<0，则应投产
若σn+1=CBB-1Pn+1－Cn+1>0，则不应投入。
即新产品的机会成本小于目前的市场价格时，应投产否则不应投产。
（4）对增加新约束条件的分析
在企业生产过程中，经常有新情况发生，造成原本不紧缺的某种资源
变成为紧缺资源，对生产计划造成影响，如水、电和资源的供应不足等，
对生产过程提出了新约束等。
对增加新约束条件的分析方法步骤是：
第一步：将目前的最优解代入新增加的约束，若能满足约束条件，则
说明新增约束对目前的最优解（即最优生产方案）不构成影响（称此约束
为不起作用约束），可暂时不考虑新增约束条件。否则转下一步；
第二步：把新增约束添加到原问题最终表中，并作初等行变换，构成
)(0 Nrjrj JjaC
}0|/{min}0|/{min rjrjjjrrjrjjj aaCaa
对偶可行的单纯形表，并用对偶单纯形法迭代，求出新的最优解。
例：
（5）技术系数 aij 变化的分析
第一种情况（当 jⅠJN）：方法与增加一个新产品的分析相同。
第二种情况（当 jⅠJB）：由于 B 中元素的改变影响到 B-1 的变化，因
此也影响到 T(B)。目前的基 B 对应的解有可能既不是原始可行，也不是对
偶可行。于是不如重新求解。
第二章 特殊 LP 问题及其解法
所谓特殊 LP 问题是指 LP 模型的系数矩阵具有特殊的结构，有可能找
到比单纯形法更为简便的求解方法，从而节省人力和物力。
§1 运输问题及其解法
引例：
某公司经销甲产品，它下设三个加工厂，每日的产量分别为：A1-7 吨，
A2-4 吨，A3-9 吨。该公司把这些产品分别运往四个销售点，各销售每日销
量为：B1-3 吨，B2-6 吨，B3-5 吨，B4-6 吨。已知从各工厂到各销售点的单
位产品的运价为下表所示。问该公司应如何调运产品，在满足各销售点需
求量的前提下，使总运费为最少。
平衡表（单位：吨） 运价表 （单位：元/吨）
销地
产地
B1 B2 B3 B4 产量 B1 B2 B3 B4
A1 7 3 11 3 10
A2 4 1 9 2 8
A3 9 7 4 10 5
销 量 3 6 5 6
解：这是一个产销平衡的运输问题，其数学模型是：
设 Xij 表示从 Ai 调运产品到 Bj 的数量（吨），则
minZ=3X11+11X12+3X13+10X14+X21+9X22
+2X23+8X24+7X31+4X32+10X33+5X34
x11+x12+x13+x14 =7
x21+x22+x23+x24 =4
x31+x32+x33+x34 =9
x11 +x21 +x31 =3
x12 +x22 +x32 =6
x13 +x23 +x33 =5
x14 +x24 +x34=6
xij≥0 (i=1,2,3, j=1,2,3,4)
一、产量平衡的运输问题及其解法
1.产销平衡的运输问题的数学模型及其特点
特点：（1）其系数矩阵的结构疏松，且每一列向量
Pij=(0,…1,…1,…0)T=ei+em+j
m
i
n
j
ijij XCZ
1 1
min
)1,1(0
),,2,1(
),,2,1(
1
1
njmiX
niaX
mjbX
ij
n
j
iij
m
i
jij
可以证明，r(A)=m+n－1。即有 m+n－1 个独立方程。
于是，该 LP 问题有且仅有 m+n－1 个基变量。
（2） （产销平衡条件）
（3）因为 故必有可行解和最优解。
由于上述特点，若按单纯形法求解必须增加人工变量，致使计算量大
大增加，故用特殊解法──表上作业法。
2.表上作业法
表上作业法实质上还是单纯形法，但具体计算和术语上有所不同。其
计算步骤方法，并通过对引例的求解过程说明之一。
（1）用最小元素法确定初始方案（即初始基可行解）
切记在产销平衡表上必须且只能填写 m+n－1 个数字格
（2）用位势法求出空格的检验数并进行最优解的判别
设 u1,u2,…um; v1,v2,…,vn 是对应运输问题 m+n 个约束条件的对偶变量，
B 为含有人工变量的初始可行基，由 LP 问题的对偶理论知
CBB-1=(u1,u2,…um; v1,v2,…,vn)
而每个决策变量 Xij 相应的系数向量 Pij=ei+em+j，所以 CBB-1Pij=ui+vj
于是，检验数σij=CBB-1Pij－Cij =(ui+vj)－Cij
又各基变量的检验数为 0，故对每个基变量所在的数格的检验数有
(ui+vj)－Cij =0 i,jⅠJB
即有方程组
m
i
n
j
ji ba
1 1
m
i
n
j
ijij XCMinZ
1 1
0
共 m+n 个未知数 s=m+n－1 个方程
显然上述方程有解，且由于含有一个自由变量，因此，可令任一未知
数为 0，就可求出上述方程组的解(ui1,ui2,…uim,vj1,vj2,…vjn)──称为位势解。
如用位势法求引例初始基可行解的检验数：
销地
产地
B1 B2 B3 B4 ui
3 11 Ⅰ Ⅰ
A1 -1 -2 0
1 9 Ⅰ Ⅰ
A2 -1 +1 -1
7 Ⅰ Ⅰ Ⅰ
A3 -10 -12 -5
vj 2 9 3 10
第一步：将运价表中的数字分别写在各格听右上角，并对基变量相应
的运价加圈，同时在表中增加 vj 和 ui 列。
第二步：利用圈数格分别算出 ui 和 vj，即
令 u1=0，然后按 ui+vj=Cij (i,jⅠJB)，相继确定 ui，vj 的值。于是有
v3=3,v4=10,u2=-1,v1=2,u3=-5,v2=9
第三步：按σij= (ui+vj)－Cij (i,jⅠJN)算出表中各空格（即非基变量）
的检验数：
σ11=(0+2)－3=-1，σ12=(0+9)－11=-2，σ22=-1，σ24=1，σ31=-10，σ33=-12
由于运输问题的目标函数是求最小化，故判别最优解的准则是所有的σ
ij=CBB-1Pij－Cij≤0
isjsjsis
jiji
jiji
Cvu
Cvu
Cvu
:
2222
1111
因为Ⅰ24=+1>0，所以目前尚未得到最优解，尚须改进
（3）在调运平衡表上用闭回路法进行调整，得到新的基可行解（新的
调运方案）
i) 确定换入变量：自上而上，自左向右第一个正检验数相应的非基变
量（空格）为入基变量。
ii) 作闭回路：以换入变量空格为出发点，用水平或垂直线向前划，当
碰到某一恰当数格转 90Ⅰ后，继续前进，直至回到起始空格止。
iii) 确定调整量Ⅰ=min{第奇数次拐角格的调运量}
iv) 在闭回路上进行调整：对闭回路上每个奇数次拐角格的调运量－Ⅰ
对闭回路上每个第偶数次（含起始格）拐角格的调运量+Ⅰ。调整后，将闭
回路中为 0 的一个数格作为空格（即出基变量）。
闭回路外的各调运量不变。这样便得到新的调运方案（新基可行解）
销地
产地
B1 B2 B3 B4 产量
A1 (+1)4 3(-1) 7
A2 3 (-1)1 (+1) 4
A3 6 3 9
销量 3 6 5 6
对调整后所得的新方案，再进行检验，已得到最优解（最优调运方
案）；
从 A1 调运到 5 吨到 B3，调运 2 吨到 B4
从 A2 调运到 3 吨到 B1，调运 1 吨到 B4
从 A3 调运到 6 吨到 B2，调运 3 吨到 B4
总运费最小是 85 元
（4）在进行表上作业法须注意的问题：
i) 在最终调运表中，若有某个空格（非基变量）的检验为 0 时，则表
明该运输问题有多重调运方案；
ii) 在确定初始方案时，若在(i,j)格填上某数字后,出现 Ai 处的余量=Bj
处的需量，此时必须在平衡表上被划去行和列相应位置的任一空格处填上
一个“0”，以满足数格=m+n－1 个的需要；
iii) 在用闭回路法调整时，当闭回路上第奇数次拐角数有几个相同的
最小值时，调整后只能有一个空格，其余均要保留数“0”，以保证数格=m+n
－1 个的需要。
以上 ii)，iii)均出现退化解。
iv) 用最小元素法所得到的初始方案可以不唯一。
二、产销不平衡的运输的问题及其求解方法
1.数学模型：产大于销 产小于销
2.解法思路：
将不平衡转化为平衡。即当 时，考虑在平衡表中增加
一 虚 拟 列 ， 表 示 增 加 一 个 销 货 点 (j=n+1) 如 仓 库 ， 其 销 货 量 为
n
j
j
m
i
i ba
11
n
j
j
m
i
i ba
11
m
i
n
j
jiij XCZ
1 1
min
m
i
n
j
jiij XC
1 1
min
),,2,1,,2,1(0
),,2,1(
),,2,1(
1
1
njmiX
njbX
miaX
ij
m
i
jij
n
j
iij
),,2,1,,2,1(0
),,2,1(
),,2,1(
1
1
njmiX
njbX
miaX
ij
m
i
jij
n
j
iij
n
j
j
m
i
i ba
11
，且各运价 Cin+1=0；当 时，考虑在平
衡表中增加一虚拟行，表示增加一个新产地，且各运价 Cm+1j=0。然后再用
产销平衡的运输问题的解法进行解之。
例
三、转运问题及其解法：
1.所谓转运问题是在以下背景产生的：
(1)每个工厂生产的产品不直接运到销地，可以几个产地集中一起运。
(2)运往各销地的物资可先运给其中的几个销地，再转运给其它销地。
(3)除产、销地之外，还可以有几个中间转运站，在产地之间，销地之
间或产销之间转运。
凡类似上述情况下的调运物资并使总运费最小的问题统称为转运问题。
2.求解“转运问题”的思路是把问题中所有的产地、中转站和销地都既
看作产地，又都看作销地，把“转运问题”变成扩大后的产销平衡的运输问
题处理。
3.求解“转运问题”的方法步骤：
(1)建立扩大的产销平衡运输问题单位运价表。其中
1)对两地不能直接运输的单位运价定为 M（很大的正数）；
2) 对 所 有 中 转 站 Tj 的 产 量 和 销 量 定 为 相 等 ， 设 定 为
；
3)对产量列的各数据可按下式计算并填入：
Ai 的产量=ai+Ⅰ,Tj 产量=Ⅰ，Bj 的产量=Ⅰ
n
j
j
m
i
i ba
11
n
j
j
m
i
i ba
11
n
j
j
m
i
i ba
11
4)对销量行的各数据可按下式计算并填入：
Aj 的产量=Ⅰ,Tj 销量=Ⅰ，Bj 的销量=Ⅰ+bj
(2)用表上作业法进行求解
§2 指派问题及其解法
引例
任务
人员
E J G R
甲 2 15 13 4
乙 10 4 14 15
丙 9 14 16 13
丁 7 8 11 9
解：设 Xij 表示第 i 人从事第 j 项工作，且
因此，该问题的数学模型为
MinZ=2X11+15X12+13X13+4X14+10X21+4X22+14X23+15X24
+9X31+14X32+16X33+13X34+7X41+8X42+11X43+9X44
表示第 j 项工作只指派人完成
表示第 i 人被指派完成一项工作
0
1
jiX
1
1
1
1
44342414
43332313
42322212
41312111
XXXX
XXXX
XXXX
XXXX
1
1
1
1
44434241
34333231
24232221
14131211
XXXX
XXXX
XXXX
XXXX
当指派第 i 人去完成第 j 项工
作
否则
Xij=0 或 1(i,j=1,2,3,4)
诸如此类，有 n 项任务，恰好有 n 个人可承担这些任务，但由于每人
的专长技术不同，完成任务的效率(所费时间_不同，为使完成 n 项任务的
总效率最高（即所需总时最少），应如何指派（分派）人员的问题统称为指
派（分派）问题。
一、指派问题的数学模型及其特点
1.数学模型：
2.特点
（ 1 ） 给 定 一 个 指 派 问 题 时 ， 必 须 给 出 效 率 矩 阵 （ 系 数 矩 阵 ）
C=(Cij)nxn,且 CijⅠ0，因此必有最优解( )。
（2）指派问题是一种特殊的平衡的运输问题，由于模型结构的特殊性
（看作每产地的产量均为 1，每销地的销量均为 1），故可用更为简便的匈
牙利法进行求解。
（3）解矩阵
n
i
n
j
ijijij CXCMinZ
1 1
)0(
),2,1(10
),,2,1(1
),,2,1(1
1
1
nijX
niX
njX
ij
n
j
ij
n
i
ij
或
n
i
n
j
ijij XCMinZ
1 1
0
是指派问题的可行解，但不一定是最优解。
二、指派问题的解法──匈牙利法
1.匈牙利法的基本思想是：对同一项工作（任务）j 来说，同时提高或
降低每人相同的效率（常数 ti），不影响其最优指派；同样，对同一个人 i
来说，完成各项工作的效率都提高或降低相同的效率（常数 di），也不影响
其最优指派，因此可得到新的效率矩阵(bij)nxn，其中
bij=Cij+ti+dj （对所有的 i,j）
则新的目标函数为
其中 为常数
这说明 ZⅠ与 Z 同时达到最小值。因而最优解相同。故指派问题有以
下性质：
若从效率矩阵(Cij)nxn 的一行（列）各元素中分别减去该行（列）的最
100
001
010
)(
ijX
n
i
n
j
ijij XbZ
1 1
'
n
i
n
j
ijjiij XdtC
1 1
)(
n
i
n
j
n
i
n
j
n
i
ijj
n
j
ijiijij XdXtXC
1 1 1 1 11
)()(
)(
1 1
n
i
n
j
ji dtZ
n
i
n
j
ji dt
1 1
小元素，得到的新效率矩阵(bij)nxn 不改变原指派问题的最优解。
2.匈牙利法
三、对求最大化的指派问题，（即求 ）,可采用
构造新的效率矩阵(M－Cij)nxn，其中 M=max{Cij}，（显然 M－CijⅠ0），将
其转化为
求所得到的最优解就是原问题的最优解。事实上
由于 nM 为常数，因此，使 ZⅠ取得最小的最优解就是使 Z 取得最大
的最优解。
4.以上讨论的指派问题是效率矩阵的行数等于列数，即 m+n 的情况。
当 mⅠn 时，则可用增加虚设的零元数行（列）使效率矩阵变成方阵后，再
用匈牙利法求解。
当 m<n 时 当 m>n 时
5.指派问题必有最优解，但可以不唯一。
n
i
n
j
ijij XCMaxZ
1 1
n
i
n
j
ijij XCMZMin
1 1
)(
ij
n
i
n
j
ij
n
i
n
j
ij
n
i
n
j
ijij XCXMXCMZ
1 11 1 1 1
)(
ZnMXCnM ij
n
i
n
j
ij
1 1
000
000
,
,
21
11211
mnmm
n
CCC
CCC
00
::::::
00
00
1
221
111
mnm
n
n
CC
CC
CC
n-m 行
m-n 列
§3 整数线性规划问题及其解法
一、整数线性规划
在上一章讨论的 LP 问题中,对决策变量只限于不能取负值的连续型数
值,即可以是正分数或正小数。然而在许多经济管理的实际问题中，决策变
量只有非负整数才有实际意义。对求整数最优解的问题，称为整数规划
(Integer Programming)(简记为 IP)。又称约束条件和函数均为线性的 IP 为整
数线性规划(Integer Linear Programming)(简记为 ILP)。
ILP 问题数学模型的一般形式为：求一组变量 X1,X2,…,Xn，使
人们对 IP 感兴趣，还因为有些经济管理中的实际问题的解必须满足如
逻辑条件和顺序要求等一些特殊的约束条件。此时需引进逻辑变量（又称
0-1 变量），以“0”表示“非”，以“1”表示“是”。凡决策变量均是 0-1 变量的 IP
为 0-1 规划。
严格地说，IP 是个非线性问题。这是因为 IP 的可行解集是由一些离散
的非负整数所组成，不是一个凸集。迄今为止，求解 IP 问题尚无统一的有
效方法。
求解 ILP 问题方法的思考：
1）“舍入取整”法：即先不考虑整数性约束，而去求解其相应的 LP 问题
（称为松驰问题），然后将得到的非整数最优解用“舍入取整”的方法。这样
n
j
jjMin
XCMaxZ
1
数且皆为整数或部分为整,0
),,2,1(
. 1
Xj
mibXa
ts
n
j
iijij
能否得到整数最优解？否！这是因为“舍入取整”的解一般不是原问题的最
优解，甚至是非可行解。
但在处理个别实际问题是，如果允许目标函数值在某一误差范围内，
有时也可采用“舍入取整”得到的整数可行解作为原问题整数最优解的近似。
这样可节省求解的人力、物力和财力。
设 X*是原 ILP 的最优解，X 是其松驰问题的非整数最优解， 是“舍
入取整”的整数可行解，d 为给出目标函数值的允许误差。由于
ⅠCX*ⅠCX
所以 CX*－ ⅠCX－
当 CX－ Ⅰd 时，则可将 作为 X*的近似解。
2）完全枚举法 此法仅在决策变量很少的情况下才实际有效。对于变
量稍多的 ILP 问题则几乎不可能。如在指派问题中，当 n=20，则有可行解
20！个，而 20！>2X1018，这在计算机上也是不可能实现的。
3）求解 ILP 问题常见的几种解法有：分枝定界法，割平面法，0-1 规
划的特殊解法等。
二、0-1 变量产生的背景和应用
引例（详见书 P72 例 2）
由引例可见，利用 0-1 变量处理一类“可供选择条件”的问题查非常简
明且方便的。下面再进一步分别说明对 0-1 变量的应用。
假定现有 m 种资源对可供选择的 n 个项目进行投资的数学模型为：
求一组决策变量 X1,X2,…,Xn，使
X~
XC ~
XC ~ XC ~
XC ~ X~
（）
满足
其中，Cj 表示投资第 j 项获得的期望收益，aij 表示第 i 种资源投于第 j
项目数量，bj 表示第 i 种资源的限量。
1.对可供项目的选择
（1）如果在可供选择的前 k(kⅠn)个项目中，必须且只能选择一项，
则在()中加入新的约束条件：
（2）如果可供选择的 k(kⅠn)个项目是相互排斥的，则在()中加入新
的约束条件：
同时它还表示在第 k 个项目中至多只能选择一项投资。
（3）如果在可供选择的 k(kⅠn)个项目中，至少应选择一项投资，则
在()中加入新的约束条件：
（4）如果项目 j 的投资必须以项目 i 的投资为前提，则可在()中加
入新的约束条件：
XjⅠXi
n
j
jj XCZ
1
max
),,2,1(10
),,2,1(
1
njX
mibXa
j
n
j
ijij
或
k
j
jX
1
1
k
j
jX
1
1
k
j
jX
1
1
（）
（）
（5）如果项目 i 与项目 j 要么同时被选中，要么同时不被选中，则在
()中加入新的约束条件：
Xj=Xi (iⅠj)
2.对可供资源的选择
（1）如果对第 r 种资源 br 与第 t 种资源 bt 的投资是相互排斥的，即只
允许对资源 br 与 bt 中的一种进行投资，则可将()的第 r 个和第 t 个约束
条件改写为：
Ⅰ
Ⅰ
其中 y 为新引进的 0-1 变量，M 为充分大正数。易见，当 y=0 时，Ⅰ
式就是原来的第 r 个约束条件，具有约束作用。此时对Ⅰ式而方，无论 Xj
为何值，都成立，毫无约束作用，这就使问题仅允许第 r 种资源进行投资。
当 y=1 时，Ⅰ式对 Xj 起了约束作用，而Ⅰ式成了多余的条件。到底是满足Ⅰ
还是Ⅰ，则视问题在求出最优解后，y 为 0 还是 1 而言。
（2）如果问题是要求在前 m 个约束条件中至少满足 k(1<k<m)个，则
可将()中的原约束条件修改为：
其中 M 为充分大的正数，k 为整数。
3.在固定费用问题中的应用（详见书）
n
j
rjrj yMbXa
1
n
j
tjtj MybXa
1
)1(
),,2,1()1(
1
miMybXa
n
j
iijij
n
i
i ky
1
三、0-1 规划的解法
1.完全枚举法：其基本思想是：首先将全部变量取 0 或 1 的所有组合
（解）列出，然后在逐个检查这些组合（解）是否可行的过程中，利用增
加并不断修改过滤条件的办法，减少计算量，以达到求出最优解之目的。
例（详见书）
该法只在变量少的情况下使用才有效。
2.隐枚举法：
0-1 规划的隐枚举法是一种特殊的分枝定界法，其基本思想是利用变量
只能为 0 或 1 两个值的特性，进行分枝定界，以减少枚举而达到求出最优
解之目的。该法适用于任何 0-1 规划问题的求解。
