運籌學第八章動態(tài)規(guī)劃8.1 動態(tài)規(guī)劃的研究對象和特點

動態(tài)規(guī)劃(DynamicProgramming)是一項重要的數(shù)量規(guī)劃方法，由美國數(shù)學家貝爾曼(R..Bellman)和徳賴費斯（Dreyfus）等人在二十世紀中葉提出的。1957年，貝爾曼發(fā)表了動態(tài)規(guī)劃方面的第一本著作〈〈DynamicProgramming〉〉,標志著運籌學的又一個分支動態(tài)規(guī)劃的建立。動態(tài)規(guī)劃被廣泛應用于企業(yè)經(jīng)營、工業(yè)工程、資源理論、最佳控制理論和商業(yè)決策理論中，并且取得了一定的經(jīng)濟效果。第2頁,共90頁，2024年2月25日，星期天

一、動態(tài)規(guī)劃的研究對象

動態(tài)規(guī)劃最初是根據(jù)多階段決策問題的特點，由貝爾曼等人提出了解決此類問題的“最優(yōu)化原理”，并且進一步成功地解決了許多實際問題，才得到大家的充分重視。

1.多階段決策又稱序貫決策問題，通常它可以按時間順序分成若干個相互聯(lián)系的階段，在每一個階段都需要作出一個決策，每一個階段作出的決策又稱為子策略，每個階段作出的子策略就組成此多階段決策問題的策略集。實際工作中我們很難遇到不影響未來決策的當前決策，決策者經(jīng)常面臨的問題通常是要他們作出一系列決策，而這些決策中的每一個均依賴于先前決策的結果，動態(tài)規(guī)劃就可被用來解決很多此類問題。

2.動態(tài)規(guī)劃也可以應用于解決某些與時間無關的問題。例如：把固定數(shù)量的幾種資源在若干用途上進行配置，這個問題被劃分成幾個步驟來求解，用這種方法求最后的決策就好象它和時間有關似的，這就進一步擴大了動態(tài)規(guī)劃解決問題的范圍。

第3頁,共90頁，2024年2月25日，星期天二、動態(tài)規(guī)劃的特點

1.動態(tài)規(guī)劃根據(jù)問題的具體情況，把整個問題劃分成數(shù)個階段，而變成數(shù)個部分問題。當這些部分問題由階段的順序而貫通，則形成一項多重階段的程序（過程）。2.動態(tài)規(guī)劃對整個問題的求解，通常是從一個階段的部分問題開始，逐個逆序向前推求解。對某些問題也可以反過來從最前一個階段順序向后推求解。但逆序求解是動態(tài)規(guī)劃的一個顯著特點。3.動態(tài)規(guī)劃在每一個階段求得自以往各階段至本階段的最佳解，并將此項最佳解帶入次階段。4.動態(tài)規(guī)劃的目標是全局（系統(tǒng)）的最優(yōu)化，而不僅是局部（本階段）的優(yōu)化。5.動態(tài)規(guī)劃與運籌學的其它分支不同，它沒有標準的數(shù)學表達式和解題規(guī)則，但卻是更一般性的解題方法。一個動態(tài)規(guī)劃問題公式的格式在性質(zhì)上和復雜程度上會與其它動態(tài)規(guī)劃問題大不一樣，其差異取決于問題的結構。解題時要有豐富的想象力和創(chuàng)造性技巧?？傊?，應用動態(tài)規(guī)劃可把一個復雜的難以下手的大問題變成一系列較易于各個解決的小問題，然后可以一個一個求解。所以許多問題用動態(tài)規(guī)劃求解，常較運籌學的其它方法更有效果。第4頁,共90頁，2024年2月25日，星期天三、動態(tài)規(guī)劃數(shù)學模型的類型

動態(tài)規(guī)劃分為離散確定性、離散隨機性，連續(xù)確定性、連續(xù)隨機性四種決策類型。本章主要研究離散型動態(tài)規(guī)劃，這也正是動態(tài)規(guī)劃的核心內(nèi)容和特色所在

第5頁,共90頁，2024年2月25日，星期天

8.2動態(tài)規(guī)劃的基本概念與

最優(yōu)化原理

第6頁,共90頁，2024年2月25日，星期天一、多階段決策問題（漫游數(shù)學家問題）

這是一個典型的多階段決策問題，通過這個例子，有助于我們更好的理解動態(tài)規(guī)劃的基本概念和基本思路。例8—1有一個智慧比金錢多的應用數(shù)學家渴望進行一次旅行。假設他住在城市1，而渴望到城市10（見圖8-1表示可能的路線和花費）。這是一個長途的旅行，要求必須進行3次中間停留，中間站可以選擇。他希望為這次旅行付出的花費最小，那么他將選擇那些城市作為自己的中間站？

第7頁,共90頁，2024年2月25日，星期天

0站1站2站3站4站.

圖8-1

684712441526381097413411369553第8頁,共90頁，2024年2月25日，星期天分析：他可以采用枚舉法，列出所有18種可能的路線來解決這個問題。是否有更好的方法？例如：假設我們在城市5，可通過城市8，也可通過城市9到達城市10，很明顯我們會選城市9而不會選城市8。因為（8+3）＜（9+5）,

即（5—9—10）這條路花費較少,由于可按三種不同的路線到達城市5，可以看出枚舉法將做不少不必要的工作。這個相當簡單的觀察為我們提供了一種解題的思路。若我們處在第3站，可通過城市8或9到達城市10可用表8—1說明表8—1

