数学建模-图论

初等数学方法建模

现实世界中有很多问题，它的机理较简单，用静态,线性或逻辑的方法即可建立模型，使用初等的数学方法，即可求解，我们称之为初等数学模型。本章主要介绍有关自然数，比例关系，状态转移，及量刚分析等建模例子，这些问题的巧妙的分析处理方法，可使读者达到举一反三，开拓思路，提高分析, 解决实际问题的能力。

第一节 有关自然数的几个模型

1.1鸽笼原理

鸽笼原理又称为抽屉原理，把N 个苹果放入)(N n n < 个抽屉里，则必有一个抽屉中至少有2个苹果。 问题1：如果有N 个人，其中每个人至多认识这群人中的)(N n n <个人（不包括自己），则至少有两个人所认识的人数相等。

分析：我们按认识人的个数，将N 个人分为n ,2,1,0 类，其中)0(n k k ≤≤类，表示认识k 个人，这样形成 1+n 个“鸽笼”。若 1-

问题2：在一个边长为1的正三角形内最多能找到几个点，而使这些点彼此间的距离大于5.0.

分析：边长为1的正三角形 ABC ?，分别以C B A ,,为中心，5.0为半径圆弧，将三角形分为四个部分（如图1-1 ），则四部分中任一部分内两点距离都小于5.0 ，由鸽笼原理知道，在三角形内最多能找四个点，使彼此间距离大于5.0 ，且确实可找到如C B A ,,及三角形中心四个点。

图1—1

问题3：能否在88?的方格表ABCD 的各个空格中，分别填写3,2,1这三个数中的任一个，使得每行，每列及对角线BD AC ,的各个数的和都不相同？为什么？

分析：若从考虑填法的种类入手，情况太复杂；这里我们注意到，方格表中行,列及对角线的总数为18个；而用3,2,1填入表格，每行,列及对角线都是8个数，8个数的和最小为8，

最大为24，共有171824=+-

种；利用鸽笼原理，18个“鸽”放入17个“鸽笼”，必有两个在一个“鸽笼”，也即必有两个和相同。所以题目中的要求，无法实现。

思考题：在一个边长为1的正三角形内，若要彼此间距离大于

n

1

，最多能找到几个点？ 1.2 “奇偶校验”方法 所谓 “奇偶校验”，即是如果两个数都是奇数或偶数，则称这两个数具有相同的奇偶性；若一个数是奇数，另一个数是偶数，则称具有相反的奇偶性。在组合问题中，经常使用“奇偶校验”考虑配对问题。

问题1（棋盘问题）：假设你有一张普通的国际象棋盘，一组对角上的两个方格被切掉，这样棋盘上只剩下62个方格（如图1—2）。若你还有31块骨牌，每块骨牌的大小为21?方格。试说明用互不重叠的骨牌完全覆盖住这张残缺的棋盘是不可能的。

分析：关键是对图1—2的棋盘进行黑白着色，使得相邻的两个方格有不同的颜色；用一块骨牌覆盖两个方格，必是盖住颜色不同的方格。我们计算一下黑白着色棋盘的黑格，白格个数，分别为30和32；因此不同能用31块骨牌盖住这张残缺的棋盘。用奇偶校验法，我们可以把黑色方格看成奇数方格，白色方格看成偶数方格；因为奇偶个数不同，所以不能进行奇偶配对，故题中要求的作法是不可能实现的。

问题2（菱形十二面体上的H 路径问题）：沿一菱形十二面体各棱行走，要寻找一条这样的路径它通过各顶点恰好一次，该问题被称为Hamilton 路径问题。

分析：我们注意到菱形十二面体每个顶点的度或者为3或者为4，所谓顶点的度是指通过这一顶点的棱数，如图1—3；且每3度顶点刚好与3个4度顶点相连，而每个4度顶点刚好与4个3度 顶点相连。因此一个Hamilton 路径必是3度与4度顶点交错，故若存在Hamilton 路径，则3度顶点个数，与4度顶点个数要么相等，要么相差1。用奇偶校验法3度顶点为奇数顶点，4度顶点为偶数顶点，奇偶配对，最多只能余

1个；而事实上菱形十二面体中，有3度顶点8个，4度顶点6个；可得结论，菱形十二面体中不存在Hamilton 路径.

思考题：1、设一所监狱有64间囚室，其排列类似88?棋盘，看守长告诉关押在一个角落里的囚犯，

只要他能够不重复地通过每间囚室到达对角的囚室（所有相邻囚室间都有门相通）,他将获释，问囚犯能否获得自由？

2、某班有49个学生，坐成7行7列，每个坐位的前后左右的坐位叫做它的邻座，要让49个学生都换到他的邻座上去，问是否有这种调换位置的方案？ 1.3 自然数的因子个数与狱吏问题

令 )(n d 为自然数 n 的因子个数，则 )(n d 有的为奇数，有的为偶数，见下表:

图1-2

图1-3

我们发现这样一个规律，当且仅当n 为完全平方数时,)(n d 为奇数；这是因为n 的因子是成对出现的,也即 ab n =; 只有n 为完全平方数, 才会出现 2

a n =的情形，)(n d 才为奇数。

下面我们利用上述结论研究一个有趣的问题.

狱吏问题：某王国对囚犯进行大赦，让一狱吏n 次通过一排锁着的n 间牢房，每通过一次按所定规则转动门锁, 每转动一次, 原来锁着的被打开, 原来打开的被锁上；通过n 次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第k 次通过牢房，从第k 间开始转动，每隔k-1 间转动一次；问通过n 次后，那些牢房的锁仍然是打开的？

问题分析： 牢房的锁最后是打开的，则该牢房的锁要被转动奇数次；如果把n 间牢房用n ,,2,1 编号，则第k 间牢房被转动的次数，取决于k 是否为n ,,2,1 整除，也即k 的因子个数，利用自然数因子个数定理，我们得到结论：只有编号为完全平方数的牢房门仍是开着的。 1．4 相识问题

问题：在6人的集会上，总会有3人互相认识或互相不认识。

分析：设6人为621,,,A A A ;下面分二种情形，1.1A 至多只和两个人相识，不妨设1A 不认识432,,A A A ；若432,,A A A 互相都认识，则结论成立，若432,,A A A 中有两人不认识，则加上1A

，有三人互不相识. 2．1A 至少和三人相识，不妨设1A 认识432,,A A A ；若432,,A A A 互不相识结论成立，若432,,A A A 有两人相识，加上1A 则有三人互相认识 。这样，我们就证明了结论成立,这个问题的讨论，我们也可以采用几何模似的方法，如图1—4

在平面上画出六个点，表示6个人，两点间存在连线，表示两人相识；只需说明，图中必有三点组成三角形（有三人相识），或有三点之间设有一条连线（三人互不相识）即可，

第二节 状态转移问题

本节介绍两种状态转移问题，解决这种问题的方法,有状态转移法，图解法及用图的邻接距阵等。

2．1 人、狗、鸡、米问题

人、狗、鸡、米均要过河，船上除1人划船外，最多还能运载一物，而人不在场时，狗要吃鸡，鸡要

图1-4

吃米，问人，狗、鸡、米应如和过河？

分析：假设人、狗、鸡、米要从河的南岸到河的北岸，由题意，在过河的过程中， 两岸的状态要满足一定条件，所以该问题为有条件的状态转移问题。

1. 允许状态集合 我们用（w, x, y, z ），w, x, y, z=0或1，表示南岸的状态，例如（1，1，1，1）表示它们都在南岸，（0，1，1，0）表示狗，鸡在南岸，人，米在北岸；很显然有些状态是允许的，有些状态是不允许的，用穷举法可列出全部10个允许状态向量，

(1, 1, 1, 1) (1, 1, 1, 0) (1, 1, 0, 1) (1, 0, 1, 1) (1, 0, 1, 0) (0, 0, 0, 0) (0, 0, 0, 1) (0, 0, 1, 0) (0, 1, 0, 0) (0, 1, 0, 1) 我们将上述10个可取状态向量组成的集合记为S ，称S 为允许状态集合 2、状态转移方程

对于一次过河，可以看成一次状态转移，我们用向量来表示决策，例（1，0，0，1）表示人，米过河。令D 为允许决策集合，

D={ (1, x, y, z) : x+y+z=0 或 1}

另外，我们注意到过河有两种，奇数次的为从南岸到北岸，而偶数次的为北岸回到南岸，因此得到下述转移方程，

k k

k k d S S )1(1-+=+ ------------------------(2.1)

),,,(k k k k k z y x w S =表示第k 次状态，D d k ∈ 为决策向量.

图2-1

2. 人、狗、鸡、米过河问题，即要找到D d d d m ∈-121,,, ，S S S S m ∈,,,10 )0,0,0,0(0=S

)1,1,1,1(=m S 且满足（2.1）式。

下面用状态转移图求解

将10个允许状态用10个点表示，并且仅当某个允许状态经过一个允许决策仍为允许状态，则这两个允许状态间存在连线，而构成一个图, 如图2—1 , 在其中寻找一条从（1，1，1，1）到（0，0，0，0）的路径，这样的路径就是一个解, 可得下述路径图,

由图2—2，有两个解都是经过7次运算完成，均为最优解 2．2 商人过河问题

三名商人各带一个随从乘船渡河，现有一只小船只能容纳两个人，由他们自己划行，若在河的任一岸的随从人数多于商人，他们就可能抢劫财物。但如何乘船渡河由商人决定，试给出一个商人安全渡河的方案。

首先介绍图论中的一个定理

G 是一个图，V （G ）为G 的顶点集，E(G)为G 的边集。 设G 中有n 个顶点n v v v ,,,21 ;

n n ij a A ?=)(为G 的邻接距阵，其中

??

??∈=)

