動態(tài)規(guī)劃習題

1、第七章 動態(tài)規(guī)劃規(guī)劃問題的最終目的就是確定各決策變量的取值,以使目標函數(shù)到達極大或極小.在線性規(guī)劃和非線性規(guī)劃中,決策變量都是以集合的形式被一次性處理的；然而,有時我們也會面對決策變量需分期、分批處理的多階段決策問題.所謂多階段決策問題是指這樣一類活動過程：它可以分解為假設(shè)干個互相聯(lián)系的階段,在每一階段分別對應著一組可供選取的決策集合；即構(gòu)成過程的每個階段都需要進行一次決策的決策問題.將各個階段的決策綜合起來構(gòu)成一個決策序列,稱為一個策略.顯然,由于各個階段選取的決策不同,對應整個過程可以有一系列不同的策略.當過程采取某個具體策略時,相應可以得到一個確定的效果,采取不同的策略,就會得到不同的效

2、果.多階段的決策問題,就是要在所有可能采取的策略中選取一個最優(yōu)的策略,以便得到最正確的效果.動態(tài)規(guī)劃(dynamic programming )同前面介紹過的各種優(yōu)化方法不同,它不是一種算法,而是考察問題的一種途徑.動態(tài)規(guī)劃是一種求解多階 段決策問題的系統(tǒng)技術(shù),可以說它橫跨整個規(guī)劃領(lǐng)域(線性規(guī)劃和非線性規(guī)劃).當然,由于動態(tài)規(guī)劃不是一種特定的算法,因而它不象線性規(guī)劃那樣有一個標準的數(shù)學表達式和明確定 義的一組規(guī)那么,動態(tài)規(guī)劃必須對具體問題進行具體的分析處理.在多階段決策問題中,有些問題對階段的劃分具有明顯的時序性,動態(tài)規(guī)劃的“動態(tài)"二字也由此而得名.動態(tài)規(guī)劃的主要創(chuàng)始人是美國數(shù)學家貝

3、爾曼 (Bellman).20世紀40年代末50年代初,當時在蘭德公司(Rand Corporation )從事研究工作的貝爾曼首先提出了動態(tài)規(guī)劃的概念.1957年貝爾曼發(fā)表了數(shù)篇研究論文,并出版了他的第一部著作?動態(tài)規(guī)劃?.該著作成為了當時唯一的進一步研究和應用動態(tài)規(guī)劃的理論源泉.1961年貝爾曼出版了他的第二部著作,并于 1962年同杜瑞佛思 (Dreyfus)合作出版了第三部著作.在貝爾曼及其助手們致力于開展和推廣這一技術(shù)的同時, 其他一些學者也對動態(tài)規(guī)劃的開展做出了重大的奉獻,其中最值得一提的是愛爾思(Aris)和梅特頓(Mitten).愛爾思先后于1961年和1964年出版了兩部關(guān)于

4、動態(tài)規(guī)劃的著作,并 于1964年同尼母霍思爾(Nemhauser)、威爾德(Wild)一道創(chuàng)立了處理分枝、循環(huán)性多階段 決策系統(tǒng)的一般性理論.梅特頓提出了許多對動態(tài)規(guī)劃后來開展有著重要意義的根底性觀 點,并且對明晰動態(tài)規(guī)劃路徑的數(shù)學性質(zhì)做出了巨大的奉獻.動態(tài)規(guī)劃在工程技術(shù)、經(jīng)濟治理等社會各個領(lǐng)域都有著廣泛的應用,并且獲得了顯著的效果.在經(jīng)濟治理方面,動態(tài)規(guī)劃可以用來解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)調(diào)度問 題、庫存治理問題、排序問題、設(shè)備更新問題以及生產(chǎn)過程最優(yōu)限制問題等,是經(jīng)濟治理中一種重要的決策技術(shù).許多規(guī)劃問題用動態(tài)規(guī)劃的方法來處理,常比線性規(guī)劃或非線性規(guī)劃更有效.特別是對于離散的問題

