運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本課件

1、運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,1,第八章 動(dòng)態(tài)規(guī)劃,8.1 多階段決策問(wèn)題 8.2 最優(yōu)化原理與動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型 8.3 離散確定性動(dòng)態(tài)規(guī)劃模型的求解 8.4 離散隨機(jī)性動(dòng)態(tài)規(guī)劃模型的求解 8.5 一般數(shù)學(xué)規(guī)劃模型的動(dòng)態(tài)規(guī)劃解法,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,2,理解動(dòng)態(tài)規(guī)劃基本概念、最優(yōu)化原理和基本方程，逆序法和順序解法，學(xué)習(xí)應(yīng)用動(dòng)態(tài)規(guī)劃解決多階段決策問(wèn)題。 重點(diǎn) :掌握動(dòng)態(tài)規(guī)劃模型結(jié)構(gòu)、逆序法算法原理、資源分配、設(shè)備更新、生產(chǎn)與存貯等問(wèn)題。,學(xué)習(xí)要點(diǎn)：,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,3,第一節(jié) 多階段的決策問(wèn)題,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,4,動(dòng)態(tài)規(guī)劃（Dynamic Programming）

2、,動(dòng)態(tài)規(guī)劃是解決復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的一種方法。是解決動(dòng)態(tài)系統(tǒng)多階段決策過(guò)程的基本方法之一。,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,5,動(dòng)態(tài)規(guī)劃：是解決多階段決策過(guò)程最優(yōu)化問(wèn)題的一種方法，無(wú)特定的數(shù)學(xué)模型。,可解決 與時(shí)間有關(guān)的動(dòng)態(tài)問(wèn)題 與時(shí)間無(wú)關(guān)的靜態(tài)問(wèn)題,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,6,多階段決策問(wèn)題 1）動(dòng)態(tài)決策將時(shí)間作為變量的決策問(wèn)題稱(chēng)為動(dòng)態(tài)決策。其基本特點(diǎn)是多次決策。 2）多階段決策問(wèn)題是一類(lèi)特殊形式的動(dòng)態(tài)決策問(wèn)題。是指這樣一類(lèi)活動(dòng)過(guò)程：系統(tǒng)的動(dòng)態(tài)過(guò)程可以按照時(shí)間進(jìn)程分為狀態(tài)互相聯(lián)系而又互相區(qū)別的各個(gè)階段，而且在每個(gè)階段都要進(jìn)行決策，當(dāng)每一個(gè)階段的決策確定以后，就完全確定了一個(gè)過(guò)程的活動(dòng)路線。,運(yùn)

3、籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,7,引例1 最短路線問(wèn)題,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,C1,C3,D1,A,B1,B3,B2,D2,E,C2,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,8,引例2 生產(chǎn)與存貯問(wèn)題 要求確定一個(gè)逐月的生產(chǎn)計(jì)劃，在滿足需求條件下，使一年的生產(chǎn)與存貯費(fèi)用之和最?。?引例3 投資決策問(wèn)題 某公司現(xiàn)有資金Q萬(wàn)元，在今后5年內(nèi)考慮給A，B，C，D 4個(gè)項(xiàng)目投資？ 引例4 設(shè)備更新問(wèn)題 現(xiàn)企業(yè)要決定一臺(tái)設(shè)備未來(lái)8年的更新計(jì)劃，問(wèn)應(yīng)在哪些年更新設(shè)備可使總費(fèi)用最?。?運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,9,動(dòng)態(tài)規(guī)劃方法的特點(diǎn),優(yōu)點(diǎn)： 1）許多問(wèn)題用動(dòng)態(tài)規(guī)劃

4、求解比線性規(guī)劃、非線性規(guī)劃更有效，特別是離散性問(wèn)題，解析數(shù)學(xué)無(wú)用武之地，而動(dòng)態(tài)規(guī)劃成為得力工具。 2）某些情況下，用動(dòng)態(tài)規(guī)劃處理不僅能作定性描述分析，且可利用計(jì)算機(jī)給出求其數(shù)值解的方法。,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,10,動(dòng)態(tài)規(guī)劃方法的特點(diǎn),缺點(diǎn)： 1）沒(méi)有統(tǒng)一的處理方法，求解時(shí)要根據(jù)問(wèn)題的性質(zhì)，結(jié)合多種數(shù)學(xué)技巧。因此，實(shí)踐經(jīng)驗(yàn)及創(chuàng)造性思維將起重要作用。 2）“維數(shù)障礙”：當(dāng)變量個(gè)數(shù)太多時(shí)，由于計(jì)算機(jī)內(nèi)存和速度的限制導(dǎo)致問(wèn)題無(wú)法解決。有些問(wèn)題由于涉及的函數(shù)沒(méi)有理想的性質(zhì)使問(wèn)題只能用動(dòng)態(tài)規(guī)劃描述，而不能用動(dòng)態(tài)規(guī)劃方法求解。,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,11,第二節(jié) 最優(yōu)化原理與動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型

