運籌學(六)剖析

1、第七章第七章動動 態(tài)態(tài) 規(guī)規(guī) 劃劃主要內(nèi)容：主要內(nèi)容：第一節(jié)第一節(jié) 多階段決策過程的最優(yōu)化多階段決策過程的最優(yōu)化第二節(jié)第二節(jié) 動態(tài)規(guī)劃的基本概念和基本原理動態(tài)規(guī)劃的基本概念和基本原理第三節(jié)第三節(jié) 動態(tài)規(guī)劃的建模與求解動態(tài)規(guī)劃的建模與求解第四節(jié)第四節(jié) 動態(tài)規(guī)劃在經(jīng)濟管理中的應用動態(tài)規(guī)劃在經(jīng)濟管理中的應用第一節(jié)第一節(jié)多階段決策過程的最優(yōu)化多階段決策過程的最優(yōu)化o動態(tài)規(guī)劃：動態(tài)規(guī)劃：是解決是解決多階段決策過程最優(yōu)化問題多階段決策過程最優(yōu)化問題的一種方法的一種方法o多階段決策過程多階段決策過程 是指某一些特殊的活動過程，它們可以按照是指某一些特殊的活動過程，它們可以按照時間順序劃分為若干個相互聯(lián)系的階

2、段，在每時間順序劃分為若干個相互聯(lián)系的階段，在每個階段都需要進行決策。個階段都需要進行決策。一、多階段決策過程的最優(yōu)化的相關概念一、多階段決策過程的最優(yōu)化的相關概念o多階段決策過程最優(yōu)化多階段決策過程最優(yōu)化 在多階段決策過程中，各個階段所確定的決在多階段決策過程中，各個階段所確定的決策就構成了一個決策序列，稱為一個策就構成了一個決策序列，稱為一個策略策略。一。一般來說，由于每一階段可供選擇的決策往往不般來說，由于每一階段可供選擇的決策往往不止一個，因此，對于整個過程，就會有許多可止一個，因此，對于整個過程，就會有許多可供選擇的策略。在所有可供選擇的策略中，對供選擇的策略。在所有可供選擇的策略中

3、，對應的整體效果最好的策略稱為應的整體效果最好的策略稱為最優(yōu)策略最優(yōu)策略。 把一個問題劃分成若干個相互聯(lián)系的階段把一個問題劃分成若干個相互聯(lián)系的階段并選取其最優(yōu)策略，這就是多階段決策過程的并選取其最優(yōu)策略，這就是多階段決策過程的最優(yōu)化問題。最優(yōu)化問題。二、多階段決策過程最優(yōu)化的例子二、多階段決策過程最優(yōu)化的例子o生產(chǎn)與存貯問題生產(chǎn)與存貯問題 某工廠每月需供應市場一定數(shù)量的產(chǎn)品，某工廠每月需供應市場一定數(shù)量的產(chǎn)品，并將所余產(chǎn)品存入倉庫。一般某月適當增加產(chǎn)并將所余產(chǎn)品存入倉庫。一般某月適當增加產(chǎn)量可降低生產(chǎn)成本，但超產(chǎn)部分存入倉庫會增量可降低生產(chǎn)成本，但超產(chǎn)部分存入倉庫會增加庫存費用。要求確定一個

4、逐月的生產(chǎn)計劃，加庫存費用。要求確定一個逐月的生產(chǎn)計劃，在滿足需求的條件下，使一年的生產(chǎn)與存貯費在滿足需求的條件下，使一年的生產(chǎn)與存貯費用之和最小。用之和最小。 可以把該問題可以把該問題按月按月劃分為劃分為12個階段，每個階段，每個階段初決定該階段（月）的生產(chǎn)數(shù)量。個階段初決定該階段（月）的生產(chǎn)數(shù)量。o設備更新問題設備更新問題 企業(yè)考慮企業(yè)考慮n n年內(nèi)某種設備的更新問題。我們年內(nèi)某種設備的更新問題。我們知道，設備使用時間越長，維修費用越高，處知道，設備使用時間越長，維修費用越高，處理價值（設備殘值）越低，但是如果賣去舊的理價值（設備殘值）越低，但是如果賣去舊的買新的，則需要一次性支出較大的費

5、用。因此買新的，則需要一次性支出較大的費用。因此就需要綜合權衡決定設備的使用年限，使總的就需要綜合權衡決定設備的使用年限，使總的經(jīng)濟效益最好。經(jīng)濟效益最好。 可以把該問題可以把該問題按年按年劃分為劃分為n個階段，每個階個階段，每個階段（年）初都需要進行決策，決定設備是否更段（年）初都需要進行決策，決定設備是否更新。新。 以上所舉問題的發(fā)展過程都與時間因素有以上所舉問題的發(fā)展過程都與時間因素有關，因此在這類多階段決策問題中，階段的劃關，因此在這類多階段決策問題中，階段的劃分常取時間區(qū)段來表示，并且各個階段上的決分常取時間區(qū)段來表示，并且各個階段上的決策往往也與時間因素有關，這就使它具有了策往往也

6、與時間因素有關，這就使它具有了“動態(tài)動態(tài)”的含義，所以把處理這類動態(tài)問題的的含義，所以把處理這類動態(tài)問題的方法稱為動態(tài)規(guī)劃方法。方法稱為動態(tài)規(guī)劃方法。 不過，實際中尚有許多不包含時間因素的不過，實際中尚有許多不包含時間因素的一類一類“靜態(tài)靜態(tài)”決策問題，就其本質(zhì)而言是一次決策問題，就其本質(zhì)而言是一次決策問題，是非動態(tài)決策問題，但是也可以人決策問題，是非動態(tài)決策問題，但是也可以人為地引入階段的概念當作多階段決策問題，應為地引入階段的概念當作多階段決策問題，應用動態(tài)規(guī)劃方法加以解決。用動態(tài)規(guī)劃方法加以解決。o背包問題背包問題 一位旅行者攜帶背包去登山，已知他所能承一位旅行者攜帶背包去登山，已知他所

