第6章動態(tài)規(guī)劃

1、多階段決策問題及其舉例多階段決策問題及其舉例 動態(tài)規(guī)劃的基本概念及基本方程動態(tài)規(guī)劃的基本概念及基本方程 資源分配問題資源分配問題 生產(chǎn)與存儲問題生產(chǎn)與存儲問題 其他動態(tài)規(guī)劃問題其他動態(tài)規(guī)劃問題第六章第六章 動態(tài)規(guī)劃動態(tài)規(guī)劃 (Dynamic programming)(Dynamic programming)背包問題背包問題 WinQSBWinQSB軟件應(yīng)用軟件應(yīng)用 動態(tài)規(guī)劃是解決多階段決策問題最優(yōu)化的一種數(shù)學(xué)方法，動態(tài)規(guī)劃是解決多階段決策問題最優(yōu)化的一種數(shù)學(xué)方法，大約產(chǎn)生于大約產(chǎn)生于50年代，年代，1951年美國數(shù)學(xué)家數(shù)學(xué)家貝爾曼年美國數(shù)學(xué)家數(shù)學(xué)家貝爾曼(R.Bellman)等人根據(jù)多階段決策

2、問題的特點，把多階段決策等人根據(jù)多階段決策問題的特點，把多階段決策問題變換為一系列相互聯(lián)系的單階段問題，然后逐個加以解決。問題變換為一系列相互聯(lián)系的單階段問題，然后逐個加以解決。與此同時他提出了解決這類問題的最優(yōu)性原理，研究了許多實與此同時他提出了解決這類問題的最優(yōu)性原理，研究了許多實際問題，從而創(chuàng)立了解決最優(yōu)化問題的一種新方法際問題，從而創(chuàng)立了解決最優(yōu)化問題的一種新方法動態(tài)規(guī)劃動態(tài)規(guī)劃（Dynmamic Programming），他的名著），他的名著動態(tài)規(guī)劃動態(tài)規(guī)劃于于1957年出版。年出版。 動態(tài)規(guī)劃問世之初，受計算技術(shù)水平的限制，對人們所關(guān)心動態(tài)規(guī)劃問世之初，受計算技術(shù)水平的限制，對人們

3、所關(guān)心的許多復(fù)雜問題難以進(jìn)行處理。以后的許多復(fù)雜問題難以進(jìn)行處理。以后,隨著計算技術(shù)的進(jìn)步隨著計算技術(shù)的進(jìn)步,動態(tài)動態(tài)規(guī)劃的思想方法規(guī)劃的思想方法,在工程技術(shù)、企業(yè)管理、工農(nóng)業(yè)生產(chǎn)以及軍事在工程技術(shù)、企業(yè)管理、工農(nóng)業(yè)生產(chǎn)以及軍事等部門都有廣泛的應(yīng)用。例如在企業(yè)管理方面，動態(tài)規(guī)劃可以等部門都有廣泛的應(yīng)用。例如在企業(yè)管理方面，動態(tài)規(guī)劃可以用來解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)調(diào)度問題、庫存用來解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)調(diào)度問題、庫存問題、裝載問題、排序問題、設(shè)備更新問題、生產(chǎn)過程最優(yōu)控問題、裝載問題、排序問題、設(shè)備更新問題、生產(chǎn)過程最優(yōu)控制問題等等。制問題等等。 第一節(jié)第一節(jié) 多階段決

4、策問題及其舉例多階段決策問題及其舉例 動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點在于，它可以把一個其特點在于，它可以把一個n 維決策問題變換為幾個一維最優(yōu)維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決?；瘑栴}，從而一個一個地去解決。 需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。必須對具體問題進(jìn)行具體分析，的一種途徑，而不是一種算法。必須對具體問題進(jìn)行具體分析，運(yùn)用動態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動態(tài)運(yùn)用動態(tài)規(guī)劃的

5、原理和方法，建立相應(yīng)的模型，然后再用動態(tài)規(guī)劃方法去求解。規(guī)劃方法去求解。 多階段決策過程最優(yōu)化的目標(biāo)，就是要在所有可采取的策多階段決策過程最優(yōu)化的目標(biāo)，就是要在所有可采取的策略中選取一個最優(yōu)的策略，從而使整個過程在預(yù)定目標(biāo)下達(dá)到略中選取一個最優(yōu)的策略，從而使整個過程在預(yù)定目標(biāo)下達(dá)到最好的活動效果。最好的活動效果。 所謂所謂多階段決策問題多階段決策問題是指這樣一類活動過程：由于它的特殊是指這樣一類活動過程：由于它的特殊性，可將整個過程按照時間劃分為若干個互相聯(lián)系的階段，在性，可將整個過程按照時間劃分為若干個互相聯(lián)系的階段，在它的每一個階段都需要作出決策，當(dāng)各個階段決策確定后，就它的每一個階段都需

6、要作出決策，當(dāng)各個階段決策確定后，就組成了一個決策序列，因而也就確定了整個過程的一條活動路組成了一個決策序列，因而也就確定了整個過程的一條活動路線。如下圖：線。如下圖： 12n狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài) 2 2、即在系統(tǒng)發(fā)展的不同時刻（或階段）根據(jù)系統(tǒng)所處的狀、即在系統(tǒng)發(fā)展的不同時刻（或階段）根據(jù)系統(tǒng)所處的狀態(tài)，不斷地做出決策；態(tài)，不斷地做出決策；一、動態(tài)決策問題的特點一、動態(tài)決策問題的特點 1 1、系統(tǒng)所處的狀態(tài)和時刻是進(jìn)行決策的重要因素；、系統(tǒng)所處的狀態(tài)和時刻是進(jìn)行決策的重要因素；3 3、找到不同時刻的最優(yōu)決策以及整個過程的最優(yōu)策略。、找到不同時刻的最

