運籌學(xué)-第3版-課件-第5章動態(tài)規(guī)劃

1、第第1頁頁運運 籌籌 帷帷 幄幄 之之 中中決決 勝勝 千千 里里 之之 外外Dynamic ProgrammingDynamic Programming第第5 5章章 動態(tài)規(guī)劃動態(tài)規(guī)劃第第2頁頁綜綜 述述 動態(tài)規(guī)劃是運籌學(xué)的一個分支，是解決多階段決策問題的一動態(tài)規(guī)劃是運籌學(xué)的一個分支，是解決多階段決策問題的一種最優(yōu)化方法。與線性規(guī)劃不同的是，動態(tài)規(guī)劃沒有統(tǒng)一的數(shù)學(xué)種最優(yōu)化方法。與線性規(guī)劃不同的是，動態(tài)規(guī)劃沒有統(tǒng)一的數(shù)學(xué)模型和算法，它要求對具體問題進行具體分析，因而動態(tài)規(guī)劃更模型和算法，它要求對具體問題進行具體分析，因而動態(tài)規(guī)劃更多地是求解多階段決策問題的一種定量分析方法和途徑。多地是求解多階

2、段決策問題的一種定量分析方法和途徑。 所謂所謂多階段決策問題是多階段決策問題是指一類活動過程，它可以分為若指一類活動過程，它可以分為若干個相互聯(lián)系的階段，在每個階段都需要作出決策。這個決策不干個相互聯(lián)系的階段，在每個階段都需要作出決策。這個決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)。僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)。 每個階段的決策確定以后，就得到一個決策序列，稱為每個階段的決策確定以后，就得到一個決策序列，稱為策略。多階段決策問題就是求一個策略，使各階段的效益的總和策略。多階段決策問題就是求一個策略，使各階段的效益的總和達到最優(yōu)。達到最優(yōu)。第第3頁頁綜綜 述述 自

3、從自從2020世紀世紀5050年代，美國數(shù)學(xué)家貝爾曼提出動態(tài)規(guī)劃年代，美國數(shù)學(xué)家貝爾曼提出動態(tài)規(guī)劃的最優(yōu)性原理以來，動態(tài)規(guī)劃方法已獲得廣泛應(yīng)用，的最優(yōu)性原理以來，動態(tài)規(guī)劃方法已獲得廣泛應(yīng)用，它也成為現(xiàn)代企業(yè)管理中的一種重要的決策方法。應(yīng)它也成為現(xiàn)代企業(yè)管理中的一種重要的決策方法。應(yīng)用動態(tài)規(guī)劃可以解決諸如最優(yōu)路徑問題、資源分配問用動態(tài)規(guī)劃可以解決諸如最優(yōu)路徑問題、資源分配問題、生產(chǎn)調(diào)度問題、庫存問題、設(shè)備更新問題以及最題、生產(chǎn)調(diào)度問題、庫存問題、設(shè)備更新問題以及最優(yōu)控制問題等。優(yōu)控制問題等。 本章討論多階段決策問題以及動態(tài)規(guī)劃的基本本章討論多階段決策問題以及動態(tài)規(guī)劃的基本概念、原理和方法，并通過

4、若干典型實例來說明動概念、原理和方法，并通過若干典型實例來說明動態(tài)規(guī)劃在實踐中的一些應(yīng)用。態(tài)規(guī)劃在實踐中的一些應(yīng)用。第第4頁頁n5.1 多階段決策問題多階段決策問題n5.2 最優(yōu)化原理最優(yōu)化原理n5.3 確定性的定期多階段決策問題確定性的定期多階段決策問題n5.4 確定性的不定期多階段決策問題確定性的不定期多階段決策問題 第第5 5章章 動態(tài)規(guī)劃動態(tài)規(guī)劃第第5頁頁5.1 多階段決策問題多階段決策問題 例例1 最短路問題最短路問題 例例2 資源分配問題資源分配問題 例例3 生產(chǎn)和庫存問題生產(chǎn)和庫存問題 例例4 機金礦問題機金礦問題 例例5 多階段決策問題多階段決策問題例1、最短線路問題 最短路問

