第五章動態(tài)規(guī)劃

“運籌學”編寫組

2008年12月

運籌學第五章動態(tài)規(guī)劃內容多階段決策過程與方法動態(tài)規(guī)劃的基本概念和遞歸方程最優(yōu)性原理與建模方程動態(tài)規(guī)劃的應用案例實際應用案例:機器生產(chǎn)負荷分配習題概述

動態(tài)規(guī)劃（dynamicprogramming）是求解多階段決策問題的一種最優(yōu)化方法。20世紀50年代初，R.E.Bellman等人在研究多階段決策過程(multiplestepdecisionprocess)的優(yōu)化問題時，提出了著名的最優(yōu)性原理（principleofoptimality）,即把多階段決策過程轉化為一系列單階段問題，逐個求解，創(chuàng)立了解決這類多階段優(yōu)化問題的新方法—動態(tài)規(guī)劃。1957年R.E.Bellman出版了《DynamicProgramming》，這是該領域的第一本著作。概述

動態(tài)規(guī)劃問世以來，在經(jīng)濟管理、生產(chǎn)調度、工程技術、博弈論和最優(yōu)控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題，用動態(tài)規(guī)劃方法比用其它方法求解更為方便。雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時間無關的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃），其本質是一個多階段決策問題,可以人為地引進時間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。概述

應指出，動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種特殊算法（如線性規(guī)劃的是一種算法）。因而，它不象線性規(guī)劃那樣有一個標準的數(shù)學表達式和明確定義的一組規(guī)則，而必須對具體問題進行具體分析處理,面向特定問題,建立動態(tài)規(guī)劃模型。因此，在學習時，除了要對基本概念和方法正確理解外，應以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解問題,通過案例揣摩解題精髓。5．1多階段決策過程與方法

動態(tài)規(guī)劃是目前解決多階段決策過程問題的基本方法之一。

所謂多階段決策過程，是指這樣一類的決策問題：由問題的特性可將整個決策過程按時間、空間等標志劃分為若干個互相聯(lián)系又互相區(qū)別的階段。在它的每一階段都需要作出決策，從而使整個過程達到最好的效果。因此，各個階段決策的不是任意確定的，它依賴于當前面臨的狀態(tài)，又影響以后的發(fā)展，當各個階段決策確定后，就組成了一個決策序列，因而也就決定了整個決策過程的一條活動路線，這樣一個前后關聯(lián)具有鏈狀結構的多階段決策過程就稱為多階段決策過程，也稱為序貫決策過程（見圖5－1所示），這種問題稱為多階段決策問題。

在多階段決策問題中，各個階段采取的決策，一般來說是與時間有關的，決策依賴于當前的狀態(tài)，又隨即引起狀態(tài)的轉移，一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動態(tài)”的含義，因此處理這種問題的方法稱為動態(tài)規(guī)劃方法。圖5－1

這是一個以空間位置為特征的多階段決策問題,決策順序為ABCDE。例5.1如圖5－2所示，給定一個線路網(wǎng)絡，兩點之間連線上的數(shù)字表示兩點間的距離（或費用）。試求一條由A到E的線路，使總長度最小（或總費用最?。?。AD2D1C1B3B2D3EB1123533134241352315AC2圖5－2例5.2工廠生產(chǎn)某種產(chǎn)品，每單位（千件）的成本為1（千元），每次開工的固定成本為3（千元），工廠每季度的最大生產(chǎn)能力為6（千件）。經(jīng)調查，市場對該產(chǎn)品的需求量第一、二、三、四季度分別為2，3，2，4（千件）。如果工廠在第一、二季度將全年的需求都生產(chǎn)出來，自然可以降低成本（少付固定成本費），但是對于第三、四季度才能上市的產(chǎn)品需付存儲費，每季每千件的存儲費為0.5（千元）。還規(guī)定年初和年末這種產(chǎn)品均無庫存。試制定一個生產(chǎn)計劃，即安排每個季度的產(chǎn)量，使一年的總費用（生產(chǎn)成本和存儲費）最少。顯然，這是一個以時間為特征的多階段決策問題。例5.1通常稱為最短路徑問題，這是一個簡單而又十分典型的多階段決策問題。我們以它為例來說明用動態(tài)規(guī)劃求解多階段決策問題的特點與方法原理。從圖5－2可以看出，從A到E一共有18條不同的線路，即18種不同的方案。顯然其中必存在一條從全過程看效果最好的線路，稱之為最佳線路。

