最優(yōu)化原理與動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型

最優(yōu)化原理與動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型第1頁，課件共36頁，創(chuàng)作于2023年2月BACDEFG本例中分為k=1,2,3,4,5,6

，共六個(gè)階段。(1)階段將所給問題的過程，按時(shí)間或空間特征分解成若干相互聯(lián)系的階段，以便按次序去求每個(gè)階段的解，常用字母k表示階段變量.第2頁，課件共36頁，創(chuàng)作于2023年2月(2)狀態(tài)各階段開始時(shí)的客觀條件叫做狀態(tài)。描述各階段狀態(tài)的變量稱為狀態(tài)變量，常用sk表示第k階段的狀態(tài)變量，狀態(tài)變量sk的取值集合稱為狀態(tài)集合，用Sk表示。無后效性：當(dāng)某階段狀態(tài)給定以后，在這階段以后過程的發(fā)展不受這段以前的各階段的影響。即當(dāng)前的階段是過去歷史的一個(gè)完整總結(jié)，過程的過去歷史只能通過當(dāng)前狀態(tài)去影響它未來的發(fā)展。第3頁，課件共36頁，創(chuàng)作于2023年2月狀態(tài)變量可以是一個(gè)數(shù)或一個(gè)向量。在本例中s2可取B1,B2,或?qū)i定義為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}第4頁，課件共36頁，創(chuàng)作于2023年2月(3)決策和策略

當(dāng)一個(gè)階段的狀態(tài)確定后，可以作出各種選擇從而演變到下一階段的某個(gè)狀態(tài)，這種選擇手段稱為決策，在最優(yōu)控制問題中也稱為控制。

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

sk的函數(shù)，用Dk(sk)表示sk的允許決策集合。決策變量簡稱決策。第5頁，課件共36頁，創(chuàng)作于2023年2月由第k個(gè)狀態(tài)sk開始到終止?fàn)顟B(tài)的后部子過程的策略記作類似地，由第k到第j階段的子過程的策略記作可供選擇的策略有一定的范圍，稱為允許策略集合，用表示決策組成的序列稱為策略。由初始狀態(tài)s1開始的全過程的策略記作第6頁，課件共36頁，創(chuàng)作于2023年2月

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

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

u2(B1)=C3表示一個(gè)策略第7頁，課件共36頁，創(chuàng)作于2023年2月(4)狀態(tài)轉(zhuǎn)移方程

在確定性過程中，一旦某階段的狀態(tài)和決策為已知，下階段的狀態(tài)便完全確定。用狀態(tài)轉(zhuǎn)移方程表示這種演變規(guī)律，寫作本例中狀態(tài)轉(zhuǎn)移方程：(5)指標(biāo)函數(shù)用于衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)稱為指標(biāo)函數(shù).第8頁，課件共36頁，創(chuàng)作于2023年2月階段指標(biāo)函數(shù)：指第k階段，從狀態(tài)sk出發(fā)，采取決策uk時(shí)的效益，用d(sk,uk)表示。過程指標(biāo)函數(shù)：是定義在全過程和后部子過程上確定的數(shù)量函數(shù)。一個(gè)n段決策過程,從1到n叫作問題的全過程；對于任意一個(gè)給定的k,從第k到n段的過程稱為全過程的一個(gè)后部子過程.V1,n(s1,p1,n)表示在第1階段，狀態(tài)為s1，采用策略p1,n時(shí)，原過程的指標(biāo)函數(shù)值；Vk,n(sk,pk,n)表示在第k階段，狀態(tài)為sk，采用策略pk,n時(shí)，后部子過程的指標(biāo)函數(shù)值。第9頁，課件共36頁，創(chuàng)作于2023年2月fk(sk)與Vk,n(sk,pk,n)間的關(guān)系為：當(dāng)k=1時(shí)f1(s1)就是從初始狀態(tài)到全過程的整體最優(yōu)函數(shù).其中opt可根據(jù)具體情況取max或min

