數(shù)學(xué)建模例題及解析

1、例1分分方程一一資金的時間價值問題1:抵押貸款買房一一從一則廣告談起每家人家都希望有一套（甚至一棟）屬于自己的住房，但又沒有足夠的資金一次買 下，這就產(chǎn)生了貸款買房的問題。先看一下下面的廣告（這是1991年1月1日某 大城市晚報上登的一則廣告），任何人看了這則廣告都會產(chǎn)生許多疑問，且不談 廣告中沒有談住房面積、設(shè)施等等，人們關(guān)心的是：如果一次付款買這棟房要多 少錢呢銀行貸款的利息是多少呢為什么每個月要付1200元呢是怎樣算出來的因?yàn)槿藗兌贾溃糁懒朔績r（一次付款買房的價格），如果自己只能支付一部分 款，那就要把其余的款項(xiàng)通過借貸方式來解決，只要知道利息，就應(yīng)該可以算出五年還清每月要付多少錢

2、才能按時還清貸款了， 從而也就可以對是否要去買該廣 告中所說的房子作出決策了。現(xiàn)在我們來進(jìn)行數(shù)學(xué)建模。由于本問題比較簡單無 需太多的抽象和簡化。a.明確變量、參數(shù)，顯然下面的量是要考慮的：需要借多少錢，用記；月利率（貸款通常按復(fù)利計）用R記；每月還多少錢用x記；借期記為N個月。b.建立變量之間的明確的數(shù)學(xué)關(guān)系。若用 *記第k個月時尚欠的 款數(shù)，則一 個月后（加上利息后）欠款 且=, 不過我們又還了 x元 所以總的欠款為&+】三人工 k=0,1, 2, 3,而一開始的借款為所以我們的數(shù)學(xué)模型可表述如下上jt+i ） 4r五出:0, 11 2 t 3 ,為已知（不妨假設(shè)人為已知）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á)"為&之間的顯式關(guān)系。d.針對廣告中的情形我們來看(1)和(2)中哪些量是已知的。N=5年=60個月， 已知；每月還款x= 1200元，已知A。即一次性付款購買價減去 70000元后剩下 的要另外去借的款，并沒有告訴你，此外銀行貸款利率R也沒告訴你，這造成了 我們決策的困又to然而，由(2)可知60個月后還清，即四

4、時三。，從 而得 0 = &(1+R嚴(yán)- 專入 HR)叫 1 # _ 1200(l+/°- 1小二一赤科一 表示N= 60, x= 1200給定時A0和x之間的關(guān)系式，如果 我們已經(jīng)知道銀行 的貸款利息R,就可以算出A0。例如，若R =0. 01 ,則由(3)可算得 為三53946元。如果該房地產(chǎn)公司說一 次性付款的房價大于70000十53946= 123946元的話，你就應(yīng)自 己去銀行借款。事實(shí)上，利用圖形計算器或 Mathematica 這樣的數(shù)學(xué)軟件可把(3)的圖形畫出來，從而可以進(jìn)行估算決策。以下我們進(jìn)一步考慮 下面兩個問題。注1問題1標(biāo)題中“抵押貸款”的意思無非是銀

5、行伯你借了錢不還，因而要你用某種不動產(chǎn)(包括房子的產(chǎn)權(quán))作抵押，即萬一你還不出錢了，就沒收你的不動產(chǎn)。 例題1某高校一對年青夫婦為買房要用銀行貸款 60000元，月利率0. 01,貸款 期25年=300月,這對夫婦希望知道每月要還多少錢，25年就可還清。假設(shè)這 對夫婦每月可有節(jié)余900元，是否可以去買房呢解：現(xiàn)在的問題就是要求使 月網(wǎng)。二口的x,由（2）式知_/0一*x （1+一）*-）現(xiàn)為= 60000, R= 0. 01, k = 300,算得x=632元，這說明這對夫婦有能力買房。 例題2恰在此時這對夫婦看到某借貸公司的一則廣告：“若借款60000元，22年還清，只要；（i）每半個月還3