對最佳線路來說，它具有如下的重要性質：設最佳線路第二、三、四階段決策的結果是選擇，，（見圖5－3），則其中從第二階段初始狀態(tài)到E點的路徑也是從到E點一切可能路徑中的最佳路徑，這性質很容易用反證法證明：設從到E另有一條更短的路線。則用再加上這條路徑就

比

更短。這與后者是一切路徑中最短路徑相矛盾。因此從必也是從一切路徑中最短路徑。顯然這個性質不僅對是成立的，而且對最短路徑中的任一個中間點都是成立的。因此，最佳路徑中任一個狀態(tài)（中間點）到最終狀態(tài)（最終點）的路徑也是該狀態(tài)到最終狀態(tài)一切可能路徑中的最短路徑。圖5－3

利用這個性質，則可以從最后一段開始，由終點向起點逐階遞推，尋求各點到終點的最短路徑，當遞推到起始點A時，便是全過程的最短路徑。這種由后向前逆向遞推的方法正是動態(tài)規(guī)劃中常用的逆序法(逆向歸納法)。我們以例5.1為例,說明如何用逆向歸納法來求解多階段決策問題。

我們以例5.1為例,說明如何用逆向歸納法來求解多階段決策問題。

由圖5－2，將決策全過程分為四個階段。從最后一個階段開始計算：（1）k

=4，第四階段在第四階段，有三個初時狀態(tài)：D1,D2

與D3，而全過程的最短路徑究竟是經(jīng)過D1，D2

，D3中的哪一點，目前無法肯定，因此只能將各種可能都考慮，若全過程的最短路徑經(jīng)過D1，則從D1到終點的最短路徑距離為：f4(D1)=3；

而類似可得：f4(D2)=1,f4(D3)=5。

（2），第三階段在第三階段有兩個初始狀態(tài)：C1

與C2。同樣我們無法確定全過程的最短路徑是經(jīng)過C1還是C2。因此兩種狀態(tài)都要計算：若全過程最短路徑是經(jīng)過C1，則由C1到E有三條支路：C1－D1－E、C1－D2－E及C1－D3－E，而對支路C1－D1－E，其最短路徑應為：從C1－D1的距離，再加上D1－E的最短路徑，故有

C1－D1－E：，C1－D2－E：，

C1－D3－E：。

由前述性質可知，若全過程最短路徑經(jīng)過C1，則C1到終點E應是一切可能路徑中最短路徑，因此可有

即由C1－E的最短路徑為C1－D1－E，最短距離為5。同理，有

即由C2－E的最短路徑為C2－D1－E，最短距離為4。

（2），第二階段第二階段有三種初始狀態(tài)：。同理可得到：因此從的最短路徑為B1－C2－D1－E，最短距離為7；從的最短路徑為B2－C1－D1－E，最短距離為6；從的最短路徑為B3－C1－D1－E，最短距離為8。（4），第一階段第一階段只有一種初始狀態(tài)A，可計算：

即從的最短路徑為A－B2－C1－D1－E，最短距離為8。從以上的計算過程可看出，動態(tài)規(guī)劃方法的基本思想是，把一個比較復雜的問題分解成一系列同一類型的更容易求解的子問題，對每個子問題，計算過程單一化，便于應用計算機。同時由于對每個子問題都考慮到最優(yōu)效果，于是就系統(tǒng)地刪去了大量的中間非最優(yōu)化的方案組合，使得計算工作量比窮舉法大大減少,但是其本質還是窮舉法。

