数学建模例题及解析

1、例1分分方程一一资金的时间价值问题1:抵押贷款买房一一从一则广告谈起每家人家都希望有一套（甚至一栋）属于自己的住房，但又没有足够的资金一次买 下，这就产生了贷款买房的问题。先看一下下面的广告（这是1991年1月1日某 大城市晚报上登的一则广告），任何人看了这则广告都会产生许多疑问，且不谈 广告中没有谈住房面积、设施等等，人们关心的是：如果一次付款买这栋房要多 少钱呢银行贷款的利息是多少呢为什么每个月要付1200元呢是怎样算出来的因为人们都知道，若知道了房价（一次付款买房的价格），如果自己只能支付一部分 款，那就要把其余的款项通过借贷方式来解决，只要知道利息，就应该可以算出五年还清每月要付多少钱

2、才能按时还清贷款了， 从而也就可以对是否要去买该广 告中所说的房子作出决策了。现在我们来进行数学建模。由于本问题比较简单无 需太多的抽象和简化。a.明确变量、参数，显然下面的量是要考虑的：需要借多少钱，用记；月利率（贷款通常按复利计）用R记；每月还多少钱用x记；借期记为N个月。b.建立变量之间的明确的数学关系。若用 *记第k个月时尚欠的 款数，则一 个月后（加上利息后）欠款 且=, 不过我们又还了 x元 所以总的欠款为&+】三人工 k=0,1, 2, 3,而一开始的借款为所以我们的数学模型可表述如下上jt+i ） 4r五出:0, 11 2 t 3 ,为已知（不妨假设人为已知）c. （1

