動(dòng)態(tài)規(guī)劃講解含例題及答案

1、動(dòng)態(tài)規(guī)劃講解大全動(dòng)態(tài)規(guī)劃講解大全動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃(dynamicprogramming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程(decisionprocess)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程(multistepdecisionprocess)的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理(principleofoptimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個(gè)求解，創(chuàng)立了解決

2、這類過程優(yōu)化問題的新方法——?jiǎng)討B(tài)規(guī)劃。1957年出版了他的名著DynamicProgramming，這是該領(lǐng)域的第一本著作。動(dòng)態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動(dòng)態(tài)規(guī)劃方法比用其它方法求解更為方便。雖然動(dòng)態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動(dòng)態(tài)過程的優(yōu)化問題，但是一些與時(shí)間無關(guān)的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃)，只要人為地引進(jìn)時(shí)

3、間因素，把它視為多階段決策過程，也可以用動(dòng)態(tài)規(guī)劃方法方便地求解。動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。不象前面所述的那些搜索或數(shù)值計(jì)算那樣，具有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確清晰的解題方法。動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)往往是針對一種最優(yōu)化問題，由于各種問題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動(dòng)態(tài)規(guī)劃的設(shè)計(jì)方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動(dòng)態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問題。因此讀者在

4、學(xué)習(xí)時(shí)，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。我們也可以通過對若干有代表性的問題的動(dòng)態(tài)規(guī)劃算法進(jìn)行分析、討論，逐漸學(xué)會(huì)并掌握這一設(shè)計(jì)方法?；灸Ｐ突灸Ｐ投嚯A段決策過程的最優(yōu)化問題。在現(xiàn)實(shí)生活中，有一類活動(dòng)的過程，由于它的特殊性，可將過程分成若干個(gè)互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個(gè)過程達(dá)到最好的活動(dòng)效果。當(dāng)然，各個(gè)階段決策的選取不是任意確定的，它

5、依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展，當(dāng)各個(gè)階段決策確定后，就組成一個(gè)決策序列，因而也就確定了整個(gè)過程的一條活動(dòng)路線，如圖所示：（看詞條圖）這種把一個(gè)問題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，這種問題就稱為多階段決策問題。記憶記憶化搜索化搜索給你一個(gè)數(shù)字三角形形式如下:12345678910找出從第一層到最后一層的一條路使得所經(jīng)過的權(quán)值之和最小或者最大.無論對與新手還是老手，這都是再熟悉不過的題了，很容易地，

6、我們寫出狀態(tài)轉(zhuǎn)移方程：f(ij)=a[ij]minf(i1j)，f(i1j1)對于動(dòng)態(tài)規(guī)劃算法解決這個(gè)問題，我們根據(jù)狀態(tài)轉(zhuǎn)移方程和狀態(tài)轉(zhuǎn)移方向，比較容易地寫出動(dòng)態(tài)規(guī)劃的循環(huán)表示方法。但是，當(dāng)狀態(tài)和轉(zhuǎn)移非常復(fù)雜的時(shí)候，也許寫出循環(huán)式的動(dòng)態(tài)規(guī)劃就不是那么簡單了。外，也有階段變量是連續(xù)的情形。如果過程可以在任何時(shí)刻作出決策，且在任意兩個(gè)不同的時(shí)刻之間允許有無窮多個(gè)決策時(shí)，階段變量就是連續(xù)的。在前面的例子中，第一個(gè)階段就是點(diǎn)A，而第二個(gè)階段就是

7、點(diǎn)A到點(diǎn)B，第三個(gè)階段是點(diǎn)B到點(diǎn)C，而第四個(gè)階段是點(diǎn)C到點(diǎn)D。狀態(tài)狀態(tài)：狀態(tài)表示每個(gè)階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉(zhuǎn)移，也稱為不可控因素。在上面的例子中狀態(tài)就是某階段的出發(fā)位置，它既是該階段某路的起點(diǎn)，同時(shí)又是前一階段某支路的終點(diǎn)。在前面的例子中，第一個(gè)階段有一個(gè)狀態(tài)即A，而第二個(gè)階段有兩個(gè)狀態(tài)B1和B2，第三個(gè)階段是三個(gè)狀態(tài)C1，C2和C3，而第四個(gè)階段又是一個(gè)狀態(tài)D。過程的狀態(tài)通?？梢杂靡粋€(gè)或一組數(shù)來描述，

