動(dòng)態(tài)規(guī)劃方法建模

1、第七章 動(dòng)態(tài)規(guī)劃方法建模動(dòng)態(tài)規(guī)劃是由理查德·貝爾曼（Richard Bellman）所建立的，它是解最優(yōu)化問(wèn)題的一個(gè)特殊“技術(shù)”.我們這里用“技術(shù)”，是因?yàn)閯?dòng)態(tài)規(guī)劃不是一個(gè)或一種特殊算法.7.1 動(dòng)態(tài)規(guī)劃的基本概念在生產(chǎn)和科學(xué)實(shí)驗(yàn)中，有一類活動(dòng)的過(guò)程，由于它的特殊性，可將過(guò)程分為若干個(gè)互相聯(lián)系的階段，在它的每一個(gè)階段都需要作出決策，從而使整個(gè)過(guò)程達(dá)到最好的活動(dòng)效果.因此，各個(gè)階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展.當(dāng)各個(gè)階段決策確定后，就組成了一個(gè)決策序列，因此也就決定了整個(gè)過(guò)程的一條活動(dòng)路線.這種把一個(gè)問(wèn)題可看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程

2、（如圖7.1）就稱為多階段決策過(guò)程，也稱序貫決策過(guò)程.這種問(wèn)題就稱為多階段決策問(wèn)題.在多階段決策問(wèn)題中，各個(gè)階段采取的決策，一般來(lái)說(shuō)是與時(shí)間有關(guān)的，決策依賴于當(dāng)前的狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，故有“動(dòng)態(tài)”的含義.因此，把處理它的方法稱為動(dòng)態(tài)規(guī)劃方法.但是，一些與時(shí)間沒(méi)有關(guān)系的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃等）問(wèn)題，只要人為地引進(jìn)“時(shí)間”因素，也可把它視為多階段決策問(wèn)題，用動(dòng)態(tài)規(guī)劃方法來(lái)處理.涉及到動(dòng)態(tài)規(guī)劃，總會(huì)有下面幾個(gè)概念： 動(dòng)態(tài)規(guī)劃的基本概念（）階段把所給問(wèn)題的過(guò)程，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段，以便能按一定的次序求解.描述階段的變量稱為階段變

3、量，常用表示.階段的劃分，一般是根據(jù)時(shí)間和空間的自然特征來(lái)劃分，但要便于把問(wèn)題的過(guò)程能轉(zhuǎn)化成為多階段決策的過(guò)程.（）狀態(tài)狀態(tài)表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件，它描述了研究問(wèn)題的狀況，又稱不可控因素.在最短路問(wèn)題中，狀態(tài)就是某階段的出發(fā)位置.它既是該階段某支路的起點(diǎn)，又是前一階段某支路的終點(diǎn).通常一個(gè)階段有若干個(gè)狀態(tài)（一般第一個(gè)階段只有一個(gè)狀態(tài)，它構(gòu)成動(dòng)態(tài)規(guī)劃的遞推方程的出口），每一個(gè)階段的所有狀態(tài)構(gòu)成一個(gè)集合，叫做狀態(tài)集合.用一個(gè)變量來(lái)描述在第個(gè)階段的狀態(tài)集合上的取值，此變量稱為狀態(tài)變量（如7.2節(jié)中最短路問(wèn)題中的，以及后面要介紹的背包問(wèn)題、分割問(wèn)題及設(shè)備更新問(wèn)題中的參數(shù)）.這里所說(shuō)的

4、狀態(tài)是具體的屬于某階段的，它應(yīng)具備下面的性質(zhì)：如果某階段狀態(tài)給定后，則在這階段以后過(guò)程的發(fā)展不受這階段以前各階段狀態(tài)的影響.換句話說(shuō)，過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它未來(lái)的發(fā)展，當(dāng)前的狀態(tài)是以往歷史的總結(jié).這個(gè)性質(zhì)稱為無(wú)后效性，也稱馬爾可夫（Markov）性.如果狀態(tài)僅僅描述過(guò)程的具體特征，則并不是任何實(shí)際過(guò)程都能滿足無(wú)后效性的要求.所以，在構(gòu)造決策過(guò)程的動(dòng)態(tài)規(guī)劃模型時(shí)，不能僅由描述過(guò)程的具體特征這點(diǎn)著眼去規(guī)定狀態(tài)變量，而要充分注意到是否滿足無(wú)后效性的要求.如果狀態(tài)的某種規(guī)定方式可能導(dǎo)致不滿足無(wú)后效性，則應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的規(guī)定方法，達(dá)到能使它滿足無(wú)后效性的要求.（）決策決策表示當(dāng)過(guò)程處

