数学建模例题及解析

例1差分方程——资金的时间价值

问题1:抵押贷款买房——从一则广告谈起

每家人家都希望有一套（甚至一栋）属于自己的住房，但又没有足够的资金

一次买下，这就产生了贷款买房的问题。先看一下下面的广告（这是1991

年1月1口某大城市晚报上登的一则广告），任何人看了这则广告都会产生

许多疑问，且不谈广告中没有谈住房面积、设施等等，人们关心的是：如

果一次付款买这栋房要多少钱呢银行贷款的利息是多少呢为什么每个月

要付12。。元呢是怎样算出来的因为人们都知道，若知道了房价（一次付款

买房的价格），如果自己只能支付一部分款，那就耍把其余的款项通过借贷

方式来解决，只要知道利息，就应该可以算出五年还清每月要付多少钱才

能按时还清贷款了，从而也就可以对是否要去买该广告中所说的房子作出

决策了。现在我们来进行数学建模。由干本问题比较简单无需太多的抽象

和简化。

a.明确变量、参数，显然下面的量是要考虑的：

需要借多少钱，用记；

月利率（贷款通常按复利计）用R记；

每月还多少钱用x记；

借期记为N个月。

b.建立变量之间的明确的数学关系。若用记第k个月时尚欠的款数,

则一个月后（加上利息后）欠款，不过我们又还了x元所以总的

欠款为

k=0,1,2,3,

而一开始的借款为工。。所以我们的数学模型可表述如下

=(1+K)Ak-xk=011,2,3,

为己知(不妨假设劣为己知)⑴

。(1)的求解。由

Ai=(1+R)AQ-X

4=Q+我)/]-彳=(1+K)[Q+K)

=(1+R)%-x[(1+R)+1]

易知

Ak=(1+K)(1+K)上】+(1+R)"?+…+(1+R)+1]

=(1+K)%。-章Q+K)A-1]

故4=(4-/)(1+立)"+京⑵

这就是工。‘。‘X'R之间的显式关系。

d.针对广告中的情形我们来看⑴和⑵中哪些量是已知的。N=5年=60

个月，已知；每月还款x=1200元，已知Ao即一次性付款购买价减去

70000元后剩下的要另外去借的款，并没有告诉你，此外银行贷款利率R

也没告诉你，这造成了我们决策的困难。然而，由⑵可知60个月后还清,

即，从而得

0=4(l+R)60-耳2[(1+&)6。-1]

£\

_12OO[(1+A)60-1]

4=11+&6。(3)

(3)表示N=60,x=1200给定时和x之间的关系式，如果我们已经知

道银行的贷款利息R,就可以算出。例如，若R=0.01,则由(3)可算

得53946元。如果该房地产公司说一次性付款的房价大于

70000十53946=123946元的话，你就应自己去银行借款。事实上，利

用图形计算器或Mathematica这样的

数学软件可把⑶的图形画出来，从而可以进行估算决策。以下我们进一步

考虑下面两个问题。

注1问题1标题中“抵押贷款”的意思无非是银行伯你借了钱不还，因而

要你用某种不动产(包括房子的产权)作抵押，即万一你还不出钱了，就没

收你的不动产。

例题1某高校一对年青夫妇为买房要用银行贷款6。。0。元，月利率0.01,

贷款期25年=300月，这对夫妇希望知道每月要还多少钱，25年就可还

清。假设这对夫妇每月可有节余900元，是否可以去买房呢

解：现在的问题就是要求使的x,由⑵式知

_(1+1)-

X—(1+A)k-1

现=60000,R=0.01,k=300,算得x=632元，这说明这对夫妇有能

力买房。

例题2恰在此时这对夫妇看到某借贷公司的一则广告：“若借款60000

元,22年还清，只要；⑴每半个月还316元；(ii)由于文书工作多了的关系

要你预付三个月的款，即316X6=1896元,这对夫妇想：提前三年还清

当然是好事，每半个月还316元，那一个月不正好是还632元，只不过多

跑一趟去交款罢了；要预付18%元，当然使人不高兴，但提前三年还清省

下来的钱可是22752元哟，是1896元的十几倍明H这家公司是慈善机构