5、,由于解析數(shù)學無法發(fā)揮作用,動態(tài)規(guī)劃便成為了一種非常 有用的工具.動態(tài)規(guī)劃可以根據(jù)決策過程的演變是否確定分為確定性動態(tài)規(guī)劃和隨機性動態(tài)規(guī)劃；也可以根據(jù)決策變量的取值是否連續(xù)分為 連續(xù)性動態(tài)規(guī)劃和離散性動態(tài)規(guī)劃.本教材主要 介紹動態(tài)規(guī)劃的根本概念、理論和方法,并通過典型的案例說明這些理論和方法的應用.§ 7.1 動態(tài)規(guī)劃的根本理論1.1 多階段決策過程的數(shù)學描述有這樣一類活動過程,其整個過程可分為假設(shè)干相互聯(lián)系的階段,每一階段都要作出相應 的決策,以使整個過程到達最正確的活動效果.任何一個階段(stage ,即決策點)都是由輸入(input )、決策(decision )、狀態(tài)轉(zhuǎn)移律(

6、transformation function )和輸出(output ) 構(gòu)成的,如圖7-1 (a)所示.其中輸入和輸出也稱為狀態(tài)( state ),輸入稱為輸入狀態(tài),輸 出稱為輸出狀態(tài).由于每一階段都有一個決策,所以每一階段都應存在一個衡量決策效益大小的指標函數(shù) 這一指標函數(shù)稱為 階段指標函數(shù),用gn表示.顯然gn是狀態(tài)變量 &和決策變量dn的函數(shù), 即gn= r (S, dn),如圖7-1 (b)所示.顯然,輸出是輸入和決策的函數(shù),即：Sn1f(Sn,dn)(7-1)式(71)即為狀態(tài)轉(zhuǎn)移律.在由N個階段構(gòu)成的過程里,前一個階段的輸出即為后一個階段的輸入.1.2 動態(tài)規(guī)劃的根本概

7、念動態(tài)規(guī)劃的數(shù)學描述離不開它的一些根本概念與符號,因此有必要在介紹多階段決策 過程的數(shù)學描述的根底上,系統(tǒng)地介紹動態(tài)規(guī)劃的一些根本概念.1 .階段(stage)階段是過程中需要做出決策的決策點.描述階段的變量稱為階段變量,常用k來表示.階段的劃分一般是根據(jù)時間和空間的自然特征來進行的,但要便于將問題的過程轉(zhuǎn)化為多階段決策的過程.對于具有N個階段的決策過程,其階段變量k=1,2,N2 .狀態(tài)(state )狀態(tài)表示每個階段開始所處的自然狀況或客觀條件,它描述了研究問題過程的狀況.狀態(tài)既反映前面各階段系列決策的結(jié)局,又是本階段決策的一個出發(fā)點和依據(jù)；它是各階段信息的傳遞點和結(jié)合點.各階段的狀態(tài)通常

8、用狀態(tài)變量G來加以描述.作為狀態(tài)應具有這樣的性質(zhì)：如果某階段狀態(tài)給定后,那么該階段以后過程的開展不受此階段以前各階段狀態(tài)的影 響.換句話說,過程的歷史只能通過當前的狀態(tài)來影響未來,當前的狀態(tài)是以往歷史的一個 總結(jié).這個性質(zhì)稱為 無后效性 (the future is independent of the past )或健忘性(the process is forgetful ).3 .決策(decision )決策是指決策者在所面臨的假設(shè)干個方案中做出的選擇.決策變量dk表示第k階段的決策.決策變量dk的取值會受到狀態(tài) &的某種限制,用 D(8)表示第k階段狀態(tài)為8時決策 變量允許的取

9、值范圍,稱為允許決策集合,因而有dk (G) 口(&).4 .狀態(tài)轉(zhuǎn)移律(transformation function )狀態(tài)轉(zhuǎn)移律是確定由一個狀態(tài)到另一狀態(tài)演變過程的方程,這種演變的對應關(guān)系記為 &+1 = Tk (& , dk).5 .策略(policy )與子策略(sub-policy )由所有階段決策所組成的一個決策序列稱為一個策略,具有N個階段的動態(tài)規(guī)劃問題的策略可表不為：d1(S1),d2(S2), ,dN(SN )從某一階段開始到過程終點為止的一個決策子序列,稱為過程子策略或子策略.從第k個階段起的一個子策略可表示為：dk(Sk),dki(Sk 1),

10、En(Sn)6 .指標函數(shù)指標函數(shù)有階段指標函數(shù)和過程指標函數(shù)之分.階段指標函數(shù)是對應某一階段決策的 效率度量,用gk= r(&, dk)來表示；過程指標函數(shù)是用來衡量所實現(xiàn)過程優(yōu)劣的數(shù)量指標,是定義在全過程(策略)或后續(xù)子過程(子策略)上的一個數(shù)量函數(shù),從第 k個階段起的一 個子策略所對應的過程指標函數(shù)常用G,n來表示,即：Gk,NR(Sk,dk,Sk1,dk1, 04)構(gòu)成動態(tài)規(guī)劃的過程指標函數(shù),應具有可分性并滿足遞推關(guān)系；即：Gk,N g k Gk 1,N這里的表示某種運算,最常見的運算關(guān)系有如下二種：(1 )過程指標函數(shù)是其所包含的各階段指標函數(shù)的“和,即：NGk,N g jj

