吉林大學(xué)本科運(yùn)籌學(xué)PPT演示文稿

1、第七章 動(dòng)態(tài)規(guī)劃,動(dòng)態(tài)規(guī)劃的基本方法 動(dòng)態(tài)規(guī)劃應(yīng)用舉例,動(dòng)態(tài)規(guī)劃,什么是動(dòng)態(tài)規(guī)劃 解決多階段決策過(guò)程最優(yōu)化的一種數(shù)學(xué)方法。 動(dòng)態(tài)規(guī)劃的形成 產(chǎn)生于20世紀(jì)50年代。1951年美國(guó)數(shù)學(xué)家貝爾曼(R.Bellman)等人，根據(jù)一類(lèi)多階段決策問(wèn)題的特點(diǎn)，把多階段決策問(wèn)題變換為一系列互相聯(lián)系的單階段問(wèn)題，然后逐個(gè)加以解決。與此同時(shí)，他提出了解決這類(lèi)問(wèn)題的“最優(yōu)性原理”，研究了許多實(shí)際問(wèn)題，從而創(chuàng)建了解決最優(yōu)化問(wèn)題的一種新的方法動(dòng)態(tài)規(guī)劃。 動(dòng)態(tài)規(guī)劃的應(yīng)用 在工程技術(shù)、企業(yè)管理、工農(nóng)業(yè)生產(chǎn)及軍事等部門(mén)中都有廣泛的應(yīng)用，并且獲得了顯著的效果。,動(dòng)態(tài)規(guī)劃,動(dòng)態(tài)規(guī)劃在企業(yè)管理中的主要應(yīng)用領(lǐng)域 最優(yōu)路徑問(wèn)題 資源

2、分配問(wèn)題 生產(chǎn)調(diào)度問(wèn)題 庫(kù)存問(wèn)題 裝載問(wèn)題 排序問(wèn)題 設(shè)備更新問(wèn)題 生產(chǎn)過(guò)程最優(yōu)控制問(wèn)題 等等 動(dòng)態(tài)規(guī)劃是求解某類(lèi)問(wèn)題的一種方法，是考查問(wèn)題的一種途徑，而不是一種特殊算法(如線(xiàn)性規(guī)劃是一種算法)。因而，它不像線(xiàn)性規(guī)劃那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，而必須對(duì)具體問(wèn)題進(jìn)行具體分析處理。,動(dòng)態(tài)規(guī)劃,動(dòng)態(tài)規(guī)劃模型的分類(lèi) 根據(jù)多階段決策過(guò)程的時(shí)間參量是離散的還是連續(xù)變量，分為離散決策過(guò)程和連續(xù)決策過(guò)程。 根據(jù)決策過(guò)程的演變是確定性的還是隨機(jī)性的，又可分為確定性決策過(guò)程和隨機(jī)性決策過(guò)程。 組合起來(lái)可分為 離散確定性 離散隨機(jī)性 連續(xù)確定性 連續(xù)隨機(jī)性 本書(shū)主要研究離散確定性決策過(guò)程。,第8

3、章 動(dòng)態(tài)規(guī)劃的基本方法,第1節(jié) 多階段決策過(guò)程及實(shí)例 第2節(jié) 動(dòng)態(tài)規(guī)劃的基本概念和基本方程 第3節(jié) 動(dòng)態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理 第4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,第1節(jié) 多階段決策過(guò)程及實(shí)例,例1 最短路線(xiàn)問(wèn)題 給定一個(gè)線(xiàn)路網(wǎng)絡(luò)，兩點(diǎn)之間連線(xiàn)上的數(shù)字表示兩點(diǎn)間的距離(或費(fèi)用)，試求一條由A到G的鋪管線(xiàn)路，使總距離為最短(或總費(fèi)用最小)。,第1節(jié) 多階段決策過(guò)程及實(shí)例,多階段決策過(guò)程 在生產(chǎn)和科學(xué)實(shí)驗(yàn)中，有一類(lèi)活動(dòng)的過(guò)程，由于它的特殊性，可將過(guò)程分為若干個(gè)互相聯(lián)系的階段，在它的每一個(gè)階段都需要作出決策，從而使整個(gè)過(guò)程達(dá)到最好的活動(dòng)效果。因此，各個(gè)階段決策的選取不是任意確定的，它依賴(lài)于當(dāng)前面

