管理運籌學(xué)課件第9章動態(tài)規(guī)劃

1、第9章 動態(tài)規(guī)劃,課件,2,2020/8/16,教學(xué)目標(biāo)與要求,【教學(xué)目標(biāo)】 1. 理解下列基本概念：狀態(tài)變量，決策變量，策略，狀態(tài)轉(zhuǎn)移方程，指標(biāo)函數(shù)和最優(yōu)值函數(shù) 2. 理解動態(tài)規(guī)劃的基本方程和最優(yōu)化原理 3. 理解動態(tài)規(guī)劃模型建立過程 5. 掌握順序算法與逆序算法解題方法 【知識結(jié)構(gòu)】,課件,3,2020/8/16,引例 馬車驛站問題,E,E,D1D2,D1D2,D1D2,D1D2,C2C3C4,C1C2C3,1,D1E,1,D2E,2,C4D1 C4D2,2,C3D1 C3D2,2,C2D1 C2D2,2,C1D1C1D2,3,B2C2B2C3B2C4,3,B1C1B1C2B1C3,B1B

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

3、.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 應(yīng)用舉例 案例1 資源分配問題 案例2 設(shè)備負(fù)荷問題 案例3 生產(chǎn)庫存問題 案例4 背包問題 本章小結(jié),課件,5,2020/8/16,9.1.1 動態(tài)規(guī)劃的基本概念,1.階段: 把所給問題的過程，恰當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便能按一定的次序去求解。描述階段的變量稱為階段變量，常用k表示。導(dǎo)入案例中k=1,2,3,4,2.狀態(tài)變量: 每個階段開始所處的自然狀況或客觀條件(用點集表示).如引例:第1階段的狀態(tài)就是起點A,記為s1=A;第2階段有2個狀態(tài)B1,B

4、2,記為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種選擇構(gòu)成了允許決策的集合。不同狀態(tài)下允許決策的集合也不同，故決策變量是狀態(tài)變量的函數(shù)，即xk(sk)D(sk),4.策略 按順序排列的決策組成的集合，由過程的第k階段開始到終止?fàn)顟B(tài)為止的過程(或k子過程),k子過程的策略稱子策略，記為Pk,n(sk),即 Pk,n(sk)=xk(sk),xk+1(sk+1),xn(sn) 當(dāng)k=

5、1時，即為全過程的一個策略。如引例中：DE，即4到5過程起始有2個狀態(tài)，D1和D2，因此有P4,5=D1E，D2E,5.狀態(tài)轉(zhuǎn)移方程 確定過程是由一個狀態(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)=8,6.指標(biāo)函數(shù) 用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)。其基本方程有加法和乘法兩種形式，通常加法形式用的較多，其公式為：,7.邊界條件 起始或終止條件。,課件

6、,6,2020/8/16,5.1.2 動態(tài)規(guī)劃的基本原理,最優(yōu)化原理(Optimality principle) : 最優(yōu)策略具備這樣的性質(zhì):無論初始狀態(tài)與初始決策如何,以后諸決策對以第一個決策所形成的狀態(tài)作為初始狀態(tài)的過程而言,必然構(gòu)成最優(yōu)策策略.通俗地說:最優(yōu)策略的子策略也是最優(yōu)的. 例如，在導(dǎo)入案例中，最優(yōu)策略是AB1C2D1E,最短距離為13,其子策略:B1C2D1E, C2D1E, D1E也是最優(yōu)的。 依據(jù)這一原理，從后往前推各階段最優(yōu)子過程，從而得到全程最優(yōu)過程。,設(shè)f(i)表示從點i到終點E的最短距離,d(i,j)表示點i,j之間的距離. 顯然f(E)=0,為該問題的邊界條件.,

7、k=4,決策：D1E,k=3,決策：D2E,決策：C1D1,決策：C2D1,k=2,決策：C3D2,決策：C4D2,決策：B1C2,決策：B2C3,k=1,決策：AB1,最短路線:AB1C2D1E 最短路長:13,課件,7,2020/8/16,5.1.2 動態(tài)規(guī)劃的最優(yōu)化原理,課件,8,2020/8/16,9.2.1 動態(tài)規(guī)劃模型的建立,解 把生產(chǎn)第k種產(chǎn)品看成是第k階段，劃分為n個階段. 設(shè) sk表示第k階段初資源可用量（狀態(tài)變量） xk表示分配給第k階段資源的數(shù)量（決策變量），顯然有： 允許決策集合 sk+1=sk-xk （狀態(tài)轉(zhuǎn)移方程） s1=a （邊界條件） 指標(biāo)函數(shù)： 若fk(sk)

8、表示數(shù)量為sk資源分配給第k種產(chǎn)品時，從第k階段到第n階段總收益，則有：,課件,9,2020/8/16,9.2.1 動態(tài)規(guī)劃模型的建立,指標(biāo)函數(shù)通常有兩種形式：加法形式和乘法形式。,課件,10,2020/8/16,9.2.2 動態(tài)規(guī)劃問題的解法:逆序法,最優(yōu)值函數(shù)f(k):從k階段到E的最短距離；階段指標(biāo)函數(shù),即該階段選擇不同路線的距離。從后向前推。,S1=A S2=B1,B2 S3=C1,C2,C3,C4 S4=D1,D2 S5=E,f5(E)=0 同理 f4(D1)=2,f4(D2)=1 同理 f3(C2)=5,f3(C3)=4,f3(c4)=5 同理 f2(B2)=11,課件,11,20

