運(yùn)籌學(xué)基礎(chǔ) 課件 第5章

第5章動(dòng)態(tài)規(guī)劃5.1多階段決策問題5.2網(wǎng)絡(luò)模型5.3Bellman遞歸方程5.4典型案例

5.1多階段決策問題

當(dāng)問題的對(duì)象處于某種狀態(tài)x時(shí),會(huì)有一個(gè)決策集合μ{x}(在最優(yōu)控制中,決策也稱為控制),當(dāng)選定某種決策μi∈μ{x}并且付諸行動(dòng)之后,問題的對(duì)象會(huì)從狀態(tài)x轉(zhuǎn)移為狀態(tài)y,一般可記為行動(dòng)的成本記為

例5-1(多階段最短路問題)對(duì)如圖5-1所示的圖求解從起點(diǎn)S到終點(diǎn)E的最短路。

如果將圖5-1中的點(diǎn)看作決策問題的狀態(tài),則這個(gè)問題具有明顯的階段性,且狀態(tài)僅在相鄰的狀態(tài)之間向后轉(zhuǎn)移,因此這是一個(gè)多階段決策問題。狀態(tài)集合為

圖5-1多階段最短路問題

例5-2(背包問題)給定n種物品,每種物品都有自己的質(zhì)量wi和價(jià)值ri,背包的最大承重為W,請(qǐng)選擇裝入背包物品的種類和數(shù)量,使裝入背包的物品總價(jià)值最高。

假設(shè)背包最大承重W=10,可裝物品的單件質(zhì)量和單件價(jià)值如表5-1所示,可裝物品的數(shù)量足夠。

第4階段:考慮裝入C類物品,將第3階段狀態(tài)作為起始狀態(tài),其對(duì)應(yīng)的決策、到達(dá)狀態(tài)及行動(dòng)收益如表5-3所示。

第5階段:只有一個(gè)結(jié)束狀態(tài),記為x26。從第4階段的狀態(tài)到x26的狀態(tài)轉(zhuǎn)移收益均為0。

5.2網(wǎng)絡(luò)模型在多階段決策問題中,如果令狀態(tài)集合X=X1∪X2∪…∪Xn代表網(wǎng)絡(luò)上的點(diǎn)集,狀態(tài)x到y(tǒng)的轉(zhuǎn)移y=f(x,μi)作為網(wǎng)絡(luò)上的邊,而狀態(tài)轉(zhuǎn)移的行動(dòng)費(fèi)用作為邊上的權(quán)重,則每一個(gè)多階段決策問題都可以轉(zhuǎn)換為一個(gè)網(wǎng)絡(luò)模型,即其中,

多階段決策問題網(wǎng)絡(luò)模型建立的過程如下:

步驟1:分析決策問題的狀態(tài)有哪些,將時(shí)間或者步驟分成n個(gè)階段,分析每個(gè)階段的狀態(tài),由此可以確定網(wǎng)絡(luò)上點(diǎn)的子集Vi。

步驟2:分析狀態(tài)之間是否有可能存在可行的遷移,如果存在,則分析狀態(tài)遷移的成本或者費(fèi)用,并將其作為兩點(diǎn)之間的狀態(tài)轉(zhuǎn)移費(fèi)用,由此可以確定序號(hào)相鄰子集之間的邊及邊的權(quán)重。

步驟3:根據(jù)問題分析起始狀態(tài)和最終狀態(tài),確定起點(diǎn)和終點(diǎn)。

5.3Bellman遞歸方程

5.3.1最優(yōu)性原則最優(yōu)性原則對(duì)以后階段所做出的未來(lái)決策將會(huì)產(chǎn)生一個(gè)最優(yōu)策略,它與前面各階段所采用的策略無(wú)關(guān)。在多階段決策問題的模型中,假設(shè)對(duì)階段k以后所做出的最優(yōu)策略為π*=(μk,…,μn),即則根據(jù)最優(yōu)性原則,π*與前面各階段X1,…,Xk-1所采用的策略無(wú)關(guān)。

最優(yōu)子結(jié)構(gòu)定理對(duì)滿足最優(yōu)性原則的多階段決策問題,最優(yōu)決策序列的子序列也是最優(yōu)的。