5、題就是從某地出發(fā)，途經(jīng)若干中間點最后到達目的地，要求找出路程或費用最小的路線。一般的最短路問題將在下一章討論，這里只討論分層的最短路問題。下面的管道設(shè)計問題(例5.1.1)就是其中之一。ED3D1D2C1C3C2AB3B2B1542634656122233234n從A點到E點要鋪設(shè)一條天然氣管道，n 中間必須經(jīng)過三個中間站，n第一站可在B1、B2、B3中選擇，n第二站可在C1、C2、C3中選擇，n第三站可在D1、D2、D3中選擇，n要求選擇一條由A 到E的鋪管路線，使總長度最短。n其中兩點連線上的數(shù)字表示兩點間管線的長度。ED3D1D2C1C3C2AB3B2B15426346561222332

6、34從A點到E點鋪設(shè)管道，可以按其地理特點自然地分成四個階段：（如下圖所示）從A到B是第一階段，從B到C是第二階段，從C到D是第三階段，從D到E是第四階段，ABCDE階段1階段2階段3階段4ED3D1D2C1C3C2AB3B2B1542634656122233234在階段2，從B3點出發(fā)，只有C1、C3兩種可選擇的點，如選C1,則C1就是階段2在B3點的決策結(jié)果；C1點既是階段2鋪設(shè)管道的終點，又是階段3鋪設(shè)管道的起點；ED3D1D2C1C3C2AB3B2B1542634656122233234同樣的理由，可以遞推得其余階段的鋪設(shè)路線，如階段3在C1點的決策是D1，階段4在D1點的決策只有E點

7、；由于到E點是整個鋪設(shè)管道的終點，至此，決策過程完成，鋪設(shè)一條A點到E點的管道是由四個階段的管道組成的，如A-B3-C1-D1-E，它也稱為一個策略。ED3D1D2C1C3C2AB3B2B1542634656122233234 可以看出，各個階段的決策不同，鋪設(shè)的管道也不同，并且當某個階段的 始點給定后，它直接影響著后面各階段的行進路線和管道的長短，而后面各階段的路線 的選取不受這點以前各階段路線的影響。 因此，最短路線問題可簡化為四個階段決策問題，使由這四個階段決策組成決策序列，也 稱為策略所決定的一條路線的總長度最短。ED3D1D2C1C3C2AB3B2B15426346561222332

8、34第第12頁頁例例2 2 多階段資源分配問題多階段資源分配問題 設(shè)有數(shù)量為設(shè)有數(shù)量為x的某種資源，將它投入兩種的某種資源，將它投入兩種生產(chǎn)方式生產(chǎn)方式A和和B中：以數(shù)量中：以數(shù)量y投入生產(chǎn)方式投入生產(chǎn)方式A，剩下的量投入生產(chǎn)方式剩下的量投入生產(chǎn)方式B，則可得到收入，則可得到收入g(y)+h(x-y)，其中，其中g(shù)(y)和和h(y)是已知函數(shù)，并且是已知函數(shù)，并且g(0)=h(0)=0；同時假設(shè)以；同時假設(shè)以y與與x-y分別投入兩種分別投入兩種生產(chǎn)方式生產(chǎn)方式A，B后可以回收再生產(chǎn)，回收率分后可以回收再生產(chǎn)，回收率分別為別為a與與b。試求進行。試求進行n個階段后的最大總收入。個階段后的最大總收

9、入。 第第13頁頁例例2 2 多階段資源分配問題多階段資源分配問題- -續(xù)續(xù)(1)(1) 若以若以y與與x-y分別投入生產(chǎn)方式分別投入生產(chǎn)方式A與與B，在第一，在第一階段生產(chǎn)后回收的總資源為階段生產(chǎn)后回收的總資源為x1=ay+b(x-y)，再將，再將x1投入生產(chǎn)方式投入生產(chǎn)方式A和和B，則可得到收入，則可得到收入g(y1)+h(x1-y1)，繼續(xù)回收資源繼續(xù)回收資源x2=ay1+b(x1-y1)， 若上面的過程進行若上面的過程進行n個階段，我們希望選擇個階段，我們希望選擇n個變量個變量y,y1,y2,yn-1，使這，使這n個階段的總收入最大。個階段的總收入最大。 第第14頁頁 因此，我們的問題

