当前位置:首页 >> 其它课程 >>

运筹学基础教程(第二版)教学课件


返回总目录

运筹学基础教程
(第二版) 制作人:黄桐城
(上海交通大学安泰经济与管理学院)

版权所有 侵权必究 1

返回总目录

概述
运筹学(Operations Research)是用数学方法研究各种系统的最

优化问题,运筹学强调发挥现有系统的效能,应用数学模型求得合理利
用各种资源的最佳方案,为决策者提供科学决策的依据。 运筹学的内容有数学规划、运输问题、图与网络分析、排队论、存 储论、决策论和对策论等,其中数学规划又包括线性规划、整数规划、 非线性规划、目标规划和动态规划等, 虽然运筹学包括的内容较多,但是它们有两个共同的特点:一是以 全局最优作为问题的基本出发点;二是通过建立数学模型,运用优化技

术求得系统最合理的运营方案。由于各种系统的运营机制和性能不尽相
同,它们的数学模型也各不相同,从而形成了运筹学的不同分支。
2

返回总目录
所以可对运筹学做如下概括: 1.运筹学的研究对象是各种系统。 2.运筹学的研究目的是实现系统的最优化,求得合理利用各种资 源的最优方案。 3.运筹学的研究方法是运用数学语言来描述实际系统,通过建立 数学模型和优化技术求得系统运营的最优解。 4.运筹学的研究动机是为决策者提供科学决策的依据。 运筹学在工业、农业、商业、物流、经济计划、人力资源、军事 等行业都有着非常广泛的应用。有人曾对世界上500家著名的企业集 团或跨国公司进行过调查,发现其中95%曾使用过线性规划,75%使用 过运输模型,90%使用过网络计划技术,90%使用过存储模型,43%使 用过动态规划。 由此可见运筹学是一门应用性很强的学科。特别是随着计算机技 术的不断发展,计算机成为运筹学最强有力的运算工具,运筹学越来 越显示出其广泛的使用价值。
3

返回总目录
运筹学这一名词最早出现于1938年。当时英,美等国盟军在与德 国的战争中遇到了许多错综复杂的战略和战术问题难以解决,比如: 1.防空雷达的布臵问题:英美等国为了对付德国的空袭配备了先 进的雷达作为防空系统的一部分,但是由于雷达系统的布臵不甚合理, 通过防空演习发现实际效果并不理想。 2.护航舰队的编队问题:英美等国需要对本国的商船队配备护航 舰队,以防止德国潜艇的攻击,这里有一个如何合理编队才能使商船 队一旦遭受德国潜艇攻击时损失最少的问题。 为了应付上述各种复杂问题,英美等国逐批召集不同专业背景的 科学家,在三军组织了各种研究小组,研究的问题都是军事性质的, 在英国称为“Operational Research”,其他英语国家称为 “Operations Research”,意思是军事行动研究。这些研究小组运用 系统优化的思想,应用数学技术分析军事问题,取得了非常理想的效 果。
4

返回总目录
二战以后,在军事运筹小组中工作过的一部分科学家开始转入 民用部门,他们把对军事系统最优化的研究成果拓展到各种民用系 统的研究上。 1947年美国数学家G.B.Dantzig在研究美国空军资源配臵时,提 出了求解线性规划的有效方法——单纯形法。20世纪50年代初,应 用计算机求解线性规划获得成功。 至50年代末,一些工业先进国家的大型企业已经较普遍地使用 运筹学方法解决在生产经营管理中遇到的实际问题,并取得了良好 的效果,至60年代中期,运筹学开始应用于一些服务性行业和公用 事业。 同时很多国家成立了运筹学研究学会,一些大学的相关专业也 陆续设臵了运筹学的有关课程。专门发表运筹学研究论文的刊物开 始出版,运筹学的理论研究日趋成熟,在实际应用上则日趋广泛。
5

返回总目录
我国运筹学的研究始于20世纪50年代中期,当时由钱学森教授将运 筹学从西方国家引入我国,以华罗庚教授为代表的一大批科学家在有关 企事业单位积极推广和普及运筹学方法,在建筑、纺织、交通运输、水 利建设和邮电等行业都有不少应用。关于邮递员投递的最佳路线问题就 是由我国年轻的数学家管梅谷于1962年首先提出的,在国际上统称为中 国邮递员问题。我国运筹学的理论和应用研究在较短时间内赶上了世界 水平。 如今对运筹学的研究大致在三个领域发展:运筹学应用、运筹科学 和运筹数学。一般的共识是,运筹学的研究不能忘记其原有的应用性强 的特色,必须强调多学科的交叉联系和解决实际问题的研究。我们面临 的很多系统通常涉及到大量的经济、技术、社会、政治和心理等综合因 素,这些综合因素受到人的影响和干预,存在非结构性的复杂问题,仅 用数学模型是很难加以描述和解决的。总之随着社会的不断发展和进步, 实践将对运筹学提出更新更多的研究课题,运筹学正处于不断发展,不 断进步的时期。
6

返回总目录

目 录
第1章 第2章 第3章 第4章 第5章 第6章 第7章 第8章 线性规划的基本概念 单纯形法 对偶规划与灵敏度分析 运输问题 图与网络分析 排队论 存贮论 决策分析
7

返回总目录

第1章 线性规划的基本概念
? ? ? ? ? 线性规划问题及其数学模型 线性规划的图解法 线性规划的标准形式 标准型线性规划的解的概念 线性规划的基本理论

8

返回总目录

?线性规划问题及其数学模型
? 问题的提出:
在生产管理的经营活动中,通常需要对“有限的资源”寻求 “最佳”的利用或分配方式。
? ?

有限资源:劳动力、原材料、设备或资金等 最佳:有一个标准或目标,使利润达到最大或成本达到最小。

有限资源的合理配臵有两类问题: ? 如何合理的使用有限的资源,使生产经营的效益达到最大; ? 在生产或经营的任务确定的条件下,合理的组织生产,安排经 营活动,使所消耗的资源数最少。
9

返回总目录

与规划问题有关的数学模型总有两部分组成: 约束条件:反映了有限资源对生产经营活动的种种约束, 或者生产经营必须完成的任务;
?

目标函数:反映生产经营者在有限资源条件下希望达到 的生产或经营的目标。
?

10

返回总目录

例1

某制药厂生产甲、乙两种药品,生产这两种药品要消耗某种维生

素。生产每吨药品所需要的维生素量,所占用的设备时间,以及该厂每

周可提供的资源总量如下表所示:
每吨产品的消耗
甲 维生素(公斤) 设备(台班) 30 5 乙 20 1 160 15

每周资源总量

已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元。但根据
市场需求调查的结果,甲药品每周的产量不应超过4吨。问该厂应如何 安排两种药品的产量才能使每周获得的利润最大?
11

返回总目录
每吨产品的消耗 甲 维生素(公斤) 设备(台班) 单位利润(万元) 30 5 5 乙 20 1 2 160 15 每周资源总量

定义x1 为生产甲种药品的计划产量数,x2 为生产乙种药品的计划产量数。
目标: 使总利润 约束: 每周资源总量的限制, Z=5x1+2x2 极大化 30x1+20x2≤160 5x1+ x2 ≤15 甲种药品每周产量不应超过4吨的限制 x1≤4 计划生产数不可能是负数, x1≥0 x2≥0
12

返回总目录
每吨产品的消耗
甲 维生素(公斤) 设备(台班) 单位利润(万元) 30 5 5 乙 20 1 2 160 15

每周资源总量

数学模型为 s.t. (subject to) (such that)

maxZ=5x1 +2x 2 ?30x1 ? 20x 2 ? 160 ?5x ? x ? 15 ? 1 2 ? ? x1 ? 4 ? x1 ? 0, x 2 ? 0 ?

? 这是一个如何合理的使用有限的资源,使生产经营的效益达到最大 的数学规划问题。 ? 在满足一组约束条件的限制下,寻求决策变量x1,x2的决策值,使目 标函数达到最大值。
13

返回总目录
例2 某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料

混合配制而成的特种产品。已知甲、乙两种原料都含有A、B、C三种 化学成分,两种原料分别所含三种化学成分的百分比含量,以及按合 同规定的产品中三种化学成分的最低含量如下表所示:
原料 化学成分 化学成分含量(%) 产品中化学成分的最低含量 (%)

甲 12

乙 3

A

4

B
C

2
3

3
15

2
5

已知甲、乙两种原料的成本分别是每公斤3元和2元,厂方希望

总成本达到最小,问如何配臵该产品?
14

返回总目录
原料
化学成分

化学成分含量(%)
甲 12 乙 3

产品中化学成分的最低含量 (%)
4

A

B
C 单位成本(元)

2
3 3

3
15 2

2
5

定义x1,x2分别为每公斤产品中甲,乙两种原料的数量, 目标:使总成本 约束:配料平衡条件, Z=3x1+2x2 极小化 x1+x2=1 12x1+3x2≥4 2x1+3x2≥2

产品中A、B、C三种化学成分的最低含量

3x1+15x2≥5
非负性条件 x1≥0,x2≥0
15

返回总目录
原料
化学成分 A B C 单位成本(元)

化学成分含量(%)
甲 12 2 3 3 乙 3 3 15 2

产品中化学成分的最低含量(%)
4 2 5

minZ=3x1 +2x 2 ? x1 ? x 2 ? 1 ?12x ? 3x ? 4 2 ? 1 s.t. ? ?2x1 ? 3x 2 ? 2 ?3x ? 15x ? 0 2 ? 1 ? x1 ? 0,x 2 ? 0 ? ? 这是一个原料配制问题,是在生产任务确定的条件下,合理的组织 生产,使所消耗的资源数最少的数学规划问题。 ? 满足一组约束条件的同时,寻求变量x1和x2的值使目标函数取得最小 值。
16

数学模型:

返回总目录
例3 某铁器加工厂要制作100套钢架,每套要用长为2.9米、2.1米

和1.5米的圆钢各一根。已知原料长为7.4米,问应如何下料,可使 材料最省? ? 分析:在长度确定的原料上截取三种不同规格的圆钢,可以归纳 出8种不同的下料方案:
圆钢(米) Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ Ⅶ Ⅶ

2.9
2.1 1.5 料头(米)

1
0 3 0

2
0 1 0.1

0
2 2 0.2

1
2 0 0.3

0
1 3 0.8

1
1 1 0.9

0
3 0 1.1

0
0 4 1.4

问题归纳为如何混合使用这8种不同的下料方案,来制造100

套钢架,且要使剩余的料头总长为最短。
17

返回总目录
圆钢(米) 2.9 2.1 1.5 料头(米) Ⅰ 1 0 3 0 Ⅱ 2 0 1 0.1 Ⅲ 0 2 2 0.2 Ⅳ 1 2 0 0.3 Ⅴ 0 1 3 0.8 Ⅵ 1 1 1 0.9 Ⅶ 0 3 0 1.1 Ⅶ 0 0 4 1.4

设xj表示用第j种下料方案下料的原料根数,j=1,2,…,8,
目标:使料头总长度 Z=0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8

极小化
约束:三种规格圆钢根数 x1+2x2 +x4 +x6 =100 =100 2x3+2x4 +x5+x6+3x7

3x1+x2+2x3
非负取整条件

+3x5+x6

+4x8=100
18

xj≥0 (j=1,2,…,8)且取整数

返回总目录
圆钢(米)
2.9 2.1 1.5 料头(米)


1 0 3 0


2 0 1 0.1


0 2 2 0.2


1 2 0 0.3


0 1 3 0.8


1 1 1 0.9


0 3 0 1.1


0 0 4 1.4

minZ=0.1x 2 +0.2x 3 +0.3x 4 +0.8x 5 +0.9x 6 +1.1x 7 +1.4x 8
数学模型

x4 ? x6 ? 100 ? x1 ? 2x 2 ? ? 2x 3 ? 2x 4 ? x 5 ? x 6 ? 3x 7 ? 100 ? s.t. ? 3x 5 ? x 6 ? 4x 8 ? 100 ?3x1 ? x 2 ? 2x 3 ? ? x j ? 0,j ? 1,2 ?8 , 且为整数 ?

? 这是一个下料问题,是在生产任务确定的条件下,合理的组织生产, 使所消耗的资源数最少的数学规划问题。 ? 满足一组约束条件的同时,寻求变量x1至x8的值,使目标函数取得最 小值。
19

返回总目录

? 线性规划的一般数学模型
线性规划模型的特征: (1)用一组决策变量x1,x2,…xn表示某一方案,且在一般情况下, 变量的取值是非负的。 (2)有一个目标函数,这个目标函数可表示为这组变量的线性函数。 (3)存在若干个约束条件,约束条件用决策变量的线性等式或线 性不等式来表达。 (4)要求目标函数实现极大化(max)或极小化(min)。 ? 满足上述4个特征的规划问题称为线性规划问题

20

返回总目录
线性规划的模型的一般形式: 目标函数 max(min)Z=c1 x1 +c2 x2 +?? +cn xn

? a11x1 ? a12 x 2 ???? a1n x n ? ( ? , ? )b1 ? 满足约束条件 a 21x1 ? a 22 x 2 ???? a 2n x n ? ( ? , ? )b 2 ? ? ? ??????????????? ? a x ? a x ???? a x ? ( ? , ? )b mn n m ? m1 1 m2 2 ? x1 ,x 2 ,? x n ? 0 ?
通常称 x1 ,x 2 ,? , x n 为决策变量,c1 ,c2 ,? , cn 为价值系数, a11 ,a12 ,? , a mn 为消耗系数, b1 ,b2 ,? , bm 为资源限制系数。

21

返回总目录

?线性规划的图解法
适用于求解两个变量的线性规划问题

? 图解法的基本步骤
例4 利用例1说明图解法的主要步骤。 例1的数学模型为

maxZ ? 5x1 ? 2x 2 ?30x1 ? 2 0x 2 ? 160 ? 5x ? x ? 15 ? 1 2 ? ?4 ? x1 ? x1 ? 0, x 2 ? 0 ?
22

s.t.

返回总目录
x2 5x1+x2=15 10 C x1=4

maxZ ? 5x1 ? 2x 2 ?30x1 ? 2 0x 2 ? 160 ? 5x ? x ? 15 ? 1 2 ? ?4 ? x1 ? x1 ? 0, x 2 ? 0 ?
? ?Z ?Z ? ?Z= ? , ? =(5,) 2 ? ?x1 ?x 2 ?

B( 2, 5) 5 5x1+2x2=5 ▽Z O 1 A 30x1+20x2=160

5

10

15

x1
23

返回总目录

线性规划图解法的基本步骤:
(1)建立以x1,x2为坐标轴的直角坐标系,画出线性规划 问题的可行域。 (2)求目标函数 Z=C1x1+C2x2 的梯度▽Z =(c1,c2)。 (3)任取等值线 C1x1+C2x2=Z0, 沿梯度▽Z正方向平移, (若是极小化问题,则沿负梯度方向-▽Z平移),

求等直线将离未离可行域时与可行域的交点。
(4)若交点存在,则该点坐标就是最优解。* X

24

返回总目录

? 图解法的几种可能结果
(1)有唯一最优解,如例1。 (2)有无穷多最优解 如例1中的目标函数设为 maxZ=10x1+2x2

则目标函数等值线10x1+2x2=Z 与第二约束 5x1+x2≤15
的边界线平行。将等值线沿梯度▽Z =(10,2)正方向平移 至B点时与可行域OABC的整条边界线AB重合。

这表明线段AB上的每一点都使目标函数取得同样的最大值,
因而都是最优解。

25

返回总目录
x2 5x1+x2=15 10 C x1=4

maxZ ? 10 x1 ? 2x 2

? ?Z ?Z ? ?Z= ? , ? =(10,) 2 ? ?x1 ?x 2 ?

5 10x1+2x2=5 ▽Z O 1

B(2,5)

30x1+20x2=160

A

5

10

15

x1
26

返回总目录
(3) 无界解(或称无最优解)
无界解是指线性规划问题的最优解无界。 若是极大化问题,则可使目标函数值Z→+∝, 极小化问题 则可使目标函数值Z→-∝, 有无界解的线性规划问题的可行域通常是无界区域,但反之 则不必然。

例5

试用图解法求解下列线性规划问题

minZ ? ?3x1 ? 2x 2

st. ?-2x1 ? x 2 ? 2

? ? x1 -3x 2 ? 3 ? x ? 0,x ? 0 2 ? 1
27

返回总目录

minZ ? ?3x1 ? 2x 2
x2 -2x1+x2=2

4
3

?-2x1 ? x 2 ? 2 ? ? x1 -3x 2 ? 3 ? x ? 0,x ? 0 2 ? 1
? ?Z ?Z ? ?Z= ? , ? =(-3,- 2) ? ?x1 ?x 2 ?

2
-▽Z=(3,2)

x1-3x2=3

-1 O

2 -1 O

3

4

x1

28

返回总目录

(4)无可行解 某些线性规划问题的可行域是空集,即不存在满足所有约束条 件的点,这时问题无可行解,当然更谈不上最优解了。 在实际中出现这种情况可以认为资源条件无法满足人们的要求, 即不存在可行方案。

29

返回总目录

?线性规划的标准形式
? 标准线性规划模型
线性规划问题的标准形式:

maxZ=c1x1 +c 2 x 2 + ?? +c n x n

(1.1)

s.t

? a11x1 +a12 x 2 + ?? +a1n x n =b1 ? a x +a x + ?? +a x =b 2n n 2 ? 21 1 22 2 ? ? ???? ? ?a m1x1 +a m2 x 2 + ?? +a mn x n =b m ? x ,x ,? x ? 0 ? 1 2 n

(1.2)

(1.3)

其中式(1.1)为目标函数,式(1.2)为约束条件,式(1.3)为非负条 件, 为称呼方便,有时也将式(1.3) 称为约束条件。
30

返回总目录
?紧凑格式:

maxZ= ? C j x j
? n ?? a ij x j =b i , i=1,2, ? ,m ? j=1 ? x ? 0, j=1,2,? ,n ? j
j=1

n

s.t.

?向量格式:

maxZ=CX
? n ?? Pj x j =b ? j=1 ? x ? 0, j=1,2, ? ,n ? j
T
T

s.t.

其中 C=(c1 ,c2 ,?,cn ) 称为价值向量, X=(x1 ,x 2 ,? , x n ) 为决
策变量向量, Pj =(a1j ,a 2j ,?, a mj ) 为决策变量xj所对应的消耗系数 向量,b=(b1 ,b 2 ,? , b m ) 为资源向量。
31
T

返回总目录
?矩阵格式:

maxZ=CX ? AX=b ? ?X ? 0

其中

? a11 a12 ? ? a 21 a 22 A= ? ... ... ? ?a ? m1 a m2

... a1n ? ? ... a 2n ? ... ... ? ? ... a mn ? ?

为m×n阶矩阵

C=(c1 ,c2 ,?,cn ) 为价值向量,

X=(x1 ,x 2 ,?, x n )T 为决策变量向量, b=(b1 ,b 2 ,? , b m )T 为资源向量。
32

返回总目录

?非标准形式线性规划问题的标准化
(1)极大化与极小化 : n 若 minZ= ? C j x j ,令 Z' = -Z ,则有
j=1 n

maxZ' =max( -Z)= -maxZ= -? C j x j
j=1
j=1

n

原目标函数 minZ ? maxZ' = -? C j x j 。 (2) 线性不等式与线性等式:

?a x
ij j=1

n

j

? bi ?

? a x +x
ij j j=1

n

n+i

=bi

其中 x n+i 为非负松弛变量,

?a
j=1

n

kj

x j ? bk ?

?a
j=1

n

kj

x j - x n+k =b k
33

其中 x n+k 为非负剩余变量。

返回总目录
(3) 非负变量与符号不受限制的变量:

若 xi的符号不受限制,则可引进非负变量xi1,xi2,令 xi = xi1-xi2,这样就可以使线性规划里所有的变量都转化为有非负限 制的变量。
例6 将下述线性规划问题化为标准型

minZ=-x1 +2x 2 -3x3 ? x1 ? x 2 ? x 3 ? 7 ? x -x ? x ? 2 ? ? 1 2 3 ? ?3x1 -x 2 -2x3 ? 5 ? x1 ? 0,x 2 ? 0,x3 符号不受限制 ?
令 x 3 =x 4 -x 5 ,其中 x 4 ? 0, x 5 ? 0.

maxZ' = x1 -2x 2 +3x4 -3x5 ? x1 ? x 2 ? x 4 -x 5 ? x 6 =7 ? x -x ? x -x -x7 =2 ? 1 2 4 5 ? ?5 ?3x1 -x 2 -2x 4 +2x5 ? x1 ,x 2 ,x 4 ,x 5 ,x 6 ,x 7 ? 0 ?

解:令 Z' = -Z ,可将目标函数化为max型,
34

返回总目录

?标准型线性规划的解的概念
考虑一个标准的线性规划问题:

maxZ ? CX
s.t

(1.4) (1.5) (1.6)

? AX ? b ? ? X?0

其中C为n维行向量, X是n维列向量, b是m维列向量,

A是m×n阶矩阵,假定满足m≤n,且R(A)=m,
35

返回总目录

maxZ ? CX (1.4)
线性规划问题解的概念:

?AX ? b ? ? X?0

(1.5) (1.6)

(1) 可行解。满足约束条件(1.5)、(1.6)的解 X=(x1 ,x 2 ,? , x n )T 称为线性规划问题的可行解。 可行解集 D= ?X / AX=b ,X ? 0 ? 称为线性规划问题的可行域。 (2) 最优解。使目标函数(1.4)达到最优值的的可行解称为最优解,

最优解常用 X*表示。
(3) 基。若B是A中m×m阶非奇异矩阵,即|B|≠0,则称B是线性规

划问题的一个基。
36

返回总目录
若B是线性规划问题的一个基,那么B一定是由m个线性无关的列 向量组成,不失一般性,可设

? a11 a12 ? ? a 21 a 22 B= ? ... ... ? ?a ? m1 a m2


... a1m ? ? ... a 2m ? =(P1 ,P2 ,?, Pm ) ... ... ? ? ... a mm ? ?

p j =(a1j ,a 2j ,? a mj ), (j=1,2,? m) 为基向量,

与基向量 Pj 相对应的变量 x j , (j=1,2,? m) 称为基变量。

Cm ? 一个线性规划的基通常不是唯一的,但是基的个数也不会超过 n
个。一旦线性规划的基确定了,那么相应的基向量、基变量和非 基变量也就确定了。
37

返回总目录
(4) 基本解。设B是线性规划的一个基,若令n-m个非基变量等于0,则 所得的方程组AX=b的解称为线性规划问题的一个基本解(简称基解)。

? 有一个基就可以求得一个基本解。
? 由基的有限性可知,基本解的个数也不会超过C m 个。 n ? 由于基本解中的非零分量可能是负数,所以基本解不一定是可行的。 (5) 基本可行解。满足非负条件的基本解称为基本可行解 (简称基可行解)。与基本可行解对应的基成为可行基。 ? 基本可行解的非零向量的个数小于等于m,并且都是非负的。 ? 由于基本可行解的数目一般少于基本解的数目,因此可行基 的数目也要少于基的数目。 ? 当基本可行解中有一个或多个基变量是取零值时,称此解为

退化的基本可行解。
38

返回总目录

线性规划问题各种解的关系可用文氏图表示:

可 行 解

基本 可行 解

基 本 解

39

返回总目录
例7 求下列约束方程所对应的线性规划的所有基本解,基本可行解。

? x1 ? 2x 2 ? 8 ? s.t ? x 2 ? 2 ? x ,x ? 0 ? 1 2
解:化为标准形式

?8 ? x1 ? 2x 2 ? x 3 ? ? x2 ? x4 ? 2 ? ? x ,x ,x ,x ? 0 ? 1 2 3 4

?8? ?1 2 1 0 ? A= ? ? =(P1 ,P2 ,P3 ,P4 ) 为2×4阶矩阵。 b= ? 2 ? ? ? ? 0 1 0 1? 2 且R(A)=2,所以该线性规划基的个数≤C 4 =6个
?1 2? 取 B1 =(P1 ,P2 ) ? ? ? , x1 ,x 2 为基变量, ?0 1? ? x1 ? 2x 2 ? 8 若令非基变量 x 3 =x 4 ? 0 , 约束方程组为 ?

?

x2 ? 2
40

可得对应的基本解 X 1 ? (4, 2, 0, 0)T 是一个基本可行解。

返回总目录
?1 2 1 0 ? A= ? ? =(P1 ,P2 ,P3 ,P4 ) ? 0 1 0 1?

?8? b= ? ? ? 2?

按相同步骤,可求得线性规划其他4个基: T 对应基本解 X 2 =(8,0,0,2) ?1 0?

B2 =(P1 ,P4 ) ? ? ? 0 1? ?

是一个基本可行解。 对应基本解 X 3 =(0,2,4,0)T

?2 1? B3 =(P2 ,P3 ) ? ? ? 1 0? ? ? 2 0? B4 =(P2 ,P4 ) ? ? ? 1 1? ? ?1 B5 =(P3 ,P4 ) ? ? ?0 0? ? 1?

是一个基本可行解。
对应基本解 X 4 =(0,4,0,-2)T 不是一个基本可行解。 对应基本解 X 5 =(0,0,8,2)T 是一个基本可行解。
41

x1 ? 2 x2 ? 8

返回总目录
若利用图解法画出线性规划的可行域,如图,

D 4

? x1 ? 2x 2 ? 8 ? ?x 2 ? 2 ? x ,x ? 0 ? 1 2

x1 +2x 2 =8
B

C

x 2 =2
A

O

4

8

X1 =(4,2,0,0) ? B, X 2 =(8,0,0,2) ? A, X 3 =(0,2,4,0) ? C X 4 =(0,4,0,-2) ? D, X5 =(0,0,8,2) ? O.
42

返回总目录

?线性规划的基本理论
由图解法的步骤,可以从几何的角度得出以下两个 结论: (1)线性规划问题的可行域是一个有界或无界的凸多边 形,其顶点个数是有限个。

(2)若线性规划问题有最优解,那么最优解一定可在可
行域的某个顶点上找到。

43

返回总目录

?几个基本概念
(1)凸集:设k是n维欧式空间的一个点集,若任意两点 X(1)∈k, X(2)∈k的连线上的一切点αX(1)+ (1-α)X(2)∈k ( 0<α<1),则称k为凸集。

? 连接几何形体中任意两点的线段仍完全在该几何形体之中。 ? 有限个凸集的交集仍然是凸集。
44

返回总目录

(2)凸组合:设X(1),X(2),…,X(k)是n维欧式空间中的k个点,

若存在μ1, μ2,…, μk满足0≤μi≤1,( i=1,2,…,k), ? u i =1
使 X=μ1X(1)+μ2 X(2)+…μk X(k),
i=1

k

则称X为X(1),X(2),…,X(k)的凸组合。 ? 凸集k中任意两点X(1) ,X(2) 连线上的任一点X都是X(1) 与X(2) 的 一个凸组合。 (3)顶点:设k为凸集,X∈k,若X不能用X(1)∈k,X(2)∈k两点的 一个凸组合表示为X=αX(1)+ (1-α)X(2),其中0<α<1 ,则称X为k 的一个顶点。
45

返回总目录

? 线性规划的基本定理
定理1 若线性规划问题存在可行域,则其可行域
D= ?X / AX=b ,X ? 0 ?

是一个凸集。

证明:为了证明满足AX=b,X≥0的所有点(可行解)组成的几何体 是凸集,只要证明D中任意两点任意两点 X (1) ,X (2) 连线上的一切点均满 足线性约束条件既可。
(1) (1) (2) (2) 任取 X (1) ? D,X (2) ? D,满足 AX =b,X ? 0, AX =b,X ? 0,

则对任意的 X=? X(1) +(1-? )X(2) ,0<? ? 1,有

AX=A[αX(1) +(1-α)X(2) ]=αAX(1) +(1-α)AX(2) =αb+(1-α)b=b
又因为 X (1) ,X (2) ,α,1-α 均≥0,所以 X=? X(1) +(1-? )X(2) ? 0, 由此可知, ? X(1) +(1-? )X(2) ? D,即D是凸集。 X=
46

返回总目录
引理1 线性规划问题的可行解

X=(x1 ,x 2 ,? , x n )T

是基本可行解的充要条件是X的正分量所对应的系数列向量线性无关。

证明:必要性:因为X是基本解,由基本解的定义,X的非零分量所
对应的系数列向量线性无关,又因为X是可行解,由基本可行解的定 义,非零分量均是正的,所以X的正分量所对应的系数列向量线性无

关。
充分性:设X是线性规划问题的可行解,且正分量 x1 ,x1 ,? x k 所对应的列向量 P1 ,P1 ,? Pk 也线性无关,则必有k≤m,若k=m,则
P1 ,P1 ,? Pk 刚好构成一个基, X=(x1 ,x1 ,? x k , 0,? 0)T 为相应的基本 可行解。若k<m,则由线性代数知识,一定可以从其余的n-k个系数列

向量中取出m-k个与 P1 ,P1 ,? Pk 构成最大线性无关向量组,其对应的 基本可行解恰好为X,不过此时的X是一个退化的基本可行解。

47

返回总目录
定理2 设线性规划问题的可行域
n ? ? D= ? X / ? Pj x j = b, x j ? 0, j=1,2,...,n?,则X是D的一个 j=1 ? ? 顶点的充分必要条件是X为线性规划问题的基本可行解。

