運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃-河北科技大學(xué)大學(xué)英語(yǔ)精品課

1、動(dòng) 態(tài) 規(guī) 劃 (Dynamic programming),,動(dòng)態(tài)規(guī)劃的基本思想,最短路徑問(wèn)題,資源分配問(wèn)題,背包問(wèn)題,生產(chǎn)計(jì)劃問(wèn)題,復(fù)合系統(tǒng)工作可靠性問(wèn)題,動(dòng)態(tài)規(guī)劃是用來(lái)解決多階段決策過(guò)程最優(yōu)化的一種數(shù)量方法。其特點(diǎn)在于，它可以把一個(gè)n 維決策問(wèn)題變換為幾個(gè)一維最優(yōu)化問(wèn)題，從而一個(gè)一個(gè)地去解決。 需指出：動(dòng)態(tài)規(guī)劃是求解某類(lèi)問(wèn)題的一種方法，是考察問(wèn)題的一種途徑，而不是一種算法。必須對(duì)具體問(wèn)題進(jìn)行具體分析，

2、運(yùn)用動(dòng)態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動(dòng)態(tài)規(guī)劃方法去求解。,,即在系統(tǒng)發(fā)展的不同時(shí)刻（或階段）根據(jù)系統(tǒng)所處的狀態(tài)，不斷地做出決策；,每個(gè)階段都要進(jìn)行決策,目的是使整個(gè)過(guò)程的決策 達(dá)到最優(yōu)效果。,動(dòng)態(tài)決策問(wèn)題的特點(diǎn)：,系統(tǒng)所處的狀態(tài)和時(shí)刻是進(jìn)行決策的重要因素；,找到不同時(shí)刻的最優(yōu)決策以及整個(gè)過(guò)程的最優(yōu)策略。,多階段決策問(wèn)題：,在多階段決策過(guò)程中,系統(tǒng)的動(dòng)態(tài)過(guò)程可以按照時(shí)間進(jìn)程分為狀

3、態(tài)相互聯(lián)系而又相互區(qū)別的各個(gè)階段；,多階段決策問(wèn)題的典型例子： 1 . 生產(chǎn)決策問(wèn)題：企業(yè)在生產(chǎn)過(guò)程中，由于需求是隨時(shí)間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個(gè)生產(chǎn)過(guò)程中逐月或逐季度地根據(jù)庫(kù)存和需求決定生產(chǎn)計(jì)劃。,2. 機(jī)器負(fù)荷分配問(wèn)題：某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。在高負(fù)荷下進(jìn)行生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機(jī)器數(shù)量u1的關(guān)系為g=g(u1),1,2,n,,,,,,?,,,,狀態(tài),決策,狀態(tài),決

4、策,狀態(tài),狀態(tài),決策,這時(shí)，機(jī)器的年完好率為a，即如果年初完好機(jī)器的數(shù)量為u，到年終完好的機(jī)器就為au, 0<a<1。,在低負(fù)荷下生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機(jī)器數(shù)量u2的關(guān)系為 h=h(u2),假定開(kāi)始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為s1。要求制定一個(gè)五年計(jì)劃，在每年開(kāi)始時(shí)，決定如何重新分配完好的機(jī)器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。,相應(yīng)的機(jī)器年完好率b, 0&

5、lt; b<1。,3. 航天飛機(jī)飛行控制問(wèn)題：由于航天飛機(jī)的運(yùn)動(dòng)的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機(jī)飛行在不同環(huán)境中的情況，不斷地決定航天飛機(jī)的飛行方向和速度（狀態(tài)），使之能最省燃料和實(shí)現(xiàn)目的（如軟著落問(wèn)題）。,4 .不包含時(shí)間因素的線(xiàn)性規(guī)劃、非線(xiàn)性規(guī)劃等靜態(tài)決策問(wèn)題（本質(zhì)上是一次決策問(wèn)題）也可以適當(dāng)?shù)匾腚A段的概念，作為多階段的決策問(wèn)題用動(dòng)態(tài)規(guī)劃方法來(lái)解決。,5 . 最短路問(wèn)題：給定一個(gè)交通網(wǎng)絡(luò)圖如下，其中兩點(diǎn)之間的數(shù)字表

6、示距離（或花費(fèi)），試求從A點(diǎn)到G點(diǎn)的最短距離（總費(fèi)用最?。?,,,,,,,,1,2,3,4,5,6,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,,3,（一）、基本概念 1、階段： 把一個(gè)問(wèn)題的過(guò)程

7、，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段，以便于按一定的次序去求解。 描述階段的變量稱(chēng)為階段變量（k)。k=1,2 ,3, …，n階段的劃分，一般是根據(jù)時(shí)間和空間的自然特征來(lái)進(jìn)行的，但要便于問(wèn)題轉(zhuǎn)化為多階段決策。,2、狀態(tài)：表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件。通常一個(gè)階段有若干個(gè)狀態(tài)，描述過(guò)程狀態(tài)的變量稱(chēng)為狀態(tài)變量sk (表示第k階段的狀態(tài)變量 )。,一個(gè)數(shù)、一組數(shù)、一個(gè)向量,狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱(chēng)為

