運(yùn)籌學(xué)第八章動(dòng)態(tài)規(guī)劃.ppt

,第八章 動(dòng)態(tài)規(guī)劃,引 言,動(dòng)態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化的一種方法。 該方法是由美國數(shù)學(xué)家貝爾曼（R. E. Bellman）等人在20世 紀(jì)50年代初提出的。并成功地解決了生產(chǎn)管理、工程技術(shù)等方 面的許多問題，從而建立了運(yùn)籌學(xué)的一個(gè)新的分支，即動(dòng)態(tài)規(guī) 劃。Bellman在1957年出版了Dynamic Programming一 書，是動(dòng)態(tài)規(guī)劃領(lǐng)域中的第一本著作。,動(dòng)態(tài)規(guī)劃與其他規(guī)劃方法的不同之處在于： 動(dòng)態(tài)規(guī)劃是求解某類問題（多階段決策問題）的一種方法， 是考察問題的一種途徑，而不是一種特定算法。 因此，它不像線性規(guī)劃那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確 定義的一組（算法）規(guī)則，而必須對(duì)具體問題進(jìn)行具體分析處 理。因此，學(xué)習(xí)動(dòng)態(tài)規(guī)劃時(shí)，除對(duì)基本概念和基本方法正確理解 外，還應(yīng)在一定經(jīng)驗(yàn)積累基礎(chǔ)上，以豐富的想像力去建立模型， 用創(chuàng)造性的技巧去求解。,提 綱,1 動(dòng)態(tài)規(guī)劃實(shí)例 2 動(dòng)態(tài)規(guī)劃的基本概念 3 動(dòng)態(tài)規(guī)劃的基本思想與基本原理 4 逆序解法與順序解法,學(xué)習(xí)目標(biāo)： 1 明確什么是多階段的決策問題，特別要注意沒有明顯 的時(shí)段背景的問題如何化歸為多階段的決策問題。,1 動(dòng)態(tài)規(guī)劃實(shí)例,P156 例2 機(jī)器負(fù)荷分配問題（時(shí)間階段問題） 設(shè)有某種機(jī)器設(shè)備，用于完成兩類工作A和B。若第k年初完好 機(jī)器的數(shù)量為 xk ，若以數(shù)量 uk 用于A，余下的（xkuk）用于 工作B，則該年的預(yù)期收入為 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(xk uk)。 設(shè)第1年初完好的機(jī)器總數(shù)為1000臺(tái)，問在連續(xù)5年內(nèi)每年應(yīng)如 何分配用于A、B兩項(xiàng)工作的機(jī)器數(shù)，使5年的總收益為最大。,1 動(dòng)態(tài)規(guī)劃實(shí)例,相應(yīng)的問題稱為多階段決策問題。,這是一個(gè)多階段決策過程。 該過程可以分為相互聯(lián)系的若干階段，每一階段都需作出決 策，從而形成全過程的決策。,第1年,u1,x2=0.7u1+ 0.9(x1-u1),u2,x3=0.7u2+ 0.9(x2-u2),u3,第4年,u4,x5=0.7u4+ 0.9(x4-u4),u5,P156 例1 最短路線問題（空間階段的例子） 設(shè)有一個(gè)旅行者從下圖中的A點(diǎn)出發(fā)，途中要經(jīng)過B、C、D等 處，最后到達(dá)終點(diǎn)E。從A到E有很多條路線可以選擇，各點(diǎn)之間的距 離如圖所示，問該旅行者應(yīng)選擇哪一條路線，使從A到達(dá)E的總的路程 為最短。,1,2,3,4,決策1,決策2,決策3,決策4,可看成 4階段 的決策 問題。,從以上兩個(gè)例子，可以知道 所謂多階段決策問題是指這樣的決策問題：其過程可分為若 干個(gè)相互聯(lián)系的階段，每一階段都對(duì)應(yīng)著一組可供選擇的決策， 每一決策的選定既依賴于當(dāng)前面臨的狀態(tài)，又影響以后總體的效 果。 當(dāng)每一階段的決策選定以后，就構(gòu)成一個(gè)決策序列，稱為一 個(gè)策略，它對(duì)應(yīng)著一個(gè)確定的效果。多階段決策問題就是尋找使 此效果最好的策略。,多階段決策過程的特點(diǎn),1.各階段的決策相互關(guān)聯(lián) 多階段決策過程最優(yōu)化的目的，是要達(dá)到整個(gè)活動(dòng)過程的總體 效果最優(yōu)，而不是某個(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)化方法。,2.各個(gè)階段的決策一般與“時(shí)間”有關(guān) 動(dòng)態(tài)規(guī)劃方法與“時(shí)間”關(guān)系很密切，隨著時(shí)間過程的發(fā)展而決 定各階段的決策，從而產(chǎn)生一個(gè)決策序列，這就是“動(dòng)態(tài)”的意 思。 但是，一些與時(shí)間無關(guān)的靜態(tài)問題，只要在問題中人為引 入“時(shí)間”因素，也可將其看成是多階段的決策問題，用動(dòng)態(tài)規(guī)劃 方法去處理。,學(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ī)劃的基本概念,為了便于求解和表示決策及過程的發(fā)展順序，而把所給問題恰 當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系又有區(qū)別的子問題，稱之為多段決策 問題的階段。一個(gè)階段，就是需要作出一個(gè)決策的子問題。 通常，階段是按決策進(jìn)行的時(shí)間或空間上先后順序劃分的。 描述階段的變量稱為階段變量，常記為k，k=1,2, ,n。 如本例可按空間分為4個(gè) 階段來求解， k=1, 2, 3, 4。,（1）階段（stage）,狀態(tài)：每階段初的客觀條件。描述各階段狀態(tài)的變量稱為狀態(tài) 變量，常用xk表示第k階段的狀態(tài)。,（2）狀態(tài)（state）,例1中，狀態(tài)就是某 階段的出發(fā)位置。,按狀態(tài)變量的取值是連續(xù)還是離散，可將動(dòng)態(tài)規(guī)劃問題分為離 散型和連續(xù)型。,動(dòng)態(tài)規(guī)劃中的狀態(tài)應(yīng)滿足無后效性（馬爾科夫性）： 所謂無后效性指系統(tǒng)到達(dá)某個(gè)狀態(tài)前的過程的決策將不影響 到該狀態(tài)以后的決策。指系統(tǒng)從某個(gè)階段往后的發(fā)展，僅由本 階段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經(jīng)歷的狀態(tài) 和決策（歷史）無關(guān)。過程的過去歷史只能通過當(dāng)前的狀態(tài)去影 響它未來的發(fā)展 例1中，當(dāng)某階段的狀態(tài)已選定某個(gè)點(diǎn)時(shí)，從這個(gè)點(diǎn)以后的路 線只與該點(diǎn)有關(guān)，不受該點(diǎn)以前的路線的影響，所以滿足狀態(tài)的 無后效性。,狀態(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。 ,（3）決策（decision）,當(dāng)過程處于某一階段的某狀態(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。 如我們決定選擇C1， 則可表示為：u2( B1 ) = C1。,B1,C1,C2,C3,決策集合：第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 ；,B1,C1,C2,C3,決策集合實(shí)際上是決策的約束條件，uk( xk ) Dk( xk ) 。,小結(jié) 階段 k、 狀態(tài) xk、 狀態(tài)集合 Sk、 決策 uk( xk )、 決策集合 Dk( xk )。,（4）狀態(tài)轉(zhuǎn)移律（方程）,狀態(tài)轉(zhuǎn)移律：從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)）。,上例中， u2( B1 ) = C2 狀態(tài)轉(zhuǎn)移律為： xk+1 = uk( xk ),一般來說，下一階段狀態(tài)變量xk+1的取值是上階段的某一狀態(tài) 變量xk和上階段決策變量uk(xk)的函數(shù)，記為 xk+1=Tk( xk, uk(xk) ),（5）策略（policy）和子策略（subpolicy）,策略：由依次進(jìn)行的n個(gè)階段決策構(gòu)成的決策序列就構(gòu)成一個(gè) 策略，用 p1n u1(x1), u2(x2), , un(xn) 表示。,本例中，如p14 u1(A)=B1, u2(B1) = C2, u3(C2) = D1, u4(D1) = E 表示其中一個(gè)策略，其總距離為2+5+6+3=16。,策略集合：在實(shí)際問題中，由于在各個(gè)階段可供選擇的決策有 許多個(gè)，因此，它們的不同組合就構(gòu)成了許多可供選擇的決策序 列（策略），由它們組成的集合，稱為策略集合，記作 P1n。 從策略集合中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。,子策略：從k階段到第n階段，依次進(jìn)行的階段決策構(gòu)成的 決策序列稱為k部子策略，表示為 pkn = uk(xk), uk+1(xk+1), , un(xn) ,如從第3階段的C2 狀態(tài)開始的一個(gè)子策 略可表示： p34=u3(C2) = D1, u4(D1) = E ,C2,（6）指標(biāo)函數(shù),用來衡量策略或子策略或決策的效果的某種數(shù)量指標(biāo)，就稱 為指標(biāo)函數(shù)。 它是定義在全過程或各子過程或各階段上的確定數(shù)量函數(shù)。 對(duì)不同問題，指標(biāo)函數(shù)可以是諸如費(fèi)用、成本、產(chǎn)值、利潤、 產(chǎn)量、耗量、距離、時(shí)間、效用，等等。,階段 指標(biāo)函數(shù),過程 指標(biāo)函數(shù),階段指標(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。,過程指標(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 =9,C2,過程指標(biāo)函數(shù)Vkn通常是描述所實(shí)現(xiàn)的全過程或k后部子過程效 果優(yōu)劣的數(shù)量指標(biāo)，它是由各階段的階段指標(biāo)函數(shù)vk(xk,uk)累積形 成的。 （1）可分性：適于用動(dòng)態(tài)規(guī)劃求解的問題的過程指標(biāo)函數(shù)（即目 標(biāo)函數(shù)），必須具有關(guān)于階段指標(biāo)的可分離形式，即對(duì)于后部子 過程的指標(biāo)函數(shù)可以表示為： Vkn( xk, uk, xk+1, uk+1, , xn ) = vk(xk, uk) vk+1(xk+1, uk+1) vn(xn, un) 式中，表示某種運(yùn)算，可以是加、減、乘、除、開方等。,多階段決策問題中，常見的目標(biāo)函數(shù)形式之一是取各階段效應(yīng) 之和的形式，即: 有些問題，如系統(tǒng)可靠性問題，其目標(biāo)函數(shù)是取各階段效應(yīng)的 連乘積形式，如： 總之，具體問題的目標(biāo)函數(shù)表達(dá)形式需要視具體問題而定。,（2）可遞推：過程指標(biāo)函數(shù)Vkn要滿足遞推關(guān)系，即,可遞推,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 ),最優(yōu)指標(biāo)函數(shù)：表示從第 k 階段狀態(tài)為 xk 時(shí)采用最優(yōu)策略 pkn*到過程終止時(shí)的最佳效益值。記為 fk( xk )。 fk( xk ) = Vkn( xk , pkn*) = 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),多階段決策問題的數(shù)學(xué)模型 綜上所述，適于應(yīng)用動(dòng)態(tài)規(guī)劃方 法求解的一類多階段決策問題的數(shù)學(xué)模型呈以下形式: f1 = opt V1n( x1 , p1n ) 最優(yōu)指標(biāo)函數(shù) xk+1=Tk( xk, uk(xk) ) 狀態(tài)轉(zhuǎn)移方程 ukDk 決策變量 xkSk 狀態(tài)變量 k=1,2,n 階段變量,st.,上述數(shù)學(xué)模型說明了對(duì)于給 定的多階段決策過程，求取一 個(gè)(或多個(gè))最優(yōu)策略或最優(yōu)決策 序列 u1, u2, , un ，使之既滿 足左式給出的全部約束條件， 又使左式所示的目標(biāo)函數(shù)取得 極值，并且同時(shí)指出執(zhí)行該最 優(yōu)策略時(shí)，過程狀態(tài)演變序列 即是最優(yōu)路線。,小結(jié):,指標(biāo)函數(shù)形式:和、積,無后效性,可遞推,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 ) ,解多階段決策過程問題，求出, u1*, u2*, , un* , x1*, x2*, , xn* ,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ī)劃求解多階段決策問題的第一 步，在確定多階段特性后，按時(shí)間或空間先后順序， 將過程劃分為若干相互聯(lián)系的階段。對(duì)于靜態(tài)問題要 人為地賦予“時(shí)間”概念，以便劃分階段。,建立動(dòng)態(tài)規(guī)劃模型的步驟,選擇狀態(tài)變量既要能確切描述過程演變又要滿足無后 效性，而且各階段狀態(tài)變量的取值能夠確定。,通常選擇所求解問題的關(guān)鍵變量作為決策變量，同時(shí) 要給出決策變量的取值范圍，即確定允許決策集合。,根據(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ī)劃基本方程。,以上五步是建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。 由于動(dòng)態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動(dòng)態(tài)規(guī)劃模 型沒有統(tǒng)一的模式，建模時(shí)必須根據(jù)具體問題具體分 析，只有通過不斷實(shí)踐總結(jié)，才能較好掌握建模方法 與技巧。 下面我們看一個(gè)具體的例子,P156 例2 機(jī)器負(fù)荷分配問題（時(shí)間階段問題）,P156 例2 機(jī)器負(fù)荷分配問題（時(shí)間階段問題） 設(shè)有某種機(jī)器設(shè)備，用于完成兩類工作A和B。若第k年初完好 機(jī)器的數(shù)量為 xk ，若以數(shù)量 uk 用于A，余下的（xkuk）用于 工作B，則該年的預(yù)期收入為 g( uk ) + h( xkuk )。其中 g( 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(xk uk)。 設(shè)第1年初完好的機(jī)器總數(shù)為1000臺(tái)，問在連續(xù)5年內(nèi)每年應(yīng)如 何分配用于A、B兩項(xiàng)工作的機(jī)器數(shù)，使5年的總收益為最大。,1.劃分階段,按年度來劃分階段，k=1,2,3,4,5,2.正確選擇狀態(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工作。,4.確定狀態(tài)轉(zhuǎn)移方程,狀態(tài)轉(zhuǎn)移方程為 xk+1=0.7uk+0.9(xkuk),5.確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃基本方程,指標(biāo)函數(shù)為,令最優(yōu)指標(biāo)函數(shù)fk( xk ) 表示由資源量xk出發(fā)，從第k年開始到 第5年結(jié)束時(shí)所取得的最大預(yù)期收入。因而有：,fk( xk ) = max ,學(xué)習(xí)目標(biāo)： 1 掌握最優(yōu)化原理的內(nèi)容 2 掌握逆序解法,3 動(dòng)態(tài)規(guī)劃的基本思想與基本原理,多階段決策過程的最優(yōu)化一般有三種思路求解 1.全枚舉法或窮舉法：它的基本思想是列舉出所有可能發(fā)生的 方案和結(jié)果，再對(duì)它們一一進(jìn)行比較，求出最優(yōu)方案。 可以計(jì)算：從A到E的路程可分為4個(gè)階段。第一段走法有3 種，第二段走法有3種，第三段走法有2種，第四段走法僅1種， 共有332118條可能的路線，分別算出各條路線的距離， 最后進(jìn)行比較，可知最優(yōu)路線是AB3C2 D2E，最短距離 是11。 用窮舉法求最優(yōu)路線的計(jì)算 工作量將會(huì)十分龐大，而且 其中包含著許多重復(fù)計(jì)算。,2.局部最優(yōu)路徑法：某人從k點(diǎn)出發(fā)，并不顧及全線是否最短， 只是選擇當(dāng)前最短途徑，“逢近便走”，錯(cuò)誤地以為局部最優(yōu)會(huì) 致整體最優(yōu)，在這種想法指導(dǎo)下，所取決策必是 AB1C2D2E，全程長度是14；顯然，這種方法的結(jié)果常 是錯(cuò)誤的。,小結(jié)： 全枚舉法雖可找出最優(yōu)方案，但不是個(gè)好算法， 局部最優(yōu)法則完全是個(gè)錯(cuò)誤方法， 只有動(dòng)態(tài)規(guī)劃方法屬較科學(xué)有效的算法,作為一個(gè)全過程的最優(yōu)策略具有這樣的性質(zhì)：對(duì)于最優(yōu)策略 過程中的任意狀態(tài)而言，無論其過去的狀態(tài)和決策如何，余下 的諸決策必構(gòu)成一個(gè)最優(yōu)子策略。（一個(gè)最優(yōu)策略的子策略總 是最優(yōu)的）,3. 貝爾曼最優(yōu)化原理（動(dòng)態(tài)規(guī)劃方法）,作該原理的具體解釋是，若某一全過程最優(yōu)策略為： p1n*( x1 )= u1*(x1), , uk*(xk), uk+1*(xk+1), , un*(xn) 則對(duì)上述策略中所隱含的任一狀態(tài)（xk）而言，第k子過程上 對(duì)應(yīng)于 xk 的最優(yōu)策略必然包含在上述全過程最優(yōu)策略p1n*中， 即為 pkn*( xk )= uk*(xk), uk+1*(xk+1), , un*(xn) ,C1,D1,A,B3,D2,E,C2,反證法進(jìn)行證明,最優(yōu)性原理在最短路線中的應(yīng)用 在最短路線中，若找到了AB3C2D2E是由A到E的最 短路線，則B3C2D2E必是由B3出發(fā)到E點(diǎn)的所有可能選擇的 不同路線中的最短路線。（一個(gè)最優(yōu)策略的子策略總是最優(yōu)的）,4.函數(shù)基本方程 基于這個(gè)原理，提出了一種逆序遞推法；該法的關(guān)鍵在于給 出一種遞推關(guān)系。一般把這種遞推關(guān)系稱為動(dòng)態(tài)規(guī)劃的函數(shù)基本 方程。 對(duì)于求最小的加法的基本方程為（如例1）：,fk( xk ) = min vk(xk, uk ) + fk+1(xk+1) fn+1( xn+1 ) = 0,邊界條件,ukDk,用函數(shù)基本方程逆推求解是常用的方法： 首先要有效地建立動(dòng)態(tài)規(guī)劃模型， 然后再遞推求解， 最后得出結(jié)論。 正確地建立一個(gè)動(dòng)態(tài)規(guī)劃模型，是解決問題的關(guān)鍵。,5.標(biāo)號(hào)法（只適用于一類最優(yōu)路線問題的特殊解法） 標(biāo)號(hào)法是借助網(wǎng)絡(luò)圖通過分段標(biāo)號(hào)來求出最優(yōu)路線的一種 簡便、直觀的方法。通常標(biāo)號(hào)法采取“逆序求解”的方法來尋找問 題的最優(yōu)解，即從最后階段開始，逐次向階段數(shù)小的方向推算， 最終求得全局最優(yōu)解。,E,A,標(biāo)號(hào)法的一般步驟： （1）給最后一段標(biāo)號(hào)，該段各狀態(tài)（即各始點(diǎn)）到終點(diǎn)的距 離用數(shù)字分別標(biāo)在各點(diǎn)上方的方格內(nèi)，并用粗箭線連接各點(diǎn)和終 點(diǎn)。 （2）向前遞推，給前一階段的各個(gè)狀態(tài)標(biāo)號(hào)。每個(gè)狀態(tài)上方 方格內(nèi)的數(shù)字表示該狀態(tài)到終點(diǎn)的最短距離。將剛標(biāo)號(hào)的點(diǎn)沿著 最短距離用粗箭線連接起來，表示出各剛標(biāo)號(hào)的點(diǎn)到終點(diǎn)的最短 路線。 （3）逐次向前遞推，直到將第一階段的狀態(tài)（即起點(diǎn)）標(biāo) 號(hào)，起點(diǎn)方格內(nèi)的數(shù)字就是起點(diǎn)到終點(diǎn)的最短距離，從起點(diǎn)開始 連接終點(diǎn)的粗箭線就是最短路線。,第（1）步 k=5, f5( x5 ) = f5( E ) = 0 這是邊界條件,0,E,fk( xk ) 表示從第 k 階段狀態(tài) xk 到 E 點(diǎn)的的最短距離,第（2）步 k=4,狀態(tài)變量 x4 可取兩種狀態(tài) D1、D2。 由D1到終點(diǎn)E只有一條路線，路長為3，即 f4( D1 ) = 3。 同理， f4( D2 ) = 4 。,3,表示由D1點(diǎn)至E 點(diǎn)的最短路長 為3。,4,0,D1,第（3）步 k=3,狀態(tài)變量 x3 可取三個(gè)值：C1、C2、C3。 由C1到終點(diǎn)E有2條路線，分別為經(jīng)過D1、D2到達(dá)E點(diǎn)（由D1、D2到達(dá) E點(diǎn)的最短路長在第一步已計(jì)算得出），需加以比較，取其中最短的。,路線1 v3(C1, D1)+ f4(D1) = 1+3=4 路線2 v3(C1, D2)+ f4(D2) = 4+4=8,3,4,則由C1到終點(diǎn)E的最短距離 f3( C1 ) = minv3(C1, D1)+ f4(D1), v3(C1, D2)+ f4(D2) = 4,4,C1,第（3）步 k=3,由C2到終點(diǎn)E有2條路線，分別為經(jīng)過D1、D2到達(dá)E點(diǎn)（由D1、D2到達(dá) E點(diǎn)的最短路長在第一步已計(jì)算得出），需加以比較，取其中最短的。,路線1 v3(C2, D1)+ f4(D1) = 6+3=9 路線2 v3(C2, D2)+ f4(D2) = 3+4=7,3,4,則由C2到終點(diǎn)E的最短距離 f3( C2 ) = minv3(C2, D1)+ f4(D1), v3(C2, D2)+ f4(D2) = 7,C2,7,4,第（3）步 k=3,由C3到終點(diǎn)E有2條路線，分別為經(jīng)過D1、D2到達(dá)E點(diǎn)（由D1、D2到達(dá) E點(diǎn)的最短路長在第一步已計(jì)算得出），需加以比較，取其中最短的。,路線1 v3(C3, D1)+ f4(D1) = 3+3=6 路線2 v3(C3, D2)+ f4(D2) = 3+4=7,3,4,則由C3到終點(diǎn)E的最短距離 f3( C3 ) = minv3(C3, D1)+ f4(D1), v3(C3, D2)+ f4(D2) = 6,C3,7,4,6,第（4）步 k=2,狀態(tài)變量 x2 可取三個(gè)值：B1、B2、B3。 由B1到終點(diǎn)E，可分別經(jīng)過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=12,3,4,則由B1到終點(diǎn)E的最短距離 f2( B1 ) = minv2(B1, C1)+ f3(C1), v2(B1, C2)+ f3(C2) v2(B1, C3)+ f3(C3) = 11,4,B1,7,6,11,第（4）步 k=2,由B2到終點(diǎn)E，可分別經(jīng)過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=10,3,4,則由B2到終點(diǎn)E的最短距離 f2( B2 ) = minv2(B2, C1)+ f3(C1), v2(B2, C2)+ f3(C2) v2(B2, C3)+ f3(C3) = 7,4,B2,7,6,11,7,第（4）步 k=2,由B3到終點(diǎn)E，可分別經(jīng)過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=11,3,4,則由B3到終點(diǎn)E的最短距離 f2( B3 ) = minv2(B3, C1)+ f3(C1), v2(B3, C2)+ f3(C2) v2(B3, C3)+ f3(C3) = 8,4,B3,7,6,11,7,8,第（5）步 k=1,狀態(tài)變量 x1 只取一個(gè)值：A。 由A到終點(diǎn)E，可分別經(jīng)過B1、B2、B3到達(dá)E點(diǎn)（由B1、B2、B3到E點(diǎn) 的最短距離在第三步已計(jì)算出），需加以比較，取其中最短的。,經(jīng)過B1點(diǎn) v1(A, B1)+ f2(B1) = 2+11=13 經(jīng)過B2點(diǎn) v1(A, B2)+ f2(B2) = 5+7=12 經(jīng)過B3點(diǎn) v1(A, B3)+ f2(B3) = 3+8=11,3,4,則由A到終點(diǎn)E的最短距離 f1( A ) = minv1(A, B1)+ f2(B1), v1(A, B2)+ f2(B2) v1(A, B3)+ f2(B3) = 11,4,A,7,6,11,7,8,11,從下圖反推可得到最優(yōu)路線。,3,4,4,A,7,6,11,7,8,11,因此，由A到終點(diǎn)E的最優(yōu)解為： AB3C2D2E 由點(diǎn)A到終點(diǎn)E的最優(yōu)值為11。,小結(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）式稱 為邊界條件。,3,4,4,A,7,6,11,7,8,11,動(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ī)劃的解法中，得到的不僅僅是由A點(diǎn)出發(fā)到E點(diǎn)的 最短路線及相應(yīng)距離，而且得到了從所有中間點(diǎn)出發(fā)到E點(diǎn)的最 短路線及相應(yīng)距離。這對(duì)于許多實(shí)際問題來說是很有用的，有 利于幫助分析所得的結(jié)果。,動(dòng)態(tài)規(guī)劃方法的基本思想,1. 將多階段決策過程劃分階段，恰當(dāng)?shù)剡x擇狀態(tài)變量、決策變 量，定義最優(yōu)指標(biāo)函數(shù)，從而把問題化成一簇同類型的子問 題，然后逐個(gè)求解。 2. 求解時(shí)從邊界條件開始，逆過程方向行進(jìn)，逐段遞推尋優(yōu)， 在每一個(gè)子問題求解時(shí)，都要使用它前面已求出的子問題的 最優(yōu)結(jié)果，最后一個(gè)子問題的最優(yōu)解，就是整個(gè)問題的最優(yōu) 解。,學(xué)習(xí)目標(biāo)： 1 了解順序解法,4 逆序解法和順序解法,動(dòng)態(tài)規(guī)劃的求解有兩種基本方法 逆序解法（后向動(dòng)態(tài)規(guī)劃方法） 如例1所使用的方法，尋優(yōu)的方向與多階段決策過程的實(shí)際 行進(jìn)方向相反，從最后一段開始計(jì)算逐段前推，求得全過程的 最優(yōu)策略。 順序解法（前向動(dòng)態(tài)規(guī)劃方法） 與逆序解法相反，順序解法的尋優(yōu)的方向與過程的行進(jìn)方向 相同，計(jì)算時(shí)從第一段開始逐段向后遞推，計(jì)算后一段要用到 前一段的求優(yōu)結(jié)果，最后一段計(jì)算的結(jié)果就是全過程的最優(yōu)結(jié) 果。,我們?cè)俅斡美?來說明順序解法。 由于此問題的始點(diǎn)A與終點(diǎn)E都是固定的，計(jì)算由A點(diǎn)到E點(diǎn) 的最短路線與由E點(diǎn)到A點(diǎn)的最短路線沒有什么不同。 若設(shè) fk( xk+1 ) 表示從起點(diǎn)A到第k階段末狀態(tài)點(diǎn)xk+1的最短距離 就可以由前向后逐步求出起點(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 ),第一步 k=0, f0( x1 ) = f0( A ) = 0 這是邊界條件,0,A,fk( xk+1 ) 表示從起點(diǎn)A到第k階段 末狀態(tài)點(diǎn)xk+1的最短距離,第二步 k=1,2,3,5,0,按 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,B1,B2,B3,第三步 k=2,2,3,5,0,按 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 或B3,8,C1,狀態(tài)轉(zhuǎn)移方程： xk=Tk( xk+1, uk ),第三步 k=2,2,3,5,0,按 f2( x3 ) 的定義有 v( C2, B1 ) + f1( B1 ) = 5+2 = 7 f2( C2 ) = min v( C2, B2 ) + f1( B2 ) = 2+5 = 7 v( C2, B3 ) + f1( B3 ) = 1+3 = 4,u2( C2 ) = B3,8,4,C2,第三步 k=2,2,3,5,0,按 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,8,4,u2( C3 ) = B1 或B3,8,C3,第四步 k=3,2,3,5,0,按 f3( x4 ) 的定義有 v( D1, C1 ) + f2( C1 ) = 1+8 = 9 f3( D1 ) = min v( D1, C2 ) + f2( C2 ) = 6+4 = 10 v( D1, C3 ) + f2( C3 ) = 3+8 = 11,8,4,u3( D1 ) = C1,8,9,D1,第四步 k=3,2,3,5,0,按 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,8,4,u3( D2 ) = C2,8,9,7,D2,第五步 k=4,2,3,5,0,按 f4( x5 ) 的定義有 v( E, D1 ) + f3( D1 ) = 3+9 = 12 f4( E ) = min v( E, D2 ) + f3( D2 ) = 4+7 = 11,8,4,u4( E ) = D2,8,9,7,11,E,2,3,5,0,8,4,8,9,7,即可得到最優(yōu)路線。,因此，由A到終點(diǎn)E的最優(yōu)解為： AB3C2D2E 由點(diǎn)A到終點(diǎn)E的最優(yōu)值為11。,11,課堂練習(xí),從A 地到D 地要鋪設(shè)一條煤氣管道,其中需經(jīng)過兩級(jí)中間站，兩點(diǎn)之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短？,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,解：整個(gè)計(jì)算過程分三個(gè)階段，從最后一個(gè)階段開始 第一階段（C D）： C 有三條路線到終點(diǎn)D 。 顯然有 f3 (C1 ) = 1 ； f3(C2 ) = 3 ； f3 (C3 ) = 4,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,2,1,1,1,4,C1,C2,C3,第二階段（B C）： B 到C 有六條路線。 d( B1,C1 ) + f3 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f3 (C2 ) = min 3+3 d( B1,C3 ) + f3 (C3 ) 1+4 4 = min 6 = 4 5,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,B1,B2,d( B2,C1 ) + f3 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f3 (C2 ) = min 3+3 d( B2,C3 ) + f3 (C3 ) 1+4 3 = min 6 = 3 5,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,B1,B2,第三階段（ A B ）： A 到B 有二條路線。 f1 (A) = min = min6,7=6,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,A,d(A, B1 ) f2 ( B1 ) d(A, B2 ) f2 ( B2 ),(最短路線為AB1C1 D),練習(xí) P156 例2 機(jī)器負(fù)荷分配問題（時(shí)間階段問題） 設(shè)有某種機(jī)器設(shè)備，用于完成兩類工作A和B。若第k年初完好 機(jī)器的數(shù)量為 xk ，若以數(shù)量 uk 用于A，余下的（xkuk）用于 工作B，則該年的預(yù)期收入為 g( uk ) + h( xkuk )。其中 g( 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(xk uk)。 設(shè)第1年初完好的機(jī)器總數(shù)為1000臺(tái)，問在連續(xù)5年內(nèi)每年應(yīng)如 何分配用于A、B兩項(xiàng)工作的機(jī)器數(shù)，使5年的總收益為最大。,構(gòu)造動(dòng)態(tài)規(guī)劃模型如下： 階段k：運(yùn)行年份（k = 1,2,6）, 其中k=1表示第一年初， 依次類推；k=6表示第5年末（即第6年初）。 狀態(tài)變量xk：第k年初完好的機(jī)器數(shù)（k=1,2, ,4），其中x6表 示第5年末（即第6年初）的完好機(jī)器數(shù)。 決策變量uk：第k年度中分配于A工作的機(jī)器數(shù)量，則xkuk為 用于B工作的機(jī)器數(shù)量。 狀態(tài)轉(zhuǎn)移方程：xk+1=0.7uk + 0.9( xkuk ) 決策允許集合：Dk( xk ) = uk | 0ukxk 階段指標(biāo)：vk( xk , uk ) = 8uk + 5( xkuk ) 終端條件：f6( x6 ) = 0,遞推方程：fk( xk ) = max vk( xk, uk ) + fk+1( xk+1 ) dkDk(xk) =max 8uk+5(xk - uk)+fk+10.7uk+0.9(xk-uk) 0dkxk,這里xk和uk均取連續(xù)變量，它們的非整數(shù)值可以這樣理 解，如xk=0.6，就表示一臺(tái)機(jī)器在第k年度中正常工作時(shí)間只 占6/10；uk=0.3，就表示一臺(tái)機(jī)器在該年度只有3/10的時(shí)間能 正常用于A工作。,f5(x5) = max 8u5+5(x5u5) + f6( x6 ) 0u5x5,u5*=x5,= max 3u5+5x5 0u5x5,= 8x5,f4(x4) = max 8u4+5(x4u4) + f5( x5 ) 0u4x4,=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 0u4x4,u4*=x4,=13.6x4,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.28u3+17.22x3 0u3x3,u3*=x3,=17.5x3,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 0u2x2,u2*= 0,=20.8x2,f1(x1) = max 8u1+5(x1u1) + f2( x2 ) 0u1x1,=max 8u1+5(x1u1)+20.8x2 0u1x1,狀態(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 0u1x1,u1*= 0,=23.7x1,由此可以得到： f1(x1)=23.7x1, u1*=0 f2(x2)=20.8x2, u2*=0 f3(x3)=17.5x3, u3*=x3 f4(x4)=13.6x4, u4*=x4 f5(x5)=8x5 u5*=x5 用x1=1000代入，得到五年最大總收入為 f1(x1)=f1(1000)=23700,x1u1 =1000,x2 = 900,x2u2 =900,x3 = 810,u3= 810,x3u3 =0,x4 = 567,u4= 567,x4u4 =0,x5 = 397,u5= 397,x5u5 =0,例4 某一警衛(wèi)部門共有12支巡邏隊(duì)，負(fù)責(zé)4個(gè)要害部位A、B、C、Dde警衛(wèi)巡邏。對(duì)每個(gè)部位可分別派出24支巡邏隊(duì)，并且由于派出巡邏隊(duì)隊(duì)數(shù)不同，各部位預(yù)期在一段時(shí)間內(nèi)可能造成的損失由差別，具體數(shù)字見表。問該警衛(wèi)部門分別派多少支巡邏隊(duì)，使總的預(yù)期損失為最小。,解 把12支巡邏隊(duì)伍往4部位看成依次分4個(gè)階段（用k表示，k=1,2,3,4) (1)逆序解法 每個(gè)階段初擁有的可派遣的巡邏隊(duì)數(shù)是前面階段決策的結(jié)果，用狀態(tài)變量 來表示。各階段的決策變量就是對(duì)各部位派出的巡邏隊(duì)數(shù)，用 表示 ，顯然個(gè)階段允許的決策集合為 英每階段初擁有可派遣的巡邏隊(duì)數(shù)等于上階段初擁有的數(shù)量減去上階段排出的數(shù)，故狀態(tài)轉(zhuǎn)移律為 若用 表示階段 派出的巡邏隊(duì)數(shù)為 時(shí)，該階段的部位的預(yù)期損失值，因此指標(biāo)函數(shù)可寫為,設(shè)用 表示 階段狀態(tài)為 ，以此出發(fā)采用最優(yōu)子策略到過程結(jié)束時(shí)的預(yù)期損失值，因此有 先考慮給D部位派巡邏隊(duì)，即 ，上式可寫為 因問題中只有4個(gè)要害部門，故第5階段初擁有的未派出的巡邏隊(duì)數(shù)隊(duì)前4個(gè)部位的預(yù)期損失不再起影響，故邊界條件 ，因此有 因 ，又 的可能值為 ，故由表1的數(shù)據(jù)可得表2的結(jié)果。,表2,再聯(lián)合考慮對(duì)C、D兩個(gè)部位派巡邏隊(duì)，即 ，這是有 因有 ，又 ，故可得表3的結(jié)果,表3,下面考慮對(duì)B、C、D三個(gè)部位派巡邏隊(duì)，即 ，這時(shí)有 同樣有 又 ，故計(jì)算得表4。,表4,最后考慮對(duì)A、B、C、D四個(gè)部位派巡邏隊(duì)，即 時(shí)，有 因 有 故計(jì)算得表5,由表5知，最優(yōu)策略是：A部位4支，B部位2支，C部位2支，D部位4支，總預(yù)期損失為97單位。,動(dòng)態(tài)規(guī)劃,動(dòng)態(tài)規(guī)劃問題實(shí)例 動(dòng)態(tài)規(guī)劃的基本概念與原理 動(dòng)態(tài)規(guī)劃應(yīng)用舉例,例 Wyndor Glass Company Problem,使用動(dòng)態(tài)規(guī)劃進(jìn)行求解,1,2,一、動(dòng)態(tài)規(guī)劃問題建模,這個(gè)問題需要對(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 ）,狀態(tài)變量 ：可用于第k階段生產(chǎn)的資源量（右端項(xiàng)）。即,狀態(tài)轉(zhuǎn)移方程：,階段指標(biāo)函數(shù) ：第 k 階段確定 時(shí)所產(chǎn)生的利潤即,最優(yōu)指標(biāo)函數(shù) ：第 k 階段狀態(tài)為 且采取最佳投資 策略，從第 k 個(gè)活動(dòng)以及以后的最大總利潤。,逆序法基本遞推方程：,二、動(dòng)態(tài)規(guī)劃問題求解,（1）k=2 時(shí),因?yàn)?故有,k=2 時(shí)決策表,（2）k=1 時(shí),因?yàn)槌鯐r(shí)狀態(tài)確定,且,k=2 時(shí)決策表,在可行區(qū)間 上,因?yàn)?和,都在x1=2時(shí)獲得最大值,k=1 時(shí)決策表,所以,k=1 時(shí)決策表,k=2 時(shí)決策表,背 包 問 題,一般的提法為：一旅行者攜帶背包去登山。已知他所能承受 的背包重量的極限為a (千克)，現(xiàn)有n種物品可供他選擇裝入 背包。第i種物品的單位重量為 (千克)，其價(jià)值（可以是表 明本物品對(duì)登山者的重要性指標(biāo)）是攜帶數(shù)量 的函數(shù) （i=1，2，n）.問旅行者應(yīng)如何選擇攜帶物品的件 數(shù)，以