7、優(yōu)決策以及整個過程的最優(yōu)策略。二、多階段決策問題舉例二、多階段決策問題舉例 即如果由即如果由A A點經(jīng)過點經(jīng)過P P點和點和H H點而到達(dá)點而到達(dá)G G點是一條最短線路，則由點是一條最短線路，則由P P點出發(fā)經(jīng)過點出發(fā)經(jīng)過H H點到達(dá)終點的這條子線路，相對于從點到達(dá)終點的這條子線路，相對于從P P點出發(fā)到達(dá)終點出發(fā)到達(dá)終點的所有可呢選擇的不同線路來說，是頂是最短線路。點的所有可呢選擇的不同線路來說，是頂是最短線路。 【例【例6-16-1】生產(chǎn)與存貯問題。某工廠每月需供應(yīng)市場一定數(shù)】生產(chǎn)與存貯問題。某工廠每月需供應(yīng)市場一定數(shù)量的產(chǎn)品，并將所余產(chǎn)品存入倉庫。一般某月適當(dāng)增加產(chǎn)量可量的產(chǎn)品，并將所余

8、產(chǎn)品存入倉庫。一般某月適當(dāng)增加產(chǎn)量可降低生產(chǎn)成本，但超產(chǎn)部分存入倉庫會增加庫存費(fèi)用。要求確降低生產(chǎn)成本，但超產(chǎn)部分存入倉庫會增加庫存費(fèi)用。要求確定一個逐月的生產(chǎn)計劃，在滿足需求的條件下，使一年的生產(chǎn)定一個逐月的生產(chǎn)計劃，在滿足需求的條件下，使一年的生產(chǎn)與存貯費(fèi)用之和最小。與存貯費(fèi)用之和最小。 本例中，我們可以把每個月作為一個階段，全年分為本例中，我們可以把每個月作為一個階段，全年分為1212個階個階段逐次決策。段逐次決策。 【例【例6-26-2】設(shè)備更新問題。企業(yè)在使用設(shè)備時都要考慮設(shè)備】設(shè)備更新問題。企業(yè)在使用設(shè)備時都要考慮設(shè)備的更新問題，因為設(shè)備越陳舊所需的維修費(fèi)用越多，但購買新的更新問題

9、，因為設(shè)備越陳舊所需的維修費(fèi)用越多，但購買新設(shè)備則要一次性支出較大的費(fèi)用。現(xiàn)某企業(yè)要決定一臺設(shè)備未設(shè)備則要一次性支出較大的費(fèi)用。現(xiàn)某企業(yè)要決定一臺設(shè)備未來來8 8年的更新計劃，已預(yù)測了第年的更新計劃，已預(yù)測了第j j 年購買設(shè)備的價格為年購買設(shè)備的價格為K Ki i，設(shè)，設(shè)G Gj j為設(shè)備經(jīng)過為設(shè)備經(jīng)過j j年后的殘值，年后的殘值，C Cj j為設(shè)備連續(xù)使用為設(shè)備連續(xù)使用j j-1-1年后在第年后在第j j年的年的維修費(fèi)維修費(fèi)( (j j=1=1，2 2，n)n)，問應(yīng)在哪些年更新設(shè)備可使總費(fèi)用，問應(yīng)在哪些年更新設(shè)備可使總費(fèi)用最小。最小。 【例【例6-36-3】投資決策問題。某公司現(xiàn)有資金】

10、投資決策問題。某公司現(xiàn)有資金Q Q萬元，在今后萬元，在今后5 5年內(nèi)考慮給年內(nèi)考慮給A A、B B、C C、D D四個項目投資，這些項目投資的回收期四個項目投資，這些項目投資的回收期限、回報率均不相同，問該公司應(yīng)如何確定這些項目每年的投限、回報率均不相同，問該公司應(yīng)如何確定這些項目每年的投資額，使到第資額，使到第5 5年年末擁有資金的本利總額最大。這是一個年年末擁有資金的本利總額最大。這是一個5 5階階段決策問題。段決策問題。 第二節(jié)第二節(jié) 動態(tài)規(guī)劃的基本概念及基本方程動態(tài)規(guī)劃的基本概念及基本方程一、動態(tài)規(guī)劃的基本概念一、動態(tài)規(guī)劃的基本概念 【例【例6-46-4】最短路問題。今有如圖】最短路問

11、題。今有如圖6-26-2所示交通網(wǎng)絡(luò)，頂點連所示交通網(wǎng)絡(luò)，頂點連接線段上的數(shù)字表示兩地距離，求接線段上的數(shù)字表示兩地距離，求s s至至t t距離最短的線路。距離最短的線路。 1、階段、階段 把一個問題的過程，恰當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的把一個問題的過程，恰當(dāng)?shù)胤譃槿舾蓚€相互聯(lián)系的階段階段，以，以便于按一定的次序去求解。便于按一定的次序去求解。 描述階段的變量稱為描述階段的變量稱為階段變量階段變量，通常用通常用k表示。階段的劃分，表示。階段的劃分，一般是根據(jù)時間和空間的自然特征來進(jìn)行的，但要便于問題轉(zhuǎn)一般是根據(jù)時間和空間的自然特征來進(jìn)行的，但要便于問題轉(zhuǎn)化為多階段決策。化為多階段決策。8A1A2A

12、3sB1B2B3C1C2t6473643562652744445 例例6-46-4中，從中，從s s到到t t可以分成四個可以分成四個階段：階段：s sA(AA(A有三種選擇，有三種選擇，A A1 1或或A A2 2或或A A3 3) )，A AB(BB(B1 1或或B B2 2或或B B3 3) )，B BC(CC(C1 1或或C C2 2) )，C Ct t，因此，因此k k1 1，2 2，3 3，4 4。 表示每個階段開始所處的表示每個階段開始所處的自然狀況或客觀條件自然狀況或客觀條件。 狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)

13、狀態(tài)允許集合，允許集合，第第k階段的可能狀態(tài)集用階段的可能狀態(tài)集用Sk表示。表示。2、狀態(tài)、狀態(tài) 描述各階段狀態(tài)的變量稱為描述各階段狀態(tài)的變量稱為狀態(tài)變量狀態(tài)變量，常用，常用s sk k表示第表示第k k階段階段的狀態(tài)變量。的狀態(tài)變量。 在例在例6-46-4中，第一階段有一個狀態(tài)中，第一階段有一個狀態(tài)s s，則，則S S1 1=s=s；第二階段的；第二階段的狀態(tài)有狀態(tài)有A A1 1、A A2 2、A A3 3三個，則三個，則S S2 2=A=A1 1,A,A2 2,A,A3 3 ；第三階段的狀態(tài)也有；第三階段的狀態(tài)也有B B1 1、B B2 2和和B B3 3三個，則三個，則S S3 3=B=

