運籌學動態(tài)規(guī)劃課件

運籌學運籌帷幄之中決勝千里之外動態(tài)規(guī)劃DynamicProgramming第五章2精選課件第五章動態(tài)規(guī)劃重點：理解動態(tài)規(guī)劃基本概念、最優(yōu)化原理和基本方程；通過資源分配、生產(chǎn)與存儲和設(shè)備更新等問題，學習應(yīng)用動態(tài)規(guī)劃解決多階段決策問題；重點掌握動態(tài)規(guī)劃模型結(jié)構(gòu)、逆序算法原理、資源分配問題、生產(chǎn)與存儲問題。難點為動態(tài)規(guī)劃中狀態(tài)變量、基本方程等的確定。3精選課件概述1951年Bellman提出，1957《動態(tài)規(guī)劃》動態(tài)規(guī)劃是解決多階段決策問題的一種數(shù)學方法。動態(tài)規(guī)劃思想：把多階段決策問題變換為一系列互相聯(lián)系的單階段問題，然后逐個加以解決。即：把一個n維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決。需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。必須對具體問題進行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動態(tài)規(guī)劃求解方法去求解。應(yīng)用：最短路線、資源分配、生產(chǎn)調(diào)度問題4精選課件主要內(nèi)容一、多階段決策問題二、動態(tài)規(guī)劃的基本概念三、動態(tài)規(guī)劃的基本思想四、動態(tài)規(guī)劃遞推求解方法五、動態(tài)規(guī)劃的最優(yōu)性原理六、動態(tài)規(guī)劃的優(yōu)缺點七、動態(tài)規(guī)劃問題應(yīng)用舉例5精選課件AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456引例：圖中所示為從A到G的路線網(wǎng)絡(luò)，圖中數(shù)字表示相應(yīng)線路的長度，如何求出從A到G的最短路線？（窮舉法48條路線）6精選課件AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221233355266312345637597681310912131618447精選課件AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876683533842212333552663123456151313151113136810953181648精選課件AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456最短路的特性：

如果已有從起點到終點的一條最短路，那么從最短路線上中間任何一點出發(fā)到終點的路線仍然是最短路。（證明用反證法）9精選課件§1動態(tài)規(guī)劃的研究對象和引例動態(tài)系統(tǒng)：包含隨時間變化的因素和變量的系統(tǒng)。動態(tài)決策問題：

系統(tǒng)所處的狀態(tài)和時刻是進行決策的重要因素。

找到不同時刻的最優(yōu)決策以及整個過程的最優(yōu)策略。12n狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策全過程的最優(yōu)階段10精選課件

1、生產(chǎn)決策問題

企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計劃。多階段決策問題的典型例子11精選課件

2、機器負荷分配問題某種機器高負荷低負荷g=g(u1)產(chǎn)品的年產(chǎn)量投入生產(chǎn)的機器數(shù)量機器的年完好率為a，0<a<1h=h(u2)機器的年完好率為b，0<b<1年終完好的機器？

假定開始生產(chǎn)時完好的機器數(shù)量為s1。要求制定一個n年計劃，在每年開始時，決定如何重新分配完好的機器在兩種不同的負荷下生產(chǎn)的數(shù)量，使在n年內(nèi)產(chǎn)品的總產(chǎn)量達到最高。12精選課件3、線性規(guī)劃、非線性規(guī)劃等靜態(tài)的規(guī)劃問題也可以通過適當?shù)匾腚A段的概念，應(yīng)用動態(tài)規(guī)劃方法加以解決。

不包含時間因素的靜態(tài)決策問題（一次決策問題）也可以適當?shù)匾腚A段的概念，作為多階段的決策問題用動態(tài)規(guī)劃方法來解決。4、最短路問題（引例）：給定一個交通網(wǎng)絡(luò)圖如前，其中兩點之間的數(shù)字表示距離（或花費），試求從A點到G點的最短距離（總費用最?。?。13精選課件AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456§2動態(tài)規(guī)劃的基本概念和定義1、階段、階段變量

