2007-6-28
第一章 线性规划（Linear Programming）
第一章 线性规划（ ）
1.1 线性规划的模型与图解法
1.2 单纯形法
1.3 对偶问题与灵敏度分析
1.4 运输问题
1.5 线性整数规划
http://www.tju.edu.cn
第一章 线性规划
1.1 线性规划的模型与图解法一、线性规划问题及其数学模型
1.线性规划问题在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到最大的效益。
http://www.tju.edu.cn
第一章 线性规划例1 某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：
试拟订使总收入最大的生产计划方案。
资源单耗 产品资源甲 乙 资源限量煤电油
9 4
4 5
3 10
360
200
300
单位产品价格
7 12
http://www.tju.edu.cn
第一章 线性规划
1.决策变量：需决策的量，即待求的未知数；
2.目标函数：需优化的量，即欲达的目标，用决策变量的表达式表示；
3.约束条件：为实现优化目标需受到的限制，
用决策变量的等式或不等式表示。
线性规划模型的三要素
http://www.tju.edu.cn
第一章 线性规划目标函数,总收入，记为,则,
为体现对其追求极大化，在 的前面冠以极大号
Max；
决策变量,甲、乙产品的计划产量，记为 ；
在本例中约束条件,分别来自资源煤、电、油限量的约束，
和产量非负的约束，表示为
≥
≤+
≤+
≤+
0,
300103
20054
36049
..
21
21
21
21
xx
xx
xx
xx
ts
21
,xx
z
12
712z xx= +
z
http://www.tju.edu.cn
第一章 线性规划解：设安排甲、乙产量分别为,总收入为,则模型为：
21,xx
z
21 127 xxMaxz +=
≥
≤+
≤+
≤+
0,
300103
20054
36049
..
21
21
21
21
xx
xx
xx
xx
ts
http://www.tju.edu.cn
第一章 线性规划线性规划模型的一个基本特点：
目标和约束均为变量的线性表达式如果模型中出现如的非线性表达式，则不属于线性规划。
3
2
2
1
1
ln2
x
xx?+
http://www.tju.edu.cn
第一章 线性规划例2 某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：
要求在充分利用各种资源条件下使建造住宅的总面积为最大，求建造方案。
水泥
(公斤 /m
2
)
4000
(千工日 )
147000
(千块 )
150000
(吨 )
20000
(吨 )
110000
(千元 )
资源限量
3.5——18025120
大模住宅
3.0——19030135
壁板住宅
4.521011012105
砖混住宅人工
(工日/m
2
)
砖
(块/m
2
)
钢材
(公斤/m
2
)
造价
(元/m
2
)
资源住宅体系
http://www.tju.edu.cn
第一章 线性规划解,设今年计划修建砖混、壁板、大模住宅各为,为总面积,则本问题的数学模型为:
≥
≤++
≤
≤++
≤++
≤++
0,,
40000035.0003.00045.0
147000210.0
150000180.0190.0110.0
20000025.0030.0012.0
110000120.0135.0105.0
.
321
321
1
321
321
321
xxx
xxx
x
xxx
xxx
xxx
ts
321 xxxMaxz ++=
前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个变量，10个约束条件。
123
,,x xx
z
http://www.tju.edu.cn
第一章 线性规划练习：
某畜牧厂每日要为牲畜购买饲料以使其获取 A、
B,C,D四种养分。市场上可选择的饲料有 M,N两种。
有关数据如下：试决定买 M与 N二种饲料各多少公斤而使支出的总费用为最少？
4
10
售价 （元
/公斤）
0.4 0.6 2.0 1.7
牲畜每日每头需要量
0 0.1 0.2 0.1N
0.1 0 0.1 0.2M
每公斤含营养成分
A B C D
http://www.tju.edu.cn
第一章 线性规划解：设购买 M,N饲料各为,则
21 410 xxMinz +=
≥
≥+
≥+
≥+
≥+
0,
7.11.02.0
0.22.01.0
6.01.00
4.001.0
..
21
21
21
21
21
xx
xx
xx
xx
xx
ts
21
,xx
http://www.tju.edu.cn
第一章 线性规划线性规划模型的一般形式：以 MAX型,约束为例
2,线性规划的数学模型决策变量：
目标函数：
约束条件：
n
xx,,
1
null
nn
xcxcMaxz ++= null
11
≥
≤++
≤++
0,,
..
1
11
11111
n
m
nmnm
nn
xx
bxaxa
bxaxa
ts
null
null
null
null
≤
http://www.tju.edu.cn
第一章 线性规划则模型可表示为模型一般式的矩阵形式
T
mnmijn
T
n
bbbaAccCxxX ),,(,)(),,,(,),,(
111
nullnullnull ====
×
≥
≤
=
0
..
X
bAX
ts
CXMaxz
http://www.tju.edu.cn
第一章 线性规划一般地中 称为决策变量向量,称为价格系数向量,
称为技术系数矩阵,称为资源限制向量。
≥
≤
=
0
..
X
bAX
ts
CXMaxz
X
C
A
b
http://www.tju.edu.cn
第一章 线性规划图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。
二、线性规划问题的图解法
http://www.tju.edu.cn
第一章 线性规划
1,先做约束的图形先做非负约束的图形；
再做资源约束的图形 。
以例1为例，其约束为
≥
≤+
≤+
≤+
0,
300103
20054
36049
.
21
21
21
21
xx
xx
xx
xx
ts
0
1x
2x
90
40 50 100
40
30
http://www.tju.edu.cn
第一章 线性规划
0
1x
2x
对于目标函数任给 二不同的值，
便可做出相应的二直线，用虚线表示。
以例1为例，其目标为
，分别令,做出相应的二直线，便可看出 增大的方向。
nn
xcxcz ++= null
11
z
21
127 xxz +=
16884 == zz 和
z
7
12
14
24
2,再做目标图形
http://www.tju.edu.cn
第一章 线性规划
3,求出最优解将目标直线向使目标 优化的方向移，直至可行域的边界为止，
这时其与可行域的,切,
点 即最优解。
如在例1中，
是可行域的一个角点，
经求解交出 的二约束直线联立的方程可解得
z
*
X
*
X
*
X
T
X )24,20(
*
=
0
1x
2x
90
40 50 100
30
40
*
X
http://www.tju.edu.cn
第一章 线性规划由图解法的结果得到例1的最优解,
还可将其代入目标函数求得相应的最优目标值
。说明当甲产量安排 20 个单位，乙产量安排 24 个单位时，可获得最大的收入 428元。
T
X )24,20(
*
=
428
*
=z
http://www.tju.edu.cn
第一章 线性规划
≥
≥+
≥+
+=
0,
5.143
12
..
46
21
21
21
21
xx
xx
xx
ts
xxMinz
0
1x
2x
1
5.0
375.0
5.1
1
*
X
3,)0,5.0(
**
== zX
T
练习：用图解法求解下面的线性规划。
http://www.tju.edu.cn
第一章 线性规划最优解在什么位置获得？
线性规划的可行域是一个什么形状？
思考
——
多边形，而且是
“
凸
”
形的多边形。
——
在边界，而且是在某个顶点获得。
http://www.tju.edu.cn
第一章 线性规划
（1 ） 线性规划的约束集（即可行域）是一个凸多面体。
凸多面体是凸集的一种。所谓凸集是指：集中任两点的连线仍属此集。试判断下面的图形是否凸集：
凸集中的
“
极点
”
，又称顶点或角点，是指它属于凸集，但不能表示成集中某二点连线的内点。如多边形的顶点。
由图解法得到线性规划解的一些特性
http://www.tju.edu.cn
第一章 线性规划因为，由图解法可知，只有当目标直线平移到边界时，
才能使目标 z 达到最大限度的优化。
问题,本性质有何重要意义？
（ 2）线性规划的最优解（若存在的话）必能在可行域的顶点获得
http://www.tju.edu.cn
第一章 线性规划
（ 3）线性规划解的几种情形
1）唯一解 2）多重最优解
3）无可行解注：出现 3）,4）情况时，建模有问题
4）无有限最优解
http://www.tju.edu.cn
第一章 线性规划单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B.Danzig）提出。
尽管在其后的几十年中，又有一些算法问世，
但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。
1.2 单纯形法
http://www.tju.edu.cn
第一章 线性规划一、单纯形法的预备知识
1,线性规划问题的标准型
≥
=
=
0
..
X
bAX
ts
CXMaxz
标准型的特征：Max型、等式约束、非负约束
。）（的秩为其中,0,≥≤
×
bnmmA
nm
http://www.tju.edu.cn
第一章 线性规划线性规划问题的一般型如何化为标准型？
（ 1）如果目标函数求极小，则
（ 2）如果约束条件为不等式，则引入松弛或剩余变量
CXMinz=
CXMaxz?=
/
加负号
36049
21
≤+ xx
36049
321
=++ xxx
)(xf
)(xf?
*
x
x3
称为松弛变量。问题,它的实际意义是什么？
——
煤资源的“剩余”。
http://www.tju.edu.cn
第一章 线性规划
（ 3）如果存在自由变量，则：
（ 4）右端项 仅需将等式或不等式两端同乘（ -1）
（ 5）对 即可xxx?=≤
'
0 令
0<
i
b
0,,
//////
≥?=
kkkkk
xxxxx
http://www.tju.edu.cn
第一章 线性规划练习：请将例 1的约束化为标准型
≥
≤+
≤+
≤+
0,
300103
20054
36049
..
21
21
21
21
xx
xx
xx
xx
ts
,,,
543
xxx
≥
=++
=++
=++
0,,,,
300 103
20054
360 49
..
543
21
5
21
4
21
3
21
xxxxx
xxx
xxx
xxx
ts
解：增加松弛变量 则约束化为易见，增加的松弛变量的系数恰构成一个单位阵
I
。
http://www.tju.edu.cn
第一章 线性规划一般地，记松弛变量的向量为 X
s
，则
≥
≤
0
..
X
bAX
ts
≥
=+
0,
..
s
s
XX
bIXAX
ts
≥
≥
0
..
X
bAX
ts
≥
=?
0,
..
s
s
XX
bIXAX
ts
http://www.tju.edu.cn
第一章 线性规划
2,基本概念
（1 ）可行解与最优解；的解，记为可行解：满足全体约束 X
*
,
X
XCXCX
≤
最优解：可行解中最优的，记为 则对任可行解，有 。
直观上，可行解是可行域中的点，是一个可行的方案；
最优解是可行域的顶点，是一个最优的方案。
http://www.tju.edu.cn
第一章 线性规划
（2 ）基矩阵与基变量基矩阵 (简称基 )：系数阵A中的m 阶可逆子阵，记为B；其余部分称为非基矩阵，记为 N。
基向量：基 B中的列；其余称非基向量。
基变量：与基向量P
j
对应的决策变量 x
j
，记其组成的向量为X
B；与非基向量对应的变量称非基变量，记其组成的向量为X
N
。
http://www.tju.edu.cn
第一章 线性规划
123
12 4
14
3
2 1
2 3
,,0
xxx
xx x
xx
++ =
+=
≥
null
例,下面为某线性规划的约束请例举出其基矩阵和相应的基向量、基变量。
3
http://www.tju.edu.cn
第一章 线性规划阶可逆子阵有中的，解：本例中,2
1
0
0
1
1
2
2
1
AA
=
—— 6个。
一般地，m × n 阶矩阵 A中基的个数最多有多少个？
个。——
m
n
C;,,,
1
0
0
1
4
3
43431
1?
=
=
x
x
XxxPPB
B
，基变量为，其相应的基向量为
。基变量为其相应的基向量为
=
=
2
1
21212
2
,,,,,
1
2
2
1
x
x
XxxPPB
B
问题：本例的A中一共有几个基？
http://www.tju.edu.cn
第一章 线性规划
（3 ）基本解与基本可行解
() ()
.
0
,0,
,,
,
1
111
===?=
=?
==
=
bB
XbBXXNXBbBX
b
X
X
NBbAXXXX
NBAmABBA
BNNB
N
B
T
NB
时，有当取即可表示为约束中的相应地
）（列，则可记中的前表示取定后，不妨设中的基当解；为线性规划的一个基本的解称?
==
0
1
bB
XbAX
http://www.tju.edu.cn
第一章 线性规划可见：一个基本解是由一个基决定的。
注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。
称非负的基本解为基本可行解（简称基可行解）。
http://www.tju.edu.cn
第一章 线性规划在上例中
≥
=+?
=++
0,,
32
12
41
421
321
xx
xxx
xxx
null
求相应于基 B
1
和 B
2
的基本解，它们是否基本可行解？
,
3
1
3
1
1
0
0
1
,
1
0
0
1
,
1
0
0
1
11
1
=
=
=
=
bBBB
11
解：
是基本可行解。的基本解为相应于基,)3,1,0,0(
1
T
XB =
,
5
1
-
5
7
3
1
5
1
-
5
2
5
2
5
1
,
5
1
-
5
2
5
2
5
1
,
1-
2
2
1
11
2
=
=
=
=
bBBB
22
不是基本可行解。的基本解为相应于基,,0,0)
5
1
,-
5
7
(
2
T
XB =
http://www.tju.edu.cn
第一章 线性规划上二组概念间的联系：
系数阵 A中可找出若干个基B
每个基 B都对应于一个基本解非负的基本解就是基本可行解几种解之间的关系：
可行解基本解非可行解基本可行解问题：基本可行解是可行域中的哪些点？
http://www.tju.edu.cn
第一章 线性规划
3,基本定理
（1）线性规划的可行域是一个凸多面体。
（3）线性规划的最优解（若存在的话）必能在可行域的顶点获得。
（2）线性规划可行域的顶点与基本可行解一一对应。
http://www.tju.edu.cn
第一章 线性规划二、单纯形法的步骤确定初始基本可行解检验其是否最优？
寻找更好的基本可行解否是单纯形法是一种迭代的算法，它的思想是在可行域的顶点 ——基本可行解中寻优。由于顶点是有限个,因此，算法经有限步可终止。
方法前提,模型化为标准型
http://www.tju.edu.cn
第一章 线性规划
1.确定初始基可行解由于基可行解是由一个可行基决定的，因此，确定初始基可行解 X
0
相当于确定一个初始可行基 B
0
。
方法：若A中含 I，则 B
0
=I；
若 A中不含 I，则可用人工变量法构造一个 I。
方法：若A中含 I，则 B
0
=I；
若 A中不含 I，则可用人工变量法构造一个 I。
问题：若 B
0
=I，则 X
0
=？例 1中X
0
=？
http://www.tju.edu.cn
第一章 线性规划
2,最优性检验
bAX =
b
X
X
NB
N
B
=
),(
NB
NXBbBX
11
=
矩阵分块把目标函数用 非基变量 表示：
∴
CXZ =
=
N
B
NB
X
X
CC ),(
NNBB
XCXC +=
NNNB
XCNXBbBC +?=
)(
11
NBNB
XNBCCbBC )(
11
+=
检验数向量，记为 σ。 当 σ ≤ 0时，当前解为最优解。
http://www.tju.edu.cn
第一章 线性规划方法,（1 ）计算每个 x
j
的检验数 jBjj
PBCc
1?
=σ
（2 ）若所有 σ
j
≤0,则当前解为最优；
否则，至少有 σ
k
>0,转3 。
http://www.tju.edu.cn
第一章 线性规划
3,寻找更好的基可行解由于基可行解与基对应，即寻找一个新的基可行解，
相当于从上一个基B
0
变换为下一个新的基B
1
，因此，本步骤也称为基变换。
≥
>
0
1
1
01
bB
zz
可行：
改善：
基变换的原则
）变换的方法：（
nkl
PPPP,,,,,,
1
nullnullnull
进基；对应的令保证“改善”进基
kk
P0> σ
可决定出基由保证“可行”出基 0
11
≥?=
NB
NXBbBX
http://www.tju.edu.cn
第一章 线性规划
{ }
出基。对应的令进基；对应的方法：令
lik
ik
i
i
i
l
kj
j
k
PPB
PB
bB
P
>===
>=
0)(
)(
)(
min
0max
1
1
1
θθ
σσ
称作检验比。
i
θ
http://www.tju.edu.cn
第一章 线性规划以例1 为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。
（1）先将模型化为标准型
≥
=++
=++
=++
0,,,,
300103
20054
36049
..
543
21
5
21
4
21
3
21
xxxxx
xxx
xxx
xxx
ts
21 127 xxMaxz +=
http://www.tju.edu.cn
第一章 线性规划
(2) 确定初始基可行解、检验;00,300)(0,0,360,2,00)(360,200,3,
0
1
00
TT
XbBB ==
=
1
1
1;,
52
PP 向量为再计算检验比确定出基量为计算检验数确定进基向
http://www.tju.edu.cn
第一章 线性规划
（ 3）换基、计算下一个基可行解、再检验，直至最优;50,0)(0,24,240,,)(240,50,30,
10
51
41
1
1
11
TT
XbBB ==
=;0,0)(20,24,84,,(84,20,24),
103
54
491
2
1
22
TT
XbBB ==
=
0
0;,
41
PP 向量为再计算检验比确定出基量为计算检验数确定进基向前解为最优。计算检验数均非正，当问题：当模型规模较大时，计算量很大。
事实上，单纯形法的实现是在单纯形表上完成的。
事实上，单纯形法的实现是在单纯形表上完成的。
http://www.tju.edu.cn
第一章 线性规划三、单纯形表单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。
1
1
0
1
01
1
0
0
)(
)(
0
00
B
PB
bB
PBCc
bB
XB
ik
i
i
ijBBjj
→=→?=→
=→
min
0
θσ
回顾单纯形法步骤
bB
1?
需计算
AB
1?
需计算
( ),AbB
1?
内容是因此，单纯形表的主体
( )
()
()
1
2
1
1
1
0
null
AbB
AbB
AbB
↓
↓
即单纯形表。
变换迭代计算的由此设计了基于初等行得。也可通过初等行变换求个两只有一列不同，故相邻而相邻两个
1?
B
B
http://www.tju.edu.cn
第一章 线性规划单纯形表的主要结构：
X
C
AB
1?
bB
1?
σ
问题：第一张表的B
-1
=？ ——单位阵 I。
检验数的公式是什么？ jBjj
PBCc
1?
= σ
在哪里？
j
PB
1?
列中的第jAB
1
http://www.tju.edu.cn
第一章 线性规划例1
Max Z=7 x
1
+12x
2
9 x
1
+4x
2
≤ 360
4x
1
+5x
2
≤ 200
3 x
1
+10x
2
≤ 300
x
1
,x
2
≥ 0
s.t.
Max Z=7 x
1
+12x
2
9 x
1
+4x
2
+x
3
=360
4x
1
+5x
2
+x
4
= 200
3 x
1
+10x
2
+x
5
= 300
x
1
,…,x
5
≥ 0
s.t.
化为标准型
σ 的计算,
X
B
C
B
B
-1
b
7
x
1
12
X
2
0
x
3
0
x
4
0
x
5
θ
σ
x
3
x
4
x
5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12 000
单纯形表,
7
1
1
11
PBCc
B
=σ
= 7
7=
]0,0,0[
3
4
9
http://www.tju.edu.cn
第一章 线性规划
σ
θ
0
x
5
0
x
4
0
x
3
12
x
2
7
x
1
B
-1
b
C
B
X
B
x
3
x
4
x
5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12 000
单纯形表,
7
90
40
30
[ ]
主元素
σ
θ
0
x
5
0
x
4
0
x
3
12
x
2
7
x
1
B
-1
b
C
B
X
B
x
3
x
4
x
5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12 000
单纯形表,
7
90
40
30
[ ]
x
3
x
4
x
2
0
0
12 30 0.3 1 0 0 0.1
σ
以
10
为主元进行初等行变换
50 2.5 0 0 1 -0.5
240 7.8 0 1 0 -0.4
3.4 0 0 0 -1.2
或,
1
1
11
PBCc
B
=σ
= 7
4.3=
]12,0,0[
3.0
5.2
8.7
σ
θ
0
x
5
0
x
4
0
x
3
12
x
2
7
x
1
B
-1
b
C
B
X
B
x
3
x
4
x
5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12 000
单纯形表,
7
90
40
30
[ ]
0.3 1 0 0 0.1
σ
x
3
x
4
x
2
0
0
12 30
以
10
为主元进行初等行变换
50 2.5 0 0 1 -0.5
7.8
3.4
240 0 1 0 -0.4
0 0 0 -1.2
或,
5
1
55
PBCc
B
=σ?= 0
2.1?=
]12,0,0[
1.0
5.0
4.0
30.8
20
100
x
3
x
1
x
2
0
7
12 24 0 1 0 -0.12 0.16
σ
20 1 0 0 0.4 -0.2
84 0 0 1 -3.12 1.16
0 0 0 -1.36 -0.52
σ
σ
θ
0
x
5
0
x
4
0
x
3
12
x
2
7
x
1
B
-1
b
C
B
X
B
x
3
x
4
x
5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12 000
单纯形表,
7
90
40
30
[ ]
0
0
12 30 0.3 1 0 0 0.1
50 2.5 001-0.5
240 7.8 0 1 0 -0.4
3.4 0 0 0 -1.2
[ ]
x
3
x
4
x
2
30.8
20
100
以为主元进行初等行变换
2.5
∴ X*=(20,24,84,0,0)
T
Z*=428
x
3
x
1
x
2
0
7
12 24 0 1 0 -0.12
0.16
σ
20 1 0 0 0.4 -0.2
84 0 0 1 -3.12 1.16
0 0 0 -1.36 -0.52
σ
σ
θ
x
5
x
4
x
3
x
2
x
1
B
-
1
b
C
B
X
B
x
3
x
4
x
5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12 000
单纯形表,
7
90
40
30
x
3
x
4
x
2
0
0
12 30 0.3 1 0 0 0.1
50 2.5 0 0 1 -0.5
240 7.8 0 1 0 -0.4
3.4 0 0 0 -1.2
30.8
20
100
== ),,(
243
PPPB
1000
510
401
以第 2个表为例：
=
1
B
1.000
5.010
4.001
注：单纯形表中的信息
⑴每一列的含义：
B
-1
(bA)=(B
-1
b,B
-1
P
1
,…,B
-1
P
n
)
⑵每个表中的B和B
-1
的查找
B从初表中找；
B
-1
从当前表中找，对应 于初表中的 I的位置。
⑶终表分析 ——最优基B*
和 (B*)
-1
的查找
== ),,(
213
*
PPPB
1030
540
491
16.012.00
2.04.00
16.112.31
=
1*
)(B
x
3
x
1
x
2
0
7
12 24 0 1 0 -0.12
0.16
σ
20 1 0 0 0.4 -0.2
84 0 0 1 -3.12 1.16
0 0 0 -1.36 -0.52
σ
σ
θ
x
5
x
4
x
3
x
2
x
1
B
-
1
b
C
B
X
B
x
3
x
4
x
5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12 000
单纯形表,
7
90
40
30
x
3
x
4
x
2
0
0
12 30 0.3 1 0 0 0.1
50 2.5 0 0 1 -0.5
240 7.8 0 1 0 -0.4
3.4 0 0 0 -1.2
30.8
20
100
注：单纯形表中的信息
http://www.tju.edu.cn
第一章 线性规划练习：用单纯形法求解下面的线性规划
≥
≤+
≤+
0,
2
5
..
21
21
21
xx
xx
xx
ts 105
153
212.5 xxMaxz +=
将模型化为标准型：解：增加松弛变量,,
43
xx
21 xxMaxz += 5.2
≥
=++
=++
0,,,
1025
15 53
..
43
4
21
3
21
21
xxxx
xxx
xxx
ts
http://www.tju.edu.cn
第一章 线性规划
10 2 5
0153
10
15
4
3
x
x
0
0
0 0 1 2.5
2
5
[ ]
4321
xxxx
0 0 1 2.5
bB
1?
B
X
B
C
θ
5
1
0
5
2
1
5
3
- 1
5
19
0
2
9
1
3
x
x
2.5
0
0.5- 0 0 0
T
X )09,0,2,(=
5=
z
,
1
1
1
0
=
B
,
5
1
0
5
3
-1
1
1
=
B
问题：本题的单纯形终表检验数有何特点？
—— 非基变量 x
2
的检验数等于零。
http://www.tju.edu.cn
第一章 线性规划注：（ 1）解的几种情况在单纯形表上的体现（Max 型）：
- 唯一最优解：终表非基变量检验数均小于零；
- 多重最优解：终表非基变量检验数中有等于零的；
- 无界解：任意表有正检验数相应的系数列均非正。
- 无解：最优解的基变量中含有人工变量注：（ ）解的几种情况在单纯形表上的体现（ 型）：
唯一最优解：终表非基变量检验数均小于零；
多重最优解：终表非基变量检验数中有等于零的；
无界解：任意表有正检验数相应的系数列均非正。
无解：最优解的基变量中含有人工变量
（ 2） Min型单纯形表与Max 型的区别仅在于：检验数反号，即
- 令负检验数中最小的对应的变量进基；
- 当检验数均大于等于零时为最优。
（ ） 型单纯形表与 型的区别仅在于：检验数反号，即令负检验数中最小的对应的变量进基；
当检验数均大于等于零时为最优。
http://www.tju.edu.cn
第一章 线性规划一、对偶问题及其性质乙甲例 1称为例 4的原问题,记为（ P）
1,问题的提出例1 煤电油例
Max Z=7 x
1
+12x
2
9 x
1
+4x
2
≤ 360
4x
1
+5x
2
≤ 200
3 x
1
+10x
2
≤ 300
x
1
,x
2
≥ 0
s.t.
Min W=360y
1
+200y
2
+300y
3
s.t.
9y
1
+4y
2
+3y
3
≥ 7
4y
1
+5y
2
+10y
3
≥ 12
y
1,
y
2,
y
3
≥ 0
例4、这时有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽量少。试建立购买者的线性规划模型。
例 4称为例 1的对偶问题，记为（D ）
1.3 对偶问题与灵敏度分析
http://www.tju.edu.cn
第一章 线性规划
2,对偶模型的一般式则对偶问题为，记 ),,(
321
yyyY =
≥
≤
以例 4为例，原问题为
=
0
..
X
bAX
ts
CXzmax
（P ）
≥
≥
=
0
..
min
Y
CYA
ts
Ybw
（D ）
这是最常见的对偶模型形式，称为对称式对偶模型。二者间具有十分对称的对应关系：
（ 4） P的目标函数系数,D约束右边向量
（ 5） P的资源约束向量 =D的目标函数系数
（ 6） P技术系数矩阵 =D技术系数矩阵转置特点：
（ 1） P为 max型,D为 min型
（ 2） P的变量个数 =D的约束个数
（ 3） P的约束个数 =D的变量个数
http://www.tju.edu.cn
第一章 线性规划若 P的某个约束为,=”型则D的相应变量为自由若 P的某个变量为自由则D的相应约束为,=”型简单推导过程：
设 P为：
≥
=+
≤+
≤+
+=
0,
300103
20054
36049
..
127
21
21
21
21
21
xx
xx
xx
xx
ts
xxZMax
≥
≤
≤+
≤+
≤+
+=
0,
300103
300103
20054
36049
..
127
21
21
21
21
21
21
xx
xx
xx
xx
xx
ts
xxZMax
D为：
≥
≥?++
≥?++
++=
0,,,
12101054
73349
..
300300200360
4321
4321
4321
4321
yyyy
yyyy
yyyy
ts
yyyyZMin
43
'
3
yyy?=令
≥
≥++
≥++
++=
无约束
'
321
'
321
'
321
'
321
,0,
121054
7349
..
300200360
yyy
yyy
yyy
ts
yyyZMin
http://www.tju.edu.cn
第一章 线性规划
3,如何写出LP模型的对偶模型
（1）若LP为Max型，则尽量化成(P)形式。(等式、自由变量不用转换)
（2）若LP为Min型，则尽量化成(D)形式。(等式、自由变量不用转换)
≥
≤
=
0
..
X
bAX
ts
CXzmax
（P ）
≥
≥
=
0
..
min
Y
CYA
ts
Ybw
（D ）
http://www.tju.edu.cn
第一章 线性规划例 5：写出下面线性规划的对偶规划模型：
≥
=+?
≤?
≤+
+=
0
13
52
32
..
32max
1
21
21
21
21
x
xx
xx
xx
ts
xxz
则对偶目标为解：设对偶变量为
,
,,,
321
w
yyy
≥
=+?
≥?+
++=
0,
3
22
..
53
21
321
321
321
yy
yyy
yyy
ts
yyyw
32
min
http://www.tju.edu.cn
第一章 线性规划
≥≤
=++
≤?+
≥+?+
+?+=
无约束
4321
432
431
4321
4321
,0,,0
6
42 2
5 3
..
4532
xxxx
xxx
xxx
xxxx
ts
xxxxZMin
练习：写出下面LP的对偶
http://www.tju.edu.cn
第一章 线性规划其对偶模型为：
123
12
13
123
123
12
546
22
3
32 5..
4
,0,
Max w yyy
yy
yyyst
yyy
yy
=?+
+≤?
+ ≤
+≤?
+ +=
≥?
http://www.tju.edu.cn
第一章 线性规划
(1)对称性
（ P）与（ D）互为对偶
4,对偶性质
(2)弱对偶性设 X,Y 分别为（P ）、（D）的任一可行解，
则
YbCX ≤
证,∵
X,Y 为（ P）、（ D）的可行解
bAX
∴
≤ YbYAX ≤
CXYAX ≥
YbCX ≤
CYA≥
由此可推出：若（P ）为无界解，则（ D）无可行解若（D）为无界解，则（ P）无可行解
http://www.tju.edu.cn
第一章 线性规划
(4)对偶定理若（P ）有最优解，则（ D）也有最优解，且二者最优值相等,
(3)解的最优性设,分别为（ P）与（ D）的可行解，且
X Y bYXC =
则
*
XX =
*
YY =
http://www.tju.edu.cn
第一章 线性规划证：对（P ）增加松弛变量Xs，化为
≥
=+
=
0,
..
s
s
XX
bIXAX
ts
CXMaxz
设其最优基为B，终表为
s
XX
C
0
IBAB
11
1
bBC
B
IBCABCC
Bb
11
0
≤?=
≤?=
00
0
1
1
IBC
ABCC
Bs
B
σ
σ
其检验数为满足则取 YBCY
B
,
1?
=
≥
≥
0Y
CAY
== zbBCbYY
B
1
D）的可行解，且是（即
.3
=YY，由性质
http://www.tju.edu.cn
第一章 线性规划问题：(1) 由性质5 可知，对偶问题最优解的表达式
Y* =？
(2) 求 Y*是否有必要重新求解（ D）？
—— C
B
B
-1
—— 不必。可以从原问题（P ）的单纯形终表获得。
http://www.tju.edu.cn
第一章 线性规划
≥
≤+
≤+
0,
2
5
..
21
21
21
xx
xx
xx
ts 105
153
212.5 xxMaxz +=
T
例如，在前面的练习中已知 的终表为
X )09,0,2,(=
5=
z
5
)5.0,0(
=
=
w
Y
4321
xxxx
0 0 1 2.5
bB
1?
B
X
B
C
θ
5
1
0
5
2
1
5
3
- 1
5
19
0
2
9
1
3
x
x
2.5
0
0.5- 0 0 0
http://www.tju.edu.cn
第一章 线性规划
（5）松紧定理（互补松弛性）
设,分别为（P ）与（D）的可行解，则YX
X
Y,是最优解? 0== XYXY
SS
分为最优解中松弛变量部、其中
SS
YX
在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式，另一方面，如果约束条件取严格不等式，则其对应的变量一定为零.
http://www.tju.edu.cn
第一章 线性规划
y
1
… y
i
… y
m
y
m+1
…y
m+j …
y
n+m
x
1
…x
j
…x
n
x
n+1
…x
n+i
…x
n+m
对偶问题的变量 对偶问题的松弛变量原始问题的变量 原始问题的松弛变量
x
j
y
m+j
=0 y
i
x
n+i
=0 (i=1,2,…,m; j=1,2,…,n)
在一对变量中，其中一个大于 0，另一个一定等于 0
直观上
http://www.tju.edu.cn
第一章 线性规划例 6：已知线性规划问题
5,
5
3
,
5
4
5,,2,1,0
332
432
..
32532min
*
2
*
1
54321
54321
54321
===
=≥
≥+++?
≥++++
++++=
zyy
jx
xxxxx
xxxxx
ts
xxxxxw
j
解为：已知其对偶问题的最优
null
试用对偶理论找出原问题的最优解
http://www.tju.edu.cn
第一章 线性规划
5.对偶问题的经济解释
(1) 对偶最优解的经济解释：资源的影子价格
（Shadow Price）
C
B
B
-1 ——
对偶问题的最优解 —— 买主的最低出价；
——
原问题资源的影子价格 —— 当该资源增加 1单位时引起的总收入的增量 ——卖主的内控价格。
设 DP其最优值为 Z
*
(注：与 LP最优值同），则根据
Z
*
= y
*
b = y
1
*
b
1
+ y
2
*
b
2
+ nullnull + y
m
*
b
m
Z /?b
i
=y
i
*
简单推导：
http://www.tju.edu.cn
第一章 线性规划例 7：例 1（煤电油例）的单纯形终表如下：
0.2- 0.4 0 1
1.16 0.32- 1 0
0.16 0.12- 0 0
2
1
3
x
x
x
12
7
0
0.52- 1.36- 0 0 0
24
20
84
1
0
0
428=
z
（ 1）请指出资源煤电油的影子价格，并解释其经济意义。
（ 2）由单纯形终表还可得到哪些有用的信息？
http://www.tju.edu.cn
第一章 线性规划影子价格在管理决策中的作用：
（ 1）影子价格≠市场价格若影子价格＞市场价格，则应影子价格＜市场价格，则应买进该资源卖出该资源
（ 2）影子价格反映了资源的稀缺性，影子价格越高，则越稀缺。
http://www.tju.edu.cn
第一章 线性规划
≥
≤++++
≤++++
≤++++
++++=
0
max
21
2211
222222121
111212111
2211
nj
mnmnjmjmm
nnjj
nnjj
nnjj
xxxx
bxaxaxaxa
bxaxaxaxa
bxaxaxaxa
st
xcxcxcxcz
nullnull
nullnullnullnullnull
nullnull
nullnull
nullnull
Y
1
Y
2
y
m
（ 2）对偶 约束的 经济解释 ——产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润
mmjiijjj
yayayaya +++++ nullnull
2211
http://www.tju.edu.cn
第一章 线性规划
≥
=?++
=?++
=?++
+++=
+
+
+
0
min
21
2211
222222112
111221111
2211
m
nnmmmnnn
mmm
mmm
mm
yyy
cyyayaya
cyyayaya
cyyayaya
st
ybybybw
null
null
nullnullnullnullnullnullnullnull
null
null
null
（ 3）对偶 松弛变量的 经济解释 ——产品的差额成本差额成本 =机会成本 － 利润
jj
T
jmjmjjjm
caYcayayayy?=?+++=
+
)(
2211
null
机会成本差额成本利润
http://www.tju.edu.cn
第一章 线性规划
=?>
=?>
=
=?>
=?>
=
+
+
+
+
+
+
00
00
0
00
00
0
jjm
jmj
jmj
iin
ini
ini
xy
yx
yx
yx
xy
xy
在利润最大化的生产计划中
（ 1）影子价格大于 0的资源没有剩余；
（ 2）有剩余的资源影子价格等于 0；
（ 3）安排生产的产品机会成本等于利润；
（ 4）机会成本大于利润的产品不安排生产。
（ 4）互补松弛关系的经济解释
http://www.tju.edu.cn
第一章 线性规划二、灵敏度分析任务：讨论模型的系数或变量发生小的变化时对解的影响
（如它们在何范围内变化时可使原最优解或最优基不变？）
对解的影响可行性：B
-1
b≥ 0
最优性：
0
1
≥?
jBj
PBCc
我们主要讨论C,b和变量结构变化时对解的影响。
http://www.tju.edu.cn
第一章 线性规划
1、b 变化时的分析
（只影响解的可行性）
设第 r 种资源 b
r
→b
r
+△（ b→
问题,b在何范围变化时，不影响最优基？
方法：
b）
0
1
≥
bB （保证可行性）
即 0),,,,(
1
1
≥Δ+
T
mr
bbbB nullnull,解出△即可
http://www.tju.edu.cn
第一章 线性规划
2,C 变化时的分析但要分两种情况讨论 。只影响最优性时变为价格,,
jjj
ccc Δ+
即可。故只要
，为因只影响自己的检验数的价格系数是非基变量
0
,
(1)
1
≤
Δ+=
j
jBjjj
jj
PBCcc
xc
σ
σ
的范围。解得只需由
jj
cΔ≤ 0σ
。解得公共的应由所有的数这时要影响所有的检验的价格系数是基变量
ji
imiiii
jj
c
PBccccc
xc
Δ≤
Δ+?=
0
,)(
(2)
1
1
σ
σ nullnull
http://www.tju.edu.cn
第一章 线性规划
3.增加新变量时的分析主要讨论增加新变量 x
n+1
是否有利。经济意义是第 n+1
种新产品是否应当投产，数学意义是 x
n+1
是否应进基。
，即投产无利。，则不增加若
，即投产有利；，则增加若的检验数方法：计算
11
11
1
1
111
0
0
,
++
++
+
+++
≤
>
=
nn
nn
nBnnn
x
x
PBCcx
σ
σ
σ
1
1
11 +
++
=
nBnn
PBCcσ
经济意义：
市场价 影子价
http://www.tju.edu.cn
第一章 线性规划
0.2- 0.4 0 1
1.16 0.32- 1 0
0.16 0.12- 0 0
2
1
3
x
x
x
12
7
0
0.52- 1.36- 0 0 0
24
20
84
1
0
0
428=
z
（ 1）电的影子价格是多少？使最优基仍适用的电的变化范围为何？
（ 2）若有人愿以每度 1元的价格向该厂供应 25度电，是否值得接受？
（ 3）甲产品的价格在何范围内变化时，现最优解不变？
（ 4）若现又考虑一新产品丙，其资源单耗为 10,2，5，
售价为 6.5，问该产品是否可投产？
例 8
http://www.tju.edu.cn
第一章 线性规划
0.2- 0.4 0 1
1.16 0.32- 1 0
0.16 0.12- 0 0
2
1
3
x
x
x
12
7
0
0.52- 1.36- 0 0 0
24
20
84
1
0
0
428=
z
（ 1）电的影子价格是多少？使最优基仍适用的电的变化范围为何？
解：（ 1）电的影子价格是 1.36。
解得由 0
0.12
0.4
3.12
24
20
84
300
200
360
22
1
≥Δ
+
=
Δ+
bbB
仍适用的范围。，即使原最优基 Bb 26.9250
2
≤Δ≤?
http://www.tju.edu.cn
第一章 线性规划
0.2- 0.4 0 1
1.16 0.32- 1 0
0.16 0.12- 0 0
2
1
3
x
x
x
12
7
0
0.52- 1.36- 0 0 0
24
20
84
1
0
0
428=
z
（ 2）若有人愿以每度 1元的价格向该厂供应 25度电，是否值得接受？
解：（ 2）值得。
因 25在 B的适用范围内（即影子价格适用），且
1.36-1.00>0。
http://www.tju.edu.cn
第一章 线性规划
0.2- 0.4 0 1
1.16 0.32- 1 0
0.16 0.12- 0 0
2
1
3
x
x
x
12
7
0
0.52- 1.36- 0 0 0
24
20
84
1
0
0
428=
z
（ 3）甲产品的价格在何范围内变化时，现最优解不变？
解：甲产品的价格c
1
是基变量的价格系数。
() 044.14.08.2
12.0
4.0
12.3
12700
114
≤+Δ=
Δ+?= ccσ由
，得 4.3
1
≥Δc
() 01.920.2.41
0.16
0.2-
1.16
12700
115
≤?Δ+=
Δ+?= ccσ由
，得,6
1
2≤Δc
http://www.tju.edu.cn
第一章 线性规划
0.2- 0.4 0 1
1.16 0.32- 1 0
0.16 0.12- 0 0
2
1
3
x
x
x
12
7
0
0.52- 1.36- 0 0 0
24
20
84
1
0
0
428=
z
（ 4）若现又考虑一新产品丙，其资源单耗为 10,2，5，
售价为 6.5，问该产品是否可投产？
() 032.55.6
5
2
10
52.036.105.6 >?=
=
丙解：因为 σ
故丙产品可以投产。
http://www.tju.edu.cn
第一章 线性规划
1,运输问题的数学模型问题：现有一批货物，从m个仓库运往n个销售地，S
i
处有货物a
i
吨，D
j
处需货物b
j
吨，从
S
i
到D
j
的运价为c
ij
元/吨。问如何安排，既可满足各销地需要，又使总运费最小？
1.4 运输问题
http://www.tju.edu.cn
第一章 线性规划
S
1
S
2
S
m
…
D
n
D
2
D
1
…
a
1
a
2
a
m
b
n
b
2
b
1
…
…
http://www.tju.edu.cn
第一章 线性规划销地产地
D
1
D
2
… D
n
产量
S
1
S
2
…
S
m
X
11
x
12
… x
1n
X
21
x
22
… x
2n
…………
X
m1
x
m2
… x
mn
a
1
a
2
…
a
m
销量
b
1
b
2
… b
n
∑∑
==
=
m
i
n
j
ji
ba
11
产销平衡表
http://www.tju.edu.cn
第一章 线性规划单位运价表销地产地
D
1
D
2
… D
n
S
1
S
2
…
S
m
c
11
c
12
… c
13
c
21
c
22
… c
23
…… … …
c
m1
c
m2
… c
mn
http://www.tju.edu.cn
第一章 线性规划
∑∑
==
=
+++
+++
++=
m
i
n
j
ijij
mnmnmmmm
nn
nn
xc
xcxcxc
xcxcxc
xcxcxcz
11
2211
2222222121
1112121111
...........
min
null
null
null
2,运输问题的数学模型
http://www.tju.edu.cn
第一章 线性规划约束条件为：
njbx
miax
njbx
miax
njbx
miax
j
m
i
ij
iij
j
m
i
ij
iij
j
m
i
ij
iij
,,2,1,
,,2,1,
3
,,2,1,
,,2,1,
)2(
,,2,1,
,,2,1,
)1(
1
n
1j
1
n
1j
1
n
1j
null
null
null
null
null
null
==
=≥
==
=≤
==
==
∑
∑
∑
∑
∑
∑
=
=
=
=
=
=
，则有）供不应求的运输问题（
有供过于求运输问题，则有供销平衡运输问题，则
http://www.tju.edu.cn
第一章 线性规划将约束方程式展开可得
11 1 1
21 2 2
1
11 21 1 1
12 22 2
n
n
mmnm
m
m
x xa
x xa
x xa
x xx b
xxx
++ =
+ +=
++ =
++
null
null
nullnull
null
null
null
2
12
nnmnn
b
x xx b
=
+ +=
nullnullnull null
null
约束方程式中共 m*n个变量,m+n个约束。
http://www.tju.edu.cn
第一章 线性规划
1 1
11
A= 1 1
1 1 1
1 1 1
null
null
null
null
null
nullnull null
null
技术系数矩阵
http://www.tju.edu.cn
第一章 线性规划求解平衡运输问题的表上作业法
（1）确定一个初始的可行调运方案：最小元素法、西北角法、Vogel法
（2）判断当前可行方案是否最优：闭回路法、
位势法
（3）方案调整
3,运输问题的解法
http://www.tju.edu.cn
第一章 线性规划例9：某食品公司下设3个加工厂A1,A2，A3，和4
个门市部B1,B2，B3，B4。各加工厂每天的产量、
各门市部每天的销售量以及从各加工厂到各门市部的运价如下表所示。
问：该公司应如何调运，在满足各门市部销售需要的情况下，使得运费支出为最少？
http://www.tju.edu.cn
第一章 线性规划销地产地
D
1
D
2
D
3
D
4
产量
S
1
S
2
S
3
7
4
9
销量
3 6 5 6
产销平衡表
http://www.tju.edu.cn
第一章 线性规划销地产地
D
1
D
2
D
3
D
4
S
1
S
2
S
3
3 11 3 10
1 9 2 8
7 4 10 5
单位运价表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
D1 D2 D3 D4
S1 7
S2 3 4
S3 9
3 6 5 6
运价表
（ 1）确定初始调运方案（最小元素法）
产销平衡表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
D1 D2 D3 D4
S1 7
S2 3 1 4
S3 9
3 6 5 6
运价表产销平衡表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
D1 D2 D3 D4
S1 4 7
S2 3 1 4
S3 9
3 6 5 6
运价表产销平衡表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
D1 D2 D3 D4
S1 4 7
S2 3 1 4
S3 6 9
3 6 5 6
运价表产销平衡表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
D1 D2 D3 D4
S1 4 7
S2 3 1 4
S3 6 3 9
3 6 5 6
运价表产销平衡表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
D1 D2 D3 D4
S1 4 3 7
S2 3 1 4
S3 6 3 9
3 6 5 6
运价表产销平衡表
http://www.tju.edu.cn
第一章 线性规划
（ 1）确定初始调运方案（西北角法）
1
D
2
D
3
D
4
D
产量
3113 10
7
1928
4
7
3
1045
9
36 5 620
2
S
3
S
销量
1
S
3
4
22
6
1
D
2
D
3
D
4
D
产量
3113 10
7
1928
4
71045
9
36 5 620
2
S
3
S
销量
1
S
31[5]2
列罚数行罚数
1
1
0
2
1
0
[3]12
列罚数
6
1
0
[2]1[2]
列罚数
3
3
6
[7]
21
列罚数
5
1
2
（1 ）确定初始调运方案 Vogel法）
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 4 3 7
S2 3 1 4
S3 6 3 9
3 6 5 6
由各封闭回路可以计算各空格的检验数。
它等于其闭回路上奇数点运价与偶数点运价之负值的和产销平衡表
（ 2）判断当前方案是否为最优（闭回路法，位势法）
闭回路法
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 4 3 7
S2 3 1 4
S3 6 3 9
3 6 5 6
D1 D2 D3 D4
S1 4 3 7
S2 3 1 4
S3 6 3 9
3 6 5 6
产销平衡表 产销平衡表
D1 D2 D3 D4
S1 4 3 7
S2 3 1 4
S3 6 3 9
3 6 5 6
D1 D2 D3 D4
S1 4 3 7
S2 3 1 4
S3 6 3 9
3 6 5 6
D1 D2 D3 D4
S1 4 3 7
S2 3 1 4
S3 6 3 9
3 6 5 6
产销平衡表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
D1 D2 D3 D4
S1 4 3
S2 3 1
S3 6 3
12
10
1
1
2
1
1314343333
21231314343131
1413232424
32341413232222
3234141212
2123131111
=?+?=
=?+?+?=
=?+?=
=?+?+?=
=?+?=
=?+?=
cccc
cccccc
cccc
cccccc
cccc
cccc
σ
σ
σ
σ
σ
σ
产销平衡表运价表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1
S2
S3
12
1-1
10 12
当所有空格检验数
0≥
ij
σ
则当前方案是最优的，若尚有空格检验数小于零，
表明当前方案尚有待调整。
ij
σ
具有确切的经济意义，它表示由Ai 往Bj 增运 1单位时，引起的总运输成本的变化数。
若所有的空格检验数都大于等于零，表明任何一个空格处调运 1单位都会引起总成本的上升，这表明当前方案不能再改进，即定为最优方案。
http://www.tju.edu.cn
第一章 线性规划位势法
D1 D2 D3 D4
S1 3 10
S2 1 2
S3 4 5
D1 D2 D3 D4
S1 4 3
S2 3 1
S3 6 3
（ 1）在有数格上填上相应的运价产销平衡表运价表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 10 u1
S2 1 2 u2
S3 4 5 u3
v1 v2 v3 v4
运价表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 10 U1 0
S2 1 2 U2 -1
S3 4 5 U3 -5
V1 V2 V3 V4
2 9 3 10
上。值，并填在相应的位置和
（有数格），依次求得，然后根据设
ji
ij1
vu
cu
ji
vu +== 0
（2）
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 2 9 (3) (10) U1 0
S2 (1) 8 (2) 9 U2 -1
S3 -3 (4) -2 (5) U3 -5
V1 V2 V3 V4
2 9 3 10
值加上括号以示区别。并将有数格位置上的应位置上，）位势和值填在表中相）表，把（计算（
j
jj
v
vv
+
++
i
ii
u
uu
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
D1 D2 D3 D4
S1 2 9 (3) (10) U1 0
S2 (1) 8 (2) 9 U2 -1
S3 -3 (4) -2 (5) U3 -5
V1 V2 V3 V4
2 9 3 10
单位运价表
（ Ui+vj）表
D1 D2 D3 D4
S1 1 2
S2 1 -1
S3 10 12
检验数表
（ 3）计算检验数表
)(
jiijij
vuc +?=σ
http://www.tju.edu.cn
第一章 线性规划调整方案,若在检验数表上有某空格的检验数为负，则应改进方案，降低成本。调整的方法是从具有负检验数的空格出发（有多个负检验数时，选择绝对值大的一个），沿它的闭回路进行调整，即在方案可行的条件下，尽量增加空格上的运量。
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 4 3 7
S2 3 1 4
S3 6 9
3 6 5 6
一般说来，调整量为闭回路上偶数顶点格上运量最小数
3
http://www.tju.edu.cn
第一章 线性规划调整后的结果为：
D1 D2 D3 D4
S1 5 2 7
S2 3 0 4
S3 6 9
3 6 5 6
1
3
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
单位运价表
（ Ui+vj）表
D1 D2 D3 D4
S1 3 9 (3) (10) U1 0
S2 (1) 7 1 (8) U2 -2
S3 -2 (4) -2 U3 -5
V1 V2 V3 V4
9 3 10
3
(5)
D1 D2 D3 D4
S1 0 2
S2 2 1
S3 9 12
检验数表
http://www.tju.edu.cn
第一章 线性规划再计算新方案的空格检验数：
D1 D2 D3 D4
S1 0 2
S2 2 1
S3 9 12
http://www.tju.edu.cn
第一章 线性规划对于产销不平衡问题，可以增加虚设的产地或销地，将不平衡问题转化为平衡问题处理
∑∑
∑∑
==
+
+
==
=
>
m
i
n
j
ji
n
j
ji
ba
ba
11
11
.
1n
1n
m
i
b
B 其销量为：可以虚拟一销售地当产大于销时：
http://www.tju.edu.cn
第一章 线性规划
∑∑
∑∑
==
+
+
==
=
<
m
qi
i
n
j
j
n
j
ji
ab
ba
1
11
.
1m
1m
m
i
a
A 其产量为：可以虚拟一产地当产小于销时：
http://www.tju.edu.cn
第一章 线性规划一、线性整数规划问题与模型
1,线性整数规划问题实例例10 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、
可获利润以及托运受限制如下表：问两种货物各托运多少箱，可使获得利润最大？
货物 体积每箱（米
3
） 重量每箱（百斤） 利 润每箱（百元）
甲乙
5
4
2
5
20
10
限制
24 13
1.5 线性整数规划
http://www.tju.edu.cn
第一章 线性规划
≥
≤+
≤+
+=
整数
21
21
21
21
21
,
0,
1352
2445
1020
xx
xx
xx
xx
xxMaxz
http://www.tju.edu.cn
第一章 线性规划例11 投资项目选择问题现有资金总额为B。可供选择的投资项目有n
个，项目j所需投资和预期收益分别为a
j
和c
j
。
此外，由于种种原因，有三个附加条件：第一，若选择项目1，就必须同时选择项目2。反之，则不一定；第二，项目3和4中 至少选择一个；第三，项目5,6和7中恰好选择两个。
应当怎 样选择投资项目，才能使总预 期收益最大？
http://www.tju.edu.cn
第一章 线性规划
==
=++
≥+
≥
≤
=
∑
∑
=
=
n),1,2,j10
2
1
max
765
43
12
1
1
null（或
j
n
j
jj
n
j
jj
x
xxx
xx
xx
Bxa
xcz
http://www.tju.edu.cn
第一章 线性规划例 12 运动员选拔问题
4*100m混合泳接力是观众最感兴趣的游泳项目之一。现在从实例出发，研究混合泳运动员的选拔问题：
甲、乙、丙、丁是4名游泳运动员，他们各种姿势的100m游泳成绩见表，为组成一个4*100m
混合泳接力队，怎样选派运动员，方使接力队的游泳成绩最好？
http://www.tju.edu.cn
第一章 线性规划运动员 仰泳 蛙泳 蝶泳 自由泳甲乙丙丁
75.5
65.8
67.6
74.0
86.8
66.2
84.3
69.4
66.6
57.0
77.8
60.8
58.4
52.8
59.1
57.0
http://www.tju.edu.cn
第一章 线性规划
1,2,3,4)j(i,,10
)4,3,2,1(1
)4,3,2,1(1
0.578.604.690.74
1.598.773.846.67
8.520.572.668.65
4.586.668.8675.5xy min
4321
4321
44434241
34333231
24232221
14131211
==
==+++
==+++
++++
++++
++++
+++=
或
ij
iiii
jjjj
x
ixxxx
jxxx
st
xxxx
xxxx
xxxx
xxx
http://www.tju.edu.cn
第一章 线性规划例13 固定费用问题某工厂为生产某种产品，有3种不同的生产方式可供选择。设第 j种生产方式的固定成本为 k
j
，
可变成本为 c
j
。若不考虑其他约束，请建立使总成本最小的规划模型。
=
≤
≥
+++++=
10
0
)()()(
333322221111
或
j
jjj
j
y
yMx
x
xcykxcykxcykMinz
http://www.tju.edu.cn
第一章 线性规划一个徒步旅行者要在背包中选择一些最有价值的物品携带，他最多能携带115kg
的物品。现共有5件物品，分别重54kg、
35kg、57kg、46kg、19kg,其价值依次为7、5、9、6、3。问该旅行者携带那些物品，使总价值最大?
例 14 背包问题
http://www.tju.edu.cn
第一章 线性规划
=
≤++++
++++=
=
10
1151946573554
..
3695
0
1
54321
5432
或则有：
件物品不携带第件物品携带第解：设
j
j
x
xxxxx
ts
xxxx
x
1
7xzmax
j
j
http://www.tju.edu.cn
第一章 线性规划
2,线性整数规划的一般形式：
=≥
==
=
∑
∑
=
=
为整数（部分或全部）
j
j
n
j
ijij
n
j
jj
x
njx
mibxa
xcz
,,2,10
,,2,1
max
1
1
null
null
http://www.tju.edu.cn
第一章 线性规划整数规划一般可以分为三类：
1）纯整数规划：全部决策变量都限定取整数；
2）混合整数规划：部分决策变量为整数，即规划中变量一部分取整数，其余部分是连续变量；
3）0-1规划，不仅限定决策变量取整数，而且只允许取0和1两个值。
http://www.tju.edu.cn
第一章 线性规划
3,线性整数规划问题解的特点松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题
http://www.tju.edu.cn
第一章 线性规划例 15
≥
≤+
≤+
+=
整数
21
21
21
21
21
,
0,
1352
2445
1020
xx
xx
xx
xx
xxMaxz
0
1x
2x
4.8
http://www.tju.edu.cn
第一章 线性规划最优解不一定在顶点上达到最优解不一定是放松问题最优解的邻近整数解整数可行解远多余于顶点，枚举法不可取
http://www.tju.edu.cn
第一章 线性规划二、线性整数规划的分枝定界法分枝定界法：设有最大化的整数规划问题A,与它相应的线性规划问题为B,求解问题B,若B 的最优解不符合A 的整数条件，则 B的最优值一定为A 最优值Z
*
的上界，而A
的任意可行解的目标函数值将是Z
*
的下界，分支定界法就是将B 的可行域分成子区域（称为分支方法）
的方法，通过减小最优值的上界和下界最终得到最优值分支边界
http://www.tju.edu.cn
第一章 线性规划
≥
≤+
≤+
+=
整数
21
21
21
21
21
,
0,
70207
5679
9040
xx
xx
xx
xx
xxMaxz
例 16
0
1x
2x
4.81
1.82
3560
356
*
0
≤≤
=
Z
Z
http://www.tju.edu.cn
第一章 线性规划对原问题增加两个约束条件
5,4
11
≥≤ xx
0
1x
2x
4.81
1.82
问题 B
1
问题 B
2
问题 B
1
问题 B
2
Z
1
=349
X
1
=4
X
2
=2.1
Z
2
=341
X
1
=5
X
2
=1.57
3490
*
≤≤ Z
http://www.tju.edu.cn
第一章 线性规划对 B
1
问题增加两个约束条件
2,3
22
≤≥ xx
问题 B
3
问题 B
4
Z
1
=340
X
1
=4
X
2
=2
Z
2
=327
X
1
=1.42
X
2
=3
341340
*
≤≤ Z
http://www.tju.edu.cn
第一章 线性规划对 B
2
问题增加两个约束条件
1,2
22
≤≥ xx
问题 B
5
问题 B
6
Z
1
=308
X
1
=5.44
X
2
=1
无可行解
340
*
=Z
问题 B
Z
0
=356
X
1
=4.81
X
2
=1.82
问题 B
1
Z
1
=349
X
1
=4
X
2
=2.1
问题 B
3
Z
3
=340
X
1
=4
X
2
=2
问题 B
4
Z
4
=327
X
1
=1.42
X
2
=3
问题 B
5
Z
5
=308
X
1
=5.44
X
2
=1
问题 B
6
无可行解问题 B
2
Z
2
=341
X
1
=5
X
2
=1.57
4
1
≤x 5
1
≥x
3560
356
*
0
≤≤
=
Z
Z
2
2
≤x
3
2
≥x
2
2
≤x
3
2
≥x
××
×
3490
*
≤≤ Z
341340
*
≤≤ Z
340
*
=Z
http://www.tju.edu.cn
第一章 线性规划分枝定界法求解问题的步骤：
将要求解的整数规划问题称为问题 A，将其松弛问题称为问题 B，若
（ 1） B没有可行解，这时 A也没有可行解，停止
（ 2） B有最优解，并符合问题 A的整数条件,B的最优解即为 A的最优解
（ 3） B有最优解，但不符合 A的整数条件，记它目标函数值为最优值上界，观察一下界值。
ZZ
Z
_
*
_
≤≤
http://www.tju.edu.cn
第一章 线性规划第一步：分枝，在Ｂ
中选择一个不符合整数条件的变量 xj，其值为 bj，［ bj］表示小于 bj的最大整数，
构造两个约束条件。
1][
][
+≥
≤
jj
jj
bx
bx
将此两个约束条件加入 B，在不考虑整数条件的情况下，求解两个后继问题 B
1
和 B
2
http://www.tju.edu.cn
第一章 线性规划定界，以每个后继问题为一分枝标明求解结果，与其他问题解的结果中，找出目标函数最大者作为新的上界，从已符合整数条件的各分支中，找出目标函数值最大者作为新的下界，
若无作用，下界仍为零。
第二步：比较与剪枝，各分枝的最优目标函数中若有小于下界者，则剪掉这枝，此后无需再考虑。若大于下界，且不符合整数条件，则重复第一步，直至找到最优解为止。
http://www.tju.edu.cn
第一章 线性规划三、线性整数规划的割平面法算法思想由放松问题的可行域向整数规划的可行域逼近方法 ——利用超平面切除要求整数解保留不符合整数要求的线性规划最优解被切除
http://www.tju.edu.cn
第一章 线性规划例 17：求解
≥
≤+
≤+?
+=
整数
21
21
21
21
21
,
0,
43
1
xx
xx
xx
xx
xxMaxz
0
1x
2x
4
10
max,
4
7
,
4
3
21
=== Zxx
A
D
C
http://www.tju.edu.cn
第一章 线性规划
0
x
4
0
x
3
1
x
2
1
x
1
B
-1
b
C
B
X
B
x
3
x
4
0
0
1
4
-1
3
1
1
1
0
0
1
1 00
单纯形表,
1
x
1
x
2
7/4 0 1 3/4 1/4
σ
3/4 1 0 -1/4 1/4
0 0 -1/2 -1/2
1
1
http://www.tju.edu.cn
第一章 线性规划由终表得到如下关系：
将系数和常数项分解成整数和真分数之和，移项变为：
4
7
4
1
4
3
4
3
4
1
4
1
432
431
=++
=+?
xxx
xxx
)
4
1
4
3
(
4
3
1
)
4
1
4
3
(
4
3
432
4331
xxx
xxxx
+?=?
+?=?
http://www.tju.edu.cn
第一章 线性规划整数条件可由下式代替
0)
4
1
4
3
(
4
3
43
≤+? xx
这就得到了一个切割方程，代入单纯形表终表中，利用对偶单纯形法求解即可
http://www.tju.edu.cn
第一章 线性规划
0
1
1
0
x
4
0
x
3
1
x
2
1
x
1
B
-1
b
C
B
X
B
单纯形表,
x
1
x
2
7/4 0 1 3/4 1/4
σ
3/4 1 0 -1/4 1/4
0 0 -1/2 -1/2
0
x
5
x
5
-3
00[-3] -1
0
0
1
0
0
1
1
x
1
x
2
10100
11001/3
0 0 0 -1/3
x
3
1
0011/3
1/4
-1/12
-1/3
-1/6
解题完毕
http://www.tju.edu.cn
第一章 线性规划割平面法的步骤：
1,令 x
i
是相应线性规划最优解中为分数值的基变量，由单纯形表的终表得到：
2、将b
i
和a
ij
都分解成整数部分[b
i
]与非负真分数f之和，[b
i
]为不超过b的最大整数
∑
=+
ijiji
bxax
10][
10,][
<≤+=
<<+=
ikijijij
iiii
ffaa
ffbb
若 b
i
=2.35,则[b
i
]=2,f=0.35
若 b
i
=-0.45,则 [b
i
]=-1,f=0.55
http://www.tju.edu.cn
第一章 线性规划
∑∑
=?+
kk
kikiikiki
xffNxNx
提出切割方程
0≤?
∑
k
kiki
xff
http://www.tju.edu.cn
第一章 线性规划算法步骤求放松问题的最优基可行解判断是否为整数解是停止得到最优解否在单纯性表中加入一列利用对偶单纯形算法求最优解
http://www.tju.edu.cn
第一章 线性规划四、0-1型整数规划问题的求解方法：隐枚举法枚举法：将全部解列出，验证约束，比较目标隐枚举法：找出一个可行解，祘其目标。由此确定一个过滤条件，再枚举
http://www.tju.edu.cn
第一章 线性规划
==
≤+
≤+
≤++
≤?+
+?=
3,2,110
64
3
44
22
523
32
21
321
321
321
ix
xx
xx
xxx
xxx
xxxMaxz
i
，或点约束
？
Z
01234
000
001
010
011
100
101
110
111
0
5
-2
3
3
8
1
6
-1
0
1
2
0
1
1
1
5
8
例18
http://www.tju.edu.cn
第一章 线性规划例19 指派问题有一份中文说明书，需译成英、日、德、
俄四种文字。分别记为E、J、G、R，有甲、
乙、丙、丁四人，他们将中文说明书翻译成不同语种说明书所需时间如表所示，问应当如何指派工作，使所需总时间最少。
http://www.tju.edu.cn
第一章 线性规划人员
EJGR
甲乙丙丁
2
10
9
7
15
4
14
8
13
14
16
11
4
15
13
9
http://www.tju.edu.cn
第一章 线性规划
=
==
==
=
∑
∑
∑∑
=
=
==
10
,,2,11
,,2,11
..
min
1
1
11
或
ij
n
j
ij
n
i
ij
n
i
n
j
ijij
x
nix
njx
ts
xcZ
null
null
指派问题最优解具有如下性质：
若从指派问题的系数矩阵C的某行
（或某列）个元素分别减去一个常数k，得到一个新矩阵C
’
，则以C
和C ’为系数矩阵的两个指派问题有相同的最优解。
http://www.tju.edu.cn
第一章 线性规划指派问题的匈牙利解法步骤1,变换系数矩阵。先对各行元素分别减去本行中最小元素，再对各列元素分别减去本列中最小元素。
步骤2,在变换后的系数矩阵中确定独立零元素，若独立零元素为n个，得到最优解，否则，作能覆盖所有零元素的最小直线数目的直线集合，转步骤3
步骤3,继续变换系数矩阵，在未被覆盖的元素中找出一个最小元素，未被覆盖的元素所在行或列中各元素都减去这一最小元素，从而出现零元素。
http://www.tju.edu.cn
第一章 线性规划例
=
6101296
1061476
781296
10141797
1215784
c
=
06630
40810
12630
37820
811340
c
-4
-7
-6
-6
-6
=
06320
40500
12320
37510
811030
c
-1 -3
http://www.tju.edu.cn
第一章 线性规划
=
]0[632
45]0[
1232
3751]0[
811]0[3
φ
φφ
φ
φ
c
√
√
√
http://www.tju.edu.cn
第一章 线性规划
=?
=
04321
40501
01210
26600
811031
04320
40500
01211
26601
811030
'''
cc
[ ]
[ ]
[ ]
[ ]
[ ]
http://www.tju.edu.cn
第一章 线性规划
=
10000
01000
00001
00010
00100
'
X
第一章 线性规划（Linear Programming）
第一章 线性规划（ ）
1.1 线性规划的模型与图解法
1.2 单纯形法
1.3 对偶问题与灵敏度分析
1.4 运输问题
1.5 线性整数规划
http://www.tju.edu.cn
第一章 线性规划
1.1 线性规划的模型与图解法一、线性规划问题及其数学模型
1.线性规划问题在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到最大的效益。
http://www.tju.edu.cn
第一章 线性规划例1 某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：
试拟订使总收入最大的生产计划方案。
资源单耗 产品资源甲 乙 资源限量煤电油
9 4
4 5
3 10
360
200
300
单位产品价格
7 12
http://www.tju.edu.cn
第一章 线性规划
1.决策变量：需决策的量，即待求的未知数；
2.目标函数：需优化的量，即欲达的目标，用决策变量的表达式表示；
3.约束条件：为实现优化目标需受到的限制，
用决策变量的等式或不等式表示。
线性规划模型的三要素
http://www.tju.edu.cn
第一章 线性规划目标函数,总收入，记为,则,
为体现对其追求极大化，在 的前面冠以极大号
Max；
决策变量,甲、乙产品的计划产量，记为 ；
在本例中约束条件,分别来自资源煤、电、油限量的约束，
和产量非负的约束，表示为
≥
≤+
≤+
≤+
0,
300103
20054
36049
..
21
21
21
21
xx
xx
xx
xx
ts
21
,xx
z
12
712z xx= +
z
http://www.tju.edu.cn
第一章 线性规划解：设安排甲、乙产量分别为,总收入为,则模型为：
21,xx
z
21 127 xxMaxz +=
≥
≤+
≤+
≤+
0,
300103
20054
36049
..
21
21
21
21
xx
xx
xx
xx
ts
http://www.tju.edu.cn
第一章 线性规划线性规划模型的一个基本特点：
目标和约束均为变量的线性表达式如果模型中出现如的非线性表达式，则不属于线性规划。
3
2
2
1
1
ln2
x
xx?+
http://www.tju.edu.cn
第一章 线性规划例2 某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：
要求在充分利用各种资源条件下使建造住宅的总面积为最大，求建造方案。
水泥
(公斤 /m
2
)
4000
(千工日 )
147000
(千块 )
150000
(吨 )
20000
(吨 )
110000
(千元 )
资源限量
3.5——18025120
大模住宅
3.0——19030135
壁板住宅
4.521011012105
砖混住宅人工
(工日/m
2
)
砖
(块/m
2
)
钢材
(公斤/m
2
)
造价
(元/m
2
)
资源住宅体系
http://www.tju.edu.cn
第一章 线性规划解,设今年计划修建砖混、壁板、大模住宅各为,为总面积,则本问题的数学模型为:
≥
≤++
≤
≤++
≤++
≤++
0,,
40000035.0003.00045.0
147000210.0
150000180.0190.0110.0
20000025.0030.0012.0
110000120.0135.0105.0
.
321
321
1
321
321
321
xxx
xxx
x
xxx
xxx
xxx
ts
321 xxxMaxz ++=
前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个变量，10个约束条件。
123
,,x xx
z
http://www.tju.edu.cn
第一章 线性规划练习：
某畜牧厂每日要为牲畜购买饲料以使其获取 A、
B,C,D四种养分。市场上可选择的饲料有 M,N两种。
有关数据如下：试决定买 M与 N二种饲料各多少公斤而使支出的总费用为最少？
4
10
售价 （元
/公斤）
0.4 0.6 2.0 1.7
牲畜每日每头需要量
0 0.1 0.2 0.1N
0.1 0 0.1 0.2M
每公斤含营养成分
A B C D
http://www.tju.edu.cn
第一章 线性规划解：设购买 M,N饲料各为,则
21 410 xxMinz +=
≥
≥+
≥+
≥+
≥+
0,
7.11.02.0
0.22.01.0
6.01.00
4.001.0
..
21
21
21
21
21
xx
xx
xx
xx
xx
ts
21
,xx
http://www.tju.edu.cn
第一章 线性规划线性规划模型的一般形式：以 MAX型,约束为例
2,线性规划的数学模型决策变量：
目标函数：
约束条件：
n
xx,,
1
null
nn
xcxcMaxz ++= null
11
≥
≤++
≤++
0,,
..
1
11
11111
n
m
nmnm
nn
xx
bxaxa
bxaxa
ts
null
null
null
null
≤
http://www.tju.edu.cn
第一章 线性规划则模型可表示为模型一般式的矩阵形式
T
mnmijn
T
n
bbbaAccCxxX ),,(,)(),,,(,),,(
111
nullnullnull ====
×
≥
≤
=
0
..
X
bAX
ts
CXMaxz
http://www.tju.edu.cn
第一章 线性规划一般地中 称为决策变量向量,称为价格系数向量,
称为技术系数矩阵,称为资源限制向量。
≥
≤
=
0
..
X
bAX
ts
CXMaxz
X
C
A
b
http://www.tju.edu.cn
第一章 线性规划图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。
二、线性规划问题的图解法
http://www.tju.edu.cn
第一章 线性规划
1,先做约束的图形先做非负约束的图形；
再做资源约束的图形 。
以例1为例，其约束为
≥
≤+
≤+
≤+
0,
300103
20054
36049
.
21
21
21
21
xx
xx
xx
xx
ts
0
1x
2x
90
40 50 100
40
30
http://www.tju.edu.cn
第一章 线性规划
0
1x
2x
对于目标函数任给 二不同的值，
便可做出相应的二直线，用虚线表示。
以例1为例，其目标为
，分别令,做出相应的二直线，便可看出 增大的方向。
nn
xcxcz ++= null
11
z
21
127 xxz +=
16884 == zz 和
z
7
12
14
24
2,再做目标图形
http://www.tju.edu.cn
第一章 线性规划
3,求出最优解将目标直线向使目标 优化的方向移，直至可行域的边界为止，
这时其与可行域的,切,
点 即最优解。
如在例1中，
是可行域的一个角点，
经求解交出 的二约束直线联立的方程可解得
z
*
X
*
X
*
X
T
X )24,20(
*
=
0
1x
2x
90
40 50 100
30
40
*
X
http://www.tju.edu.cn
第一章 线性规划由图解法的结果得到例1的最优解,
还可将其代入目标函数求得相应的最优目标值
。说明当甲产量安排 20 个单位，乙产量安排 24 个单位时，可获得最大的收入 428元。
T
X )24,20(
*
=
428
*
=z
http://www.tju.edu.cn
第一章 线性规划
≥
≥+
≥+
+=
0,
5.143
12
..
46
21
21
21
21
xx
xx
xx
ts
xxMinz
0
1x
2x
1
5.0
375.0
5.1
1
*
X
3,)0,5.0(
**
== zX
T
练习：用图解法求解下面的线性规划。
http://www.tju.edu.cn
第一章 线性规划最优解在什么位置获得？
线性规划的可行域是一个什么形状？
思考
——
多边形，而且是
“
凸
”
形的多边形。
——
在边界，而且是在某个顶点获得。
http://www.tju.edu.cn
第一章 线性规划
（1 ） 线性规划的约束集（即可行域）是一个凸多面体。
凸多面体是凸集的一种。所谓凸集是指：集中任两点的连线仍属此集。试判断下面的图形是否凸集：
凸集中的
“
极点
”
，又称顶点或角点，是指它属于凸集，但不能表示成集中某二点连线的内点。如多边形的顶点。
由图解法得到线性规划解的一些特性
http://www.tju.edu.cn
第一章 线性规划因为，由图解法可知，只有当目标直线平移到边界时，
才能使目标 z 达到最大限度的优化。
问题,本性质有何重要意义？
（ 2）线性规划的最优解（若存在的话）必能在可行域的顶点获得
http://www.tju.edu.cn
第一章 线性规划
（ 3）线性规划解的几种情形
1）唯一解 2）多重最优解
3）无可行解注：出现 3）,4）情况时，建模有问题
4）无有限最优解
http://www.tju.edu.cn
第一章 线性规划单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B.Danzig）提出。
尽管在其后的几十年中，又有一些算法问世，
但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。
1.2 单纯形法
http://www.tju.edu.cn
第一章 线性规划一、单纯形法的预备知识
1,线性规划问题的标准型
≥
=
=
0
..
X
bAX
ts
CXMaxz
标准型的特征：Max型、等式约束、非负约束
。）（的秩为其中,0,≥≤
×
bnmmA
nm
http://www.tju.edu.cn
第一章 线性规划线性规划问题的一般型如何化为标准型？
（ 1）如果目标函数求极小，则
（ 2）如果约束条件为不等式，则引入松弛或剩余变量
CXMinz=
CXMaxz?=
/
加负号
36049
21
≤+ xx
36049
321
=++ xxx
)(xf
)(xf?
*
x
x3
称为松弛变量。问题,它的实际意义是什么？
——
煤资源的“剩余”。
http://www.tju.edu.cn
第一章 线性规划
（ 3）如果存在自由变量，则：
（ 4）右端项 仅需将等式或不等式两端同乘（ -1）
（ 5）对 即可xxx?=≤
'
0 令
0<
i
b
0,,
//////
≥?=
kkkkk
xxxxx
http://www.tju.edu.cn
第一章 线性规划练习：请将例 1的约束化为标准型
≥
≤+
≤+
≤+
0,
300103
20054
36049
..
21
21
21
21
xx
xx
xx
xx
ts
,,,
543
xxx
≥
=++
=++
=++
0,,,,
300 103
20054
360 49
..
543
21
5
21
4
21
3
21
xxxxx
xxx
xxx
xxx
ts
解：增加松弛变量 则约束化为易见，增加的松弛变量的系数恰构成一个单位阵
I
。
http://www.tju.edu.cn
第一章 线性规划一般地，记松弛变量的向量为 X
s
，则
≥
≤
0
..
X
bAX
ts
≥
=+
0,
..
s
s
XX
bIXAX
ts
≥
≥
0
..
X
bAX
ts
≥
=?
0,
..
s
s
XX
bIXAX
ts
http://www.tju.edu.cn
第一章 线性规划
2,基本概念
（1 ）可行解与最优解；的解，记为可行解：满足全体约束 X
*
,
X
XCXCX
≤
最优解：可行解中最优的，记为 则对任可行解，有 。
直观上，可行解是可行域中的点，是一个可行的方案；
最优解是可行域的顶点，是一个最优的方案。
http://www.tju.edu.cn
第一章 线性规划
（2 ）基矩阵与基变量基矩阵 (简称基 )：系数阵A中的m 阶可逆子阵，记为B；其余部分称为非基矩阵，记为 N。
基向量：基 B中的列；其余称非基向量。
基变量：与基向量P
j
对应的决策变量 x
j
，记其组成的向量为X
B；与非基向量对应的变量称非基变量，记其组成的向量为X
N
。
http://www.tju.edu.cn
第一章 线性规划
123
12 4
14
3
2 1
2 3
,,0
xxx
xx x
xx
++ =
+=
≥
null
例,下面为某线性规划的约束请例举出其基矩阵和相应的基向量、基变量。
3
http://www.tju.edu.cn
第一章 线性规划阶可逆子阵有中的，解：本例中,2
1
0
0
1
1
2
2
1
AA
=
—— 6个。
一般地，m × n 阶矩阵 A中基的个数最多有多少个？
个。——
m
n
C;,,,
1
0
0
1
4
3
43431
1?
=
=
x
x
XxxPPB
B
，基变量为，其相应的基向量为
。基变量为其相应的基向量为
=
=
2
1
21212
2
,,,,,
1
2
2
1
x
x
XxxPPB
B
问题：本例的A中一共有几个基？
http://www.tju.edu.cn
第一章 线性规划
（3 ）基本解与基本可行解
() ()
.
0
,0,
,,
,
1
111
===?=
=?
==
=
bB
XbBXXNXBbBX
b
X
X
NBbAXXXX
NBAmABBA
BNNB
N
B
T
NB
时，有当取即可表示为约束中的相应地
）（列，则可记中的前表示取定后，不妨设中的基当解；为线性规划的一个基本的解称?
==
0
1
bB
XbAX
http://www.tju.edu.cn
第一章 线性规划可见：一个基本解是由一个基决定的。
注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。
称非负的基本解为基本可行解（简称基可行解）。
http://www.tju.edu.cn
第一章 线性规划在上例中
≥
=+?
=++
0,,
32
12
41
421
321
xx
xxx
xxx
null
求相应于基 B
1
和 B
2
的基本解，它们是否基本可行解？
,
3
1
3
1
1
0
0
1
,
1
0
0
1
,
1
0
0
1
11
1
=
=
=
=
bBBB
11
解：
是基本可行解。的基本解为相应于基,)3,1,0,0(
1
T
XB =
,
5
1
-
5
7
3
1
5
1
-
5
2
5
2
5
1
,
5
1
-
5
2
5
2
5
1
,
1-
2
2
1
11
2
=
=
=
=
bBBB
22
不是基本可行解。的基本解为相应于基,,0,0)
5
1
,-
5
7
(
2
T
XB =
http://www.tju.edu.cn
第一章 线性规划上二组概念间的联系：
系数阵 A中可找出若干个基B
每个基 B都对应于一个基本解非负的基本解就是基本可行解几种解之间的关系：
可行解基本解非可行解基本可行解问题：基本可行解是可行域中的哪些点？
http://www.tju.edu.cn
第一章 线性规划
3,基本定理
（1）线性规划的可行域是一个凸多面体。
（3）线性规划的最优解（若存在的话）必能在可行域的顶点获得。
（2）线性规划可行域的顶点与基本可行解一一对应。
http://www.tju.edu.cn
第一章 线性规划二、单纯形法的步骤确定初始基本可行解检验其是否最优？
寻找更好的基本可行解否是单纯形法是一种迭代的算法，它的思想是在可行域的顶点 ——基本可行解中寻优。由于顶点是有限个,因此，算法经有限步可终止。
方法前提,模型化为标准型
http://www.tju.edu.cn
第一章 线性规划
1.确定初始基可行解由于基可行解是由一个可行基决定的，因此，确定初始基可行解 X
0
相当于确定一个初始可行基 B
0
。
方法：若A中含 I，则 B
0
=I；
若 A中不含 I，则可用人工变量法构造一个 I。
方法：若A中含 I，则 B
0
=I；
若 A中不含 I，则可用人工变量法构造一个 I。
问题：若 B
0
=I，则 X
0
=？例 1中X
0
=？
http://www.tju.edu.cn
第一章 线性规划
2,最优性检验
bAX =
b
X
X
NB
N
B
=
),(
NB
NXBbBX
11
=
矩阵分块把目标函数用 非基变量 表示：
∴
CXZ =
=
N
B
NB
X
X
CC ),(
NNBB
XCXC +=
NNNB
XCNXBbBC +?=
)(
11
NBNB
XNBCCbBC )(
11
+=
检验数向量，记为 σ。 当 σ ≤ 0时，当前解为最优解。
http://www.tju.edu.cn
第一章 线性规划方法,（1 ）计算每个 x
j
的检验数 jBjj
PBCc
1?
=σ
（2 ）若所有 σ
j
≤0,则当前解为最优；
否则，至少有 σ
k
>0,转3 。
http://www.tju.edu.cn
第一章 线性规划
3,寻找更好的基可行解由于基可行解与基对应，即寻找一个新的基可行解，
相当于从上一个基B
0
变换为下一个新的基B
1
，因此，本步骤也称为基变换。
≥
>
0
1
1
01
bB
zz
可行：
改善：
基变换的原则
）变换的方法：（
nkl
PPPP,,,,,,
1
nullnullnull
进基；对应的令保证“改善”进基
kk
P0> σ
可决定出基由保证“可行”出基 0
11
≥?=
NB
NXBbBX
http://www.tju.edu.cn
第一章 线性规划
{ }
出基。对应的令进基；对应的方法：令
lik
ik
i
i
i
l
kj
j
k
PPB
PB
bB
P
>===
>=
0)(
)(
)(
min
0max
1
1
1
θθ
σσ
称作检验比。
i
θ
http://www.tju.edu.cn
第一章 线性规划以例1 为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。
（1）先将模型化为标准型
≥
=++
=++
=++
0,,,,
300103
20054
36049
..
543
21
5
21
4
21
3
21
xxxxx
xxx
xxx
xxx
ts
21 127 xxMaxz +=
http://www.tju.edu.cn
第一章 线性规划
(2) 确定初始基可行解、检验;00,300)(0,0,360,2,00)(360,200,3,
0
1
00
TT
XbBB ==
=
1
1
1;,
52
PP 向量为再计算检验比确定出基量为计算检验数确定进基向
http://www.tju.edu.cn
第一章 线性规划
（ 3）换基、计算下一个基可行解、再检验，直至最优;50,0)(0,24,240,,)(240,50,30,
10
51
41
1
1
11
TT
XbBB ==
=;0,0)(20,24,84,,(84,20,24),
103
54
491
2
1
22
TT
XbBB ==
=
0
0;,
41
PP 向量为再计算检验比确定出基量为计算检验数确定进基向前解为最优。计算检验数均非正，当问题：当模型规模较大时，计算量很大。
事实上，单纯形法的实现是在单纯形表上完成的。
事实上，单纯形法的实现是在单纯形表上完成的。
http://www.tju.edu.cn
第一章 线性规划三、单纯形表单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。
1
1
0
1
01
1
0
0
)(
)(
0
00
B
PB
bB
PBCc
bB
XB
ik
i
i
ijBBjj
→=→?=→
=→
min
0
θσ
回顾单纯形法步骤
bB
1?
需计算
AB
1?
需计算
( ),AbB
1?
内容是因此，单纯形表的主体
( )
()
()
1
2
1
1
1
0
null
AbB
AbB
AbB
↓
↓
即单纯形表。
变换迭代计算的由此设计了基于初等行得。也可通过初等行变换求个两只有一列不同，故相邻而相邻两个
1?
B
B
http://www.tju.edu.cn
第一章 线性规划单纯形表的主要结构：
X
C
AB
1?
bB
1?
σ
问题：第一张表的B
-1
=？ ——单位阵 I。
检验数的公式是什么？ jBjj
PBCc
1?
= σ
在哪里？
j
PB
1?
列中的第jAB
1
http://www.tju.edu.cn
第一章 线性规划例1
Max Z=7 x
1
+12x
2
9 x
1
+4x
2
≤ 360
4x
1
+5x
2
≤ 200
3 x
1
+10x
2
≤ 300
x
1
,x
2
≥ 0
s.t.
Max Z=7 x
1
+12x
2
9 x
1
+4x
2
+x
3
=360
4x
1
+5x
2
+x
4
= 200
3 x
1
+10x
2
+x
5
= 300
x
1
,…,x
5
≥ 0
s.t.
化为标准型
σ 的计算,
X
B
C
B
B
-1
b
7
x
1
12
X
2
0
x
3
0
x
4
0
x
5
θ
σ
x
3
x
4
x
5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12 000
单纯形表,
7
1
1
11
PBCc
B
=σ
= 7
7=
]0,0,0[
3
4
9
http://www.tju.edu.cn
第一章 线性规划
σ
θ
0
x
5
0
x
4
0
x
3
12
x
2
7
x
1
B
-1
b
C
B
X
B
x
3
x
4
x
5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12 000
单纯形表,
7
90
40
30
[ ]
主元素
σ
θ
0
x
5
0
x
4
0
x
3
12
x
2
7
x
1
B
-1
b
C
B
X
B
x
3
x
4
x
5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12 000
单纯形表,
7
90
40
30
[ ]
x
3
x
4
x
2
0
0
12 30 0.3 1 0 0 0.1
σ
以
10
为主元进行初等行变换
50 2.5 0 0 1 -0.5
240 7.8 0 1 0 -0.4
3.4 0 0 0 -1.2
或,
1
1
11
PBCc
B
=σ
= 7
4.3=
]12,0,0[
3.0
5.2
8.7
σ
θ
0
x
5
0
x
4
0
x
3
12
x
2
7
x
1
B
-1
b
C
B
X
B
x
3
x
4
x
5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12 000
单纯形表,
7
90
40
30
[ ]
0.3 1 0 0 0.1
σ
x
3
x
4
x
2
0
0
12 30
以
10
为主元进行初等行变换
50 2.5 0 0 1 -0.5
7.8
3.4
240 0 1 0 -0.4
0 0 0 -1.2
或,
5
1
55
PBCc
B
=σ?= 0
2.1?=
]12,0,0[
1.0
5.0
4.0
30.8
20
100
x
3
x
1
x
2
0
7
12 24 0 1 0 -0.12 0.16
σ
20 1 0 0 0.4 -0.2
84 0 0 1 -3.12 1.16
0 0 0 -1.36 -0.52
σ
σ
θ
0
x
5
0
x
4
0
x
3
12
x
2
7
x
1
B
-1
b
C
B
X
B
x
3
x
4
x
5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12 000
单纯形表,
7
90
40
30
[ ]
0
0
12 30 0.3 1 0 0 0.1
50 2.5 001-0.5
240 7.8 0 1 0 -0.4
3.4 0 0 0 -1.2
[ ]
x
3
x
4
x
2
30.8
20
100
以为主元进行初等行变换
2.5
∴ X*=(20,24,84,0,0)
T
Z*=428
x
3
x
1
x
2
0
7
12 24 0 1 0 -0.12
0.16
σ
20 1 0 0 0.4 -0.2
84 0 0 1 -3.12 1.16
0 0 0 -1.36 -0.52
σ
σ
θ
x
5
x
4
x
3
x
2
x
1
B
-
1
b
C
B
X
B
x
3
x
4
x
5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12 000
单纯形表,
7
90
40
30
x
3
x
4
x
2
0
0
12 30 0.3 1 0 0 0.1
50 2.5 0 0 1 -0.5
240 7.8 0 1 0 -0.4
3.4 0 0 0 -1.2
30.8
20
100
== ),,(
243
PPPB
1000
510
401
以第 2个表为例：
=
1
B
1.000
5.010
4.001
注：单纯形表中的信息
⑴每一列的含义：
B
-1
(bA)=(B
-1
b,B
-1
P
1
,…,B
-1
P
n
)
⑵每个表中的B和B
-1
的查找
B从初表中找；
B
-1
从当前表中找，对应 于初表中的 I的位置。
⑶终表分析 ——最优基B*
和 (B*)
-1
的查找
== ),,(
213
*
PPPB
1030
540
491
16.012.00
2.04.00
16.112.31
=
1*
)(B
x
3
x
1
x
2
0
7
12 24 0 1 0 -0.12
0.16
σ
20 1 0 0 0.4 -0.2
84 0 0 1 -3.12 1.16
0 0 0 -1.36 -0.52
σ
σ
θ
x
5
x
4
x
3
x
2
x
1
B
-
1
b
C
B
X
B
x
3
x
4
x
5
0
0
0
360
200
300
9
4
3
4
5
10
1
0
0
0
1
0
0
0
1
12 000
单纯形表,
7
90
40
30
x
3
x
4
x
2
0
0
12 30 0.3 1 0 0 0.1
50 2.5 0 0 1 -0.5
240 7.8 0 1 0 -0.4
3.4 0 0 0 -1.2
30.8
20
100
注：单纯形表中的信息
http://www.tju.edu.cn
第一章 线性规划练习：用单纯形法求解下面的线性规划
≥
≤+
≤+
0,
2
5
..
21
21
21
xx
xx
xx
ts 105
153
212.5 xxMaxz +=
将模型化为标准型：解：增加松弛变量,,
43
xx
21 xxMaxz += 5.2
≥
=++
=++
0,,,
1025
15 53
..
43
4
21
3
21
21
xxxx
xxx
xxx
ts
http://www.tju.edu.cn
第一章 线性规划
10 2 5
0153
10
15
4
3
x
x
0
0
0 0 1 2.5
2
5
[ ]
4321
xxxx
0 0 1 2.5
bB
1?
B
X
B
C
θ
5
1
0
5
2
1
5
3
- 1
5
19
0
2
9
1
3
x
x
2.5
0
0.5- 0 0 0
T
X )09,0,2,(=
5=
z
,
1
1
1
0
=
B
,
5
1
0
5
3
-1
1
1
=
B
问题：本题的单纯形终表检验数有何特点？
—— 非基变量 x
2
的检验数等于零。
http://www.tju.edu.cn
第一章 线性规划注：（ 1）解的几种情况在单纯形表上的体现（Max 型）：
- 唯一最优解：终表非基变量检验数均小于零；
- 多重最优解：终表非基变量检验数中有等于零的；
- 无界解：任意表有正检验数相应的系数列均非正。
- 无解：最优解的基变量中含有人工变量注：（ ）解的几种情况在单纯形表上的体现（ 型）：
唯一最优解：终表非基变量检验数均小于零；
多重最优解：终表非基变量检验数中有等于零的；
无界解：任意表有正检验数相应的系数列均非正。
无解：最优解的基变量中含有人工变量
（ 2） Min型单纯形表与Max 型的区别仅在于：检验数反号，即
- 令负检验数中最小的对应的变量进基；
- 当检验数均大于等于零时为最优。
（ ） 型单纯形表与 型的区别仅在于：检验数反号，即令负检验数中最小的对应的变量进基；
当检验数均大于等于零时为最优。
http://www.tju.edu.cn
第一章 线性规划一、对偶问题及其性质乙甲例 1称为例 4的原问题,记为（ P）
1,问题的提出例1 煤电油例
Max Z=7 x
1
+12x
2
9 x
1
+4x
2
≤ 360
4x
1
+5x
2
≤ 200
3 x
1
+10x
2
≤ 300
x
1
,x
2
≥ 0
s.t.
Min W=360y
1
+200y
2
+300y
3
s.t.
9y
1
+4y
2
+3y
3
≥ 7
4y
1
+5y
2
+10y
3
≥ 12
y
1,
y
2,
y
3
≥ 0
例4、这时有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽量少。试建立购买者的线性规划模型。
例 4称为例 1的对偶问题，记为（D ）
1.3 对偶问题与灵敏度分析
http://www.tju.edu.cn
第一章 线性规划
2,对偶模型的一般式则对偶问题为，记 ),,(
321
yyyY =
≥
≤
以例 4为例，原问题为
=
0
..
X
bAX
ts
CXzmax
（P ）
≥
≥
=
0
..
min
Y
CYA
ts
Ybw
（D ）
这是最常见的对偶模型形式，称为对称式对偶模型。二者间具有十分对称的对应关系：
（ 4） P的目标函数系数,D约束右边向量
（ 5） P的资源约束向量 =D的目标函数系数
（ 6） P技术系数矩阵 =D技术系数矩阵转置特点：
（ 1） P为 max型,D为 min型
（ 2） P的变量个数 =D的约束个数
（ 3） P的约束个数 =D的变量个数
http://www.tju.edu.cn
第一章 线性规划若 P的某个约束为,=”型则D的相应变量为自由若 P的某个变量为自由则D的相应约束为,=”型简单推导过程：
设 P为：
≥
=+
≤+
≤+
+=
0,
300103
20054
36049
..
127
21
21
21
21
21
xx
xx
xx
xx
ts
xxZMax
≥
≤
≤+
≤+
≤+
+=
0,
300103
300103
20054
36049
..
127
21
21
21
21
21
21
xx
xx
xx
xx
xx
ts
xxZMax
D为：
≥
≥?++
≥?++
++=
0,,,
12101054
73349
..
300300200360
4321
4321
4321
4321
yyyy
yyyy
yyyy
ts
yyyyZMin
43
'
3
yyy?=令
≥
≥++
≥++
++=
无约束
'
321
'
321
'
321
'
321
,0,
121054
7349
..
300200360
yyy
yyy
yyy
ts
yyyZMin
http://www.tju.edu.cn
第一章 线性规划
3,如何写出LP模型的对偶模型
（1）若LP为Max型，则尽量化成(P)形式。(等式、自由变量不用转换)
（2）若LP为Min型，则尽量化成(D)形式。(等式、自由变量不用转换)
≥
≤
=
0
..
X
bAX
ts
CXzmax
（P ）
≥
≥
=
0
..
min
Y
CYA
ts
Ybw
（D ）
http://www.tju.edu.cn
第一章 线性规划例 5：写出下面线性规划的对偶规划模型：
≥
=+?
≤?
≤+
+=
0
13
52
32
..
32max
1
21
21
21
21
x
xx
xx
xx
ts
xxz
则对偶目标为解：设对偶变量为
,
,,,
321
w
yyy
≥
=+?
≥?+
++=
0,
3
22
..
53
21
321
321
321
yy
yyy
yyy
ts
yyyw
32
min
http://www.tju.edu.cn
第一章 线性规划
≥≤
=++
≤?+
≥+?+
+?+=
无约束
4321
432
431
4321
4321
,0,,0
6
42 2
5 3
..
4532
xxxx
xxx
xxx
xxxx
ts
xxxxZMin
练习：写出下面LP的对偶
http://www.tju.edu.cn
第一章 线性规划其对偶模型为：
123
12
13
123
123
12
546
22
3
32 5..
4
,0,
Max w yyy
yy
yyyst
yyy
yy
=?+
+≤?
+ ≤
+≤?
+ +=
≥?
http://www.tju.edu.cn
第一章 线性规划
(1)对称性
（ P）与（ D）互为对偶
4,对偶性质
(2)弱对偶性设 X,Y 分别为（P ）、（D）的任一可行解，
则
YbCX ≤
证,∵
X,Y 为（ P）、（ D）的可行解
bAX
∴
≤ YbYAX ≤
CXYAX ≥
YbCX ≤
CYA≥
由此可推出：若（P ）为无界解，则（ D）无可行解若（D）为无界解，则（ P）无可行解
http://www.tju.edu.cn
第一章 线性规划
(4)对偶定理若（P ）有最优解，则（ D）也有最优解，且二者最优值相等,
(3)解的最优性设,分别为（ P）与（ D）的可行解，且
X Y bYXC =
则
*
XX =
*
YY =
http://www.tju.edu.cn
第一章 线性规划证：对（P ）增加松弛变量Xs，化为
≥
=+
=
0,
..
s
s
XX
bIXAX
ts
CXMaxz
设其最优基为B，终表为
s
XX
C
0
IBAB
11
1
bBC
B
IBCABCC
Bb
11
0
≤?=
≤?=
00
0
1
1
IBC
ABCC
Bs
B
σ
σ
其检验数为满足则取 YBCY
B
,
1?
=
≥
≥
0Y
CAY
== zbBCbYY
B
1
D）的可行解，且是（即
.3
=YY，由性质
http://www.tju.edu.cn
第一章 线性规划问题：(1) 由性质5 可知，对偶问题最优解的表达式
Y* =？
(2) 求 Y*是否有必要重新求解（ D）？
—— C
B
B
-1
—— 不必。可以从原问题（P ）的单纯形终表获得。
http://www.tju.edu.cn
第一章 线性规划
≥
≤+
≤+
0,
2
5
..
21
21
21
xx
xx
xx
ts 105
153
212.5 xxMaxz +=
T
例如，在前面的练习中已知 的终表为
X )09,0,2,(=
5=
z
5
)5.0,0(
=
=
w
Y
4321
xxxx
0 0 1 2.5
bB
1?
B
X
B
C
θ
5
1
0
5
2
1
5
3
- 1
5
19
0
2
9
1
3
x
x
2.5
0
0.5- 0 0 0
http://www.tju.edu.cn
第一章 线性规划
（5）松紧定理（互补松弛性）
设,分别为（P ）与（D）的可行解，则YX
X
Y,是最优解? 0== XYXY
SS
分为最优解中松弛变量部、其中
SS
YX
在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式，另一方面，如果约束条件取严格不等式，则其对应的变量一定为零.
http://www.tju.edu.cn
第一章 线性规划
y
1
… y
i
… y
m
y
m+1
…y
m+j …
y
n+m
x
1
…x
j
…x
n
x
n+1
…x
n+i
…x
n+m
对偶问题的变量 对偶问题的松弛变量原始问题的变量 原始问题的松弛变量
x
j
y
m+j
=0 y
i
x
n+i
=0 (i=1,2,…,m; j=1,2,…,n)
在一对变量中，其中一个大于 0，另一个一定等于 0
直观上
http://www.tju.edu.cn
第一章 线性规划例 6：已知线性规划问题
5,
5
3
,
5
4
5,,2,1,0
332
432
..
32532min
*
2
*
1
54321
54321
54321
===
=≥
≥+++?
≥++++
++++=
zyy
jx
xxxxx
xxxxx
ts
xxxxxw
j
解为：已知其对偶问题的最优
null
试用对偶理论找出原问题的最优解
http://www.tju.edu.cn
第一章 线性规划
5.对偶问题的经济解释
(1) 对偶最优解的经济解释：资源的影子价格
（Shadow Price）
C
B
B
-1 ——
对偶问题的最优解 —— 买主的最低出价；
——
原问题资源的影子价格 —— 当该资源增加 1单位时引起的总收入的增量 ——卖主的内控价格。
设 DP其最优值为 Z
*
(注：与 LP最优值同），则根据
Z
*
= y
*
b = y
1
*
b
1
+ y
2
*
b
2
+ nullnull + y
m
*
b
m
Z /?b
i
=y
i
*
简单推导：
http://www.tju.edu.cn
第一章 线性规划例 7：例 1（煤电油例）的单纯形终表如下：
0.2- 0.4 0 1
1.16 0.32- 1 0
0.16 0.12- 0 0
2
1
3
x
x
x
12
7
0
0.52- 1.36- 0 0 0
24
20
84
1
0
0
428=
z
（ 1）请指出资源煤电油的影子价格，并解释其经济意义。
（ 2）由单纯形终表还可得到哪些有用的信息？
http://www.tju.edu.cn
第一章 线性规划影子价格在管理决策中的作用：
（ 1）影子价格≠市场价格若影子价格＞市场价格，则应影子价格＜市场价格，则应买进该资源卖出该资源
（ 2）影子价格反映了资源的稀缺性，影子价格越高，则越稀缺。
http://www.tju.edu.cn
第一章 线性规划
≥
≤++++
≤++++
≤++++
++++=
0
max
21
2211
222222121
111212111
2211
nj
mnmnjmjmm
nnjj
nnjj
nnjj
xxxx
bxaxaxaxa
bxaxaxaxa
bxaxaxaxa
st
xcxcxcxcz
nullnull
nullnullnullnullnull
nullnull
nullnull
nullnull
Y
1
Y
2
y
m
（ 2）对偶 约束的 经济解释 ——产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润
mmjiijjj
yayayaya +++++ nullnull
2211
http://www.tju.edu.cn
第一章 线性规划
≥
=?++
=?++
=?++
+++=
+
+
+
0
min
21
2211
222222112
111221111
2211
m
nnmmmnnn
mmm
mmm
mm
yyy
cyyayaya
cyyayaya
cyyayaya
st
ybybybw
null
null
nullnullnullnullnullnullnullnull
null
null
null
（ 3）对偶 松弛变量的 经济解释 ——产品的差额成本差额成本 =机会成本 － 利润
jj
T
jmjmjjjm
caYcayayayy?=?+++=
+
)(
2211
null
机会成本差额成本利润
http://www.tju.edu.cn
第一章 线性规划
=?>
=?>
=
=?>
=?>
=
+
+
+
+
+
+
00
00
0
00
00
0
jjm
jmj
jmj
iin
ini
ini
xy
yx
yx
yx
xy
xy
在利润最大化的生产计划中
（ 1）影子价格大于 0的资源没有剩余；
（ 2）有剩余的资源影子价格等于 0；
（ 3）安排生产的产品机会成本等于利润；
（ 4）机会成本大于利润的产品不安排生产。
（ 4）互补松弛关系的经济解释
http://www.tju.edu.cn
第一章 线性规划二、灵敏度分析任务：讨论模型的系数或变量发生小的变化时对解的影响
（如它们在何范围内变化时可使原最优解或最优基不变？）
对解的影响可行性：B
-1
b≥ 0
最优性：
0
1
≥?
jBj
PBCc
我们主要讨论C,b和变量结构变化时对解的影响。
http://www.tju.edu.cn
第一章 线性规划
1、b 变化时的分析
（只影响解的可行性）
设第 r 种资源 b
r
→b
r
+△（ b→
问题,b在何范围变化时，不影响最优基？
方法：
b）
0
1
≥
bB （保证可行性）
即 0),,,,(
1
1
≥Δ+
T
mr
bbbB nullnull,解出△即可
http://www.tju.edu.cn
第一章 线性规划
2,C 变化时的分析但要分两种情况讨论 。只影响最优性时变为价格,,
jjj
ccc Δ+
即可。故只要
，为因只影响自己的检验数的价格系数是非基变量
0
,
(1)
1
≤
Δ+=
j
jBjjj
jj
PBCcc
xc
σ
σ
的范围。解得只需由
jj
cΔ≤ 0σ
。解得公共的应由所有的数这时要影响所有的检验的价格系数是基变量
ji
imiiii
jj
c
PBccccc
xc
Δ≤
Δ+?=
0
,)(
(2)
1
1
σ
σ nullnull
http://www.tju.edu.cn
第一章 线性规划
3.增加新变量时的分析主要讨论增加新变量 x
n+1
是否有利。经济意义是第 n+1
种新产品是否应当投产，数学意义是 x
n+1
是否应进基。
，即投产无利。，则不增加若
，即投产有利；，则增加若的检验数方法：计算
11
11
1
1
111
0
0
,
++
++
+
+++
≤
>
=
nn
nn
nBnnn
x
x
PBCcx
σ
σ
σ
1
1
11 +
++
=
nBnn
PBCcσ
经济意义：
市场价 影子价
http://www.tju.edu.cn
第一章 线性规划
0.2- 0.4 0 1
1.16 0.32- 1 0
0.16 0.12- 0 0
2
1
3
x
x
x
12
7
0
0.52- 1.36- 0 0 0
24
20
84
1
0
0
428=
z
（ 1）电的影子价格是多少？使最优基仍适用的电的变化范围为何？
（ 2）若有人愿以每度 1元的价格向该厂供应 25度电，是否值得接受？
（ 3）甲产品的价格在何范围内变化时，现最优解不变？
（ 4）若现又考虑一新产品丙，其资源单耗为 10,2，5，
售价为 6.5，问该产品是否可投产？
例 8
http://www.tju.edu.cn
第一章 线性规划
0.2- 0.4 0 1
1.16 0.32- 1 0
0.16 0.12- 0 0
2
1
3
x
x
x
12
7
0
0.52- 1.36- 0 0 0
24
20
84
1
0
0
428=
z
（ 1）电的影子价格是多少？使最优基仍适用的电的变化范围为何？
解：（ 1）电的影子价格是 1.36。
解得由 0
0.12
0.4
3.12
24
20
84
300
200
360
22
1
≥Δ
+
=
Δ+
bbB
仍适用的范围。，即使原最优基 Bb 26.9250
2
≤Δ≤?
http://www.tju.edu.cn
第一章 线性规划
0.2- 0.4 0 1
1.16 0.32- 1 0
0.16 0.12- 0 0
2
1
3
x
x
x
12
7
0
0.52- 1.36- 0 0 0
24
20
84
1
0
0
428=
z
（ 2）若有人愿以每度 1元的价格向该厂供应 25度电，是否值得接受？
解：（ 2）值得。
因 25在 B的适用范围内（即影子价格适用），且
1.36-1.00>0。
http://www.tju.edu.cn
第一章 线性规划
0.2- 0.4 0 1
1.16 0.32- 1 0
0.16 0.12- 0 0
2
1
3
x
x
x
12
7
0
0.52- 1.36- 0 0 0
24
20
84
1
0
0
428=
z
（ 3）甲产品的价格在何范围内变化时，现最优解不变？
解：甲产品的价格c
1
是基变量的价格系数。
() 044.14.08.2
12.0
4.0
12.3
12700
114
≤+Δ=
Δ+?= ccσ由
，得 4.3
1
≥Δc
() 01.920.2.41
0.16
0.2-
1.16
12700
115
≤?Δ+=
Δ+?= ccσ由
，得,6
1
2≤Δc
http://www.tju.edu.cn
第一章 线性规划
0.2- 0.4 0 1
1.16 0.32- 1 0
0.16 0.12- 0 0
2
1
3
x
x
x
12
7
0
0.52- 1.36- 0 0 0
24
20
84
1
0
0
428=
z
（ 4）若现又考虑一新产品丙，其资源单耗为 10,2，5，
售价为 6.5，问该产品是否可投产？
() 032.55.6
5
2
10
52.036.105.6 >?=
=
丙解：因为 σ
故丙产品可以投产。
http://www.tju.edu.cn
第一章 线性规划
1,运输问题的数学模型问题：现有一批货物，从m个仓库运往n个销售地，S
i
处有货物a
i
吨，D
j
处需货物b
j
吨，从
S
i
到D
j
的运价为c
ij
元/吨。问如何安排，既可满足各销地需要，又使总运费最小？
1.4 运输问题
http://www.tju.edu.cn
第一章 线性规划
S
1
S
2
S
m
…
D
n
D
2
D
1
…
a
1
a
2
a
m
b
n
b
2
b
1
…
…
http://www.tju.edu.cn
第一章 线性规划销地产地
D
1
D
2
… D
n
产量
S
1
S
2
…
S
m
X
11
x
12
… x
1n
X
21
x
22
… x
2n
…………
X
m1
x
m2
… x
mn
a
1
a
2
…
a
m
销量
b
1
b
2
… b
n
∑∑
==
=
m
i
n
j
ji
ba
11
产销平衡表
http://www.tju.edu.cn
第一章 线性规划单位运价表销地产地
D
1
D
2
… D
n
S
1
S
2
…
S
m
c
11
c
12
… c
13
c
21
c
22
… c
23
…… … …
c
m1
c
m2
… c
mn
http://www.tju.edu.cn
第一章 线性规划
∑∑
==
=
+++
+++
++=
m
i
n
j
ijij
mnmnmmmm
nn
nn
xc
xcxcxc
xcxcxc
xcxcxcz
11
2211
2222222121
1112121111
...........
min
null
null
null
2,运输问题的数学模型
http://www.tju.edu.cn
第一章 线性规划约束条件为：
njbx
miax
njbx
miax
njbx
miax
j
m
i
ij
iij
j
m
i
ij
iij
j
m
i
ij
iij
,,2,1,
,,2,1,
3
,,2,1,
,,2,1,
)2(
,,2,1,
,,2,1,
)1(
1
n
1j
1
n
1j
1
n
1j
null
null
null
null
null
null
==
=≥
==
=≤
==
==
∑
∑
∑
∑
∑
∑
=
=
=
=
=
=
，则有）供不应求的运输问题（
有供过于求运输问题，则有供销平衡运输问题，则
http://www.tju.edu.cn
第一章 线性规划将约束方程式展开可得
11 1 1
21 2 2
1
11 21 1 1
12 22 2
n
n
mmnm
m
m
x xa
x xa
x xa
x xx b
xxx
++ =
+ +=
++ =
++
null
null
nullnull
null
null
null
2
12
nnmnn
b
x xx b
=
+ +=
nullnullnull null
null
约束方程式中共 m*n个变量,m+n个约束。
http://www.tju.edu.cn
第一章 线性规划
1 1
11
A= 1 1
1 1 1
1 1 1
null
null
null
null
null
nullnull null
null
技术系数矩阵
http://www.tju.edu.cn
第一章 线性规划求解平衡运输问题的表上作业法
（1）确定一个初始的可行调运方案：最小元素法、西北角法、Vogel法
（2）判断当前可行方案是否最优：闭回路法、
位势法
（3）方案调整
3,运输问题的解法
http://www.tju.edu.cn
第一章 线性规划例9：某食品公司下设3个加工厂A1,A2，A3，和4
个门市部B1,B2，B3，B4。各加工厂每天的产量、
各门市部每天的销售量以及从各加工厂到各门市部的运价如下表所示。
问：该公司应如何调运，在满足各门市部销售需要的情况下，使得运费支出为最少？
http://www.tju.edu.cn
第一章 线性规划销地产地
D
1
D
2
D
3
D
4
产量
S
1
S
2
S
3
7
4
9
销量
3 6 5 6
产销平衡表
http://www.tju.edu.cn
第一章 线性规划销地产地
D
1
D
2
D
3
D
4
S
1
S
2
S
3
3 11 3 10
1 9 2 8
7 4 10 5
单位运价表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
D1 D2 D3 D4
S1 7
S2 3 4
S3 9
3 6 5 6
运价表
（ 1）确定初始调运方案（最小元素法）
产销平衡表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
D1 D2 D3 D4
S1 7
S2 3 1 4
S3 9
3 6 5 6
运价表产销平衡表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
D1 D2 D3 D4
S1 4 7
S2 3 1 4
S3 9
3 6 5 6
运价表产销平衡表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
D1 D2 D3 D4
S1 4 7
S2 3 1 4
S3 6 9
3 6 5 6
运价表产销平衡表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
D1 D2 D3 D4
S1 4 7
S2 3 1 4
S3 6 3 9
3 6 5 6
运价表产销平衡表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
D1 D2 D3 D4
S1 4 3 7
S2 3 1 4
S3 6 3 9
3 6 5 6
运价表产销平衡表
http://www.tju.edu.cn
第一章 线性规划
（ 1）确定初始调运方案（西北角法）
1
D
2
D
3
D
4
D
产量
3113 10
7
1928
4
7
3
1045
9
36 5 620
2
S
3
S
销量
1
S
3
4
22
6
1
D
2
D
3
D
4
D
产量
3113 10
7
1928
4
71045
9
36 5 620
2
S
3
S
销量
1
S
31[5]2
列罚数行罚数
1
1
0
2
1
0
[3]12
列罚数
6
1
0
[2]1[2]
列罚数
3
3
6
[7]
21
列罚数
5
1
2
（1 ）确定初始调运方案 Vogel法）
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 4 3 7
S2 3 1 4
S3 6 3 9
3 6 5 6
由各封闭回路可以计算各空格的检验数。
它等于其闭回路上奇数点运价与偶数点运价之负值的和产销平衡表
（ 2）判断当前方案是否为最优（闭回路法，位势法）
闭回路法
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 4 3 7
S2 3 1 4
S3 6 3 9
3 6 5 6
D1 D2 D3 D4
S1 4 3 7
S2 3 1 4
S3 6 3 9
3 6 5 6
产销平衡表 产销平衡表
D1 D2 D3 D4
S1 4 3 7
S2 3 1 4
S3 6 3 9
3 6 5 6
D1 D2 D3 D4
S1 4 3 7
S2 3 1 4
S3 6 3 9
3 6 5 6
D1 D2 D3 D4
S1 4 3 7
S2 3 1 4
S3 6 3 9
3 6 5 6
产销平衡表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
D1 D2 D3 D4
S1 4 3
S2 3 1
S3 6 3
12
10
1
1
2
1
1314343333
21231314343131
1413232424
32341413232222
3234141212
2123131111
=?+?=
=?+?+?=
=?+?=
=?+?+?=
=?+?=
=?+?=
cccc
cccccc
cccc
cccccc
cccc
cccc
σ
σ
σ
σ
σ
σ
产销平衡表运价表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1
S2
S3
12
1-1
10 12
当所有空格检验数
0≥
ij
σ
则当前方案是最优的，若尚有空格检验数小于零，
表明当前方案尚有待调整。
ij
σ
具有确切的经济意义，它表示由Ai 往Bj 增运 1单位时，引起的总运输成本的变化数。
若所有的空格检验数都大于等于零，表明任何一个空格处调运 1单位都会引起总成本的上升，这表明当前方案不能再改进，即定为最优方案。
http://www.tju.edu.cn
第一章 线性规划位势法
D1 D2 D3 D4
S1 3 10
S2 1 2
S3 4 5
D1 D2 D3 D4
S1 4 3
S2 3 1
S3 6 3
（ 1）在有数格上填上相应的运价产销平衡表运价表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 10 u1
S2 1 2 u2
S3 4 5 u3
v1 v2 v3 v4
运价表
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 10 U1 0
S2 1 2 U2 -1
S3 4 5 U3 -5
V1 V2 V3 V4
2 9 3 10
上。值，并填在相应的位置和
（有数格），依次求得，然后根据设
ji
ij1
vu
cu
ji
vu +== 0
（2）
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 2 9 (3) (10) U1 0
S2 (1) 8 (2) 9 U2 -1
S3 -3 (4) -2 (5) U3 -5
V1 V2 V3 V4
2 9 3 10
值加上括号以示区别。并将有数格位置上的应位置上，）位势和值填在表中相）表，把（计算（
j
jj
v
vv
+
++
i
ii
u
uu
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
D1 D2 D3 D4
S1 2 9 (3) (10) U1 0
S2 (1) 8 (2) 9 U2 -1
S3 -3 (4) -2 (5) U3 -5
V1 V2 V3 V4
2 9 3 10
单位运价表
（ Ui+vj）表
D1 D2 D3 D4
S1 1 2
S2 1 -1
S3 10 12
检验数表
（ 3）计算检验数表
)(
jiijij
vuc +?=σ
http://www.tju.edu.cn
第一章 线性规划调整方案,若在检验数表上有某空格的检验数为负，则应改进方案，降低成本。调整的方法是从具有负检验数的空格出发（有多个负检验数时，选择绝对值大的一个），沿它的闭回路进行调整，即在方案可行的条件下，尽量增加空格上的运量。
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 4 3 7
S2 3 1 4
S3 6 9
3 6 5 6
一般说来，调整量为闭回路上偶数顶点格上运量最小数
3
http://www.tju.edu.cn
第一章 线性规划调整后的结果为：
D1 D2 D3 D4
S1 5 2 7
S2 3 0 4
S3 6 9
3 6 5 6
1
3
http://www.tju.edu.cn
第一章 线性规划
D1 D2 D3 D4
S1 3 11 3 10
S2 1 9 2 8
S3 7 4 10 5
单位运价表
（ Ui+vj）表
D1 D2 D3 D4
S1 3 9 (3) (10) U1 0
S2 (1) 7 1 (8) U2 -2
S3 -2 (4) -2 U3 -5
V1 V2 V3 V4
9 3 10
3
(5)
D1 D2 D3 D4
S1 0 2
S2 2 1
S3 9 12
检验数表
http://www.tju.edu.cn
第一章 线性规划再计算新方案的空格检验数：
D1 D2 D3 D4
S1 0 2
S2 2 1
S3 9 12
http://www.tju.edu.cn
第一章 线性规划对于产销不平衡问题，可以增加虚设的产地或销地，将不平衡问题转化为平衡问题处理
∑∑
∑∑
==
+
+
==
=
>
m
i
n
j
ji
n
j
ji
ba
ba
11
11
.
1n
1n
m
i
b
B 其销量为：可以虚拟一销售地当产大于销时：
http://www.tju.edu.cn
第一章 线性规划
∑∑
∑∑
==
+
+
==
=
<
m
qi
i
n
j
j
n
j
ji
ab
ba
1
11
.
1m
1m
m
i
a
A 其产量为：可以虚拟一产地当产小于销时：
http://www.tju.edu.cn
第一章 线性规划一、线性整数规划问题与模型
1,线性整数规划问题实例例10 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、
可获利润以及托运受限制如下表：问两种货物各托运多少箱，可使获得利润最大？
货物 体积每箱（米
3
） 重量每箱（百斤） 利 润每箱（百元）
甲乙
5
4
2
5
20
10
限制
24 13
1.5 线性整数规划
http://www.tju.edu.cn
第一章 线性规划
≥
≤+
≤+
+=
整数
21
21
21
21
21
,
0,
1352
2445
1020
xx
xx
xx
xx
xxMaxz
http://www.tju.edu.cn
第一章 线性规划例11 投资项目选择问题现有资金总额为B。可供选择的投资项目有n
个，项目j所需投资和预期收益分别为a
j
和c
j
。
此外，由于种种原因，有三个附加条件：第一，若选择项目1，就必须同时选择项目2。反之，则不一定；第二，项目3和4中 至少选择一个；第三，项目5,6和7中恰好选择两个。
应当怎 样选择投资项目，才能使总预 期收益最大？
http://www.tju.edu.cn
第一章 线性规划
==
=++
≥+
≥
≤
=
∑
∑
=
=
n),1,2,j10
2
1
max
765
43
12
1
1
null（或
j
n
j
jj
n
j
jj
x
xxx
xx
xx
Bxa
xcz
http://www.tju.edu.cn
第一章 线性规划例 12 运动员选拔问题
4*100m混合泳接力是观众最感兴趣的游泳项目之一。现在从实例出发，研究混合泳运动员的选拔问题：
甲、乙、丙、丁是4名游泳运动员，他们各种姿势的100m游泳成绩见表，为组成一个4*100m
混合泳接力队，怎样选派运动员，方使接力队的游泳成绩最好？
http://www.tju.edu.cn
第一章 线性规划运动员 仰泳 蛙泳 蝶泳 自由泳甲乙丙丁
75.5
65.8
67.6
74.0
86.8
66.2
84.3
69.4
66.6
57.0
77.8
60.8
58.4
52.8
59.1
57.0
http://www.tju.edu.cn
第一章 线性规划
1,2,3,4)j(i,,10
)4,3,2,1(1
)4,3,2,1(1
0.578.604.690.74
1.598.773.846.67
8.520.572.668.65
4.586.668.8675.5xy min
4321
4321
44434241
34333231
24232221
14131211
==
==+++
==+++
++++
++++
++++
+++=
或
ij
iiii
jjjj
x
ixxxx
jxxx
st
xxxx
xxxx
xxxx
xxx
http://www.tju.edu.cn
第一章 线性规划例13 固定费用问题某工厂为生产某种产品，有3种不同的生产方式可供选择。设第 j种生产方式的固定成本为 k
j
，
可变成本为 c
j
。若不考虑其他约束，请建立使总成本最小的规划模型。
=
≤
≥
+++++=
10
0
)()()(
333322221111
或
j
jjj
j
y
yMx
x
xcykxcykxcykMinz
http://www.tju.edu.cn
第一章 线性规划一个徒步旅行者要在背包中选择一些最有价值的物品携带，他最多能携带115kg
的物品。现共有5件物品，分别重54kg、
35kg、57kg、46kg、19kg,其价值依次为7、5、9、6、3。问该旅行者携带那些物品，使总价值最大?
例 14 背包问题
http://www.tju.edu.cn
第一章 线性规划
=
≤++++
++++=
=
10
1151946573554
..
3695
0
1
54321
5432
或则有：
件物品不携带第件物品携带第解：设
j
j
x
xxxxx
ts
xxxx
x
1
7xzmax
j
j
http://www.tju.edu.cn
第一章 线性规划
2,线性整数规划的一般形式：
=≥
==
=
∑
∑
=
=
为整数（部分或全部）
j
j
n
j
ijij
n
j
jj
x
njx
mibxa
xcz
,,2,10
,,2,1
max
1
1
null
null
http://www.tju.edu.cn
第一章 线性规划整数规划一般可以分为三类：
1）纯整数规划：全部决策变量都限定取整数；
2）混合整数规划：部分决策变量为整数，即规划中变量一部分取整数，其余部分是连续变量；
3）0-1规划，不仅限定决策变量取整数，而且只允许取0和1两个值。
http://www.tju.edu.cn
第一章 线性规划
3,线性整数规划问题解的特点松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题
http://www.tju.edu.cn
第一章 线性规划例 15
≥
≤+
≤+
+=
整数
21
21
21
21
21
,
0,
1352
2445
1020
xx
xx
xx
xx
xxMaxz
0
1x
2x
4.8
http://www.tju.edu.cn
第一章 线性规划最优解不一定在顶点上达到最优解不一定是放松问题最优解的邻近整数解整数可行解远多余于顶点，枚举法不可取
http://www.tju.edu.cn
第一章 线性规划二、线性整数规划的分枝定界法分枝定界法：设有最大化的整数规划问题A,与它相应的线性规划问题为B,求解问题B,若B 的最优解不符合A 的整数条件，则 B的最优值一定为A 最优值Z
*
的上界，而A
的任意可行解的目标函数值将是Z
*
的下界，分支定界法就是将B 的可行域分成子区域（称为分支方法）
的方法，通过减小最优值的上界和下界最终得到最优值分支边界
http://www.tju.edu.cn
第一章 线性规划
≥
≤+
≤+
+=
整数
21
21
21
21
21
,
0,
70207
5679
9040
xx
xx
xx
xx
xxMaxz
例 16
0
1x
2x
4.81
1.82
3560
356
*
0
≤≤
=
Z
Z
http://www.tju.edu.cn
第一章 线性规划对原问题增加两个约束条件
5,4
11
≥≤ xx
0
1x
2x
4.81
1.82
问题 B
1
问题 B
2
问题 B
1
问题 B
2
Z
1
=349
X
1
=4
X
2
=2.1
Z
2
=341
X
1
=5
X
2
=1.57
3490
*
≤≤ Z
http://www.tju.edu.cn
第一章 线性规划对 B
1
问题增加两个约束条件
2,3
22
≤≥ xx
问题 B
3
问题 B
4
Z
1
=340
X
1
=4
X
2
=2
Z
2
=327
X
1
=1.42
X
2
=3
341340
*
≤≤ Z
http://www.tju.edu.cn
第一章 线性规划对 B
2
问题增加两个约束条件
1,2
22
≤≥ xx
问题 B
5
问题 B
6
Z
1
=308
X
1
=5.44
X
2
=1
无可行解
340
*
=Z
问题 B
Z
0
=356
X
1
=4.81
X
2
=1.82
问题 B
1
Z
1
=349
X
1
=4
X
2
=2.1
问题 B
3
Z
3
=340
X
1
=4
X
2
=2
问题 B
4
Z
4
=327
X
1
=1.42
X
2
=3
问题 B
5
Z
5
=308
X
1
=5.44
X
2
=1
问题 B
6
无可行解问题 B
2
Z
2
=341
X
1
=5
X
2
=1.57
4
1
≤x 5
1
≥x
3560
356
*
0
≤≤
=
Z
Z
2
2
≤x
3
2
≥x
2
2
≤x
3
2
≥x
××
×
3490
*
≤≤ Z
341340
*
≤≤ Z
340
*
=Z
http://www.tju.edu.cn
第一章 线性规划分枝定界法求解问题的步骤：
将要求解的整数规划问题称为问题 A，将其松弛问题称为问题 B，若
（ 1） B没有可行解，这时 A也没有可行解，停止
（ 2） B有最优解，并符合问题 A的整数条件,B的最优解即为 A的最优解
（ 3） B有最优解，但不符合 A的整数条件，记它目标函数值为最优值上界，观察一下界值。
ZZ
Z
_
*
_
≤≤
http://www.tju.edu.cn
第一章 线性规划第一步：分枝，在Ｂ
中选择一个不符合整数条件的变量 xj，其值为 bj，［ bj］表示小于 bj的最大整数，
构造两个约束条件。
1][
][
+≥
≤
jj
jj
bx
bx
将此两个约束条件加入 B，在不考虑整数条件的情况下，求解两个后继问题 B
1
和 B
2
http://www.tju.edu.cn
第一章 线性规划定界，以每个后继问题为一分枝标明求解结果，与其他问题解的结果中，找出目标函数最大者作为新的上界，从已符合整数条件的各分支中，找出目标函数值最大者作为新的下界，
若无作用，下界仍为零。
第二步：比较与剪枝，各分枝的最优目标函数中若有小于下界者，则剪掉这枝，此后无需再考虑。若大于下界，且不符合整数条件，则重复第一步，直至找到最优解为止。
http://www.tju.edu.cn
第一章 线性规划三、线性整数规划的割平面法算法思想由放松问题的可行域向整数规划的可行域逼近方法 ——利用超平面切除要求整数解保留不符合整数要求的线性规划最优解被切除
http://www.tju.edu.cn
第一章 线性规划例 17：求解
≥
≤+
≤+?
+=
整数
21
21
21
21
21
,
0,
43
1
xx
xx
xx
xx
xxMaxz
0
1x
2x
4
10
max,
4
7
,
4
3
21
=== Zxx
A
D
C
http://www.tju.edu.cn
第一章 线性规划
0
x
4
0
x
3
1
x
2
1
x
1
B
-1
b
C
B
X
B
x
3
x
4
0
0
1
4
-1
3
1
1
1
0
0
1
1 00
单纯形表,
1
x
1
x
2
7/4 0 1 3/4 1/4
σ
3/4 1 0 -1/4 1/4
0 0 -1/2 -1/2
1
1
http://www.tju.edu.cn
第一章 线性规划由终表得到如下关系：
将系数和常数项分解成整数和真分数之和，移项变为：
4
7
4
1
4
3
4
3
4
1
4
1
432
431
=++
=+?
xxx
xxx
)
4
1
4
3
(
4
3
1
)
4
1
4
3
(
4
3
432
4331
xxx
xxxx
+?=?
+?=?
http://www.tju.edu.cn
第一章 线性规划整数条件可由下式代替
0)
4
1
4
3
(
4
3
43
≤+? xx
这就得到了一个切割方程，代入单纯形表终表中，利用对偶单纯形法求解即可
http://www.tju.edu.cn
第一章 线性规划
0
1
1
0
x
4
0
x
3
1
x
2
1
x
1
B
-1
b
C
B
X
B
单纯形表,
x
1
x
2
7/4 0 1 3/4 1/4
σ
3/4 1 0 -1/4 1/4
0 0 -1/2 -1/2
0
x
5
x
5
-3
00[-3] -1
0
0
1
0
0
1
1
x
1
x
2
10100
11001/3
0 0 0 -1/3
x
3
1
0011/3
1/4
-1/12
-1/3
-1/6
解题完毕
http://www.tju.edu.cn
第一章 线性规划割平面法的步骤：
1,令 x
i
是相应线性规划最优解中为分数值的基变量，由单纯形表的终表得到：
2、将b
i
和a
ij
都分解成整数部分[b
i
]与非负真分数f之和，[b
i
]为不超过b的最大整数
∑
=+
ijiji
bxax
10][
10,][
<≤+=
<<+=
ikijijij
iiii
ffaa
ffbb
若 b
i
=2.35,则[b
i
]=2,f=0.35
若 b
i
=-0.45,则 [b
i
]=-1,f=0.55
http://www.tju.edu.cn
第一章 线性规划
∑∑
=?+
kk
kikiikiki
xffNxNx
提出切割方程
0≤?
∑
k
kiki
xff
http://www.tju.edu.cn
第一章 线性规划算法步骤求放松问题的最优基可行解判断是否为整数解是停止得到最优解否在单纯性表中加入一列利用对偶单纯形算法求最优解
http://www.tju.edu.cn
第一章 线性规划四、0-1型整数规划问题的求解方法：隐枚举法枚举法：将全部解列出，验证约束，比较目标隐枚举法：找出一个可行解，祘其目标。由此确定一个过滤条件，再枚举
http://www.tju.edu.cn
第一章 线性规划
==
≤+
≤+
≤++
≤?+
+?=
3,2,110
64
3
44
22
523
32
21
321
321
321
ix
xx
xx
xxx
xxx
xxxMaxz
i
，或点约束
？
Z
01234
000
001
010
011
100
101
110
111
0
5
-2
3
3
8
1
6
-1
0
1
2
0
1
1
1
5
8
例18
http://www.tju.edu.cn
第一章 线性规划例19 指派问题有一份中文说明书，需译成英、日、德、
俄四种文字。分别记为E、J、G、R，有甲、
乙、丙、丁四人，他们将中文说明书翻译成不同语种说明书所需时间如表所示，问应当如何指派工作，使所需总时间最少。
http://www.tju.edu.cn
第一章 线性规划人员
EJGR
甲乙丙丁
2
10
9
7
15
4
14
8
13
14
16
11
4
15
13
9
http://www.tju.edu.cn
第一章 线性规划
=
==
==
=
∑
∑
∑∑
=
=
==
10
,,2,11
,,2,11
..
min
1
1
11
或
ij
n
j
ij
n
i
ij
n
i
n
j
ijij
x
nix
njx
ts
xcZ
null
null
指派问题最优解具有如下性质：
若从指派问题的系数矩阵C的某行
（或某列）个元素分别减去一个常数k，得到一个新矩阵C
’
，则以C
和C ’为系数矩阵的两个指派问题有相同的最优解。
http://www.tju.edu.cn
第一章 线性规划指派问题的匈牙利解法步骤1,变换系数矩阵。先对各行元素分别减去本行中最小元素，再对各列元素分别减去本列中最小元素。
步骤2,在变换后的系数矩阵中确定独立零元素，若独立零元素为n个，得到最优解，否则，作能覆盖所有零元素的最小直线数目的直线集合，转步骤3
步骤3,继续变换系数矩阵，在未被覆盖的元素中找出一个最小元素，未被覆盖的元素所在行或列中各元素都减去这一最小元素，从而出现零元素。
http://www.tju.edu.cn
第一章 线性规划例
=
6101296
1061476
781296
10141797
1215784
c
=
06630
40810
12630
37820
811340
c
-4
-7
-6
-6
-6
=
06320
40500
12320
37510
811030
c
-1 -3
http://www.tju.edu.cn
第一章 线性规划
=
]0[632
45]0[
1232
3751]0[
811]0[3
φ
φφ
φ
φ
c
√
√
√
http://www.tju.edu.cn
第一章 线性规划
=?
=
04321
40501
01210
26600
811031
04320
40500
01211
26601
811030
'''
cc
[ ]
[ ]
[ ]
[ ]
[ ]
http://www.tju.edu.cn
第一章 线性规划
=
10000
01000
00001
00010
00100
'
X
