運籌學基礎 課件 第5章

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

5.1多階段決策問題

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

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

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

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

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

假設背包最大承重W=10,可裝物品的單件質量和單件價值如表5-1所示,可裝物品的數量足夠。

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

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

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

多階段決策問題網絡模型建立的過程如下:

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

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

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

5.3Bellman遞歸方程

5.3.1最優(yōu)性原則最優(yōu)性原則對以后階段所做出的未來決策將會產生一個最優(yōu)策略,它與前面各階段所采用的策略無關。在多階段決策問題的模型中,假設對階段k以后所做出的最優(yōu)策略為π*=(μk,…,μn),即則根據最優(yōu)性原則,π*與前面各階段X1,…,Xk-1所采用的策略無關。

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

證明:假設路徑(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)子結構定理,也就是說,其最優(yōu)決策序列的子序列不一定是最優(yōu)的。

例5-3某導彈部隊的導彈火力單元隱蔽待機于待機地p1和p2,接收到3波次火力打擊任務?；鹆卧枰ㄟ^網絡(見圖5-2)機動到某導彈倉庫dj(j=1,2,…,5)裝載導彈,然后通過網絡機動到某一個發(fā)射點ri

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

圖5-2多波次導彈火力打擊行動網絡

圖5-33波次導彈火力打擊行動問題的多階段網絡模型

圖5-3中,虛線所示的有向邊的權重為狀態(tài)轉移所對應的物理上兩個地點的最短路的距離?；鹆卧娜我饪尚行袆勇窂揭欢▽獔D5-3所示模型中的一條從s到e的路,但是,一條從s到e的路未必是火力單元可行的行動路徑,因為要滿足發(fā)射點不重復的約束。例如,存在這種情況:從s到e的最短路如圖5-4中加粗實線箭頭所示,但是,根據發(fā)射點不重復的約束,這不是火力單元的一條可行路徑。

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

因為要滿足發(fā)射點不重復的約束,這個模型不滿足最優(yōu)性原則,也就是對以后階段所做出的未來決策將會產生一個最優(yōu)策略,它與前面各階段所采用的策略不是無關的。這個模型也不滿足最優(yōu)子結構定理。對于某個火力單元的最優(yōu)路徑,其子路徑不一定是最優(yōu)的。例如,存在這種情況:某火力單元的最優(yōu)路徑如圖5-5中加粗實線箭頭所示,則從第5階段的d1到e的子路徑不一定是最優(yōu)的。

圖5-5-3波次導彈火力打擊行動模型不滿足最優(yōu)子結構定理

5.3.2兩個推論

5.3.3兩個方程

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

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

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

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

5.4典型案例

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

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

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

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

步驟1:輸入背包問題的參數,確定階段的數量。將問題分成n+2個階段,增加一個虛擬的起始狀態(tài)和一個虛擬的結束狀態(tài),中間每個階段考慮一種類型的物品。因為要最大化背包中物品的價值,所以將單位物品的價值加上一個負號。

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

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

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

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

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

3.求解

利用動態(tài)規(guī)劃的順序方程進行求解。

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

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

5.4.2設備更新問題

1.問題描述

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

例5-6某部門要對一臺已經使用了2年的設備確定今后5年的最優(yōu)更新策略。已知設備的最大使用年限為6年,購買一臺新機器的費用是1000萬元。該問題的基本數據見表5-4。

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

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

(1)確定階段。

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

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

3.求解

求解的具體步驟如下:

步驟1:輸入問題的基本參數。

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

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

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

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

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

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

5.4.3過河問題

1.問題描述

小明一家四口人要過河。單獨過河爸爸要1分鐘,媽媽要2分鐘,小明要5分鐘,弟弟要10分鐘。最多兩個人同時過河,并且只有一個手電筒,每次都需要手電筒。兩人過河按慢的時間算。請設計過河方案,使一家人過河總時間最少。

2.問題分析

為了描述方便,將爸爸、媽媽、小明、弟弟分別記為A、B、C、D。假設過河時的順序為從左到右,回程時的順序為從右到左,過河的時候兩個人,回程的時候一個人。

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

3.建立模型

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

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

下一步決策的內容為選擇一個已經過河的人帶手電筒回來,其決策、到達狀態(tài)、行動耗時如表5-6所示。

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

下一步決策的內容為選擇兩個尚未過河的人一起過河,其決策、到達狀態(tài)、行動耗時如表5-7所示。

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

下一步決策的內容為選擇一個已經過河的人帶手電筒回來,其決策、到達狀態(tài)、行動耗時如表5-8所示。

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

下一步決策的內容為選擇兩個尚未過河的人一起過河,其決策、到達狀態(tài)、行動耗時如表5-9所示。

4.求解

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

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

程序運行結果如圖5-11所示圖5-11過河問題的動態(tài)規(guī)劃解

5.討論

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

5.4.4炮兵陣地問題

1.問題描述

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

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

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

2.問題分析

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

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

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

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

3.建立模型

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

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

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

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

5.4.5-巡邏隊分配問題

1.問題描述

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

2.建立模型

為了陳述方便,將巡邏隊數量2、3、4對應的方案分別稱為巡邏方案1、2、3,四個部位A、B、C、D分別編號為1、2、3、4。

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

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