把所給問題的過程，適當（按時間和空間）地分為若干個相互聯(lián)系的階段；描述階段的變量稱為階段變量，常用k表示。14精選課件2、狀態(tài)、狀態(tài)變量

每個階段開始所處的自然狀態(tài)或客觀條件，描述過程的狀況，通常一個階段有若干個狀態(tài)。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456

描述過程狀態(tài)的變量稱為狀態(tài)變量，它可用一個數(shù)、一組數(shù)或一向量來描述，常用sk表示第k階段的狀態(tài)。s2=?狀態(tài)允許集合，狀態(tài)變量的取值允許集合或范圍。15精選課件

在最優(yōu)控制中也稱為控制。3、決策、決策變量

某一階段、某個狀態(tài)，可以做出不同的決定（選擇），決定下一階段的狀態(tài)，這種決定稱為決策。453136876683533822123335526643AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G123456決策變量，描述決策的變量。uk(sk)，表示第k階段當狀態(tài)為sk時的決策變量。

允許決策集合，常用Dk(sk)

表示第k

階段從狀態(tài)sk出發(fā)的允許決策集合。uk(sk)Dk(sk)D2(B1)?16精選課件AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456系統(tǒng)當前的狀態(tài)和決策4、多階段決策過程在每個階段進行決策控制過程的發(fā)展；其發(fā)展是通過一系列的狀態(tài)轉(zhuǎn)移來實現(xiàn)的；系統(tǒng)過去的歷史狀態(tài)和決策B1C1s2=T1(s1,u1)s3=T2(s1,u1,s2,u2)sk+1=Tk(s1,u1,s2,u2,,sk,uk)狀態(tài)轉(zhuǎn)移方程的一般形式s2=B1,u2=C1,s3=?17精選課件12ks1u1s2u2s3skuksk+1

能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性的多階段決策過程。圖示如下：5、無后效性或馬爾可夫性

如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以前各階段狀態(tài)的影響；過程的過去歷史只能通過當前的狀態(tài)去影響它未來的發(fā)展。18精選課件

構(gòu)造動態(tài)規(guī)劃模型時，要充分注意狀態(tài)變量是否滿足無后效性的要求；狀態(tài)轉(zhuǎn)移方程？

狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)移方程如下：s2=T1(s1,u1)s3=T2(s2,u2)sk+1=Tk(sk,uk)19精選課件AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456

由每段的決策按順序排列組成的決策函數(shù)序列稱為

k子過程策略。簡稱子策略，記為pk,n(sk)，即，Pk,n(sk)={uk(sk),uk+1(sk+1),

,un(sn)}C1D1E1F1G6、策略按順序排列的決策組成的集合。

由過程的第k

終止狀態(tài)為止的過程，稱為問題的后部子過程（k

子過程）。20精選課件AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456允許策略集合，可供選擇的策略范圍，用P表示。最優(yōu)策略，達到最優(yōu)效果的策略。

當k=1時，此決策函數(shù)序列成為全過程的一個策略，簡稱策略，記為p1,n

(s1)，即P1,n(s1)={u1(s1),u2(s2),…,un(sn)}AB1C1D1E1F1G21精選課件7、指標函數(shù)和最優(yōu)值函數(shù)

指標函數(shù)，用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標，它是定義在全過程或所有后部子過程上確定的數(shù)量函數(shù)。用Vk,n

表示。Vk,n=Vk,n

(sk,uk,

sk+1,

uk+1,

,

sn+1),k=1,2,,nAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456

動態(tài)規(guī)劃模型的指標函數(shù)，應(yīng)具有可分離性，并滿足遞推關(guān)系。即Vk,n可以表示為sk,uk,Vk+1,n的函數(shù)。22精選課件常見的指標函數(shù)的形式是：

過程和它的任一子過程的指標是它所包含的各階段的指標和。即無后效性的結(jié)果

其中V(sj,uj

)

表示第j階段的階段指標。這時上式可寫成Vk,n(sk,uk,…,sn+1)=vk(sk,uk)+Vk+1,nV5,6=V5,6