11、 k于是Gk,Ng k Gk 1,N(2)過程指標函數(shù)是其所包含的各階段指標函數(shù)的“積,即：N Gk,Ng jjk于是Gk,N g k Gk 1,N7.最優(yōu)指標函數(shù)從第k個階段起的最優(yōu)子策略所對應的過程指標函數(shù)稱為最優(yōu)指標函數(shù),可以用式(7-2)加以表不：fk(Sk)opt g k gk 1gN(72)dkN其中“opt是最優(yōu)化“ optimization 的縮寫,可根據(jù)題意取最大“maX'或最小" min".在不同的問題中,指標函數(shù)的含義可能是不同的,它可能是距離、利潤、本錢、產(chǎn)量或資源量等.1.3動態(tài)規(guī)劃的數(shù)學模型動態(tài)規(guī)劃的數(shù)學模型除包括式7-2外,還包括階段的

12、劃分、各階段的狀態(tài)變量和決 策變量的選取、允許決策集合和狀態(tài)轉(zhuǎn)移律確實定等.如何獲得最優(yōu)指標函數(shù)呢？ 一個N階段的決策過程,具有如下一些特性：（1） 剛好有N個決策點；（2） 對階段k而言,除了其所處的狀態(tài) Sk和所選擇的決策dk外,再沒有任何其它因 素影響決策的最優(yōu)性了；（3） 階段k僅影響階段k 1的決策,這一影響是通過 Sk1來實現(xiàn)的；（4） 貝爾曼Bellman最優(yōu)化原理：在最優(yōu)策略的任意一階段上,無論過去的狀態(tài) 和決策如何,對過去決策所形成的當前狀態(tài)而言,余下的諸決策必須構(gòu)成最優(yōu) 子策略.根據(jù)貝爾曼Bellman最優(yōu)化原理,可以將式7-2 表示為遞推最優(yōu)指標函數(shù)關(guān)系式73或式7-4

13、:fkSkoptgkgk19noptgkfk1S73dkNdkfkSkoptgkgk1gNoptgkfkNSkl7-4dkNdk利用式7-3和式74可表示出最后一個階段第N個階段,即k=ND的最優(yōu)指標函數(shù)：fN Sn optgN fN iSn 175dNfN Sn optgN fN iSn 17-6dN其中fN iSn i稱為邊界條件.一般情況下,第 N階段的輸出狀態(tài) Sn 1已經(jīng)不再影響本過 程的策略,即式75中的邊界條件fN iSn i 0,式7-6中的邊界條件fN iSn 1 1 ; 但當問題第N階段的輸出狀態(tài)Sn 1對本過程的策略產(chǎn)生某種影響時,邊界條件fN iSn i就要根據(jù)問題的具

14、體情況取適當?shù)闹?這一情況將在后續(xù)例題中加以反映.邊界條件fN iSn i,利用式73或式7-4 即可求得最后一個階段的最優(yōu)指標函數(shù)£nSn;有了 fNSN,繼續(xù)利用式7-3或式7-4即可求得最后兩個階段的 最優(yōu)指標函數(shù)fN iSn 1；有了 fN 1Sn 1,進一步又可以求得最后三個階段的最優(yōu)指標函 數(shù)fN 2Sn 2；反復遞推下去,最終即可求得全過程 N個階段的最優(yōu)指標函數(shù) 36,從 而使問題得到解決.由于上述最優(yōu)指標函數(shù)的構(gòu)建是按階段的逆序從后向前進行的,所以也稱為動態(tài)規(guī)劃的逆序算法.通過上述分析可以看出,任何一個多階段決策過程的最優(yōu)化問題,都可以用非線性規(guī)劃特殊的可以用線性規(guī)

15、劃模型來描述；因此,從原那么上講,一般也可以用非線性規(guī)劃或 線性規(guī)劃的方法來求解.那么利用動態(tài)規(guī)劃求解多階段決策過程有什么優(yōu)越性、又有什么 局限性呢？動態(tài)規(guī)劃的優(yōu)點：第一,求解更容易、效率更高 .動態(tài)規(guī)劃方法是一種逐步改善法,它 把原問題化成一系列結(jié)構(gòu)相似的最優(yōu)化子問題,而每個子問題的變量個數(shù)比原問題少得多, 約束集合也簡單得多,故較易于確定最優(yōu)解.第二,解的信息更豐富.非線性規(guī)劃或線性規(guī)劃的方法是對問題的整體進行一次性求解的,因此只能得到全過程的解；而動態(tài)規(guī)劃方法是將過程分解成多個階段進行求解的,因此不僅可以得到全過程的解,同時還可以得到所有子過程的解.動態(tài)規(guī)劃的缺點：第一,沒有一個統(tǒng)一的標