证明思路:必要性:由引理1,若X是D的一个顶点,要证明X是线性 规划的一个基本可行解,只要证明X的正分量 x1 ,x1 ,? x k 所对应的 系数列向量线性无关。 用反证法,倘若X的正分量所对应的系数列向量 P1 ,P1 ,? Pk 线性相关, 1 1 (2) 则可以在D中找到两点 ,使 X (1) ,X (2) X= X (1) + ,与X是D的顶 X 2 2 点矛盾 充分性:若X是线性规划的一个基本可行解,要证明X是可行域 D的一个顶点, 仍用反证法,倘若X不是可行域D的顶点 ,可以证明X的基变量 所对应的系数列向量 P1 ,P1 ,? Pm 线性相关,与X是基本可行解矛盾。
48

返回总目录
例8 已知线性规划问题的约束条件为

? 10 ? x1 ? x 2 ? x 3 ? ? x 4 ? 10 ? x1 ? x ,x ,x ,x ? 0 ? 1 2 3 4
解:可行域

?1 1 1 0 ? A?? ? 1 0 0 1? ?

试讨论可行域顶点和基本可行解之间的对应关系。

D= ?X / x1 +x 2 +x3 =10, x1 +x4 =10, xj ? 0, j=1,2,3,4,?

为四维凸多面体,可以推得在四维空间中有3个顶点, A=(0,0,10,10),B=(0,10,0,10),C=(10,0,0,0)。 这3个顶点与线性规划的5个基本可行解的对应关系如下: 顶点A对应以x3,x4为基变量的基本可行解; 顶点B对应以x2,x4为基变量的基本可行解;

顶点C对应x1,x2;x1,x3和x1,x4为基变量的退化基本可行解。
49

返回总目录
?一个线性规划问题,如果它的所有基本可行解都是非退化的,那么 称这个线性规划是非退化的,只有在这种情况下,顶点和基本可行解 之间才是一一对应的。 定理3 若可行域D非空有界,那么线性规划问题的目标函数一定可以 在可行域D的顶点上达到最优值。 本定理称为线性规划的基本定理,证明的思路是: ( 因为可行域非空有界,所以线性规划一定有最优解,倘若 X 0) 不是点, 且目标函数在该点处取到最优值 Z* ,则必能找到可行域的一个顶 ( 点 X m),使目标函数在的值也等于 Z* 。 ?定理3并不排除在一个非顶点上有一个最优解的可能性。但是在一个 给定的线性规划问题的所有最优解中,至少有一个是顶点。 ?如果可行域无界,则线性规划问题可能无最优解。 ?如果目标函数同时在两个顶点上达到最优解,那么不难证明在这两个 点的凸组合上也达到最优解,这时线性规划问题有无穷多最优解。
50

返回总目录

第2章 单纯形法
? ? ? ? ? 单纯形法的一般原理 表格单纯形法 借助人工变量求初始的基本可行解 单纯形表与线性规划问题的讨论 改进单纯形法

51

返回总目录

?单纯形法的一般原理
考虑到如下线性规划问题

maxZ=CX ? AX=b ? ?X ? 0

其中A一个m×n矩阵,且秩为m,b总可以被调整为一个m维非负列 向量,C为n维行向量,X为n维列向量。 根据线性规划基本定理: 如果可行域D={ X∈Rn / AX=b,X≥0}非空有界, 则D上的最优目标函数值Z=CX一定可以在D的一个顶点上达到。 这个重要的定理启发了Dantzig的单纯形法,

即将寻优的目标集中在D的各个顶点上。

52

返回总目录
Dantzig的单纯形法把寻优的目标集中在所有基本可行解

(即可行域顶点)中。
其基本思路是从一个初始的基本可行解出发,寻找一条达到 最优基本可行解的最佳途径。 单纯形法的一般步骤如下:

(1)寻找一个初始的基本可行解。
(2)检查现行的基本可行解是否最优,如果为最优, 则停止迭代,已找到最优解,否则转一步。 (3)移至目标函数值有所改善的另一个基本可行解, 然后转到步骤(2)。

53

返回总目录

? 确定初始的基本可行解
确定初始的基本可行解等价于确定初始的可行基,一旦初始 的可行基确定了,那么对应的初始基本可行解也就唯一确定 为了讨论方便,不妨假设在标准型线性规划中,系数矩阵A 中前m个系数列向量恰好构成一个可行基,即 A=(BN),其中 B=(P1,P2,…Pm)为基变量x1,x2,…xm的系数列向量 构成的可行基, N=(Pm+1,Pm+2,…,Pn)为非基变量xm+1 ,xm+2,…,xn的 系数列向量构成的矩阵。

54

返回总目录
所以约束方程

AX=b 就可以表示为

? XB ? AX=(BN) ? ? =BX B +NX N =b ? XN ?
用可行基B的逆阵B-1左乘等式两端,再通过移项可推得:

X B =B-1b-B-1NX N -1 若令所有非基变量 X N =0 , 则基变量 X B =B b
由此可得初始的基本可行解

? B ?1 b ? X= ? ? ? 0 ?
55

返回总目录

AX=b ? BX B +NX N =b ? X B =B-1b-B-1NX N ? X N =0,X B =B-1b
? 问题: ? 要判断m个系数列向量是否恰好构成一个基并不是一件容易的事。 基由系数矩阵A中m个线性无关的系数列向量构成。 但是要判断m个系数列向量是否线性无关并非易事。

? 即使系数矩阵A中找到了一个基B,也不能保证该基恰好是可行基。 因为不能保证基变量XB=B-1b≥0。

? B ?1 b ? -1 ? 为了求得基本可行解 X= ? ? ,必须求基B的逆阵B 。 ? 0 ?
但是求逆阵B-1也是一件麻烦的事。

? 结论:在线性规划标准化过程中应设法得到一个m阶单位矩阵I作为初 始可行基B,
56

返回总目录
为了设法得到一个m阶单位矩阵I作为初始可行基B,可在性规 划标准化过程中作如下处理: ? 若在化标准型前,m个约束方程都是“≤”的形式, 那么在化标准型时只需在一个约束不等式左端都加上一个松弛变 量xn+i (i=1,2,…,m)。 ? 若在化标准形式前,约束方程中有“≥”不等式, 那么在化标准型时除了在方程式左端减去剩余变量使不等式变 成等式以外,还必须在左端再加上一个非负新变量,称为 人工变量. ? 若在化标准形式前,约束方程中有等式方程,那么可以直接在 等式左端添加人工变量。

57

返回总目录

?判断现行的基本可行解是否最优
? B ?1 b ? 假如已求得一个基本可行解 X= ? ? 0 ? ?
将这一基本可行解代入目标函数,可求得相应的目标函数值

? B?1b ? Z=CX=(C BC N ) ? =C B B-1b ? ? 0 ?
其中 C =(c ,c ,? c ), C =(c ,c ,? c ) 分别表示基变量和 B 1 2 m N m+1 m+2 n
非基变量所对应的价值系数子向量。

58

返回总目录
要判定 Z=CB B-1b 是否已经达到最大值,只需将

X B =B-1b-B-1NX N 代入目标函数,使目标函数用非基变量
表示,即:

? x m+1 ? ? ? x m+2 ? ? CB B-1b+σ N X N ? CB B-1b+(σm+1, σ m+1, ? σ n ) ? ? ? ? ? ? x ? ? ? n ? 其中 ? N =CN -CB B-1N=(? m+1 , ? m+1 ,?? n ) 称为非基变量XN
=CB B-1b+(C N -CB B-1 N)X N
的检验向量,它的各个分量称为检验数。若σN的每一个检验数均小 于等于0,即σN≤0,那么现在的基本可行解就是最优解。
59

? XB ? Z=CX=(CBC N ) ? ? XN ? ? =CB X B +C N X N =CB (B-1b-B-1 NX N )+C N X N

返回总目录
定理1 最优解判别定理

对于线性规划问题 maxZ=CX, D= X ? R n /AX=b,X ? 0 若某个基本可行解所对应的检验向量 ? N =C N -CB B-1 N ? 0,

?

?

则这个基本可行解就是最优解。

定理2

无穷多最优解判别定理

? x m+1 ? ? ? x m+2 ? -1 Z ? CB B b+(σ m+1, σ m+1, ? σ n ) ? ? ? ? ? ? x ? ? ? n ?

? B ?1b ? 是一个基本可行解,所对应的检验向量 若 X= ? ? 0 ? ?

? N =C N -CB B-1 N ? 0 ,其中存在一个检验数σm+k=0,
则线性规划问题有无穷多最优解。

60

返回总目录

? 基本可行解的改进
如果现行的基本可行解X不是最优解,即在检验向量

? N =CN -CBB-1N 中存在正的检验数,则需在原基本可行解X的基
础上寻找一个新的基本可行解,并使目标函数值有所改善。具体 做法是: ? 先从检验数为正的非基变量中确定一个换入变量,使它从非基 变量变成基变量(将它的值从零增至正值), ? 再从原来的基变量中确定一个换出变量,使它从基变量变成非 基变量(将它的值从正值减至零)。
? x m+1 ? ? ? x m+2 ? 由此可得一个新的基本可行解,由 Z ? CB B-1b+(σ m+1,σ m+1, ? σ n ) ? ? ? ? ? 可知,这样的变换一定能使目标函数值有所增加。 ? x ? ? ? n ?

61

返回总目录
换入变量和换出变量的确定:

?换入变量的确定— 最大增加原则 假设检验向量 ? N =C N -CB B N=(? m+1 , ? m+2 ,?? n ) , 若其中有两个以上的检验数为正,那么为了使目标函数值增加得快 些,通常要用“最大增加原则”,即选取最大正检验数所对应的非基 变量为换入变量,即若
-1

max ?σ j /σ j >0,m+1 ? j ? n? =σ m+k 则选取对应的 x m+k 为换入变量,
由于? m+k ? 0 且为最大,

? x m+1 ? ? ? x m+2 ? -1 可使目标函数值 Z ? CB B b+(σ m+1, σ m+1, ? σ n ) ? ? ? ? 最大限度的增加。 ? ? x ? ? ? n ?

因此当 x m+k 由零增至正值,

62

返回总目录
? 换出变量的确定— 最小比值原则 如果确定 x m+k 为换入变量,方程

X B =B-1b-B-1 NX N ? X B =B-1b-B-1Pm+k x m+k
其中 Pm+k为A中与

x m+k

对应的系数列向量。

现在需在 X B =(x1 , x 2 ,? x m )T 中确定一个基变量为换出变量。 当 x m+k 由零慢慢增加到某个值时, B 的非负性可能被打破。 X 为保持解的可行性,可以按最小比值原则确定换出变量:



? (B-1b)i ? (B-1b)l ? min ? -1 /(B-1Pm+k )i >0,1 ? i ? m ? = -1 ? (B Pm+k )i ? (B Pm+k )l ?

则选取对应的基变量 x l 为换出变量。
63

返回总目录
定理3 无最优解判别定理

? B ?1 b ? 若 X= ? ? 是一个基本可行解,有一个检验数 ? m+k ? 0 ? -1 但是 B Pm+k ? 0 ,则该线性规划问题无最优解。
证:令 x m+k ? ? ,(? ? 0),则得新的可行解

?0



将上式代入 X B =B b-B Pm+k x m+k ? B b-B Pm+k?
-1 -1 -1 -1

? x m+1 ? ? ? ? ? ? -1 Z=CB B b+(σ m+1 ,? σ m+k ,? σ n ) ? ? ? ? C B B-1b+σ m+k? ? ? ? ? ? ? x ? ? n ?
因为

? m+k ? 0, 故当λ→+≦时,Z→+≦。
64

返回总目录

? 用初等变换求改进了的基本可行解
假设B是线性规划

maxZ=CX,AX=b,X ? 0 的可行基,则

? XB ? ? XB ? -1 (I,B N) ? =B-1b AX=b ? (BN) ? ? ??b? XN ? ? ? XN ?
令非基变量 X N =0 ,则基变量 X B =B?1b 。

? B ?1 b ? 可得基本可行解 X= ? ?。 ? 0 ?
? 用逆阵 B?1 左乘约束方程组的两端,等价于对方程组施以一系列 的初等“行变换”。变换的结果是将系数矩阵A中的可行基B变换 成单位矩阵I,把非基变量系数列向量构成的矩阵N变换成?1 N B 把资源向量b变换成 ?1b B 。
65



返回总目录
由于行初等变换后的方程组 (I,B-1 N) ?

? XB ? 与原约束方程组 AX=b 或 (B,N) ? ? =b 同解 ? XN ?

? XB ? -1 ? =B b ? XN ?

且改进了的基本可行解 只是在X的基变量的基础上用一个换入 X' 变量替代其中一个换出变量,其他的基变量仍然保持不变。这些基 变量的系数列向量是单位矩阵I中的单位向量。为了求得改进的基本

可行解

,只需对增广矩阵 X'

(I,B N,B b)
施行初等行变换,将换入变量的系数列向量变换成换出变量所对应 的单位向量即可。

-1

-1

66

返回总目录
例1 maxZ=5x1 ? 2x2 ? 3x3 ? x4 ? x5

?8 ? x1 ? 2x 2 ? 2x 3 ? x 4 ? ? x5 ? 7 ?3x1 ? 4x 2 ? x 3 ? x ,x ,x ,x ,x ? 0 ? 1 2 3 4 5
解: (1)确定初始的基本可行解。

C=(5,2,3, ? 1 ,1)

?1 2 2 A= ? ?3 4 1

1 0

0? ?8? ? b ? ?7? 1? ? ?

?1 B=(P4 P5 )= ? ?0

0? ? ,基变量 1?

x 4 ,x 5,非基变量 x1 ,x 2 , x 3 。

? x1 ? ? x4 ? ?1 0? ? 1 2 2 ? C B =(-1,1) ?8? ? ? X B = ? ? ,X N = ? x 2 ? ,B= ? ,b= ? ? ? ,N= ? ?, x5 ? 0 1? 3 4 1 ? C N =(5,2,3) ? ? ?7? ? ?x ? ? 3? ?8? ?1 X N =0 ? X B =B b= ? ? ? X=(0,0,0, 8, 7)T ?7? ?8? Z=CB B?1b=(-1,1) ? ? ? ? 1 ?7?

67

返回总目录
? x1 ? ? x4 ? ?1 0? ? 1 2 2 ? C B =(-1,1) ?8? ? ? X B = ? ? ,X N = ? x 2 ? ,B= ? ? ,N= ? ? , C =(5,2,3) ,b= ? ? ?0 1? ?3 4 1? N ?7? ? x5 ? ?x ? ? 3?
(2) 检验 X=(0,0,0,8, 7)T 是否最优。

检验向量 σ N =C N -C B B-1 N=(5,2,3)-(-1,1) ?

?1 ?3

2 4

2? ? 1?

=(5,2,3)-(2,2,-1)=(3, 0, 4) ? ? ? σ1 σ 2 σ3
因为σ1=3,σ3=4 均大于零,

所以 X=(0,0,0,8, 7)T 不是最优解。

68

返回总目录
? x1 ? ? x4 ? ?1 0? ? 1 2 2 ? C B =(-1,1) ?8? ? ? X B = ? ? ,X N = ? x 2 ? ,B= ? ? ,N= ? ? , C =(5,2,3) ,b= ? ? ?0 1? ?3 4 1? N ?7? ? x5 ? ?x ? ? 3?

? N =(? 1 ,? 2 ,? 3 ) ? (3, 0, 4)
(3)基本可行解 X=(0,0,0,8, 7)T 的改进
① 选取换入变量 因为max{3,4}=4,取x3为换入变量。 ②
?1

选取换出变量

? 8 ? ?1 ? 2? ?8 7 ? 8 且 min ? , ? ? , B b= ? ? , B P3 ? ? ? ? 0 ?2 1? 2 ?7? ?1?
选取x4为换出变量.

? x4 ? ?8? ? 2? -1 -1 ? ? =B b-B P3 x 3 = ? ? - ? ? x 3 ?7? ?1? ? x5 ?

69

返回总目录
? x1 ? ? x4 ? ?1 0? ? 1 2 2 ? C B =(-1,1) ?8? ? ? X B = ? ? ,X N = ? x 2 ? ,B= ? ? ,N= ? ? , C =(5,2,3) ,b= ? ? ?0 1? ?3 4 1? N ?7? ? x5 ? ?x ? ? 3?
(4)求改进了的基本可行解 X ' 对约束方程组的增广矩阵施以初等行变换,使换入变量x3所对应的

1 2 系数列向量 P = ? ? 变换成换出变量x4所对应的单位向量 P ? ? ? , 4 ? ? 3 ? ?

?0? 注意保持基变量x5的系数列向量 P5 = ? ?为单位向量不变。 ?1?

?1?

?0?

? 1 1 1 1 0 4? ? 1 2 2 1 0 8 ? 第一行除以2 ? 2 ? ? ? ???????? ? 2 ? ? ?3 4 1 0 1 7 ? 3 4 1 0 1 7? ? ?1 1 1 1 0 4? ?2 ? 2 ????????? ? ? 5 3 0 -1 1 3 ? ? ? ?2 2 ?
第二行减去第一行

70

返回总目录
C=(5,2,3, ?1,1)

?1 2 2 1 0 8? ? ? ?3 4 1 0 1 7 ?
可得改进的基本可行解。

——————————————————————————
?1 0? B=(P3 P5 )= ? x ? ,基变量 x 3 , 5 非基变量x1 ,x 2 , x 4 。 ?0 1? 1? ?1 ? x1 ? ? 2 1 2 ? CB =(3,1) ? x3 ? ?1 0? ? 4? ? ? X B = ? ? ,X N = ? x 2 ? ,B= ? ,b= ? ? ?, ? ,N= ? ?0 1? ? 5 3 -1 ? C N =(5,2,-1) ? 3? ? x5 ? ?x ? ? ? ? 4? ?2 2?
?1

C=(5,2,3, ?1,1) ?1 1 1 1 0 4? ?2 ? 2 ? ? ? 5 3 0 -1 1 3 ? ? ?2 2 ?

? 4? X N =0 ? X B =B b= ? ? ? 基本可行解 X=(0,0,4, 0, 3)T ? 3?
? 4? Z=CB B b=(3,1) ? ? ? 15 ? 3?
?1

目标函数值

易见目标函数值比原来的Z=-1增加了, 再转向步骤(2)

71

返回总目录
1? ?1 ? x1 ? 1 ?2 ? x3 ? ?1 0? ? 4? ? ? 2 ? CB =(3,1) X B = ? ? ,X N = ? x 2 ? ,B= ? ,b= ? ? ?, ? ,N= ? ?0 1? ? 5 3 -1 ? C N =(5,2,-1) ? 3? ? x5 ? ?x ? ? ? ? 4? ?2 2?
(2)检验 X=(0,0,4, 0, 3)T 是否最优。

?1 ?2 检验向量 -1 σ N =C N -C B B N=(5,2,-1)-(3,1) ? ?5 ? ?2 =(5,2,-1)-(4,6,1)=(1, -4, -2)
因为

1 3

1? 2? ? -1 ? ? 2?

?1 ? 1 ? 0

? ? ?

T

σ1 σ 2 σ 4

所以 X=(0,0,4, 0, 3) 仍不是最优解。
72

返回总目录
1? ?1 ? x1 ? 1 ?2 ? x3 ? ?1 0? ? 4? ? ? 2 ? CB =(3,1) X B = ? ? ,X N = ? x 2 ? ,B= ? ,b= ? ? ?, ? ,N= ? ?0 1? ? 5 3 -1 ? C N =(5,2,-1) ? 3? ? x5 ? ?x ? ? ? ? 4? ?2 2?
(3)基本可行解 X=(0,0,4, 0, 3)T 的改进 ① 选取换入变量

因为 ? ? 1 ? 0 ,取 x 为换入变量。 1 1 ② 选取换出变量 ?1? ?2? 3 ? 3 ? 4 ? ?1 ? 4 ?1 , B b= ? ? , B P1 ? ? ? ? 0 且 min ? , ?? 3? 5? 1/ 2 5 / 2 ? 5 / 2 ? ? ? ? ? ?2? 选取x 5 为换出变量. ? x ? ? 4 ? ? 1/2 ?

=B-1b-B-1P1x1 = ? ? - ? ? ? ? x1 ? 3 ? ? 5/2 ? ? x5 ?

3

73

返回总目录
1? ?1 ? x1 ? ? 2 1 2 ? CB =(3,1) ? x3 ? ?1 0? ? 4? ? ? X B = ? ? ,X N = ? x 2 ? ,B= ? ,b= ? ? ?, ? ,N= ? ?0 1? ? 5 3 -1 ? C N =(5,2,-1) ? 3? ? x5 ? ?x ? ? ? ? 4? ?2 2? (4)求改进了的基本可行解 X ''
对约束方程组的增广矩阵施以初等行变换,使换入变量 x 1 所对应
?1? ? ? 的系数列向量 P1 = ? 2 ? 变换成换出变量 ?5? ? ? ?2?

x 5 所对应的单位向量 P5 ? ? ?
1 1 1 2 6 0 -1 5 5 2 1 3 5 5 6 0 -1 5 5 0 4 ? ? 2 6? ? 5 5? -1 17 ? 5 5 ? 2 6? ? 5 5?

?0? ?1?

?1 ?2 ?5 ? ?2

?1 1 1 1 0 4? 第二行乘以2/5 ?2 ? 2 ????????? ? ? -1 1 3 ? 3 0 ? ?1 2 ? ? ? ?????????? ? ? ?1 ?
第一行减以第二行的1/2倍 ? 0

74

返回总目录 C=(5,2,3, ?1,1)
?1 ?2 ?5 ? ?2

C=(5,2,3, ?1,1)
2 1 3 -1 17 ? 5 5 5 5 ? 6 0 -1 2 6 ? ? 5 5 5 5?

——————————————————————————
可得改进的基本可行解。

?0 1 1 1 0 4? ? ? 2 ? ? ? 3 0 -1 1 3 ? ?1 2 ? ?

?1 0? B=(P3 P1 )= ? ?,基变量 x 3 ,x1 ,非基变量 x 2 ,x 4 , x 5 ?0 1? ? 2 3 -1 ? ? 17 ? ? x2 ? ? 5 5 5 ? CB =(3,5) ? 5? ? x3 ? ?1 0? ? ? X B = ? ? ,X N = ? x 4 ? ,B= ? ,b= ? ? ?, ? ,N= ? ? 6 -1 2 ? C N =(2,-1,1) ? 6? ?0 1? ? x1 ? ?x ? ? ? ? ? ? 5? ?5 5 5 ? ? 5? ? 17 ? ? 5 ? 6 17 ?1 X=( ,0, , 0, 0)T X N =0 ? X B =B b= ? ? ? 基本可行解 5 5 ? 6 ?
目标函数值 骤(2)

? ? ? 17 ? ? 5 ? ? 5 ? 81 ?1 Z=C B B b=(3,5) ? ?? 比Z=15增加了,再转向步 6 ? 5 ? 75 ? ? ? 5 ?

返回总目录
?2 ? x2 ? ?5 ? x3 ? ?1 0? ? ? X B = ? ? ,X N = ? x 4 ? ,B= ? ? ,N= ? x1 ? ?6 ?0 1? ? ?x ? ? ? 5? ?5 3 -1 ? ? 17 ? ? 5? 5 5 ? CB =(3,5) ,b= ? ? ?, C N =(2,-1,1) -1 2 ? ? 6? ? ? ? 5 5? ? 5?
-1 ? 5? ? 2? ? 5?

(2)检验 X'' =( 6 ,0, 17 , 0, 0)T
5 5
检验向量

是否最优。
3 5 -1 5

?2 ?5 -1 σ N =C N -C B B N=(2,-1,1)-(3,5) ? ?6 ? ?5 36 4 7 -26 -9 -2 =(2,-1,1)-( , , )=( , , ) 5 5 5 5 5 5 ? ? ? σ 2 σ 4 σ5

因为所有检验数均小于零,
*

'' =( 6 ,0, 17 , 0, 0)T 是最优解, Z* = 81 所以 X =X 5 5 5
76

返回总目录

?表格单纯形法
通过例1我们发现,在单纯形法的求解过程中,有下列重要指标: ? 每一个基本可行解的检验向量 σ N =C N -CB B-1 N 根据检验向量可以确定所求得的基本可行解是否为最优解。如果不 是最优又可以通过检验向量确定合适的换入变量。 ? 每一个基本可行解所对应的目标函数值 Z=C B B?1b 通过目标函数值可以观察单纯形法的每次迭代是否能使目标函数值 有效地增加,直至求得最优目标函数为止。

? 在单纯形法求解过程中,每一个基本可行解X都以某个经过初等行
变换的约束方程组中的单位矩阵Ι为可行基。 当B=I时,B-1=I,易知: σ N =CN -CB N
Z=CB b

77

返回总目录
可将这些重要结论的计算设计成如下一个简单的表格, 即单纯形表来完成:

C CB C1 C2 . . Cm Z XB X1 X2 . . Xm b b1 b2 . . bm CBb

CB X1 X2 · Xm · ·

CN X m+1 Xm+2 · Xn · · θ θ1 θ2 . . θm

I
0

N
CN - CBN

78

返回总目录
例2 试利用单纯形表求例1中的最优解解: maxZ=5x1 ? 2x2 ? 3x3 ? x4 ? x5 C=(5,2,3, ? 1,1) ?8 ? x1 ? 2x 2 ? 2x 3 ? x 4 ? 1 2 2 1 0 8? ? (Ab)= ? ? ? x5 ? 7 ?3x1 ? 4x 2 ? x 3 3 4 1 0 1 7? ? ? x ,x ,x ,x ,x ? 0 ? 1 2 3 4 5 得初始的单纯形表: C CB -1 1 Z XB x4 x5 b 8 7 -1
Z=CB b

5 x1 1 3 3

2 x2 2 4 0

3 x3 2 1 4

-1 x4 1 0 0

1 x5 0 1 0

Θ

σ N =CN -CB N
79

初始基本可行解 X=(0,0,0, 8, 7)T ,Z= -1,

返回总目录
C 5 2 3 -1 1 Θ 8/2

CB
-1

XB
x4

b
8

x1
1

x2
2

x3
2

x4
1

x5
0

1 Z

x5

7 -1

3 3

4 0

1 4

0 0

1 0

7/1

x 3 换入变量,x 4 换出变量,2为主元进行旋转变换
C CB 3 1 Z XB x3 x5 b 4 3 15 5 x1 1/2 5/2 1 2 x2 1 3 -4 3 x3 1 0 0 -1 x4 1/2 -1/2 -2 1 x5 0 1 0
80

Θ

X=(0,0,4, 0, 3)T 基本可行解 ,Z= 15,

返回总目录
C CB 3 1 Z XB x3 x5 b 4 3 15 5 x1 1/2 5/2 1 2 x2 1 3 -4 3 x3 1 0 0 -1 x4 1/2 -1/2 -2 1 x5 0 1 0 4/1/2 3/5/2 Θ

x 1 换入变量,x 5 换出变量,5/2为主元进行旋转变换
C CB 3 5 Z XB x3 x1 b 17/5 6/5 81/5 5 x1 0 1 0 2 x2 2/5 6/5 -26/5 3 x3 1 0 0 -1 x4 3/5 -1/5 -9/5 1 x5 -1/5 2/5 -2/5 Θ

T 6 17 σ N =C N -CB N ? 0 最优解 X ? ? ? , 0, , 0, 0 ?最优值 Z? ? 81 ? ? 5 5 ?5 ?

81

返回总目录
例3 用单纯形方法求解线性规划问题

minZ=-x1 -2x 2 ? x3 ?4 ? x1 ? x2 ? x4 ?3 ? ? ? x5 ? 8 ? x1 ? 2x 2 ? x j ? 0 ,j ? 1,2,3,4,5 ?
解:本题的目标函数是求极小化的线性函数,
可以令

Z' = -Z = x1 +2x 2



minZ=-x1 -2x2 ? max Z ' ? x1 +2x2

这两个线性规划问题具有相同的可行域和最优解, 只是目标函数相差一个符号而已。
82

返回总目录
C CB 0 0 0 XB x3 x4 x5 b 4 3 8 1 x1 1 0 1 2 x2 0 1 2 0 x3 1 0 0 0 x4 0 1 0 0 x5 0 0 1 Θ _ 3/1 8/2 4/1 -

Z’
0 2 x3 x2

0
4 3

1
1 0

2
0 1

0
1 0

0
0 1

0
0 0

0
Z’ 0 2 1 Z’

x5
x3 x2 x1

2
6 2 3 2 8
T

1
1 0 0 1 0

0
0 0 1 0 0

0
0 1 0 0 0

-2
-2 2 1 -2 0

1
0 -1 0 1 -1

2/1
2/2 3/1 -

? 最优解 X ? ? 2,3, 2, 0, 0 ? 最优值

maxZ' =8 or minZ=-8
83

返回总目录
因为非基变量x4的检验数σ4=0,由无穷多最优解判别定理,本例
的线性规划问题存在无穷多最优解。事实上若以x4为换入变量,以x3为 换出变量,再进行一次迭代,可得以下单纯形表: C 1 2 0 0 0 Θ

CB
0 2 1 Z’

XB
x4 x2 x1

b
1 2 4 8

x1
0 0 1 0