指標(biāo)函數(shù)的最優(yōu)值稱為最優(yōu)指標(biāo)函數(shù)，記為fk(sk)，表示從第k階段狀態(tài)sk采用最優(yōu)策略p*k,n到過程中止時(shí)的最佳效益。第10頁，課件共36頁，創(chuàng)作于2023年2月本例中，指標(biāo)函數(shù)是距離，如第二階段，階段指標(biāo)：狀態(tài)為B1時(shí)d(B1,C2)表示由B1出發(fā)采用決策到下一段C2點(diǎn)的兩點(diǎn)距離；過程指標(biāo)：V2,6(B1)表示從B1到G

的距離，f2(B1)則表示從B1到G的最短距離。第11頁，課件共36頁，創(chuàng)作于2023年2月三、基本思想與最優(yōu)化原理從例4的求解過程說明動(dòng)態(tài)規(guī)劃的基本思想：例4

最短路問題如圖所示，給定一個(gè)線路網(wǎng)絡(luò)圖，要從A地向F地鋪設(shè)一條輸油管道，各點(diǎn)間連線上的數(shù)字表示距離，問應(yīng)選擇什么路線，可使總距離最短？AB1B2C1C2C3D1D2D3E1E2F48544665333332482C47785451第12頁，課件共36頁，創(chuàng)作于2023年2月AB1B2C1C2C3D1D2D3E1E2F48544665333332482C47785451第一步：從k=5開始，狀態(tài)變量s5可取兩種狀態(tài)E1,E2，它們到F點(diǎn)的路長分別為4,3。即第13頁，課件共36頁，創(chuàng)作于2023年2月AB1B2C1C2C3D1D2D3E1E2F48544665333332482C47785451第二步：k=4時(shí)，狀態(tài)變量s4可取三個(gè)值D1,D2,D3，這是經(jīng)過中途點(diǎn)到達(dá)終點(diǎn)F的兩級決策問題，從D1到F有兩條路線，比較取最短者此時(shí)從D1到F的最短路徑：相應(yīng)決策：第14頁，課件共36頁，創(chuàng)作于2023年2月AB1B2C1C2C3D1D2D3E1E2F4844665333332482C47785451同理，從D2到F有兩條路線，比較取最短者此時(shí)從D2到F的最短路徑：相應(yīng)決策：第15頁，課件共36頁，創(chuàng)作于2023年2月AB1B2C1C2C3D1D2D3E1E2F484465333332482C47785451同理，從D3到F有兩條路線，比較取最短者此時(shí)從D3到F的最短路徑：相應(yīng)決策：第16頁，課件共36頁，創(chuàng)作于2023年2月AB1B2C1C2C3D1D2D3E1E2F48446533332482C47785451同理，k=3時(shí)有：此時(shí)最短路徑：相應(yīng)決策：第17頁，課件共36頁，創(chuàng)作于2023年2月AB1B2C1C2C3D1D2D3E1E2F844653333242C477551同理，k=2時(shí)有：此時(shí)最短路徑：相應(yīng)決策：第18頁，課件共36頁，創(chuàng)作于2023年2月AB1B2C1C2C3D1D2D3E1E2F445333342C47551k=1時(shí)，只有一個(gè)狀態(tài)點(diǎn)A，則：此時(shí)最短路徑：相應(yīng)決策：第19頁，課件共36頁，創(chuàng)作于2023年2月在計(jì)算過程中可以看到，在求解的個(gè)階段，都利用了第k段和第k+1段的如下關(guān)系：這種遞推關(guān)系稱為動(dòng)態(tài)規(guī)劃的基本方程，第二個(gè)方程稱為邊界條件。基本方程和邊界條件統(tǒng)稱為動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型第20頁，課件共36頁，創(chuàng)作于2023年2月AB1B2C1C2C3D1D2D3E1E2F44333342C47551在圖上直接計(jì)算的方法叫標(biāo)號法。動(dòng)態(tài)規(guī)劃較之于窮舉法的優(yōu)點(diǎn)：一、計(jì)算量小二、計(jì)算結(jié)果不僅得到最短路線，而且得到了中間段任一點(diǎn)到F的最短路線第21頁，課件共36頁，創(chuàng)作于2023年2月動(dòng)態(tài)規(guī)劃的基本思想：（1）將多階段決策過程劃分階段，恰當(dāng)選取狀態(tài)變量、決策變量以及定義最優(yōu)指標(biāo)函數(shù)，從而把問題化成一族同類型的子問題。（2）求解時(shí)從邊界條件開始，逆（順）序逐段遞推尋優(yōu)。在每一個(gè)子問題求解時(shí)，都要使用它前面已求出的子問題的最優(yōu)結(jié)果，最后一個(gè)子問題的最優(yōu)解，就是整個(gè)問題的最優(yōu)解。（3）動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段與未來各段分開，又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法，因此每段的最優(yōu)決策選取是從全局考慮的，與該段的最優(yōu)選擇一般不同.第22頁，課件共36頁，創(chuàng)作于2023年2月最優(yōu)化原理：作為整個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)：“無論過去的狀態(tài)和決策如何，相對于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略?！币簿褪钦f，一個(gè)最優(yōu)策略的子策略也是最優(yōu)的。動(dòng)態(tài)規(guī)劃方法基于貝爾曼等人提出的最優(yōu)化原理：第23頁，課件共36頁，創(chuàng)作于2023年2月練習(xí)：求從A到E的最短路徑路線為A→B2→C1→D1→E

