工商管理中的定量分析方法
——数据, 模型和决策
同济大学经济与管理学院 孙昌言
第五章 线性规划
运筹学是 20世纪 40年代前后发展起来的一门新
兴学科，它是运用科学方法 (主要是系统方法和数
学模型 )，去研究并定量分析客观世界中各种复杂
系统的运行规律，从而求得系统的最优设计方案，
以帮助管理者进行科学决策，获得最优的经济和
社会效果。运筹学现已成为当今社会现代化科学
管理中必不可少的强有力工具。
线性规划 (Linear Programming，简称 LP)是运筹
学中最重要的一个分支，主要研究有限资源的最
优分配问题。客观世界中的大量问题都可以用线
性规划模型进行描述和求解。
案例 1 最优生产计划问题
设某厂生产甲、乙、丙三种产品，要经过三道
工序加工，每种产品在各道工序的加工时间、各
工序的生产能力和各产品的单位利润如下：
问：应如何安排生产计划，可使总利润为
最大？
单位产品加工时间产品
工序 甲 乙 丙
加工能力
( 分钟 / 天 )
1 1 2 1 4 3 0
2 3 0 2 4 6 0
3 1 4 0 4 2 0
单位利润 3 2 5
案例 2 饲料配方问题
某饲料公司生产一种鸡饲料，每份饲料为 100
公斤，饲料中的营养成份要求、配料及其成本数
据如下：
问：如何配置该鸡饲料，可使成本最低？
配料
营养成分
大豆粉 玉米粉 石灰石 含量要求
蛋白质 0, 5 0 0, 0 9 0 ≥ 22%
钙 0, 0 0 2 0, 0 0 1 0, 3 8 ≥ 0,8% 且≤ 1, 2 %
单位
配料
含量 粗纤维 0, 0 8 0, 0 2 0 ≤ 5%
单位配料成本 2, 5 0 0, 9 2 6 0, 1 6 4
案例 3 下料问题
某纸厂接到三种宽度卷纸的定单，要求见下表。
该厂生产两种标准宽度的卷纸 (10尺和 20尺宽 )。
需要按订单要求的宽度切割 (设卷纸长度可以连
接 )。问应如何切割，可使总的切割损失为最小？
定单号 宽度要求 (尺 ) 需要量 (尺 )
1 5 10000
2 7 30000
3 9 20000
案例 4 产品配套问题
某厂生产的一种产品由 4个 A零件和 3个 B零件组成。生
产零件 A和 B都需要原料 1和原料 2，原料 1和原料 2的总供
应量分别为 100和 200个单位；该厂有三个车间可以生产这
两种零件，但由于各部门的工艺装备不同，从而产量和原
料单耗都各不相同。问应如何安排各车间的生产班次，可
使产品的总配套数为最大？
每班用料 ( 单位 ) 每班产量 ( 件 )
车间
原料 1 原料 2 零件 A 零件 B
1 8 6 70 50
2 5 9 60 90
3 3 2 80 40
原料数量 1 0 0 2 0 0
案例 5 季节性生产存货控制问题
某企业的产品需求量受季节影响较大，现要制
定某种产品今后 n个月的生产计划。已知在第 i个
月的需求量为 ri，每个月的需求必须保证供货；
如果第 i月的产量比上月产量增加，则每增产 1件
将增加成本 ai元，反之每减产 1件也将增加成本 bi
元；而每件产品存储到下一个月的费用为 ci元，
i=1,2,…,n
问应如何制定该产品 n个月的生产计划，可使 n
个月的总成本 (产量变动和存储成本 )为最低？
案例 6 投资方案选择问题
某公司有 100万元闲置资金，现有以下四种投资项目可
供选择：
项目 A：每年年初都可投资，于次年末可收回投资额的
115%；
项目 B：在第三年年初投入一笔资金，第五年年末可收
回投资额的 135%，但该项目至多只可投资 40万元；
项目 C：第二年年初投入一笔资金，第五年年末可收回
投资额的 145%；
项目 D：每年年初可可购买年利率为 6%的一年期债券，
年底归还。
公司的所有资金必须在第五年年末全部收回，问应如
何安排投资，可使公司在第五年年末拥有的资金最多？
§ 5.1 线性规划模型及其应用
一, 线性规划模型的基本要素
1,决策变量 —实际问题所要确定的一组未知
数 X1,X2,…,X n ；
2,约束条件 —对决策变量取值的限制条件，
由决策变量 X1,X2,…,X n 的线性不等式组或线性方
程组构成；
3,目标函数 —是决策变量的线性函数，目标
可以是最大化或最小化。
二, 线性规划模型的建立
线性规划广泛地应用于军事、工程技术、科学
研究和经济管理等领域，这是由于：
(1)各领域中的大量问题都能使用线性规划模
型来描述；
(2) LP模型有有效的求解方法 (单纯形法 )；
(3) LP模型能有效地分析参数的变化 (灵敏度分
析 )。
案例 1 最优生产计划问题
设某厂生产甲、乙、丙三种产品，要经过三道
工序加工，每种产品在各道工序的加工时间，各
工序的生产能力和各产品的单位利润如下：
问：应如何安排生产计划，可使总利润为
最大？试建立此问题的 LP模型。
单位产品加工时间产品
工序 甲 乙 丙
加工能力
( 分钟 / 天 )
1 1 2 1 4 3 0
2 3 0 2 4 6 0
3 1 4 0 4 2 0
单位利润 3 2 5
案例 1 分析
设 X1,X2,X3分别为产品甲,乙,丙的计划日产量，
X0为每天的总利润，则：
目标函数,max X0=3X1+2X2+5X3
约束条件,X1+2X2+ X3≤430
3X1 +2X3≤460
X1+4X2 ≤420
X1,X2,X3≥0??
?
?
?
案例 2 饲料配方问题
某饲料公司生产一种鸡饲料，每份饲料为 100
公斤，饲料中的营养成份要求、配料及其成本数
据如下：
问：如何配置该鸡饲料，可使成本最低？
配料
营养成分
大豆粉 玉米粉 石灰石 含量要求
蛋白质 0, 5 0 0, 0 9 0 ≥ 22%
钙 0, 0 0 2 0, 0 0 1 0, 3 8 ≥ 0,8% 且≤ 1, 2 %
单位
配料
含量 粗纤维 0, 0 8 0, 0 2 0 ≤ 5%
单位配料成本 2, 5 0 0, 9 2 6 0, 1 6 4
案例 2 分析
设 X1,X2,X3分别为每 100kg饲料中大豆粉、玉米
粉和石灰石的数量 (kg)，则
目标函数,min X0=2.5 X1+0.926X2+0.164X3
约束条件,X1+ X2+ X3 =100
0.5X1+0.09X2 ≥22
0.002X1+0.001X2+0.38X3≥0.8
0.002X1+0.001X2+0.38X3≤ 1.2
0.08X1+0.02X2 ≤5
X1,X2,X3≥0?
?
?
?
?
?
?
案例 3 下料问题
某纸厂接到三种宽度卷纸的定单，要求见下表。
该厂生产两种标准宽度的卷纸 (10尺和 20尺宽 )。
需要按订单要求的宽度切割 (设卷纸长度可以接
连 )，问应如何切割，可使总的切割损失为最小？
定单号 宽度要求 (尺 ) 需要量 (尺 )
1 5 10000
2 7 30000
3 9 20000
案例 3 分析
设 Xij为第 i (i=1,2)种标准卷纸用第 j种切割方
式切割的长度，则两种标准卷纸所有合理的切割
方式及余料宽度如下：
并设 S1,S2,S3分别为所切割的 5尺,7尺,9尺宽卷纸
的总长度超过需要量的多余量，设 X0是总的切割
损失 (面积 )，则
10 尺卷纸 20 尺卷纸
切割宽度
X
1 1
X
1 2
X
13
X
2 1
X
2 2
X
2 3
X
2 4
X
2 5
X
26
需要量
5 尺 2 0 0 4 2 2 1 0 0 10000
7 尺 0 1 0 0 1 0 2 1 0 30000
9 尺 0 0 1 0 0 1 0 1 2 20000
余料宽度 0 3 1 0 3 1 1 4 2
案例 3的 LP模型
min X0=3X12+X13+3X22+X23+X24
+4X25+2X26+5S1+7S2+9S3
2X11+4X21+2X22+2X23+X24-S1=10000
X12+X22+2X24+X25-S2=30000
X13+X23+X25+2X26-S3=20000
Xij≥0,Si≥0，对一切 i,j??
?
?
?
案例 3的 LP模型（解法二）
决策变量 Xij仍如上所设, 而使总的切割损失为
最小的目标, 则等价于所耗用的标准纸张面积为
最小, 故本问题的 LP模型也可更简洁地表达为：
min X0=10X11+10X12+10X13+20X21+20X22
+20X23+20X24+20X25+20X26
2X11+4X21+2X22+2X23+X24≥10000
X12+X22+2X24+X25≥30000
X13+X23+X25+2X26≥20000
Xij≥0,对一切 i,j??
?
?
?
案例 4 产品配套问题
某厂生产的一种产品由 4个 A零件和 3个 B零件组成。生
产零件 A和 B都需要原料 1和原料 2，原料 1和原料 2的总量
分别为 100和 200个单位；该厂有三个车间可以生产这两种
零件，但由于各车间的工艺不同，从而产量和原料单耗都
各不相同。应如何安排各车间的生产班次，可使产品的总
配套数为最大？
每班用料 ( 单位 ) 每班产量 ( 件 )
车间
原料 1 原料 2 零件 A 零件 B
1 8 6 70 50
2 5 9 60 90
3 3 2 80 40
原料数量 1 0 0 2 0 0
案例 4 分析
设 X1,X2,X3分别为车间 1,2,3生产这两种零件的班次数，
则零件 A,B的产量分别为 70X1+60X2+80X3 和
50X1+90X2+40X3。令 Y为产品的配套数，则
则有 (70X1+60X2+80X3)/4≥Y； (50X1+90X2+40X3)/3≥Y
从而 max X0 =Y
70X1+60X2+80X3-4Y≥0
50X1+90X2+40X3-3Y≥0
8X1+5X2+3X3≤100
6X1+9X2+2X3≤200
X1,X2,X3≥0, Y≥0
??
?
??
? ?????
3
40X90X50X，
4
80X60X70Xm i nY 321321
?
?
?
?
?
案例 5 季节性生产存货控制问题
某企业产品的需求受季节影响较大，现要合理
制定产品今后 n个月的生产计划。已知在第 i个月
的需求量为 ri，每个月的需求必须保证供货；如
果第 i月的产量比上月产量增加，则每增产 1件将
增加成本 ai元，反之每减产 1件也将增加成本 bi元；
而每件产品存储到下一个月的费用为 ci元，
i=1,2,…,n。
问应如何制定产品 n个月的生产计划，可使 n个
月的总成本 (产量变动和存储成本 )为最低 (不考虑
正常生产的成本 )？
案例 5 分析
设第 i月的产量为 Xi，第 i月的期初库存为 Ii，
则
Ii+1=Ii+Xi-ri,i=1,2,…,n
其中 I1为已知，其余 Ii是待定的决策变量，由
目标可知,In+1应为 0。设第 i月因调整产量而产生
的成本为 Yi，则
因此第 i月的总成本为,Yi+ciIi+1,n个月的总
成本为,X0=∑(Y i+ciIi+1)
?
?
?
?
?
?
??
??
?
?
??
??
1ii
1iii1ii
1ii1iii
i
XX, 0
XX,)X(Xb
XX,)X(Xa
Y
案例 5的 LP模型
由于 Yi是分段线性函数，因而 X0不是线性函数。
可对 Yi作如下线性化处理，从新令
Yi=max{ai(Xi-Xi-1),bi(Xi-1-Xi)}，则
ai(Xi-Xi-1)≤Y i； bi(Xi-1-Xi)≤Y i
从而本案例的 LP模型为：
min X0=∑(Y i+ciIi+1)
aiXi- aiXi-1≤Y i
-biXi+biXi-1≤Y i i=1,2,…,n
Ii+1=Ii+Xi-ri
Ii,Xi,Yi≥0, i=1,2,…,n??
?
?
?
案例 6 投资方案选择问题
某公司有 100万元闲置资金，现有以下四种投资项目可
供选择：
项目 A：每年年初都可投资，于次年末可收回投资额的
115%；
项目 B：在第三年年初投入一笔资金，第五年年末可收
回投资额的 135%，但该项目至多只可投资 40万元；
项目 C：第二年年初投入一笔资金，第五年年末可收回
投资额的 145%；
项目 D：每年年初可可购买年利率为 6%的一年期债券，
年底归还。
公司的所有资金必须在第五年年末全部收回，问应如
何安排投资，可使公司在第五年年末拥有的资金最多？
案例 6 分析
设 XAi为第 i年年初投入项目 A的资金,i=1,2,3,4；
XB,XC分别为投入项目 B,C的资金；
XDi为第 i年年初购入的债券数,i=1,2,3,4,5，
则各年年初的资金拥有量及可能的投资方案可分析如下：
XD5XA1+XD1
XA2+XC+XD2
XA3+XB+XD
3
XA4+XD4
拥有量
100 1.06XD1 1.15XA1+1.06XD2
1.15XA2+1.06XD3 1.15XA4+1.35XB
+1.45XC+1.06XD5
投资
1.15XA3+1.06XD4
1 2 3 4 5 6 年初
案例 6的 LP模型
为使第五年年末拥有的资金数最大，每年年初
的可用资金应都进行投资，故本案例的 LP模型为：
max X0=1.15XA4+1.35XB+1.45XC+1.06XD5
XA1+XD1=100
XA2+XC+XD2=1.06XD1
XA3+XB+XD3=1.15XA1+1.06XD2
XA4+XD4=1.15XA2+1.056XD3
XD5=1.15XA3+1.06XD4
XB≤40
Xj≥0, 对一切 j
?
?
?
?
?
?
?
三, 线性规划的数学模型
1,LP模型的一般形式
s.t：, i=1,2,…,m
Xj≥0, j=1,2,…,n
在上述 LP模型中，称 Xj为决策变量；,Xj≥0” 称为 非
负性条件 ； cj,aij,bi为 模型中的已知参数，在有限资源
分配 (如案例 1,4,6)的背景下，各参数的含义可解释为：
bi —— 第 i种资源的可利用量；
aij ——第 j种活动 (作业 )对资源 i的单位消耗量；
Cj —— 活动 j的单位价值；
i
n
1j
jij )b，(Xa ????
?
??
?
n
1j
jj0 XcX max/min
2,LP模型的标准形式
称以下形式的 LP模型为 LP的标准形：
i=1,2,…,m
Xj≥0, j=1,2,…,n
??
?
n
1j
jj0 XcX max/min
0)(b bXa,s.t iin
1j
jij ???
?
3,化标准形的方法
(1) ai1X1+ai2X2+ … +ainXn＝ bi,bi＜ 0
则,-(ai1X1+ai2X2+ … +ainXn)＝ - bi
(2) ai1X1+ai2X2+ … +ainXn≤b i
引入非负松驰变量 Si,可得
ai1X1+ai2X2+ … +ainXn+Si＝ bi
(3) ai1X1+ai2X2+ … +ainXn≥b i
引入非负剩余变量 Si,可得
ai1X1+ai2X2+ … +ainXn- Si＝ bi
(4) Xj≤0,令 Xj'=-Xj,则 ≥0
(5) Xj 无符号限制
令,其中 ≥0, ≥0
'jX
'jX''j'jj XXX ?? 'jX
例 1,将下面 LP模型化为标准形
min X0＝ -X1+2X2-3X3
X1+X2+ X3≤7
s.t,X1-X2+ X3≥2
3X1-X2-2X3＝ -5
X1≥0,X 2≤0,X 3 无符号限制
解,令,,并引进松弛变量 S1和
剩余量 S2,则
min X0＝ -X1-2X2'-3X3'+3X3"
X1- X2'+ X3'- X3"+S1 ＝ 7
s.t,X1+ X2'+ X3'- X3" -S2＝ 2
-3X1- X2'+2X3'-2X3" ＝ 5
X1,X2',X3',X3",S1,S2≥0
2'2 XX ?? ''3'33 XXX ??
?
?
?
?
?
?
?
?
?
?
§ 5.2 两个变量 LP问题的图解法
例 2,max X0=4X1+3X2
2X1+3X2≤6
-3X1+2X2≤3
2X1+ X2≤4
X1,X2≥0
在以 X1为横坐标,X2为纵坐标的直角平面上作
图如下。
?
?
?
?
?
?
?
图中多边形 Q(ABCDE)的内部 及其边界上所有点都满
足所有约束条件，都是 LP的可行解。
3
目标函数的等值线
最优解,X1*=1.5,X2*=1
E
A-1
B
C(1.5,1)1.5 D
X1
X2
Q
2X1+X2=4 ③
4
2
2
线性规划的基本概念 (1)
(1) 可行解 满足所有约束条件的变量 X1,X2,…,
Xn的一组取值；
(2) 可行域 所有可行解的集合，记为 Q(可行
解空间 )。若 Q有界非空，则在二维时，它是凸多
边形；三维时是凸多面体； n维时，则是由许多 n
维超平面围成的 n维凸多面体，称为 单纯形 。
(3) 极点 n个约束方程 (直线或平面 )的交点。
(4) 可行极点 可行域 Q的顶点 (如图中 A,B,C、
D,E)。
(5) 最优解 使目标函数达到最优的可行解。
§ 5.3 单纯型形法的原理
一, 单纯型形法的基本思想
由图解法可知，只要可行域 Q有界非空，则 LP
问题一定存在最优解；且最优解一定在 Q的某个
可行极点处得到。
求解 LP问题只需考虑有限个可行极点就可以了。
这就是单纯型形法的基本思想。
二, LP标准形下极点的确定方法
将例 2的 LP模型化为标准形：
max X0= 4X1+3X2
2X1+3X2+S1 ＝ 6 ①
-3X1+2X2 +S2 ＝ 3 ②
2X1+ X2 +S3＝ 4 ③
X1,X2≥0,S1,S2,S3≥0
于是可行域 Q可用图形表示如下。
?
?
?
?
?
?
?
令两个变量为零可确定一个极点
X2=0
(X1=S2=0)E
A B
C(S1=S3=0)
D
X1
X2
Q
X 1
=0
(X1=X2=0) (X2=S3=0)
G
F
由图可知，对两个变量的 LP问题
(1) 可行域 Q的边界上都有且仅有一个变量为零；
(2) 每一极点上都有两个变量为零，反之令两个
变量为零即可确定一个极点 (包括不可行极点 )；
(3) 在可行域内部的点上，所有变量都大于零。
由此可知，在引进松弛变量化为标准形后，可
行域 Q上所有点的变量值都是非负的；反之，若
某一点处所有变量值都是非负的，则该点一定在
可行域上。
一般地，设有 n个决策变量 m个约束条件的 LP
问题的约束条件为：
Xj≥0,j=1,2,…,n
引进 m个松弛变量后化为标准形：
(5.3-1)
则其可行域的每一极点上都有 n个变量为零。
通过令 n个变量为零，上式就化为 m个变量 m个方
程的线性方程组，若方程组的系数矩阵满秩，则
该方程组有唯一解，该组解就对应一个极点；若
该组解是非负的，则它就对应 Q的一个可行极点。
m)1,2,...,i 0,(b,bXa iin
1j
jij ????
?
m1,2,...,i,bSXa iin
1j
jij ????
?
LP的基本概念 (2)
(1) 基本解和基变量 在 (5.3-1)式所示 n+m个变
量 m个方程的线性方程组中，令其中 n个变量为零
所得到的一组解称为该 LP问题的一个 基本解； 这
n个为零的变量就称为 非基变量；余 下的 m个变量
就称为 基变量 。一个基本解与可行域的一个极点
对应。
(2) 基本可行解 称满足非负性条件的基本解为
基本可行解。一个基本可行解与可行域的一个可
行极点相对应。
(3) 最优基本可行解 使目标函数达到最优的基
本可行解称为最优基本可行解。
三, 线性规划的基本定理
若可行域有界非空，则 LP问题一定存在最优解，
且最优解一定在可行域的某个可行极点处得到 (即
一定存在最优基本可行解 )。
由定理可知，求解 LP问题只需考虑有限个基本
可行解即可。
四, 单纯形法的基本原理
求解 LP问题的单纯形法的基本原理是：从一个
初始基本可行解出发，通过对基变量的迭代运算
(每次更换一个基变量，即从一个可行极点移动到
与之相邻的一个可行极点 )，而得到下一个基本可
行解，同时使目标函数得到改善；经过有限次的
迭代运算，就可得到 LP的最优解。见下图所示。
单纯形法迭代过程示意图
初始基本可行解
最优解,X1=1.5,X2=1(X1=S2=0)E
A B
C(S1=S3=0)D
X1
X2
Q
X2=0
X 1
=0 经过辆次迭代得到最优解
案例 1的计算机求解
设 X1,X2,X3分别为产品甲,乙,丙的计划日产量,X0为每
天的总利润，则 LP模型为：
max X0=3X1+2X2+5X3
X1+2X2+ X3≤430
3X1 +2X3≤460
X1+4X2 ≤420
X1,X2,X3≥0
用 Excel 软件求解本案例，可得最优解为：
X1*=0,X2*=100,X3*=230,X0*=1350
此外输出的“运算结果报告”还给出了最优解中松弛
变量的值，为,S1=S2=0,S3=20，说明第一、二道工序的
能力已用完，第三道工序则每天有 20分钟的富裕能力。
?
?
?
?
?
用 Excel求解案例 1的输入格式
A B C D E F
1 2ú ?·?× X
1
2ú ?·ò X
2
2ú ?·±? X
3
X
0
2 μ￥ ?o ?? èó, 3 2 5 ?? èó ×ü ??,
3 2ú à?,
4
5 a
i1
a
i2
a
i3
|2 a
ij
X
j
?¤Dò ?ü à| b
i
6 ?¤Dò 1,1 2 1 0 430
7 ?¤Dò 2,3 0 2 0 460
8 ?¤Dò 3,1 4 0 0 420
9 ?μ ??￡ 1
10
11 ?ú F2 μ￥ ?a ·? ?D ê? è? ?? ê? ￡1 = B 2* B 3+ C 2* C 3+ D 2* D 3
12 ?ú E6 ?D ê? è? ?? ê? ￡1 = B 6* $B $3 + C 6* $C $3 + D 6* $D $3,èo 1ó ·′ ?? μ? E 7,E 8
±í ?D êμ ?? ?ò ?ú ·?μ ￥ ?a ·? Dè òa ê? è? ?? ?? ?? ê?
±í ?D Dé ?? ?ò ?ú ·?μ ￥ ?a ·? Dè òa ê? è? LP ?￡ Dí μ? ?- ê? êy ?Y
案例 2的计算机求解
本问题的 LP模型为：
min X0=2.5 X1+0.926X2+0.164X3
X1+ X2+ X3 =100
0.5X1+0.09X2 ≥22
0.002X1+0.001X2+0.38X3≥0.8
0.002X1+0.001X2+0.38X3≤ 1.2
0.08X1+0.02X2 ≤5
X1,X2,X3 ≥ 0
用 Excel 软件求解本案例，可得最优解为：
X1*=32.32,X2*=64.86,X3*=2.82 X0*=141.33
即每 100公斤饲料应按 32.32kg大豆纷,64.86kg玉米纷，
2.82kg石灰石进行配料，可使成本最低，为 141.33元
/100kg。
?
?
?
?
?
?
?
第六章 对偶问题
§ 6.1 对偶问题的定义
在第五章中谈到，线性规划最典型的应用背景
是如何分配有限资源，使经济效益达到最优。对
同一个实际问题，通常可以使用两种线性规划模
型来描述，其中一个是最大化问题，另一个则是
最小化问题。这两个问题在目标函数、约束条件
以及变量之间存在对应的关系。如果称一个问题
是原始问题 (primal problem)，则另一个问题就称
为它的对偶问题 (Dual problem)，反之亦然。
一, 问题的提出
对外加工定价问题 考虑案例 1的产品计划问
题，如果该厂三道工序的加工能力除了可以加工
本厂产品外，还可以承接对外加工业务来获取经
济效益 (相当于出售资源 )。问每道工序每分钟的
加工利润应如何确定才是合适的?
为便于分析，列出案例 1的 LP模型如下：
(P),max X0=3X1+2X2+5X3
X1+2X2+ X3≤430 Y1
3X1 +2X3≤460 Y2
X1+4X2 ≤420 Y3
X1,X2,X3≥0
对外加工问题的 LP模型
设 Y1,Y2,Y3分别为三道工序对外加工的单位 (分
钟 )利润。显然，将原生产每件甲产品的工序时间
用于对外加工后所获得的利润不应低于生产甲产
品的单位利润，由此得到约束条件：
Y1+3Y2+ Y3≥3
同理有,2Y1 +4Y3≥2
Y1+2Y2 ≥5
如果该厂的三道工序全部用于承担对外加工业
务，则总利润为：
Y0=430Y1+460Y2+420Y3
两个 LP问题的最优目标函数值相等
考虑到市场竞争，在总利润不减少的前提下，各工序
的单位时间加工利润应定得尽可能低些，否则将招揽不到
业务。从而本问题的 LP模型为：
(D),min Y0=430Y1+460Y2+420Y3
Y1+3Y2+ Y3≥3
2Y1 +4Y3≥2
Y1+2Y2 ≥5
Y1,Y2,Y3≥0
可求得最优解为：
Y1*=1,Y2*=2,Y3*=0,Y0*=1350
本案例中 (P)与 (D)两个问题的最优目标函数值相等，即
max X0 = min Y0 = 1350，这并非巧合。
二, 原始问题为典则形式的对偶问题
对比上例中的 (P)与 (D)的 LP模型，可以发现两
个 LP模型中有如下对偶关系：
1,一个为最大化问题,≤ 约束，另一个为最小
化问题,≥ 约束；
2,(P)的一个约束条件对应 (D)的一个变量,(P)
的一个变量对应 (D)的一个约束条件，反之亦然；
3,(P)的约束条件右端常数是 (D)的目标函数系
数,(P)的目标函数系数是 (D)的约束条件右端常
数，反之亦然；
4,(P)与 (D)的约束条件系数矩阵是互为转置的。
称以下形式的 LP模型为典则形式：
(P),max X0=c1X1+ c2 X2+…+c n Xn
a11X1+a12X2+…+a 1nXn≤b1
a21X1+a22X2+…+a 2nXn≤b2
…………………...
am1X1+am2X2+…+a mnXn≤bm
Xj≥0,j=1,2,…,n
则定义其对偶问题为：
(D),min Y0 =b1Y1+ b2Y2+…+ b mYm
a11Y1+a21Y2+…+a m1Ym≥c1
a12Y1+a22Y2+…+a m2Ym≥c2
…………………….
a1nY1+a2nY2+…+a mnYm≥cn
Yi≥0,i=1,2,…,m
上述 (D)也是 典则形式。
例 3,写出下面 LP问题的对偶问题
(P) max X0=5X1+6X2
X1+9X2≤60 Y 1
2X1+3X2≤45 Y 2
5X1-2X2≤20 Y 3
X2≤30 Y 4
X1,X2≥0
(D) min Y0=60Y1+45Y2+20Y3+30Y4
Y1+2Y2+5Y3 ≥5
9Y1+3Y2-2Y3+Y4≥6
Yi≥0, i=1,2,3,4
三, (P)为标准形式的对偶问题
(P),max X0=c1X1+ c2 X2+…+c n Xn
a11X1+a12X2+…+a 1nXn＝ b1
a21X1+a22X2+…+a 2nXn＝ b2
…………………...
am1X1+am2X2+…+a mnXn＝ bm
Xj≥0,j=1,2,…,n
则其对偶问题为：
(D),min Y0 =b1Y1+ b2Y2+…+ b mYm
a11Y1+a21Y2+…+a m1Ym≥c1
a12Y1+a22Y2+…+a m2Ym≥c2
…………………….
a1nY1+a2nY2+…+a mnYm≥cn
Yi 无符号限制,i=1,2,…,m
以上说明,(P)中的一个等式约束对应 (D)的一个
无限制变量，反之也有,(P)中的一个无限制变量
对应 (D)的一个等式约束。
四, 一般形式 LP问题的对偶问题
1,(P)中的一个不符合典则形式的约束条件
(“max,≥” 或,min,≤” )，则对应的对偶变量
≤0；
2,(P)中的一个 ≤0的变量，对应 (D)中一个 不符
合典则形式的约束条件 (“max,≥” 或,min，
≤” )。
(P)与 (D)之间的对偶关系
综合以上分析，任一原始问题 (P)与其对偶 (D)
之间有如下对偶关系：
1,一个为最大化问题，另一个为最小化问题；
2,(P)与 (D)的约束条件系数矩阵是互为转置的；
3,(P)的一个约束条件对应 (D)的一个变量，反
之亦然；
4,(P)的目标函数系数对应 (D)的约束条件右端
常数，反之亦然；
5,(P)的约束条件类型与 (D)的变量限制条件相
对应，反之亦然，即：
一个符合典则形式的约束条件，对应 (D)中的一
个非负变量，反之亦然；
一个等式约束，对应 (D)中的一个无符号限制变
量，反之亦然；
max问题中的一个 ≥约束，或 min问题中的一个 ≤
约束，对应 (D)中的一个” ≤0”的变量，反之亦然；
6,(P)与 (D)互为对偶问题，即 (D)的对偶问题就
是 (P)。
根据以上关系，就可直接写出任一 LP问题的对
偶问题。
例 4,写出以下 LP问题的对偶问题
(P),min X0=5X1-6X2+3X3
-3X1+2X2 ≤3
2X1- X2 + X3 ≥2
2X1+ X2 - X3 = 4
X1无限制,X2 ≤0, X3≥0
(D),max Y0 =3Y1+2Y2+4Y3
-3Y1+2Y2+2Y3 = 5
2Y1- Y2+ Y3 ≥ -6
Y2- Y3≤ 3
Y1≤0, Y2≥0, Y3无限制
§ 6.2 对偶问题的基本性质
一, 对偶问题的基本定理
若 (P)和 (D)都有可行解，则 (P)和 (D)都有
最优解，且 (P)和 (D)最优解的目标函数值相
等。
二, 可由 (P)的最优解中 得到 (D)的 最优解
在用 Excel 软件求得 (P)的最优解的同时，软件
输出的“敏感性报告”中的“阴影价格”给出的
就是各最优对偶变量的值。
例如求解案例 1输出的“敏感性报告”中给出
的 (D)的最优解为,Y1*=1,Y2*=2,Y3*=0。
二, 对偶变量的经济含义 — 影子价格
设 (P):,max X0 = ? CjXj
s.t,? aijXj≤bi,bi≥0,i=1,2,…,m
Xj ≥0,j=1,2,…,n
并设 Y1*,Y2*,…,Y m*是 (D)的最优解，则
max X0 = minY0 = b1Y1*+b2Y2*+…+b mYm*
上式说明最优对偶解 Yi*是第 i种有限资源对目标函数的
单位贡献，即该资源的价值。当资源 i的市场价格低于 Yi*
时，就应购入一定数量的 资源 i；反之就应出售一部分 资
源 i。此外，当 (P)最优解中某个松弛变量 Si>0时，则对应
的对偶变量 Yi*=0，此时无论资源 i的市场价格是多少，企
业都不应购入而应售出一部分 (此时企业的该资源有富裕 )。
因此，称 Yi*为第 i种资源的 影子价格 。
案例 1最优对偶解的经济含义
由求解案例 1时输出的,敏感性报告”中，得
到 (D)的最优解为,Y1*=1,Y2*=2,Y3*=0。
说明该厂第一、二道工序每分钟所提供的利润
分别为 1和 2，如果增加这两道工序的能力所需增
加的费用 (包括外发加工 )分别不超过每分钟 1和 2，
就可适当增加这两道工序的加工能力。但所能增
加的数量则需要通过敏感性分析后决定。第三道
工序的影子价格为 0，说明该道工序能力有多余
(多余 20分钟 /天,即最优解中松弛变量 S3的值，在
输出的“运算结果报告”中给出 ),企业可考虑承
接该工序的对外加工业务 (至多 20分钟 /天 )。
三, 敏感性分析简介
1.敏感性分析的意义
线性规划的敏感性分析 （ Sensitivity Analysis）
是分析 LP模型的各种参数的变化以及增加新的决策
变量, 新的约束条件对最优解的影响, 它在辅助决
策中有着非常重要的意义 。 这是由于,
(1)在实际问题中, LP模型中的参数 cj,aij,bi往往
是人们的估计值或预测值, 与实际情况之间总会存
在一定的偏差；此外, 这些参数会随市场环境和生
产工艺技术条件等的改变而发生变化 。 由于参数的
变化很可能影响目前解的最优性和可行性, 因此需
要了解最优解对各参数变化的敏感性程度 （ 即最优
解的稳定性 ） 。
(2)根据实际问题所建模型的最优解, 是在当前资源配置
条件下的最优解 。 但目前的资源配置是否合理, 应如何进
一步优化配置各种资源, 则还需要作进一步的深入分析,
使企业的各种资源得到更充的分利用并获得更大的经济或
社会效益 。
(3)企业要在激烈的市场竞争中立于不败之地, 就需要不
断进行技术创新并不断推出满足用户要求的新产品, 但新
产品的投产是否能提高企业的经济效益, 就需要进行定量
分析 。
(4)随着市场, 财务, 法规, 生产工艺技术条件等企业内
外部环境的改变, 原先建模时未加考虑或忽略的某些约束
条件就可能变得非常重要, 因此还需要分析增加新的约束
条件后对当前最优解的影响 。
以上内容都可以通过敏感性分析加以解决, 通过敏感性
分析, 可以为决策者提供许多有用的经济信息 。
由于敏感性分析是在最优解的基础上进行的, 故又称为
,最优化后分析, 。
2,Excel 输出的“敏感性报告”中的主要内容
求解第五章案例 1问题的敏感性报告见下图所示，
图中,可变单元格” 下的,递减成本” 给出的
是最优单纯形迭代中各决策变量检验数的负值；
,允许的增量” 和,允许的减量” 则给出了在不
影响当前最优基的条件下各决策变量目标函数系
数 cj的可变动范围。
而,约束” 下的,阴影价格” 则给出了各种资
源的“影子价格”；,允许的增量” 和,允许的
减量,则给出了在不影响当前最优基的条件下各
有限资源数量（约束条件右端常数）的可变动范
围。
——数据, 模型和决策
同济大学经济与管理学院 孙昌言
第五章 线性规划
运筹学是 20世纪 40年代前后发展起来的一门新
兴学科，它是运用科学方法 (主要是系统方法和数
学模型 )，去研究并定量分析客观世界中各种复杂
系统的运行规律，从而求得系统的最优设计方案，
以帮助管理者进行科学决策，获得最优的经济和
社会效果。运筹学现已成为当今社会现代化科学
管理中必不可少的强有力工具。
线性规划 (Linear Programming，简称 LP)是运筹
学中最重要的一个分支，主要研究有限资源的最
优分配问题。客观世界中的大量问题都可以用线
性规划模型进行描述和求解。
案例 1 最优生产计划问题
设某厂生产甲、乙、丙三种产品，要经过三道
工序加工，每种产品在各道工序的加工时间、各
工序的生产能力和各产品的单位利润如下：
问：应如何安排生产计划，可使总利润为
最大？
单位产品加工时间产品
工序 甲 乙 丙
加工能力
( 分钟 / 天 )
1 1 2 1 4 3 0
2 3 0 2 4 6 0
3 1 4 0 4 2 0
单位利润 3 2 5
案例 2 饲料配方问题
某饲料公司生产一种鸡饲料，每份饲料为 100
公斤，饲料中的营养成份要求、配料及其成本数
据如下：
问：如何配置该鸡饲料，可使成本最低？
配料
营养成分
大豆粉 玉米粉 石灰石 含量要求
蛋白质 0, 5 0 0, 0 9 0 ≥ 22%
钙 0, 0 0 2 0, 0 0 1 0, 3 8 ≥ 0,8% 且≤ 1, 2 %
单位
配料
含量 粗纤维 0, 0 8 0, 0 2 0 ≤ 5%
单位配料成本 2, 5 0 0, 9 2 6 0, 1 6 4
案例 3 下料问题
某纸厂接到三种宽度卷纸的定单，要求见下表。
该厂生产两种标准宽度的卷纸 (10尺和 20尺宽 )。
需要按订单要求的宽度切割 (设卷纸长度可以连
接 )。问应如何切割，可使总的切割损失为最小？
定单号 宽度要求 (尺 ) 需要量 (尺 )
1 5 10000
2 7 30000
3 9 20000
案例 4 产品配套问题
某厂生产的一种产品由 4个 A零件和 3个 B零件组成。生
产零件 A和 B都需要原料 1和原料 2，原料 1和原料 2的总供
应量分别为 100和 200个单位；该厂有三个车间可以生产这
两种零件，但由于各部门的工艺装备不同，从而产量和原
料单耗都各不相同。问应如何安排各车间的生产班次，可
使产品的总配套数为最大？
每班用料 ( 单位 ) 每班产量 ( 件 )
车间
原料 1 原料 2 零件 A 零件 B
1 8 6 70 50
2 5 9 60 90
3 3 2 80 40
原料数量 1 0 0 2 0 0
案例 5 季节性生产存货控制问题
某企业的产品需求量受季节影响较大，现要制
定某种产品今后 n个月的生产计划。已知在第 i个
月的需求量为 ri，每个月的需求必须保证供货；
如果第 i月的产量比上月产量增加，则每增产 1件
将增加成本 ai元，反之每减产 1件也将增加成本 bi
元；而每件产品存储到下一个月的费用为 ci元，
i=1,2,…,n
问应如何制定该产品 n个月的生产计划，可使 n
个月的总成本 (产量变动和存储成本 )为最低？
案例 6 投资方案选择问题
某公司有 100万元闲置资金，现有以下四种投资项目可
供选择：
项目 A：每年年初都可投资，于次年末可收回投资额的
115%；
项目 B：在第三年年初投入一笔资金，第五年年末可收
回投资额的 135%，但该项目至多只可投资 40万元；
项目 C：第二年年初投入一笔资金，第五年年末可收回
投资额的 145%；
项目 D：每年年初可可购买年利率为 6%的一年期债券，
年底归还。
公司的所有资金必须在第五年年末全部收回，问应如
何安排投资，可使公司在第五年年末拥有的资金最多？
§ 5.1 线性规划模型及其应用
一, 线性规划模型的基本要素
1,决策变量 —实际问题所要确定的一组未知
数 X1,X2,…,X n ；
2,约束条件 —对决策变量取值的限制条件，
由决策变量 X1,X2,…,X n 的线性不等式组或线性方
程组构成；
3,目标函数 —是决策变量的线性函数，目标
可以是最大化或最小化。
二, 线性规划模型的建立
线性规划广泛地应用于军事、工程技术、科学
研究和经济管理等领域，这是由于：
(1)各领域中的大量问题都能使用线性规划模
型来描述；
(2) LP模型有有效的求解方法 (单纯形法 )；
(3) LP模型能有效地分析参数的变化 (灵敏度分
析 )。
案例 1 最优生产计划问题
设某厂生产甲、乙、丙三种产品，要经过三道
工序加工，每种产品在各道工序的加工时间，各
工序的生产能力和各产品的单位利润如下：
问：应如何安排生产计划，可使总利润为
最大？试建立此问题的 LP模型。
单位产品加工时间产品
工序 甲 乙 丙
加工能力
( 分钟 / 天 )
1 1 2 1 4 3 0
2 3 0 2 4 6 0
3 1 4 0 4 2 0
单位利润 3 2 5
案例 1 分析
设 X1,X2,X3分别为产品甲,乙,丙的计划日产量，
X0为每天的总利润，则：
目标函数,max X0=3X1+2X2+5X3
约束条件,X1+2X2+ X3≤430
3X1 +2X3≤460
X1+4X2 ≤420
X1,X2,X3≥0??
?
?
?
案例 2 饲料配方问题
某饲料公司生产一种鸡饲料，每份饲料为 100
公斤，饲料中的营养成份要求、配料及其成本数
据如下：
问：如何配置该鸡饲料，可使成本最低？
配料
营养成分
大豆粉 玉米粉 石灰石 含量要求
蛋白质 0, 5 0 0, 0 9 0 ≥ 22%
钙 0, 0 0 2 0, 0 0 1 0, 3 8 ≥ 0,8% 且≤ 1, 2 %
单位
配料
含量 粗纤维 0, 0 8 0, 0 2 0 ≤ 5%
单位配料成本 2, 5 0 0, 9 2 6 0, 1 6 4
案例 2 分析
设 X1,X2,X3分别为每 100kg饲料中大豆粉、玉米
粉和石灰石的数量 (kg)，则
目标函数,min X0=2.5 X1+0.926X2+0.164X3
约束条件,X1+ X2+ X3 =100
0.5X1+0.09X2 ≥22
0.002X1+0.001X2+0.38X3≥0.8
0.002X1+0.001X2+0.38X3≤ 1.2
0.08X1+0.02X2 ≤5
X1,X2,X3≥0?
?
?
?
?
?
?
案例 3 下料问题
某纸厂接到三种宽度卷纸的定单，要求见下表。
该厂生产两种标准宽度的卷纸 (10尺和 20尺宽 )。
需要按订单要求的宽度切割 (设卷纸长度可以接
连 )，问应如何切割，可使总的切割损失为最小？
定单号 宽度要求 (尺 ) 需要量 (尺 )
1 5 10000
2 7 30000
3 9 20000
案例 3 分析
设 Xij为第 i (i=1,2)种标准卷纸用第 j种切割方
式切割的长度，则两种标准卷纸所有合理的切割
方式及余料宽度如下：
并设 S1,S2,S3分别为所切割的 5尺,7尺,9尺宽卷纸
的总长度超过需要量的多余量，设 X0是总的切割
损失 (面积 )，则
10 尺卷纸 20 尺卷纸
切割宽度
X
1 1
X
1 2
X
13
X
2 1
X
2 2
X
2 3
X
2 4
X
2 5
X
26
需要量
5 尺 2 0 0 4 2 2 1 0 0 10000
7 尺 0 1 0 0 1 0 2 1 0 30000
9 尺 0 0 1 0 0 1 0 1 2 20000
余料宽度 0 3 1 0 3 1 1 4 2
案例 3的 LP模型
min X0=3X12+X13+3X22+X23+X24
+4X25+2X26+5S1+7S2+9S3
2X11+4X21+2X22+2X23+X24-S1=10000
X12+X22+2X24+X25-S2=30000
X13+X23+X25+2X26-S3=20000
Xij≥0,Si≥0，对一切 i,j??
?
?
?
案例 3的 LP模型（解法二）
决策变量 Xij仍如上所设, 而使总的切割损失为
最小的目标, 则等价于所耗用的标准纸张面积为
最小, 故本问题的 LP模型也可更简洁地表达为：
min X0=10X11+10X12+10X13+20X21+20X22
+20X23+20X24+20X25+20X26
2X11+4X21+2X22+2X23+X24≥10000
X12+X22+2X24+X25≥30000
X13+X23+X25+2X26≥20000
Xij≥0,对一切 i,j??
?
?
?
案例 4 产品配套问题
某厂生产的一种产品由 4个 A零件和 3个 B零件组成。生
产零件 A和 B都需要原料 1和原料 2，原料 1和原料 2的总量
分别为 100和 200个单位；该厂有三个车间可以生产这两种
零件，但由于各车间的工艺不同，从而产量和原料单耗都
各不相同。应如何安排各车间的生产班次，可使产品的总
配套数为最大？
每班用料 ( 单位 ) 每班产量 ( 件 )
车间
原料 1 原料 2 零件 A 零件 B
1 8 6 70 50
2 5 9 60 90
3 3 2 80 40
原料数量 1 0 0 2 0 0
案例 4 分析
设 X1,X2,X3分别为车间 1,2,3生产这两种零件的班次数，
则零件 A,B的产量分别为 70X1+60X2+80X3 和
50X1+90X2+40X3。令 Y为产品的配套数，则
则有 (70X1+60X2+80X3)/4≥Y； (50X1+90X2+40X3)/3≥Y
从而 max X0 =Y
70X1+60X2+80X3-4Y≥0
50X1+90X2+40X3-3Y≥0
8X1+5X2+3X3≤100
6X1+9X2+2X3≤200
X1,X2,X3≥0, Y≥0
??
?
??
? ?????
3
40X90X50X，
4
80X60X70Xm i nY 321321
?
?
?
?
?
案例 5 季节性生产存货控制问题
某企业产品的需求受季节影响较大，现要合理
制定产品今后 n个月的生产计划。已知在第 i个月
的需求量为 ri，每个月的需求必须保证供货；如
果第 i月的产量比上月产量增加，则每增产 1件将
增加成本 ai元，反之每减产 1件也将增加成本 bi元；
而每件产品存储到下一个月的费用为 ci元，
i=1,2,…,n。
问应如何制定产品 n个月的生产计划，可使 n个
月的总成本 (产量变动和存储成本 )为最低 (不考虑
正常生产的成本 )？
案例 5 分析
设第 i月的产量为 Xi，第 i月的期初库存为 Ii，
则
Ii+1=Ii+Xi-ri,i=1,2,…,n
其中 I1为已知，其余 Ii是待定的决策变量，由
目标可知,In+1应为 0。设第 i月因调整产量而产生
的成本为 Yi，则
因此第 i月的总成本为,Yi+ciIi+1,n个月的总
成本为,X0=∑(Y i+ciIi+1)
?
?
?
?
?
?
??
??
?
?
??
??
1ii
1iii1ii
1ii1iii
i
XX, 0
XX,)X(Xb
XX,)X(Xa
Y
案例 5的 LP模型
由于 Yi是分段线性函数，因而 X0不是线性函数。
可对 Yi作如下线性化处理，从新令
Yi=max{ai(Xi-Xi-1),bi(Xi-1-Xi)}，则
ai(Xi-Xi-1)≤Y i； bi(Xi-1-Xi)≤Y i
从而本案例的 LP模型为：
min X0=∑(Y i+ciIi+1)
aiXi- aiXi-1≤Y i
-biXi+biXi-1≤Y i i=1,2,…,n
Ii+1=Ii+Xi-ri
Ii,Xi,Yi≥0, i=1,2,…,n??
?
?
?
案例 6 投资方案选择问题
某公司有 100万元闲置资金，现有以下四种投资项目可
供选择：
项目 A：每年年初都可投资，于次年末可收回投资额的
115%；
项目 B：在第三年年初投入一笔资金，第五年年末可收
回投资额的 135%，但该项目至多只可投资 40万元；
项目 C：第二年年初投入一笔资金，第五年年末可收回
投资额的 145%；
项目 D：每年年初可可购买年利率为 6%的一年期债券，
年底归还。
公司的所有资金必须在第五年年末全部收回，问应如
何安排投资，可使公司在第五年年末拥有的资金最多？
案例 6 分析
设 XAi为第 i年年初投入项目 A的资金,i=1,2,3,4；
XB,XC分别为投入项目 B,C的资金；
XDi为第 i年年初购入的债券数,i=1,2,3,4,5，
则各年年初的资金拥有量及可能的投资方案可分析如下：
XD5XA1+XD1
XA2+XC+XD2
XA3+XB+XD
3
XA4+XD4
拥有量
100 1.06XD1 1.15XA1+1.06XD2
1.15XA2+1.06XD3 1.15XA4+1.35XB
+1.45XC+1.06XD5
投资
1.15XA3+1.06XD4
1 2 3 4 5 6 年初
案例 6的 LP模型
为使第五年年末拥有的资金数最大，每年年初
的可用资金应都进行投资，故本案例的 LP模型为：
max X0=1.15XA4+1.35XB+1.45XC+1.06XD5
XA1+XD1=100
XA2+XC+XD2=1.06XD1
XA3+XB+XD3=1.15XA1+1.06XD2
XA4+XD4=1.15XA2+1.056XD3
XD5=1.15XA3+1.06XD4
XB≤40
Xj≥0, 对一切 j
?
?
?
?
?
?
?
三, 线性规划的数学模型
1,LP模型的一般形式
s.t：, i=1,2,…,m
Xj≥0, j=1,2,…,n
在上述 LP模型中，称 Xj为决策变量；,Xj≥0” 称为 非
负性条件 ； cj,aij,bi为 模型中的已知参数，在有限资源
分配 (如案例 1,4,6)的背景下，各参数的含义可解释为：
bi —— 第 i种资源的可利用量；
aij ——第 j种活动 (作业 )对资源 i的单位消耗量；
Cj —— 活动 j的单位价值；
i
n
1j
jij )b，(Xa ????
?
??
?
n
1j
jj0 XcX max/min
2,LP模型的标准形式
称以下形式的 LP模型为 LP的标准形：
i=1,2,…,m
Xj≥0, j=1,2,…,n
??
?
n
1j
jj0 XcX max/min
0)(b bXa,s.t iin
1j
jij ???
?
3,化标准形的方法
(1) ai1X1+ai2X2+ … +ainXn＝ bi,bi＜ 0
则,-(ai1X1+ai2X2+ … +ainXn)＝ - bi
(2) ai1X1+ai2X2+ … +ainXn≤b i
引入非负松驰变量 Si,可得
ai1X1+ai2X2+ … +ainXn+Si＝ bi
(3) ai1X1+ai2X2+ … +ainXn≥b i
引入非负剩余变量 Si,可得
ai1X1+ai2X2+ … +ainXn- Si＝ bi
(4) Xj≤0,令 Xj'=-Xj,则 ≥0
(5) Xj 无符号限制
令,其中 ≥0, ≥0
'jX
'jX''j'jj XXX ?? 'jX
例 1,将下面 LP模型化为标准形
min X0＝ -X1+2X2-3X3
X1+X2+ X3≤7
s.t,X1-X2+ X3≥2
3X1-X2-2X3＝ -5
X1≥0,X 2≤0,X 3 无符号限制
解,令,,并引进松弛变量 S1和
剩余量 S2,则
min X0＝ -X1-2X2'-3X3'+3X3"
X1- X2'+ X3'- X3"+S1 ＝ 7
s.t,X1+ X2'+ X3'- X3" -S2＝ 2
-3X1- X2'+2X3'-2X3" ＝ 5
X1,X2',X3',X3",S1,S2≥0
2'2 XX ?? ''3'33 XXX ??
?
?
?
?
?
?
?
?
?
?
§ 5.2 两个变量 LP问题的图解法
例 2,max X0=4X1+3X2
2X1+3X2≤6
-3X1+2X2≤3
2X1+ X2≤4
X1,X2≥0
在以 X1为横坐标,X2为纵坐标的直角平面上作
图如下。
?
?
?
?
?
?
?
图中多边形 Q(ABCDE)的内部 及其边界上所有点都满
足所有约束条件，都是 LP的可行解。
3
目标函数的等值线
最优解,X1*=1.5,X2*=1
E
A-1
B
C(1.5,1)1.5 D
X1
X2
Q
2X1+X2=4 ③
4
2
2
线性规划的基本概念 (1)
(1) 可行解 满足所有约束条件的变量 X1,X2,…,
Xn的一组取值；
(2) 可行域 所有可行解的集合，记为 Q(可行
解空间 )。若 Q有界非空，则在二维时，它是凸多
边形；三维时是凸多面体； n维时，则是由许多 n
维超平面围成的 n维凸多面体，称为 单纯形 。
(3) 极点 n个约束方程 (直线或平面 )的交点。
(4) 可行极点 可行域 Q的顶点 (如图中 A,B,C、
D,E)。
(5) 最优解 使目标函数达到最优的可行解。
§ 5.3 单纯型形法的原理
一, 单纯型形法的基本思想
由图解法可知，只要可行域 Q有界非空，则 LP
问题一定存在最优解；且最优解一定在 Q的某个
可行极点处得到。
求解 LP问题只需考虑有限个可行极点就可以了。
这就是单纯型形法的基本思想。
二, LP标准形下极点的确定方法
将例 2的 LP模型化为标准形：
max X0= 4X1+3X2
2X1+3X2+S1 ＝ 6 ①
-3X1+2X2 +S2 ＝ 3 ②
2X1+ X2 +S3＝ 4 ③
X1,X2≥0,S1,S2,S3≥0
于是可行域 Q可用图形表示如下。
?
?
?
?
?
?
?
令两个变量为零可确定一个极点
X2=0
(X1=S2=0)E
A B
C(S1=S3=0)
D
X1
X2
Q
X 1
=0
(X1=X2=0) (X2=S3=0)
G
F
由图可知，对两个变量的 LP问题
(1) 可行域 Q的边界上都有且仅有一个变量为零；
(2) 每一极点上都有两个变量为零，反之令两个
变量为零即可确定一个极点 (包括不可行极点 )；
(3) 在可行域内部的点上，所有变量都大于零。
由此可知，在引进松弛变量化为标准形后，可
行域 Q上所有点的变量值都是非负的；反之，若
某一点处所有变量值都是非负的，则该点一定在
可行域上。
一般地，设有 n个决策变量 m个约束条件的 LP
问题的约束条件为：
Xj≥0,j=1,2,…,n
引进 m个松弛变量后化为标准形：
(5.3-1)
则其可行域的每一极点上都有 n个变量为零。
通过令 n个变量为零，上式就化为 m个变量 m个方
程的线性方程组，若方程组的系数矩阵满秩，则
该方程组有唯一解，该组解就对应一个极点；若
该组解是非负的，则它就对应 Q的一个可行极点。
m)1,2,...,i 0,(b,bXa iin
1j
jij ????
?
m1,2,...,i,bSXa iin
1j
jij ????
?
LP的基本概念 (2)
(1) 基本解和基变量 在 (5.3-1)式所示 n+m个变
量 m个方程的线性方程组中，令其中 n个变量为零
所得到的一组解称为该 LP问题的一个 基本解； 这
n个为零的变量就称为 非基变量；余 下的 m个变量
就称为 基变量 。一个基本解与可行域的一个极点
对应。
(2) 基本可行解 称满足非负性条件的基本解为
基本可行解。一个基本可行解与可行域的一个可
行极点相对应。
(3) 最优基本可行解 使目标函数达到最优的基
本可行解称为最优基本可行解。
三, 线性规划的基本定理
若可行域有界非空，则 LP问题一定存在最优解，
且最优解一定在可行域的某个可行极点处得到 (即
一定存在最优基本可行解 )。
由定理可知，求解 LP问题只需考虑有限个基本
可行解即可。
四, 单纯形法的基本原理
求解 LP问题的单纯形法的基本原理是：从一个
初始基本可行解出发，通过对基变量的迭代运算
(每次更换一个基变量，即从一个可行极点移动到
与之相邻的一个可行极点 )，而得到下一个基本可
行解，同时使目标函数得到改善；经过有限次的
迭代运算，就可得到 LP的最优解。见下图所示。
单纯形法迭代过程示意图
初始基本可行解
最优解,X1=1.5,X2=1(X1=S2=0)E
A B
C(S1=S3=0)D
X1
X2
Q
X2=0
X 1
=0 经过辆次迭代得到最优解
案例 1的计算机求解
设 X1,X2,X3分别为产品甲,乙,丙的计划日产量,X0为每
天的总利润，则 LP模型为：
max X0=3X1+2X2+5X3
X1+2X2+ X3≤430
3X1 +2X3≤460
X1+4X2 ≤420
X1,X2,X3≥0
用 Excel 软件求解本案例，可得最优解为：
X1*=0,X2*=100,X3*=230,X0*=1350
此外输出的“运算结果报告”还给出了最优解中松弛
变量的值，为,S1=S2=0,S3=20，说明第一、二道工序的
能力已用完，第三道工序则每天有 20分钟的富裕能力。
?
?
?
?
?
用 Excel求解案例 1的输入格式
A B C D E F
1 2ú ?·?× X
1
2ú ?·ò X
2
2ú ?·±? X
3
X
0
2 μ￥ ?o ?? èó, 3 2 5 ?? èó ×ü ??,
3 2ú à?,
4
5 a
i1
a
i2
a
i3
|2 a
ij
X
j
?¤Dò ?ü à| b
i
6 ?¤Dò 1,1 2 1 0 430
7 ?¤Dò 2,3 0 2 0 460
8 ?¤Dò 3,1 4 0 0 420
9 ?μ ??￡ 1
10
11 ?ú F2 μ￥ ?a ·? ?D ê? è? ?? ê? ￡1 = B 2* B 3+ C 2* C 3+ D 2* D 3
12 ?ú E6 ?D ê? è? ?? ê? ￡1 = B 6* $B $3 + C 6* $C $3 + D 6* $D $3,èo 1ó ·′ ?? μ? E 7,E 8
±í ?D êμ ?? ?ò ?ú ·?μ ￥ ?a ·? Dè òa ê? è? ?? ?? ?? ê?
±í ?D Dé ?? ?ò ?ú ·?μ ￥ ?a ·? Dè òa ê? è? LP ?￡ Dí μ? ?- ê? êy ?Y
案例 2的计算机求解
本问题的 LP模型为：
min X0=2.5 X1+0.926X2+0.164X3
X1+ X2+ X3 =100
0.5X1+0.09X2 ≥22
0.002X1+0.001X2+0.38X3≥0.8
0.002X1+0.001X2+0.38X3≤ 1.2
0.08X1+0.02X2 ≤5
X1,X2,X3 ≥ 0
用 Excel 软件求解本案例，可得最优解为：
X1*=32.32,X2*=64.86,X3*=2.82 X0*=141.33
即每 100公斤饲料应按 32.32kg大豆纷,64.86kg玉米纷，
2.82kg石灰石进行配料，可使成本最低，为 141.33元
/100kg。
?
?
?
?
?
?
?
第六章 对偶问题
§ 6.1 对偶问题的定义
在第五章中谈到，线性规划最典型的应用背景
是如何分配有限资源，使经济效益达到最优。对
同一个实际问题，通常可以使用两种线性规划模
型来描述，其中一个是最大化问题，另一个则是
最小化问题。这两个问题在目标函数、约束条件
以及变量之间存在对应的关系。如果称一个问题
是原始问题 (primal problem)，则另一个问题就称
为它的对偶问题 (Dual problem)，反之亦然。
一, 问题的提出
对外加工定价问题 考虑案例 1的产品计划问
题，如果该厂三道工序的加工能力除了可以加工
本厂产品外，还可以承接对外加工业务来获取经
济效益 (相当于出售资源 )。问每道工序每分钟的
加工利润应如何确定才是合适的?
为便于分析，列出案例 1的 LP模型如下：
(P),max X0=3X1+2X2+5X3
X1+2X2+ X3≤430 Y1
3X1 +2X3≤460 Y2
X1+4X2 ≤420 Y3
X1,X2,X3≥0
对外加工问题的 LP模型
设 Y1,Y2,Y3分别为三道工序对外加工的单位 (分
钟 )利润。显然，将原生产每件甲产品的工序时间
用于对外加工后所获得的利润不应低于生产甲产
品的单位利润，由此得到约束条件：
Y1+3Y2+ Y3≥3
同理有,2Y1 +4Y3≥2
Y1+2Y2 ≥5
如果该厂的三道工序全部用于承担对外加工业
务，则总利润为：
Y0=430Y1+460Y2+420Y3
两个 LP问题的最优目标函数值相等
考虑到市场竞争，在总利润不减少的前提下，各工序
的单位时间加工利润应定得尽可能低些，否则将招揽不到
业务。从而本问题的 LP模型为：
(D),min Y0=430Y1+460Y2+420Y3
Y1+3Y2+ Y3≥3
2Y1 +4Y3≥2
Y1+2Y2 ≥5
Y1,Y2,Y3≥0
可求得最优解为：
Y1*=1,Y2*=2,Y3*=0,Y0*=1350
本案例中 (P)与 (D)两个问题的最优目标函数值相等，即
max X0 = min Y0 = 1350，这并非巧合。
二, 原始问题为典则形式的对偶问题
对比上例中的 (P)与 (D)的 LP模型，可以发现两
个 LP模型中有如下对偶关系：
1,一个为最大化问题,≤ 约束，另一个为最小
化问题,≥ 约束；
2,(P)的一个约束条件对应 (D)的一个变量,(P)
的一个变量对应 (D)的一个约束条件，反之亦然；
3,(P)的约束条件右端常数是 (D)的目标函数系
数,(P)的目标函数系数是 (D)的约束条件右端常
数，反之亦然；
4,(P)与 (D)的约束条件系数矩阵是互为转置的。
称以下形式的 LP模型为典则形式：
(P),max X0=c1X1+ c2 X2+…+c n Xn
a11X1+a12X2+…+a 1nXn≤b1
a21X1+a22X2+…+a 2nXn≤b2
…………………...
am1X1+am2X2+…+a mnXn≤bm
Xj≥0,j=1,2,…,n
则定义其对偶问题为：
(D),min Y0 =b1Y1+ b2Y2+…+ b mYm
a11Y1+a21Y2+…+a m1Ym≥c1
a12Y1+a22Y2+…+a m2Ym≥c2
…………………….
a1nY1+a2nY2+…+a mnYm≥cn
Yi≥0,i=1,2,…,m
上述 (D)也是 典则形式。
例 3,写出下面 LP问题的对偶问题
(P) max X0=5X1+6X2
X1+9X2≤60 Y 1
2X1+3X2≤45 Y 2
5X1-2X2≤20 Y 3
X2≤30 Y 4
X1,X2≥0
(D) min Y0=60Y1+45Y2+20Y3+30Y4
Y1+2Y2+5Y3 ≥5
9Y1+3Y2-2Y3+Y4≥6
Yi≥0, i=1,2,3,4
三, (P)为标准形式的对偶问题
(P),max X0=c1X1+ c2 X2+…+c n Xn
a11X1+a12X2+…+a 1nXn＝ b1
a21X1+a22X2+…+a 2nXn＝ b2
…………………...
am1X1+am2X2+…+a mnXn＝ bm
Xj≥0,j=1,2,…,n
则其对偶问题为：
(D),min Y0 =b1Y1+ b2Y2+…+ b mYm
a11Y1+a21Y2+…+a m1Ym≥c1
a12Y1+a22Y2+…+a m2Ym≥c2
…………………….
a1nY1+a2nY2+…+a mnYm≥cn
Yi 无符号限制,i=1,2,…,m
以上说明,(P)中的一个等式约束对应 (D)的一个
无限制变量，反之也有,(P)中的一个无限制变量
对应 (D)的一个等式约束。
四, 一般形式 LP问题的对偶问题
1,(P)中的一个不符合典则形式的约束条件
(“max,≥” 或,min,≤” )，则对应的对偶变量
≤0；
2,(P)中的一个 ≤0的变量，对应 (D)中一个 不符
合典则形式的约束条件 (“max,≥” 或,min，
≤” )。
(P)与 (D)之间的对偶关系
综合以上分析，任一原始问题 (P)与其对偶 (D)
之间有如下对偶关系：
1,一个为最大化问题，另一个为最小化问题；
2,(P)与 (D)的约束条件系数矩阵是互为转置的；
3,(P)的一个约束条件对应 (D)的一个变量，反
之亦然；
4,(P)的目标函数系数对应 (D)的约束条件右端
常数，反之亦然；
5,(P)的约束条件类型与 (D)的变量限制条件相
对应，反之亦然，即：
一个符合典则形式的约束条件，对应 (D)中的一
个非负变量，反之亦然；
一个等式约束，对应 (D)中的一个无符号限制变
量，反之亦然；
max问题中的一个 ≥约束，或 min问题中的一个 ≤
约束，对应 (D)中的一个” ≤0”的变量，反之亦然；
6,(P)与 (D)互为对偶问题，即 (D)的对偶问题就
是 (P)。
根据以上关系，就可直接写出任一 LP问题的对
偶问题。
例 4,写出以下 LP问题的对偶问题
(P),min X0=5X1-6X2+3X3
-3X1+2X2 ≤3
2X1- X2 + X3 ≥2
2X1+ X2 - X3 = 4
X1无限制,X2 ≤0, X3≥0
(D),max Y0 =3Y1+2Y2+4Y3
-3Y1+2Y2+2Y3 = 5
2Y1- Y2+ Y3 ≥ -6
Y2- Y3≤ 3
Y1≤0, Y2≥0, Y3无限制
§ 6.2 对偶问题的基本性质
一, 对偶问题的基本定理
若 (P)和 (D)都有可行解，则 (P)和 (D)都有
最优解，且 (P)和 (D)最优解的目标函数值相
等。
二, 可由 (P)的最优解中 得到 (D)的 最优解
在用 Excel 软件求得 (P)的最优解的同时，软件
输出的“敏感性报告”中的“阴影价格”给出的
就是各最优对偶变量的值。
例如求解案例 1输出的“敏感性报告”中给出
的 (D)的最优解为,Y1*=1,Y2*=2,Y3*=0。
二, 对偶变量的经济含义 — 影子价格
设 (P):,max X0 = ? CjXj
s.t,? aijXj≤bi,bi≥0,i=1,2,…,m
Xj ≥0,j=1,2,…,n
并设 Y1*,Y2*,…,Y m*是 (D)的最优解，则
max X0 = minY0 = b1Y1*+b2Y2*+…+b mYm*
上式说明最优对偶解 Yi*是第 i种有限资源对目标函数的
单位贡献，即该资源的价值。当资源 i的市场价格低于 Yi*
时，就应购入一定数量的 资源 i；反之就应出售一部分 资
源 i。此外，当 (P)最优解中某个松弛变量 Si>0时，则对应
的对偶变量 Yi*=0，此时无论资源 i的市场价格是多少，企
业都不应购入而应售出一部分 (此时企业的该资源有富裕 )。
因此，称 Yi*为第 i种资源的 影子价格 。
案例 1最优对偶解的经济含义
由求解案例 1时输出的,敏感性报告”中，得
到 (D)的最优解为,Y1*=1,Y2*=2,Y3*=0。
说明该厂第一、二道工序每分钟所提供的利润
分别为 1和 2，如果增加这两道工序的能力所需增
加的费用 (包括外发加工 )分别不超过每分钟 1和 2，
就可适当增加这两道工序的加工能力。但所能增
加的数量则需要通过敏感性分析后决定。第三道
工序的影子价格为 0，说明该道工序能力有多余
(多余 20分钟 /天,即最优解中松弛变量 S3的值，在
输出的“运算结果报告”中给出 ),企业可考虑承
接该工序的对外加工业务 (至多 20分钟 /天 )。
三, 敏感性分析简介
1.敏感性分析的意义
线性规划的敏感性分析 （ Sensitivity Analysis）
是分析 LP模型的各种参数的变化以及增加新的决策
变量, 新的约束条件对最优解的影响, 它在辅助决
策中有着非常重要的意义 。 这是由于,
(1)在实际问题中, LP模型中的参数 cj,aij,bi往往
是人们的估计值或预测值, 与实际情况之间总会存
在一定的偏差；此外, 这些参数会随市场环境和生
产工艺技术条件等的改变而发生变化 。 由于参数的
变化很可能影响目前解的最优性和可行性, 因此需
要了解最优解对各参数变化的敏感性程度 （ 即最优
解的稳定性 ） 。
(2)根据实际问题所建模型的最优解, 是在当前资源配置
条件下的最优解 。 但目前的资源配置是否合理, 应如何进
一步优化配置各种资源, 则还需要作进一步的深入分析,
使企业的各种资源得到更充的分利用并获得更大的经济或
社会效益 。
(3)企业要在激烈的市场竞争中立于不败之地, 就需要不
断进行技术创新并不断推出满足用户要求的新产品, 但新
产品的投产是否能提高企业的经济效益, 就需要进行定量
分析 。
(4)随着市场, 财务, 法规, 生产工艺技术条件等企业内
外部环境的改变, 原先建模时未加考虑或忽略的某些约束
条件就可能变得非常重要, 因此还需要分析增加新的约束
条件后对当前最优解的影响 。
以上内容都可以通过敏感性分析加以解决, 通过敏感性
分析, 可以为决策者提供许多有用的经济信息 。
由于敏感性分析是在最优解的基础上进行的, 故又称为
,最优化后分析, 。
2,Excel 输出的“敏感性报告”中的主要内容
求解第五章案例 1问题的敏感性报告见下图所示，
图中,可变单元格” 下的,递减成本” 给出的
是最优单纯形迭代中各决策变量检验数的负值；
,允许的增量” 和,允许的减量” 则给出了在不
影响当前最优基的条件下各决策变量目标函数系
数 cj的可变动范围。
而,约束” 下的,阴影价格” 则给出了各种资
源的“影子价格”；,允许的增量” 和,允许的
减量,则给出了在不影响当前最优基的条件下各
有限资源数量（约束条件右端常数）的可变动范
围。