10、就變成：求因此，我們的問題就變成：求y,y1,y2,yn-1，以，以使使g(y)+h(x-y)+ g(y1)+h(x1-y1)+ +g(yn-1)+h(xn-1-yn-1) 達到最大，且滿足條件達到最大，且滿足條件 x1=ay+b(x-y) x2=ay1+b(x1-y1) xn-1=ayn-2+b(xn-2-yn-2) yi與與xi均非負均非負,i=1,2, ,n-1 例例2 2 多階段資源分配問題多階段資源分配問題- -續(xù)續(xù)(2)(2)第第15頁頁例例3 3 生產(chǎn)和庫存問題生產(chǎn)和庫存問題 某工廠生產(chǎn)某種季節(jié)性商品，需要作下一某工廠生產(chǎn)某種季節(jié)性商品，需要作下一年度的生產(chǎn)計劃，假定這種商品的生

11、產(chǎn)周期需年度的生產(chǎn)計劃，假定這種商品的生產(chǎn)周期需要兩個月，全年共有要兩個月，全年共有6個生產(chǎn)周期，需要作出個生產(chǎn)周期，需要作出各個周期中的生產(chǎn)計劃。各個周期中的生產(chǎn)計劃。設(shè)已知各周期對該商品的需要量如下表所示設(shè)已知各周期對該商品的需要量如下表所示：周期周期123456需求量需求量551030508第第16頁頁 假設(shè)這個工廠根據(jù)需要可以日夜兩班生產(chǎn)或只是日假設(shè)這個工廠根據(jù)需要可以日夜兩班生產(chǎn)或只是日班生產(chǎn)，當開足日班時，每一個生產(chǎn)周期能生產(chǎn)商品班生產(chǎn)，當開足日班時，每一個生產(chǎn)周期能生產(chǎn)商品1515個單位，每生產(chǎn)一個單位商品的成本為個單位，每生產(chǎn)一個單位商品的成本為100100元。當開足元。當開足

12、夜班時，每一生產(chǎn)周期能生產(chǎn)的商品也是夜班時，每一生產(chǎn)周期能生產(chǎn)的商品也是1515個，但是由個，但是由于增加了輔助性生產(chǎn)設(shè)備和生產(chǎn)輔助費用，每生產(chǎn)一單于增加了輔助性生產(chǎn)設(shè)備和生產(chǎn)輔助費用，每生產(chǎn)一單位商品的成本為位商品的成本為120120元。由于生產(chǎn)能力的限制，可以在元。由于生產(chǎn)能力的限制，可以在需求淡季多生產(chǎn)一些商品儲存起來以備需求旺季使用，需求淡季多生產(chǎn)一些商品儲存起來以備需求旺季使用，但存儲商品是需要存儲但存儲商品是需要存儲費用的，假設(shè)每單位商品存儲一費用的，假設(shè)每單位商品存儲一周期需要周期需要16元，已知開始時存儲為零，年終也不存儲商元，已知開始時存儲為零，年終也不存儲商品備下年使用，問

13、應(yīng)該如何作生產(chǎn)和存儲計劃，才能使品備下年使用，問應(yīng)該如何作生產(chǎn)和存儲計劃，才能使總的生產(chǎn)和存儲費用最?。靠偟纳a(chǎn)和存儲費用最?。坷? 3 生產(chǎn)和生產(chǎn)和庫存庫存問題問題- -續(xù)續(xù)(1)(1)第第17頁頁 設(shè)第設(shè)第i個周期的生產(chǎn)量為個周期的生產(chǎn)量為xi，周期末的存儲量為，周期末的存儲量為ui，那，那么這個問題用式子寫出來就是：求么這個問題用式子寫出來就是：求x1,x2,x6，滿足條件：，滿足條件： x1=5+u1， x2+u1=5+u2， x3+u2=10+u3 x4+u3=30+u4 ， x5+u4=50+u5， x6+u5=8 0 xi 30, 0 uj, i=1,2,6; j=1,2, ,