5、于某一階段的某一狀態(tài)時(shí)，可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策.在最優(yōu)控制中也稱為控制（只有它才是我們能夠控制的）.描述決策的變量稱為決策變量.它可以用一個(gè)數(shù)、一組數(shù)或一個(gè)向量來(lái)描述.常用表示第階段當(dāng)狀態(tài)處于時(shí)的決策變量，它是狀態(tài)或狀態(tài)變量的函數(shù)（可能是向量值函數(shù)或多值函數(shù)）.在實(shí)際問(wèn)題中，決策變量的取值往往限制在某一范圍之內(nèi)，此范圍稱為允許決策集合.常用表示第階段當(dāng)狀態(tài)處于出發(fā)的允許決策集合，顯然有.例如，在最短路問(wèn)題中，.（）策略策略是一個(gè)按順序排列的決策組成的集合.由過(guò)程的第階段開(kāi)始到終止?fàn)顟B(tài)為止的過(guò)程，稱為問(wèn)題的后部子過(guò)程.由每段的決策按順序排列組成的決

6、策函數(shù)序列稱為子策略，記為當(dāng)時(shí)，此決策函數(shù)序列即為一個(gè)策略.在實(shí)際問(wèn)題中，可供選擇的策略有一定的范圍，此范圍稱為允許策略集合.從允許策略集合中找到達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略.（）狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程式確定過(guò)程有一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程.若給定第階段狀態(tài)和該階段的決策變量，則第階段的狀態(tài)也就完全確定.即的值隨和的值變化而變化.這種確定的對(duì)應(yīng)關(guān)系，記為，它描述了由第階段到第階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程.稱為狀態(tài)轉(zhuǎn)移函數(shù).例如，在最短路問(wèn)題中，狀態(tài)轉(zhuǎn)移方程為.（）指標(biāo)函數(shù)和最優(yōu)值函數(shù)用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的數(shù)量指標(biāo)，稱為指標(biāo)函數(shù).它是定義在全過(guò)程和所有后部子過(guò)程上確定的函數(shù).對(duì)

7、于要構(gòu)成動(dòng)態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分性，并滿足遞推關(guān)系（詳見(jiàn)文獻(xiàn)），在實(shí)際問(wèn)題中，很多指標(biāo)函數(shù)都滿足此性質(zhì).指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù).根據(jù)問(wèn)題，取min或max之一.在動(dòng)態(tài)規(guī)劃模型中，總會(huì)出現(xiàn)一個(gè)或一組遞推關(guān)系，我們把它稱為動(dòng)態(tài)規(guī)劃的基本方程. 動(dòng)態(tài)規(guī)劃方法的基本思想現(xiàn)將動(dòng)態(tài)規(guī)劃方法的基本思想歸納如下：一、動(dòng)態(tài)規(guī)劃方法的關(guān)鍵在于正確寫(xiě)出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件（基本方程）.要做到這一點(diǎn)，必須先將問(wèn)題的整個(gè)過(guò)程分成幾個(gè)相互聯(lián)系的階段，恰當(dāng)?shù)剡x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個(gè)大問(wèn)題化成一族同類型的子問(wèn)題，然后逐個(gè)求解.即從邊界條件開(kāi)始，逐段遞推尋優(yōu)，在每一個(gè)子

8、問(wèn)題的求解中，均利用了它前面的子問(wèn)題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個(gè)子問(wèn)題所得的最優(yōu)解，就是整個(gè)問(wèn)題的最優(yōu)解.二、在多階段決策過(guò)程中，動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段和未來(lái)各段分開(kāi)，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法.因此，每段決策的選取是從全局來(lái)考慮的，與該段的最優(yōu)選擇答案一般是不同的.三、在求整個(gè)問(wèn)題的最優(yōu)策略時(shí)，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過(guò)的各段狀態(tài)便可逐次變換得到，從而確定了最優(yōu)策略.動(dòng)態(tài)規(guī)劃的理論基礎(chǔ)叫做動(dòng)態(tài)規(guī)劃的最優(yōu)化原理，它是這樣描述的：作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：即無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)前面決策所形成的狀態(tài)而言

