管理運籌學動態(tài)規(guī)劃課件

1、第9章 動態(tài)規(guī)劃7/26/20221課件教學目標與要求【教學目標】1. 理解下列基本概念：狀態(tài)變量，決策變量，策略，狀態(tài)轉移方程，指標函數(shù)和最優(yōu)值函數(shù)2. 理解動態(tài)規(guī)劃的基本方程和最優(yōu)化原理3. 理解動態(tài)規(guī)劃模型建立過程5. 掌握順序算法與逆序算法解題方法【知識結構】7/26/20222課件引例 馬車驛站問題124833538667863235AB2B1D2D1C3C2C4C1EA B C D E階段1階段2階段3階段44個階段EED1D2D1D2D1D2D1D2C2C3C4C1C2C3 1D1E1D2E2C4D1 C4D22C3D1 C3D22C2D1 C2D22C1D1C1D23B2C2B

2、2C3B2C43B1C1B1C2B1C3B1B22AB1AB2AB2B1C4C3C2C1D1D24321終點路線數(shù)可選路線起點階段一共有2321=12條不同的路線f(E)=0f(D1)=2f(D2)=1f(C1)=8f(C2)=5f(C3)=4f(C1)=5f(B1)=8f(B2)=11f(A)=13回顧分析過程:1.將分析對象劃分成4階段;2.每階段始點狀態(tài)與終點狀態(tài)有關,而不考慮始終點狀態(tài)如何形成(無記憶性);3.每階段各始點狀態(tài)為終點狀態(tài)與始點至終點距離之和的最小值(狀態(tài)轉移)這種最優(yōu)化方法稱為動態(tài)規(guī)劃, 由美國數(shù)學家貝爾曼等人于20世紀50年代創(chuàng)立.7/26/20223課件本章主要內(nèi)容

3、9.1 動態(tài)規(guī)劃的概念和原理9.1.1 動態(tài)規(guī)劃的基本概念9.1.2 動態(tài)規(guī)劃的最優(yōu)化原理9.2 動態(tài)規(guī)劃的模型和求解9.2.1 動態(tài)規(guī)劃模型的建立9.2.2 動態(tài)規(guī)劃問題的解法9.3 應用舉例案例1 資源分配問題案例2 設備負荷問題案例3 生產(chǎn)庫存問題案例4 背包問題本章小結7/26/20224課件9.1.1 動態(tài)規(guī)劃的基本概念1.階段:把所給問題的過程，恰當?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便能按一定的次序去求解。描述階段的變量稱為階段變量，常用k表示。導入案例中k=1,2,3,42.狀態(tài)變量:每個階段開始所處的自然狀況或客觀條件(用點集表示).如引例:第1階段的狀態(tài)就是起點A,記為s1=A;

4、第2階段有2個狀態(tài)B1,B2,記為s2=B1,B2;第3階段有4個狀態(tài)C1,C2,C3,C4,記為s3=C1,C2,C3,C4;第4階段有2個狀態(tài)D1,D2,記為s4=D1,D2;3.決策變量:在某一階段的某個狀態(tài)時的不同選擇,如引例中B1狀態(tài)下有3種選擇:B1C1,B1C2,B1C3這3種選擇構成了允許決策的集合。不同狀態(tài)下允許決策的集合也不同，故決策變量是狀態(tài)變量的函數(shù)，即xk(sk)D(sk)124833538667863235AB2B1D2D1C3C2C4C1E A B C D E階段1階段2階段3階段44個階段4.策略按順序排列的決策組成的集合，由過程的第k階段開始到終止狀態(tài)為止的過

5、程(或k子過程),k子過程的策略稱子策略，記為Pk,n(sk),即 Pk,n(sk)=xk(sk),xk+1(sk+1),xn(sn)當k=1時，即為全過程的一個策略。如引例中：DE，即4到5過程起始有2個狀態(tài)，D1和D2，因此有P4,5=D1E，D2E5.狀態(tài)轉移方程確定過程是由一個狀態(tài)到另一個狀態(tài)的演變過程。第k階段狀態(tài)變量值給定后，如果確定決策變量，第k+1階段狀態(tài)變量值就完全確定。即：sk+1=T(sk,xk)如引例中：若對AB1,AB2選擇了AB1,則s2=5,B1到C有3種選擇:B1C1、B1C2、B1C3，若選擇了B1C2,則s3=s2+d(B1,C2)=86.指標函數(shù)用來衡量所