3、）的求解。由 丛二 G十丘)工厂工二(1十式)Ci+长)4口。=Q+Q-可。十衣)F1易知4 二(1+R)，-工(1+K)(1+A)4+ (1+R)+1=(1 +R)4 - 4 C f A故 Ai = (j40 - -i) (1 + 又)*+鼻(2(2(2)这就是达"为&之间的显式关系。d.针对广告中的情形我们来看(1)和(2)中哪些量是已知的。N=5年=60个月， 已知；每月还款x= 1200元，已知A。即一次性付款购买价减去 70000元后剩下 的要另外去借的款，并没有告诉你，此外银行贷款利率R也没告诉你，这造成了 我们决策的困又to然而，由(2)可知60个月后还清，即四

4、时三。，从 而得 0 = &(1+R严- 专入 HR)叫 1 # _ 1200(l+/°- 1小二一赤科一 表示N= 60, x= 1200给定时A0和x之间的关系式，如果 我们已经知道银行 的贷款利息R,就可以算出A0。例如，若R =0. 01 ,则由(3)可算得 为三53946元。如果该房地产公司说一 次性付款的房价大于70000十53946= 123946元的话，你就应自 己去银行借款。事实上，利用图形计算器或 Mathematica 这样的数学软件可把(3)的图形画出来，从而可以进行估算决策。以下我们进一步考虑 下面两个问题。注1问题1标题中“抵押贷款”的意思无非是银

5、行伯你借了钱不还，因而要你用某种不动产(包括房子的产权)作抵押，即万一你还不出钱了，就没收你的不动产。 例题1某高校一对年青夫妇为买房要用银行贷款 60000元，月利率0. 01,贷款 期25年=300月,这对夫妇希望知道每月要还多少钱，25年就可还清。假设这 对夫妇每月可有节余900元，是否可以去买房呢解：现在的问题就是要求使 月网。二口的x,由（2）式知_/0一*x （1+一）*-）现为= 60000, R= 0. 01, k = 300,算得x=632元，这说明这对夫妇有能力买房。 例题2恰在此时这对夫妇看到某借贷公司的一则广告：“若借款60000元，22年还清，只要；（i）每半个月还3

6、16元；（ii）由于文书工作多了的关系要你预付 三个月的款，即316X 6= 1896元。这对夫妇想：提前三年还清当然是好事，每 半个月还316元，那一个月不正好是还632元，只不过多跑一趟去交款罢了； 要 预付18%元，当然使人不高兴，但提前三年还清省下来的钱可是22752元哟，是1896元的十几倍哪！这家公司是慈善机构呢还是仍然要赚我们的钱呢这对夫 妇请教你给他们一个满意的回答。具体解法略。问题2:养老基金今后，当年青人参加工作后就要从其每月工资中扣除一部分作为个人的养老基金，所在单位（若经济效益好的话）每月再投入一定数量的钱，再存入某种利息 较高而又安全的“银行”（也可称为货币市场）到6

7、0岁退休时可以动用。也就是 说，若退休金不足以维持一定的生活水平时， 就可以动用自己的养老基金，每月 取出一定的款项来补贴不足部分。假设月利率及= 0. 01不变，还允许在建立养 老基金时自己可以一次性地存入一笔钱 人（不论多少），每月存入y元（个人和单 位投入的总和）；通常从三十一岁开始到六十岁就可以动用。这当然是一种简化的假设，但作为估算仍可作为一种考虑的出发点。本问题实际上有两个阶段， 即退休前和退休后，其数学模型为UI+l = 44A h = U? 1, 2 f 3 1回已知= 4 ：1+一） - xj ra = 3 11 1.h川已知其中x为每月要从养老基金中提出的款项。习题1某大学

8、年青教师小李从31岁开始建立自己的养老基金，他把已有的积蓄1万元也一次性地存入，已知月利率为 0. 01 （以复利计），每月存入300 元，试问当小李60岁退休时，他的退休基金有多少又若，他退休后每月要从银行提取1000元，试问多少年后他的退休基金将用完你能否根据你了解的实际 情况建立一个较好的养老基金的数学模型及相应的算法和程取软件）。习题2渔业（林业）管理问题设某养鱼池（或某海域）一开始有某种鱼条，鱼的平均年 净繁殖率为R,每 年捕捞x条，记第N年有鱼.加条，则池内鱼数按年的变化规律为工胡4三乂州11+尺J * Z ）工巾已知注意，在实际渔业经营中并不按条数计算而是以吨记数的。若对某海域的

9、渔业作业中4=100000吨，R= 0. 02, x=1000吨，试问="会不会使得若干年后 就没有鱼可捕捞了（资源枯竭了） 例2比例分析法一一席位分配问题：某学校有三个系联合成立学生会，（1）试确定学生会席位分配方案。（2）若甲系有100名，乙系60名，丙系40名。学生会设20个席位，分配方案 如何（3）若丙系有3名学生转入甲系，3名学生转入乙系，分配方案有何变化（4）因为有20个席位的代表会议在表决提案时有可能出现 10: 10的平局， 会议决定下一届增加1席，若在第（3）问中将学生会席位增加一席呢（5）试确定一数量指标衡量席位分配的公平性，并以此检查（1） （4）。公平而又简单

10、的席位分配办法是按人数的比例分配，若甲系有100名，乙系60名，丙系40名。学生会设20个席位，三个系分别应有10, 6, 4个席位。如果丙系有6名学生转入其他两系学习，各系人数如表所示系别学生人数所占比例（%按比例分配的席位按惯例分配的席位甲10310乙636丙344总和20020第二列所示，按比例分配席位时，出现了小数（见表中第四列）.在将取得整数的 19席分配完毕后，剩下的1席按照惯例分给余数最大的丙系，于是三个系仍分 别占有10、6、4个席位.因为有20个席位的代表会议在表决提案时有可能出现 10: 10的平局，会议决定 下一届增加1席，于是他们按照上述惯例重新分配席位，计算的结果令人

11、吃惊： 总席位增加1席，丙系反而减少1席，见下表.系别学生人数所占比例（%按比例分配的席位按惯例分配的席位甲10311乙637丙：343总和20021看来，要解决这个矛盾，必须重新研究所谓惯例分配方法，提出更加“公平”的 办法.下面就介绍这样一个席位分配模型.设 A、B两方人数分别是pl和p2,分别占 有n1和n2个席位，则两方每个席位所代表的人数分别是 pl /n12和p2/n2.很明显，仅当这两个 数值相等时，席位的分配才是公平的.但是，通常它们不会相等，这时席位分配 得不公平。不公平的程度可以用数值加加2|来表示，它衡量的是“绝对不公平”.从下表所举的例子来看，A B之间的“绝对不公平”

12、与 G D之间是一样的。但是 从常识的角度看，A B之间显然 比G D之间存在着更加严重的不公平.所以“绝对不公平”不是一个好的衡量标准.pnp/np1/n1-p2/n2A120101212-10=2B1001010C102010102102-100=2D100010100为了改进绝对标准，我们自然想到用相对标准.因为p/n越大，每个席位代表的人数越多，或者说，总人数一定时分配的席位越少。所以，如果p1/n13>p2/n2,则A方是吃亏的，或者说，对 A是不公平的，由此，我们这样定义“相 对不公平”：若 p1/n1>p2/n2,则称尸2的2学1仅1 p2n , /加1#1理2为对A

13、的相对不公平值，记做皿吟“若 p1/n1<p2/n2,则称产1加1子2加2 _ pl烈2p2 M2中2部】为对B的相对不公平值，记做陛（川，吟。假设A、B两方已分别占有n1和n2个席位，我们利用相对不公平的城念来讨论，当总席位再增加1席时，应该给且A方还是B方不失一般性，可设p1/n1>p2/n2,即此时对A方不公平，有定义.当再分配1个席位时，关于p/n的不等式有以下三种可能：1）p1/（n1十1） >p2/n2,这说明即使A方增加1席，仍然对A不公平，所以这 1席当然应给A2）p1/（n1十1）<p2/n2,说明当A方增加1席位，将对B不公平，此时应参照 式，计算对

14、B的相对不公平值3）说明当B方增加1席时，将对A方不公平，此时计算得对 A的相对不公平值 是心（管 1 + 1,前2）（打 1, «2 + 1）（注意：在p1/n1；'p2/n2的假设下，不可能出现 p1/n1 <p2/（n2+1）的情况因为公平的席位分配方法应该使得相对不公平的数值尽量地小，所以如果广总(«1 +1 j盟2)(哲1.司2 + 1)则这1席应给A方；反之应给B方.根据（3）、（4）两式，（5）式等价于并且不难 证明1从上述第1）种情况的p1/（n1十1） >p2/p2也可推出。 于是我们的结 论是：当（6）式成立时，增加的1席应分配A方；

15、反之，应分配给B方.若记!'（存计1,则增加的1席位应分配给Q值较大的一方.将上述方法可以推广到有m方分配席位的情况.下面用这个方法，重新讨论本节开始时提出的，三个系分配21个席位的问题.首先每系分配1席，然后计算：甲系n1 = 1,_3” _ 1。里Q =乙系，n2=1 ,=02） 3_ 53二防二位而+1）一 =丙系，n3=1,_03） 3_ 3 甲Q=支（蔻+1）一=而因为Q1最大，所以第4席应分配给甲系，继续计算：甲系n1 = 2,O1） 3103工Q = MTEHT = R= 176g 2将以与上面的。如1a相比，5最大，第5席应分给乙系，继续计算。如此继续, 直到第21席分

16、配给某个系为止（详见列表）.n甲系乙系丙系1(4)(5)578 (9)2(6)(8)(15)3(12)(21)4(10)(14)5(11)(18)6(13)7(16)8(17)9(19)10(20)11合计11席6席4席可以看出，用Q值法，丙系保住了它险些丧失的1席。你觉得这个方法公平吗 习题：学校共1000名学生，235入住在A宿合，333人住在B宿合，432人住在C宿合.学 生们要组织一个10人的委员会，试用下列办法分配各宿舍的委员数.1)惯例的方法，印按比例分配完整数名额后，剩下名额给余数最大者。2) Q值方法。如果委员会从10人增至15人，分配名额将发生什么变化，例3状态转移问题一一常