6、16元；（ii）由于文書工作多了的關(guān)系要你預(yù)付 三個月的款，即316X 6= 1896元。這對夫婦想：提前三年還清當(dāng)然是好事，每 半個月還316元，那一個月不正好是還632元，只不過多跑一趟去交款罷了； 要 預(yù)付18%元，當(dāng)然使人不高興，但提前三年還清省下來的錢可是22752元喲，是1896元的十幾倍哪！這家公司是慈善機(jī)構(gòu)呢還是仍然要賺我們的錢呢這對夫 婦請教你給他們一個滿意的回答。具體解法略。問題2:養(yǎng)老基金今后，當(dāng)年青人參加工作后就要從其每月工資中扣除一部分作為個人的養(yǎng)老基金，所在單位（若經(jīng)濟(jì)效益好的話）每月再投入一定數(shù)量的錢，再存入某種利息 較高而又安全的“銀行”（也可稱為貨幣市場）到6

7、0歲退休時可以動用。也就是 說，若退休金不足以維持一定的生活水平時， 就可以動用自己的養(yǎng)老基金，每月 取出一定的款項(xiàng)來補(bǔ)貼不足部分。假設(shè)月利率及= 0. 01不變，還允許在建立養(yǎng) 老基金時自己可以一次性地存入一筆錢 人（不論多少），每月存入y元（個人和單 位投入的總和）；通常從三十一歲開始到六十歲就可以動用。這當(dāng)然是一種簡化的假設(shè)，但作為估算仍可作為一種考慮的出發(fā)點(diǎn)。本問題實(shí)際上有兩個階段， 即退休前和退休后，其數(shù)學(xué)模型為UI+l = 44A h = U? 1, 2 f 3 1回已知= 4 ：1+一） - xj ra = 3 11 1.h川已知其中x為每月要從養(yǎng)老基金中提出的款項(xiàng)。習(xí)題1某大學(xué)

8、年青教師小李從31歲開始建立自己的養(yǎng)老基金，他把已有的積蓄1萬元也一次性地存入，已知月利率為 0. 01 （以復(fù)利計），每月存入300 元，試問當(dāng)小李60歲退休時，他的退休基金有多少又若，他退休后每月要從銀行提取1000元，試問多少年后他的退休基金將用完你能否根據(jù)你了解的實(shí)際 情況建立一個較好的養(yǎng)老基金的數(shù)學(xué)模型及相應(yīng)的算法和程取軟件）。習(xí)題2漁業(yè)（林業(yè)）管理問題設(shè)某養(yǎng)魚池（或某海域）一開始有某種魚條，魚的平均年 凈繁殖率為R,每 年捕撈x條，記第N年有魚.加條，則池內(nèi)魚數(shù)按年的變化規(guī)律為工胡4三乂州11+尺J * Z ）工巾已知注意，在實(shí)際漁業(yè)經(jīng)營中并不按條數(shù)計算而是以噸記數(shù)的。若對某海域的

9、漁業(yè)作業(yè)中4=100000噸，R= 0. 02, x=1000噸，試問="會不會使得若干年后 就沒有魚可捕撈了（資源枯竭了） 例2比例分析法一一席位分配問題：某學(xué)校有三個系聯(lián)合成立學(xué)生會，（1）試確定學(xué)生會席位分配方案。（2）若甲系有100名，乙系60名，丙系40名。學(xué)生會設(shè)20個席位，分配方案 如何（3）若丙系有3名學(xué)生轉(zhuǎn)入甲系，3名學(xué)生轉(zhuǎn)入乙系，分配方案有何變化（4）因?yàn)橛?0個席位的代表會議在表決提案時有可能出現(xiàn) 10: 10的平局， 會議決定下一屆增加1席，若在第（3）問中將學(xué)生會席位增加一席呢（5）試確定一數(shù)量指標(biāo)衡量席位分配的公平性，并以此檢查（1） （4）。公平而又簡單

