1、a,1,第一講動(dòng)態(tài)規(guī)劃(DynamicProgramming),動(dòng)態(tài)規(guī)劃的基本概念和思想最短路徑問題投資分配問題背包問題排序問題,a,2,動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，是求解多階段決策過程最優(yōu)化問題的數(shù)學(xué)方法。動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)管理、工程技術(shù)、工農(nóng)業(yè)生產(chǎn)及軍事部門中都有著廣泛的應(yīng)用，并且獲得了顯著的效果。學(xué)習(xí)動(dòng)態(tài)規(guī)劃，我們首先要了解多階段決策問題。,a,3,最短路徑問題：給定一個(gè)交通網(wǎng)絡(luò)圖如下，其中兩點(diǎn)之間的數(shù)字表示距離（或運(yùn)費(fèi)），試求從A點(diǎn)到G點(diǎn)的最短距離（總運(yùn)輸費(fèi)用最?。?。,1,2,3,4,5,6,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G,5,3

2、,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,3,a,4,背包問題有一個(gè)徒步旅行者，其可攜帶物品重量的限度為a公斤，設(shè)有n種物品可供他選擇裝入包中。已知每種物品的重量及使用價(jià)值（作用），問此人應(yīng)如何選擇攜帶的物品（各幾件），使所起作用（使用價(jià)值）最大？,類似的還有工廠里的下料問題、運(yùn)輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題等。,a,5,生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時(shí)間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個(gè)生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計(jì)劃。,機(jī)器負(fù)荷分配問題：某種機(jī)器可以在高低兩

3、種不同的負(fù)荷下進(jìn)行生產(chǎn)。要求制定一個(gè)五年計(jì)劃，在每年開始時(shí)，決定如何重新分配完好的機(jī)器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。,航天飛機(jī)飛行控制問題：由于航天飛機(jī)的運(yùn)動(dòng)的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機(jī)飛行在不同環(huán)境中的情況，不斷地決定航天飛機(jī)的飛行方向和速度（狀態(tài)），使之能最省燃料和完成飛行任務(wù)（如軟著陸）。,a,6,根據(jù)過程的特性可以將過程按空間、時(shí)間等標(biāo)志分為若干個(gè)互相聯(lián)系又互相區(qū)別的階段。在每一個(gè)階段都需要做出決策，從而使整個(gè)過程達(dá)到最好的效果。各個(gè)階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個(gè)階段的決策確定后，就組成了一個(gè)決

4、策序列，因而也就決定了整個(gè)過程的一條活動(dòng)路線，這樣的一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策問題。,多階段決策過程的特點(diǎn)：,a,7,針對(duì)多階段決策過程的最優(yōu)化問題，美國數(shù)學(xué)家Bellman等人在20世紀(jì)50年代初提出了著名的最優(yōu)化原理，把多階段決策問題轉(zhuǎn)化為一系列單階段最優(yōu)化問題，從而逐個(gè)求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法：動(dòng)態(tài)規(guī)劃。,對(duì)最佳路徑（最佳決策過程）所經(jīng)過的各個(gè)階段，其中每個(gè)階段始點(diǎn)到全過程終點(diǎn)的路徑，必定是該階段始點(diǎn)到全過程終點(diǎn)的一切可能路徑中的最佳路徑（最優(yōu)決策），這就是Bellman提出的著名的最優(yōu)化原理。簡言之，一個(gè)最優(yōu)策略的子策略必然也是最優(yōu)的。,Bel

5、lman在1957年出版的DynamicProgramming是動(dòng)態(tài)規(guī)劃領(lǐng)域的第一本著作。,a,8,例1、從A地到E地要鋪設(shè)一條煤氣管道,其中需經(jīng)過三級(jí)中間站，兩點(diǎn)之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短？,二.最短路徑問題,A,B2,B1,B3,C1,C3,D1,D2,E,5,2,14,1,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C2,a,9,解：整個(gè)計(jì)算過程分四個(gè)階段，從最后一個(gè)階段開始。,第四階段（DE）：D有兩條路線到終點(diǎn)E。,顯然有,A,B2,B1,B3,C1,C3,D1,D2,E,5,2,14,1,12,6,1

6、0,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C2,a,10,首先考慮經(jīng)過的兩條路線,第三階段（CD）：C到D有6條路線。,(最短路線為),A,B2,B1,B3,C1,C3,D1,D2,E,5,2,14,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C2,a,11,A,B2,B1,B3,C1,C3,D1,D2,E,5,2,14,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C2,(最短路線為),考慮經(jīng)過的兩條路線,a,12,A,B2,B1,B3,C1,C3,D1,D2,E,5,2,14,12,6,1

