数学建模实例：人口预报问题

数学建模实例：人口预报问题

1.问题

人口问题是当前世界上人们最关心的问题之一.认识人口数量的变化规律，

作出较准确的预报，是有效控制人口增长的前提.下面介绍两个最基本的人口模

型，并利用表1给出的近两百年的美国人口统计数据，对模型做出检验，最后用

它预报2000年、2010年美国人口.

表1美国人口统计数据

年（公17181818181818

元）90001020304050

人口（百3.5.7.9.121723

万）9326.9.1.2

年（公18181818191919

元）60708090001020

人口（百31385062769210

万）.4.6.2.9.0.06.5

年（公19191919191919

元）30405060708090

人口（百12131517202225

万）3.21.70.79.34.06.51.4

2.指数增长模型（马尔萨斯人口模型）

此模型由英国人口学家马尔萨斯（Malthusl766—1834）于1798年提出.

[1]假设：人口增长率〃是常数（或单位时间内人口的增长量与当时的人口

成正比）.

[2]建立模型：记时刻上0时人口数为x。,时刻「的人口为山），由于量大,

W）可视为连续、可微函数到，+△，时间内人口的增量为：

2）-矶次）

N

于是."）满足微分方程：

r<±x

--------=KJC

\"⑴

[x（。）=X。

[3]模型求解：解微分方程（1）得

九"）二/e"（2）

表明：ffoo时，378（r>0）.

[4]模型的参数估计：

要用模型的结果（2）来预报人口，必须对其中的参数「进行估计，这可以

用表14的数据通过拟合得到.拟合的具体方法见本书第16章或第18章.

通过表中1790—1980的数据拟合得：r=0307.

[5]模型检验：

将xo=3.9,r=0.307代入公式（2）,求出用指数增长模型预测的1810

—1920的人口数，见表2.

表2美国实际人口与按指数增长模型计算的人口比较

年实际人口指数增长模型

（公元）（白力）预测人口（百误差（％）

万）

17903.9

18005.3

18107.27.31.4

18209.610.04.2

183012.913.76.2

184017.118.79.4

185023.225.610.3

186031.435.010.8

187038.647.823.8

188050.265.530.5

189062.989.642.4

190076.0122.561.2

191092.0167.682.1

1920106.5229.3115.3

从表2可看出，1810—1870间的预测人口数与实际人口数吻合较好，但

1880年以后的误差越来越大.

分析原因，该模型的结果说明人口将以指数规律无限增长.而事实上，随

着人口的增加，自然资源、环境条件等因素对人口增长的限制作用越来越显著.

如果当人口较少时人口的自然增长率可以看作常数的话，那么当人口增加到一

定数量以后，这个增长率就要随着人口增加而减少.于是应该对指数增长模型关

于人口净增长率是常数的假设进行修改.下面的模型是在修改的模型中著名的一

个.

3.阻滞增长模型（logistic模型）

⑴假设।

（a）人口增长率厂为人口前的函数6）（减函数），最简单假定

r（x）=r-5x,r,5>0（线性函数），厂叫做固有增长率.

（b）自然资源和环境条件年容纳的最大人口容量工…

[2]建立模型：

当X=/时，增长率应为0,即-&）=0,于是s=1，代入曲）="SX

m

得：

将（3）式代入（1）得:

dx,x

—=r1-------x

模型:出I(4)

耳。)=%

[3]模型的求解:解方程组(4)得(5)

dr

根据方程(4)作出?-X曲线图，见图1,由该图可看出人口增长率

出

随人口数的变化规律.根据结果(5)作出X-/曲线，见图2,由该图可看出人口

数随时间的变化规律.

[4]模型的参数估计：

利用表1中1790—1980的数据对r和4拟合得：r=0.2072,=464.

[5]模型检验：

将r=0.2072,%=464代入公式(5),求出用指数增长模型预测的1800-

1990的人口数，见表3第3、4列.

也可将方程(4)离散化，得

+1)=3)+Ax=x(f)+r(l--)x(t)Z=0,l,2,...,(6)

用公式(6)预测1800—1990的人口数，结果见表3第5、6列.

表3美国实际人口与按阻滞增长模型计算的人口比较

实阻滞增长模型

年际公式（5）公式（6）

人预测人口误差预测人口误差

□（百万）(%)（百万）(%)