14、5 使使S= = 為最小，其中為最小，其中例例3 3 生產(chǎn)和生產(chǎn)和庫存庫存問題問題- -續(xù)續(xù)(2)(2) tjjiiuxf16116)()1852345(16)(5432161xxxxxxfii3015,300120150 ,100)(iiiiixxxxxf第第18頁頁例4.機金礦問題 兩個金礦兩個金礦A,B分別有存儲量分別有存儲量x，y，現(xiàn)有一部開礦機，現(xiàn)有一部開礦機器，如果開采金礦器，如果開采金礦A，則以概率，則以概率p1得儲量得儲量x的的r1倍（倍（0 r11），并且機器沒有損壞，可以繼續(xù)再去開采金礦），并且機器沒有損壞，可以繼續(xù)再去開采金礦A或或B。同時又以概率。同時又以概率1- p1

15、宣告失敗，機器報廢，也宣告失敗，機器報廢，也得不到金子；如果把這部開礦機器用以開采金礦得不到金子；如果把這部開礦機器用以開采金礦B，則以概率則以概率p2得到儲量得到儲量y的的r2倍（倍（0r21），并且機器沒），并且機器沒有損壞，可以繼續(xù)再去開采金礦有損壞，可以繼續(xù)再去開采金礦A或或B，同時又以概，同時又以概率率1- p2宣告失敗，機器報廢，也得不到金子。宣告失敗，機器報廢，也得不到金子。 把機器用于開采金礦把機器用于開采金礦A或者或者B，如果機器沒有損壞，如果機器沒有損壞，將繼續(xù)把機器用于開采金礦，將繼續(xù)把機器用于開采金礦A或者或者B，直到機器損，直到機器損壞，問應(yīng)該如何選擇開礦的序列使獲得

16、金子的期望值壞，問應(yīng)該如何選擇開礦的序列使獲得金子的期望值最大。最大。第第19頁頁例例5 多階段決策問題多階段決策問題 有一個系統(tǒng)，可以分成若干個階段，任意一有一個系統(tǒng)，可以分成若干個階段，任意一個階段個階段k，系統(tǒng)的狀態(tài)可以用，系統(tǒng)的狀態(tài)可以用xk表示（可以是數(shù)量、表示（可以是數(shù)量、向量、集合等）。在每一階段向量、集合等）。在每一階段k的每一狀態(tài)都有一的每一狀態(tài)都有一個決策集合個決策集合Qk(xk)，在，在Qk(xk)中選定一個決策中選定一個決策qkQk(xk)，狀態(tài)，狀態(tài)xk就轉(zhuǎn)移到新的狀態(tài)就轉(zhuǎn)移到新的狀態(tài)xk+1=Tk(xk,qk)，并且得到效益并且得到效益Rk(xk,qk)。我們的目的

17、就是在每一。我們的目的就是在每一個階段都在它的決策集合中選擇一個決策，使所個階段都在它的決策集合中選擇一個決策，使所有階段的總效益達到最大。有階段的總效益達到最大。 這樣的多階段決策問題稱為這樣的多階段決策問題稱為動態(tài)規(guī)劃動態(tài)規(guī)劃。第第20頁頁多階段決策問題的基本要素：階段數(shù)、狀態(tài)變量、多階段決策問題的基本要素：階段數(shù)、狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移方程和目標函數(shù)。決策變量、狀態(tài)轉(zhuǎn)移方程和目標函數(shù)。例例5 多階段決策問題多階段決策問題 多階段決策問題的分類多階段決策問題的分類階段數(shù)：有限階段決策問題和無限階段決策問題；階段數(shù)：有限階段決策問題和無限階段決策問題；狀態(tài)變量：連續(xù)多階段決策問題和離散

18、多有限階段決狀態(tài)變量：連續(xù)多階段決策問題和離散多有限階段決策問題；策問題；階段個數(shù)是否明確：定期多階段決策問題和不定期多階段個數(shù)是否明確：定期多階段決策問題和不定期多階段決策問題；階段決策問題；參數(shù)取值情況：確定多階段決策問題和不確定多階段參數(shù)取值情況：確定多階段決策問題和不確定多階段決策問題。決策問題。第第21頁頁5.35.3 最優(yōu)化原理最優(yōu)化原理動態(tài)規(guī)劃最優(yōu)化原理動態(tài)規(guī)劃最優(yōu)化原理：一個過程的最優(yōu)策：一個過程的最優(yōu)策略具有這樣的性質(zhì)，即無論其初始狀態(tài)及略具有這樣的性質(zhì)，即無論其初始狀態(tài)及其初始決策如何，其以后諸決策對以第一其初始決策如何，其以后諸決策對以第一個決策所形成的狀態(tài)作為初始狀態(tài)而

19、言，個決策所形成的狀態(tài)作為初始狀態(tài)而言，必須構(gòu)成最優(yōu)策略。必須構(gòu)成最優(yōu)策略。動態(tài)規(guī)劃的理論基礎(chǔ)是最優(yōu)性原理，它是貝爾動態(tài)規(guī)劃的理論基礎(chǔ)是最優(yōu)性原理，它是貝爾曼于曼于2020世紀世紀5050年代依據(jù)一類多階段決策問題提年代依據(jù)一類多階段決策問題提出的。出的。第第22頁頁最優(yōu)化原理的性質(zhì)：最優(yōu)化原理的性質(zhì)：對于多階段決策問題對于多階段決策問題的最優(yōu)策略，如果用它的前步策略產(chǎn)生的的最優(yōu)策略，如果用它的前步策略產(chǎn)生的情況（加上原有的約束條件）來形成一個情況（加上原有的約束條件）來形成一個前步問題，那么所給最優(yōu)策略的前階段的前步問題，那么所給最優(yōu)策略的前階段的策略構(gòu)成這前步問題的一個最優(yōu)策略。策略構(gòu)成這

20、前步問題的一個最優(yōu)策略。 5.35.3 最優(yōu)化原理最優(yōu)化原理動態(tài)規(guī)劃的最優(yōu)化定理的數(shù)學(xué)表述 設(shè)一個 n 階段決策問題，階段變量 k=1，2，n ，初始狀態(tài) 已知，則允許策略 是最優(yōu)策略的充要條件是:對任意一個 k ，1kn 成立。 其中 ，opt是 max 或 min ，運算符 “ * ” 表示加法或乘法。1s),(*),(),(, 11, 1, 11, 1, 11, 1, 1, 1nkknkpkkpnnpsvoptpsvoptpsvnkk)(),(1, 1, 1, 1kkknkknsusppp 下面以下圖所示的網(wǎng)絡(luò)中確定AE最短路(例1)為例，來說明應(yīng)用動態(tài)規(guī)劃最優(yōu)化定理解決問題的步驟。2E

21、D3D1D2C1C3C2AB3B2B154263465612233234 由最優(yōu)化定理可知，一條 A-E 最短路的后部子路也是最短的。即如果找到一條 A-E 最短路 A-B3-C1-D1-E，則 C1-D1-E 也是一條連接 C1 與 E 的最短路。利用最短路的這一特性，尋找 A-E 最短路的方法，就是從最后一段，即 D-E 段開始，用由后向前逐步逆推的方法，求出各點到 E 的最短路線，最后求出從 A 點到 E 點的最短路。 當 k=4 時，取定一個狀態(tài) D1 ，從 D1 到 E 只有一條路線，故 ； 同理， , 。 2)(14Df3)(24Df4)(34Df332 , 21min)(),()