7、0,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C2,(最短路線為),考慮經(jīng)過的兩條路線,a,13,A,B2,B1,B3,C1,C3,D1,D2,E,5,2,14,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C2,(最短路線為),第二階段（BC）：B到C有9條路線。,首先考慮經(jīng)過的3條路線,a,14,A,B2,B1,B3,C1,C3,D1,D2,E,5,2,14,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C2,(最短路線為),考慮經(jīng)過的3條路線,a,15,A,B2,B1,B3,C1,C3,D1,

8、D2,E,5,2,14,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C2,(最短路線為),考慮經(jīng)過的3條路線,a,16,A,B2,B1,B3,C1,C3,D1,D2,E,5,2,14,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,1,C2,(最短路線為),第一階段（AB）：A到B有3條路線。,（最短距離為19）,a,17,動(dòng)態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點(diǎn)在于，它可以把一個(gè)n維決策問題變換為幾個(gè)一維最優(yōu)化問題，從而一個(gè)一個(gè)地去解決。需指出：動(dòng)態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不

9、是一種算法。必須對(duì)具體問題進(jìn)行具體分析，運(yùn)用動(dòng)態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動(dòng)態(tài)規(guī)劃方法去求解。,即在系統(tǒng)發(fā)展的不同時(shí)刻（或階段）根據(jù)系統(tǒng)所處的狀態(tài)，不斷地做出決策；,動(dòng)態(tài)決策問題的特點(diǎn)：,系統(tǒng)所處的狀態(tài)和時(shí)刻是進(jìn)行決策的重要因素；,找到不同時(shí)刻的最優(yōu)決策以及整個(gè)過程的最優(yōu)策略。,a,18,動(dòng)態(tài)規(guī)劃方法的關(guān)鍵：在于正確地寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件（簡稱基本方程）。要做到這一點(diǎn)，就必須將問題的過程分成幾個(gè)相互聯(lián)系的階段，恰當(dāng)?shù)倪x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個(gè)大問題轉(zhuǎn)化成一組同類型的子問題，然后逐個(gè)求解。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個(gè)子問題的求解

10、中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個(gè)子問題所得的最優(yōu)解，就是整個(gè)問題的最優(yōu)解。,a,19,2、在多階段決策過程中，動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段和未來一段分開，又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的.,最優(yōu)化原理：作為整個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，相對(duì)于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略。也就是說，一個(gè)最優(yōu)策略的子策略也是最優(yōu)的。,3、在求整個(gè)問題的最優(yōu)策略時(shí)，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀

11、態(tài)便可逐段變換得到，從而確定了最優(yōu)路線。,a,20,動(dòng)態(tài)規(guī)劃求解的多階段問題的特點(diǎn)：每個(gè)階段的最優(yōu)決策過程只與本階段的初始狀態(tài)有關(guān)，而與以前各階段的決策（即為了到達(dá)本階段的初始狀態(tài)而采用哪組決策路線無關(guān)）。換言之，本階段之前的狀態(tài)與決策，只是通過系統(tǒng)在本階段所處的初始狀態(tài)來影響本階段及以后各個(gè)階段的決策?；蛘哒f，系統(tǒng)過程的歷史只能通過系統(tǒng)現(xiàn)階段的狀態(tài)去影響系統(tǒng)的未來。具有這種性質(zhì)的狀態(tài)稱為無后效性（即馬爾科夫性）狀態(tài)。動(dòng)態(tài)規(guī)劃方法只適用于求解具有無后效性狀態(tài)的多階段決策問題。,a,21,現(xiàn)有數(shù)量為a（萬元）的資金，計(jì)劃分配給n個(gè)工廠,用于擴(kuò)大再生產(chǎn)。假設(shè)：xi為分配給第i個(gè)工廠的資金數(shù)量（萬元