17、染色体遗传模型随着人类的进化，人们为了揭示生命的奥秘，越来越注重遗传学的研究，特别是 遗传特征的逐代传播，引起人们的注意。无论是人，还是动植物都会将本身的特 征遗传给下一代，这主要是因为后代继承了双亲的基因， 形成自己的基因对，基 因对将确定后代所表现的特征。下面，我们来研究两种类型的遗传：常染色体遗 传和x一链遗传。根据亲体基因遗传给后代的方式，建立模型，利用这些模型可 以逐代研究一个总体基因型的分布。在常染色体遗传中，后代从每个亲体的基因对中各继承一个基因，形成自己的基因对，基因对也称基因型。如果我们所考虑的遗传特征是有两个基因 A和控制的， 那么就有三种基因对，记为 AA A,。例如，金

18、草鱼由两个遗传基因决定花的颜 色，基因型是AA的金鱼草开红花，型的开粉红色花，而型的开白花。又如人类 的眼睛的颜色也是提高通过常染色体遗传控制的。基因型是的人，眼睛是棕色， 基因型是的人，眼睛是兰色。这里因为都表示了同一外部特征，我们认为基因 A 支配基因，也可以认为基因对于 A来说是隐性的父体一母体的基因型AA-AAAA-AaAA-aaAa-AaAa-aaaa-aa后 代 基 因 型AA11/201/400Aa01/211/21/20aa0001/41/21农场的植物园中某种植物的基因型为 AA A和。农场计划采用AA型的植物与每种基因型植物相结合的方案培育植物后代。那么经过若干年后，这种植