8、狀態(tài)允許集合S K ={s1,s2, …, s k ,…}。,一、動(dòng)態(tài)規(guī)劃的基本思想,3、決策：表示當(dāng)過(guò)程處于某一階段的某個(gè)狀態(tài)時(shí)，可以作出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱(chēng)為決策。,描述決策的變量，稱(chēng)為決策變量。 常用uk（sk）表示第k階段當(dāng)狀態(tài)為sk時(shí)的決策變量。 決策變量是狀態(tài)變量的函數(shù)?？捎靡粋€(gè)數(shù)、一組數(shù)或一向量（多維情形）來(lái)描述。 在實(shí)際問(wèn)題中決策變量的取值往往在某一范圍之內(nèi)，

9、此范圍稱(chēng)為允許決策集合。 常用Dk（sk）表示第k階段從狀態(tài)sk出發(fā)的允許決策集合，顯然uk（sk）∈Dk（sk）。,4、多階段決策過(guò)程,可以在各個(gè)階段進(jìn)行決策，去控制過(guò)程發(fā)展的多段過(guò)程；,其發(fā)展是通過(guò)一系列的狀態(tài)轉(zhuǎn)移來(lái)實(shí)現(xiàn)的；,系統(tǒng)在某一階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)的當(dāng)前的狀態(tài)和決策有關(guān)，而且還與系統(tǒng)過(guò)去的歷史狀態(tài)和決策有關(guān)。,圖示如下：,狀態(tài)轉(zhuǎn)移方程是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程。如果第k階段狀態(tài)變量sk的值、該階段

10、的決策變量一經(jīng)確定，第k+1階段狀態(tài)變量sk+1的值也就確定。,其狀態(tài)轉(zhuǎn)移方程如下（一般形式）,能用動(dòng)態(tài)規(guī)劃方法求解的多階段決策過(guò)程是一類(lèi)特殊的多階段決策過(guò)程，即具有無(wú)后效性的多階段決策過(guò)程。,如果狀態(tài)變量不能滿(mǎn)足無(wú)后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。,動(dòng)態(tài)規(guī)劃中能處理的狀態(tài)轉(zhuǎn)移方程的形式。,狀態(tài)具有無(wú)后效性的多階段決策過(guò)程的狀態(tài)轉(zhuǎn)移方程如下,無(wú)后效性(馬爾可夫性),如果某階段狀態(tài)給定后，則在這個(gè)階段以后過(guò)程的發(fā)展不受這

11、個(gè)階段以前各段狀態(tài)的影響；,過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它未來(lái)的發(fā)展；,構(gòu)造動(dòng)態(tài)規(guī)劃模型時(shí)，要充分注意是否滿(mǎn)足無(wú)后效性的要求；,狀態(tài)變量要滿(mǎn)足無(wú)后效性的要求；,5、策略：相互連接的決策序列稱(chēng)為一個(gè)策略。 從第k階段開(kāi)始到第n階段結(jié)束稱(chēng)為一個(gè)子策略。 Pk,n , 全策略 P1,n . 所有策略當(dāng)中有最優(yōu)值的策略稱(chēng)為最優(yōu)策略。,6、狀態(tài)轉(zhuǎn)移方程：是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程

12、，描述了狀態(tài)轉(zhuǎn)移規(guī)律。,,7、指標(biāo)函數(shù)和最優(yōu)值函數(shù)：用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的一種數(shù)量指標(biāo)，為指標(biāo)函數(shù)。 階段指標(biāo)函數(shù)： Vk (sk ,uk ) 表示第 k 階段位于sk 狀態(tài)、決策為 uk 的指標(biāo)值。 策略指標(biāo)函數(shù)：各決策序列指標(biāo)值之和。（個(gè)別情況為乘積）指標(biāo)函數(shù)的最優(yōu)值，稱(chēng)為最優(yōu)值函數(shù)。在不同的問(wèn)題中，指標(biāo)函數(shù)的含義是不同的，它可能是距離、利潤(rùn)、成本、產(chǎn)量或資源消耗等。 動(dòng)態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性，

13、并滿(mǎn)足遞推關(guān)系。,小結(jié):,指標(biāo)函數(shù)形式:,和、,積,無(wú)后效性,可遞推,解多階段決策過(guò)程問(wèn)題，求出,,,,f1(s1),,從 k 到終點(diǎn)最優(yōu)策略子策略的最優(yōu)目標(biāo)函數(shù)值,1、動(dòng)態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫(xiě)出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件（簡(jiǎn)稱(chēng)基本方程）。要做到這一點(diǎn)，就必須將問(wèn)題的過(guò)程分成幾個(gè)相互聯(lián)系的階段，恰當(dāng)?shù)倪x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個(gè)大問(wèn)題轉(zhuǎn)化成一組同類(lèi)型的子問(wèn)題，然后逐個(gè)求解。即從邊界條件開(kāi)始，逐段遞推尋

14、優(yōu)，在每一個(gè)子問(wèn)題的求解中，均利用了它前面的子問(wèn)題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個(gè)子問(wèn)題所得的最優(yōu)解，就是整個(gè)問(wèn)題的最優(yōu)解。,（二）、動(dòng)態(tài)規(guī)劃的基本思想,2、在多階段決策過(guò)程中，動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段和未來(lái)一段分開(kāi)，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來(lái)考慮的，與該段的最優(yōu)選擇答案一般是不同的.,最優(yōu)化原理：作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：無(wú)論過(guò)去的狀態(tài)和決策如何，相對(duì)于前面的決策所

