運(yùn)籌學(xué)第八章_動(dòng)態(tài)規(guī)劃PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1動(dòng)態(tài)規(guī)劃是解決多階段決策過(guò)程最優(yōu)化的一種方法。該方法是由美國(guó)數(shù)學(xué)家貝爾曼（R. E. Bellman）等人在20世紀(jì)50年代初提出的。并成功地解決了生產(chǎn)管理、工程技術(shù)等方面的許多問(wèn)題，從而建立了運(yùn)籌學(xué)的一個(gè)新的分支，即動(dòng)態(tài)規(guī)劃。Bellman在1957年出版了Dynamic Programming一書，是動(dòng)態(tài)規(guī)劃領(lǐng)域中的第一本著作。第1頁(yè)/共191頁(yè)動(dòng)態(tài)規(guī)劃與其他規(guī)劃方法的不同之處在于： 動(dòng)態(tài)規(guī)劃是求解某類問(wèn)題（多階段決策問(wèn)題）的一種方法，是考察問(wèn)題的一種途徑，而不是一種特定算法。 因此，它不像線性規(guī)劃那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組（算法）規(guī)則，而必須對(duì)具體問(wèn)題進(jìn)行具體分析

2、處理。因此，學(xué)習(xí)動(dòng)態(tài)規(guī)劃時(shí)，除對(duì)基本概念和基本方法正確理解外，還應(yīng)在一定經(jīng)驗(yàn)積累基礎(chǔ)上，以豐富的想像力去建立模型，用創(chuàng)造性的技巧去求解。第2頁(yè)/共191頁(yè)提 綱1 動(dòng)態(tài)規(guī)劃實(shí)例2 動(dòng)態(tài)規(guī)劃的基本概念3 動(dòng)態(tài)規(guī)劃的基本思想與基本原理4 逆序解法與順序解法第3頁(yè)/共191頁(yè)學(xué)習(xí)目標(biāo)：1 明確什么是多階段的決策問(wèn)題，特別要注意沒(méi)有明顯 的時(shí)段背景的問(wèn)題如何化歸為多階段的決策問(wèn)題。1 動(dòng)態(tài)規(guī)劃實(shí)例第4頁(yè)/共191頁(yè)P(yáng)156 例2 機(jī)器負(fù)荷分配問(wèn)題（時(shí)間階段問(wèn)題）設(shè)有某種機(jī)器設(shè)備，用于完成兩類工作A和B。若第k年初完好機(jī)器的數(shù)量為 xk ，若以數(shù)量 uk 用于A，余下的（xkuk）用于工作B，則該年的預(yù)

3、期收入為 g( uk ) + h( xkuk )。這里g( uk )和 h( xkuk )是已知函數(shù)，且 g( 0 ) = h( 0 ) = 0。又機(jī)器設(shè)備在使用中會(huì)有損壞，設(shè)機(jī)器用于工作A時(shí)，一年后能繼續(xù)使用的完好機(jī)器數(shù)占年初投入量的70%；若用于工作B時(shí)，一年后能繼續(xù)使用的完好機(jī)器數(shù)占年初投入量的90%。則在下一年初能繼續(xù)用于A、B工作的設(shè)備數(shù)為 xk+1=0.7uk+0.9(xkuk)。設(shè)第1年初完好的機(jī)器總數(shù)為1000臺(tái)，問(wèn)在連續(xù)5年內(nèi)每年應(yīng)如何分配用于A、B兩項(xiàng)工作的機(jī)器數(shù)，使5年的總收益為最大。1 動(dòng)態(tài)規(guī)劃實(shí)例第5頁(yè)/共191頁(yè)相應(yīng)的問(wèn)題稱為多階段決策問(wèn)題。這是一個(gè)多階段決策過(guò)程。

4、該過(guò)程可以分為相互聯(lián)系的若干階段，每一階段都需作出決 策，從而形成全過(guò)程的決策。第1年x1=1000u1第2年x2=0.7u1+ 0.9(x1-u1)u2第3年x3=0.7u2+ 0.9(x2-u2)u3第4年u4第5年x5=0.7u4+ 0.9(x4-u4)u5x4=0.7u3+ 0.9(x3-u3)x6第6頁(yè)/共191頁(yè)P(yáng)156 例1 最短路線問(wèn)題（空間階段的例子） 設(shè)有一個(gè)旅行者從下圖中的A點(diǎn)出發(fā)，途中要經(jīng)過(guò)B、C、D等處，最后到達(dá)終點(diǎn)E。從A到E有很多條路線可以選擇，各點(diǎn)之間的距離如圖所示，問(wèn)該旅行者應(yīng)選擇哪一條路線，使從A到達(dá)E的總的路程為最短。2537563245511463333

5、4C1C3D1AB1B3B2D2EC21234狀態(tài)1決策1狀態(tài)2狀態(tài)3狀態(tài)4狀態(tài)5決策2決策3決策4可看成 4階段 的決策 問(wèn)題。第7頁(yè)/共191頁(yè)從以上兩個(gè)例子，可以知道 所謂多階段決策問(wèn)題是指這樣的決策問(wèn)題：其過(guò)程可分為若干個(gè)相互聯(lián)系的階段，每一階段都對(duì)應(yīng)著一組可供選擇的決策，每一決策的選定既依賴于當(dāng)前面臨的狀態(tài)，又影響以后總體的效果。 當(dāng)每一階段的決策選定以后，就構(gòu)成一個(gè)決策序列，稱為一個(gè)策略，它對(duì)應(yīng)著一個(gè)確定的效果。多階段決策問(wèn)題就是尋找使此效果最好的策略。第8頁(yè)/共191頁(yè)多階段決策過(guò)程的特點(diǎn)1.各階段的決策相互關(guān)聯(lián)多階段決策過(guò)程最優(yōu)化的目的，是要達(dá)到整個(gè)活動(dòng)過(guò)程的總體效果最優(yōu)，而不

6、是某個(gè)階段“局部”的效果最優(yōu)。因此，各個(gè)階段決策的選取不是任意確定的。前一個(gè)決策的選取決定了當(dāng)前狀態(tài)，當(dāng)前狀態(tài)進(jìn)行決策后又影響到下一階段的狀態(tài)和決策，以至于影響總體效果。所以決策者在每個(gè)階段決策時(shí)，不應(yīng)僅考慮本階段最優(yōu)，還應(yīng)考慮對(duì)最終目標(biāo)的影響，從而做出對(duì)全局而言是最優(yōu)的決策。動(dòng)態(tài)規(guī)劃就是符合這一要求的一種最優(yōu)化方法。第9頁(yè)/共191頁(yè)2.各個(gè)階段的決策一般與“時(shí)間”有關(guān)動(dòng)態(tài)規(guī)劃方法與“時(shí)間”關(guān)系很密切，隨著時(shí)間過(guò)程的發(fā)展而決定各階段的決策，從而產(chǎn)生一個(gè)決策序列，這就是“動(dòng)態(tài)”的意思。但是，一些與時(shí)間無(wú)關(guān)的靜態(tài)問(wèn)題，只要在問(wèn)題中人為引入“時(shí)間”因素，也可將其看成是多階段的決策問(wèn)題，用動(dòng)態(tài)規(guī)劃方