7、能承受的背包重量限制為受的背包重量限制為a a千克，現(xiàn)有千克，現(xiàn)有n n種物品可供種物品可供他選擇裝入背包，第他選擇裝入背包，第i i件物品的重量為件物品的重量為a ai千克，千克，其價值是攜帶數(shù)量其價值是攜帶數(shù)量xi的函的函數(shù)數(shù) 。 問旅行者如何選擇攜帶各種物品的件數(shù)，以使問旅行者如何選擇攜帶各種物品的件數(shù)，以使總價值最大?？們r值最大。 可以把該問題可以把該問題按物品種類按物品種類劃分為劃分為n個階段，個階段，每個階段（種類）都需要進行決策，決定該種每個階段（種類）都需要進行決策，決定該種物品的件數(shù)。物品的件數(shù)。nixcii, 2 , 1 )( o投資問題投資問題 某公司有某公司有Q Q元資

8、金用于投資，可以投資于元資金用于投資，可以投資于n n個個項目，投資于第項目，投資于第i i個項目投資額為個項目投資額為x xi i時，其收益時，其收益為為 ，如何分配投資額，才能使，如何分配投資額，才能使總收益最大?？偸找孀畲?。 可以把該問題可以把該問題按項目按項目劃分為劃分為n個階段，每個個階段，每個階段（項目）都需要進行決策，決定項目投資階段（項目）都需要進行決策，決定項目投資的數(shù)額。的數(shù)額。nixgii, 2 , 1 )( o最短路問題最短路問題 求求v1v1到到v13v13的最短距離。的最短距離。 v1v2v3v4v5v6v7v8v9v12v10v11v135455544442368

9、77838362313第1階段第2階段第3階段第4階段第5階段按空間按空間劃分為劃分為5各階段。各階段。第二節(jié)第二節(jié)動態(tài)規(guī)劃的基本概念和基本原理動態(tài)規(guī)劃的基本概念和基本原理一、動態(tài)規(guī)劃的基本概念一、動態(tài)規(guī)劃的基本概念1、階段和階段變量、階段和階段變量 將所給問題的過程，按決策進行的時間將所給問題的過程，按決策進行的時間或空間上先后順序劃分為若干子過程，每個或空間上先后順序劃分為若干子過程，每個子過程稱為一個子過程稱為一個階段階段。 用以描述階段的變量叫作用以描述階段的變量叫作階段變量階段變量，一，一般以字母般以字母k k表示。表示。例中：階段例中：階段k=1,2,3,4,5 2、狀態(tài)、狀態(tài)變量

10、和狀態(tài)集、狀態(tài)、狀態(tài)變量和狀態(tài)集 各階段開始時的客觀條件（所處的位置、各階段開始時的客觀條件（所處的位置、運動狀態(tài)等）稱為運動狀態(tài)等）稱為狀態(tài)狀態(tài)。 描述各階段狀態(tài)的變量叫作描述各階段狀態(tài)的變量叫作狀態(tài)變量狀態(tài)變量，一，一般用字母般用字母sk表示第表示第k階段的狀態(tài)變量。階段的狀態(tài)變量。 狀態(tài)變量狀態(tài)變量sk的取值集合稱為狀態(tài)集合，的取值集合稱為狀態(tài)集合，用字母用字母Sk表示，有表示，有 。 Sskk 例中：例中：S1=v1S2=v2,v3S3=v4,v5, v6, v7S4=v8,v9, v10S5=v11,v12無后效性無后效性當某階段的狀態(tài)給定以后，在這當某階段的狀態(tài)給定以后，在這階段以

11、后過程的發(fā)展不受這段以前各階段的影階段以后過程的發(fā)展不受這段以前各階段的影響。響。動態(tài)規(guī)劃中的各階段的狀態(tài)應具有無后效性。動態(tài)規(guī)劃中的各階段的狀態(tài)應具有無后效性。 3、決策、決策變量和允許決策集合、決策、決策變量和允許決策集合 當各階段的狀態(tài)取定以后，就可以作出不當各階段的狀態(tài)取定以后，就可以作出不同的決定（或選擇），從而確定下一階段的狀同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為態(tài)，這種決定稱為決策決策。 描述各階段決策的變量稱為描述各階段決策的變量稱為決策變量決策變量，一，一般用字母般用字母 表示第表示第k階段狀態(tài)為階段狀態(tài)為sk 時的決時的決策變量。策變量。 決策變量的允許取

12、值集合稱為決策變量的允許取值集合稱為允許決策集允許決策集合合，用字母，用字母 表示第表示第k階段狀態(tài)為階段狀態(tài)為sk 時的時的允許決策集合，有允許決策集合，有 。 )(kksu )(kksD )( )(kkkksDsu 例中：例中：D1(v1)=v2,v3D2 (v2)=v4,v5, v6D3 (v3)=v5, v6 , v7D4(v4)=v8, v9 4、策略、允許策略集合、策略、允許策略集合 當各階段的決策確定以后，整個問題的決策當各階段的決策確定以后，整個問題的決策序列就夠成一個序列就夠成一個策略策略，用用 表示。表示。 策略的允許取值集合稱為策略的允許取值集合稱為允許策略集合允許策略集

13、合，記作記作 。 從從k階段到第階段到第n階段，依次進行的階段決策階段，依次進行的階段決策構成的決策序列稱為構成的決策序列稱為k部子策略部子策略, ,表示為表示為 。 允許策略集合中，效果最優(yōu)的策略稱為允許策略集合中，效果最優(yōu)的策略稱為最最優(yōu)策略優(yōu)策略。 )(,),(),(2211, 1nnnsususup , 1 nP )(,),(),(11,nnkkkknksususup 例中：例中：p1,nv3,v5,v8,v11,v13為一個策略。為一個策略。共有共有24個策略。個策略。 5、狀態(tài)轉(zhuǎn)移方程、狀態(tài)轉(zhuǎn)移方程 動態(tài)規(guī)劃中，某階段的狀態(tài)是上一階段的狀動態(tài)規(guī)劃中，某階段的狀態(tài)是上一階段的狀態(tài)和上

14、一階段的決策的結果。態(tài)和上一階段的決策的結果。 如果給定了第如果給定了第k階段的狀態(tài)階段的狀態(tài)sk, ,該階段的決該階段的決策為策為 ，則第，則第k+1階段的狀態(tài)階段的狀態(tài)sk+1也就完也就完全確定，它們的關系可用下式表示：全確定，它們的關系可用下式表示：)(kksu),(1kkkkusTs 例中：例中：sk+1=uk(sk) 6、指標函數(shù)和最優(yōu)指標函數(shù)、指標函數(shù)和最優(yōu)指標函數(shù) 用來衡量策略效果的某種數(shù)量指標，稱為指用來衡量策略效果的某種數(shù)量指標，稱為指標函數(shù)。對不同問題，指標函數(shù)可以是諸如費用、標函數(shù)。對不同問題，指標函數(shù)可以是諸如費用、成本、產(chǎn)值、利潤、產(chǎn)量、耗量、距離、時間、成本、產(chǎn)值、

15、利潤、產(chǎn)量、耗量、距離、時間、效用，等等。效用，等等。 (1)(1)階段指標函數(shù)階段指標函數(shù)（也稱階段效應）。（也稱階段效應）。 表示第表示第k k段處于段處于sk狀態(tài)、所作決策為狀態(tài)、所作決策為u uk k( (s sk k) )時時的指標就是第的指標就是第k段指標函數(shù)，記為段指標函數(shù)，記為d dk k( (s sk k , ,u uk k ) )。 例中：階段指標函數(shù)為距離。例中：階段指標函數(shù)為距離。 d(v1,v3)表示在表示在v1,選擇選擇v3的距離。的距離。),(, 11, 1nnpsV),(,nkknkpsV初始狀態(tài)為初始狀態(tài)為s1，采取策略，采取策略p1,n1,n的全過程的全過程

16、的指標函數(shù)。的指標函數(shù)。初始狀態(tài)為初始狀態(tài)為sk，采取策略，采取策略pk,nk,n的后部子的后部子過程的指標函數(shù)。過程的指標函數(shù)。(2)過程指標函數(shù)過程指標函數(shù)例中：例中：V2,5(v3)表示從表示從V3到到V13的距離。的距離。V1,5(v1)表示從表示從V1到到V13的距離。的距離。 過程指標函數(shù)形式之一是取各階段指標之和的形過程指標函數(shù)形式之一是取各階段指標之和的形式，即式，即: 有些問題，如系統(tǒng)可靠性問題，其過程指標函數(shù)有些問題，如系統(tǒng)可靠性問題，其過程指標函數(shù)是取各階段指標的連乘積形式，如：是取各階段指標的連乘積形式，如： 總之，具體問題的過程指標函數(shù)表達形式需要視總之，具體問題的過

17、程指標函數(shù)表達形式需要視具體問題而定。具體問題而定。 nkiiiinkusdV),(, nkiiiinkusdV),(, (3) (3)最優(yōu)指標函數(shù)最優(yōu)指標函數(shù) ),(),()(,*,nkknkPpnkknkkkpsVoptpsVsfnknk 表示在第表示在第k階段，狀態(tài)為階段，狀態(tài)為sk時，采取最優(yōu)策略時，采取最優(yōu)策略p*k,nk,n到最終階段到最終階段的指標函數(shù)。的指標函數(shù)。)(11sf即為全過程最優(yōu)指標函數(shù)。即為全過程最優(yōu)指標函數(shù)。例中：例中：f3(v5)表示從表示從V5到到V13的最短距離。的最短距離。f1(v1)表示從表示從V1到到V13的最短距離。的最短距離。二、動態(tài)規(guī)劃的基本原理

18、二、動態(tài)規(guī)劃的基本原理o最優(yōu)化原理最優(yōu)化原理 （貝爾曼最優(yōu)化原理）（貝爾曼最優(yōu)化原理） 作為一個全過程的最優(yōu)策略具有這樣的作為一個全過程的最優(yōu)策略具有這樣的性質(zhì)：無論初始狀態(tài)和初始決策如何，對于性質(zhì)：無論初始狀態(tài)和初始決策如何，對于先前決策所形成的狀態(tài)而言，其后的所有決先前決策所形成的狀態(tài)而言，其后的所有決策必構成一個最優(yōu)子策略。策必構成一個最優(yōu)子策略。第三節(jié)第三節(jié)動態(tài)規(guī)劃模型的建立與求解動態(tài)規(guī)劃模型的建立與求解一、動態(tài)規(guī)劃模型的建立一、動態(tài)規(guī)劃模型的建立 （1）劃分階段）劃分階段 分析問題，識別問題的多階段特點，按時間或分析問題，識別問題的多階段特點，按時間或空間的先后順序劃分為滿足遞推關系

19、的若干階段，空間的先后順序劃分為滿足遞推關系的若干階段，對非時序的對非時序的“靜態(tài)靜態(tài)”問題，要人為地賦予問題，要人為地賦予“階段階段”概念。概念。 （2）正確選擇狀態(tài)變量）正確選擇狀態(tài)變量 動態(tài)規(guī)劃中狀態(tài)變量要具有動態(tài)規(guī)劃中狀態(tài)變量要具有無后效性無后效性和和可知性。可知性。 可知性可知性，即所規(guī)定的各段狀態(tài)變量的值，可以，即所規(guī)定的各段狀態(tài)變量的值，可以直接或間接地測算得到。直接或間接地測算得到。 （3）正確定義決策變量）正確定義決策變量 根據(jù)經(jīng)驗，一般將問題中待求的量，選作動根據(jù)經(jīng)驗，一般將問題中待求的量，選作動態(tài)規(guī)劃模型中的決策變量。態(tài)規(guī)劃模型中的決策變量。 （4）正確寫出狀態(tài)轉(zhuǎn)移方程）

20、正確寫出狀態(tài)轉(zhuǎn)移方程 （5）寫出指標函數(shù)）寫出指標函數(shù) （6）寫出基本方程）寫出基本方程 二、動態(tài)規(guī)劃模型的求解二、動態(tài)規(guī)劃模型的求解（逆序解法和順序解法）（逆序解法和順序解法）例例1：逆序解法求以下最短路問題：逆序解法求以下最短路問題v1v2v3v4v5v6v7v8v9v12v10v11v13545554444236877838362313狀態(tài)變量狀態(tài)變量sk：第：第k階段初所處的位置；階段初所處的位置；決策變量決策變量uk：第：第k階段初所做的決策；階段初所做的決策；狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程：sk+1=uk；階段指標函數(shù)階段指標函數(shù)d (sk,uk)：從第：從第k階段初所處的位置，階段初所

21、處的位置，采取決策到下一階段的距離采取決策到下一階段的距離；階段階段k：?。喝?,2,3,4,5；過程指標函數(shù)過程指標函數(shù)： ，表示從第，表示從第k階段初所處階段初所處的位置，采取一系列決策到終點的距離的位置，采取一系列決策到終點的距離； 55,),(kiiiikusdV最優(yōu)指標函數(shù)最優(yōu)指標函數(shù)fk(sk):表示從第表示從第k階段初所處的位置，階段初所處的位置，采取一系列決策到終點的最短距離采取一系列決策到終點的最短距離；基本方程為：基本方程為： 0)()(),()(6611minsfsfusdsfkkkkkDukkkk （1）當）當k=5時，時， 40),()(1311115 vvdvf,1

22、2115vvS 30),()(1312125 vvdvf （2）當）當k=4時，時， ,10984vvvS 73543min)(),()(),(min)(12512811511884 vfvvdvfvvdvf118*4)(vvu 53246min)(),()(),(min)(12512911511994 vfvvdvfvvdvf129*4)(vvu 53341min)(),()(),(min)(12512101151110104 vfvvdvfvvdvf1110*4)(vvu （3）k=3時，時，,76543vvvvS 125875min)(),()(),(min)(9494848443 vf

23、vvdvfvvdvf84*3)(vvu 105574min)(),()(),(min)(9495848553 vfvvdvfvvdvf95*3)(vvu 85453min)(),()(),(min)(104106949663 vfvvdvfvvdvf96*3)(vvu 95458min)(),()(),(min)(104107949773 vfvvdvfvvdvf107*3)(vvu （4）k=2時，時，,232vvS 1386103122min)(),()(),()(),(min)(63625352434222 vfvvdvfvvdvfvvdvf52*2)(vvu 159787108min)

