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

會計學1第6章動態(tài)規(guī)劃

動態(tài)規(guī)劃所謂多階段決策問題是指這樣的決策問題:其過程可分為若干個相互聯(lián)的階段，每一階段都對應著一組可供選擇的決策，每一決策的選定即依賴于當前面臨的狀態(tài)，又影響以后總體的效果。當每一階段的決策選定以后，就構成一個決策序列，稱為一個策略，它對應著一個確定的效果。多階段決策問題就是尋找使此效果最好的策略。狀態(tài)

x1階段1T1決策u1狀態(tài)

x2決策u2階段2T2狀態(tài)

x3...狀態(tài)

xk決策uk階段kTk狀態(tài)

xk+1...狀態(tài)

xn決策un階段nTn狀態(tài)

xn+1第1頁/共55頁多階段決策問題工廠生產過程:由于市場需求是一隨著時間而變化的因素，因此，為了取得全年最佳經濟效益，就要在全年的生產過程中，逐月或者逐季度地根據庫存和需求情況決定生產計劃安排。設備更新問題:一般企業(yè)用于生產活動的設備，剛買來時故障少，經濟效益高，即使進行轉讓，處理價值也高，隨著使用年限的增加，就會逐漸變?yōu)楣收隙?，維修費用增加，可正常使用的工時減少，加工質量下降，經濟效益差，并且，使用的年限越長、處理價值也越低，自然，如果賣去舊的買新的，還需要付出更新費．因此就需要綜合權衡決定設備的使用年限，使總的經濟效益最好。第2頁/共55頁多階段決策問題連續(xù)生產過程的控制問題:一般化工生產過程中，常包含一系列完成生產過程的設備，前一工序設備的輸出則是后一工序設備的輸入，因此應該如何根據各工序的運行工況，控制生產過程中各設備的輸入和輸出，以使總產量最大。資源分配問題:資源分配問題屬于靜態(tài)問題。如某工業(yè)部門或公司，擬對其所屬企業(yè)進行稀缺資源分配，為此需要制定出收益最大的資源分配方案。這種問題原本要求一次確定出對各企業(yè)的資源分配量，它與時間因素無關，不屬動態(tài)決策，但是，我們可以人為地規(guī)定一個資源分配的階段和順序，從而使其變成一個多階段決策問題。第3頁/共55頁動態(tài)規(guī)劃求解的特點通常多階段決策過程的發(fā)展是通過狀態(tài)的一系列變換來實現(xiàn)的。一般情況下，系統(tǒng)在某個階段的狀態(tài)轉移除與本階段的狀態(tài)和決策有關外，還可能與系統(tǒng)過去經歷的狀態(tài)和決策有關。適合于用動態(tài)規(guī)劃方法求解的只是一類特殊的多階段決策問題，即具有“無后效性”的多階段決策過程。無后效性(又稱馬爾柯夫性)是指系統(tǒng)從某個階段往后的發(fā)展，僅由本階段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經歷的狀態(tài)和決策(歷史)無關。第4頁/共55頁A

動態(tài)規(guī)劃問題實例C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643例6-1給定一個線路網絡，要從A向F鋪設一條輸油管，各點間連線上的數字表示距離，問應選擇什么路線，可使總距離最短？第5頁/共55頁A

動態(tài)規(guī)劃C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643第6頁/共55頁1.階段與階段變量為了便于求解和表示決策及過程的發(fā)展順序，而把所給問題恰當地劃分為若干個相互聯(lián)系又有區(qū)別的子問題，稱為多段決策問題的階段。描述階段的變量稱為階段變量，常用k表示。階段的劃分，一般是根據時間和空間的自然特征來進行的，但要便于問題轉化為多階段決策。

動態(tài)規(guī)劃的基本概念第7頁/共55頁

動態(tài)規(guī)劃的基本概念2.狀態(tài)、狀態(tài)變量與可能狀態(tài)集描述事物(或系統(tǒng))在某特定的時間與空間域中所處位置及運動特征的量，稱為狀態(tài)。反映狀態(tài)變化的量叫做狀態(tài)變量。狀態(tài)變量包含在給定的階段上確定全部允許決策所需要的信息。每個階段的狀態(tài)可分為初始狀態(tài)和終止狀態(tài)，或稱輸入狀態(tài)和輸出狀態(tài)，階段k的初始狀態(tài)記作sk，終止狀態(tài)記為sk+1。通常定義階段的狀態(tài)即指其初始狀態(tài)。一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集，或可達狀態(tài)集?？赡軤顟B(tài)集實際上是關于狀態(tài)的約束條件。通?？赡軤顟B(tài)集用相應階段狀態(tài)sk的大寫字母Sk表示，sk∈Sk，。第8頁/共55頁A