4、臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個(gè)階段決策確定后，就組成了一個(gè)決策序列，因而也就決定了整個(gè)過(guò)程的一條活動(dòng)路線(xiàn)。這種把一個(gè)問(wèn)題可看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程就稱(chēng)為多階段決策過(guò)程，也稱(chēng)序貫決策過(guò)程。,第1節(jié) 多階段決策過(guò)程及實(shí)例,例2 機(jī)器負(fù)荷分配問(wèn)題 某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。在高負(fù)荷下進(jìn)行生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機(jī)器數(shù)量u1的關(guān)系為 g=g(u1) 這時(shí)，機(jī)器的年完好率為a，即如果年初完好機(jī)器的數(shù)量為u，到年終時(shí)完好的機(jī)器就為au，0a1，在低負(fù)荷下生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機(jī)器數(shù)量u2的關(guān)系為 h=h(u2) 相應(yīng)的機(jī)器年完好率為b,0b1。

5、 假定開(kāi)始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為s1。要求制定一個(gè)五年計(jì)劃，在每年開(kāi)始時(shí)，決定如何重新分配完好的機(jī)器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。,第2節(jié) 動(dòng)態(tài)規(guī)劃的基本概念和基本方程,例1中求A到G的最短路線(xiàn)問(wèn)題是動(dòng)態(tài)規(guī)劃中一個(gè)典型例子?，F(xiàn)通過(guò)討論它的解法，說(shuō)明動(dòng)態(tài)規(guī)劃方法的基本思想，并闡述有關(guān)基本概念。 由圖8-2可知，從A點(diǎn)到G點(diǎn)可以分為6個(gè)階段。在第一階段，A為起點(diǎn)，終點(diǎn)有B1、B2兩個(gè)，因而這時(shí)走的路線(xiàn)有兩個(gè)選擇，一是走到B1；一是走到B2，若選擇走到B2的決策，則B2就是第一階段決策的結(jié)果。它既是第一階段路線(xiàn)的終點(diǎn)，又是第二階段路線(xiàn)的始點(diǎn)。在第二階段，再?gòu)腂2點(diǎn)出發(fā)

6、，有一個(gè)可供選擇的終點(diǎn)集合C2，C3，C4；若選擇由B2走至C2，則C2就是第二階段的終點(diǎn)，同時(shí)又是第三階段的始點(diǎn)。遞推下去可看到：各個(gè)階段的決策不同，路線(xiàn)就不同。顯然，當(dāng)某階段的始點(diǎn)給定后，會(huì)影響后面各階段的行進(jìn)路線(xiàn)和整個(gè)路線(xiàn)的長(zhǎng)短，而后面各階段路線(xiàn)的發(fā)展不受這點(diǎn)以前各階段決策的影響。故此問(wèn)題的要求是：在各個(gè)階段上選則一個(gè)恰當(dāng)?shù)臎Q策，使得由這些決策組成的一個(gè)決策序列所決定的一條路線(xiàn)是總路程最短的一條。,2.1 動(dòng)態(tài)規(guī)劃的基本概念,1階段 把所給問(wèn)題的過(guò)程，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段，以便能按一定的次序去求解。描述階段的變量稱(chēng)為階段變量，常用k表示。階段的劃分，一般是根據(jù)時(shí)間和空間的自然特