，最短路徑為19AB2B1B3C1C3D1D2EC25214126101043121113965810521第24頁，課件共36頁，創(chuàng)作于2023年2月四、逆序解法與順序解法動(dòng)態(tài)規(guī)劃求解的兩種基本方法：逆序解法（后向動(dòng)態(tài)規(guī)劃方法）順序解法（向前動(dòng)態(tài)規(guī)劃方法）逆序解法：從最后一段開始計(jì)算逐段前推，求得全過程的最優(yōu)策略，稱為逆序解法。順序解法：從第一階段開始逐段向后遞推，計(jì)算后一階段要用到前一階段的尋優(yōu)結(jié)果，最后一段計(jì)算的結(jié)果就是全過程的最優(yōu)結(jié)果。再次以例4為例說明順序解法：第25頁，課件共36頁，創(chuàng)作于2023年2月AB1B2C1C2C3D1D2D3E1E2F48544665333332482C47785451k=0時(shí)，f0(s1)=f0(A)=0，為邊界條件k=1時(shí)，按f1(s2)的定義，有第26頁，課件共36頁，創(chuàng)作于2023年2月AB1B2C1C2C3D1D2D3E1E2F48544665333332482C47785451k=2時(shí)，狀態(tài)變量s3可取四個(gè)值C1,C2,C3,C4，從C1到B只有一條路線，故此時(shí)從C1到A的最短路徑：第27頁，課件共36頁，創(chuàng)作于2023年2月同理，從C2到A有兩條路線，比較取最短者此時(shí)從C2到A的最短路徑：AB1B2C1C2C3D1D2D3E1E2F48544665333332482C47785451第28頁，課件共36頁，創(chuàng)作于2023年2月同理，從C3到A有兩條路線，比較取最短者此時(shí)從C3到A的最短路徑：AB1B2C1C2C3D1D2D3E1E2F4544665333332482C47785451第29頁，課件共36頁，創(chuàng)作于2023年2月同理，從C4到A只有一條路線，此時(shí)從C4到A的最短路徑：AB1B2C1C2C3D1D2D3E1E2F4544665333332482C4785451第30頁，課件共36頁，創(chuàng)作于2023年2月同理，k=3時(shí)有：此時(shí)最短路徑：相應(yīng)決策：AB1B2C1C2C3D1D2D3E1E2F4544665333332482C4785451第31頁，課件共36頁，創(chuàng)作于2023年2月同理，k=4時(shí)有：此時(shí)最短路徑：相應(yīng)決策：AB1B2C1C2C3D1D2D3E1E2F5446653333242C475451第32頁，課件共36頁，創(chuàng)作于2023年2月k=5時(shí)，只有一個(gè)狀態(tài)點(diǎn)F，則：此時(shí)最短路徑：AB1B2C1C2C3D1D2D3E1E2F4465333242C47545第33頁，課件共36頁，創(chuàng)作于2023年2月類似于逆序解法，寫出順序解法的遞推方程：這里