一般地，我們用下面的記號來表示D中的特定元素： d—D中第之行，第j列元素。 我們總是用大寫字母來表示矩陣，而用對應的帶下標的小寫字母來表示矩陣的元素。 矩陣的規模是指矩陣的行數和列數，並用行數×列數表示。因而，D的規模就是2×3。 經常，我們還會看到只有一行或一列的矩陣。例如： 6 G= 4 2 3 就是一個只有一列的矩陣。如果一個矩陣只有一列，我們就稱其為列向量。類似地，如果矩陣只有一行，我們就稱為行向量。按前面的約定，要指定G矩陣的具體元素，我們可以用8來表示。但是因為G只有一列，所以列的位置就不重要了，我們常常只給出行號。也就是說，我們不用8w的形式，而只用一個下標來表示元素在向量中的位置。例如： 81 =6,8 =4,8=2,8=3 17A.2 矩陣的運算矩陣的轉量矩陣的轉置是透過將原矩陣的行轉變為轉置矩陣的列，當然，原矩陣的列就轉變為轉置矩陣的行。例如，矩陣 0-［。的轉理為》。 注意，上標！表示一個矩陣的轉置。 矩陣的蒙法我們用例子來說明怎樣做下面兩類矩陣的乘法：（1）兩個向量相乘；（2）一個矩陣乘以另一個矩陣。 規模為1xn 行向量與規模為n×1的列向量相乘，結果是將行向量的第一個元素同列向量的第一個元素相乘，再將行向量的第二個元素同列向量的第二個元素相乘，以此類推，直到行向量的最後一個元素同列向量的最後一個元素相乘，再把所有這些乘積加起來。例如，我們假設要將行向量日同列向量G相乘，其中， H= ［21 5 0］， 且G= 2 .3」 向量的乘積記為HG，由下得到： HG =2×6+1×4+5×2+0×3=26 規模為pxn的矩陣同規模為n xm 的矩陣相乘，得到一個規模為Pxm的新矩陣。新矩陣中的第；行、第j 列的元素是由Pxn矩陣的第；行同nxm矩陣的第j列相乘。例如，假改我們要將D乘以A，其中， 「1 3 0 4 L1 52」 令C=DA記為D來以A。那麼C的第1行、第1列元素就由D的第一行同A的第一列相乘，即用下面的方法得到： 「1 Cu=［1 2］ =1×1+3×2+2×1=9 C的第2行、第1列元素就由D的第二行同A的第一列相乘，即用下面的方法得到： C21 = ［0 30x1+Ax2+5x1-1
476 資料、樸型與決策：管理科學篤用同樣的方法計算C的剩餘的元素，最後我們得到： 很明顯，一個矩陣同一個向量相桑只是兩個矩陣相乘的特例。例如，m xn 的矩陣同nX1的向量相乘，最後得到一個m×1的新向量。新向量的第；個位置是由mxn矩陣的第；行同nx1 向量相乘得到的。例如，假設我們要算D和K的乘積， 0-［。＆引，×= ［1 3 DK的第二個元素就是D的第二行同K的乘積，因而有 「17 ［2」 4=1×1+3×4+2×2=17 ［0 4 5］ =0×1+4×4+5×2=26 因此，我們得到D和K的乘積 DK： 「17 oK=l1引那麼任意兩個矩陣可以相乘嗎？答案是否定的。要對兩個矩陣相乘，必須保證第一個矩陣的列數同第二個矩陣的行數相等。滿足該條件的矩陣稱做乘積匹配的（conform for multiplication）。因而，在這個例子中，D和 K可以相乘，因為D有3列，而K有3行。 矩陣的逆運算矩陣A的逆是另一個矩陣，記為A~'，我們有AA' =1且 A~'A=1。任何兩行兩列的矩陣的逆可以由下式來計算： aiz A= -aaild 而d=au Cz2-021012是2×2矩陣A的行列式。例如， A= 0.7 -0.3 那麼，d=0.7×0.9-（-0.3）×（-0.3）=0.54 10.9/0.54 0.3/0.54 1-10:370.34 8.30.34）-16.82 936
第18章動態規劃動態規劃是將一個難以解決的大問題分解為許多通常更容易解決的子問題的一種解決問題的方法。動態規劃方法使我們在按這種方法分解一個大問題時，一旦所有的子問題都解決了，我們就得到了這個大問題的最優解。我們會看到每一個子問題都被視為動態規劃方案程式的一個階段。因此，這種技術被用在了本質上為多階段的決策問題上。通常因為一系列的決策要隨著時間才能做出，所以我們要建立多個階段。例如，在一年中做出最優決策的問題可能會被分為12個小階段，每個階段的最佳決策要在一個月的時間內做出。在大多情況下，每個子問題都不能看做與其他問題完全獨立，動態規劃在這方面就非常有用。讓我們從展示如何用動態規劃解決最短路徑問題開始我們的學習。 18.1 最短路徑問題在第9章，我們學習瞭解決最短路徑問題的標籤法。現在，讓我們透過將其用於解決最短路徑問題說明動態規劃方法。考慮一下圖18-1中的網路。假設每條弧上的數字代表兩個節點間的直接距離， 我們的任務是找出從節點1到節點10 的最短距離。 圈18-1 墩短路徑問題的網路k
478 資料、模型與決策：管理科學篇在試圖解決這個問題之前，讓我們考慮一下所有最短路徑問題的一個重要特點。這個特點就是 Richard Beliman 著名的最優性原則應用在最短路徑問題上的重述。° 最優性原則若某一點在最優路徑上，那麼從那一點到終點的最短路徑也在最優路徑上。 解決最短路徑同題的動態規劃方法主要就是將每一個節點看傲是在最優路徑上，然後做出相應的計算。做的時候，我們將從終端節點，也就是第10個節點開始，逆推，計算每個節點到第10個節點的最短路徑，直到到達起始節點，也就是第一個節點。這個時候，我們就解決了找出從節點！到節點 10之間最短路徑這個初始問題。 正如我們在本章的引言中所提到的那樣，動態規劃就是將最初的問題分解為許多更容易解決的子問題。在圖18-1 的最短路徑問題中，我們將要建立的那些子問題定義為一個4階段的動態規劃問題。 階段1從與終點相隔1條弧的那些節點開始，到終點節點結束。注意圖18-1，只有節點8、9與節點10 是一弧之隔。在動態規劃術語中，節點8、節點9被看做階段1的輸入節點，節點10被看做階段1的輸出節點。 階段2從距離終點2條弧的那些節點開始，到臣離終點1條弧的那些節點為止。所以，節點5、 6、7是階段2的輸人節點，節點8、9時階段2的輸出節點。注意，階段2的輸出節點就是階段1的輸入節點。階段3的輸人節點就是那些距離終點3條弧的節點，也就是節點2、3、4。階段3的輸出節點就是距離終點更近1條弧的節點5、6、7。最終，階段4 的輸人節點是節點1，輸出節點是2、3、4。 我們在每一個階段所要解決的決策問題就是，哪一個特殊的輸入節點到輸出節點之間的弧是最優的。 讓我們考慮階段1的問題。 我們隨機從節點9開始階段1的計算。因力從節點9到節點 10只有一條路，所以顯然這條路表1 階段1 就是最短的，而且它長2英里。類似地，從節點8 到節點10只有一條路。從節點8到終點的最短路徑就是這條路的長度，或者說是5英里。階段1的輸入節點 8 9 弧（決策） 8-10 9-10 至節點 10的最短路徑 5 2 決策問題就解決了。對於每個輸人節點，我們都找到了最優解，也就是到輸出節點的最優弧。階段1的結果總結如表1。 在開始解決階段2問題時，我們轉到節點7。（我們也可以選擇節點5或6；每一階段選擇節點的順序是隨機的。）從節點7出發，有2條弧和階段1的輸入節點相連：長8英里的弧7-8和長10英里的弧7-9。如果我們選擇弧7-8，距離就是從節點7~10的13英里，也就是弧7-8的長度8英里加上節點8~10的最短距離5英里。因此，選擇弧7-8這個決策的總關聯距離為8+5=13（英里）。弧7-9的距離是10英里，階段1中的節點9~10的距離是 2英里，選擇弧 7-9，則總關聯距離就為 10+2=12（英里）。為此，假定我們在節點7， 我們就應該選擇弧7-9，因為它在到達節點 10的最短距離（12英里）的路徑上。對節點5、6進行相似的計算，我們就可以得出階段2的結果， 表2 階段2 輸入節點弧（決策） 輸出節點 5 5-8 8 6 6-9 9 7 7-9 9 至節點 10的最短路徑 8 7 12 如表2所示。 圖18-2中每個節點上方方框中的數字代表從該點到終點的最短路徑的長度。我們已經完全解決了前兩個子問題（階段1和階段2）。現在我們知道了從節點5、6、7、8和9到節點10的最短路徑。 讓我們從節點2開始階段3。注意到有3條弧將節點2連線到階段2的輸人節點上。因此，為了找 S. Dreyfus, Dynamic Programming and the Calculus of Variatione （New York : Academic Preee, 1965）.
第18章動態規劃 479 到從節點2到節點10的最短路徑，我們必須做3次計算。如果我們選擇了弧 2-7並且按最短路徑到達終點，那麼我們的距離就是11+12=23（英里）。類似地，選擇弧2-6 的距離是12+7=19 （英里），弧2-5是13+8=21（英里）。 所以，假定我們在節點2，那麼從節點 2到節點10的最短路徑是19英里，這說明弧2-6是最佳選擇。同樣，我們得出從節點3到節點10的最短路徑 min 14+12,10+7,6+8/ = 14；從節點4到節點10的最短路徑 min 114+ 7,12+8 =20。我們完成了階段3的計算，結果如表3。 在解決階段4的子問題時，我們發現從節點1到節點10的最短路徑為 min 11+19,5+14,2+20/=19。所以，階段4的最優選擇是弧1-3。在網絡圖上從階段4到階段3，再到階段2， 再到階段1，我們找出了每個階段的最優決策，因此也就找出了從節點1到節點10的最短路徑。這樣，最短路徑經過節點1-3-5-8-10，距離為5+6+3 +5=19（英里）。 注意每個後續階段的計算是如何利用前一階段的運算結果的。這個特點是動態規劃過程中重要的一部分。 圖18-3說明了最終的網路圖計算。注意，在每個階段的逆推過程中，我們就決定了從每個節點到節點10的最短路徑。 在每個階段我們要列舉或評估幾條路徑，然而動態規劃並不要求我們列舉從節點1到節點 10的所有可能路徑。回到階段4的計算，從節點1出發有3個選擇，每一種選擇的完整路徑如下： 12 10 10 12 圖 18-2 用動態規劃解答最短路徑問題的中間解輸入節點 2 3 4 弧（決策） 2-6 3-5 4-5 階段3 輸出節點 6 5 至節點10的最短路徑 19 14 20 表3 階段 4 3 2 弧（決策） 1-3 3-5 5-8 8-10 20 12 14 10 0 1I 圖 18-3 用動態規劃解答最短路徑問題的最終解節點1的備用弧 1-2 1-3 1-4 到節點10 的完全路徑 1-2-6-9-10 1-3-5-8-10 1-4-5-8-10 距離 20 19 22 •最優選擇當你意識到從節點1到節點10共有16條可供選擇的路徑時，你就可以看到動態規劃為我們節省了大量的計算，不用列舉出所有可能的方法。 從節點10回推到節點1時，我們不必評估每個階段所有的路徑，這說明了動態規劃的強大作用。
480 資料、模型與決策：管理科學篇運用動態規劃，在大量的需要全部列舉的計算中，我們只需要計算一小部分。如果例子中的網路圖被放大，動態規劃所節省的計算量就會更大。 18. 2 動態規劃符號學習運用動態規劃可能最困難的一個方面就是理解它的符號。我們所用的符號和 Nemhauser°所用的一樣，非常標準。 動態規劃解題程式的階段是透過將最初問題分解為若干子問題而形成的。和每個子問題對應的， 就是動態規劃解題程式的一個階段。例如，第18.1 節中的最短路徑問題就是用一個4階段動態規劃解題程式來解決的。有4個階段，是因為我們將最初問題分解為下述4個子問題： 1.階段1問題：沿著最短路徑到達節點10，我們是應該從節點8還是節點9出發？ 2. 階段2問題：利用階段1的結果，為了沿著最短路徑到達節點 10，我們應該從節點5、節點6 還是節點7出發？ 3. 階段3問題：利用階段2的結果，為了沿著最短路徑到達節點 10，我們應該從節點2、節點3 還是節點4 出發？ 4. 階段4問題：利用階段3的結果，為了沿著最短路徑到達節點 10，我們應該從節點1往何處出發？ 讓我們仔細看一下階段2發生了什麼問題。考慮以下關於這個階段的表述： 決策回題過殺定的槍人，我們應該訪擇哪條那到所段決銀淮劑測綠肉的最短眶商（巫上的值加從輸出節太利終點的最短距離） 輸出 （網路中的位置： 節點8或9） 輸入 （網路中的位置： 節點5、6或7） 用動態規劃符號，我們定義一階段2的輸人；代表網路圖中階段2的起始點（節點5、6、7）； d—階段2的決策變數（被選來移動到階段1的弧）； *，一階段2的輸出；代表網路圖中階段2的結束點（節點8、9）。 用這些符號，階段2的問題就可以表示如下： Xz 回想一下用動態規劃來解決最短路徑問題，在這些階段中我們用的是倒推法，從節點10開始。 當我們到達階段2，我們並不知道*2，因為階段3的問題還沒有解決。我們用的方法就是考慮輸人*， 的所有的可能，然後決定對於每一個輸人*，的最佳決策d。接著，當我們在系統中繼續推進而重新獲得最佳決策順序時，我們看到階段3的決策提供了一個特殊的x，就是節點5，從前面的分析我們就知道了繼續進行到階段1的最佳決策（d）。 讓我們考慮有N 階段的一般動態規劃，並採用如下通用符號： x.第n階段的輸入（第n+1 階段的輸出）； d—第n階段的決策變數。 一般N 階段的問題可以分解成如下形式： © G. L Nemhauser, Inaroduction to Dynamic Programming （New York: Wiley, 1966）
第18章動態規劃 481 X1 階發 4 個階段的最短路徑問題可以表示成如下形式： 附段階段階段輸入和輸出變數x、*、x2、x，和x。的值很重要，因為他們將4個子問題聯絡到一起。在任何一個階段，我們最終都需要解出輸人*，來做出最佳決策d。。這些變數x，可以看做是從一個階段移到另一個階段的系統狀態或條件。相應地，這些變數就是問題的狀態變數。在最短路徑問題中，狀態變數代表網路中每個階段的位置（比如一個特殊的節點）。 在最短路徑問題的階段2中，我們考慮了輸人x，且做出了決策d，使到達終點的臣離最短。輸出 x，是以輸人和決策的綜合為基礎的；就是說，x，是x，和d，的函式。用動態規劃符號中，寫做： （x，d）是決定階段2輸出的函式。因為1（x，d）是將這個階段的輸入“轉化”為輸出的函式，這個函式就被稱為階段轉移函式。階段轉移函式的一般表述為階段轉移函式的數學形式依賴於具體的動態規劃問題。在最短路徑問題中，階段轉移函式是基於表格運算的。比如，表18-1列出了階段2的階段轉移函式！（*2，d）。 d可能的值就是表中所選的弧。 每個階段都有一個相應的收益。在最短路徑問題中， 收益就是從一個輸入節點到一個輸出節點的弧的長度。例如，如果節點7是階段2的輸人節點，並且我們選擇了弧 7-9作為d，那麼這個階段的收益就是那段弧的長度，10 英里。某一階段的收益也可以看做這一階段的支付或是價值，它用一般符號T，（x，d。）表示。 運用階段轉移函式和收益函式，最短路徑問題可以表述如下： 表18-1階段2中對應每個*，值的X， 的階段轉化工= （x，d） 錦入狀態輸出狀態 8 9 7 5-8 6-8 7-8 5-9 6-9 7-9 所段4 階段 d M段2 所股！ 「（×，Q） ⅓（×，④） 「：（、4.） 如果我們把一個系統或過程看做N個階段，我們可以將一個動態規劃公式表述如下： d， d
482 資料、模型與決策：管理科學篇圖中的每一個矩形表示流程的一個階段。如上圖所示， 最佳總收益僅取決於狀態變數。 每個階段有兩個輸人：狀態變數和決策變數。每個階段也有兩個輸出：狀態變數的新值和這個階段的收益。狀態變數的新值是以t。（x，d。）作為輸入的一個函數。一個階段的收益的值則是以T。（x。，d。）作為輸人的函效。 另外，在第n階段的輸入*，給定的情況下，我們用f。（x。）這個符號來表示第n階段和所有其他階段的最優總收益。比如在最短路徑問題中，f（x）表示給定階段2輸人*，的情況下，階段2和所有其他階段的最佳總收益（比如最短距離）。所以，在圖18-3中，我們得出f（x=節點5）=8， 註釋與評論 1. 動態規劃最主要的優，點就是它“分解並攻克”的解決問題的策略。利用動態規劃，一個大的複雜問題可以被劃分為一系列小的相互關聯的問題。按順序解決完小的問題後，大問題的最優解決方法也就找到了。動態規劃是一種解決問題的一般方法；動態規劃不是一種特殊技巧，它與可以用同一種方式來解決許多問題的線性規劃不同。儘管動態規劃問題的某些特點是相同的，但每次應用都需要一定程度的創新性、洞察力以及將大問題劃分為一系列小的相互關聯的子問題的專業技術。 2. 動態規劃已被用來解決各種各樣的問題，包括存貨控制、生產排程、資金預算、資源分配、 器材更換和維修。其中許多應用都是將時段，例如日、周和月等，作為大的多階段問題的相互聯絡的子階段的。 18.3 揹包問題揹包問題的基本思想就是 N種不同的物件可以放在一個揹包中。每個物品都有其重量和價值。問題就是決策將多少單位的物件放在一個揹包中， 使得總價值最大化。揹包允許的最大重量是有限制的。 工作型別為了提供一個揹包問題實際應用的例子，我們考慮有一個生產運作經理，他必須每兩週從4 類工作中做出選擇，在接下來的兩週內做這些工作。表18-2 是待處理工作編號的清單，還有完工 1 2 3 4 表18-2 有關生產加工的工作資料要處理工作每項工作預計的編號完成時間（天） 4 1 3 3 2 2 每項工作的價值籌級 2 8 11 20 的預期時間和每項工作的價值等級。 每項工作的價值等級是經理的主觀評分。每項工作的價值從1到20不等，其中1代表價值最小的工作，20代表價值最大的工作。工作的價值是由這些因素決定的，如期望收益、某項工作已等待處理的時間、優先順序等等。在這種情況下，我們要選擇接下來兩週的工作，使得這些工作可以在10個工作日內處理完，而且總價值最大。用揹包問題的術語，就是我們選擇兩週的最佳工作的揹包，這個背包的容量等於10天的生產能力。讓我們用動態規劃來建模並求解這個問題。 這個問題可以闡述為一個4階段的動態規劃問題。在階段1，我們必須決定在第一類工作中要處理多少；在階段2，我們必須決定在第二類工作中要處理多少；以此類推。因此，我們令 d—第n類工作中要處理的工作量（第n階段的決策變數）； *，第n階段開始時剩餘的天數（第n階段的狀態變數）。 因此，在生產期為兩週的情況下，x。=10表示可用於完成工作的總天數。階段轉移函式如下： 階段4： =1（xa,d）=。-7da 階段3:x2=t（x3，d）=X-4d
第18章動態規劃 483 階段1：20=1（，c）=x-1d， 每個階段的收益是以該類工作的價值等級和工作量為基礎的，收益函式如下所示： 階段4:74（x,d）=20da 階段3：（*，d）=11ds 階段2： （d）=8d 階段1:7；（x,d）=2d， 圖18-4 描述了問題的機理。 d X.=10 階段4 階段， 階段 2，（，4，）=20d， 7，（K,Q）=110，（X.d.）=2d， 圖18-4 工作選擇問題的動態規劃模型與第18.1 節的最短路徑問題一樣，我們將使用倒推法；就是說，我們假設已經做出了第4、3、2 階段的決策，只剩下最終的決策（階段1應從第一類工作中挑選多少工作）。最優性原則的重述可用於這個問題。也就是說，不管在前一階段做出何種決策，如果第n階段的決策是總的最優策略的一部分，那麼第n階段做出的決策必須是所有其他階段的最優選擇。 讓我們建立一個表來幫助我們計算階段1的最優決策。 階段1 注意在階段1，輸人（x，）和可用的工作時間的天數是不知道的，因為我們尚未對前面階段做出決策。因此，在我們對階段1進行分析時，就要考慮x，所有可能的取值以及在每種情況下的最優決策d；大（x，）是決定了d，後的總收益。x，可能的取值和相關的d」、f（x；）的值如下： 0 2 6 7 8 9 10 0 1 2 3 4 4 4 4 4 4 4 f，（*） 0 2 4 6 8 8 8 8 8 8 8 d；這一列是在x，取特定值時相對應的d，的最優值，x，的範圍是從0~10。x，的特定值取決於在階段2、3、4中所選擇的其他型別的工作的處理時間。由於每個階段中一項工作都需要一天的處理時間，每項工作有兩個正收益，所以我們在這一階段要選擇儘可能多的工作。第一類工作的工作量將取決於可行的處理時間，但不能超過4。 回顧一下，假設階段！的輸人為*，則大（x」）代表從階段1到其他所有階段的最優總收益的值。 因此，在x≤4時，f（x）=2x；在x，>4時，f（x」）=8。階段1的最最佳化就完成了。現在我們轉到階段2，對這個階段進行最最佳化操作。 階段2 我們將再一次用表來幫助找出最優決策。因為階段2的輸人（x）未知，我們就必須考慮從0~10的所有值。同時，我們還必須考慮d所有可能的值（比如0、1、2或3）。給定輸人*，和
484 資料、模型與決策：管理科學篇決策d，標題T2（*2，d）+f，（x」）下的條目表示伴隨最後兩階段而來的總收益。例如，如果階段2 剩餘的工作時間為*=7天，並且我們決定從第二類工作中挑選兩項工作（比如d=2），那麼階段1 和階段2的總收益將為18。 d 2 3 0 f（x） 0 ② ④ 2 ⑧ 8 8 10 8 ② 14 16 16 16 16 18 20 22 24 1 2 2 2 3 3 10 12 16 18 20 24 26 2 0 2 階段2的收益為 （x2，d） =8d=8×2=16，當x=7，d=2時，我們有x：= -3d=7-6=1。 從上面的表格我們可以看出，當x=1時，階段1的最優收益為力（1）=2。因此，當x=7，d=2 時，7（7,2）tf（1）=16+2=18 就是相對應的總收益。同理，4=5，d=1時，我們得到「2 （5,1）+（2）=8+4=12。注意，有些x與d的結合是不可行的。比如x=2，d=1就是不可行的，因為第二類工作的每一項都需要3天來完成。不可行的方案用短橫槓表示。 計算了矩形中的所有收益後，我們就能對這一階段的輸人或狀態變數，的每一個可能的取值做出最優決策。舉例來說，如果x=9，我們從d的4個可能取值0、1、2、3中選擇一個。顯然，d=3可以使最後兩階段的總收益達到最大值。因此，我們將這個值記在該列中。另外要強調的就是，我們在最佳收益在矩形中的對應元素上畫圈。給定x=9且我們必須再經過兩個階段，最佳總收益就是24，我們就將這個值記在 （x）列上。假如我們進人階段2，=9，最優選擇 d=3，我們將帶人階段1的就是 （9，3）=x-3d=9-3×3=0。這個值記錄在表的最後一列中。我們現在開始階段了。 階段3我們在這裡建立的表格和階段2很相似。標題rs（xs，d）+f（x2）下的條目表示在所有可能的輸人*，和決策d，下，階段3、2、1的總收益。 0 2 0 5 7 8 9 10 ② ④ ⑧ 10 12 16 18 20 ④ 26 — ① ③ 15 ⑨9 21 23 ②7 — ② ④ 26 0 0 0 0 1 1 0 1 2 0,2 1 0 2 0 1 4 8 11 13 16 19 22 24 27 3 0 1 6 3 0 9,1 6 這個表格中有一些階段2中所沒有的有趣特徵。我們注意到如果狀態變數x，=9，那麼兩個可能的決策將能從階段1、2、3中得出最優總收益。也就是說，我們可以不從階段3選擇工作，這樣的話， 我們在階段3得不到任何收益，但都以x=9進入階段2。因為 （9）=24，d=0的選擇會使總收益達到24。然而，選擇d=2 也會使總收益達到24。在階段3，我們的總收益是11（dg）=11×2=
第18章動態規劃 485 22，並且由於*=1，剩下的兩個階段，我們的收益就是2。為了顯示這個階段所有可以選擇的最優解，我們在d和x，=1（xg，d）欄中列出了這兩個條目。表格中其他條目的計算方法與階段2相同。現在我們進人最後一階段。 階段4 我們知道計劃期有10天的時間；因此，階段4的輸入x，=10。那麼我們就要考慮表中和階段4相符的惟一一行。 10 0 27 1 28 28 3 *，=10時，最優決策d=1 我們已經用動態規劃完成了對這個問題的求解。要找出總的最優解，我們必須從階段4，也就是最後一個階段開始往回檢視錶格。階段4的最優決策是d=1。所以，*=10-7d&=3， 然後我們進人有3天工作時間的階段3。當*=3時，階段3的最優決策d=0。接著，我們以x=3 進人階段2。 階段2 的最後選擇就是*=3時，d=1，從而使得x，=0。最終，階段1的決策必然是d=0。生產運作的最佳策略如下： 策略 d=0 d： =1 d； =0 d=1 收益 0 8 0 20 總和 28 在接下來的10天內，我們應該從第二類工作中選出一項工作，從第四類工作中選出一項。 現在可以闡明動態規劃的另一個優點了。假設我們想做出一個僅有8天時間的工作計劃。解決這個新問題，我們只需簡單地再計算一下階段4。新的階段4 的表格如下； 0 ②3 0， 1 22 8.1 實際上，我們是在根據可行工作日總數的改變來測試最優解的靈敏度的。這裡我們有一個可供選擇的最優解的例子。一個解決方案就是設定d：=0，然後往回檢視錶格。這樣做我們得到如下結果： 策略收益 d =0 0 d=0 0 d=2 22 d=0 總和 22 另一個最優解是設定d；=1，然後往回檢視錶格。這樣做，我們得到了另一個解決方案（總收益和第一種方案相同）。 策賂 d=1 d=0 d=0 d=1 收益 2 0 0 20 總和 22
486 資料、模型與決策：管理科學篇從最短路徑到揹包問題的例子中，你應該對動態規劃的一個階段接另一個階段的解決問題的程式比較熟悉了。在下一節，我們將告訴大家如何用動態規劃來解決生產和庫存控制問題。 18.4 生產和庫存控制問題假定我們對某一產品在幾個時期的需求做出了預測，我們要決定在每一時期的產量，使得需求能以最低成本來滿足。我們要考慮兩種成本：生產成本和持有成本。假定每一階段都有生產準備，這樣，準備成本就是常量。因此，在分析中就不考慮準備成本了。 我們允許不同時期的生產和持有成本可變。這種規定使模型更靈活，因為它使得在不同階段用不同生產和儲存裝置成為可能。在模型中，生產和儲存能力是有限制的，在不同階段是不同的。我們來用以下符號： N—時期數（動態規劃公式中的階段）； D.階段n的需求（n =1,2， ⋯，N）； *。—表示階段n開始時庫存量的狀態變數（n=1，2， ⋯，N）； d階段n的產量（n=1,2，⋯，N）； P階段n的生產能力（n=1，2， “，N）； W，階段n末的儲存能力（n=1，2，…，N）； C階段n的單位生產成本（n =1，2， ⋯，N）； H。階段n最終存貨的單位持有成本（n=1，2，⋯，N）。 我們用動態規劃方案來解決一個3個月期的生產運作問題。這個問題的資料在表18-3中。我們將每個月看做動態規劃公式中的一個階段。圖18-5示意了這個公式。注意，1月的期初庫存數是1。 在圖18-5中我們是倒著給出階段編碼的；就是說，階段1對應3月，階段2對應2月，階段3對應1月。階段轉移函式的形式是期末存貨=期初存貨＋生產-需求。因此，我們有 *s=1 *2 =*g +d-D，=xg +ds-2 x=Xtd-D=x+d，-3 %o=t，+d-D.=x1+d-3 每個階段的收益函式表示每個月生產和持有成本的總額。例如，在階段1（3月），「（x，d、） =200d，+40（x，+d，-3）表示這個階段總的生產和持有成本。生產成本是每單位200美元，持有成本是每單位期末庫存40美元。其他的收益函式為 2（2，d）=150d+30（x1+d-3） 「s（x，ds）= 175d + 30（x +ds-2） 階段2，2月階段3，1月 03P3 w2d D3 T.T P 階菸3 （） 階段？ （2月） 圖18-5 作為一個三階段動態規劃問題的生產庫存控制問題第18章動態規劃 487 表18-3 生產庫存控制問題資料生產能力每單位成本月份需求 1月 2月 3月 2 3 3 生產 3 2 3 儲存 2 3 2 生產 $175 150 200 持有 ＄30 30 40 注：1月的期初庫存數是1。 這個問題非常有趣，因為在我們進行最最佳化的過程中，每一個階段我們都要滿足3個約束條件。 第一個約束條件是期末庫存必須少於或等於倉庫庫存容量。用數學方式表示，我們有 x.+d-D，≤W。 或 x。+d.≤W.+D。 （18-1） 第二個約束條件是每個階段的生產水平不能超過生產能力。用數學表示，我們有： d.≤P. （18-2） 為了滿足需求，第三個約束條件是期初庫存與生產的和必須大於等於需求。用數學形式表示，這個約束條件可以寫作 *.+d.≥D. （18-3） 現在我們開始以分段方式進行解決問題的序。在每一個階段，我們將根據式（18-1）、式（18階段1 階段1的問題如下： min s.t. （，d」）=200d，+40（x」+d-3） x， +d， ≤S 倉庫約束 d， ≤3 生產約束 x，+d，≥3 滿足需求約束合併目標函式中的各項，我們可以把問題重寫為： min 「1（x，d）=240d+40x，-120 8.t. x， +d，≤S d，≤3 4. +d，≥3 根據第18.3 節中我們使用的列表法，我們將考慮階段1（x、）中所有可能的輸人，並做出相關的成本最小化決策。因為我們想使成本最小化，我們希望決策變數d，越小越好，並仍然能夠滿足需求的約束。這樣，階段1的表格如下： 0 1 2 •3 3 2 1 0 階段1中3的生產能力限制了d，的值 240d，+40x， 120 600 400 200 階段2中3的庫存能力限制了x，的值需求約束：x，+d，≥3 現在讓我們進行階段2的動作。
488 資料、模型與決策：管理科學篇 min 2（2 d）十 .（x」）=150d：+30（x2 + d-3）+（4） =180d+30x2-90+5（x」） S. t. *+d：≤6 d≤2 *+d≥3 階段2 階段2 的計算總結如下表： 0 1 階段292的庫有能內 2 0 1 M 900 750 900 （730 0 2 730 4 階段3中2的生產能力每一個x，d組合檢查需求約束，+d，≥3（負號表示不可行解） 7（1,2）+斤（0）=180×2+30×1-90+600 = 900 7（2,1）+5（0）=180×1+30×2-90+600 = 750 當x=2且d=2時，我們得到 72（2,2）+f（1）=180×2+30×2-90+400 = 730 注意，當x=0時，5（*）這一列的值是一個無限的高成本值M。因為階段2的輸入點0並不是一個可行解，*=0與輸人點相關的成本 M 將會排除最優解中出現x，=0的情況。 階段 3 min rs（xs,ds）+f（x）= 175d，+30（x + ds-2） +5（x） =205d，+30x-60+f（4） s.t Xg+d≤4 d≤3 x+d≥2 由於期初庫存水平為*，=1，所以階段3的表格如下： 所段3#3的生產能力 0 2 0 M Q280 1315 1280 這樣，我們在最優生產與存貨政策下算出的總成本是1280美元。要找出每階段的最優決策和存貨水平，我們需要回溯檢視每一階段，並得出x，和d。表18-4總結了最優生產和存貨策略。 表18-4 最優生產和庫存控制策略月份 1月 2月 3月期初犘存生產生產成本期末庫存 $ 350 持有戒本 ＄30 300 0 3 600 0 0 總和 $1250 0 $ 30 總月度成本 $380 300 600 $1280
第18章動態規劃 489 註釋與評論 1. 與其他管理科學技術一樣，在使用動態規劃的情況下，計算機會成為一種很有價值的輔助計算工具。但是，由於動態規劃是一種隨各種應用而變化的解決步驟問題的一般方法，所以事實上並沒有任何解決動態規劃的演演算法或計算機軟體包。雖然有一些可以解決特殊形式問題的軟體程式，但是如果要使用計算機解決問題，那麼許多動態規劃的新應用就要求有特殊設計的軟體程式。 2. 本章關於動態規劃的介紹以及描述是特定的，並且有固定數目的可選項方法及步驟。對於這樣的問題，我們可以透過表格形式來組織和進行計算。在這種結構下，每個階段的敢最佳化問題可以通過對所有可能的結果列舉來解決。更復雜的動態規劃模型可能包括隨機成分、連續型的決策變數和 （或）無限次的步驟數目。在每個步驟包含連續決策變數的那些問題中，要想獲得最優解，可能需要用到線性規劃或者徽積分學的方法。 本章小結當我們有可能把一個大問題分割成一些彼此關聯的子問題時，動態規劃就是解決這類問題的一個有吸引力的方法。解決步驟因此是倒推式的，即在每個階段解決各個子問題中的一個。動態規劃不是一種特殊的演算法，而是一種解決問題的方法。這樣，倒推式優選法可以針對性不同問題採取不同的步驟。在任何一個問題上，解決一系列子問題幾乎總是比解決一個大問題容易。透過這個過程，動態規劃發揮了其威力。專欄18-1介紹了 EPA如何用動態規劃模型來建立季節性排汙底限以保護水質。 專欄18-1 實踐中的管理科學 EPA 與水質管理美國環保署（EPA）是聯邦政府的獨立執行機構。EPA監管如下領域的綜合環保法律問題： •水汙染控制、水質以及飲用水。 •空氣汙染和輻射。 •殺蟲劑和有毒物質。 •固體和危險廢料，包括緊急洩漏反應和超級基金資助點的整治。 EPA還監管那些用於維護全美河流和澳流水質在可接受範圍的專案。政府要求所有公司在排汙前必須獲得聯邦或州政府的許可。這些許可特別強調了每個排汙戶可以排出的廢料的數量。排汙的底限是確保水質在河流或溪流流量相當少的幹李也能達到標準。最常見的方法是按照過去10年的最低流量記錄來定此標準。確保水質維持低流量標準能夠高度保證全年內也能維持高的水質標準。 EPA的目標是建立一個李節性的排汙底限，在維持預先規定的可靠水質標準的同時還能夠使治理成本降低。這些排汙底限透過先確定接收廢料的流體設計流量來制定。每個李節的設計流量必須考慮到保證能維持全年水質條件。在俄亥俄州辛辛那提市的城市環境研究實驗室建立了一個動態規劃模型來確定設計流量，該模型接下來也可以用於制定季節性廢料排汙底限。模型透過最小化治理成本來選擇設計流量，約束條件是無水質損害的機率要大於一個可接受的最低水平。模型中將每個季節視為階段，而且透過可靠性約東在動態規則中建立狀態變數。通用使用這種動態規劃模型，EPA能夠建立率節性排汙底限，在維持 EPA 水質標準的前提下，提供最低成本的治理計劃。 資料來源：基於美國環保署的 John Conrey 提供的資訊。 專業術語 dynamic programming 動態規劃一種解決問題的方法，把一個可能難以解決的大問題分解成大量互相關聯的通常更容易解決的子問題。 principle of optimality 最優性原期不管在先前的階段所做的決策如何，如果在階段n中所做決策是整個最優解的一部分，那麼在階段n中所做的決策必須對所有剩餘的階段來說是最優的。
490 資料、模型與決策：管理科學篇 stages 階段當一個大問題被分解成若干子問題時，動態規劃解決方法則為每個問題提供了一個階段。 decision variabled. 決策變數d。 在階段n中可做出的可能的決策的變數。 state variables x. and x. 狀態變數工，和x.1一個輸人狀態變數x，和一個輸出狀態變數*.1一起定義了階段n的開始和結束的過程的條件。 stage transformation functiont. （x.，0.） 階段轉移爾數，（*，，d.）把階段n中的輸出狀態變數*.-1和輸人狀態變數x，以及決策變數d。聯絡起來的規則或等式。 return functionr.（x..d，） 收益函式T。（.，d.） 與階段n的一個特定輸入狀態變數x。的值以及做出的決策d。相關聯的值（例如收益和損失）。 knapsack problem 揹包問題 N種物品，每種物品有不同的重量和價值，把它們裝到一個有一定重量限制的揹包中，求裝載每種物品的數量以便最大化揹包中物品的總價值。 問題 2. 考慮下面的網路圖。每條弧上面的數字代表相連兩個結點之間的距離。 8 10 6 a.用動態規劃的方法找到從節點1到節點10的最短路徑。 b. 從節點4到節點10，哪條是最短路徑？ c.列舉出所有從節點1到節點10 的路徑。解釋為什麼動態規劃可以用比窮舉法更少的計算表4 步驟求解問題。 新員工數 4.一個公司剛僱用了8名員工，打算將他們的時工作 0 3 4 5 6 7 8 間分配給4項工作。表4是每項工作的利潤。這 22 30 37 44 49 54 58 60 61 裡，工作被看做分配去完成它的員工數的函式。 30 40 48 55 59 62 64 66 67 a.用動態規劃的方法求出員工與工作的最優 46 52 56 59 62 65 67 68 69 5 22 36 48 52 55 58 60 61 分配。 b. 假設只有6名員工被僱用，又將怎樣分配？ 6.一個大的製造公司擁有一個完善的管理培訓專案。每個受訓者被要求完成一個4 階段的專案，在每個階段， 受訓者可能會有一系列不同的任務。下表是各階段相關任務的預測完成時間。 階段1 階段2 階段 3 階段4 階段1 階段2 階段3 階段4 A-13 E-3 H-12 1-10 C-20 G-5 J-7 N-13 B-10 F-6 1-6 M-5 D-17 K-10 後面的作業主要依賴於前面的作業。例如，一個受訓者在階段1完成A任務後，可能只能向階段2的F或 G 任務繼續，也就是說每項任務都有一個繼承關係。 作業可行的後縫任務作業可行的後繼任務作業可行的後繼任務作業可行的後繼任務 A F,G E H,1,J,K 1 L,M M 完工 B F F H,K J C K M,N N 完工 G G J,K N D E,G H L,M L 完工 a.公司希望確定使培訓時間最小化的作業順序。用動態規劃方法建模並求解該問題。（提示：建立何題的