9、，余下的諸決策必須構(gòu)成最優(yōu)策略.簡(jiǎn)言之，一個(gè)最優(yōu)策略的子策略總是最優(yōu)的.動(dòng)態(tài)規(guī)劃的優(yōu)劣：優(yōu)點(diǎn)：（1）易于確定全局最優(yōu)解.因?yàn)樗蠼獾娜且痪S問(wèn)題，所以容易確定.（2）能得到一族（全部的）最優(yōu)解，有利于分析結(jié)果.（3）能利用經(jīng)驗(yàn)，提高求解效率.缺點(diǎn)：（1）到目前為止，沒(méi)有一個(gè)統(tǒng)一的標(biāo)準(zhǔn)模型可供應(yīng)用.由于問(wèn)題的不同，有時(shí)要將問(wèn)題轉(zhuǎn)化成滿足條件（無(wú)后效性、目標(biāo)函數(shù)的可分性）的多階段決策過(guò)程是非常困難的，需要豐富的想象力和靈活的技巧.（2）應(yīng)用的局限性.“無(wú)后效性”條件的限制，降低了動(dòng)態(tài)規(guī)劃的通用性.（3）在數(shù)值計(jì)算時(shí)，存在所謂的“維數(shù)災(zāi)難”.當(dāng)階段數(shù)目較多且每一階段的允許狀態(tài)也較多時(shí)，計(jì)算成本變得非

10、常昂貴，有時(shí)使得計(jì)算不可能進(jìn)行下去.在二維或三維動(dòng)態(tài)規(guī)劃中，問(wèn)題顯得更加突出.7.2 最短路問(wèn)題問(wèn)題：某人想進(jìn)行一次旅行.他住在城市1，而希望到達(dá)城市10，見(jiàn)圖7.2.這是一次長(zhǎng)途的旅行，而且他還必須進(jìn)行三次中間停留.對(duì)他旅行中的三個(gè)中間停留站的每一站，都有兩到三個(gè)不同的城市可供他選擇.選擇不同的中間站，旅行的花費(fèi)是不同的.兩城市之間的花費(fèi)以及連接示于圖7.2中.由于他希望為這次旅行付出的總花費(fèi)達(dá)到最小，他將確定哪些城市作為他的中間站，顯然，它可以用枚舉法來(lái)解決此問(wèn)題，總的可能的路線有18條（3×3×218）.但問(wèn)題肯定有更好的解法，下面我們用更好的方法來(lái)解決此問(wèn)題.我們從

11、終點(diǎn)（城市10）逆序來(lái)分析這個(gè)問(wèn)題.第一步：若我們處在第3站，可通過(guò)城市8或城市9到達(dá)城市10.可用表（1）說(shuō)明： 表（1）城市最小花費(fèi)路徑第3站89380280810910第二步：現(xiàn)在假設(shè)在第2站，并問(wèn)哪一條是到達(dá)城市10且花費(fèi)最小的路徑.若在城市5，最小花費(fèi)是510，即（210380，230280）中的最小值，將選用路徑5910.同理，若在城市6，最小花費(fèi)是660，即（350380，380280）中的最小值，將選擇路徑6910.此結(jié)果列于表（2）中.表（2）城市最小花費(fèi)路徑第2站567510660670591069107810第三步：假定處在第1站.用類似于第2站的分析方法進(jìn)行分析，例如，

12、由城市2到達(dá)城市10的最小花費(fèi)是830min（320510，350660，400670）括號(hào)中和式的第一項(xiàng)是由城市2到城市5、6、7的花費(fèi)，第二項(xiàng)是城市5、6、7到城市10的最小花費(fèi)，它可由表31（2）查到，最小花費(fèi)路徑是25910.第1站的所有計(jì)算結(jié)果有表（3）給出.表（3）城市最小花費(fèi)路徑第1站234830860810259103591045910第四步：假設(shè)處在城市1，這是起點(diǎn).必須由城市1到城市2、3、4中的一個(gè).最小花費(fèi)的路徑是那一條呢？應(yīng)用表（3）的結(jié)果和由城市1到城市2、3、4的花費(fèi)，則可計(jì)算出全旅程的最小花費(fèi)為： min（300830，200860，350810）min（113

13、0，1060，1160）1060最小花費(fèi)路徑是：135910.上面的解決非常簡(jiǎn)單.它是基于這樣的思考：不論現(xiàn)在處于那一個(gè)城市，從最后一個(gè)城市開(kāi)始，將總是選擇最優(yōu)（最小花費(fèi)）的路徑.若在城市10（第4站），就留在那里.若在城市5（第3站），則從城市8或9到達(dá)城市10.如此繼續(xù)下去，直到發(fā)現(xiàn)自己在城市1（第0站），并且順序地找到了最小花費(fèi)的解，以及實(shí)現(xiàn)最小花費(fèi)的路徑.應(yīng)當(dāng)注意，即使沒(méi)有達(dá)到第0站，最優(yōu)解將是什么樣，也是清楚的.我們注意到，在第1站，最小費(fèi)用將是由城市3到城市10的最小費(fèi)用加上200.另外，如果他改變了他的愿望，并決定從任何其它城市起始，我們也知道最優(yōu)解是什么.上面的解法雖然簡(jiǎn)單，但