由上述分析，可將動態(tài)規(guī)劃方法求解多階段決策問題的特點歸納如下：（1）每個階段的最優(yōu)決策過程只與本階段的初始狀態(tài)有關，而與以前各階段的決策（即為了到達本階段的初始狀態(tài)而采取的決策組合）無關。換言之，本階段之前的狀態(tài)與決策，只是通過系統(tǒng)在本階段所處的初始狀態(tài)來影響系統(tǒng)的未來。具有這種性質的狀態(tài)稱為無后效性（即馬爾可夫性）狀態(tài)，動態(tài)規(guī)劃方法適用于求解具有無后效性的多階段決策問題。（2）對最佳路徑（最優(yōu)決策過程）所經(jīng)過的各個階段，其中每個階段始點到全過程終點的路徑，也是子決策中的最佳路徑，整體最優(yōu)必然有局部最優(yōu)。這就是Bellman提出的著名的最優(yōu)化原理。（3）在逐段遞推過程中，每階段選擇最優(yōu)決策時，不應只從本階段的直接效果出發(fā)，而應從本階段開始的往后全過程的效果出發(fā)，也即應該考慮兩種效果：一是本階段初到本階段終（也即下階段初）所選決策的直接效果；二是由所選決策確定的下階段初往后直到終點的所有決策過程的總效果，也稱為間接效果。這兩種效果的結合必須是最優(yōu)的。（4）經(jīng)過遞推計算得到各階段的有關數(shù)據(jù)后，反方向即可求出相應的最優(yōu)決策過程。5．2動態(tài)規(guī)劃的基本概念和遞歸方程（1）階段階段(step)是對整個決策過程的自然劃分。通常根據(jù)時間順序或空間順序的特征,來劃分階段，以便按階段的次序解優(yōu)化問題。階段變量一般用k=1,2,

…,n表示。（2）狀態(tài)狀態(tài)（state）表示每個階段開始時決策過程所處的自然狀況……。它應能描述過程的特征并且無后效性，即當某階段的狀態(tài)變量給定時，這個階段以后過程的演變與該階段以前各階段的狀態(tài)無關。通常要求狀態(tài)是直接的或間接可以觀測的。描述狀態(tài)的變量稱狀態(tài)變量（statevariable）。變量允許取值的范圍稱允許狀態(tài)集合(setofadmissiblestates)。用xk表示第k階段的狀態(tài)變量，它可以是一個數(shù)或一個向量。用Xk表示第k階段的允許狀態(tài)集合,有xk∈Xk。n個階段的決策過程有n+1個狀態(tài)變量，xn+1表示xn演變的結果。根據(jù)過程演變的具體情況，狀態(tài)變量可以是離散的或連續(xù)的。為了計算的方便,有時將連續(xù)變量離散化；為了分析的方便有時又將離散變量視為連續(xù)的。狀態(tài)變量簡稱為狀態(tài)。（3）決策當一個階段的狀態(tài)確定后，可以作出各種選擇從而演變到下一階段的某個狀態(tài)，這種選擇過程稱為決策（decision），在最優(yōu)控制問題中也稱為控制（control）。描述決策的變量稱決策變量（decisionvariable），變量允許取值的范圍稱允許決策集合（setofadmissibledecisions）。用uk(xk)表示第k階段處于狀態(tài)xk時的決策變量，它是xk的函數(shù)，

用Uk(xk)表示xk的允許決策集合,決策過程就是選擇uk(xk)∈Uk(xk)的過程。決策變量簡稱決策。（4）策略決策組成的序列稱為策略（policy）。由初始狀態(tài)開始的全過程的策略記作，即:.由第k階段的狀態(tài)開始到終止狀態(tài)的后部子過程的策略記作，即:，.類似地，由第k到第j階段的子過程的策略記作:.可供選擇的策略有一定的范圍，稱為允許策略集合(setofadmissiblepolicies)，用表示。，

（5）狀態(tài)轉移方程在確定性決策過程中，一旦某階段的狀態(tài)和決策為已知，下階段的狀態(tài)便完全確定,這個過程稱作狀態(tài)轉移。用狀態(tài)轉移方程（equationofstatetransition）表示這種演變規(guī)律，寫作為:

（5.1）（6）指標函數(shù)和最優(yōu)值函數(shù)指標函數(shù)(objectivefunction)是衡量決策過程和決策結果優(yōu)劣的數(shù)量指標，它是定義在全過程和所有后部子過程上的數(shù)量函數(shù)，用表示，。指標函數(shù)應具有可分離性，即可表為的函數(shù)，記為

決策過程在第j階段的階段指標取決于狀態(tài)xj和決策uj，用vj(xj,uj)