呢还是仍然要赚我们的钱呢这对夫妇请教你给他们一个满意的回答。

具体解法略。

问题2:养老基金

今后，当年青人参加工作后就要从其每月工资中扣除一部分作为个人的

养老基金，所在单位（若经济效益好的话）每月再投入一定数量的钱，再

存入某种利息较高而又安全的“银行”（也可称为货币市场）到60岁退休时

可以动用。也就是说，若退休金不足以维持一定的生活水平时，就可以动

用自己的养老基金，每月取出一定的款项来补贴不足部分。假设月利率与

=0.01不变，还允许在建立养老基金时自己可以一次性地存入一笔钱

（不论多少），每月存入y元（个人和单位投入的总和）；通常从三十一岁

开始到六十岁就可以动用。这当然是一种简化的假设，但作为估算仍可作

为一种考虑的出发点。本问题实际上有两个阶段，即退休前和退休后，其

数学模型为

[•Ax+i=4*（1+R）+y，n=091»2*3»,,,

‘4己知

=Ax（1+7?）-x>〃=31，...

己知

其中x为每月要从养老基金中提出的款项。

习题1某大学年青教师小李从31岁开始建立自己的养老基金，他把

已有的积蓄1万元也一次性地存入，已知月利率为0.01（以复利计），每

月存入300元，试问当小李60岁退休时，他的退休基金有多少又若,

他退休后每月要从银行提取1000元，试问多少年后他的退休基金将用完

你能否根据你了解的实际情况建立一个较好的养老基金的数学模型与相

应的算法和程取软件）。

习题2渔业（林业）管理问题

设某养鱼池（或某海域）一开始有某种鱼条，鱼的平均年净繁殖率为

R,每年捕捞x条，记第N年有鱼条，则池内鱼数按年的变化规律为

工w+1=(1+R)-X，4己知

注意，在实际渔业经营中并不按条数计算而是以吨记数的。若对某海域的

渔业作业中=100000吨，R=0.02,x=1000吨，试问会不会使得

若干年后就没有鱼可捕捞了(资源枯竭了)？

例2比例分析法——席位分配

问题：某学校有三个系联合成立学生会，

(1)试确定学生会席位分配方案。

(2)若甲系有10。名，乙系60名，丙系4。名。学生会设20个席位，分

配方案如何？

⑶若丙系有3名学生转入甲系，3名学生转入乙系，分配方案有何变化？

(4)因为有20个席位的代表会议在表决提案时有可能出现10：10的

平局，会议决定下一届增加1席，若在第(3)问中将学生会席位增加一席

呢？

(5)试确定一数量指标衡量席位分配的公平性，并以此检查(1)—(4)。

公平学生人数所占比例按比例分配的席按惯例分配的席位

而又(%)位

简单

的席

位分

配办

法是

按人

数的

比例

分配，

若甲

系有

100

名，

乙系

60

名，

丙系

40

名。

学生

会设

20个

席位,

三个

系分

别应

有

10,

6,4

个席

位。

如果

丙系

有6

名学

生转

入其

他两

系学

习，

各系

人数

如表

所示

系别

甲10351.510.310

乙6331.56.36

丙3417.03.44

总和200100.020.020

第二列所示，按比例分配席位时，出现了小数（见表中第四列）.在将取得

整数的19席分配完毕后，剩下的1席按照惯例分给余数最大的丙系，于

是三个系仍分别占有10、6.4个席位.

因为学生人数所占比例（％）按比例分配的席按惯例分配的席位

有位

20

个席

位的

代表

会议

在表

决提

案时

有可

能出

现

10：

10

的平

局，

会议

决定

下一

届增

加1

席，

于是

他们

按照

上述

惯例

重新

分配

席

位，

计算

的结

果令

人吃

惊：

总席

位增

加1

席，

丙系

反而

减少

1席,

见K

表.

系别

甲10351.510.81511

乙6331.56.6157

丙3417.03.5703

总和200100.021.00021

看来，要解决这个矛盾，必须重新研究所谓惯例分配方法，提出更加“公

平”的办法.

下面就介绍这样一个席位分配模型.设A.B两方人数分别是pl和p2,分

别占有nl和n2个席位，

则两方每个Pnp/npl/nl-p2/n2

席位所代表

的人数分别

是pl/

nl2和p2/

n2.很明显，

仅当这两个

数值相等时，

席位的分配

才是公平

的,但是，通

常它们不会

相等，这时

席位分配得

不公平。

不公平的程

度可以用数

值来表示，

它衡量的是

“绝对不公

平”.从下表

所举的例子

来看，A、B

之间的“绝对

不公平”与

C、D之间是

一样的。但是

从常识的角

度看，A、B

之间显然

比c、D之

间存在着更

加严重的不

公平.所以

“绝对不公

平”不是一个

好的衡量标

准.

A120101212-10=2

B1001010

C102010102102-100=2

D100010100

为了改进绝对标准，我们自然想到用相对标准.因为p/n越大，每个席

位代表的人数越多，或者说，总人数一定时分配的席位越少。所以，如

果pl/nl3>p2/n2,则A方是吃亏的，或者说，对A是不公平的，由此,

我们这样定义“相对不公平”：

若pl/nl>p2/n2,则称

p\!n\p\n2'

为对A的相对不公平值，记做

若pl/nlVp2/n2,则称

p\!n\-p2/n2_p\n2.

p2!n2p2n\'

为对B的相对不公平值，记做

假设A.B两方已分别占有nl和n2个席位，我们利用相对不公平的城念

来讨论，当总席位再增加1席时，应该给且A方还是B方

不失一般性，Wpl/nl>p2/n2,即此时对A方不公平，，

有定义.当再分配1个席位时，关于p/n的不等式有以下三种可能：

I）pl/（nl-bl）>p2/n2,这说明即使A方增加1席，仍然对A不公平，

所以这1席当然应给A方；

2）pl/（nl十I）<p2/n2,说明当A方增加1席位，将对B不公平，此

时应参照式，计算对B的相对不公平值

3）说明当B方增加1席时，将对A方不公平，此时计算得对A的相对不

公平值是

勺（力1+1,«2）<.rA（«1,匕2+1）

（注意：在pl/nlp2/n2的假设下，不可能出现pl/nlVp2/（n2+l）

的情况因为公平的席位分配方法应该使得相对不公平的数值尽量地小，所

以如果

+力2）<<4（«1,〃2+1）

则这1席应给A方；反之应给B方.根据（3）、（4）两式，（5）式等价于并

且不难证明1从上述第1）种情况的pl/（nl十I）>p2/p2也可推出。

于是我们的结论是：当⑹式成立时，增加的1席应分配A方；反之，应分

配给B方.

若记，则增加的1席位应分配给Q值较大的一方.

将上述方法可以推广到有m方分配席位的情况.

下面用这个方法，重新讨论本节开始时提出的，三个系分配21个席位的

问题.

首先每系分配1席，然后计算：

甲系nl=l,

一3)2_10支

