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

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

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

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

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

動態(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)和終止?fàn)顟B(tài)，或稱輸入狀態(tài)和輸出狀態(tài)，階段k的初始狀態(tài)記作sk，終止?fàn)顟B(tài)記為sk+1。通常定義階段的狀態(tài)即指其初始狀態(tài)。一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集，或可達狀態(tài)集?？赡軤顟B(tài)集實際上是關(guān)于狀態(tài)的約束條件。通?？赡軤顟B(tài)集用相應(yīng)階段狀態(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.決策當(dāng)一階段的狀態(tài)確定后，可以作出不同的選擇從而演變到下一階段的某個狀態(tài)，這種選擇手段稱為決策。在最優(yōu)控制問題中也稱為控制。描述決策的變量，稱為決策變量。決策變量的允許取值的范圍稱為允許決策集合。決策變量是狀態(tài)變量的函數(shù)。用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階段開始到終止階段為止的過程稱為問題的后部子過程。由每段的決策按順序排列組成的決策函數(shù)序列{uk(sk),…,un(sn)}稱為K子過程策略，簡稱子策略，記為pk,n(sk)。當(dāng)K=1時，此決策函數(shù)序列稱為全過程的一個策略，簡稱策略，記為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)轉(zhuǎn)移方程確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。若給定第K階段的狀態(tài)變量sk的值，如果該階段的決策變量uk一經(jīng)確定，第K+1階段的狀態(tài)變量sk+1的值也就完全確定。即sk+1的值隨sk和uk的值變化而變化。這種確定的對應(yīng)關(guān)系記為: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)轉(zhuǎn)移方程: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.指標(biāo)函數(shù)和最優(yōu)值函數(shù)用來衡量策略或子策略或決策的效果的某種數(shù)量指標(biāo)，就稱為指標(biāo)函數(shù)。它是定義在全過程或各子過程或各階段上的確定數(shù)量函數(shù)。對不同問題，指標(biāo)函數(shù)可以是諸如費用、成本、產(chǎn)值、利潤、產(chǎn)量、耗量、距離、時間、效用等等。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

動態(tài)規(guī)劃的基本概念7.多階段決策問題的數(shù)學(xué)模型綜上所述，適于應(yīng)用動態(tài)規(guī)劃方法求解的一類多階段決策問題，亦即具有無后效性的多階段決策問題的數(shù)學(xué)模型呈以下形式:?????íì=??===+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)變量取字符值而不是數(shù)值。將決策定義為到達下一站所選擇的路徑，例如目前的狀態(tài)是s2=B2，這時決策允許集合包含三個決策，它們是D2(s2)=D2(B2)={B2→C2，B2

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

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

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

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

Vk+1(sk+1,…

,sn+1)]函數(shù)嚴(yán)格單調(diào)。即:

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

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