16、準模型.由于實際問題不同,其動態(tài)規(guī)劃模型也就各有差異,模型構(gòu)建存在一定困難.第二,應用條件苛刻.由于構(gòu)造動態(tài)規(guī)劃模型狀態(tài)變量必須滿足“無后效性條件,這一條件不僅依賴于狀態(tài)轉(zhuǎn)移律,還依賴于允許決策集合和指標函數(shù)的結(jié)構(gòu),不少實際問題在取其自然牛I征作為狀態(tài)變量時并不滿足這一條件,這就降低了動態(tài)規(guī)劃的通用性.第三,狀態(tài)變量存在“維數(shù)障礙.最優(yōu)指標函數(shù)fk sk是狀態(tài)變量的函數(shù),當狀態(tài)變量的維數(shù)增加時,最優(yōu)指標函數(shù)的計算量將成指數(shù)倍增長；因此,無論是手工計算還是電算“維數(shù)障礙都是無法完全克服的.§ 7.2確定性動態(tài)規(guī)劃問題確定性動態(tài)規(guī)劃問題即階段的輸出狀態(tài)完全由其輸入狀態(tài)和決策所決定的動態(tài)規(guī)

17、劃問 題.確定性動態(tài)規(guī)劃解決的問題可能包含經(jīng)濟治理的方方面面,可以是最短路線問題,可以是資源配置問題,也可以是其他的規(guī)劃優(yōu)化問題.最短路線問題直觀、 具體地演示了動態(tài)規(guī)劃的根本概念和根本步驟；因此,讓我們首先來分析一下最短路線問題.2-1最短路線問題例7-1美國黑金石油公司The Black Gold Petroleum Company 最近在阿拉斯 力口Alaska的北斯洛波North Slope 發(fā)現(xiàn)了大的石油儲量.為了大規(guī)模開發(fā)這一油田, 首先必須建立相應的輸運網(wǎng)絡(luò),使北斯洛波生產(chǎn)的原油能運至美國的3個裝運港之一.在油田的集輸站結(jié)點C與裝運港結(jié)點Pi、P2、R之間需要假設(shè)干個中間站,中間

18、站之間的 聯(lián)通情況如圖72所示,圖中線段上的數(shù)字代表兩站之間的距離單位：10千米.試確定一最正確的輸運線路,使原油的輸送距離最短.解：最短路線有一個重要性質(zhì),即如果由起點 A經(jīng)過B點和C點到達終點D是一條最短路 線,那么由B點經(jīng)C點到達終點D一定是B到D的最短路貝爾曼最優(yōu)化原理.此性質(zhì)用反證 法很容易證實,由于如果不是這樣 ,那么從B點到D點有另一條距離更短的路線存在,不妨假 設(shè)為B- P- D;從而可知路線 A-B- P-D比原路線 A-B-C- D距離短,這與原路線 A-B-C D 是最短路線相矛盾,性質(zhì)得證.根據(jù)最短路線的這一性質(zhì),尋找最短路線的方法就是從最后階段開始,由后向前逐步遞推求

19、出各點到終點的最短路線,最后求得由始點到終點的最短路；1點逐段向始點方向?qū)ふ易疃搪肪€的一種方法.根據(jù)動態(tài)規(guī)劃的方法,段,即階段變量k 1,2,3,4;取過程在各階段所處的位置為狀態(tài)變量I M3dL 80c1M33iTXMJRk=1k=2k=3k=4如動態(tài)規(guī)劃的方法是從終將此過程劃分為 4個階Sk ,按逆序算法求解.歹當k 4時：由結(jié)點Mi到達目的地有兩條路線可以選擇,即選擇 R或故:8f4(S4 M31) min 6選才i P26由結(jié)點M32到達目的地有三條路線可以選擇,即選擇R、P2或 P3；故:4選才i P2Pi、P2或 P3；故:選才i P3f4(S4 M32) min 337由結(jié)點M3

20、到達目的地也有三條路線可以選擇,即選擇7f4(S4 M33) min 655由結(jié)點M4到達目的地有兩條路線可以選擇,即選擇P2或P3；故:一一、 .3八,一f4(S4 M34) min 3選才P P24當k 3時：由結(jié)點Mi到達下一階段有三條路線可以選擇,即選擇Mi、M2或M3；故:10 6f3(S3 M21) min 7 310選才i M265由結(jié)點Mb到達下一階段也有三條路線可以選擇,即選擇 M1、Mb或M3；故:9 6f3(S3M22) min 7 310選才i M2或 M355由結(jié)點M3到達下一階段也有三條路線可以選擇,即選擇M2、M33或M4；故:11 3f3(S3M23) min