10、的席位分配辦法是按人數(shù)的比例分配，若甲系有100名，乙系60名，丙系40名。學(xué)生會設(shè)20個席位，三個系分別應(yīng)有10, 6, 4個席位。如果丙系有6名學(xué)生轉(zhuǎn)入其他兩系學(xué)習(xí)，各系人數(shù)如表所示系別學(xué)生人數(shù)所占比例（%按比例分配的席位按慣例分配的席位甲10310乙636丙344總和20020第二列所示，按比例分配席位時，出現(xiàn)了小數(shù)（見表中第四列）.在將取得整數(shù)的 19席分配完畢后，剩下的1席按照慣例分給余數(shù)最大的丙系，于是三個系仍分 別占有10、6、4個席位.因?yàn)橛?0個席位的代表會議在表決提案時有可能出現(xiàn) 10: 10的平局，會議決定 下一屆增加1席，于是他們按照上述慣例重新分配席位，計算的結(jié)果令人

11、吃驚： 總席位增加1席，丙系反而減少1席，見下表.系別學(xué)生人數(shù)所占比例（%按比例分配的席位按慣例分配的席位甲10311乙637丙：343總和20021看來，要解決這個矛盾，必須重新研究所謂慣例分配方法，提出更加“公平”的 辦法.下面就介紹這樣一個席位分配模型.設(shè) A、B兩方人數(shù)分別是pl和p2,分別占 有n1和n2個席位，則兩方每個席位所代表的人數(shù)分別是 pl /n12和p2/n2.很明顯，僅當(dāng)這兩個 數(shù)值相等時，席位的分配才是公平的.但是，通常它們不會相等，這時席位分配 得不公平。不公平的程度可以用數(shù)值加加2|來表示，它衡量的是“絕對不公平”.從下表所舉的例子來看，A B之間的“絕對不公平”

12、與 G D之間是一樣的。但是 從常識的角度看，A B之間顯然 比G D之間存在著更加嚴(yán)重的不公平.所以“絕對不公平”不是一個好的衡量標(biāo)準(zhǔn).pnp/np1/n1-p2/n2A120101212-10=2B1001010C102010102102-100=2D100010100為了改進(jìn)絕對標(biāo)準(zhǔn)，我們自然想到用相對標(biāo)準(zhǔn).因?yàn)閜/n越大，每個席位代表的人數(shù)越多，或者說，總?cè)藬?shù)一定時分配的席位越少。所以，如果p1/n13>p2/n2,則A方是吃虧的，或者說，對 A是不公平的，由此，我們這樣定義“相 對不公平”：若 p1/n1>p2/n2,則稱尸2的2學(xué)1僅1 p2n , /加1#1理2為對A

13、的相對不公平值，記做皿吟“若 p1/n1<p2/n2,則稱產(chǎn)1加1子2加2 _ pl烈2p2 M2中2部】為對B的相對不公平值，記做陛（川，吟。假設(shè)A、B兩方已分別占有n1和n2個席位，我們利用相對不公平的城念來討論，當(dāng)總席位再增加1席時，應(yīng)該給且A方還是B方不失一般性，可設(shè)p1/n1>p2/n2,即此時對A方不公平，有定義.當(dāng)再分配1個席位時，關(guān)于p/n的不等式有以下三種可能：1）p1/（n1十1） >p2/n2,這說明即使A方增加1席，仍然對A不公平，所以這 1席當(dāng)然應(yīng)給A2）p1/（n1十1）<p2/n2,說明當(dāng)A方增加1席位，將對B不公平，此時應(yīng)參照 式，計算對

14、B的相對不公平值3）說明當(dāng)B方增加1席時，將對A方不公平，此時計算得對 A的相對不公平值 是心（管 1 + 1,前2）（打 1, «2 + 1）（注意：在p1/n1；'p2/n2的假設(shè)下，不可能出現(xiàn) p1/n1 <p2/（n2+1）的情況因?yàn)楣降南环峙浞椒☉?yīng)該使得相對不公平的數(shù)值盡量地小，所以如果廣總(«1 +1 j盟2)(哲1.司2 + 1)則這1席應(yīng)給A方；反之應(yīng)給B方.根據(jù)（3）、（4）兩式，（5）式等價于并且不難 證明1從上述第1）種情況的p1/（n1十1） >p2/p2也可推出。 于是我們的結(jié) 論是：當(dāng)（6）式成立時，增加的1席應(yīng)分配A方；