x2
0 1 0 0

x3
1/2 -1/2 1 0

x4
1 0 0 0

x5
-1/2 1/2 0 -1

最优解 X ? ? ? 4, 2, 0,1, 0?T 最优值 最优解的一般表示式
? T

maxZ' =8 or minZ=-8
T

X ? ? (2,3, 2, 0, 0) ? (1? ? ) ? 4, 2, 0,1, 0? , 0 ? ? ? 1.
84

返回总目录
对于极小化的线性规划问题的处理: ? 先化为标准型,即将极小化问题变换为极大化问题,然后利用单 纯形方法求解. ? 直接利用单纯形方法求解,但是检验是否最优的准则有所不同,

即: 若某个基本可行解的所有非基变量对应的检验数

σ N =C N -CB N ? 0 (而不是≤0),
则基本可行解为最优解.

否则采用最大减少原则(而非最大增加原则)来确定换入变量,
即: 若

min ?σ j /σ j <0,m+1 ? j ? n? =σ m+k

则选取对应的非基变量xm+k为换入变量. ? 确定了换入变量以后,换出变量仍采用最小比值原则来确定。
85

返回总目录

?借助人工变量求初始的基本可行解
若约束方程组含有“≥”不等式,那么在化标准形时除了在方程 式左端减去剩余变量,还必须在左端加上一个非负的人工变量。 因为人工变量是在约束方程已为等式的基础上,人为的加上去 的一个新变量,因此加入人工变量后的约束方程组与原约束方程组 是不等价的。 加上人工变量以后,线性规划的基本可行解不一定是原线性规 划的问题的基本可行解。只有当基本可行解中所有人工变量都为取 零值的非基变量时,该基本可行解对原线性规划才有意义。因为此 时只需去掉基本可行解中的人工变量部分,剩余部分即为原线性规 划的一个基本可行解.而这正是我们引入人工变量的主要目的。

86

返回总目录
考虑线性规划问题: maxZ=

?c x
j j=1

n

j

? n ? ? a i j x j =bi ,i=1,2,...,m ? j=1 ? x ? 0,j=1,2,....,n ? j
为了在约束方程组的系数矩阵中得到一个m阶单位矩阵作为 初始可行基,在每个约束方程组的左端加上一个人工变量

x n+i (i=1,2,? m)
可得到:

maxZ= ? c j x j
j=1

n

? n ? ? a i j x j +x n+i =bi ,i=1,2,...,m ? j=1 ? x ? 0,j=1,2,....,n+m ? j

87

返回总目录
? ? ? ? ?

————————————————————————

? n ? a i jx j =bi ,i=1,2,...,m ? ? ? a i jx j +x n+i =bi ,i=1,2,...,m j=1 ? j=1 ? x ? 0,j=1,2,....,n+m x j ? 0,j=1,2,....,n ? j
n

添加了m个人工变量以后,在系数矩阵中得到一个m阶单位矩阵, 以该单位矩阵对应的人工变量 x n+i (i=1,2,? m) 为基变量, 即可得到一个初始的基本可行解

X (0) =(0,0,?,0,b1 ,b 2 ,? b m )T
这样的基本可行解对原线性规划没有意义的。 但是我们可以从X(0)出发进行迭代,一旦所有的人工变量都从基变 量迭代出来,变成只能取零值的非基变量,那么我们实际上已经求得 了原线性规划问题的一个初始的基本可行解。 此时可以把所有人工变量剔除,开始正式进入求原线性规划最优 解的过程。
88

返回总目录

? 大M法
大M法首先将线性规划问题化为标准型。如果约束方程组中包含 有一个单位矩阵I,那么已经得到了一个初始可行基。否则在约束方 程组的左边加上若干个非负的人工变量,使人工变量对应的系数列向 量与其他变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初 始基,即可求得一个初始的基本可行解。 为了求得原问题的初始基本可行解,必须尽快通过迭代过程把人 工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋 予人工变量一个绝对值很大的负系数-M。这样只要基变量中还存在 人工变量,目标函数就不可能实现极大化。 以后的计算与单纯形表解法相同,M只需认定是一个很大的正数 即可。假如在单纯形最优表的基变量中还包含人工变量,则说明原问 题无可行解。否则最优解中剔除人工变量的剩余部分即为原问题的初 始基本可行解。
89

返回总目录
例4 用大M法求解下面的线性规划问题: 解: 首先将原问题化为标准型

maxZ=-x1 +2x 2 ? x1 ? x 2 ? 2 ? -x ? x ? 1 ? 1 2 ? x2 ? 3 ? ? x1 ,x 2 ?? 0 ?

?2 ? x1 ? x 2 -x 3 ?-x ? x -x 4 ?1 ? 1 2 ? x2 ? x5 ? 3 ? ? x j ?? 0,j ? 1,2,3,4,5 ?

添加人工变量 x 6 ,x 7 ,并在目标函数中分别赋予-M

maxZ= -x1 +2x 2 -Mx 6 -Mx 7 ? x6 ?2 ? x1 ? x 2 -x 3 ? -x ? x -x 4 ? x7 ? 1 ? 1 2 ? x2 ? x5 ?3 ? ? x j ?? 0,j ? 1,2,3,4,5,6,7 ?
90

返回总目录
C CB -M -M 0 Z -M 2 0 Z -1 2 0 Z X1 X2 X5 X6 X2 X5 XB X6 X7 X5 b 2 1 3 -3M 1 1 2 2-M 1/2 3/2 3/2 5/2

-1
X1 1 -1 0 -1 2 -1 1 1+2M 1

2
X2 1 1 1 2+2M 0 1 0 0 0

0
X3 -1 0 0 -M -1 0 0 -M -1/2

0
X4 0 -1 0 -M 1 -1 1 2+M 1/2

0
X5 0 0 1 0 0 0 1 0 0

-M
X6 1 0 0 0 1 0 0 1/2

-M
X7 0 1 0 0 -1 1 -1 -1/2

θ
2/1 1/1 3/1 1/2 2/1

0 -2-2M

0
0 0

1
0 0

-1/2
1/2 1/2

-1/2
1/2 3/2

0
1

1/2
-1/2

1/2
-1/2

-

0 -1/2-M -3/2-M

91

返回总目录
C CB -1 2 0 XB X1 X2 X5 b 1/2 3/2 3/2 -1 X1 1 0 0 2 X2 0 1 0 0 X3 -1/2 -1/2 1/2 0 X4 1/2 -1/2 1/2 0 X5 0 0 1 0 0 -M X6 1/2 1/2 -1/2 1 1 -M X7 -1/2 1/2 -1/2 -1 0 θ
1/2/1/2 3/2 /1/2

Z
0 2 0 Z 0 2 0 Z X4 X2 X3 X4 X2 X5

5/2
1 2 1 4 2 3 1 6

0
2 1

0
0 1

1/2
-1 -1

3/2
1 0

0 -1/2-M -3/2-M

-1
-3 1 0 -1 -1
T

0
0 0 1 0 0

1
2 0 0 1 0

0
0 1 0 0 0

1
0 1 1 1 -2

-1
-2-M 0 0 -1 -M

0
-M -1 0 0 -M

X? ? ? 0,3,1, 2, 0 ? 最优解

最优值

Z? ? 6
92

返回总目录

? 两阶段法
两阶段法引入人工变量的目的和原则与大M法相同,所不同的是
处理人工变量的方法。 两阶段法的步骤: ? 求解一个辅助线性规划。目标函数取所有人工变量之和,并取极 小化;约束条件为原问题中引入人工变量后包含一个单位矩阵的标准 型的约束条件。 如果辅助线性规划存在一个基本可行解,使目标函数的最小值等于 零,则所有人工变量都已经“离基”。表明原问题已经得了一个初始 的基本可行解,可转入第二阶段继续计算;否则说明原问题没有可行 解,可停止计算。 ? 求原问题的最优解。在第一阶段已求得原问题的一个初始基本可 行解的基础上,继续用单纯形法求原问题的最优解
93

返回总目录
例5 用两阶段法求解例4中的线性规划问题。maxZ=-x +2x 1 2 解:首先将问题化为标准型

?2 ? x1 ? x 2 -x 3 ?-x ? x -x 4 ?1 ? 1 2 ? x2 ? x5 ? 3 ? ? x j ? 0, j ? 1,2,3,4,5 ?

? x1 ? x 2 ? 2 ? -x ? x ? 1 ? 1 2 ? x2 ? 3 ? ? x1 ,x 2 ?? 0 ?

添加人工变量x6,x7,并建立辅助线性规划如下:

minZ=x 6 +x 7 ? x6 ?2 ? x1 ? x 2 -x 3 ? -x ? x -x 4 ? x7 ? 1 ? 1 2 ? x2 ? x5 ?3 ? ? x j ? 0, j ? 1,2,3,4,5,6,7 ?

由于辅助线性规划的目标函数 是极小化,因此最优解的判别 准则应为:

σ N =C N -CB N ? 0
94

返回总目录
C CB 1 1 0 W 1 0 0 W 0 0 0 W X1 X2 X5 X6 X2 X5 XB X6 X7 X5 b 2 1 3 3 1 1 2 1 1/2 3/2 3/2 0

0 X1 1
-1 0 0 2 -1 1 -2 1 0 0 0

0 X2 1
1 1 -2 0 1 0 0 0 1 0 0

0 X3 -1
0 0 1 -1 0 0 1 -1/2 -1/2 1/2 0

0 X4 0
-1 0 1 1 -1 1 -1 1/2 -1/2 1/2 0

0 X5 0
0 1 0 0 0 1 0 0 0 1 0

1 X6 1
0 0 0 1 0 0 0 1/2 1/2 -1/2 1

1 X7 0
1 0 0 -1 1 -1 2 -1/2 1/2 -1/2 1

θ 2/1 1/1 3/1 1/2 2/1

1 3 3 辅助规划所有检验数: σ N =C N -CB N ? 0, X=( , ,0,0, ) 2 2 2 95 minW=0 原问题已得一个初始基本可行解,

返回总目录
由上表可知,通过若干次旋转变换,原问题的约束方程组已 变换成包含一个单位矩阵的约束方程组

?2 ? x1 ? x 2 -x 3 ?-x ? x -x ?1 ? 1 2 4 ? x2 ? x5 ? 3 ? ? x j ? 0, j ? 1,2,3,4,5 ?

1 1 1 ? - x3 ? x4 ? ? x1 2 2 2 ? 1 1 3 ? ? x 2 - x3 - x4 ? ? 2 2 2 ? ? 1 1 3 x3 ? x 4 ? x5 ? ? 2 2 2 ? ? x j ? 0, j ? 1,2,3,4,5 ?

该约束方程组可作为第二阶段初始约束方程组,将目标函数
则还原成原问题的目标函数,可继续利用单纯形表求解。

96

返回总目录
CB

C
XB b

-1 X1 1 0 0 0 2 1 -1

2 X2 0 1 0 0 0 1 0

0 X3

0 X4

0 X5 0 0 1 0 0 0 1

θ
1/2/ 1/2

-1 2 0
Z 0 2 0 Z 0 2 0 Z

X1 X2 X5
X4 X2 X5 X4 X2 X3

1/2 3/2 3/2
5/2 1 2 1 4 2 3 1 6

-1/2 1/2 -1/2 -1/2 1/2 1/2 1/2 -1 -1 1 3/2 1 0 0

3/2/ 1/2

-3
1 0 -1 -1
T

0
0 1 0 0

2
0 0 1 0

0
1 0 0 0

0
1 1 1 -2

可得最优解 X ? ? ? 0, 3,1, 2, 0 ? ,目标函数值maxZ=6, 与用大M法的结果完全相同。
97

返回总目录

?单纯形表与线性规划问题的讨论
?无可行解
通过大M法或两阶段法求初始的基本可行解。但是如果在大

M法的最优单纯形表的基变量中仍含有人工变量,或者两阶段法的
辅助线性规划的目标函数的极小值大于零,那么该线性规划就不存 在可行解。 人工变量的值不能取零,说明了原线性规划的数学模型的约束 条件出现了相互矛盾的约束方程。此时线性规划问题的可行域为空 集。

98

返回总目录
例6 解: 首先将问题化为标准型 令 求解下列线性规划问题

minZ=3x1 +2x 2 +x 3 ? x1 ? x 2 ? x 3 ? 6 ?x -x 3 ? 4 ? 1 ? x 2 -x 3 ? 3 ? ? x1 ,x 2 ,x 3 ? 0 ?

Z' = -Z ,则

maxZ' = -3x1 -2x2 -x3 =6 ? x1 +x 2 +x 3 +x 4 ?x -x3 -x5 =4 ? 1 ? -x6 =3 ? x 2 -x3 ? xj ? 0, j=1,2,? 6. ?
故引入人工变量

maxZ' = -3x1 -2x 2 -x 3 -Mx 7 -Mx 8 =6 ? x1 +x 2 +x 3 +x 4 ?x -x 3 -x 5 +x 7 =4 ? 1 ? -x 6 +x 8 =3 ? x 2 -x 3 ? xj ? 0, j=1,2,?8. ?
99

x 7 ,x 8 ,

并利用大M法求解

返回总目录
C
CB 0 -M -M XB X4 X7 X8 Z’ 0 -M -2 Z’ -3 -M -2 Z’ X1 X7 X2 X4 X7 x2

b 6 4 3
-7M 3 4 3 -6-4M 3 1 3 -15-M

-3 X1
1 1 0

-2 X2
1 0 1

-1 X3
1 -1 -1

0 X4
1 0 0 0 1 0 0 0

0 X5
0 -1 0 -M 0 -1 0 -M

0 X6
0 0 -1 -M 1 0 -1 -2

-M -M X7 X8
0 1 0 0 0 1 0 0 0 1 0 -1 0 1

θ 6/1 3/1

-3+M -2+M -1-2M 1 1 0 -3+M 0 0 1 0 2 -1 -1 -3-M

3/1 4/1 -

0 2-M

1 0 0
0

0 0 1
0

2 -3 -1
3-3M

1 -1 0
3-M

0 -1 0
-M

1 -1 -1
1-M

0 1 0
0

-1 1 1
-1

在以上最优单纯形表中,所有非基变量检验数都小于零,但在该表中人 工变量x7=1为基变量,所以原线性规划不存在可行解。
100

返回总目录

?无最优解
无最优解与无可行解时两个不同的概念。 ? 无可行解是指原规划不存在可行解,从几何的角度解释是指 线性规划问题的可行域为空集; ? 无最优解则是指线性规划问题存在可行解,但是可行解的目 标函数达不到最优值,即目标函数在可行域内可以趋于无穷大 (或者无穷小)。无最优解也称为有限最优解,或无界解。 ?判别方法:无最优解判别定理 在求解极大化的线性规划问题过程中,若某单纯形表的检验 行存在某个大于零的检验数,但是该检验数所对应的非基变量 的系数列向量的全部系数都为负数或零,则该线性规划问题 无最优解,

? m+k ? 0
B-1Pm+k ? 0

X B =B-1b-B-1Pm+k x m+k

x m+k 可以 ? ??

Z 可以 ? ??

Z=CB B-1b+σ m+k x m+k
101

返回总目录
例7 试用单纯形法求解下列线性规划问题:

maxZ=2x1 +2x 2 ? x1 - x 2 ? -1 ? 1 ? ?- x1 ? x 2 ? 2 ? 2 ? x1 ? 0,x 2 ? 0 ?
因 ? 1 = 2>0

解:引入松弛变量x3,x4化为标准型

maxZ=2x1 +2x 2 ? -x1 ? x 2 ? x 3 ? 1 ? 1 ? +x 4 ? 2 ? - x1 ? x 2 ? 2 ? x j ? 0,j ? 1,2,3,4 ?
C C 0 0 Z XB X3 X4 B 1 2 0 2 X1 -1 -1/2 2 2 X2 1 1 2 0 X3 1 0 0 0 X4 0 1 0

θ

? -1 ? ? ? 但 P1 = ? 1 ? ? 0 ?- ? ? 2?
所以原问题 无最优解
102

返回总目录

? 退化解
当线性规划问题的基本可行解中有一个或多个基变量取零值时, 称此基本可行解为退化解。 ? 产生的原因:在单纯形法计算中用最小比值原则确定换出变量 时,有时存在两个或两个以上相同的最小比值θ,那么在下次迭代中 就会出现一个甚至多个基变量等于零。 ? 遇到的问题:当某个基变量为零,且下次迭代以该基变量作为 换出变量时,目标函数并不能因此得到任何改变(由旋转变换性质 可知,任何一个换入变量只能仍取零值,其他基变量的取值保持不 变)。通过基变换以后的前后两个退化的基本可行解的坐标形式完 全相同。从几何角度来解释,这两个退化的基本可行解对应线性规 划可行域的同一个顶点, ? 解决的办法:最小比值原则计算时存在两个及其以上相同的最 小比值时,选取下标最大的基变量为换出变量,按此方法进行迭代 一定能避免循环现象的产生(摄动法原理)。
103

返回总目录
例8 求解下述线性规划问题:

maxZ=3x1 -80x2 +2x3 -24x4 ? x1 -32x 2 -4x3 ? 36x 4 ? 0 ? x -24x - x ? 6x ? 0 ? 1 2 3 4 ? x3 ?1 ? ? x j ? 0,j ? 1,2,3,4 ?
解:引入松弛变量

maxZ=3x1 -80x 2 +2x 3 -24x 4 ?0 ? x1 -32x 2 -4x 3 ? 36x 4 ? x 5 ? x -24x - x ? 6x ? x6 ?0 ? 1 2 3 4 ? x3 ? x7 ? 1 ? ? x j ? 0,j ? 1,2,3,4,5,6,7 ?
104

x 5 ,x 6 ,x 7

化标准型

返回总目录
0
0 0 Z 0 3

C CB X B b

3 x1

-80 x2

2 x3

-24 x4

0 x5

0 x6

0 x7

θ

第一次迭代 中使用了摄动 法原理,选择 下 标 为 6的 基 变量x6离基。

x5
x6 x7 x5 x1

0
0 1 0 0 0

1
1 0 3 0 1

-32
-24 0 -80 -8 -24

-4
-1 1 2 -3 -1 1 5 0 0 1 0

36
6 0 -24 30 6

1
0 0 0 1 0

0
1 1 0 -1 1

0
0 1 0 0 0

0
0 -

0
Z 0 3 2 Z

x7
x5 x1 x3

1
0 3 1 1 5

0
0 0 1 0 0
T

0
-8 -8 -24 0 -8

0
-42 30 6 0 -42

0
0 1 0 0 0

1
-3 2 2 0 -6

1
0 3 1 1 -5

可得最优解 X ? ? ?1, 0,1, 0,3 ? ,目标函数值maxZ=5,

105

返回总目录

? 无穷多最优解
无穷多最优解判别原理:

若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零, 但其中存在一个检验数等于零,那么该线性规划问题有无穷多最优解。
例 最优表: 非基变量检验 数 , 所以有无穷多 ?4= 0 最优解。 C CB 0 2 1 XB X3 X2 X1 b 2 3 2 1 X1 0 0 1 2 X2 0 1 0 0 0 X3 1 0 0 0 0 X4 2 1 -2 0 0 X5 -1 0 1 -1

θ 2/2 3/1 -

Z’ 8 0 最优解集为可行域两个顶点的凸组合:

X? ? ? (2,3, 2, 0, 0)T ? (1 ? ? ) ? 4, 2, 0,1, 0 ? , 0 ? ? ? 1.
T

106

返回总目录

?改进单纯形法
?改进单纯形法的特点
利用单纯形表求解线性规划时,每一次迭代都把整个单纯形表计 算一遍,事实上我们关心的只是以下一些数据: ?基本可行解 X B =B-1b ,其相应的目标函数值 ?非基变量检验数 ? N =CN -CB B-1N 设 设

max ?σ j / σ j >0, j 为非基变量下标

Z=CB B-1b , ,及其换入变量 x k,

? =σ

k

主元列元素 B-1Pk ,及其换出变量 x l ,
? (B-1b)i ? (B?1b)l ? -1 min ? -1 /(B Pk )i >0, i为基变量下标 ? ? ?1 ? (B Pk )i ? (B Pk )l ? 利用它们可得到一组新的基变量以及新的可行基B1。
107

返回总目录
X B =B b
-1

Z=CB B-1b

? N =CN -CBB-1N

B-1Pk

对任一基本可行解X,只要知道

B-1 ,上述关键数据都可以从

线性规划问题的初始数据直接计算出来。因此如何计算基本可行解

X对应的可行基B的逆阵

B-1 成为改进单纯形法的关键.

-1 改进单纯形法推导出从可行基B变换到B1时, -1到 B1 B

的变换公式。当初始可行基为单位矩阵Ι时,变换公式将更具有优

越性,因为这样可以避免矩阵求逆的麻烦

以下推导从 B-1 到 B-1 的变换公式: 1

108

返回总目录
假设当前基 B ? (P1 , P2 ,? , Pl ?1 , Pl , Pl ?1 ,? Pm ) , 基变换中用非基变量 x k 取代基变量 x l 可得新基

B1 ? (P1 , P2 ,?, Pl ?1 , Pk , Pl ?1,? Pm )
. ? . 0? ? . ? 1 ? m? m ?

?1 B-1B ? (B-1P1 , B-1P2 ,? , B-1Pl ?1 , B-1Pl , B-1Pl ?1 ,? B-1 Pm ) ? ? . ? ?0 ? 比较以上二式,可得

前后二个基相比仅相差一列,且

B-1B1 ? (B-1P1 , B-1P2 ,? , B-1Pl ?1 , B-1Pk , B-1Pl ?1 ,? B-1Pm )

? (e1 ,

e2 , ? , el ?1 , B-1Pk , el ?1 ,? em )

其中 ei表示第 i 个元素为1,其他元素均为零的单位列向量,
B-1Pk为主元列元素。
109

返回总目录
B-1B1 ? (e1 , e2 , ? , el ?1 , B-1Pk , el ?1 ,? em )
第 l 列(换出变量x l 对应列 )
a'1k a'lk a'2k a'lk ? 1 a'lk ? ? a'mk a'lk ? ? ? 0? ? ? ? ? ? ? ? ? 第l 行 ? ? ? ? ? 1? ?
110

? a'1k ? ? ? a'2k ? ? ? ? ? -1 假设 B PK = ? ? , ? a'lk ? ? ? ? 主元素 ? ? a' ? ? ? mk ?

? ?1 ? ? ? ? ? Elk ? (B-1B1)-1 ? ? 则 ? ? ? ? ? ? ? ?0 ?

? ? -

所以由

Elk ? (B-1B1 )-1 ? B1-1B ? B1-1 ? E lk B-1

返回总目录

? 改进单纯形法的步骤
(1) 根据给出的线性规划问题的标准型,确定初始基变量和初 始可行基B。求初始可行基B的逆阵B-1,得初始基本可行解

X B =B-1b,X N ? 0



-1 -1 (2)计算单纯形乘子 π=CB B ,得目标函数当前值 Z=CB B b=πb

(3) 计算非基变量检验数 ? N =C N -CB B-1N=C N -πN



若σN≤0,则当前解已是最优解,停止计算;否则转下一步。
(4) 根据 max σ j /σ j >0 =σ k ,确定非基变量 x k 为换入变量,
-1 计算 B Pk ,若 B-1Pk ≤0,则问题没有有限最优解,停止计算,

?

?

否则转下一步。
111

返回总目录
? (B-1b)i ? (B-1b)l ? (5) 根据 min ? -1 /(B-1Pk )i >0 ? = -1 ? (B Pk )i ? (B Pk )l ?

,确定基变量 x l

为换出变量。
-1 -1 (6) 用 Pk 替代 Pl 得新基B1,由变换公式 B1 ? Elk B

计算新基的逆阵B1-1,求出新的基本可行解 其中 Elk 为变换矩阵,构造方法是: 从一个单位矩阵出发,把换出变量

x l 在基B中的对应列的单位

向量,替换成换入变量 x k 对应的系数列向量 B-1Pk,并做如下变形,
' 主元素 a lk (应在主对角线上)取倒数,其他元素除以主元素

a l' k 并取相反数。
重复(2)~(6)直至求得最优解。
112

返回总目录 ①
初始基 B=I

maxZ=CX ? AX=b ? ?X ? 0

X B =B-1b,X N ? 0

② π=CB B-1

Z=πb

③ ≤0 最优解 ? N =CN -πN ④
换入 x k

max ?σ j /σ j >0? =σ k
B1-1 ? Elk B-1


新基

B1

换出 x l



≤0
B-1Pk
无界解

? (B-1b)i ? (B-1b)l ? -1 min ? -1 /(B Pk )i >0 ? = -1 ? (B Pk )i ? (B Pk )l ?

113

返回总目录
例9 解: 试用改进单纯形法求解

maxZ=3x1 +2x 2 ? x1 +x 2 +x 3 =40 ? ?2x1 +x 2 +x 4 =60 ? x ,x ,x ,x ? 0 ? 1 2 3 4

C=(3,2,0,0)
?1 1 1 0 ? ? 40 ? A= ? ? b= ? ? 60 ? ?2 1 0 1 ? ?

(1)观察法确定

?1 0? B0 =(P3 P4 )= ? ? 0 1? ?
-1 0

, x 3 ,x 4 为基变量 x1 ,x 2 为非基变量

?1 0? ? 1 0 ?? 40 ? ? 40 ? -1 B ?? , X B =B0 b= ? = ? ? , X 0 ? (0, 0, 40, 60)T ? ?? ? 0 1? 0 1 ?? 60 ? ? 60 ? ? ?

114

返回总目录
C=(3,2,0,0)
?1 1 1 0 ? A= ? ? 2 1 0 1? ?
-1 0 -1 0

? 40 ? b= ? ? 60 ? ?

?1 0? (2)计算单纯行乘子 π 0 =C B B ? (c3 ,c 4 )B ? (0, 0) ? ? ? (0, 0) ?0 1? 目标函数当前值 ? 40 ? Z0 = π 0 b = (0,0) ? ? ? 0 ? 60 ?
(3)非基变量检验数

? 1 1? σ N =C N -π 0 N=(c1 ,c 2 )-π 0 (P1P2 )=(3,2)-(0,0) ? ? = (3, 2) ? 2 1?
max ?σ j /σ j >0? = ?3,2? =3

(4) 选择换入变量

?1 ? 2

x 1 为换入变量。计算 B-1P ? ? 1 0 ? ? 1 ? ? ? 1 ? ? 0 故 0 1 ? ?? ? ? ? 0 1?? 2? ? 2? ?
115

返回总目录 C=(3,2,0,0)
?1 1 1 0 ? A= ? ? 2 1 0 1? ?

? 40 ? b= ? ? 60 ? ?

? 40 ? X B =B b= ? ? ? 60 ?
-1 0

?1? B-1P1 ? ? ? 0 ? 2?

(5)确定换出变量 ? ? B0 ?1b ? ? B0 ?1b ? ? ? ? 40 60 ? 60 3 4 ? min ? , ?? , ?? ? B0 ?1P1 ? ? B0 ?1P1 ? ? ? 1 2 ? 2 ?? 3 4 ? ? 确定 x 4 为换出变量,主元素=2

? ?1 -1 -1 B1 = E 41B0 = ? ?0 ? ?

?1 (6) 用 P1 代替 P4得新可行基 B1 =(P3 ,P1 )= ? ?0
-1 ? ? ??1 0? ?1 2 ?? ?=? 1 ?? 0 1 ? ? ? ?0 2? ? -1 ? 2? ? 1? ? 2?

1? ? x 3 ,x1为基变量, 2?
x 2 ,x 4 为非基变量,

?1 ? ?0

0? ?1 ??? 1? ?0

1? ? 2?

重复以上步骤,进入第二循环

? ?1 ?? ? ?0 ?
116

-1 ? ? 2? 1? ? 2?

返回总目录 C=(3,2,0,0)
?1 1? ?1 1 1 0 ? ? 40 ? A= ? ? b= ? ? B1 =(P3 ,P1 )= ? 0 2 ? ? ? ?2 1 0 1 ? ? 60 ?

-1 ? ? 1 ? 2? -1 B1 = ? ? ?0 1 ? ? ? ? 2?

?1 (1) -1 X B =B1 b= ? ?0 ? ?

? 10 ? ? ? ? , X1 ? (30, 0,10, 0)T ? 30 ? ?1 ? ? ?1 2 ? (2) 3 -1 -1 π1 =CB B1 ? (c3 ,c1 )B1 ? (0,3) ? ? ? (0, ) 2 ?0 1 ? ? ? ? 2 ? 3 ? 40 ? Z1 = π1b = (0, ) ? ? ? 90 2 ? 60 ?
(3)

?1 ? 2 ? ? 40 ? 1 ? ? 60 ? ?? ? 2 ?

3 ?1 0 ? 1 3 σ N =C N -π1 N=(c 2 ,c 4 )-π1 (P2 P4 )=(2,0)-(0, ) ? ? =( , - ) 2 ?1 1 ? 2 2

?2 ?4

117