7、征來(lái)劃分，但要便于把問(wèn)題的過(guò)程能轉(zhuǎn)化為多階段決策的過(guò)程。如例1可分為6個(gè)階段來(lái)求解，k分別等于1、2、3、4、5、6。,2.1 動(dòng)態(tài)規(guī)劃的基本概念,2狀態(tài) 狀態(tài)表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件，它描述了研究問(wèn)題過(guò)程的狀況，又稱(chēng)不可控因素。在例1中，狀態(tài)就是某階段的出發(fā)位置。它既是該階段某支路的起點(diǎn)，又是前一階段某支路的終點(diǎn)。通常一個(gè)階段有若干個(gè)狀態(tài)，第一階段有一個(gè)狀態(tài)就是點(diǎn)A，第二階段有兩個(gè)狀態(tài)，即點(diǎn)集合B1，B2，一般第k階段的狀態(tài)就是第k階段所有始點(diǎn)的集合。,2.1 動(dòng)態(tài)規(guī)劃的基本概念,描述過(guò)程狀態(tài)的變量稱(chēng)為狀態(tài)變量。它可用一個(gè)數(shù)、一組數(shù)或一向量(多維情形)來(lái)描述。常用Sk表示第k

8、階段的狀態(tài)變量。如在例1中第三階段有四個(gè)狀態(tài)，則狀態(tài)變量Sk可取四個(gè)值，即C1、C2、C3、C4。點(diǎn)集合C1，C2，C3，C4就稱(chēng)為第三階段的可達(dá)狀態(tài)集合。記為S3C1，C2，C3，C4。有時(shí)為了方便起見(jiàn)，將該階段的狀態(tài)編上號(hào)碼1，2這時(shí)也可記S31，2，3，4。第k階段的可達(dá)狀態(tài)集合就記為Sk。,馬爾科夫性 這里所說(shuō)的狀態(tài)應(yīng)具有下面的性質(zhì)：如果某階段狀態(tài)給定后，則在這階段以后過(guò)程的發(fā)展不受這階段以前各段狀態(tài)的影響。換句話(huà)說(shuō)，過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它未來(lái)的發(fā)展，當(dāng)前的狀態(tài)是以往歷史的一個(gè)總結(jié)。這個(gè)性質(zhì)稱(chēng)為無(wú)后效性(即馬爾科夫性)。,2.1 動(dòng)態(tài)規(guī)劃的基本概念,3決策 決策表示當(dāng)

9、過(guò)程處于某一階段的某個(gè)狀態(tài)時(shí)，可以作出不同的決定(或選擇)，從而確定下一階段的狀態(tài)，這種決定稱(chēng)為決策。在最優(yōu)控制中也稱(chēng)為控制。描述決策的變量，稱(chēng)為決策變量。它可用一個(gè)數(shù)、一組數(shù)或一向量來(lái)描述。常用uk（sk）表示第k階段當(dāng)狀態(tài)處于sk時(shí)的決策變量。它是狀態(tài)變量的函數(shù)。在實(shí)際問(wèn)題中，決策變量的取值往往限制在某一范圍之內(nèi)，此范圍稱(chēng)為允許決策集合。常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，顯然有uk（sk）Dk(sk)。,2.1 動(dòng)態(tài)規(guī)劃的基本概念,3決策 如在例1第二階段中，若從狀態(tài)B1出發(fā)，就可作出三種不同的決策，其允許決策集合D2(B1)C1，C2，C3，若選取的點(diǎn)為C2，則C

10、2是狀態(tài)B1在決策u2(B1)作用下的一個(gè)新的狀態(tài)，記作u2(B1)=C2。,2.1 動(dòng)態(tài)規(guī)劃的基本概念,4策略 策略是一個(gè)按順序排列的決策組成的集合。由過(guò)程的第k階段開(kāi)始到終止?fàn)顟B(tài)為止的過(guò)程，稱(chēng)為問(wèn)題的后部子過(guò)程。由每段的決策按順序排列組成的決策函數(shù)序列 稱(chēng)為k子過(guò)程策略，簡(jiǎn)稱(chēng)子策略，記為 ，即,當(dāng)k=1時(shí)，此決策函數(shù)序列稱(chēng)為全過(guò)程的一個(gè)策略，簡(jiǎn)稱(chēng)策略，記為 ，即,在實(shí)際問(wèn)題中，可供選擇的策略有一定的范圍，此范圍稱(chēng)為允許策略集合，用P表示。從允許策略集合中找出達(dá)到最優(yōu)效果的策略稱(chēng)為最優(yōu)策略。,2.1 動(dòng)態(tài)規(guī)劃的基本概念,5狀態(tài)轉(zhuǎn)移方程 狀態(tài)轉(zhuǎn)移方程是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程。