24、(),()(),()(),(min)(73736363535332 vfvvdvfvvdvfvvdvf63*2)(vvu （5）k=1時，時，11vS 17155134min)(),()(),(min)(3231222111 vfvvdvfvvdvf21*1)(vvu 順藤摸瓜，找出最優(yōu)決策序列（最優(yōu)策略）：順藤摸瓜，找出最優(yōu)決策序列（最優(yōu)策略）：21*1)(vvu 52*2)(vvu 95*3)(vvu 129*4)(vvu 1312*5)(vvu 最短路線為：最短路線為：v1 v2 v5 v9 v12 v13 最短路距離為：最短路距離為：f1(v1)=17例例2：用逆序法求如下投資問題：用

25、逆序法求如下投資問題 某公司有某公司有1010萬元資金投資于萬元資金投資于i(i=1,2,3)i(i=1,2,3)，投資于第投資于第i i個項目投資額為個項目投資額為x xi i時，其收益分別時，其收益分別為為g g1 1( (x x1 1)=4x)=4x1 1,g,g2 2(x(x2 2)=9x)=9x2 2,g,g3 3(x(x3 3)=2x)=2x3 32 2，如何分，如何分配投資額，才能使總收益最大。配投資額，才能使總收益最大。 該問題的靜態(tài)模型為：該問題的靜態(tài)模型為： 2321294maxxxxZ )3 , 2 , 1( 010321ixxxxi該問題的動態(tài)規(guī)劃求解過程為：該問題的動

26、態(tài)規(guī)劃求解過程為： 狀態(tài)變量狀態(tài)變量sk：可以用于投資到第：可以用于投資到第k到到n個項目的資金數(shù)；個項目的資金數(shù)；決策變量決策變量xk：投入到第：投入到第k個項目的資金；個項目的資金；狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程：sk+1=sk-xk；階段指標函數(shù)階段指標函數(shù)gk (xk)：投入第：投入第k個項目個項目xk獲得的收益獲得的收益；階段階段k：?。喝?,2,3；過程指標函數(shù)過程指標函數(shù)： ，表示投入項目，表示投入項目k到到n個項個項目獲得的收益目獲得的收益；33 ,)(kiiikxgV最優(yōu)指標函數(shù)最優(yōu)指標函數(shù)fk(sk):表示可投資金為表示可投資金為sk時，投資第時，投資第k到到n個項目所獲得的最大

27、收益?zhèn)€項目所獲得的最大收益；基本方程為：基本方程為： 0)()()()(44110maxsfsfxgsfkkkksxkkkk （1）當）當k=3時，時，232344233322)(2)(maxmax3333sxsfxsfsxsx 3*3sx （2）當）當k=2時，時，29)(232022max22sxsfsx )(2922220max22xsxsx 2)49(22222220max22sxsxsx 數(shù)數(shù)為開口向上的拋物線函為開口向上的拋物線函2222222)49(2sxsx 兩兩端端取取得得，在在因因此此該該函函數(shù)數(shù)極極大大值值只只能能02s222222)(0ssfx 時，當222229)(s

28、sfsx時，當29922222sss時，當,s9s229s2222 時時，因因此此，有有：，時，時，2222s9s229s （3）當）當k=1時，時，10),(4)(1221011max11 ssfxsfsxx5s91110 x2/11max1 ,)29s(s9)s (f2222時時即即當當 x9s9x4)10(f11110 x2/111max1 2/125 2/11x *1 此此時時，0 ,2 )(sf *22222xs2*2222 ,9s)(sf sx 200 x36x21212/11x0max1 ,)29s(s2)s (f22222時時即即當當 )x10(2x4)10(f2112/11x

29、01max1 數(shù)數(shù)為為開開口口向向上上的的拋拋物物線線函函200362221 xx兩兩端端取取得得，在在因因此此該該函函數(shù)數(shù)極極大大值值只只能能2/110200)10(011 fx時，時，當當200)10(1 f因此因此0*1 x2162)10(f2/11x11 時，時，當當 順藤摸瓜，找出最優(yōu)決策序列（最優(yōu)策略）：順藤摸瓜，找出最優(yōu)決策序列（最優(yōu)策略）：0*1 x2/9102 s0*2 x10*223*3 xssx.200310萬萬中中，收收益益最最大大，為為萬萬資資金金都都投投入入到到項項目目因因此此，當當200)10(f, 2/1252001 所所以以因因為為0*1 x例例3：順序解法求

30、以下最短路問題：順序解法求以下最短路問題v1v2v3v4v5v6v7v8v9v12v10v11v13545554444236877838362313狀態(tài)變量狀態(tài)變量sk+1：第：第k階段末所處的位置；階段末所處的位置；決策變量決策變量uk：第：第k階段末所做的決策；階段末所做的決策；狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程：sk=uk；階段指標函數(shù)階段指標函數(shù)d (sk+1,uk)：從第：從第k階段末所處的位置，階段末所處的位置，采取決策到采取決策到k階段初的距離階段初的距離；階段階段k：?。喝?,2,3,4,5；過程指標函數(shù)過程指標函數(shù)： ，表示從第，表示從第k階段末所處階段末所處的位置，采取一系列決策到起

31、點的距離的位置，采取一系列決策到起點的距離； kiiiikusdV11,1),(最優(yōu)指標函數(shù)最優(yōu)指標函數(shù)fk(sk+1):表示從第表示從第k階段末所處的位置，階段末所處的位置，采取一系列決策到起點的最短距離采取一系列決策到起點的最短距離；基本方程為：基本方程為： 0)()(),()(10111minsfsfusdsfkkkkkDukkkk （1）當）當k=1時時， 40),()(1221 vvdvf,322vvS 50),()(1331 vvdvf （2）k=2時，時，,76543vvvvS 642min)(),(min)(212442 vfvvdvf24*2)(vvu 75843min)()

