第七章動(dòng)態(tài)規(guī)劃學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1第七章動(dòng)態(tài)第七章動(dòng)態(tài)(dngti)規(guī)劃規(guī)劃第一頁(yè)，共76頁(yè)。動(dòng)態(tài)規(guī)劃的起源： 1951年,(美)數(shù)學(xué)家R.Bellman等人，根據(jù)多階段序貫決策問(wèn)題的特點(diǎn)，提出了著名的“最優(yōu)性原理”。將多階段決策問(wèn)題轉(zhuǎn)變?yōu)橐幌盗械幕ハ嗦?lián)系的單階段決策問(wèn)題，然后，逐個(gè)階段予以解決，最后再形成總體解決。從而創(chuàng)建了求解優(yōu)化問(wèn)題的新方法動(dòng)態(tài)規(guī)劃。1957年，他的名著動(dòng)態(tài)規(guī)劃出版。最優(yōu)性原理: 作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：即無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成(guchng)最優(yōu)子策略。簡(jiǎn)言之，最優(yōu)策略的子策略總是最優(yōu)的。2第1頁(yè)/共75頁(yè)第二頁(yè)，共76頁(yè)。動(dòng)態(tài)

2、決策(juc)問(wèn)題： 決策(juc)過(guò)程具有階段性和時(shí)序性(與時(shí)間有關(guān))的決策(juc)問(wèn)題。即決策(juc)過(guò)程可劃分為明顯的階段。動(dòng)態(tài)決策(juc)問(wèn)題分類： 1、按數(shù)據(jù)給出的形式分為： 離散型動(dòng)態(tài)決策(juc)問(wèn)題。 連續(xù)型動(dòng)態(tài)決策(juc)問(wèn)題。 2、按決策(juc)過(guò)程演變的性質(zhì)分為： 確定型動(dòng)態(tài)決策(juc)問(wèn)題。 隨機(jī)型動(dòng)態(tài)決策(juc)問(wèn)題。 3第2頁(yè)/共75頁(yè)第三頁(yè)，共76頁(yè)。例1 生產(chǎn)與存貯問(wèn)題要求確定一個(gè)逐月的生產(chǎn)計(jì)劃，在滿足需求條件下，使一年的生產(chǎn)與存貯費(fèi)用之和最?。?例2 投資決策問(wèn)題某公司現(xiàn)有資金Q萬(wàn)元，在今后(jnhu)5年內(nèi)考慮給A，B，C，D 4個(gè)項(xiàng)目投資？例

3、3 設(shè)備更新問(wèn)題現(xiàn)企業(yè)要決定一臺(tái)設(shè)備未來(lái)8年的更新計(jì)劃，問(wèn)應(yīng)在哪些年更新設(shè)備可使總費(fèi)用最?。?4第3頁(yè)/共75頁(yè)第四頁(yè)，共76頁(yè)。例例4 基建投資基建投資(tu z)問(wèn)題問(wèn)題 一家公司有三個(gè)工廠，每個(gè)廠都需要進(jìn)行擴(kuò)建。公司用于擴(kuò)一家公司有三個(gè)工廠，每個(gè)廠都需要進(jìn)行擴(kuò)建。公司用于擴(kuò)建的資金總共為建的資金總共為7萬(wàn)元。各個(gè)廠的投資萬(wàn)元。各個(gè)廠的投資(tu z)方案及擴(kuò)建后預(yù)期方案及擴(kuò)建后預(yù)期可獲得的利潤(rùn)如表所示可獲得的利潤(rùn)如表所示(單位：萬(wàn)元單位：萬(wàn)元)。 現(xiàn)在公司(n s)要確定時(shí)各廠投資多少才能使公司(n s)的總利潤(rùn)達(dá)到最大？ 廠名廠名方案方案1方案方案2方案方案3方案方案4投資數(shù)投資數(shù)利潤(rùn)

4、利潤(rùn)投資數(shù)投資數(shù)利潤(rùn)利潤(rùn)投資數(shù)投資數(shù)利潤(rùn)利潤(rùn)投資數(shù)投資數(shù)利潤(rùn)利潤(rùn)一廠一廠001528510二廠二廠001339411三廠三廠00273114135第4頁(yè)/共75頁(yè)第五頁(yè)，共76頁(yè)。例例5 貨船裝運(yùn)問(wèn)題貨船裝運(yùn)問(wèn)題 有四種貨物準(zhǔn)備裝到一艘貨船上。第有四種貨物準(zhǔn)備裝到一艘貨船上。第i(i12，3，4)種種貨物的每一箱重量是貨物的每一箱重量是wi(單位：噸單位：噸)，其價(jià)值，其價(jià)值(jizh)是是vi(單位：?jiǎn)挝唬焊稍稍?，如表所示。，如表所示。 假定這艘貨船(hu chun)的總載重量是10噸，現(xiàn)在要確定這四種貨物應(yīng)各裝幾箱才能使裝載貨物的總價(jià)值達(dá)到最大？ 貨物i單位重量wi單位價(jià)值vi1242