表示,即為對整體目標函數(shù)的貢獻。整體指標函數(shù)由vj(j=1,2,…,n)組成，常見的形式有：階段指標之和，即，階段指標之積，即，階段指標之極大（或極小），即

.這些形式下第k

到第j

階段子過程的指標函數(shù)為。

根據(jù)狀態(tài)轉移方程,指標函數(shù)Vnk

還可以表示為狀態(tài)xk和策略pnk的函數(shù)，即Vnk(xk,pnk)。在給定時,指標函數(shù)Vnk

對pnk

的最優(yōu)值稱為最優(yōu)值函數(shù)（optimalvaluefunction），記為fk(xk)，即.

實際上,fk(xk)是從狀態(tài)xk開始的后繼最有決策的目標函數(shù)值。（7）最優(yōu)策略和最優(yōu)軌線使指標函數(shù)Vnk

達到最優(yōu)值的策略是從k開始的后部子過程的最優(yōu)子策略，記作。是全過程的最優(yōu)策略，簡稱最優(yōu)策略（optimalpolicy）。從初始狀態(tài)出發(fā)，決策過程按照和狀態(tài)轉移方程演變所經(jīng)歷的狀態(tài)序列稱為最優(yōu)軌線（optimaltrajectory）。（8）遞歸方程如下方程稱為遞歸方程

fn+1(xn+1)稱作邊界條件。在遞歸方程中，當為加法時,fn+1(xn+1)=0；當為乘法時，fn+1(xn+1)=1

。動態(tài)規(guī)劃遞歸方程是動態(tài)規(guī)劃的最優(yōu)性原理的基礎，即：最優(yōu)策略的子策略，構成最優(yōu)子策略。用狀態(tài)轉移方程（1）和遞歸方程（2）求解動態(tài)規(guī)劃的過程，是由k=n+1逆推至k=1，故這種解法稱為逆序解法。當然，對某些動態(tài)規(guī)劃問題，也可采用順序解法。(5-2)5．3最優(yōu)性原理與建模方程

最優(yōu)化性原理作為動態(tài)規(guī)劃的理論基礎，它能解決許多類型多階段決策優(yōu)化問題。長期以來，許多著作都是沿用這一提法。動態(tài)規(guī)劃的最優(yōu)性原理是“作為整個過程的最優(yōu)策略具有這樣的性質：即無論過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構成最優(yōu)決策”。簡言之，一個最優(yōu)策略的子策略總是最優(yōu)的。但是，隨著人們深入地研究動態(tài)規(guī)劃，逐漸認識到：對于不同類型問題所建立的嚴格定義的動態(tài)規(guī)劃模型，必須對相應的最優(yōu)性原理給以必要的驗證。即是說，最優(yōu)性原理不是對任何決策過程都普遍成立的。而且，“最優(yōu)性原理”與動態(tài)規(guī)劃基本方程并不是無條件等價的，兩者之間也不存在確定的蘊含關系。而動態(tài)規(guī)劃的遞歸方程在動態(tài)規(guī)劃的理論和方法中起著更為重要的作用，反應動態(tài)規(guī)劃遞歸方程的是最優(yōu)性原理，遞歸方程是策略最優(yōu)性的充要條件，而最優(yōu)性原理僅僅是策略最優(yōu)性的必要條件。所以把動態(tài)規(guī)劃的遞歸方程作為動態(tài)規(guī)劃的理論基礎可能更為合理。動態(tài)規(guī)劃的遞歸方程：設階段數(shù)為n

的多階段決策過程，其階段編號為k=0，1，…，n-1。允許策略是最優(yōu)策略的充要條件，是對任一個k，0<k<n-1和s0∈S0有，

其中，。它是由給定的初始狀態(tài)s0和子策略p0,k-1所確定的k段狀態(tài)。當V是效益函數(shù)時，opt取max；當V是損失函數(shù)時，opt取min。推論:若允許策略是最優(yōu)策略，則對任意的k，k=0，1，…，n-1,它的子策略對于為起點的k到n-1子過程來說，必是最優(yōu)策略。此推論就是前面提到的動態(tài)規(guī)劃的“最優(yōu)性原理”，它僅僅是最優(yōu)性策略的必要性，所以，動態(tài)規(guī)劃的遞歸方程是動態(tài)規(guī)劃的理論基礎?？v上所述，如果一個問題能用動態(tài)規(guī)劃方法求解，那么，我們可以按下列步驟，首先建立起動態(tài)規(guī)劃的數(shù)學模型：（1）將決策過程劃分成恰當?shù)碾A段。（2）正確選擇狀態(tài)變量xk，使它既能描述過程的狀態(tài)，又滿足無后效性，同時確定允許狀態(tài)集合Xk。（3）選擇決策變量uk