15、反之，應(yīng)分配給B方.若記!'（存計1,則增加的1席位應(yīng)分配給Q值較大的一方.將上述方法可以推廣到有m方分配席位的情況.下面用這個方法，重新討論本節(jié)開始時提出的，三個系分配21個席位的問題.首先每系分配1席，然后計算：甲系n1 = 1,_3” _ 1。里Q =乙系，n2=1 ,=02） 3_ 53二防二位而+1）一 =丙系，n3=1,_03） 3_ 3 甲Q=支（蔻+1）一=而因?yàn)镼1最大，所以第4席應(yīng)分配給甲系，繼續(xù)計算：甲系n1 = 2,O1） 3103工Q = MTEHT = R= 176g 2將以與上面的。如1a相比，5最大，第5席應(yīng)分給乙系，繼續(xù)計算。如此繼續(xù), 直到第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席。你覺得這個方法公平嗎 習(xí)題：學(xué)校共1000名學(xué)生，235入住在A宿合，333人住在B宿合，432人住在C宿合.學(xué) 生們要組織一個10人的委員會，試用下列辦法分配各宿舍的委員數(shù).1)慣例的方法，印按比例分配完整數(shù)名額后，剩下名額給余數(shù)最大者。2) Q值方法。如果委員會從10人增至15人，分配名額將發(fā)生什么變化，例3狀態(tài)轉(zhuǎn)移問題一一常

17、染色體遺傳模型隨著人類的進(jìn)化，人們?yōu)榱私沂旧膴W秘，越來越注重遺傳學(xué)的研究，特別是 遺傳特征的逐代傳播，引起人們的注意。無論是人，還是動植物都會將本身的特 征遺傳給下一代，這主要是因?yàn)楹蟠^承了雙親的基因， 形成自己的基因?qū)Γ?因?qū)⒋_定后代所表現(xiàn)的特征。下面，我們來研究兩種類型的遺傳：常染色體遺 傳和x一鏈遺傳。根據(jù)親體基因遺傳給后代的方式，建立模型，利用這些模型可 以逐代研究一個總體基因型的分布。在常染色體遺傳中，后代從每個親體的基因?qū)χ懈骼^承一個基因，形成自己的基因?qū)Γ驅(qū)σ卜Q基因型。如果我們所考慮的遺傳特征是有兩個基因 A和控制的， 那么就有三種基因?qū)?，記?AA A,。例如，金

18、草魚由兩個遺傳基因決定花的顏 色，基因型是AA的金魚草開紅花，型的開粉紅色花，而型的開白花。又如人類 的眼睛的顏色也是提高通過常染色體遺傳控制的?；蛐褪堑娜耍劬κ亲厣?， 基因型是的人，眼睛是蘭色。這里因?yàn)槎急硎玖送煌獠刻卣?，我們認(rèn)為基因 A 支配基因，也可以認(rèn)為基因?qū)τ?A來說是隱性的父體一母體的基因型AA-AAAA-AaAA-aaAa-AaAa-aaaa-aa后 代 基 因 型AA11/201/400Aa01/211/21/20aa0001/41/21農(nóng)場的植物園中某種植物的基因型為 AA A和。農(nóng)場計劃采用AA型的植物與每種基因型植物相結(jié)合的方案培育植物后代。那么經(jīng)過若干年后，這種植

19、物的任 代的三種基因型分布如何第一步：假設(shè)：令n=0,1,2,A 0(1)設(shè)an，bn和cn分別表示第n代植物中，基因型為AA,Aa和aa的植物占植物總數(shù)的百分率。令x為第n代植物的基因型分布：anlx(n) = bncn J當(dāng)n=0時ax=bo：c0 一表示植物基因型的初始分布（即培育開始時的分布），顯然有ao - bo Co =1（2）第n代的分布與第n-1代的分布之間的關(guān)系是通過上表確定的。第二步：建模根據(jù)假設(shè)（2）,先考慮第n代中的AA型。由于第n-1代的AA型與AA型結(jié)合，后代全部是AA型；第n-1代的Aa型與AA型結(jié)合，后代是AA型的可能性為1/2 ,第n-1代的aa型與AA型結(jié)合