11、若給定第k階段狀態(tài)變量的值，如果該段的決策變量uk一經(jīng)確定，第k+1階段的狀態(tài)變量sk+1的值也就完全確定。即sk+1的值隨sk和uk的值變化而變化。這種確定的對(duì)應(yīng)關(guān)系，記為,上式描述了由k階段到k+1階段的階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱(chēng)為狀態(tài)轉(zhuǎn)移方程。Tk稱(chēng)為狀態(tài)轉(zhuǎn)移函數(shù)。如例1中，狀態(tài)轉(zhuǎn)移方程為,2.1 動(dòng)態(tài)規(guī)劃的基本概念,6指標(biāo)函數(shù)和最優(yōu)值函數(shù) 用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的一種數(shù)量指標(biāo)，稱(chēng)為指標(biāo)函數(shù)。它是定義在全過(guò)程和所有后部子過(guò)程上確定的數(shù)量函數(shù)。常用Vk,n表示，即,對(duì)于要構(gòu)成動(dòng)態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性，并滿(mǎn)足遞推關(guān)系。即Vk,n可以表示為sk、uk、Vk+1,n的函數(shù)，記為,在實(shí)際

12、問(wèn)題中很多指標(biāo)函數(shù)都滿(mǎn)足這個(gè)性質(zhì)。,2.1 動(dòng)態(tài)規(guī)劃的基本概念,(1) 過(guò)程和它的任一子過(guò)程的指標(biāo)是它所包含的各階段的指標(biāo)的和。即,其中,表示第j階段的階段指標(biāo)，這時(shí)上式可寫(xiě)成,(2) 過(guò)程和它的任一子過(guò)程的指標(biāo)是它所包含的各階段的指標(biāo)的乘積。即,這時(shí)就可寫(xiě)成,常見(jiàn)的指標(biāo)函數(shù)形式,2.1 動(dòng)態(tài)規(guī)劃的基本概念,指標(biāo)函數(shù)的最優(yōu)值，稱(chēng)為最優(yōu)值函數(shù)，記為,。它表示從第,k階段的狀態(tài)sk開(kāi)始到第n階段的終止?fàn)顟B(tài)的過(guò)程，采取最優(yōu)策略所得到的指標(biāo)函數(shù)值。即,“opt”是最優(yōu)化(optimization)的縮寫(xiě)，可根據(jù)題意而取min或max。,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,結(jié)合最短路線(xiàn)問(wèn)題介紹動(dòng)態(tài)規(guī)劃

13、方法的基本思想。 生活中的常識(shí)告訴我們，最短路線(xiàn)有一個(gè)重要特性：如果由起點(diǎn)A經(jīng)過(guò)P點(diǎn)和H點(diǎn)而到達(dá)終點(diǎn)G是一條最短路線(xiàn)，則由點(diǎn)P出發(fā)經(jīng)過(guò)H點(diǎn)到達(dá)終點(diǎn)G的這條子路線(xiàn)，對(duì)于從點(diǎn)P出發(fā)到達(dá)終點(diǎn)的所有可能選擇的不同路線(xiàn)來(lái)說(shuō)，必定也是最短路線(xiàn)。例如，在最短路線(xiàn)問(wèn)題中，若找到了AB1C2D1E2F2G是由A到G的最短路線(xiàn)，則D1E2F2G應(yīng)該是由D1出發(fā)到G點(diǎn)的所有可能選擇的不同路線(xiàn)中的最短路線(xiàn)。 證明：（用反證法）如果不是這樣，則從點(diǎn)P到G點(diǎn)有另一條距離更短的路線(xiàn)存在，把它和原來(lái)最短路線(xiàn)由A點(diǎn)到達(dá)P點(diǎn)的那部分連接起來(lái)，就會(huì)得到一條由A點(diǎn)到G點(diǎn)的新路線(xiàn)，它比原來(lái)那條最短路線(xiàn)的距離還要短些。這與假設(shè)矛盾，是不