7、法去處理。第10頁(yè)/共191頁(yè)學(xué)習(xí)目標(biāo)：1 準(zhǔn)確、熟練地掌握動(dòng)態(tài)規(guī)劃的基本概念、特別是狀態(tài) 變量、決策變量、狀態(tài)轉(zhuǎn)移律、指標(biāo)函數(shù)、基本方程 等。2 動(dòng)態(tài)規(guī)劃的基本概念第11頁(yè)/共191頁(yè)為了便于求解和表示決策及過(guò)程的發(fā)展順序，而把所給問(wèn)題恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系又有區(qū)別的子問(wèn)題，稱之為多段決策問(wèn)題的階段。一個(gè)階段，就是需要作出一個(gè)決策的子問(wèn)題。 通常，階段是按決策進(jìn)行的時(shí)間或空間上先后順序劃分的。描述階段的變量稱為階段變量，常記為k，k=1,2, ,n。如本例可按空間分為4個(gè) 階段來(lái)求解， k=1, 2, 3, 4。（1）階段（stage）第12頁(yè)/共191頁(yè)狀態(tài)：每階段初的客觀條件。描述各

8、階段狀態(tài)的變量稱為狀態(tài)變量，常用xk表示第k階段的狀態(tài)。（2）狀態(tài)（state）例1中，狀態(tài)就是某階段的出發(fā)位置。x1x2x3x4x5按狀態(tài)變量的取值是連續(xù)還是離散，可將動(dòng)態(tài)規(guī)劃問(wèn)題分為離 散型和連續(xù)型。第13頁(yè)/共191頁(yè)動(dòng)態(tài)規(guī)劃中的狀態(tài)應(yīng)滿足無(wú)后效性（馬爾科夫性）： 所謂無(wú)后效性指系統(tǒng)到達(dá)某個(gè)狀態(tài)前的過(guò)程的決策將不影響到該狀態(tài)以后的決策。指系統(tǒng)從某個(gè)階段往后的發(fā)展，僅由本階段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經(jīng)歷的狀態(tài)和決策（歷史）無(wú)關(guān)。過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它未來(lái)的發(fā)展例1中，當(dāng)某階段的狀態(tài)已選定某個(gè)點(diǎn)時(shí)，從這個(gè)點(diǎn)以后的路線只與該點(diǎn)有關(guān)，不受該點(diǎn)以前的路線的影響，

9、所以滿足狀態(tài)的無(wú)后效性。第14頁(yè)/共191頁(yè)狀態(tài)集合：狀態(tài)變量 xk 的取值集合稱為狀態(tài)集合，狀態(tài)集合實(shí)際上是關(guān)于狀態(tài)的約束條件。通常用Sk表示狀態(tài)集合，xkSk。第1階段 S1=A；第2階段具有3個(gè)狀態(tài)B1、B2和B3，故 S2=B1, B2, B3。x1x2x3x4x5第15頁(yè)/共191頁(yè)（3）決策（decision）當(dāng)過(guò)程處于某一階段的某狀態(tài)時(shí)，可以做出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決策。 描述決策的變量稱為決策變量，常用uk( xk )表示第k階段當(dāng)狀態(tài)處于xk時(shí)的決策變量，它是狀態(tài)變量的函數(shù)。例1中，從第2階段的狀態(tài)B1出發(fā)，可以選擇下一階段的C1、C2、C3。如我

10、們決定選擇C1，則可表示為：u2( B1 ) = C1。B1C1C2C3x2第16頁(yè)/共191頁(yè)決策集合：第k階段當(dāng)狀態(tài)處于xk時(shí)決策變量uk( xk )的取值范稱為決策集合，常用Dk( xk ) 表示。例1中，從第2階段的狀態(tài)B1出發(fā)，可以選擇下一階段的C1、C2、C3。即 D2( B1 ) = C1、C2、C3 ；B1C1C2C3決策集合實(shí)際上是決策的約束條件，uk( xk ) Dk( xk ) 。第17頁(yè)/共191頁(yè)小結(jié) 階段 k、 狀態(tài) xk、 狀態(tài)集合 Sk、 決策 uk( xk )、 決策集合 Dk( xk )。x1x2x3x4x5第18頁(yè)/共191頁(yè)（4）狀態(tài)轉(zhuǎn)移律（方程）狀態(tài)轉(zhuǎn)

11、移律：從xk的某一狀態(tài)值出發(fā)，當(dāng)決策變量uk(xk) 的取值決定后，下一階段狀態(tài)變量xk+1的取值也隨之確定。描述從 xk 轉(zhuǎn)變?yōu)?xk+1 的規(guī)律稱為狀態(tài)轉(zhuǎn)移規(guī)律（方程）。從第2階段的狀態(tài)B1出發(fā)，如我們決定選擇C2（也即確定了下一階段的狀態(tài)）。B1C2第19頁(yè)/共191頁(yè)B1C2上例中， u2( B1 ) = C2狀態(tài)轉(zhuǎn)移律為： xk+1 = uk( xk )一般來(lái)說(shuō)，下一階段狀態(tài)變量xk+1的取值是上階段的某一狀態(tài)變量xk和上階段決策變量uk(xk)的函數(shù)，記為 xk+1=Tk( xk, uk(xk) )12nx1u1x2u2x3xnunxn+1第20頁(yè)/共191頁(yè)（5）策略（polic

12、y）和子策略（subpolicy）策略：由依次進(jìn)行的n個(gè)階段決策構(gòu)成的決策序列就構(gòu)成一個(gè) 策略，用 p1n u1(x1), u2(x2), , un(xn) 表示。25375632455114633334C1C3D1AB1B3B2D2EC2本例中，如p14 u1(A)=B1, u2(B1) = C2, u3(C2) = D1, u4(D1) = E 表示其中一個(gè)策略，其總距離為2+5+6+3=16。第21頁(yè)/共191頁(yè)策略集合：在實(shí)際問(wèn)題中，由于在各個(gè)階段可供選擇的決策有許多個(gè)，因此，它們的不同組合就構(gòu)成了許多可供選擇的決策序列（策略），由它們組成的集合，稱為策略集合，記作 P1n。從策略集合