，確定允許決策集合Uk(xk)

。（4）寫出狀態(tài)轉移方程。（5）確定階段指標vk(xk,uk)及指標函數(shù)Vnk

的形式（階段指標之和，階段指標之積，階段指標之極大或極小等）。（6）寫出基本方程,即最優(yōu)值函數(shù)滿足的遞歸方程，以及邊界條件。

建立動態(tài)規(guī)劃模型，基本上是按照上述順序，逐步確定（1）－（6）的內容。建模是解決實際問題的第一步，也是比較困難的一步，動態(tài)規(guī)劃不像線性規(guī)劃那樣有統(tǒng)一的模型和統(tǒng)一的處理方法，必須針對具體問題做具體分析，綜合考慮多方面的因素。譬如，如何劃分階段，如何選擇正確的狀態(tài)變量和決策變量，如何構造遞歸方程等等，確實需要一定的技巧，需要多練習，不斷總結和積累經(jīng)驗。5．4動態(tài)規(guī)劃的應用案例5．4．1背包問題背包問題是一個典型多階段決策問題。一維背包問題是：一位旅行者能承受的背包最大載重量是b(kg)，現(xiàn)有種物品供他選擇裝入背包，第i種物品單件重量為ai(kg),其價值（或其他重要參數(shù)）為ci

，1≤i≤n

。設裝載數(shù)量是xi,則總價值是攜帶數(shù)量xi的函數(shù),即ci

xi。問旅行者應如何選擇所攜帶物品的件數(shù),以使總裝載價值最大？背包問題實際上就是運輸問題中車船的最優(yōu)配載問題，還可以廣泛地用于解決其他的問題,或者作為其他復雜問題的子問題。其一般的整數(shù)規(guī)劃模型可表述為：下面用動態(tài)規(guī)劃方法來求解。（1）階段k

：即需要裝入的n種物品的次序，每段裝入一種物品，共n段。（2）狀態(tài)變量sk

：即在第k段開始時允許裝入物品的總重量，即可以動用的資源。顯然有s1=b。（3）決策變量xk

：即裝入第k種物品的件數(shù)。（4）狀態(tài)轉移方程：sk+1=sk-akxk允許的決策集合是。（5）遞歸（基本）方程是例5.3一分銷商擬用一10噸載重的大卡車裝載3種貨物，資料見表5－1，問應如何組織裝載，可使總價值最大？表5－1數(shù)據(jù)資料

解：設裝載第i種貨物的件數(shù)為xi

，則有整數(shù)線性規(guī)劃貨物編號123單位質量單位價值345456用動態(tài)規(guī)劃方法的順序解法求解，則當k=3時，計算結果列入表5－2。表5－2s3012345678910x300000111112f3(s3)000006666612當

k=2時，計算結果列入表5－3。表5－3s2012345678910x2000001010101012012012V2000005050505051005100510V2+f3000005656565651061110121110f2(s2)0000566610111200001000210當

k=1時,即，依狀態(tài)轉移方程反推，此時有，依第2段計算結果,。有，由第3段計算結果知，。即最優(yōu)方案為，最大價值為13。

5．4．2投資問題例5.4現(xiàn)有資金5百萬元，可對三個項目進行投資，投資額均為整數(shù)（單位：百萬元），其中2＃項目的投資不得超過3百萬元，1＃和3#項目得投資均不得超過4百萬元，3#項目至少要投資1百萬元，每個項目投資5年后，投資額與預計收益見表5－4。問如何投資可望獲得最大收益。表5－4投資收益投資項目012341＃03610122＃051012－3＃－481115解：這個投資問題可以分成三個階段，在第k階段確定k#

項目的投資額，令狀態(tài)變量sk為對1＃，2＃，…,(k-1)#項目投資后剩余的資金額；xk為對k＃項目的投資額；rk(xk)為對k#項目投資xk的收益，fk(sk)為應用剩余的資金sk