14、可能的。,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,根據(jù)最短路線(xiàn)這一特性，尋找最短路線(xiàn)的方法，就是從最后一段開(kāi)始，用由后向前逐步遞推的方法，求出各點(diǎn)到G點(diǎn)的最短路線(xiàn)，最后求得由A點(diǎn)到G點(diǎn)的最短路線(xiàn)。所以，動(dòng)態(tài)規(guī)劃的方法是從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易疃搪肪€(xiàn)的一種方法。下面按照動(dòng)態(tài)規(guī)劃的方法，將例1從最后一段開(kāi)始計(jì)算，由后向前逐步推移至A點(diǎn)。,2.1 動(dòng)態(tài)規(guī)劃的基本概念,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,當(dāng)k=6時(shí)，由F1到終點(diǎn)G只有一條路線(xiàn)，故,。同理，,當(dāng)k=5時(shí)，出發(fā)點(diǎn)有 三個(gè)。若從E1出發(fā)，則有兩個(gè)選擇至F1， 至F2，則,其相應(yīng)的決策為,這說(shuō)明，由E1至終點(diǎn)G的最短距離為7，其最短路線(xiàn)是,

15、2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,同理，從E2和E3出發(fā)，則有,其相應(yīng)的決策為,且,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,當(dāng)k=4時(shí)，有,當(dāng)k=3時(shí)，有,當(dāng)k=2時(shí)，有,當(dāng)k=1時(shí)，出發(fā)點(diǎn)有一個(gè)A點(diǎn)，則,且,。于是得到從起點(diǎn)A到終點(diǎn)G的最短距離為18。,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,為了找出最短路線(xiàn)，再按計(jì)算的順序反推之，可求出最優(yōu)決策函數(shù)序列,，即由,組成一個(gè)最優(yōu)策略。因而，找出相應(yīng)的最短路線(xiàn)為,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,從上面的計(jì)算過(guò)程中可以看出，在求解的各個(gè)階段，我們利用了,k階段與k+1階段之間的遞推關(guān)系：,一般情況，k階段與k+1階段的遞推關(guān)系式可寫(xiě)成,邊界條

16、件為,遞推關(guān)系式(8-1)稱(chēng)為動(dòng)態(tài)規(guī)劃的基本方程。,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,動(dòng)態(tài)規(guī)劃方法基本思想歸納： 動(dòng)態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫(xiě)出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件(簡(jiǎn)言之為基本方程)。要做到這一點(diǎn)，必須先將問(wèn)題的過(guò)程分成幾個(gè)相互聯(lián)系的階段，恰當(dāng)?shù)剡x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個(gè)大問(wèn)題化成一族同類(lèi)型的子問(wèn)題，然后逐個(gè)求解。即從邊界條件開(kāi)始，逐段遞推尋優(yōu)，在每一個(gè)子問(wèn)題的求解中，均利用了它前面的子問(wèn)題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個(gè)子問(wèn)題所得的最優(yōu)解，就是整個(gè)問(wèn)題的最優(yōu)解。 在多階段決策過(guò)程中，動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段和未來(lái)各段分開(kāi)，又把當(dāng)前效益和未來(lái)效益結(jié)

17、合起來(lái)考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來(lái)考慮的，與該段的最優(yōu)選擇答案一般是不同的。,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,在求整個(gè)問(wèn)題的最優(yōu)策略時(shí)，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過(guò)的各段狀態(tài)便可逐次變換得到，從而確定了最優(yōu)路線(xiàn)。 如例1最短路線(xiàn)問(wèn)題，初始狀態(tài)A已知，則按下面箭頭所指的方向逐次變換有,從而可得最優(yōu)策略為u1(A),u2(B1),u0(F2)，相應(yīng)的最短路線(xiàn)為,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,求解最短路問(wèn)題的標(biāo)號(hào)法逆序解法,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,求解最短路問(wèn)題的標(biāo)號(hào)法順序解法,2.2 動(dòng)態(tài)規(guī)劃的基本思想和