5、123474356第5頁(yè)/共75頁(yè)第六頁(yè)，共76頁(yè)。例例6 最短路程問(wèn)題最短路程問(wèn)題(wnt) 假定從假定從A地到地到E地要鋪設(shè)一條管道，其中要經(jīng)過(guò)若干個(gè)中地要鋪設(shè)一條管道，其中要經(jīng)過(guò)若干個(gè)中間點(diǎn)間點(diǎn)(如圖如圖)。 圖中兩點(diǎn)之間連線上的數(shù)字(shz)表示兩地間的距離，現(xiàn)在要選擇一條鋪設(shè)管道的路線使總長(zhǎng)度最短。 AB1B2B3C1C2C3D1D2 E3677695238354369437第6頁(yè)/共75頁(yè)第七頁(yè)，共76頁(yè)。1、階段：將所給問(wèn)題(wnt)的過(guò)程，按時(shí)間或空間特征分解成若干互相聯(lián)系的階段，以便按次序去求每階段的解，常用字母k表示階段變量。動(dòng)態(tài)(dngti)規(guī)劃模型要用到的概念： (1)

6、階段; (2)狀態(tài); (3)決策和策略; (4)狀態(tài)轉(zhuǎn)移; (5)指標(biāo)函數(shù)。8第7頁(yè)/共75頁(yè)第八頁(yè)，共76頁(yè)。2、狀態(tài)(zhungti)：各階段開(kāi)始時(shí)的客觀條件叫做狀態(tài)(zhungti)。狀態(tài)(zhungti)變量：描述各階段狀態(tài)(zhungti)的變量，用sk表示第k階段的狀態(tài)(zhungti)變量。狀態(tài)(zhungti)集合：狀態(tài)(zhungti)變量的取值集合，用Sk表示。一階段(jidun)：S1A二階段(jidun)：S2B1,B2,B3三階段(jidun)：S3C1,C2,C3四階段(jidun)：S4D1,D2AB1B2B3C1C2C3D1D2 E367769523835436

7、9439第8頁(yè)/共75頁(yè)第九頁(yè)，共76頁(yè)。3、決策：當(dāng)各段的狀態(tài)取定以后，就可以作出不同的決定(judng)（或選擇），從而確定下一階段的狀態(tài)，這種決定(judng)稱為決策。決策變量：表示決策的變量，稱為決策變量，常用uk(sk)表示第k階段當(dāng)狀態(tài)為sk時(shí)的決策變量。允許決策集合：決策變量的取值往往限制在一定范圍內(nèi)，我們稱此范圍為允許決策集合，用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合。D2( B1)=C1,C2 D2( B2)=C1,C2,C3如狀態(tài)為B1時(shí)選擇(xunz)C2，可表示為：u2(B1)=C210第9頁(yè)/共75頁(yè)第十頁(yè)，共76頁(yè)。策略：各段決策確定后，整個(gè)問(wèn)題的決

8、策序列就構(gòu)成一個(gè)策略，用p1,nu1(s1),u2(s2),.un(sn)表示。允許(ynx)策略集合：對(duì)每個(gè)實(shí)際問(wèn)題，可供選擇的策略有一定范圍，稱為允許(ynx)策略集合，記作P1,n，使整個(gè)問(wèn)題達(dá)到最優(yōu)效果的策略就是最優(yōu)策略。AB1B2B3C1C2C3D1D2 E367769523835436943p1,4B1,C1, D1,E二、基本概念和基本原理11第10頁(yè)/共75頁(yè)第十一頁(yè)，共76頁(yè)。 4、狀態(tài)轉(zhuǎn)移方程：動(dòng)態(tài)規(guī)劃(guhu)中本階段的狀態(tài)往往是上一階段狀態(tài)和上一階段的決策結(jié)果。第k段的狀態(tài)sk，本階段決策為uk(sk)，則第k+1段的狀態(tài)sk+1也就完全確定，它們的關(guān)系可用公式表示：

9、sk+1=Tk(sk,uk)sk+1= uk(sk)AB1B2B3C1C2C3D1D2 E367769523835436943二、基本概念和基本原理12第11頁(yè)/共75頁(yè)第十二頁(yè)，共76頁(yè)。 5、指標(biāo)函數(shù)：用于衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)。 它分為階段指標(biāo)函數(shù)和過(guò)程指標(biāo)函數(shù)。 階段指標(biāo)函數(shù)是指第k段，從狀態(tài)sk出發(fā)，采取決策uk時(shí)的效益，用d(sk,uk)表示(biosh)。d(B1,C2) 一個(gè)n段決策過(guò)程，從1到n叫作問(wèn)題的原過(guò)程，對(duì)于任意一個(gè)給定的k(1k n)，從第k段到第n段的過(guò)程稱為原過(guò)程的一個(gè)后部子過(guò)程。 V1,n(s1,p1,n) 表示(biosh)初始狀態(tài)為s1采用策略p1,

10、n時(shí)原過(guò)程的指標(biāo)函數(shù)值;Vk,n(sk,pk,n)表示(biosh)在第k段，狀態(tài)為sk采用策略pk,n時(shí),后部子過(guò)程的指標(biāo)函數(shù)值。 最優(yōu)指標(biāo)函數(shù)記為fk(sk)：表示(biosh)從第k段狀態(tài)sk采用最優(yōu)策略到過(guò)程終止時(shí)的最佳效益值。二、基本概念和基本原理13第12頁(yè)/共75頁(yè)第十三頁(yè)，共76頁(yè)。最簡(jiǎn)單的方法窮舉法。共有多少條路徑，依次計(jì)算并比較。動(dòng)態(tài)(dngti)規(guī)劃方法本方法是從過(guò)程的最后一段開(kāi)始，用逆序遞推方法求解，逐步求出各段各點(diǎn)到終點(diǎn)的最短路線，最后求得起始點(diǎn)到終點(diǎn)的最短路線。二、基本概念和基本原理14第13頁(yè)/共75頁(yè)第十四頁(yè)，共76頁(yè)。251121410610413111239