證明:假設(shè)路徑(A,A1,A2,…,Am,C,B1,B2,…,Bn,B)為從A到B的最優(yōu)決策序列,那么其子序列一定也是最優(yōu)的。例如,A,A1,A2,…,Am,C一定是從A到C的最優(yōu)決策序列,C,B1,B2,…,Bn,B也一定是從C到B的最優(yōu)決策序列。利用反證法很容易證明(證明略)。

需要注意的是,如果多階段決策問題不滿足最優(yōu)性原則,則不一定滿足最優(yōu)子結(jié)構(gòu)定理,也就是說,其最優(yōu)決策序列的子序列不一定是最優(yōu)的。

例5-3某導(dǎo)彈部隊(duì)的導(dǎo)彈火力單元隱蔽待機(jī)于待機(jī)地p1和p2,接收到3波次火力打擊任務(wù)。火力單元需要通過網(wǎng)絡(luò)(見圖5-2)機(jī)動(dòng)到某導(dǎo)彈倉(cāng)庫(kù)dj(j=1,2,…,5)裝載導(dǎo)彈,然后通過網(wǎng)絡(luò)機(jī)動(dòng)到某一個(gè)發(fā)射點(diǎn)ri

(i=1,2,…,30)發(fā)射導(dǎo)彈,完成1波次的發(fā)射任務(wù)。整個(gè)任務(wù)需要完成3波次的打擊。假設(shè)為了提高生存能力,在整個(gè)火力打擊任務(wù)中,所有的火力單元均不會(huì)第二次使用同一個(gè)發(fā)射點(diǎn),直到所有的火力單元都完成3波次火力打擊任務(wù)為止,則可以建立如圖5-3所示的多階段決策問題的網(wǎng)絡(luò)模型。

圖5-2多波次導(dǎo)彈火力打擊行動(dòng)網(wǎng)絡(luò)

圖5-33波次導(dǎo)彈火力打擊行動(dòng)問題的多階段網(wǎng)絡(luò)模型

圖5-3中,虛線所示的有向邊的權(quán)重為狀態(tài)轉(zhuǎn)移所對(duì)應(yīng)的物理上兩個(gè)地點(diǎn)的最短路的距離?；鹆卧娜我饪尚行袆?dòng)路徑一定對(duì)應(yīng)圖5-3所示模型中的一條從s到e的路,但是,一條從s到e的路未必是火力單元可行的行動(dòng)路徑,因?yàn)橐獫M足發(fā)射點(diǎn)不重復(fù)的約束。例如,存在這種情況:從s到e的最短路如圖5-4中加粗實(shí)線箭頭所示,但是,根據(jù)發(fā)射點(diǎn)不重復(fù)的約束,這不是火力單元的一條可行路徑。

圖5-4模型的可行路徑未必是火力單元的可行路徑

因?yàn)橐獫M足發(fā)射點(diǎn)不重復(fù)的約束,這個(gè)模型不滿足最優(yōu)性原則,也就是對(duì)以后階段所做出的未來(lái)決策將會(huì)產(chǎn)生一個(gè)最優(yōu)策略,它與前面各階段所采用的策略不是無(wú)關(guān)的。這個(gè)模型也不滿足最優(yōu)子結(jié)構(gòu)定理。對(duì)于某個(gè)火力單元的最優(yōu)路徑,其子路徑不一定是最優(yōu)的。例如,存在這種情況:某火力單元的最優(yōu)路徑如圖5-5中加粗實(shí)線箭頭所示,則從第5階段的d1到e的子路徑不一定是最優(yōu)的。

圖5-5-3波次導(dǎo)彈火力打擊行動(dòng)模型不滿足最優(yōu)子結(jié)構(gòu)定理

5.3.2兩個(gè)推論

5.3.3兩個(gè)方程

5.3.4多階段最短路問題的求解

例5-4利用Bellman逆序方程求解多階段最短路問題(見圖5-1)的具體步驟如下:

因此,從S到E的最短路長(zhǎng)度為21。最短路的序列可以從求解的過程數(shù)據(jù)倒推得到。例5-1中,最短路的序列包括以下幾個(gè):

利用Bellman順序方程求解多階段最短路問題(見圖5-1)的具體步驟如下:

5.4典型案例

5.4.1背包問題1.問題描述背包問題可以描述為:給定n種物品,每種物品都有自己的質(zhì)量wi和價(jià)值ri。背包的最大承重為W,請(qǐng)選擇裝入背包物品的種類和數(shù)量,使裝入背包的物品總價(jià)值最高。