18、基本方程,動(dòng)態(tài)規(guī)劃的方法比窮舉法有以下優(yōu)點(diǎn)： (1) 減少了計(jì)算量。計(jì)算例1若用窮舉法，就要對(duì)48條路線(xiàn)進(jìn)行比較，運(yùn)算在計(jì)算機(jī)上進(jìn)行時(shí)，比較運(yùn)算要進(jìn)行47次；求各條路線(xiàn)的距離，即使用逐段累加方法，也要進(jìn)行6+12+24+48+48138次加法運(yùn)算。用動(dòng)態(tài)規(guī)劃方法來(lái)計(jì)算，比較運(yùn)算(從k=5段開(kāi)始向前算)共進(jìn)行3+3+4+4+115次。每次比較運(yùn)算相應(yīng)有兩次加法運(yùn)算，再去掉中間重復(fù)兩次(即B1C1，B2C4各多算了一次)，實(shí)際只有28次加法運(yùn)算?？梢?jiàn)，動(dòng)態(tài)規(guī)劃方法比窮舉法減少了計(jì)算量。而且隨著段數(shù)的增加，計(jì)算量將大大地減少。 (2) 豐富了計(jì)算結(jié)果。在逆序(或順序)解法中，我們得到的不僅僅是由A點(diǎn)

19、(或G點(diǎn))出發(fā)到G點(diǎn)(或A點(diǎn))的最短路線(xiàn)及相應(yīng)的最短距離，而且得到了從所有各中間點(diǎn)出發(fā)到G點(diǎn)(或A點(diǎn))的最短路線(xiàn)及相應(yīng)的距離。這就是說(shuō)，求出的不是一個(gè)最優(yōu)策略，而是一族的最優(yōu)策略。,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,建立動(dòng)態(tài)規(guī)劃模型的五個(gè)要點(diǎn)： (1) 將問(wèn)題的過(guò)程劃分成恰當(dāng)?shù)碾A段； (2) 正確選擇狀態(tài)變量sk，使它既能描述過(guò)程的演變，又要滿(mǎn)足無(wú)后效性； (3) 確定決策變量uk及每階段的允許決策集合Dk(sk)； (4) 正確寫(xiě)出狀態(tài)轉(zhuǎn)移方程； (5) 正確寫(xiě)出指標(biāo)函數(shù)的關(guān)系，它應(yīng)滿(mǎn)足下面性質(zhì)： 是定義在全過(guò)程和所有后部子過(guò)程上的數(shù)量函數(shù)； 要具有可分離性，并滿(mǎn)足遞推關(guān)系。即,2.2

20、動(dòng)態(tài)規(guī)劃的基本思想和基本方程,所以，得到動(dòng)態(tài)規(guī)劃逆序解法的基本方程：,邊界條件為,式中,求解過(guò)程，根據(jù)邊界條件，從k=n開(kāi)始，由后向前逆推，從而逐步可求得各段的最優(yōu)決策和相應(yīng)的最優(yōu)值，最后求出,時(shí)，就得到整個(gè)問(wèn)題的最優(yōu)解。,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,動(dòng)態(tài)規(guī)劃順序解法的基本方程,邊界條件為,式中,求解過(guò)程：根據(jù)邊界條件，從k=1開(kāi)始，由前向后順推，逐步求得各段的最優(yōu)決策和相應(yīng)的最優(yōu)值，最后求出 ，,就得到整個(gè)問(wèn)題的最優(yōu)解。,第3節(jié) 動(dòng)態(tài)規(guī)劃的最優(yōu)性原理和最優(yōu)性定理,動(dòng)態(tài)規(guī)劃的最優(yōu)性原理： “作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：即無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言