5、一 最短路線問(wèn)題求解,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(E)=0,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,12,考慮一個(gè)階段的最優(yōu)選擇,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D1)=3,f(E)=0,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,13,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(D1)=3,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,

6、3,3,4,考慮一個(gè)階段的最優(yōu)選擇,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,14,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C1)=4,f(D1)=3,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,考慮二個(gè)階段的最優(yōu)選擇,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,15,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C2)=7,f(D1)=3,f(C1)=4,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,2,5,3,4,考慮二個(gè)階段的最優(yōu)選擇,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,16,C

7、1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(C1)=4,f(C2)=7,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,考慮二個(gè)階段的最優(yōu)選擇,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,17,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B1)=11,f(C2)=7,f(C1)=4,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,考慮三個(gè)階段的最優(yōu)選擇,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,18,C1,C

8、3,D1,A,B1,B3,B2,D2,E,C2,f (D2)=4,f (E)=0,f(C3)=6,f (D1)=3,f(B2)=7,f(C2)=7,f(C1)=4,f(B1)=11,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,考慮三個(gè)階段的最優(yōu)選擇,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,19,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,f(C1)=4,f(B1)=11,f(B2)=7,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,

9、考慮三個(gè)階段的最優(yōu)選擇,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,20,10,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,f(C1)=4,f(A)=11,f(B2)=7,f(B1)=11,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,四個(gè)階段聯(lián)合考慮從A點(diǎn)到E點(diǎn)的最優(yōu)選擇,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,21,6,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,f(C1)=

10、4,f(A)=11,f(B2)=7,f(B1)=11,狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài),A （ A，B3） B3,7,5,3,2,4,5,5,1,2,5,3,1,4,6,3,3,3,3,4,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,22,6,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,f(C1)=4,f(A)=11,f(B2)=7,f(B1)=11,狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài),A （ A，B3） B3 （ B3， C2 ） C

11、2,7,5,3,2,4,5,5,1,2,5,3,1,4,6,3,3,3,3,4,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,23,6,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,f(C1)=4,f(A)=11,f(B2)=7,f(B1)=11,狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài),A （ A，B3） B3 （ B3， C2 ） C2 （ C2， D2 ） D2,7,5,3,2,4,5,5,1,2,5,3,1,4,6,3,3,3,3,4,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,24,6,

12、C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,f(C1)=4,f(A)=11,f(B2)=7,f(B1)=11,狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài),A （ A，B3） B3 （ B3， C2 ） C2 （ C2， D2 ） D2 （ D2， E） E,7,5,3,2,4,5,5,1,2,5,3,1,4,6,3,3,3,3,4,從A到E的最短路徑為11，路線為AB3C2 D2 E,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,25,通過(guò)上例的討論，可以看到多級(jí)決策過(guò)程具有以下特

13、點(diǎn)：,（1）把整個(gè)過(guò)程看成（或認(rèn)為地分成）n個(gè)具有遞推關(guān)系的單級(jí)過(guò)程。 （2）采取逐級(jí)分析的方法，一般由最后一級(jí)開(kāi)始倒向進(jìn)行。 （3）在每一級(jí)決策時(shí)，不只考慮本級(jí)的性能指標(biāo)的最優(yōu)，而且同時(shí)考慮本級(jí)及以后的總性能指標(biāo)最優(yōu)，因此它是根據(jù)“全局”最優(yōu)作出本級(jí)決策的。,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,26,動(dòng)態(tài)規(guī)劃法較之窮舉法的優(yōu)點(diǎn): (1) 容易計(jì)算出結(jié)果； (2) 動(dòng)態(tài)規(guī)劃的計(jì)算結(jié)果不僅得到了從起始點(diǎn)到最終點(diǎn)的最短路線，而且得到了中間段任一點(diǎn)到最終點(diǎn)的最短路線 。,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,27,動(dòng)態(tài)規(guī)劃方法的基本思想： (1)將多階段決策過(guò)程劃分階段，恰當(dāng)?shù)剡x取狀態(tài)變量、決策變量及定義最優(yōu)指標(biāo)函數(shù)