動態(tài)規(guī)劃問題實例C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643第1階段第2階段第3階段第4階段第5階段狀態(tài)1狀態(tài)2狀態(tài)3狀態(tài)4狀態(tài)5狀態(tài)6第6階段狀態(tài)7第9頁/共55頁

動態(tài)規(guī)劃的基本概念3.決策當一階段的狀態(tài)確定后，可以作出不同的選擇從而演變到下一階段的某個狀態(tài)，這種選擇手段稱為決策。在最優(yōu)控制問題中也稱為控制。描述決策的變量，稱為決策變量。決策變量的允許取值的范圍稱為允許決策集合。決策變量是狀態(tài)變量的函數。用uk(sk)表示第K階段處于狀態(tài)sk時的決策變量；Dk(sk)表示sk的允許決策集合。第10頁/共55頁A

動態(tài)規(guī)劃問題實例C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643第1階段第2階段第3階段第4階段第5階段狀態(tài)1狀態(tài)2狀態(tài)3狀態(tài)4狀態(tài)5狀態(tài)6第6階段狀態(tài)7u2(B2)=C2D2(B2)={C2,C3,C4}第11頁/共55頁

動態(tài)規(guī)劃的基本概念4.策略一個按順序排列的決策組成的集合。由過程的第K階段開始到終止階段為止的過程稱為問題的后部子過程。由每段的決策按順序排列組成的決策函數序列{uk(sk),…,un(sn)}稱為K子過程策略，簡稱子策略，記為pk,n(sk)。當K=1時，此決策函數序列稱為全過程的一個策略，簡稱策略，記為p1,n(s1)，即:

p1,n(s1)={u1(s1),u2(s2),…,un(sn)}第12頁/共55頁A

動態(tài)規(guī)劃問題實例C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643狀態(tài)1狀態(tài)2狀態(tài)3狀態(tài)4狀態(tài)5狀態(tài)6狀態(tài)7p3,6(C2)={u3(C2),u4(D2),u5(E3),u6(F1)}p1,6(A)={u1(A),u2(B1),u3(C2),u4(D2),u5(E3),u6(F1)}第13頁/共55頁

動態(tài)規(guī)劃的基本概念5.狀態(tài)轉移方程確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。若給定第K階段的狀態(tài)變量sk的值，如果該階段的決策變量uk一經確定，第K+1階段的狀態(tài)變量sk+1的值也就完全確定。即sk+1的值隨sk和uk的值變化而變化。這種確定的對應關系記為:sk+1=Tk(sk,uk(sk))工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態(tài)s2狀態(tài)變量sk

:可用于第k,k+1,…n個工廠的投資額。決策變量xk

:第k

階段對第k

個工廠的投資額。狀態(tài)轉移方程:sk+1

=sk

-xks1=600狀態(tài)s3狀態(tài)s4狀態(tài)s5s2=s1-x1s3=s2-x2s4=s3-x3第14頁/共55頁

動態(tài)規(guī)劃的基本概念6.指標函數和最優(yōu)值函數用來衡量策略或子策略或決策的效果的某種數量指標，就稱為指標函數。它是定義在全過程或各子過程或各階段上的確定數量函數。對不同問題，指標函數可以是諸如費用、成本、產值、利潤、產量、耗量、距離、時間、效用等等。

1)階段指標函數(階段效應)用gk(sk,uk)表示第k段處于sk狀態(tài)且所作決策為uk(sk)時的指標，則它就是第k段指標函數，簡記為gk。第15頁/共55頁

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

(2)過程指標函數(目標函數)用Vk(sk,uk)表示第k子過程的指標函數指標函數，不僅跟當前狀態(tài)sk有關，還跟該子過程策略pk(sk)有關，因此它是sk和pk(sk)的函數，嚴格說來，應表示為:Vk(sk,

pk(sk))，實際應用中上式可表示為:Vk(sk,

uk)或Vk(sk)。過程指標函數Vk(sk,uk)通常是描述所實現(xiàn)的全過程或k