(s5,u5,

V6,6

)=v5(s5,u5)+V6,6

AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G45313687668353382212333552664312345623精選課件過程和它的任意子過程的指標是它所包含的各階段的指標的乘積。即可改寫成Vk,n(sk,uk,…,sn+1)=vk(sk,uk)Vk+1,n(sk+1,uk+1,…,sn+1)

指標函數(shù)的最優(yōu)值，記為fk(sk)。表示從第k階段的狀態(tài)

sk到第n

階段的終止狀態(tài)的采取最優(yōu)策略所得到的指標函數(shù)值。即最優(yōu)值函數(shù)：24精選課件AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456f6(s6)=？f6(F1)=4f6(F2)=3f5(E1)=？全過程的最優(yōu)值函數(shù)記為f1(s1)25精選課件多階段決策過程的數(shù)學模型：（具有無后效性，以和式為例）opt{u1,u2,…,un}sk+1=Tk(sk,uk)skSkukDkk=1,2,…,ns.t.26精選課件小結(jié):方程:狀態(tài)轉(zhuǎn)移方程概念:階段變量

k﹑狀態(tài)變量

sk﹑決策變量

uk;動態(tài)規(guī)劃本質(zhì)上是多階段決策過程;

效益指標函數(shù)形式:和、積無后效性可遞推指標:Vk,n=Vk,n

(sk,uk,

sk+1,

uk+1,

,

sn+1)

fk(sk)=optVk,n(sk,uk,…,sn+1){uk,…,un}=k[sk,uk,Vk+1,n

(sk+1,

uk+1,

,

sn+1)]27精選課件最優(yōu)策略：最優(yōu)目標函數(shù)值：{u1*

,u2*

,…,un*}{s1*

,s2*

,…,sn*}即最優(yōu)決策序列即執(zhí)行最優(yōu)策略時的狀態(tài)序列解多階段決策過程問題，應(yīng)求出：f1(s1)=?最優(yōu)軌線：28精選課件§3動態(tài)規(guī)劃的基本思想和基本方程（窮舉法48條路線）AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456最短路的特性：

如果已有從起點到終點的一條最短路，那么從最短路線上中間任何一點出發(fā)到終點的路線仍然是最短路。（證明用反證法）29精選課件k=5，出發(fā)點有E1,E2,E3u5(E1)=F1E1F1Gu5(E2)=F2E2F2Gk=6，

F1

G，f6(F1)=4F2

G，f6(F2)=3u5(E3)=F2E3F2GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G45313687668353382212333552664330精選課件k=3

f3(C1)=13u3(C1)=D1

f3(C2)=10u3(C2)=D1f3(C3)=9u3(C3)=D2f3(C4)=12u3(C4)=D3k=2f2(B1)=13u2(B1)=C2

f2(B2)=10u2(B2)=C3k=4

f4(D1)=7u4(D1)=E2

f4(D2)=6u4(D2)=E2f4(D3)=8u4(D3)=E2AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G4531368766835338221233355266435+133+16=mink=1f1(A)

=18

=mind1(A,B1)+f2(B1)d1(A,B2)+f2(B2)u1(A)=B131精選課件最優(yōu)決策函數(shù)序列｛uk｝：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643最優(yōu)策略最短路線為

AB1C2D1E2F2Gu1(A)=B1,u2(B1)=C2,u3(C2)=D1,u4(D1)=E2,u5(E2)=F2,u6(F2)=G32精選課件動態(tài)規(guī)劃基本方程fk(sk)=opt{vk(sk,uk(sk))+fk+1(sk+1)}ukDk(sk)fn+1

(sn+1)=0（邊界條件）

求解的各個階段，我們利用了k階段與k+1階段之間的遞推關(guān)系:f7(s7)=0fk(sk)=min{dk(sk,uk(sk))+fk+1(sk+1

)}