32、,()(),(min)(3135212552 vfvvdvfvvdvf25*2)(vvu 105746min)(),()(),(min)(3136212662 vfvvdvfvvdvf26*2)(vvu 1257min)(),(min)(313772 vfvvdvf37*2)(vvu （3）當）當k=3時，時， ,10984vvvS 117465min)(),()(),(min)(5258424883 vfvvdvfvvdvf548*3)(vvvu或或 121281037568min)(),()(),()(),()(),(min)(727962695259424993 vfvvdvfvvdvf

33、vvdvfvvdvf59*3)(vvu 14124104min)(),()(),(min)(7371063610103 vfvvdvfvvdvf610*3)(vvu （4）k=4時，時，,12115vvS （5）k=5時，時，136vS 17143144min)(),()(),(min)(12412131141113135 vfvvdvfvvdvf1213*5)(vvuin)(),()(),()(),(min)(10310119391183811114 vfvvdvfvvdvfvvdvf811*4)(vvuin)(),()(),()(),(m

34、in)(10310129391283812124 vfvvdvfvvdvfvvdvf912*4)(vvu 順藤摸瓜，找出最優(yōu)決策序列（最優(yōu)策略）：順藤摸瓜，找出最優(yōu)決策序列（最優(yōu)策略）：1213*5)(vvu 912*4)(vvu 59*3)(vvu 25*2)(vvu 12*1)(vvu 最短路線為：最短路線為：v1 v2 v5 v9 v12 v13 最短路距離為：最短路距離為：f1(v1)=17，與逆序法結論相同。，與逆序法結論相同。例例4：用順序法求如下投資問題：用順序法求如下投資問題 某公司有某公司有1010萬元資金投資于萬元資金投資于i(i=1,2,3)i(i=1,2,3)，投資于第

35、投資于第i i個項目投資額為個項目投資額為x xi i時，其收益分別時，其收益分別為為g g1 1( (x x1 1)=4x)=4x1 1,g,g2 2(x(x2 2)=9x)=9x2 2,g,g3 3(x(x3 3)=2x)=2x3 32 2，如何分，如何分配投資額，才能使總收益最大。配投資額，才能使總收益最大。 該問題的靜態(tài)模型為：該問題的靜態(tài)模型為： 2321294maxxxxZ )3 , 2 , 1( 010321ixxxxi該問題的動態(tài)規(guī)劃求解過程為：該問題的動態(tài)規(guī)劃求解過程為： 狀態(tài)變量狀態(tài)變量sk+1：可以用于投資到第：可以用于投資到第1到到k個項目的資金數(shù)；個項目的資金數(shù)；決策

36、變量決策變量xk：投入到第：投入到第k個項目的資金；個項目的資金；狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程：sk=sk+1-xk；階段指標函數(shù)階段指標函數(shù)gk (xk)：投入第：投入第k個項目個項目xk獲得的收益獲得的收益；階段階段k：?。喝?,2,3；過程指標函數(shù)過程指標函數(shù)： ，表示投入項目，表示投入項目1到到k個項個項目獲得的收益目獲得的收益； kiiikxgV1, 1)(最優(yōu)指標函數(shù)最優(yōu)指標函數(shù)fk(sk+1):表示可投資金為表示可投資金為sk+1時，投資時，投資第第1到到k個項目所獲得的最大收益?zhèn)€項目所獲得的最大收益；基本方程為：基本方程為： 0)()()()(10101max1sfsfxgsfkk

37、kksxkkkk （1）當）當k=1時，時，)(4)(10121max21sfxsfsx 41max21xsx 24s 2*1sx （2）當）當k=2時，時，)(9)(212032max32sfxsfsx 49220max32sxsx )(492320max32xsxsx 45320max32sxsx 39s 3*2sx （3）當）當k=3時，時，s4=10)(2)(3223043max43sfxsfsx 923230max43sxsx )(9234230max43xsxsx )10(92323100max3xxx 9092323100max3 xxx數(shù)數(shù)為開口向上的拋物線函為開口向上的拋物線

38、函9092323 xx兩兩端端取取得得，在在因因此此該該函函數(shù)數(shù)極極大大值值只只能能10090)10(031 fx時時，當當200)10(3 f因此因此10*3 x200)10(1033 fx時時，當當 順藤摸瓜，找出最優(yōu)決策序列（最優(yōu)策略）：順藤摸瓜，找出最優(yōu)決策序列（最優(yōu)策略）：01010*343*2 xssx000*232*1 xssx三、順序法與逆序法的不同點三、順序法與逆序法的不同點 兩種方法本質(zhì)是相同的。主要區(qū)別如下：兩種方法本質(zhì)是相同的。主要區(qū)別如下：o狀態(tài)轉(zhuǎn)移方式不同狀態(tài)轉(zhuǎn)移方式不同o指標函數(shù)的定義不同指標函數(shù)的定義不同o基本方程形式不同基本方程形式不同逆序法：逆序法：順序法：

39、順序法：逆序法：逆序法：順序法：順序法：),(1kkkkusTs ),(1kkkkusTs 程最優(yōu)效益值。程最優(yōu)效益值。出發(fā)，到終點后部子過出發(fā)，到終點后部子過階段從狀態(tài)階段從狀態(tài)表示第表示第kkksksf)(程最優(yōu)效益值。程最優(yōu)效益值。出發(fā)，到起點前部子過出發(fā)，到起點前部子過階段從狀態(tài)階段從狀態(tài)表示第表示第11)( kkksksff1(s1)是整體是整體最優(yōu)函數(shù)值最優(yōu)函數(shù)值fn(sn+1)是整是整體最優(yōu)函數(shù)值體最優(yōu)函數(shù)值第四節(jié)第四節(jié)動態(tài)規(guī)劃在經(jīng)濟管理中的應用動態(tài)規(guī)劃在經(jīng)濟管理中的應用一、一、背包問題背包問題 一位旅行者攜帶背包去登山，已知他所能承受的背包一位旅行者攜帶背包去登山，已知他所能承

40、受的背包重量限制為重量限制為a千克，現(xiàn)有千克，現(xiàn)有n種物品可供他選擇裝入背包，種物品可供他選擇裝入背包，第第i件物品的重量為件物品的重量為ai千克，其價值是攜帶數(shù)量千克，其價值是攜帶數(shù)量xi的函的函數(shù)數(shù) 。問旅行者如何選擇攜帶各種物品。問旅行者如何選擇攜帶各種物品的件數(shù)，以使總價值最大。的件數(shù)，以使總價值最大。nixcii, 2 , 1 )( 設設xi為第為第i種物品攜帶的數(shù)量，該問題的整數(shù)規(guī)劃模種物品攜帶的數(shù)量，該問題的整數(shù)規(guī)劃模型如下：型如下： )(max1 niiixcZ nixxainiii, 2 , 1 0a 1且且為為整整數(shù)數(shù) 用動態(tài)規(guī)劃的順序解法建模求解，過程如下：用動態(tài)規(guī)劃的順

41、序解法建模求解，過程如下：階段階段k：將可裝入物品按將可裝入物品按1，2，n 排序，每種物品排序，每種物品按一個階段，共按一個階段，共n個階段。個階段。K=1，2，n。狀態(tài)變量狀態(tài)變量sk+1：在第在第k階段開始時，可以裝入前階段開始時，可以裝入前k種物品種物品的總重量。的總重量。決策變量決策變量xk：在第在第k階段開始時，裝入第階段開始時，裝入第k種物品的件數(shù)。種物品的件數(shù)。狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 ： sk = sk+1-akxk允許決策集合允許決策集合 ： Dk (sk+1)= xk|0 xksk+1/ak, xk為整數(shù)為整數(shù)最優(yōu)指標函數(shù)最優(yōu)指標函數(shù) fk (sk+1)：在第：在第k階段

42、初，可以裝入前階段初，可以裝入前k種種物品的總重量為物品的總重量為sk+1時，選擇最優(yōu)策略裝前時，選擇最優(yōu)策略裝前k種物品的價值。種物品的價值?；痉匠袒痉匠蹋?0)s (f)s (f)x(c)s (f10k1kkka/s x01kkmaxk1kk且為整數(shù)且為整數(shù) 例：有一輛貨運量為例：有一輛貨運量為10t10t的卡車，用以裝載的卡車，用以裝載3 3種貨物，種貨物，每種貨物的單位重量及相應單位價值如下表所示。應如每種貨物的單位重量及相應單位價值如下表所示。應如何裝載可使裝載總價值最大？何裝載可使裝載總價值最大？貨物編號貨物編號123單位重量（單位重量（t）345單位價值單位價值456 解：設

43、第解：設第i i種貨物裝入種貨物裝入x xi i件，該問題可表示為：件，該問題可表示為：321654maxxxxZ 且且為為整整數(shù)數(shù) 0,10543321321xxxxxx 建立動態(tài)規(guī)劃模型（順序解法）：建立動態(tài)規(guī)劃模型（順序解法）：階段階段k：將可裝入物品按將可裝入物品按1，2，3 排序，每種物品按一排序，每種物品按一個階段，共個階段，共3個階段。個階段。K=1，2，3。狀態(tài)變量狀態(tài)變量sk+1：在第在第k階段開始時，可以裝入前階段開始時，可以裝入前k種物品種物品的總重量。的總重量。決策變量決策變量xk：在第在第k階段開始時，裝入第階段開始時，裝入第k種物品的件數(shù)。種物品的件數(shù)。狀態(tài)轉(zhuǎn)移方程

44、狀態(tài)轉(zhuǎn)移方程 ： sk = sk+1-akxk （a1=3，a2=4，a3=5）允許決策集合允許決策集合 ： Dk (sk+1)= xk|0 xksk+1/ak, xk為整數(shù)為整數(shù)最優(yōu)指標函數(shù)最優(yōu)指標函數(shù) fk (sk+1)：在第：在第k階段初，可以裝入前階段初，可以裝入前k種種物品的總重量為物品的總重量為sk+1時，選擇最優(yōu)策略裝前時，選擇最優(yōu)策略裝前k種物品的價值。種物品的價值。基本方程基本方程： 0)()()()(101/01max1sfsfxcsfkkkkasxkkkkk且為整數(shù)且為整數(shù)（1）當）當K=1時時3/ 404)(213/021max21sxsfsx 且且為為整整數(shù)數(shù)s201

45、2345678910f1(s2)0 x1*000004141418282821231233/2*1sx （2）當）當K=2時時)4(5)(23124/032max32xsfxsfsx 且且為為整整數(shù)數(shù)s3012345678910f2(s3)x2*x25x2 +f1(s2)00000 1 01010 1 0 1 220 12010000000004404 551455185808 9918 9 1010212 9 1012012 1310131（3）當）當K=3時時 ，s4=100*3 x21:*1*2 xx，逆推，得逆推，得.13最最大大價價值值為為s410f3(s4)x3*x36x2 +f2

46、(s3)012)5(6)(34235/043max43xsfxsfsx 且且為為整整數(shù)數(shù)131112130二、生產(chǎn)與存貯問題二、生產(chǎn)與存貯問題 例：例：某工廠生產(chǎn)并銷售某種產(chǎn)品，已知今后四個月市某工廠生產(chǎn)并銷售某種產(chǎn)品，已知今后四個月市場需求預測如下表，又每月生產(chǎn)場需求預測如下表，又每月生產(chǎn)j j單位產(chǎn)品費用為：單位產(chǎn)品費用為： 千千元元 ,6)1,2,(j j30)(j 0)(jC 每月庫存每月庫存j j單位產(chǎn)品的費用為單位產(chǎn)品的費用為E(j)=0.5jE(j)=0.5j（千元），該（千元），該廠最大庫存量為廠最大庫存量為3 3單位，每月最大生產(chǎn)能力為單位，每月最大生產(chǎn)能力為6 6單位，計劃

47、單位，計劃開始和計劃期末庫存量都是零。試制定四個月的生產(chǎn)計劃，開始和計劃期末庫存量都是零。試制定四個月的生產(chǎn)計劃，在滿足用戶需求條件下總費用最小。假設第在滿足用戶需求條件下總費用最小。假設第i+1i+1個月的庫存?zhèn)€月的庫存量是第量是第i i個月可銷售量與該月用戶需求量之差；而第個月可銷售量與該月用戶需求量之差；而第i i個月個月的可銷售量是本月初庫存量與產(chǎn)量之和。的可銷售量是本月初庫存量與產(chǎn)量之和。 解：用動態(tài)規(guī)劃的解：用動態(tài)規(guī)劃的逆序解法逆序解法建模求解，過程如下：建模求解，過程如下：階段階段k：每個月為一個階段，共每個月為一個階段，共4個階段。個階段。k=1，2，3，4。狀態(tài)變量狀態(tài)變量s