后部子過程效果優(yōu)劣的數量指標，它是由各階段的階段指標函數gk(sk,uk)累積形成的。第16頁/共55頁

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

適于用動態(tài)規(guī)劃求解的問題的過程指標函數(即目標函數)，必須具有關于階段指標的可分離形式．對于k部子過程的指標函數可以表示為:

Vk,n=Vk,n(sk,uk,sk+1,uk+1,…

,sn,un)=gk(sk,uk)⊙gk+1(sk+1,uk+1)⊙…⊙gn(sn,un)多階段決策問題中，常見的目標函數形式之一是取各階段效應之和的形式，即:

?==nkiiuisigkV),(有些問題，如系統(tǒng)可靠性問題，其目標函數是取各階段效應的連乘積形式，如:

?==nkiiiikusgV),(第17頁/共55頁

動態(tài)規(guī)劃的基本概念指標函數的最優(yōu)值稱為最優(yōu)值函數，記為fk(sk)。它表示從第K階段的狀態(tài)開始到第n階段的終止狀態(tài)的過程，采取最優(yōu)策略所得到的指標函數值。),,,()(1,},,{+=nkknkuukksusVoptsfnkLL

相應的子策略稱為sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk)；而構成該子策賂的各段決策稱為該過程上的最優(yōu)決策，記為:uk*(sk),uk+1*(sk+1),…,un*(sn)。