19、物的任 代的三种基因型分布如何第一步：假设：令n=0,1,2,A 0(1)设an，bn和cn分别表示第n代植物中，基因型为AA,Aa和aa的植物占植物总数的百分率。令x为第n代植物的基因型分布：anlx(n) = bncn J当n=0时ax=bo：c0 一表示植物基因型的初始分布（即培育开始时的分布），显然有ao - bo Co =1（2）第n代的分布与第n-1代的分布之间的关系是通过上表确定的。第二步：建模根据假设（2）,先考虑第n代中的AA型。由于第n-1代的AA型与AA型结合，后代全部是AA型；第n-1代的Aa型与AA型结合，后代是AA型的可能性为1/2 ,第n-1代的aa型与AA型结合

20、，后代不可能是 AA型。因此，当n = 0,1,2,A时an =1?am bnd/2 - 0?Cn即 an =an3 bnj/2类似可推出an =cn1 bn J / 2Cn =0将式相加，得a n bn Cn = Hn bn 1 Cn 1根据假设（1）,有an bn ' Cn = a。 bo Co =1对于式、式和式，我们采用矩阵形式简记为x（n） =Mx（n,）,n =1,2,上其中一1 1/2 o-an!M = o 1/2 1x（n）= bn9 o oj-Cn式递推，得x（n） =Mx（n） =M2x（" =A =Mnx（o）式给出第代基因型的分布与初始分布的关系。为了