14、B1 1,B,B2 2,B,B3 3 ；第四階段的狀態(tài)有兩個，；第四階段的狀態(tài)有兩個，C C1 1和和C C2 2，記為則，記為則S S4 4=C=C1 1,C,C2 2 。 8A1A2A3sB1B2B3C1C2t6473643562652744445狀態(tài)變量的特征：狀態(tài)變量的特征：n能描述過程的演變特征；能描述過程的演變特征； n滿足無后效性滿足無后效性指系統(tǒng)從某個階段往后的發(fā)展，完指系統(tǒng)從某個階段往后的發(fā)展，完全由本階段所處的狀態(tài)及其往后的決策決定，與系統(tǒng)全由本階段所處的狀態(tài)及其往后的決策決定，與系統(tǒng)以前的狀態(tài)和決策無關(guān)。即過程過去的歷史只能通過以前的狀態(tài)和決策無關(guān)。即過程過去的歷史只能通

15、過當(dāng)前的狀態(tài)去影響未來的發(fā)展，當(dāng)前狀態(tài)是未來過程當(dāng)前的狀態(tài)去影響未來的發(fā)展，當(dāng)前狀態(tài)是未來過程的初始狀態(tài)。的初始狀態(tài)。n可知性可知性各階段狀態(tài)變量的值直接或間接均為已知。各階段狀態(tài)變量的值直接或間接均為已知。 3.3.決策和策略決策和策略 當(dāng)各階段的狀態(tài)確定以后，就可以做出不同的選擇，從而確當(dāng)各階段的狀態(tài)確定以后，就可以做出不同的選擇，從而確定下一階段的狀態(tài)，這種選擇稱為定下一階段的狀態(tài)，這種選擇稱為決策決策。 表示決策的變量稱為表示決策的變量稱為決策變量決策變量，用，用u uk k(s(sk k) )表示第表示第k k階段狀態(tài)為階段狀態(tài)為s sk k時的決策變量。在實際問題中，決策變量的取值

16、往往限制在一時的決策變量。在實際問題中，決策變量的取值往往限制在一定范圍內(nèi)，我們稱該范圍為定范圍內(nèi)，我們稱該范圍為允許決策集合允許決策集合，用，用D Dk k(s(sk k) )表示第表示第k k階階段狀態(tài)為段狀態(tài)為sksk時的允許決策集合，顯然時的允許決策集合，顯然u uk k(s(sk k)D)Dk k(s(sk k) )。 在例在例6-46-4中，從第二階段的狀態(tài)中，從第二階段的狀態(tài)A A1 1出發(fā)，可選擇下一階段出發(fā)，可選擇下一階段到達(dá)到達(dá)B B1 1、B B2 2或或B B3 3，即第二階段狀態(tài)為，即第二階段狀態(tài)為A A1 1時的允許決策集合為時的允許決策集合為D D2 2(A(A1

17、 1)=B)=B1 1，B B2 2，B B3 3 。如決定選。如決定選B B2 2，則可表示為，則可表示為u u2 2(A(A1 1)=B)=B2 2。 各階段的決策確定后，整個問題的決策序列就構(gòu)成一個各階段的決策確定后，整個問題的決策序列就構(gòu)成一個策策略略。含。含n n個階段的動態(tài)規(guī)劃問題的策略可表示為個階段的動態(tài)規(guī)劃問題的策略可表示為 P P1n1n=u1(s1)=u1(s1)，u u2 2( (s s2 2) )，u un n( (s sn n)。自第。自第k k 階段開始到最后第階段開始到最后第n n階段的決策序階段的決策序列稱為列稱為k k子策略，記為子策略，記為P Pknkn=u

18、 uk k( (s sk k) )，u uk k+1+1( (s sk k+1+1) )，u un n( (s sn n)。 8A1A2A3sB1B2B3C1C2t64736435626527444454.4.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 動態(tài)規(guī)劃中本階段的狀態(tài)往往是上一階段狀態(tài)和上一階段動態(tài)規(guī)劃中本階段的狀態(tài)往往是上一階段狀態(tài)和上一階段的決策結(jié)果。如果給定了第的決策結(jié)果。如果給定了第k k階段的狀態(tài)階段的狀態(tài)s sk k，本階段決策為，本階段決策為u uk k( (s sk k) )，則第，則第k k+1+1階段的狀態(tài)階段的狀態(tài)s sk k+1+1也就完全確定，它們的關(guān)系可也就完全確定，它們的關(guān)

19、系可表示為：表示為： 由于它表示了由由于它表示了由k k階段到階段到k k+1+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，所以稱階段的狀態(tài)轉(zhuǎn)移規(guī)律，所以稱為狀態(tài)轉(zhuǎn)移方程。為狀態(tài)轉(zhuǎn)移方程。 kkkkusTs,1狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程。如果第程。如果第k k階段狀態(tài)變量階段狀態(tài)變量s sk k的值、該階段的決策變量一經(jīng)確的值、該階段的決策變量一經(jīng)確定，第定，第k k+1+1階段狀態(tài)變量階段狀態(tài)變量s sk k+1+1的值也就確定。的值也就確定。圖示如下：圖示如下：12ks1u1s2u2s3skuksk+15.5.指標(biāo)函數(shù)指標(biāo)函數(shù) 階段

20、指標(biāo)函數(shù)階段指標(biāo)函數(shù) 階段指標(biāo)函數(shù)是指第階段指標(biāo)函數(shù)是指第k k階段，從狀態(tài)階段，從狀態(tài)s sk k出發(fā)，采取決策出發(fā)，采取決策u uk k( (s sk k) )時的效益，用時的效益，用v vk k(s(sk k，u uk k) )表示。表示。 過程指標(biāo)函數(shù)過程指標(biāo)函數(shù) 過程指標(biāo)函數(shù)是指從第過程指標(biāo)函數(shù)是指從第k k階段的狀態(tài)階段的狀態(tài)s sk k( (k k1 1，2 2，n n) )出出發(fā)，采取某種策略到第發(fā)，采取某種策略到第n n階段的終止?fàn)顟B(tài)時的效益，它與所選階段的終止?fàn)顟B(tài)時的效益，它與所選取的策略有關(guān)，因此常記作：取的策略有關(guān)，因此常記作： ), 2 , 1(),(1,nkussu

21、sVnnkkknk 常用的指標(biāo)函數(shù)的形式有各階段指標(biāo)函數(shù)的和的形式和積常用的指標(biāo)函數(shù)的形式有各階段指標(biāo)函數(shù)的和的形式和積的形式兩種。的形式兩種。 和的形式和的形式 nkjjjjnkkknkusvususV),(),(1,),(),(11, 1nkknkkkkuusVusv積的形式積的形式 ),(),(1,jnkjjjnkkknkusvususV),(),(11, 1nkknkkkkuusVusv 指標(biāo)函數(shù)的最優(yōu)值稱為最優(yōu)值函數(shù)，是指對某一確定狀態(tài)指標(biāo)函數(shù)的最優(yōu)值稱為最優(yōu)值函數(shù)，是指對某一確定狀態(tài)選取最優(yōu)策略后得到的指標(biāo)函數(shù)值。對應(yīng)于從狀態(tài)選取最優(yōu)策略后得到的指標(biāo)函數(shù)值。對應(yīng)于從狀態(tài)s sk k

22、出發(fā)的最出發(fā)的最優(yōu)子策略的最優(yōu)值函數(shù)，記為優(yōu)子策略的最優(yōu)值函數(shù)，記為f fk k(s(sk k) )，則有：，則有： ),()(1,nkkknkkkususVoptsf其中其中optopt表示最優(yōu)化，可根據(jù)具體問題取表示最優(yōu)化，可根據(jù)具體問題取max(max(求最大求最大) )或或min(min(求求最小最小) )。 問題：動態(tài)規(guī)劃的最優(yōu)解和最優(yōu)值各是什么？問題：動態(tài)規(guī)劃的最優(yōu)解和最優(yōu)值各是什么？最優(yōu)解：最優(yōu)策略最優(yōu)解：最優(yōu)策略P1n ， 最優(yōu)值：最優(yōu)指標(biāo)最優(yōu)值：最優(yōu)指標(biāo)f1。二、動態(tài)規(guī)劃的數(shù)學(xué)模型二、動態(tài)規(guī)劃的數(shù)學(xué)模型 動態(tài)規(guī)劃的數(shù)學(xué)模型可以描述如下：動態(tài)規(guī)劃的數(shù)學(xué)模型可以描述如下： ),(

23、2211, 1nnnusususVopt nksDsuSsusTskkkkkkkkkk, 2 , 1,1建立實際問題的動態(tài)規(guī)劃模型一般可遵循以下步驟：建立實際問題的動態(tài)規(guī)劃模型一般可遵循以下步驟： 第一，按時間或空間順序?qū)⒍嚯A段決策問題劃分為適當(dāng)?shù)牡谝唬磿r間或空間順序?qū)⒍嚯A段決策問題劃分為適當(dāng)?shù)碾A段；階段； 第二，恰當(dāng)選擇狀態(tài)變量第二，恰當(dāng)選擇狀態(tài)變量sksk，使它既能確切地描述過程的，使它既能確切地描述過程的演變，又滿足過程的無后效性；演變，又滿足過程的無后效性； 第三，確定決策變量第三，確定決策變量u uk k及每階段的容許決策集及每階段的容許決策集D Dk k( (s sk k) )。