返回总目录 C=(3,2,0,0)
?1 1 1 0 ? ? 40 ? ? 10 ? ?1 1? -1 A= ? ? b= ? ? B1 =(P3 ,P1 )= ? ? X B =B1 b= ? 30 ? ?2 1 0 1 ? ? 60 ? ? ? ?0 2?
?1 ? ? ?1? ? 1 2 ? ? 1? ? 2 ? (4) 选择 x 2 换入变量 -1 B1 P2 ? ? ?? ? ? ? ? ? 0 ? 0 1 ? ? 1? ? 1 ? ? ? ? ? ? 2 ? ?2? ? ? B1?1b ? ? B1?1b ? ? ? ? 10 30 ? 10 3 1 ? min ? , ?? , ? ?? (5) ?1 ?1 ? ? B1 P2 ?3 ? B1 P2 ?1 ? ?1/ 2 1/ 2 ? 1/ 2 ? ?
-1 x 3 换出变量,主元素= (B1 P2 )3 ? 选择

?1 ? ?0 ? ?1 ?2 ? ?1 ? ?2

0? ? 1? ? 0? ? 1? ? ?

?1 1 ? ? x 2 ,x1 (6) 用 P2 代替 P3 得新可行基 B2 =(P2 ,P1 )= ? 1 2 ? ? ? 为基变量, ? 2 0 ? -1 ? ? 1 x 3 ,x 4 为非基变量,? ? ? 2 0?? 2 ? ? 2 -1? -1 -1 -1 1 ? ? B2 = E 32 B1 = ? ?=? ?? ? ? ?1 1 ? ? 0 1 ? ? -1 1 ? 进入第三循环. ? ? 118 ? 2?

1 2

返回总目录 C=(3,2,0,0)

-1? ?1 1 ? ?1 1 1 0 ? ? 40 ? -1 ? 2 A= ? ? b= ? ? B2 =(P2 ,P1 )= ? 1 2 ? B2 = ? ? 2 1 0 1? 60 ? ? ? -1 1 ? ? ? ?

? 2 ?1? ? 40 ? ? 20 ? ? ? ? , X 2 ? (20, 20, 0, 0)T ?? ? ?1 1 ? ? 60 ? ? 20 ? ? ? 2 ?1? (2) -1 -1 π 2 =CB B2 ? (c 2 ,c1 )B2 ? (2,3) ? ? ? (1, 1) ? ?1 1 ? ? 40 ? Z2 = π 2 b = (1,1) ? ? ? 100 ? 60 ? ?1 0? (3) σ N =C N -π 2 N=(c3 ,c 4 )-π 2 (P3 P4 )=(0,0)-(1,1) ? ? =(-1, -1) ?0 1? 非基变量对应的检验数全部非正, ?3 ?4 故当前解 X 2 =X* =(20, 20, 0, 0)T 即为最优解,
(1) X B =B-1b= 2 ? 相应的目标函数最优值

maxZ ? 100。
119

返回总目录

第3章 对偶规划与灵敏度分析
? ? ? ? ? 对偶线性规划 对偶定理 对偶最优解的经济解释——影子价格 对偶单纯形法 灵敏度分析

120

返回总目录
对偶理论是线性规划的重要内容之一。随着线性规划问题
研究的深入,人们发现对应于每个线性规划问题都伴生一个相 应的线性规划问题。 前者是由矩阵A,右端向量b和价值向量C定义的,称之 为原问题; 后者也是由相同的数据集合A,b和C构成的,称之为原

问题的对偶问题。
一对原问题和对偶问题是紧密关联的,它们不但有相同的 数据集合,相同的最优目标函数值,而且在求得一个线性规划

的最优解的同时,也同步得到对偶线性规划的最优解。对偶理
论深刻地指示了原问题和对偶问题的内在联系,由对偶问题引 伸出来的对偶解还有着重要的经济意义,是研究经济学的重要

概念和工具之一。
121

返回总目录

?对偶线性规划
?对偶问题的提出
例1 某工厂生产甲,乙两种产品,这两种产品需要在A、B、C三种 不同设备上加工。每种甲、乙产品在不同设备上加工所需的台时, 它们销售后所能获得的利润,以及这三种设备在计划期内能提供的 有限台时数均列于表。试问如何安排生产计划,即甲、乙两种产品 各生产多少吨,可使该厂所获得利润达到最大。
设备 A B C 利润(元/吨) 每吨产品的加工台时 可供台时数 36 40 76
122


3 5 9 32


4 4 8 30

返回总目录
设备
A B C 利润(元/吨)

每吨产品的加工台时
甲 3 5 9 32 乙 4 4 8 30

可供台时数
36 40 76

?3x1 +4x 2 ? 36 ?5x +4x ? 40 ? 1 2 4 2 (元) * ? X = ( , 8) maxZ=282 ?9x1 +8x 2 ? 76 3 3 ? x1 ? 0,x 2 ? 0 ? 4 即在计划期内甲产品生产 吨,乙产品生产8吨,可以使总利润 3 2 达到最大,为 元。 282
用图解法或单纯形法可求得最优解

假设计划期内甲乙两种产品各生产

x1 ,x 2 吨,

maxZ=32x1 +30x 2

3

123

返回总目录
现在从另一个角度来考虑该工厂的生产问题: 假设该厂的决策者打算不再自己生产甲、乙产品,而是把各 种设备的有限台时数租让给其他工厂使用,这时工厂的决策者应 该如何确定各种设备的租价。 设 y1 ,y 2 , y3 分别为设备A、B、C每台时的租价,

约束条件:把设备租出去所获得的租金不应低于利用这些设备自
行生产所获得的利润

?3y1 +5y 2 +9y3 ? 32 ? ? 4y1 +4y 2 +8y3 ? 30 ? y ? 0,y ? 0,y ? 0 2 3 ? 1

目标函数:所获租金总额尽量少.

minW=36y1 +40y2 +76y3
124

返回总目录
由此可得两个对称的线性规划: maxZ=32x1 +30x 2

minW=36y1 +40y2 +76y3 ?3y1 +5y2 +9y3 ? 32 ? ?4y1 +4y2 +8y3 ? 30 ? y ? 0,y ? 0,y ? 0 2 3 ? 1

4 * T X = ( , 8) 3

?3x1 +4x 2 ? 36 ?5x +4x ? 40 ? 1 2 ? ?9x1 +8x 2 ? 76 ? x1 ? 0,x 2 ? 0 ?

2 maxZ=282 3

7 19 2 * Y =( ,0, ) minW=282 6 6 3
? 36 ? ? ? minW=(y1 ,y 2 ,y 3 ) ? 40 ? ? 76 ? ? ? ? ?3 4? ? ? ? (y1 ,y 2 ,y 3 ) ? 5 4 ? ? (32,30) ? ? ?9 8? ? ? ? ? (y ,y ,y ) ? 0 ? 1 2 3
125

矩阵形式: ? x1 ? maxZ=(32,30) ? ? ? x2 ?

??3 4? ? 36 ? x1 ? ? ? ?? ?? 5 4 ? ? ? ? ? 40 ? ?? ? ? 9 8 ? ? x 2 ? ? 76 ? ?? ? ? ? ? x ?? 1 ? ? 0 ?? x 2 ? ?? ?

返回总目录

?对偶线性规划

maxZ=CX

? AX ? b 考虑如下具有“≤”不等式约束的线性规划问题? ?X ? 0
加入松弛变量XS=(xn+1,xn+2,…,xn+m)T以后可得标准型
若B是系数矩阵(A , I)中的一个可行基,

maxZ=CX+0X S ?AX ? I ? X S ? b ? ?X ? 0, X S ? 0

并假设(A , I)可表示为(B, N), maxZ=C B X B +C N X N 则线性规划问题可改写为 ? BX B +NX N =b ? ? X B ? 0, X N ? 0

X B =B-1b ,目标函数值 Z=CB B-1b , 可得基本可行解
-1 -1 若非基变量检验数 ? N =C N -CB B N ? 0 则 X B =B b 为最优解

126

返回总目录
因为基变量检验数 CB - CB B-1B ? 0 , 最优解判别准则又可表述为 (CB ,C N ) - CB B-1 (B,N) ? 0 。 上述表达式又可写成 (C,0) - C B-1 (A,I) ? 0 B 即 CB B-1A ? C C B B-1 ? 0,其中 CB B-1称为单纯形乘子。 所以当 X B =B-1b 为最优解,且单纯形乘子 CB B-1 用符号Y示时, 可以推得: ① YA ? C ② Y?0 ③ Yb=CB B-1b=CX 且由 AX ? b,Y ? 0 ? YAX ? Yb ,所以 Yb 只存在最小值。

由此可以得到另一个线性规划:

称之为原线性规划问题

minW=Yb ? YA ? C ? ?Y ? 0

maxZ=CX ? AX ? b ? ?X ? 0 的对偶问题,
127

返回总目录

? 线性规划问题标准型的对偶问题
考虑一个标准形式的线性规划问题

maxZ=CX ? AX=b ? ?X ? 0

由于任何一个等式约束都可以用两个不等式约束等价地表示,所以 标准形线性规划问题可等价表示为: maxZ=CX 它的对偶规划为:

?b? minW=(Y1 ,Y2 ) ? ? =(Y1 -Y2 )b ? -b ? ? ?A ? (Y1 ,Y2 ) ? ? =(Y1 -Y2 )A ? C ? ? ? -A ? ?Y ? 0,Y ? 0 ? 1 1

?? A ? ?b ? ?? ? X ? ? ? ?? -A ? ? -b ? ?X ? 0 ?
若令 Y=Y1 -Y2 线性规划标准型 的对偶规划为:minW=Yb

? YA ? C ? ? Y无约束

128

返回总目录

?对偶线性规划的求法
从任何一个线性规划出发,都可以求出相应的对偶规划,在 实际求解过程中,通常不通过求标准型,而是利用如下反映原始 问题与对偶问题对应关系的原始─对偶表:
原问题(或对偶问题) 目标函数maxZ 约束条件个数:m个
?? 第i个约束条件 ? ?? (i ? 1, 2,? m) ? ??

对偶问题(或原问题) 目标函数minW 对偶变量个数:m个
?? 0 第i个对偶变量yi ? ?? 0 (i ? 1, ? m) 2, ?无约束 ?

决策变量个数:n个
?? 0 第j个决策变量x j ? ?? 0 (j ? 1, ? n) 2, ?无约束 ?

约束条件个数:n个
?? 第j个约束条件 ? ?? (j ? 1 2, n) ? ,? ??

约束条件右端项 目标函数变量系数

目标函数变量系数 约束条件右端项

129

返回总目录
例2 写出下列线性规划的对偶问题

maxZ= 5x1 +4x 2 +6x 3

?2 ? x1 +2x 2 ? + x3 ? 3 ? x1 解:设对于原问题4个约束条件 ? ?-3x1 +2x 2 +x 3 ? -5 y1 ,y2 , y3 , y4 的对偶变量分别为 ? x -x +x =1 2 3 ? 1 由4个约束条件的类型,可知4个 ? x1 ? 0,x 2 ? 0,x 3无约束 ? 对偶变量分别为≤0,≥0,≥0和无约束;
又因为原问题有3个决策变量
的类型分别为≥,≤,=。 由此可得上述问题的对偶规划:

x1 ,x 2 , x 3 ,因此对偶规划有3个
minW=2y1 +3y 2 -5y3 +y 4 ? y1 + y 2 -3y3 +y 4 ? 5 ?2y +2y3 -y 4 ? 4 ? 1 ? y2 +y3 +y 4 ? 6 ? ? y ? 0, y ? 0, y ? 0, y 无约束 2 3 4 ? 1

约束条件,由3个决策变量的符号,可知对偶规划3个约束条件

130

返回总目录

?对偶定理
本节讨论几条重要的对偶定理,这些定理揭示了原始问题的解和
对偶问题的解之间的基本关系。 定理1 对偶问题的对偶是原问题。

证明:设原问题为 maxZ=CX

对偶问题为

minW=Yb ? YA ? C ? ?Y ? 0

改写对偶问题为

? AX ? b ? ?X ? 0

对偶问题的对偶为

max-W=Y(-b) ? Y(-A) ? -C ? ?Y ? 0

min-Z=-CX ?-AX ? -b ? ?X ? 0

maxZ=CX ? ? AX ? b ? ?X ? 0
131

返回总目录
定理2 弱对偶定理 若 X 是原(极大化)问题的可行解, Y 是对偶(极小化)问题的 可行解,那么 CX ? Yb

证明:因为 Y 是对偶问题的可行解,所以满足约束条 Y ? 0, ? C YA 且;又因为 X 是原问题的可行解,可得 X ? 0 , AX ? b ,
所以

CX ? YAX ? Yb 。

推论1 原(极大化)问题的最优目标函数值以对偶问题任一可行解的 目标函数值为上界。 对偶(极小化)问题的最优目标函数值以原问题任一可行解的目 标函数值为下界。 推论2 如果原问题没有上界(即maxZ→+≦),则对偶问题不可行。 如果对偶问题没有下界(即minW→-≦),则原问题不可行。
132

返回总目录

定理3

最优性定理

? 若 X 是原问题的可行解,Y 是对偶问题的可行解,而 ? ? ? ? ? 且两者的目标函数值相等,即 CX=Yb ,则 X 和 Y
分别是原问题和对偶问题的最优解。 证明:由弱对偶定理,对于原始问题的所有可行解 X ,

? ? ? 都有 CX ? Yb=CX 因此 X 是原问题的最优解。 ? ? 同理,对于对偶问题的所有可行解 Y ,都有 Yb=CX ? Yb
? 所以 Y 是对偶问题的最优解。
133

返回总目录
定理4 强对偶定理 如果原问题有最优解,那么对偶问题也有最优解,而且目标函数 值相等。

证明:设 X 是原问题的最优解,则它们对应的基B必有 ? C-CB B-1A ? 0 ,且松弛变量检验数 -C B B-1 ? 0 。

? ? 若定义Y=CB B-1 ,则 YA ? C,且 Y ? 0 , ? ? ? ? 因此 Y=CB B-1 为对偶问题的可行解,而且 CX=C B B-1b=Yb , ? 由最优性定理,Y=CB B-1 是对偶问题的最优解。
推论1 若原问题有一个对应于基B的最优解,那么此时的单纯形乘 子 Y=C B-1 是对偶问题的一个最优解。 B ? 根据这个推论我们可以在原问题的最优单纯形表中直接找到对偶

问题的最优解,即松弛变量检验数的相反数B B-1 C


134

返回总目录
例4 利用单纯形表求例1中原问题的最优解,并由最优单纯 形表推出对偶问题的最优解。 解:原问题线性规划模型为: maxZ=32x1 +30x 2

?3x1 +4x 2 ? 36 ?5x +4x ? 40 ? 1 2 ? ?9x1 +8x 2 ? 76 ? x1 ? 0,x 2 ? 0 ?
引入松弛变量 化标准形得:

x 3 ,x 4 , x 5 , maxZ=32x1 +30x 2
=36 ?3x1 +4x 2 +x 3 ?5x +4x +x 4 =40 ? 1 2 ? +x 5 =76 ?9x1 +8x 2 ? x j ? 0,j=1...5 ?
135

返回总目录
282 2 3

C CB XB b

32 X1 3 5 9

30 X2 4 4 8

0 X3 1 0 0

0 X4 0 1 0

0 X5 0 0 1

Θ 36/3
40/5 76/9 12/8/5 8/4/5

0
0 0 Z 0 32 0 Z 0 32 30 Z 0 32 30

X3
X4 X5 X3

36
40 76 0 12 8 4 256 4 4 5 278

32
0 1 0 0

30
8/5 4/5 4/5 22/5

0
1 0 0 0

0
-3/5 1/5 -9/5 -32/5

0
0 0 1 0

X1
X5 X3 X1 X2 X4 X1 X2

4/4/5
4/3 4/2

0
1 0 0 0

0
0 1 0 0

1
0 0 0 1/3

3
2 -9/4 7/2 1

-2
-1 5/4 -11/2 -2/3

3/4 4/3 8 2 282 3

1
0 0

0
1 0

-2/3
3/4 -7/6

0
0 0

1/3
-1/4 -19/6
136

Z

返回总目录
C CB 0 32 30 Z XB X4 X1 X2 b 3/4 4/3 8
282 2 3

32 30
X1 X2

0
X3

0
X4

0
X6

maxZ=32x1 +30x 2 =36 ?3x1 +4x 2 +x 3 ?5x +4x +x 4 =40 ? 1 2 ? +x 5 =76 ?9x1 +8x 2 ? x j ? 0,j=1...5 ?

0 1 0 0

0 0 1 0

1/3 -2/3 3/4 -7/6

1 0 0 0
*

-2/3 1/3 -1/4 -19/6

2 4 3 由最优表可知,原问题最优解 X = ( , 8,0, ,0) maxZ=282 3 3 4
? 1 同时不难得到原问题的最优基 ? 3 ?0 3 4? -1 ? ? ? 2 B ? ? ? 3 B=(P4, P1 ,P2 ) ? ?1 5 4 ? ? ?0 9 8? ? 3 ? ? ? 4 由强对偶定理的推论可得此时的单纯形乘子
* -1

1 0 0

?2? 3? 1 ? 3 ? ? ?1? 4?

的相反数。

7 19 Y =CB B ? ( , 0, )为对偶问题的最优解,即松弛变量检验数 6 6
137

返回总目录
定理5 互补松弛定理 ? ? 如果 X , Y 分别是原问题的对偶问题的可行解,那么 ? ? ? ? X 和 Y 为最优解的充要条件是 YX S =0 , YS X=0 Y 其中 XS 为原问题的松弛变量, S 是对偶问题的剩余变量。

? ? 通常称 YX S =0 , YS X=0 为互补松弛条件。
? 若令 Y ? (y ,y ,? y ) ? 1 2 m

XS ? (u1 ,u 2 ,? u m )T

? 则 YX S =0 的含义是:要么yi ? 0 ,要么 u i ? 0, i=1,2,? m.
? 若令

YS ? (v1 ,v 2 ,? v n )

? X ? (x1 ,x 2 ,? x n )T

? 则 Y X=0的含义是:要么x j ? 0,要么 S

v j ? 0, j=1,2,? n.
138

返回总目录
例5 已知线性规划问题: 其对偶问题的最优解。

maxZ=4x1 ? 3x 2 ? x1 +2x 2 ? 2 ? x - x ?3 2 ? 1 ?2x1 +3x 2 ? 5 ? ? ? x1 +x 2 ? 2 ?3x1 +x 2 ? 3 ? ? x1 ,x 2 ? 0 ?

Y=(1,0,0,0,1), min W ? 5
试用互补松弛定理找出原问题的最优解。 解:原问题的对偶问题为:

minW=2y1 +3y2 +5y3 +2y4 +3y5 ? y1 +y2 +2y3 +y4 +3y5 ? 4 ? ?2y1 -y2 +3y3 +y4 + y5 ? 3 ? y ? 0,i=1,2,3,4,5 ? i

? x1 +2x 2 =2 4 3 ? x1 = ,x 2 = , ? 5 5 ?3x1 +x 2 =3

由对偶问题最优解 Y=(1,0,0,0,1) 可知 y1 ? 0, y5 ? 0 , 由互补松弛定理,原问题的松弛变量 u1 ? 0, u 5 ? 0 解方程组 所以原问题最优解

X =(

*

4 3 , ), maxZ=5 5 5
139

返回总目录
定理6 原问题的检验数对应对偶问题的一个基本解。

证明:设B是原问题的一个可行基, 且 A=(B,N) 对偶问题可改写为 则原问题可以写为

maxZ=C B X B +C N X N ? BX B +NX N +X S =b ? ? X B ,X N ,X S ? 0

minW=Yb ?Y(B,N)-(YS1 ,YS2 )=(CB ,C N ) ? ? ?Y,YS1 ,YS2 ? 0 ?

其中 YS1 ,YS2 分别为原问题决策变量中基变量和非基变量所对应的对偶约束 的剩余变量。 对偶问题也可等价表示为:

minW=Yb

? YB-YS1 =C B ? ? YN-YS2 =C N ? Y=CB B-1 ,YS1 =0, YS2 = -(C N -CB B-1N) ? Y,YS1 ,YS2 ? 0 不难验证, 为对偶问题的一个基本解。

对原问题可行基B,可得可行解 X B =B b XN , XS 对应于 X B , 的检验数分别为 0, C N -CB B-1N, -CB B-1 。

-1

140

返回总目录

?对偶最优解的经济解释——影子价格
由强对偶定理可知,如果原问题有最优解 X * ,那么对偶 问题也有最优解Y * ,而且它们的目标函数值相等,即有:
* Z=CX* =Y*b=y1 b1 ? y* b 2 ? ? ? y* b m 2 m

其中 b=(b1 , b 2 ,? , b m )T 是线性规划原问题约束条件的右端 数据向量,它代表各种资源的拥有量。
* Y* =(y1 ,y* ,?, y* ) 为对偶问题最优解,它代表在资源最优 2 m

利用条件下对各种单位资源的估价,这种估计不是资源的市场 价格,而是根据资源在生产中所作出的贡献(如创造利润、产

值等)而作出估价,为区别起见,称之为影子价格(shadow
price)。
141

返回总目录
影子价格的大小客观地反映了各种不同资源在系统内的稀缺程度。

如果第i种资源供大于求,即在达到最优解时,该种资源没有用完,或

? 0,由互补松弛定理,在对偶最优解 Y * 中,第i种资源 * 的影子价格 y* ? 0。反之如果第i种资源的影子价格 yi ? 0 ,那么由互 i
松弛变量 u i

补松弛定理,原问题的第i个约束为严格等式,即 u i ? 0 ,这表明第i种
资源已经用完,成为稀缺资源。 资源的影子价格同时也是一种机会成本,在市场经济的条件下,当

某种资源的市场价格低于影子价格时,企业应买进这种资源用于扩大生
产;相反当某种资源的市场价格高于影子价格时,企业应卖出这种资源。 随着资源的买进卖出,企业资源的影子价格也将随之发生变化,一直到

影子价格与市场价格保持同等水平时,才处于平衡状态。
142

返回总目录

设备 每吨产品的加工台时 甲 乙 可供台时数

A B C
利润(元/吨)

3 5 9
32

4 4 8
30

36 40 76

maxZ=32x1 +30x 2 =36 ?3x1 +4x 2 +x 3 ?5x +4x +x 4 =40 ? 1 2 ? +x 5 =76 ?9x1 +8x 2 ? x j ? 0,j=1...5 ?

对偶最优解 Y* = ( , 0 , ) 6 6 7 * y1 = 其中 为设备A的影子价格, 6 在资源最优利用的条件下,设备A每增加

7

19

7 一个单位台时,可以使总利润增加 元。 6

4 2 * T 若设备A可供台时数=37,则 X = ( , 8) maxZ=282 3 3 2 3 T maxZ=283 5 * X = ( ,8 ) 6 3 4

143

返回总目录

?对偶单纯形法
第2章介绍的单纯形法是以保持原问题可行为条件,即不论

进行怎样的基变换,常数列 B-1b 必须保持非负。 利用对偶问题的对称性,我们从另一个角度来考虑求解原问
题最优解的方法,这种方法以保持对偶问题可行为条件,即不论 进行何种基变换,必须保持所有的检验数非正,同时取消原问题 必须可行的要求,即取消常数列的非负限制,通过基变换使原问 题在非可行解的基础上逐步转换成基本可行解,一旦原问题的基 本解可行,则该基本可行解也就是最优解,这就是对偶单纯形法

的基本思想。
原问题: 基本解 → 基本可行解(已为最优解) 可行解(保持所有的检验数非正)
144

对偶问题: 可行解 →

返回总目录

对偶单纯形法基变换的次序和一般单纯形法不同:

?一般单纯形法首先由最大增加原则确定换入变量 x k

,然

x 而用最小比值原则确定换出变量 l
?



对偶单纯形法则是先将具有负分量的基变量

x l 取出,作

为换出变量,然后确定某个非基变量

x k 作为换入变量。其

变换目的是在保持对偶问题可行性的前提下,使原问题的基

本解向可行解靠拢。

145

返回总目录
对偶单纯形法的计算步骤如下: (1)根据原始线性规划,列出初始单纯形表,检查b列数字和 检验行元素,若b列数字全部非负,检验数全部非正,则已经 求得最优解,停止计算。若b列中至少有一个负分量,检验数 全部非正,则转入(2)。 (2)确定换出变量。 根据 min{ (B b)i / (B b)i ? 0} ? (B b)l ,确定基变量 x l 作为换出变量。检验 x l 所在行各元素 a lj ,j=1,2,? n,
-1 -1 -1

若所有 a lj ? 0 ,则无可行解,停止计算。否则转入(3), (3)确定换入变量。
?σj ? σk ? ? min ? / a lj ? 0, j为非基变量下标 ? ? 按最小比值原则,若 ? a lj ? a lk ? ?

确定非基变量

x k为换入变量。

(4)以a lk为主元进行旋转变换,得新的单纯形表,重复

(2)-(4),直到求得最优解。
146

返回总目录
例6 用对偶单纯形法求解

minW=3x1 +2x 2 ?2x1 +3x 2 ? 18 ? x -x ? 2 ? 1 2 ? ? x1 +3x 2 ? 10 ? x1 ? 0,x 2 ? 0 ?

解:先化为标准型

max-W=-3x1 -2x 2 =18 ?2x1 +3x 2 +x 3 ? x -x -x 4 =2 ? 1 2 ? -x 5 =10 ? x1 +3x 2 ? x i ? 0,i=1,2,3,4,5 ?

max-W=-3x1 -2x 2

=18 ?2x1 +3x 2 +x 3 ? -x + x +x 4 = -2 2 对偶单纯形允许约束方程右端为负, ? 1 ? +x 5 =-10 ?-x1 -3x 2 因此可将方程2,3两端同乘-1, ? x i ? 0,i=1,2,3,4,5 ? 可得含单位矩阵的标准型:
147

返回总目录
据此列出初始单纯形表,并施行对偶单纯形法迭代步骤如下:
C CB XB b -3 x1 -2 x2 0 x3 0 x4 0 x5

0
0 0 -W 0 0 -2 -W 0 -3 -2

x3
x4 x5 x3 x4 x2 x3 x1 x2

18
-2 -10 0 8 -16/3 10/3 -20/3 4 4 2

2
-1 -1 -3 1 -4/3 1/3 -7/3 0 1 0

3
1 -3 -2 0 0 1 0 0 0 1

1
0 0 0 1 0 0 0 1 0 0

0
1 0 0 0 1 0 0 3/4 -3/4 1/4

0
0 1 0 1 1/3 -1/3 -2/3 5/4 -1/4 -1/4

-W

-16

0

0

0

-7/4

-5/4
148

可得最优解

* T X = (4, 2, 4) , max-W= -16, or minW=16

返回总目录

?灵敏度分析
一个标准形式的线性规划问题可由约束矩阵A,右端项

向量b,和价值向量C完全确定,假如一个线性规划问题对于
给定的数据集合A,b,C有最优解,则最优解 X B =B-1b 最优目标函数值 Z=C B-1b B ,其中B为最优基。 。

但是线性规划问题所对应的数据集合A,b,C常常是通
过预测或估计所得到的统计数据,在实际使用中,不免会有 一定的误差。而且随着市场环境,工艺条件和资源数量的改 变,这些数据完全可能发生变化。因此有必要来分析一下当 这些数据发生波动时,对目前的最优解,最优值或者最优基 会产生什么影响,这就是所谓的灵敏度分析。
149

返回总目录
灵敏度分析主要讨论如下二类问题: ?线性规划的数据集合在什么范围内波动将不影响最优解或最优基? ?若最优解发生变化,应如何用最简单的方法找到新的最优解。 为讨论方便,以下列出标准型线性规划问题最优单纯形表的一般形式, 其中B为线性规划问题的最优基: C C1 C2 … Cn

CB
CB1 CB2 : CBm

XB
XB1 XB2 : XBm

b

x1

x2



xn

B-1b
CBB-1b

B-1A=B-1(P1,P2,…,Pn)
C-CBB-1A
150

Z

返回总目录

?价值向量C的改变
当价值向量由 C=(CB ,CN ) ? C ? ΔC=(CB +ΔCB ,CN +ΔC N ) 时,

最优单纯形表发生变化的只是检验行的有关数据,其中基变量检 验数保持为零。非基变量检验数应修改为:
σ N =(C N +ΔC N )-(C B +?C B )B-1N=(C N -C BB -1N)+(ΔC N -ΔC BB -1N) =σ N +(ΔC N -ΔC B B-1 N)
-1 目标函数值应为 Z=(CB +ΔCB )B b 。

σ N =σ N +(ΔCN -ΔCB B-1N) ? 0 只要变化以后的非基变量检验数 那么原最优解仍然为最优。 至于目标函数值是否改变,取决于基变量价值系数的改变量 ΔC B

以下分别就价值系数对应非基变量或基变量两种情况加以讨论:
151

返回总目录
?若 c j 是非基变量x j 的价值系数, c 为该价值系数的改变量。那么 ?

在最优表中只有 x j 的检验数σ j 发生变化。

j

由 σ N =σ N +(ΔCN -ΔCB B-1N) ? 0只要 σ j =σ j +Δc j ? 0 即 Δc j ? ?σ j 就可以保持现行最优解仍为最优,由此可以确定价值系数 c j 的可变化范围。 若超出稳定范围,那么x j 的检验数 σ ? 0 ,当前解已不是最 j 优解。此时必须以修改后的单纯形表出发,重新进行单纯形迭代, 直至求出新的最优解。 ?若非基变量价值系数的变化超过稳定范围,则可使最优基B改变, 从而导致最优解 和最优值 X=B-1b