對k#

，k#,(k+1)#，…，N#進行最優(yōu)化投資可獲得的最大收益。狀態(tài)轉移方程為。為了獲得最大收益，必須將5百萬元全部用于投資，故假想有第4階段存在時，必有s4=0，于是得遞歸方程：當k=3時，（3＃至多投資4百萬元，至少投資1百萬元）.當k=2時，（2＃投資不超過3百萬元），注意：3#至多投資4百萬元。，當k=1

時，s1

=5（最初有5百萬元，3＃至少投資1百萬元）應用順序反推可知最優(yōu)投資方案。方案1：；方案2：。

最大收益均為21百萬元。一、定價問題某公司考慮為某新產(chǎn)品定價，該產(chǎn)品的單價擬從每件5元、6元、7元和8元這四個中選取一個，每年允許價格有1元幅度的變動，該產(chǎn)品預計暢銷五年，據(jù)預測不同價格下各年的利潤如表3-1所示。表3-2每年預計利潤額單價第一年第二年第三年第四年第五年5元6元7元8元1012141612131415151616152020181425241814建立數(shù)學模型按年劃分階段，k=1,2,...,5每階段的狀態(tài)變量為本年(上一年已確定)的價格，狀態(tài)變量的可行集合Sk=(5,6,7,8)。決策變量為每年依據(jù)當年價格為下一年度決定價格，根據(jù)題意決策變量的可行集合是：采用逆序算法，因此狀態(tài)轉移方程是最優(yōu)值函數(shù)遞推方程為進行各階段的計算采用逆序法，設當k=5時，S5=(5,6,7,8)，由表3-1得到當k=4時，S4=(5,6,7,8)，由遞推方程得繼續(xù)求解同理得其它各階段的最優(yōu)解反推得最優(yōu)路線按照與求最優(yōu)值函數(shù)方向相反的順序求最優(yōu)狀態(tài)路線：最優(yōu)決策變量。即從第一年單價應為8元開始，向后推算。得第二年定價8元，第三年定價7元，第四年定價6元，第五年定價5元。最大利潤值為92萬元。也可用決策圖求解二、資源分配問題某公司將5臺加工中心分配給甲、乙、丙、丁四個工廠，各工廠得設備后可產(chǎn)生如表3-2所示的利潤，應怎么分配設備可使公司總利潤最大？工廠設備數(shù)甲乙丙丁012345067101215037912130510111111046111212建立數(shù)學模型按工廠次序劃分階段，k=1，2，3，4狀態(tài)變量為各階段可用于分配的設備總臺數(shù)決策變量是分配給第k工廠的設備數(shù)采用逆序算法，狀態(tài)轉移方程最優(yōu)值函數(shù)遞推方程第4階段的最優(yōu)解當k=4時，S4=(0,1,2,3,4,5)012345012345046111212046111212012345第3階段的最優(yōu)解當k=3時，S3=(0,1,2)000000010105404551201205106406910102第3階段的最優(yōu)解（續(xù)）當k=3時，S3=3301230510111164011111411142第3階段的最優(yōu)解（續(xù)）當k=3時，S3=44012340510111112116401216161511161，2第3階段的最優(yōu)解（續(xù)）當k=3時，S3=550123450510111111121211640121721171511212第2階段的最優(yōu)解當k=2時，S2=(0,1,2)000000010103505350201203710501087100第2階段的最優(yōu)解（續(xù)）當k=2時，S2=33012303791410501413129140第2階段的最優(yōu)解（續(xù)）當k=2時，S2=4401234037912161410501617171412171，2第2階段的最優(yōu)解（續(xù)）當k=2時，S2=55012345037912132116141050211921191715210，2第1階段的最優(yōu)解（續(xù)）當k=1時，S1=5

