第9章動態規劃2/6/20231課件教學目標與要求【教學目標】1.理解下列基本概念：狀態變量，決策變量，策略，狀態轉移方程，指標函數和最優值函數2.理解動態規劃的基本方程和最優化原理3.理解動態規劃模型建立過程5.掌握順序算法與逆序算法解題方法【知識結構】2/6/20232課件[引例]馬車驛站問題124833538667863235AB2B1D2D1C3C2C4C1EA—B—C—D—E階段1階段2階段3階段44個階段EED1

D2D1

D2D1

D2D1

D2C2

C3

C4C1

C2

C31D1E1D2E2C4D1

C4D22C3D1

C3D22C2D1

C2D22C1D1

C1D23B2C2

B2C3

B2C43B1C1

B1C2

B1C3B1

B22AB1

AB2AB2B1C4C3C2C1D1D24321終點路線數可選路線起點階段一共有2×3×2×1=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.每階段始點狀態與終點狀態有關,而不考慮始終點狀態如何形成(無記憶性);3.每階段各始點狀態為終點狀態與始點至終點距離之和的最小值(狀態轉移)這種最優化方法稱為動態規劃,由美國數學家貝爾曼等人于20世紀50年代創立.2/6/20233課件9.1.1動態規劃的基本概念1.階段:把所給問題的過程，恰當地分為若干個相互聯系的階段，以便能按一定的次序去求解。描述階段的變量稱為階段變量，常用k表示。[導入案例]中k=1,2,3,42.狀態變量:每個階段開始所處的自然狀況或客觀條件(用點集表示).如引例:

第1階段的狀態就是起點A,記為s1={A};

第2階段有2個狀態{B1,B2},記為s2={B1,B2};

第3階段有4個狀態{C1,C2,C3,C4},記為s3={C1,C2,C3,C4};

第4階段有2個狀態{D1,D2},記為s4={D1,D2};3.決策變量:在某一階段的某個狀態時的不同選擇,如引例中B1狀態下有3種選擇:

B1—C1,B1—C2,B1—C3

這3種選擇構成了允許決策的集合。不同狀態下允許決策的集合也不同，故決策變量是狀態變量的函數，即xk(sk)∈D(sk)124833538667863235AB2B1D2D1C3C2C4C1EA—B—C—D—E階段1階段2階段3階段44個階段4.策略按順序排列的決策組成的集合，由過程的第k階段開始到終止狀態為止的過程(或k子過程),k子過程的策略稱子策略，記為Pk,n(sk),即Pk,n(sk)={xk(sk),xk+1(sk+1),…,xn(sn)}當k=1時，即為全過程的一個策略。如引例中：D—E，即4到5過程起始有2個狀態，D1和D2，因此有P4,5={D1—E，D2—E}5.狀態轉移方程確定過程是由一個狀態到另一個狀態的演變過程。第k階段狀態變量值給定后，如果確定決策變量，第k+1階段狀態變量值就完全確定。即：sk+1=T(sk,xk)如引例中：若對A—B1,A—B2選擇了A—B1,則s2=5,B1到C有3種選擇:B1—C1、B1—C2、B1—C3，若選擇了B1—C2,則s3=s2+d(B1,C2)=86.指標函數用來衡量所實現過程優劣的一種數量指標。其基本方程有加法和乘法兩種形式，通常加法形式用的較多，其公式為：7.邊界條件起始或終止條件。2/6/20235課件5.1.2動態規劃的基本原理124833538667863235AB2B1D2D1C3C2C4C1EA—B—C—D—E階段1階段2階段3階段44個階段最優化原理