如果令裝入第i(i=1,2,…,n)種物品的數(shù)量為xi,則可以建立如下背包問題的整數(shù)規(guī)劃模型:

2.建立動(dòng)態(tài)規(guī)劃模型

建立動(dòng)態(tài)規(guī)劃模型的具體步驟如下:

步驟1:輸入背包問題的參數(shù),確定階段的數(shù)量。將問題分成n+2個(gè)階段,增加一個(gè)虛擬的起始狀態(tài)和一個(gè)虛擬的結(jié)束狀態(tài),中間每個(gè)階段考慮一種類型的物品。因?yàn)橐畲蠡嘲形锲返膬r(jià)值,所以將單位物品的價(jià)值加上一個(gè)負(fù)號(hào)。

步驟2:建立每個(gè)階段狀態(tài)的集合,第1階段的狀態(tài)設(shè)定為一個(gè)虛擬的起點(diǎn),最后一個(gè)階段也就是第NStage階段的狀態(tài)設(shè)定為一個(gè)虛擬的終點(diǎn)。狀態(tài)為當(dāng)前背包中物品的質(zhì)量。狀態(tài)之間是否可以轉(zhuǎn)移或者說點(diǎn)之間是否有邊相連,取決于兩個(gè)狀態(tài)之間的轉(zhuǎn)移是否對(duì)應(yīng)一種可行的裝包方案,也就是包里物品總質(zhì)量的增加是否是當(dāng)前物品的整數(shù)倍。相鄰兩個(gè)階段點(diǎn)xi(k)和xi-1(h)的狀態(tài)轉(zhuǎn)移采用如下規(guī)則確定:

若mod((xi(k)-xi-1

(h)),wi)=0,且xi(k)≥xi-1

(h),則兩者之間有邊相連,邊的權(quán)重為

建立的背包問題模型如圖5-6所示。圖5-6背包問題的動(dòng)態(tài)規(guī)劃模型

3.求解

利用動(dòng)態(tài)規(guī)劃的順序方程進(jìn)行求解。

程序運(yùn)行結(jié)果如圖5-7所示,其中最優(yōu)的決策序列使用加粗的路徑標(biāo)識(shí)。

圖5-7背包問題的動(dòng)態(tài)規(guī)劃順序方程求解

5.4.2設(shè)備更新問題

1.問題描述

設(shè)備更新問題可以使用動(dòng)態(tài)規(guī)劃的模型求解。設(shè)備更新問題是指機(jī)器或者設(shè)備(如汽車)會(huì)隨著使用年數(shù)的增加而老化,從而導(dǎo)致運(yùn)行成本c的增加,折舊現(xiàn)值s的減少,收入r的減少,但是購(gòu)買新機(jī)器又要花費(fèi)一大筆費(fèi)用,因此需要我們決定什么時(shí)候替換現(xiàn)有的機(jī)器,什么時(shí)候再替換,等等,以便在未來(lái)的N年內(nèi)將總成本降到最低。

例5-6某部門要對(duì)一臺(tái)已經(jīng)使用了2年的設(shè)備確定今后5年的最優(yōu)更新策略。已知設(shè)備的最大使用年限為6年,購(gòu)買一臺(tái)新機(jī)器的費(fèi)用是1000萬(wàn)元。該問題的基本數(shù)據(jù)見表5-4。

2.建立動(dòng)態(tài)規(guī)劃模型

假設(shè)我們必須在N個(gè)時(shí)間段內(nèi)(如年份)都擁有這樣一臺(tái)機(jī)器,令y表示機(jī)器當(dāng)前的年齡,c(i)表示一臺(tái)年初年齡為i的機(jī)器運(yùn)行一年的運(yùn)行成本,s(i)表示一臺(tái)年初年齡為i的機(jī)器折舊之后的現(xiàn)值,r(i)表示一臺(tái)年初年齡為i的機(jī)器運(yùn)行一年能帶來(lái)的收入,Newr表示一臺(tái)新機(jī)器(0歲)的價(jià)格,則建立模型如下:

(1)確定階段。

(2)確定每個(gè)階段的狀態(tài)。

(3)確定相鄰階段狀態(tài)之間的轉(zhuǎn)移是否存在以及收益是多少。

3.求解

求解的具體步驟如下:

步驟1:輸入問題的基本參數(shù)。