24、狀。狀態(tài)變量和決策變量可以是連續(xù)的，也可以是離散的；態(tài)變量和決策變量可以是連續(xù)的，也可以是離散的； 第四，正確寫出狀態(tài)轉(zhuǎn)移方程第四，正確寫出狀態(tài)轉(zhuǎn)移方程s sk k+1+1T Tk k( (s sk k，u uk k) )； 第五，正確寫出指標(biāo)函數(shù)第五，正確寫出指標(biāo)函數(shù)V Vk k, ,n n，它應(yīng)具有可分離性，并滿，它應(yīng)具有可分離性，并滿足遞推關(guān)系。足遞推關(guān)系。 （1）基本原理略。子過程來說必為最優(yōu)策至點的為起對于以），子策略（則對任何是最優(yōu)策略，最優(yōu)性原理：若nksPnkkPBellmankknn11以最短路為例說明三、動態(tài)規(guī)劃的基本原理和基本方程三、動態(tài)規(guī)劃的基本原理和基本方程 （2 2

25、）基本方程）基本方程 在在n n階段決策過程中，當(dāng)指標(biāo)函數(shù)滿足階段決策過程中，當(dāng)指標(biāo)函數(shù)滿足 時，根時，根據(jù)最優(yōu)值函數(shù)的定義有：據(jù)最優(yōu)值函數(shù)的定義有：nkjjjjnkusvV),(,)(),()(11)(kkkkksDukksfusvoptsfkkk當(dāng)指標(biāo)函數(shù)滿足當(dāng)指標(biāo)函數(shù)滿足 時，有：時，有：),(,jnkjjjnkusvV)(),()(11)(kkkkksDukksfusvoptsfkkk動態(tài)規(guī)劃的求解有兩種基本方法：逆序解法和順序解法。動態(tài)規(guī)劃的求解有兩種基本方法：逆序解法和順序解法。 若尋優(yōu)方向與實際行進(jìn)方向相反，即從最后一階段開始計若尋優(yōu)方向與實際行進(jìn)方向相反，即從最后一階段開始計算

26、，逐段前推，求得全過程的最優(yōu)解，則稱為算，逐段前推，求得全過程的最優(yōu)解，則稱為逆序解法逆序解法。 若尋優(yōu)方向與實際行進(jìn)方向相同，計算時從第一階段開始若尋優(yōu)方向與實際行進(jìn)方向相同，計算時從第一階段開始向后遞推，計算后一階段要用到前一階段的結(jié)果，最后一階段向后遞推，計算后一階段要用到前一階段的結(jié)果，最后一階段的結(jié)果就是全過程的最優(yōu)結(jié)果，則稱為的結(jié)果就是全過程的最優(yōu)結(jié)果，則稱為順序解法順序解法。 下面我們用例下面我們用例6-46-4來說明順序解法。來說明順序解法。 將求將求s s至至t t的最短路問題視為一個四階段決策問題，設(shè)：的最短路問題視為一個四階段決策問題，設(shè)： s sk k 第第k k階段的

27、初始狀態(tài)。階段的初始狀態(tài)。 s sk k+1+1 第第k k階段的終止?fàn)顟B(tài)。階段的終止?fàn)顟B(tài)。 u uk k 第第k k階段選擇的路線。狀態(tài)轉(zhuǎn)移方程：階段選擇的路線。狀態(tài)轉(zhuǎn)移方程：s sk ku uk k( (s sk k+1+1) ) v vk k( (s sk k+1+1，u uk k)第第k k階段選擇路線階段選擇路線ukuk時增加的距離，即從初時增加的距離，即從初 始狀態(tài)始狀態(tài)s sk k到到s sk k+1+1的距離。的距離。 11,kkkkkssdusvf fk k( (s sk k+1+1)從起點從起點s s到第到第k k階段終止?fàn)顟B(tài)階段終止?fàn)顟B(tài)sksk+1+1 的距離。的距離。