(0

)(1

G E v v G E v v a j i j i ij n j i ,,2,1, =

定理1：设)(G A 为图G 的邻接距阵，则G 中从顶点i v 到顶点j v ，长度为k 的道路的条数为k

A 中的i 行

j 列元素.

证： 对k 用数学归纳法

1=k 时，显然结论成立; 假设k 时，定理成立， 考虑 1+k 的情形.

记l

A 的i 行j 列元素为 2)

(≥l a l ij

, 因为 1+=?l l A A A , 所以

nj l

in j l i j l i l ij

a a a a a a a +++=+ 2211)

1( (2.2)

而从 i v 到 j v 长1+k 的道路无非是从i v 经k 步到某顶n l v l ≤≤1,再从l v 走一步到j v ；由归纳假设从i v 到l v 长为k 的道路共计k

il a 条，而从l v 到j v 长为1的道路为lj a 条，所以长为1+k 的从i v 经k 步到l v 再一步到j v 的道路共有lj k il a a

)

(条，故从i v 经1+k 步到j v 的路径共有∑=+=n

l lj k il k ij

a a a

1

)

()1(条. 下面分析及求解

假设渡河是从南岸到北岸，（m ，n ）表示南岸有m 个商人，n 个随从，全部的允许状态共有10个

)2,2()0,3()1,3()2,3()