（百

万）

1793.9

0

1805.35.90250.11373.90000.2642

0

1817.27.26140.00856.50740.0962

0

1829.68.93320.06958.68100.0957

0

18312.10.98990.148111.41530.1151

09

18417.13.52010.209415.12320.1156

01

18523.16.63280.283119.81970.1457

02

18631.20.46210.348326.52280.1553

04

18738.25.17310.347835.45280.0815

06

18850.30.96870.383143.53290.1328

02

18962.38.09860.394356.18840.1067

09

19076.46.86990.383370.14590.0770

00

19192.57.66070.373384.73050.0790

fulU

19210670.93590.3339102.46260.0379

0.5

19312387.26740.2917118.95090.0345

0.2

194131107.35880.1848137.88100.0469

0.7

195150132.07590.1236148.79780.0126

0.7

196179162.48350.0938170.27650.0503

0・3

197204199.89190.0201201.17720.0138

0.0

198226245.91270.0857227.57480.0047

0.5

199251302.52880.2034250.44880.0038

0.4

[6]模型应用：

现应用该模型预测人口.用表1中1790-1990年的全部数据重新估计参

数，可得r=0.2083,%=4576用公式(6)作预测得:

x(2000)=275;x(2010)=297.9.

也可用公式(5)进行预测.

双层玻璃的功效

北方城镇的有些建筑物的窗户是双层的，即窗户上装两层厚度为

〃的玻璃夹着一层厚度为/的空气，如左图所示，据说这样做是为了

保暖，即减少室内向室外的热量流失.

我们要建立一个模型来描述热量通过窗户的热传导（即流失）过

程，并将双层玻璃窗与用同样多材料做成的单层玻璃窗（如右图，玻

璃厚度为2d）的热量传导进行对比，对双层玻璃窗能够减少多少热

量损失给出定量分析结果.

墙墙i

Tt

热传导方向

墙墙

一、模型假设

1.热量的传播过程只有传导，没有对流,即假定窗户的密

封性能很好，两层玻璃之间的空气是不流动的；

2.室内温度7；和室外温度％保持不变，热传导过程已处于

稳定状态，即沿热传导方向，单位时间通过单位面积的热量是

常数；

3.玻璃材料均匀，热传导系数是常数.

符号说明

十——室内温度

T2——室外温度

-单层玻璃厚度

两层玻璃之间的空气厚度

-内层玻璃的外侧温度

-外层玻璃的内侧温度

热传导系数

热量损失

三、模型建立与求解

由物理学知道，在上述假设下，热传导过程遵从下面的物理规律:

厚度为d的均匀介质，两侧温度差为则单位时间由温度高的

一侧向温度低的一例通过单位面积的热量为。，与△丁成正比，与“成

反比，即

其中％为热传导系数.

1.双层玻璃的热量流失

记双层窗内窗玻璃的外侧温度为7；,外层玻璃的内侧温度为〃，

玻璃的热传导系数为占，空气的热传导系数为七，由（1）式单位时

间单位面积的热量传导（热量流失）为：

由。=尤J^及。=匕幺言可得，一。二区一七）一2孚

aa4

再代入。=七^就将（2）中乙、。消去，变形可得：

a

2.单层玻璃的热量流失

对于厚度为2d的单层玻璃窗户，容易写出热量流失为：

3.单层玻璃窗和双层玻璃窗热量流失比较

比较⑶⑷有：（5）

显然，

为了获得更具体的结果，我们需要匕，包的数据，从有关资料可知,

不流通、干燥空气的热传导系数心=2.5x107（J/cm.s.℃）,常用玻璃

的热传导系数占=4x103〜8X103（J/cm.S.℃）,于是

2=16〜32

k2

在分析双层玻璃窗比单层玻璃窗可减少多少热量损失时，我们作

最保守的估计，即取g=16,由（3）（5）可得：

K2

Q1>I

—=--------/?=—（6）

Q8/2+1d

4.模型讨论

比值Q/。反映了双层玻璃窗在减少热量损失上的功效，它只与

有关，下图给出了Q/。'〜力的曲线，当力由0增加时，Q/Q'迅速

下降，而当〃超过一定值（比如〃>4）后2/Q，下降缓慢，可见〃不宜

选得过大.

这个模型具有一定的应用价值.制作双层玻璃窗虽然工艺复

