最優化原理與動態規劃的數學模型第一頁，共三十六頁，2022年，8月28日BACDEFG本例中分為k=1,2,3,4,5,6

，共六個階段。(1)階段將所給問題的過程，按時間或空間特征分解成若干相互聯系的階段，以便按次序去求每個階段的解，常用字母k表示階段變量.第二頁，共三十六頁，2022年，8月28日(2)狀態各階段開始時的客觀條件叫做狀態。描述各階段狀態的變量稱為狀態變量，常用sk表示第k階段的狀態變量，狀態變量sk的取值集合稱為狀態集合，用Sk表示。無后效性：當某階段狀態給定以后，在這階段以后過程的發展不受這段以前的各階段的影響。即當前的階段是過去歷史的一個完整總結，過程的過去歷史只能通過當前狀態去影響它未來的發展。第三頁，共三十六頁，2022年，8月28日狀態變量可以是一個數或一個向量。在本例中s2可取B1,B2,或將Bi定義為i(i=1,2)，則s2=1,2，則S2={1,2}S1={A}S2={B1,B2}S3={C1,C2,C3,C4}S4={D1,D2,D3}S5={E1,E2,E3}S6={F1,F2}第四頁，共三十六頁，2022年，8月28日(3)決策和策略

當一個階段的狀態確定后，可以作出各種選擇從而演變到下一階段的某個狀態，這種選擇手段稱為決策，在最優控制問題中也稱為控制。

描述決策的變量稱決策變量，變量允許取值的范圍稱允許決策集合。用uk(sk)表示第k階段處于狀態sk時的決策變量，它是

sk的函數，用Dk(sk)表示sk的允許決策集合。決策變量簡稱決策。第五頁，共三十六頁，2022年，8月28日由第k個狀態sk開始到終止狀態的后部子過程的策略記作類似地，由第k到第j階段的子過程的策略記作可供選擇的策略有一定的范圍，稱為允許策略集合，用表示決策組成的序列稱為策略。由初始狀態s1開始的全過程的策略記作第六頁，共三十六頁，2022年，8月28日

在本例中，從第二階段的狀態B1出發，可選擇下一段的C1,C2,C3，即允許決策集合為。

D2(B1)={C1,C2,C3}如果決定選擇C3則可表示為：

u2(B1)=C3表示一個策略第七頁，共三十六頁，2022年，8月28日(4)狀態轉移方程

在確定性過程中，一旦某階段的狀態和決策為已知，下階段的狀態便完全確定。用狀態轉移方程表示這種演變規律，寫作本例中狀態轉移方程：(5)指標函數用于衡量所選定策略優劣的數量指標稱為指標函數.第八頁，共三十六頁，2022年，8月28日階段指標函數：指第k階段，從狀態sk出發，采取決策uk時的效益，用d(sk,uk)表示。過程指標函數：是定義在全過程和后部子過程上確定的數量函數。一個n段決策過程,從1到n叫作問題的全過程；對于任意一個給定的k,從第k到n段的過程稱為全過程的一個后部子過程.V1,n(s1,p1,n)表示在第1階段，狀態為s1，采用策略p1,n時，原過程的指標函數值；Vk,n(sk,pk,n)表示在第k階段，狀態為sk，采用策略pk,n時，后部子過程的指標函數值。第九頁，共三十六頁，2022年，8月28日fk(sk)與Vk,n(sk,pk,n)間的關系為：當k=1時f1(s1)就是從初始狀態到全過程的整體最優函數.其中opt可根據具體情況取max或min

指標函數的最優值稱為最優指標函數，記為fk(sk)，表示從第k階段狀態sk采用最優策略p*k,n到過程中止時的最佳效益。第十頁，共三十六頁，2022年，8月28日本例中，指標函數是距離，如第二階段，階段指標：狀態為B1時d(B1,C2)表示由B1出發采用決策到下一段C2點的兩點距離；過程指標：V2,6(B1)表示從B1到G

的距離，f2(B1)則表示從B1到G的最短距離。第十一頁，共三十六頁，2022年，8月28日三、基本思想與最優化原理從例4的求解過程說明動態規劃的基本思想：例4