14、從而把問(wèn)題化成一族同類(lèi)型的子問(wèn)題，然后逐個(gè)求解。 (2)求解時(shí)從邊界條件開(kāi)始，逆(或順)過(guò)程行進(jìn)方向，逐段遞推尋優(yōu)。在每一個(gè)子問(wèn)題求解時(shí)，都要使用它前面已求出的子問(wèn)題的最優(yōu)結(jié)果，最后一個(gè)子問(wèn)題的最優(yōu)解，就是整個(gè)問(wèn)題的最優(yōu)解。 (3)動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段與未來(lái)各段分開(kāi)，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法，因此每段的最優(yōu)決策選取是從全局考慮的，與該段的最優(yōu)選擇一般是不同的。,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,28,二、基本概念和基本原理,動(dòng)態(tài)規(guī)劃模型要用到的概念： (1)階段; (2)狀態(tài); (3)決策和策略; (4)狀態(tài)轉(zhuǎn)移律; (5)指標(biāo)函數(shù)。,1、階段：將所給問(wèn)題的過(guò)程，按時(shí)

15、間或空間特征分解成若干互相聯(lián)系的階段，以便按次序去求每階段的解，常用字母k表示階段變量。,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,29,2、狀態(tài)：各階段開(kāi)始時(shí)的客觀條件叫做狀態(tài)。 狀態(tài)變量：描述各階段狀態(tài)的變量，用sk表示第k階段的狀態(tài)變量。 狀態(tài)集合：狀態(tài)變量的取值集合，用Sk表示。,一階段：S1A 二階段：S2B1,B2,B3 三階段：S3C1,C2,C3 四階段：S4D1,D2,一階段：S1A 二階段：S2B1,B2,B3 三階段：S3C1,C2,C3 四階段：S4D1,D2,二、基本概念和基本原理,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,30,二、基本概念和基本原理,二、基本概念和基本原理,3、決策：當(dāng)各段的

16、狀態(tài)取定以后，就可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱(chēng)為決策。 決策變量：表示決策的變量，稱(chēng)為決策變量，常用xk(sk)表示第k階段當(dāng)狀態(tài)為sk時(shí)的決策變量。 允許決策集合：決策變量的取值往往限制在一定范圍內(nèi)，我們稱(chēng)此范圍為允許決策集合，用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合。,D2( B1)=C1,C2 D2( B2)=C1,C2,C3 如狀態(tài)為B1時(shí)選擇C2，可表示為：u2(B1)=C2,D2( B1)=C1,C2 D2( B2)=C1,C2,C3 如狀態(tài)為B1時(shí)選擇C2，可表示為： x2(B1)=C2,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,31,二、基本概

17、念和基本原理,4 策略：各段決策確定后，整個(gè)問(wèn)題的決策序列就構(gòu)成一個(gè)策略，用p1,nx1(s1),x2(s2),.xn(sn)表示。 允許策略集合：對(duì)每個(gè)實(shí)際問(wèn)題，可供選擇的策略有一定范圍，稱(chēng)為允許策略集合，記作P1,n，使整個(gè)問(wèn)題達(dá)到最優(yōu)效果的策略就是最優(yōu)策略。,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,32,二、基本概念和基本原理,5、狀態(tài)轉(zhuǎn)移方程：動(dòng)態(tài)規(guī)劃中本階段的狀態(tài)往往是上一階段狀態(tài)和上一階段的決策結(jié)果。 第k段的狀態(tài)sk，本階段決策為xk(sk)，則第k+1段的狀態(tài)sk+1也就完全確定，它們的關(guān)系可用公式表示：sk+1=Tk(sk,xk),運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,33,6、指標(biāo)函數(shù)：用于衡量

18、所選定策略優(yōu)劣的數(shù)量指標(biāo)。 它分為階段指標(biāo)函數(shù)和過(guò)程指標(biāo)函數(shù)。 階段指標(biāo)函數(shù)是指第k段，從狀態(tài)sk出發(fā)，采取決策xk時(shí)的效益，用Vk(sk,uk)表示。 過(guò)程指標(biāo)函數(shù)記為fk(sk)：表示從第k段狀態(tài)sk按預(yù)定指標(biāo)到過(guò)程終止時(shí)的效益值。,二、基本概念和基本原理,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,34,最簡(jiǎn)單的方法窮舉法。共有多少條路徑，依次計(jì)算并比較。 動(dòng)態(tài)規(guī)劃方法本方法是從過(guò)程的最后一段開(kāi)始，用逆序遞推方法求解，逐步求出各段各點(diǎn)到終點(diǎn)的最短路線，最后求得起始點(diǎn)到終點(diǎn)的最短路線。,三、最優(yōu)化原理與動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,35,最優(yōu)化原理Optimization Princip