9、20/8/16,9.2.2 動態(tài)規(guī)劃問題的解法:順序法,最優(yōu)值函數(shù)f(k):從A到k階段的最短距離；階段指標(biāo)函數(shù),即該階段選擇不同路線的距離。從前向后推。,S0=A S1=B1,B2 S2=C1,C2,C3,C4 S3=D1,D2 S4=E,最優(yōu)值函數(shù): f0(A)=0 f1(B1)=5,f2(B2)=3 f2(C1)=7,f3(C2)=8,f3(C3)=10,f3(c4)=9 f3(D1)=11,f4(D2)=13,課件,12,2020/8/16,案例1 資源分配問題,5臺設(shè)備分配給3個工廠，盈利表如下，如何分配可使獲利最大？,分析 3個工廠看成3個階段. 階段變量 k(k=1,2,3)；

10、狀態(tài)變量 sk表示為分配給第k個工廠至第n個工廠的設(shè)備臺數(shù)； 決策變量xk 表示分配給第k個工廠的設(shè)備臺數(shù)； 則有sk+1=sk-xk； Pk(xk)表示為xk 臺設(shè)備分配到第k個工廠所得贏利值； fk(sk)表示為 臺設(shè)備分配給第k個工廠至第n個工廠所得到的最大贏利值。則有:,k=3,k=2,k=1,方案一:1,2,2,方案二:2,1,2,方案三:2,2,1,方案四:3,2,0,課件,14,2020/8/16,案例2 設(shè)備負(fù)荷問題,某種機器可在高低兩種不同的負(fù)荷下進行生產(chǎn)，設(shè)機器在高負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為g=9x，其中x為投入生產(chǎn)的機器數(shù)量，季度完好率為a=0.65，在低負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)

11、為h=4y，其中y為投入生產(chǎn)的機器數(shù)量，季度完好率為b=0.95。設(shè)資源擁有量100. 解 4季度看成4階段sk第k季初擁有完好機器數(shù)xk第k季分配給高負(fù)荷機器數(shù),則低負(fù)荷分配數(shù)sk-xk下季度初完好機器數(shù)sk+1=0.65xk+0.95(sk-xk)第k季產(chǎn)量vk=6xk+4(sk-xk),課件,15,2020/8/16,k=4,f4 是x4 的增函數(shù),故最大值解為 x4*=s4,相應(yīng)地有 f4(s4)=9s4,k=3,f3 是x3 的增函數(shù),故最大值解為 x3*=s3,相應(yīng)地有 f3(s3)=14.85s3,課件,16,2020/8/16,k=2,f2 是x2 的增函數(shù),故最大值解為 x2

12、*=s2,相應(yīng)地有 f2(s2)=18.6525s2,k=1,f1 是x1 的減函數(shù),故最大值解為 x1*=0,相應(yīng)地有 f1(s1)=21.719875s1=2172,反向推算，由s1=100，x1=0，知s2=95，x2=95， s3=61.75，x3=61.75，s4=40.14，x4=40.14，s5=26.09。 即第1季度設(shè)備100%全部分配給低負(fù)荷第2季度初完好設(shè)備為95%，全部分配給高負(fù)荷第3季度完好設(shè)備為61.75%，全部分配給高負(fù)荷第4季度完好設(shè)備為40.14%，全部分配給高負(fù)荷。全年結(jié)束后，設(shè)備完好率為26.09%.最大產(chǎn)量2172。,課件,17,2020/8/16,Li

13、ngo程序,model: sets: JD/1.4/:s,x,v;!定義狀態(tài)變量、決策變量和指標(biāo)函數(shù); ZB/1.5/:f;!定義最優(yōu)值函數(shù); endsets f(5)=0;!初始化最優(yōu)值函數(shù); s(1)=100;!初始化狀態(tài)變量; for(jd:x=s);!決策變量取值限制; for(jd(k)|k#lt#4:s(k+1)=0.65*x(k)+0.95*(s(k)-x(k););!狀態(tài)轉(zhuǎn)移方程; for(jd(k):v(k)=9*x(k)+4*(s(k)-x(k);!指標(biāo)函數(shù)表達(dá)式; for(zb(k)|k#lt#5:f(k)=v(k)+f(k+1););!基本方程; max=f(1);!目

14、標(biāo); end,課件,18,2020/8/16,案例3 生產(chǎn)庫存問題,課件,19,2020/8/16,案例3 生產(chǎn)庫存問題,課件,20,2020/8/16,案例3 生產(chǎn)庫存問題,課件,21,2020/8/16,案例3 生產(chǎn)庫存問題,逆推: f5 =26.5, s5=0, x5*=0 或 3,s4=3 ,x4*=6,s4=0 ,x4*=0,s3=1 ,s3=4 ,x3*=0 或 3,x3*=6,s2=3 ,s2=0 ,s2=0 ,x2*=6 ,x2*=0,x2*=0,s1=0 ,x1*=2,s1=3 ,x1*=5,s1=3 ,x1*=5,課件,22,2020/8/16,案例4 背包問題,課件,23,2020/8/16,案例4 背包問題,課件,24,2020/8/16,案例4 背包問題,最優(yōu)方案:依次裝2,1,0個 最大價值:13,課件,25,2020/8/16,本章小結(jié),本章介紹了動態(tài)規(guī)劃的基本概念、基本原理和幾種典型的應(yīng)用問題。要求 1）理解動態(tài)規(guī)劃的核心概念 狀態(tài)與狀態(tài)變量、決策與決策變量、策略、狀態(tài)轉(zhuǎn)移方程、指標(biāo)函數(shù)和最優(yōu)值函數(shù)。 2）理解動態(tài)規(guī)劃的最優(yōu)化原理：一個最優(yōu)策略的子策略總是最優(yōu)的