48、k：第第k階段（月）初的庫存量。階段（月）初的庫存量。決策變量決策變量uk：第第k階段的生產(chǎn)量。階段的生產(chǎn)量。狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 ： sk+1 = sk+uk-gk最優(yōu)指標函數(shù)最優(yōu)指標函數(shù) fk (sk)：在第：在第k月初庫存量為月初庫存量為sk時，選擇最優(yōu)時，選擇最優(yōu)策略生產(chǎn)，從本月到第策略生產(chǎn)，從本月到第4個月末的最低生產(chǎn)、庫存費用之和。個月末的最低生產(chǎn)、庫存費用之和。i（月）1234gi（需求）2324 （1）當）當k=4時，時，)()4()()()()(445544444max44sEsCsfsEuCsfsu 首先確定首先確定s4的允許集合。的允許集合。 考慮到最大庫存量考慮到最

49、大庫存量3：s43。 考慮到最大生產(chǎn)能力考慮到最大生產(chǎn)能力6：s43*6-（2+3+2）。）。 考慮到期末庫存量為考慮到期末庫存量為0：s44。 綜上，有：綜上，有：s43，即，即s4 可以取可以取0，1，2，3。s40f4(s4)u4*u4C4 +E412343217+0746+0.56.535+1624+1.55.53 （2）當）當k=3時，時，)()()()(443333max33sfsEuCsfDu 首先確定首先確定s3的允許集合。的允許集合。 考慮到最大庫存量考慮到最大庫存量3：s33。 考慮到最大生產(chǎn)能力考慮到最大生產(chǎn)能力6：s32*6-（2+3）。 考慮到期末庫存量為考慮到期末庫

50、存量為0：s32+4。 綜上，有：綜上，有：s33，即，即s3 可以取可以取0，1，2，3。 然后確定然后確定u3允許集合。允許集合。 考慮到最大庫存量考慮到最大庫存量3：s3+u3g33，即，即u33+2-s3。 考慮到最大生產(chǎn)能力考慮到最大生產(chǎn)能力6：u36。 考慮到期末庫存量為考慮到期末庫存量為0：s3+u3-g34，即，即u34+2-s3 考慮到本月需求量考慮到本月需求量g3為為2：s3+u32，即，即u3 2-s3 綜上，有：綜上，有： max0，2-s3 u35-s3s30f3(s3)u3*u3C3 +E3 +f412323451234 012301212705)220(5 . 0

51、0)23(4 f12 12.55 .125 . 606)230(5 . 00)33(4 f13 13.512211.55 .1175 . 04)211(5 . 01)13(4 f12 12.5 1311.518 11.5 1212.5808 11.5 1280 （3）當）當k=2時，時，)()()()(332222max22sfsEuCsfDu 首先確定首先確定s2的允許集合。的允許集合。 考慮到最大庫存量考慮到最大庫存量3：s23。 考慮到最大生產(chǎn)能力考慮到最大生產(chǎn)能力6：s26-2。 考慮到期末庫存量為考慮到期末庫存量為0：s23+2+4。 綜上，有：綜上，有：s23，即，即s2 可以取可

52、以取0，1，2，3。 然后確定然后確定u2允許集合。允許集合。 考慮到最大庫存量考慮到最大庫存量3：s2+u2g23，即，即u23+3-s2。 考慮到最大生產(chǎn)能力考慮到最大生產(chǎn)能力6：u26。 考慮到期末庫存量為考慮到期末庫存量為0：s2+u2-g2g3+g4，即，即u22+4+3-s3 考慮到本月需求量考慮到本月需求量g2為為3：s2+u23，即，即u2 3-s2 綜上，有：綜上，有： max0，3-s2 u27-s2s20f2(s2)u2*u2C2 +E2+f3123345623451234012181206)330(5 . 00)33(3 f18 18.55 .185 .1107)340