11、6581052C1C3D1AB1B3B2D2EC2練習(xí)(linx)：求從A到E的最短路徑(ljng)。二、基本概念和基本原理15第14頁(yè)/共75頁(yè)第十五頁(yè)，共76頁(yè)。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0二、基本概念和基本原理16第15頁(yè)/共75頁(yè)第十六頁(yè)，共76頁(yè)。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0505)E(f)ED(d)D(f5114二、基本概念和基本原理17第16頁(yè)/共75頁(yè)第十七頁(yè)，共76頁(yè)。2511214106104131112

12、396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5202)E(f)ED(d)D(f5224二、基本概念和基本原理18第17頁(yè)/共75頁(yè)第十八頁(yè)，共76頁(yè)。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=51124211411138118min2953min)(),()(),(min)(DCDfDCdDfDCdCf最優(yōu)決策二、基本概念和基本原理19第18頁(yè)/共75頁(yè)第十九頁(yè)，共76頁(yè)。2511214106104131112396581052C1

13、C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82224221412237711min2556min)(),()(),(min)(DCDfDCdDfDCdCf最優(yōu)決策二、基本概念和基本原理20第19頁(yè)/共75頁(yè)第二十頁(yè)，共76頁(yè)。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7232423141333121213min21058min)(),()(),(min)(DCDfDCdDfDCdCf最優(yōu)

14、決策二、基本概念和基本原理21第20頁(yè)/共75頁(yè)第二十一頁(yè)，共76頁(yè)。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8113331232113111220222120min1210714812min)(),()(),()(),(min)(CBCfCBdCfCBdCfCBdBf最優(yōu)決策二、基本概念和基本原理22第21頁(yè)/共75頁(yè)第二十二頁(yè)，共76頁(yè)。2511214106104131112396581052C1C3D1AB1B3B2D2EC2

15、f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=21123332232213122214161714min12471086min)(),()(),()(),(min)(CBCfCBdCfCBdCfCBdBf最優(yōu)決策二、基本概念和基本原理23第22頁(yè)/共75頁(yè)第二十三頁(yè)，共76頁(yè)。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=1

16、4233333232313133219231921min1211712813min)(),()(),()(),(min)(CBCfCBdCfCBdCfCBdBf最優(yōu)決策二、基本概念和基本原理24第23頁(yè)/共75頁(yè)第二十四頁(yè)，共76頁(yè)。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=212323222121119201923min191145212min)(),()(),()(),(min)(

17、BABfBAdBfBAdBfBAdAf最優(yōu)決策二、基本概念和基本原理25第24頁(yè)/共75頁(yè)第二十五頁(yè)，共76頁(yè)。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)(zhungti) 最優(yōu)決策 狀態(tài)(zhungti) 最優(yōu)決策 狀態(tài)(zhungti) 最優(yōu)決策 狀態(tài)(zhungti) 最優(yōu)決策 狀態(tài)(zhungti)A （ A，B2） B2二、基本概念和基本原理26第25頁(yè)/共75頁(yè)第二

18、十六頁(yè)，共76頁(yè)。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)(zhungti) 最優(yōu)決策 狀態(tài)(zhungti) 最優(yōu)決策 狀態(tài)(zhungti) 最優(yōu)決策 狀態(tài)(zhungti) 最優(yōu)決策 狀態(tài)(zhungti)A （ A，B2） B2 （B2，C1） C1二、基本概念和基本原理27第26頁(yè)/共75頁(yè)第二十七頁(yè)，共76頁(yè)。251121410610413111239658105

19、2C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)(zhungti) 最優(yōu)決策 狀態(tài)(zhungti) 最優(yōu)決策 狀態(tài)(zhungti) 最優(yōu)決策 狀態(tài)(zhungti) 最優(yōu)決策 狀態(tài)(zhungti)A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1二、基本概念和基本原理28第27頁(yè)/共75頁(yè)第二十八頁(yè)，共76頁(yè)。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)

20、=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)(zhungti) 最優(yōu)決策 狀態(tài)(zhungti) 最優(yōu)決策 狀態(tài)(zhungti) 最優(yōu)決策 狀態(tài)(zhungti) 最優(yōu)決策 狀態(tài)(zhungti)A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E從A到E的最短路徑(ljng)為19，路線為AB 2C1 D1 E 二、基本概念和基本原理29第28頁(yè)/共75頁(yè)第二十九頁(yè)，共76頁(yè)?？梢钥闯?kn ch)，在求解的各階段，都利用了第k段和第k+1段的

