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