5一«1(〃1+1)-1x2

乙系，n2=l,

一3)2_632

6一«2(〃2+1)-1x2

丙系，n3=l,

一53)-_3-

©一«303+1)-1x2

因为最大，所以第4席应分配给甲系，继续计算:

甲系nl=2,

»1)21032

5=阀1Q1+1)=讨=1768.2

将与上面的甲系乙系丙系

相比，最大，

第5席应分给乙

系，继续计算。如

此继续，直到第

21席分配给某

个系为止(详见

列表).

n

15304.5(4)1984.5(5)578(9)

21768.2(6)661.5(8)192.7(15)

3884.1(7)330.8(12)96.3(21)

4530.5(10)198.5(14)

5353.6(11)132.3(18)

6252.6(13)94.5

7189.4(16)

8147.3(17)

9117.9(19)

1096.4(20)

1180.4

合计11席6席4席

可以看出，用Q值法，丙系保住了它险些丧失的1席。你觉得这个方法公

平吗？

习题：

学校共1000名学生，235入住在A宿合，333人住在B宿合，432人住

在C宿合.学生们要组织一个1。人的委员会，试用下列办法分配各宿舍

的委员数.

1)惯例的方法，印按比例分配完整数名额后，剩下名额给余数最大者。

2)Q值方法。

如果委员会从1。人增至15人，分配名额将发生什么变化，