28、于是，可得下面的動態(tài)規(guī)劃基本方程：于是，可得下面的動態(tài)規(guī)劃基本方程： )4 , 3 , 2 , 1()(),(min11)(1ksfssdsfkkkksDukkkkkk k=0=0時，時，f f0 0( (s s1 1)= )= f f0 0(s)=0(s)=0，這是邊界條件。，這是邊界條件。 k k=1=1時，時，S S2 2=A=A1 1，A A2 2，A A3 3 8A1A2A3s648)(11Af6)(21Af4)(31Afk k=2=2時，時，S S3 3=B=B1 1，B B2 2，B B3 3 B1B2B38A1A2A3s64736435626)(),()(),()(),(min

29、)(31132112111112AfBAdAfBAdAfBAdBf10466483min即從即從s s到到B B1 1的最短路線為：的最短路線為：sAsA2 2BB1 1或或sAsA3 3BB1 1。 )(),()(),()(),(min)(31232122112122AfBAdAfBAdAfBAdBf6426386min即從即從s s到到B B2 2的最短路線為：的最短路線為：sAsA3 3BB2 2。 )(),()(),()(),(min)(31332132113133AfBAdAfBAdAfBAdBf10466587min即從即從s s到到B B3 3的最短路線為：的最短路線為：sAsA

30、3 3BB3 3。 C1C2B1B2B38A1A2A3s64736435626527444k k=3=3時，時，S S4 4=C=C1 1，C C2 2 )(),()(),()(),(min)(32132212121113BfCBdBfCBdBfCBdCf1210467102min即從即從s s到到C C1 1的最短路線為：的最短路線為：sAsA2 2BB1 1CC1 1 或或sAsA3 3BB1 1CC1 1。 )(),()(),()(),(min)(32232222122123BfCBdBfCBdBfCBdCf1010464105min即從即從s s到到C C2 2的最短路線為：的最短路線

31、為：sAsA3 3BB2 2CC2 2。 k k=4=4時，時，S S5 5=t =t )(),()(),(min)(2321315CftCdCftCdtf15105124min即從即從s s到到t t的最短路線為：的最短路線為：sAsA3 3BB2 2CC2 2tt。 t4C1C2B1B2B38A1A2A3s647364356265274445即從即從s s到到t t的最短距離為：的最短距離為：4+2+4+5=154+2+4+5=15AEB1B2B3C1C2C3D1D229531225156468101312111410解：設(shè)階段k=1，2，3，4依次表示4個階段選路的過程； 狀態(tài)sk表示k

32、階段初可能處的位置；決策xk表示k階段初可能選擇的路；階段指標(biāo)vk表示k階段與所選擇的路段相應(yīng)的路長；指標(biāo)函數(shù) vk4 = 表示k至4階段的總路長；v ,14, 0, 51kffvMinfkkk遞推公式：用逆序解法用逆序解法來求最短路來求最短路問題問題AEB1B2B3C1C2C3D1D2295312251564681013121114104k Sk uk vk vkn=vk+fk+1 fkknP21DDEE02052525EDED21321DD21DD21DDC1C2C3935610829532556210588712C1D1EC2D2EC3D2Ek Sk uk vk vkn=vk+fk+1

33、fkknPAEB1B2B3C1C2C3D1D2295312251564681013121114102B1B2B321CC141271481220B1C1D1EP21CCC41061247108614B2C1D1EP21CCC111213121171281319B3C2D2Ek Sk xk vk vkn=vk+fk+1 fkknPAEB1B2B3C1C2C3D1D2295312251564681013121114101A321BBB15219152021419AB2C1D1EP*14=AB2C1D1Ef1 = 19（最短路）（最短距）練習(xí)練習(xí)1：AB1B2C1C2C3C4D1D2D3E1E2E3

34、F1F2G53136876368533842221333525664最優(yōu)路線為：最優(yōu)路線為：A B1 C2 D1 E2 F2 G 路長路長18求從求從A到到G的最短路徑的最短路徑3k=5k=5，出發(fā)點，出發(fā)點E1E1、E2E2、E3E3 73543min,min2621516115FfFEdFfFEdu5(E1)=F1E1 F1 G 53245min,min262251612525FfFEdFfFEdfEAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643)(15Efu5(E2)=F2E2 F2 G 93646min,min2

35、62351613535FfFEdFfFEdfEu5(E3)=F2E3 F2 Gk=6k=6,F1 G f f6 6(F1)=4(F1)=4F F2 2 G ,f,f6 6(F2)=3(F2)=3k=4，f4(D1)=7 u4(D1)=E2f4(D2)=6 u4(D2)=E2f4(D3)=8 u4(D3)=E2k=2, f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3f3(C1)=13 u3(C1)=D1f3(C2)=10 u3(C2)=D1f3(C3)=9 u3(C3)=D1f3(C4)=12 u3(C4)=D3k=3,= minf1(A)= mind1(A,B1

36、)+ f2(B1) d1(A,B2)+ f2(B2)5+133+16=18k=1,u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u5(E1)=F1E1 F1 Gu5(E2)=F2E2 F2 Gu5(E3)=F2E3 F2 G7 5 9 u5(E2)=F2u6(F2)=G最優(yōu)策略最優(yōu)策略AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643第三節(jié)第三節(jié) 資源分配問題資源分配問題 資源分配問題就是將一定數(shù)量的一種或幾種資源恰當(dāng)?shù)胤仲Y源分配問