6、實現(xiàn)過程優(yōu)劣的一種數(shù)量指標。其基本方程有加法和乘法兩種形式，通常加法形式用的較多，其公式為：7.邊界條件起始或終止條件。7/26/20225課件5.1.2 動態(tài)規(guī)劃的基本原理124833538667863235AB2B1D2D1C3C2C4C1EA B C D E階段1階段2階段3階段44個階段最優(yōu)化原理(Optimality principle) :最優(yōu)策略具備這樣的性質(zhì):無論初始狀態(tài)與初始決策如何,以后諸決策對以第一個決策所形成的狀態(tài)作為初始狀態(tài)的過程而言,必然構成最優(yōu)策策略.通俗地說:最優(yōu)策略的子策略也是最優(yōu)的.例如，在導入案例中，最優(yōu)策略是AB1C2D1E,最短距離為13,其子策略:B

7、1C2D1E, C2D1E, D1E也是最優(yōu)的。依據(jù)這一原理，從后往前推各階段最優(yōu)子過程，從而得到全程最優(yōu)過程。設f(i)表示從點i到終點E的最短距離,d(i,j)表示點i,j之間的距離.顯然f(E)=0,為該問題的邊界條件.k=4決策：D1Ek=3決策：D2E決策：C1D1決策：C2D1k=2決策：C3D2決策：C4D2決策：B1C2決策：B2C3k=1決策：AB1最短路線:AB1C2D1E最短路長:137/26/20226課件5.1.2 動態(tài)規(guī)劃的最優(yōu)化原理7/26/20227課件9.2.1 動態(tài)規(guī)劃模型的建立解 把生產(chǎn)第k種產(chǎn)品看成是第k階段，劃分為n個階段.設 sk表示第k階段初資源可

8、用量（狀態(tài)變量） xk表示分配給第k階段資源的數(shù)量（決策變量），顯然有： 允許決策集合 sk+1=sk-xk （狀態(tài)轉移方程） s1=a （邊界條件） 指標函數(shù)：若fk(sk)表示數(shù)量為sk資源分配給第k種產(chǎn)品時，從第k階段到第n階段總收益，則有：7/26/20228課件9.2.1 動態(tài)規(guī)劃模型的建立指標函數(shù)通常有兩種形式：加法形式和乘法形式。7/26/20229課件9.2.2 動態(tài)規(guī)劃問題的解法:逆序法最優(yōu)值函數(shù)f(k):從k階段到E的最短距離；階段指標函數(shù),即該階段選擇不同路線的距離。從后向前推。S1=AS2=B1,B2S3=C1,C2,C3,C4S4=D1,D2S5=Ef5(E)=0同理

9、 f4(D1)=2,f4(D2)=1同理 f3(C2)=5,f3(C3)=4,f3(c4)=5同理 f2(B2)=11124833538667863235AB2B1D2D1C3C2C4C1E A B C D E階段1階段2階段3階段47/26/202210課件9.2.2 動態(tài)規(guī)劃問題的解法:順序法124833538667863235AB2B1D2D1C3C2C4C1E A B C D E階段1階段2階段3階段4最優(yōu)值函數(shù)f(k):從A到k階段的最短距離；階段指標函數(shù),即該階段選擇不同路線的距離。從前向后推。S0=AS1=B1,B2S2=C1,C2,C3,C4S3=D1,D2S4=E最優(yōu)值函數(shù):

10、f0(A)=0f1(B1)=5,f2(B2)=3f2(C1)=7,f3(C2)=8,f3(C3)=10,f3(c4)=9f3(D1)=11,f4(D2)=137/26/202211課件案例1 資源分配問題5臺設備分配給3個工廠，盈利表如下，如何分配可使獲利最大？ 臺數(shù)工廠012345甲乙丙00045389711119111211111212分析 3個工廠看成3個階段.階段變量 k(k=1,2,3)；狀態(tài)變量 sk表示為分配給第k個工廠至第n個工廠的設備臺數(shù)；決策變量xk 表示分配給第k個工廠的設備臺數(shù)；則有sk+1=sk-xk；Pk(xk)表示為xk 臺設備分配到第k個工廠所得贏利值；fk(s

11、k)表示為 臺設備分配給第k個工廠至第n個工廠所得到的最大贏利值。則有:7/26/202212課件k=3 x3s3P3(x3)f3(s3)x3*0123450123450379111203791112012345k=2 x2s2P2(x2)+f3(s2-x2)f2(s2)x2*01234501234500+30+70+90+110+12 5+05+35+75+95+11 9+09+39+79+9 11+011+311+7 12+012+312+0059121618 0121，222，3 k=1 x1s1P1(x1)+f2(s1-x1)f1(s1)x1*01234550+184+168+1211