21、如下關(guān)系:0)(1 , 2 , 3 , 4 , 5)(),(min)(6611sfksfusdsfkkkkkkk這種遞推關(guān)系稱為動(dòng)態(tài)規(guī)劃的基本方程(fngchng)，第二個(gè)式子稱為邊界條件。這種在圖上直接計(jì)算的方法稱為標(biāo)號(hào)法。二、基本概念和基本原理30第29頁(yè)/共75頁(yè)第三十頁(yè)，共76頁(yè)。動(dòng)態(tài)規(guī)劃標(biāo)號(hào)法較之窮舉法的優(yōu)點(diǎn): 第一，容易算出; 其次，動(dòng)態(tài)規(guī)劃的計(jì)算結(jié)果不僅得到了從起始點(diǎn)到最終點(diǎn)的最短路線，而且得到了中間(zhngjin)段任一點(diǎn)到最終點(diǎn)的最短路線 。二、基本概念和基本原理31第30頁(yè)/共75頁(yè)第三十一頁(yè)，共76頁(yè)。動(dòng)態(tài)規(guī)劃(guhu)方法的基本思想： (1)將多階段決策過(guò)程劃分階段

22、，恰當(dāng)?shù)剡x取狀態(tài)變量、決策變量及定義最優(yōu)指標(biāo)函數(shù)從而把問(wèn)題化成一族同類型的子問(wèn)題，然后逐個(gè)求解。 (2)求解時(shí)從邊界條件開(kāi)始，逆(或順)過(guò)程行進(jìn)方向，逐段遞推尋優(yōu)。在每一個(gè)子問(wèn)題求解時(shí)，都要使用它前面已求出的子問(wèn)題的最優(yōu)結(jié)果，最后一個(gè)子問(wèn)題的最優(yōu)解，就是整個(gè)問(wèn)題的最優(yōu)解。 (3)動(dòng)態(tài)規(guī)劃(guhu)方法是既把當(dāng)前一段與未來(lái)各段分開(kāi)，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法，因此每段的最優(yōu)決策選取是從全局考慮的，與該段的最優(yōu)選擇一般是不同的。二、基本概念和基本原理32第31頁(yè)/共75頁(yè)第三十二頁(yè)，共76頁(yè)。（一）動(dòng)態(tài)規(guī)劃模型的建立（一）動(dòng)態(tài)規(guī)劃模型的建立（二）逆序解法與順序解法（二）逆

23、序解法與順序解法（三）基本方程（三）基本方程(fngchng)分段求解時(shí)的幾種常用算法分段求解時(shí)的幾種常用算法33第32頁(yè)/共75頁(yè)第三十三頁(yè)，共76頁(yè)。 （一）動(dòng)態(tài)規(guī)劃模型的建立建立動(dòng)態(tài)規(guī)劃的模型關(guān)鍵，在于識(shí)別問(wèn)題的多階段持征，將問(wèn)題分解成為可用遞推關(guān)系式聯(lián)系起來(lái)的若干子問(wèn)題，或者說(shuō)正確地建立具體問(wèn)題的基本方程。而正確建立基本遞推關(guān)系方程的關(guān)鍵又在于正確選擇狀態(tài)變量，保證各階段的狀您變量具有遞推的狀態(tài)轉(zhuǎn)移(zhuny)關(guān)系 sk+1=Tk(sk,uk)下面以資源分配問(wèn)題為例介紹動(dòng)態(tài)規(guī)劃的建模條件及解法。34第33頁(yè)/共75頁(yè)第三十四頁(yè)，共76頁(yè)。 例5 某公司有資金10萬(wàn)元若投資于項(xiàng)目i(i

24、1，2，3）的投資額為xi時(shí)，其收益分別為g1(x1)4x1，g2(x2)9x2，g3(x3)2x32，問(wèn)應(yīng)如何(rh)分配投資數(shù)額才能使總收益最大?可以人為地賦予時(shí)段，把問(wèn)題轉(zhuǎn)化為一個(gè)3段決策過(guò)程。關(guān)鍵問(wèn)題是如何正確選擇(xunz)狀態(tài)變量，使各后部子過(guò)程之間具有遞進(jìn)關(guān)系。)3 , 2 , 1(010. .294max3212321ixxxxtsxxxzi35第34頁(yè)/共75頁(yè)第三十五頁(yè)，共76頁(yè)。22112xuussK=1K=2第k段時(shí)所以，建立動(dòng)態(tài)規(guī)劃模型(mxng)：階段k：本例中取1，2，3狀態(tài)變量sk：第k段可以投資于第k項(xiàng)到第3個(gè)項(xiàng)目的資金數(shù)決策變量xk：決定給第k個(gè)項(xiàng)目投資的資

25、金數(shù)。狀態(tài)轉(zhuǎn)移方程：sk+1sk-xk最優(yōu)指標(biāo)函數(shù)fk(sk)：當(dāng)可投資金數(shù)為sk時(shí)，投資第k-3項(xiàng)所得的最大收益(shuy)數(shù)?；痉匠虨椋?1110 xuskkkkkxuuss1133 ,)( 函數(shù) 指標(biāo)kiiikxgV0)(1 , 2, 3)()(max)(44110sfksfxgsfkkkksxkkk36第35頁(yè)/共75頁(yè)第三十六頁(yè)，共76頁(yè)。 建立(jinl)動(dòng)態(tài)規(guī)劃模型的要點(diǎn)1、分析題意，識(shí)別問(wèn)題的多階段特性，按時(shí)間或空間的先后順序適當(dāng)?shù)貏澐譃闈M足遞推關(guān)系的若干階段。2、正確地選擇狀態(tài)變量，使其具備兩個(gè)必要待征： (1)可知性； (2)能夠確切地描述過(guò)程的演變且滿足無(wú)后效性。3、根

26、據(jù)狀態(tài)變量與決策變量的含義，正確寫(xiě)出狀態(tài)轉(zhuǎn)移方程sk+1=Tk(sk,uk)或轉(zhuǎn)移規(guī)則。4、根據(jù)題意明確指標(biāo)函數(shù)vk,n最優(yōu)指標(biāo)函數(shù)fk(sk)以及k階段指標(biāo)vk(sk,uk)的含義，并正確列出最優(yōu)指標(biāo)函數(shù)的遞推關(guān)系及邊界條件(即基本方程)。37第36頁(yè)/共75頁(yè)第三十七頁(yè)，共76頁(yè)。（二）逆序解法與順序解法如果尋優(yōu)的方向與多階段決策過(guò)程的實(shí)際行進(jìn)(xngjn)方向相反，從最后一段開(kāi)始計(jì)算逐段前推，求得全過(guò)程的最優(yōu)策略，稱為逆序解法。順序解法的尋優(yōu)方向同于過(guò)程的行進(jìn)(xngjn)方向，計(jì)算時(shí)從第一段開(kāi)始逐段向后遞推，計(jì)算后一階段要用到前一階段的求優(yōu)結(jié)果，最后一段計(jì)算的結(jié)果就是全過(guò)程的最優(yōu)結(jié)果。