例3状态转移问题——常染色体遗传模型

随着人类的进化，人们为了揭示生命的奥秘：越来越注重遗传学的研究,

特别是遗传特征的逐代传播，引起人们的注意。无论是人，还是动植物都

会将本身的特征遗传给下一代，这主要是因为后代继承了双亲的基因，形

成自己的基因对，基因对将确定后代所表现的特征。下面，我们来研究两

种类型的遗传：常染色体遗传和X一链遗传。根据亲体基因遗传给后代的

方式，建立模型，利用这些模型可以逐代研究一个总体基因型的分布。

在常染

色体遗

传中，

后代从

每个亲

体的基

因对中

各继承

一个基

因，形

成自己

的基因

对，基

因对也

称基因

型。如

果我们

所考虑

的遗传

特征是

有两个

基因A

和控制

的，则

就有三

AA-AAAA-AaAA-aaAa-AaAa-aaaa-aa

后AA11/201/400

代

基Aa01/211/21/20

因

型aa0001/41/21

农场的植物园中某种植物的基因型为AA,A和。农场计划采用AA型的植

物与每种基因型植物相结合的方案培育植物后代。则经过若干年后，这种

植物的任一代的三种基因型分布如何？

第一步：假设：令c

设和分别表示第代植物中，基因型为AA,Aa和aa的植物占植物总

数的百分率。令为第n代植物的基因型分布：

&一

b„

当n=0时

国「

”=%

5o_

表示植物基因型的初始分布(即培育开始时的分布)，显然有

旬+%+。0=1

(1)第n代的分布与第n-1代的分布之间的关系是通过上表确定的。

第二步：建模

根据假设(2),先考虑第n代中的AA型。由于第n-1代的AA型与AA

型结合，后代全部是AA型；第n-l代的Aa型与AA型结合，后代是AA

型的可能性为1/2,第n-l代的aa型与AA型结合，后代不可能是AA型。

因此，当时

%="z+%/2+0・%

即=%+配/2

类似可推出

%=%+%/2

g=0

将式相加，得

an+bn+cn=an_l+bn_l+cn_l

根据假设(1),有

对于式、式和式，我们采用矩阵形式简记为

=1,2,…

其中

-

11/201[an~

M=01/21/)=bn

00()J|_c„

式递推，得

x(,,)==M2aLD=…="

式给出第代基因型的分布与初始分布的关系。

为了计算出,我们将M对角化，即求出可逆矩阵P和对角阵D,使

M=PDPX

因而有

Mn=PO"K,〃=1,2,…

其中

n

4oo-A!；00

D"=0220=0冬0

oo400^

这里是矩阵M的三个特征值。对于式中的M,易求得它的特征值和特征

向量:

4=1,4=1/2,4

011

D=0-13一-2

因此0001

。=口-2

所以1

通过计算,因此有

=M"x^=PD"P-xx^

111001