14、它卻富有啟發(fā)性.一方面，在計(jì)算過(guò)程中，我們使用了已經(jīng)計(jì)算出的數(shù)據(jù)，這大大的節(jié)約了計(jì)算成本；另一方面，我們得到了比我們預(yù)期多得多的信息，我們不僅僅解得了從城市1（起點(diǎn)）到城市10的最小費(fèi)用路徑，而且還得到了其它任何一個(gè)城市到達(dá)城市10的最小費(fèi)用路徑.顯然，如果在原問(wèn)題的旅行圖前又增添了一些新的城市，我們已經(jīng)計(jì)算出的數(shù)據(jù)仍然可以利用，并且進(jìn)一步的計(jì)算不會(huì)比上面的計(jì)算更復(fù)雜.下面我們將上面的解法步驟用符號(hào)表示，以期望得到更一般的形式.用符號(hào)()表示10個(gè)城市.表示城市到城市的距離.如果城市到城市必須經(jīng)過(guò)其它城市，則.于是所有數(shù)據(jù)構(gòu)成一個(gè)矩陣，即為用表示第站所有城市構(gòu)成的集合.即，.用表示從第站的城市

15、到目的地的最小費(fèi)用值.于是上面的解題過(guò)程可由下面的遞推公式完成： (7.2.1)當(dāng)然，在每步極小化時(shí)，應(yīng)記住極小值點(diǎn)，這樣才能確定最小費(fèi)用路徑.顯然，根據(jù)對(duì)稱性，你還可以使用“順推法”.與之對(duì)應(yīng)，上面的過(guò)程稱為“逆推法”.7.3 背包問(wèn)題問(wèn)題：有人在某地旅游結(jié)束后，決定購(gòu)買一些“特產(chǎn)”，打算帶回家，再賣給他的一些同事，指望得到一筆誠(chéng)實(shí)無(wú)欺的利潤(rùn).他知道在他的行李中最多只能帶20，才不會(huì)超重.他可以購(gòu)買四種不同類型的特產(chǎn)，其特征如見(jiàn)表.表項(xiàng)目重量（）估計(jì)利潤(rùn)（元）12342354110160260210由于這些項(xiàng)目不可能分割包裝，這就限制了只能取其整數(shù)倍.根據(jù)第六章，此問(wèn)題可以用整數(shù)線性規(guī)劃來(lái)描

16、述.設(shè)，表示準(zhǔn)備帶回家的各種特產(chǎn)的數(shù)量，則問(wèn)題變?yōu)榍蠼?() ()下面我們將用動(dòng)態(tài)規(guī)劃技術(shù)來(lái)解此問(wèn)題.假設(shè)已知的最優(yōu)值，記為.若是這種情況，我們只需要解一個(gè)單變量問(wèn)題，將代入式(7.3.1)(7.3.2)中，可得 ()約束為 ()為整數(shù) ()由于是一個(gè)常數(shù)（若已知的值），則目標(biāo)函數(shù)式(7.3.3)僅僅是 ()自然，是未知的.但是，我們知道必須滿足203 ()否則的話，問(wèn)題式(7.3.3)-(7.3.5)是無(wú)解的.若我們規(guī)定一個(gè)新的變量，通常稱為狀態(tài)變量，則可將式(7.3.4)寫(xiě)成為 ()其中，可為，20中任何一個(gè)值，因?yàn)樵谶@里實(shí)際上 是未知的.現(xiàn)在來(lái)解由式(7.3.6)和式(7.3.8)給出的

17、一維問(wèn)題，即 （）約束為 ()對(duì)于每一個(gè)值，此問(wèn)題是易于求解的.例如：得出得出若定義 ()則給出的最大值，并且是給出極大值的的值.和二者為的函數(shù)，因此極大化將限制在的某些特定值上.若對(duì)全部的求解(7.3.9)，可得表（1）：表（1）012345600110110220220330001122378910111213330440440550550660660344556614151617181920770770880880990990110077889910考慮到，現(xiàn)在已經(jīng)知道滿足原問(wèn)題(7.3.1)-(7.3.2)的約束的最優(yōu)值是怎樣地取決于，以及怎樣地取決于原問(wèn)題的任一可能的限制.現(xiàn)在來(lái)考慮