21、计算出Mn,我们将M对角化，即求出可逆矩阵P和对角阵D,使M =PDP'因而有nn 1M PD P , n =1,2,上其中%00n ，.；00Dn = 0 均 0= 0 九2000%00儿3M,易求得它的特征值和特征这里人1,九2, %是矩阵M的三个特征值。对于式中的 向量：11 =1, I2 -1/2, 3 = 010：。一100D = 0 1/2 0£1因止匕 P 0叱P = I' 1, 2所以1 11%= 0120 01 _通过计算P=P，因此有X7(X nM-(O(XPnD p-0130/V1 o21 一 11 11 一 o 1 o o-1 o o- J o

22、 o o11o(n)1-(1/2)n Vad(1/2广仇0I CoZn一1 1-(1/2)n bn = 0(1/2)n:Cn _ p 0a0 +仇+C0 -(1/2)nb -(1/2)n%0(1/2)nb0 +(1/2)n%所以有an =1 -(1/2)nb0 -(1/2)n%0 4 bn =(1/2)nb0 +(1/2)n%0Cn =0当nT馅时(1/2)nT 0所以从式得到an T 1,bn T 0 和 Cn=0即在极限的情况下，培育的植物都是 AA型。第三步：模型讨论若在上述问题中，不选用基因 AA型的植物与每一植物结合，而是将具有相同基 因型植物相结合，那么后代具有三代基因型的概率如下

23、表：父体一母体基因型AA-AAAa-Aaaa-aa后 代 基 因 型AA11/40Aa1/20aa01/4111/4 0M = 0 1/2 0并且x=M nx，其中 P 1/4 1 一 M的特征值为1 =1, '2 =1,'3 =1/2一。10九3一1 1-2J 一通过计算，可以解出与，%相对应的两个线性无关的特征向量 入1和红，及与九3一1 1%=0相对应的特征向量%:1-101P = G % % 】=0 0 -2因止匕1 11 111/201P = 1110 -1/2 0_(n) Xx(0)二 PDnP1 (0)x0 一101(1/2)n_01/20 a。11 Ib0-1/

24、2 0_coj101100 0 -2 0 1n -1 11_0 0所以有an =a0 +(1/2)bo +(1/2)n”0bn =(1/2)nbon -1Cn =Co (1/2)bo -(1/2) b0当nTg时。/2）nT 0,所以从式得到anT a0 +（1/ 2）b0, bn t。和 Cn t C0 + （1/2也因此，如果用基因型相同的植物培育后代，在极限情况下，后代仅具有基因AA和aa。例4合作对策模型在经济或社会活动中，几个社会实体（个人、公司、党派、国家）相互合作或结 成联盟，常能获得比他们单独行动更多的经济或社会效益。这样合理地分配这些效益是合作对策要研究的问题。请看下面的例子

25、。问题一：经商问题甲、乙、丙三人经商，若单干，每人仅能获利 1元；甲乙合作可获利7元；甲丙 合作可获利5元；乙丙合作可获利4元；三人合作可获利10元，问三人合作时 如何分配10元的收入。甲的收入应按照甲对各种形式的合作的贡献来确定.对于某一合作的贡献定义为：有甲参加时这个合作的收入与无甲参加时这个合作的收入之差.例如甲对甲乙二人合作的贡献是 71=6 （因为甲乙合作获利 7元，而乙单干仅获利 1 元）.甲可以参加的，合作有四个：甲自己（单干视为合作的特例）、甲乙、甲丙、 甲乙丙.甲对这些合作的贡献分别是甲：1 0=1元；甲乙：71 = 6元；甲内：51 = 4元；甲乙丙：104 = 6元，甲应

26、分得的收入是这四个贡献的加权平 均值，加权因子将由下面的一般模型给出.这个问题叫做3人合作对策，是对策论的一部分，这里介绍它的一种解法。一般的n人合作对策模型可以叙述如下：记n人集合为1=1；，丸-造），如果对于I中的任一子集&#1,都对应一个实值函数v （s）,满足v 10）= 0v Csio 匆）v （门.）-Hv （/）（4G s =小）则称为定义在I上的特征函数.所谓合作对策是指定义了特征函数的I中n个人 的合作结果，用向量值函数。=例'Q，s快） 来表示.在实际问题中.常可把I中各种组合的合作获得的利益定义为特征函数，上式表示合作规模扩大时，获利不会减少。不 难看出，

27、如将三人经商问题中合作的获利定义为特征函数 v, v是满足（1）、（2） 的.为了确定，,Shapley在1953年首先制定了一组6刃应该满足的公理，然后证明了满足这组公理的 *'I的唯一解是他（Q 二, 5 = 1, 2, 3,.1,司其中凡是I中包含i的所有子集，Ml是集合s中的人数，是加权因子，由(|占|)=ql- 1> ! 5 |川1 Iy 9 ' is- a” 可看作成员i对合作s的贡献；表示对所有包含i的集合求和.63,称为由v定义的合作的Shapley值.我们用（3）、（4）计算三人经商问题中各个人应得到的收入.甲、乙、丙分别记作1 , 2 , 3,包含1的

28、集合有1、1 , 2、1 , 3、1 , 2, 3,计算结果列入下表.S11,21,31,2,3V17510V(s-1)0114V(s)- V(s-1)1646国1223W(e 1)1/31/61/61/3w( m )v(s)-V(s-1)1/312/32旧 3 = 1/3+1+2/3+2 = 4元 .同样可以算出乙、丙应得收入为 6 卜）=3. 5元， '»）=元。问题二：三城镇的污水处理方案沿河有三城镇1、2和3,地理位置如图4; 6所示.污水需处理后才能排入河中.三 城镇或者单独建立污水处理厂，或者联合建厂，用管道将污水集中处理 （污水应 于河流的上游城镇向下游城镇输送

29、）。以Q表示污水量（吨/秒），工表示管道长 度（公里）。0.712按照经验公式，建立处理厂的费用为P = 73Q,铺设管道的费用为P = 0.66Q051L .今已知三城镇的污水量分别为Q1 = 5,Q2 = 3,Q3 = 5 L的数值L12 = 20, L23 = 38 .试从节约总投资的角度为三城镇制定污水处理方案；包括是单独还是联合建厂；如果联合，如何分担投资额等.三城镇或单干或不同形式的联合，共有五种方案。下面一一计算所需的投资.方案一三城镇都单干。投资分别为0(1) = 730 X 50712 = 2300C =730X50 711 = 16000(3) = 2300总投资：M -

30、UCJ + UO+U=6200方案二 城1、2合作。这时城1、2将从节约投资的角度对联合还是分别建厂 作出决策，所以城1、2的投资为： 门八八/联合：7?0(5+3)°J6 6乂5咐攵2。= M50。C (1, 2 = 取叫单干：。+匚=3900)=3500C (3) =2300 总投资：国=C (1, 2)+ C =5S0Q方案三 城2、3合作7(3* 3)p30 G+5),-TQ+6,63,n1(7(2)-G C3)= 39PCC (1) =2300总投资：凡=C 3)+ C =595Q方案四 城1、3合作C 口，一娟壮白(3) - J600C (2) =1600总投资：工三 C

31、 Ch 3)+ C =6 2 00方案五三城镇合作3)MI阳7 cccc+ 6 6x5v J1x20 + 65560，CCC2 + + +c + 233 + 5(3) = 5300U) = 5900Q) = 6200+ C(3) = 6200二5560 总投资:M = C (J，2, 3)= 5560比较五个方案可知，应该选择三城合作，联合建厂的方案.下面的问题是如何分担总额为 5560的费用.城3的负责人提出，联合建厂的费用按三城的污水量之比5: 3: 5分担，铺设管道费应由城1、2担负.城2的负责人同意，并提出从城2到城3的管道费由城1、2按污水量之比5: 3分担；从城1到城2的管道费理应