ukDk(sk)k=6,5,4,3,2,133精選課件最優(yōu)性原理(R.Bellman)：“一個過程的最優(yōu)策略具有這樣的性質(zhì)：即無論其初始狀態(tài)及初始決策如何，對于先前決策所形成的狀態(tài)而言，余下的諸決策仍構(gòu)成最優(yōu)策略?！?/p>

最優(yōu)策略的任何一部分子策略，也是它相應(yīng)初始狀態(tài)的最優(yōu)策略。每個最優(yōu)策略只能由最優(yōu)子策略構(gòu)成。含義動態(tài)規(guī)劃的理論基礎(chǔ)34精選課件動態(tài)規(guī)劃的最優(yōu)性定理：設(shè)階段數(shù)為

n的多階段決策過程，其階段編號為k=0,1,...,n-1。允許策略p*0,n-1=(u*0,u*1,…,u*n-1)是最優(yōu)策略的充要條件是:

對任意一個

k,0

<

k<

n-1和

s0S0，有35精選課件證明：必要性充分性：設(shè)p0,n-1=(p0,k-1,pk,n-1)為任一策略，sk為由（s0，p0,k-1）所確定的k階段的起始狀態(tài)，則有（以最大化為例）36精選課件37精選課件

推論：若允許策略p*0,n-1是最優(yōu)策略，則對任意的k，0<k<n-1，它的子策略p*k,n-1對于以s*k=Tk-1(s*k-1,u*k-1)為起點的k到n-1子過程來說，必是最優(yōu)策略。（注意：k段狀態(tài)s*k，是由s0和p*0,k-1所確定的）最優(yōu)性原理38精選課件動態(tài)規(guī)劃（逆序法）小結(jié):將問題的過程劃分成恰當?shù)碾A段；選擇狀態(tài)變量sk,既能描述過程的變化又滿足無后效性；確定決策變量

uk及每一階段的允許決策集合Dk(

sk)；正確寫出狀態(tài)轉(zhuǎn)移方程；正確寫出指標函數(shù)

Vk,n的關(guān)系，它應(yīng)滿足下面三個性質(zhì)：1.是定義在全過程和所有后部子過程上的數(shù)量函數(shù);2.要具有可分離性，并滿足遞推關(guān)系。即

Vk,n

(sk,uk,

,

sn+1)=

k[sk,uk,Vk+1,n

(sk+1,

uk+1,

,

sn+1)]39精選課件3.函數(shù)k（sk，uk，Vk+1,n）對于變量Vk+1,n要嚴格單調(diào)。求解時從邊界條件開始，逆（或順）過程行進方向，逐段遞推尋優(yōu)。每段決策的選取都是從全局考慮的，與該段的最優(yōu)選擇答案一般是不同的。在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的,每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐次變換得到，從而確定了最優(yōu)路線。40精選課件解：可列出靜態(tài)規(guī)劃問題的模型如下例1某公司有資金10萬元，若投資于項目i（i=1,2,3）的投資額為xi時，其效益分別為問如何分配投資數(shù)額才能使總效益最大?§4動態(tài)規(guī)劃與靜態(tài)規(guī)劃41精選課件

分階段：每一階段可使用的資金數(shù)為狀態(tài)變量sk。

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

確定決策變量：

確定狀態(tài)變量：分三個階段，即k=3，2，1。

通常可以取靜態(tài)規(guī)劃中的變量為決策變量。42精選課件

指標函數(shù)

基本方程當階段k=3時，有最優(yōu)決策為最優(yōu)目標函數(shù)43精選課件當階段k=2時，有最優(yōu)決策為最優(yōu)目標函數(shù)當階段k=1時，有是凸函數(shù)，最大值點只能在[0,s1]的端點上取得，即2階導(dǎo)數(shù)>0（最優(yōu)決策）44精選課件所以

最優(yōu)投資方案是全部資金投于第3個項目，可得最大收益200萬元。例2

求解下面問題：(考慮用動態(tài)規(guī)劃的逆序法進行求解。)解題思路？45精選課件解：1、將該問題劃分為三個階段，即k=1，2，32、確定狀態(tài)變量并可得狀態(tài)轉(zhuǎn)移方程：3、指標函數(shù)46精選課件

