運(yùn)籌學(xué)-第9章-動(dòng)態(tài)規(guī)劃

1、,五 動(dòng)態(tài)規(guī)劃,第9章 動(dòng)態(tài)規(guī)劃的基本方法第10章 動(dòng)態(tài)規(guī)劃應(yīng)用舉例,1,2,動(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ù)一類多階段決策問(wèn)題的特點(diǎn)，把多階段決策問(wèn)題變換為一系列互相聯(lián)系的單階段問(wèn)題，然后逐個(gè)加以解決。與此同時(shí)，他提出了解決這類問(wèn)題的“最優(yōu)性原理”，研究了許多實(shí)際問(wèn)題，從而創(chuàng)建了解決最優(yōu)化問(wèn)題的

2、一種新的方法——?jiǎng)討B(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃的應(yīng)用在工程技術(shù)、企業(yè)管理、工農(nóng)業(yè)生產(chǎn)及軍事等部門中都有廣泛的應(yīng)用，并且獲得了顯著的效果。,3,動(dòng)態(tài)規(guī)劃,動(dòng)態(tài)規(guī)劃在企業(yè)管理中的主要應(yīng)用領(lǐng)域最優(yōu)路徑問(wèn)題資源分配問(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ī)劃是求解某類問(wèn)題的一種方法，是考查問(wèn)題的一種途徑，而不是一種特殊算法(如線性規(guī)劃是一種算法)。因而，它不像線性規(guī)劃那樣有一個(gè)標(biāo)

3、準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，而必須對(duì)具體問(wèn)題進(jìn)行具體分析處理。,4,動(dòng)態(tài)規(guī)劃,動(dòng)態(tài)規(guī)劃模型的分類根據(jù)多階段決策過(guò)程的時(shí)間參量是離散的還是連續(xù)變量，分為離散決策過(guò)程和連續(xù)決策過(guò)程。根據(jù)決策過(guò)程的演變是確定性的還是隨機(jī)性的，又可分為確定性決策過(guò)程和隨機(jī)性決策過(guò)程。組合起來(lái)可分為離散確定性離散隨機(jī)性連續(xù)確定性連續(xù)隨機(jī)性本書(shū)主要研究離散決策過(guò)程。,5,第9章 動(dòng)態(tài)規(guī)劃的基本方法,第1節(jié) 多階段決策過(guò)程及實(shí)例第2節(jié)

4、 動(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)系,6,第1節(jié) 多階段決策過(guò)程及實(shí)例,多階段決策過(guò)程在生產(chǎn)和科學(xué)實(shí)驗(yàn)中，有一類活動(dòng)的過(guò)程，由于它的特殊性，可將過(guò)程分為若干個(gè)互相聯(lián)系的階段，在它的每一個(gè)階段都需要作出決策，從而使整個(gè)過(guò)程達(dá)到最好的活動(dòng)效果。因此，各個(gè)階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個(gè)階段決策確定后，就組成了一個(gè)決策序

5、列，因而也就決定了整個(gè)過(guò)程的一條活動(dòng)路線。這種把一個(gè)問(wèn)題可看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程就稱為多階段決策過(guò)程，也稱序貫決策過(guò)程。,7,第1節(jié) 多階段決策過(guò)程及實(shí)例,例1 最短路線問(wèn)題 給定一個(gè)線路網(wǎng)絡(luò)，兩點(diǎn)之間連線上的數(shù)字表示兩點(diǎn)間的距離(或費(fèi)用)，試求一條由A到G的鋪管線路，使總距離為最短(或總費(fèi)用最小)。,8,第1節(jié) 多階段決策過(guò)程及實(shí)例,例2 機(jī)器負(fù)荷分配問(wèn)題某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生

6、產(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，0＜a＜1，在低負(fù)荷下生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機(jī)器數(shù)量u2的關(guān)系為 h=h(u2)相應(yīng)的機(jī)器年完好率為b

7、,0＜b＜1。假定開(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á)到最高。,9,第2節(jié) 動(dòng)態(tài)規(guī)劃的基本概念和基本方程,例1中求A到G的最短路線問(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è)，因而

8、這時(shí)走的路線有兩個(gè)選擇，一是走到B1；一是走到B2，若選擇走到B2的決策，則B2就是第一階段決策的結(jié)果。它既是第一階段路線的終點(diǎn)，又是第二階段路線的始點(diǎn)。在第二階段，再?gòu)腂2點(diǎn)出發(fā)，有一個(gè)可供選擇的終點(diǎn)集合｛C2，C3，C4｝；若選擇由B2走至C2，則C2就是第二階段的終點(diǎn)，同時(shí)又是第三階段的始點(diǎn)。遞推下去可看到：各個(gè)階段的決策不同，路線就不同。顯然，當(dāng)某階段的始點(diǎn)給定后，會(huì)影響后面各階段的行進(jìn)路線和整個(gè)路線的長(zhǎng)短，而后面各階段路線的發(fā)

9、展不受這點(diǎn)以前各階段決策的影響。故此問(wèn)題的要求是：在各個(gè)階段上選則一個(gè)恰當(dāng)?shù)臎Q策，使得由這些決策組成的一個(gè)決策序列所決定的一條路線是總路程最短的一條。,10,2.1 動(dòng)態(tài)規(guī)劃的基本概念,1．階段把所給問(wèn)題的過(guò)程，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段，以便能按一定的次序去求解。描述階段的變量稱為階段變量，常用k表示。階段的劃分，一般是根據(jù)時(shí)間和空間的自然特征來(lái)劃分，但要便于把問(wèn)題的過(guò)程能轉(zhuǎn)化為多階段決策的過(guò)程。如例1可分為6個(gè)階段來(lái)求解，k