32、由城1自己担负.城 1的负责人觉得他们的提议似乎是合理的， 但因事关重大，他没有马上表示同意；-7O/C 上。上匚0.712A con而是先算了一笔账.联合建厂的费用是73(5+3+5)=4530,城2到城3的管道费是730,城1到城2的管道费是300,按上述办法分配时，城3负担的 费用为1740,城2的费用为1320,域1的费用为2500.结果出乎意料之外，城 3和城2的费用都比单独建厂时少，而城1的费用却比单独建厂时的C(1)还要多. 城1的负责人当然不能同意这个方法，但是一时他又找不出公平合理的解决办 法.为了促成联合的实现，你能为他们提供一个满意的分担费用的方案吗首先，应当指出，城3和

33、城2负责人提出的办法是不合理的：从前面的计算我们 知道，三城联合，才能使总投资节约了 640的效益应该分配给三城，使三城分配 的费用都比他们单干时要少，这是为促成联合所必须制定的一条原则. 至于如何 分配，则是下面要进一步研究的问题.把分担费用转化为分配效益，就不会出现城1联合建厂分担的费用反比单独建厂 费用高的情况.将三城镇记为I=1,2,3,联合建厂比单独建厂节约的投资定义 为特征函数.于是有v( )=0,v(1)=v(2)=v(3)=0,v(1,2)=c(1)+c(2)-c(1,2)=2300+1600-3500=400M2,3)=c(2)+c(3)-c(2,3)=1600+2300-3

34、650=250,v(1,3)=0MI)=c (1)+c(2)+c(3)-c(1,2,3)=640.S11,21,31,2,3V04000640V(s-1)000250V(s)- V(s-1)04000390kl1223W卜1)1/31/61/61/3w( m )v(s)-V(s-1)0670130即 1(V)=197同理得 *2(v) = 321,*3(v)=122那么，城1分担的费用为2300-197=2103,城2分担的费用为1600-321=1279, 城3分担的费用为2300-122=2178，合计5560.习题：某甲(农民)有一块土地。如果从事农业生产可年收入 100元；如果将土地租

35、给 某企业家用于工业生产，可年收入200元；如果租给某旅店老板开发旅游业， 可 年收入300元；当旅店老板请企业家参与经营时， 年收入可达400元。为实现最 高收入，试问如何分配各人的所得才能达成协议例5动态规划模型有不少动态过程可抽象成状态转移问题，特别是多阶段决策过程的最优化如最短路径问题，最优分配，设备更新问题，排序、生产计划和存储等问题.动态规划是一种将复杂问题转化为一种比较简单问题的最优化方法，它的基本特征是包含多个阶段的决策.1951年，美国数学家贝尔曼(R. Bellman)等人，提 出了解决多阶段决策问题的“最优化原理”，并研究了许多实际问题，从而创建 了动态规划动态规划方法的

36、基本思想是：将一个复杂问题分解成若干个阶段， 每一个阶段作 为一个小问题进行处理，从而决定整个过程的决策，阶段往往可以用时间划分这 就具有“动态”的含义，然而，一些与时间无关的静态规划中的最优化问题，也 可人为地把问题分成若干阶段，作为一个多阶段决策问题来处理，计算过程单一 化，便于应用计算机.求解过程分为两大步骤，先按整体最优化思想递序地求 出各个可能状态的最优化决策；再顺序地求出整个题的最优策略和最优路线.下面，结合一个求最短路径的例子，来说明动态规划的一些基本概念.最短路径问题如图所示的交通网络，节点连接线路上的数字表示两地距离， 计算从A到E的最 短路径及长度。1 .阶段.把所要处理的