0-1-20(夕00

0010000

1—(1/2)”1-(1/2尸%

x(】/2)"(1/2)”Tb0

00

即。。

。0+〃0+/-(1/2)〃%一(1/2)”-20

(1/2)»O+(1/2)”TC。

0

所以有

%=1-(1/2)"d-(1/2尸Co

、2=(1/2)〃4+(1/2)”-70

c〃二°

当时，所以从式得到

anfLb”-0和c“=0

即在极限的情况下，培育的植物都是AA型。

第三步：模型讨论

若在上父体一母体基因型

述问题

中，不

选用基

因AA

型的植

物与每

一植物

结合，

而是将

具有相

同基因

型植物

相结

合，贝1」

后代具

有三代

基因型

的概率

如下

表：

AA-AAAa-Aaaa-aa

后AA11/40

代Aa01/20

基aa01/41

因

型

并且，其中

M的特征值为4==1,4=1/2

通过计算，可以解出与相对应的两个线性无关的特征向量和，与与

相对应的特征向量

101

4]=。0-2

-111

因此

-11/20-

尸7=111

0-1/20

x(n)=PD,!P-lx(0)

'1o1Ti0011/2oj。。

=00-20I"0111b°

-1i1j|_0

0(l/2)nJ|_0-1/20c°

所以有

%+(1/2)%+(1/2)"+也

2二(1/2)"%

C=c0+(l/2)%一(1/2)向瓦

当时，所以从式得到

%f%+(1/2)%也t0和cnfc()+(1/2)%

因此，如果用基因型相同的植物培育后代，在极限情况下，后代仅具有基

因AA和aao

例4合作对策模型

在经济或社会活动中，几个社会实体（个人、公司、党派、国家）相互合

作或结成联盟，常能获得比他们单独行动更多的经济或社会效益。这样合

理地分配这些效益是合作对策要研究的问题。请看下面的例子。

问题一：经商问题

甲、乙、丙三人经商，若单干，每人仅能获利1元；甲乙合作可获利7元;

甲丙合作可获利5元；乙丙合作可获利4元；三人合作可获利10元，问

三人合作时如何分配1。元的收入。

甲的收入应按照甲对各种形式的合作的贡献来确定.对于某一合作的贡献

定义为：有甲参加时这个合作的收入与无甲参加时这个合作的收入之差.

例如甲对甲乙二人合作的贡献是7-1=6（因为甲乙合作获利7元，而

乙单干仅获利1元）.甲可以参加的，合作有四个：甲自己（单干视为合作的

特例）、甲乙、甲丙、甲乙丙.甲对这些合作的贡献分别是甲：1一0=

1元；甲乙：7—1=6元；甲内：5—1=4元；甲乙丙：10—4=6元,

甲应分得的收入是这四个贡献的加权平均值，加权因子将由下面的一般模

型给出.

这个问题叫做3人合作对策，是对策论的一部分，这里介绍它的一种解

法。

一般的n人合作对策模型可以叙述如下：

记n人集合为1=，如果对于I中的任一子集，都对应一个实值函数v

（s）,满足

v10J=0

V（S1CG2y（S1）+v（$2）

（S1CS?=◎）

则称为定义在I上的特征函数.所谓合作对策是指定义了特征函数的I中n

个人的合作结果，用向量值函数

来表示.在实际问题中.常可把I中各种组合的

合作获得的利益定义为特征函数，上式表示合作规模扩大时，获利不会减

少。不难看出，如将三人经商问题中合作的获利定义为特征函数V,v是满

足⑴、⑵的.

为了确定,Shapley在1953年首先制定了一组应该

满足的公理，然后证明了满足这组公理的的唯一解是

S（Q=£/（|s|）［y（s）-y（s-{i}）］»j=1»2,3,…，n

5电

其中是I中包含出的所有子集，是集合s中的人数，是

加权因子，由

确定.（3）式中可看作

成员6}对合作s的贡献；表示对所有包含{i}的集合求和.称为由v定义的

合作的Shapley值.

我们用（3）、（4）计算三人经商问题中各个人应得到的收入.

甲、乙、丙分别记作

{1},{2},{3},包含{1}{1,2}{1,3}{1,2,3}

{1}的集合有“}、{1,

2｝、｛1,3｝、｛1,2,3｝,

计算结果列入下表.

S

V(s)17510

V(s-{1})0114

V(s)-V(s-{1})1646

Id1223

W(|s|)1/31/61/61/3

W(⑸)[V(s)-

1/312/32

V(s-{1})]

6（y）=1/3+1+2/3+2=4元

同样可以算出乙、丙应得收入为=3.5元，=2.5元。

问题二：三城镇的污水处理方案

沿河有三城镇L2和3,地理位置如图4;6所示.污水需处理后才能排入

河中.三城镇或者单独建立污水处理厂，或者联合建厂，用管道将污水集

中处理（污水应于河流的上游城镇向下游城镇输送）。以Q表示污水量触/

秒），工表示管道长度（公里）。

按照经验公式，建立处理厂的费用为，铺设管道的费用为.今已知

三城镇的污水量分别为.L的数值.试从节约总投资的角度为三城镇

制定污水处理方案；包括是单独还是联合建厂；如果联合，如何分担投资

额等.

三城镇或单干或不同形式的联合，共有五种方案。下面一一计算所需的投

资.

方案一三城镇都单干。投资分别为

C(l)=730X50-712=2300

C(2)=730X30-712=1600

C(3)=2300

总投资：

Si=C(l)+C(2)+C(3)=6200

方案二城1.2合作。这时城1.2将从节约投资的角度对联合还是分别

建厂作出决策，所以城1.2的投资为：

广.俾合：()°-712+6.6X5051X20

C(1,2)=尚叫单干：7©3(015)+43-0(2)=3900=35001)