步驟2:建立每個(gè)階段狀態(tài)的集合,第1階段的狀態(tài)設(shè)定為一個(gè)虛擬的起點(diǎn),最后一階段也就是第NStage階段的狀態(tài)設(shè)定為一個(gè)虛擬的終點(diǎn)。中間的階段狀態(tài)設(shè)定為各種可能的設(shè)備年齡。

步驟3:建立鄰接矩陣,也就是檢驗(yàn)每個(gè)前一階段的點(diǎn)與后一階段的點(diǎn)之間可能存在的狀態(tài)轉(zhuǎn)移,并計(jì)算狀態(tài)轉(zhuǎn)移的權(quán)重,將其存入狀態(tài)轉(zhuǎn)移矩陣A。

得到的動(dòng)態(tài)規(guī)劃模型如圖5-8所示。圖5-8設(shè)備更新問題的動(dòng)態(tài)規(guī)劃模型

步驟4:利用動(dòng)態(tài)規(guī)劃的遞歸方程進(jìn)行求解。

程序運(yùn)行結(jié)果如圖5-9所示,其中最優(yōu)的決策序列使用加粗的路徑標(biāo)識(shí)。

圖5-9設(shè)備更新問題的動(dòng)態(tài)規(guī)劃最優(yōu)解

5.4.3過河問題

1.問題描述

小明一家四口人要過河。單獨(dú)過河爸爸要1分鐘,媽媽要2分鐘,小明要5分鐘,弟弟要10分鐘。最多兩個(gè)人同時(shí)過河,并且只有一個(gè)手電筒,每次都需要手電筒。兩人過河按慢的時(shí)間算。請(qǐng)?jiān)O(shè)計(jì)過河方案,使一家人過河總時(shí)間最少。

2.問題分析

為了描述方便,將爸爸、媽媽、小明、弟弟分別記為A、B、C、D。假設(shè)過河時(shí)的順序?yàn)閺淖蟮接?回程時(shí)的順序?yàn)閺挠业阶?過河的時(shí)候兩個(gè)人,回程的時(shí)候一個(gè)人。

將系統(tǒng)的狀態(tài)記為沒有過河的人的組合,因此,起始狀態(tài)記為ABCD,代表四個(gè)人都沒有過河;最終的狀態(tài)為?,代表一家人都已過河。

3.建立模型

步驟1:第1階段的狀態(tài)集合為X1={ABCD},決策集合為{AB,AC,AD,BC,BD,CD},代表選擇兩個(gè)尚未過河的人一起過河,從起始狀態(tài)到第2階段的決策、到達(dá)狀態(tài)、行動(dòng)耗時(shí)如表5-5所示。

步驟2:由表5-5可得第2階段的狀態(tài)集合為

下一步?jīng)Q策的內(nèi)容為選擇一個(gè)已經(jīng)過河的人帶手電筒回來(lái),其決策、到達(dá)狀態(tài)、行動(dòng)耗時(shí)如表5-6所示。

步驟3:由表5-6可得第3階段的狀態(tài)集合為

下一步?jīng)Q策的內(nèi)容為選擇兩個(gè)尚未過河的人一起過河,其決策、到達(dá)狀態(tài)、行動(dòng)耗時(shí)如表5-7所示。

步驟4:由表5-7可得第4階段的狀態(tài)集合為

下一步?jīng)Q策的內(nèi)容為選擇一個(gè)已經(jīng)過河的人帶手電筒回來(lái),其決策、到達(dá)狀態(tài)、行動(dòng)耗時(shí)如表5-8所示。

步驟5:由表5-8可得第5階段的狀態(tài)集合為

下一步?jīng)Q策的內(nèi)容為選擇兩個(gè)尚未過河的人一起過河,其決策、到達(dá)狀態(tài)、行動(dòng)耗時(shí)如表5-9所示。

4.求解

上述動(dòng)態(tài)規(guī)劃模型中的階段、狀態(tài)、狀態(tài)轉(zhuǎn)移、行動(dòng)耗時(shí)等均可使用動(dòng)態(tài)規(guī)劃的圖模型來(lái)表示,如圖5-10所示。

圖5-10過河問題的動(dòng)態(tài)規(guī)劃模型

程序運(yùn)行結(jié)果如圖5-11所示圖5-11過河問題的動(dòng)態(tài)規(guī)劃解

5.討論

值得注意的是,本題如果使用貪婪規(guī)則,也就是每次都派過河最快的A出動(dòng),則總的過河時(shí)間是19分鐘,不是最優(yōu)的,這與經(jīng)常在實(shí)際中出現(xiàn)的能者多勞的思想并不一致。經(jīng)過優(yōu)化后,工作效率提升超過5%。