Z=CB B-1的改变。 b
152

返回总目录
? 若 c j 是某基变量 x j 的价值系数, ?c j 为价值系数的改变量。 由于 x j 为基变量,所以在最优表中所有的非基变量检验数均发生 了变化, 由 σ N =σ N +(ΔCN -ΔCB B-1N) ? 0 只要非基变量检验数:

σ N =σ N -Δc j (B-1 N) j ? 0



Δc j (B-1 N) j ? σ N

即可使最优解仍然保持为最优,

x 数矩阵中基变量 j 所在行中所有非基变量对应的系数。 由上式可得到一个联列不等式组,求解该不等式组就可得到价 值系数 c j 的可变动范围。 ?若基变量价值系数的变化超过稳定范围,则可使最优基B改变,
从而导致最优解 X=B-1b 的改变。但最优值 Z=(CB +?CB )B-1b 则 一定改变。
153

σ N 为原最优表中非基变量检验数,(B-1N) j 为最优表系 其中

返回总目录
例7 某工厂用甲乙两种原料生产A,B,C,D四种产品,每种产品的 利润,现有原料数及每种产品消耗原料定额如表所示: 产品(万件)
原料(公斤) 甲 乙 利润(万元/万件) 供应量

A 3 0 9

B 2 0 8

C 10 2 50

D 4 1/2 19
18 3

问应该怎样组织生产,才能使总利润最大,若产品A或C的利润产 生波动,波动范围多大时,原最优解保持不变? 解:设生产A,B,C,D四种产品 各 x1 , x 2 , x 3 , x 4 万件,则此问题的 ?3x1 +2x 2 +10x 3 +4x 4 ? 18 ? 线性规划模型为: 2x 3 + 1 x 4 ? 3 ? 2

maxZ=9x1 +8x 2 +50x 3 +19x 4

? x ? 0,j=1,2,3,4 ? j

154

返回总目录
标准化,引入松弛变量x5,x6,, 利用单纯形表求解:
C CB 0 0 XB X5 X6 B 18 3 9 X1 3 0 8 X2 2 0 50 X3 10 2 19 X4 4 1/2 0 X5 1 0 0 X6 0 1 θ 9/5 3/2 1 -

Z
0 50 Z 9 50 Z 19 50 Z X4 X3 X1 X3 X5 X3

0
3 3/2 75 1 3/2 84 2 1 88

9
3 0 9 1 0 0 2 -1/2 -4

8
2 0 8 2/3 0 2 4/3 -1/3 -2/3

50
0 1 0 0 1 0 0 1 0

19
3/2 1/4 13/2 1/2 1/4 2 1 0 0

0
1 0 0 1/3 0 -3

0
-5 1/2 -25 -5/3 1/2 -10 2 6

2/3 -10/3 -1/6 4/3 -13/3 -10/3

* T X = (0,0,1,2) ,

即最优生产方案是生产C产品1万件,D产品2万件, maxZ=88 不生产A,B两种产品。可得最大利润为88万元。

155

返回总目录
最优表:
CB 19 50 Z C XB X4 X3 B 2 1 88 9 X1 2 -1/2 -4 8 X2 4/3 -1/3 -2/3 50 X3 0 1 0 19 X4 1 0 0 0 X5 0 X6 θ 2/3 -10/3 -1/6 4/3 -13/3 -10/3

? Δc ? 2 1 1 1 4 2 13 10 ? 3 Δc3 (B-1 N)3 ? Δc3 ( ? , ? , ? , ) ? ( ?4, ? , ? , ? ) ? ? 2 3 6 3 3 3 3 ? Δc3 ? 26 5 ?Δc3 ? ?5 / 2 ? ? ?c3 ? 2 或 47.5 ? c3 ? 52 时 即当 ? 2
' -1

(1)若A产品的利润 c1 ? 9,有改变量 ?c1 。因为 x 1为非基变量, 由 Δc j ? ?σ j 推得 Δc1 ? ?? 1 ? 4 或 c1 ? 13 (万元)时 * T ' -1 原最优解 X = (0,0,1,2) 不变,最优利润值 Z =CB B b=88(万元)也 不变。 (2)若C产品的利润 c3 ? 50 ,有改变量 ?c3 。因为 x 3为基变量, 由 Δc (B-1 N) j ? σ N 推得 ? Δc ? 8
j

3

? 2? 原最优解不变,最优利润值 Z =CB B b=(19,50+?c3 ) ? ? =88+?c(万元) 3 1? ? 156

返回总目录

?右端项向量b的改变
当右端项向量b由 b ? b+?b 时,改变的只是表中右端常数列。 此时基变量 X 'B =B-1 (b+?b) ,目标函数值 Z' =CB B-1 (b+?b) 。 而检验行的检验向量保持不变。 右端项向量b的波动会使最优解和最优目标函数值发生变化,但 原最优解的检验向量仍能保持非正。为了使B可行,只要 -1 * X' =B-1 (b+?b)=B-1b+B-1?b=X* ? B-1?b ? 0 或
B

B ?b ? ?X

若 X* ? B-1?b ? 0,因为检验向量仍保持非正,因此可用对偶 单纯形法再次进行迭代,直到求得新最优解。 ?右端列向量b变化时,最优解X=B (b+?b) 和最优值 Z=CB B-1 (b+?b) 一定改变。因此我们主要讨论右端列向量b变化时,最优基B是否改 变
-1

157

返回总目录
在例7中,若想增加甲种原料,问增加多少时原最优基不变? ? Δb ? Δb1 ,则Δb= ? 1 ? 解:设甲种原料的改变量为 ? 0 ? -1 * 由 B ?b ? ?X 即 ? 2 ? 例8

-10 ? ? Δb ? ? Δb1 ? ? 2? 3 ? 1 =? 3 ? ? -? ? ? ?? 4 ?? 0 ? ? 1 ? ?1? - Δb1 ? ? 3 ? ? 6 ? 由此可以推得, ?3 ? Δb ? 6 即当 15 ? b ? 24 时,原最优基 1 1
不变。

? 2 ? 3 -1 B Δb ? ? ? -1 ? 6

C

9

8

50

19

0

0

CB
19 50 Z

XB
X4 X3

B
2 1 88

X1
2 -1/2 -4

X2
4/3 -1/3 -2/3

X3
0 1 0

X4
1 0 0

X5

X6

θ

原料 (公斤) 甲 乙

供应 量 18 3
158

2/3 -10/3 -1/6 4/3 -13/3 -10/3

返回总目录
此时最优解



? 2? ? ? ?x ? 2? ' -1 3 4 X B =B (b+Δb)= ? ? +Δb ? ? 1 ? 1 ? ?x ?1? 3 ?- ? ? 6?

最优目标函数值

1 2 ' X =(0,0,1- Δb1 ,2+ Δb1 ) 6 3

?2 ? Δb1 ? 13 ' =C B-1(b+Δb)=88+(19,50)? 3 Z ? ?=88+ Δb1 (万元) B 3 ? - 1 Δb ? ? 1? ? 6 ?
C CB 19 50 Z XB X4 X3 B 2 1 88 9 X1 2 -1/2 -4 8 X2 4/3 -1/3 -2/3 50 X3 0 1 0 19 X4 1 0 0 0 X5 0 X6

θ

2/3 -10/3 -1/6 4/3 -13/3 -10/3

?2 ? ? Δb1 ? ? 3 Δb1 ? -1 ? B ? ?=? ? 0 ? ? - 1 Δb ? ? 1? ? 6 ?
159

返回总目录

?约束矩阵A的改变
约束矩阵A的改变可能导致不同的最优解和最优基.以下只涉 及两种较简单的情形: ? 增加或减少一个变量, ? 增加或减少一个约束条件。 maxZ=CX

? AX=b 以下讨论假设原线性规划问题 ? ?X ? 0 -1
?B b? 有一个最优解 X = ? ? ? 0 ?
*

且约束矩阵被划分为

A=(B,N) ?

其中B为最优基, maxZ=C B X B +C N X N

? BX B +NX N =b ? ? X B ? 0, X N ? 0
160

返回总目录
? 增加或减少一个变量 (1)增加一个新变量 假设在获得原线性规划的最优解之后,又发现了一个新变 量 x n+1,其对应的价值系数为 cn+1 ,在新的约束矩阵中对应的 系数列向量为 Pn+1,于是可得如下新的线性规划问题:

? X* ? 设 x n+1 ? 0 ,则 X = ? ? ?0?
'

maxZ=CX+c n+1x n+1 ?AX+Pn+1x n+1 =b ? ?X ? 0, x n+1 ? 0

为新线性规划问题的一个可行解。 因此可在此基础上开始单纯形法,求新的最优解。 如果 ? n+1 ? 0 ,则含 x n+1

? X* ? ? 0 的当前解 X' = ? ? 是新问题的最优解。 ?0 ?

否则以 x n+1 为换入变量进行基变换,继续使用单纯形算法为新的线 性规划寻求一个最优解。
161

返回总目录
(2)减少一个变量 如果必须把某个变量 作量去寻求新的最优解。
?

xi

从决策变量中去掉,那么原最优解在

新的线性规划中一定发生改变。我们讨论的目标是如何用最小的工 如果原最优解中的 如果原最优解中的

x i ? 0 ,则只需将 x i 从原最优解中剔除即
(此时x i 必为基变量),则必须重新计 xi ? 0

可保持最优。
?

算新的解。为此可建立一个辅助线性规划:

minW=x i ? AX=b

由于约束方程组没有改变,因此原最优解 ? ?X ? 0 在辅助线性规划中可以作为初始基本可行解用 于单纯形算法。如果辅助线性规划最优解的目 标函数值为零,则用此最优解剔除 x i ? 0 以后,可得新的线性规划问题 的一个初始基本可行解,经有限次迭代,即可求出新问题的最优解。否 则从原来问题中去除 x i 而得到的新的线性规划必定是不可行的。
162

返回总目录
?增加或减少一个约束 (1) 增加一个约束 如果在原来的线性规划的基础上再加入一个新的约束条件, 不妨假设此附加的约束条件为不等式形式,即 a m+1X ? b m+1 其中a m+1 是n维行向量, b m+1为右端项系数, maxZ=CX 于是新的线性规划变成

maxZ=CX ? AX=b ? ?X ? 0

? AX=b ? ? ?a m+1X ? b m+1 ?X ? 0 ?

为了求解有附加约束条件的新问题,可以在附加不等式约束左端 加上一个松弛变量 x n+1 , maxZ=CB X B ? CN X N 并考虑如下线性规划问题: ? B X + N X =b

? ?(a m+1 )B X B +(a m+1 ) N X N + x n+1 =b m+1 ?X ,X ? 0,x ? 0 n+1 ? B N

B

N

163

返回总目录
其中 (a m+1 ) B , (a m+1 ) N 是 a m+1 中对 应于基变量 X B 和非基变量 X N 的子向量,由此可以在原来最优 基B的基础上定义一个新的基。

maxZ=CB X B ? C N X N =b ? B XB + N X N ? ?(a m+1 )B X B +(a m+1 ) N X N + x n+1 =b m+1 ?X ,X ? 0,x ? 0 n+1 ? B N

0? ? B B?? ? -1 B-1 0? ? ? ? (a m+1 ) B 1 ? 易证 B 是非奇异矩阵,其逆阵 B ? ? -(a m+1 ) B B-1 1 ? ?
按新基可以定义有附加约束条件新问题的一个基本解
-1 ? b ? X B =B ? ? , X N =0 ? b m+1 ?

该基本解不一定是可行解,因为不一定满足非负条件,但是由于 B是原线性规划问题的最优解,因此不难证明,即使对有附加约束 条件的线性规划是不可行的,但都能保证该线性规划的对偶规划是 可行的。
164

返回总目录
因为对应于 B 的非基变量检验数

? B-1 ? N ? σ N =C N -(CB ,0)B ? ? =C N -(CB ,0) ? -(a m+1 ) B B-1 ? (a m+1 ) N ? ? ? N ? -1 =C N -(CB B ,0) ? =C N -CB B-1N ? 0 ? (a m+1 ) N ? ?
-1

0?? N ? ?? ? 1 ? ? (a m+1 ) N ?

结论:如果由新基定义的基本解

? XB ? X= ? ? ? 0 ?

?是非负的。那么该基本解就是有附加约束条件的新线性规划问题的

最优解。 ?不满足非负条件。那么至少有一个基变量小于零,此时可用对偶单 纯形法求出新问题的最优解。

165

返回总目录

?

减少一个约束 在原来线性规划的基础上,去掉一个约束条件的情况比较复杂, 因为单纯形法是通过旋转运算实现基变换的,线性规划的旋转运 算使每行元素成为其他各行元素的线性组合。因此如果要减少一 个约束条件,那么原来的运算结果很难加以利用。一般情况下将 不得不从头求解减少了一个约束条件的新的线性规划问题,好在 减少一个约束条件可以大大地简化计算步骤。

166

返回总目录
例9 在例7中,若考虑生产另一种产品E,已知每生产1万件E产

品要消耗甲原料3公斤,乙原料1公斤,那么,E产品的每万件利润为 多少时才有利于该种产品投产? 若假设该工厂又增加了用电量不超过8千瓦的限制,已知生产A、 B、C、D四种产品各1万件分别耗电4、3、5、2千瓦,问此约束是 否改变了原最优决策方案? 解:(1)设生产E产品x7万件,1万件E产品的利润为c7万元, 则数学模型变为:

maxZ=9x1 +8x 2 +50x 3 +19x 4 ?3x1 +2x 2 +10x 3 +4x 4 ? 18 ? 2x 3 + 1 x 4 ? 3 ? 2 ? x ? 0,j=1,2,3,4 ? j

maxZ=9x1 +8x2 +50x3 +19x4 +c7 x7 ?3x1 +2x 2 +10x3 +4x4 +x5 +3x7 =18 ? ?? 2x 3 + 1 x 4 +x 6 +x7 =3 2 ? x ? 0,j=1,2,3,4,5,6,7 ? j
167

返回总目录
已知X* = (0,0,1,2,0,0)T是原问题的最优解,若令 x ? 0 , 7 * ?X ? 则 X= ? ? 是现问题的一个可行解,但未必是最优解。 ?0 ? 若要E产品投产,即 x 7 ? 0 ,则其检验数 σ 7 ? 0 ,即

?2 ?3 -1 σ 7 =c 7 -C B B P7 =c 7 -(19,50) ? ? -1 ? 6

? 4? 10 ? - ? ? 3? ?- ? 49 3 ? 3 ? =c 7 >0 ? ? ? =c 7 -(19,50) 3 4 ? ?1? ?5? ? ? 3 ? ?6? 49 得每万件E产品利润 c > 万元时,有利于生产E产品。 7 3
C CB XB B 9 X1 8 X2 50 X3 19 X4 0 X5 0 X6 θ

19 50
Z

X4 X3

2 1
88

2 -1/2
-4

4/3 -1/3
-2/3

0 1
0

1 0
0

2/3 -10/3 -1/6 4/3
-13/3 -10/3
168

返回总目录
例如当 c7 =17>

x7 得 增加新变量

49 万元时,代入原线性规划的最优单纯形表, 3
的单纯形表, 其中
-1

? 2 / 3 ?10 / 3 ?? 3 ? ? ?4 / 3 ? B P7 ? ? ?? ? ? ? ? ?1/ 6 4 / 3 ?? 1 ? ? 5 / 6 ? ?
50 X3 19 X4 0 X5 0 X6 17 X7 θ

C CB XB B

9 X1

8 X2

19
50 Z 19 17 Z

X4
X3 X4 X7

2
1 88 18/5 6/5
88 4 5

2
-1/2 -4 6/5 -3/5 -18/5

4/3
-1/3 -2/3 4/5 -2/5 -2/5

0
1 0 8/5 6/5 -4/5

1
0 0 1 0 0

2/3
-1/6 -13/3 2/5 - 1/5 -21/5

-10/3
4/3 -10/3 -6/5 8/5 -22/5

-4/3
5/6 2/3 0 1 0

由此可的新的最优解

18 6 为生产 5 万件D产品和 5

X' =(0,0,0, ,0,0, ) ,即最优生产方案
5
169

18 6 5 5 件E产品,总利润为 88 4 万元。

返回总目录
(2) 假设工厂又增加了用电量不超过8千瓦,且生产A、B、C、

D四种产品各1万件分别耗电4、3、5、2千瓦用电量限制,则相当于
原问题约束方程组增加了一个约束方程 增加松弛变量 x 7 ,得

4x1 +3x 2 +5x3 +3x4 ? 8

4x1 +3x 2 +5x3 +3x 4 ? x7 ? 8

利用原线性规划最优单纯形表,增加一行和一列得一张新表,施
行初等变换,使基变量 x 4 ,x 3 ,x 7 对应的系数列向量为单位矩阵,若变 换结果使基变量取了负值,则对应的基不是可行基,要用对偶单纯形 法进行了基变换,并求得最优解,否则变换结果已为最优解。

170

返回总目录
C CB XB B 9 X1 8 X2 50 X3 19 X4 0 X5 0 X6 0 X7 θ

19
50 0 Z 19 50 0

X4
X3 X7 X4 X3 X7

2
1 8 88 2 1 -1

2
-1/2 4 -4 2 -1/2 5/2

4/3
-1/3 3 -2/3 4/3 -1/3 2

0
1 5 0 0 1 0

1
0 2 0 1 0 0

2/3
-1/6 0 -13/3 2/3 -1/6 -1/2

-10/3
4/3 0 -10/3 -10/3 4/3 0

0
0 1 0 0 0 1

Z
19 50 0 Z X4 X3 X5

88
2/3 4/3 2
79 1 3

-4
-16/3 -4/3 -5 -77/3

-2/3
4 -1 -2 -18

0
0 1 0 0

0
1 0 0 0

-13/3
0 0 1 0

-10/3
-10/3 4/3 0 -10/3

0
4/3 -1/3 -2 -26/3

2 4 可见增加用电约束以后,最优生产方案是 万件C产品, 万件D 3 3 产品,总利润为79 1 万元,比原问题的最大利润减少 8 2 。

3

3

171

返回总目录

第4章 运输问题
? 运输问题及其数学模型 ? 表上作业法 ? 产销不平衡的运输问题

172

返回总目录
运输问题是在实际应用中经常会遇到的一类线性规划问题。从

理论上讲运输问题也可以用单纯形方法来求解。但是由于在运输问
题的数学模型中,约束方程的系数矩阵具有特殊的结构。因此,存 在一种比单纯形法更为简便的方法——表上作业法。

表上作业法通过定制的运输表确定最优调运方案,但其本质仍 然是单纯形法,其主要步骤是:首先需要确定一个初始调运方案

(初始基本可行解),然后检验现行调运方案(现行基本可行解)
是否最优,若非最优,则需对现行调运方案(现行基本可行解)进 行改进等几个阶段。只是表上作业法对单纯形法作了适当的修改, 从而提高了计算的效率。
173

返回总目录

?运输问题及其数学模型
运输问题的一般提法是:某种物质(粮食、棉花、煤炭等)有m 个产地 Ai (i=1,2? m) ,其产量是 a i (i=1,2? m) ;有n个销 地 B j (j=1,2? n) ,其销量(或需求量)是 b (j=1,2? n) 。 j 现在需要把这种物质从m个产地运送到n个销地。若从 A i 运到
B j 的单位运价为

c ij。

又限定产销平衡,即

? a =? b
i i=1 j=1

m

n

j



问应如何制定调运方案可使总费用最小?

174

返回总目录

上述已知条件可用下面的表格来表示。
销地 产地

B1 A1
A2 c11
c21

B2 c12

?
?

Bn c1n

产量

a1 a2

c22

?
?

c2n

?
Am

?
cm1
b1

?
cm 2

?
cmn
m

?
am
? ai ? ? b j
i ?1 j ?1 n

?
?

销量

b2

bn

175

返回总目录
如果用 x ij 代表从第i产地运往第j销地的物质单位数量

(i=1,2 m;j=1,2,…,n),Z为总运费,那么求解上述
使总运费最小的运输问题。可以用下列数学模型描述:

minZ= ?? cij x ij
i=1 j=1

m

n

使总运费达到最小

? n ? x ij =a i i=1,2? m. 从每一个产地运往各个销地的物 ? 质数量之和等于该产地的产量 j=1 ? ? m 从各个产地运往每一个销地的物质 . ? ? x ij =b j j=1,2? n. 数量之和等于该销地的销量 ? i=1 ? x ij ? 0, i=1,2,? ,m; j=1,2,? ,n 运输量非负 ? ? ?
176

返回总目录
运输问题的线性规划模型具有
特殊的结构,其约束方程组的系数 矩阵A具有如下形式:

m×n个决策变量,m+n个约束条件,

? n ?? x ij =a i ? j=1 ? m ? x =b ? ? ij j ? i=1

i=1,2 ? m. j=1,2 ? n.

? x11x12 ? x1n x 21x 22 ? x 2n ?? x m1x m2 ? x mn

1 1

1 1 1

?1
?
1 1 1

m行

A=
1 1 1

?1
?
n行 1
177

?
1

1

1

?
1

返回总目录
x11x12 ? x1n x 21x 22 ? x 2n ?? x m1x m2 ? x mn
1 1

?1

1 1

?1
?
1 1 1

m行

A=

1 1

1 1

?1
?
n行
1

1

?
1

?
1

? 该矩阵的元素全部为0或1。每一列只有2个元素为1,其余为0。 若用 Pij 表示决策变量 x ij 的系数列向量,则在 Pij 中第i个和第 m+j 个元素为1,其余为0。我们也可以用两个单位向量之和来

表示。即:

Pij =ei +e m+j
其中 e i 和 e m+j 分别为第i个元素和第m+j个元素为1的单位向量。
178

返回总目录
通过对运输问题的数学模型约束矩阵A的特殊结构作进一步分 析,还可以发现矩阵A的秩为m+n-1,即R(A)=m+n-1。 这是因为系数矩阵A的前m个行向量之和减去后n个行向量之 和恰好为零向量。即矩阵A的m+n个行向量线性相关。因此 R(A)<m+n。再将矩阵A的第2,3,…m+n行与 x11x12 ? x1n x 21x 31 ? x m1 所对应的列的交叉处的元素构成一个m+n-1阶子式。
?

x11x12 ? x1n x 21x 22 ? x 2n ?? x m1x m2 ? x mn
1 1

1 1 ?

?1
1 1

?1
?
1 1

? ? ? m-1 ? ?
1 1

D?

1 1 ? 1 ? ?? ? ?

1

1

?1
?
1

? ? ?n ? ?

1 1

1 1

1 1

? ?? ? ?

?
1

n

m-1

?
1

因为D=±1,所以R(A)=m+n-1
179

返回总目录