4、基本方程最優(yōu)值函數(shù)當階段k=3時，有最優(yōu)決策當階段k=2時，有得最優(yōu)決策最優(yōu)目標函數(shù)47精選課件因此最后可得：當階段k=1時，有最優(yōu)決策最優(yōu)目標函數(shù)48精選課件動態(tài)規(guī)劃的優(yōu)缺點優(yōu)點:

最優(yōu)解是全局最優(yōu)解。能得到一系列（包括子過程）的最優(yōu)解。不需要對系統(tǒng)狀態(tài)轉(zhuǎn)移方程、階段效應(yīng)函數(shù)等的解析性質(zhì)作任何假設(shè)。缺點：沒有統(tǒng)一的標準模型和標準的算法可供使用。應(yīng)用的局限性，要求滿足“無后效性”?！熬S數(shù)災(zāi)難”問題。49精選課件

設(shè)有某種原料，總數(shù)量為a，用于生產(chǎn)n種產(chǎn)品。若分配數(shù)量xi

用于生產(chǎn)第i種產(chǎn)品，其收益為gi(xi)，問應(yīng)如何分配，才能使生產(chǎn)n種產(chǎn)品的總收入最大？§5

資源分配問題5.1資源平行分配問題MaxZ=g1(x1)+g2(x2)++gn(xn)

s.t.

x1+x2+

+

xn=axi0i=1,2,

,n靜態(tài)規(guī)劃模型50精選課件

例3

某公司擬將5臺某種設(shè)備分配給所屬的甲、乙、丙三個工廠，各工廠若獲得這種設(shè)備，可以為公司提供的盈利如表。問：這五臺設(shè)備如何分配給各工廠，才能使公司得到的盈利最大。046111212051011111103791213012345丙乙甲工廠盈利設(shè)備臺數(shù)

51精選課件甲乙丙012345037912130510111111046111212如何劃分階段s1的可達狀態(tài)集合s2的可達狀態(tài)集合s3的可達狀態(tài)集合決策變量uk(sk)0sk3個階段xk狀態(tài)轉(zhuǎn)移方程？52精選課件甲乙丙012345037912130510111111046111212s1s2s3321x1x2x3基本方程?指標函數(shù)gk(xk)?s453精選課件解：將問題按工廠分為三個階段，甲、乙、丙分別編號為1，2，3。決策變量xk::

分配給生產(chǎn)第k

個工廠的設(shè)備數(shù)量

分配給第k個工廠至第3

個工廠的設(shè)備數(shù)量。狀態(tài)變量sk:甲乙丙01234503791213051011111104611121254精選課件Dk(sk)={uk|0xksk}基本方程：數(shù)量為sk的原料分配給第k個工廠至第3個工廠所得到的最大總收益狀態(tài)轉(zhuǎn)移方程:sk+1=sk-

xkxk的取值范圍？甲乙丙01234503791213051011111104611121255精選課件x3*(0)

=0x3*(1)

=1x3*(2)

=2x3*(3)

=3k=3，s3=0,1,2,3,4,5，0x3s3s3=0s3=3甲乙丙012345037912130510111111046111212046111212s3=2s3=156精選課件甲乙丙012345037912130510111111046111212x3*(5)

=4,5x3*(4)

=4046111212x3s3g3(x3)f3(s3)x*3012345012345046111212046111212012344,5結(jié)果可寫成表格的形式:s3=4s3=557精選課件甲乙丙012345037912130510111111046111212

k=2，s3=s2-x2，s2=0,1,2,3,4,5，0x2s2，有x2*(0)

=0s2=0x3s3g3(x3)f3(s3)x*3012345012345046111212046111212012344,558精選課件x2*(1)

=1s2=1甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*3012345012345046111212046111212012344,559精選課件x2*(2)

=2s2=2甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*3012345012345046111212046111212012344,560精選課件x2*(3)

=2甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*3012345012345046111212046111212012344,5s2=361精選課件甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*3012345012345046111212046111212012344,5x2*(4)