3,3(54321=====v v v v v )0,0()

1,0()

2,0()

3,0()

1,1(109876=====v v v v v

以{}1021,,v v v V =为顶点集，考虑到奇数次渡河及偶数次渡河的不同，我们建立两个邻接距阵

图2-2

T A B A A A A =??

??

??=3210 其中 ???

????

?

????????=???

?

???

?

????????=???

?

???

?

?????

???=00000

1000011000

0110011000

00101

0000000001

0000000000

00000

0000001000

1110010110

321A A A

其中A 表示从南岸到北岸渡河的图的邻接距阵，T A B =表示从北岸到南岸渡河的图的邻接距阵。 由定理1、我们应考虑最小的k ，A AB t

s k )(? 中1行10列的元素不为0，此时12+k 即为最少的

渡河次数，而矩阵A AB k

)(中1行10列的元素为最佳的路径数目。

经过计算K=5时, A AB 5

)(的第1行10列元素为2，所以需11次渡河，有两条最佳路径. 最后我们用图解法求解：

前面我们已求出问题的10种允许状态，允许决策向量集合{}2,1:),(=+=v u v u D ,状态转移方程为

k k k k d S S )1(1-+=+ , 如图2—3，标出10种允许状态，找出从1s 经由允许状态到原点的路径，该路径还

要满足奇数次向左，向下；偶数次向右, 向上.

由图2—3可得这样的过河策略，共分11次决策

图2--3

去一商一随

（2，2）

（3，3）

回一商

（3，2）

去二随

（3，0）

回一随

（3，1）

去二商

（1，1）

回一商一随

（2，2）

去二商

（0，2）

回一随

（0，3）

去二随

（0，1）

回一随

（0，2）

去二随

（0，0）

思考题：1、在商人过河中若有4名商人，各带一随从能否过河？

2、夫妻过河问题：有3对夫妻过河，船最多能载2人，条件是任一女子不能在其丈夫不在的情况下与其他男子在一起，如何安排三对夫妻过河？若船最多能载3人，5对夫妻能否过河？

3、量纲分析法

量纲分析是20世纪初提出的, 在物理领域中建立数学模型的一种方法，它是在经验和实验的基础上, 利用物理定律的量纲齐次原则，确定各物理量之间的关系。

3.1 量纲齐次原则与Pi 定理

许多物理量是有量纲的，有些物理量的量纲是基本的，另一些物理量的量纲则可以由基本量纲根据其定义或某些物理定律推导出来。例如在动力学中，把长度l , 质量m 和时间t 的量纲作为基本量纲，记为

[][][]T t M m L l ===,,; 而速度f v ，力的量纲可表示为[][]21,--==MLT f LT v .

在国际单位制中，有7个基本量：长度、质量、时间、电流、温度、光强度和物质的量，它们的量纲分别为L 、M 、T 、I 、Θ、J 、和N ；称为基本量纲。任一个物理量q 的量纲都可以表成基本量纲的幂次之积，

[]η

ξ

ε

δ

γ

β

α

J N I T M L q Θ=

量纲齐次性原则：用数学公式表示一个物理定律时，等式两端必须保持量纲一致。

量纲分析就是在保证量纲一致的原则下，分析和探求物理量之间关系；先看一个具体的例子，再给出量纲分析的一般方法。

例3—1： 单摆运动，质量为m 的小球系在长度为l 的线的一端，线的另一端固定，小球偏离平衡位置后，在重力mg 作用下做往复摆动，忽略阻力，求摆动周期t 的表达式。 解：在这个问题中有关的物理量有g l m t ,,,设它们之间有关系式

3

211αααλg l m t =

---------------（3.1）

其中32,,ααα为待定常数，入为无量纲的比例系数，取（3．1）式的量纲表达式有

[][][][]3

2

1

α

ααg l m t = 整理得：33

212αααα

-+=T L

M T --------------（3.2）

由量纲齐次原则应有

??

?

??=-=+=1

200

3321αααα ---------------（3.3） 解得：,2

1

,2

1

,0321-

==

=ααα 代入（3．1）得 g

l

t λ= -------（3.4）

（3.4）式与单摆的周期公式是一致的

下面我们给出用于量纲分析建模的 Buckingham Pi 定理， 定理：设n 个物理量n x x x ,,,21 之间存在一个函数关系

()0,,,21=n x x x f --------------（3.5）

[][]m x x 1为基本量纲，n m ≤。1x 的量纲可表示为

n i x x ij

j m

j i ,,2,1]