37、題就是將一定數(shù)量的一種或幾種資源恰當(dāng)?shù)胤峙浣o若干使用者，以獲取最大效益。這里的資源可以是資金、配給若干使用者，以獲取最大效益。這里的資源可以是資金、設(shè)備、原材料、勞動力等。資源分配問題是動態(tài)規(guī)劃的典型應(yīng)設(shè)備、原材料、勞動力等。資源分配問題是動態(tài)規(guī)劃的典型應(yīng)用之一。本節(jié)和后面幾節(jié)中我們都采用逆序解法來求解動態(tài)規(guī)用之一。本節(jié)和后面幾節(jié)中我們都采用逆序解法來求解動態(tài)規(guī)劃問題。劃問題。 一、一維資源分配問題一、一維資源分配問題 假設(shè)某部門掌握總數(shù)為假設(shè)某部門掌握總數(shù)為a a的某種資源，現(xiàn)有的某種資源，現(xiàn)有n n個項目提出對個項目提出對這種資源的需求。若把數(shù)量為這種資源的需求。若把數(shù)量為xkxk的資源分

38、配給第的資源分配給第k k個項目，則個項目，則其相應(yīng)的收益為其相應(yīng)的收益為g gk k( (x xk k) )。問應(yīng)如何分配這種資源，才能獲得最。問應(yīng)如何分配這種資源，才能獲得最大收益？大收益？ 這個問題可寫成如下的規(guī)劃模型：這個問題可寫成如下的規(guī)劃模型： nkkkxgz1)(max), 2 , 1( , 01nkxaxknkk 把它看做一個多階段決策問題，從而應(yīng)用動態(tài)規(guī)劃方法求把它看做一個多階段決策問題，從而應(yīng)用動態(tài)規(guī)劃方法求解。確定一個項目的資源分配數(shù)量視為一個階段，于是共有解。確定一個項目的資源分配數(shù)量視為一個階段，于是共有n n個階段。令：個階段。令： s sk k 分配給第分配給第k

39、 k個項目到第個項目到第n n個項目的資源數(shù)量之和。個項目的資源數(shù)量之和。 x xk k 分配給第分配給第k k個項目的資源數(shù)量。個項目的資源數(shù)量。 v vk k(s(sk k，x xk k)從從s sk k中取出中取出x xk k數(shù)量的資源分配給第數(shù)量的資源分配給第k k個項目個項目 可獲得的收益。即：可獲得的收益。即： )(),(kkkkkxgxsvf fk k(s(sk k)將數(shù)量為將數(shù)量為s sk k的資源分配給第的資源分配給第k k個項目到第個項目到第n n個項個項 目可獲得的最大收益。目可獲得的最大收益。 于是，可得到下面的狀態(tài)轉(zhuǎn)移方程和動態(tài)規(guī)劃基本方程：于是，可得到下面的狀態(tài)轉(zhuǎn)移

40、方程和動態(tài)規(guī)劃基本方程： ), 2 , 1(1nkxsskkk0)() 1 ,()(),(max)(1111)(nnkkkkksDxkksfnksfusvsfkkk 【例【例6-56-5】某公司有資金】某公司有資金1010萬元，若投資于項目萬元，若投資于項目x xi i(i=1,2,3)(i=1,2,3)的投資額為的投資額為x xi i時，其收益分別為時，其收益分別為g(xg(x1 1)=4x)=4x1 1, g(x, g(x2 2)=9x)=9x2 2, , g(xg(x3 3)=2x)=2x3 32 2, ,問應(yīng)如何分配投資數(shù)額才能使總收益最大？問應(yīng)如何分配投資數(shù)額才能使總收益最大？ 解解

41、: :該問題的靜態(tài)模型為：該問題的靜態(tài)模型為： 2321294maxxxxz0,10321321xxxxxx 將投資項目排序時，首先考慮對項目將投資項目排序時，首先考慮對項目1 1的投資，然后再考慮的投資，然后再考慮對項目對項目2 2的投資，最后考慮對項目的投資，最后考慮對項目3 3的投資，這樣可以把問題劃的投資，這樣可以把問題劃分為分為3 3個階段，每個階段只決定對一個項目應(yīng)投資的金額。這個階段，每個階段只決定對一個項目應(yīng)投資的金額。這樣就把問題轉(zhuǎn)化為一個樣就把問題轉(zhuǎn)化為一個3 3段決策過程。段決策過程。 通?？梢园褯Q策變量通常可以把決策變量u uk k定為原問題中的變量定為原問題中的變量x

42、 xk k，即設(shè)：，即設(shè)：u uk k=x=xk k (k=1,2,3)(k=1,2,3)把每個階段可供使用的資金定為狀態(tài)變量把每個階段可供使用的資金定為狀態(tài)變量s sk k，初始狀態(tài)，初始狀態(tài)s s1 1=10=10。當(dāng)?shù)谝浑A段當(dāng)?shù)谝浑A段(k =1)(k =1)時，有：時，有：11110 xs當(dāng)?shù)诙A段當(dāng)?shù)诙A段(k =2)(k =2)時，有：時，有：22112xss第第k k 階段時，有：階段時，有：kkkkkxss11于是，有：于是，有：階段階段k=1,2,3k=1,2,3； 狀態(tài)變量狀態(tài)變量s sk k：第：第k k段可以投資于第段可以投資于第k k到第到第3 3個項目的資金；個項目的