19、le,作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)： 無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)先前決策所形成的狀態(tài)而言，余下的諸決策必構(gòu)成最優(yōu)策略。,若M是從A到B的最優(yōu)路線上的一點(diǎn)，則從M到B的路線也是最優(yōu)的。,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,36,動(dòng)態(tài)規(guī)劃的基本方程（最優(yōu)化原理的應(yīng)用）,根據(jù)最優(yōu)化原理得到的計(jì)算動(dòng)態(tài)規(guī)劃問(wèn)題的遞（逆）推關(guān)系式：,邊界條件： k=n時(shí)，fn+1(sn+1)=0,邊界條件： k=n時(shí)， fn+1(sn+1)=1,Opt: optimization, max or min vk: k階段的指標(biāo)函數(shù) fk+1:k+1階段的最優(yōu)指標(biāo)函數(shù)值 fk:k階段的最優(yōu)指標(biāo)函數(shù)值,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版

20、版本,37,構(gòu)成動(dòng)態(tài)規(guī)劃模型的條件-1,根據(jù)時(shí)間或空間的自然特征，實(shí)際問(wèn)題能恰當(dāng)?shù)貏澐譃槿舾呻A段，形成多階段決策的過(guò)程,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,38,構(gòu)成動(dòng)態(tài)規(guī)劃模型的條件-2,正確的選擇狀態(tài)變量S 動(dòng)態(tài)規(guī)劃的狀態(tài)應(yīng)具有三個(gè)特征： 能夠用來(lái)描述受控過(guò)程的演變特征； 滿足無(wú)后效性：如果某階段狀態(tài)給定，則在這階段以后過(guò)程的發(fā)展只與當(dāng)前的狀態(tài)有關(guān)，而與過(guò)去的歷史無(wú)關(guān)?；虍?dāng)前的狀態(tài)是過(guò)去歷史發(fā)展的一個(gè)總結(jié)，過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前的狀態(tài)影響未來(lái)的發(fā)展。 可知性：各階段狀態(tài)變量的值，直接或間接地都是可以知道的。,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,39,構(gòu)成動(dòng)態(tài)規(guī)劃模型的條件 - 3,確定決策變量sk的含