第3站城市Min（f）最佳路徑

8

5

8-------10

9

3

9-------10第9頁,共90頁，2024年2月25日，星期天

現(xiàn)在假定在第2站，并問哪一條路到城市10最近，花費最小。若在城市5，最小花費是11，即Min{9+5,8+3}=11，將選擇路徑（5—9—10）。同理若在城市6最小花費是12，Min{7+5,12+3}=12，將選擇（6—8—10）。城市7最小費用8，Min{----,5+3}=8，將選擇路徑為（7—9—10），結果列于表8—2

表8—2第2站城市Min（f）最佳路徑

5

11

5---9----106

126---8----10

7

87---9----10第10頁,共90頁，2024年2月25日，星期天

現(xiàn)在假定在第1站，用類似方法可知：由城市2到城市10的最小費用為Min{3+11,---,4+8}=12，路徑為（2—5—9—10）。第一站計算結果為表8—3

表8—3

第1站城市Min（f）最佳路徑

2

12

2----7---9----103

143-----7---9----10

4

124----5---9----10第11頁,共90頁，2024年2月25日，星期天最后假定在第0站即城市1也就是起點，那么由城市1到城市10最小花費的路線，應由城市1到第一站的哪個城市呢？由Min{4+12,3+14,11+12}=16可知花費最小的路線為（1—2—7—9—10），第0站計算結果見表8—4表8—4第0站城市Min（f）最佳路徑

1

161—2—7—9—10第12頁,共90頁，2024年2月25日，星期天52638109741341134697125534461812340531112812141216第13頁,共90頁，2024年2月25日，星期天二、動態(tài)規(guī)劃的基本概念

階段和階段變量.

狀態(tài)和狀態(tài)變量.

決策和決策變量.

策略和最優(yōu)策略.

指標函數(shù).

狀態(tài)轉(zhuǎn)移方程.

第14頁,共90頁，2024年2月25日，星期天

1.階段（Stage）和階段變量

把所給問題的過程，按照時間或空間恰當?shù)貏澐譃槿舾蓚€相互聯(lián)系的階段，以便于求解。描述階段的變量稱為階段變量，通常用K表示階段變量。如例8-1可分為4個階段，當K=2時，表示對第2階段求解。第15頁,共90頁，2024年2月25日，星期天2.狀態(tài)（State）和狀態(tài)變量

狀態(tài)表示某階段的初始位置，它既是該段某支路的始點，同時也是前一階段某支路的終點。通常一個階段，包含若干個狀態(tài)。描述過程狀態(tài)的變量，稱為狀態(tài)變量，可用一個數(shù)、一組數(shù)或一個向量表示。用SK表示，如例8—1中，階段2有三個狀態(tài)。則狀態(tài)變量S2可取{２，３，４}，S2=3表示第二階段在狀態(tài)3{城市3}處考慮問題．

第16頁,共90頁，2024年2月25日，星期天3.決策{Deciding}和決策變量

決策就是某階段狀態(tài)給定以后，從該狀態(tài)演變到下一階段某狀態(tài)的選擇。描述決策的變量，稱為決策變量（它是改變狀態(tài)變量的機會，可能以概率方式出現(xiàn)），常用XK(SK)表示第K階段當狀態(tài)為SK時的決策變量，它是狀態(tài)SK的函數(shù)。在實際問題中，決策變量的取值往往限制在某一范圍之內(nèi)，此范圍稱為允許決策集合，通常用DK(SK)表示第K階段的關于SK狀態(tài)的允許決策集合。顯然有XK(SK)∈DK(SK)第17頁,共90頁，2024年2月25日，星期天4．策略（Strategies）和最優(yōu)策略

由過程的第K階段開始到終點為止的過程稱為問題的后部子過程。由后部子過程的每個階段的決策組成的決策函數(shù)序列{XK(SK)，XK+1(SK+1)―――――Xn(Sn)}就稱為子過程的策略，簡稱子策略。并記為：PK..n(SK)={XK(SK)，XK+1(SK+1)..

..

..

Xn(Sn)}

當K=1時，則此決策函數(shù)序列就是全過程的一個策略，簡稱策略，記為P1..n(S1)?？晒┻x擇的策略范圍，稱為允許策略集合用P表示。使問題達到最優(yōu)效果的策略，稱為最優(yōu)策略。例8—1中：{X1(1)=2,X2(2)=7,X3(7)=9,X4(9)=10}就是一個策略，且為最優(yōu)策略。第18頁,共90頁，2024年2月25日，星期天5．指標函數(shù)和最優(yōu)指標函數(shù)值階段指標函數(shù)是用來表示某階段給定狀態(tài)和決策取得效應的一種數(shù)量指標。它是定義在第K階段上的一個數(shù)量函數(shù)。用vK..N表示：

vK..N=vK..N(SK,XK)

過程指標函數(shù)（簡稱指標函數(shù)；又稱目標函數(shù)）是用來衡量所考查過程效應的一種數(shù)量指標。它是定義在從第K階段到終點過程上的一個數(shù)量函數(shù)。用VK..N表示：

VK..N=VK..N(SK,XK.SK+1,XK+1――――SN+1)

(k=1,2――――N)當初始狀態(tài)給定時過程的策略就確定了，因而指標也就確定了，所以指標函數(shù)又是初始狀態(tài)和策略的函數(shù)即：

VK..N=VK..N(SK，PK..N(SK))