(Optimalityprinciple):最優策略具備這樣的性質:無論初始狀態與初始決策如何,以后諸決策對以第一個決策所形成的狀態作為初始狀態的過程而言,必然構成最優策策略.通俗地說:最優策略的子策略也是最優的.例如，在導入案例中，最優策略是A—B1—C2—D1—E,最短距離為13,其子策略:B1—C2—D1—E,C2—D1—E,D1—E也是最優的。依據這一原理，從后往前推各階段最優子過程，從而得到全程最優過程。設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最短路長:132/6/20236課件5.1.2動態規劃的最優化原理2/6/20237課件9.2.1動態規劃模型的建立指標函數通常有兩種形式：加法形式和乘法形式。2/6/20239課件9.2.2動態規劃問題的解法:逆序法最優值函數f(k):從k階段到E的最短距離；階段指標函數,即該階段選擇不同路線的距離。從后向前推。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)=11124833538667863235AB2B1D2D1C3C2C4C1EA—B—C—D—E階段1階段2階段3階段42/6/202310課件9.2.2動態規劃問題的解法:順序法124833538667863235AB2B1D2D1C3C2C4C1EA—B—C—D—E階段1階段2階段3階段4最優值函數f(k):從A到k階段的最短距離；階段指標函數,即該階段選擇不同路線的距離。從前向后推。S0={A}S1={B1,B2}S2={C1,C2,C3,C4}S3={D1,D2}S4={E}最優值函數:f0(A)=0f1(B1)=5,f2(B2)=3f2(C1)=7,f3(C2)=8,f3(C3)=10,f3(c4)=9f3(D1)=11,f4(D2)=132/6/202311課件k=3x3s3P3(x3)f3(s3)x3*0123450123450379111203791112012345k=2x2s2P2(x2)+f3(s2-x2)f2(s2)x2*01234501234500+30+70+90+110+125+05+35+75+95+119+09+39+79+911+011+311+712+012+312+00591216180121，222，3k=1x1s1P1(x1)+f2(s1-x1)f1(s1)x1*01234550+184+168+1211+911+511+0201，2，3012345甲乙丙00045389711119111211111212方案一:1,2,2方案二:2,1,2方案三:2,2,1方案四:3,2,02/6/202313課件案例2設備負荷問題某種機器可在高低兩種不同的負荷下進行生產，設機器在高負荷下生產的產量函數為g=9x，其中x為投入生產的機器數量，季度完好率為a=0.65，在低負荷下生產的產量函數為h=4y，其中y為投入生產的機器數量，季度完好率為b=0.95。設資源擁有量100.解4季度看成4階段

sk第k季初擁有完好機器數

xk第k季分配給高負荷機器數,則低負荷分配數sk-xk

下季度初完好機器數sk+1=0.65xk+0.95(sk-xk)

第k季產量vk=6xk+4(sk-xk)2/6/202314課件k=4f4是x4的增函數,故最大值解為x4*=s4,相應地有f4(s4)=9s4k=3f3是x3的增函數,故最大值解為x3*=s3,相應地有f3(s3)=14.85s32/6/202315課件Lingo程序model:

sets: JD/1..4/:s,x,v; !定義狀態變量、決策變量和指標函數; ZB/1..5/:f; !定義最優值函數;

endsets f(5)=0; !初始化最優值函數; s(1)=100; !初始化狀態變量;

@for(jd:x<=s); !決策變量取值限制;

@for(jd(k)|k#lt#4:s(k+1)=0.65*x(k)+0.95*(s(k)-x(k));); !狀態轉移方程;

@for(jd(k):v(k)=9*x(k)+4*(s(k)-x(k))); !指標函數表達式;

@for(zb(k)|k#lt#5:f(k)=v(k)+f(k+1);); !基本方程;

max=f(1);

!目標;end2/6/202317課件案例3生產庫存問題2/6/202318課件案例3生產庫存問題2/6/202319課件案例3生產庫存問題階段12345需求/dk23243逆推:f5=26.5,s5=0,x5*=0或3s4=3↑x4*=6←s4=0↑→x4*=0s3=1↑s3=4↑x3*=0或3←→x3*=6s2=3↑s2=0↑s2=0↑x2*=6←→x2*=0→x2*=0s1=0↑x1*=2←s1=3↑→x1*=5s1=3↑→x1*=52/6/202321課件案例4背包問題2/6/202322課件案例4背包問題2/6/202323課件本章小結本章介紹了動態規劃的基本概念、基本原理和幾種典型的應用問題。要求1）理解動態規劃的核心概念狀態與狀態變量、決策與決策變量、策略、狀態轉移方程、指標函