特別當k=1且s1取值唯一時，f1(s1)就是問題的最優(yōu)值，而p1*就是最優(yōu)策略。但若取值不唯一,則問題的最優(yōu)值記為f0有:)()}({11111011*?*===ssfsfoptfSs第18頁/共55頁

動態(tài)規(guī)劃的基本概念7.多階段決策問題的數學模型綜上所述，適于應用動態(tài)規(guī)劃方法求解的一類多階段決策問題，亦即具有無后效性的多階段決策問題的數學模型呈以下形式:?????íì=??===+nkUuSsusTsstusususVVoptfkkkkkkkknnuun,,2,1),(),,,,,,(12211~1LL第19頁/共55頁A

最短路徑問題C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643例6-2:用動態(tài)規(guī)劃求解最短路徑。第20頁/共55頁將問題分成五個階段，第k階段到達的具體地點用狀態(tài)變量sk表示，例如:s2=B2表示第二階段到達位置B2。這里狀態(tài)變量取字符值而不是數值。將決策定義為到達下一站所選擇的路徑，例如目前的狀態(tài)是s2=B2，這時決策允許集合包含三個決策，它們是D2(s2)=D2(B2)={B2→C2，B2

→C3，B2→C4}。最優(yōu)指標函數fk(xk)表示從目前狀態(tài)到E的最短路徑。終端條件為:f7(s7)=f7(G)=0其含義是從G到G的最短路徑為0。遞推方程為: )}(),({)(11)(++?+=kkkkksDukksfusVMinsfkkk

最短路徑問題第21頁/共55頁貝爾曼最優(yōu)化原理作為一個全過程的最優(yōu)策略具有這樣的性質:對于最優(yōu)策略過程中的任意狀態(tài)而言，無論其過去的狀態(tài)和決策如何，余下的諸決策必構成一個最優(yōu)子策略。該原理的具體解釋是，若某一全過程最優(yōu)策略為:p1*(s1)={u1*(s1),u2*(s2),…,un*(sn)}則對上述策略中所隱含的任一狀態(tài)而言，第k子過程上對應于該狀態(tài)的最優(yōu)策略必然包含在上述全過程最優(yōu)策略p1*中，即為:pk*(sk)={uk*(sk),uk+1*(sk+1),…,un*(sn)}第22頁/共55頁貝爾曼最優(yōu)化原理基于貝爾曼最優(yōu)化原理，提出了一種逆序遞推法；該法的關鍵在于給出一種遞推關系。一般把這種遞推關系稱為動態(tài)規(guī)劃的函數基本方程。對于求最小的加法的計算公式為:?????íì-=+==++?++1,2,,1,)},())(,({min)(0)(11)(11LnnksfsusgsfsfkkkkkksUukknnkkk第23頁/共55頁貝爾曼最優(yōu)化原理(1)當過程指標函數為“和”的形式時，相應的函數基本方程為:?????íì-=+==++?++1,2,,1,)},())(,({)(0)(1111LnnksfsusgoptsfsfkkkkkkUukknnkk(2)當過程指標函數為“和”的形式時，相應的函數基本方程為:?????íì-=·==++?++12111111,,,n,nk)}s(f))s(u,s(g{opt)s(f)s(fkkkkkkUukknnkkL第24頁/共55頁動態(tài)規(guī)劃方法的基本步驟用函數基本方程逆推求解是常用的方法:首先要有效地建立動態(tài)規(guī)劃模型,然后再遞推求解,最后得出結論。正確地建立一個動態(tài)規(guī)劃模型,是解決問題的關鍵。正確的動態(tài)規(guī)劃模型,應該滿足下列條件:1.應將實際問題恰當地分割成n個子問題(n個階段)通常是根據時間或空間而劃分的，或者在經由靜態(tài)的數學規(guī)劃模型轉換為動態(tài)規(guī)劃模型時，常取靜態(tài)規(guī)劃中變量的個數n。第25頁/共55頁動態(tài)規(guī)劃方法的基本步驟2.正確地定義狀態(tài)變量sk，使它既能正確地描述過程的狀態(tài)，又能滿足無后效性。要能夠正確地描述受控過程的變化特征。要滿足無后效性。即如果在某個階段狀態(tài)已經給定，那么在該階段以后，過程的發(fā)展不受前面各段狀態(tài)的影響，如果所選的變量不具備無后效性，就不能作為狀態(tài)變量來構造動態(tài)規(guī)劃的模型。要滿足可知性。即所規(guī)定的各段狀態(tài)變量的值，可以直接或間接地測算得到。一般在動態(tài)規(guī)劃模型中，狀態(tài)變量大都選取那種可以進行累計的量。在解靜態(tài)規(guī)劃模型時，線性與非線性規(guī)劃中約束條件的個數，相當于動態(tài)規(guī)劃中狀態(tài)變量sk的維數．約束條件所表示的內容，就是狀態(tài)變量sk所代表的內容。第26頁/共55頁動態(tài)規(guī)劃方法的基本步驟3.正確地定義決策變量及各階段的允許決策集合Uk(sk)一般將問題中待求的量，選作動態(tài)規(guī)劃模型中的決策變量，或者在把靜態(tài)規(guī)劃模型(如線性與非線性規(guī)劃)轉換為動態(tài)規(guī)劃模型時，常常取前者的變量xj為后者的決策變量uk。4.正確地寫出狀態(tài)轉移方程要能正確反映狀態(tài)轉移規(guī)律。如果給定第k階段狀態(tài)變量sk的值，則該段的決策變量uk一經確定，第k+1段的狀態(tài)變量sk+1的值也就完全確定，即有:

sk+1=Tk(sk,uk)第27頁/共55頁動態(tài)規(guī)劃方法的基本步驟5.正確地寫出目標函數。要滿足可分性，即對于所有k后部子過程，其目標函數僅取決于狀態(tài)sk及其以后的決策:uk,uk+1,…,un。即它是定義在全過程和所有后部子過程上的數量函數。要滿足遞推關系。即:Vk,n(sk,uk,sk+1,uk+1,…

,sn+1)=ψk[sk,uk,

Vk+1(sk+1,…

,sn+1)]函數嚴格單調。即:

ψk[sk,uk,Vk+1(sk+1,…

,sn+1)]對變元Rk+1來說要嚴格單調。第28頁/共55頁動態(tài)規(guī)劃方法的基本步驟動態(tài)規(guī)劃的四大要素狀態(tài)變量及其可能集合sk∈Sk決策變量及其允許集合uk∈Uk

狀態(tài)轉移方程sk+1=Tk(sk,uk)階段效應Vk(sk,uk)動態(tài)規(guī)劃基本方程?????íì-=+==++?++1,2,,1,)},())(,({)(0)(1111LnnksfsusgoptsfsfkkkkkkUukknnkk第29頁/共55頁逆推解法設已知初始狀態(tài)為s1,并假定最優(yōu)值函數fk(sk)表示第k階段的初始狀態(tài)為sk，從k階段到n階段所得到的最大效益。從第n階段開始，則有:),(max)()(nnnsDxnnxsvsfnnn?=解該問題，得到最優(yōu)解xn=xn(sn)和最優(yōu)值fn(sn)。在第n階段，有)](),([max)(111)(1111nnnnnsDxnnsfxsvsfnnn*=---?----在第k階段，有)](),([max)(11)(1++?*=kkkkksDxkksfxsvsfkkk如此類推，直到第一階段有)](),([max)(22111)(11111sfxsvsfsDx*=?由于初始狀態(tài)s1已知,故x1=x1(s1)和f1

(s1)是確定的，從而s2=T1(s1,x1)也就可以確定，于是x2=x2(s2)和f2(s2)也可確定。按照上述遞推過程相反的順序推算，就可逐步確定每階段的決策和效益。第30頁/共55頁逆推解法例6-3:用逆推法求解下面問題。0,,max32132132213=++=xxxcxxxxxxz按照變量個數劃分階段，該問題是一個三階段決策問題。狀態(tài)變量為s1,s2,s3,且s1=c決策變量即為問題中的變量x1,x2,x3各階段指標函數按乘積方式最優(yōu)值函數fk(sk)表示從第k階段初始狀態(tài)sk

到第3階段所得最大值。設s1=c，

s2+x1=s1,s3+x2=s2,s3=x3則有x3=s3，0≤x2≤s2，0≤x1≤s1第31頁/共55頁順推解法設已知終止狀態(tài)為sn+1,并假定最優(yōu)值函數fk(sk)表示第k階段末的結束狀態(tài)為sk，從1階段到k

n階段所得到的最大效益。從第1階段開始，則有:),(max)()(111sDx11xsvsf111?=解該問題，得到最優(yōu)解x1=x1

(s2)和最優(yōu)值f1(s2)。在第n階段，有)](),([max)()(1nn-1nnnsDxnnsfxsvsfnnn*=?+由于終止狀態(tài)sn+1已知,故xn=xn(sn+1)和最優(yōu)值fn

(sn+1)是確定的，按照上述遞推過程相反的順序推算，就可逐步確定每階段的決策和效益。得到最優(yōu)解xn=xn(sn+1)和最優(yōu)值fn

(sn+1)。第32頁/共55頁例6-4:用順推法求解下面問題。0,,max32132132213=++=xxxcxxxxxxz最優(yōu)值函數fk(sk+1)表示從第k階段末的結束狀態(tài)sk+1，從第1階段到k階段所得最大值。設

s2=x1,s3+x2=s3,s3+x3=s4=c則有x1=s2，0≤x2≤s3，0≤x3≤s4順推解法第33頁/共55頁資源分配問題(離散型)例6-5:設有6萬元資金用于4個工廠的擴建，已知每個工廠的利潤增長額同投資額的大小有關，見下表。問應如何確定對這四個工廠的投資額，使總利潤增長額最大？投資額(j)工廠(i)0100200300400500600

10204260758590

20254557657073

30183961789095

40284765748085表1利潤增長額gi(xj)單位:百元第34頁/共55頁資源分配問題(離散型)解:把對四個工廠的投資依次看成4個階段的決策過程，確定對第k個工廠的投資額看成第k個階段的決策，k=1,2,3,4。工廠1工廠2工廠3工廠4投資x1投資x2投資x3投資x4狀態(tài)s2狀態(tài)變量sk

:可用于第k,k+1,…n個工廠的投資額。決策變量xk

:第k

階段對第k

個工廠的投資額。允許決策集Dk:{100,200,

…,sk}狀態(tài)轉移方程:sk+1

=sk

-xk，

s1=600階段指標函數gk

:第k階段投資xk元時所產生的利潤。最優(yōu)指標函數fk

(sk):第k階段狀態(tài)為sk且采取最佳投資策略，從第k

個工廠以及以后的最大總利潤。s1=600狀態(tài)s3狀態(tài)s4狀態(tài)s5s2=s1-x1s3=s2-x2s4=s3-x3?íì=+=++￡￡0)()()({max)(55110sfsfsgsfkkkksxkkkk第35頁/共55頁資源分配問題(離散型)投資額(j)工廠(i)010020030040050060030284765748085k=4時，第4個工廠投資時，還有資金s4，若投資于第4個工廠的資金為x4，則最大利潤為:)}({max)}()({max)(44055440444444xgsfxgsfsxsx￡￡￡￡=+=x4

g4(x4)s4f4(s4)x4*01002003004005006000000028100281000284720047200028476530065300028476574400744000284765748050080500028476574808560085600第36頁/共55頁資源分配問題(離散型)投資額(j)工廠(i)010020030040050060030183961789095k=3時，第3個工廠投資時，還有資金s3，若投資于第3個工廠的資金為x3，則最大利潤為:x3

g3+f4s3f3(s3)x3*01002003004005006000+00000+2818+01002800+4718+2839+02004700+6518+4739+2861+0300652000+7418+6539+4761+2878+0400893000+8018+7439+6561+4778+2890+05001083000+8518+8039+7461+6578+4790+2895+0600126300)}()({max)}()({max)(33433044330334433xsfxgsfxgsfsxsx-+=+=￡￡￡￡第37頁/共55頁資源分配問題(離散型)投資額(j)工廠(i)01002003004005006002f3(s3)0254557657073028476789108126k=2時，第2個工廠投資時，還有資金s2，若投資于第2個工廠的資金為x2，則最大利潤為:x2

g2+f3s2f2(s2)x2*01002003004005006000+00000+2825+01002800+4725+2845+0200531000+6725+4745+2857+0300732000+8925+6745+4757+2865+040092100,2000+10825+8945+6757+4765+2870+05001141000+12625+10845+8957+6765+4770+2873+0600134200)}()({max)}()({max)(22322033220222222xsfxgsfxgsfsxsx-+=+=￡￡￡￡第38頁/共55頁資源分配問題(離散型)投資額(j)工廠(i)01002003004005006001f2(s2)0204260758590028537392114134k=1時，s1=600，若投資于第1個工廠的資金為x1，則最大利潤為:x1

g1+f2s1f3(s3)x1*01002003004005006000+13420+11442+9260+7375+5385+2890+06001340,100,200)}()({max)}()({max)600()(1121160002211600011111xsfxgsfxgfsfxx-+=+==￡￡￡￡此時對應最大值134的有三個值，所對應的最優(yōu)策略分別為x1*=0,100,200，再由狀態(tài)轉移方程可得到其它最優(yōu)策略:x1*=0,x2*=200,x3*=300,x4*=100,x1*=100,x2*=100,x3*=300,x4*=100x1*=200,x2*=100,x3*=200,x4*=100,x1*=200,x2*=200,x3*=0,x4*=200第39頁/共55頁背包問題設有n種物品，每一種物品數量無限。第i種物品每件重量為wi，每件價值ci?，F(xiàn)有一只可裝載重量為W的背包，求各種物品應各取多少件放入背包，使背包中物品的價值最高。這個問題可以用整數規(guī)劃模型來描述。設第i種物品取xi件(i=1,2,…,n，xi為非負整數)，背包中物品的價值為z，則則Max

z=c1x1+c2x2+…+cnxn

w1x1+w2x2+…+wnxn≤W

x1,x2,…,xn為正整數第40頁/共55頁階段k:第k次裝載第k種物品(k=1,2,…,n)狀態(tài)變量sk:第k次裝載時背包還可以裝載的重量決策變量xk:第k次裝載第k種物品的件數決策允許集合: Dk(sk)={xk|0≤xk≤

sk/wk，xk為整數}；狀態(tài)轉移方程:sk+1=sk-wkxk階段指標:vk=ckxk遞推方程fk(sk)=max{ckxk+fk+1(sk+1)}=max{ckxk+fk+1(sk-wkxk)}終端條件:fn+1(sn+1)=0背包問題第41頁/共55頁例6-6:已知c1=65,c2=80,c3=30,w1=2,w2=3,w3=1,W=5,f4(x4)=0背包問題k=3時:k=2時:k=2時:)}30{max)}({max)(3/04433/033333333xsfxcsfwsxwsx￡￡￡￡=+=)}3(80{max)}({max)(2232/03322/022222222xsfxsfxcsfwsxwsx-+=+=￡￡￡￡)}2(65{max)}({max)(1121/02211/011111111xsfxsfxcsfwsxwsx-+=+=￡￡￡￡應取第一種物品2件,第三種物品1件,最高價值為160元,背包沒有余量。由f1(x1)得列表可以看出，如果背包得容量為W=4，W=3，W=2和W=1時，相應的最優(yōu)解立即可以得到。第42頁/共55頁設有某種資源總數量為s1,可投入用于生產A、B產品。第一年若以數量u1投入生產A，剩下的s1-u1就投入生產B，則可得到收入為g(u1)+h(s1-u1),其中g(u1)和h(u1)為已知函數，且g(0)+h(0)=0,這種資源在投入A、B產品生產后，年終還可回收再投入生產。設年回收率分別為0<a<1和0<b<1，則在第一年生產后，回收的資源量合計為s2=au1+bh(s1-u1)。第二年再將資源數量s2中的u2和s2-u2分別投入A、B產品生產，則又可得到收入為g(u2)+h(s2-u2)。如此進行n年，試問應當如何決定每年投入A生產的資源量u1,u2,…,un,才能使總的收入最大？資源分配問題(連續(xù)型)第43頁/共55頁MaxZ=g(u1)+h(s1-u1)+g(u2)+h(s2-u2)+…+g(un)+h(sn-un)s2=au1+bh(s1-u1)s3=au2+bh(s2-u2)……sn+1=aun+bh(sn-un)0≤ui≤si+1，i=1，2，…，n狀態(tài)變量sk:第k階段可投入A、B兩種生產的資源量決策變量uk:第k階段可投入A生產的資源量，則sk-uk投入B生產的資源量狀態(tài)轉移方程:sk+1=auk+b(sk-uk)資源分配問題(連續(xù)型)???íì-+=-++-+=￡￡+￡￡)}()({max)()]}([)()({max)(010nnnsunnkkkkkkksukkushugsfusbaufushugsfnnkk第44頁/共55頁例6-7:某公司有500輛運輸卡車，在超負荷運輸(即每天滿載行駛500km以上)情況下，年利潤為25萬元/輛，這時卡車的年損壞率為0.3；在低負荷下運輸(即每天行駛300km以下)情況下，年利潤為16萬元/輛。年損壞率為0.1?，F(xiàn)要制定一個5年計劃，問每年年初應如何分配在兩種不同的負荷下完好車輛運輸的卡車數量，使5年內的總利潤最大？狀態(tài)變量sk:第k年初完好卡車數量，其中s1=500決策變量xk:第k年初分配給超負荷運輸的卡車數量，則分配給低負荷的卡車數為sk-uk狀態(tài)轉移方程:sk+1=(1-0.3)xk

+(1-0.1)(sk-xk)=0.9sk

-0.2xk階段指標函數gk(xk):表示第k年度利潤,即

gk(xk)=25xk+16(sk-xk)=16sk+9xk設備負荷分配問題第45頁/共55頁最優(yōu)指標函數fk(sk):第k年度初完好車輛數為sk時，采用最優(yōu)策略到第5年末所產生的最大利潤。

設備負荷分配問題{}?íì==+=++￡￡0)(1,2,3,4,5)()(max)(66110sfksfxgsfkkkksxkkkk第一年初:500輛車全部用于低負荷運輸。第二年初:還有450輛完好的車，也全部用于低負荷運輸。第三年初:還有405輛完好的車，全部用于超負荷運輸。第四年初:還有238.5輛完好的車，全部用于超負荷運輸。第五年初:還有198.45輛完好的車，全部用于超負荷運輸。到第五年末，即第六年初，還剩余138.15輛完好的車。實現(xiàn)最大利潤約3.74億元。第46頁/共55頁課堂思考:某公司有1000輛運輸卡車，在超負荷運輸(即每天滿載行駛500km以上)情況下，年利潤為25萬元/輛，這時卡車的年損壞率為0.3；在低負荷下運輸(即每天行駛300km以下)情況下，年利潤為16萬元/輛。年損壞率為0.1?，F(xiàn)要制定一個5年計劃，問每年年初應如何分配在兩種不同的負荷下完好車輛運輸的卡車數量，使在第5年年末剩余的完好卡車數量為500臺，并且使在5年內的總利潤最大？設備負荷分配問題第47頁/共55頁例6-8:某工廠要對一種產品制定今后四個時期的生產計劃，據估計在今后四個時期內，市場對于該產品的數量如下表所示。該廠生產每批產品的固定成本為3千元，若不生產為0；每單位產品成本為1千元；每個時期生產能力所允許的最大生產批量為不超過6個單位；每個時期末未售出的產品，每單位需支付存儲費用0.5千元。假定在第一個時期的庫存為0，第四個時期庫存量為0。該廠應如何安排各個時期的生產與庫存，才能在滿足市場需要的條件下，成本最??？時期1234需求量2324生產計劃問題第48頁/共55頁狀態(tài)變量sk

:第k階段結束時的產品庫存量。決策變量xk

:xk為第k階段該產品的生產量。狀態(tài)轉移方程:設dk為第k階段對產品的需求量，則

sk

=sk-1

+xk-dkck(xk)表示第k階段生產產品xk時的成本費用。h