第19頁,共90頁，2024年2月25日，星期天5．指標函數(shù)和最優(yōu)指標函數(shù)值指標函數(shù)VK..N的最優(yōu)值，稱為相應的最優(yōu)指標函數(shù)值記為：FK(SK)=optVKN(SK，PK..N(SK))式中opt是optimization(最優(yōu)化)的縮寫，根據(jù)問題不同取Max或Min。在不同問題中指標的涵義不同，可以是距離、費用、收益、產(chǎn)品產(chǎn)量、資源消耗等。從例8—1中：VK..N表示第k階段的點SK到終點城市10的花費。FK(SK)=MinVK,N表示SK到城市10的最小花費。第20頁,共90頁，2024年2月25日，星期天6.狀態(tài)轉(zhuǎn)移方程

狀態(tài)轉(zhuǎn)移方程表示從階段k到階段k+1的狀態(tài)轉(zhuǎn)移規(guī)律的表達式。多級決策過程中，如給定了第K階段的狀態(tài)變量SK和決策變量XK(SK)，則下一階段K+1階段狀態(tài)變量的值也就確定了。即SK+1=TK(SK,XK(SK))上式又稱為狀態(tài)轉(zhuǎn)移函數(shù)。第21頁,共90頁，2024年2月25日，星期天三、動態(tài)規(guī)劃數(shù)學模型的構造條件

1.能夠恰當?shù)貏澐謫栴}的階段，把問題化為多階段決策過程；2.正確地選擇狀態(tài)變量動態(tài)規(guī)劃中的狀態(tài)要能描述受控過程的演變特征：滿足無后效性和可知性。

第22頁,共90頁，2024年2月25日，星期天

無后效性——如果過程某階段的狀態(tài)給定，則在這個階段以后過程的發(fā)展不受前面各個階段的影響，只和當前狀態(tài)及今后的決策有關，過程前面的狀態(tài)和決策只能通過形成的當前狀態(tài)去影響過程未來的發(fā)展，即重要的是當前的狀態(tài)和今后的決策而于過去的狀態(tài)和決策無關。可知性—各階段狀態(tài)變量的值直接或間接均為已知。第23頁,共90頁，2024年2月25日，星期天3.能確定決策變量及各階段的允許決策集合；4.能寫出狀態(tài)轉(zhuǎn)移方程；5.根據(jù)實際問題，列出指標函數(shù)VK,N，要滿足遞推關系。VK,N(SK,XK,SK+1,XK+1,……SN+1)=Ψ[SK,XK,VK+1..N(SK+1,XK+1,……SN+1)]一般是求和或求積的關系。

第24頁,共90頁，2024年2月25日，星期天

四、最優(yōu)化原理和基本方程

1.最優(yōu)化原理最優(yōu)策略具有這樣的性質(zhì)：無論過去狀態(tài)和決策如何，對前面決策所形成的某一狀態(tài)而言，余下的決策序列必須構成最優(yōu)策略。第25頁,共90頁，2024年2月25日，星期天2.動態(tài)規(guī)劃的基本方程利用最優(yōu)化原理，把多階段決策問題的求解過程分解為一個連續(xù)的遞推過程，由后向前逐步推算。求解時，各階段以前的狀態(tài)和決策，對后部子過程來說，只充當其初始條件，并不影響后面過程的最優(yōu)策略。據(jù)此可得出動態(tài)規(guī)劃的遞推關系：為使關系式表達方便,可對問題增加第N+1階段此時有：

FN+1(SN+1)=ee為一常數(shù)FN+1(SN+1)=e又稱為動態(tài)規(guī)劃的邊界條件。

第26頁,共90頁，2024年2月25日，星期天2.動態(tài)規(guī)劃的基本方程

對于任何第K階段（1≤K≤N）當

VK,N=∑vj(Sj,Xj)時則有FK(SK)=opt{vK(SK,XK)+Fk+1(SK+1)}

XK(SK)∈DK(SK)sK∈SK

第27頁,共90頁，2024年2月25日，星期天2.動態(tài)規(guī)劃的基本方程又當

VK,N=

∏vj(Sj，Xj)時則有

Fn+1(Sn+1)≠0

Fk

(Sk)=opt{Vk(Sk,Xk)Fk+1(Sk+1)}

Xk

(Sk)∈Dk(Sk)Sk∈Sk再有狀態(tài)轉(zhuǎn)移函數(shù)

Sk+1=Tk

(Sk,Xk(Sk))

問題就可以求解啦

第28頁,共90頁，2024年2月25日，星期天例8—2：求X1、X2、X3在滿足約束條件：

X1+X2+X3=CXi≧0(i=1,2,3)之下，使函數(shù)F(X1、X2、X3)=X1?X2?X3→MaxK:按變量將問題劃分為3個階段，每個階段只決定X1、X2、X3

其中一個變量的值。SK:表示第K個階段初尚未分配出的數(shù)值，S1=CXK：表示第K個階段分配給的數(shù)值,0≤XK≤SK狀態(tài)轉(zhuǎn)移函數(shù)：Sk+1=SK—XK(K=1、2、3)各個階段效益按乘積組合，所以基本方程為：

FK(SK)=max{XKFk+1(Sk+1)}(K=1,2,3)0≤XK≤SKF4(S4)=1第29頁,共90頁，2024年2月25日，星期天

例8—3某公司有資金1000萬元，擬投資項目有3個，已知對第i個項目投資Xi萬元，凈收益為gi(Xi)，應如何分配資金才能使公司總的凈收益最大？