50123450671012152117141050212321201715231反向求最佳狀態(tài)路線方案一方案二工廠名分配設備數(shù)工廠名分配設備數(shù)甲乙丙丁1121甲乙丙丁1220三、生產(chǎn)存儲問題某公司生產(chǎn)并銷售某產(chǎn)品。根據(jù)市場預測，今后四個月的市場需求量如表3-7所示。時期（月）需求量（dk）12342324三、生產(chǎn)存儲問題某公司生產(chǎn)并銷售某產(chǎn)品。根據(jù)市場預測，今后四個月的市場需求量如表3-7所示。時期（月）需求量（dk）12342324已知的其它條件已知生產(chǎn)一件產(chǎn)品的成本是1千元，每批產(chǎn)品的生產(chǎn)準備成本是3千元，每月僅能生產(chǎn)一批，每批6件。每件存儲成本為0.5千元，且第一個月初無存貨，第四個月末的存貨要求為零。求最優(yōu)生產(chǎn)計劃。設第k月的生產(chǎn)量uk，存儲量為Sk,則總成本為建立數(shù)學模型以月劃分階段，k=1,2,3,4各階段決策變量為該階段生產(chǎn)量uk，狀態(tài)變量為該階段存儲量Sk。采用逆序算法，則狀態(tài)轉移方程為最低成本遞推公式是第四階段的最優(yōu)解當k=4時，d4=4,因第四階段末無存貨，因此S4=(0,1,2,3,4)S4u4本期成本C4S5f5(S5)f4(S4)生產(chǎn)存儲01234432107654000.511.5276.565.52000000000076.565.52第三階段最優(yōu)解當k=3時，由于，且第三階段需求量d3=2，S3=(0,1,2,3,4,5,6)S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲0234565678900000567890123476.565.521212.51313.511第三階段最優(yōu)解:S3=1S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲112345456780.50.50.50.50.54.55.56.57.58.50123476.565.5211.512.012.513.010.5第三階段最優(yōu)解:S3=2S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲2012340456711111156780123476.565.52811.512.012.510.0第三階段最優(yōu)解:S3=3,4S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲3012304561.51.51.51.51.55.56.57.512346.565.52811.512.09.5401204522226723465.52811.59第三階段最優(yōu)解:S3=5,6S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲501042.52.52.56.5345.5288.560033425第二階段最優(yōu)解當k=2時，d2=3，由于最生產(chǎn)能力為6，而d1=2，因此S2=(0,1,2,3,4)S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲03456678900006789012311.010.58.08.01717.51617第二階段最優(yōu)解:S2=1S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲123456567890.50.50.50.50.55.56.57.58.59.50123411.010.58.08.08.016.51715.516.517.5第二階段最優(yōu)解:S2=2S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲2123456456789111111567891001234511.010.58.08.08.08.016.016.515.016.017.018.0第二階段最優(yōu)解:S2=3S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲3012345604567891.51.51.51.51.51.51.51.55.56.57.58.59.510.5012345611.010.58.08.08.08.05.012.516.014.515.516.517.515.5第二階段最優(yōu)解:S2=4S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲4012345045678222222267891012345610.58.08.08.08.05.012.51415161715第一階段最優(yōu)解當k=1時，d1=2，S1=0S1u1本期成本C1S2f2(S2)f1(S1)生產(chǎn)存儲0234565678900000567890123416.015.515.012.512.52121.52220.521.5最優(yōu)解從第一階段向后反推最優(yōu)路線，總結可得時期K期初存貨期末存貨最優(yōu)生產(chǎn)量該期成本總成本SkSk+1123403043040506081.59220.512.5112已知的其它條件已知生產(chǎn)一件產(chǎn)品的成本是1千元，每批產(chǎn)品的生產(chǎn)準備成本是3千元，每月僅能生產(chǎn)一批，每批6件。每件存儲成本為0.5千元，且第一個月初無存貨，第四個月末的存貨要求為零。求最優(yōu)生產(chǎn)計劃。設第k月的生產(chǎn)量uk，存儲量為Sk,則總成本為建立數(shù)學模型以月劃分階段，k=1,2,3,4各階段決策變量為該階段生產(chǎn)量uk，狀態(tài)變量為該階段存儲量Sk。采用逆序算法，則狀態(tài)轉移方程為最低成本遞推公式是第四階段的最優(yōu)解當k=4時，d4=4,因第四階段末無存貨，因此S4=(0,1,2,3,4)S4u4本期成本C4S5f5(S5)f4(S4)生產(chǎn)存儲01234432107654000.511.5276.565.52000000000076.565.52第三階段最優(yōu)解當k=3時，由于，且第三階段需求量d3=2，S3=(0,1,2,3,4,5,6)S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲0234565678900000567890123476.565.521212.51313.511第三階段最優(yōu)解:S3=1S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲112345456780.50.50.50.50.54.55.56.57.58.50123476.565.5211.512.012.513.010.5第三階段最優(yōu)解:S3=2S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲2012340456711111156780123476.565.52811.512.012.510.0第三階段最優(yōu)解:S3=3,4S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲3012304561.51.51.51.51.55.56.57.512346.565.52811.512.09.5401204522226723465.52811.59第三階段最優(yōu)解:S3=5,6S3u3本期成本C3S4f4(S4)f3(S3)生產(chǎn)存儲501042.52.52.56.5345.5288.560033425第二階段最優(yōu)解當k=2時，d2=3，由于最生產(chǎn)能力為6，而d1=2，因此S2=(0,1,2,3,4)S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲03456678900006789012311.010.58.08.01717.51617第二階段最優(yōu)解:S2=1S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲123456567890.50.50.50.50.55.56.57.58.59.50123411.010.58.08.08.016.51715.516.517.5第二階段最優(yōu)解:S2=2S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲2123456456789111111567891001234511.010.58.08.08.08.016.016.515.016.017.018.0第二階段最優(yōu)解:S2=3S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲3012345604567891.51.51.51.51.51.51.51.55.56.57.58.59.510.5012345611.010.58.08.08.08.05.012.516.014.515.516.517.515.5第二階段最優(yōu)解:S2=4S2u2本期成本C2S3f3(S3)f2(S2)生產(chǎn)存儲4012345045678222222267891012345610.58.08.08.08.05.012.51415161715第一階段最優(yōu)解當k=1時，d1=2，S1=0S1u1本期成本C1S2f2(S2)f1(S1)生產(chǎn)存儲0234565678900000567890123416.015.515.012.512.52121.52220.521.5最優(yōu)解從第一階段向后反推最優(yōu)路線，總結可得時期K期初存貨期末存貨最優(yōu)生產(chǎn)量該期成本總成本SkSk+1123403043040506081.59220.512.5112