15、形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略?！币簿褪钦f(shuō)，一個(gè)最優(yōu)策略的子策略也是最優(yōu)的。,3、在求整個(gè)問(wèn)題的最優(yōu)策略時(shí)，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過(guò)的各段狀態(tài)便可逐段變換得到，從而確定了最優(yōu)路線(xiàn)。,,,,（三）、建立動(dòng)態(tài)規(guī)劃模型的步驟 1、劃分階段k劃分階段是運(yùn)用動(dòng)態(tài)規(guī)劃求解多階段決策問(wèn)題的第一步，在確定多階段特性后，按時(shí)間或空間先后順序，將過(guò)程劃分為若干相互聯(lián)系的階段。對(duì)于靜態(tài)問(wèn)

16、題要人為地賦予“時(shí)間”概念，以便劃分階段。 2、正確選擇狀態(tài)變量sk選擇變量既要能確切描述過(guò)程演變又要滿(mǎn)足無(wú)后效性，而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)變量的選擇是從過(guò)程演變的特點(diǎn)中尋找。 3、確定決策變量uk(sk)及允許決策集合Dk(sk)通常選擇所求解問(wèn)題的關(guān)鍵變量作為決策變量，同時(shí)要給出決策變量的取值范圍，即確定允許決策集合。,,,,,4、確定狀態(tài)轉(zhuǎn)移方程根據(jù)k 階段狀態(tài)變量和決策變量，寫(xiě)出k+1階段狀態(tài)

17、變量，狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系。 sk+1 =Tk (sk ,uk ) Tk —函數(shù)關(guān)系 5、確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃基本方程 階段指標(biāo)函數(shù)是指第k 階段的收益，最優(yōu)指標(biāo)函數(shù)是指從第k 階段狀態(tài)出發(fā)到第n 階段末所獲得收益的最優(yōu)值，最后寫(xiě)出動(dòng)態(tài)規(guī)劃基本方程。f k (sk ) = Opt [ Vk (sk ,uk ) + f k+1 (s k+1) ]fn+1 (

18、s n+1 ) = 0 Opt 最優(yōu)化（max,min）,以上五步是建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。由于動(dòng)態(tài)規(guī)劃模型與線(xiàn)性規(guī)劃模型不同，動(dòng)態(tài)規(guī)劃模型沒(méi)有統(tǒng)一的模式，建模時(shí)必須根據(jù)具體問(wèn)題具體分析，只有通過(guò)不斷實(shí)踐總結(jié)，才能較好掌握建模方法與技巧。,f1(s1) 是整個(gè)問(wèn)題的最優(yōu)策略，最優(yōu)值。 f k(sk) 表示從第k階段（狀態(tài)sk）到終點(diǎn)的最優(yōu)指標(biāo)值。（距離、利潤(rùn)、成本等）,例一、從A

19、地到D 地要鋪設(shè)一條煤氣管道,其中需經(jīng)過(guò)兩級(jí)中間站，兩點(diǎn)之間的連線(xiàn)上的數(shù)字表示距離，如圖所示。問(wèn)應(yīng)該選擇什么路線(xiàn)，使總距離最短？,A,B1,B2,C1,C2,C3,D,,,,,,,,,,,,2,4,3,3,3,3,2,1,1,1,4,,,,二、最短路徑問(wèn)題,解：整個(gè)計(jì)算過(guò)程分三個(gè)階段，從最后一個(gè)階段開(kāi)始。,第三階段（C →D）： C 有三條路線(xiàn)到終點(diǎn)D 。,A,B1,B2,C1,C2,C3,D,,,,,,,,,,,,2,4,3,3,3,

20、3,2,1,1,1,4,,,,D,C1,C2,C3,顯然有 f3 (C1 ) = 1 ； f3(C2 ) = 3 ； f3 (C3 ) = 4,d( B1,C1 ) + f3 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f3 (C2 ) = min 3+3

21、 d( B1,C3 ) + f3 (C3 ) 1+4 4 = min 6 = 4 5,,,,,第二階段（B →C）： B 到C 有六條路線(xiàn)。

22、,,,A,B1,B2,C1,C2,C3,D,,,,,,,,,,,,2,4,3,3,3,3,2,1,1,1,4,,,,D,C1,C2,C3,B1,B2,,,,,(最短路線(xiàn)為B1→C1 →D),d( B2,C1 ) + f3 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f3 (C2 ) = min 3+3

23、 d( B2,C3 ) + f3 (C3 ) 1+4 3 = min 6 = 3 5,,,,,,,A,B1,B2

24、,C1,C2,C3,D,,,,,,,,,,,,2,4,3,3,3,3,2,1,1,1,4,,,,D,C1,C2,C3,B1,B2,,,,,(最短路線(xiàn)為B2→C1 →D),,,,,第一階段（ A → B ）： A 到B 有二條路線(xiàn)。,f1(A)1 = d(A, B1 )＋ f2 ( B1 ) ＝2＋4＝6 f1 (A)2 = d(A, B2 )＋ f2 ( B2 ) ＝4＋3＝7,∴ f1 (A) = min

25、 = min｛6,7｝=6,d(A, B1 )＋ f2 ( B1 )d(A, B2 )＋ f2 ( B2 ),,,(最短路線(xiàn)為A→B1→C1 →D),A,B1,B2,C1,C2,C3,D,,,,,,,,,,,,2,4,3,3,3,3,2,1,1,1,4,,,,D,C1,C2,C3,B1,B2,,,,,,,,,A,,,,A,B1,B2,C1,C2,C3,D,,,,