杂会增加一些费用，但它减少的热量损失却是相当可观的.通常，建

筑规范要求〃=//cb4,按照这个模型，Q/0=3%,即双层玻璃窗比用

同样多的玻璃材料制成的单层窗节约热量97%左右.不难发现,之所以

有如此高的功效主要是由于层间空气的极低的热传导系数&，而这要

求空气是干燥、不流通的,作为模型假设的这个条件在实际环境下当

然不可能完全满足，所以实际上双层玻璃窗的功效会比上述结果差一

些

椅子能在不平的地面上放稳吗？

把椅子往不平的地面上一放，通常只有三只脚着地，放不稳，然

而只要稍挪动几次，就可以四脚着地，放稳了.下面用数学语言证明.

一、模型假设

对椅子和地面都要作一些必要的假设：

1.椅子四条腿一样长，椅脚与地面接触可视为一个点，四

脚的连线呈正方形.

2.地面高度是连续变化的，沿任何方向都不会出现间断

（没有像台阶那样的情况），即地面可视为数学上的连续曲面.

3.对于椅脚的间距和椅脚的长度而言，地面是相对平坦

的，使椅子在任何位置至少有三只脚同时着地.

二、模型建立

中心问题是数学语言表

示四只脚同时着地的条件、

结论.

首先用变量表示椅子的

位置，由于椅脚的连线呈正

方形，以中心为对称点，正

方形绕中心的旋转正好代表了椅子的位置的改变，于是可以用旋转角

度。这一变量来表示椅子的位置.

其次要把椅脚着地用数学符号表示出来，如果用某个变量表示椅

脚与地面的竖直距离，当这个距离为0时，表示椅脚着地了.椅子要

挪动位置说明这个距离是位置变量的函数.

由于正方形的中心对称性，只要设两个距离函数就行了，记4

。两脚与地面距离之和为/（。），B、。两脚与地面距离之和为g®）,显

然Mge)NO,由假设2知八g都是连续函数，再由假设3知小)、

g(8)至少有一个为0.当。=0时，不妨设ge)=ojM)>o,这样改变椅

子的位置使四只脚同时着地，就归结为如下命题:

命题已知/⑹、g®)是e的连续函数，对任意*/(e)*g®)=0,

且g(o)=oj(o)>o,则存在/，使g®o)=/®o)=O.

三、模型求解

将椅子旋转901对角线ZC和8。互换，由g(O)=O"(O)>O可知

8(乃/2)>0,/(4/2)=0.令〃(0)=8(。)—/(0),则力(0)>0,力(乃/2)<0,由八g的

连续性知/?也是连续函数，由零点定理，必存在%(0<%(乃/2)使

蚓=o,g®o)=f®0),由g(q)x/(q)=o,所以g(%)=/(%)=o.

四、评注

模型巧妙在于用一元变量。表示椅子的位置，用。的两个函

数表示椅子四脚与地面的距离.利用正方形的中心对称性及旋转90。并

不是本质的，同学们可以考虑四脚呈长方形的情形.

钢管订购和运输优化模型

要铺设一条A->A2f…的输送天然气的主管道，如图1所示（见反面）.经筛

选后可以生产这种主管道钢管的钢厂有S?,,S?.图中粗线表示铁路，单细线表示公路,

双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车

站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位：km）.

为方便计，1km主管道钢管称为1单位钢管.

一个钢厂如果承担制造这种钢管，至少需要生产500个单位.钢厂S：在指定期限内能生

产该钢管的最大数量为4个单位，钢管出厂销价1单位钢管为P,万元，如下表：

i1234567

80080010002000200020003000

Pi160155155160155150160

1单位钢管的铁路运价如卜表:

里程（程）<300301〜350351〜400401〜450451〜500

运价（万元）2023262932

里程（km）501-600601〜700701~800801〜900901~1000

运价（万元）3744505560

1000km以上每增加1至100km运价增加5万元.

公路运输费用为1单位钢管每千米0.1万元（不足整千米部分按整千米计算）.

钢管可由铁路、公路运往铺设地点（不只是运到点A「A2,…,而是管道全线）•

问题：

（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用）.

思考题：

（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大,

哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结

果.

（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，

请就这种更一般的情形给出一•种解决办法，并对图2按（1）的要求给出模型和结果.

图1

力

4

