《動態(tài)規(guī)劃》PPT課件.ppt

第五章動態(tài)規(guī)劃,1多階段決策過程及實例2動態(tài)規(guī)劃的基本概念和基本方程3動態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理4動態(tài)規(guī)劃與靜態(tài)規(guī)劃的關系,1多階段決策過程及實例,在實際中，有一類問題可以看作是一活動的過程，由于它的特殊性，可將過程分為若干個相互聯(lián)系階段，在每個階段都要依據(jù)該階段所處的狀態(tài)作出相應的決策，該決策又引起該階段狀態(tài)的轉移，決定了下一階段的狀態(tài)，當每個階段的決策確定后，由這些決策組成一個決策序列，即整個過程的一條活動路線。這類活動過程稱為多階段決策過程。這類問題稱為多階段決策問題。,1,2,n,狀態(tài),狀態(tài),狀態(tài),狀態(tài),狀態(tài),決策,決策,決策,例1最短路線問題如下圖，是一線路網(wǎng)絡，兩點之間連線上的數(shù)字表示兩點之間的距離（或費用）試求一條由A到G的鋪管線路，使總距離為最短（或總費用最?。?。,1,狀態(tài),狀態(tài),狀態(tài),狀態(tài),狀態(tài),決策,決策,決策,2,3,4,5,6,狀態(tài),狀態(tài),決策,決策,決策,B2,C3,D2,E3,F2,G,B2,C3,D2,E3,F2,G,A,V6,6=3,V1,6=24,V5,6=9,V4,6=11,V3,6=14,V2,6=21,V1,6=24,例2機器負荷分配問題某種機器可以在高低兩種不同負荷下進行生產(chǎn)。在高負荷下進行生產(chǎn)時，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機器數(shù)u的關系為,在低負荷下進行生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機器數(shù)u的關系為,1,狀態(tài),狀態(tài),狀態(tài),狀態(tài),狀態(tài),決策,決策,決策,2,3,4,5,狀態(tài),決策,決策,u1,u2,u3,u4,u5,s2,s3,s4,s5,s6,s1,設：,2動態(tài)規(guī)劃的基本概念和基本方程,2.1動態(tài)規(guī)劃的基本概念1.階段把過程依據(jù)一定的時間和空間特征恰當?shù)貏澐譃槿舾蓚€相互聯(lián)系的階段，以便利用動態(tài)規(guī)劃的方法求解。描述階段的變量稱為階段變量，用k表示。k=1，2，n2.狀態(tài)每個階段開始所處的自然狀況或客觀條件，稱為狀態(tài)。狀態(tài)是不可控的，是客觀存在的。描述狀態(tài)的變量稱為狀態(tài)變量，用sk表示。狀態(tài)變量可以是一個數(shù)或一個向量。狀態(tài)變量sk的取值范圍稱為可達狀態(tài)集合，用Sk表示。例1中，S3=C1,C2,C3,C4。,狀態(tài)變量的性質(zhì)（無后效性）如果某階段的狀態(tài)給定后，則該階段以后的過程的發(fā)展不受該階段以前各階段狀態(tài)的影響。即過程的過去歷史只能通過當前的狀態(tài)去影響未來的發(fā)展，當前的狀態(tài)是以往歷史的總結，以后發(fā)展的依據(jù)。這個性質(zhì)稱為無后效性（即馬爾科夫性）。無后效性的特征：在每個階段所作的決策只依據(jù)當前的狀態(tài)，和以往的狀態(tài)無關。在選取狀態(tài)變量時，一定要保證狀態(tài)變量具有無后效性，否則不能利用動態(tài)規(guī)劃的方法求解。,3.決策在每個階段所作的決定或選擇稱為決策或控制。決策依據(jù)與當前狀態(tài)，又決定下一階段的狀態(tài)。描述決策的變量稱為決策變量，用uk(sk)表示。他是狀態(tài)變量sk的函數(shù)。決策變量的取值范圍稱為容許決策集合，用Dk(sk)表示。在例1中D1(A)=B1,B2D2(B1)=C1,C2,C3，D2(B2)=C2,C3,C4D4(D1)=E2,E3在例2中D1(s1)=u1(s1)|0u1(s1)s1D2(s2)=u2(s2)|0u2(s2)s2Dk(sk)=uk(sk)|0uk(sk)sk,4.策略按一定順序排列的決策序列集合稱為策略。由過程的第k階段開始到終止狀態(tài)為止的過程，稱為問題的后部子過程（或稱為k子過程）。由k子過程的每個階段的決策函數(shù)組成的決策函數(shù)序列集合uk(sk),uk+1(sk+1),un(sn)稱為k子過程策略，簡稱為子策略，記為pk,n(sk)，即pk,n(sk)=uk(sk),uk+1(sk+1),un(sn)當k=1時,此決策函數(shù)序列稱為全過程的一個策略，簡稱為策略，記為p1,n(s1)。即p1,n(sk)=u1(s1),u2(s2),un(sn)策略的取值范圍稱為容許策略集合，用P表示。在P中,使指標函數(shù)達到最優(yōu)的策略稱為最優(yōu)策略。例1中，每一條線路就是一個策略，容許策略集合中有48個策略。A到G的最短線路就是最優(yōu)策略。,5.狀態(tài)轉移方程若給定第k個階段狀態(tài)變量sk的值，該階段的決策變量uk的值一經(jīng)確定，第k+1個階段的狀態(tài)變量sk+1的值也就完全確定了，即sk+1是sk和uk的函數(shù)，記為sk+1=Tk(sk,uk)該函數(shù)描述由第k個階段到第k+1個階段的狀態(tài)轉移規(guī)律,稱為狀態(tài)轉移方程。,例1中，狀態(tài)轉移方程為,例2中，狀態(tài)轉移方程為,6.指標函數(shù)和最優(yōu)值函數(shù)用來衡量過程和子過程（策略和子策略）優(yōu)劣的一種數(shù)量指標，稱為指標函數(shù)。它是定義在全過程和后部子過程上的數(shù)量函數(shù)，用Vk,n表示。即,指標函數(shù)的性質(zhì)：動態(tài)規(guī)劃中的指標函數(shù)應具有可分離性，并滿足地推關系，,常見指標函數(shù)的形式（1）過程和子過程的指標函數(shù)可分解為它所包含的階段的指標的和，即,（2）過程和子過程的指標函數(shù)可分解為它所包含的階段的指標的積，即,指標函數(shù)的最優(yōu)值稱為最優(yōu)值函數(shù)，記為,它表示最優(yōu)的k子策略p*k,n(sk)對應的指標函數(shù)值。,2.1動態(tài)規(guī)劃的基本思想和基本方程最短路線的特征：如果由起點A經(jīng)過P和H到達G是一條由A到G的最短路線，則由P到G的最短路線是PHG即最短路線的子線路是最短路線。,根據(jù)最短路線的特征，求A到G的最短路線，可以采用由后向前逐步遞推的方法，從最后一個階段開始，求出每個點到G的最短路線，最后出A到G的最短路線。,P1H1G,P2H2G,A,12,15,8,3,18,4,3,7,5,9,0,4,3,7,5,9,7,6,8,0,4,3,7,5,9,7,6,8,13,10,9,12,0,4,3,7,5,9,7,6,8,13,10,9,12,13,16,0,4,3,7,5,9,7,6,8,13,10,9,12,13,16,18,AB1C2D1E2F2G,最短路線為：,最優(yōu)策略為：,P*=,0,該題中，在求解過程中，利用了第k階段與第k+1階段之間的遞推關系：,一般情況，第k階段與第k+1階段之間的遞推關系式可表示為：,該遞推關系式稱為動態(tài)規(guī)劃的基本方程。,邊界條件,邊界條件,即,一般情況，第k階段與第k+1階段之間的遞推關系,動態(tài)規(guī)劃模型的建立步驟：1.將過程恰當?shù)貏澐譃殡A段；2.正確選擇狀態(tài)變量sk，既要描述過程的演變，又要滿足無后效性；3.確定決策變量uk及uk的容許決策集合Dk(sk);4.寫出狀態(tài)轉移方程sk+1=Tk(sk,uk);5.寫出指標函數(shù)Vk,n(sk,uk,sk+1,sn),應滿足：（1）是定義在全過程和后部子過程上數(shù)量函數(shù)；（2）具有可分離性，并滿足遞推關系；,（3）函數(shù)對于變量要嚴格單調(diào)；,6.寫出基本方程。,1,狀態(tài),狀態(tài),狀態(tài),狀態(tài),狀態(tài),決策,決策,2,n-1,n,狀態(tài),決策,決策,u1,u2,un-1,un,s2,s3,sn-1,sn,sn+1,s1,D(s1),D(s2),D(sn-1),D(sn),轉移方程,指標函數(shù),基本方程,4,3,7,5,9,7,6,8,13,10,9,12,13,16,18,0,16,15,13,13,15,11,13,6,8,10,9,5,3,0,18,13,標號法,3動態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理,動態(tài)規(guī)劃的最優(yōu)性原理最優(yōu)策略的子策略必是最優(yōu)策略。它是最優(yōu)策略的必要條件，而不是充要條件。,動態(tài)規(guī)劃的最優(yōu)性定理,4動態(tài)規(guī)劃與靜態(tài)規(guī)劃的關系,動態(tài)規(guī)劃、線性規(guī)劃和非線性規(guī)劃都是屬于數(shù)學規(guī)劃的范疇，本質(zhì)都是求極值問題，都是利用迭代法逐步求解。線性規(guī)劃迭代中的每一步是就問題的整體加以改善。動態(tài)規(guī)劃遞推中的每一步是問題局部最優(yōu)解向整體最優(yōu)解的靠近。對于某些靜態(tài)規(guī)劃問題可以引入某些因素，使之轉化為動態(tài)規(guī)劃問題。,靜態(tài)規(guī)劃問題,動態(tài)規(guī)劃問題,解：將該靜態(tài)規(guī)劃轉化為動態(tài)規(guī)劃如下：,1,狀態(tài),狀態(tài),狀態(tài),狀態(tài),決策,決策,決策,2,3,0x1s1,0x2s2,x3=s3,s2=s1-x1,s3=s2-x2,s4=s3-x3=0,s1=c,1,狀態(tài),狀態(tài),狀態(tài),狀態(tài),決策,決策,決策,2,3,0x1s1,0x2s2,X3=s3,s2=s1-x1,s3=s2-x2,s4=s3-x3=0,s1=c,解：將該靜態(tài)規(guī)劃轉化為動態(tài)規(guī)劃如下：,1,狀態(tài),狀態(tài),狀態(tài),狀態(tài),決策,決策,決策,2,3,0x1c-s1,0x2c-s2,x3=c-s3,s2=s1+x1,s3=s2+x2,s4=s3+x3=c,s1=0,1,狀態(tài),狀態(tài),狀態(tài),狀態(tài),決策,決策,決策,2,3,0x1c-s1,0x2c-s2,X3=c-s3,s2=s1+x1,s3=s2+x2,s4=s3+x3=c,s1=0,解