這個問題與時間無明顯關系，我們可按項目將問題分為三個階段，每個階段只考慮對一個項目的投資額。K=3狀態(tài)變量SK表示第K個階段初未分配資金額。決策變量XK表示第K個階段分配給第K個項目的投資額。狀態(tài)轉(zhuǎn)移函數(shù)為：SK+1=SK-XK

（K=1、2、3）指標函數(shù)基本方程為：

FK(SK)=max{gK(XK)+FK+1(SK+1)}(K=1,2,3)0≤XK≤SK

F4(S4)=0第30頁,共90頁，2024年2月25日，星期天

8.2動態(tài)規(guī)劃的基本概念與最優(yōu)化原理

根據(jù)動態(tài)規(guī)劃的基本思路和最優(yōu)化原理，一般列出其基本方程即可對實際問題進行求解，但有些問題由于結構的不同，其基本方程可能有特殊性，關鍵是要靈活地創(chuàng)造性地應用動態(tài)規(guī)劃的最優(yōu)化原理和思想。第31頁,共90頁，2024年2月25日，星期天8.3動態(tài)規(guī)劃的求解與應用一、動態(tài)規(guī)劃的解法動態(tài)規(guī)劃的求解有兩種基本方法：逆序解法（后向動態(tài)規(guī)劃）、順序解法（前向動態(tài)規(guī)劃）（一）逆序解法逆序解法的尋優(yōu)方向與實際決策過程的行進方向相反，它是從最后一個階段開始逐段向前推進，從而求得全過程的最優(yōu)策略，這種方法更體現(xiàn)動態(tài)規(guī)劃的本質(zhì)和最優(yōu)化原理：不管過去如何，只求未來更優(yōu)。前面我們建立的動態(tài)規(guī)劃模型均是按逆序方法建立的，它也是求解動態(tài)規(guī)劃問題的主要方法。例8—4用動態(tài)規(guī)劃逆序法求解例例8—2解：基本方程為：

FK(SK)=Max{XKFk+1(Sk+1)}(K=1,2,3)0≤XK≤SKF4(S4)=1狀態(tài)轉(zhuǎn)移函數(shù)為：Sk+1=SK—XK(K=1、2、3)第32頁,共90頁，2024年2月25日，星期天8.3動態(tài)規(guī)劃的求解與應用第Ⅲ階段，K=3F3(S3)=Max{X3

·F4(S4)}0≤X3≤S3

=Max{X3

?1}0≤X3≤S3

=S3

X3=S3

第Ⅱ階段，K=2F2(S2)=Max{X2

?F3(S3)}0≤X2≤S2=Max{X2

?S3}0≤X2≤S2=Max{X2

?(X2-S2)}=Max{(S2/2)2-(X2-S2/2)2}=(S2/2)2X2=S2/2第33頁,共90頁，2024年2月25日，星期天8.3動態(tài)規(guī)劃的求解與應用第Ⅰ階段，K=1F1(S1)=Max{X1?F2(S2)}0≤X1≤S1

=Max{X1

?(S2/2)2}=Max{X1

?(S1-X1/2)2}=(S1/3)3X1=S1/3由于初始狀態(tài)S1=C所以：

S1=CX1*=C/3F1(C)=(C/3)3S2=C-X1*=2C/3X2*=C/3F2(S2)=(C/3)2S3=S2-X2*=C/3X3*=S3=C/3F3(S3)=(C/3)所以最優(yōu)策略為：X1*=X2*=X3*=C/3最優(yōu)指標函數(shù)的值為：F1(S1)=F1(C)=(C/3)3第34頁,共90頁，2024年2月25日，星期天8.3動態(tài)規(guī)劃的求解與應用（二）順序解法順序解法的尋優(yōu)方向與實際決策過程的行進方向相同，它是從第一個階段（始點）開始，逐段向后推進，從而求得全過程的最優(yōu)策略。順序解法的階段變量、狀態(tài)變量設置同逆序解法相同，而最優(yōu)指標函數(shù)FK(SK+1)表示第K階段末的結束狀態(tài)為SK+1時，從第一階段到第K階段所得到的最大收益。一般選擇第K階段末（即第K+1階段）的狀態(tài)作為第K階段的狀態(tài)變量狀態(tài)轉(zhuǎn)移方程為：

SK=TK(SK+1,XK)

基本方程為：

FK(SK+1)=opt{VK(SK+1,XK)+FK--1(SK)}

XK(SK+1)∈DK(SK+1)

F0(S1)=0式中FK(SK+1)指第K階段狀態(tài)為SK+1時從始點到第K階段的最優(yōu)指標函數(shù)值；VK(SK+1,XK)表示第Ｋ階段末狀態(tài)為SK+1時，決策變量為XK時本階段的效益值．第35頁,共90頁，2024年2月25日，星期天8.3動態(tài)規(guī)劃的求解與應用

逆序解法和順序解法兩者的解題方向不同，但結果是一致的。在解動態(tài)規(guī)劃問題時，順序解法有時比較困難，甚至有些問題根本無法采用順序解法，而逆序解法在大多數(shù)情況下都比較方便。一般來講，當過程的終點狀態(tài)給定時，可采用順序解法，當過程的起點狀態(tài)和終點狀態(tài)都給定時，則逆序解法和順序解法都會得到最優(yōu)結果，只給定初始狀態(tài)時則無法采用順序解法，因大多數(shù)問題均只有初始狀態(tài)，所以常用逆序解法。求解動態(tài)規(guī)劃問題時，除了我們介紹的數(shù)學解析方法，對離散型問題可能用表格法更合適，下面我們將結合具體應用問題進行介紹。第36頁,共90頁，2024年2月25日，星期天二、動態(tài)規(guī)劃的應用