21、4 563當k 2時:由結(jié)點Mi到達下一階段有兩條路線可以選擇,即選擇Mi或M2；故:8 10f2(S2 M11) min16選才i g6 10由結(jié)點M2到達下一階段也有兩條路線可以選擇,即選擇M2或M3;故:9 10f2(S2 M12) min19選才i M211 9當k 1時：由結(jié)點C到達下一階段有兩條路線可以選擇,即選擇M1或M2；故:3(5C)12 16 min可以得到兩條最正確的輸運線路: 280千米.C-M110 19從而通過順序(計算的反順序)追蹤(黑體標示)M2 M2 P2； C M1 M2M13 P3.最短的輸送距離是2-2資源分配問題所謂資源分配問題,就是將一定數(shù)量的一種或

22、假設(shè)干種資源(如原材料、機器設(shè)備、資金、勞動力等)恰當?shù)胤峙浣o假設(shè)干個使用者,以使資源得到最有效地利用.設(shè)有 m種資源,總量 分別為bi (i = 1,2 , m),用于生產(chǎn)n種產(chǎn)品,假設(shè)用Xj代表用于生產(chǎn)第j種產(chǎn)品的第i種資源的數(shù)量(j = 1,2,n),那么生產(chǎn)第j種產(chǎn)品的收益是其所獲得的各種資源數(shù)量的函數(shù),即gj =f(X1j,X2j,Xmj).由于總收益是n種產(chǎn)品收益的和,此問題可用如下靜態(tài)模型加以描述：nmax zg jj 1nXijbi (i 1,2,m)j 1Xij0 (i 1,2,m; j 1,2, n)假設(shè)Xj是連續(xù)變量,當 g = f(X*X2j, , Xmj)是線性函數(shù)時

23、,該模型是線性規(guī)劃模型； 當g = f (X1j,Xj, , Xmj)是非線性函數(shù)時,該模型是非線性規(guī)劃模型.假設(shè) 為是離散變量 或(和)卬=f(X1j,X2j, , Xmj)是離散函數(shù)時,此模型用線性規(guī)劃或非線性規(guī)劃來求解都 將是非常麻煩的.然而在此情況下,由于這類問題的特殊結(jié)構(gòu),可以將它看成為一個多階段決策問題,并利用動態(tài)規(guī)劃的遞推關(guān)系來求解.本教材只考慮一維資源的分配問題,設(shè)狀態(tài)變量&表示分配于從第 k個階段至過程最終(第N個階段)的資源數(shù)量,即第 k個階段初資源的擁有量；決策變量Xk表示第k個階段資 源的分配量.于是有狀態(tài)轉(zhuǎn)移律：Sk1SkXk允許決策集合Dk(Sk) Xk|0

24、 XkSk最優(yōu)指標函數(shù)(動態(tài)規(guī)劃的逆序遞推關(guān)系式)：fk(Sk)maxgk(Xk) fki(Ski)(k N,N 1,N 2, ,1)0 xk SkfN 1(Sn 1)0利用這一遞推關(guān)系式,最后求得的3(&)即為所求問題的最大總收益,下面來看一個具體的例子.例72某公司擬將500萬元的資本投入所屬的甲、乙、丙三個工廠進行技術(shù)改造,各工廠獲得投資后年利潤將有相應的增長,增長額如表7-1所示.試確定500萬元資本的分配方案,以使公司總的年利潤增長額最大.表71投資額100萬元200萬元300萬元400萬元500萬元甲307090120130乙50100110110110丙406011012

25、0120解：將問題按工廠分為 三個階段k 1,2,3,設(shè)狀態(tài)變量Sk (k 1,2,3)代表從第k個工 廠到第3個工廠的投資額,決策變量Xk代表第k個工廠的投資額.于是有 狀態(tài)轉(zhuǎn)移率 Sk 1 Sk Xk、允許決策集合Dk(Sk) Xk |0 Xk Sk和遞推關(guān)系式：一fk(Sk)maxgk(Xk) fk1(Sk x/(k 3,2,1)0 xk Sk一 f4(S4) 0當k 3時：f3(&)0m3axew00m3ax3g3(x3)于是有表72,表中X3表示第三個階段的最優(yōu)決策.表7-2(單位：百萬元)S3012345X3012345f3(S3)00.40.61.11.21.2當k 2時

26、：f2(S2)maxg2(X2) f3(S2 X2)0 X2 S2于是有表73.表73單位：百萬元g2 (x2)+f 3(S 2 x 2)f2$)x20i234500+000i0+0.40.5+00.5i20+0.60. 5+0. 4io 0+0io 0230+i.i0.5+0.6i.0+0.4io i+0io 4240+i.20. 5+io iio 0+0.6i.i+0.4io i+0io 6i, 250+i.20.5+i.2io0+i.iio i+0.6i.i+0.4i.i+02.i2當k 1時:fi(Si)maxg(xi)f2(S x)0 Xi Si于是有表74.表74£gi