20、，后代不可能是 AA型。因此，當(dāng)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根據(jù)假設(shè)（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）式給出第代基因型的分布與初始分布的關(guān)系。為了

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當(dāng)nT餡時(1/2)nT 0所以從式得到an T 1,bn T 0 和 Cn=0即在極限的情況下，培育的植物都是 AA型。第三步：模型討論若在上述問題中，不選用基因 AA型的植物與每一植物結(jié)合，而是將具有相同基 因型植物相結(jié)合，那么后代具有三代基因型的概率如下

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 一通過計算，可以解出與，%相對應(yīng)的兩個線性無關(guān)的特征向量 入1和紅，及與九3一1 1%=0相對應(yīng)的特征向量%: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當(dāng)nTg時。/2）nT 0,所以從式得到anT a0 +（1/ 2）b0, bn t。和 Cn t C0 + （1/2也因此，如果用基因型相同的植物培育后代，在極限情況下，后代僅具有基因AA和aa。例4合作對策模型在經(jīng)濟(jì)或社會活動中，幾個社會實(shí)體（個人、公司、黨派、國家）相互合作或結(jié) 成聯(lián)盟，常能獲得比他們單獨(dú)行動更多的經(jīng)濟(jì)或社會效益。這樣合理地分配這些效益是合作對策要研究的問題。請看下面的例子

25、。問題一：經(jīng)商問題甲、乙、丙三人經(jīng)商，若單干，每人僅能獲利 1元；甲乙合作可獲利7元；甲丙 合作可獲利5元；乙丙合作可獲利4元；三人合作可獲利10元，問三人合作時 如何分配10元的收入。甲的收入應(yīng)按照甲對各種形式的合作的貢獻(xiàn)來確定.對于某一合作的貢獻(xiàn)定義為：有甲參加時這個合作的收入與無甲參加時這個合作的收入之差.例如甲對甲乙二人合作的貢獻(xiàn)是 71=6 （因?yàn)榧滓液献鳙@利 7元，而乙單干僅獲利 1 元）.甲可以參加的，合作有四個：甲自己（單干視為合作的特例）、甲乙、甲丙、 甲乙丙.甲對這些合作的貢獻(xiàn)分別是甲：1 0=1元；甲乙：71 = 6元；甲內(nèi)：51 = 4元；甲乙丙：104 = 6元，甲應(yīng)

26、分得的收入是這四個貢獻(xiàn)的加權(quán)平 均值，加權(quán)因子將由下面的一般模型給出.這個問題叫做3人合作對策，是對策論的一部分，這里介紹它的一種解法。一般的n人合作對策模型可以敘述如下：記n人集合為1=1；，丸-造），如果對于I中的任一子集&#1,都對應(yīng)一個實(shí)值函數(shù)v （s）,滿足v 10）= 0v Csio 匆）v （門.）-Hv （/）（4G s =小）則稱為定義在I上的特征函數(shù).所謂合作對策是指定義了特征函數(shù)的I中n個人 的合作結(jié)果，用向量值函數(shù)。=例'Q，s快） 來表示.在實(shí)際問題中.?？砂袸中各種組合的合作獲得的利益定義為特征函數(shù)，上式表示合作規(guī)模擴(kuò)大時，獲利不會減少。不 難看出，

27、如將三人經(jīng)商問題中合作的獲利定義為特征函數(shù) v, v是滿足（1）、（2） 的.為了確定，,Shapley在1953年首先制定了一組6刃應(yīng)該滿足的公理，然后證明了滿足這組公理的 *'I的唯一解是他（Q 二, 5 = 1, 2, 3,.1,司其中凡是I中包含i的所有子集，Ml是集合s中的人數(shù)，是加權(quán)因子，由(|占|)=ql- 1> ! 5 |川1 Iy 9 ' is- a” 可看作成員i對合作s的貢獻(xiàn)；表示對所有包含i的集合求和.63,稱為由v定義的合作的Shapley值.我們用（3）、（4）計算三人經(jīng)商問題中各個人應(yīng)得到的收入.甲、乙、丙分別記作1 , 2 , 3,包含1的

