第七章動態(tài)規(guī)劃學(xué)習(xí)教案_第1頁
第七章動態(tài)規(guī)劃學(xué)習(xí)教案_第2頁
第七章動態(tài)規(guī)劃學(xué)習(xí)教案_第3頁
第七章動態(tài)規(guī)劃學(xué)習(xí)教案_第4頁
第七章動態(tài)規(guī)劃學(xué)習(xí)教案_第5頁
已閱讀5頁,還剩71頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

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

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

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

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

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

6、階段; (2)狀態(tài); (3)決策和策略; (4)狀態(tài)轉(zhuǎn)移; (5)指標(biāo)函數(shù)。8第7頁/共75頁第八頁,共76頁。2、狀態(tài)(zhungti):各階段開始時的客觀條件叫做狀態(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頁/共75頁第九頁,共76頁。3、決策:當(dāng)各段的狀態(tài)取定以后,就可以作出不同的決定(judng)(或選擇),從而確定下一階段的狀態(tài),這種決定(judng)稱為決策。決策變量:表示決策的變量,稱為決策變量,常用uk(sk)表示第k階段當(dāng)狀態(tài)為sk時的決策變量。允許決策集合:決策變量的取值往往限制在一定范圍內(nèi),我們稱此范圍為允許決策集合,用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合。D2( B1)=C1,C2 D2( B2)=C1,C2,C3如狀態(tài)為B1時選擇(xunz)C2,可表示為:u2(B1)=C210第9頁/共75頁第十頁,共76頁。策略:各段決策確定后,整個問題的決

8、策序列就構(gòu)成一個策略,用p1,nu1(s1),u2(s2),.un(sn)表示。允許(ynx)策略集合:對每個實(shí)際問題,可供選擇的策略有一定范圍,稱為允許(ynx)策略集合,記作P1,n,使整個問題達(dá)到最優(yōu)效果的策略就是最優(yōu)策略。AB1B2B3C1C2C3D1D2 E367769523835436943p1,4B1,C1, D1,E二、基本概念和基本原理11第10頁/共75頁第十一頁,共76頁。 4、狀態(tài)轉(zhuǎn)移方程:動態(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頁/共75頁第十二頁,共76頁。 5、指標(biāo)函數(shù):用于衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)。 它分為階段指標(biāo)函數(shù)和過程指標(biāo)函數(shù)。 階段指標(biāo)函數(shù)是指第k段,從狀態(tài)sk出發(fā),采取決策uk時的效益,用d(sk,uk)表示(biosh)。d(B1,C2) 一個n段決策過程,從1到n叫作問題的原過程,對于任意一個給定的k(1k n),從第k段到第n段的過程稱為原過程的一個后部子過程。 V1,n(s1,p1,n) 表示(biosh)初始狀態(tài)為s1采用策略p1,

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

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

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

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

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

18、十六頁,共76頁。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頁/共75頁第二十七頁,共76頁。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頁/共75頁第二十八頁,共76頁。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頁/共75頁第二十九頁,共76頁??梢钥闯?kn ch),在求解的各階段,都利用了第k段和第k+1段的

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

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

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

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

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

