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

“運(yùn)籌學(xué)”編寫組

2008年12月

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

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

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

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

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

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

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

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

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

比

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

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

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

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

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

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

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

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

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

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

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

C1－D3－E：。

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

即由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，可計(jì)算：

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

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

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

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

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

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

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

表示,即為對整體目標(biāo)函數(shù)的貢獻(xiàn)。整體指標(biāo)函數(shù)由vj(j=1,2,…,n)組成，常見的形式有：階段指標(biāo)之和，即，階段指標(biāo)之積，即，階段指標(biāo)之極大（或極?。?/p>

.這些形式下第k

到第j

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

根據(jù)狀態(tài)轉(zhuǎn)移方程,指標(biāo)函數(shù)Vnk

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

對pnk

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

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

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

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

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

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

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

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

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

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

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

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

，1≤i≤n

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

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

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

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

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

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

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

k=2時(shí)，計(jì)算結(jié)果列入表5－3。表5－3s2012345678910x2000001010101012012012V2000005050505051005100510V2+f3000005656565651061110121110f2(s2)0000566610111200001000210當(dāng)

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

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

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

對k#

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

時(shí)，s1

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

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

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

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

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

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

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

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