27、(xi) +f2(si - x i)fi(Si)xi0i234550+2.i0. 3+i.60.7+i o40.9+i.0i.2+0.5i.3+02.i0,2然后按計算表格的順序反推算 ,可知最優(yōu)分配方案有兩個：i甲工廠投資200萬元, 乙工廠投資200萬元,丙工廠投資 i00萬元；2甲工廠沒有投資,乙工廠投資200萬元,丙工廠投資300萬元.按最優(yōu)分配方案分配投資資源 ,年利潤將增長2I0萬元.這個例于是決策變量取離散值的一類分配問題,在實際問題中,相類似的問題還有銷售店的布局分配問題、設(shè)備或人力資源的分配問題等.在資源分配問題中,還有一種決策 變量為連續(xù)變量的資源分配問題,請見例7-3.例

28、73機器負荷分配問題.某種機器可在上下兩種不同的負荷下進行生產(chǎn),設(shè)機器在高負荷下生產(chǎn)的產(chǎn)量件函數(shù)為 gi 8X ,其中X為投入高負荷生產(chǎn)的機器數(shù)量,年度 完好率 0.7 年底的完好設(shè)備數(shù)等于年初完好設(shè)備數(shù)的70%;在低負荷下生產(chǎn)的產(chǎn)量件函數(shù)為g2 5y,其中y為投入低負荷生產(chǎn)的機器數(shù)量,年度完好率0.9.假定開始生產(chǎn)時完好的機器數(shù)量為i000臺,試問每年應如何安排機器在高、低負荷下的生產(chǎn),才能使5年生產(chǎn)的產(chǎn)品總量最多？解：設(shè)階段k表示年度k i,2,3,4,5；狀態(tài)變量Sk為第k年度初擁有的完好機器數(shù) 量同時也是第k i年度末時的完好機器數(shù)量.決策變量xk為第k年度分配高負荷下生產(chǎn) 的機器數(shù)量

29、,于是Sk xk為該年度分配在低負荷下生產(chǎn)的機器數(shù)量.這里的Sk和xk均為連續(xù)變量,它們的非整數(shù)值可以這樣理解：如Sk 0.6就表示一臺機器在第 k年度中正常工作時間只占全部時間的 60%；xk0.3就表示一臺機器在第 k年度中只有30%的工作時間在高負荷下運轉(zhuǎn).狀態(tài)轉(zhuǎn)移方程 為：SkixkSk xk 0.7xk 0.9Sk xk 0.9Sk 0.2xk允許決策集合：Dk(Sk) Xk|0 Xk Sk設(shè)階段指標Qk(Sk,Xk)為第k年度的產(chǎn)量,那么：Qk(Sk,Xk)過程指標是階段指標的和,即：令最優(yōu)值函數(shù)fk(Sk)表示從資源量8Xk 5(Sk Xk) 5Sk 3Xk5Qk5 Qj j k

30、Sk出發(fā),采取最優(yōu)子策略所生產(chǎn)的產(chǎn)品總量,因而有逆推關(guān)系式：fk(0)maX、50 3Xk fki(0.90 0.2Xk)Xk Dk (Sk)邊界條件f6(S6 )0.當k 5時：f5(S5) max5S5 3x§ feS) max5S5 3x50 x5 S50 X5 S5因£565)是關(guān)于X5的單調(diào)遞增函數(shù),故取X5 S5,相應有f5(S5) 8s5. 當k 4時：f4(S4)max 5S4 3x4 f5 (0.9S4 0.2x4)0 X4 S4max5S4 3x4 8(0.9S4 0.2X4)0 X4 S40mX4aSX4i2.2S1.4x4因f4(S4)是關(guān)于X4的單