26、,,,,,,,,2,4,3,3,3,3,2,1,1,1,4,,,,D,C1,C2,C3,B1,B2,,,,,,,,,A,,,,最短路線(xiàn)為 A→B1→C1 →D 路長(zhǎng)為 6,,,,,三、非線(xiàn)性規(guī)劃問(wèn)題,【例7-4】 用動(dòng)態(tài)規(guī)劃方法解下列非線(xiàn)性規(guī)劃問(wèn)題,,解： 解決這一類(lèi)靜態(tài)規(guī)劃問(wèn)題，需要人為地賦予時(shí)間概念，從而將該問(wèn)題轉(zhuǎn)化為多階段決策過(guò)程?！　“磫?wèn)題的變量個(gè)數(shù)劃分階段，把它

27、看作一個(gè)三階段決策問(wèn)題，k=1，2，3　　設(shè)狀態(tài)變量為s1，s2，s3，s4并記s1≤c　　取問(wèn)題中的變量x1，x2，x3為決策變量,,狀態(tài)轉(zhuǎn)移方程為：s3=x3s3+x2=s2s2+x1=s1≤c允許決策集合為：x3=s30≤x2≤s20≤x1≤s1　各階段指標(biāo)函數(shù)為：v1（x1）=x1v2（x2）=x22v3（x3）=x3，　各指標(biāo)函數(shù)以乘積方式結(jié)合，最優(yōu)指標(biāo)函數(shù)fk（sk）表示從第k階段初始狀

28、態(tài)sk出發(fā)到第3階段所得到的最大值，則動(dòng)態(tài)規(guī)劃基本方程為：,,用逆序解法由后向前依次求解：k=3時(shí)，　　　　　　　　x3*=s3 k=2時(shí)，,,,令h2（s2，x2）=x22（s2－x2）用經(jīng)典解析法求極值點(diǎn)：解得：　　　　　　　　　　　 x2=0（舍） 所以 　　　是極大值點(diǎn)。,,,,,,,,k=1時(shí)， 令解得：　　　　　　x1=s1（舍）

29、所以 是極大值點(diǎn)。,,,,,,,,由于s1未知，所以對(duì)s1再求極值，顯然s1=c時(shí)，f1（s1）取得最大值 反向追蹤得各階段最優(yōu)決策及最優(yōu)值： s1=c所以最優(yōu)解為：,,,,,,,,,,,,,,一般地，如果階段指標(biāo)函數(shù)vk（sk，uk）是線(xiàn)性函數(shù)或凸函數(shù)時(shí)，最優(yōu)指標(biāo)函數(shù)fk（sk）的表達(dá)式比較容易得到，但是當(dāng)vk（sk，uk）不具備上述特性時(shí)，最優(yōu)指標(biāo)函數(shù)fk（sk）的表達(dá)式不易得到，就需要采用數(shù)值法

30、，即對(duì)連續(xù)變量進(jìn)行離散化處理，再分散求解。例如靜態(tài)規(guī)劃模型其動(dòng)態(tài)規(guī)劃基本方程為：狀態(tài)轉(zhuǎn)移方程為sk+1=sk－xks1=a,,,狀態(tài)變量sk及決策變量xk都是連續(xù)變量，對(duì)其進(jìn)行離散化處理，具體做法是：1. 對(duì)區(qū)間[0，a]進(jìn)行分割，分割數(shù)m= ，其中Δ是分割后的小區(qū)間的長(zhǎng)度，其大小可以根據(jù)所求解問(wèn)題要求的精度及計(jì)算機(jī)運(yùn)算能力而定，分割點(diǎn)為0，Δ，2Δ，…，mΔ= a。2. 規(guī)定狀態(tài)變量sk及決策變量xk僅在離

31、散點(diǎn)0，Δ，2Δ，…，mΔ處取值，最優(yōu)指標(biāo)函數(shù)fk（sk）也定義在這些離散點(diǎn)上。動(dòng)態(tài)規(guī)劃基本方程可以寫(xiě)為：其中sk=qΔ，xk=pΔ。3. 由后向前逐段遞推，直至求出整個(gè)過(guò)程最優(yōu)解。,,,【例7-5】解 按變量個(gè)數(shù)將原問(wèn)題分為三個(gè)階段，階段變量k=1，2，3；選擇xk為決策變量；狀態(tài)變量sk表示第k階段至第3階段決策變量之和；取小區(qū)間長(zhǎng)度Δ=1，小區(qū)間數(shù)目m=6/1=6，狀態(tài)變量sk的取值點(diǎn)為：狀態(tài)轉(zhuǎn)

32、移方程：sk+1=sk－xk；允許決策集合：Dk（sk）=｛xk|0≤xk≤sk｝k=1，2，3xk，sk均在分割點(diǎn)上取值；,,,階段指標(biāo)函數(shù)分別為：g1（x1）=x12　　　　　　g2（x2）=x2　　g3（x3）=x33，　　　最優(yōu)指標(biāo)函數(shù)fk（sk）表示從第k階段狀態(tài)sk出發(fā)到第3階段所得到的最大值，動(dòng)態(tài)規(guī)劃的基本方程為： 　　k=3時(shí)， 　　s3及x3取值點(diǎn)較多，計(jì)算結(jié)果以表格形式給出，見(jiàn)表7-1所示。