图2

一、基本假设

1.沿铺设的主管道以有公路或者有施工公路.

2.在主管道上，每千米卸1单位的钢管.

3.公路运输费用为1单位钢管每千米0.1万元（不足整千米部分按整千米计算）

4.在计算总费用时，只考虑运输费和购买钢管的费用，而不考虑其他费用.

5.在计算钢厂的产量对购运计划影响时，只考虑钢厂的产量足够满足需要的情况，即钢厂

的产量不受限制.

6.假设钢管在铁路运输路程超过1000km时，铁路每增加1至100km,1单位钢管的运价

增加5万元.

二、符号说明：

S,:第i个钢厂；i=l,2,…,7

2：第i个钢厂的最大产量；i=12…,7

A,:输送管道（主管道）上的第/个点；/=1,2,…J5

Pi：第，个钢厂1单位钢管的销价；i=12…,7

%:钢厂S,向点4运输的钢管量；i=12…,7/=1,2,…,15

：在点4.与点A川之间的公路上，运输点为向点八加方向铺设的钢管量；

/=1,2,3,…,14（八=0）

%：1单位钢管从钢厂S1.运到结点A,的最少总费用，即公路运费、铁路运费和

钢管销价之和；i=12…,7/=1,2,…,15

hj:与点4相连的公路和铁路的相交点；/=2,3,・一,15

A/J+]:相邻点4与A*之间的距离；J=1,2,…,14

三、模型的建立与求解

问题一：讨论如何调整主管道钢管的订购和运输方案使总费用最小

由题意可知，钢管从钢厂s,到运输结点勺的费用勺包括钢管的销价、钢管的铁路运输

费用和钢管的公路运输费吐在费用询最小时，对钢管的订购和运输进行分配，可得出本问

题的最佳方案.

1.求钢管从钢厂S,运到运输点A,•的最小费用

1）将图1转换为一系列以单位钢管的运输费用为权的赋权图.

由于钢管从钢厂S,.运到运输点A,要通过铁路和公路运输，而铁路运输费用是分段函

数，与全程运输总距离有关.又由于钢厂Sj直接与铁路相连，所以可先求出钢厂Sj到铁路与

公路相交点鸟的最短路径如图3

图3铁路网络图

依据钢管的铁路运价表，算出钢厂S,到铁路与公路相交点鸟的最小铁路运输费用，并

把费用作为边权赋给从钢厂s,到鸟的边.再将与鸟相连的公路、运输点儿及其与之相连的

要铺设管道的线路（也是公路）添加到图上，根据单位钢管在公路上的运价规定，得出每一

图4钢管从钢厂S1运到各运输点A.的铁路运输与公路运输费用权值图

2）计算单位钢管从4到4•的最少运输费用

根据图4,借助图论软件包中求最短路的方法求出单位钢管从a到4的最少运输费用

依次为：170.7,160.3,140.2,98.6,38,20.5,3.1,21.2,64.2,92,96,106,121.2,

128,142（单位：万元）.加上单位钢管的销售价P-得出从钢厂购买单位钢管运输到点

的最小费用％j依次为：3303320.3,300.2,258.6,198,180.5,163,1,181.2,224.2,

252,256.266,281.2,288,302（单位:万元）.

同理，可用同样的方法求出钢厂s2、S3、S,、S5、56、S7到点少的最小费用，从

而得出钢厂到点的最小总费用（单位：万元）为：

表1Sj到点4最小费用

AA/A///A//

5678910111231415

234

trt.

3321112428

120.300.258.69880.56381.224.25256661.28802