5.4.4炮兵陣地問題

1.問題描述

司令部的將軍們打算在M×N的網(wǎng)格地圖上部署他們的炮兵部隊(duì)。一個(gè)M×N的網(wǎng)絡(luò)地圖由M行N列組成,其中的每一格可能是山地(用“-1”表示),也可能是平原(用“0”

表示),如圖5-12所示。在每一格平原地形上最多可以部署一支炮兵部隊(duì)(山地上不能部署炮兵部隊(duì));如果在圖中的灰色格上部署一支炮兵部隊(duì),則圖中的黑色網(wǎng)格表示它能夠攻擊到的區(qū)域:沿橫向左右各兩格,沿縱向上下各兩格。圖上的白色網(wǎng)格均表示攻擊不到的區(qū)域。由圖5-12可見炮兵的攻擊范圍不受地形的影響。

圖5-12炮兵部署及其攻擊范圍(部署于灰色格處,攻擊范圍為黑色格)

2.問題分析

如果將一種部署方案作為一個(gè)狀態(tài),那么起始狀態(tài)如圖5-13所示。圖5-13起始狀態(tài)

第2階段的狀態(tài)為在平原上部署一支炮兵部隊(duì),其態(tài)勢(shì)圖如圖5-14所示。圖5-14在平原上部署一支炮兵部隊(duì)后的態(tài)勢(shì)圖

為了計(jì)算方便,我們將黑色區(qū)域標(biāo)記為2,代表已經(jīng)處于炮兵的攻擊范圍,不再考慮部署,將已經(jīng)部署炮兵的格子標(biāo)記為1,代表已經(jīng)部署炮兵部隊(duì),也不再考慮部署,因此,這個(gè)狀態(tài)可以表示為如圖5-15所示的形式。

圖5-15-第2階段的狀態(tài)

3.建立模型

步驟1:第1階段使用矩陣Map存儲(chǔ)狀態(tài)，從起始狀態(tài)開始，針對(duì)所有的平原方格，判斷期可部署性，如果可以部署，則計(jì)算部署后的狀態(tài)矩陣，并將其作為第2階段的一個(gè)狀態(tài)。

步驟2:針對(duì)第Kmax(>2)階段,從Kmax-1階段的狀態(tài)開始,判斷是否可以進(jìn)一步部署一支炮兵部隊(duì),如果可以部署,則計(jì)算部署后的狀態(tài),將其歸并到第Kmax階段的狀態(tài),并記錄狀態(tài)與狀態(tài)之間的轉(zhuǎn)移關(guān)系到鄰接矩陣A。如果第K-1階段的狀態(tài)都無(wú)法進(jìn)一步部署炮兵部隊(duì),則算法結(jié)束。

對(duì)于本例來(lái)講,建立的動(dòng)態(tài)規(guī)劃模型如圖5-16所示,可知最多可以部署三支炮兵部隊(duì),具體方案如圖5-17所示。圖5-16炮兵陣地問題的動(dòng)態(tài)規(guī)劃模型

圖5-17炮兵陣地部署問題的三個(gè)方案

5.4.5-巡邏隊(duì)分配問題

1.問題描述

某一警衛(wèi)部門共有12支巡邏隊(duì),負(fù)責(zé)4個(gè)要害部位A、B、C、D的警衛(wèi)巡邏。對(duì)每個(gè)部位可分別派出2~4支巡邏隊(duì),并且由于派出巡邏隊(duì)數(shù)量的不同,各部位預(yù)期在一段時(shí)期內(nèi)可能造成的損失有差別,具體數(shù)字如表5-10所示。問警衛(wèi)部門應(yīng)往各部位分別派多少支巡邏隊(duì),可使總的預(yù)期損失最小?

2.建立模型

為了陳述方便,將巡邏隊(duì)數(shù)量2、3、4對(duì)應(yīng)的方案分別稱為巡邏方案1、2、3,四個(gè)部位A、B、C、D分別編號(hào)為1、2、3、4。

使用第i個(gè)巡邏方案巡邏部位j的損失變量記為cij,決策變量記為xij,則可以建立如下0－1整數(shù)規(guī)劃模型:

步驟1:第1階段的狀態(tài)集合為X1={0},代表尚未開始指派;決策集合為{2,3,4},代表可以為A