22、,(),(min)(2421141113DfDCdDfDCdCf 當 k=3 時，取定一個狀態(tài) C1 ，從 C1 出發(fā)，有 D1、D2 兩種選擇，所以 故相應(yīng)的決策為 。這說明，從C1到終點 E 的最短路長是3，最短路線是 ：C1-D1-E 。 同理，從狀態(tài) C2 出發(fā)，有:相應(yīng)決策為 ；113)(DCu442 , 22min)(),(),(),(min)(3432141223DfDCdDfDCdCf123)(DCu類似地可算出：當 k=2 時當 k=1 時，于是從 A 到 E 的最短路為 。 643 , 33min)(),(),(),(min)(3433242333DfDCdDfDCdCf2

23、1212)(, 7)(CBuBf12222)(, 7)(CBuBf13232)(, 8)(CBuBf10)(1Af 為了找出最短路，按計算的順序反推之，可求出最優(yōu)決策序列：因而得到相應(yīng)的最短路 A-B3-C1-D1-E。 以上計算最短路的過程，可用以下圖形標出：EDuDCuCBuBAu)(,)(,)(,)(1411313231543233222165436624ED3D1D2C1C3C2AB3B2B1410877634320 在上圖中，每個節(jié)點上方的數(shù)表示從該點到 E 的最短路長。其中粗線表示一條 A-E 的最短路。這種在圖上作業(yè)的方法稱為標號法。它是先從 E 開始，逆著階段順序方向（狀態(tài)行進

24、方向）進行的，因此，這種方法也稱為逆序法。 一般地，給定一個 n 階段決策問題，階段變量為 k=1，2，n , 初始狀態(tài)已知，狀態(tài)變量為 ，決策變量為 ，決策指標記為 。則直觀模型如下圖所示：ks)(kksu),(kkkusv 因為初始狀態(tài)已知，從上圖中，狀態(tài)轉(zhuǎn)移方程為：它說明狀態(tài)的行進方向是順著 階段的自然順序的。利用最優(yōu)化定理，該問題的尋優(yōu)途徑是先從最后一個階段開始逆著狀態(tài)行進方向進行，稱為逆序法。11s1u1vn1nsnsnvnuk1kskskvku。2ss k+1 = u k(s k) (k=1,2,n) 設(shè) 表示從第 k階段的狀態(tài) 開始到第 n 階段的終止狀態(tài) 的過程，采取最優(yōu)策略所

25、得到的指標函數(shù)值。綜上分析得出 k 階段與 k+1 階段之間的遞推關(guān)系：邊界條件為 。 )(kksfks1ns) 1,.,1,()(*)(,()(11)(nnksfsusvoptsfkkkkkkssukkkkk0)(11nnsf 這種遞推關(guān)系式稱為動態(tài)規(guī)劃逆序法的基本方程，簡稱基本方程。 通過求解基本方程可以得出問題的一個最優(yōu)策略。 如果 n 階段決策問題的終止狀態(tài) 給定，如何確定它的基本方程呢？假設(shè)階段變量 k 與狀態(tài)變量 的定義不變。由于終止狀態(tài)給定，從而決策變量應(yīng)寫為 ，從而狀態(tài)轉(zhuǎn)移方程為：1nsks)(1kksu)(1kkksus11s1u1vn1nsnsnvnuk1kskskvku。

26、2s 這說明狀態(tài)的行進方向與階段的自然順序相反，因而尋優(yōu)途徑應(yīng)從第1階段的初始狀態(tài) s 1 開始，沿著與狀態(tài)的行進方向相反方向，因而順著階段的自然順序進行，稱為順序法。 這可看成處于第 k 階段的終止狀態(tài) 作出決策 而得到第 k-1 階段的終止狀態(tài)。因而，給問題的直觀模型下圖所示：1ksku 令 表示從第1階段的起始狀態(tài)到第 k 階段的終止狀態(tài) 的過程，最優(yōu)策略的指標函數(shù)值。建立遞推關(guān)系式為 (2)邊界條件 其中 表示第 k 階段的終止狀態(tài) 的允許決策集合。稱（2）式是動態(tài)規(guī)劃順序法的基本方程，簡稱基本方程。)(1kksf1ks),.,2 , 1()(*),()(11)(11nksfusvop

27、tsfkkkkksDukkkrkk0)(10sf)(1krksD第第37頁頁用最優(yōu)化原理求解例用最優(yōu)化原理求解例3：生產(chǎn)和庫存問題生產(chǎn)和庫存問題 如果一開始的存儲量如果一開始的存儲量u u0 0已經(jīng)給定，要已經(jīng)給定，要求最后一個周期結(jié)束時有存儲量求最后一個周期結(jié)束時有存儲量u un n，那么最，那么最優(yōu)生產(chǎn)和存儲費用就完全由優(yōu)生產(chǎn)和存儲費用就完全由u u0 0，u un n決定。對決定。對某一個周期某一個周期k k，如果這個周期開始時有庫存，如果這個周期開始時有庫存量量u uk-1k-1，要求結(jié)束時有庫存量，要求結(jié)束時有庫存量u uk k，那么它的，那么它的生產(chǎn)數(shù)量生產(chǎn)數(shù)量x xk k=s=s

28、k k+u+uk k-u-uk-1k-1，s sk k是這個周期的商是這個周期的商品需求量，所以它的生產(chǎn)和存儲費為品需求量，所以它的生產(chǎn)和存儲費為f(xf(xk k)+16 u)+16 uk-1k-1，其中，其中3015,300120150 ,100)(xxxxxf第第38頁頁 用用Fk(u0,uk)表示開始的存儲量為表示開始的存儲量為u0，第，第k個周期結(jié)束個周期結(jié)束時存儲量為時存儲量為uk的滿足前的滿足前k個周期需要的前個周期需要的前k個周期的最優(yōu)個周期的最優(yōu)生產(chǎn)和存儲費用，由最優(yōu)化原理生產(chǎn)和存儲費用，由最優(yōu)化原理 xk=sk+uk-uk-1, k=2,3,6 x1=s1+u1-u0, 讓

29、讓k=2,3,6，求出，求出F6(u0,u6)，就得到問題的解，就得到問題的解16)(),(min),(1101001kkkkukkuxfuuFuuFk0110116)(),(uxfuuF求解例求解例3：生產(chǎn)和庫存問題生產(chǎn)和庫存問題-續(xù)續(xù) (1)第第39頁頁5.3 確定性的定期多階段決策問題確定性的定期多階段決策問題q旅行售貨員問題旅行售貨員問題 q多階段資源分配問題多階段資源分配問題q用最優(yōu)化原理解某些非線性規(guī)劃問題用最優(yōu)化原理解某些非線性規(guī)劃問題 q排序排序q最優(yōu)排序法最優(yōu)排序法第第40頁頁旅行售貨員問題旅行售貨員問題 旅行售貨員問題是圖論中一個著名問題，就是在網(wǎng)絡(luò)旅行售貨員問題是圖論中一

30、個著名問題，就是在網(wǎng)絡(luò)N N上找一條從上找一條從v v0 0點出發(fā)，經(jīng)過點出發(fā)，經(jīng)過v v1 1,v,v2 2,v,vn n各一次最后返回各一次最后返回v v0 0的最短路線和最短路程。現(xiàn)把它看成一個多階段決策的最短路線和最短路程?，F(xiàn)把它看成一個多階段決策問題。從問題。從v v0 0出發(fā)，經(jīng)過出發(fā)，經(jīng)過n n個階段，每個階段的決策是選擇個階段，每個階段的決策是選擇下一個點。如果用所在的位置來表示狀態(tài)，那么狀態(tài)與下一個點。如果用所在的位置來表示狀態(tài)，那么狀態(tài)與階段數(shù)就不能完全決定決策集合了，因為走過的點不需階段數(shù)就不能完全決定決策集合了，因為走過的點不需要再走，所以決策集合與以前選的決策有關(guān)。用

31、（要再走，所以決策集合與以前選的決策有關(guān)。用（v vi i,V,V）表示狀態(tài)，表示狀態(tài)，v vi i是所處的點，是所處的點，V V是還沒有經(jīng)過的點集合。在是還沒有經(jīng)過的點集合。在狀態(tài)（狀態(tài)（v vi i,V,V）的決策集合中，取決策）的決策集合中，取決策v vj jV V，獲得的效益是，獲得的效益是v vi i到到v vj j的距離的距離d dijij，轉(zhuǎn)入下一個狀態(tài)（，轉(zhuǎn)入下一個狀態(tài)（v vj j,Vv,Vvj j ），現(xiàn)在），現(xiàn)在用最優(yōu)化原理來找遞推公式。用最優(yōu)化原理來找遞推公式。第第41頁頁旅行售貨員問題旅行售貨員問題-續(xù)續(xù) (1) 用用f fk k(v(vi i,V),V)表示從表示從

32、v vi i點出發(fā)，經(jīng)過點出發(fā)，經(jīng)過V V中的點中的點各一次，最后回到各一次，最后回到v v0 0點的最短路程，點的最短路程，V V是一個是一個頂點集合，頂點集合，|V|=k|V|=k，d dijij是是v vi i到到v vj j的弧長，則的弧長，則001),(, 2 , 1),(min),(iijjkijVvikdvfnkvVvfdVvfj其余內(nèi)容見書本第166頁!第第42頁頁多階段資源分配問題多階段資源分配問題下面討論有限資源分配問題，它的遞推公式是：下面討論有限資源分配問題，它的遞推公式是： 一般情況下，一般情況下，g(y)，g(y)是很復(fù)雜的函數(shù)時，這個問題的是很復(fù)雜的函數(shù)時，這個問

33、題的解不容易找。當解不容易找。當g(y)，g(y)為凸函數(shù)，且為凸函數(shù)，且h(0)=g(0)=0時，可以證明在每個階段上時，可以證明在每個階段上y的最優(yōu)決策總是取其端的最優(yōu)決策總是取其端點的值。點的值。 )()(max)(2),()()(max)(0110yxhygxfkyxbayfyxhygxfxykxyk第第43頁頁多階段資源分配問題多階段資源分配問題-續(xù)續(xù)(1)引理引理5.2.1 設(shè)設(shè)g(x)，g(y)是凸函數(shù)，則對任何固定是凸函數(shù)，則對任何固定 的的x，F(xiàn)(y)=g(y)+h(x-y)是是y的凸函數(shù)。的凸函數(shù)。 引理引理5.2.2 設(shè)設(shè)F1(x),F2(X)是是x的凸函數(shù)，則的凸函數(shù)，

34、則 F(x)=max F1(x),F2(X) 也是也是x的凸函數(shù)。的凸函數(shù)。第第44頁頁多階段資源分配問題多階段資源分配問題-續(xù)續(xù)(2)定理定理5.2.1 設(shè)設(shè)g(y)g(y)，g(y)g(y)是凸函數(shù)，且是凸函數(shù)，且h(0)=g(0)=0h(0)=g(0)=0，則則n n階段資源分配問題的最優(yōu)策略階段資源分配問題的最優(yōu)策略y y在每個階段在每個階段總?cè)】側(cè)?yx0yx的短點的值，并且的短點的值，并且)(),(max)()()(),()(max)(111xgxhxfaxfxgbxfxhxfkkk第第45頁頁5.4 確定性的不定期多階段決策問題確定性的不定期多階段決策問題 有的多階段決策過程有的

35、多階段決策過程, ,給定一個狀態(tài)集合給定一個狀態(tài)集合X XT T , ,當狀態(tài)當狀態(tài)x xX XT T時時, ,過程停止過程停止, ,這是階段不確定的多階這是階段不確定的多階段決策過程。如果經(jīng)過有限階段段決策過程。如果經(jīng)過有限階段, ,狀態(tài)狀態(tài)x x一定能進一定能進入入X XT T , ,就是階段數(shù)有限的就是階段數(shù)有限的, ,否則就是階段數(shù)無限否則就是階段數(shù)無限的的. .這類問題通常利用最優(yōu)化原理得到一個函數(shù)這類問題通常利用最優(yōu)化原理得到一個函數(shù)方程來求解方程來求解. . 主要有主要有: : 1: 1:最優(yōu)線路問題最優(yōu)線路問題. . 2: 2:有限資源分配問題有限資源分配問題. . 不作詳細講

36、述不作詳細講述. . 第第46頁頁用最優(yōu)化原理解某些非線性規(guī)劃問題用最優(yōu)化原理解某些非線性規(guī)劃問題 假設(shè)有數(shù)量假設(shè)有數(shù)量x0的物資可用于的物資可用于n種生產(chǎn)，若以種生產(chǎn)，若以xi投入第投入第i種生產(chǎn)時可得收益種生產(chǎn)時可得收益gi(xi)，問應(yīng)如何選取，問應(yīng)如何選取xi，使得，使得x0用用于于n種生產(chǎn)時得到的總收益最大。這個問題可以寫成種生產(chǎn)時得到的總收益最大。這個問題可以寫成數(shù)學(xué)規(guī)劃問題：數(shù)學(xué)規(guī)劃問題：nixxxxxtsxgxgxgFinnn, 2 , 1, 0. .)()()(max0212211第第47頁頁續(xù)續(xù) (1) 假設(shè)每個假設(shè)每個gi(xi)在內(nèi)連續(xù)，顯然在內(nèi)連續(xù)，顯然F的極大值存的極大值存在，這是一個特殊類型的非線性規(guī)劃問題，由在，這是一個特殊類型的非線性規(guī)劃問題，由于這類問題的特殊結(jié)構(gòu)，可以把它看成一個多于這類問題的特殊結(jié)構(gòu)，可以把它看成一個多階段決策問題，并利用動態(tài)規(guī)劃的遞推關(guān)系求階段決策問題，并利用動態(tài)規(guī)劃的遞推關(guān)系求解。解。 把數(shù)量為把數(shù)量為x0的物資投入的物資投入n種生產(chǎn)方式，可以種生產(chǎn)方式，可以看成是看成是n階段決策問題每階段投入一定數(shù)量物