18、下述問(wèn)題： (7.3.12)約束為 (7.3.13)為什么要考慮式(7.3.12)和(7.3.13)形式的最優(yōu)化問(wèn)題呢？首先我們注意到，這個(gè)問(wèn)題的所有可行解，也是原問(wèn)題的可行解.其次，若固定于某些值上，則問(wèn)題是單變量問(wèn)題，這可從下面的一些論述看出.利用定義式(7.3.11)可看出，在式(7.3.12)中是.所以，式(7.3.12)可寫(xiě)為 (7.3.14)注意，對(duì)于固定的，式(7.3.14)是一個(gè)單變量最優(yōu)化問(wèn)題.然而，式(7.3.14)不是完全的.由式(7.3.13)和的非負(fù)性，可看出，所以有 (7.3.15)其中，.于是可將式(7.3.14)寫(xiě)為 (7.3.16)其中.式(7.3.16)是相

19、當(dāng)重要的.首先，它是一個(gè)單變量最優(yōu)化問(wèn)題，易于求解；而且對(duì)于全部可能的值，在表（1）中已經(jīng)給出，求只需查表（1）就行.這樣，利用式(7.3.16)和表（1）可計(jì)算出的值.結(jié)果見(jiàn)表（2）中.表（）012345600110160220270330000101078910111213380440490550600660710101010114151617181920770820880930990104011000101010同理，下面我們來(lái)考慮問(wèn)題 (7.3.17)約束為 (7.3.18)此外，若用式(7.3.12)給出的，式(7.3.17)可寫(xiě)為 (7.3.19)并且，由于，可獲得類似于式(7.3

20、.16)的形式，即 (7.3.20)其中.現(xiàn)在可以用式(7.3.20)和表（2）可求出的值.見(jiàn)表（3）：表（3）012345600110160220270330000000078910111213380440490550600660710000000014151617181920770820880930990104011000000000最后，我們來(lái)考察如下問(wèn)題： (7.3.21)其中極大化是從0到之間的整數(shù)上考慮的.回到原問(wèn)題，因?yàn)橐馕吨试S攜帶物品的總重量，故此時(shí)只須求時(shí)的值，即利用表（2）的值，可知道.此時(shí)，.我們已經(jīng)得到了最優(yōu)值以及，注意到，從表（3）可知道，而且.同理，表（2）告訴和

21、.最后，在表（1）中得到.于是原問(wèn)題的解為：， ，.在這個(gè)例子中，我們的解題方法有類似于上一節(jié)最短路問(wèn)題求解的特征：(1)用解四個(gè)單變量的最優(yōu)化問(wèn)題，代替解一個(gè)四變量的最優(yōu)化問(wèn)題.(2)就象最短路問(wèn)題一樣，我們先來(lái)處理一個(gè)變量（最短路問(wèn)題中，先考慮最后1站），接著是兩個(gè)變量，直到最后我們才處理了全部變量.(3)盡管我們感興趣的是的情形，但是除了最后一步僅是對(duì)求解外，我們對(duì)的全部可能的整數(shù)值（），求解了問(wèn)題.如果用和分別表示第種物品的重量和獲利（）.表示剩余下的用于攜帶物品的重量.表示用于攜帶物品的重量為時(shí)帶第種物品的最大利潤(rùn).則有下面的遞推方程可表示上面的解題過(guò)程： (7.3.22)用此方法解

22、題，可以節(jié)約計(jì)算.7.4 分割問(wèn)題問(wèn)題：給定一個(gè)正數(shù)，將其分成個(gè)部分，使這部分的乘積最大.下面我們用動(dòng)態(tài)規(guī)劃的方法來(lái)解決這個(gè)問(wèn)題.注意到是未指定的.首先我們令 即表示任何一個(gè)正數(shù)分成部分，它們乘積的最大值.乘積的最大值可這樣分解：它的第1部分為，且剩余的為分成部分時(shí)乘積的最大值.第一步：考慮的情形（最簡(jiǎn)單的情形）.對(duì)于這個(gè)問(wèn)題，即任何一個(gè)正數(shù)分成部分，顯然乘積的最大值為.因此，我們定義 (7.4.1)第二步：考慮的情形.即將數(shù)分成乘積最大的部分.設(shè)其中的一部分為，則另一部分為，于是 (7.4.2)利用式(7.4.1)上式也可寫(xiě)成這是一個(gè)含參數(shù)的單變量最大化問(wèn)題，可用數(shù)學(xué)分析的方法求最大化.對(duì)右