狀態(tài)轉(zhuǎn)移方程sk+1=Tk(sk,uk)階段效應(yīng)Vk(sk,uk)動態(tài)規(guī)劃基本方程?????íì-=+==++?++1,2,,1,)},())(,({)(0)(1111LnnksfsusgoptsfsfkkkkkkUukknnkk第29頁/共55頁逆推解法設(shè)已知初始狀態(tài)為s1,并假定最優(yōu)值函數(shù)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按照變量個數(shù)劃分階段，該問題是一個三階段決策問題。狀態(tài)變量為s1,s2,s3,且s1=c決策變量即為問題中的變量x1,x2,x3各階段指標(biāo)函數(shù)按乘積方式最優(yōu)值函數(shù)fk(sk)表示從第k階段初始狀態(tài)sk

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

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

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

(s2)和最優(yōu)值f1(s2)。在第n階段，有)](),([max)()(1nn-1nnnsDxnnsfxsvsfnnn*=?+由于終止?fàn)顟B(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)值函數(shù)fk(sk+1)表示從第k階段末的結(jié)束狀態(tài)sk+1，從第1階段到k階段所得最大值。設(shè)

s2=x1,s3+x2=s3,s3+x3=s4=c則有x1=s2，0≤x2≤s3，0≤x3≤s4順推解法第33頁/共55頁資源分配問題(離散型)例6-5:設(shè)有6萬元資金用于4個工廠的擴建，已知每個工廠的利潤增長額同投資額的大小有關(guān)，見下表。問應(yīng)如何確定對這四個工廠的投資額，使總利潤增長額最大？投資額(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)轉(zhuǎn)移方程:sk+1

=sk

-xk，

s1=600階段指標(biāo)函數(shù)gk

:第k階段投資xk元時所產(chǎn)生的利潤。最優(yōu)指標(biāo)函數(shù)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-+=+==￡￡￡￡此時對應(yīng)最大值134的有三個值，所對應(yīng)的最優(yōu)策略分別為x1*=0,100,200，再由狀態(tài)轉(zhuǎn)移方程可得到其它最優(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頁背包問題設(shè)有n種物品，每一種物品數(shù)量無限。第i種物品每件重量為wi，每件價值ci。現(xiàn)有一只可裝載重量為W的背包，求各種物品應(yīng)各取多少件放入背包，使背包中物品的價值最高。這個問題可以用整數(shù)規(guī)劃模型來描述。設(shè)第i種物品取xi件(i=1,2,…,n，xi為非負(fù)整數(shù))，背包中物品的價值為z，則則Max

z=c1x1+c2x2+…+cnxn

w1x1+w2x2+…+wnxn≤W

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

sk/wk，xk為整數(shù)}；狀態(tài)轉(zhuǎn)移方程:sk+1=sk-wkxk階段指標(biāo):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-+=+=￡￡￡￡應(yīng)取第一種物品2件,第三種物品1件,最高價值為160元,背包沒有余量。由f1(x1)得列表可以看出，如果背包得容量為W=4，W=3，W=2和W=1時，相應(yīng)的最優(yōu)解立即可以得到。第42頁/共55頁設(shè)有某種資源總數(shù)量為s1,可投入用于生產(chǎn)A、B產(chǎn)品。第一年若以數(shù)量u1投入生產(chǎn)A，剩下的s1-u1就投入生產(chǎn)B，則可得到收入為g(u1)+h(s1-u1),其中g(shù)(u1)和h(u1)為已知函數(shù)，且g(0)+h(0)=0,這種資源在投入A、B產(chǎn)品生產(chǎn)后，年終還可回收再投入生產(chǎn)。設(shè)年回收率分別為0<a<1和0<b<1，則在第一年生產(chǎn)后，回收的資源量合計為s2=au1+bh(s1-u1)。第二年再將資源數(shù)量s2中的u2和s2-u2分別投入A、B產(chǎn)品生產(chǎn)，則又可得到收入為g(u2)+h(s2-u2)。如此進行n年，試問應(yīng)當(dāng)如何決定每年投入A生產(chǎn)的資源量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兩種生產(chǎn)的資源量決策變量uk:第k階段可投入A生產(chǎn)的資源量，則sk-uk投入B生產(chǎn)的資源量狀態(tài)轉(zhuǎn)移方程:sk+1=auk+b(sk-uk)資源分配問題(連續(xù)型)???íì-+=-++-+=￡￡+￡￡)}()({max)()]}([)()({max)(010nnnsunnkkkkkkksukkushugsfusbaufushugsfnnkk第44頁/共55頁例6-7:某公司有500輛運輸卡車，在超負(fù)荷運輸(即每天滿載行駛500km以上)情況下，年利潤為25萬元/輛，這時卡車的年損壞率為0.3；在低負(fù)荷下運輸(即每天行駛300km以下)情況下，年利潤為16萬元/輛。年損壞率為0.1。現(xiàn)要制定一個5年計劃，問每年年初應(yīng)如何分配在兩種不同的負(fù)荷下完好車輛運輸?shù)目ㄜ嚁?shù)量，使5年內(nèi)的總利潤最大？狀態(tài)變量sk:第k年初完好卡車數(shù)量，其中s1=500決策變量xk:第k年初分配給超負(fù)荷運輸?shù)目ㄜ嚁?shù)量，則分配給低負(fù)荷的卡車數(shù)為sk-uk狀態(tài)轉(zhuǎn)移方程:sk+1=(1-0.3)xk

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

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

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

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

:第k階段結(jié)束時的產(chǎn)品庫存量。決策變量xk

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

sk

=sk-1

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