=3500

C(3)=2300

总投资：

$2=c(1,2)+C(3)=5800

方案三城2.3合作。

0n2051

'广⑵心3Q)=_掰叫/073(02()3+50)(3)+=6.63x9300x38=3650、/=_3泰65”0

C(1)=2300

总投资：

$3=c(2,3)+C(1)=5950

方案四城1.3合作。

onasl

C(1’3Q)"叫-(c73(01()5++5C)(3)+6=.64x56°00-x58=46301)=4皿60日0

C(2)=1600

总投资：

$4=C(1,3)+C⑵=6200

方案五三城镇合作

730(5+3+5)°712+6.6x5onx204-6.6x8o-51x38=5560

C

C(1,2)+CC3)=5300

C(1»2,3)=minC(2,3)+CCl)=5900

CCl,3)+C(2)=6200

Cl)+C(2)+C(3)=6200

=5560

总投资：

S5=C(1,2,3)=5560

比较五个方案可知，应该选择三城合作，联合建厂的方案.

下面的问题是如何分担总额为5560的费用.

城3的负责人提出，联合建厂的费用按三城的污水量之比5:3:5分担，铺

设管道费应由城1.2担负.城2的负责人同意，并提出从城2到城3的管

道费由城1.2按污水量之比5:3分担;从城1到城2的管道费理应由城1

自己担负.城1的负责人觉得他们的提议似乎是合理的，但因事关重大,

他没有马上表示同意；而是先算了一笔账.联合建厂的费用是，城2到

城3的管道费是730,城1到城2的管道费是300,按上述办法分配时,

城3负担的费用为1740,城2的费用为1320,域1的费用为2500.结

果出乎意料之外，城3和城2的费用都比单独建厂时少，而城1的费用却

比单独建厂时的C(l)还要多.城1的负责人当然不能同意这个方法，但是

一时他又找不出公平合理的解决办法.为了促成联合的实现，你能为他们

提供一个满意的分担费用的方案吗

首先，应当指出，城3和城2负责人提出的办法是不合理的：从前面的计

算我们知道，三城联合，才能使总投资节约了640的效益应该分配给三城,

使三城分配的费用都比他们单干时要少，这是为促成联合所必须制定的一

条原则.至于如何分配，则是下面要进一步研究的问题.

把分担费用转化为分配效益，就不会出现城1联合建厂分担的费用反比单

独建厂费用高的情况.将三城镇记为1={1,2,3},联合建厂比单独建厂节约的

投资定义为特征函数.于是有

v(。)=0,v({l})=v({2})=v({3})=0,v({l,2))=c(l)+c(2)-c(l,2)=2300+1600-3

500=400,v({2,3})=c(2)+c(3)-c(2,3)=1600+2300-3650=250,v({l,3})=0

,v(I)=c(l)+c(2)+c(3)-c(1,2,3)=640.

S{1}{1,2}{1,3}{1,2,3}

V(s)04000640

V(s-{1})000250

V(s)-V(s-{1})04000390

s1223

W(|s|)1/31/61/61/3

W(Is)[V(s)-

0670130

V(s-{1})]

即3)=197

同理得心⑺=321%。)=122

则，城1分担的费用为2300-197=2103,城2分担的费用为

1600-321=1279,城3分担的费用为2300-122=2178,合计5560.

习题:

某甲(农民)有一块土地。如果从事农业生产可年收入1。。元；如果将土

地租给某企业家用于工业生产，可年收入200元；如果租给某旅店老板开

发旅游业，可年收入30。元；当旅店老板请企业家参与经营时，年收入可

达40。元。为实现最高收入，试问如何分配各人的所得才能达成协议？

例5动态规划模型

有不少动态过程可抽象成状态转移问题，特别是多阶段决策过程的最优化

如最短路径问题，最优分配，设备更新问题，排序、生产计划和存储等问