23、端函數(shù)的變量求導(dǎo)數(shù)并令其導(dǎo)數(shù)等于，就得到時(shí)有最大值.因此我們求得了的顯式表達(dá)式：且其第部分為. (7.4.3)第三步：考慮的情形.即將數(shù)分成乘積最大的部分.設(shè)其中的一部分為，則剩余部分的和為，于是 (7.4.4)利用式(7.4.1)上式也可寫(xiě)成這是一個(gè)含參數(shù)的單變量最大化問(wèn)題，可用數(shù)學(xué)分析的方法求最大化.對(duì)右端函數(shù)的變量求導(dǎo)數(shù)并令其導(dǎo)數(shù)等于就得到時(shí)有最大值.因此我們求得了的顯式表達(dá)式：且其第部分為. (7.4.5)第四步：根據(jù)(7.4.1)(7.4.3)(7.4.5)，現(xiàn)在我們猜測(cè)且其第部分為. (7.4.6)下面用歸納法來(lái)證明.事實(shí)上，的情形已經(jīng)證明.假設(shè)時(shí)(7.4.6)成立.第五步：當(dāng)時(shí)，

24、因?yàn)?(7.4.7)利用假設(shè)，則這仍然是一個(gè)單變量的最優(yōu)化問(wèn)題.利用數(shù)學(xué)分析的知識(shí)可求得且其第部分為.這樣就完成了歸納法的證明.最后：將代入式(7.4.6)，我們得到正數(shù)分割成部分時(shí)最大乘積為且分割的第一部分為，剩余部分為，將此部分分割成份，使得乘積最大的分割中第一部分為，又剩余了，再將此部分分割成份，依次下去，我們會(huì)得到每一部分都是.于是，原問(wèn)題就解決了.答案是：給定一個(gè)正數(shù)，將其等分成個(gè)部分，這樣部分的乘積最大.我們?nèi)匀粚⑸厦娴挠?jì)算方法歸結(jié)為下面的遞推方程： (7.4.8)值的注意的是，我們的方法當(dāng)問(wèn)題改變?yōu)槿缦聲r(shí)仍然有效：將一個(gè)正整數(shù)分割成（）個(gè)正整數(shù)使其乘積最大.但在每一步求解最優(yōu)化時(shí)

25、不能使用經(jīng)典方法.建議讀者動(dòng)手做做.7.5 簡(jiǎn)單的設(shè)備更新問(wèn)題一部用于化學(xué)處理的設(shè)備，特別易于遭到腐蝕的損壞，致使影響生產(chǎn)效率.設(shè)當(dāng)用了年后，從運(yùn)轉(zhuǎn)中得到的凈收入（扣除運(yùn)轉(zhuǎn)費(fèi)用后），可用下式給出 (7.5.1)由式(7.5.1)可看出，這部設(shè)備在使用一定年限后應(yīng)該淘汰.更新的價(jià)值為22，并且當(dāng)它被更換后，它又有了五年的生產(chǎn)壽命.經(jīng)常保持有一部已用了一年的設(shè)備在運(yùn)轉(zhuǎn).若每年做一次決策，繼續(xù)保持這部設(shè)備或更換它，那么采用什么策略會(huì)使一個(gè)規(guī)劃期限內(nèi)（五年）的總贏利為最大？由于式子(7.5.1)給出了凈收入，可看出，年贏利是收入與花費(fèi)之差（即扣除運(yùn)轉(zhuǎn)費(fèi)用）.由此，若保持這部現(xiàn)用設(shè)備，則贏利為 (7.5

26、.2)而更換這部設(shè)備，贏利為 (7.5.3)由于這部設(shè)備已沒(méi)有挽救的價(jià)值，所以從新設(shè)備中的凈贏利不取決于所更新設(shè)備的使用年限.所以為從新設(shè)備中第一年的贏利.現(xiàn)在讓我們把問(wèn)題公式化.我們希望求出五個(gè)逐年決策的序列，即，保持或更換，使從五年運(yùn)轉(zhuǎn)中的贏利為最大.所以希望 (7.5.4)其中，由式(7.5.2)或式(7.5.3)給出，哪一個(gè)由作出的決策來(lái)定.現(xiàn)在讓我們來(lái)處理這個(gè)多級(jí)最佳化問(wèn)題.若倒過(guò)來(lái)排各級(jí)的序號(hào)，則分析起來(lái)將方便些，即，第一級(jí)表示還剩下一年，因此從第五級(jí)開(kāi)始.圖7.3上表示了我們將采用的符號(hào)，對(duì)于時(shí)間，將做出保持或更換的決策.若決策保持這個(gè)設(shè)備，可看出可由下式給出 (7.5.5) 若