10、分別等于1、2、3、4、5、6。,,,,,,,,11,2.1 動(dòng)態(tài)規(guī)劃的基本概念,2．狀態(tài)狀態(tài)表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件，它描述了研究問(wèn)題過(guò)程的狀況，又稱不可控因素。在例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)的集合。,,,12,2.1 動(dòng)

11、態(tài)規(guī)劃的基本概念,描述過(guò)程狀態(tài)的變量稱為狀態(tài)變量。它可用一個(gè)數(shù)、一組數(shù)或一向量(多維情形)來(lái)描述。常用Sk表示第k階段的狀態(tài)變量。如在例1中第三階段有四個(gè)狀態(tài)，則狀態(tài)變量Sk可取四個(gè)值，即C1、C2、C3、C4。點(diǎn)集合｛C1，C2，C3，C4｝就稱為第三階段的可達(dá)狀態(tài)集合。記為S3＝｛C1，C2，C3，C4｝。有時(shí)為了方便起見(jiàn)，將該階段的狀態(tài)編上號(hào)碼1，2…這時(shí)也可記S3＝｛1，2，3，4｝。第k階段的可達(dá)狀態(tài)集合就記為Sk。,馬爾科夫

12、性這里所說(shuō)的狀態(tài)應(yīng)具有下面的性質(zhì)：如果某階段狀態(tài)給定后，則在這階段以后過(guò)程的發(fā)展不受這階段以前各段狀態(tài)的影響。換句話說(shuō)，過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它未來(lái)的發(fā)展，當(dāng)前的狀態(tài)是以往歷史的一個(gè)總結(jié)。這個(gè)性質(zhì)稱為無(wú)后效性(即馬爾科夫性)。,13,2.1 動(dòng)態(tài)規(guī)劃的基本概念,3．決策決策表示當(dāng)過(guò)程處于某一階段的某個(gè)狀態(tài)時(shí)，可以作出不同的決定(或選擇)，從而確定下一階段的狀態(tài)，這種決定稱為決策。在最優(yōu)控制中也稱為控制。描述決策的變

13、量，稱為決策變量。它可用一個(gè)數(shù)、一組數(shù)或一向量來(lái)描述。常用uk（sk）表示第k階段當(dāng)狀態(tài)處于sk時(shí)的決策變量。它是狀態(tài)變量的函數(shù)。在實(shí)際問(wèn)題中，決策變量的取值往往限制在某一范圍之內(nèi)，此范圍稱為允許決策集合。常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，顯然有uk（sk）∈Dk(sk)。,,14,2.1 動(dòng)態(tài)規(guī)劃的基本概念,3．決策 如在例1第二階段中，若從狀態(tài)B1出發(fā)，就可作出三種不同的決策，其允許決策集合D

14、2(B1)＝｛C1，C2，C3｝，若選取的點(diǎn)為C2，則C2是狀態(tài)B1在決策u2(B1)作用下的一個(gè)新的狀態(tài)，記作u2(B1)=C2。,,,15,2.1 動(dòng)態(tài)規(guī)劃的基本概念,4．策略策略是一個(gè)按順序排列的決策組成的集合。由過(guò)程的第k階段開(kāi)始到終止?fàn)顟B(tài)為止的過(guò)程，稱為問(wèn)題的后部子過(guò)程。由每段的決策按順序排列組成的決策函數(shù)序列 稱為k子過(guò)程策略，簡(jiǎn)稱子策略，記為

15、 ，即,當(dāng)k=1時(shí)，此決策函數(shù)序列稱為全過(guò)程的一個(gè)策略，簡(jiǎn)稱策略，記為 ，即,在實(shí)際問(wèn)題中，可供選擇的策略有一定的范圍，此范圍稱為允許策略集合，用P表示。從允許策略集合中找出達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。,16,2.1 動(dòng)態(tài)規(guī)劃的基本概念,,5．狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程。若給定第k階段狀態(tài)變量的值，如果該段的決策變量uk一經(jīng)確定，第k+1階段的狀態(tài)變量sk+1