最短路問題如圖所示，給定一個線路網絡圖，要從A地向F地鋪設一條輸油管道，各點間連線上的數字表示距離，問應選擇什么路線，可使總距離最短？AB1B2C1C2C3D1D2D3E1E2F48544665333332482C47785451第十二頁，共三十六頁，2022年，8月28日AB1B2C1C2C3D1D2D3E1E2F48544665333332482C47785451第一步：從k=5開始，狀態變量s5可取兩種狀態E1,E2，它們到F點的路長分別為4,3。即第十三頁，共三十六頁，2022年，8月28日AB1B2C1C2C3D1D2D3E1E2F48544665333332482C47785451第二步：k=4時，狀態變量s4可取三個值D1,D2,D3，這是經過中途點到達終點F的兩級決策問題，從D1到F有兩條路線，比較取最短者此時從D1到F的最短路徑：相應決策：第十四頁，共三十六頁，2022年，8月28日AB1B2C1C2C3D1D2D3E1E2F4844665333332482C47785451同理，從D2到F有兩條路線，比較取最短者此時從D2到F的最短路徑：相應決策：第十五頁，共三十六頁，2022年，8月28日AB1B2C1C2C3D1D2D3E1E2F484465333332482C47785451同理，從D3到F有兩條路線，比較取最短者此時從D3到F的最短路徑：相應決策：第十六頁，共三十六頁，2022年，8月28日AB1B2C1C2C3D1D2D3E1E2F48446533332482C47785451同理，k=3時有：此時最短路徑：相應決策：第十七頁，共三十六頁，2022年，8月28日AB1B2C1C2C3D1D2D3E1E2F844653333242C477551同理，k=2時有：此時最短路徑：相應決策：第十八頁，共三十六頁，2022年，8月28日AB1B2C1C2C3D1D2D3E1E2F445333342C47551k=1時，只有一個狀態點A，則：此時最短路徑：相應決策：第十九頁，共三十六頁，2022年，8月28日在計算過程中可以看到，在求解的個階段，都利用了第k段和第k+1段的如下關系：這種遞推關系稱為動態規劃的基本方程，第二個方程稱為邊界條件。基本方程和邊界條件統稱為動態規劃的數學模型第二十頁，共三十六頁，2022年，8月28日AB1B2C1C2C3D1D2D3E1E2F44333342C47551在圖上直接計算的方法叫標號法。動態規劃較之于窮舉法的優點：一、計算量小二、計算結果不僅得到最短路線，而且得到了中間段任一點到F的最短路線第二十一頁，共三十六頁，2022年，8月28日動態規劃的基本思想：（1）將多階段決策過程劃分階段，恰當選取狀態變量、決策變量以及定義最優指標函數，從而把問題化成一族同類型的子問題。（2）求解時從邊界條件開始，逆（順）序逐段遞推尋優。在每一個子問題求解時，都要使用它前面已求出的子問題的最優結果，最后一個子問題的最優解，就是整個問題的最優解。（3）動態規劃方法是既把當前一段與未來各段分開，又把當前效益和未來效益結合起來考慮的一種最優化方法，因此每段的最優決策選取是從全局考慮的，與該段的最優選擇一般不同.第二十二頁，共三十六頁，2022年，8月28日最優化原理：作為整個過程的最優策略具有這樣的性質：“無論過去的狀態和決策如何，相對于前面的決策所形成的狀態而言，余下的決策序列必然構成最優子策略。”也就是說，一個最優策略的子策略也是最優的。動態規劃方法基于貝爾曼等人提出的最優化原理：第二十三頁，共三十六頁，2022年，8月28日練習：求從A到E的最短路徑路線為A→B2→C1→D1→E

，最短路徑為19AB2B1B3C1C3D1D2EC25214126101043121113965810521第二十四頁，共三十六頁，2022年，8月28日四、逆序解法與順序解法動態規劃求解的兩種基本方法：逆序解法（后向動態規劃方法）順序解法（向前動態規劃方法）逆序解法：從最后一段開始計算逐段前推，求得全過程的最優策略，稱為逆序解法。順序解法：從第一階段開始逐段向后遞推，計算后一階段要用到前一階段的尋優結果，最后一段計算的結果就是全過程的最優結果。再次以例4為例說明順序解法：第二十五頁，共三十六頁，2022年，8月28日AB1B2C1C2C3D1D2D3E1E2F48544665333332482C47785451k=0時，f0(s1)=f0(A)=0，為邊界條件k=1時，按f1(s2)的定義，有第二十六頁，共三十六頁，2022年，8月28日AB1B2C1C2C3D1D2D3E1E2F48544665333332482C47785451k=2時，狀態變量s3可取四個值C1,C2,C3,C4，從C1到B只有一條路線，故此時從C1到A的最短路徑：第二十七頁，共三十六頁，2022年，8月28日同理，從C2到A有兩條路線，比較取最短者此時從C2到A的最短路徑：AB1B2C1C2C3D1D2D3E1E2F48544665333332482C47785451第二十八頁，共三十六頁，2022年，8月28日同理，從C3到A有兩條路線，比較取最短者此時從C3到A的最短路徑：AB1B2C1C2C3D1D2D3E1E2F4544665333332482C47785451第二十九頁，共三十六頁，2022年，8月28日同理，從C4到A只有一條路線，此時從C4到A的最短路徑：AB1B2C1C2C3D1D2D3E1E2F4544665333332482C4785451第三十頁，共三十六頁，2022年，8月28日同理，k=3時有：此時最短路徑：相應決策：AB1B2C1C2C3D1D2D3E1E2F4544665333332482C4785451第三十一頁，共三十六頁，2022年，8月28日同理，k=4時有：此時最短路徑：相應決策：AB1B2C1C2C3D1D2D3E1E2F5446653333242C475451第三十二頁，共三十六頁，2022年，8月28日k=5時，只有一個狀態點F，則：此時最短路徑：AB1B2C1C2C3D1D2D3E1E2F4465333242C47545第三十三頁，共三十六頁，2022年，8月28日類似于逆序解法，寫出順序解法的遞推方程：這里一