28、集合有1、1 , 2、1 , 3、1 , 2, 3,計算結(jié)果列入下表.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元 .同樣可以算出乙、丙應(yīng)得收入為 6 卜）=3. 5元， '»）=元。問題二：三城鎮(zhèn)的污水處理方案沿河有三城鎮(zhèn)1、2和3,地理位置如圖4; 6所示.污水需處理后才能排入河中.三 城鎮(zhèn)或者單獨(dú)建立污水處理廠，或者聯(lián)合建廠，用管道將污水集中處理 （污水應(yīng) 于河流的上游城鎮(zhèn)向下游城鎮(zhèn)輸送

29、）。以Q表示污水量（噸/秒），工表示管道長 度（公里）。0.712按照經(jīng)驗(yàn)公式，建立處理廠的費(fèi)用為P = 73Q,鋪設(shè)管道的費(fèi)用為P = 0.66Q051L .今已知三城鎮(zhèn)的污水量分別為Q1 = 5,Q2 = 3,Q3 = 5 L的數(shù)值L12 = 20, L23 = 38 .試從節(jié)約總投資的角度為三城鎮(zhèn)制定污水處理方案；包括是單獨(dú)還是聯(lián)合建廠；如果聯(lián)合，如何分擔(dān)投資額等.三城鎮(zhèn)或單干或不同形式的聯(lián)合，共有五種方案。下面一一計算所需的投資.方案一三城鎮(zhèn)都單干。投資分別為0(1) = 730 X 50712 = 2300C =730X50 711 = 16000(3) = 2300總投資：M -

30、UCJ + UO+U=6200方案二 城1、2合作。這時城1、2將從節(jié)約投資的角度對聯(lián)合還是分別建廠 作出決策，所以城1、2的投資為： 門八八/聯(lián)合：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方案五三城鎮(zhèn)合作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比較五個方案可知，應(yīng)該選擇三城合作，聯(lián)合建廠的方案.下面的問題是如何分擔(dān)總額為 5560的費(fèi)用.城3的負(fù)責(zé)人提出，聯(lián)合建廠的費(fèi)用按三城的污水量之比5: 3: 5分擔(dān)，鋪設(shè)管道費(fèi)應(yīng)由城1、2擔(dān)負(fù).城2的負(fù)責(zé)人同意，并提出從城2到城3的管道費(fèi)由城1、2按污水量之比5: 3分擔(dān)；從城1到城2的管道費(fèi)理應(yīng)

32、由城1自己擔(dān)負(fù).城 1的負(fù)責(zé)人覺得他們的提議似乎是合理的， 但因事關(guān)重大，他沒有馬上表示同意；-7O/C 上。上匚0.712A con而是先算了一筆賬.聯(lián)合建廠的費(fèi)用是73(5+3+5)=4530,城2到城3的管道費(fèi)是730,城1到城2的管道費(fèi)是300,按上述辦法分配時，城3負(fù)擔(dān)的 費(fèi)用為1740,城2的費(fèi)用為1320,域1的費(fèi)用為2500.結(jié)果出乎意料之外，城 3和城2的費(fèi)用都比單獨(dú)建廠時少，而城1的費(fèi)用卻比單獨(dú)建廠時的C(1)還要多. 城1的負(fù)責(zé)人當(dāng)然不能同意這個方法，但是一時他又找不出公平合理的解決辦 法.為了促成聯(lián)合的實(shí)現(xiàn)，你能為他們提供一個滿意的分擔(dān)費(fèi)用的方案嗎首先，應(yīng)當(dāng)指出，城3和