13、中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。第22頁(yè)/共191頁(yè)子策略：從k階段到第n階段，依次進(jìn)行的階段決策構(gòu)成的決策序列稱為k部子策略，表示為 pkn = uk(xk), uk+1(xk+1), , un(xn) 如從第3階段的C2狀態(tài)開(kāi)始的一個(gè)子策略可表示： p34=u3(C2) = D1, u4(D1) = E C2第23頁(yè)/共191頁(yè)（6）指標(biāo)函數(shù)用來(lái)衡量策略或子策略或決策的效果的某種數(shù)量指標(biāo)，就稱為指標(biāo)函數(shù)。 它是定義在全過(guò)程或各子過(guò)程或各階段上的確定數(shù)量函數(shù)。對(duì)不同問(wèn)題，指標(biāo)函數(shù)可以是諸如費(fèi)用、成本、產(chǎn)值、利潤(rùn)、產(chǎn)量、耗量、距離、時(shí)間、效用，等等。階段指標(biāo)函數(shù)過(guò)程指標(biāo)函數(shù)第24頁(yè)/共

14、191頁(yè)階段指標(biāo)函數(shù)：是指第 k 階段從狀態(tài) xk 出發(fā)，采取決策 uk 時(shí)產(chǎn)生的效益，用 vk(xk, uk) 表示。例1中，指標(biāo)函數(shù)是距離。如 v2(B1, C2) 表示由B1 出發(fā)，采用決策到C2 點(diǎn)的兩點(diǎn)間距離，即 v2( B1, C2) = 5。B1C2第25頁(yè)/共191頁(yè)過(guò)程指標(biāo)函數(shù)：是指從第 k 階段的某狀態(tài) xk 出發(fā)，采取子策略 pkn 時(shí)所得到的效益，記作 Vkn( xk, uk, xk+1, uk+1, , xn )例1中，如V34( C2, u3(C2)=D1, D1, u4(D1)= E, E ) = 6+3 =9C2第26頁(yè)/共191頁(yè)第27頁(yè)/共191頁(yè)Vkn =

15、 vi（xi, ui）i=kn (8.3a) Vkn = vi（xi, ui）i=kn (8.3b) 第28頁(yè)/共191頁(yè)可遞推Vkn( xk, uk, xk+1, uk+1, , xn )k xk, uk, V(k+1)n(xk+1, uk+1, , xn ) vk(xk,uk) vk+1(xk+1, uk+1) vn(xn,un) vk(xk,uk) V(k+1)n( xk+1, uk+1, , xn )第29頁(yè)/共191頁(yè)最優(yōu)指標(biāo)函數(shù)：表示從第 k 階段狀態(tài)為 xk 時(shí)采用最優(yōu)策略 pkn*到過(guò)程終止時(shí)的最佳效益值。記為 fk( xk )。 fk( xk ) = Vkn( xk , pk

16、n*) = opt Vkn( xk , pkn )例1中，如 f3( C2 ) = 3+4 = 7。其中 opt 可根據(jù)具體情況取max 或min。C2動(dòng)態(tài)規(guī)劃的目標(biāo)？最優(yōu)解：最優(yōu)策略 p1n最優(yōu)值：最優(yōu)指標(biāo) f1(A)第30頁(yè)/共191頁(yè)st.上述數(shù)學(xué)模型說(shuō)明了對(duì)于給定的多階段決策過(guò)程，求取一個(gè)(或多個(gè))最優(yōu)策略或最優(yōu)決策序列 u1, u2, , un ，使之既滿足左式給出的全部約束條件，又使左式所示的目標(biāo)函數(shù)取得極值，并且同時(shí)指出執(zhí)行該最優(yōu)策略時(shí)，過(guò)程狀態(tài)演變序列即是最優(yōu)路線。第31頁(yè)/共191頁(yè)小結(jié):概念 :階段變量k狀態(tài)變量xk決策變量uk;動(dòng)態(tài)規(guī)劃本質(zhì)上是多階段決策過(guò)程; 效益指標(biāo)函

17、數(shù)形式:和、積無(wú)后效性可遞推方程 :狀態(tài)轉(zhuǎn)移方程xk+1=Tk( xk, uk(xk) )指標(biāo) : Vkn( xk, uk, xk+1, uk+1, , xn )fk( xk ) = Vkn( xk , pkn*) = opt Vkn( xk , pkn )Vkn( xk, uk, xk+1, uk+1, , xn )k xk, uk, V(k+1)n(xk+1, uk+1, , xn ) 第32頁(yè)/共191頁(yè)解多階段決策過(guò)程問(wèn)題，求出 最優(yōu)策略，即最優(yōu)決策序列 最優(yōu)軌線，即執(zhí)行最優(yōu)策略時(shí)的狀態(tài)序列 u1*, u2*, , un* x1*, x2*, , xn* 最優(yōu)目標(biāo)函數(shù)值p1nP1nf1

18、( x1 ) = V1n( x1 , p1n*) = opt V1n( x1 , p1n )第33頁(yè)/共191頁(yè)1.劃分階段2.正確選擇狀態(tài)變量 3.確定決策變量及允許決策集合4.確定狀態(tài)轉(zhuǎn)移方程 5.確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃基本方程劃分階段是運(yùn)用動(dòng)態(tài)規(guī)劃求解多階段決策問(wèn)題的第一步，在確定多階段特性后，按時(shí)間或空間先后順序，將過(guò)程劃分為若干相互聯(lián)系的階段。對(duì)于靜態(tài)問(wèn)題要人為地賦予“時(shí)間”概念，以便劃分階段。建立動(dòng)態(tài)規(guī)劃模型的步驟 選擇狀態(tài)變量既要能確切描述過(guò)程演變又要滿足無(wú)后效性，而且各階段狀態(tài)變量的取值能夠確定。通常選擇所求解問(wèn)題的關(guān)鍵變量作為決策變量，同時(shí)要給出決策變量

19、的取值范圍，即確定允許決策集合。根據(jù)k 階段狀態(tài)變量和決策變量，寫出k+1階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系。階段指標(biāo)函數(shù)是指第k 階段的收益，最優(yōu)指標(biāo)函數(shù)是指從第k 階段狀態(tài)出發(fā)到第n 階段末所獲得收益的最優(yōu)值，最后寫出動(dòng)態(tài)規(guī)劃基本方程。第34頁(yè)/共191頁(yè) 以上五步是建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。由于動(dòng)態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動(dòng)態(tài)規(guī)劃模型沒(méi)有統(tǒng)一的模式，建模時(shí)必須根據(jù)具體問(wèn)題具體分析，只有通過(guò)不斷實(shí)踐總結(jié)，才能較好掌握建模方法與技巧。 下面我們看一個(gè)具體的例子 P156 例2 機(jī)器負(fù)荷分配問(wèn)題（時(shí)間階段問(wèn)題）第35頁(yè)/共191頁(yè)P(yáng)156 例2 機(jī)器負(fù)荷分配問(wèn)題（時(shí)間階段問(wèn)題