=1,2s2=462精選課件s2=5甲乙丙012345037912130510111111046111212x3s3g3(x3)f3(s3)x*3012345012345046111212046111212012344,5x2*(5)

=263精選課件結(jié)果列于下表：x2s2g2(x2)+f3(s2-x2)f2(s2)x*20123450123450+00+40+60+110+120+125+05+45+65+115+1210+010+410+610+1111+011+411+611+011+411+0051014162101221,22k=1時，s2=s1-x1，

s1=5，0x1s1，有64精選課件x2s2f2(s2)x*2012345051014162101221,22x1*(5)

=0,2甲乙丙01234503791213051011111104611121265精選課件結(jié)果可寫成表格的形式x1s1g1(x1)+f2(s1-x1)f1(s1)x*101234550+213+167+149+1012+513+0210,2最優(yōu)分配方案一：由x1*=0，根據(jù)s2=s1-x1*=5-0=5，查表知x2*=2，由s3=s2-x2*=5-2=3，故x3*=s3=3。即得甲工廠分配0臺，乙工廠分配2臺，丙工廠分配3臺。最優(yōu)分配方案？66精選課件

最優(yōu)分配方案二：由x1*=2，根據(jù)s2=s1-x1*=5-2=3，查表知x2*=2，由s3=s2-x2*=3-2=1，故x3*=s3=1。即得甲工廠分配2臺，乙工廠分配2臺，丙工廠分配1臺。以上兩個分配方案所得到的總盈利均為21萬元。問題：如果原設(shè)備臺數(shù)是4臺，求最優(yōu)分配方案？如果原設(shè)備臺數(shù)是3臺，求最優(yōu)分配方案？67精選課件5.2資源連續(xù)分配問題A種生產(chǎn)數(shù)量u1投入收益g(u1)

年終資源回收率a

B種生產(chǎn)數(shù)量s1-u1收益h(s1-u1)年終資源回收率b資源數(shù)量s1第一年資源數(shù)量s2=au1+b(s1-u1)第二年

A種生產(chǎn)數(shù)量u2投入;收益g(u2);年終資源回收率aB種生產(chǎn)數(shù)量s2-u2;收益h(s2-u2);年終資源回收率b到n年68精選課件

如此進行n年，如何確定投入A的資源量u1、…、un，使總收入最大？此問題的靜態(tài)規(guī)劃問題模型為：69精選課件高負荷:產(chǎn)量函數(shù)g=8u，年完好率為a=0.7，機器例4機器負荷分配問題假定開始生產(chǎn)時完好機器的數(shù)量為1000臺。

低負荷:產(chǎn)量函數(shù)h=5y，年完好率為b=0.9。

試問每年如何安排機器在高低兩種負荷下的生產(chǎn)，可使5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高?投入生產(chǎn)的機器數(shù)量70精選課件

狀態(tài)變量sk狀態(tài)轉(zhuǎn)移方程決策變量uk第k年初擁有的完好機器臺數(shù)第k年高負荷下投入的機器數(shù)sk+1=auk+b(sk-

uk)=0.7uk+0.9(sk-uk)0uksk分析：第k年低負荷下投入的機器數(shù)sk–uk階段？71精選課件遞推方程？指標函數(shù)第k年度產(chǎn)量為fk(sk)=max{8uk+5(sk-uk)+fk+1(0.7uk+0.9(sk-uk))}0ukskk=5,4,3,2,1sk+1階段指標f6(s6)=072精選課件則狀態(tài)轉(zhuǎn)移方程為sk+1=0.7uk+0.9(sk-uk)k=1,2,…,5解：設(shè)階段序數(shù)k表示年度，sk為第k年初擁有的完好機器臺數(shù)，第k年度高負荷下投入的機器數(shù)為uk臺。fk(sk)=max{8uk+5(sk-uk)+fk+1(0.7uk+0.9(sk-uk))}0ukskk=5,4,3,2,1f6(s6)=0