12、）；gi(xi)為第i個(gè)工廠得到資金后提供的利潤值（萬元）。問題：如何確定各工廠的資金數(shù)，使得總的利潤為最大。,據(jù)此，有下式：,三.投資分配問題,a,22,令：fk(x)表示以數(shù)量為x的資金分配給前k個(gè)工廠，所得到的最大利潤值。用動(dòng)態(tài)規(guī)劃求解，就是求fn(a)的問題。,當(dāng)k=1時(shí)，f1(x)=g1(x)（因?yàn)橹唤o一個(gè)工廠）,當(dāng)1kn時(shí)，其遞推關(guān)系如下：設(shè)：y為分給第k個(gè)工廠的資金（其中0yx），此時(shí)還剩xy（萬元）的資金需要分配給前k1個(gè)工廠,如果采取最優(yōu)策略，則得到的最大利潤為fk1(xy),因此總的利潤為：gk(y)fk1(xy),a,23,如果a是以萬元為資金分配單位，則式中的y只取非負(fù)

13、整數(shù)0，1，2，x。上式可變?yōu)椋?所以，根據(jù)動(dòng)態(tài)規(guī)劃的最優(yōu)化原理，有下式：,a,24,例2：設(shè)國家撥給60萬元投資，供四個(gè)工廠擴(kuò)建使用，每個(gè)工廠擴(kuò)建后的利潤與投資額的大小有關(guān)，投資后的利潤函數(shù)如下表所示。,解：依據(jù)題意，是要求f4(60)。,a,25,按順序解法計(jì)算。第一階段：求f1(x)。顯然有f1(x)g1(x)，得到下表,第二階段：求f2(x)。此時(shí)需考慮第一、第二個(gè)工廠如何進(jìn)行投資分配，以取得最大的總利潤。,a,26,最優(yōu)策略為（40，20），此時(shí)最大利潤為120萬元。,同理可求得其它f2(x)的值。,a,27,最優(yōu)策略為（30，20），此時(shí)最大利潤為105萬元。,a,28,最優(yōu)策略為

14、（20，20），此時(shí)最大利潤為90萬元。,最優(yōu)策略為（20，10），此時(shí)最大利潤為70萬元。,a,29,最優(yōu)策略為（10，0）或（0，10），此時(shí)最大利潤為20萬元。,f2(0)0。最優(yōu)策略為（0，0），最大利潤為0萬元。得到下表,最優(yōu)策略為（20，0），此時(shí)最大利潤為50萬元。,a,30,第三階段：求f3(x)。此時(shí)需考慮第一、第二及第三個(gè)工廠如何進(jìn)行投資分配，以取得最大的總利潤。,a,31,最優(yōu)策略為（20，10，30），最大利潤為155萬元。,同理可求得其它f3(x)的值。得到下表,a,32,第四階段：求f4(60)。即問題的最優(yōu)策略。,a,33,最優(yōu)策略為（20，0，30，10），最大

15、利潤為160萬元。,a,34,有一個(gè)徒步旅行者，其可攜帶物品重量的限度為a公斤，設(shè)有n種物品可供他選擇裝入包中。已知每種物品的重量及使用價(jià)值（作用），問此人應(yīng)如何選擇攜帶的物品（各幾件），使所起作用（使用價(jià)值）最大？,這就是背包問題。類似的還有工廠里的下料問題、運(yùn)輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題等。,四、背包問題,a,35,設(shè)xj為第j種物品的裝件數(shù)（非負(fù)整數(shù)）則問題的數(shù)學(xué)模型如下：,用動(dòng)態(tài)規(guī)劃方法求解，令fk(y)=總重量不超過y公斤，包中只裝有前k種物品時(shí)的最大使用價(jià)值。其中y0，k1,2,n。所以問題就是求fn(a),a,36,其遞推關(guān)系式為：,當(dāng)k=1時(shí)，有：,a,37,例

16、3：求下面背包問題的最優(yōu)解,解：a5，問題是求f3(5),a,38,a,39,a,40,a,41,a,42,所以，最優(yōu)解為X（1.1.0），最優(yōu)值為Z=13。,總結(jié)：解動(dòng)態(tài)規(guī)劃的一般方法:從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易钚?大)的方法。,a,43,排序問題指n種零件經(jīng)過不同設(shè)備加工是的順序問題。其目的是使加工周期為最短。,1、n1排序問題即n種零件經(jīng)過1種設(shè)備進(jìn)行加工，如何安排？,例5.1,五、排序問題,a,44,（1）平均通過設(shè)備的時(shí)間最小,按零件加工時(shí)間非負(fù)次序排列順序，其時(shí)間最小。（即將加工時(shí)間由小到大排列即可）,零件加工順序,平均通過時(shí)間,延遲時(shí)間=136=7,a,45,（2）按時(shí)交貨排列順序,零件加工順序,平均通過時(shí)間,延遲時(shí)間=0,a,46,（3）既滿足交貨時(shí)間，又使