5．4．3排序問題設有n個工件需要在機床A、B上加工，每個工件都必須講過先A而后B得兩道加工工序。以ai,bi分別表示工件i(0≤i≤n)在A、B上的加工時間。問應如何在兩機床上安排加工得順序，使在機床A上加工第一個工件開始到在機床B上將最后一個工件加工完為止，所用的加工總時間最少？

加工工件在機床A上有加工順序問題，在機床B上也有加工順序問題。它們在A、B兩臺機床上加工工件的順序是可以不同的。當機床B上的加工順序與機床A不同時，意味著在機床A上加工完畢的某些工件，不能在機床B上立即加工，而是要等到另一個或一些工件加工完畢后才能加工。這樣，使機床B的等待加工時間加長，從而使總的加工時間加長了?？梢宰C明：最優(yōu)加工順序在兩臺機床上可同時實現(xiàn)。因此，最優(yōu)排序方案可以在機床A、B上加工順序相同的排序中去尋找。即使如此，所有可能的方案仍有n!

個，這是一個不小的數(shù)，用窮舉法是不現(xiàn)實的。下面用動態(tài)規(guī)劃方法來研究同順序兩臺機床加工n個工件的排序問題。

當加工順序取定之后，工件在A上加工時沒有等待時間，而在B上則常常等待，因此，尋求最優(yōu)排序方案只有盡量減少在B上等待加工的時間，才能使總加工時間最短。設第i個工件在機床A上加工完畢以后，在B上要經(jīng)過若干等待時間才能加工，故對同一個工件來說，在A、B上總是出現(xiàn)加工完畢的時間差，我們可以它來描述加工狀態(tài)?，F(xiàn)在，我們以在機床A上更換工件的時刻作為時段，以X表示在機床A上等待加工的按取定順序排列的工件集合。以x表示不屬于X的在A上最后加工完的工件。以t表示在A上加工完x的時刻算起到B上加工完x所需的時間。這樣，在A上加工完一個工件之后，就有(X,t)與之對應。

今選取(X,t)作為描述機床A、B在加工過程中的狀態(tài)變量。這樣