33、,,,表7－1　取值,,,,k=2時(shí)，計(jì)算結(jié)果見(jiàn)表7-2,,,,,,k=1時(shí)，其中s1=6，計(jì)算結(jié)果見(jiàn)表7-3所示。　　由表7-3知，x1*=2，s1=6，則s2= s1－x1*=6－2=4，查表7-2得：x2*=1，則s3= s2－x2*=4－1=3，查表7-1得：x3*=3，所以最優(yōu)解為：x1*=2，x2*=1，x3*=3，f1(s1)=108?！　　”纠部捎媒?jīng)典解析法求得各段的極值，讀者可自行求解，二者結(jié)論完全

34、相同。需要指出的是當(dāng)連續(xù)變量離散化處理以后，由于狀態(tài)變量和決策變量只在給定的離散點(diǎn)上取值，故有可能漏掉最優(yōu)解，因此需要慎重選擇參數(shù)m與Δ。,,,,,,資源分配問(wèn)題就是將一定數(shù)量的一種或若干種資源（原材料、資金、設(shè)備等）合理分配給若干使用者，使得資源分配后總結(jié)果最優(yōu)。一種資源的分配問(wèn)題稱(chēng)為一維資源分配問(wèn)題，兩種資源的分配問(wèn)題稱(chēng)為二維資源分配問(wèn)題。,四、資源分配問(wèn)題,假設(shè)有一種資源，數(shù)量為a，將其分配給n個(gè)使用者，分配給第i個(gè)使用者數(shù)量xi

35、時(shí)，相應(yīng)的收益為gi（xi），問(wèn)如何分配使得總收入最大？這就是一維資源分配問(wèn)題，該問(wèn)題的數(shù)學(xué)模型為：　　　這是一個(gè)靜態(tài)規(guī)劃問(wèn)題，應(yīng)用動(dòng)態(tài)規(guī)劃方法求解時(shí)人為賦予時(shí)間概念，將其看作是一個(gè)多階段決策問(wèn)題。,,按變量個(gè)數(shù)劃分階段，k=1，2，…，n；設(shè)決策變量uk=xk，表示分配給第k個(gè)使用者的資源數(shù)量；設(shè)狀態(tài)變量為sk，表示分配給第k個(gè)至第n個(gè)使用者的總資源數(shù)量；狀態(tài)轉(zhuǎn)移方程：sk+1=sk－xk，其中s1=a；允許決策

36、集合：Dk（sk）=｛xk|0≤xk≤sk｝階段指標(biāo)函數(shù)：vk（sk，uk）=gk（xk）表示分配給第k個(gè)使用者數(shù)量xk時(shí)的收益；最優(yōu)指標(biāo)函數(shù)fk（sk）表示以數(shù)量sk的資源分配給第k個(gè)至第n個(gè)使用者所得到的最大收益，則動(dòng)態(tài)規(guī)劃基本方程為：由后向前逐段遞推，f1（a）即為所求問(wèn)題的最大收益。,,【例7-6】 某公司打算在3個(gè)不同的地區(qū)設(shè)置4個(gè)銷(xiāo)售點(diǎn)，根據(jù)市場(chǎng)部門(mén)估計(jì)，在不同地區(qū)設(shè)置不同數(shù)量的銷(xiāo)售點(diǎn)每月可得到的利潤(rùn)如表7-4所

37、示。試問(wèn)在各地區(qū)如何設(shè)置銷(xiāo)售點(diǎn)可使每月總利潤(rùn)最大。表7-4,,解 如前所述，建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型：將問(wèn)題分為3個(gè)階段，k=1，2，3；決策變量xk表示分配給第k個(gè)地區(qū)的銷(xiāo)售點(diǎn)數(shù)；狀態(tài)變量為sk表示分配給第k個(gè)至第3個(gè)地區(qū)的銷(xiāo)售點(diǎn)總數(shù)；狀態(tài)轉(zhuǎn)移方程：sk+1=sk－xk，其中s1=4；允許決策集合：Dk（sk）=｛xk|0≤xk≤sk｝　　階段指標(biāo)函數(shù)：gk（xk）表示xk個(gè)銷(xiāo)售點(diǎn)分配給第k個(gè)地區(qū)所獲得的利潤(rùn)；　　　最優(yōu)指

38、標(biāo)函數(shù)fk（sk）表示將數(shù)量為sk的銷(xiāo)售點(diǎn)分配給第k個(gè)至第3個(gè)地區(qū)所得到的最大利潤(rùn)，動(dòng)態(tài)規(guī)劃基本方程為：,,k=3時(shí)，數(shù)值計(jì)算如下表7-5　　　　　　　表7-5,,,,,,,,,,,k=2時(shí)，計(jì)算結(jié)果見(jiàn)下表7-6　　　　　　　　　　　　　　　　表7-6,,,,,,,,,,,k=1時(shí)，k=1時(shí)，只有s1=4的情況。計(jì)算結(jié)果如表7-7所示。所以最優(yōu)解為：x1*=2，x2*=1，x3*=1，f1(4)=47，即