26、據(jù)狀態(tài)變量與決策變量的含義,正確寫出狀態(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頁/共75頁第三十七頁,共76頁。(二)逆序解法與順序解法如果尋優(yōu)的方向與多階段決策過程的實(shí)際行進(jìn)(xngjn)方向相反,從最后一段開始計(jì)算逐段前推,求得全過程的最優(yōu)策略,稱為逆序解法。順序解法的尋優(yōu)方向同于過程的行進(jìn)(xngjn)方向,計(jì)算時從第一段開始逐段向后遞推,計(jì)算后一階段要用到前一階段的求優(yōu)結(jié)果,最后一段計(jì)算的結(jié)果就是全過程的最優(yōu)結(jié)果。

27、38第37頁/共75頁第三十八頁,共76頁。第一步:k=0狀態(tài)(zhungti):s1Af0(A)0求解(qi ji)步驟39第38頁/共75頁第三十九頁,共76頁。第二步:k=1 狀態(tài)(zhungti):B1 B2 u1*(B1)=Au1*(B2)=Af1(B1)4f2(B2)5(4)(5)40第39頁/共75頁第四十頁,共76頁。第三步: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頁/共75頁

28、第四十一頁,共76頁。(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頁/共75頁第四十二頁,共76頁。第五步: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頁/共75頁第四十三頁,共76頁。第六步: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頁/共75頁第四十四頁,共76頁。逆序解法逆序解法(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頁/共75頁第四十五頁,共76頁。2指標(biāo)函數(shù)的定義不同 逆序解法中,我們定義最優(yōu)指標(biāo)函數(shù)fk(sk)表示第k段從狀態(tài)sk出發(fā),到終點(diǎn)后部子過程(guchng)最優(yōu)效益值,f1(s1)是整體最優(yōu)函數(shù)值。 順序解法中,定義最優(yōu)指標(biāo)函數(shù)fk(sk+1)表示第k段時從起點(diǎn)到狀態(tài)sk+1的前部子過程(guchng)最優(yōu)效益值。fn(sn+1)是整體最優(yōu)函數(shù)值。46第45頁/共75頁第四十六頁,共76頁。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頁/共75頁第四十七頁,共76頁。(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頁/共75頁第四十八頁,共76頁。1離散變量(binling)的分段窮舉算法 動態(tài)規(guī)劃模型中的狀態(tài)變量(binling)與決策變量(binling)若被限定只能取離散值,則可采用分段窮舉法。如前面例4的求解方法就是分段窮舉算法,由于每段的狀態(tài)變量(binling)和決策變量(binling)離散取值個數(shù)較少,所以動態(tài)規(guī)劃的窮舉法要比一般的窮舉法有效。用分段窮舉法求最優(yōu)指標(biāo)函數(shù)值時,最重要的是正確確定每段狀態(tài)變量(binling)取值范圍和允許決策集合的范圍。(三)基本方程(fngchng)分段求解時的

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

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

35、)(max)(44110sfksfxgsfkkkksxkkk52第51頁/共75頁第五十二頁,共76頁。k3時2max)(2303333xsfsx 233*32s,sx取得極大值時當(dāng)232303322max)(33sxsfsx233*32s,sx取得極大值時當(dāng)53第52頁/共75頁第五十三頁,共76頁。k2時)(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時當(dāng)時當(dāng)54第53頁/共75頁第五十四頁,共76頁。k1時 )(4max)(22101111sfxsfsx2222*29)(ss,fsx時當(dāng)111100111100195-9max9-94max)10(11sxsxsxfxx2*22222*22222),()0(2/90),()0(2/9sxsf,fsxsf,fs時當(dāng)時當(dāng)10010112xss。,s舍去矛盾與2/9255第54頁/共75頁第五十五頁,共76頁。k1時 )(4max)(22101111sfxsfsx2222*22)(0ss,fx 時當(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個項(xiàng)目(xingm),可得最大收益200萬元。56第55頁/共75頁第五十六頁,共76頁。四、在經(jīng)濟(jì)四、在經(jīng)濟(jì)(jngj)管理中的應(yīng)用管理中的應(yīng)用(一)背包(bibo)問題 背包問題的一般提法是:一位旅行者攜帶背包去登山、已知他所能承受的背包重量限度為a千克,現(xiàn)有(xin yu)n種物品可供

38、他選擇裝入背包。第i種物品的單件重量為ai干克、其價值(可以是表明本物品對登山的重要性的數(shù)量指標(biāo))是攜帶數(shù)量xi的函數(shù)ci(xi) (i1,2,n),問旅行者應(yīng)如何選擇攜帶各種物品的件數(shù),以使總價值最大? 其他如車、船、飛機(jī)、潛艇、人造衛(wèi)星等工具的最優(yōu)裝載問題,機(jī)床加工中零件最優(yōu)加工、下料問題、投資決策問題,均等同于背包問題。57第56頁/共75頁第五十七頁,共76頁。背包問題背包問題(wnt)的動態(tài)規(guī)劃模的動態(tài)規(guī)劃模型型1階段k:將可裝入物品按1,2,.,n排序,共劃分為n個階段,即k1,2,.,n。2狀態(tài)變量sk+1:在第k段開始時,背包中允許裝入前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)表示在背包中允許裝入物品的總重量不超過sk+1千克,采用最優(yōu)策略只裝前k種物品時的最大使用(shyng)價值。7順序遞推方程:0)(n1,2,.,k )()(max)(1011/,.,1 , 01sfxasfxcsfkkkkkkasrkkkkk四、在經(jīng)濟(jì)管理四、在經(jīng)濟(jì)管理(gunl)中的應(yīng)用中的應(yīng)用58第57頁/共75頁第五十八頁,共76頁。例: 有一輛最大貨運(yùn)量為10噸的卡車(kch),用以裝載3種貨物每種貨物的單位重量及相應(yīng)單位

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

41、,.,1 , 01sfxasfxcsfkkkkkkasxkkkkk建立動態(tài)(dngti)規(guī)劃模型,用列表法求解四、在經(jīng)濟(jì)管理四、在經(jīng)濟(jì)管理(gunl)中的應(yīng)中的應(yīng)用用60第59頁/共75頁第六十頁,共76頁。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頁/共75頁第六十一頁,共76頁。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,最大價值為13。四、在經(jīng)濟(jì)管理中的應(yīng)用四、在經(jīng)濟(jì)管理中的應(yīng)用62第61頁/共75頁第六十二頁,共76頁。(二)生產(chǎn)經(jīng)營(jngyng)問題生產(chǎn)與存貯問題 在生產(chǎn)和經(jīng)營管理中

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

44、月初庫存量與產(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頁/共75頁第六十四頁,共76頁。0)(1,2,3,4k )()()(min)(551sfgusfsEucsfkkkkkkkk(1)階段:每個月為一個階段,k1,2,3,4。(2)狀態(tài)變量:sk為第k個月初的庫存量。(3)決策變量:uk為第k個月的生產(chǎn)(shngchn)量。(4)狀態(tài)轉(zhuǎn)移方程:sk+1=sk+uk-gk(5)最優(yōu)指標(biāo)函數(shù):fk(sk)表示第k月狀態(tài)為sk時,采用最佳策略生產(chǎn)(shngchn),從本月到計(jì)劃

45、結(jié)束(第4個月末)的生產(chǎn)(shngchn)與存貯最低費(fèi)用。(6)基本方程:解:建立動態(tài)規(guī)劃(guhu)模型四、在經(jīng)濟(jì)四、在經(jīng)濟(jì)(jngj)管理中的應(yīng)用管理中的應(yīng)用65第64頁/共75頁第六十五頁,共76頁。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頁/共75頁第六十六頁,共76頁。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頁/共75頁第六十七頁,共76頁。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頁/共75頁第六十八頁,共76頁。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ì)劃為:第一個月生產(chǎn)2單位,第二個月生產(chǎn)5單位,第三個月不生產(chǎn),第四個月生產(chǎn)4單位。四、在經(jīng)濟(jì)四、在經(jīng)濟(jì)(jngj)管理中的應(yīng)用管理中的應(yīng)用69第68頁/共75頁第六十九頁,共76頁。采購采購(cigu)與銷售問題與銷售問題 某商店在未來的某商店在未來的4個月里個月里,準(zhǔn)備用它的一個倉庫來專門經(jīng)銷某種商準(zhǔn)備用它的一個倉庫來專門經(jīng)銷某種商品品,倉庫最大容量能貯存這種商品倉庫最大容量能貯存這種商品1000單位單位.假定該商店每月只能出賣假定該商店每月只能出賣倉庫現(xiàn)有的貨倉庫現(xiàn)有的貨,當(dāng)商店在某月購貨時當(dāng)商店在某月購貨時,下月初才能到貨下月初才能到貨.預(yù)測該商品未來預(yù)測該商品未來四個月的買賣價格如表四個月的買賣價格如表7-12所示所示,假定商店在假定商店在1月開

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論