27、更換這個(gè)設(shè)備，則.圖7.4更詳細(xì)地解釋了上述記號(hào)與約定.現(xiàn)在假設(shè)剩下的運(yùn)轉(zhuǎn)時(shí)間為一年（最后一級(jí)）.定義當(dāng)設(shè)備使用了年時(shí)，進(jìn)入最后一個(gè)運(yùn)轉(zhuǎn)年，采取或時(shí)獲得的最大贏利.那么，很清楚有 (7.5.6)用式(7.5.6)的采樣計(jì)算如下：表中第一欄包含了，當(dāng)設(shè)備還剩一年運(yùn)轉(zhuǎn)時(shí)間時(shí)，對(duì)不同使用期的設(shè)備全部計(jì)算.表設(shè)備役令剩下的運(yùn)轉(zhuǎn)年限23.543.559719122035.547.5(或)67.583315.527.547.563（或）78.541027.547.563755427.547.563756427.547.56375現(xiàn)在我們需要對(duì)還剩下兩年或更多年運(yùn)轉(zhuǎn)期的設(shè)備，發(fā)展一種計(jì)算最大贏利的一般方法.

28、定義具有役令的設(shè)備進(jìn)入第運(yùn)轉(zhuǎn)年時(shí)采用或R的最大贏利.可由定義很清楚地給出 (7.5.7)應(yīng)用最佳化原理、定義和式(7.5.7),可得 (7.5.8)現(xiàn)在用式(7.5.8)計(jì)算.由式(7.5.5)知.一些采樣計(jì)算為 我們前面已經(jīng)計(jì)算了.由此得 同理 剩余的計(jì)算結(jié)果列表于的各欄中. 現(xiàn)在我們能夠回答原始的問(wèn)題了.若目前有一運(yùn)轉(zhuǎn)了一年的設(shè)備，查表7中行的第五欄，由此可計(jì)算最佳的五年策略.可看出，最大的贏利為91，并保持這個(gè)設(shè)備一年.現(xiàn)在移到第四欄的第二行，應(yīng)為現(xiàn)在設(shè)備已用了兩年.可看出，最佳的策 仍是保持設(shè)備.現(xiàn)在移到第三欄第三行，則必需更換設(shè)備.若這樣做，則移到了第二欄第一行.繼續(xù)保持設(shè)備，并移到

29、第一欄第二行.這條路徑已描繪在表中.可看出，最佳策略是.這就是說(shuō)，在運(yùn)轉(zhuǎn)的前兩年我們保持設(shè)備，在第三年更換，然后繼續(xù)保持兩年.最大的贏利將為91.當(dāng)然，我們可以用這個(gè)算出來(lái)的表，來(lái)回答可能提出的其它問(wèn)題.例如，假設(shè)我們希望在下一個(gè)五年里獲得最大的贏利，起始點(diǎn)是使用了兩年的設(shè)備.對(duì)于這種情況，存在有兩種最佳的策略，得出相同的贏利為83.這些最佳策略是 或讀者可通過(guò)表74繪出這些路徑.當(dāng)這兩種策略得到相同的總贏利83時(shí)，若一個(gè)是考慮到在五年周期中的前兩年產(chǎn)生43.5的贏利，另一個(gè)在前兩年中只產(chǎn)生35.5，如果企求獲得較多贏利越早越好（實(shí)際上常是這樣），則第一個(gè)策略比第二個(gè)更好. 練習(xí)用動(dòng)態(tài)規(guī)劃解下

30、面問(wèn)題：（）（）（）（）某工業(yè)部門(mén)根據(jù)國(guó)家計(jì)劃的安排，擬將某種高效率的設(shè)備五臺(tái)，分配給所屬的甲、乙、丙三個(gè)工廠，各工廠若獲得這種設(shè)備之后，可為國(guó)家提供的盈利如表所示.問(wèn)：這五臺(tái)設(shè)備如何分配給各工廠，才能使國(guó)家得到的盈利最大.表工廠設(shè)備臺(tái)數(shù)甲乙丙某工廠要對(duì)一種產(chǎn)品制訂今后四個(gè)時(shí)期的生產(chǎn)計(jì)劃，據(jù)估計(jì)在今后四個(gè)時(shí)期內(nèi)，市場(chǎng)對(duì)于該產(chǎn)品的需求量如表所示.表時(shí)期需求量假定該廠生產(chǎn)每批產(chǎn)品的固定成本為千元，若不生產(chǎn)就為；每單位產(chǎn)品成本為千元；每個(gè)時(shí)期生產(chǎn)能力所允許的最大生產(chǎn)批量不超過(guò)個(gè)單位；每個(gè)時(shí)期末未售出的產(chǎn)品，每單位需付存儲(chǔ)費(fèi).5千元.還假定在第一個(gè)時(shí)期的初始庫(kù)存為，第四個(gè)時(shí)期末的庫(kù)存量也為.試問(wèn)該廠應(yīng)