43、資金；決策變量決策變量x xk k：決定給第：決定給第k k個項目投資的資金；個項目投資的資金； 狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：s sk+1k+1=s=sk k-x-xk k 最優(yōu)目標(biāo)函數(shù)最優(yōu)目標(biāo)函數(shù)f fk k(s(sk k) )：可投資金為：可投資金為s sk k時，投資第時，投資第k-3k-3項所得項所得的最大收益。的最大收益。 該問題的動態(tài)規(guī)劃基本方程為：該問題的動態(tài)規(guī)劃基本方程為： 0)() 1 , 2 , 3()()(max)(44110sfksfxgsfkkkksxkkkk33 ,)(kiiikxgV指標(biāo)函數(shù)：指標(biāo)函數(shù)：下面用逆序解法求解例下面用逆序解法求解例6-56-5：當(dāng)當(dāng)k=

44、3k=3時：時：)2(max)(2303333xsfsx 顯然，當(dāng)顯然，當(dāng)x x3 3=s=s3 3時，時，f f3 3(s(s3 3) )取得極大值，即：取得極大值，即：23230332)2(max)(33sxsfsx當(dāng)當(dāng)k=2k=2時：時：)(29max)(9max)(222203320222222xsxsfxsfsxsx2222222)(29),(xsxxsh令：令： 0) 1)(492222xsdxdh由由 2222222)(2)0(ssfsf所以所以 為極小值點。為極小值點。 4922 sx042222dxhd而：而： 4922 sx解得：解得： 故極大值只可能在故極大值只可能在0,

45、s0,s2 2 的端點處取得，則：的端點處取得，則：f f2 2(0)(0)與與f f2 2(s(s2 2) )的關(guān)系，有以下三種情況：的關(guān)系，有以下三種情況：f f2 2(0)=f(0)=f2 2(s(s2 2) )，解得：，解得：292s2*2*20sxx 或f f2 2(0)f(0)f2 2(s(s2 2) )，解得：，解得：292s0*2xf f2 2(0)f(0)f2 2(s(s2 2) )，解得：，解得：292s2*2sx 當(dāng)當(dāng)k=1k=1時：時：)(4max)(22101111sfxsfsx0*1x11110011110011959max)(94max)(11sxsxsxsfxx

46、f f2 2(s(s2 2)=9s)=9s2 2時：時：f f2 2(s(s2 2)=2s)=2s2 22 2時：時：2910010112xss，與，與s s2 29/29/2矛盾，所以舍去。矛盾，所以舍去。 2111111)(24),(xsxxsh令：令： )(24max)10(211110011xsxfx0) 1)(441111xsdxdh由由 111 sx解得：解得： 所以所以 為極小值點。為極小值點。 111 sx012112dxhd而：而： 故極大值只可能在故極大值只可能在0,s0,s1 1 的端點處取得。的端點處取得。比較兩個端點：比較兩個端點：01x2002)10(221 sf1

47、01x40)10(1f再由狀態(tài)轉(zhuǎn)移方程順推得：再由狀態(tài)轉(zhuǎn)移方程順推得： 2910*112xss因為因為 292s所以：所以：0*2x10*223xss103*3 sx 例例 設(shè)有設(shè)有500500萬元資金用于擴(kuò)建三個工廠萬元資金用于擴(kuò)建三個工廠A A、B B、C C，各廠獲，各廠獲得資金后的利潤增長額與投資數(shù)有關(guān)，詳細(xì)數(shù)據(jù)如下表所示：得資金后的利潤增長額與投資數(shù)有關(guān)，詳細(xì)數(shù)據(jù)如下表所示： 投資數(shù)投資數(shù)( (百萬元百萬元) )0 01 12 23 34 45 5利潤利潤增長增長額額A A0 02 22 23 33 33 3B B0 00 01 12 24 47 7C C0 01 12 23 34

48、45 5解：解：將問題視為三個階段決策問題。將問題視為三個階段決策問題。x xk k表示表示k k階段初可用的投資數(shù)；階段初可用的投資數(shù)； u uk k為分配給第為分配給第k k個工廠的資金數(shù)；個工廠的資金數(shù)； 狀態(tài)轉(zhuǎn)移方程為狀態(tài)轉(zhuǎn)移方程為x xk+1k+1x xk k-u-uk k f fk k(x(xk k) )表示表示x xk k資金被分配給工廠資金被分配給工廠k-nk-n后，所得利潤增長額。后，所得利潤增長額。 問應(yīng)如何確定這三個工廠的投資數(shù)，使總的利潤增長額為問應(yīng)如何確定這三個工廠的投資數(shù)，使總的利潤增長額為最大？最大？ 則該問題的動態(tài)規(guī)劃基本方程為：則該問題的動態(tài)規(guī)劃基本方程為：

49、0)() 1 , 2 , 3()()(max)(4411xfkxfgxfkkkkukkk 當(dāng)當(dāng)k=3k=3時，時，x x3 3的可能取值為的可能取值為0 0、1 1、2 2、3 3、4 4、5 5，這些投資全，這些投資全部分配給部分配給C C工廠，即工廠，即u u3 3=x=x3 3。因此有以下關(guān)系式：。因此有以下關(guān)系式：)(max)(333333gxfxu 00max)(max)0(33033gfu4)(33x若若x x3 3=0=0，則：，則：若若x x3 3=1=1，則：，則：11max)(max) 1 (33133gfu若若x x3 3=2=2，則：，則： 22max)(max)2(3

50、3233gfu若若x x3 3=3=3，則：，則： 32max)(max)3(33333gfu若若x x3 3=4=4，則：，則： 44max)(max)4(33333gfu3)(33x0)(33x1)(33x2)(33x若若x x3 3=5=5，則：，則： 55max)(max)5(33333gfu用表格表示為：用表格表示為：5 54 43 32 21 10 05 54 43 32 21 10 0 u u3 3x x3 333ug 33xf 33x5)(33x012345012345012345 當(dāng)當(dāng)k=2k=2時，時，x x2 2的可能取值為的可能取值為0 0、1 1、2 2、3 3、4

51、4、5 5，這些投資全部分配給，這些投資全部分配給B B工廠工廠和和C C工廠，即工廠，即u u2 2xx2 2。因此有以下關(guān)系式：。因此有以下關(guān)系式：)()(max)(33222222xfgxfxu000max)()(max)0(0332223222xuxuxfgf若若x x2 2=0=0，則，則u u2 2=x=x2 2=0=00)(22x 若若x x2 2=1=1，則，則u u2 2的取值可以為的取值可以為0 0、1 1，利用狀態(tài)轉(zhuǎn)移方程知，利用狀態(tài)轉(zhuǎn)移方程知x x3 3的取值為的取值為1 1、0 0。10010max)0() 1 () 1 ()0(max)()(max) 1 (1 ,

52、032321 , 033221 , 02222uuufgfgxfgf0)(22x 若若x x2 2=2=2，則，則u u2 2的取值可以為的取值可以為0 0、1 1、2 2，利用狀態(tài)轉(zhuǎn)移方程知，利用狀態(tài)轉(zhuǎn)移方程知x x3 3的取值為的取值為2 2、1 1、0 0。2011020max)0()2() 1 () 1 ()2()0(max)()(max)2(3232322, 1 , 033222, 1 , 0222fgfgfgxfgfuu0)(22x 若若x x2 2=3=3，則，則u u2 2的取值可以為的取值可以為0 0、1 1、2 2、3 3，利用狀態(tài)轉(zhuǎn)移方程，利用狀態(tài)轉(zhuǎn)移方程知知x x3 3

53、的取值為的取值為3 3、2 2、1 1、0 0。 302112030max03) 1 ()2()2() 1 ()3()0(max)()(max)3(323232323 , 2, 1 , 033223 , 2, 1 , 0222fgfgfgfgxfgfuu0)(22x 若若x x2 2=4=4，則，則u u2 2的取值可以為的取值可以為0 0、1 1、2 2、3 3、4 4，利用狀態(tài)轉(zhuǎn)移方，利用狀態(tài)轉(zhuǎn)移方程知程知x x3 3的取值為的取值為4 4、3 3、2 2、1 1、0 0。 40412213040max0413)2()2()3() 1 ()4()0(max)()(max)4(3232323

54、2324, 3 , 2, 1 , 033224, 3 , 2, 1 , 0222fgfgfgfgfgxfgfuu40)(22或x 若若x x2 2=5=5，則，則u u2 2的取值可以為的取值可以為0 0、1 1、2 2、3 3、4 4、5 5，利用狀態(tài)轉(zhuǎn)，利用狀態(tài)轉(zhuǎn)移方程知移方程知x x3 3的取值為的取值為5 5、4 4、3 3、2 2、1 1、0 0。 7071422314050max051423)3()2()4() 1 ()5()0(max)()(max)5(3232323232325 , 4, 3 , 2, 1 , 033225 , 4, 3 , 2, 1 , 0222fgfgfgf

55、gfgfgxfgfuu5)(22x用表格表示為：用表格表示為：5 54 43 32 21 10 05 54 43 32 21 10 0 u u2 2x x2 222322uxfug 2*2xf 22x0+00+10+20+30+40+50+00+10+20+30+41+01+11+21+32+02+12+24+04+17+001234700000/455 55 54 43 32 21 10 0 u u1 1x x1 1 12115ufug 11xu 11xf0+72+42+33+23+13+0705 54 43 32 21 10 05 54 43 32 21 10 0 u u2 2x x2 2

56、22322uxfug22xf 22x0+00+10+20+30+40+50+00+10+20+30+41+01+11+21+32+02+12+24+04+17+00123470123455 54 43 32 21 10 05 54 43 32 21 10 0 u u3 3x x3 333ug 33xf 33x012345012345012345 7031323324270max051423)3()2()4() 1 ()5()0(max)()(max)5(2122212121215 , 4, 3 , 2, 1 , 022115 , 4, 3 , 2, 1 , 0111fgfgfgfgfgfgxf

57、gfuu0)(11x 當(dāng)當(dāng)k=1k=1時，時，x x1 1的可能取值為的可能取值為5 5，這些投資全部分配給，這些投資全部分配給A A工廠、工廠、B B工廠和工廠和C C工廠，即工廠，即u u1 1xx1 1。因此有以下關(guān)系式：。因此有以下關(guān)系式：)()(max)(22111111xfgxfxu用表格表示為：用表格表示為：5 55 54 43 32 21 10 0 u u1 1x x1 1 12115ufug 11xu 11xf0+72+42+33+23+13+070二、二維資源分配問題二、二維資源分配問題 此問題可寫成如下數(shù)學(xué)模型：此問題可寫成如下數(shù)學(xué)模型： ), 2 , 1(0, 0),(

58、max111niyxbyaxtSyxgziinjiniiniiii 在資源分配問題中，若考慮的資源有兩種時，便是二維資在資源分配問題中，若考慮的資源有兩種時，便是二維資源分配問題。一般的二維資源分配問題可敘述如下：某部門具源分配問題。一般的二維資源分配問題可敘述如下：某部門具有總數(shù)分別為有總數(shù)分別為a a和和b b的兩種資源，現(xiàn)有的兩種資源，現(xiàn)有n n個項目提出對這兩種資個項目提出對這兩種資源的需求。若把數(shù)量為源的需求。若把數(shù)量為x xk k的資源的資源A A和數(shù)量為和數(shù)量為y yk k的資源的資源B B分配給項分配給項目目k k，可獲得收益，可獲得收益v vk k( (x xk k，y yk

59、 k) )。問應(yīng)如何分配這兩種資源，使總。問應(yīng)如何分配這兩種資源，使總收益最大？收益最大？ 用動態(tài)規(guī)劃方法來求解，狀態(tài)變量和決策變量要取二維的。用動態(tài)規(guī)劃方法來求解，狀態(tài)變量和決策變量要取二維的。 設(shè)：設(shè)： ),(),(kkkkkkkkyxvyxtsv ( (s sk k，t tk k)s sk k和和t tk k分別為分配給第分別為分配給第k k至第至第n n個項目的資源個項目的資源A A和和資源資源B B的總量。的總量。 ( (x xk k，y yk k)x xk k和和y yk k分別為分配給第分別為分配給第k k個項目的資源個項目的資源A A和資源和資源B B的總量。的總量。 v vk

60、 k( (s sk k，t tk k，x xk k，y yk k)從從s sk k中取出數(shù)量為中取出數(shù)量為x xk k的資源的資源A A，從，從 t tk k中取出數(shù)量為中取出數(shù)量為y yk k的資源的資源B B分配給項目分配給項目k k可獲得的收益。即：可獲得的收益。即： f fk k( (s sk k，t tk k)將數(shù)量為將數(shù)量為s sk k的資源的資源A A和數(shù)量為和數(shù)量為tktk的資源的資源B B分配分配給第給第k k至第至第n n個項目可獲得的最大收益。個項目可獲得的最大收益。 于是可得下面的狀態(tài)轉(zhuǎn)移方程和基本方程：于是可得下面的狀態(tài)轉(zhuǎn)移方程和基本方程： ), 2 , 1(11nk