12、+911+511+0201，2，3012345甲乙丙00045389711119111211111212方案一:1,2,2方案二:2,1,2方案三:2,2,1方案四:3,2,07/26/202213課件案例2 設備負荷問題某種機器可在高低兩種不同的負荷下進行生產(chǎn)，設機器在高負荷下生產(chǎn)的產(chǎn)量函數(shù)為g=9x，其中x為投入生產(chǎn)的機器數(shù)量，季度完好率為a=0.65，在低負荷下生產(chǎn)的產(chǎn)量函數(shù)為h=4y，其中y為投入生產(chǎn)的機器數(shù)量，季度完好率為b=0.95。設資源擁有量100.解 4季度看成4階段sk第k季初擁有完好機器數(shù)xk第k季分配給高負荷機器數(shù),則低負荷分配數(shù)sk-xk下季度初完好機器數(shù)sk+1=0

13、.65xk+0.95(sk-xk)第k季產(chǎn)量vk=6xk+4(sk-xk)7/26/202214課件k=4f4 是x4 的增函數(shù),故最大值解為 x4*=s4,相應地有 f4(s4)=9s4k=3f3 是x3 的增函數(shù),故最大值解為 x3*=s3,相應地有 f3(s3)=14.85s37/26/202215課件k=2f2 是x2 的增函數(shù),故最大值解為 x2*=s2,相應地有 f2(s2)=18.6525s2k=1f1 是x1 的減函數(shù),故最大值解為 x1*=0,相應地有 f1(s1)=21.719875s1=2172反向推算，由s1=100，x1=0，知s2=95，x2=95， s3=61.7

14、5，x3=61.75，s4=40.14，x4=40.14，s5=26.09。即第1季度設備100%全部分配給低負荷第2季度初完好設備為95%，全部分配給高負荷第3季度完好設備為61.75%，全部分配給高負荷第4季度完好設備為40.14%，全部分配給高負荷。全年結束后，設備完好率為26.09%.最大產(chǎn)量2172。7/26/202216課件Lingo程序model:sets:JD/1.4/:s,x,v;!定義狀態(tài)變量、決策變量和指標函數(shù);ZB/1.5/:f;!定義最優(yōu)值函數(shù);endsetsf(5)=0;!初始化最優(yōu)值函數(shù);s(1)=100;!初始化狀態(tài)變量;for(jd:x=s);!決策變量取值限

15、制;for(jd(k)|k#lt#4:s(k+1)=0.65*x(k)+0.95*(s(k)-x(k););!狀態(tài)轉移方程;for(jd(k):v(k)=9*x(k)+4*(s(k)-x(k);!指標函數(shù)表達式;for(zb(k)|k#lt#5:f(k)=v(k)+f(k+1););!基本方程;max=f(1);!目標;end7/26/202217課件案例3 生產(chǎn)庫存問題7/26/202218課件案例3 生產(chǎn)庫存問題7/26/202219課件案例3 生產(chǎn)庫存問題7/26/202220課件案例3 生產(chǎn)庫存問題階段12345需求/dk23243逆推: f5 =26.5, s5=0, x5*=0 或

16、 3s4=3 x4*=6s4=0 x4*=0s3=1 s3=4 x3*=0 或 3x3*=6s2=3 s2=0 s2=0 x2*=6 x2*=0 x2*=0s1=0 x1*=2s1=3 x1*=5s1=3 x1*=57/26/202221課件案例4 背包問題7/26/202222課件案例4 背包問題7/26/202223課件案例4 背包問題背包重345價值456最優(yōu)方案:依次裝2,1,0個最大價值:137/26/202224課件本章小結本章介紹了動態(tài)規(guī)劃的基本概念、基本原理和幾種典型的應用問題。要求1）理解動態(tài)規(guī)劃的核心概念狀態(tài)與狀態(tài)變量、決策與決策變量、策略、狀態(tài)轉移方程、指標函數(shù)和最優(yōu)值函數(shù)。2）理解動態(tài)規(guī)劃的最