20、）設(shè)有某種機(jī)器設(shè)備，用于完成兩類工作A和B。若第k年初完好機(jī)器的數(shù)量為 xk ，若以數(shù)量 uk 用于A，余下的（xkuk）用于工作B，則該年的預(yù)期收入為 g( uk ) + h( xkuk )。其中g(shù)( uk ) 8uk ， h( xkuk ) = 5（xkuk）。又機(jī)器設(shè)備在使用中會(huì)有損壞，設(shè)機(jī)器用于工作A時(shí)，一年后能繼續(xù)使用的完好機(jī)器數(shù)占年初投入量的70%；若用于工作B時(shí)，一年后能繼續(xù)使用的完好機(jī)器數(shù)占年初投入量的90%。則在下一年初能繼續(xù)用于A、B工作的設(shè)備數(shù)為 xk+1=0.7uk+0.9(xkuk)。設(shè)第1年初完好的機(jī)器總數(shù)為1000臺(tái)，問(wèn)在連續(xù)5年內(nèi)每年應(yīng)如何分配用于A、B兩項(xiàng)工作

21、的機(jī)器數(shù)，使5年的總收益為最大。第36頁(yè)/共191頁(yè)1.劃分階段按年度來(lái)劃分階段，k=1,2,3,4,52.正確選擇狀態(tài)變量狀態(tài)變量xk為第k年度初擁有的完好機(jī)器數(shù)量 3.確定決策變量及允許決策集合決策變量uk為第k年度中分配于A工作的機(jī)器數(shù)量，則xkuk為用于B工作的機(jī)器數(shù)量。第k階段決策集合Dk( xk ) = uk | 0ukxk 這里xk和uk均取連續(xù)變量，它們的非整數(shù)值可以這樣理解，如xk=0.6，就表示一臺(tái)機(jī)器在第k年度中正常工作時(shí)間只占6/10；uk=0.3，就表示一臺(tái)機(jī)器在該年度只有3/10的時(shí)間能正常用于A工作。第37頁(yè)/共191頁(yè)4.確定狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程為 xk+1

22、=0.7uk+0.9(xkuk) 5.確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃基本方程指標(biāo)函數(shù)為V1,5 = vi（xi, ui）i=15 = g( ui ) + h( xiui )i=15令最優(yōu)指標(biāo)函數(shù)fk( xk ) 表示由資源量xk出發(fā)，從第k年開(kāi)始到第5年結(jié)束時(shí)所取得的最大預(yù)期收入。因而有： fk( xk ) = max Vk,5 = vi（xi, ui）i=k5 = 8ui + 5( xiui )i=k5 = 8ui +5(xiui)i=15第38頁(yè)/共191頁(yè)學(xué)習(xí)目標(biāo)：1 掌握最優(yōu)化原理的內(nèi)容2 掌握逆序解法3 動(dòng)態(tài)規(guī)劃的基本思想與基本原理第39頁(yè)/共191頁(yè)第40頁(yè)/共191

23、頁(yè)第41頁(yè)/共191頁(yè)第42頁(yè)/共191頁(yè)作為一個(gè)全過(guò)程的最優(yōu)策略具有這樣的性質(zhì)：對(duì)于最優(yōu)策略過(guò)程中的任意狀態(tài)而言，無(wú)論其過(guò)去的狀態(tài)和決策如何，余下的諸決策必構(gòu)成一個(gè)最優(yōu)子策略。（一個(gè)最優(yōu)策略的子策略總是最優(yōu)的）作該原理的具體解釋是，若某一全過(guò)程最優(yōu)策略為： p1n*( x1 )= u1*(x1), , uk*(xk), uk+1*(xk+1), , un*(xn) 則對(duì)上述策略中所隱含的任一狀態(tài)（xk）而言，第k子過(guò)程上對(duì)應(yīng)于 xk 的最優(yōu)策略必然包含在上述全過(guò)程最優(yōu)策略p1n*中，即為 pkn*( xk )= uk*(xk), uk+1*(xk+1), , un*(xn) 第43頁(yè)/共19

24、1頁(yè)C1D1AB3D2EC2反證法進(jìn)行證明最優(yōu)性原理在最短路線中的應(yīng)用 在最短路線中，若找到了AB3C2D2E是由A到E的最短路線，則B3C2D2E必是由B3出發(fā)到E點(diǎn)的所有可能選擇的不同路線中的最短路線。（一個(gè)最優(yōu)策略的子策略總是最優(yōu)的）第44頁(yè)/共191頁(yè) fk( xk ) = min vk(xk, uk ) + fk+1(xk+1) fn+1( xn+1 ) = 0邊界條件ukDk第45頁(yè)/共191頁(yè)第46頁(yè)/共191頁(yè)5.標(biāo)號(hào)法（只適用于一類最優(yōu)路線問(wèn)題的特殊解法） 標(biāo)號(hào)法是借助網(wǎng)絡(luò)圖通過(guò)分段標(biāo)號(hào)來(lái)求出最優(yōu)路線的一種簡(jiǎn)便、直觀的方法。通常標(biāo)號(hào)法采取“逆序求解”的方法來(lái)尋找問(wèn)題的最優(yōu)解，

25、即從最后階段開(kāi)始，逐次向階段數(shù)小的方向推算，最終求得全局最優(yōu)解。行進(jìn)方向動(dòng)態(tài)規(guī)劃尋優(yōu)途徑EA第47頁(yè)/共191頁(yè)第48頁(yè)/共191頁(yè)第（1）步 k=5 f5( x5 ) = f5( E ) = 0 這是邊界條件0Efk( xk ) 表示從第 k 階段狀態(tài) xk 到 E 點(diǎn)的的最短距離第49頁(yè)/共191頁(yè)第（2）步 k=4狀態(tài)變量 x4 可取兩種狀態(tài) D1、D2。 由D1到終點(diǎn)E只有一條路線，路長(zhǎng)為3，即 f4( D1 ) = 3。 同理， f4( D2 ) = 4 。3表示由D1點(diǎn)至E點(diǎn)的最短路長(zhǎng)為3。40D1第50頁(yè)/共191頁(yè)第（3）步 k=3狀態(tài)變量 x3 可取三個(gè)值：C1、C2、C3。

26、由C1到終點(diǎn)E有2條路線，分別為經(jīng)過(guò)D1、D2到達(dá)E點(diǎn)（由D1、D2到達(dá)E點(diǎn)的最短路長(zhǎng)在第一步已計(jì)算得出），需加以比較，取其中最短的。路線1 v3(C1, D1)+ f4(D1) = 1+3=4路線2 v3(C1, D2)+ f4(D2) = 4+4=834則由C1到終點(diǎn)E的最短距離 f3( C1 ) = minv3(C1, D1)+ f4(D1), v3(C1, D2)+ f4(D2) = 44C1第51頁(yè)/共191頁(yè)第（3）步 k=3由C2到終點(diǎn)E有2條路線，分別為經(jīng)過(guò)D1、D2到達(dá)E點(diǎn)（由D1、D2到達(dá)E點(diǎn)的最短路長(zhǎng)在第一步已計(jì)算得出），需加以比較，取其中最短的。路線1 v3(C2, D

27、1)+ f4(D1) = 6+3=9路線2 v3(C2, D2)+ f4(D2) = 3+4=734則由C2到終點(diǎn)E的最短距離 f3( C2 ) = minv3(C2, D1)+ f4(D1), v3(C2, D2)+ f4(D2) = 7C274第52頁(yè)/共191頁(yè)第（3）步 k=3由C3到終點(diǎn)E有2條路線，分別為經(jīng)過(guò)D1、D2到達(dá)E點(diǎn)（由D1、D2到達(dá)E點(diǎn)的最短路長(zhǎng)在第一步已計(jì)算得出），需加以比較，取其中最短的。路線1 v3(C3, D1)+ f4(D1) = 3+3=6路線2 v3(C3, D2)+ f4(D2) = 3+4=734則由C3到終點(diǎn)E的最短距離 f3( C3 ) = min

