第五章 動(dòng)態(tài)規(guī)劃 山大刁在筠 運(yùn)籌學(xué)講義

第五章動(dòng)態(tài)規(guī)劃教學(xué)重點(diǎn)：用遞推的方法求解最短路線問題，有限資源分配問題，旅行售貨員問題，最優(yōu)線路問題等。教學(xué)難點(diǎn)：有限資源分配問題。教學(xué)課時(shí)：10學(xué)時(shí)主要教學(xué)環(huán)節(jié)的組織：將最優(yōu)化原理應(yīng)用于幾種典型多階段問題當(dāng)中，結(jié)合實(shí)例給學(xué)生以具體的認(rèn)識(shí)，通過習(xí)題加以鞏固。第一節(jié)多階段決策問題教學(xué)重點(diǎn)：通過具體實(shí)例得多階段決策問題的模型，討論多階段決策問題的解決方法。教學(xué)難點(diǎn)：多階段決策問題的解法。教學(xué)課時(shí)：1學(xué)時(shí)主要教學(xué)環(huán)節(jié)的組織：給出具體的多階段決策問題，討論多階段決策問題的算法—遞推法。實(shí)例最短路問題---例1最短路問題就是從某地出發(fā)，途經(jīng)若干中間點(diǎn)最后到達(dá)目的地，要求找出路程或費(fèi)用最小的路線。一般的最短路問題將在下一章討論，這里只討論分層的最短路問題。下面的管道設(shè)計(jì)問題(例5.1.1)就是其中之一。5542634656122233234ED3D1D2C1C3C2AB3B2B1從A點(diǎn)到E點(diǎn)要鋪設(shè)一條煤氣管道，中間必須經(jīng)過三個(gè)中間站，第一站可在B1、B2、B3中選擇，第二站可在C1、C2、C3中選擇，第三站可在D1、D2、D3中選擇，要求選擇一條由A到E的鋪管路線，使總長度最短。其中兩點(diǎn)連線上的數(shù)字表示兩點(diǎn)間管線的長度。從A點(diǎn)到E點(diǎn)鋪設(shè)管道，可以按其地理特點(diǎn)自然地分成四個(gè)階段：（如下圖所示）從A到B是第一階段，從B到C是第二階段，從C到D是第三階段，從D到E是第四階段。AABCDE階段1階段2階段3階段4在階段2，從B3點(diǎn)出發(fā)，只有C1、C3兩種可選擇的點(diǎn)，如選C1,則C1就是階段2在B3點(diǎn)的決策結(jié)果；C1點(diǎn)既是階段2鋪設(shè)管道的終點(diǎn)，又是階段3鋪設(shè)管道的起點(diǎn)；同樣的理由，可以遞推得其余階段的鋪設(shè)路線，如階段3在C1點(diǎn)的決策是D1，階段4在D1點(diǎn)的決策只有E點(diǎn)；由于到E點(diǎn)是整個(gè)鋪設(shè)管道的終點(diǎn)，至此，決策過程完成，鋪設(shè)一條A點(diǎn)到E點(diǎn)的管道是由四個(gè)階段的管道組成的，如A---B3---C1---D1---E，它也稱為一個(gè)策略。可以看出，各個(gè)階段的決策不同，鋪設(shè)的管道也不同，并且當(dāng)某個(gè)階段的始點(diǎn)給定后，它直接影響著后面各階段的行進(jìn)路線和管道的長短，而后面各階段的路線的選取不受這點(diǎn)以前各階段路線的影響。因此，最短路線問題可簡化為四個(gè)階段決策問題，使由這四個(gè)階段決策組成決策序列，也稱為策略所決定的一條路線的總長度最短。例2資源分配問題（略）例3生產(chǎn)-庫存問題（略）一般多階段決策問題有一個(gè)系統(tǒng)，可以分成若干個(gè)階段，任意一個(gè)階段，系統(tǒng)的狀態(tài)可以用表示（可以是數(shù)量、向量、集合等）。在每一階段的每一狀態(tài)都有一個(gè)決策集合，在中選定一個(gè)決策，狀態(tài)就轉(zhuǎn)移到新的狀態(tài)，并且得到效益。我們的目的就是在每一個(gè)階段都在它的決策集合中選擇一個(gè)決策，使所有階段的總效益達(dá)到最大。我們稱之為多階段決策問題。多階段決策問題的基本要素：階段數(shù)、狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移方程和目標(biāo)函數(shù)。多階段決策問題的分類階段數(shù)：有限階段決策問題和無限階段決策問題；狀態(tài)變量：連續(xù)多階段決策問題和離散多有限階段決策問題；階段個(gè)數(shù)是否明確：定期多階段決策問題和不定期多階段決策問題；參數(shù)取值情況：確定多階段決策問題和不確定多階段決策問題。第二節(jié)最優(yōu)化原理教學(xué)重點(diǎn)：最優(yōu)化原理。教學(xué)難點(diǎn)：無。教學(xué)課時(shí)：1學(xué)時(shí)主要教學(xué)環(huán)節(jié)的組織：介紹最優(yōu)化原理。動(dòng)態(tài)規(guī)劃最優(yōu)化原理：一個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)，即無論其初始狀態(tài)及其初始決策如何，其以后諸決策對(duì)以第一個(gè)決策所形成的狀態(tài)作為初始狀態(tài)而言，必須構(gòu)成最優(yōu)策略。動(dòng)態(tài)規(guī)劃原理還應(yīng)該包括如下性質(zhì)：對(duì)于多階段決策的最優(yōu)策略如果用它的前i步產(chǎn)生的情況來形成一個(gè)前i步問題，那么所給最優(yōu)策略的前i階段的策略構(gòu)成這前i步問題的一個(gè)最優(yōu)策略。用動(dòng)態(tài)規(guī)劃求解多階段決策問題的一般步驟：第1步明確問題，找出階段數(shù)第2步確定變量，找出狀態(tài)變量和決策變量第3步找出狀態(tài)轉(zhuǎn)移方程第4步寫出遞推關(guān)系式第5步求解遞推關(guān)系式第三節(jié)確定性的定期多階段決策問題教學(xué)重點(diǎn)：旅行售貨員問題，多階段資源分配問題，可靠性問題。教學(xué)難點(diǎn)：多階段資源分配問題。教學(xué)課時(shí)：4學(xué)時(shí)主要教學(xué)環(huán)節(jié)的組織：用具體的實(shí)例計(jì)算以上問題。1、旅行售貨員問題旅行售貨員問題是圖論中一個(gè)著名問題，就是在網(wǎng)絡(luò)上找一條從點(diǎn)出發(fā)，經(jīng)過各一次最后返回的最短路線和最短路程?，F(xiàn)把它看成一個(gè)多階段決策問題。從出發(fā)，經(jīng)過個(gè)階段，每個(gè)階段的決策是選擇下一個(gè)點(diǎn)。如果用所在的位置來表示狀態(tài)，那么狀態(tài)與階段數(shù)就不能完全決定決策集合了，因?yàn)樽哌^的點(diǎn)不需要再走，所以決策集合與以前選的決策有關(guān)。用表示狀態(tài)，是所處的點(diǎn)，是還沒有經(jīng)過的點(diǎn)集合。在狀態(tài)的決策集合中，取決策，獲得的效益是到的距離，轉(zhuǎn)入下一個(gè)狀態(tài)，現(xiàn)在用最優(yōu)化原理來找遞推公式。用表示從點(diǎn)出發(fā)，經(jīng)過中的點(diǎn)各一次，最后回到點(diǎn)的最短路程，是一個(gè)頂點(diǎn)集合，是到的弧長，則例5.3.1對(duì)圖5.3.1求從出發(fā)經(jīng)過，，，又返回的最短路線和最短路徑。解：可以用一個(gè)矩陣表示到的距離。表示從出發(fā)，經(jīng)過各一次又回到的最短路程。則：同樣，現(xiàn)在從最后一個(gè)階段解起：2、多階段資源分配問題下面討論有限資源分配問題，它的遞推公式是：一般情況下，，是很復(fù)雜的函數(shù)時(shí)，這個(gè)問題的解不容易找。當(dāng)，為凸函數(shù)，且時(shí)，可以證明在每個(gè)階段上的最優(yōu)決策總是取其端點(diǎn)的值。引理5.3.1設(shè)是凸函數(shù)，則對(duì)任何固定的，是的凸函數(shù)。引理5.3.2設(shè)是的凸函數(shù)，則也是的凸函數(shù)。定理5.3.1設(shè)g(y)，g(y)是凸函數(shù)，且h(0)=g(0)=0，則n階段資源分配問題的最優(yōu)策略y在每個(gè)階段總?cè)?yx的短點(diǎn)的值，并且證明：因?yàn)椋?由引理5.3.1知對(duì)固定的為凸函數(shù)，其極大值一定在或點(diǎn)上達(dá)到，所以，由引理5.3.2可知，是的凸函數(shù)，易證也是的凸函數(shù)，所以也是的凸函數(shù)，用歸納法可得：例5.3.2在有限資源分配問題中，而且，求第四節(jié)定性的不定期多階段決策問題教學(xué)重點(diǎn)：最優(yōu)線路問題，有限資源分配問題。教學(xué)難點(diǎn)：有限資源分配問題。教學(xué)課時(shí)：2學(xué)時(shí)主要教學(xué)環(huán)節(jié)的組