21、，余下的諸決策必須構(gòu)成最優(yōu)策略?！?簡(jiǎn)言之，一個(gè)最優(yōu)策略的子策略總是最優(yōu)的。 動(dòng)態(tài)規(guī)劃的基本方程或者說(shuō)最優(yōu)性定理才是動(dòng)態(tài)規(guī)劃的理論基礎(chǔ),第4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,相同點(diǎn) 動(dòng)態(tài)規(guī)劃、線(xiàn)性規(guī)劃和非線(xiàn)性規(guī)劃都屬于數(shù)學(xué)規(guī)劃范圍，研究對(duì)象本質(zhì)上都是求極值問(wèn)題，都是利用迭代法去逐步求解。 不同點(diǎn) 線(xiàn)性規(guī)劃和非線(xiàn)性規(guī)劃研究的問(wèn)題通常與時(shí)間無(wú)關(guān)，故又稱(chēng)為靜態(tài)規(guī)劃。線(xiàn)性規(guī)劃迭代中的每一步是就問(wèn)題的整體加以改善的。 動(dòng)態(tài)規(guī)劃研究的問(wèn)題與時(shí)間有關(guān)，研究具有多階段決策過(guò)程的一類(lèi)問(wèn)題，將問(wèn)題的整體按時(shí)間或空間的特征分成若干個(gè)前后銜接的時(shí)空階段，把多階段決策問(wèn)題表示為前后有關(guān)聯(lián)的一系列單階段決策問(wèn)題，然后逐個(gè)加以

22、解決，從而求出整個(gè)問(wèn)題的最優(yōu)決策序列。 對(duì)于某些靜態(tài)問(wèn)題，也可以人為地引入時(shí)間因素，把它看作是按階段進(jìn)行的一個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題，這就使得動(dòng)態(tài)規(guī)劃成為求解某些線(xiàn)性、非線(xiàn)性規(guī)劃的有效方法。,第4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,動(dòng)態(tài)規(guī)劃方法 逆序解法 順序解法 關(guān)鍵：正確寫(xiě)出動(dòng)態(tài)規(guī)劃的遞推關(guān)系式 逆推形式，當(dāng)初始狀態(tài)給定時(shí)，用逆推比較方便 順推形式，當(dāng)終止?fàn)顟B(tài)給定時(shí)，用順推比較方便,第4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,考查如圖所示的n階段決策過(guò)程。其中取狀態(tài)變量為,決策變量為,。在第k階段，決策xk使?fàn)顟B(tài)sk(輸入）轉(zhuǎn)移,為sk+1 (輸出)，設(shè)狀態(tài)轉(zhuǎn)移函數(shù)為,假定過(guò)程的總效益(指標(biāo)函數(shù))與各階段效益(階段

23、指標(biāo)函數(shù))的關(guān)系為,其中記號(hào)*都表示為+,或都表示為。問(wèn)題是：使,達(dá)到最優(yōu)化，即求,，為簡(jiǎn)單起見(jiàn)，不妨此處就求,第4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,4.1 逆推解法 設(shè)已知初始狀態(tài)為s1，并假定最優(yōu)值函數(shù)fk(sk)表示第k階段的初始狀態(tài)為sk，從k階段到n階段所得到的最大效益。,第4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,例3 用逆推解法求解下面問(wèn)題,解 : 按問(wèn)題的變量個(gè)數(shù)劃分階段，把它看作為一個(gè)三階段決策問(wèn)題。 設(shè)狀態(tài)變量為s1, s2,s3,s4，并記s1=c；取問(wèn)題中的變量x1,x2,x3為決策變量；各階段指標(biāo)函數(shù)按乘積方式結(jié)合。令最優(yōu)值函數(shù)fk(sk)表示為第k階段的初始狀態(tài)為sk，從k階段到3階段所得到的最大值。,設(shè),第4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,用逆推解法，從后向前依次有,及最優(yōu)解,由,得,和,(舍去),，而,，故,為極大值點(diǎn)。,最優(yōu)解,由,所以,第4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,像前面一樣利用微分法易知,故,由于已知,而按計(jì)算的順序反推算，可得各階段的最優(yōu)決策和最優(yōu)值。,第4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,即,由,所以,所以,因此得到最優(yōu)解為,最大值為,由,第4節(jié) 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系,4.2 順推解法 設(shè)已知終止?fàn)?/p>