28、v3(C3, D1)+ f4(D1), v3(C3, D2)+ f4(D2) = 6C3746第53頁(yè)/共191頁(yè)第（4）步 k=2狀態(tài)變量 x2 可取三個(gè)值：B1、B2、B3。由B1到終點(diǎn)E，可分別經(jīng)過(guò)C1、C2、C3到達(dá)E點(diǎn)（由C1、C2、C3到E點(diǎn) 的最短距離在第二步已計(jì)算出），需加以比較，取其中最短的。路線1 v2(B1, C1)+ f3(C1) = 7+4=11路線2 v2(B1, C2)+ f3(C2) = 5+7=12路線3 v2(B1, C3)+ f3(C3) = 6+6=1234則由B1到終點(diǎn)E的最短距離 f2( B1 ) = minv2(B1, C1)+ f3(C1), v

29、2(B1, C2)+ f3(C2) v2(B1, C3)+ f3(C3) = 114B17611第54頁(yè)/共191頁(yè)第（4）步 k=2由B2到終點(diǎn)E，可分別經(jīng)過(guò)C1、C2、C3到達(dá)E點(diǎn)（由C1、C2、C3到E點(diǎn) 的最短距離在第二步已計(jì)算出），需加以比較，取其中最短的。路線1 v2(B2, C1)+ f3(C1) = 3+4=7路線2 v2(B2, C2)+ f3(C2) = 2+7=9路線3 v2(B2, C3)+ f3(C3) = 4+6=1034則由B2到終點(diǎn)E的最短距離 f2( B2 ) = minv2(B2, C1)+ f3(C1), v2(B2, C2)+ f3(C2) v2(B2,

30、 C3)+ f3(C3) = 74B276117第55頁(yè)/共191頁(yè)第（4）步 k=2由B3到終點(diǎn)E，可分別經(jīng)過(guò)C1、C2、C3到達(dá)E點(diǎn)（由C1、C2、C3到E點(diǎn) 的最短距離在第二步已計(jì)算出），需加以比較，取其中最短的。路線1 v2(B3, C1)+ f3(C1) = 5+4=9路線2 v2(B3, C2)+ f3(C2) = 1+7=8路線3 v2(B3, C3)+ f3(C3) = 5+6=1134則由B3到終點(diǎn)E的最短距離 f2( B3 ) = minv2(B3, C1)+ f3(C1), v2(B3, C2)+ f3(C2) v2(B3, C3)+ f3(C3) = 84B376117

31、8第56頁(yè)/共191頁(yè)第（5）步 k=1狀態(tài)變量 x1 只取一個(gè)值：A。 由A到終點(diǎn)E，可分別經(jīng)過(guò)B1、B2、B3到達(dá)E點(diǎn)（由B1、B2、B3到E點(diǎn) 的最短距離在第三步已計(jì)算出），需加以比較，取其中最短的。經(jīng)過(guò)B1點(diǎn) v1(A, B1)+ f2(B1) = 2+11=13經(jīng)過(guò)B2點(diǎn) v1(A, B2)+ f2(B2) = 5+7=12經(jīng)過(guò)B3點(diǎn) v1(A, B3)+ f2(B3) = 3+8=1134則由A到終點(diǎn)E的最短距離 f1( A ) = minv1(A, B1)+ f2(B1), v1(A, B2)+ f2(B2) v1(A, B3)+ f2(B3) = 114A76117811第57

32、頁(yè)/共191頁(yè)從下圖反推可得到最優(yōu)路線。344A76117811因此，由A到終點(diǎn)E的最優(yōu)解為： AB3C2D2E由點(diǎn)A到終點(diǎn)E的最優(yōu)值為11。第58頁(yè)/共191頁(yè)小結(jié)：在求解的各階段，都利用了第k階和第k+1段的如下關(guān) 系： fk( xk ) = min vk( xk, uk ) + fk+1( xk+1 ) (1) f5( x5 = E ) = 0 (2)上述遞推關(guān)系稱為動(dòng)態(tài)規(guī)劃的基本方程。其中（2）式稱為邊界條件。344A76117811第59頁(yè)/共191頁(yè)動(dòng)態(tài)規(guī)劃方法的優(yōu)點(diǎn)1.減少計(jì)算量 動(dòng)態(tài)規(guī)劃方法減少了計(jì)算量，而且隨著階段數(shù)的增加，計(jì)算量將大大減少。2.豐富了計(jì)算結(jié)果 在動(dòng)態(tài)規(guī)劃的解

33、法中，得到的不僅僅是由A點(diǎn)出發(fā)到E點(diǎn)的最短路線及相應(yīng)距離，而且得到了從所有中間點(diǎn)出發(fā)到E點(diǎn)的最短路線及相應(yīng)距離。這對(duì)于許多實(shí)際問(wèn)題來(lái)說(shuō)是很有用的，有利于幫助分析所得的結(jié)果。第60頁(yè)/共191頁(yè)動(dòng)態(tài)規(guī)劃方法的基本思想1. 將多階段決策過(guò)程劃分階段，恰當(dāng)?shù)剡x擇狀態(tài)變量、決策變 量，定義最優(yōu)指標(biāo)函數(shù)，從而把問(wèn)題化成一簇同類型的子問(wèn) 題，然后逐個(gè)求解。2. 求解時(shí)從邊界條件開(kāi)始，逆過(guò)程方向行進(jìn)，逐段遞推尋優(yōu)， 在每一個(gè)子問(wèn)題求解時(shí)，都要使用它前面已求出的子問(wèn)題的 最優(yōu)結(jié)果，最后一個(gè)子問(wèn)題的最優(yōu)解，就是整個(gè)問(wèn)題的最優(yōu) 解。第61頁(yè)/共191頁(yè)學(xué)習(xí)目標(biāo)：1 了解順序解法4 逆序解法和順序解法第62頁(yè)/共1