53、(5 . 00)43(3 f16 1716517.55 .17125 . 05)321(5 . 01)23(3 f1815.516.515.541717.5 15 1615313.51714.513.50315.5 （4）當）當k=1時，時，)()()()(221111max11sfsEuCsfDu s1=0。 然后確定然后確定u1允許集合。允許集合。 考慮到最大庫存量考慮到最大庫存量3：s1+u1g13，即，即u13+2-s1。 考慮到最大生產(chǎn)能力考慮到最大生產(chǎn)能力6：u26。 考慮到期末庫存量為考慮到期末庫存量為0： s1+u1-g1g2+g3+g4，即，即u13+2+4+2-s1 考慮到

54、本月需求量考慮到本月需求量g1為為2：s1+u12，即，即u1 2-s1 綜上，有：綜上，有： max0，2-s1 u15-s1 即：即： 2 u15s10f1(s1)u1*u1C1 +E1 +f22345211605)220(5 . 00)23(2 f2121.55 .215 .1506)230(5 . 00)33(2 f2221.5212u1*=2s2=2+2-0=0u2*=5s3=0+5-3=2u3*=0s4=2+0-2=0u4*=4 0)()()()()(1111maxnnkkkkDukksfsfsEuCsfkk 設最大能力為設最大能力為p，最大庫存量為，最大庫存量為q。允許決策集合為

55、允許決策集合為: 允許允許狀態(tài)集合為：狀態(tài)集合為： 此類生產(chǎn)與庫存問題的基本方程為此類生產(chǎn)與庫存問題的基本方程為：)(,min011 kjjnkjjkgpgqs,min, 0maxkkknkjjkkksqgsgpusg 最大庫存限制最大庫存限制期末庫存量為期末庫存量為0的限制的限制最大生產(chǎn)能力的限制最大生產(chǎn)能力的限制最大生產(chǎn)能力限制最大生產(chǎn)能力限制期末庫存量為期末庫存量為0的限制的限制最大庫存限制最大庫存限制本月需求的限制本月需求的限制三、采購與銷售問題三、采購與銷售問題 例：例：某商店在未來的某商店在未來的4 4個月里，準備利用它的一個倉庫來專個月里，準備利用它的一個倉庫來專門經(jīng)銷某種商品，

56、倉庫最大容量能貯存該種商品門經(jīng)銷某種商品，倉庫最大容量能貯存該種商品10001000單位。假單位。假定該商店每月只能出賣倉庫現(xiàn)有的貨物。當商店在某月購貨時，定該商店每月只能出賣倉庫現(xiàn)有的貨物。當商店在某月購貨時，下月初才能到貨。預測該商店未來四個月的買賣價格如下表所下月初才能到貨。預測該商店未來四個月的買賣價格如下表所示，假定商店在示，假定商店在1 1月開始經(jīng)銷時，倉庫存有該商品月開始經(jīng)銷時，倉庫存有該商品500500單位。試單位。試問若不計較庫存費用，該商店應如何制定問若不計較庫存費用，該商店應如何制定1 1月至月至4 4月的訂購與銷月的訂購與銷售計劃，使預期獲利最大。售計劃，使預期獲利最大

57、。月份（月份（k）購買單價（購買單價（ck）銷售單價（銷售單價（pk）110122983111341517 解：用動態(tài)規(guī)劃的解：用動態(tài)規(guī)劃的逆序解法逆序解法建模求解，過程如下：建模求解，過程如下：階段階段k：每個月為一個階段，共每個月為一個階段，共4個階段。個階段。k=1，2，3，4。狀態(tài)變量狀態(tài)變量sk：第第k階段（月）初的庫存量（含上月訂貨量）。階段（月）初的庫存量（含上月訂貨量）。決策變量：決策變量：xk第第k月的出售量；月的出售量；yk第第k月的訂貨量。月的訂貨量。狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 ： sk+1 = sk+yk-xk最優(yōu)指標函數(shù)最優(yōu)指標函數(shù) fk (sk)：在第：在第k月初庫存

58、量為月初庫存量為sk時，選擇最優(yōu)時，選擇最優(yōu)策略，獲得的從本月初到第策略，獲得的從本月初到第4個月末的利潤。個月末的利潤。 0)()(max)(5511)(100000 sfsfycxpsfkkkkkkxsysxkkkkkkk基本方程為：基本方程為： （1）當）當k=4時時1517max)(44)(100000 4444444yxsfxsysx 417s 0 , *44*4 ysx此此時時， （2）當）當k=3時時)(171113max)(33333)(100000 3333333xysyxsfxsysx1764max333)(100000 33333syxxsysx 3136000s 100

59、0 , *33*3 ysx此此時時，求解一個線性規(guī)劃問題求解一個線性規(guī)劃問題 （3）當）當k=2時時)(13600098max)(22222)(100000 2222222xysyxsfxsysx 45136000max322)(100000 22222yxsxsysx 2910000s 2*2*21000 , 0 syx 此此時時，求解一個線性規(guī)劃問題求解一個線性規(guī)劃問題 （4）當）當k=1時，時，s1=500)(9100001012max)(11111)(100000 1111111xysyxsfxsysx 16000 0 ,500 *1*1 yx此此時時，)500(9100001012m

60、ax1111)500(100005000 111xyyxxyx 145003max1150005000 111 yxxyx0 ,500 *1*1 yx0500500s 2 1000s1000y , 0 x 2*2*2 1000010000s 3 1000y ,1000 x *3*3 1000 4 s0 ,1000 *4*4 yx四、設備更新問題四、設備更新問題 已知一臺設備的效益函數(shù)為已知一臺設備的效益函數(shù)為r(t)r(t)，維修費用函數(shù)為，維修費用函數(shù)為u(t)u(t)，更新費用函數(shù)為，更新費用函數(shù)為c(t)c(t)，要求在，要求在n n年內(nèi)的每年年初作出年內(nèi)的每年年初作出決策，是繼續(xù)使用舊