39、在第1個(gè)地區(qū)設(shè)置2個(gè)銷(xiāo)售點(diǎn)，第2個(gè)地區(qū)設(shè)置1個(gè)銷(xiāo)售點(diǎn)，第3個(gè)地區(qū)設(shè)置1個(gè)銷(xiāo)售點(diǎn)，每月可獲利潤(rùn)47。表7-7,,,,,,,,,,【例7-7】機(jī)器負(fù)荷問(wèn)題　　　某工廠(chǎng)有100臺(tái)機(jī)器，擬分四期使用，每一期都可在高、低兩種不同負(fù)荷下進(jìn)行生產(chǎn)。若把x臺(tái)機(jī)器投入高負(fù)荷下進(jìn)行生產(chǎn)，則在本期結(jié)束時(shí)將有1/3x臺(tái)機(jī)器損壞報(bào)廢；余下的機(jī)器全部投入低負(fù)荷下進(jìn)行生產(chǎn)，則在期末有1/10的機(jī)器報(bào)廢。如果高負(fù)荷下生產(chǎn)時(shí)每臺(tái)機(jī)器可獲利潤(rùn)為10，低負(fù)荷下生產(chǎn)時(shí)

40、每臺(tái)機(jī)器可獲利潤(rùn)為7，問(wèn)怎樣分配機(jī)器使四期的總利潤(rùn)最大？解 將問(wèn)題按周期分為4個(gè)階段，k=1，2，3，4；狀態(tài)變量sk表示第k階段初完好的機(jī)器數(shù)，s1=100，0≤sk≤100；決策變量xk表示第k階段投入高負(fù)荷下生產(chǎn)的機(jī)器數(shù)，則sk－xk表示第k階段投入低負(fù)荷下生產(chǎn)的機(jī)器數(shù)；允許決策集合：Dk（sk）=｛xk|0≤xk≤sk｝狀態(tài)轉(zhuǎn)移方程：sk+1=Tk（sk，xk），即第k+1階段初擁有的完好機(jī)器數(shù)sk+1為：,,階段指

41、標(biāo)函數(shù)：vk（sk，xk）=10xk+7（sk－xk）表示第k階段所獲得的利潤(rùn)；　　　最優(yōu)指標(biāo)函數(shù)fk（sk）表示從第k階段初完好機(jī)器數(shù)為sk至第四階段的最大利潤(rùn)，動(dòng)態(tài)規(guī)劃基本方程為： 　k=4時(shí)， 　　　　　　　　　x4*=s4 　k=3時(shí)， 　　　　　　　 ∴ x3*=s3,,,,k=2時(shí)， 　　　　　　　　　　　　　 ∴ x2*

42、=0 k=1時(shí)， 　　　　　　　　　 ∴ x1*=0,,,因?yàn)閟1=100，所以f1（100）=2680，逆向追蹤得：　s1=100，x1*=0 　　　　　　　　　　　　　　　　x2*=0 　　　　　　　　　　　　　　　　x3*=s3=81 　　　　　　　　　　　　　　　　x4*=s4=54　　　　　即，第1，2期把全部完好機(jī)器投入低負(fù)荷下生產(chǎn)，第3，4

43、期把全部完好機(jī)器投入高負(fù)荷下生產(chǎn)所得利潤(rùn)最大。,,,,五、生產(chǎn)計(jì)劃問(wèn)題,在企業(yè)生產(chǎn)經(jīng)營(yíng)活動(dòng)中，經(jīng)常會(huì)遇到如何合理安排生產(chǎn)、庫(kù)存及銷(xiāo)售計(jì)劃，使總效益最高的問(wèn)題，這一類(lèi)問(wèn)題統(tǒng)稱(chēng)為生產(chǎn)計(jì)劃問(wèn)題。,【例7-8】 （生產(chǎn)—庫(kù)存問(wèn)題）　　　某工廠(chǎng)要對(duì)一種產(chǎn)品制定今后四個(gè)時(shí)期的生產(chǎn)計(jì)劃，據(jù)估計(jì)在今后四個(gè)時(shí)期內(nèi)，市場(chǎng)對(duì)該產(chǎn)品的需求量分別為2，3，2，4單位，假設(shè)每批產(chǎn)品固定成本為3千元，若不生產(chǎn)為0，每單位產(chǎn)品成本為1千元，每個(gè)時(shí)期最大生產(chǎn)能力不超過(guò)

44、6個(gè)單位，每期期末未出售產(chǎn)品，每單位需付存貯費(fèi)0.5千元，假定第1期初和第4期末庫(kù)存量均為0，問(wèn)該廠(chǎng)如何安排生產(chǎn)與庫(kù)存，可在滿(mǎn)足市場(chǎng)需求的前提下總成本最小。解 以每個(gè)時(shí)期作為一個(gè)階段，該問(wèn)題分為4個(gè)階段，k=1，2，3，4； 決策變量xk表示第k階段生產(chǎn)的產(chǎn)品數(shù)； 狀態(tài)變量sk表示第k階段初的庫(kù)存量；,以dk表示第k階段的需求，則狀態(tài)轉(zhuǎn)移方程：sk+1=sk+xk－dk k=4，3，2，1 由于期初

45、及期末庫(kù)存為0，所以s1=0，s5=0； 允許決策集合Dk（sk）的確定： 當(dāng)sk≥dk時(shí)，xk可以為0，當(dāng)sk<dk時(shí)，至少應(yīng)生產(chǎn)dk－sk，故xk的下限為max（0，dk－sk）；每期最大生產(chǎn)能力為6，xk最大不超過(guò)6，由于期末庫(kù)存為0，xk還應(yīng)小于本期至4期需求之和減去本期的庫(kù)存量 　　　　，所以xk的上限為min（ 　　　　，6），故有： Dk（sk）=｛xk| max（0,d