34、91頁(yè)動(dòng)態(tài)規(guī)劃的求解有兩種基本方法 逆序解法（后向動(dòng)態(tài)規(guī)劃方法） 如例1所使用的方法，尋優(yōu)的方向與多階段決策過(guò)程的實(shí)際行進(jìn)方向相反，從最后一段開(kāi)始計(jì)算逐段前推，求得全過(guò)程的最優(yōu)策略。 順序解法（前向動(dòng)態(tài)規(guī)劃方法） 與逆序解法相反，順序解法的尋優(yōu)的方向與過(guò)程的行進(jìn)方向相同，計(jì)算時(shí)從第一段開(kāi)始逐段向后遞推，計(jì)算后一段要用到前一段的求優(yōu)結(jié)果，最后一段計(jì)算的結(jié)果就是全過(guò)程的最優(yōu)結(jié)果。第63頁(yè)/共191頁(yè)我們?cè)俅斡美?來(lái)說(shuō)明順序解法。由于此問(wèn)題的始點(diǎn)A與終點(diǎn)E都是固定的，計(jì)算由A點(diǎn)到E點(diǎn)的最短路線與由E點(diǎn)到A點(diǎn)的最短路線沒(méi)有什么不同。若設(shè) fk( xk+1 ) 表示從起點(diǎn)A到第k階段末狀態(tài)點(diǎn)xk+1的最

35、短距離 就可以由前向后逐步求出起點(diǎn)A到各階段末狀態(tài)點(diǎn)的最短距離，最后求出起點(diǎn)A到E點(diǎn)的最短距離及路線。動(dòng)態(tài)規(guī)劃的目標(biāo)：最優(yōu)指標(biāo) f4( E )第64頁(yè)/共191頁(yè)第一步 k=0 f0( x1 ) = f0( A ) = 0 這是邊界條件0Afk( xk+1 ) 表示從起點(diǎn)A到第k階段末狀態(tài)點(diǎn)xk+1的最短距離第65頁(yè)/共191頁(yè)第二步 k=12350按 f1( x2 ) 的定義有 f1( B1 ) = v( B1, A ) + f0( A ) = 2 f1( B2 ) = v( B2, A ) + f0( A ) = 5 f1( B3 ) = v( B3, A ) + f0( A ) = 3

36、B1B2B3第66頁(yè)/共191頁(yè)第三步 k=22350按 f2( x3 ) 的定義有 v( C1, B1 ) + f1( B1 ) = 7+2 = 9 f2( C1 ) = min v( C1, B2 ) + f1( B2 ) = 3+5 = 8 v( C1, B3 ) + f1( B3 ) = 5+3 = 8 u2( C1 ) = B2 或B38C1狀態(tài)轉(zhuǎn)移方程： xk=Tk( xk+1, uk )第67頁(yè)/共191頁(yè)第三步 k=22350按 f2( x3 ) 的定義有 v( C2, B1 ) + f1( B1 ) = 5+2 = 7 f2( C2 ) = min v( C2, B2 ) +

37、 f1( B2 ) = 2+5 = 7 v( C2, B3 ) + f1( B3 ) = 1+3 = 4 u2( C2 ) = B384C2第68頁(yè)/共191頁(yè)第三步 k=22350按 f2( x3 ) 的定義有 v( C3, B1 ) + f1( B1 ) = 6+2 = 8 f2( C3 ) = min v( C3, B2 ) + f1( B2 ) = 4+5 = 9 v( C3, B3 ) + f1( B3 ) = 5+3 = 8 84u2( C3 ) = B1 或B38C3第69頁(yè)/共191頁(yè)第四步 k=32350按 f3( x4 ) 的定義有 v( D1, C1 ) + f2( C1

38、 ) = 1+8 = 9 f3( D1 ) = min v( D1, C2 ) + f2( C2 ) = 6+4 = 10 v( D1, C3 ) + f2( C3 ) = 3+8 = 11 84u3( D1 ) = C189D1第70頁(yè)/共191頁(yè)第四步 k=32350按 f3( x4 ) 的定義有 v( D2, C1 ) + f2( C1 ) = 4+8 = 12 f3( D2 ) = min v( D2, C2 ) + f2( C2 ) = 3+4 = 7 v( D2, C3 ) + f2( C3 ) = 3+8 = 11 84u3( D2 ) = C2897D2第71頁(yè)/共191頁(yè)第五

39、步 k=42350按 f4( x5 ) 的定義有 v( E, D1 ) + f3( D1 ) = 3+9 = 12 f4( E ) = min v( E, D2 ) + f3( D2 ) = 4+7 = 11 84u4( E ) = D289711E第72頁(yè)/共191頁(yè)235084897即可得到最優(yōu)路線。因此，由A到終點(diǎn)E的最優(yōu)解為： AB3C2D2E由點(diǎn)A到終點(diǎn)E的最優(yōu)值為11。11第73頁(yè)/共191頁(yè)AB1B2C1C2C3D24333321114第74頁(yè)/共191頁(yè)AB1B2C1C2C3D2433321114C1C2C3第75頁(yè)/共191頁(yè)AB1B2C1C2C3D24333321114B1

40、B231()1fC32()3fC33()4fC第76頁(yè)/共191頁(yè)nn = min 6 = 3n 5AB1B2C1C2C3D24333321114B1B231()1fC32()3fC33()4fC第77頁(yè)/共191頁(yè)AB1B2C1C2C3D24333321114A21()4fB22()3fBd(A, B1 ) f2 ( B1 )d(A, B2 ) f2 ( B2 )(最短路線為AB1C1 D)第78頁(yè)/共191頁(yè)（xkuk）。n又機(jī)器設(shè)備在使用中會(huì)有損壞，設(shè)機(jī)器用于工作A時(shí)，一年后n能繼續(xù)使用的完好機(jī)器數(shù)占年初投入量的70%；若用于工作Bn時(shí)，一年后能繼續(xù)使用的完好機(jī)器數(shù)占年初投入量的90%。

41、則在n下一年初能繼續(xù)用于A、B工作的設(shè)備數(shù)為xk+1=0.7uk+0.9(xknuk)。n設(shè)第1年初完好的機(jī)器總數(shù)為1000臺(tái)，問(wèn)在連續(xù)5年內(nèi)每年應(yīng)如n何分配用于A、B兩項(xiàng)工作的機(jī)器數(shù)，使5年的總收益為最大。第79頁(yè)/共191頁(yè)第80頁(yè)/共191頁(yè)這里xk和uk均取連續(xù)變量，它們的非整數(shù)值可以這樣理解，如xk=0.6，就表示一臺(tái)機(jī)器在第k年度中正常工作時(shí)間只占6/10；uk=0.3，就表示一臺(tái)機(jī)器在該年度只有3/10的時(shí)間能正常用于A工作。第81頁(yè)/共191頁(yè)u5*=x5= max 3u5+5x5 0u5x5= 8x5f4(x4) = max 8u4+5(x4u4) + f5( x5 ) 0u