基本方程為73精選課件f4(s4)=13.6s4u*4=s4k=4u*5=s5k=5f5(s5)=8s5074精選課件依次類推可得，因此最優(yōu)策略為最高產(chǎn)量為23700。練習：1.每年年初的完好機器數(shù)。

2.如規(guī)定在第五年結(jié)束時完好機器數(shù)為500臺，該如何安排生產(chǎn)？75精選課件k=4k=5其他略76精選課件§6

生產(chǎn)與存貯問題

生產(chǎn)周期分為n個階段，已知最初庫存量：x1

階段市場的需求：dk

生產(chǎn)的固定成本：K單位產(chǎn)品的消耗費用：L

單位產(chǎn)品的階段庫存費用：h倉庫容量：M

階段生產(chǎn)能力為B

一個生產(chǎn)部門，如何在已知生產(chǎn)成本、庫存費用和各階段市場需求條件下，決定各階段產(chǎn)量，使計劃內(nèi)的費用總和為最小的問題。

問如何安排各階段產(chǎn)量，使計劃周期內(nèi)的費用總和最小。77精選課件不能超過階段k至階段n的需求總量xkdk+dk+1++dn，k=1,2,,n階段k的初始庫存量，x1已知，xn+1=00xkmin{M，dk+dk+1++dn}，（k=1,2,,n）狀態(tài)變量xk：不能超過庫存容量M，78精選課件決策變量uk：不超過生產(chǎn)能力階段k的產(chǎn)量ukdk+dk+1++dn-xk不小于該階段的需求和庫存量之差，

不超過kn階段的總需求減去第k階段初的庫存量，dk-xk

ukmin{B，dk+dk+1++dn-xk}79精選課件

狀態(tài)轉(zhuǎn)移方程為階段生產(chǎn)費用和庫存費用之和，即階段k的生產(chǎn)費用k階段末的庫存費用動態(tài)規(guī)劃基本方程階段效益fn+1（xn+1）=0，k=1,2,,ny=0or180精選課件例5

已知n=3，K=8，L=2，h=2，x1=1，M=4，x4=0，B=6，d1=3，d2=4，d3=3，求解生產(chǎn)與庫存問題。解：遞推方程f4(x4)=0，k=1,2,3y=0,1當時=8+2(3-x3)=14-2x3倉庫容量4dk-xk

ukmin{B，dk+dk+1++dn-xk}81精選課件若x3=0,

u*3(0)=3則f3(0)=14若x3=1,則f3(1)=12u*3(1)=2若x3=2,則f3(2)=10u*3(2)=1

若x3=3,則f3(3)=0

u*3(0)=0f3(x3)=14-2x3u3=3-x3x3：0～382精選課件k=2容量44+3ukdk-xk4-x2

u2min{6,7-x2}

f2(x2)=min{8y+2u2+2(x2+u2-4)+f3(x2+u2-4)}4-x2

u2min{B，d2+d3-x2}=min{6,7-x2}0

x2min{M，d2+d3}=min{4,7}=483精選課件u*2(0)=4x2=04-x2

u2min{6,7-x2}

x2=1u*2(1)=684精選課件x2=2u*2(2)=54-x2

u2min{6,7-x2}

x2=3u*2(3)=485精選課件x2=4u*2(4)=04-x2

u2min{6,7-x2}

結(jié)果見下表：86精選課件k=1f2=302u16x2=x1+u1-d1=1+u1-3=u1-2u*1(1)=2x1=1u*1(1)=6u*1(1)=387精選課件f3=1488精選課件最優(yōu)決策(1)為{1，0，0，0}x2=u1-2=0x3=x2+u2-d2=0+4-4=0最優(yōu)路線為最優(yōu)目標函數(shù)值為42。（狀態(tài)變量）u*1(1)=2，u*2(0)=4，u*3(0)=389精選課件最優(yōu)決策(2)為：{1，1，3，0}x2=u1-2=0x3=x2+u2-d2=1+6-4=3最優(yōu)路線為最優(yōu)目標函數(shù)值為42。（狀態(tài)變量）u*1(1)=3，u*2(0)=6，u*3(0)=090精選課