27、38第37頁(yè)/共75頁(yè)第三十八頁(yè)，共76頁(yè)。第一步：k=0狀態(tài)(zhungti)：s1Af0(A)0求解(qi ji)步驟39第38頁(yè)/共75頁(yè)第三十九頁(yè)，共76頁(yè)。第二步：k=1 狀態(tài)(zhungti)：B1 B2 u1*(B1)=Au1*(B2)=Af1(B1)4f2(B2)5(4)(5)40第39頁(yè)/共75頁(yè)第四十頁(yè)，共76頁(yè)。第三步：k=2 狀態(tài)(zhungti)：C1 C2 C3 C4u2*(C1)=B1u2*(C2)=B1u2*(C3)=B1f2(C1)6f2(C2)7f2(C3)10u2*(C4)=B2f2(C4)12(4)(5)(6)(7)(10)(12)41第40頁(yè)/共75頁(yè)

28、第四十一頁(yè)，共76頁(yè)。(4)(5)(6)(7)(10)(12)第四步：k=3 狀態(tài)(zhungti)：D1 D2 D3u3*(D1)=C1或C2u3*(D2)=C2u3*(D3)=C3f3(D1)11f3(D2)12f3(D3)14(11)(12)(14)42第41頁(yè)/共75頁(yè)第四十二頁(yè)，共76頁(yè)。第五步：k=4 狀態(tài)(zhungti)：E1 E2 u4*(E1)=D1u4*(E2)=D2f4(E1)14f4(E2)14(4)(5)(6)(7)(10)(12)(11)(12)(14)(14)(14)43第42頁(yè)/共75頁(yè)第四十三頁(yè)，共76頁(yè)。第六步：k=5 狀態(tài)(zhungti)：F u5*(

29、F)=E2f5(F)17(6)(4)(5)(7)(10)(12)(11)(12)(14)(14)(14)(17)即從A到F的最短距離為17。最優(yōu)路線(lxin)為：AB1C2D2E2F44第43頁(yè)/共75頁(yè)第四十四頁(yè)，共76頁(yè)。逆序解法逆序解法(ji f)與順序解法與順序解法(ji f)建模的不同點(diǎn)建模的不同點(diǎn)1狀態(tài)轉(zhuǎn)移(zhuny)方式不同sk+1=Tk(sk,uk) sk=Tk(sk+1,uk) 1狀態(tài)s1決策u1效益v1(s1,u1)s2kskukvk(sk,uk)Sk+1nsnunvn(sn,un)Sn+11狀態(tài)s1決策u1效益v1(s2,u1)s2kskukvk(sk+1,uk)Sk

30、+1nsnunvn(sn+1,un)Sn+145第44頁(yè)/共75頁(yè)第四十五頁(yè)，共76頁(yè)。2指標(biāo)函數(shù)的定義不同 逆序解法中，我們定義最優(yōu)指標(biāo)函數(shù)fk(sk)表示第k段從狀態(tài)sk出發(fā)，到終點(diǎn)后部子過(guò)程(guchng)最優(yōu)效益值，f1(s1)是整體最優(yōu)函數(shù)值。 順序解法中，定義最優(yōu)指標(biāo)函數(shù)fk(sk+1)表示第k段時(shí)從起點(diǎn)到狀態(tài)sk+1的前部子過(guò)程(guchng)最優(yōu)效益值。fn(sn+1)是整體最優(yōu)函數(shù)值。46第45頁(yè)/共75頁(yè)第四十六頁(yè)，共76頁(yè)。3，基本(jbn)方程形式不同(1)當(dāng)指標(biāo)函數(shù)為階段指標(biāo)和形式逆序解法則基本(jbn)方程為：則基本(jbn)方程為：順序解法nkjjjjnkusvV