46、k－sk）≤xk≤min（ 　　　　,6）｝,階段指標(biāo)函數(shù)rk（sk，xk）表示第k期的生產(chǎn)費(fèi)用與存貯費(fèi)用之和：最優(yōu)指標(biāo)函數(shù)fk（sk）表示第k期庫(kù)存為sk到第4期末的生產(chǎn)與存貯最低費(fèi)用，動(dòng)態(tài)規(guī)劃基本方程為：,先求出各狀態(tài)允許狀態(tài)集合及允許決策集合，如表7-8所示。表7-8,k=4時(shí)，計(jì)算結(jié)果見(jiàn)表7-9所示。 表7-9,k=3時(shí)，計(jì)算結(jié)果如下表：,,k=2時(shí)，計(jì)算結(jié)果如下表,,,,,,k=1時(shí)，

47、計(jì)算結(jié)果見(jiàn)表7-12所示 　　　 逆向追蹤可得：x1*=5，s2=3，x2*=0，s3=0，x3*=6，s4=4，x4*=0，即第1時(shí)期生產(chǎn)5個(gè)單位，第3時(shí)期生產(chǎn)6個(gè)單位，第2，4時(shí)期不生產(chǎn)，可使總費(fèi)用最小，最小費(fèi)用為20.5千元。,,【例7-9】 （庫(kù)存—銷(xiāo)售問(wèn)題） 設(shè)某公司計(jì)劃在1至4月份從事某種商品經(jīng)營(yíng)。已知倉(cāng)庫(kù)最多可存儲(chǔ)600件這種商品，已知1月初存貨200件，根據(jù)預(yù)測(cè)知1至4月份各月的

48、單位購(gòu)貨成本及銷(xiāo)售價(jià)格如表7-13所示，每月只能銷(xiāo)售本月初的庫(kù)存，當(dāng)月進(jìn)貨供以后各月銷(xiāo)售，問(wèn)如何安排進(jìn)貨量和銷(xiāo)售量，使該公司四個(gè)月獲得利潤(rùn)最大（假設(shè)四月底庫(kù)存為零）。表7-13,解 按月份劃分階段，k=1，2，3，4；狀態(tài)變量sk表示第k月初的庫(kù)存量，s1=200，s5=0；決策變量 xk表示第k月售出的貨物數(shù)量，yk表示第k月購(gòu)進(jìn)的貨物數(shù)量；狀態(tài)轉(zhuǎn)移方程：sk+1=sk+yk－xk；允許決策集合：0≤xk≤sk，0≤yk

49、≤600－（sk－xk）；階段指標(biāo)函數(shù)為：pkxk－ckyk表示k月份的利潤(rùn)，其中pk為第k月份的單位銷(xiāo)售價(jià)格，ck為第k月份的單位購(gòu)貨成本；最優(yōu)指標(biāo)函數(shù)fk（sk）表示第k月初庫(kù)存為sk時(shí)從第k月至第4月末的最大利潤(rùn)，則動(dòng)態(tài)規(guī)劃基本方程為：,k=4時(shí)，　　　　　　x4*=s4　　　y4*=0k=3時(shí)，,為求出使44s3－5x3+4y3最大的x3，y3，須求解線(xiàn)性規(guī)劃問(wèn)題：,只有兩個(gè)變量x3，y3，可用圖解法也可用單純

50、形法求解，圖解法求解示意圖如圖7-5所示：在A點(diǎn)處取得最優(yōu)解，x3*=0，y3*=600－s3，f3（s3）=40s3+2400,,k=2時(shí)，類(lèi)似地求得：x2*=s2，y2*=600，f2（s2）=42s2+3600k=1時(shí)，類(lèi)似地求得：x1*=s1，y1*=600， f1（s1）=45s1+4800=13800,逆向追蹤得各月最優(yōu)購(gòu)貨量及銷(xiāo)售量：x1*=s1=200

51、y1*=600；x2*=s2=s1+ y1*－x1*=600y2*=600；x3*=0y3*=600－s3=600－（s2+ y2*－x2*）=0x4*=s4=（s3+ y3*－x3*）=600y4*=0　即1月份銷(xiāo)售200件，進(jìn)貨600件，2月份銷(xiāo)售600件，進(jìn)貨600件，3月份銷(xiāo)售量及進(jìn)貨量均為0，4月份銷(xiāo)售600件，不進(jìn)貨，可獲得最大總利潤(rùn)13800。,六、背包問(wèn)題,有人攜帶背包上山，其可攜帶物品的重量限度

52、為a公斤，現(xiàn)有n種物品可供選擇，設(shè)第i種物品的單件重量為ai公斤，其在上山過(guò)程中的價(jià)值是攜帶數(shù)量xi的函數(shù)ci（xi），問(wèn)應(yīng)如何安排攜帶各種物品的數(shù)量，使總價(jià)值最大。這就是背包問(wèn)題，類(lèi)似的貨物裝載問(wèn)題，下料問(wèn)題都等同于背包問(wèn)題。背包問(wèn)題的數(shù)學(xué)模型為：,下面用動(dòng)態(tài)規(guī)劃方法求解：按照裝入物品的種類(lèi)劃分階段，k=1，2，…，n；狀態(tài)變量sk表示裝入第k種至第n種物品的總重量；決策變量xk表示裝入第k種物品的件數(shù)；狀態(tài)轉(zhuǎn)移方程為：sk