16、的值也就完全確定。即sk+1的值隨sk和uk的值變化而變化。這種確定的對(duì)應(yīng)關(guān)系，記為,上式描述了由k階段到k+1階段的階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。Tk稱為狀態(tài)轉(zhuǎn)移函數(shù)。如例1中，狀態(tài)轉(zhuǎn)移方程為,17,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)，稱為指標(biāo)函數(shù)。它是定義在全過(guò)程和所有后部子過(guò)程上確定的數(shù)量函數(shù)。常用Vk,n表示，即,對(duì)于要構(gòu)成動(dòng)態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性

17、，并滿足遞推關(guān)系。即Vk,n可以表示為sk、uk、Vk+1,n的函數(shù)，記為,在實(shí)際問(wèn)題中很多指標(biāo)函數(shù)都滿足這個(gè)性質(zhì)。,,18,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ù)形式,,,,19,2.1 動(dòng)態(tài)規(guī)劃的基本概念,,指標(biāo)函數(shù)的最優(yōu)值，稱

18、為最優(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。,20,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,,結(jié)合最短路線問(wèn)題介紹動(dòng)態(tài)規(guī)劃方法的基本思想。生活中的常識(shí)告訴我們，最短路線有一個(gè)重要特性：如果由起點(diǎn)A經(jīng)過(guò)P點(diǎn)和H點(diǎn)而到達(dá)終點(diǎn)G是一條最短路線，則由點(diǎn)P出發(fā)經(jīng)過(guò)H點(diǎn)到達(dá)終點(diǎn)G的這條子路線

19、，對(duì)于從點(diǎn)P出發(fā)到達(dá)終點(diǎn)的所有可能選擇的不同路線來(lái)說(shuō)，必定也是最短路線。例如，在最短路線問(wèn)題中，若找到了A→B1→C2→D1→E2→F2→G是由A到G的最短路線，則D1→E2→F2→G應(yīng)該是由D1出發(fā)到G點(diǎn)的所有可能選擇的不同路線中的最短路線。證明：（用反證法）如果不是這樣，則從點(diǎn)P到G點(diǎn)有另一條距離更短的路線存在，把它和原來(lái)最短路線由A點(diǎn)到達(dá)P點(diǎn)的那部分連接起來(lái)，就會(huì)得到一條由A點(diǎn)到G點(diǎn)的新路線，它比原來(lái)那條最短路線的距離還要短些。

20、這與假設(shè)矛盾，是不可能的。,21,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,,根據(jù)最短路線這一特性，尋找最短路線的方法，就是從最后一段開(kāi)始，用由后向前逐步遞推的方法，求出各點(diǎn)到G點(diǎn)的最短路線，最后求得由A點(diǎn)到G點(diǎn)的最短路線。所以，動(dòng)態(tài)規(guī)劃的方法是從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易疃搪肪€的一種方下面按照動(dòng)態(tài)規(guī)劃的方法，將例1從最后一段開(kāi)始計(jì)算，由后向前逐步推移至A點(diǎn)。,22,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,,當(dāng)k=6時(shí)，由F1到終點(diǎn)G只有一

21、條路線，故,。同理，,當(dāng)k=5時(shí)，出發(fā)點(diǎn)有 三個(gè)。若從E1出發(fā)，則有兩個(gè)選擇①至F1，②至F2，則,其相應(yīng)的決策為,這說(shuō)明，由E1至終點(diǎn)G的最短距離為7，其最短路線是,23,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,,同理，從E2和E3出發(fā)，則有,其相應(yīng)的決策為,且,24,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)，則,且,。于是

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

23、的基本方程。,27,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)題化成一族同類型的子問(wèn)題，然后逐個(gè)求解。即從邊界條件開(kāi)始，逐段遞推尋優(yōu)，在每一個(gè)子問(wèn)題的求解中，均利用了它前面的子問(wèn)題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一

24、個(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é)合起來(lái)考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來(lái)考慮的，與該段的最優(yōu)選擇答案一般是不同的。,28,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)路線。如例1最短路

25、線問(wèn)題，初始狀態(tài)A已知，則按下面箭頭所指的方向逐次變換有,從而可得最優(yōu)策略為｛u1(A),u2(B1),…,u0’(F2)｝，相應(yīng)的最短路線為,,,,,29,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,,求解最短路問(wèn)題的標(biāo)號(hào)法——逆序解法,30,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,,求解最短路問(wèn)題的標(biāo)號(hào)法——順序解法,31,2.2 動(dòng)態(tài)規(guī)劃的基本思想和基本方程,,動(dòng)態(tài)規(guī)劃的方法比窮舉法有以下優(yōu)點(diǎn)：(1) 減少了計(jì)算量。計(jì)算例1若用窮