31、調(diào)遞增函數(shù),故取 X4 S4,相應有f4(S4) I3.6S4；依次類推, 可求得：當 k 3時：X3 S3, f3(S3) 17.5S3當 k 2時：x20, f2(S2) 20.8S2當 k 1時：x10, f1(S1 1000) 23.7S1 23700計算結(jié)果說明最優(yōu)策略為：x10 ,x20,x3S3,x4S4,x5S5;即前兩年將全部設(shè)備都投入低負荷生產(chǎn),后三年將全部設(shè)備都投入高負荷生產(chǎn),這樣可以使5年的總產(chǎn)量最大,最大產(chǎn)量是23700件.有了上述最優(yōu)策略,各階段的狀態(tài)也就隨之確定了,即按階段順序計算出各年年初的 完好設(shè)備數(shù)量.S11000S20.9S10.2x10.910000.2

32、0900S30.9S20.2x20.99000.20810S40.9S30.2x30.98100.2810567S50.9S40.2x40.95670.2567397S60.9S50.2x50.93970.2397278上面所討論的過程始端狀態(tài)S是固定的,而終端狀態(tài) &是自由的,實現(xiàn)的目標函數(shù)是5年的總產(chǎn)量最高.如果在終端也附加上一定的約束條件,如規(guī)定在第5年結(jié)束時,完好的機器數(shù)量不低于350臺(上面的例子只有278臺),問應如何安排生產(chǎn),才能在滿足這一終端 要求的情況下使產(chǎn)量最高呢？解：階段k表示年度(k 1,2,3,4,5 );狀態(tài)變量Sk為第k年度初擁有的完好機器數(shù)量；決策變量X