動態(tài)規(guī)劃的應用范圍很廣，解題的方法也各有不同。下面我們將介紹一些典型應用問題，進一步加深對動態(tài)規(guī)劃的理解和解題技巧的掌握。

（一）資源分配問題（一維資源分配問題）資源分配問題，是指將供應量有限的一種或若干種資源（如原材料、資金、機器、勞力、食品等）分配給若干用戶，而使目標函數(shù)最優(yōu)。設有某種原料總量為M，擬用來進行N種生產(chǎn)活動。若分配數(shù)量為Xi的原料用于第i種生產(chǎn)活動，其收益為gi(Xi)，問應如何分配才能使N種生產(chǎn)活動的總收益最大？這類問題可寫成靜態(tài)規(guī)劃問題：

Max[g1(X1)+g2(X2)+…+gn(Xn)]X1+X2+…+Xn=MXi≧0i=1,2,3,…n第37頁,共90頁，2024年2月25日，星期天（一）資源分配問題（一維資源分配問題）

在用動態(tài)規(guī)劃方法求解此類問題時，一般地將N種活動作為一個互相銜接的整體，由于要確定分給每種活動的資源數(shù)，所以通常把資源分配給一個或幾個使用者的過程劃分為若干個階段，每個階段都要確定分配給某一種活動的資源量，并且首先要對N種活動指定分配的階段序號。由于將階段聯(lián)系在一起的是所有生產(chǎn)活動都在爭取的資源，因此狀態(tài)變量就要按照資源分配來確定。把第K個階段的狀態(tài)變量SK定義為第K階段初所擁有的資源量，即將要在第K種活動到第N種活動之間分配的資源量。這樣我們在確定第K個階段的資源分配時就不需要考慮第K個階段以前的資源分配情況。決策變量XK定義為第K個階段對資源的分配量，即對第K種活動的資源分配量。

第38頁,共90頁，2024年2月25日，星期天（一）資源分配問題（一維資源分配問題）狀態(tài)變量的約束條件是：0≤SK≤M

決策變量的約束條件是：0≤XK≤SK

此時狀態(tài)轉(zhuǎn)移函數(shù)是：SK+1=SK-XK即第K+1階段初的資源擁有量等于第K階段初的資源擁有量與分配量之差。顯然，它滿足無后效性。階段指標函數(shù)為對第K個階段分配資源XK時的收益：

VK(SK,XK)=gK(XK)

目標函數(shù)FK(SK)為從第K個階段到第N個階段按最優(yōu)分配方案分配資源后的最大總收益，則動態(tài)規(guī)劃的基本方程為

FK(SK)=Max{gK(SK)(XK)+FK+1(SK+1)}(K=1,2,3,---,n)0≤XK≤SKFn+1(Sn+1)=0第39頁,共90頁，2024年2月25日，星期天（一）資源分配問題（一維資源分配問題）例8-6某機械公司購置五臺先進設備，需分給所屬的甲，乙，丙三個工廠。各工廠獲得這些設備后，每年為公司提供的盈利（萬元）見表8—5：表8—5單位：萬元

設備數(shù)工廠

012345甲

03791213乙

0510111111丙046111212第40頁,共90頁，2024年2月25日，星期天（一）資源分配問題（一維資源分配問題）問如何分配這些設備才能使公司得到的盈利額最大。此問題當設Xi(i=1,2,3)為分配給第i個工廠的設備數(shù)時，gi(Xi)為第i個工廠的盈利時，可以寫成靜態(tài)規(guī)劃問題:

Max[g1(X1)+g2(X2)+g3(X3)]X1+X2+X3=5Xi≧0i=1,2,3

無法用單純形方法求解，枚舉法比較麻煩。故采用動態(tài)規(guī)劃的方法，特別當工廠和設備數(shù)量增大時，采用動態(tài)規(guī)劃的方法更方便一些。第41頁,共90頁，2024年2月25日，星期天（一）資源分配問題（一維資源分配問題）解：將問題按工廠劃分為三個階段，三個工廠的編號分別記為1，2，3。SK表示分配給第K個工廠到第3個工廠的設備臺數(shù)，XK表示分配給第K個工廠的設備臺數(shù)：

S1=5SK+1=SK-XK

VK(XK)表示XK臺設備分配到第K個工廠得到的盈利值。

FK(SK)表示SK臺設備分配到第K個工廠至第三個工廠所得的最大盈利。因此有遞推關系：

FK(SK)=Max{VK(XK)+FK+1(SK-XK)}(K=1,2,3)0≤XK≤SK(K=1,2,3)F4(S4)=0第42頁,共90頁，2024年2月25日，星期天（一）資源分配問題（一維資源分配問題）現(xiàn)從最后一個階段向前遞推求解：階段ⅢK=3

設把S3臺設備（S3=0，1，2，3，4，5）全部分配給工廠3時，則最大盈利值為：F3(S3)=Max[V3(X3)]X3=0,1,2,3,4,5因為只有一個工廠，給不同臺數(shù)的盈利就是每種情況下的最大盈利。因此最優(yōu)方案是把全部設備放到工廠3去。數(shù)值計算及決策見表8—6

