版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、第七章第七章 動態(tài)規(guī)劃動態(tài)規(guī)劃 動態(tài)規(guī)劃是運籌學的一個重要分支,它是從1951年開始,由美國人貝克曼為首的一個學派發(fā)展起來的,動態(tài)規(guī)劃在經濟、管理、軍事、工程技術等方面都有廣泛的應用。 動態(tài)規(guī)劃是解決多階段決策過程的最優(yōu)化問題的一種方法。所謂多階段決策過程是指這樣一類決策過程:它可以把一個復雜問題按時間(空間)分成若干個階段,每個階段都要作出決策,以便得到過程的最優(yōu)結局。由于在每個階段采取的決策是與時間有關的而且前一階段采取的決策如何,不但與該階段的經濟效果有關,還影響以后的各階段的經濟效果。可見,這類多階段決策問題是一個動態(tài)問題。因此,處理的方法稱為動態(tài)規(guī)劃方法。然而,動態(tài)規(guī)劃也可以處理一些
2、本來與時間無關的靜態(tài)模型,這只需要在靜態(tài)模型中人為引入“時間”因素,分成時段,就可以把它看作是多階段的動態(tài)模型,用動態(tài)規(guī)劃方法來處理。 動態(tài)規(guī)劃解決多階段決策問題的效果是明顯的,但也有一定的局限性,首先,它沒有統(tǒng)一的處理方法;另外當變量的維數(shù)增大時,有“維數(shù)障礙”問題。在研究經濟、經營管理和工程技術領域內的有關問題中,有一類特殊形式的動態(tài)決策問題多階段決策問題。在多階段決策過程中,系統(tǒng)的動態(tài)過程可以按照時間進程分為相互聯(lián)系而又相互區(qū)別的各個階段,在每個階段都需要進行決策,系統(tǒng)在每個階段存在許多不同的狀態(tài),在某個時間的狀態(tài)往往要依某種形式受到過去某些決策的影響,而系統(tǒng)的當前狀態(tài)和決策又會影響系統(tǒng)
3、過程的今后的發(fā)展,因而在尋求多階段決策問題的最優(yōu)解時,重要的是不能從眼前的局部利益出發(fā)進行決策而需要從系統(tǒng)所經過的整個期間的總效益出發(fā),有預見性進行動態(tài)決策,找到不同時點的最優(yōu)決策及整個過程的最優(yōu)策略。第一節(jié)第一節(jié) 多階段決策問題多階段決策問題 例例7.1 最短路問題如圖所示,要從A地到E地鋪設管線,中間需要經過三個中間站,兩點之間的連線上的數(shù)字表示距離,問應該選擇什么路線,使總距離最短? 35256321737562254321B1AB2B3C1C2C3C4ED2D1例例7-2 機器負荷問題某工廠有100臺機器,擬分四個周期使用,在每一個周期有兩種生產任務。據經驗,把機器x1臺投入第一種生產
4、任務,則在一個生產周期中將有1/3x1臺機器報廢;余下的機器全部投入第二種生產任務,則有1/10的機器報廢,如果干第一種生產任務每臺機器可以收益10,干第二種生產任務每臺機器可以收益7,問怎樣分配機器使總收益最大? 例例7-3 資源分配問題假設有一種資源其數(shù)量為a,現(xiàn)將它分配給n個使用者。若分配給第i個使用者的數(shù)量為xi(i=1,n),產生的相應收益為gi(xi),問如何分配使總收益最大?投資決策問題、生產存貯問題、采購問題、設備更新問題等都具有多階段決策問題的特征,都可以用動態(tài)規(guī)劃方法求解。 第二節(jié)第二節(jié) 動態(tài)規(guī)劃的基本概念和基本原理動態(tài)規(guī)劃的基本概念和基本原理 一、動態(tài)規(guī)劃的基本概念動態(tài)規(guī)
5、劃的基本概念1.階段(stage)動態(tài)規(guī)劃通常都具有時間或空間上的次序性,因此,求解這類問題時,首先要將問題按一定次序劃分為若干個相互聯(lián)系的階段,以便能按一定次序求解。描述階段的變量稱為階段變量(k)k=1,AB;k=2,BC;k=3,CD;k=4,DE。35256321737562254321B1AB2B3C1C2C3C4ED2D12.狀態(tài)(state) 在多階段決策過程中,每個階段都要進行決策,而決策是根據系統(tǒng)所處情況決定的。狀態(tài)表示各階段開始所處的自然狀況或客觀條件,它既是某階段過程演變的起點,又是前一階段某種決策的結果。描述狀態(tài)的變量稱為狀態(tài)變量( ) 。狀態(tài)變量 的取值集合稱為狀態(tài)集
6、合,第k階段的狀態(tài)集合記為 ,kskskS35256321737562254321B1AB2B3C1C2C3C4ED2D1狀態(tài)的選取應當滿足無后效性無后效性:系統(tǒng)從某個階段往后的發(fā)展演變,完全由系統(tǒng)本階段所處的狀態(tài)及決策所決定,與系統(tǒng)以前的狀態(tài)及決策無關。也就是說,過去的歷史只能通過當前的狀態(tài)去影響未來的發(fā)展,當前的狀態(tài)是過去歷史的一個完整總結。只有具有無后效性的多階段決策過程只有具有無后效性的多階段決策過程才適合于用動態(tài)規(guī)劃方法求解。才適合于用動態(tài)規(guī)劃方法求解。各階段狀態(tài)集合分別為:S1=AS2=B1,B2,B3S3=C1,C2,C3,C4S4=D1,D23.決策(decision)當各階段
7、的狀態(tài)選定以后可以做出不同的決定(或選擇)從而確定下一個階段的狀態(tài),這種決定(或選擇)稱為決策。表述決策的變量稱為決策變量,常用uk(sk)表示第k階段當狀態(tài)為sk時的決策變量。實際問題中,決策變量的取值往往限制在某一范圍內,此范圍稱為允許決策集合,常用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合,uk(sk)Dk(sk)。從B2出發(fā),可以選擇C1,C2,C3,C4,即允許決策集合為:D2(B2)=C1,C2,C3,C4當決定選擇C3時,可以表示為:u2(B2)=C335256321737562254321B1AB2B3C1C2C3C4ED2D14.策略(policy) 當各個階段的決
8、策確定以后,各階段的決策形成一個決策序列,稱此決策序列為一個策略. 使系統(tǒng)達到最優(yōu)效果的策略稱為最優(yōu)策略。 在n階段決策過程中,從第k階段到終止狀態(tài)的過程,稱為k后部子過程(或稱為k子過程),k后部子過程相應的決策序列稱為k后部子過程策略,簡稱子策略,記為pk,n(sk):pk,n(sk)=uk(sk),uk+1(sk+1),un(sn)當k=1時,即由第一階段某個狀態(tài)出發(fā)做出的決策序列稱為全過程策略,簡稱策略,記為p1,n(s1):p1,n(s1)=u1(s1),u2(s2),un(sn) 5.狀態(tài)轉移方程(state transfer equation)設第k階段狀態(tài)為sk,做出的決策為u
9、k(sk),則第k+1階段的狀態(tài)sk+1隨之確定,他們之間的關系可以表示為:sk+1=Tk(sk,uk)表示從第k階段到第k+1階段狀態(tài)轉移規(guī)律的方程稱為狀態(tài)轉移方程,它反映了系統(tǒng)狀態(tài)轉移的遞推規(guī)律。狀態(tài)轉移方程為:sk+1= uk(sk)35256321737562254321B1AB2B3C1C2C3C4ED2D16.指標函數(shù)和最優(yōu)指標函數(shù)衡量所選策略優(yōu)劣的數(shù)量指標稱為指標函數(shù)。它定義在全過程和所有后部子過程,常用Vk,n表示,即:Vk,n=Vk,n(sk,uk,sk+1,sn+1)當k=1時,V1,n表示初始狀態(tài)為s1,采用策略p1,n時的指標函數(shù)值。V1,n=V1,n(s1,u1,s2
10、,sn+1)動態(tài)規(guī)劃數(shù)學模型的指標函數(shù)應該具有可分離性,并滿足遞推關系,即:Vk,n(sk,uk,sk+1,sn+1)=ksk,uk,Vk+1,n(sk+1,sn+1)在階段k狀態(tài)為sk,決策為uk(sk)時得到的反映第k階段的數(shù)量指標vk(sk,uk)稱為k階段的指標函數(shù)。在最短路線問題中,第k階段指標函數(shù)vk(sk,uk)通常也用dk(sk,uk)表示。 常見的指標函數(shù)形式有兩種:(1)任一后部子過程的指標函數(shù)是它所包含的各階段指標的和,即:Vk,n(sk,uk,sn+1)= 寫成遞推關系:Vk,n(sk,uk,sn+1)= vk(sk,uk)+ Vk+1,n(sk+1,uk+1,sn+1
11、)(2)任一后部子過程的指標函數(shù)是它所包含的各階段指標的積,即:Vk,n(sk,uk,sn+1)= 寫成遞推關系:Vk,n(sk,uk,sn+1)= vk(sk,uk)Vk+1,n(sk+1,uk+1,sn+1)nkjjjjusv),(nkjjjjusv),(指標函數(shù)的最優(yōu)值記為fk(sk),它表示從第k階段狀態(tài)sk出發(fā),采取最優(yōu)策略p*k,n(sk)到第n階段的終止狀態(tài)時的最佳指標函數(shù)值,即:當k=1時,f1(s1)就是從初始狀態(tài)s1出發(fā)到終止狀態(tài)的最優(yōu)函數(shù)。),()(1,nkknkuukksusVoptsfnkABC二、動態(tài)規(guī)劃的基本思想與基本原理二、動態(tài)規(guī)劃的基本思想與基本原理35256
12、321737562254321B1AB2B3C1C2C3C4ED2D1k=4時,狀態(tài)變量s4可取兩種狀態(tài)D1,D2:f4(D1)= d4(D1,E)=3u4(D1)=Ef4(D2)= d4(D2,E)=5u4(D2)=E55532min)(),()(),(min)(242131411313DfDCdDfDCdCfu3(C1)=D1 k=3時,狀態(tài)變量s3可取四種狀態(tài)C1,C2,C3,C4,當s3= C1時,35256321737562254321B1AB2B3C1C2C3C4ED2D1f3(C4)= d3(C4,D2)+ f4(D2)=7+5=12 u3(C4)=D2同理,從C2,C3,C4出
13、發(fā),有:u3(C2)=D2u3(C3)=D185336min)(),()(),(min)(242231412323DfDCdDfDCdCf55132min)(),()(),(min)(242331413333DfDCdDfDCdCf35256321737562254321B1AB2B3C1C2C3C4ED2D1k=2時,108455min)(),()(),(min)(232121311212CfCBdCfCBdBf10123558657min)(),()(),()(),()(),(min)(4342233322232221312222CfCBdCfCBdCfCBdCfCBdBf712252mi
14、n)(),()(),(min)(434323333232CfCBdCfCBdBfu2(B1)=C1u2(B2)=C3u2(B3)=C3按計算順序反向追蹤,得到最優(yōu)決策序列uku1(A)=B3,u2(B3)=C3,u3(C3)=D1,u4(D1)=E;最優(yōu)路線為:AB3C3D1E。 1073101102min)(),()(),()(),(min)(3231222112111BfBAdBfBAdBfBAdAfk=1時,有:u1(A)=B335256321737562254321B1AB2B3C1C2C3C4ED2D1 0)( 1 , 2 , 3 , 4 )(),(min)(5511sfksfusd
15、sfkkkkkkk或f4(s4)= d4(s4,E) 07585351012101035256321737562254321B1AB2B3C1C2C3C4ED2D1從后向前標號: 從前向后標號: 35256321737562254321B1AB2B3C1C2C3C4ED2D1100213765476最優(yōu)性原理:“作為整個過程的最優(yōu)策略具有這樣的性質:無論過去的狀態(tài)和決策如何,相對于前面的決策所形成的狀態(tài)而言,余下的決策序列必然構成最優(yōu)子策略?!焙喲灾鹤顑?yōu)策略的任何一部分子策略也必須是最優(yōu)的。例、已知網絡各段路線所需費用如圖所示,選擇從A線到B線最小費用路線,并計算總費用。2321232452
16、42613514173321256331AB動態(tài)規(guī)劃的基本思想: 1、 將多階段決策問題按照空間或時間順序劃分成相互聯(lián)系的階段,即把一個大問題分解成一族同類型的子問題,選取恰當?shù)臓顟B(tài)變量和決策變量,寫出狀態(tài)轉移方程,定義最優(yōu)指標函數(shù),寫出遞推關系式和邊界條件。 2、 從邊界條件開始,由后向前逐段遞推尋找最優(yōu),在每一個階段的計算中都要用到前一階段的最優(yōu)結果,依次進行,求得最后一個子問題的最優(yōu)解就是整個問題的最優(yōu)解。 3、 在多階段決策過程中,確定階段k的最優(yōu)決策時,不是只考慮本階段最優(yōu),而是要考慮本階段及其所有后部子過程的整體最優(yōu),也就是說,它是把當前效益和未來效益結合起來考慮的一種方法。第三節(jié)
17、第三節(jié) 動態(tài)規(guī)劃模型及求解方法動態(tài)規(guī)劃模型及求解方法一、動態(tài)規(guī)劃的數(shù)學模型一、動態(tài)規(guī)劃的數(shù)學模型2. 建立動態(tài)規(guī)劃模型的步驟(1)劃分階段(2)正確選擇狀態(tài)變量sk(描述演變特性、無后效性、遞推性)(3)確定決策變量uk及允許決策集合Dk(sk)(4)確定狀態(tài)轉移方程sk+1=Tk(sk,uk)(5)確定階段指標函數(shù)和最優(yōu)指標函數(shù)(6)建立動態(tài)規(guī) 劃基本方程。 10)( 1 , 1, )(),()(1111)(或nnkkkkksDukksfnnksfusvoptsfkkk二、動態(tài)規(guī)劃的求解方法二、動態(tài)規(guī)劃的求解方法例例7.4 用動態(tài)規(guī)劃方法解下列非線性規(guī)劃問題3 , 2 , 1 0 max32
18、13221ixcxxxxxxzi解解按問題的變量個數(shù)劃分階段,k=1,2,3設狀態(tài)變量為s1,s2,s3,s4并記s1c取問題中的變量x1,x2,x3為決策變量狀態(tài)轉移方程為:s3=x3s3+x2=s2s2+x1=s1c允許決策集合為:x3=s30 x2s20 x1s1階段指標函數(shù)為:v1(x1)=x1 v2(x2)=x22 v3(x3)=x3最優(yōu)指標函數(shù)fk(sk)表示從第k階段初始狀態(tài)sk出發(fā)到第3階段所得到的最大值,則動態(tài)規(guī)劃基本方程為:1)(1 , , 2 , 3 )()(max)(4411)(sfksfxvsfkkkksDxkkkkk334433)(33)(max)()(max)(3
19、3333sxsfxvsfsxsDx)(max)(max)()(max)(2222032203322)(222222222xsxsxsfxvsfsxsxsDx032222222xsxdxdh22222262xsdxhd02322222222ssxdxhd2232sx 32222222274)32()32()(sssssf2*232sx k=3時,k=2時,x3*=s3令h2(s2,x2)=x22(s2x2)解得:x2=0(舍)2232sx 是極大值點。)(274max)274(max)()(max)(3111032102211)(111111111xsxsxsfxvsfsxsxsDx0) 1()
20、(2712)(274211131111xsxxsdxdh)2)(2724)(2724)(2712) 1()(271211111112112112112sxxsxsxxsxsdxhd02794121112112ssxdxhd41311111641)41(27441)(sssssf1*141sx k=1時,3111111)(274),(xsxxsh令1141sx 解得:x1=s1(舍)1141sx 是極大值點。反向追蹤得各階段最優(yōu)決策及最優(yōu)值:csx41411*1411641)(csfcxss43*112csx21322*233222161274)(cssfcxss41*223csx413*3cs
21、sf41)(3334*3*2*1641,41,21,41czcxcxcxs1=c所以最優(yōu)解為:)641(max)(max41011011ssfcscs411641)(csf第四節(jié)第四節(jié) 動態(tài)規(guī)劃的應用舉例動態(tài)規(guī)劃的應用舉例一、資源分配問題一、資源分配問題 假設有一種資源,數(shù)量為a,將其分配給n個使用者,分配給第i個使用者數(shù)量xi時,相應的收益為gi(xi),問如何分配使得總收入最大?數(shù)學模型為:nixaxxxxgxgxgzinnn, 2 , 1 0 )()()( max212211解解 :按變量個數(shù)劃分階段,k=1,2,n;設決策變量uk=xk,表示分配給第k個使用者的資源數(shù)量;設狀態(tài)變量為s
22、k,表示分配給第k個至第n個使用者總的資源數(shù)量;狀態(tài)轉移方程:sk+1=skxk,其中s1=a;允許決策集合:Dk(sk)=xk|0 xksk階段指標函數(shù):vk(sk,uk)=gk(xk)表示分配給第k個使用者數(shù)量xk時的收益;最優(yōu)指標函數(shù)fk(sk)表示以數(shù)量sk的資源分配給第k個至第n個使用者所得到的最大收益,則動態(tài)規(guī)劃基本方程為:0)(1 , )()(max)(11110nnkkkksxkksfnksfxgsfkk例例7.7 某公司打算在3個不同的地區(qū)設置4個銷售點,根據市場部門估計,在不同地區(qū)設置不同數(shù)量的銷售點每月可得到的利潤如表所示。試問在各地區(qū)如何設置銷售點可使每月總利潤最大。地
23、區(qū)銷售點01234101625303220121721223 010141617解解 :將問題分為3個階段,k=1,2,3;決策變量xk表示分配給第k個地區(qū)的銷售點數(shù);狀態(tài)變量為sk表示分配給第k個至第3個地區(qū)的銷售點總數(shù);狀態(tài)轉移方程:sk+1=skxk,其中s1=4;允許決策集合:Dk(sk)=xk|0 xksk階段指標函數(shù):gk(xk)表示xk個銷售點分配給第k個地區(qū)所獲得的利潤;最優(yōu)指標函數(shù)fk(sk)表示將數(shù)量為sk的銷售點分配給第k個至第3個地區(qū)所得到的最大利潤,動態(tài)規(guī)劃基本方程為:0)(1 , 2 , 3 )()(max)(4410sfkxsfxgsfkkkkksxkkkk)(m
24、ax)(333333xgsfsx k=3時,g3(x3) f3(s3) x3* 0123400 001 10 1012 14 1423 16 1634 1717 4 fx3s3k=2時,)()(max)(2232202222xsfxgsfsxg2(x2)+f3(s2x2) f2(s2) x2* 0123400 0010+1012+0 12120+1412+1017+0 22130+1612+14 17+1021+0 2724 0+17 12+16 17+14 21+10 22+0 31 2,3 fx2s2)()(max)(1121101111xsfxgsfsx)4()(max)(1211401
25、11xfxgsfxk=1時,g1(x1)+f2(s1x1) f1(s1) x1* 012344 0+31 16+27 25+22 30+12 32+0 47 2fx1s1最優(yōu)解為:x1*=2,x2*=1,x3*=1,f1(4)=47,即在第1個地區(qū)設置2個銷售點,第2個地區(qū)設置1個銷售點,第3個地區(qū)設置1個銷售點,每月可獲利潤47。 例例7.8 機器負荷問題某工廠有100臺機器,擬分四期使用,每一期都可在高、低兩種不同負荷下進行生產。若把x臺機器投入高負荷下進行生產,則在本期結束時將有1/3x臺機器損壞報廢;余下的機器全部投入低負荷下進行生產,則在期末有1/10的機器報廢。如果高負荷下生產時每
26、臺機器可獲利潤為10,低負荷下生產時每臺機器可獲利潤為7,問怎樣分配機器使四期的總利潤最大? 解解 將問題按周期分為4個階段,k=1,2,3,4;狀態(tài)變量sk表示第k階段初完好的機器數(shù),s1=100,0sk100;決策變量xk表示第k階段投入高負荷下生產的機器數(shù),則skxk表示第k階段投入低負荷下生產的機器數(shù);允許決策集合:Dk(sk)=xk|0 xksk狀態(tài)轉移方程:sk+1=Tk(sk,xk),第k+1階段初擁有的完好機器數(shù)sk+1為:階段指標函數(shù):vk(sk,xk)=10 xk+7(skxk)表示第k階段所獲得的利潤;最優(yōu)指標函數(shù)fk(sk)表示從第k階段初完好機器數(shù)為sk至第四階段的最
27、大利潤,動態(tài)規(guī)劃基本方程為:)(109321kkkkxsxs0)(1 , 2 , 3 , 4 )(),(max)(55110sfksfxsvsfkkkkksxkkkk444044404410)73(max)(710max)(4444ssxxsxsfsxsx333033333304333044333033350 )1632(max )(1093210)(710max 10)(710max )()(710max)(33333333ssxxsxxsxsxsxsfxsxsfsxsxsxsxk=4時,x4*=s4k=3時,x3*=s322202222220322203322202222 )9822(ma
28、x )(10932350)(710max 350)(710max )()(710max)(22222222sxsxsxxsxsxsxsfxsxsfsxsxsxsx1110111111021110221110115134 )15325134(max )(1093222)(710max 22)(710max )()(710max)(11111111sxsxsxxsxsxsxsfxsxsfsxsxsxsxk=2時,k=1時,x2*=0 x1*=0因為s1=100,所以f1(100)=2680,逆向追蹤得:90)(10932*11*12xsxs81)(10932*22*23xsxs54)(10932*
29、33*34xsxsx1*=0s1=100 x2*=0 x3*=s3=81x4*=s4=54 第1,2期把全部完好機器投入低負荷下生產,第3,4期把全部完好機器投入高負荷下生產所得利潤最大。二、生產計劃問題二、生產計劃問題例例7.9 (生產庫存問題)某工廠要對一種產品制定今后四個時期的生產計劃,據估計在今后四個時期內,市場對該產品的需求量分別為2,3,2,4單位,假設每批產品固定成本為3千元,若不生產為0,每單位產品成本為1千元,每個時期最大生產能力不超過6個單位,每期期末未出售產品,每單位需付存貯費0.5千元,假定第1期初和第4期末庫存量均為0,問該廠如何安排生產與庫存,可在滿足市場需求的前提
30、下總成本最小。解解 以每個時期作為一個階段,k=1,2,3,4;決策變量xk表示第k階段生產的產品數(shù);狀態(tài)變量sk表示第k階段初的庫存量;以dk表示第k階段的需求,則狀態(tài)轉移方程:sk+1=sk+xkdk k=4,3,2,1s1=0,s5=0;允許決策集合Dk(sk)的確定:xk的下限為max(0,dksk);xk的上限為min( ,6),故有:kkjjsd 4kkjjsd 4Dk(sk)=xk| max(0,dksk)xkmin( ,6)階段指標函數(shù)rk(sk,xk)表示第k期的生產費用與存貯費用之和: 6 , 5 , 4 , 3 , 2 , 1 5 . 030 5 . 0),(kkkkkk
31、kkxsxxsxsr最優(yōu)指標函數(shù)fk(sk)表示第k期庫存為sk到第4期末的生產與存貯最低費用,動態(tài)規(guī)劃基本方程為:0)(1 , 2 , 3 , 4 )(),(min)(5511)(sfksfxsrsfkkkkksDxkkkkks10 D1(s1)2,3,4,5,6 s201234 D2(s2) 3,4,5,62,3,4,5,6 1,2,3,4,5,6 0,1,2,3,4,5,60,1,2,3,4,5 s30123456D3(s3)2,3,4,5,6 1,2,3,4,50,1,2,3,40,1,2,30,1,20,10s401234 D4(s4)43210 kkjjsd 4Dk(sk)=xk|
32、 max(0,dksk)xkmin( ,6)例例7-9 (庫存銷售問題)設某公司計劃在1至4月份從事某種商品經營。已知倉庫最多可存儲600件這種商品,已知1月初存貨200件,根據預測知1至4月份各月的單位購貨成本及銷售價格如表7-13所示,每月只能銷售本月初的庫存,當月進貨供以后各月銷售,問如何安排進貨量和銷售量,使該公司四個月獲得利潤最大(假設四月底庫存為零)。月份購貨成本C銷售價格P14045238423403944244解解 按月份劃分階段,k=1,2,3,4;狀態(tài)變量sk表示第k月初的庫存量,s1=200,s5=0;決策變量 xk表示第k月售出的貨物數(shù)量,yk表示第k月購進的貨物數(shù)量;
33、狀態(tài)轉移方程:sk+1=sk+ykxk;允許決策集合:0 xksk,0yk600(skxk);階段指標函數(shù)為:pkxkckyk表示k月份的利潤,其中pk為第k月份的單位銷售價格,ck為第k月份的單位購貨成本;最優(yōu)指標函數(shù)fk(sk)表示第k月初庫存為sk時從第k月至第4月末的最大利潤,則動態(tài)規(guī)劃基本方程為: 0)(1 , 2 , 3 , 4 )(max)(5511)(60000sfksfycxpsfkkkkkkxsysxkkkkkkk444)(600004444)4244(max)(44444syxsfxsysx)4544(max )(444039max )(4039max)(333)(600
34、0033333)(600004433)(6000033333333333333333yxsxysyxsfyxsfxsysxxsysxxsysx0,600 4544 max3333333333yxsyxsxyxsz k=4時,x4*=s4y4*=0k=3時,As3600y3x30600s3)24002240(max 2400)(403842max )(3842max)(222)(6000022222)(600003322)(6000022222222222222222yxsxysyxsfyxsfxsysxxsysxxsysx)36002342(max 3600)(424045max )(4045
35、max)(111)(6000011111)(600002211)(6000011111111111111111yxsxysyxsfyxsfxsysxxsysxxsysxk=2時,類似地求得:x2*=s2,y2*=600,f2(s2)=42s2+3600k=1時,類似地求得:x1*=s1,y1*=600,f1(s1)=45s1+4800=13800逆向追蹤得各月最優(yōu)購貨量及銷售量:x1*=s1=200y1*=600;x2*=s2=s1+ y1*x1*=600y2*=600;x3*=0y3*=600s3=0 x4*=s4=(s3+ y3*x3*)=600y4*=0即1月份銷售200件,進貨600件
36、,2月份銷售600件,進貨600件,3月份銷售量及進貨量均為0,4月份銷售600件,不進貨,可獲得最大總利潤13800。 三、背包問題三、背包問題 有人攜帶背包上山,其可攜帶物品的重量限度為a公斤,現(xiàn)有n種物品可供選擇,設第i種物品的單件重量為ai公斤,其在上山過程中的價值是攜帶數(shù)量xi的函數(shù)ci(xi),問應如何安排攜帶各種物品的數(shù)量,使總價值最大。數(shù)學模型為: ), 2 , 1(0 )()()( max22112211nixaxaxaxaxcxcxczinnnn且為整數(shù)按照裝入物品的種類劃分階段,k=1,2,n;狀態(tài)變量sk表示裝入第k種至第n種物品的總重量;決策變量xk表示裝入第k種物品
37、的件數(shù);狀態(tài)轉移方程為:sk+1=skakxk允許決策集合為:其中 表示不超過 的最大整數(shù);階段指標函數(shù)ck(xk)表示第k階段裝入第k種商品xk件時的價值;最優(yōu)指標函數(shù)fk(sk)表示第k階段裝入物品總重量為sk時的最大價值,動態(tài)規(guī)劃基本方程為:kkaskkas為整數(shù)kkkkkkkxasxxsD,0)(0)(1 , 1, )()(max)(1111 , 1 , 0nnkkkkasxkksfnnksfxcsfkkk例例7.11 某工廠生產三種產品,各產品重量與利潤關系如表所示,現(xiàn)將此三種產品運往市場銷售,運輸能力總重量不超過6噸,問如何安排運輸使總利潤最大?種類123單位重量(噸)234單位利
38、潤(元)80130180解解 設xi為裝載第i種貨物的件數(shù),i=1,2,3該問題數(shù)學模型為:) 3 , 2 , 1(06432 18013080 max321321ixxxxxxxzi且為整數(shù)k=3時,)180(max)(34 , 1 , 03333xsfsxc3(x3) f3(s3) x3* 010,1,2,30 004,5,6 0180180 1 fx3s3k=2時,)3(130max )(130max)(22323 , 1 , 03323 , 1 , 0222222xsfxsfxsfsxsxc2(x2)+ f3(s23 x2) f2(s2) x2* 0120,1,20+0 0030+01
39、30+0 13014,50+180130+0 18006 0+180130+0260+0260 2 fx2s2c1(x1)+ f2(s12 x1) f1(s1) x1* 01236 0+26080+180160+0240+0260 0,1 fx1s1k=1時,)2(80max )(80max)(11213 , 2, 1 , 02213 , 2, 1 , 01111xsfxsfxsfxx四、復合系統(tǒng)工作可靠性問題四、復合系統(tǒng)工作可靠性問題 設第i(i=1,2,n)個部件上裝有ui個備用元件,正常工作的概率為pi(ui),則整個系統(tǒng)正常工作的可靠性為裝第i個部件的費用為ci,重量為wi,要求總費用不超過
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025山西勞動合同范文
- 2025工程勞務分包合同范本
- 2025貨物委托代理合同例文
- 真空電容器生產加工項目可行性研究報告
- (規(guī)劃可研)蠟油渣油項目可行性研究報告
- 2024年02月中國進出口銀行博士后科研工作站2024年度招收博士后研究人員筆試歷年參考題庫附帶答案詳解
- 移植排斥反應預后評估-洞察分析
- 尾礦中稀貴金屬提取-洞察分析
- 維綸纖維在電子領域的應用-洞察分析
- 2025委托加工合同食品類樣本
- 2023年普通高等學校招生“圓夢杯”統(tǒng)一模擬考試數(shù)學試題+含答案
- 《麥當勞戰(zhàn)略管理5800字(論文)》
- 工程倫理分析-切爾諾貝利
- 外墻用水泥纖維板接縫位置開裂問題及處理
- 超星爾雅學習通【中國近現(xiàn)代史綱要(首都師范大學)】章節(jié)測試含答案
- 金色年終匯報PPT模板
- 沭陽縣國土空間總體規(guī)劃(2021-2035)草案公示1
- C++初學者入門全篇
- 哈爾濱市商品房買賣合同書(最終定稿)
- 警犬行為理論考試題庫(含答案)
- 財政與金融基礎知識全套教學課件(中職)
評論
0/150
提交評論