26、舉法，就要對(duì)48條路線進(jìn)行比較，運(yùn)算在計(jì)算機(jī)上進(jìn)行時(shí)，比較運(yùn)算要進(jìn)行47次；求各條路線的距離，即使用逐段累加方法，也要進(jìn)行6+12+24+48+48＝138次加法運(yùn)算。用動(dòng)態(tài)規(guī)劃方法來(lái)計(jì)算，比較運(yùn)算(從k=5段開(kāi)始向前算)共進(jìn)行3+3+4+4+1＝15次。每次比較運(yùn)算相應(yīng)有兩次加法運(yùn)算，再去掉中間重復(fù)兩次(即B1→C1，B2→C4各多算了一次)，實(shí)際只有28次加法運(yùn)算。可見(jiàn)，動(dòng)態(tài)規(guī)劃方法比窮舉法減少了計(jì)算量。而且隨著段數(shù)的增加，計(jì)算量將

27、大大地減少。(2) 豐富了計(jì)算結(jié)果。在逆序(或順序)解法中，我們得到的不僅僅是由A點(diǎn)(或G點(diǎn))出發(fā)到G點(diǎn)(或A點(diǎn))的最短路線及相應(yīng)的最短距離，而且得到了從所有各中間點(diǎn)出發(fā)到G點(diǎn)(或A點(diǎn))的最短路線及相應(yīng)的距離。這就是說(shuō)，求出的不是一個(gè)最優(yōu)策略，而是一族的最優(yōu)策略。,32,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ò)程的演變，

28、又要滿足無(wú)后效性；(3) 確定決策變量uk及每階段的允許決策集合Dk(sk)；(4) 正確寫(xiě)出狀態(tài)轉(zhuǎn)移方程；(5) 正確寫(xiě)出指標(biāo)函數(shù)Vk,n的關(guān)系，它應(yīng)滿足下面三個(gè)性質(zhì)： ① 是定義在全過(guò)程和所有后部子過(guò)程上的數(shù)量函數(shù)； ② 要具有可分離性，并滿足遞推關(guān)系。即 ③ 函數(shù) 對(duì)于變量Vk+1,n要嚴(yán)格單調(diào)。,33,第3節(jié) 動(dòng)態(tài)規(guī)劃的

29、最優(yōu)性原理和最優(yōu)性定理,,動(dòng)態(tài)規(guī)劃的最優(yōu)性原理：“作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：即無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(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ǔ),具體說(shuō)，此問(wèn)題先從F開(kāi)始，因?yàn)镕是終點(diǎn)。再無(wú)后繼過(guò)程，故可以接著考慮第5階段上所有可能狀態(tài)E1，E2的最優(yōu)后續(xù)過(guò)程。因?yàn)閺腅1 ,E2到F的路線是

30、唯一的，所以E1，E2的最優(yōu)決策和最優(yōu)后繼過(guò)程就是到F，它們的最短距離分別是4和3。 接著考慮階段4上可能的狀態(tài)D1，D2，D3 到F的最優(yōu)決策和最優(yōu)后繼過(guò)程．在狀態(tài)D1上，到E1是3，到E2是5，綜合考慮后繼過(guò)程整體最優(yōu)，取最優(yōu)決策是到E1,最優(yōu)后繼過(guò)程是D1→E1→F ，最短距離是7。同理，狀態(tài)D2的最優(yōu)決策是至E2 ；D3的最優(yōu)決策是到E1。,同樣，當(dāng)階段4上所有可能狀態(tài)的最優(yōu)后繼過(guò)程都已求得后，便可以開(kāi)始考慮階段3上

31、所有可能狀態(tài)的最優(yōu)決策和最優(yōu)后繼過(guò)程，如C1的最優(yōu)決策是到D1,最優(yōu)路線是C1→D1→E1→F ，最短距離是12…依此類推，最后可以得到從初始狀態(tài)A的最優(yōu)決策是到F最優(yōu)路線是A→B1→C2→D2→E2 →F ，全程的最短距離是17。圖7—1中粗實(shí)線表示各點(diǎn)到的最優(yōu)路線，每點(diǎn)上方括號(hào)內(nèi)的數(shù)字表示該點(diǎn)到終點(diǎn)的最短路距離。,,,,,綜上所述可見(jiàn)，全枚舉法雖可找出最優(yōu)方案，但不是個(gè)好算法，局部最優(yōu)法則完全是個(gè)錯(cuò)誤方法，只有動(dòng)態(tài)規(guī)劃方法屬較科學(xué)有