[][1

===α∏

矩阵m n ij A ?=)(α称为量纲距阵，若,r RankA =则（3.5）式与下式等价，

0)(21=-r n F πππ

其中F 为一个未定的函数关系，s π为无量纲量，且s π可表示为

)

(1

s i i

n

i s x βπ∏== -----------(3.6)

而)()

()(2)(1)

(s n s s s ββββ

=为线性齐次方程组0=βT A 的基本解向量.

利用Pi 定理建模，关键是确定与该问题相关的几个基本量纲的无量纲量r n -πππ 21, 作为量纲分析法的应用，下面我们介绍航船阻力的建模.

3．2 航船的阻力，

长l 吃水深度h 的船以速度v 航行，若不考虑风的影响，航船受到的阻力f 除依赖于船的诸变量

v h l 、、以外，还与水的参数——密度P ，粘性系数μ, 以及重力加速度g 有关。

我们利用pi 定理分析f 和上述物理之间的关系 1． 航船问题中涉及的物理量及其量纲为

?????

??????=======------2

1131

2][][][][][][][LT g MT L M L LT v L

h L l LMT f μρ 我们要寻求的关系式为

0),,,,,,(=g v h l f μρ? ---------------（3.7）

这些物理量中涉及到的基本量纲为L 、M 、T 2． 写出量纲距阵

T

M L A T

??

????????------=210100201100011131111 3=A rank

3． 解齐次线性方程组0=βT

A , 可得 4=-A r a n k

n 个基本解向量

????

??

?---=-=-=-=T

T

T

T

）

、、、、、、（）

、、、、、、（、、、、、、、、、、、、00120210111010)1002010()0000110()4()3()2()1(ββββ 由（3.6）式，可给出4个无量量纲

???

?

??

?====------1

2241

32211ρπρμ

πππv fl lv g

lv lh - -------------------（3.8） 由Pi 定理，（3.7）等价于下列方程 0),,,(4321=Φππππ -------------------（3.9） 这里Φ是未定的函数

由（3.８）,（３.９）可得阻力f 的显式表达式，

),,(3212

2πππρψv l f = -------------------（3.10）

其中ψ是由（３.９）可得到的未知的函数关系,在力学上,

lg

v 称为Froude 数，记为Fr ;

μ

ρ

lv 称为

Reynold 数，记为Re , 因此（3.10）又可写为

Re),,(22Fr v l f h l ρψ= ------------------（3.11）

4. 下面我们利用物理模拟进一步确定航船在水中的阻力。

设:g v h l f g v h l f '''''''、、、、、、和、、、

、、、μρμρ分别表示模型和原型中的各物理量, 由(3.11)有

),lg ,(

2

2

μρρψlv v h l v l f = ),g