33、k為第k年度分配高負荷下生產(chǎn)的機器數(shù)量；狀態(tài)轉(zhuǎn)移方程 為：ScXk(Sk Xk) 0.7Xk 0.9(Sk Xk) 0.9Sk 0.2Xk終端約束：S6 3500.9S5 0.2X5350x5 4.5S5 1750允許決策集合：Dk(Sk) (Xk |0 Xk Sj “加第k階段的終端遞推條件對于k 5,考慮終端遞推條件有：D5(S5) (X5 |0 X54.5S5 1750 S5500 S5 389同理其他各階段的允許決策集合可在過程指標函數(shù)的遞推中產(chǎn)生.設(shè)階段指標：Qk(Sk,Xk) 8Xk 5(Sk Xk) 5Sk 3Xk過程指標： 5Qk5Qjj k最優(yōu)值函數(shù)：fk(0)max、50

34、3Xkfki(0.90 0.2Xk)Xk Dk (Sk)邊界條件f6(S6) 0 o當k 5時：f5(1)max 5S5 3x5X Ds(S5)155f60)maXX5 D5(S5)(5S53x5因f5(S5)是關(guān)于X5的單調(diào)遞增函數(shù),故取X5 4.5S5 1750 ,相應有:0 4.5S5 1750 S5即：389 S5500x54.5S5 1750, f5(S5) 18.5S5 5250當k 4時：f4(S4)max 5S4 3X4 f5(0.9S4 0.2X4)X4 D4(S4)'max 21.65S4 0.7x4 5250X4 D484),44由$5 0.9S4 0.2x4 5

35、00 可得 x4 4.5S4 2500 ,又因 f4 (S4)是關(guān)于 X4 的單調(diào)遞減函數(shù),故取x4 4.5S4 2500 ,相應有：0 4.5S4 2500 S4556 S4714X44.5S4 2500 ,f4(S4) 18.5S4 3500當k 3時:f3S3max 5S3 3x3X3 Deg)133f4(0.9S3 0.2x3)max 21.65S3 0.7x3 3500x3 D3(S3)由S40.9S30.2x3714可彳#x34.5S33570,又因f3 (S3)是關(guān)于x3的單調(diào)遞減函數(shù),故取x3 4.5S3 3570 ,相應有：0 4.5S3 3570 S3793 S3 1020

36、由于Si 1000,所以S3 1020是恒成立的,即 S3 793.x34.5S3 3570, f3(S3) 18.5S3 1001當k 2時：f2(S2)max 5S2 3x2 f3(0.9S2 0.2x2)x D2 (S2 1max 21.65S2 0.7x2 1001x2 D2 (S2 )因f2(Sz)是關(guān)于x2的單調(diào)遞減函數(shù),而S3的取值并不對 *2有下界的約束,故取 x2 0 ,相應有：x20, f2(S2)21.65S2 1001當k 1時：f1(S1)max 5S1 3x1f2 (0.9S1 0.2x1)均 DNS)黑的4.4856 1.33x1 1001因力&是關(guān)于x1

37、的單調(diào)遞減函數(shù),故取x10,相應有x10, f1(S1 1000) 24.485S1 1001 23484計算結(jié)果說明最優(yōu)策略為：(1 )第1年將全部設(shè)備都投入低負荷生產(chǎn).S11000, x1 0,S2 0.9S10.2x10.91000 0.20900Q1(S,X1)5S1 3x15 1000 30 5000(2)第2年將全部設(shè)備都投入低負荷生產(chǎn).S2900, x2 0,S3 0.9S20.2x2 0.9900 0.20810Q2(S2,x2) 5s2 3x25 900 3 04500(3)第3年將x34.5S3 3570 4.5 810 3570 75臺完好設(shè)備投入高負荷生產(chǎn),將剩余的S3

38、 x3 810 75 735臺完好設(shè)備投入低負荷生產(chǎn).Q3(S3,x3) 5S3 3x3 5 810 3 75 4275S4 0.9S3 0.2x30.9 810 0.2 75 714(4)第4年將x44.5S4 2500 4.5 714 2500 713臺完好設(shè)備均投入高負荷生產(chǎn),將剩余的1臺完好設(shè)備均投入低負荷生產(chǎn).Q4(S4,x4) 5S4 3x45 714 3 713 5709S5 0.9S4 0.2x4 0.9 714 0.2 713 500(5)第 5 年將 x5 4.5S5 1750 4.5 500 1750 500 ,即將 S5 500 臺完好設(shè)備 均投入高負荷生產(chǎn).Q5(S5

39、,x5) 5S5 3x5 5 500 3 500 4000Se 0.9S5 0.2x5 0.9 500 0.2 500 3505f1(S11000) Qj(Sj,xj) 23484j 123存貯限制問題由于供應與需求在時間上存在差異,需要在供應與需求之間構(gòu)建存貯環(huán)節(jié)以平衡這種差異.存貯物資需要付出資本占用費和保管費等,過多的物資儲藏意味著浪費；而過少的儲備又會影響需求造成缺貨損失.存貯限制問題就是要在平衡雙方的矛盾中,尋找最正確的采購 批量和存貯量,以期到達最正確的經(jīng)濟效果.例7 4某鞋店銷售一種雪地防潮鞋,以往的銷售經(jīng)歷說明,此種鞋的銷售季節(jié)是從10月1日至3月31日.下個銷售季節(jié)各月的需求

40、預測值如表7-5所示.表7-5 單位：雙月份101112123需求402030403020該鞋店的此種鞋完全從外部生產(chǎn)商進貨,進貨價每雙4美元.進貨批量的根本單位是箱,每箱10雙.由于存貯空間的限制,每次進貨不超過 5箱.對應不同的訂貨批量,進價 享受一定的數(shù)量折扣,具體數(shù)值如表 7-6所示.表7-6進貨批量1箱2箱3箱4箱5箱數(shù)量折扣4%5%10%20%25%假設(shè)需求是按一定速度均勻發(fā)生的,訂貨不需時間,但訂貨只能在月初辦理一次,每次訂貨的采購費與采購數(shù)量無關(guān) 為10美元.月存貯費按每月月底鞋的存量計,每雙0.2美元.由于訂貨不需時間,所以銷售季節(jié)外的其他月份的存貯量為“0.試確定最正確的進

41、貨方案,以使總的銷售費用最小.解：階段：將銷售季節(jié) 6個月中的每一個月作為一個階段,即k 1,2, ,6;狀態(tài)變量：第k階段的狀態(tài)變量Sk代表第k個月初鞋的存量；決策變量：決策變量xk代表第k個月的采購批量；狀態(tài)轉(zhuǎn)移律：Sk 1 Sk xk dk dk是第k個月的需求量；邊界條件：S S7 0, f7S7 0;階段指標函數(shù)：rkSk,Xk代表第k個月所發(fā)生的全部費用 ,即與采購數(shù)量無關(guān)的 采購 費Ck、與采購數(shù)量成正比的 購置費Gk和存貯費Zk.其中：0, Xk 0Ck “Gk Px Xk； Zk 0.2Sk Xk dk10,xk 0最優(yōu)指標函數(shù)：最優(yōu)指標函數(shù)具有如下遞推形式 fkSk min

42、Ck Gk Zk fk 式& 1 xkminCk Gk 0.2Sk xk dk fk 1 Sk xk dkxk當k 6時3月：表7701020*620100f6(S6)86480當k 5時2月：02041881645016410172168142401422013413612230122308698900864050520505040410月份采購4箱40雙,11當k 4時1月：表7-9X4S'01020304050X4f4(SJ0302304403021028228228630、4028220250262264252202503021223024423021810212401641922122101961700164501441741781761520144601261401441320126當k 3時12月：表 7-10X3S、01020304050X3f30)04204224145041410388402392384503842035037037236233250332303023323403423103140302402843023102902922980284當k