8、稱為狀態(tài)變量。一般，狀態(tài)是離散的，但有時(shí)為了方便也將狀態(tài)取成連續(xù)的。當(dāng)然，在現(xiàn)實(shí)生活中，由于變量形式的限制，所有的狀態(tài)都是離散的，但從分析的觀點(diǎn)，有時(shí)將狀態(tài)作為連續(xù)的處理將會(huì)有很大的好處。此外，狀態(tài)可以有多個(gè)分量(多維情形)，因而用向量來代表；而且在每個(gè)階段的狀態(tài)維數(shù)可以不同。當(dāng)過程按所有可能不同的方式發(fā)展時(shí)，過程各段的狀態(tài)變量將在某一確定的范圍內(nèi)取值。狀態(tài)變量取值的集合稱為狀態(tài)集合。無后效性無后效性：我們要求狀態(tài)具有下面的性質(zhì)：如果給

9、定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時(shí)，整個(gè)過程也就確定了。換句話說，過程的每一次實(shí)現(xiàn)可以用一個(gè)狀態(tài)序列表示，在前面的例子中每階段的狀態(tài)是該線路的始點(diǎn)，確定了這些點(diǎn)的序列，整個(gè)線路也就完全確定。從某一階段以后的線路開始，當(dāng)這段的始點(diǎn)給定時(shí)，不受以前線路（所通過的點(diǎn)）的影響。狀態(tài)的這個(gè)性質(zhì)意味著過程的歷史只能通過當(dāng)前的狀態(tài)去影響它的未來的發(fā)展，這個(gè)性質(zhì)稱為無后效性。決策決策：一個(gè)階段的

10、狀態(tài)給定以后，從該狀態(tài)演變到下一階段某個(gè)狀態(tài)的一種選擇（行動(dòng)）稱為決策。在最優(yōu)控制中，也稱為控制。在許多間題中，決策可以自然而然地表示為一個(gè)數(shù)或一組數(shù)。不同的決策對應(yīng)著不同的數(shù)值。描述決策的變量稱決策變量，因狀態(tài)滿足無后效性，故在每個(gè)階段選擇決策時(shí)只需考慮當(dāng)前的狀態(tài)而無須考慮過程的歷史。決策變量的范圍稱為允許決策集合。策略策略：由每個(gè)階段的決策組成的序列稱為策略。對于每一個(gè)實(shí)際的多階段決策過程，可供選取的策略有一定的范圍限制，這個(gè)范圍稱

11、為允許策略集合。允許策略集合中達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。給定k階段狀態(tài)變量x(k)的值后，如果這一階段的決策變量一經(jīng)確定，第k1階段的狀態(tài)變量x(k1)也就完全確定，即x(k1)的值隨x(k)和第k階段的決策u(k)的值變化而變化，那么可以把這一關(guān)系看成(x(k)，u(k))與x(k1)確定的對應(yīng)關(guān)系，用x(k1)=Tk(x(k)u(k))表示。這是從k階段到k1階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。最優(yōu)性原理最優(yōu)性原理:作為整個(gè)

12、過程的最優(yōu)策略，它滿足：相對前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略”。D也是B1到D的最短路徑……──事實(shí)正是如此，因此我們認(rèn)為這個(gè)例子滿足最優(yōu)性原理的要求。?C2?C2是A到C2的最短路徑，B1?B1?D，這些點(diǎn)的選擇構(gòu)成了這個(gè)例子的最優(yōu)策略，根據(jù)最優(yōu)性原理，這個(gè)策略的每個(gè)子策略應(yīng)是最優(yōu)：A?C2?B1?最優(yōu)性原理實(shí)際上是要求問題的最優(yōu)策略的子策略也是最優(yōu)。讓我們通過對前面的例子再分析來具體說明這一點(diǎn)：從A到D，我