31、),( ,kjjjjkusvV11, 1),( 0)(1 , 2,.,1,)(),()(1111nnkkkkkDukksfnnksfusvoptsfkk0)(,.,2 , 1)(),()(10111sfnksfusvoptsfkkkkkDukkkk47第46頁(yè)/共75頁(yè)第四十七頁(yè)，共76頁(yè)。(2)當(dāng)指標(biāo)(zhbio)函數(shù)為階段指標(biāo)(zhbio)積形式逆序解法基本(jbn)方程為：基本(jbn)方程為：順序解法nkjjjjnkusvV),( ,kjjjjkusvV11, 1),( 1)(1 , 2,.,1,)(),()(1111nnkkkkkDukksfnnksfusvoptsfkk1)(,.,

32、2 , 1)(),()(10111sfnksfusvoptsfkkkkkDukkkk48第47頁(yè)/共75頁(yè)第四十八頁(yè)，共76頁(yè)。1離散變量(binling)的分段窮舉算法 動(dòng)態(tài)規(guī)劃模型中的狀態(tài)變量(binling)與決策變量(binling)若被限定只能取離散值，則可采用分段窮舉法。如前面例4的求解方法就是分段窮舉算法，由于每段的狀態(tài)變量(binling)和決策變量(binling)離散取值個(gè)數(shù)較少，所以動(dòng)態(tài)規(guī)劃的窮舉法要比一般的窮舉法有效。用分段窮舉法求最優(yōu)指標(biāo)函數(shù)值時(shí)，最重要的是正確確定每段狀態(tài)變量(binling)取值范圍和允許決策集合的范圍。（三）基本方程(fngchng)分段求解時(shí)的

33、幾種常用算法49第48頁(yè)/共75頁(yè)第四十九頁(yè)，共76頁(yè)。2連續(xù)變量的解法 當(dāng)動(dòng)態(tài)規(guī)劃模型中狀態(tài)變量與決策變量為連續(xù)變量，就要根據(jù)方程的具體情況靈活選取求解方法，如經(jīng)典解析方法、線性規(guī)劃方法、非線性規(guī)劃法或其它數(shù)值計(jì)算方法等。如在例5中，狀態(tài)變量與決策變量均可取連續(xù)值而不是(b shi)離散值，所以每階段求優(yōu)時(shí)不能用窮舉方法處理。下面分別用逆序解法求解。三、動(dòng)態(tài)(dngti)規(guī)劃模型的建立與求解50第49頁(yè)/共75頁(yè)第五十頁(yè)，共76頁(yè)。 例5： 某公司有資金10萬(wàn)元若投資(tu z)于項(xiàng)目i(i1，2，3）的投資(tu z)額為xi時(shí)，其收益分別為g1(x1)4x1,g2(x2)9x2,g3(x

34、3)2x32，問(wèn)應(yīng)如何分配投資(tu z)數(shù)額才能使總收益最大?)3 , 2 , 1(010. .294max3212321ixxxxtsxxxzi三、動(dòng)態(tài)規(guī)劃(guhu)模型的建立與求解51第50頁(yè)/共75頁(yè)第五十一頁(yè)，共76頁(yè)。其動(dòng)態(tài)規(guī)劃模型已建立如下：階段(jidun)k：本例中取1，2，3狀態(tài)變量sk：第k段可以投資于第k項(xiàng)到第3個(gè)項(xiàng)目的資金數(shù)決策變量xk：決定給第k個(gè)項(xiàng)目投資的資金數(shù)。狀態(tài)轉(zhuǎn)移方程：sk+1sk-xk最優(yōu)指標(biāo)函數(shù)fk(sk)：當(dāng)可投資金數(shù)為sk時(shí)，投資第k-3項(xiàng)所得(su d)的最大收益數(shù)?；痉匠虨椋?3 ,)( 函數(shù) 指標(biāo)kiiikxgV0)(1 , 2, 3)(

35、)(max)(44110sfksfxgsfkkkksxkkk52第51頁(yè)/共75頁(yè)第五十二頁(yè)，共76頁(yè)。k3時(shí)2max)(2303333xsfsx 233*32s，sx取得極大值時(shí)當(dāng)232303322max)(33sxsfsx233*32s，sx取得極大值時(shí)當(dāng)53第52頁(yè)/共75頁(yè)第五十三頁(yè)，共76頁(yè)。k2時(shí))(29max29max )(9max)(222202320332022222222xsxsxsfxsfsxsxsx2222222)(29),(xsxxsh令是極小值點(diǎn)9422 sx22222229)(2)0(0ssfsf。，s端點(diǎn)取得極大值只可能在2/9)()0(2222ssff得當(dāng)2*

36、22222*22222),()0(2/90),()0(2/9sxsf，fsxsf，fs時(shí)當(dāng)時(shí)當(dāng)54第53頁(yè)/共75頁(yè)第五十四頁(yè)，共76頁(yè)。k1時(shí) )(4max)(22101111sfxsfsx2222*29)(ss，fsx時(shí)當(dāng)111100111100195-9max9-94max)10(11sxsxsxfxx2*22222*22222),()0(2/90),()0(2/9sxsf，fsxsf，fs時(shí)當(dāng)時(shí)當(dāng)10010112xss。，s舍去矛盾與2/9255第54頁(yè)/共75頁(yè)第五十五頁(yè)，共76頁(yè)。k1時(shí) )(4max)(22101111sfxsfsx2222*22)(0ss，fx 時(shí)當(dāng))-(24m

37、ax)10(211110011xsxfx)-(24),(2111111xsxxsh令是極小點(diǎn)111 sx40)10(200)0(10011ff。，端點(diǎn)取得極大值只可能在10010*112xss0*1x所以2/92s滿足條件1010010, 03*3*223*2s；xxssx所以最優(yōu)投資方案為全部資金投于第3個(gè)項(xiàng)目(xingm)，可得最大收益200萬(wàn)元。56第55頁(yè)/共75頁(yè)第五十六頁(yè)，共76頁(yè)。四、在經(jīng)濟(jì)四、在經(jīng)濟(jì)(jngj)管理中的應(yīng)用管理中的應(yīng)用（一）背包(bibo)問(wèn)題 背包問(wèn)題的一般提法是：一位旅行者攜帶背包去登山、已知他所能承受的背包重量限度為a千克，現(xiàn)有(xin yu)n種物品可供

38、他選擇裝入背包。第i種物品的單件重量為ai干克、其價(jià)值(可以是表明本物品對(duì)登山的重要性的數(shù)量指標(biāo))是攜帶數(shù)量xi的函數(shù)ci(xi) (i1，2，n)，問(wèn)旅行者應(yīng)如何選擇攜帶各種物品的件數(shù)，以使總價(jià)值最大？ 其他如車、船、飛機(jī)、潛艇、人造衛(wèi)星等工具的最優(yōu)裝載問(wèn)題，機(jī)床加工中零件最優(yōu)加工、下料問(wèn)題、投資決策問(wèn)題，均等同于背包問(wèn)題。57第56頁(yè)/共75頁(yè)第五十七頁(yè)，共76頁(yè)。背包問(wèn)題背包問(wèn)題(wnt)的動(dòng)態(tài)規(guī)劃模的動(dòng)態(tài)規(guī)劃模型型1階段k：將可裝入物品按1，2，.，n排序，共劃分為n個(gè)階段，即k1，2，.，n。2狀態(tài)變量sk+1：在第k段開(kāi)始時(shí)，背包中允許裝入前k種物品的總重量。3決策變量xk：裝入第

39、k種物品的件數(shù)。4狀態(tài)轉(zhuǎn)移方程：sk=sk+1-akxk5允許決策集合為： Dk(sk+1)xk|oxk sk+1/ak，xk為整數(shù)6最優(yōu)指標(biāo)函數(shù) fk(sk+1)表示在背包中允許裝入物品的總重量不超過(guò)sk+1千克，采用最優(yōu)策略只裝前k種物品時(shí)的最大使用(shyng)價(jià)值。7順序遞推方程：0)(n1,2,.,k )()(max)(1011/,.,1 , 01sfxasfxcsfkkkkkkasrkkkkk四、在經(jīng)濟(jì)管理四、在經(jīng)濟(jì)管理(gunl)中的應(yīng)用中的應(yīng)用58第57頁(yè)/共75頁(yè)第五十八頁(yè)，共76頁(yè)。例: 有一輛最大貨運(yùn)量為10噸的卡車(kch)，用以裝載3種貨物每種貨物的單位重量及相應(yīng)單位

40、價(jià)值如表所示。應(yīng)如何裝載可使總價(jià)值最大?設(shè)第i種貨物裝載的件數(shù)(jin sh)為xi(i1，2，3)，則問(wèn)題可表為貨物編號(hào)I123單位重量（t）345單位價(jià)值ci456) 3 , 2 , 1(為整數(shù)010543. .654max321321ixxxxtsxxxzi四、在經(jīng)濟(jì)四、在經(jīng)濟(jì)(jngj)管理中的應(yīng)用管理中的應(yīng)用59第58頁(yè)/共75頁(yè)第五十九頁(yè)，共76頁(yè)。K=1 3/ 44max)(213/021121sxsfxsx為整數(shù)s2012345678910f1(s2)0004448881212x1*00011122233s2f1(s2)x1*0)(n1,2,.,k )()(max)(1011/

41、,.,1 , 01sfxasfxcsfkkkkkkasxkkkkk建立動(dòng)態(tài)(dngti)規(guī)劃模型，用列表法求解四、在經(jīng)濟(jì)管理四、在經(jīng)濟(jì)管理(gunl)中的應(yīng)中的應(yīng)用用60第59頁(yè)/共75頁(yè)第六十頁(yè)，共76頁(yè)。K=2)4(5max)(23124/032232xsfxsfxsx為整數(shù)s30123 45678910 x200000 10 10 10 10 1 20 1 20 1 2c2+f200044 54 58 58 98 9 1012 9 1012 13 10f2(s3)0004 5 58 9 1012 13x2*0000 1 10 1 20 1s3x2c2+f2f2(s3)x2*四、在經(jīng)濟(jì)四、

42、在經(jīng)濟(jì)(jngj)管理中的應(yīng)管理中的應(yīng)用用61第60頁(yè)/共75頁(yè)第六十一頁(yè)，共76頁(yè)。K=3)510(6max)10(3232, 1 , 033xfxfx)0(12),5(6),10(max222fff012, 56 ,13max13所以(suy)x3*=0s3=s4-5x3=10-5*0=10所以(suy)x2*=1s2=s3-4x2=10-4*1=6所以(suy)x1*=2全部策略為：x1*=2 x2*=1 x3*=0，最大價(jià)值為13。四、在經(jīng)濟(jì)管理中的應(yīng)用四、在經(jīng)濟(jì)管理中的應(yīng)用62第61頁(yè)/共75頁(yè)第六十二頁(yè)，共76頁(yè)。（二）生產(chǎn)經(jīng)營(yíng)(jngyng)問(wèn)題生產(chǎn)與存貯問(wèn)題 在生產(chǎn)和經(jīng)營(yíng)管理中

43、經(jīng)常遇到如何合理地安排生產(chǎn)計(jì)劃、采購(gòu)計(jì)劃以及倉(cāng)庫(kù)(cngk)的存貨計(jì)劃和銷售計(jì)劃，使總效益最高的問(wèn)題。四、在經(jīng)濟(jì)管理四、在經(jīng)濟(jì)管理(gunl)中的應(yīng)中的應(yīng)用用63第62頁(yè)/共75頁(yè)第六十三頁(yè)，共76頁(yè)。 例：某工廠生產(chǎn)并銷售某種產(chǎn)品，已知今后四個(gè)月市場(chǎng)需求預(yù)測(cè)如表，又每月生產(chǎn)單位(dnwi)產(chǎn)品費(fèi)用為： 每月庫(kù)存j單位產(chǎn)品的費(fèi)用為E(j)0.5j(干元)，該廠最大庫(kù)存容量為3單位，每月最大生產(chǎn)能力為6單位，計(jì)劃開(kāi)始和計(jì)劃期末庫(kù)存量都是零。試制定(zhdng)四個(gè)月的生產(chǎn)計(jì)劃，在滿足用戶需求條件下總費(fèi)用最小。假設(shè)第j+1個(gè)月的庫(kù)存量是第j個(gè)月可銷售量與該月用戶需求量之差；而第i個(gè)月的可銷售量是本

44、月初庫(kù)存量與產(chǎn)量之和。 i（月）1234gi（需求）2324 )6,.,2 , 1(3)0(0 )(jjjjC四、在經(jīng)濟(jì)四、在經(jīng)濟(jì)(jngj)管理中的應(yīng)用管理中的應(yīng)用64第63頁(yè)/共75頁(yè)第六十四頁(yè)，共76頁(yè)。0)(1,2,3,4k )()()(min)(551sfgusfsEucsfkkkkkkkk(1)階段：每個(gè)月為一個(gè)階段，k1，2，3，4。(2)狀態(tài)變量:sk為第k個(gè)月初的庫(kù)存量。(3)決策變量:uk為第k個(gè)月的生產(chǎn)(shngchn)量。(4)狀態(tài)轉(zhuǎn)移方程：sk+1=sk+uk-gk(5)最優(yōu)指標(biāo)函數(shù)：fk(sk)表示第k月?tīng)顟B(tài)為sk時(shí)，采用最佳策略生產(chǎn)(shngchn)，從本月到計(jì)劃

45、結(jié)束（第4個(gè)月末）的生產(chǎn)(shngchn)與存貯最低費(fèi)用。(6)基本方程：解：建立動(dòng)態(tài)規(guī)劃(guhu)模型四、在經(jīng)濟(jì)四、在經(jīng)濟(jì)(jngj)管理中的應(yīng)用管理中的應(yīng)用65第64頁(yè)/共75頁(yè)第六十五頁(yè)，共76頁(yè)。K=4 u4=4-s4s40123f4(s4)76.565.5u4(s4)4321 )()(min)(4444sEucsfs4f4(s4)u4(s4)四、在經(jīng)濟(jì)四、在經(jīng)濟(jì)(jngj)管理中的應(yīng)管理中的應(yīng)用用66第65頁(yè)/共75頁(yè)第六十六頁(yè)，共76頁(yè)。s30123u3(s3)2 3 4 51 2 3 40 1 2 3 0 1 2C+E+f412 12.5 13 13.511.5 12 12.5

46、 138 11.5 12 12.58 11.5 12f3(s3)1211.588u3 *(s3)2100K=3 s3=0,1,2,3 )()()(min)(33343333gusfsEucsf且為整數(shù))6 ,5 , 6min(2 , 0max3333ssuss3u3(s3)C+E+f4f3(s3)u3 *(s3)四、在經(jīng)濟(jì)四、在經(jīng)濟(jì)(jngj)管理中的應(yīng)用管理中的應(yīng)用67第66頁(yè)/共75頁(yè)第六十七頁(yè)，共76頁(yè)。s20123u2(s2)3 4 5 62 3 4 51 2 3 40 1 2 3C+E+f318 18.5 16 1717.5 18 15.5 16.517 17.5 15 1613.5

47、 17 14.5 15.5f2(s2)1615.51513.5u2 *(s2)5430K=2 s2=0,1,2,3 )()()(min)(22232222gusfsEucsf且為整數(shù))9 ,6 , 6min(3 , 0max2233ssuss2u2(s2)C+E+f3f2(s2)u2 *(s2)四、在經(jīng)濟(jì)四、在經(jīng)濟(jì)(jngj)管理中的應(yīng)用管理中的應(yīng)用68第67頁(yè)/共75頁(yè)第六十八頁(yè)，共76頁(yè)。s10u1(s1)2345C+f22121.52221.5f1(s1)21u1 *(s1)2K=1 s1=0 )()()(min)(11121111gusfsEucsf且為整數(shù)521us1u1(s1)C+

48、f2f1(s1)u1 *(s1) 可得最佳(zu ji)生產(chǎn)計(jì)劃為：第一個(gè)月生產(chǎn)2單位，第二個(gè)月生產(chǎn)5單位，第三個(gè)月不生產(chǎn)，第四個(gè)月生產(chǎn)4單位。四、在經(jīng)濟(jì)四、在經(jīng)濟(jì)(jngj)管理中的應(yīng)用管理中的應(yīng)用69第68頁(yè)/共75頁(yè)第六十九頁(yè)，共76頁(yè)。采購(gòu)采購(gòu)(cigu)與銷售問(wèn)題與銷售問(wèn)題 某商店在未來(lái)的某商店在未來(lái)的4個(gè)月里個(gè)月里,準(zhǔn)備用它的一個(gè)倉(cāng)庫(kù)來(lái)專門經(jīng)銷某種商準(zhǔn)備用它的一個(gè)倉(cāng)庫(kù)來(lái)專門經(jīng)銷某種商品品,倉(cāng)庫(kù)最大容量能貯存這種商品倉(cāng)庫(kù)最大容量能貯存這種商品1000單位單位.假定該商店每月只能出賣假定該商店每月只能出賣倉(cāng)庫(kù)現(xiàn)有的貨倉(cāng)庫(kù)現(xiàn)有的貨,當(dāng)商店在某月購(gòu)貨時(shí)當(dāng)商店在某月購(gòu)貨時(shí),下月初才能到貨下月初才能到貨.預(yù)測(cè)該商品未來(lái)預(yù)測(cè)該商品未來(lái)四個(gè)月的買賣價(jià)格如表四個(gè)月的買賣價(jià)格如表7-12所示所示,假定商店在假定商店在1月開(kāi)