33、城2負(fù)責(zé)人提出的辦法是不合理的：從前面的計算我們 知道，三城聯(lián)合，才能使總投資節(jié)約了 640的效益應(yīng)該分配給三城，使三城分配 的費(fèi)用都比他們單干時要少，這是為促成聯(lián)合所必須制定的一條原則. 至于如何 分配，則是下面要進(jìn)一步研究的問題.把分擔(dān)費(fèi)用轉(zhuǎn)化為分配效益，就不會出現(xiàn)城1聯(lián)合建廠分擔(dān)的費(fèi)用反比單獨(dú)建廠 費(fèi)用高的情況.將三城鎮(zhèn)記為I=1,2,3,聯(lián)合建廠比單獨(dú)建廠節(jié)約的投資定義 為特征函數(shù).于是有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分擔(dān)的費(fèi)用為2300-197=2103,城2分擔(dān)的費(fèi)用為1600-321=1279, 城3分擔(dān)的費(fèi)用為2300-122=2178，合計5560.習(xí)題：某甲(農(nóng)民)有一塊土地。如果從事農(nóng)業(yè)生產(chǎn)可年收入 100元；如果將土地租

35、給 某企業(yè)家用于工業(yè)生產(chǎn)，可年收入200元；如果租給某旅店老板開發(fā)旅游業(yè)， 可 年收入300元；當(dāng)旅店老板請企業(yè)家參與經(jīng)營時， 年收入可達(dá)400元。為實(shí)現(xiàn)最 高收入，試問如何分配各人的所得才能達(dá)成協(xié)議例5動態(tài)規(guī)劃模型有不少動態(tài)過程可抽象成狀態(tài)轉(zhuǎn)移問題，特別是多階段決策過程的最優(yōu)化如最短路徑問題，最優(yōu)分配，設(shè)備更新問題，排序、生產(chǎn)計劃和存儲等問題.動態(tài)規(guī)劃是一種將復(fù)雜問題轉(zhuǎn)化為一種比較簡單問題的最優(yōu)化方法，它的基本特征是包含多個階段的決策.1951年，美國數(shù)學(xué)家貝爾曼(R. Bellman)等人，提 出了解決多階段決策問題的“最優(yōu)化原理”，并研究了許多實(shí)際問題，從而創(chuàng)建 了動態(tài)規(guī)劃動態(tài)規(guī)劃方法的

36、基本思想是：將一個復(fù)雜問題分解成若干個階段， 每一個階段作 為一個小問題進(jìn)行處理，從而決定整個過程的決策，階段往往可以用時間劃分這 就具有“動態(tài)”的含義，然而，一些與時間無關(guān)的靜態(tài)規(guī)劃中的最優(yōu)化問題，也 可人為地把問題分成若干階段，作為一個多階段決策問題來處理，計算過程單一 化，便于應(yīng)用計算機(jī).求解過程分為兩大步驟，先按整體最優(yōu)化思想遞序地求 出各個可能狀態(tài)的最優(yōu)化決策；再順序地求出整個題的最優(yōu)策略和最優(yōu)路線.下面，結(jié)合一個求最短路徑的例子，來說明動態(tài)規(guī)劃的一些基本概念.最短路徑問題如圖所示的交通網(wǎng)絡(luò)，節(jié)點(diǎn)連接線路上的數(shù)字表示兩地距離， 計算從A到E的最 短路徑及長度。1 .階段.把所要處理的

37、問題，合理地劃分成若干個相互聯(lián)系的階段，通常用 k表示 階段變量。如例中，可將問題分為 4個階段，k=1,2,3,4.2 .狀態(tài)和狀態(tài)變量.每一個階段的起點(diǎn)，稱為該階段的狀態(tài)，描述過程狀態(tài)的變量，稱為狀態(tài)變量，它可以用一個數(shù)、一組數(shù)或一個向量來描述，常用xk來表示第k階段的某一狀(i).(i)態(tài).如果狀態(tài)為非數(shù)量表示，則可以給各個階段的可能狀態(tài)編號，Xk =i(Xk表 示第k個階段的第i狀態(tài))。第k階段狀態(tài)的集合為X rx 乂(2).興. X?Xk - xk ,xk，xk，xk 如例6中，第3階段集合可記為X3 =x31),x32),x33) =Ci,C2,C3 =1,2,33 .決策和決策變

38、量.決策就是在某一階段給定初始狀態(tài)的情況下，從該狀態(tài)演變到下一階段某狀態(tài)的 選擇。即確定系統(tǒng)過程發(fā)展的方案.用一個變量來描述決策，稱這個變量為決策變量。設(shè)Uk(xk)表示第k個階段初始狀態(tài)為xk的決策變量.Dk(xk)表示初始狀態(tài)為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依次進(jìn)行的階段決策構(gòu)成的決策序列稱為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就是一個子策略.從允許策略集中選出的具有最佳效果的策略稱為最優(yōu)策略。5 .狀態(tài)轉(zhuǎn)移方程.系統(tǒng)在階段k處于狀態(tài)Xk ,執(zhí)行決策uk(Xk)的結(jié)果是系統(tǒng)狀態(tài)的轉(zhuǎn)移，即由階段K的狀態(tài)Xk轉(zhuǎn)移到階段K十1的狀態(tài)Xk 4適用于動態(tài)規(guī)劃方法求解的是一類具有無后效性的多階段決策過程.無后效性又稱馬爾科夫性，指系統(tǒng)從某個階段往 后的發(fā)展，完全由本階段所處的狀態(tài)以及其往后的決策決定， 與系統(tǒng)以前的狀態(tài) 及決策無關(guān)，對于具有無后效性的多階段過程，系統(tǒng)由階段k向階段k

40、+1的狀態(tài) 轉(zhuǎn)移方程為Xk 1-二Tk(Xk,Uk(Xk)意即Xk書只與Xk, uk(XJ有關(guān)，而與前面狀態(tài)無關(guān).Tk(Xk，Uk(Xk)稱為變換函數(shù)或算子.分確定型和隨機(jī)型，由此形成確定型動態(tài)規(guī)劃和隨機(jī)型動態(tài)規(guī)劃.6 .指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù).在多階段決策中，可用一個數(shù)量指標(biāo)來衡量每一個階段決策的效果，這個數(shù)量指標(biāo)就是指標(biāo)函數(shù)，為該階段狀態(tài)變量及其以后各階段的決策變量的函數(shù)，設(shè)為Vkf(Vk，n =Vk,n(Xk ,uk , Xk書,A , Xn )k =1,2,A , n指標(biāo)的含義在不同的問題中各不相同，可以是距離、成本、產(chǎn)品產(chǎn) 量、資源消 耗等.例6中，指標(biāo)的含義就是距離，指標(biāo)函數(shù)為 A

41、到E的距離，為各階段路程的和.最常見的指標(biāo)函數(shù)取各階段效果之和的形式，即nVk,n = " Vj (Xj, Uj) j彌指標(biāo)函數(shù)Vk，n的最優(yōu)值，稱為相應(yīng)的最優(yōu)指標(biāo)函數(shù)，記為fk(Xk)fk(Xk) =OptVk,n式中opt是最優(yōu)化之意，根據(jù)問題要求取 max或min.7.動態(tài)規(guī)劃最優(yōu)化原理.貝爾曼指出“作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：即無論過去的狀態(tài)和決 策如何，對前面的決策所形成的狀態(tài)而言， 余下的諸決策必須構(gòu)成最優(yōu)策略” 基 于這個原理，可有如下定理：定理 若策略P，n是最優(yōu)策略，則對于任意的k(1<k<n),它的子策略Pk，n對于以* 一 , *、xk =(4，1)為起點(diǎn)的k到n子過程來說，必是最優(yōu)策略.實(shí)質(zhì)上，動態(tài)規(guī)劃的方法是從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易疃搪窂降囊环N方法.8.動態(tài)規(guī)劃的數(shù)學(xué)模型.利用最優(yōu)化原理，可以得到動態(tài)規(guī)劃的數(shù)學(xué)模型fk(Xk) =OptVk(Xk,Uk) fk i(Xk .J(k =n,n -1,. ,1uk Dk(Xk)fn 1 (xn 1)-0這是一個