x3s3

V3(x3)+F4(S4)F3(s3)x3*01234500

00104

41204662304611113404611121245046111212125第43頁,共90頁，2024年2月25日，星期天（一）資源分配問題（一維資源分配問題）

階段Ⅱ

K=2

設把S2臺（S2=0，1，2，3，4，5）設備全部分給工廠3、工廠2時，則最大盈利值為：F2(S2)=Max[V2(X2)+F3(S2-X2)]X2=0,1,2,3,4,5

選擇X2數(shù)值使F2(S2)最大決策及計算結果如表6—7：

x2s2

V2(X2)+F3(S2-X2)F2(s2)X2*01234500

0010+45+0

5120+65+410+010230+115+610+411+014240+125+1110+611+411+0161&250+125+1210+1111+611+411+0212第44頁,共90頁，2024年2月25日，星期天（一）資源分配問題（一維資源分配問題）

階段ⅠK=1

設把S1臺設備（S1=5）分配給1，2，3三個工廠，則最大盈利值為：

F1(S1)=Max{V1(X1)+F2(S1-X1)}X1=0,1,2,3,4,5現(xiàn)選取X1的值，使F1(S1)最大，數(shù)值計算見表6—8由表中可知：最優(yōu)方案有二個：

(1)X1=0X2=2X3=3F1(S1)=21(2)X1=2X2=2X3=1F1(S1)=21如資源是連續(xù)的，則解題時首先必須將問題進行離散化處理，如本問題不是5臺設備而是50萬元人民幣，那么我們可以每10萬元為單位進行分割，當然也可以1萬元為單位分割，但計算工作量會大幅度提高，因此分割單位的選擇十分重要

x1s1V1(X1)+F2(S1-X1)F1(s1)X1*01234550+213+167+149+1012+513+0210&2第45頁,共90頁，2024年2月25日，星期天(二)資源分配問題（考慮資源回收的問題）例8-7．某個公司新購某種機床125臺。這種設備5年后將被其它新設備代替，此機床如在高負荷狀態(tài)下工作年損壞率為1/2，每臺年收益為10萬元；如在低負荷下工作年損壞率為1/5，每臺年收益為6萬元。問應如何安排這些機床的生產(chǎn)負荷，才能使5年內(nèi)所獲收益最大？第46頁,共90頁，2024年2月25日，星期天(二)資源分配問題（考慮資源回收的問題）

解：按年度劃分為5個階段，用K表示階段序號。狀態(tài)變量SK

為第K年擁有完好設備的數(shù)量，決策變量XK

為第K年中處于高負荷工作的設備數(shù)量，決策變量(SK—XK)為第K年中處于低負荷工作的設備數(shù)量狀態(tài)轉(zhuǎn)移函數(shù)即第K+1年年初完好的設備臺數(shù):SK+1=SK—1/2XK

—1/5(SK—XK)=4/5SK—3/10XK第K階段允許決策集合為

DK(SK)={XK/0≤XK≤SK}VK(SK,XK)為第K年度的收益則VK=VK(SK,XK)=10XK+6(SK—XK)=6SK+4XK第47頁,共90頁，2024年2月25日，星期天(二)資源分配問題（考慮資源回收的問題）因此基本方程為:FK(SK)=Max{6SK+4XK+FK+1(SK+1)}0≤XK≤SKK=1,2,3,4,5F6(S6)=0下面求解問題：階段ⅤK=5F6(S6)=0有：F5(S5)=Max{4X5+6S5}0≤X5≤S5

因為4X5+6S5隨X5單調(diào)遞增，所以取X5=S5

此時：

X5=S5

F5(S5)=10S5

第48頁,共90頁，2024年2月25日，星期天(二)資源分配問題（考慮資源回收的問題）階段ⅣK=4F4(S4)=Max{4X4+6S4+F5(S5)}0≤X4≤S4=Max{4X4+6S4+10S5}=Max{4X4+6S4+8S4-3X4}=Max{X4+14S4}0≤X4≤S4因為X4+14S4單凋遞增。所以取X4=S4此時

X4=S4