? 表上作业法
用表上作业法求解运输问题主要有三个步骤。
? ? 首先用最小元素法或伏格尔法确定初始基本可行解(初试调运 方案。 然后用闭回路法或位势法确定非基变量检验数,以判断当前 的基本可行解(当前调运方案)是否最优。如果已为最优则 停止计算。否则转入下一步, ? 用闭回路法对基本可行解(调运方案)进行调整。

由此可见表上作业法的求解思路与单纯形法基本一致。但其
求解过程都在运输表格上完成。而且使用的方法也很特殊。以下 对此作专门介绍。

180

返回总目录

? 确定初始基本可行解
求运输问题的初始基本可行解有多种方法。在此我们只介 绍最小元素法和伏格尔法两种方法。为了确定初始基本可行解, 首先必须画出运输问题的基本表格。即调运表和运价表。
调运表
销地 产地

B1

B2

?

Bn

产量

运价表
销地 产地

B1
c11 c21

B2 c12

? ? ?

Bn c1n

A1
A2

a1 a2
?

A1
A2

?
Am
销量

c22

c2n

am b1

?
Am

?
cm1

?
cm 2

?
?

?
cmn
181

b2

?

bn

返回总目录
在实际计算中,为了方便通常将调运表和运价表合二 为一,综合为下列运输表。 运输表
销地
产地

B1

B2

?
c12 c22

Bn

产量
c1n c2n
a1

A1

c11 c21

? ?
? ?

A2

a2

?
Am

?
cm1

?
cm2

?
cmn
am

? ?
bn

销量

b1

b2

182

返回总目录
1.最小元素法 最小元素法的基本思路是以运价最低者优先为原则安排初始的 调运方案,即从单位运价表中最小运价处开始确定供销关系。 若产量大于销量,则用加工厂的产量满足对应销地的全部日销 量,在对应的空格内填入相应的调运量。并用垂直直线划去销售地 所在列,表明该销地的日销量已经全部满足,同时从对应加工厂的 日产量中减去调运量。 反之,若产量小于销售量。则把加工厂的日产量全部分配给对 应的销售地。在对应空格填入调运量。用水平直线划去加工厂所在 行,并从对应销地的日销量中减去调运量。 依次类推,逐步推出初始方案。 由于最小元素法已经考虑到了运价最低者优先为原则,因此所 求的初始基本可行解通常比较接近最优解。经过若干次调整即可求

得最有解。
183

返回总目录
例1 某公司经销甲产品。下设三个加工厂A1,A2,A3,每

天把产品分别运往四个销地B1,B2,B3,B4。各加工厂的
日产量,各销地的日销量以及从各加工厂运送单位产品至各 销售地的运价如下表:
单位:千元/吨
销地
产地

B1
3 1 7 3

B2
11 9 4 6

B3
3 2 10 5

B4
10 8 5 6

日产量(吨)

A1 A2 A3
日销量(吨)

7 4 9

问该公司应如何确定调运方案,在满足各销地需求量的 前提下可使得总运费最小?
184

返回总目录
为了用最小元素法确定初始基本可行解,可先画出综合运输表。 然后按以下步骤确定初始调运方案。 ① 从全部单位运价中找出最低单位运价(若有两个以上最低单 位运价,则可在其中任选其一)。然后比较最低运价所对应的加工 厂的日产量和销地的日销量,并且确定第一笔供销关系。
销售地 加工厂

B1
3 1

B2
11 9 4

B3
3 2 10

B4
10 8 5

产量(吨)

A1 A2

7 4 -3 9

3
A3
销量(吨)

7

3


6

5

6
185

返回总目录
② 在未被划去的单位运价中再找寻最低运价,比较最低运价对应 的加工厂的日产量(或剩余量)和销地的日销量(或尚缺量)来确 定供销关系。基本原则与①中描述过程相同。

销售地 加工厂

B1
3 1

B2
11 9

B3
3 2

B4
10 8 5

产量(吨)

A1 A2

7 4 -3 9

3
A3
销量(吨)

1
7 4 10



3


6

5 -1

6
186

返回总目录
重复步骤②可逐个确定从加工厂到销地的供销关系。基本原则 是在空格内内每填入一个调运量必须划去一行或一列。填入最后一 个调运量后则同时划去一行和一列.这样在运输表中共计填入了m +n-1个数字。这些数字对应了一个初始基本可行解。

销售地 加工厂

B1
3 1

B2
11 4 9

B3
3 3 2

B4
10 8 3 5

产量(吨)

A1 A2

7 -4 4 -3


3
A3
销量(吨)

1
7 6 4 10 9 -6



3
① ④

6


5 -1

6 -3
187

返回总目录
所填入的m+n-1=3+4-1=6个数字为对应初始基本可行解的 6个初始基变量的值。即 对应的总运费为Z=4×3+3×10+3×1+1×2+6×4+3×5=86(千元)
销售地 加工厂

x13 =4,x14 =3,x 21 =3,x 23 =1,x 32 =6,x 34 ? 3
B1
3 1

B2
11 4 9

B3
3 3 2

B4
10 8 5 3

产量(吨)

A1 A2

7 -4 4 -3


3
A3
销量(吨)

1
7 6 4 10 9 -6



3


6


5 -1


6 -3
188

返回总目录
? 必须补充说明的是:利用最小元素法确定初始调运方案过

程中,可能出现最低单位运价对应的产地的产量和销地的销量 恰好相等的情形。此时在运输表中填入一个数字后,必须同时 划去产地所在行和销地所在列,这和每填入一个数字只划一条 直线的基本原则相违背(最后一个数字除外)。这时我们称运 输问题出现了退化。

为了使运输表中有m+n-1个数字格。需要添加一个“0”
调运量,它的位臵可在同时划去的那行或那列的任一空格处。 这个“0”调运量是不可缺少的。因为运输问题的基本解中基变

量的个数必须是m+n-1个。不能多,也不能少。出现了数字
为0的数字格只是说明在初始基本可行解中有一个基变量为零。 即该初始基本可行解是退化解。

189

返回总目录
2.伏格尔法(Vogel)。 最小元素法给定初始调整方案是以局部观点考虑运价最低 者优先的原则。这可能造成整体的不合理。 因为可能存在这样的情形:某单位运价在整个单位运价表 中可能并不是最低的,但是它在所在行(或所在列)中是最低

运价,而且它与同行(或同列)中的次最低运价相差非常显著。
因此就该行(或该列)而言,如果我们不慎采用了次最低 运价,而不是最低运价,那么总运费就会惩罚性地增加。我们

通常把每行或每列的次最低运价与最低运价之差额称为罚金成
本(Penalty cost)。 为了避免在总运费总增加过多的罚金成本。伏格尔法确定 初始基本可行解的基本思路是:罚金成本最高的行或列中运价 最低者优先考虑。其基本步骤为:
190

返回总目录
① 计算出每行(列)的罚金成本,并填入附加的最右列(最下行)。从所 有的罚金成本中找出最高值。选择它所在行(列)的最低运价。比较最 小运价对应的加工厂的日产量和销售地的日销量的大小,确定第一笔 供销关系。
销售地
加工厂

B1
3 1

B2
11 9

B3
3 2

B4
10 8

日产量

罚金成本

A1
A2 A3
销量 罚金成本

7
4 9 -6

0
1 1

7
3 2

6 6

4
5 1

10
6 3

5



5

191

返回总目录
②对未划去的单位运价再分别计算各行(列)的罚金成本。再从 所有的罚金成本中找出最高值。选择它所在行(列)的最低运价。 确定第二笔供销关系。
销售地
加工厂

B1
3 1

B2
11 9

B3
3 2

B4
10 8

日产量

罚金成本

A1
A2 A3
销量 罚金成本

7
4 9-6

0
1 1


1 2

7
6 3 2 6

4
5 1

10


5
6 -3 3





5

192

返回总目录
③重复步骤②,直至求得求得初始调运方案。与最小元素法相同,最 后表中应有m+n-1个数字格。对应初始基本可行解的m+n-1个基变量。

x13 =5,x14 =2,x 21 =3,x 24 =1,x 32 =6,x 34 ? 3 总运费=85(千元)
销售地 加工厂

B1
3 1 3 7

B2
11 5 9 4 6 6 5


B3
3 2 2 1 10

B4
10 8 5

日产量

罚金成本

A1 A2 A3
销量 罚金成本

7-5 0 0 7 4-3 1 1 6



5 1
1 ④
-1 6-3

9-6

1 2


3 2
2 ③

3

193

返回总目录
3.用上述两种方法求解的初始调运调运方案为运输问题的一个 基本可行解。

由运输问题数学模型的特征可知。运输问题约束条件中
独立的方程数只有m+n-1个。因此运输问题基本可行解中基 变量的个数也一定是m+n-1个。 用最小元素法或伏格尔法求得的初始调运方案中有m+n1个数字格。它们对应运输问题可行解中m+n-1个非负分量, 其他空白格对应可行解中的零分量。 要证明初始调运方案为运输问题的基本可行解,只需证 明可行解中m+n-1个非负分量为基变量。或这m+n-1个非 负分量的系数列向量线性无关即可。

194

返回总目录
若运输表中确定的一个非负分量为 量为 当确定了

x i1 j1
1

,则它对应的系数列向

Pi1 j1 =ei1 +em+j1

x i1 j1 的值以后,将划去 Ai

所在行或 B j 所在列。其以 1
1 1

后再确定的非负分量的系数列向量中将不可能再出现 e i 或 e m+j , 因此 Pi j =ei +em+j 不可能用其后非负分量的系数列向量线性表示。 11 1 1 示。 类似确定的第二个,第三个,直至第m+n-1个非负分量。它们 的系数列向量也不可能用其后的非负分量的系数列向量的线性组合表 示。因此,这m+n-1个系数列向量线性无关。否则必能找到一个非 负分量,它的系数列向量可由其后确定的系数列向量线性表示。 所以初始解中m+n-1个非负分量为运输问题一个基本可行解的 基变量,或初始调运方案为运输问题的一个初始基本可行解。
195

返回总目录

? 最优解的判别
回顾利用单纯形法求解线性规划的步骤: 在求出基本可行解以后,就必须检验该基本可行解是否为 最优解,为此给出一个检验标准。在求极大化的线性规划时, 若初始基本可行解所有非基变量检验数

σ j =c j -CB B-1Pj ? 0 (j为非基变量下标)
则初始可行解为最优解,停止计算。否则将进行基变换, 对初始基本可行解进行改进。 运输问题初始基本可行解的最优性检验也必须设定一个标 准。由于运输问题目标函数是求极小化问题,因此检验标准是 计算所有非基变量(空格)的检验数

σi j =ci j -CB B-1Pi j (i,j为非基变量下标).
-1 如果所有非基变量检验数 σi j =ci j -CB B Pi j ? 0

则初始基本可行解为最优解。 下面介绍两种计算检验数的方法。
196

返回总目录
1.闭回路法。 利用闭回路的概念计算非基变量的检验数,以判别基本可行解 是否为最优解。

? 定义:若运输表中的一组变量经过适当排列以后,可写成如下形
式:

x i1 j1 ,x i1 j2 ,x i2 j2 ,x i2 j3 ,? x is js ,x is j1

其中 i1 ,i 2 ,?,i s 互不相同,j1 ,j2 ,?,js 互不相同。

那么这些变量集合就构成了一个闭回路。其中的每一个变量称为
这个闭回路的顶点。 由闭回路定义可知,若用水平和垂直的线段将这个变量集合中

处于同行同列的相邻顶点相连接。就能构成一个封闭的回路。而且
该闭回路的每一条边(水平或垂直)上只包含两个顶点。且都处于 每条边的两个端点上。如

x 23 ,x 24 ,x14 ,x15 ,x 35 ,x 33

x11 ,x12 ,x 32 ,x 31
197

返回总目录
常见的几种闭回路见表:

B1 A1

B2

B3

B4

B5

B6

B7

B8

B9 产量 a1

A2
A3 A4 销量 b1 b2 b3 b4 b5 b6 b7 b8 b9

a2
a3 a4

表中变量集合 x11 ,x12 ,x 32 ,x 31 ,变量集合 x 23 ,x 24 ,x14 ,x15 ,x 35 ,x 33 , 变量集合 x16 ,x17 ,x 47 ,x 49 ,x 29 ,x 26 等均构成闭回路.
198

返回总目录
? 性质 定理1 运输问题模型中,系数矩阵A的一组系数列向量

Pi1 j1 ,Pi2 j2 ,? Pis js 线性无关的充分必要条件是
这组向量所对应的变量 x i j 本定理证明从略。 变量组
11

,x i2 j2 ,? x is js 不包含闭回路。

x i1 j1 ,x i2 j2 ,? x is js

不包含闭回路的含义是该变量组中

任何一个变量子集合均不构成闭回路。
由定理1可得如下推论: ? ? 推论1.若一组变量包含闭回路,那么这组变量所对应得系数列 推论2.m+n-1个变量构成基本可行解的基变量的充分必要条

向量线性相关。
件是它们不包含闭回路。
199

返回总目录

x i1 j1 ,x i2 j2 ,? x is js (s=m+n-1)是运输问题 基本可行解的基变量, ij 是一个非基变量,则变量组 x x ij ,x i1 j1 ,x i2 j2 ,? x is js 中存在包含 x ij 的唯一闭回路。
定理2 若变量组

?

由定理2可知,从任何一个非基变量对应的空格出发,用

水平或垂直线向前划,遇到某个基变量对应的数字格,试转 90o后继续前进,最后总能找到一条闭回路,回到起始空格。

200

返回总目录

?


闭回路法。 设

x ij 是一个非基变量,根据定理2,在运输表中可以找到 x ij c ij
值取为正,

为第一个顶点,其他顶点均为基变量的唯一闭回路。 然后沿一个方向将闭回路中奇数顶点对应的

偶数顶点对应的 应的检验数。

c ij

值为负。求它们的代数和,即为非基变量对

填入相应的空格。做上记号以便与数字格的基变量值(调运 量)相区别。

201

返回总目录
例2 在例1中用最小元素法求出初始基本可行解为下表所示。试用 闭回路法求各非基变量(空格)的检验数. 解:非基变量 x11 为起点的闭回路为 x11 ,x13 ,x 23 ,x 21 ,如表所示。 因此所对应的检验数 σ =c -c +c -c =3-3+2-1=1
11 11 13 23 21

销售地 加工厂

B1


B2
3 1 11 4 9

B3
3 3 2

B4
10 8 5 3

产量(吨)

A1 A2

7 4 9

3
A3
销量(吨)

1
7 6 4 10

3

6

5

6
202

返回总目录
而非基变量

x12 对应的检验数: σ12 =c12 -c14 +c34-c32 =11-10+5-4=2

其他非基变量的检验数用同样方法求解,结果下表。 本例中 σ 24 =-1<0 ,则必存在对现行调运方案的改进办 法。可使得总费用进一步降低。
销售地 加工厂

B1
1 3 1 2 1

B2
11 4 9

B3
3 3 2
-1

B4
10 8 5 3

产量(吨)

A1 A2

7 4 9

3
A3
销量(吨)

1
7 6 4 12 10

10

3

6

5

6
203

返回总目录
2.位势法。 由单纯形可知,在求解运输问题的初始基本可行解以后,也可以使 用以下公式计算非基变量检验数。 σi j =ci j -CB B-1Pi j (i,j为非基变量下标) 但是用上式计算会遇到一些麻烦。 minZ= ?? cij x ij 由运输问题原数学模型可知,系数矩
i=1 j=1 m n

? n 阵A的秩R(A)=m+n-1。即矩阵A ? ? x1j +x α =a1 ? j=1 中任意m+n个系数列向量均线性相关。 n ? =a i i=2,, m 3? 因此A中的基B实际上是不存在的。 ? ? x ij ? j=1 为了介决这个问题。可在约束条件的 ? m ? =b j j=1,2, n. ? 第一个方程的左端加上一个人工变 ? ? x ij i=1 量 x α ,这样原模型变成新模型. ? x ? 0,i=1,2, m, j=1,2, n.x ? 0. ? ? α ? ij
204

返回总目录

i=1 j=1 设新模型的系数矩阵为 A , 则 A ? (A,e1 ) ,其中e1为第一个元 ? n ? ? x1j +x α =a1 素为1,其他元素都为零的单位列向 ? j=1 量。由于加入了人工变量 x α 后模型 ? n =a i i=2,, m 3? ? ? x ij 的m+n个约束条件线性无关,因 ? j=1 此 R(A)=m+n 。在 A 中必能找到 ? m =b j j=1,2, n. ? m+n阶的基B,易知人工变量 x α 必 ? ? x ij ? i=1 为基变量。其系数列向量e1必在其B ? ? ? ? x ij ? 0,i=1,2, m, j=1,2, n.x α ? 0. 之中。 用最小元素法或伏格尔法求解m+n-1个基变量以后再加上基变 量 x α ? 0 , 即可得到新模型的一个基本可行解。且由产销平衡条件,

minZ= ?? cij x ij

m

n

在新模型的任意一个可行解中,人工变量

假设 x i1 j1 ,x i2 j2 ,? x is js (s=m+n-1)为运输问题原模型的一个基本 可行解,则矩阵 B=(Pi1 j1 ,Pi2 j2 ,? Pis js ,e1 ) 是新模型的一个可行基, 对应的基变量的价值向量 CB =(ci j ,ci j ,? ci j ,0) 。
1 1 2 2 s s

x α 只能取零。.

205

返回总目录
假设 u1 ,u 2 ,? ,u m ,v1 ,v2 ,? ,vn 为对应新模型的m+n个约束 条件的对偶变量,则由对偶性质可知

Y=(u1 ,u 2 ,?,u m ,v1 ,v 2 ,?,v n ) ? CBB-1
由检验数计算公式,可推得

σ ij =cij -C B B-1Pij ? cij -(u1 ,u 2 , ? ,u m ,v1 ,v 2 , ? ,v n )(ei +e m+j ) =cij -(u i +v j ) (i=1,2, ? m. j=1,2, ? n)
其中 u i ,v j 可由以下方程组计算确定: Y=CB B-1 ,所以 YB=C ,即 由 B

(u1 ,u 2 ,? ,u m ,v1 ,v2 ,? ,vn )(Pi1 j1 ,Pi2 j2 ,? Pis js ,e1 ) ? (ci1 j1 ,ci2 j2 ,? cis js ,0) (u i1 +v ji ,u i2 + v j2 ,? u is +v js ,u1 )=(ci1 j1 ,ci2 j2 ,? cis js ,0)
由此可推得

u i1 +v ji =ci1 j1 , u i2 + v j2 =ci2 j2 , ?? , uis +v js =cis js , u1 =0
206

返回总目录

? u i1 +v ji =ci1 j1 ? 该方程组由m+n个方程,m+n个未知量。 ? u i2 + v j2 =ci2 j2 ? 我们把这个方程组的解叫做位势。 ? ? 计算位势后,可确定所有非基变量检验数。 ? u +v js =cis js ? is 若所有检验数大于等于零。则已求得最优解, ? u1 =0 ?
或写成线性方程组形式,其中s=m+n-1, 否则必须作进一步改进。

? 求解可得 u =0,u =-1,u =-5,v =2,v =9,v =3,v =10 ? u1 +v 4 =c14 =10 1 2 3 1 2 3 4 ?u 2 +v1 =c21 =1 由 σij =cij -(u i +v j ) (i,j为非基变量下标) ? ?u 2 +v3 =c23 =2 σ11 =1, σ12 =2, σ 22 =1, 由此可得: ?u +v =c =4 ? 3 2 32 σ 24 =-1,σ 31 =10,σ33 =12. ?u 3 +v 4 =c34 =5 ? 因为 ? 24 ? ?1 ? 0 所以原方案不是最优解。 207 ?u1 =0 ?

仍以例1为例,通过位势法计算非基变量的检验数。已知基变量 ?u1 +v3 =c13 =3 为 x13 ,x14 ,x 21 ,x 23 ,x 32 ,x 34。可得方程组 ,

返回总目录
上述计算检验数的过程可以在运输表中完成。方法是用 u 列代 i

替表中的产量列,用 v i 行替代表中的销量行。首先取定 u1 =0 ,然后
根据数字格的单位运价 ci j =u i ? v j 逐个确定其他各个 u i ,v j (i=1~m,j=1~n) 最后利用公式 σi j =ci j -(u i ? v j ) 求出非基变量检验数。
销售地 加工厂

B1
1 3 1 2 1

B2
11 4 9

B3
3 3 2 -1

B4
10 8 5 3

ui
u1=0 u2=-1 u3=-5

A1 A2

3
A3 10 7 6 4

1
12 10

vj

v1=2

v2=9

v3 =3

v4=10
208

返回总目录

? 改进基本可行解的方法
对已求得的基本可行解,若存在负的检验数,则说明当前解不 是最优解,需要改进。与单纯形法对基本可行解的改进方法相似, ? 首先确定换入变量。 因为运输问题是求解极小化的问题。因此可用最大减少原则,

即选取最小的负检验数所对应的非基变量为换入变量。
? 然后确定换出变量。

再一次使用闭回路法。由定理2,若 x ij 为换入变量,则以 x ij 为起点,标出其他顶点都为基变量(数字格)的唯一闭回路,在由 出发的闭回路的偶数顶点上调运量的最小值就是调整量 θ ,而相应 的基变量就是换出变量。
209

返回总目录
? 若有两个偶数顶点同时有同一个最小值,则可任取其
中之一作为换出变量。 同时按以下方法进行调整: ① 在上述闭回路上,奇数顶点运输量的值均加上调整量 θ , 偶数顶点运输量的值均减去调整量θ 。其中换出变量运输量必调 整为零,且由数字格变成空格。表示该变量已由基变量变成了非 基变量。若有其他偶数顶点的运输量也调整为零,则必须把“0” 仍然填入所在格。表示对应的基变量并非离基变量,只是出现了 取值为零的基变量,如前所述,此时出现了退化的基本可行解。 ② 上述闭回路顶点以外的运输量保持不变。

210

返回总目录
例3 在例2中,用位势法检验初始基本可行解,出现了为负值的非基 变量检验数。试利用闭回路法对该解作进一步调整并求出最优解。

x 解:c 24 ? ?1 为负的检验数,所以以 x 24 为换入变量, 24 对应的闭回路上. 两个偶数顶点 x14 =3,x 23 =1 ,调整量 θ=min ?3,1? =1 ,以 x 23 为换入变量.
销售地 加工厂

B1


B2
3 1 11 4 9

B3
3 3 2

B4
10 -1 8 5 3

产量(吨)

A1 A2

7 4 9

3
A3
销量(吨)

1
7 6 4 10

3

6

5

6
211

返回总目录
按上述调整方法奇数点 x 24 ,x13 均增加1,即 x 24 =1,x13 =5,而偶 数点 x14 ,x 23 均减少1。即 x14 =2,x 23 =0 (离基)。由此可得改进后 的调运方案. x13 =5,x14 =2,x 21 =3,x 24 =1,x 32 =6,x 34 85(千元)
销售地 加工厂

? 3 总运费=

B1


B2
3 1 11

B3
3 4 +1

B4
10 3 -1 2 -1
+1

产量(吨)

A1 A2

7 4 9

9

8 5

3
A3
销量(吨)

1 -1
7 6 4 10

3

3

6

5

6
212

返回总目录
再利用位势法对改进后的基本可行解进行检验,如下表. 因为所有非基变量检验数均大于等于零,所以已得到最优解。 即最优调运方案 x13 =5,x14 =2,x 21 =3,x 24 =1,x 32 =6,x 34 ? 3 ,此时最小运费Z=85(千元) ? ? 11 ? 0 说明本题有无穷多最优解。
销售地 加工厂

B1
0 3 1 2 2

B2
11 5 9 4 6 1 12

B3
3 2 2 1 10 3

B4
10 8 5

ui
u1=0 u2=-2 u3=-5

A1 A2

3
A3 9 7

vj

v1=3

v2=9

v3 =3

v4=10
213

返回总目录

?产销不平衡的运输问题
在产销平衡运输问题中,如果取消产销平衡这一限制,比如 当供大于求或者供不应求时,那么运输问题将面临产销不平衡的 问题。 m n 当供大于求, 即

minZ= ?? cij x ij
i=1 j=1

?
i=1

m

ai >

?
j=1

n

bj

时,

对应的产销不平衡的

运输问题模型为

? n i=1,2 ? m. ? ? x ij ? a i ? j=1 ? m . ? ? x ij =b j j=1,2? n. ? i=1 ? x ij ? 0, i=1,2,? ,m; j=1,2,? ,n ? ? ?
214

返回总目录
对于这样一个问题怎样求解呢?一个自然的想法是设法把它变 成一个产销平衡的运输问题。然后用上一节所介绍的表上作业法求 解。

首先,我们在前m个不等式中引入松弛变量,使之变成

?x
j=0

n

ij

+x i,n+1 =ai i=1,2, ?,m

然后,再虚拟一个销售地,其需求量 b n+1 =

? a -? b
i i=1 j=1

m

n

j

? 所以称 Bn+1为虚拟的销地,是因为该销售地实际上并不存在。第 i个产地Ai 运往虚拟销售地 Bn+1 的运量实质上是产地在完成调运方

案之后多余的物质。仍存放在的库房内。因此在改进后的模型中,
从各个产地运往虚拟销地的物质的单位运价为 Ci,n+1 =0 i=1,2, ?,m 这样一来,产销不平衡问题转化成一个产销平衡问题。可以用表

上作业法求解。
215

B2

返回总目录
例4 设有产量分别为30,50,60的三个原料产地A1,A2,A3。 要将原料运往需求量分别为15,10,40,45的四个销售地B1,B2, B3,B4。单位运价表如表。试求总运费最省的调运方案。 销地

B3

B4

产地

B1

B2

B3

B4

A1 A2 A3
3

3 7 10
i

5 4 3
4 j=1

8 8 5

4 6 2

解:总产量

? a =30+50+60=140
i=1

总销量 ? b j =15+10+40+45=110

为总产量大于总销量的不平衡的运输问题。因此增加一个虚拟的销 地B5,需求量b5=140-110=30,且单位运价c15=c25=c35=0。
216

返回总目录
由此可得产销平衡的运输表
销售地 加工厂

B1 3

B2 5

B3 8

B4 4

B5 0

产量

A1 A2 A3
销量

30 50 60

7
10 15 10

4
3 40

8
5 45

6
2 30

0
0

对上述产销平衡运输表,可用表示作业法求解。

217

返回总目录
首先利用最小元素法确定初始基本可行解 X(o)
销售地 加工厂

B1
3 15 7 10 10 15 ③

B2
5 15 4 20 3 5 10 ④

B3
8 8 5 45 40 -5 -15

B4
4 6 30 2 45

B5
0 0 0 30 ①

产量
30 -15 50 -30 60 -45 -10 ⑥

A1 A2 A3 销量



得初始基本可行解 x11 ? 15, x13 ? 15, x23 ? 20, x25 ? 30, x32 ? 10, x33 ? 5, x34 ? 45



总运费Z=470
218

返回总目录
利用位势法求解非基变量检验数,以判断初始基本可行解 X 是否最优。
销售地 加工厂
(o)

B1
3 15 4 10 7 10 10 -1 -2

B2
5 15 4 20 3 5

B3
8 8 5 45 -1 1

B4
4 6 30 2 3 0

B5
0 0 0

A1 A2 A3

u1=0 u2=0 u3=-3

v1=3

v2=6

v3=8

v4 =5

v5=0

由表可知, ? 22 ? ?2 为最小的负检验数。因此可将 x 22 作为换入变 量,从 x 22出发,作出其他顶点均为基变量的闭回路。
219

返回总目录
销售地 加工厂

B1
3

B2
5

B3
8

B4
4 6

B5
0 0

产量
30 50 60

A1
15

15
7 10 10 -10 15 10 -2 4 +10 8

A2 A3 销量

20-10
5 5+10 40 45 45 2

30
0 30

3

从 x 22 出发的闭回路中,偶顶点 x 23 =20,x32 =10,调整量 () 1 θ=min ? 20,10? =10 且取 x 32 为换出变量。可得改进后的基本可行解 X

x11 =15,x13 =15,x22 =10,x23 =10,x25 =30,x33 =15,x34 =45,
总运费Z=450,比初始解 X
(o)

优。

220

返回总目录
再利用位势法求解非基变量检验数,以判断改进后的基本可行解
( X 1) 是否最优。

销售地 加工厂

B1
3 15 4 10 7 10 10 2 1

B2
5 15 4 10 3 15

B3
8 8 5 45 -1 1

B4
4 6 30 2 3 0

B5
0 0 0

X(1)

A1 A2 A3

u1=0 u2=0 u3=-3

v1=3

v2=4

v3=8

v4 =5

v5=0

由表可知, ? 14 ? ?1 为负检验数。因此可将 出发,作出其他顶点均为基变量的闭回路。

x14 作为换入变量,从 x14
221

返回总目录
销售地 加工厂

B1
3

B2
5

B3
8
-1

B4
4 +15 8 6

B5
0 0

产量
30 50 60

A1
15

15-15
7 4

A2 A3 销量
15

10
10 10 3

10
5 15 +15 40 2 45 -15 45

30
0 30

从 x14 出发的闭回路中,偶顶点 x13 ? 15, x34 ? 45,调整量 (2) θ=min ?15,45? =15 且取 x 为换出变量。可得改进后的基本可行解 X
13

x11 =15,x14 =15,x22 =10,x23 =10,x25 =30,x33 =30,x34 =30
总运费Z=435,比初始解 X
(1)

优。

222

返回总目录
继续利用位势法求解非基变量检验数,以判断二次改进后的基 (2) 本可行解 X 是否最优。
销售地 加工厂

B1
3 15 3 9 7 10 10 2 2

B2
5 4 10 3 30 1

B3
8 15 8 5 30 1

B4
4 6 30 2 3 1

B5
0 0 0

A1 A2 A3

u1=0 u2=1 u3=-2

v1=3

v2=3

v3=7

v4 =4

v5=-1

(2) 得所有非基变量检验数均大于等于零。因此 X 为最优解,即

x11 =15,x14 =15,x 22 =10,x 23 =10,x 25 =30,x 33 =30,x 34 =30
总运费Z=435。
223

返回总目录

当供应量不能满足需求量,即销量大于产量时。可以增加一个 虚拟的产地Am+1。 其产量

a m+1 = ? b j -? a i
j=1 i=1

n

m

且对应的单位运价 c m+1,j =0 j=1,2,? ,n 。这样可以把产销 不平衡运输问题转化成产销平衡的运输问题。

求解方法与例4相同。

224

返回总目录

第5章 图与网络分析
? 图论的基本概念 ? 最小支撑树 ? 最短路问题 ? 最大流问题 ? 网络计划

?

225

返回总目录

?图论的基本概念
?引言
图论是由瑞士数学家欧拉(Euler)于1736年创始的,当时有一个 世界难题,叫“哥尼斯堡七桥问题” 。 哥尼斯堡城中有一条河,叫普雷格尔河,河中有两个岛,河上有七 座桥,如图所示。当时那里的居民 A 热衷于这样的问题: 一个散步者能否走过七座桥, 但每座桥只走过一次,最后回到 D C 出发点。
B

226

返回总目录
欧拉用A、B、C、D四点表示 河的两岸和小岛,用两点间的联 线表示桥,如右下图所示,该问 题可归结为: 能否从某一点出发,一笔画 出这个图形,最后回到出发点而 不重复?即一笔画问题。
A

C

D

B

欧拉在1786年发表了题为“依据几何位臵 的解题方法”的论文,解决了著名的哥尼斯堡 七桥问题. 欧拉证明了上述图形一笔划是不可能的, 因为图中每一个点都只和奇数条线相关联.

A

C

D

B

他的结论是:图形能一笔画的充要条件是图形的奇顶点(连接 奇数条线的顶点)的个数为零
227

返回总目录

?

图的定义
在自然界和人类的实际生活中,常用点和点与点之间的联线

所构成的图,来反映某些研究对象和对象之间的某种特定的关系。 如: 为了反映城市之间有没有航


班,我们可用右图表示。甲城与
乙城,乙城与丙城有飞机到达, 而甲、丙两城没有直飞航班。

甲 丙 工人 工作 A 甲 B

对于工作分配问题,我们可
能用点表示工人与需要完成的工 作,点间连线表示每个工人可以

乙 丙
C

胜任哪些工作如右图所示。



228

返回总目录
? 图的定义:
所谓图,就是顶点(简称点)和一些点之间的连线(不带箭头或 者带箭头)所组成的集合。

为区别起见,不带箭头的连线称为边, 带箭头的连线称为弧。
? 如果一个图是由点和边所构成的,则称之为无向图(也简称为图), 记作 G= ? V,E ? ,其中V表示图G的非空的顶点集合,E表示G的边的集 vi 合。连接顶点v j 和 的边记为? vi ,v j ? ; e= ? ? ? 如果一个图是由点和弧所构成的,则称之为有向图,记作 D= ? V,A ?, 其中V仍表示有向图D的非空的顶点集合,A 表示D的弧集合。一条方

向从 vi

指向j v

的弧记为 vi ,v j a=

?

?



229

返回总目录

如无向图:G= ? V,E ?

e1
V1 V2

V= ? v1 ,v2 ,v3 ,v4 ? E= ?e1 ,e2 ,e3 ,e4 ,e5 ,e6 ,e7 ?

e2 e5
V4

e6

e3

e1 = ? v1 ,v2 ? ,e2 = ? v1 ,v2 ? ,e3 = ? v2 ,v3 ? , e4 = ? v3 ,v4 ? ,e5 = ? v1 ,v4 ? ,e6 = ? v1 ,v3 ? ,e7 =? v4 ,v4 ?

e7

e4

V3

230

返回总目录

如有向图: ? V,A ? D=

V= ?v1 ,v 2 ,v3 ,v 4 ,v5 ,v6 ,v 7 ?
V3 a2 a8 V5 a10 V7

A= ?a1 ,a 2 ,a 3 ,? ,a11?

a11 V6

V1
a1

a3

a6

a9 a7

a4

a1 = ? v1 ,v 2 ? ,a 2 = ? v1 ,v3 ? ,a 3 = ? v3 ,v 2 ? , a 4 = ? v3 ,v4 ? ,a 5 = ? v 2 ,v 4 ? ,a 6 = ? v 4 ,v5 ? , a 7 = ? v 4 ,v6 ? ,a 8 = ? v5 ,v3 ? , a 9 = ? v5 ,v 4 ? , a10 = ? v5 ,v6 ? a11 = ? v6 ,v7 ?
231

V2

a5

V4

返回总目录

? 基本概念
? 点和边的相关概念: (1)顶点数和边数:给定图 G= ? V,E ?,集合V的元素的个数,称为图G 的顶点数,记作 p(G) ;集合E的元素的个数,称为图G的边数,记q(G) 作 是 。
e= ? v i ,v j ? ? E ? ?

v i ,v j
,则称顶点 是

e
的端点,

(2)端点和关联边:若 e v i ,v j
的关联边。
j

vi


vj

vi
与同一条边相关联,则称点 和

(3)相邻点和相邻边:若顶点 vj ei e

为相邻点;若边 和

有一个共同的端点,则称其为相邻边。

(4)环和多重边:若边的两个端点属同一顶点,则称该边为环;若两 个端点之间多于一条边,则称这些边为多重边。

(5)多重图和简单图:含多重边的图称为多重图,无环也无多重边的 图称为简单图。
232

返回总目录
(6)次和孤立点:与点关联的边的条数,称为点的次,记作 d(v) ;次 数为零的点为孤立点。 (7)悬挂点和悬挂边:次为1的点称为悬挂点;悬挂点的关联边称为 悬挂边。 (8)奇点和偶点:次为奇数的点称为奇点;次为偶数的点为偶点。 定理1 图 G= ? V,E ?中,所有顶点的次之和等于所有边数的2倍, 即
v?V

? d(v)=2q
,ei1 ,vi 2 ,ei 2 ,? ,v i n-1 ,ein-1 ,v in

? 链的概念: (1)给定一个图 G= ? V,E ? ,一个点、边的交错序列

?v

i1

?,

如果满足 ei t = ? v i t ,v i t+1 ? , ? t=1, 2,? n-1? 。这样的序列称为 ? ?
一条联结

v i1 和 v i n的链,记作 ? v i ,v i ,? ,v i
1 2

n

?。

233

返回总目录
(2)开链和闭链:如果 vi1 ? vin ,则该链称为开链;如果v i1 = v in , 则该链称为闭链(或称为圈)。 (3)简单链和初等链:如链内所含的边均不相同,称之为简单链;如 链内所含的点均不相同,称之为初等链。 如:
V1

? v1 ,v 2 ,v3 ,v4 ,v5 ,v3 ,v6 ,v7 ?
V4

e4

e5
e1 e2
V2 V3

? v1 ,v 2 ,v3 ,v6 ,v7 ?
V5

是简单链,

e3 e6

是初等链,

? v1 ,v 2 ,v3 ,v 4 ,v1 ? ? v 4 ,v1 ,v2 ,v3 ,v5 ,v7 ,v6 ,v3 ,v4 ?
是简单圈,
234

e7 e8
V6

e9

是初等圈,

V7

返回总目录
(4)基础图和路:若把一个有向图D的方向去掉,即每一弧都用相应 得无向边代替,所得到的一个无向图,称为该有向图D的基础图, 记为G(D);

基础图G(D)中的链(或圈)恢复无向边的方向后,称为有向图
D的链(或圈)。 若交替序列 vi1 ,a i1 ,v i2 ,a i2 ,? ,v in-1 ,a in-1 ,v in 是有向图G的一条链,

且满足 a ik = v ik ,v ik+1 ,即链中每一条弧的箭头方向都和链的方向
一致,那么该链称为有向图D 的一条从 v i1 到 v i n 的路,简记

?

?

?

?

μ=vi1 ,vi2 ,?,vin-1 ,vin 。又若 v =v ,则称μ为图D中的回 i i
1 n

路。
? 对无向图G来说,链和路(闭链和回路)这两个概念是一致的。但 有向图D中的链不一定是路,因为有向图的链可能存在和链的方向

不一致的反向弧,但按定义,它们仍是有向图中的链。
235

返回总目录
? 连通图和网络图的概念:
(1)连通图:在一个图G 中,若任意两点之间至少存在一条链,则称 该图G为连通图,否则称之为不连通图。 如:
V1 a3 V3 V5

a1 a2

a4
V4

a5

左图为不连通图。 因为在顶点V1, V2,V3,V4和 V5,V6之间不存在任何一条链将 它们相连接。
V2 V1

V2

V6

V3

V5

右图为有向连通图
V4

236

返回总目录
(2)连通分图:若G是不连通图,那么它的每一个连通部分称为图G 的连通分图。
(3)子图和支撑子图:设图 G= ? V,E ? ,

若有 G ?= ? V?,E? ?,使 V? ? V, E? ? E ,则称 G? 是 G 的子图; 若 V?=V, E? ? E , 则称 G? 是 G 的支撑子图。
如,以下右图是左图的支撑子图。
v1 e1 v2 e4 e8 v3 e5 e3 e7 e6 v4 e4 e6 v4
237

v1 e2 v5 e1

v2

e3

v5

v3

e5

返回总目录
(4)赋权图:设图 G= ? V,E ? ,若对其边集E定义了一个实值函
数 w ? vi ,v j ? , ? vi ,v j ? ? E ,则称该图为一个赋权图。记作G= ? V,E,? ? 。 ? ? w ? vi ,v j ? 称为边 ? vi ,v j ? 的权。 ? ? 求沿道路架设连接六个车间的电话线路,使电话总长最短。
V3 6 7 V1 5 1 2 3 4 V4 5 V5

如某工厂内连接六个车间的道路网如入所示,已知每条路长,要

左图为一赋权图
4 V6

最优解:如红线所示,
电话总长15个单位。 ? 红线所示为图G的最小 支撑树

V2

238

返回总目录
(5)网络图,若 G= ? V,E,? ? 为一赋权图 ,并在其顶点集合V中指 定了起点(或称发点)和终点(或称收点),其余的点为中间点,这样 的赋权图称为网络图(简称网络)。记作 N= ? V,E,? ? 。

? 网络一般是连通的赋权图。

? 若一个网络图中的每条边都是有向的弧,则称之为有向网络,记作
N= ? V,A,? ?

239

返回总目录

? 图的矩阵表示
? 距离矩阵:设图G= ? V,E,? ? ,w ij 为边 [vi ,v j ] 上的权,表示点

v i 到 v j 之间的距离,则可构造距离矩阵 A= ? a ij ? , n?n
[vi ,v j ] ? E ? w ij a ij = ? ?0 或 ? ? 其他 如:以下无向赋权图中的权表示点与点之间距离
其中
V5

7
V1

v1
6
V4
4

v2 9 0 3 4 +?

v3 2 3 0 8 5

v4 4 4 8 0 6

v5 7 ? +? ? ? 5 ? ? 6 ? 0 ? ?
240

4 2

9
5
V2

8

v1 ? 0 v 2 ?9 ? A= v3 ? 2 ? v4 ?4 v5 ? 7 ?

3

V3

? 对有向赋权图,则定义

a ij 时将 [vi ,v j ] 改为 (v i ,v j ) 。

返回总目录
? 邻接矩阵: 设图 G= ? V,E ? ,则邻接矩阵 义如下

A= ? a ij ?

n?n

的元素可定

?1 a ij = ? ?0

[vi ,v j ] ? E
其他

?对有向赋权图,则定义

a ij 时将 [vi ,v j ] 改为 (v i ,v j )
v1 v 2 v3 v 4 v5
V3



V2

V1

V4 V5

v1 ? 0 v 2 ?1 ? A= v3 ? 0 ? v 4 ?0 v5 ? 0 ?

1 0 0 0 1

0 1 0 0 1

1 1 0 0 0

0? 0? ? 0? ? 1? 0? ?
241

返回总目录

?最小支撑树
? 树及其性质
? 树的定义:设 G= ? V,E ? ,若G连通,并且没有圈,则称G为树, · 记作 T= ? V,E ? 。
比如有六个顶点的树有6种,

·

242

返回总目录

? 定理2

以下关于树T的六种描述是等价的,

(1)无圈连通图;
(2)无圈, q ? p ? 1 ( 即图有 p ? 1 条边, p 是图中的顶点数); (3)连通, q ? p ? 1 ;

(4)无圈,但增加一条边可得唯一一个圈;
(5)连通,但舍弃一条边则不连通; (6)每一对顶点之间有一条且仅有一条链。

? 上述六个等价命题可以使用循环证明法,即由命题(1)推得命题
(2),再由命题(2)推得命题(3),……,依次类推,最后由命题 (6)回推到命题(1),完成以上推导过程即证明了六个命题是等价 的。

243

返回总目录

? 图的支撑树
? 支撑树的定义:假设图 T= ? V,E? ? 是图 G= ? V,E ? 的支撑子图, 如果图 T= ? V,E? ? 是一个树,则称T是G的支撑树。
如下图中,(b)图是(a) 图的支撑树
V3 V1 V5 V6 V3 V5 V6

V2 (a)

V4

V2 (b)

V4

? 定理3

图G有支撑树的充分必要条件是图G是连通的

244

返回总目录

? 最小支撑树
? 定义

T= ? V,E? ? 是G的一个支撑树,E? 中所有边的权之和

设赋权图 G= ? V,E,? ? ,它的每条边 ? vi ,v j ? 有非负权 wij , ? ?

w(T)=

? vi ,v j ??E? ? ?

?

wij
是G的最小支撑树。 w(T) ,则称 T*

如果 w(T* )=

T是G的支撑树

Min

? 定理4 设赋权图 G= ? V,E,w ?,若把E分割成两个不相交的非空子集 S 和 S ,那么连接这两个子集的最小边一定包含在G的最小支撑树内。 ? 由定理4可以引出求最小支撑树的方法

245

返回总目录
? 求最小支撑树的方法。 (1)避圈法。步骤如下:

① 从赋权图G中任选一点 v i,令 S= ? v i ? ,S ?

② 从连接 S 和 S 的边中选择权最小的边,不妨假设为 ? vi ,v j ? , ? ? 由定理4,它必包含在最小支撑树内;

?v/v ? V,v ? S? ;

③ 令 SU v j ? S ,S ?

? ?

?v/v ? V,v ? S? ;

④ 若 S ? ? ,则停止计算,已选出的各条边已构成最小支撑树, 否则回到②。 例1 某工厂联结六个车间的道路网如下图所示,已知每条道路长, 要求沿道路架设联结六个车间的电话网,使电话线的总长最短。
V3 6 V1 5 V2 1 7 2 V4 3 5 V5 4 V6

4
246

返回总目录
解:这是求最小支撑树的问题,由避圈法的步骤,在图G的六个顶 点中任选其中一点作为S,比如选 S= ?v 3 ? ,则, S ? ?v1 ,v 2 ,v 4 ,v5 ,v6 ? 联结 S 和 S 一共有3条边,取最短边 ? v 2 ,v3 ? ,并令 S= ?v 2 ,v 3 ?, 依次类推… V3 6 5 V5 4 1 5 V2 至此 S=E S ? ? ,停止计算, 7 3

V1

V6 4
V4

2

w(T* ) ? 1 ? 2 ? 3 ? 4 ? 5 ? 15 ,最短电话线路的总长为15个单位。
247

返回总目录
(2)破圈法。 步骤是:在图中任取一个圈,从圈中除去权最大的一条边 (圈中存在两条以上最大权的边,可任选其中一条),在余下的 支撑子图中重复这个步骤,一直得到一个不含圈的支撑子图为止, 这时的图就是原赋权图的最小支撑树。 例2,用破圈法求例1中的赋权图的最小支撑树。 V3 6 V1 5 V5 4

1 5

7 2

3 4

V6

w(T* ) ? 1 ? 2 ? 3 ? 4 ? 5 ? 15,最短电话线路的总长为15个单位。
248

返回总目录

?最短路问题
最短路问题表述:



条路,路P的权是P中所有边的权之和,记为 w ? p ? 。 最短路问题就是求从

? ? eij ? ? wij,又有两点 vs ,v t ? V,设P是G中从 v s 到 v t
vs


给定一个赋权图 G= ? V,E,? ? ,对每一边 eij =[vi ,v j ] 相应地有 的一

vt

的路中一条权最小的路P0,使

w ? p 0 ? = min w ? p ?
p

?上述定义中,若是有向赋权图,则任一边 eij =[vi ,v j ] 改为任一弧

a ij =(vi ,v j ) ,其他相同。此时从 v s 到 v t 的路应是沿弧的箭头方向首
尾相接的路。
249

返回总目录

? Dijkstra算法
狄克斯拉算法是由Dijkstra于1959年提出来,用于求解指定两 点

v s ,cc之间的最短路,或从指定点 v s 到其余各点的最短路,目前 vt 被认为是求 w ij ? 0 情形下最短路问题的最好方法。
? 基本思路基于以下原理:

v t的最短路, v i 是P中的一个点,那么从v s 到 v i 的最短路就是从v s 沿P到 v i 的那条路。
? 采用标号法:T标号与P标号。T标号为试探性标号,P为永久
i

若P是从 v s到

性标号。给 i 点一个P标号时,该标号表示从v s 到 v 点的最短路权, v

点的标号不再改变。给 v i点一个T标号时,T标号表示从 v s到

v 点的 i

最短路权的上界,是一种临时标号。凡没有得到P标号的点都有T标 号。算法每一步都把某一点的T标号改为P标号,当终点 v t 得到P标 号时,全部计算结束。
250

返回总目录
?Dijkstra算法基本步骤: ⑴ 给v s 以P标号P ? vs ? =0,其余各点均给T标号,T ? v i ? =+?。 ⑵ 若 v i 点为得到P标号的点,考虑 v j , [vi ,v j ] ? E 且 对v j的T标号进行如下的更改:

v j 为T标号。

T ? v j ? =min{T ? v j ? ,P ? v i ? +wij}

j

比较所有具有T标号的点,若 T(vk )= min{T v j }

? ?

则把最小值对应的点v k 改为P标号,即 P ? v k ? =T ? v k ?

当存在两个以上最小者时,可同时改为P标号。
若全部点均为P标号则停止。否则转回⑵。 ? 步骤(3),当给v k顶点P标号时,可以在图的对应顶点旁标上一个

v i ,P ? v k ? ),其中 v i 为从 v s 到 v k 的最短路上与 v k邻接的 顶点,P ? v k ? 为从v s 到 v k 的最短路长。v s 的记号取( v s ,0)
记号(
251

返回总目录
例3 用Dijkstra算法求图中从v1 ? v 7 的最短路

解:⑴ 首先给 v1 以P标号 P ? v1 ? =0
给其余所有点T标号

(v1, 2)
2 2
2
5 7

T ? vi ? =+?, i=2, 3,? 7. (2)考察 v1 ,由于 (v1, 0) ? v1 , v2 ?? v1 , v3 ?? v1 , v4 ? ? A 1 且 v 2 ,v3 ,v 4 是T标号点,所以
修改T标号为:

5 3
1



5


7

3 4

1

3

T ? v 2 ? =min ?T ? v 2 ? ,P ? v1 ? +w12 ? =min ? ?,0+2? =2 ? ? T ? v3 ? =min ?T ? v3 ? ,P ? v1 ? +w13 ? =min ? ?,0+5? =5 ? ? T ? v 4 ? =min ?T ? v 4 ? ,P ? v1 ? +w14 ? =min ? ?,0+3? =3 ? ?

5



在所有T标号中,T(v2 )= min {T v j }=2 ,于是给 v 2 P标号
j=2,3,4,5,6,7

? ?

令 P(v 2 )=2 ,并标上( v1 ,2)。

252

返回总目录

T ? v3 ? =5, T ? v 4 ? =3, T ? v5 ? =T ? v6 ? =T ? v7 ? =?

(3) 考察 v 2 ,

(v1, 2)
2 2
2 7

因 ? v 2 ,v3 ? , ? v 2 ,v 6 ? ? A

且 v3 ,v 6 是T标号,故修改对应
的T标号:

5
5



(v1, 0)

5

T ? v3 ? =min ?T ? v3 ? ,P ? v 2 ? +w23 ? ? ? =min ?5,2+2 ? =4 T ? v 6 ? =min ?T ? v 6 ? ,P ? v 2 ? +w26 ? ? ? =min ? ?,2+7 ? =9

3 1

6 7

3

1 5 4

3

(v1, 3)



在所有T标号中,T(v4 )= min {T v j }=3最小,于是给 v 4 P标号
j=3,4,5,6,7

? ?

令 P(v 4 )=3 ,并标上( v1,3)。
253

返回总目录
T ? v3 ? = 4, T ? v6 ? = 9, T ? v5 ? =T ? v 7 ? =?
(4) 考察 v 4 ,

因 ? v 4 ,v5 ? ? A 且 v 5 是T标号,故
修改对应的T标号为:

(v1, 2)

2
2

T ? v5 ? =min ?T ? v5 ? ,P ? v4 ? +w45 ? ? ? =min ? ?,3+5? =8

7

5
5



(v1, 0)
在所有T标号中,



5 (v2, 4)



6 7

T(v3 )= min {T ? v j ?}=4
j=3,,5,6,7

3

1 5

3

1

最小,于是给 v 3 P标号 令 P(v3 )=4 ,并标上




( v 2 ,4)。

(v1, 3)
254

返回总目录
T ? v5 ? =8, T ? v6 ? = 9, T ? v7 ? =?
(5) 考察 v 3 ,



? v3 ,v5 ? , ? v3 ,v6 ? ? A
是T标号,故修改对
2

(v1, 2)

7 2 5(v2, 4) 5

且 v5 ,v 6

应的T标号为:

5
3 1 6 7



T ? v5 ? =min ?T ? v5 ? ,P ? v3 ? +w35 ? ? ? =min ?8,4+3? =7 T ? v 6 ? =min ?T ? v 6 ? ,P ? v3 ? +w36 ? ? ? =min ?9,4+5? =9



(v1, 0)
3 1 5 4 3

(v1, 3)
j=5,6,7



(v3, 7)

在所有T标号中, 5 )= min {T v j }=7 最小,于是给 v 5 P标号 T(v 令 P(v5 )=7 ,标上( v 3 ,7)。
255

? ?

返回总目录

T ? v6 ? =9, T ? v 7 ? =?
(v1, 2)
2 2
2 5 7

(6) 考察 v 5 ,

因 ? v5 ,v 6 ? , ? v5 ,v 7 ? ? A
且 v 6 , v 7 是T标号,故修改对应的 T标号为:

T ? v 6 ? =min ?T ? v 6 ? ,P ? v5 ? +w56 ? ? ? =min ?9,7+1? =8



(v2, 4)
1

5

(v5, 8)
6 1

5





(v1, 0)
3 3 5

7

T ? v 7 ? =min ?T ? v 7 ? ,P ? v5 ? +w57 ? ? ? =min ? ?,7+7 ? =14

(v1, 3)
j=6,7





(v3, 7)

在所有T标号中, 5 )= min{T v j }=8 最小,于是给 v 6 P标号 T(v 令 P(v 6 )=8 ,标上(v 5,8)。
256

? ?

返回总目录
(7) 考察 v 6 ,
因 ? v 6 ,v 7 ? ? A 标号为:

(v1, 2)
2 2
2 5 7

且 v 7 是T标号,故修改对应的T

(v6,13)
5

T ? v7 ? =min ?T ? v7 ? ,P ? v6 ? +w 67 ? ? ? ? min ?14,8 ? 5? ? 13


(v5, 8)


5



(v2,4) 3
1 5 4

由于只剩最后一个T标号,所以
给v 7P标号。 令 P(v )=13 , 7

(v1, 0)
3 3 1

7

(v1, 3)



(v3, 7)

标上( v 6 ,13)。
由于所有顶点都标上了T标号 所以计算结束。

从v1到v 7的最短路:

v1 ? v2 ? v3 ? v5 ? v6 ? v7
最短路长13.
257

返回总目录

? 逐次逼近算法
Dijkstra算法只适用于所有 w ij ? 0 的情形,当赋权有向图中存在 负权时,则算法失效。
V2

例如在右图所示的赋权有向图中,
用Dijkstra算法得 v1 到 v 3 的最短路的 权是5.但这里显然不对;
V1

7
-4 5
V3

因为 v1 到 v 3 的最短路是 v1 ? v 2 ? v3 ,权为3。

当 D= ? V,A,? ? 存在负权时,可采取逐次逼近算法来求解最短路。 不妨设从任一点v i 到任一点v j 都有一条弧,如果 a ij =(vi ,v j ) ? A 则添加弧 a ij =(vi ,v j ) ,且令 w ? ?? 。 ij 如果为同一顶点,则 wii = 0, i=1,2,? p 。
258

返回总目录
由最优性原理,若令 d v s ,v j 为从 v s 到 v j 的最短距离,则必满足如

下方程:d vs ,v j = min d ? vs ,vi ? +wij
i=1,2,?p

?

?

?

?

?

?

,其中P为D的点数。
Vj

Vs Vi
Vs到Vi的最短路 Vs到Vj

的最短路

d ? ? ? vs ,v j ? = wsj , j ? 1, 2,? p;
1

由此可得如下递推公式:

d? ? ? vs ,v j ? ? min d?
t i=1,2,?p

?

t-1?

? vs ,vi ? +wij?

d ? ? ? v s ,v j ? 表示从
t

其中d ?1? v s ,v j 表示从 v s 走一步直接到达 v j 的最短距离,

?

?

vs

走t步到达 v j 的最短距离。t为迭代步数。

若第k步,对所有 j ? 1, 2,? p ,有 d ? k ? vs ,v j =d ? k-1? vs ,v j 则 d ? k ? v ,v 为 v s 到任一点 v j 的最短路权。

?

s

j

?

?

?

?

?

259

返回总目录
例4 求所示赋权有向图中从v1 到各点的最短路。
解:迭代初始条件为: 6
-1
1
?1?

2 -3 3

-1

5 -3 1 6 7 -5 8

d ? ? ? vs ,v j ? =w sj
1

2
-2 8 3



1
1

? v1 ,v1 ? = 0, d ? v1 ,v 2 ? = -1, 1 1 d ? ? ? v1 ,v 3 ? = -2, d ? ? ? v1 ,v 4 ? = 3, 1 1 d ? ? ? v1 ,v 5 ? =+?, d ? ? ? v1 ,v 6 ? =+?, 1 1 d ? ? ? v1 ,v 7 ? =+?, d ? ? ? v1 ,v 8 ? =+?.
d
?1?

-5
4 2 -1

1

7

第二步迭代: d ? 2 ? v s ,v j = min d ?1? ? v s ,v i ? +w ij , j=1, 2, ? 8
i

?

?

?

?

用表表示全部计算过程。
260

返回总目录 1 d ? ? ? v1 ,v1 ? = 0,

d?

1?

? v1 ,v 2 ? = -1,d ?1? ? v1 ,v3 ? = -2,

d?
t

1?

? v1 ,v 4 ? = 3

j
i
v1 v1
0 6

w ij
v2
-1 0 -3 8 -1 0 -5 0 0

d ? ? ? v1 ,v j ?

v3
-2

v4 v5
3 2

v6

v7 v8 t ? 1 t ? 2 t ? 3 t ? 4
0 -1 0 -5 -2 -7 1

v2
v3

1 2

-2 3

v4

v5
v6 v7 v8

1
-1 -3

0

1
0 -5

7

-1
5

0
261

(表中空格为+∞)

返回总目录 (表中空格为+∞)
d ? ? ? v1 ,v j ?
t

j
i
v1 v1
0 6

w ij
v2
-1 0 -3 8 -1 0 -5 0 0

v3
-2

v4 v5
3 2

v6

v7 v8 t ? 1 t ? 2 t ? 3 t ? 4
0 -1 0 -5 -2 -7 1 0 -5 -2 -7 -3

v2
v3

1 2

-2 3

v4

v5
v6 v7 v8

1
-1 -3

0

1
0 -5

7

-1
5

-1
-5 6
262

0

返回总目录 (表中空格为+∞)
d ? ? ? v1 ,v j ?
t

j
i
v1 v1
0 6

w ij
v2
-1 0 -3 8 -1 0 -5 0 0

v3
-2

v4 v5
3 2

v6

v7 v8 t ? 1 t ? 2 t ? 3 t ? 4
0 -1 0 -5 -2 -7 1 0 -5 -2 -7 -3 0 -5 -2 -7 -3

v2
v3

1 2

-2 3

v4

v5
v6 v7 v8

1
-1 -3

0

1
0 -5

7

-1
5

-1
-5 6

-1
-5 6
263

0

返回总目录
当 t=4 时

d?

4?

v1 ,v j ? =d ? ?

3?

? v ,v ? ? j=1,
1 j

2,? ,8 ?

v1 到各点的最短路的权,即表中最后一列数。 如果需要知道点v1 到各点的最短路径,可以采用“反向追踪”的办法。
表明已得到从
比如已知 d v1 ,v j

?

?

,则寻找一点 v k ,使 d ? v1 ,vk ? ? w kj ? d v1 ,v j

?

?

记下 (v k , v j ) ,再考察 d ? v1 ,v k ? , 寻找一点 v i,使 d ? v1 ,vi ? ? w ik ? d ? v1 ,vk ?
记下 (vi , vk ) ,直至达到 v1为止.本例中 因为 d ? v1 ,v8 ? =6 由 d ? v1 ,v6 ? +w 68 =(-1)+7=6=d ? v1 ,v8 ? 记下 (v 6 , v8 ) 由

d ? v1 ,v3 ? +w 36 =(-2)+1= -1 =d ? v1 ,v6 ? 记下 (v3 , v 6 )

因为d ? v1 ,v3 ? = ? 2 一步可达,所以最短路径 v1 ? v3 ? v6 ? v8
264

返回总目录 (表中空格为+∞)
d ? ? ? v1 ,v j ?
t

j
i
v1 v1
0 6

w ij
v2
-1 0 -3 0 -5 0 -1 0

v3
-2

v4 v5
3 2

v6

v7 v8 t ? 1 t ? 2 t ? 3 t ? 4
0 -1 0 -5 -2 -7 1 0 -5 -2 -7 -3 0 -5 -2 -7 -3

v2
v3

1 2

-2 3

v4

v5
v6 v7 v8

1
-1 -3

0

1
0 -5

7

-1
5

-1
-5 6

-1
-5 6
265

0

返回总目录
例5 设备更新问题。某企业使用一台设备,在每年年初,都要决定

是否更新。若购臵新设备,要付购买费;若继续使用旧设备,则支
付维修费用。试制定一个5年更新计划,使总支出最少。 若已知设备在各年的购买费及不同机器役龄时的残值和维修费,

如下表所示:
第1年 购买费 机器役龄 11 0-1 第2年 12 1-2 第3年 13 2-3 第4年 14 3-4 第5年 14 4-5

维修费
残值

5
4

6
3

8
2

11
1

18
0

266

返回总目录
第1年 购买费 11 第2年 12 第3年 13 第4年 14 第5年 14

机器役龄
维修费 残值

0-1
5 4

1-2
6 3

2-3
8 2

3-4
11 1

4-5
18 0

解:把这个问题化为最短路问题 用
i i

? v ,v ? 表示第i年初购的设备一直使用到第j年年初(第j-1年年低);弧 ? v ,v ? 旁的数字表示第i年初购进设备,一直使用到第j年初所需支付的购买、
j j

v i 表示第i年初购进一台新设备,虚设一个点 v 6

表示第5年底; 用弧

维修的全部费用。 这样设备更新问题就变为:求从

v1 到 v 6 的最短路.

267

返回总目录
第1年 购买费 机器役龄 维修费 残值
购买 1→2 11

第2年 12 1-2 6 3
残值 4 费用 12

第3年 13 2-3 8 2

第4年 14 3-4 11 1

第5年 14 4-5 18 0

11 0-1 5 4
维修 5

1→3
1→4 1→5 1→6 2→3 2→4 2→5 2→6 3→4 3→5 3→6 4→5 4→6 5→6

11
11 11 11 12 12 12 12 13 13 13 14 14 14

11
19 30 48 5 11 19 30 5 11 19 5 11 5


2 1 0 4 3 2 1 4 3 2 4 3 4

19
28 40 59 13 20 29 41 14 21 30 15 22 15

40 28 19
1

59

21
2 13 3

30
4 5 15 22 6

12

14

15

20
29 41

268

返回总目录
40 28 19 21
2 13 3

59

P标号 T T T T T T V1 0 30

(v1,0)

1

12

(v1,12)

(v3,49)
14

V2 ∞ 12
V3 ∞ 19 19 V4 ∞ 28 28 28 V5 ∞ 40 40 40 40 V6 ∞ 59 53 49 49 49
相邻点 V1 V1 V1
V1 V3

(v1,19)
20 29

4 15 (v1,28) (v3,40) 22

5 15

6

V3

41

计算结果表明 为49。

v1 ? v3 ? v6

为最短路,路长为49。即在

第1年、第3年初各购买一台新设备为最优决策,这时5年的总费用

269

返回总目录

?最大流问题
最大流问题是网络分析中一类应用极为广泛的问题。在交 通运输网络中有人流、车流、货物流;供水网络中有水流;金 融系统中有现金流;通讯系统中有信息流;等等。20世纪50年 代Ford ,Fulkerson建立的“网络流理论”是网络应用的重要 组成部分。

v 右图是输油管道网,v s 为起点, t
v 是终点,1 ,v 2 ,v3 ,v 4为中转站,边上
的数表示该管道的最大输油能力, s 问应如何安排各管道输油量,才能使 从v s到v t 的总输油量最大?
4

1
1

2
2



4 3


4
2

2 3

270

t

返回总目录

? 基本概念
? 网络与流: 我们已经给出了网络图的概念,网络图是一种无向或有向赋 权图,在其顶点集合中指定了起点和终点,其余的点为中间点。 在最大流问题中,我们所讨论的网络都是有向连通赋权图,记 作 N= ? V,A,C ? ,称V中的起点 v s 为发点,终点 v t为收点,其 余的点仍为中间点。对于每一个弧 ,v ? A ,对应有一个 v 权 c vi ,v j ? 0,称为弧的容量,简记

?

?

?

i

j

?

c ij 。

所谓网络上的流,是指定义在弧集合A上的一个函数

f= f ? vi ,v j ? ,

?

并称 f v i ,v j 为弧 vi ,v j 上的流量,简记作 f ij 。
271

?

?

?

?

?

返回总目录
? 可行流与最大流

满足下列条件的流 f ij 成为可行流: ①容量限制条件:每一弧 vi ,v j ? A, 0 ? f ij ? cij . ②平衡条件:对于中间点 v i ,有 并称 v ? f ? 为这个可行流的流量。
(vi ,v j )?A

? ?

?

?

?

fij =

(vk ,vi )?A

?

f ki

对于发点v s ,收点v ,有
t

(vs ,vi )?A

?

fsi =

(vi ,vt )?A

?

fit =v ? f ?

? 可行流总是存在的,如零流, f ij =0,v ? f ? =0 。

所谓最大流问题,就是求一个流 f ij

? ? ,使其流量v ? f ? 达到最大,

并且满足以上容量限制条件和平衡条件。 ? 最大流问题是一个特殊的线性规划问题.
272

返回总目录
? 增广链:
若 μ 是网络中联结发点v s 和收点v t 的一条链,且链的方向是从v s

μ +表示前向弧的集合; 到 v t ,则与链的方向一致的弧叫前向弧, μ _ 表示后向弧的集合。 与链的方向相反的弧叫后向弧,

μ 定义1 设 f ij 是一个可行流, 是从v s 到v t 的一条链,
若 μ 满足下列条件,则 μ是可行流 f ij

? ?

? ?

的一条增广链:

+ 0 vi ,v j ? ? μ + 上, ? fij ? cij ,即 μ 中每一弧是非饱和弧, ① 前向弧 ?

② 后向弧 v i ,v j ? μ

?

?

_

上,0<f ij

? cij ,即 μ _ 中每一弧是非零流弧。

273

返回总目录
? 截集与截量: 设 S,T ? V, S ? T=Φ ,我们把始点在S,终点在T中的所有弧构成 的集合,记为 (S,T) 。 定义1:设网络 N= ? V,A,C ? ,若点集V被剖分为两个非空集合V1 和 V1 , v 使vS ? V1 , v t ? V1 ,则把弧集 ? V1 ,V1 ? 称为分离v s, t 的截集。 ? 截集是从 v s 到 v t 的必径之道。 定义2 给定一截集? V1 ,V1 ?,把截集 ? V1 ,V1 ? 中所有弧的容量之和称为

这个截集的容量(或称截量),记作 c V1 ,V1 =

?

?

? vi ,v j ??? V 1 ,V1 ?

?

cij

?任何一个可行流的流量都不会超过任一截量的容量,即 v ? f ? ? c ? V1 ,V1 ?
* ?若对于一个可行流 f ,网络中有一个截集 ? V1* ,V1* ? ,使 v f * =c V1* ,V1*

则 f *必是最大流,而 V1* ,V1* 必定是网络的所有截集中容量最小的一个, 称为最小截量。
274

?

?

? ? ?

?

返回总目录

? 最大流量最小截量定理:
任一个网络中,从v 的最小截集的容量 c V1* ,V1* ? 定理5

?

s

到 v t 的最大流的流量 v f *

?

? ?

等于分离v , t v
s



可行流f * 是最大流,当且仅当不存在关于f * 的增广链。

证明:(→)若f * 是最大流,

反证,如果存在关于f * 的增广链μ ,则可确定调整量θ.

? ? ? * *? * θ=min ?min ? cij -fij ? , minfij ? ?f ij +θ μ? ? μ+ ? ? ** ? * ? 由增广链定义可知θ>0, 令 f ij = ? f ij -θ ** ? * 不难验证 f ij 是一个可行流,且 ? f ij ? ** * * v f =v f +θ>v f


vi ,v j ? ? μ + ?

? ? ? ?

? ?

? ?

? v ,v ? ? μ ? v ,v ? ? μ
i j i j

-



f * 为最大流矛盾.
275

返回总目录
可行流
* f 是最大流,当且仅当不存在关于 f *的增广链。

证明:(←)若D中不存在关于 f *的增广链, 则定义如下非空点集
ij

* vs ? v1 , v * 若 v ? v* ,且 f * ? cij 则令v j ? v1 , i 1 若 v ? v* ,且 f * ? 0 则令v ? v* , j 1 i 1 因为不存在关于的增广链,所以 v ? v* 。 t 1 * 1

,令

ji

于是得到一个截集, V1* ,V1*

?

?

显然必有
* 1 * 1 * 1 * 1

所以

? v ,v ? ? ? V ,V ? ? v ,v ? ? ? V ,V ? v ? f ? =c ? V ,V ? ,即可行流 f 的流量 v ? f ? 等于截集 ? V ,V ?
?cij * ? fij = ? ?0 ?
i j i j
* * 1 * 1

*

*

* 1

* 1

的截量。所以

f * 必是最大流,定理得证。
276

返回总目录

? Ford-Fulkerson算法
福特-富克逊算法又称寻求最大流的标号法。前提是已有一个可行
流,标号算法分2步。第1步:给顶点的标号过程。通过顶点的标号来寻 找增广链;第2步是调整过程,沿增广链调整f以增加流量。

⑴ 标号过程
每个顶点的标号包含两部分:第1部分表明它的标号是从哪一个顶 点得到,以便找出增广链;第2部分是为确定增广链的调整量用的。

① 给发点 v s 以标号 ? vs , ?? ? ;
② 选择一个已标号的点v i ,对于 v i的所有未标号的邻接点 v j, 如果 v i ,v j ? A,且

?

?

并给

令 l ? v j ? ? min ?l ? vi ? , cij ? ,并给 v j 以标号 -v , l (v ) ? ? i j

vj

以标号

? v , l (v ) ?
i j

fij ? cij ,令 l ? v j ? =min ?l ? vi ? ,cij - f ij ? ? ?
;如果 v j ,v i ? A,且



?

?

?

0<f ij ,

?


277

返回总目录
重复上述步骤②,直到

v t 被标上号或不再有顶点可标号为止。
f* 。

如果

v t 得到标号,说明存在增广链,转入调整过程;如果 v t

未获得标号,标号过程已无法进行时,说明f已是最大流 ⑵ 调整过程

?f ij +θ ? vi ,v j ? ? μ + ? ? ? = ? f ij -θ ? vi ,v j ? ? μ f ij 令 ? ? vi ,v j ? ? μ ? f ij ? 其中调整量 θ=l ? v t ?.调整后去掉所有标号,对新的可行流 ?f ?? ij



新进行标号过程。

?调整过程为:在增广链的前向弧上加上调整量θ,后向弧上减去调
整量θ,其他弧的流量不变.这样可使总流量增加θ,即 v f

? ? ? v ?f ? ? θ
'

278

返回总目录
找可行流f 令调整量 θ=l ? v t ? 求改进的可行流 f ' 倒向追踪 找出增广链μ

给VS 标号( VS,+∞ )


Vt 是否已 标号

是否存在已标号 但未检查的点

不存在关于f 否 的增广链 f即为最大流

?f ij +θ ? ? ? = ? f ij -θ f ij ? ? f ij ?

vi ,v j ? ? μ + ?

? v ,v ? ? μ ? v ,v ? ? μ
i j i j

-

Vi 已 标号,但未检查.

? v ,v ? ? A 若 ? v ,v ? ? A

i
j

对Vi 进行检查,并对Vj 标号:
j

,且 f ij ,且

i

? ? 0<f ji ,对Vj 标号: ? -vi , l (v j ) ? ,l ? v j ? ? min ?l ? vi ? , c ji ?
279

? cij ,对Vj 标号: ? vi , l (v j ) ?

,l

? v ? =min ?l ? v ? ,c -f ? ? ?
j i ij ij

返回总目录
例6 用标号法求所示网络图的最大流。弧旁的数是

? c ,f 。 ?
ij ij

解:经检查,网络中的流是可行 流,下面分析是否可以增加流量。 (1) 标号过程: ①先给 v s 标号 ? vs , ?? ? ; ②检查 v s,在弧 ? v ,v ?上, s 1

(-V1, 1) (4,3) 2

4 (5,3)

(3,3)
(3,0)

(VS,+∞) S (1,1)

(1,1)
(VS, 4) 3

t (2,1)

fs1 =1<cs1 =5

所以

(5,1)



(2,2)

l ? v1 ? ? min ?l ? vs ? , ? cs1 -f s1 ? ? ? min ? ??,5 ? 1? ? 4 ? ?
则 v1 的标号 ? vs ,l (v1 ) ? ? ? vs ,4 ? .弧 ? v 2 ,v s ? 不满足标号条件.
③检查

v1 ,在弧 ? v2 ,v1 ?上,f 21 =1>0 所以 v2

l ? v 2 ? ? min ?l ? v1 ? ,f 21 ? ? min ? 4,1? ? 1 则 ? ?
弧 ? v1 ,v3 ? 不满足标号条件.

的标号 ? -v1 ,l (v2 ) ? ? ? -v1 ,1?
280

返回总目录
④检查 v 2 ,在弧 ? v 2 ,v 4 ? 上,

l ? v4 ? ? min ?l ? v2 ? , ? c24 -f 24 ? ? ? ? ? min ?1,1? ? 1 给 标号

f 24 =3<c24 =4

(-V1, 1) (4,3) (V2, 1) 2 4

(3,3)
(3,0)

? v 2 ,l (v 4 ) ? ? ? v 2 ,1? 在弧 ? v 3 ,v 2 ?上. f 32 =1>0


v4

(VS,+∞) S (1,1)

(5,3) (V4, 1)

(1,1)
(VS, 4) 3 (-V2, 1)

t (2,1)

(5,1)



(2,2)

l ? v3 ? ? min ?l ? v 2 ? ,f 32 ? ? min ?1,1? ? 1 ? ?

v3

标号 ? -v 2 ,l (v3 ) ? ? ? -v 2 ,1?

⑤检查

v 4 ,在弧 ? v4 ,v t ?

上, f 4t =3<c 4t =5 所以

l ? v t ? ? min ?l ? v 4 ? , ? c 4t -f 4t ? ? ? min ?1, ?, ? 3 ? ? ? 1 ? ? ? 5 ?
给 v t标号 ? v ,l (v ) ? ? ? v ,1?.因 4 t 4

vt

已经标号,故进入调整过程.
281

返回总目录
(2) 调整过程:
(-V1, 1) (4,3) (V2, 1) 2 4

μ + = ?? vs ,v1 ? , ? v2 ,v4 ? , ? v4 ,v t ?? μ - = ?? v2 ,v1 ??
前向弧上流量增加1,后 向弧上流量减去1,其他 不变,得可行流 ①给

取定增广链.

(3,3)
S (1,1) (3,0)

(5,3) (V4, 1)

(1,1)
(VS, 4)
3 (-V2, 1)

t

(VS,+∞)

(5,1)

(2,1)



(2,2)

f'

在进入新的循环:



(4,4)
4 (5,4)

(3,3) v s 标号 ? vs , ?? ? (VS,+∞) 检查 v s 给 v1标号? v ,3? S (1,0) s (1,1) 检查 v ,标号过程无法进 1

(3,0)

t (2,1)

行下去. 所以 f
' 为最大流,

(5,2)

v ? f * ? =v ? f ' ? ? 5

1 (VS,3 )

(2,2)


282

返回总目录
由上述可见,用标号法找增广链找到最大流的同时,得到 一个最小截集。最小截集的容量大小影响网络最大流量。因此 为提高总的输送量,必须首先考虑改善最小截集中各弧的输送 能力。另一方面,一旦最小截集中弧的通过能力被降低,就会 使总的输送量减少。

? V ,V ? ? {? V ,V ? , ? V ,V ?}
* 1 * 1 s 2 1 3



(4,4)
4 (5,4) (3,0) t (2,1) 3

(3,3)
(VS,+∞) S (1,0)

(1,1)

(5,2)
1 (VS,3 )

(2,2)
283

返回总目录

? 最小费用最大流
? 基本概念 (1)最小费用最大流:设网络 N(V,A,C) ,对每一条弧 v i ,v j ? A , 对应有一个权 cij ? 0 以及单位流量费用 bij ? 0 。

?

?

要求一个最大流f,使得流的总费用 b ? f ? ? bijfij ? min (vi ,v j )?A 这就是最小费用最大流问题。

?

(2)增广链的增广费用:设网络 N(V,A,C) , f为网络的可行流, 为 μ 可行流的增广链。以 θ=1 调整 f ,则新可行流 f ?的总费用与可行 流的总费用之差

b(f ? - b(f)=? bij -? bij )
称为增广链的增广费用。 ?
μ+ μ-

增广链的增广费用是调整一个单位的流量所增加的费用。但可行 流的不同增广链的增广费用是不一样的。
284

返回总目录
? 若 f 是流量为 v ? f ? 的所有可行流中费用最小者,而 μ为可行流 f 的所有增广链中增广费用最小者,那么沿 μ 调整所得可行流 f ? ,为 流量为 v f ? 的所有可行流中费用最小的可行流。

? ?

(3)增广费用网络图。
假设有网络 N(V,A,C) , f 为网络上的可行流,可构造一个有 W(f) ,使其顶点集合与原网络相同,对中的弧作如下处理: 向赋权图

若 0 < f ij < cij ,则保留弧 vi ,v j ,增加反向弧 v j ,vi ,
并令

?

?

?

?

wij = bij , wji = - bij ;

若 0 = fij < cij ,则保留弧 vi ,v j ,令

若 0 < fij = cij
并令

wij = bij; ? ? ,则去除弧 ? v ,v ? ,用反向弧 ? v ,v ? 代替,
i j j i

wji = - bij ;
285

这样构造的图 W(f) 称为可行流的增广费用网络图。

返回总目录
? 求最小费用最大流的方法: 在 f (0) v ? f ? =0

① 设零流 f (0) = f ij ? 0 为初始可行流,因为总费用 b(f (0) )=0 ,所 以 的可行流中费用最小。 在流量为 v(f) ? v(f (k-1) ) 的可行流中费用最小, ② 设已求得

?

?

f

(k-1)

则构造 f (k-1) 的增广费用网络图 W(f (k-1) ) 。
③ 求 W(f
(k-1)

) 中从起点 v s 到 v t 终点的最短路,若最短路不存

在,则 f (k-1) 已是最小费用最大流,停止计算。否则进入④

④ 最短路对应

N 中的最小费用增广链 μ,在 μ上对 f (k-1)进行调

整,得到新的可行流,返回②。

286

返回总目录
例7 求以下网络图的最小费用最大流,弧旁的数字是 (bij ,cij ) 。
1 (4,10)


(1,7) (6,2) t (2,4)

(2,5)

(1,8) 2
(3,10)

3

解:
(0) ( 4 , 10 ) 1 (0) (1,7) 1 (4)


(1) (2) (6) t (2) 3

→ (0) (0) t S ( 2 , 5 )( 6 , 2 ) (0) (0) (0) (3,10) (1,8) (2,4) 2 3

(1) (3) 2

(a):f(0)

(b):W(f(0))
287

返回总目录
1 (0) ( 4 , 10 )

(5) (1,7 )

1
(4)
S (-1) (-2)

(-1) (1) (6) (3) t (2) 3 (d):W(f(1))

→ (5) t S (0) (2,5) (6 ,2) (5) (0) (0) (1,8) (3,10) 3 (2,4 ) 2 (c):f(1) (2) ( 4 , 10 )


(1) 2

1

(7) (1 ,7) → t

(-4) (4)


1 (-1) (6) (3) (f):W(f(2))
288

(5) (1,8)

(5) (0) (2 ,5) (6 ,2)
2 (0) (3,10) 3

(-1) (-2)

t (2) 3

(0) (2 ,4)

(1) 2

(e):f(2)

返回总目录
(2) ( 4 , 10 )


1

(7) (1,7)

(-4) (4)


1
(-1) (-2) (6) (-2) t

(8) (1,8)

→ (5) (0) t (2,5) ( 6 , 2 ) (3) (3) (2,4) (3,10) 2 3 (g):f(3)

(-1) 2

(-3) (3) (h):W(f(3)) 3

(2)

(3) ( 4 , 10 )

1

(7) (1,7)

(-4) (4)

1 (-1)

(4) → (2) (6) S S(-2) ( 2 , 5 ) (0) t t (6,2) (8) (4) (-3) (-1) (4) (-2) (1,8) (2,4) (3,10) 2 2 3 3 (3) (i):f(4) (j):W(f(4))

W(f (4) )中不存在从v s 到

总流量

v t 的最短路,所以 f (4)即为最小费用最大流。 v ? f ? =11 ,总费用 b ? f ? =55 289

返回总目录

?网络计划
20世纪50年代以来,国外陆续出现一些计划管理的新方法,如关键 路 线 法 ( Critical Path Method , 缩 写 为 CPM ) , 计 划 评 审 方 法 (Program Evaluation Review Technique,缩写为PETR)等。这些方法 都是建立在网络模型基础之上,称为网络计划技术。网络计划技术被地 广泛应用于工业、农业、国防、科研等计划管理中,对缩短工期,节约 人力、物力和财力,提高经济效益发挥了重要作用。 我国数学家华罗庚先生将这些方法总结概括为统筹方法,引入中国 并推广应用。统筹方法的基本原理是: 从任务的总进度着眼,以任务中各工作所需要的工时为时间因素; 按照工作的先后顺序和相互关系作出网络图,以反映任务全貌,实现管 理过程的模型化。然后进行时间参数计算,找出计划中的关键工作和关 键路线,对任务的各项工作所需的人、财、物通过改善网络计划作出合 理安排,得到最优方案并付诸实施。通过对各种评价指标进行定量化分 析,在计划的实施过程中,进行有效的监督与控制,以保证任务高质量 地完成。
290

返回总目录

? 网络图的绘制
? 什么是网络图: 网络图是由节点、弧及权所构成的有向赋权图。 (1)用一个箭头(弧)表示一个工序.多道工序就有多个箭头。 (2)把各个箭头按工序间的相互制约关系,依流程方向从左向右联 系起来。 (3)相邻工序交接处画上圆圈(节点),每个节点编上循序号,表 示工序的事项。节点在箭尾表示工序的开始,节点在箭头表示工序 的完成。 (4)把每道工序所需要的时间(权)标在对应的箭头旁.
3 3 1 4 2 2 5 6 4 5 5 6 7 2 8






291

返回总目录
? 网络图的组成: (1)工序:指一项有具体内容,需要一定人力,物力,经过一定时间 才能完成的生产过程或活动过程. ? 虚工序:不消耗资源,不需要时间,仅用以表示一个工序和另一工 序之间相互依存的制约关系,是虚设的工序,用虚箭头表示。

A B D 工序代号 A B C D 紧前工序 - - A,B B

(2)事项:指工序的开始(即开工事件)和工序的结束(完工事件) ?一个事项对它的前工序是完工事件,对它的后工序是开工事件。
1 A 2 B 3

②是工序A的完工事件,是B的开工事件

?只有一个总的开工事件,一个总的完工事件。
292

返回总目录
(3)路线:指网络图中从起点开始顺箭头所指方向,连续不断到达 终点为止的一条路。

3 6 5 4 3 5 5 5 6 7 2 8










? 关键路线:指完成各个工序需要时间最长的路线,也称主要矛盾线. ? 绘制网络图的规则: (1)每个工序只出现一次。 (2)只能有一个总起始顶点,一个总终止顶点。 (3)不能有回路。 (4)两个顶点之间只能有一条弧。 (5)正确表示工序之间的前行、后继关系。 (6)每一工序起始顶点编号小于终止顶点编号,所有编号从1连续编 号。 293

返回总目录
例 8 某项新产品投产前全部准备工作如下表,表中列示了各工序所 需时间以及它们之间的相互关系。要求编制该项工程的网络计划。
工序
A B C D E

工序内容
市场调整 资金筹措 需求分析 产品设计 产品研制

紧前工序
/ / A A D

工时(周)
4 10 3 6 8

F
G H I J K L

制定成本计划
制定生产计划 筹备设备 原材料准备 安装设备 人员准备 准备开工投产

C,E
F B,G B,G H G I,J,K

2
3 2 8 5 2 1
294

返回总目录
工序 A B C D 紧前工序 / / A A 工时(周) 4 10 3 6 工序 G H I J 紧前工序 F B,G B,G H 工时(周) 3 2 8 5

E
F

D
C,E 3 D 2 6 C 3

8
2

K
L

G
I,J,K

2
1



E 4 F 2 5 G 3 6 K 9 L 1 J5 8 10


I 8

A 4 1







11

295

返回总目录

? 时间参数和关键路线计算
计算网络图中有关的时间参数, 主要目的是找出关键路线,为网络计 划的优化、调整和执行提供明确的时 间概念。 通常把网络图中需时最长的路 线叫做关键路线,如右图所示网络中 双箭线表示的为关键路线,关键路线 上的工序称为关键工序。要想使任务 按期完或提前完工,就要在关键路线 的关键工序上想办法。
3 5 1 4 2 3 7 5 2 4 2 3 4 6

网络图的时间参数包括工序所需时间、事项最早、最迟时间,工序 的最早、最迟时间及时差等,下面分别叙述。
296

返回总目录
? 工序时间 t ? i,j ? 的确定 工序 ? i,j? 的所需时间可记为 t ? i,j ?,有以下两种情况: ⑴ 完成每道工序所需时间确定, 在具备劳动定额资料,或者具有类似工序作业时间消耗的统计 资料时,用对比分析来确定作业时间。 ⑵ 影响工序因素较多,作业时间难以确定, 可以采用三点时间估计法来确定作业时间: a——最快可能完成时间 b——最可能完成时间 c——最慢可能完成时间 一般情况下,可按下列公式近似计算作业时间。

a+4b+c t ? i,j? = . 6

? c-a ? σ =? ? 6 ? ?
2

2

297

返回总目录
? 事项时间参数 ⑴ 事项最早时间 TE ? j? 事项j的最早时间用 TE ? j?表示,它表示以j为始点的各工序最早 可能开工的时间,也表示以j为终点的各工序的最早可能完工时间。 它等于从始点事项到本事项最长路线的时间长度。事项最早时间 可用下列递推公式,按照事项编号从小到大(自左向右)顺序逐个计 算。

? TE ?1? =0 ? ? ? ?T ? j? = max ?T ? i ? +t ? i,j? ? E ? E ? (i,j)?A ? ?

T 其中, E ? i ? 为与事项j相邻的各紧前事项的最早时间。 t ? i,j? 是工序 ? i,j? 的工时,A为网络图弧(工序)的全体, TE ?1? ? 0为边界条件.
298

返回总目录
⑵ 事项的最迟时间 TL ? i ? 事项i的最迟时间用 TL ? i ?表示,它表明在不影响总工期条件下, 以它为终点的各工作的最迟必须完工时间,或以它为始点的工序的最 迟必须开工时间。 在一般情况下,把任务的最早完工时间作为任务的总工期,所示

事项最迟时间的计算方法如下:

? TL ? n ? =TE ? n ? ? ? ? ?T ? i ? = min T ? j? -t ? i,j? ? ?L ? L ? (i,j)?A ? ?
从终点n事项开始,令 TL ? n ? ? TE ? n ? ,并按编号由大到小(自右向 左)的顺序逐个计算。
299

其中 TL ? j? 为事项i相邻的各紧后事项j的最迟时间,它的计算

返回总目录
? 工序的时间参数

⑴工序的最早可能开工时间和最早可能完工时间。
一个工序 ? i,j?的最早可能开工时间用 t ES ? i,j? 表示,任何一个工序 都必须在其所有紧前工序全部完工后才能开始。 时间 TE ? i ?,所以 t ES ? i,j? ? TE ? i ?

由于? i,j? 的所有紧前工序全部完工的最早时间是:事项i的最早

工序 ? i,j? 的最早可能完工时间用 t EF ? i,j?表示,它表示工作按最早

开工时间开始所能达到的完工时间,计算公式如下:

t EF ? i,j? =t ES ? i,j? +t ? i,j? 或 t EF ? i,j? =TE ? i ? +t ? i,j?

300

返回总目录
⑵工序的最迟必须开工时间与最迟必须完工时间。
一个工序 ? i,j? 的最迟必须开工时间用 t LS ? i,j? 表示,它是工序 在不影响整个任务如期完成的前提下,必须开始的最晚时间。

工序 ? i,j?最迟必须完工时间用

t LF ? i,j?

表示,它表示工作 ? i,j?按

最迟时间开工,所能达到的完工时间。 由于工序 ? i,j? 最迟必须完工时间是事项j的最晚时间 TL ? j? ,

因此

t LF ? i,j? ? TL ? j?

t LS ? i,j? =TL ? j? -t(i,j)

t EF ? i,j? =TE ? i ? +t ? i,j?
TE ? i ? =t ES ? i,j? i

j t LF ? i,j? ? TL ? j?

t LS ? i,j? =TL ? j? -t(i,j)
301

返回总目录
? ⑴ 时差 工序的时差,又称为工序的松驰时间,工序时差分两种: 工序总时差 R

? i,j?

在不影响工程最早结束的条件下,工序最早开工(或完工)时间可 以推迟的时间: R

? i,j? =t LS ? i,j? -t ES ? i,j? =t LF ? i,j? -t EF ?i,j?
t ? i,j?

易知:R ? i,j? =TL ? j? -TE ? i ? -t ? i,j?

TE ? i ?





R ? i,j?

TL ? j?

? 总时差为零的工序,开始和结束的时间没有一点机动的余地,由这些 工序所组成的路线就是网络中的关键路线,这些工序就是关键工序。
302

返回总目录
例9 确定例8网络图的关键路线 解:(1)先用图上计算法求解,
10 10 3 4 4 2 A 0 0 1 4 D 6 C 3 E 18 18 20 20 8 F 4 5 2 23 23 G 3 6 K 31 31 9 L 1 J 5 25 26 8 32 32 10


I 8

B 10

23 23 7




? TE ?1? =0 ? ? ? ?T ? j? = max ?T ? i ? +t ? i,j? ? E ? E ? (i,j)?A ? ?

? TL ? n ? =TE ? n ? ? ? ? ?T ? i ? = min T ? j? -t ? i,j? ? ?L ? L ? (i,j)?A ? ?
303

返回总目录
⑵工序时间 ⑶时差 根据网络图中各事项时间参数 TE ? i ? ,TL ? i ? ,可以求出各工序的时间 参数 t ES ? i,j? ,t EF ? i,j? ,t LS ? i,j? ,t LF ? i,j? 和总时差 R ? i,j? 。
工序

t ?i , j ?
4 10

t ES ?i , j ? t EF ?i , j ? t LS ?i , j ? t LF ?i , j ? R?i , j ?
0 0 4 10 0 13 4 0 13

关键工序

i
1

TE
0

TL
0

A(1,2) B(1,7)

√ ×

C(2,4)
D(2,3) E(3,4) F(4,5) G(5,6)

3
6 8 2 3

4
4 10 18 20

7
10 18 20 23

15
4 10 18 20

23 18
10 18 20 23 23 26 31 31 31 32

2
3

4
10

4
10

11
0 0 0 0

×
√ √ √ √

4 5
6 7 8 9 10

18 20
23 23 25 31 32

18 20
23 23 26 31 32

虚(6,7)
H(7,8) I(7,9) J(8,9) K(6,9) L(9,10)

0
2 8 5 2 1

23
23 23 25 23 31

23
25 31 30 25 32

23
24 23 26 29 31

0
1 0 1 6 0


× √ × × √

= - 304

返回总目录
由总时差为0的 工序组成关键路线 ,即:①→②→③ →④→⑤→⑥→⑦ →⑧→⑨→⑩,总 工期为32周。
工序

R?i , j ?
0

关键工序

工序

R?i , j ?
0

关键工序

A(1,2)



虚(6,7)



B(1,7)
C(2,4) D(2,3) E(3,4)

13
11 0 0

×

赞助商链接
相关文章:
运筹学基础(第2版)何坚勇 第二三章习题答案
搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...运筹学作业2(清华版第二... 3页 免费运...P54 定理 2.4.3 线性规划问题的每一个基本可行解对应...
运筹学基础自考复习资料
搜试试 3 帮助 全部 DOC PPT TXT PDF XLS ...运筹学基础自考复习资料_教育学_高等教育_教育专区。...第二章 预测 一、预测的概念和程序 (一)预测的...
数学:运筹学基础(二)
运筹学PPT完整版 364页 1下载券 运筹学基础及应用(第五版... 98页 1下载券...2.4.1 一元线性回归模型预测法 Y=a+bx 最小二乘法 P19 2.5 季节性变动的...
运筹学基础复习要点
搜试试 3 帮助 全部 DOC PPT TXT PDF XLS ...运筹学基础简答 6页 免费 复习2 运筹学课件 胡运...运筹学基础(第二版) 207页 3下载券 喜欢此文档的...
运筹学基础简答
搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 工...运筹学基础(第二版) 207页 4下载券 运筹学基础串讲 38页 免费 基础运筹学试题...
2007-2014年全国高等教育自考02375运筹学基础_图文
搜试试 3 悬赏文档 全部 DOC PPT TXT PDF XLS ...2007-2014年全国高等教育自考02375运筹学基础_教育学...“树”的图形这样定义:第一必须是连通的;第二必须...
2010-7运筹学基础
搜试试 3 帮助 全部 DOC PPT TXT PDF XLS ...2010-7运筹学基础_教育学_高等教育_教育专区。全国...17.库存管理的目标一是实现均衡生产,二是使 ___达到...
运筹学基础及应用(第一二章习题解答)
运筹学基础及应用(第一二章习题解答)_理学_高等教育_教育专区。运筹学基础及应用 习题解答习题一 P46 1.1 (a) x2 4 x1 ? 2 x 2 ? 4 4 3 2 1 0 ...
运筹学课程教学大纲
第二运筹学研究的基本特征与基本方法 1 1、运筹学研究的基本特征;2、运筹...五、教学方法及手段课堂讲授:逐步完善电子教学手段,运用电子课件的形象教学和适度...
运筹学基础笔记(一纸开卷)_图文
运筹学基础笔记(一纸开卷) - 清华大学版《运筹学基础》期末考试笔记... 运筹学基础笔记(一纸开卷)_经济学_高等教育_教育专区。清华大学版《运筹学基础》期末考试笔...
更多相关文章: