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

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

2、道利息， 就應(yīng)該可以 算出五年還清每月要付多少錢才能按時還清貸款了， 從而也就可以對是否要去買 該廣告中所說的房子作出決策了。 現(xiàn)在我們來進行數(shù)學(xué)建模。 由于本問題比較簡 單無需太多的抽象和簡化。a.明確變量、參數(shù)，顯然下面的量是要考慮的：需要借多少錢，用 記； 月利率（貸款通常按復(fù)利計 ）用 R記； 每月還多少錢用 x 記； 借期記為 N 個月。b建立變量之間的明確的數(shù)學(xué)關(guān)系。若用記第 k 個月時尚欠的 款數(shù)，則一個月后（加上利息后 ）欠款， 不過 我們又還了 x元所以總的欠款為k=0，1，2，3，而一開始的借款為 。所以我們的數(shù)學(xué)模型可表述如下c. （1）的求解。由(1)這就是 之間的顯式

3、關(guān)系。d針對廣告中的情形我們來看 (1)和(2)中哪些量是已知的。 N=5年 60 個月，已 知；每月還款 x1200 元，已知 A。即一次性付款購買價減去 70000元后剩下的 要另外去借的款， 并沒有告訴你， 此外銀行貸款利率 R 也沒告訴你， 這造成了我，從 而得(3)們決策的困難。然而，由 (2)可知 60 個月后還清，即(3) 表示 N60，x1200給定時 A0和 x之間的關(guān)系式，如果 我們已經(jīng)知道銀行 的貸款利息 R，就可以算出 A0 。例如，若 R 001，則由(3)可算得53946元。如果該房地產(chǎn)公司說一 次性付款的房價大于 70000十 53946123946 元的話， 你

4、就 應(yīng)自 己去銀 行借款 。事實 上，利用圖形 計算器 或 Mathematica 這樣的數(shù)學(xué)軟件可把 (3)的圖形畫出來，從而可以進行估算決策。以下我們進一步考慮 下面兩個問題。注 1 問題 1 標題中“抵押貸款” 的意思無非是銀行伯你借了錢不還， 因而要你用 某種不動產(chǎn) (包括房子的產(chǎn)權(quán) )作抵押，即萬一你還不出錢了， 就沒收你的不動產(chǎn)。 例題 1 某高校一對年青夫婦為買房要用銀行貸款 60000 元，月利率 0 01，貸款 期 25 年300 月，這對夫婦希望知道每月要還多少錢， 25 年就可還清。假設(shè)這 對夫婦每月可有節(jié)余 900 元，是否可以去買房呢 ?解：現(xiàn)在的問題就是要求使的 x

5、，由 （2）式知現(xiàn) 60000，R001，k300，算得 x=632 元，這說明這對夫婦有能力買房。 例題 2 恰在此時這對夫婦看到某借貸公司的一則廣告： “若借款 60000 元， 22 年還清，只要； （i）每半個月還 316元；（ii）由于文書工作多了的關(guān)系要你預(yù)付三個 月的款，即 316× 61896 元。這對夫婦想：提前三年還清當(dāng)然是好事，每半個 月還 316 元，那一個月不正好是還 632元，只不過多跑一趟去交款罷了； 要預(yù)付 18元，當(dāng)然使人不高興，但提前三年還清省下來的錢可是 22752元喲，是 1896 元的十幾倍哪 ! 這家公司是慈善機構(gòu)呢還是仍然要賺我們的錢呢?

6、這對夫婦請教你給他們一個滿意的回答。具體解法略。問題 2：養(yǎng)老基金 今后，當(dāng)年青人參加工作后就要從其每月工資中扣除一部分作為個人 的養(yǎng)老基 金，所在單位（若經(jīng)濟效益好的話）每月再投入一定數(shù)量的錢，再存入某種利息 較高而又安全的“銀行” （也可稱為貨幣市場 ）到 60 歲退休時可以動用。也就是 說，若退休金不足以維持一定的生活水平時， 就可以動用自己的養(yǎng)老基金， 每月 取出一定的款項來補貼不足部分。假設(shè)月利率及 001 不變，還允許在建立養(yǎng) 老基金時自己可以一次性地存入一筆錢 A0（不論多少 ），每月存入 y 元（個人和單 位投入的總和 ）；通常從三十一歲 開始到六十歲就可以動用。這當(dāng)然是一種簡

7、 化的假設(shè)，但作為估算仍可作為一種考慮的出發(fā)點。本問題實際上有兩個階段， 即退休前和退休后，其數(shù)學(xué)模型為其中 x 為每月要從養(yǎng)老基金中提出的款項。習(xí)題 1 某大學(xué)年青教師小李從 31 歲開始建立自己的養(yǎng)老基 金，他把已有的 積蓄 1 萬元也一次性地存入，已知月利率為 001 （以復(fù)利計 ），每月存入 300 元，試問當(dāng)小李 60 歲退休時， 他的退 休基金有多少 ?又若，他退休后每月要從銀行提取 l000 元，試問多少年后他的退休基金將用完 ?你能否根據(jù)你了解的實際 情況建立一個較好的養(yǎng)老基金的數(shù)學(xué)模型及相應(yīng)的算法和程取軟件 ）。習(xí)題 2 漁業(yè) （林業(yè)）管理問題設(shè)某養(yǎng)魚池 （或某海域 ）一開始

8、有某種魚條，魚的平均年 凈繁殖率為 R，每年捕撈 x條，記第 N 年有魚 條，則池內(nèi)魚數(shù)按年的變化規(guī)律為注意，在實際漁業(yè)經(jīng)營中并不按條數(shù)計算而是以噸記數(shù)的。 若對某海域的漁業(yè)作 業(yè)中 100000噸，R002，x1000 噸，試問會不會使得若干年后就沒有魚可捕撈了（資源枯竭了）？例 2 比例分析法席位分配 問題：某學(xué)校有三個系聯(lián)合成立學(xué)生會，（1）試確定學(xué)生會席位分配方案。（2）若甲系有100名，乙系60名，丙系40名。學(xué)生會設(shè) 20個席位，分配方案 如何？（3）若丙系有 3 名學(xué)生轉(zhuǎn)入甲系， 3 名學(xué)生轉(zhuǎn)入乙系，分配方案有何變化？（4）因為有 20 個席位的代表會議在表決提案時有可能出現(xiàn) 1

9、0： 10的平局， 會議決定下一屆增加 1席，若在第（ 3）問中將學(xué)生會席位增加一席呢？（5）試確定一數(shù)量指標衡量席位分配的公平性，并以此檢查（ 1）（ 4）。 公平而又簡單的席位分配辦法是按人數(shù)的比例分配，若甲系有 100 名，乙系 60 名，丙系 40 名。學(xué)生會設(shè) 20個席位，三個系分別應(yīng)有 10，6，4 個席位。如果丙系有 6 名學(xué)生轉(zhuǎn)入其他兩系學(xué)習(xí)，各系人數(shù)如表所示系別學(xué)生人數(shù)所占比例（%）按比例分配的席位按慣例分配的席位甲10351.510.310乙6331.56.36丙3417.03.44總和200100.020.020第二列所示，按比例分配席位時，出現(xiàn)了小數(shù) （見表中第四列 ）

10、在將取得整數(shù)的19 席分配完畢后，剩下的 1 席按照慣例分給余數(shù)最大的丙系，于是三個系仍分 別占有 10、6、4 個席位因為有 20 個席位的代表會議在表決提案時有可能出現(xiàn) 10：10的平局，會議決定 下一屆增加 1 席，于是他們按照上述慣例重新分配席位，計算的結(jié)果令人吃驚： 總席位增加 1 席，丙系反而減少 1 席，見下表系別學(xué)生人數(shù)所占比例（ %）按比例分配的席位按慣例分配的席位甲10351.510.81511乙6331.56.6157丙3417.03.5703總和200100.021.00021看來，要解決這個矛盾，必須重新研究所謂慣例分配方法，提出更加“公平”的 辦法下面就介紹這樣一個

11、席位分配模型設(shè) A、B 兩方人數(shù)分別是 p1 和 p2，分別占 有 n1 和 n2 個席位，則兩方每個席位所代表的人數(shù)分別是 p1 n12和 p2n2很明顯，僅當(dāng)這兩個 數(shù)值相等時，席位的分配才是公平的但是，通常它們不會相等，這時席位分配 得不公平。不公平的程度可以用數(shù)值 來表示，它衡量的是“絕對不公平” 從 下表所舉的例子來看， A、B之間的“絕對不公平”與 C、D 之間是一樣的。但是 從常識的角度看， A、B之間顯然 比 C、D之間存在著更加嚴重的不公平所以絕對不公平”不是一個好的衡量標準pnp/np1/n1-p2/n2A120101212-10=2B1001010C10201010210

12、2-100=2D100010100為了改進絕對標準，我們自然想到用相對標準因為p n 越大，每個席位代表的人數(shù)越多，或者說，總?cè)藬?shù)一定時分配的席位 越少。所以，如果 p1 n13 >p2/n2，則A方是吃虧的，或者說，對 A是不公平的， 由此，我們這樣定義 “相 對不公平”：若 p1 n1>p2n2，則稱為對 A 的相對不公平值，記做若 p1 n1<p2n2，則稱為對 B 的相對不公平值，記做假設(shè) A、B兩方已分別占有 n1和 n2個席位，我們利用相對不公平的城念來討論， 當(dāng)總席位再增加 1 席時，應(yīng)該給且 A 方還是 B 方?不失一般性，可設(shè) p1n1>p2/n2，即

13、此時對 A 方不公平， ， 有定義當(dāng)再分配 1 個席位時，關(guān)于 pn 的不等式有以下三種可能：1）p1（n1十1）>p2n2，這說明即使 A方增加 1席，仍然對 A不公平，所以這 1 席當(dāng)然應(yīng)給 A 方；2）p1（n1十1）<p2n2，說明當(dāng) A方增加 1席位，將對 B不公平，此時應(yīng)參照 式，計算對 B 的相對不公平值3）說明當(dāng) B方增加 1席時，將對 A 方不公平，此時計算得對 A 的相對不公平值 是（注意：在 p1/n1 p2/n2 的假設(shè)下，不可能出現(xiàn) p1n1<p2 （n2+1）的情況因為 公平的席位分配方法應(yīng)該使得相對不公平的數(shù)值盡量地小，所以如果 則這 1 席應(yīng)給

14、 A方；反之應(yīng)給 B方根據(jù) （3）、（4）兩式， （5）式等價于并且不難 證明 1 從上述第 1）種情況的 p1 （n1 十 1）>p2p2 也可推出。 于是我們的結(jié) 論是：當(dāng) （6）式成立時，增加的 1 席應(yīng)分配 A 方；反之，應(yīng)分配給 B方若記 ，則增加的 1 席位應(yīng)分配給 Q值較大的一方將上述方法可以推廣到有 m 方分配席位的情況 下面用這個方法，重新討論本節(jié)開始時提出的，三個系分配 21 個席位的問題 首先每系分配 1 席，然后計算：甲系 n11，乙系， n2=1，丙系， n3=1，因為 最大，所以第 4 席應(yīng)分配給甲系，繼續(xù)計算：甲系 n12，將 與上面的 相比， 最大，第 5

15、 席應(yīng)分給乙系，繼續(xù)計算。如此繼續(xù)，直到第 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.57189.4（16）8147.3（17）9117.9（19）1096.4（20）1180.4合計11席6席4席可以看出，用Q值法，丙系保住了它險些喪失的 1 席。你覺得這個方法公平嗎？ 習(xí) 題：學(xué)校共 1000名學(xué)生，235入住在 A宿合，333

16、人住在 B宿合，432人住在 C宿合學(xué) 生們要組織一個 10 人的委員會，試用下列辦法分配各宿舍的委員數(shù) 1)慣例的方法，印按比例分配完整數(shù)名額后，剩下名額給余數(shù)最大者。 2)Q值方法。如果委員會從 10 人增至 15 人，分配名額將發(fā)生什么變化 ? ，例 3 狀態(tài)轉(zhuǎn)移問題常染色體遺傳模型 隨著人類的進化， 人們?yōu)榱私沂旧膴W秘， 越來越注重遺傳學(xué)的研究， 特別是 遺傳特征的逐代傳播， 引起人們的注意。 無論是人， 還是動植物都會將本身的特 征遺傳給下一代， 這主要是因為后代繼承了雙親的基因， 形成自己的基因?qū)Γ?基 因?qū)⒋_定后代所表現(xiàn)的特征。 下面， 我們來研究兩種類型的遺傳： 常染色體

17、遺 傳和 x鏈遺傳。根據(jù)親體基因遺傳給后代的方式，建立模型，利用這些模型可 以逐代研究一個總體基因型的分布。在常染色體遺傳中， 后代從每個親體的基因?qū)χ懈骼^承一個基因， 形成自己的基 因?qū)Γ驅(qū)σ卜Q基因型。如果我們所考慮的遺傳特征是有兩個基因 A 和控制的， 那么就有三種基因?qū)?，記?AA，A，。例如，金草魚由兩個遺傳基因決定花的顏 色，基因型是 AA 的金魚草開紅花，型的開粉紅色花，而型的開白花。又如人類 的眼睛的顏色也是提高通過常染色體遺傳控制的?；蛐褪堑娜?，眼睛是棕色， 基因型是的人，眼睛是蘭色。這里因為都表示了同一外部特征，我們認為基因 A 支配基因，也可以認為基因?qū)τ?A 來說是

18、隱性的父體母體的基因型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)過若干年后， 這種植物的任一 代的三種基因型分布如何？第一步：假設(shè)：令 n 0,1,2, 。(1) 設(shè)an , bn和cn分別表示第 n代植物中，基因型為 AA,Aa和 aa的植物占植物總數(shù)的百分率。令 x(n)為第 n 代植物的基因型分布 :(n)an bn cn當(dāng) n=0 時x(0)a0b0c

19、0表示植物基因型的初始分布（即培育開始時的分布） ，顯然有 a 0 b0 c0 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é)合，后代不可能是 AA 型。因此，當(dāng) n 0,1,2, 時 an 1?an 1 bn 1 / 2 0?cn即 a n an 1 bn 1 / 2 類似可推出a n cn 1 bn 1 / 2 c n 0將式相加

20、，得an bn cn a n 1 bn 1 cn 1根據(jù)假設(shè)（ 1），有a n bn c n a 0 b0 c0 1 對于式、式和式，我們采用矩陣形式簡記為 x（n） Mx （n 1）,n 1,2,其中11 / 20anM01 / 21(n)xbn000cn式遞推，得x(n) Mx(n 1) M 2x(n 2)M nx(0)式給出第代基因型的分布與初始分布的關(guān)系。 為了計算出 M n ，我們將 M 對角化，即求出可逆矩陣 M PDP 1因而有M n PD nP 1, n 1,2,其中P 和對角陣 D，使100n1n 0 0Dn0 2 00 n2 00 0 30 0 n3這里 1, 2, 3 是

21、矩陣 M 的三個特征值。對于式中的 征向量 :M，易求得它的特征值和特1 1, 2 1/ 2, 3 01 0 0 11D 0 1/ 2 0 1 0 2 1 因此 0 0 0 , 001 1 1P 1 2 3 0 1 2所以 0 0 1通過計算 P P 1 ，因此有121x( n) Mnx(0) PDnP 1x(0)11101200110x(n)0(12)n20an1bn cn010a0b021 c01 (1/ 2)n(1/ 2)n001 (1/ 2) n 1 a0(1/ 2)n 10b0c0a0 b0 c0 (1/2)nb0 (1/2)n 1c0(1/2)nb0 (1/2)n 1c00所以有a

22、n 1 (1/2)nb0 (1/2)n P11/2c0bn (1/2)nb0 (1/2)n 1c0 c n 0當(dāng) n時(1/ 2) 0 ，所以從式得到an 1,bn 0和 cn=0 即在極限的情況下，培育的植物都是 AA 型。1 1/ 40 1/ 2第三步：模型討論 若在上述問題中，不選用基因 AA 型的植物與每一植物結(jié)合，而是將具有相同基 因型植物相結(jié)合，那么后代具有三代基因型的概率如下表：并且 x(n) M nx(0)，其中0 1/ 4父體母體基因型AA-AAAa-Aaaa-aa后 代 基 因 型AA11/40Aa01/20aa01/41001M 的特征值為 1 1, 2 1, 3 1/

23、2x(n)Mnx(0) PDn P 1x(0)通過計算，可以解出與 1, 2相對應(yīng)的兩個線性無關(guān)的特征向量 1和 2 ，及與 3101102032相對應(yīng)的特征向量 3 ：111101P 1 2 3002因此1111/21 0 1 1 0 0 1 1/2 0 a0002n0 1n0111b011100(1/2)n0 1/2 0c0所以有n1an a0 (1/ 2)b0 (1/2)n 1b0bn (1/2)nb0cn c0 (1/ 2)b0 (1/2)n 1b0當(dāng) n時(1/ 2)0 ，所以從式得到an a0 (1/ 2)b0,bn 0和cn c0 (1/2)b0 因此，如果用基因型相同的植物培育

24、后代，在極限情況下，后代僅具有基因 AA 和 aa。例 4 合作對策模型 在經(jīng)濟或社會活動中，幾個社會實體(個人、公司、黨派、國家)相互合作或結(jié) 成聯(lián)盟，常能獲得比他們單獨行動更多的經(jīng)濟或社會效益。 這樣合理地分配這些 效益是合作對策要研究的問題。請看下面的例子。問題一：經(jīng)商問題 甲、乙、丙三人經(jīng)商，若單干，每人僅能獲利 1元；甲乙合作可獲利 7 元；甲丙 合作可獲利 5元；乙丙合作可獲利 4 元；三人合作可獲利 10 元，問三人合作時 如何分配 10 元的收入。甲的收入應(yīng)按照甲對各種形式的合作的貢獻來確定對于某一合作的貢獻定義 為：有甲參加時這個合作的收入與無甲參加時這個合作的收入之差 例如

25、甲對甲 乙二人合作的貢獻是 71 6 (因為甲乙合作獲利 7 元，而乙單干僅獲利 1 元 )甲可以參加的，合作有四個：甲自己 (單干視為合作的特例 )、甲乙、甲丙、 甲乙丙 甲對這些合作的貢獻分別是甲： 1 一 01 元；甲乙： 716 元； 甲 內(nèi)： 5 1 4 元；甲乙丙： 104 6 元，甲應(yīng)分得的收入是這四個貢獻的 加權(quán)平均值，加權(quán)因子將由下面的一般模型給出這個問題叫做 3 人合作對策，是對策論的一部分，這里介紹它的一種解法。 一般的 n 人合作對策模型可以敘述如下：記 n 人集合為 I=,如果對于 I 中 的任一子集 ，都對應(yīng)一個實值函數(shù) v( s)，滿足則稱為定義在 I上的特征函數(shù)

26、所謂合作對策是指定義了特征函數(shù)的 I中 n個人 的合作結(jié)果， 用向量值函數(shù)來表示在實際問題中?？砂?I 中各種組合的 合作獲得的利益定義為特征函數(shù)， 上式表示合作規(guī)模擴大時， 獲利不會減少。 不難看出，如將三人經(jīng)商問題中合作的獲利定義為特征函數(shù) v，v 是滿足(1)、(2)的 為 了 確 定 ， Shapley 在 1953 年 首 先 制 定 了 一 組 應(yīng)該滿足的公理，然后證明了滿足這組公理的 的唯一解是其中 是 I 中 包含i的所 有子 集， 是集 合 s 中的人數(shù)， 是加權(quán)因子，由確 定 (3) 式 中可看作成員 i對合作 s 的貢獻；表示對所有包含 i的集合求和 稱為由 v 定義的合

27、作的 Shapley值我們用 (3)、(4)計算三人經(jīng)商問題中各個人應(yīng)得到的收入甲、乙、丙分別記作 1，2， 3，包含1的集合有 1、1，2、1，3、1，2， 3，計算結(jié)果列入下表S11,21,31,2,3V(s)17510V(s-1)0114V(s)- V(s-1)16461223W()1/31/61/61/3W()V(s)- V(s-1)1/312/32.同樣可以算出乙、丙應(yīng)得收入為35 元，2.5元。問題二：三城鎮(zhèn)的污水處理方案沿河有三城鎮(zhèn) 1、2和 3，地理位置如圖 4；6所示污水需處理后才能排入河中 三 城鎮(zhèn)或者單獨建立污水處理廠，或者聯(lián)合建廠，用管道將污水集中處理(污水應(yīng)于河流的上

28、游城鎮(zhèn)向下游城鎮(zhèn)輸送 )。以Q表示污水量 (噸秒)，工表示管道長度 (公里)。0.712按照經(jīng) 驗公 式， 建立處理 廠的費用 為 P1 73Q ， 鋪設(shè) 管道 的費 用為數(shù)值 L12 20,L23 38 試從節(jié)約總投資的角度為三城鎮(zhèn)制定污水處理方案； 包 括是單獨還是聯(lián)合建廠；如果聯(lián)合，如何分擔(dān)投資額等 三城鎮(zhèn)或單干或不同形式的聯(lián)合，共有五種方案。下面一一計算所需的投資 方案一 三城鎮(zhèn)都單干。投資分別為總投資：方案二 城 1、2 合作。這時城 1、2 將從節(jié)約投資的角度對聯(lián)合還是分別建廠 作出決策，所以城 1、2 的投資為：=3500C（3）=2300總投資：方案三城 2、3 合作C（1）=

29、2300總投資： 方案四 城 1、3 合作C（2）=1600總投資：方案五三城鎮(zhèn)合作=5560總投資： 比較五個方案可知，應(yīng)該選擇三城合作，聯(lián)合建廠的方案 下面的問題是如何分擔(dān)總額為 5560 的費用城 3 的負責(zé)人提出，聯(lián)合建廠的費用按三城的污水量之比 5 ：3：5 分擔(dān)，鋪設(shè)管 道費應(yīng)由城 1、2擔(dān)負城 2的負責(zé)人同意，并提出從城 2到城 3的管道費由城 1、2按污水量之比 5：3分擔(dān)；從城 1 到城 2的管道費理應(yīng)由城 1自己擔(dān)負城 1的負責(zé)人覺得他們的提議似乎是合理的， 但因事關(guān)重大， 他沒有馬上表示同意； 而是先算了一筆賬聯(lián)合建廠的費用是 73(5 3 5) 4530，城 2 到城

30、3 的管道費是 730，城 1到城 2的管道費是 300，按上述辦法分配時，城 3負擔(dān)的 費用為 1740，城 2的費用為 1320，域 1的費用為 2500結(jié)果出乎意料之外，城 3 和城 2 的費用都比單獨建廠時少， 而城 1 的費用卻比單獨建廠時的 C(1)還要多 . 城 1 的負責(zé)人當(dāng)然不能同意這個方法，但是一時他又找不出公平合理的解決辦 法為了促成聯(lián)合的實現(xiàn)，你能為他們提供一個滿意的分擔(dān)費用的方案嗎 ? 首先，應(yīng)當(dāng)指出，城 3和城 2負責(zé)人提出的辦法是不合理的： 從前面的計算我們 知道，三城聯(lián)合，才能使總投資節(jié)約了 640 的效益應(yīng)該分配給三城， 使三城分配 的費用都比他們單干時要少，

31、 這是為促成聯(lián)合所必須制定的一條原則 至于如何 分配，則是下面要進一步研究的問題把分擔(dān)費用轉(zhuǎn)化為分配效益 ,就不會出現(xiàn)城 1 聯(lián)合建廠分擔(dān)的費用反比單獨建廠 費用高的情況 .將三城鎮(zhèn)記為 I=1,2,3,聯(lián)合建廠比單獨建廠節(jié)約的投資定義為特 征函數(shù) .于是有v( )=0,v(1)=v(2)=v(3)=0,v(1,2)=c(1)+c(2)-c(1,2)=2300+1600-3500=400,v(2,3) =c(2)+c(3)-c(2,3)=1600+2300-3650=250,v(1,3)=0,v(I)=c(1)+c(2)+c(3)-c(1,2,3)=640.S11,21,31,2,3V(s)0

32、4000640V(s-1)000250V(s)- V(s-1)040003901223W( )1/31/61/61/3W()V(s)- V(s-1)0670130即 1(v) 197同理得 2 (v) 321, 3 (v) 122那么, 城 1分擔(dān)的費用為 2300-197=2103, 城 2分擔(dān)的費用為 1600-321=1279, 城 3 分擔(dān)的費用為 2300-122=2178,合計 5560.習(xí)題：某甲(農(nóng)民)有一塊土地。如果從事農(nóng)業(yè)生產(chǎn)可年收入 100 元；如果將土地租給 某企業(yè)家用于工業(yè)生產(chǎn)， 可年收入 200 元；如果租給某旅店老板開發(fā)旅游業(yè)， 可 年收入 300元；當(dāng)旅店老板請

33、企業(yè)家參與經(jīng)營時， 年收入可達 400 元。為實現(xiàn)最 高收入，試問如何分配各人的所得才能達成協(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é)家貝爾曼 (RBellman)等人，提出 了解決多階段決策問題的“最優(yōu)化原理” ，并研究了許多實際問題，從而創(chuàng)建了 動態(tài)規(guī)劃· 動態(tài)規(guī)劃方法的基本思想是： 將一個復(fù)雜問題分解成若干個階段， 每一個階段作 為一個小問

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