rc(

3332222/Q32•

60.345.226.66650.54126.269.29701116.23347

rrcr•

333222ZNN26*

75.355.236.67660.55141.203.23741516.27387

rrrf(

433V322///234

10.395.276.61600.59176.244.22211216.24357

rrr•

133V222Z1Z22

00.380.261.60185.57666.234.21288066.22842

q

433222/c1

05.385.266.60690.58171.234.212019576.26178

rr(<

443C322ZgN19

25.305.286.62610.50191.259.23726168.28662

2.建立模型

运输总费用可分为两部分：

运输总费用二钢厂到各点的运输费用+铺设费用.

运输费用：若运输点A,向钢厂Sj订购％.单位钢管，则钢管从钢厂Sj运到运输点

4所需的费用为旬,％.由于钢管运到A必须经过A2,所以可不考虑A,那么所有钢管从

157

各钢厂运到各运输点上的总费用为：

j=2i=\

铺设费用：当钢管从钢厂s,运到点&后，钢管就要向运输点4的两边44讨段和

A-4段运输（铺设）管道.设4响4A加段铺设的管道长度为），〃则勺向段的

运输费用为0.1x（l+2+…+力）=当"（万元）；日于相邻运输点勺与A川之间的距

离为勺.，那么勺+1向4A川段铺设的管道长为羽川一八所对应的铺设费用为

（万元）.所以，主管道上的铺设费用为：

y（“。+1）+（4川TJ+M/J+I-。）、

总费用为：/=£色冯+绊4J+区生二噂%匚）

f=lj=2六|IZUZUJ

又因为一个钢厂如果承担制造钢管任务，至少需要生产500个单位，钢厂，在指定期

1515

限内最大生产量为电个单位，故500工2勺4，或2勺=0因此本问题可建立如下

>2卜2

的非线性规划模型：

14匕色+1）।（Ajj+]-《）（4川+1-。）।157

min/=^（石力勺.传

2020-

j=i；=2M

7

E%=%j=2,3,…,15

J=1

1515

s.t.，500«Zxij-si或Zxa=°

j=2；=2

%之（）/=1,..,7,j=2,,15

0%”小

3.模型求解：

1515

由于MATLAB不能直接处理约束条件：500•或X%=0,我们可先将此条

六2j=2

件改为得到如下模型：

£/（r+1）（4加F）（A小+1-。）

m"=z（r—+――蟹--+zz%•%

J=1NUNU；=2i=l

%=njj=2,3,…,15

s.t.”圣

xtf>0i=l,…,7,j=2,…,15

°<J&Ajw

用MATLAB求解，分析结果后发现购运方案中钢厂S?的生产量不足500单位，下面

我们采用不让钢厂S：生产和要求钢厂S7的产量不小于500个单位两种方法计算：

1）不让钢厂S7生产

计算结果：/,=1278632（万元）（此时每个钢厂的产量都满足条件）.

2）要求钢厂5、的产量不小于500个单位

计算结果：（万元）（此时每个钢厂的产量都满足条件）.

f2=1279664

比较这两种情况，得最优解为，min/=nin（工,力）=工=1278632（万元）具体

的购运计划如表2:

表2问题一的订购和调运方案

订豉//////，//////

//

8004(I(((t(

tf

800z(Jc((((I(

1001-(((((((

0(((c(c((((

101(c((c(L((s(

155((((((((、(t

0((f(c((s/(

function[d,DD]=dijkstra(D,s)

%Dijkstra最短路算法Matlab程序用于求从起始点s到其它各点的最短路

%D为赋权邻接矩阵

%d为s到其它各点最短路径的长度

%DD记载了最短路径生成树

[m,n]=size(D);

d=inf*ones(l,m);

d(l,s)=0;

dd=zeros(l,m);

dd(l,s)=l;

y=s;

DD=zeros(m,m);

DD(y,y)=l;

counter=l;

whilelength(find(dd==l))<m

fori=l:m

ifdd(i)==0

d(i)=min(d(i),d(/)+D(y,i));

end

end

ddd=inf;

fori=l:m

ifdd(i)二二0&&d(i)<ddd

ddd=d(i);

end

end

yy=find(d==ddd);

counter=counter+l;

DD(y,yy(1.1))=counfpr：

DD(yy(l,l),y)=counter;

y=yy(i.i)：

dd(l,y)=l;

end

建模案例：最优截断切割问题

一、问题

从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两

个长方体的对应表面是平行的）,通常要经过6次截断切割.设水平切

割单位面积的费用是垂直切割单位面积费用的r倍,且当先后两次垂

直切割的平面（不管它们之间是否穿插水平切割）不平行时，因调整

刀具需额外费用e.试设计一种安排各面加工次序（称“切割方式”）

的方法，使加工费用最少.

二、假设

1.假设水平切割单位面积的费用为r,垂直切割单位面积费用

为1;

2.当先后两次垂直切割的平面（不管它们之间是否穿插水平切

割）不平行时，调整刀具需额外费用e;

3.第一次切割前，刀具已经调整完毕，即第一次垂直切割不加

入刀具调整费用；

4,每个待加工长方体都必须经过6次截断切割.

三、模型的建立与求解

设待加工长方体的左右面、前后面、上下面间的距离分别为

bO、cO,六个切割面分别位于左、右、前、后、上、下，将他们相

应编号为Ml、M2、M3、M4、M5、M6,这六个面与待加工长方体

相应外侧面的边距分aO别为ul、u2、u3xu4su5、u6.这样,一种

切割方式就是六个切割面的一个排列，共有"=720种切割方式.当考

虑到切割费用时，显然有局部优化准则：两个平行待切割面中，边距

较大的待切割面总是先加工.

p6

由此准则，只需考虑不一^=90种切割方式•即在求最

2!x2!x2!

少加工费用时，只需在90个满足准则的切割序列中考虑.不失一般性，

设ulNu2,u3>u4,u5>u6,故只考虑Ml在M2前、M3在M4前、M5

在M6前的切割方式.

1.e

=0的情况

图1G(V,E)

为简单起见,先考虑e=0的情况.构造如图的一个有向赋权网

络图G(V,E),为了表示切割过程的有向性，在网络图上加上坐标轴X,

y,z,图G(V,E)的含义为:

(1)空间网络图中每个结点Vi(xi,yi,zi)表示被切割石材所处的

一个状态.顶点坐标xi、yi、zi分别代表石材在左右、前后、上下方向

上已被切割的刀数.例如：V24(2,1,2)表示石材在左右方向上已被切割

两刀，前后方向上已被切一刀，上下方向上已被切两刀，即面Ml、

M2、M3、M5、M6均已被切割.顶点Vl(0,0,0)表示石材的最初待加

工状态，顶点V27(2,2,2)表示石材加工完成后的状态.

(2)G的弧(Vi,Vj)表示石材被切割的一个过程，若长方体能

从状态Vi经一次切割变为状态Vj,即当且仅当xi+yi+zi+1=xj+yj+zj

时，Vi(xi,yi,zi)到Vj(xj,yj,zj)有弧(Vi,Vj),相应弧上的权W(Vi,V”即为这

一切割过程的费用.

W(Vi,Vj)=(xj-xi)x(bixci)+(yj-yi)x(aixci)+(zj-zi)x(aixbi)xr

其中，ai、bi、ci分别代表在状态Vi时，长方体的左右面、

上下面、前后面之间的距离.

例如，状态V5(1,1,0),a5=a0-ul,b5=b0-u3,c5=c0;

状态V6(2,1,0)

W(V5,V6)=(b0-u3)xc0

(3)根据准则知第一刀有三种选择，即第一刀应切Ml、M3、

M5中的某个面，在图中分别对应的弧为(VI,V2),(VI,V4),(Vl,V10).

图G中从VI到V27的任意一条有向道路代表一种切割方式,从VI到V27

共有90条有向道路，对应着所考虑的90种切割方式.VI到V27的最短

路即为最少加工费用，该有向道路即对应所求的最优切割方式.

实例：待加工长方体和成品长方体的长、宽、高分别为10、

145、19和3、2、4,两者左侧面、正面、底面之间的距离分别为6、

7、9,则边距如下表：____________________________________

u2u3u4u5u

U16

6175569

r=10t,求得最短路为VI-V10-V13-V22-V23-V26-V27,

其权为374

对应的最优切割排列为M5-M3-M6-费

用为374元.

2.ewO的情况

当段0时，即当先后两次垂直切割的平面不平行时，需加调

刀费e.希望在图1的网络图中某些边增加权来实现此费用增加.在所有

切割序列中，四个垂直面的切割顺序只有三种可能情况：

〈情况一)先切一对平行面，再切另外一对平行面，总费用

比e=0时的费用增加e.

v情况二＞先切一个，再切一对平行面，最后割剩余的一个,

总费用比e=0时的费用增加2e.

v情况三＞切割面是两两相互垂直，总费用比e=0时的费用增

加3e.

在所考虑的90种切割序列中，上述三种情况下垂直切割面的

排列情形，及在图G中对应有向路的必经点如下表：

垂直切割面排列有向路必经点

情形

情况一（一）Ml-M2-M3(l,0,z),(2,0,z),(2,l,z)

-M4

情况一（二）M3-M4-M1(0,l,z),(0,2,z),(l,2,z)

-M2

情况二（一）M3-M1-M2(0,l,z),Q,l,z),(2,l,z)

-M4

情况二（二）M1-M3-M4(l,0,z),(：U,z),(12z)

-M2

情况三（一）Ml-M3-M2(lQ,z),Q,l,z),(2,l,z)

-M4

情况三（二）M3-M1-M4(0,l,z),(Ll,z),Q2z)

-M2

z=0,l,2

我们希望通过在图1的网络图中的某些边上增加权，来进行

调刀费用增加的计算，但由于网络图中的某些边是多种切割序列所公

用的.对于某一种切割序列，需要在此边上增加权6但对于另外一种

切割序列，就有可能不需要在此边上增加权e,这样我们就不能直接

利用图1的网络图进行边加权来求最短路径.

由上表可以看出，三种情况的情形（一）有公共点集

｛（2,l,z）|z=0,l,2｝,情形（二）有公共点集｛（l,2,z）忆=0,1,2｝.且情形（-）

的有向路决不通过情形（二）的公共点集，情形（二）的有向路也不

通过情形（一）的公共点集.所以可判断出这两部分是独立的、互补的.

如果我们在图G中分别去掉点集｛（L2,z）|z=0,l,2｝和｛（2,l,z）|z=0,L2｝及

与之相关联的入弧，就形成两个新的网络图，如图H1和H2.这两个网

络图具有互补性,对于一个问题来说，最短路线必存在于它们中的某一

个中.

由于调整垂直刀具为3次时，总费用需增加3e,故我们先安

排这种情况的权增加值e,每次转刀时，给其待切弧上的权增加e.增加

e的情况如图2中所示,再来判断是否满足调整垂直刀具为二次、一次时

的情况，我们发现所增加的权满足另外两类切割序列.

综合上述分析，我们将原网络图G分解为两个网络图H1和H2,

并在指定边上的权增加e,然后分别求出图H1和H2中从VI到V27的

最短路，最短路的权分别为：dl,d2.则得出整体的最少费用为:d=

min(dl,d2),最优切割序列即为其对应的最短路径.

实例：r=15,e=2时，求得图G1与G2的最短路为G2的路VI-V4

-V5-V14-V17-V26-V27,权为4435,对应的最优切割序列为

M3-Ml-M6-M4-M5-M2,最优费用为4435.

图3H2

建模案例:最佳灾情巡视路线

这里介绍1998年全国大学生数学模型竞赛B题中的两个问题.

一、问题

今年夏天某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部

门负责人到全县各乡（镇）、村巡视.巡视路线指从县政府所在地出发，走遍各乡

（镇八村，又回到县政府所在地的路线.

1.若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的路线.

2.假定巡视人员在各乡（镇）停留时间T=2ht在各村停留时间t=lh9汽

车行驶速度H35km/h.要在24h内完成巡视，至少应分几组；给出这种分组下

最佳的巡视路线.

乡镇、村的公路网示意图见图1.

图1

二、假设

1.汽车在路上的速度总是一定，不会出现抛锚等现象；

2.巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误

时间；

3.每个小组的汽车行驶速度完全一样；

4.分组后，各小组只能走自己区内的路，不能走其他小组的路（除公共路

外）・

三、模型的建立与求解

将公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村之

间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边

上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中

寻找从给定点0出发，行遍所有顶点至少一次再回到。点，使得总权（路程或

时间）最小，此即最佳推销员回路问题.

在加权图G中求最佳推销员回路问题是NP—完全问题，我们采用一种近似

算法求出该问题的一个近似最优解，来代替最优解，算法如下：

算法一求加权图G（I4£）的最佳推销员回路的近似算法：

1.用图论软件包求出G中任意两个顶点间的最短路，构造出完备图

ZAG

C（V,E'）,V（,y）E',矶x,y）=mindc（x,y）;

2.输入图G'的一个初始々圈；

3,用对角线完全算法产生一个初始〃圈；

4.随机搜索出G'中若干个〃圈，例如2000个；

5.对第2、3、4步所得的每个〃圈，用二边逐次修正法进行优化，得到近

似最佳H圈；

6.在第5步求出的所有“圈中，找出权最小的一个，此即要找的最佳〃圈

的近似解.

由于二边逐次修正法的结果与初始圈有关，故