21、義及每階段的允許決策集合Dk(sK),運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,40,構(gòu)成動(dòng)態(tài)規(guī)劃模型的條件-4,正確寫(xiě)出狀態(tài)轉(zhuǎn)移方程 sk+1=T(sk,xk(sk) 或 sk+1=T(sk,xk),運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,41,構(gòu)成動(dòng)態(tài)規(guī)劃模型的條件-5,明確指標(biāo)函數(shù)Vk,n的關(guān)系 一般有兩種形式 和式 積式,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,42,四 逆序解法與順序解法 如果尋優(yōu)的方向與多階段決策過(guò)程的實(shí)際行進(jìn)方向相反，從最后一段開(kāi)始計(jì)算逐段前推，求得全過(guò)程的最優(yōu)策略，稱(chēng)為逆序解法。 順序解法的尋優(yōu)方向同于過(guò)程的行進(jìn)方向，計(jì)算時(shí)從第一段開(kāi)始逐段向后遞推，計(jì)算后一階段要用到前一階段的求優(yōu)結(jié)果，最后一段計(jì)算

22、的結(jié)果就是全過(guò)程的最優(yōu)結(jié)果。,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,43,第一步：k=0 狀態(tài)：s1A,f0(A)0,求解步驟,順序解法求解,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,44,第二步：k=1 狀態(tài)：B1 B2,x1*(B1)=A,x1*(B2)=A,f1(B1)4,f1(B2)5,(4),(5),運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,45,第三步：k=2 狀態(tài)：C1 C2 C3 C4,u2*(C1)=B1,x2*(C2)=B1,x2*(C3)=B1,f2(C1)6,f2(C2)7,f2(C3)10,x2*(C4)=B2,f2(C4)12,(6),(7),(10),(12),x2*(C1)=B1,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第

23、五版版本,46,第四步：k=3 狀態(tài)：D1 D2 D3,x3*(D1)=C1或C2,x3*(D2)=C2,x3*(D3)=C3,f3(D1)11,f3(D2)12,f3(D3)14,(11),(12),(14),運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,47,第五步：k=4 狀態(tài)：E1 E2,x4*(E1)=D1,x4*(E2)=D2,f4(E1)14,f4(E2)14,(14),(14),運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,48,第六步：k=5 狀態(tài)：F,u5*(F)=E2,f5(F)17,(17),即從A到F的最短距離為17。 最優(yōu)路線為：AB1C2D2E2F,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,49,逆序解法與順序解

24、法建模的不同點(diǎn),1狀態(tài)轉(zhuǎn)移方式不同 sk+1=Tk(sk,xk) sk=Tk(sk+1,xk),運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,50,2指標(biāo)函數(shù)的定義不同 逆序解法中，我們定義最優(yōu)指標(biāo)函數(shù)fk(sk)表示第k段從狀態(tài)sk出發(fā)，到終點(diǎn)后部子過(guò)程最優(yōu)效益值，f1(s1)是整體最優(yōu)函數(shù)值。 順序解法中，定義最優(yōu)指標(biāo)函數(shù)fk(sk+1)表示第k段時(shí)從起點(diǎn)到狀態(tài)sk+1的前部子過(guò)程最優(yōu)效益值。fn(sn+1)是整體最優(yōu)函數(shù)值。,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,51,3. 基本方程形式不同 (1)當(dāng)指標(biāo)函數(shù)為階段指標(biāo)和形式 逆序解法,則基本方程為：,則基本方程為：,順序解法,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,52,(2

25、)當(dāng)指標(biāo)函數(shù)為階段指標(biāo)積形式 逆序解法,基本方程為：,基本方程為：,順序解法,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,53,第3節(jié) 離散確定型動(dòng)態(tài)規(guī)劃 模型求解,Solution of Discrete Certain DP Model,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,54,例4,某一警衛(wèi)部門(mén)共有12支巡邏隊(duì)，負(fù)責(zé)4個(gè)要害部位A、B、C、D的警衛(wèi)巡邏。 對(duì)每個(gè)部位可分別派出2-4支巡邏隊(duì)，并且由于派出巡邏隊(duì)數(shù)的不同，各部位預(yù)期在一段時(shí)期內(nèi)可能造成的損失有差別，具體數(shù)字見(jiàn)表8-1。 問(wèn)該警衛(wèi)部門(mén)應(yīng)往各部位分別派多少支巡邏隊(duì)，使總的預(yù)期損失為最小。,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,55,解-1,階段變量k ：把12支

26、巡邏隊(duì)往4個(gè)部位派遣看成依次分四個(gè)階段(k=1，2，3，4)。 狀態(tài)變量sk：表示每個(gè)階段初擁有的可派遣的巡邏隊(duì)數(shù)是前面階段決策的結(jié)果，也是本階段決策的依據(jù) 決策變量xk：表示各階段對(duì)各部位派出的巡邏隊(duì)數(shù)， 各階段允許的決策集合Dk(sk)為： Dk(sk)=xk|2xk4| (k=1,2,3,4),運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,56,解-2,狀態(tài)轉(zhuǎn)移方程：sk+1=sk-xk (k=1,2,3,4) 每階段初擁有可派遣的巡邏隊(duì)數(shù)量等于上階段初擁有的數(shù)量減去上階段派出的數(shù)量 過(guò)程函數(shù)為階段指標(biāo)函數(shù)之和： 階段指標(biāo)函數(shù)vk(xk)表示k階段派出的巡邏隊(duì)數(shù)為xk時(shí)，該階段的部位的預(yù)期損失值,運(yùn)籌學(xué)基

27、礎(chǔ)及應(yīng)用第五版版本,57,解-3,fk(sk)：表示從k階段狀態(tài)為sk出發(fā)，采用最優(yōu)子策略到過(guò)程結(jié)束時(shí)的預(yù)期損失值，有 先考慮給D部位派巡邏隊(duì)，即k=4，上式可寫(xiě)為 邊界條件f5(s5)=0 ，所以,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,58,解-4,因D4（s4）=2，3，4，又s4的可能值是2s46，故由表8-1的數(shù)據(jù)，可得下表的結(jié)果,總共12支巡邏隊(duì)，每部位24支巡邏隊(duì)。,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,59,解-5,聯(lián)合考慮對(duì)C、D兩個(gè)部位派巡邏隊(duì)，k=3，有： 因D3(s3)=2,3,4，4s38，可得如下結(jié)果,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,60,解-6,考慮對(duì)B、C、D三個(gè)部位派巡邏隊(duì)，k=2，有 由D2(s2)=2,3,4，8s210，可得如下結(jié)果,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,61,解-7,考慮對(duì)A、B、C、D四個(gè)部隊(duì)派巡邏隊(duì)，即k=1時(shí)，有 因s1=12, D1(s1)=2,3,4,可得如下結(jié)果,運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版版本,62,解-8,最優(yōu)策略為： A部位4支，B部位2支，C部位2支，D部位4支，總預(yù)期損失為97單位。,運(yùn)