31、如何安排各個(gè)時(shí)期的生產(chǎn)與庫(kù)存，才能在滿足市場(chǎng)需求的條件下，使總成本最小.閱讀材料渡河問(wèn)題 人、狼、雞、米渡河問(wèn)題：人、狼、雞、米各一均要過(guò)河，船一只.船需要人劃，另外至多還能載一物，而當(dāng)人不在時(shí)，狼要吃雞，雞要吃米.問(wèn)人、狼、雞、米怎樣過(guò)河才能無(wú)一損失？這是一個(gè)有趣的數(shù)學(xué)游戲，問(wèn)題比較簡(jiǎn)單，可用遞推方法解決.但我們并不想這樣做，我們希望更有意義的解決方案.解法一：因?yàn)閱?wèn)題中出現(xiàn)了四種不同的元素，故我們期望用四維向量表示它們，即 （Man, Wolf, Cock, Rice）又因?yàn)楫?dāng)河的一岸上的情形已知時(shí)，另一岸上的情形必然已知.故可用1或0表示是否在該岸上，具體如下：左岸右岸（1，1，1，1）

32、 （0，0，0，0）（1，1，1，0）（0，0，0，1）（1，1，0，0）×（0，0，1，1）×（1，0，0，0）×（0，1，1，1）×（1，0，1，0）（0，1，0，1）（1，0，0，1）×（0，1，1，0）×（1，0，1，1）（0，1，0，0）（1，1，0，1）（0，0，1，0）表中列出了所有可能的16種狀態(tài)，當(dāng)然，根據(jù)對(duì)稱性，河的一岸還會(huì)出現(xiàn)另一岸的8種情形.這種向量的表示意義也很明確，如（1，0，1，1）表示人、雞、米在該處，而狼在另一處，等等.根據(jù)題意，有些狀態(tài)是不能允許的，就是表中用×標(biāo)記的6種，因?yàn)檫@6種狀態(tài)中

33、會(huì)出現(xiàn)河的一岸一物被另一物所吃的情況.剩下的10種狀態(tài)我們用標(biāo)記出，這些都是系統(tǒng)允許出現(xiàn)的，所以我們稱為可取狀態(tài).接下來(lái)的問(wèn)題是如何表示船的一次運(yùn)載.船上的狀態(tài)也可以用前面的四維向量表示，例如，船上裝有人（人必須在船上）和雞表示為（1，0，1，0）.因?yàn)椤按枰藙?，另外至多還能載一物”，故船上只有4種可能狀態(tài)：（1，0，0，0），（1，1，0， 0），（1，0，1，0），（1，0，0，1）.我們?cè)谶@四個(gè)向量前面加上表示第次渡河.這樣我們可以通過(guò)加法運(yùn)算來(lái)表示船的一次運(yùn)載.例如：在狀態(tài)（1，0，1，1）之下船運(yùn)載了米，即 （1，0，1，1）（1，0，0，1）（0，0，1，0）.自然，由于問(wèn)題的

34、要求，運(yùn)算的結(jié)果狀態(tài)必須是可取狀態(tài).在上面的處理下，問(wèn)題有了如下的的提法：尋求一種齊數(shù)步的系統(tǒng)狀態(tài)轉(zhuǎn)移過(guò)程，使系統(tǒng)從初始狀態(tài)（1，1，1，1）變換到狀態(tài)（0，0，0，0）.如果沒(méi)有這樣的轉(zhuǎn)移過(guò)程，或所有狀態(tài)轉(zhuǎn)移過(guò)程陷入循環(huán)狀態(tài)，則問(wèn)題無(wú)解.具體解答過(guò)程為： 上面過(guò)程中標(biāo)記“×”的為不允許狀態(tài)（或不可取狀態(tài)），標(biāo)記“××”的為不可能狀態(tài)，標(biāo)記“×！”的為雖然是可取狀態(tài)但產(chǎn)生了循環(huán)的情形.從上面的過(guò)程看出，經(jīng)過(guò)7次狀態(tài)轉(zhuǎn)移，就能使?fàn)顟B(tài)從初始狀態(tài)（1，1，1，1）變?yōu)椋?，0，0，0），所以經(jīng)過(guò)7次渡河就能全部安全過(guò)河.解法二：此問(wèn)題可用圖解法求解.將10個(gè)可取狀態(tài)用10個(gè)點(diǎn)來(lái)表示，如果某一個(gè)可取狀態(tài)可轉(zhuǎn)移到達(dá)另一可取狀態(tài)，則用一條邊