42、4x4=max 8u4+5(x4u4)+8x5 0u4x4狀態(tài)轉(zhuǎn)移方程：xk+1=0.7uk + 0.9( xkuk )=max 8u4+5(x4u4)+80.7u4+0.9( x4u4 ) 0u4x4=max 1.4u4+12.2x4 0u4x4u4*=x4=13.6x4第82頁(yè)/共191頁(yè)f3(x3) = max 8u3+5(x3u3) + f4( x4 ) 0u3x3=max 8u3+5(x3u3)+13.6x4 0u3x3狀態(tài)轉(zhuǎn)移方程：xk+1=0.7uk + 0.9( xkuk )=max 8u3+5(x3u3)+13.60.7u3+0.9( x3u3 ) 0u3x3=max 0.2

43、8u3+17.22x3 0u3x3u3*=x3=17.5x3第83頁(yè)/共191頁(yè)f2(x2) = max 8u2+5(x2u2) + f3( x3 ) 0u2x2=max 8u2+5(x2u2)+17.5x3 0u2x2狀態(tài)轉(zhuǎn)移方程：xk+1=0.7uk + 0.9( xkuk )=max 8u2+5(x2u2)+17.50.7u2+0.9( x2u2 ) 0u2x2=max 0.504u2+20.8x2 0u2x2u2*= 0=20.8x2第84頁(yè)/共191頁(yè)f1(x1) = max 8u1+5(x1u1) + f2( x2 ) 0u1x1=max 8u1+5(x1u1)+20.8x2 0u

44、1x1狀態(tài)轉(zhuǎn)移方程：xk+1=0.7uk + 0.9( xkuk )=max 8u1+5(x1u1)+20.80.7u1+0.9( x1u1 ) 0u1x1=max 0.05u1+23.7x1 0u1x1u1*= 0=23.7x1第85頁(yè)/共191頁(yè)第86頁(yè)/共191頁(yè)年年度度年初完好機(jī)器數(shù)年初完好機(jī)器數(shù)用于工作用于工作A的數(shù)的數(shù)量量用于工作用于工作B的數(shù)的數(shù)量量1x1 = 1000u1*=02x2=0.7u1 + 0.9( x1u1 )u2*=03x3=0.7u2 + 0.9( x2u2 )u3*=x34x4=0.7u3 + 0.9( x3u3 )u4*=x45x5=0.7u4 + 0.9(

45、 x4u4 )u5*=x5x1u1 =1000 x2 = 900 x2u2 =900 x3 = 810u3= 810 x3u3 =0 x4 = 567u4= 567x4u4 =0 x5 = 397u5= 397x5u5 =0第87頁(yè)/共191頁(yè)ABCD218382434314352231410312125第88頁(yè)/共191頁(yè)kxku( )|241,2,3,4kkkkD xuuk1kkkxxu1,2,3k ( )kkp xkku44,41 ,41( )( )( )ki ikkiikkki ki kVpu p upup u V第89頁(yè)/共191頁(yè)隊(duì)數(shù)隊(duì)前4個(gè)部位的預(yù)期損失不再起影響，故邊界條件，因

46、此有n因，又的可能值為，故由表1的數(shù)據(jù)可得表2的結(jié)果。()kkfxkkx11()( )min( )()kkkkkkkkkuD xf xp ufx4k 444455()( )( )( )minkkkuD xf xp uf x5 5( ) 0f x 4444()()()minkkkuDxfxp u44()2,3,4D x4x426x第90頁(yè)/共191頁(yè) 2 3 4 2 34 _ _ 34 2 3 34 31 _ 31 3 4 34 31 25 25 4 5 34 31 25 25 4 6 34 31 25 25 44u4x44()pu4 4()fx*4u第91頁(yè)/共191頁(yè)3k 333333344

47、()()()()minuDxfxpufx33()2,3,4D x348x 表3 2 3 4 4 24+34 58 2 5 24+31 22+34 55 2 6 24+25 22+31 21+34 49 2 7 24+25 22+25 21+31 47 3 8 24+25 22+25 31+25 46 43u3x33433()()pufxu33( )f x*3u第92頁(yè)/共191頁(yè)2k 222222233()()()()minuDxfxpufx22()2,3,4D x2810 x 表4 2 3 4 8 38+49 35+55 31+58 87 2 9 38+47 35+49 31+55 84 3

48、 10 38+46 35+47 31+49 80 42u2x2 2( )f x*2u22322()()pufxu第93頁(yè)/共191頁(yè)1k 111111122()()()()minuDxf xp ufx11()2,3,4D x112x 2 3 4 12 18+80 14+84 10+87 97 41u1x1 1( )f x*1u11211()()pufxu第94頁(yè)/共191頁(yè)第95頁(yè)/共191頁(yè)第96頁(yè)/共191頁(yè)例 Wyndor Glass Company Problem12max35Zxx1212124212. .3218,0 xxstxxxx使用動(dòng)態(tài)規(guī)劃進(jìn)行求解第97頁(yè)/共191頁(yè)12一、

49、動(dòng)態(tài)規(guī)劃問(wèn)題建模這個(gè)問(wèn)題需要對(duì)兩個(gè)相關(guān)活動(dòng)(activity)確定其活動(dòng)水平(level of activity)，因此我們可以將這兩個(gè)活動(dòng)看作動(dòng)態(tài)規(guī)劃中的階段。決策變量 ：第 k 個(gè)活動(dòng)的活動(dòng)水平（ level ofactivity ）kx狀態(tài)變量 ：可用于第k階段生產(chǎn)的資源量（右端項(xiàng)）。即ks123(,)kkkksRRR第98頁(yè)/共191頁(yè)狀態(tài)轉(zhuǎn)移方程：12111122213231114123183RRxxRRRRxx階段指標(biāo)函數(shù) ：第 k 階段確定 時(shí)所產(chǎn)生的利潤(rùn)即)(kkxgkx最優(yōu)指標(biāo)函數(shù) ：第 k 階段狀態(tài)為 且采取最佳投資策略，從第 k 個(gè)活動(dòng)以及以后的最大總利潤(rùn)。)(kksfk

50、s 逆序法基本遞推方程： 1133()max()()2,1( )0kkkkkkkxfsgxfskf skkc x第99頁(yè)/共191頁(yè)二、動(dòng)態(tài)規(guī)劃問(wèn)題求解（1）k=2 時(shí)232222122232231323330min(,)22(,)max5(,)RRxfRRRxfRRR33( )0f s因?yàn)?32223222212223220min(,)22(,)max55min,22RRxRRfRRRx故有2122232(,)sRRR2122232(,)fRRR*2x32225min,22RR1222320,0,0RRR2322min(,)22RRk=2 時(shí)決策表第100頁(yè)/共191頁(yè)（2）k=1 時(shí)131

51、111112131121222320min(,)3(,)max3(,)RxRf RRRxfRRR因?yàn)槌鯐r(shí)狀態(tài)確定112131(,)(4,12,18)RRR且111121112131104121104(4,12,18)max3(,)max3(4,12,18)xxfxfRx RRxxfxx12111122213231114123183RRxxRRRRxx第101頁(yè)/共191頁(yè)111121112131104121104(4,12,18)max3(,)max3(4,12,18)xxfxfRx RRxxfxx2122232(,)sRRR2122232(,)fRRR*2x32225min,22RR1222

