數(shù)學(xué)建模 動態(tài)規(guī)劃

1、第第1頁頁運運 籌籌 帷帷 幄幄 之之 中中決決 勝勝 千千 里里 之之 外外運運 籌籌 學(xué)學(xué) 課課 件件動動 態(tài)態(tài) 規(guī)規(guī) 劃劃Dynamic ProgrammingDynamic Programming第第2頁頁動動 態(tài)態(tài) 規(guī)規(guī) 劃劃n綜述綜述n最優(yōu)化原理最優(yōu)化原理n確定性的定期多階段決策問題確定性的定期多階段決策問題n確定性的不定期多階段決策問題確定性的不定期多階段決策問題 第第3頁頁綜綜 述述 動態(tài)規(guī)劃所研究的對象是多階段決策問題。動態(tài)規(guī)劃所研究的對象是多階段決策問題。 所謂所謂多階段決策問題是多階段決策問題是指一類活動過程，它指一類活動過程，它可以分為若干個相互聯(lián)系的階段，在每個階段都

2、可以分為若干個相互聯(lián)系的階段，在每個階段都需要作出決策。這個決策不僅決定這一階段的效需要作出決策。這個決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)。益，而且決定下一階段的初始狀態(tài)。 每個階段的決策確定以后，就得到一個決策每個階段的決策確定以后，就得到一個決策序列，稱為策略。多階段決策問題就是求一個策序列，稱為策略。多階段決策問題就是求一個策略，使各階段的效益的總和達(dá)到最優(yōu)。略，使各階段的效益的總和達(dá)到最優(yōu)。第第4頁頁最優(yōu)化原理最優(yōu)化原理 多階段決策問題及實例多階段決策問題及實例 例1 例2 例3 多階段決策問題 最優(yōu)化原理最優(yōu)化原理 性質(zhì) 用最優(yōu)化原理求解例2第第5頁頁例例1 1 多

