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

5.1多階段決策問題

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

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

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

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

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

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

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

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

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

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

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

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

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

5.3Bellman遞歸方程

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

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

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

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

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

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

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

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

圖5-3中,虛線所示的有向邊的權重為狀態轉移所對應的物理上兩個地點的最短路的距離。火力單元的任意可行行動路徑一定對應圖5-3所示模型中的一條從s到e的路,但是,一條從s到e的路未必是火力單元可行的行動路徑,因為要滿足發射點不重復的約束。例如,存在這種情況:從s到e的最短路如圖5-4中加粗實線箭頭所示,但是,根據發射點不重復的約束,這不是火力單元的一條可行路徑。

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

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

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

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,則可以建立如下背包問題的整數規劃模型:

2.建立動態規劃模型

建立動態規劃模型的具體步驟如下:

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

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

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

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

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

建立的背包問題模型如圖5-6所示。圖5-6背包問題的動態規劃模型

3.求解

利用動態規劃的順序方程進行求解。

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

圖5-7背包問題的動態規劃順序方程求解

5.4.2設備更新問題

1.問題描述

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

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

2.建立動態規劃模型

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

(1)確定階段。

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

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

3.求解

求解的具體步驟如下:

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

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

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

得到的動態規劃模型如圖5-8所示。圖5-8設備更新問題的動態規劃模型

步驟4:利用動態規劃的遞歸方程進行求解。

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

圖5-9設備更新問題的動態規劃最優解

5.4.3過河問題

1.問題描述

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

2.問題分析

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

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

3.建立模型

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

步驟2:由表5-5可得第2階段的狀態集合為

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

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

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

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

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

步驟5:由表5-8可得第5階段的狀態集合為

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

4.求解

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

圖5-10過河問題的動態規劃模型

程序運行結果如圖5-11所示圖5-11過河問題的動態規劃解

5.討論

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

5.4.4炮兵陣地問題

1.問題描述

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

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

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

2.問題分析

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

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

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

圖5-15-第2階段的狀態

3.建立模型

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

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

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

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

5.4.5-巡邏隊分配問題

1.問題描述

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

2.建立模型

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

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

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