35、 階段變量。如例中，可將問題分為 4個階段， k=1,2,3,4.2狀態(tài)和狀態(tài)變量 每一個階段的起點，稱為該階段的狀態(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)的集合為Xk xk(1) ,xk(2), , x(ki), ,xk(T)如例 6中，第 3階段集合可記為X3 x3(1),x3(2), x3(3) C1,C2,C3 1,2,33決策和決策變量 決策就是在某一階段給

36、定初始狀態(tài)的情況下， 從該狀態(tài)演變到下一階段某狀態(tài)的 選擇。即確定系統(tǒng)過程發(fā)展的方案 用一個變量來描述決策， 稱這個變量為決策 變量。設(shè) uk ( xk )表示第 k 個階段初始狀態(tài)為 xk的決策變量 Dk(xk)表示初始狀 態(tài)為 xk 的允許決 策集合，有uk如例 6中D1(A) B1,B2,B3，若先取 B2，則u1( A) B 4策略和子策略由每段的決策 uk ( xk )組成的整個過程的決策變量序列稱為策略，記為 P1,n ，即P1,n=u1(x1),u2(x2), ,un(xn )從階段 k到階段 n 依次進行的階段決策構(gòu)成的決策序列稱為 k子策略，記為 Pk,n 即Pk,n(x1)

37、 =uk(xk),uk 1(xk 1), ,un(xn)顯然， k=1 時的 k 子策略就是策略。如例 6，選取路徑 A B1 C2 D2 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 1適用于動態(tài)規(guī)劃方法求解的是一類具 有無后效性的多階段決策過程 無后效性又稱馬爾科夫性， 指系統(tǒng)從某個階段往 后的發(fā)展， 完全由本階段所處的狀態(tài)以及其往后的決策決定， 與系統(tǒng)以前的狀態(tài) 及決策無關(guān)， 對于具有無后效性的多階段過程，

38、 系統(tǒng)由階段 k 向階段 k+1的狀態(tài) 轉(zhuǎn)移方程為xk 1 Tk ( xk ,uk (xk )意即 xk 1只與 xk,uk(xk) 有關(guān)，而與前面狀態(tài)無關(guān)Tk (xk,uk(xk )稱為變換函數(shù)或算子 分確定型和隨機型， 由此形成確定型動態(tài)規(guī) 劃和隨機型動態(tài)規(guī)劃6指標函數(shù)和最優(yōu)指標函數(shù)在多階段決策中， 可用一個數(shù)量指標來衡量每一個階段決策的效果， 這個數(shù)量指 標就是指標函數(shù)，為該階段狀態(tài)變量及其以后各階段的決策變量的函數(shù)，設(shè)為 Vk ,n 即 Vk,n Vk,n ( xk ,uk , xk 1 , , xn )k 1,2, , n 指標的含義在不同的問題中各不相同，可以是距離、成本、產(chǎn)品產(chǎn)

39、量、資源消 耗等例 6 中，指標的含義就是距離，指標函數(shù)為 A 到 E 的距離，為各階段路程的和 最常見的指標函數(shù)取各階段效果之和的形式，即nVk,nVj (xj,uj)jk指標函數(shù) Vk ,n的最優(yōu)值，稱為相應(yīng)的最優(yōu)指標函數(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)策略” 基 于這個原理，可有如下定理：*定理 若策略 P1,n 是最優(yōu)策略，則對于任意的 k(1<k<n)，它的子策略 Pk,n 對于以xk Tk 1(xk 1,uk 1)為起點的 k到 n 子過程來說，必是最優(yōu)策略 實質(zhì)上，動態(tài)規(guī)劃的方法是從終點逐段向始點方向?qū)ふ易疃搪窂降囊环N方法 8動態(tài)規(guī)劃的數(shù)學(xué)模型利用最優(yōu)化原理，可以得到動態(tài)規(guī)劃的數(shù)學(xué)模型fk (xk) opt Vk ( xk ,uk) fk 1(xk 1)(k n,n 1, ,1uk Dk(xk )fn 1 (x n 1) 0這是一個由后向前的遞推方程下面以例 6