3、階段資源分配問題多階段資源分配問題 設(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。試求進(jìn)行。試求進(jìn)行n個階段后的最大總收入。個階段后的最大總收入。 第第6頁頁例例1 1 續(xù)

4、（續(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)， 若上面的過程進(jìn)行若上面的過程進(jìn)行n個階段，我們希望選擇個階段，我們希望選擇n個變量個變量y,y1,y2,yn-1，使這，使這n個階段的總收入最大。個階段的總收入最大。 第第7頁頁 因此，我們的問題就變成：求因此，我們的問題就變成：求y,y1,y2,yn-1，以，以使使g(

5、y)+h(x-y)+ g(y1)+h(x1-y1)+ +g(yn-1)+h(xn-1-yn-1) 達(dá)到最大，且滿足條件達(dá)到最大，且滿足條件 x1=ay+b(x-y) x2=ay1+b(x1-y1) xn-1=ayn-2+b(xn-2-yn-2) yi與與xi均非負(fù)均非負(fù),i=1,2, ,n-1 例例1 1 續(xù)（續(xù)（2 2）第第8頁頁例例2 2 生產(chǎn)和存儲控制問題生產(chǎn)和存儲控制問題 某工廠生產(chǎn)某種季節(jié)性商品，需要作下一某工廠生產(chǎn)某種季節(jié)性商品，需要作下一年度的生產(chǎn)計劃，假定這種商品的生產(chǎn)周期需年度的生產(chǎn)計劃，假定這種商品的生產(chǎn)周期需要兩個月，全年共有要兩個月，全年共有6個生產(chǎn)周期，需要作出個生產(chǎn)

6、周期，需要作出各個周期中的生產(chǎn)計劃。各個周期中的生產(chǎn)計劃。第第9頁頁設(shè)已知各周期對該商品的需要量如下表所示設(shè)已知各周期對該商品的需要量如下表所示：周期周期123456需求量需求量551030508例例2 2 續(xù)（續(xù)（1 1）第第10頁頁例例2 2 續(xù)（續(xù)（2 2） 假設(shè)這個工廠根據(jù)需要可以日夜兩班生產(chǎn)或只是日假設(shè)這個工廠根據(jù)需要可以日夜兩班生產(chǎn)或只是日班生產(chǎn)，當(dāng)開足日班時，每一個生產(chǎn)周期能生產(chǎn)商品班生產(chǎn)，當(dāng)開足日班時，每一個生產(chǎn)周期能生產(chǎn)商品1515個單位，每生產(chǎn)一個單位商品的成本為個單位，每生產(chǎn)一個單位商品的成本為100100元。當(dāng)開足元。當(dāng)開足夜班時，每一生產(chǎn)周期能生產(chǎn)的商品也是夜班時，每

7、一生產(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元，已知開始時存儲為零，年終也不存儲商元，已知開始時存儲為零，年終也不存儲商品備下年使用，問應(yīng)該如何作生產(chǎn)和存儲計劃，才能使品備下年使用，

8、問應(yīng)該如何作生產(chǎn)和存儲計劃，才能使總的生產(chǎn)和存儲費用最??？總的生產(chǎn)和存儲費用最小？第第11頁頁例例2 2 續(xù)（續(xù)（3 3） 設(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, ,5 使使S= = 為最小，其中為最小，其中 tjjiiuxf16116)()1852345(16

9、)(5432161xxxxxxfii第第12頁頁3015,300120150 ,100)(iiiiixxxxxf例例2 2 續(xù)（續(xù)（4 4）第第13頁頁例3.機(jī)金礦問題 兩個金礦兩個金礦A,B分別有存儲量分別有存儲量x，y，現(xiàn)有一部開礦機(jī)，現(xiàn)有一部開礦機(jī)器，如果開采金礦器，如果開采金礦A，則以概率，則以概率p1得儲量得儲量x的的r1倍（倍（0 r11），并且機(jī)器沒有損壞，可以繼續(xù)再去開采金礦），并且機(jī)器沒有損壞，可以繼續(xù)再去開采金礦A或或B。同時又以概率。同時又以概率1- p1宣告失敗，機(jī)器報廢，也宣告失敗，機(jī)器報廢，也得不到金子；如果把這部開礦機(jī)器用以開采金礦得不到金子；如果把這部開礦機(jī)器用

10、以開采金礦B，則以概率則以概率p2得到儲量得到儲量y的的r2倍（倍（0r21），并且機(jī)器沒），并且機(jī)器沒有損壞，可以繼續(xù)再去開采金礦有損壞，可以繼續(xù)再去開采金礦A或或B，同時又以概，同時又以概率率1- p2宣告失敗，機(jī)器報廢，也得不到金子。宣告失敗，機(jī)器報廢，也得不到金子。 把機(jī)器用于開采金礦把機(jī)器用于開采金礦A或者或者B，如果機(jī)器沒有損壞，如果機(jī)器沒有損壞，將繼續(xù)把機(jī)器用于開采金礦，將繼續(xù)把機(jī)器用于開采金礦A或者或者B，直到機(jī)器損，直到機(jī)器損壞，問應(yīng)該如何選擇開礦的序列使獲得金子的期望值壞，問應(yīng)該如何選擇開礦的序列使獲得金子的期望值最大。最大。第第14頁頁多階段決策問題多階段決策問題 有一個

11、系統(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)。我們的。我們的目的就是在每一個階段都在它的決策集合中選目的就是在每一個階段都在它的決策集合中選擇一個決策，使所有階段的總效益達(dá)到最大。

12、擇一個決策，使所有階段的總效益達(dá)到最大。 這樣的多階段問題稱為這樣的多階段問題稱為動態(tài)規(guī)劃動態(tài)規(guī)劃。第第15頁頁最優(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)而言，個決策所形成的狀態(tài)作為初始狀態(tài)而言，必須構(gòu)成最優(yōu)策略。必須構(gòu)成最優(yōu)策略。第第16頁頁最優(yōu)化原理的性質(zhì)最優(yōu)化原理的性質(zhì) 對于多階段決策問題的最優(yōu)策略，對于多階段決策問題的最優(yōu)策略，如果用它的前步策略產(chǎn)生的情況（加上如果

13、用它的前步策略產(chǎn)生的情況（加上原有的約束條件）來形成一個前步問題，原有的約束條件）來形成一個前步問題，那么所給最優(yōu)策略的前階段的策略構(gòu)成那么所給最優(yōu)策略的前階段的策略構(gòu)成這前步問題的一個最優(yōu)策略。這前步問題的一個最優(yōu)策略。第第17頁頁用最優(yōu)化原理求解例用最優(yōu)化原理求解例2 如果一開始的存儲量如果一開始的存儲量u0已經(jīng)給定，要求最后一個已經(jīng)給定，要求最后一個周期結(jié)束時有存儲量周期結(jié)束時有存儲量un，那么最優(yōu)生產(chǎn)和存儲費用就，那么最優(yōu)生產(chǎn)和存儲費用就完全由完全由u0，un決定。對某一個周期決定。對某一個周期k，如果這個周期，如果這個周期開始時有庫存量開始時有庫存量uk-1，要求結(jié)束時有庫存量，要求

14、結(jié)束時有庫存量uk，那么，那么它的生產(chǎn)數(shù)量它的生產(chǎn)數(shù)量xk=sk+uk-uk-1，sk是這個周期的商品需求是這個周期的商品需求量，所以它的生產(chǎn)和存儲費為量，所以它的生產(chǎn)和存儲費為f(xk)+16 uk-1，其中，其中3015,300120150 ,100)(xxxxxf第第18頁頁續(xù)續(xù) (1) 用用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+

15、u1-u0, 讓讓k=2,3,6，求出，求出F6(u0,u6)，就得到問題的解，就得到問題的解16)(),(min),(1101001kkkkukkuxfuuFuuFk0110116)(),(uxfuuF第第19頁頁確定性的定期多階段決策問題確定性的定期多階段決策問題q旅行售貨員問題旅行售貨員問題 q多階段資源分配問題多階段資源分配問題q用最優(yōu)化原理解某些非線性規(guī)劃問題用最優(yōu)化原理解某些非線性規(guī)劃問題 q排序排序q最優(yōu)排序法最優(yōu)排序法第第20頁頁旅行售貨員問題旅行售貨員問題 旅行售貨員問題是圖論中一個著名問題，就是在網(wǎng)絡(luò)旅行售貨員問題是圖論中一個著名問題，就是在網(wǎng)絡(luò)N上找一條從上找一條從v0點

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

17、是還沒有經(jīng)過的點集合。在是還沒有經(jīng)過的點集合。在狀態(tài)（狀態(tài)（vi,V）的決策集合中，取決策）的決策集合中，取決策vjV，獲得的效益是，獲得的效益是vi到到vj的距離的距離dij，轉(zhuǎn)入下一個狀態(tài)（，轉(zhuǎn)入下一個狀態(tài)（vj,Vvj），現(xiàn)在用），現(xiàn)在用最優(yōu)化原理來找遞推公式。最優(yōu)化原理來找遞推公式。第第21頁頁續(xù)續(xù) (1) 用用fk(vi,V)表示從表示從vi點出發(fā)，經(jīng)過點出發(fā)，經(jīng)過V中的點各一次，中的點各一次，最后回到最后回到v0點的最短路程，點的最短路程，V是一個頂點集合，是一個頂點集合，|V|=k，dij是是vi到到vj的弧長，則的弧長，則001),(, 2 , 1),(min),(iijjki

18、jVvikdvfnkvVvfdVvfj第第22頁頁多階段資源分配問題多階段資源分配問題下面討論有限資源分配問題，它的遞推公式是：下面討論有限資源分配問題，它的遞推公式是： 一般情況下，一般情況下，g(y)，g(y)是很復(fù)雜的函數(shù)時，這個問題的是很復(fù)雜的函數(shù)時，這個問題的解不容易找。當(dāng)解不容易找。當(dāng)g(y)，g(y)為凸函數(shù)，且為凸函數(shù)，且h(0)=g(0)=0時，可以證明在每個階段上時，可以證明在每個階段上y的最優(yōu)決策總是取其端的最優(yōu)決策總是取其端點的值。點的值。 )()(max)(2),()()(max)(0110yxhygxfkyxbayfyxhygxfxykxyk第第23頁頁續(xù)續(xù) (1)

19、引理引理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ù)，則 F(x)=max F1(x),F2(X) 也是也是x的凸函數(shù)。的凸函數(shù)。第第24頁頁續(xù)續(xù) (2)定理定理5.2.1 設(shè)設(shè)g(y)，g(y)是凸函數(shù)，且是凸函數(shù)，且h(0)=g(0)=0，則，則n階階段資源分配問題的最優(yōu)策略段資源分配問題的最優(yōu)策略y在每個階段總?cè)≡诿總€階段總?cè)?yx的短的短點的值，并且點的值，并且)(),(max)()()(),()(max)(11

20、1xgxhxfaxfxgbxfxhxfkkk第第25頁頁用最優(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第第26頁頁續(xù)續(xù) (1) 假設(shè)每個假設(shè)每個gi(xi)在內(nèi)連續(xù)，顯然在內(nèi)連

21、續(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ù)量物資階段決策問題每階段投入一定數(shù)量物資與某種生產(chǎn)。第與某種生產(chǎn)。第i階段初還有資源階段初還有資源y，用，用y表示狀表示狀態(tài)，投入態(tài)，投入i中生產(chǎn)的資源為中生產(chǎn)的資源為xi，(0 xi y)，還剩下資，還

22、剩下資源源y- xi，并獲得效益，并獲得效益gi(xi)。第第27頁頁續(xù)續(xù) (2) 用用fk(y)表示有資源表示有資源y投入于前投入于前k種生產(chǎn)方種生產(chǎn)方式所得到的最大收入。由最優(yōu)化原理式所得到的最大收入。由最優(yōu)化原理)(max)()()(max)(110101xgyfxyfxgyfyxkkkkyxkk第第28頁頁排排 序序 問問 題題 設(shè)有設(shè)有n個工件需要在機(jī)床個工件需要在機(jī)床A,B上加工上加工,每個工件都必每個工件都必須經(jīng)過先須經(jīng)過先A后后B的兩道加工工序的兩道加工工序,我們一號碼我們一號碼i(1in)表表示第示第i個工件個工件,以以Ai,Bi分別表示工件分別表示工件i在在A,B上的加工時

23、上的加工時間間,由于工序的不同由于工序的不同,所用的時間也是不同的所用的時間也是不同的,因此因此,加工加工完這完這 個工件的總時間是排列順序的函數(shù)個工件的總時間是排列順序的函數(shù),現(xiàn)在的問題現(xiàn)在的問題是怎樣安排加工順序才使總時間最少是怎樣安排加工順序才使總時間最少? 用用(X,t)來描述狀態(tài)來描述狀態(tài),X表示在機(jī)床表示在機(jī)床A上等待加工的工上等待加工的工件集合件集合,就是說就是說,這是這是A已經(jīng)把已經(jīng)把X以外的工件全加工完了以外的工件全加工完了,準(zhǔn)備選擇準(zhǔn)備選擇X中某個工件加工中某個工件加工,t表示表示B還需時刻還需時刻t才能把才能把X以外的工件加工完以外的工件加工完.第第29頁頁續(xù)續(xù) (1) 在狀態(tài)在狀態(tài)(X,t),決策集合是工件集合決策集合是工件集合X,選定決策選定決策i屬屬于于X,就轉(zhuǎn)入新的狀態(tài)就轉(zhuǎn)