F4(S4)=15S4第49頁,共90頁，2024年2月25日，星期天(二)資源分配問題（考慮資源回收的問題）階段ⅢK=3F3(S3)=Max{4X3+6S3+F4(S4)}=Max{4X3+6S3+15S4}=Max{4X3+6S3+15(0.8S3-0.3X3}=Max{18S3

–(1/2)X3}0≤X3≤S3

由于18S3

–(1/2)X3隨X3單調(diào)遞減所以取X3=0此時：

X3=0F3(S3)=18S3

第50頁,共90頁，2024年2月25日，星期天(二)資源分配問題（考慮資源回收的問題）階段ⅡK=2F2(S2)=Max{4X2+6S2+F3(S3)}=Max{4X2+6S2+18S3}=Max{4X2+6S2+18(0.8S2-0.3X2)}=Max{20.4S2-1.4X2}0≤X2≤S2同理取X2=0此時

X2=0F2(S2)=20.4S2第51頁,共90頁，2024年2月25日，星期天(二)資源分配問題（考慮資源回收的問題）階段ⅠK=1F1(S1)=Max{4X1+6S1+F2(S2)}=Max{4X1+6S1+20.4S2}=Max{4X1+6S1+20.4(0.8S1-0.3X1)}=Max{22.32S1-2.12X1}0≤X1≤S1同理取X1=0此時

X1=0F1(S1)=22.32S1第52頁,共90頁，2024年2月25日，星期天(二)資源分配問題（考慮資源回收的問題）將S1=125代入得:F1(S1)=F1(125)=22.32X125=2790(萬元)

即公司五年內(nèi)可獲得最大收益值為2790萬元，最優(yōu)生產(chǎn)計劃方案為表6—9所示表6—9而且5年結束后，尚有32-(1/2)x32=16臺設備處于完好狀態(tài)。如初始狀態(tài)S1=125加以改變，我們也不需要重新開始計算，借助狀態(tài)轉(zhuǎn)移函數(shù)，我們可以很快得到最佳策略，這也是動態(tài)規(guī)劃問題的一個顯著特點。年份項目12345狀態(tài)S125100806432高負荷X1=0X2=0X3=0X4=64X5=32低負荷1251008000第53頁,共90頁，2024年2月25日，星期天（三）生產(chǎn)與存貯問題例8-8某造船股份有限責任公司根據(jù)合同，從現(xiàn)在起連續(xù)4年每年年未要向客戶提供型號相同的大型遠洋客船，每年的交貨數(shù)及生產(chǎn)每條船的生產(chǎn)費用見表8—10所示。該公司的生產(chǎn)能力設計為每年6條船。每個計劃年度造船公司固定費用為60萬元。若造出的船當年不交貨，則每條船積壓一年的損失為40萬元。假定開始時及第四年年未交貨后均無積壓船只，問公司應如何安排四年的生產(chǎn)計劃，使所支付總費用最經(jīng)濟？年度項目一二三四生產(chǎn)費用（CK)百萬元/條

6.0

6.06.36.5需交付船（dK）條/年度

1

3

2

2第54頁,共90頁，2024年2月25日，星期天（三）生產(chǎn)與存貯問題解：按年度劃分階段，四年分為4個階段，k=1，2，3，4。狀態(tài)變量SK為第K階段初存儲的船只數(shù)量。狀態(tài)變量SK需要滿足以下條件：⑴不能超過本年和以后各年交船數(shù)的總和

0≤SK≤Σdi⑵為保證按時交船，每年年初的存船數(shù)加上本年度的最大可能生產(chǎn)量不得小于本年度的交船數(shù)SK+6≥dK⑶此外，還有S1=S5=0

決策變量XK為第K階段生產(chǎn)的船只數(shù),且XK必須滿足以下條件：⑴某年末所擁有的存船數(shù)，不應超過本年度及以后各年交船數(shù)的總和：

XK+SK≤Σdi⑵某年初所擁有的存船數(shù)加上當年生產(chǎn)船只數(shù)量，不應少于本年度的交船數(shù)

XK+SK≥dK第55頁,共90頁，2024年2月25日，星期天（三）生產(chǎn)與存貯問題

狀態(tài)轉(zhuǎn)移函數(shù)

SK=SK+XK

–dK=1,2,3,4即第K年初的存船數(shù)加上第K年船只的生產(chǎn)數(shù)，再減去第K年交付的船數(shù)，就等于第K+1年初的存船數(shù)。第K階段的指標函數(shù)VK就是第K年度生產(chǎn)費用與存貯費用兩部分之和。

0.6+CKXK+0.4SK

當XK>0VK(SK,XK)K=1,2,3,40.4SK

當XK=0動態(tài)規(guī)劃的基本方程為：

FK(SK)=Min{VK(SK,XK)+Fk+1(Sk+1)}(K=1,2,3,4)0≤XK≤6F5(S5)=0第56頁,共90頁，2024年2月25日，星期天（三）生產(chǎn)與存貯問題階段Ⅳ，K=4，d4=2S4∈{0,1,2}X4∈{2,1,0}0.6+6.5X4+0.4S4

當X4>0V4=0.4S4

當X4=0計算結果見表6—11所示表6—11階段Ⅳ決策表

階段k

期初存船（S4）可能的生產(chǎn)量（X4）本期費用（V4）期末存船（S5

）以后各期費用F5(S5)

總費用V4+F5

最佳生產(chǎn)量（X4）40213.60013.62117.5007.51200.8000.80第57頁,共90頁，2024年2月25日，星期天（三）生產(chǎn)與存貯問題階段Ⅲ，K=3，D3=2，故:S3∈{0,1,2,3,4}0.6+6.3X3+0.4S3

當X3>0V3=0.4S3

當X3=0計算結果如下表6—12

表6—12階段Ⅲ決策表階段k

期初存船（S3）可能的生產(chǎn)量（X3）本期費用（V3）期末存船（S4）以后各期費用F4(S4)

總費用V3+F4最佳生產(chǎn)量（X3）30213.2013.626.84319.517.527425.820.826.61

17.3013.620.9

3

213.617.521.1319.920.8

20.7第58頁,共90頁，2024年2月25日，星期天（三）生產(chǎn)與存貯問題

表6—12(續(xù))階段Ⅲ決策表階段k

期初存船（S3）可能的生產(chǎn)量（X3）本期費用（V3）期末存船（S4）以后各期費用F4(S4)

總費用V3+F4最佳生產(chǎn)量（X3）3200.8013.6

14.4017.717.515.221420.8

14.8301.217.58.7018.120.88.9401.620.8

2.40第59頁,共90頁，2024年2月25日，星期天（三）生產(chǎn)與存貯問題階段Ⅱ，K=2，D2=3，故S2∈{0,1,2,3,4,5}