题.

动态规划是一种将复杂问题转化为一种比较简单问题的最优化方法，它的

基本特征是包含多个阶段的决策.1951年，美国数学家贝尔曼(R.

Bellman)等人，提出了解决多阶段决策问题的“最优化原理”，并研究了

许多实际问题，从而创建了动态规划-

动态规划方法的基本思想是：将一个复杂问题分解成若干个阶段，每一个

阶段作为一个小问题进行处理，从而决定整个过程的决策，阶段往往可以

用时间划分这就具有“动态”的含义，然而，一些与时间无关的静态规划

中的最优化问题，也可人为地把问题分成若干阶段，作为一个多阶段决策

问题来处理，计算过程单一化，便于应用计算机.求解过程分为两大步骤,

①先按整体最优化思想递序地求出各个可能状态的最优化决策；②再顺序

地求出整个题的最优策略和最优路线.

下面，结合一个求最短路径的例子，来说明动态规划的一些基本概念.

最短路径问题

如图所示的交通网络，节点连接线路上的数字表示两地距离，计算从A到

E的最短路径与长度。

1.阶段.

把所要处理的问题，合理地划分成若干个相互联系的阶段，通常用k表示

阶段变量。如例中，可将问题分为4个阶段，k=l,2,3,4.

2.状态和状态变量.

每一个阶段的起点，称为该阶段的状态，描述过程状态的变量，称为状态

变量，它可以用一个数、一组数或一个向量来描述，常用来表示第k阶

段的某一状态.如果状态为非数量表示，则可以给各个阶段的可能状态编

号，（表示第k个阶段的第i状态）。第k阶段状态的集合为

如例6中，第3阶段集合可记为

X3={嫂,心,靖}={qc,G}={123}

3.决策和决策变量.

决策就是在某一阶段给定初始状态的情况下，从该状态演变到下一阶段某

状态的选择。即确定系统过程发展的方案.用一个变量来描述决策，称这

个变量为决策变量。设表示第k个阶段初始状态为的决策变量.表

示初始状态为的允许决策集合，有

%（乙）t2（5）=｛散｝

如例6中,若先取,则。

4.策略和子策略.

由每段的决策组成的整个过程的决策变量序列称为策略，记为，即

P\,n={%（阳）,%（%2），…，Un（招））

从阶段k到阶段n依次进行的阶段决策构成的决策序列称为k子策略，记

为即

匕，，（*）={%（占），k（克川），…，〃”（X”）}

显然，k=l时的k子策略就是策略。

如例6,选取路径就是一个子策略.从允许策略集中选出的具有最佳效

果的策略称为最优策略。

5.状态转移方程.

系统在阶段k处于状态，执行决策的结果是系统状态的转移，即由阶

段K的状态转移到阶段K十1的状态适用于动态规划方法求解的是

一类具有无后效性的多阶段决策过程.无后效性又称马尔科夫性，指系统

从某个阶段往后的发展，完全由本阶段所处的状态以与其往后的决策决定,

与系统以前的状态与决策无关，对于具有无后效性的多阶段过程，系统由

阶段k向阶段k+1的状态转移方程为

%=£“，/（与））

意即只与，有关，而与前面状态无关.

称为变换函数或算子.分编定型和的机型.由此形成确定型动态规划和随机型动态规划.

6.指标函数和最优指标函数.

在多阶段决策中，可用一个数量指标来衡量每一个阶段决策的效果，这个

数量指标就是指标函数，为该阶段状态变量与其以后各阶段的决策变量的

函数，设为即

指标的含义在不同的问题中各不相同，可以是距离、成本、产品产量、资

源消耗等.

例6中，指标的含义就是距离，指标函数为A到E的距离，为各阶段路程

的和.

最常见的指标函数取各阶段效果之和的形式，即

%二£匕。%勺)

j=k

指标函数的最优值，称为相应的最优指标函数，记为

fk(xk)=optVkn

式中opt是最优化之意，根据问题要求取max或min.

7.动态规划最优化原理.

贝尔曼指出“作为整个过程的最优策略具有这样的性质：即无论过去的状

态和决策如何，对前面的决策所形成的状态而言，余下的诸