53、+1=sk－akxk允許決策集合為：其中　　　　表示不超過(guò)　　　的最大整數(shù)；,階段指標(biāo)函數(shù)ck（xk）表示第k階段裝入第k種商品xk件時(shí)的價(jià)值；最優(yōu)指標(biāo)函數(shù)fk（sk）表示第k階段裝入物品總重量為sk時(shí)的最大價(jià)值，動(dòng)態(tài)規(guī)劃基本方程為：,【例7-10】 某工廠(chǎng)生產(chǎn)三種產(chǎn)品，各產(chǎn)品重量與利潤(rùn)關(guān)系如表7-14所示，現(xiàn)將此三種產(chǎn)品運(yùn)往市場(chǎng)銷(xiāo)售，運(yùn)輸能力總重量不超過(guò)6噸，問(wèn)如何安排運(yùn)輸使總利潤(rùn)最大？表7-14,解 設(shè)xi為裝載第i種貨

54、物的件數(shù)，i=1，2，3，該問(wèn)題數(shù)學(xué)模型為：,按前述方法建立動(dòng)態(tài)規(guī)劃模型；k=3時(shí)，計(jì)算結(jié)果如表7-15所示。,,,k=2時(shí)，計(jì)算結(jié)果如表7-16所示。表7-16,,,,k=1時(shí)，計(jì)算結(jié)果如表7-17所示。表7-17,反向追蹤得最優(yōu)方案Ⅰ：x1*=0，x2*=2，x3*=0； 最優(yōu)方案Ⅱ：x1*=1，x2*=0，x3*=1；最大總利潤(rùn)為260元。,,,七、復(fù)合系統(tǒng)工作可靠性問(wèn)題,某個(gè)機(jī)器工作

55、系統(tǒng)由n個(gè)部件串聯(lián)而成，其中只要有一個(gè)部件失效，則整個(gè)系統(tǒng)不能正常工作，因此為了提高系統(tǒng)工作的可靠性，在設(shè)計(jì)時(shí)，每個(gè)主要部件上都裝有備用元件，一旦某個(gè)主要部件失效，備用元件會(huì)自動(dòng)投入系統(tǒng)工作，顯然備用元件越多，系統(tǒng)工作可靠性越大，但是備用元件越多，系統(tǒng)的成本、重量、體積相應(yīng)增大，工作精度降低，因此在上述限制條件下，應(yīng)選擇合理的備用元件數(shù)，使整個(gè)系統(tǒng)的工作可靠性最大。,設(shè)第i（i=1，2，…，n）個(gè)部件上裝有ui個(gè)備用元件，正常工作的概率

56、為pi（ui），則整個(gè)系統(tǒng)正常工作的可靠性為　　　　　，裝第i個(gè)部件的費(fèi)用為ci，重量為wi，要求總費(fèi)用不超過(guò)c，總重量不超過(guò)w，則靜態(tài)規(guī)劃數(shù)學(xué)模型為：,按部件個(gè)數(shù)劃分階段，k=1，2，…，n；決策變量uk表示部件k上的備用元件數(shù)；狀態(tài)變量xk表示從第k個(gè)到第n個(gè)部件的總費(fèi)用，yk表示從第k個(gè)到第n個(gè)部件的總重量；狀態(tài)轉(zhuǎn)移方程為：xk+1=xk－ckuk　　　　　　yk+1=yk－wkuk允許決策集合為：

57、階段指標(biāo)函數(shù)為pk（uk），表示第k個(gè)部件的正常工作概率；最優(yōu)指標(biāo)函數(shù)fk（xk，yk）表示由狀態(tài)xk，yk出發(fā)，從部件k到部件n的系統(tǒng)工作最大可靠性，則動(dòng)態(tài)規(guī)劃基本方程為：　　　f1（c，w）即為整個(gè)系統(tǒng)工作的最大可靠性。,【例7-11】 某廠(chǎng)設(shè)計(jì)的一種電子設(shè)備由三種元件A、B、C串聯(lián)而成，已知三種元件的價(jià)格及可靠性如表7-18所示，要求設(shè)計(jì)中使用元件的總費(fèi)用不超過(guò)10萬(wàn)元，問(wèn)如何設(shè)計(jì)使設(shè)備的可靠性達(dá)到最大（不考慮重量限

58、制）。表7-18,解 如前所述建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型；按元件種類(lèi)劃分為3個(gè)階段，k=1，2，3；決策變量xk表示第k個(gè)部件配備的元件數(shù)；狀態(tài)變量sk表示從第k階段到第3階段配備元件的總費(fèi)用；狀態(tài)轉(zhuǎn)移方程為：sk+1=sk－ckxk其中ck表示第k種部件的元件單價(jià)；允許決策集合為：以pk表示第k個(gè)部件中的1個(gè)元件的正常工作概率，假定部件k的xk個(gè)元件是并聯(lián)的，則　　　　　　為xk個(gè)元件均不正常工作的概率，fk（s

59、k）表示由狀態(tài)sk開(kāi)始從第k個(gè)到　第3個(gè)部件的設(shè)備最大可靠性。,k=3時(shí)，由于A、B至少要購(gòu)置1件，用于購(gòu)置C的最高金額為s3=10－2－3=5萬(wàn)元，計(jì)算結(jié)果如表7-19所示。表7-19,,,,k=2時(shí)，計(jì)算結(jié)果如表7-20所示。表7-20,,,k=1時(shí)，計(jì)算結(jié)果如表7-21所示。表7-21,,,逆向追蹤得：x1*=2，s2=6，x2*=1，s3=3，x3*=3，即A元件用2個(gè)，B元件用1個(gè)，C元件用