37、问题，合理地划分成若干个相互联系的阶段，通常用 k表示 阶段变量。如例中，可将问题分为 4个阶段，k=1,2,3,4.2 .状态和状态变量.每一个阶段的起点，称为该阶段的状态，描述过程状态的变量，称为状态变量，它可以用一个数、一组数或一个向量来描述，常用xk来表示第k阶段的某一状(i).(i)态.如果状态为非数量表示，则可以给各个阶段的可能状态编号，Xk =i(Xk表 示第k个阶段的第i状态)。第k阶段状态的集合为X rx 乂(2).兴. X?Xk - xk ,xk，xk，xk 如例6中，第3阶段集合可记为X3 =x31),x32),x33) =Ci,C2,C3 =1,2,33 .决策和决策变

38、量.决策就是在某一阶段给定初始状态的情况下，从该状态演变到下一阶段某状态的 选择。即确定系统过程发展的方案.用一个变量来描述决策，称这个变量为决策变量。设Uk(xk)表示第k个阶段初始状态为xk的决策变量.Dk(xk)表示初始状态为xq允许决策集合，有Uk(xk) Dk(xJ =Uk如例 6 中 D1(A)=B1,B2,B3,若先取 B2,则U1(A) = B2。4 .策略和子策略.由每段的决策Uk(xk)组成的整个过程的决策变量序列称为策略，记为 P1,n ,即R,n =U1（X1）,U2（X2），Un（Xn）从阶段k到阶段n依次进行的阶段决策构成的决策序列称为k子策略，记为Pk，n即Pk,

39、n(xi) =Uk(Xk),Uk i(Xk i)J ,Un(Xn)显然，k=1时的k子策略就是策略。如例6,选取路径AT BiT C2T D2 T E就是一个子策略.从允许策略集中选出的具有最佳效果的策略称为最优策略。5 .状态转移方程.系统在阶段k处于状态Xk ,执行决策uk(Xk)的结果是系统状态的转移，即由阶段K的状态Xk转移到阶段K十1的状态Xk 4适用于动态规划方法求解的是一类具有无后效性的多阶段决策过程.无后效性又称马尔科夫性，指系统从某个阶段往 后的发展，完全由本阶段所处的状态以及其往后的决策决定， 与系统以前的状态 及决策无关，对于具有无后效性的多阶段过程，系统由阶段k向阶段k

40、+1的状态 转移方程为Xk 1-二Tk(Xk,Uk(Xk)意即Xk书只与Xk, uk(XJ有关，而与前面状态无关.Tk(Xk，Uk(Xk)称为变换函数或算子.分确定型和随机型，由此形成确定型动态规划和随机型动态规划.6 .指标函数和最优指标函数.在多阶段决策中，可用一个数量指标来衡量每一个阶段决策的效果，这个数量指标就是指标函数，为该阶段状态变量及其以后各阶段的决策变量的函数，设为Vkf(Vk，n =Vk,n(Xk ,uk , Xk书,A , Xn )k =1,2,A , n指标的含义在不同的问题中各不相同，可以是距离、成本、产品产 量、资源消 耗等.例6中，指标的含义就是距离，指标函数为 A

41、到E的距离，为各阶段路程的和.最常见的指标函数取各阶段效果之和的形式，即nVk,n = " Vj (Xj, Uj) j弥指标函数Vk，n的最优值，称为相应的最优指标函数，记为fk(Xk)fk(Xk) =OptVk,n式中opt是最优化之意，根据问题要求取 max或min.7.动态规划最优化原理.贝尔曼指出“作为整个过程的最优策略具有这样的性质：即无论过去的状态和决 策如何，对前面的决策所形成的状态而言， 余下的诸决策必须构成最优策略” 基 于这个原理，可有如下定理：定理 若策略P，n是最优策略，则对于任意的k(1<k<n),它的子策略Pk，n对于以* 一 , *、xk =(4，1)为起点的k到n子过程来说，必是最优策略.实质上，动态规划的方法是从终点逐段向始点方向寻找最短路径的一种方法.8.动态规划的数学模型.利用最优化原理，可以得到动态规划的数学模型fk(Xk) =OptVk(Xk,Uk) fk i(Xk .J(k =n,n -1,. ,1uk Dk(Xk)fn 1 (xn 1)-0这是一个