52、320,0,0RRR2322min(,)22RRk=2 時(shí)決策表111041812max35min,23xxx第102頁(yè)/共191頁(yè)111121112131104121104(4,12,18)max3(,)max3(4,12,18)xxfxfRx RRxxfxx111041812max35min,23xxx在可行區(qū)間 上104x11116021812min,3239242ifxxxifx1111041133002(4,12,18)max945242xxxfxx第103頁(yè)/共191頁(yè)因?yàn)?102max330 xx11249max452xx和都在x1=2時(shí)獲得最大值36 21112131(,)sR

53、RR1112131(,)f RRR*1x4,12,18k=1 時(shí)決策表1111041133002(4,12,18)max945242xxxfxx所以11*2,(4,12,18)36xf第104頁(yè)/共191頁(yè)36 21112131(,)sRRR1112131(,)f RRR*1x4,12,18k=1 時(shí)決策表2122232(,)sRRR2122232(,)fRRR*2x32225min,22RR1222320,0,0RRR2322min(,)22RRk=2 時(shí)決策表12111122213231114123183RRxxRRRRxx*122,(2,12,12)xs*26x第105頁(yè)/共191頁(yè)背

54、包 問(wèn) 題 一般的提法為：一旅行者攜帶背包去登山。已知他所能承受 的背包重量的極限為a (千克)，現(xiàn)有n種物品可供他選擇裝入背包。第i種物品的單位重量為 (千克)，其價(jià)值（可以是表明本物品對(duì)登山者的重要性指標(biāo)）是攜帶數(shù)量 的函數(shù) （i=1，2，n）.問(wèn)旅行者應(yīng)如何選擇攜帶物品的件數(shù)，以使總價(jià)值最大？ia)(iixgix此模型解決的是運(yùn)輸工具包括衛(wèi)星的最優(yōu)裝載問(wèn)題。其數(shù)學(xué)模型為：第106頁(yè)/共191頁(yè)設(shè) 為第 i 種物品裝入的件數(shù)，則背包問(wèn)題可歸結(jié)為如下 ix形式的整數(shù)規(guī)劃模型：niiixgz1)(max), 2 , 101nixaxainiii（整數(shù)下面從一個(gè)例子來(lái)分析動(dòng)態(tài)規(guī)劃建模。例 有一輛

55、最大貨運(yùn)量為10 t 的卡車，用以裝載3種貨物，每種貨物的單位重量及相應(yīng)單位價(jià)值如表7-4 所示。應(yīng)如何裝載可使總價(jià)值最大？第107頁(yè)/共191頁(yè)貨物編號(hào)貨物編號(hào)i 1 2 3單位重量（單位重量（t） 3 4 5單位價(jià)值單位價(jià)值 ci 4 5 6表 7- 4 設(shè)第 種貨物裝載的件數(shù)為 ix),3 , 2 , 1( ii則問(wèn)題可表為：321654maxxxxz) 3 , 2 , 1(, 010543321ixxxxi整數(shù)階段k: 將可裝入物品按1，2，3的順序排序，每段裝入一種物品，共劃分3個(gè)階段，即k=1,2,3.第108頁(yè)/共191頁(yè)狀態(tài)變量 ：在第k段開(kāi)始時(shí)，背包中允許裝入前k種物品的總重

56、量。ks決策變量 ：裝入第k種物品的件數(shù)。kx狀態(tài)轉(zhuǎn)移方程：1kkkkssa x最優(yōu)指標(biāo)函數(shù) ：在背包中允許裝入物品的總重量不超過(guò) kg，采取最優(yōu)策略只裝前k種物品時(shí)的最大使用價(jià)值()kkfsks貨物1貨物2貨物3310s 2335ssx1224ssx0113ssx1114)(xxg2225)(xxg3336)(xxg24x35x13x第109頁(yè)/共191頁(yè)由此可得動(dòng)態(tài)規(guī)劃的順序遞推方程為：1000( )max( )()1,2,3( )0k kkkkkkkkkka xsf sg xfsa xkf sK=1 時(shí)1111111000 3( )max( )( )xsxf sg xf s為整數(shù)1111

57、0 3max4 xsxx為整數(shù)貨物1貨物2貨物3310s 2335ssx1224ssx0113ssx1114)(xxg2225)(xxg3336)(xxg24x35x13x第110頁(yè)/共191頁(yè)K=1 時(shí)1111111000 3( )max ( )( )xsxf sg xf s為整數(shù)11110 3max4 xsxx為整數(shù)注意到：10,1,10s 例如：17s 時(shí)，4max)7(1730111xfxx為整數(shù)4max12, 1 , 01xx 88 , 4 , 0max2*1x其它計(jì)算結(jié)果見(jiàn)表7-5：貨物1貨物2貨物3310s 2335ssx1224ssx0113ssx1114)(xxg2225)(

58、xxg3336)(xxg24x35x13x第111頁(yè)/共191頁(yè)1x1s14x11( )f s1x0 1 2 3 0 1 2 3 4 5 6 7 8 9 104040 40 40 41 40 41 4240 41 42 430004812000123表 7- 5第112頁(yè)/共191頁(yè)K=2 時(shí)2222222110 4( )max ()( )xsxf sgxf s為整數(shù)22221220 4max 5(4)xsxxf sx為整數(shù)其中20,1,10s 例如：210s 時(shí)，222222120 410()(10)max 5(104)xxfsfxfx為整數(shù))410(5max2122, 1 , 02xfxx

59、111max0(10),5(6),10(2)fff貨物1貨物2貨物3310s 2335ssx1224ssx0113ssx1114)(xxg2225)(xxg3336)(xxg24x35x13x第113頁(yè)/共191頁(yè)111max0(10),5(6),10(2)fff13010, 85 ,120max1*2x表 7- 51x1s14x11( )f s1x0 1 2 3 0 1 2 3 4 5 6 7 8 9 104040 40 40 41 40 41 4240 41 42 430004812000123第114頁(yè)/共191頁(yè)其它計(jì)算結(jié)果見(jiàn)表7-6：2x2s21225(4)xf sx22()fs2x

60、 0 1 2 0 1 2 3 4 5 6 7 8 9 10500 504 510 5012 518 520 0513011表 7- 6第115頁(yè)/共191頁(yè)K=3 時(shí)33333333220 5( )(10)max ()()xsxf sfg xf s為整數(shù))510(6max323105033xfxxx為整數(shù))510(6max3232, 1 , 03xfxx)0(12),5(6),10(0max222fff貨物1貨物2貨物3310s 2335ssx1224ssx0113ssx1114)(xxg2225)(xxg3336)(xxg24x35x13x第116頁(yè)/共191頁(yè)2x2s21225(4)xf