l ,(22μρψρ''

''''''''''='v l v h l v l f

当无量纲量

μ

ρμ

ρ

''

''=

'

''=

'

'

=v l lv v v h l h l g l lg

-------------------（3.12） 成立时 , 可得 ρ

ρ'

?

?? ??''='2

lv v l f f --------------------（3.13） 则此时由模型船的阻力f ，及其它的ρρ'''、、、、、v l v l ；可确定原型船的阻力f '.

下面,我们讨论一下(3.12)成立的条件,如果在实验中采用跟实际同样的水质,则 ;,μμ='='p p 又

g g '=

故可得 ： l

l v v l l v v h l h l '

=''

='

'

'

=

---------------------------（3.14） 要使得(3.14)成立 , 必有h h l l '='=,；也即模型船与原型船一样大，这显然排除了物理模拟的可

行性。若考虑选用不同的水质，,μμ≠'?t s 仍设 ρρ=' 则(3.12)式化为

μμ

'

?'=''

='''=l l v v l l v v h l h l ---------------------（3.15） 由(3.15)可得

2

3??

?

??'='l l μμ , 若按1：20的比例，μμ'?=0110，显然无法找到如此小的粘性系数的液体 实际上的一种近似处理方法是，在一定条件下Re 数的影响很小，这样可近似得到， )lg

,(

2

2

v h l v l f ρψ≈ 类似地分析，只要

l l

v v h l h l '

=''

'= 即有 3

??

? ??'='l l f f ----------------（3.16） 由（3.16）式就容易确定原型船的阻力f '

3.3 无量纲化 抛射问题

下面我们通过一个例子,介绍如何使用无量纲化方法简化模型。

抛射问题：在某星球表面以初速度v 竖直向上发射火箭，记星球半径为r ，星球表面重力加速度为g ，忽略阻力，讨论发射高度x 随时间T 的变化规律.

模型建立：设x 轴竖直向上，0=t 时 0=x ，火箭和星球质量分别记为1m 和2m ，由牛顿第二定律和万有引力定律可得:

2

2

11)(r x m m k x m +-=

-----------------------（3.17）

以g x

x -==)0(,

0)0( 代入（3.17）可得 22gr km = 故得如下初值问题

???

?

??

?==+-=v x

x y x g

r x

)0(0

)0()(2

2 ----------------------（3.18） (3.18)式的解可以表为 )(g v r t x 、、、= 也即发射高度是以 g v r 、、 为参数的t 的函数,下面我们采用无量纲化方法化简方程（3.18）,

显然抛射问题中的基本量纲为 ;,T

L 而21][][][][][--=====LT g LT v L r T t L x

所谓无量纲化是指，对(3.18)式中的x 和t 分别构造且有相同的参数组合c x 和c t ，使得新变量 0

t t t x x x =

=

为无量纲量，其中 c c t x ,

称为特征尺度或参考尺度；把方程（3.18）化为 x 对 t 的微分方程，

即可简化模型，如何寻找特征尺度，这里我们以c t 为例，首先写出参数g v r 、、的量纲距阵A ??

??

??--=21011

1A

t 的量纲向量为 T )1,0( 记为 : 0β

求解线性方程组 0ββ=A 得通解: T

T k )1,2,1()0,1,1(-+-=β

任取k ，即得到一种特征尺度，例如 0=k 得 1;

1

-==-k rv t c 得 2

1;1-

==-k vg t c 得1-=rg t c 同理可得x 的几种特征尺度12,-g v r 等

以下，我们利用不同的c x 和c t 化简（3.18） 1. 令 1,

-==rv t r x c c ; 则1

,-==rv t

t r

x

x

由 t

d x

d v x = , 2

22t d x d r v x = 代入(3.18)可得:

???

?

??

?

===+-=1)0(0

)0(,)

1(12

2

x

x rg v x x εε ----------（3.19） (3.19)式的解可表为 ),(εt x x =,含一个独立参数且ε为无量纲量. 2. 令 ,r x c = 1-=

rg t c , 类似地可将(3.18)化为 :

???

????===+-=rg v x

x x x

22

,)0(0

)0(,

)1(1

εε ---------------（3.20）

3. 令 ,120-=g v x ;1

0-=vg t 可将(3.19)化为

???

?

??

?===+-=1)0(0

)0(,)

1(12

2

x

x rg v x x εεε ---------------（3.21） 按照现有科技能力, 秒米8000≈<

,1<<∴ε在（3.21）中令0=ε，则有

???

??==-=1

)0(0)0(1x x x

------------------------（3.22）

(3.22) 的解为: t t t x +-=2

)(2

, 代回原变量 得: vt gt t x +-

=2

2

1)( , ------------------------（3.23） (3.23)式恰为假定火箭运动过程中所受星球引力 不变的运动方程。

小结：无量纲化是用数学工具研究物理问题时常用的方法，恰当地选择特征尺度不仅可以减少参数的

个数，而且可以帮助人们决定舍弃哪些次要因素

第四节 比例与函数建模

本节介绍的几个模型,都是利用基本的比例关系与函数建立起的数学模型。

4.1 动物体型问题

问题： 某生猪收购站，需要研究如何根据生猪的体长（不包括头尾）估计其体重？

模型假设：

1． 将四足动物的躯干（不含头尾）视为质量为m 的圆柱体，长度为l ，截面面积s ，直径为d

如图4-1

图4-1

2． 把圆柱体的躯干看作一根支撑在四肢上的弹性梁，动物在体重f 作用下的最大下垂为δ，即梁的

最大弯曲，根据弹性力学弯曲度理论，有:

23

sd

fl ∞δ --------------------------（4.1）

3． 以生物进化学的角度，可认为动物的相对下垂度l δ已达到一个最合适的数值，也即l

δ

为常数 模型建立：

4

2

d s π=

; l d f 4

2

π=

- -----------------------（4.2）

由（1）式 可令 2

3

1sd fl k =δ 1k 为比例常数

由（2）式 222222

1

41)4(4l

f l l d sd ?=?=πππ ------------------------（4.3） f

l k 5

1

4πδ=∴

41

5

1

4

4

l l

k l k f ?=

=

∴δ

π

δ

π

令 δ

π

l

k k 1

4

=

由假设3，k 为常数

4kl f =∴ ------------------------（4.4）

因此生猪的体重与体长的四次方成正比，在实际工作中，工作人员可由实际经验及统计数据找出常数K ，

则可近似地由生猪的体长估计它的体重。

4．2 双重玻璃的功效

问题： 房间居室的窗户有的是双层的，即在窗户上装两层玻璃，且中间留有一定的空隙，试比较双层玻璃窗与单层玻璃窗的热量流失？

模型假设：1。设双层玻璃窗的两玻璃的厚度都为d ，两玻璃的间距为L ；单层玻璃窗的玻璃厚度为2d ，

所用玻璃材料相同，如图4-2

2．假设窗户的封闭性能很好，两层玻璃之间的空气不流动，即忽略热量的对流，只考虑热量的传导.

3. 室内温度1T 和室外温度2T 保持不变，热传导过程处于稳定状态，即单位时间通过单位面

积的热量为常数

4. 玻璃材料均匀，热传导系数为常数.

图4-2

模型建立：

对于厚度为d 的均匀介质，两侧温度差为T ?，则单位时间由温度高的一侧向温度低的一侧

通过单位面积的热量Q 满足 d

T

k Q ??

= k 为热传导系数

设玻璃的热传导系数为1k ，空气的热传导系数为2k （1） 先考虑单层玻璃的单位时间，单位面积的热量传导

d

T T k Q 22

111-?

= --------------------（4.5） （2） 考虑双层玻璃情形

此时热量先通过厚度为d 的玻璃传导到两层玻璃的夹层空气中，再通过空气传导，再通过

厚度为d 的玻璃传导；设内层玻璃的外侧温度为a T ，外层玻璃的内侧温度为b T ;则有:

d

T T k l T T k d T T k Q b b a a 2

1211

2-=-=-= ------------（4.6） 由（4.6）式可得

??

?

?

?

-=-+=+)

(2212

1T T d

l k k T T T T T T b b a b a ------------------（4.7）

记 d

k l

k s 11=

则 )(2221T T s T T T b b --+= ------------------（4.8）

)()(22212T T s T T T T b b ---=- - -----------------（4.9）

)(21

)(212T T S

T T b -+=- -------------（4.10） )()2(1

2112T T d

k S Q -+=

--------------（4.11）

考虑两者之比

s

Q Q +=2212 ---------------（4.12） 显然 12Q Q <, 也即双层玻璃的热量损失较小.

模型分析与应用：

常用玻璃的热传导系数 c s cm J

k ????=--3

3

110810

4 ，

而不流通,干燥空气的热传导系数 c

s cm J

k ???=-4

2105.2 ，

若取

h d

l

=, 则 h S h 3216≤≤ , 故

h

Q Q 81112+≤ ------------------（4.13）

若取 4=h ， 则

33

112≤Q Q 又此可见双层玻璃的保暖效果是相当可观的。 我国北方寒冷地区的建筑物，通常采用双层玻璃；由（4.13）式 h=4时, 1233

1

Q Q ≈

, h 再大，热量传递的减少就不明显了，再考虑到墙体的厚度；所以建筑规范通常要求 4≈h .

4.3 席位分配模型

问题：某校有200名学生，甲系100名，乙系60名，丙系40名；若学生会中学生代表有20个席位，则公平又简单的分法应各有10，6，4个席位。若丙系有6名学生分别转入甲、乙两系各3人，此时各系的人数为103，63，34；按比例席位分配应为10.3，6.3和3.4，出现了小数，19个整数席位分配完后，最后一席留给小数部分最大的丙系，分别为10，6，4。为方便提案表决，现增加1席共21席，按比例计算甲、乙、丙三系分别占有10.815，6.615，3.570；按上面的分法应分别为11，7，3；这样虽然增加了一个席位，但丙系的席位反而减少一席，因此这种分法显然是不合理的，请给出一个比较公平的席位分配方案？

问题分析： 席位分配问题，当出现小数时，无论如何分配都是不完全公平的。那么一个比较公平的分法是 应该找到一个不公平程度最低的方法，因此首先要给出不公平程度的数量化，然后考虑使之最小的分配方 案。

模型建立：

一、讨论不公平程度的数量化

设A ，B 两方人数分别为21,p p ；分别占有 1n 和 1n 个席位，则两方每个席位所代表的人数分别为

11n p 和 2

2n p

。 我们称

2

2

11n p n p - 为绝对不公平值。例：10,100,1202121====n n p p

则

22

2

11=-n p n p 又 10,1000,10202121====n n p p 则

22

2

11=-n p n p 由上例可知，用绝对不公平程度作为衡量不公平的标准，并不合理，下面我们给出相对不公平值

若 2211n p n p > 则称 112212222

11-=-

n p n p n p n p n p 为对A 的相对不公平值， 记为 ),(21n n r A

若 2211n p n p < 则称 121121

111

22-=-

n p n p n p n p n p 为对B 的相对不公平值 ，记为 ),(21n n r B

上例中，相对不公平值分别为：0.2 和 0.02，可见相对不公平值较合理。 二、 下面我们用相对不公平值建立模型，

设，A ，B 两方人数分别为 21,p p ；分别占有 1n 和 1n 个席位现在增加一个席位，应该给A 还是

B ？不妨设

2

2

11n p n p > ，此时对A 不公平，下面分二种情形 （1）

2

2111n p

n p ≥+ ，这说明即使A 增加1席，仍对A 不公平, 故这一席应给A 。 （2）

2

2111n p

n p <+ ， 说明A 方增加1席时，将对B 不公平，此时计算对B 的相对不公平值 1)

1(),1(2

11221-+=

+n p n p n n r B

若这一席给B ，则对A 的相对不公平值为 1)

1()1,(1

22121-+=

+n p n p n n r A

本着使得相对不公平值尽量小的原则，

若 )1,(),1(2121+<+n n r n n r A B ----------------------------（4.14） 则增加的1席给A 方，

若 ),1()1,(2121n n r n n r B A +<+ ----------------------------（4.15） 则增加的1席给B 方

由（4.14）式可得 ： )1()1(112

12222+<

+n n p n n p 由（4.15）式可得 ： )

1()1(112

12222+>

+n n p n n p 记 ： )

1(+=

i i i

i n n p Q 则增加的1席，应给Q 值大的一方

第一种情形，显然也符合该原则，

现在将上述方法推广到m 方分配席位的情况i A 方人数为i p 已占有i n 席 m i ,,2,1 =

计算 )

1(2

+=i i i i n n p Q 则将增加的1席分配应给?值最大的一方

下面考虑原问题：

前19席的分配没有争议，甲系得10席，乙系得6席，丙系得3席 第20席的分配

4.96)

110(101032

1=+=Q

5.94)16(6632

2=+=Q

3.96)

13(3342

3=+=Q

故第20席分配给甲系 第21席的分配

4.80)

111(111032

1=+=Q

3.96,

5

.9432==Q Q

故第21席分配给乙系

甲、乙、丙三系各分得11，6，4席，这样丙系保住它险些丧失的1席。

第五章 图与网络模型及方法

§1 概论

图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷22+n n H C 的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。

图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当

然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。

图与网络是运筹学（Operations Research ）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、

最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。

我们首先通过一些例子来了解网络优化问题。 例1 最短路问题（SPP －shortest path problem ）

一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。

例2 公路连接问题

某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？

例3 指派问题（assignment problem ）

一家公司经理准备安排N 名员工去完成N 项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？

例4 中国邮递员问题（CPP －chinese postman problem ）

一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。

例5 旅行商问题（TSP －traveling salesman problem ）

一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。

例6 运输问题（transportation problem ）

某种原材料有M 个产地，现在需要将原材料从产地运往N 个使用这些原材料的工厂。假定M 个产地的产量和N 家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？

上述问题有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization ）问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network ）。与图和网络相关的最优化问题就是网络最优化或称网络优化 （netwok optimization ）问题。所以上面例子中介绍的问题都是网络优化问题。由于多数网络优化问题是以网络上的流（flow ）为研究的对象，因此网络优化又常常被称为网络流（network flows ）或网络流规划等。

下面首先简要介绍图与网络的一些基本概念。 §2 图与网络的基本概念

2.1 无向图

一个无向图(undirected graph)G 是由一个非空有限集合)(G V 和)(G V 中某些元素的无序对集合)(G E 构成的二元组，记为))(),((G E G V G =。其中},,,{)(21n v v v G V =称为图G 的顶点集（vertex set ）或节点集（node set ）， )(G V 中的每一个元素),,2,1(n i v i =称为该图的一个顶点（vertex ）或节点（node ）；

},,,{)(21m e e e G E =称为图G 的边集（edge set ），)(G E 中的每一个元素k e (即)(G V 中某两个元素j

i v v ,的无序对) 记为),(j i k v v e =或i j j i k v v v v e == ),,2,1(m k =，被称为该图的一条从i v 到j v 的边（edge ）。

当边j i k v v e =时，称j i v v ,为边k e 的端点，并称j v 与i v 相邻（adjacent ）；边k e 称为与顶点j i v v ,关联

（incident ）。如果某两条边至少有一个公共端点，则称这两条边在图G 中相邻。

边上赋权的无向图称为赋权无向图或无向网络（undirected network ）。我们对图和网络不作严格区分，因为任何图总是可以赋权的。

一个图称为有限图，如果它的顶点集和边集都有限。图G 的顶点数用符号||V 或)(G ν表示，边数用||E 或)(G ε表示。

当讨论的图只有一个时，总是用G 来表示这个图。从而在图论符号中我们常略去字母G ，例如，分别用ν,,E V 和ε代替)(),(),(G G E G V ν和)(G ε。

端点重合为一点的边称为环(loop)。

一个图称为简单图(simple graph)，如果它既没有环也没有两条边连接同一对顶点。 2.2 有向图

定义 一个有向图（directed graph 或 digraph ）G 是由一个非空有限集合V 和V 中某些元素的有序对集合A 构成的二元组，记为),(A V G =。其中},,,{21n v v v V =称为图G 的顶点集或节点集， V 中的每一个元素),,2,1(n i v i =称为该图的一个顶点或节点；},,,{21m a a a A =称为图G 的弧集（arc set ），A 中的每一个元素k a (即V 中某两个元素j i v v ,的有序对) 记为),(j i k v v a =或),,2,1(n k v v a j i k ==，被称为该图的一条从i v 到j v 的弧（arc ）。

当弧j i k v v a =时，称i v 为k a 的尾（tail ），j v 为k a 的头（head ），并称弧k a 为i v 的出弧（outgoing arc ），为j v 的入弧（incoming arc ）。

对应于每个有向图D ，可以在相同顶点集上作一个图G ，使得对于D 的每条弧，G 有一条有相同端点的边与之相对应。这个图称为D 的基础图。反之，给定任意图G ，对于它的每个边，给其端点指定一个顺序，从而确定一条弧，由此得到一个有向图，这样的有向图称为G 的一个定向图。

以下若未指明“有向图”三字，“图”字皆指无向图。 2.3 完全图、二分图

每一对不同的顶点都有一条边相连的简单图称为完全图(complete graph)。n 个顶点的完全图记为n K 。 若Y X G V =)(，Φ=Y X ，0||||≠Y X （这里||X 表示集合X 中的元素个数），X 中无相邻顶点对，Y 中亦然，则称G 为二分图(bipartite graph)；特别地，若Y y X x ∈?∈?,，则)(G E xy ∈，则称G 为完全二分图，记成|||,|Y X K 。

2.4 子图

图H 叫做图G 的子图（subgraph ），记作G H ?，如果)()(G V H V ?，)()(G E H E ?。若H 是G 的子图，则G 称为H 的母图。

G 的支撑子图（spanning subgraph ，又成生成子图）是指满足)()(G V H V =的子图H 。

2.5 顶点的度

设)(G V v ∈，G 中与v 关联的边数（每个环算作两条边）称为v 的度(degree)，记作)(v d 。若)(v d 是奇数，称v 是奇顶点(odd point)；)(v d 是偶数，称v 是偶顶点(even point)。关于顶点的度，我们有如下结果：

(i)

∑∈=V

v v d ε2)(

(ii) 任意一个图的奇顶点的个数是偶数。

2.6 图与网络的数据结构

网络优化研究的是网络上的各种优化模型与算法．为了在计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图与网络。一般来说，算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网络的5种常用表示方法：邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法。在下面数据结构的讨论中，我们首先假设),(A V G =是一个简单有向图，m A n V ==||,||，并假设V 中的顶点用自然数n ,,2,1 表示或编号，A 中的弧用自然数m ,,2,1 表示或编号。对于有多重边或无向网络的情况，我们只是在讨论完简单有向图的表示方法之后，给出一些说明。

（i ）邻接矩阵表示法

邻接矩阵表示法是将图以邻接矩阵（adjacency matrix ）的形式存储在计算机中。图),(A V G =的邻接矩阵是如下定义的：C 是一个n n ?的10-矩阵，即

n n n n ij c C ??∈=}1,0{)(， ?

?

??∈=.),(,0,

),(,1A j i A j i c ij

也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为0。可以看出，这种表示法非常简单、直接。但是，在邻接矩阵的所有2

n 个元素中，只有m 个为非零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络中查找弧的时间。

例7 对于右图所示的图，可以用邻接矩阵表示为

???

??

?

?

?

????????0110010100000100100000110

同样，对于网络中的权，也可以用类似邻接矩阵的n n ?矩阵表示。只是此时一条弧所对应的元素不再

是1，而是相应的权而已。如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权。

（ii ）关联矩阵表示法

关联矩阵表示法是将图以关联矩阵（incidence matrix ）的形式存储在计算机中．图),(A V G =的关联矩阵B 是如下定义的：B 是一个m n ?的矩阵，即

m

n m n ik b B ??-∈=}1,0,1{)(，