0.6+6.5X2+0.4S2

當X2>0V2=0.4S2

當X2=0計算結果見表6—13所示表6—13階段Ⅱ決策表

階段k

期初存船（S2）可能的生產(chǎn)量（X2）本期費用（V2）期末存船（S3

）以后各期費用F3(S3)

總費用V2+F3最佳生產(chǎn)量（X2）20

318.6026.645.25424.6120.745.3530.6214.445.0636.638.745.3第60頁,共90頁，2024年2月25日，星期天（三）生產(chǎn)與存貯問題

表6—13(續(xù)1)階段Ⅱ決策表

階段k

期初存船（S2）可能的生產(chǎn)量（X2）本期費用（V2）期末存船（S3

）以后各期費用F3(S3)

總費用V2+F3最佳生產(chǎn)量（X2）21213026.639.64or6

319120.739.7425214.439.453138.739.763742.439.42

17.4026.6343or5

213.4120.734.1319.4214.433.8425.438.734.1531.442.433.8第61頁,共90頁，2024年2月25日，星期天

階段k

期初存船（S2）可能的生產(chǎn)量（X2）本期費用（V2）期末存船（S3

）以后各期費用F3(S3)

總費用V2+F3最佳生產(chǎn)量（X2）2301.2026.627.8017.8120.728.5213.8214.428.2319.838.728.5425.842.428.2401.6120.722.3018.2214.422.6214.238.722.9320.242.422.65

02.0214.416.4018.638.717.3214.642.417.0表6—13(續(xù)2)階段Ⅱ決策第62頁,共90頁，2024年2月25日，星期天（三）生產(chǎn)與存貯問題階段Ⅰ，K=1，D1=1，故S1=0,X1∈{1,2,3,4,5,6}V1=0.6+6.0X1計算結果見表6—14

表6—14階段Ⅰ決策表階段k

期初存船（S1）可能的生產(chǎn)量（X1）本期費用（V1）期末存船（S2）以后各期費用F2(S2)

總費用V1+F2最佳生產(chǎn)量（X1）10

16.60

45.0

51.61212.6139.452.0318.6233.852.4424.6327.852.4530.6422.352.9636.6516.453.0第63頁,共90頁，2024年2月25日，星期天（三）生產(chǎn)與存貯問題

由表6-14知，第1年應該生產(chǎn)1艘船，整個過程的最小費用為F1（0）=51.6百萬元。由遞推關系可得問題的最佳策略，詳見表5—15

公司最佳生產(chǎn)方案

即第1年船廠應該安排生產(chǎn)1艘船，第2年安排生產(chǎn)5艘船，第3年不安排生產(chǎn)，第4年安排生產(chǎn)2艘船，船廠按此策略安排生產(chǎn)計劃才能既滿足客戶要求又能使支出總費用最小，總費用為5160萬元

年度期初存船(Sk）最佳生產(chǎn)量（Xk）期末存船（Sk+1）本期費用VK(SK)

最小總費用min(VK+Fk+1)10106.651.6205230.645.032000.814.4402013.613.6第64頁,共90頁，2024年2月25日，星期天（四）背包問題背包問題又稱裝載問題，如汽車，火車，輪船，飛機，宇宙飛船等工具的裝載問題，還可用于機械加工中零部件的最優(yōu)加工，下料等問題，具有廣泛的實用價值。典型的背包問題是講有一位登山運動員，它的背包的載重量不能超過a千克，現(xiàn)有n種物品可供選擇裝入背包，第i種物品的單位重量是ai千克，第i種物品的價值是攜帶數(shù)量Xi的函數(shù)Ci(Xi)(i=1,2,---,n)，那么運動員應如何選擇各種物品的數(shù)量，而使總價值最大？

第65頁,共90頁，2024年2月25日，星期天（四）背包問題例8-9，某公司有三種貨物需要裝飛機運輸，各種貨物的重量和可能獲得的收益見表8—16。飛機允許裝載能力為6噸，問應如何裝載才能使公司獲得最大收益？表8—16解：按貨物種類劃分階段：K=1表示裝載第1種貨物；K=2表示裝載第2種貨物；K=3表示裝載第3種貨物。狀態(tài)變量SK表示第K階段可以利用的裝載能力。

S1=6SK={0，1，2，3，4，5，6}K=2，3貨物種類（i）貨物重量（Wi）噸收益（Vi）(千克)12802313034180第66頁,共90頁，2024年2月25日，星期天（四）背包問題決策變量XK為第K種貨物的裝載數(shù)量。允許決策集合：XK∈DK(SK)={0,1,2,---,[SK/aK]}K=1,2,3

狀態(tài)轉(zhuǎn)移函數(shù)：SK+1=SK—WKXK階段指標函數(shù)為：VKXK動態(tài)規(guī)劃基本方程：

FK(SK)=Max{VKXK+FK+1(SK+1)}(K=3,2,1)XK∈DK(SK)F4(S4)=0第67頁,共90頁，2024年2月25日，星期天（四）背包問題階段ⅢK=3W3=4,V3=180,S3∈{0,1,2….,6}因為X3∈{0,1,…,[S3/4]}={0,1}所以：F3(S3)=Max{180X3+0}X3∈(0,1)S3∈{0,1,2,…,6}計算結果如下表8—17階段

X3S3180X3F3(S3)

X3*S401300

00010

00120

00230

00340180+01801050180+01801160180+018012第68頁,共