第七章_動(dòng)態(tài)規(guī)劃

1、第七章第七章 動(dòng)動(dòng) 態(tài)態(tài) 規(guī)規(guī) 劃劃 (Dynamic programming)動(dòng)態(tài)規(guī)劃的基本概念、基本思想動(dòng)態(tài)規(guī)劃的基本概念、基本思想動(dòng)態(tài)規(guī)劃模型的建立和求解動(dòng)態(tài)規(guī)劃模型的建立和求解動(dòng)態(tài)規(guī)劃的應(yīng)用：動(dòng)態(tài)規(guī)劃的應(yīng)用：背包問題；生產(chǎn)背包問題；生產(chǎn)經(jīng)營問題；設(shè)備更新問題；復(fù)合系統(tǒng)經(jīng)營問題；設(shè)備更新問題；復(fù)合系統(tǒng)工作可靠性問題工作可靠性問題 第一節(jié)第一節(jié) 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃(Dynamic Programming)是用來解決是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。其特多階段決策過程最優(yōu)化的一種數(shù)量方法。其特點(diǎn)在于，它可以把一個(gè)點(diǎn)在于，它可以把一個(gè)n 維決策問題變換為幾個(gè)維決策問

2、題變換為幾個(gè)一維最優(yōu)化問題，從而一個(gè)一個(gè)地去解決。一維最優(yōu)化問題，從而一個(gè)一個(gè)地去解決。 需指出：動(dòng)態(tài)規(guī)劃是求解某類問題的一種需指出：動(dòng)態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算方法，是考察問題的一種途徑，而不是一種算法。必須對具體問題進(jìn)行具體分析，運(yùn)用動(dòng)態(tài)法。必須對具體問題進(jìn)行具體分析，運(yùn)用動(dòng)態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動(dòng)態(tài)規(guī)劃方法去求解。用動(dòng)態(tài)規(guī)劃方法去求解。一、多階段決策問題的典型例子：一、多階段決策問題的典型例子： 1 . 1 . 生產(chǎn)決策問題生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于：企業(yè)在生產(chǎn)過程中，由于需求

3、是隨時(shí)間變化的，因此企業(yè)為了獲得全年的最需求是隨時(shí)間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個(gè)生產(chǎn)過程中逐月或逐季度佳生產(chǎn)效益，就要在整個(gè)生產(chǎn)過程中逐月或逐季度地地根據(jù)庫存和需求決定生產(chǎn)計(jì)劃。根據(jù)庫存和需求決定生產(chǎn)計(jì)劃。 2. 2. 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題：某種機(jī)器可以在高低兩：某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。在高負(fù)荷下進(jìn)行生產(chǎn)時(shí)，種不同的負(fù)荷下進(jìn)行生產(chǎn)。在高負(fù)荷下進(jìn)行生產(chǎn)時(shí)，產(chǎn)品的年產(chǎn)量產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機(jī)器數(shù)量和投入生產(chǎn)的機(jī)器數(shù)量u1的關(guān)系為的關(guān)系為g=g(u1)12n狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)決策決策狀態(tài)狀態(tài)狀態(tài)狀態(tài)決策決策 這時(shí)，機(jī)器的年完好率為

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

5、最高。 相應(yīng)的機(jī)器年完好率相應(yīng)的機(jī)器年完好率b b, 0 , 0 b b11。 3. 3. 航天飛機(jī)飛行控制問題：由于航天飛機(jī)的航天飛機(jī)飛行控制問題：由于航天飛機(jī)的運(yùn)動(dòng)的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機(jī)運(yùn)動(dòng)的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機(jī)飛行在不同環(huán)境中的情況，不斷地決定航天飛機(jī)的飛行在不同環(huán)境中的情況，不斷地決定航天飛機(jī)的飛行方向和速度（狀態(tài)），使之能最省燃料和實(shí)現(xiàn)飛行方向和速度（狀態(tài)），使之能最省燃料和實(shí)現(xiàn)目的（如軟著落問題）。目的（如軟著落問題）。 不包含時(shí)間因素的靜態(tài)決策問題（本質(zhì)上是一不包含時(shí)間因素的靜態(tài)決策問題（本質(zhì)上是一次決策問題）也可以適當(dāng)?shù)匾腚A段的概念，作為次

6、決策問題）也可以適當(dāng)?shù)匾腚A段的概念，作為多階段的決策問題用動(dòng)態(tài)規(guī)劃方法來解決。多階段的決策問題用動(dòng)態(tài)規(guī)劃方法來解決。 4 4 . 線性規(guī)劃、非線性規(guī)劃等靜態(tài)的規(guī)劃問題也線性規(guī)劃、非線性規(guī)劃等靜態(tài)的規(guī)劃問題也可以通過適當(dāng)?shù)匾腚A段的概念，應(yīng)用動(dòng)態(tài)規(guī)劃方可以通過適當(dāng)?shù)匾腚A段的概念，應(yīng)用動(dòng)態(tài)規(guī)劃方法加以解決。法加以解決。 5 . 最短路問題最短路問題：給定一個(gè)交通網(wǎng)絡(luò)圖如下，其：給定一個(gè)交通網(wǎng)絡(luò)圖如下，其中兩點(diǎn)之間的數(shù)字表示距離（或花費(fèi)），試求從中兩點(diǎn)之間的數(shù)字表示距離（或花費(fèi)），試求從A點(diǎn)點(diǎn)到到G點(diǎn)的最短距離（總費(fèi)用最?。｜c(diǎn)的最短距離（總費(fèi)用最?。?。123456AB1B2C1C2C3C4D1

7、D2D3E1E2E3F1F2G531368763685338422213335256643二、解題思路二、解題思路三、應(yīng)用范圍三、應(yīng)用范圍1、動(dòng)態(tài)、動(dòng)態(tài)2、靜態(tài)、靜態(tài)四、缺點(diǎn)四、缺點(diǎn)1、建模后，沒有統(tǒng)一的方法、建模后，沒有統(tǒng)一的方法2、維數(shù)障礙、維數(shù)障礙 一、基本概念一、基本概念 1、階段：、階段： 把一個(gè)問題的過程，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的把一個(gè)問題的過程，恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段階段，以便于按一定的次序去求解。，以便于按一定的次序去求解。 描述階段的變量稱為描述階段的變量稱為階段變量階段變量,用用k表示表示。階段的劃分，。階段的劃分，一般是根據(jù)時(shí)間和空間的自然特征來進(jìn)行的，但要便于

8、一般是根據(jù)時(shí)間和空間的自然特征來進(jìn)行的，但要便于問題轉(zhuǎn)化為多階段決策。問題轉(zhuǎn)化為多階段決策。2、狀態(tài)：表示每個(gè)階段開始所處的、狀態(tài)：表示每個(gè)階段開始所處的自然狀況或客觀自然狀況或客觀條件條件。通常一個(gè)階段有若干個(gè)狀態(tài)，描述過程狀態(tài)的。通常一個(gè)階段有若干個(gè)狀態(tài)，描述過程狀態(tài)的變量稱為變量稱為狀態(tài)變量狀態(tài)變量,用用Sk表示表示。年、月、年、月、路段路段一個(gè)數(shù)、一個(gè)數(shù)、一組數(shù)、一組數(shù)、一個(gè)向一個(gè)向量量 狀態(tài)變量的取值有一定的允許集合或范圍，此集合狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為稱為狀態(tài)允許集合狀態(tài)允許集合。第二節(jié)第二節(jié) 動(dòng)態(tài)規(guī)劃的基本概念動(dòng)態(tài)規(guī)劃的基本概念 3、決策：表示當(dāng)過程處于某

9、一階段的某個(gè)狀態(tài)時(shí)，、決策：表示當(dāng)過程處于某一階段的某個(gè)狀態(tài)時(shí)，可以作出不同的決定，從而確定下一階段的狀態(tài)可以作出不同的決定，從而確定下一階段的狀態(tài)，這這種決定稱為種決定稱為決策決策。 描述決策的變量，稱為描述決策的變量，稱為決策變量決策變量,用用Uk(Sk )。決策變。決策變量是狀態(tài)變量的函數(shù)?？捎靡粋€(gè)數(shù)、一組數(shù)或一向量量是狀態(tài)變量的函數(shù)?？捎靡粋€(gè)數(shù)、一組數(shù)或一向量（多維情形）來描述。（多維情形）來描述。 在實(shí)際問題中決策變量的取值往往在某一范圍之內(nèi)，在實(shí)際問題中決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為此范圍稱為允許決策集合允許決策集合,用用Dk(Sk )表示表示。 4 4、狀態(tài)轉(zhuǎn)移方程

10、、狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程是確定過程由狀態(tài)轉(zhuǎn)移方程是確定過程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過程。如果第變過程。如果第k階段狀態(tài)階段狀態(tài)變量變量sk的值、該階段的決策的值、該階段的決策變量一經(jīng)確定，第變量一經(jīng)確定，第k+1階段階段狀態(tài)變量狀態(tài)變量sk+1的值也就確定。的值也就確定。),(),(),(221112211231112kkkkusususTsususTsusTs 圖示如下：圖示如下：12ks1u1s2u2s3skuksk+1 能用動(dòng)態(tài)規(guī)劃方法求解的多階段決策過程是一類能用動(dòng)態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即特殊的多階段決策過程，即具有無后

11、效性具有無后效性的多階段的多階段決策過程。決策過程。 如果狀態(tài)變量不能滿足無后效性的要求，應(yīng)適當(dāng)如果狀態(tài)變量不能滿足無后效性的要求，應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。地改變狀態(tài)的定義或規(guī)定方法。),(),(),(122231112kkkkusTsusTsusTs 動(dòng)態(tài)規(guī)劃中能動(dòng)態(tài)規(guī)劃中能處理的狀態(tài)轉(zhuǎn)移處理的狀態(tài)轉(zhuǎn)移方程的形式方程的形式。 狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)移方程如下移方程如下無后效性無后效性( (馬爾可夫性馬爾可夫性) ) 如果某階段狀態(tài)給定后，則在這個(gè)階段以后過程如果某階段狀態(tài)給定后，則在這個(gè)階段以后過程的發(fā)展不受這個(gè)階段以前各段

12、狀態(tài)的影響；的發(fā)展不受這個(gè)階段以前各段狀態(tài)的影響； 過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未過程的過去歷史只能通過當(dāng)前的狀態(tài)去影響它未來的發(fā)展；來的發(fā)展； 構(gòu)造動(dòng)態(tài)規(guī)劃模型時(shí)，要充分注意是否滿構(gòu)造動(dòng)態(tài)規(guī)劃模型時(shí)，要充分注意是否滿足無后效性的要求；足無后效性的要求；狀態(tài)變量要滿足無后效性的要求狀態(tài)變量要滿足無后效性的要求； 5 5、策略：是一個(gè)按順序排列的決策組成的集合。在、策略：是一個(gè)按順序排列的決策組成的集合。在實(shí)際問題中，可供選擇的策略有一定的范圍，稱為實(shí)際問題中，可供選擇的策略有一定的范圍，稱為允允許策略集合許策略集合。從允許策略集合中找出達(dá)到最優(yōu)效果的。從允許策略集合中找出達(dá)到最優(yōu)效

13、果的策略稱為策略稱為最優(yōu)策略最優(yōu)策略。全過程策略：全過程策略：U U1 1(S(S1 1), U), U2 2(S(S2 2), U), Un n(S(Sn n) )P P1n1n=U=Ui i(S(Si i), i=1,n), i=1,n子過程策略：子過程策略：U Uk k(S(Sk k), U), Uk+1k+1(S(Sk+1k+1), U), Un n(S(Sn n) )P Pknkn=U=Ui i(S(Si i), i=k,n), i=k,n6 6、階段指標(biāo)：、階段指標(biāo)：V Vk k(S(Sk k, U, Uk k),k),k階段，階段，S Sk k狀態(tài)下，作出狀態(tài)下，作出U Uk k

14、決決策帶來的效果。策帶來的效果。在不同的問題中，指標(biāo)的含義是不同的，它在不同的問題中，指標(biāo)的含義是不同的，它可能是距離、利潤、成本、產(chǎn)量或資源消耗等。可能是距離、利潤、成本、產(chǎn)量或資源消耗等。7 7、指標(biāo)函數(shù)：、指標(biāo)函數(shù)：V Vknkn(S(Sk k, P, Pknkn),k),k階段，階段，S Sk k狀態(tài)下，作出狀態(tài)下，作出P Pknkn子策略帶來的效果。子策略帶來的效果。動(dòng)態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分動(dòng)態(tài)規(guī)劃模型的指標(biāo)函數(shù)，應(yīng)具有可分離性，并滿足離性，并滿足遞推遞推關(guān)系。關(guān)系。 階段指標(biāo)與指標(biāo)函數(shù)的關(guān)系有兩種：階段指標(biāo)與指標(biāo)函數(shù)的關(guān)系有兩種：1）指標(biāo)函數(shù)是它所含有的各階段的階段指標(biāo)之

15、和。）指標(biāo)函數(shù)是它所含有的各階段的階段指標(biāo)之和。即即Vkn(Sk,Pkn）= Vj(Sj, Uj),j=k,n那么有那么有Vkn(Sk,Pkn）= Vk (Sk,Uk）+ Vk+1 n(Sk+1,Pk+1 n）2）指標(biāo)函數(shù)是它所含有的各階段的階段指標(biāo)之積。）指標(biāo)函數(shù)是它所含有的各階段的階段指標(biāo)之積。即即Vkn(Sk,Pkn）= Vj(Sj, Uj),j=k,n 那么有那么有Vkn(Sk,Pkn）= Vk (Sk,Uk） Vk+1 n(Sk+1,Pk+1 n）8、最優(yōu)指標(biāo)函數(shù)：指標(biāo)函數(shù)的最優(yōu)值，稱為、最優(yōu)指標(biāo)函數(shù)：指標(biāo)函數(shù)的最優(yōu)值，稱為最優(yōu)值最優(yōu)值函數(shù)函數(shù)。用。用fk(Sk)=optVkn(Sk

16、,Pkn)opt表示最優(yōu)化，常取表示最優(yōu)化，常取max或或min。 1、Bellman最優(yōu)性定理最優(yōu)性定理一個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)：即無論初始狀一個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)：即無論初始狀態(tài)及初始決策如何，對于先前決策所形成的狀態(tài)而言，態(tài)及初始決策如何，對于先前決策所形成的狀態(tài)而言，其以后所有的決策應(yīng)構(gòu)成最優(yōu)策略。其以后所有的決策應(yīng)構(gòu)成最優(yōu)策略。換句話說，最優(yōu)策略只能由最優(yōu)子策略構(gòu)成。換句話說，最優(yōu)策略只能由最優(yōu)子策略構(gòu)成。2、思想方法：在求解過程中，各階段的狀態(tài)和決策，、思想方法：在求解過程中，各階段的狀態(tài)和決策，對其后面的階段來說，只影響其初始狀態(tài)，而不影響對其后面的階段來說，只

17、影響其初始狀態(tài)，而不影響后面的最優(yōu)策略。后面的最優(yōu)策略。無后效性無后效性方法：方法：“順序編號，逆序求解順序編號，逆序求解”二、動(dòng)態(tài)規(guī)劃的基本思想和基本方程二、動(dòng)態(tài)規(guī)劃的基本思想和基本方程 3、基本方程、基本方程 根據(jù)最優(yōu)性定理，可以寫出動(dòng)態(tài)規(guī)劃遞推方程，根據(jù)最優(yōu)性定理，可以寫出動(dòng)態(tài)規(guī)劃遞推方程，即基本方程：即基本方程： Vkn(Sk,Pkn）= Vj(Sj, Uj),j=k,n時(shí)，時(shí)， fk(Sk)=opt Vk (Sk,Uk）+ fk+1(Sk+1) fn+1(Sn+1)=0Vkn(Sk,Pkn）= Vj(Sj, Uj),j=k,n時(shí)，時(shí)， fk(Sk)=opt Vk (Sk,Uk） fk

18、+1(Sk+1) fn+1(Sn+1)=1其中的其中的fn+1(Sn+1)為邊界條件。為邊界條件。 三、建立動(dòng)態(tài)規(guī)劃模型的步驟三、建立動(dòng)態(tài)規(guī)劃模型的步驟 1 1、劃分階段、劃分階段劃分階段是運(yùn)用動(dòng)態(tài)規(guī)劃求解多階段決策問題的第一劃分階段是運(yùn)用動(dòng)態(tài)規(guī)劃求解多階段決策問題的第一步，在確定多階段特性后，按時(shí)間或空間先后順序，步，在確定多階段特性后，按時(shí)間或空間先后順序，將過程劃分為若干相互聯(lián)系的階段。對于靜態(tài)問題要將過程劃分為若干相互聯(lián)系的階段。對于靜態(tài)問題要人為地賦予人為地賦予“時(shí)間時(shí)間”概念，以便劃分階段。概念，以便劃分階段。 2 2、正確選擇狀態(tài)變量、正確選擇狀態(tài)變量選擇變量既要能確切描述過程演

19、變又要滿足無后效性，選擇變量既要能確切描述過程演變又要滿足無后效性，而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)變量的選擇是從過程演變的特點(diǎn)中尋找。變量的選擇是從過程演變的特點(diǎn)中尋找。 3 3、確定決策變量及允許決策集合、確定決策變量及允許決策集合通常選擇所求解問題的關(guān)鍵變量作為決策變量，同時(shí)通常選擇所求解問題的關(guān)鍵變量作為決策變量，同時(shí)要給出決策變量的取值范圍，即確定允許決策集合。要給出決策變量的取值范圍，即確定允許決策集合。 4 4、確定狀態(tài)轉(zhuǎn)移方程、確定狀態(tài)轉(zhuǎn)移方程根據(jù)根據(jù)k 階段狀態(tài)變量和決策變量，寫出階段狀態(tài)變量和決策變量，寫出k+1階

20、段狀態(tài)變階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系。量，狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系。 5 5、確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)、確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃基本方程劃基本方程 階段指標(biāo)函數(shù)是指第階段指標(biāo)函數(shù)是指第k 階段的收益，最優(yōu)指標(biāo)函數(shù)階段的收益，最優(yōu)指標(biāo)函數(shù)是指從第是指從第k 階段狀態(tài)出發(fā)到第階段狀態(tài)出發(fā)到第n 階段末所獲得收益的最階段末所獲得收益的最優(yōu)值，最后寫出動(dòng)態(tài)規(guī)劃基本方程。優(yōu)值，最后寫出動(dòng)態(tài)規(guī)劃基本方程。 以上五步是建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。由于以上五步是建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。由于動(dòng)態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動(dòng)態(tài)規(guī)劃模型沒有統(tǒng)動(dòng)態(tài)

21、規(guī)劃模型與線性規(guī)劃模型不同，動(dòng)態(tài)規(guī)劃模型沒有統(tǒng)一的模式，建模時(shí)必須根據(jù)具體問題具體分析，只有通過一的模式，建模時(shí)必須根據(jù)具體問題具體分析，只有通過不斷實(shí)踐總結(jié)，才能較好掌握建模方法與技巧。不斷實(shí)踐總結(jié)，才能較好掌握建模方法與技巧。 例一、從例一、從A 地到地到D 地要鋪設(shè)一條煤氣管道地要鋪設(shè)一條煤氣管道,其中需經(jīng)過其中需經(jīng)過兩級中間站，兩點(diǎn)之間的連線上的數(shù)字表示距離，如兩級中間站，兩點(diǎn)之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短？圖所示。問應(yīng)該選擇什么路線，使總距離最短？ AB1B2C1C2C3D24333321114 第三節(jié)第三節(jié) 動(dòng)態(tài)規(guī)劃應(yīng)用舉例動(dòng)態(tài)規(guī)劃應(yīng)用舉例一

22、、最短路徑問題一、最短路徑問題 解：整個(gè)計(jì)算過程分三個(gè)階段，從最后一個(gè)階段開始。解：整個(gè)計(jì)算過程分三個(gè)階段，從最后一個(gè)階段開始。 第三階段（第三階段（C D）：）： C 有三條路線到終點(diǎn)有三條路線到終點(diǎn)D 。 AB1B2C1C2C3D24333321114DC1C2C3顯然有顯然有 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 d( B1,C3 ) + f3 (C3 ) 1+4 4 = min 6 = 4 5第

23、二階段（第二階段（B C）：）： B 到到C 有六條路線。有六條路線。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為最短路線為B1C1 D) 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 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為最短路線為B2C1 D)第一階段（第一階段（ A B ）：）： A 到到B 有二條路線。有二條路線。 f3(A)1

24、 = d(A, B1 ) f2 ( B1 ) 246 f3 (A)2 = d(A, B2 ) f2 ( B2 ) 437 f1 (A) = min = min6,7=6d(A, B1 ) f2 ( B1 )d(A, B2 ) f2 ( B2 )(最短路線為最短路線為AB1C1 D)AB1B2C1C2C3D24333321114DC1C2C3B1B2AAB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路線為最短路線為 AB1C1 D 路長為路長為 6表上作業(yè)法表上作業(yè)法K=3C1C2C3DDD134DDD000DDDK=2B1C13C1階段階段k狀態(tài)狀態(tài)Sk決策決策Uk階

25、段指標(biāo)階段指標(biāo)Vk狀態(tài)轉(zhuǎn)狀態(tài)轉(zhuǎn)移移Sk+1fk+1(Sk+1) fk(Sk) 最優(yōu)策略最優(yōu)策略Uk*134134C2C331C2C3465C1B2C1C2312C1C2C313436K=1AB2B124B1B2C14367B15C3求從求從A到到E的最短路徑的最短路徑路線為路線為AB2C1 D1 E ，最短路徑為最短路徑為1919AB2B1B3C1C3D1D2EC25214112610104312111396581052練習(xí)：練習(xí)：1 現(xiàn)有數(shù)量為現(xiàn)有數(shù)量為a的資源，用于生產(chǎn)的資源，用于生產(chǎn)n種產(chǎn)品，第種產(chǎn)品，第i種產(chǎn)品種產(chǎn)品分配分配xi，帶來gi(xi)收益，問如何分配使總收益最大？收益，問如

26、何分配使總收益最大？ nixaxxgZiniiniii.2.1 0)(max11據(jù)此，有下式：據(jù)此，有下式：二、資源分配問題二、資源分配問題1、一維資源分配、一維資源分配 求解：求解：階段：階段： k=1，2，,n,對應(yīng)第對應(yīng)第k種產(chǎn)品分配資源的過程種產(chǎn)品分配資源的過程狀態(tài)狀態(tài)Sk:表示可供分配第表示可供分配第k種到第種到第n種資源的總量種資源的總量決策變量決策變量xk:表示分配給第表示分配給第k種產(chǎn)品的資源量種產(chǎn)品的資源量狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程: Sk+1= Sk xk階段指標(biāo)函數(shù)階段指標(biāo)函數(shù):V k= gk(xk) 基本方程基本方程: fk(Sk)=maxgk(xk) +fk+1(Sk+

27、1)(k=n,n-1,1) fn+1(Sn+1)=0 例例:兩臺設(shè)備分配給三個(gè)工廠兩臺設(shè)備分配給三個(gè)工廠,這三個(gè)工廠使用這幾臺設(shè)備所產(chǎn)這三個(gè)工廠使用這幾臺設(shè)備所產(chǎn)生的效益分別為如下表生的效益分別為如下表,問如何分配使效益最大問如何分配使效益最大? 設(shè)備設(shè)備工廠工廠012A037B0510C046階段：階段： k=1，2，3,對應(yīng)第對應(yīng)第k個(gè)工廠分配設(shè)備的過程個(gè)工廠分配設(shè)備的過程狀態(tài)狀態(tài)Sk:表示可供分配第表示可供分配第k個(gè)到第個(gè)到第3個(gè)工廠的設(shè)備的臺數(shù)個(gè)工廠的設(shè)備的臺數(shù)決策變量決策變量xk:表示分配給第表示分配給第k個(gè)工廠的設(shè)備數(shù)個(gè)工廠的設(shè)備數(shù)狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程: Sk+1= Sk xk

28、階段指標(biāo)函數(shù)階段指標(biāo)函數(shù):V k= gk(xk) 基本方程基本方程: fk(Sk)=maxgk(xk) +fk+1(Sk+1) (k=3,2,1) f4(S4)=0階段階段k狀態(tài)狀態(tài)Sk決策決策Uk階段指階段指標(biāo)標(biāo)Vk狀態(tài)轉(zhuǎn)狀態(tài)轉(zhuǎn)移移Sk+1fk+1(Sk+1)fk(Sk)最優(yōu)策最優(yōu)策略略Uk*K=3021012046000000046012K=200000001010144500512012051021640691002K=12012037210105010870因此因此z*=10,X*=(0,2,0) 設(shè)備設(shè)備工廠工廠012A037B0510C046*練習(xí)：某公司打算在練習(xí)：某公司打算在3

29、個(gè)不同的地區(qū)設(shè)置個(gè)不同的地區(qū)設(shè)置4個(gè)銷售點(diǎn)，個(gè)銷售點(diǎn)，根據(jù)市場部門估計(jì)，在不同地區(qū)設(shè)置不同數(shù)量的銷根據(jù)市場部門估計(jì)，在不同地區(qū)設(shè)置不同數(shù)量的銷售點(diǎn)每月可得到的利潤如表所示。試問在各地區(qū)如售點(diǎn)每月可得到的利潤如表所示。試問在各地區(qū)如何設(shè)置銷售點(diǎn)可使每月總利潤最大。何設(shè)置銷售點(diǎn)可使每月總利潤最大。 地地區(qū)區(qū)銷售點(diǎn)銷售點(diǎn)01234123000161210251714302116322217 x1=2，x2=1，x3=1，f3(4)=47 有一個(gè)徒步旅行者，其可攜帶物品重量的限度為有一個(gè)徒步旅行者，其可攜帶物品重量的限度為a 公公斤，設(shè)有斤，設(shè)有n 種物品可供他選擇裝入包中。已知每種物品種物品可供他選

30、擇裝入包中。已知每種物品的重量及使用價(jià)值（作用），問此人應(yīng)如何選擇攜帶的重量及使用價(jià)值（作用），問此人應(yīng)如何選擇攜帶的物品（各幾件），使所起作用（使用價(jià)值）最大？的物品（各幾件），使所起作用（使用價(jià)值）最大？物品物品 1 2 j n重量（公斤重量（公斤/ /件）件） a1 a2 aj an每件使用價(jià)值每件使用價(jià)值 c1 c2 cj cn 這就是背包問題。類似的還有工廠里的下料問題、這就是背包問題。類似的還有工廠里的下料問題、運(yùn)輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題運(yùn)輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題等。等。三、背包問題三、背包問題設(shè)設(shè)xj 為第為第j 種物品的裝件數(shù)（非負(fù)整數(shù)）

31、則問題的數(shù)學(xué)種物品的裝件數(shù)（非負(fù)整數(shù)）則問題的數(shù)學(xué)模型如下：模型如下： ). 2 . 1(0max1njxaxaxcZjnijjjnjjj 且且為為整整數(shù)數(shù)例題：求下面背包問題的最優(yōu)解例題：求下面背包問題的最優(yōu)解 且且為為整整數(shù)數(shù)0,55231258max321321321xxxxxxxxxZ物品物品 1 2 3重量（公斤）重量（公斤） 3 2 5使用價(jià)值使用價(jià)值 8 5 12用動(dòng)態(tài)規(guī)劃方法求解階段：階段： k=1，2，3,對應(yīng)第對應(yīng)第k種物品的選擇過程種物品的選擇過程狀態(tài)狀態(tài)Sk:表示可供分配第表示可供分配第k種到第種到第3種物品的重量種物品的重量決策變量決策變量xk:表示分配給第表示分配給

32、第k種物品的件數(shù)種物品的件數(shù)狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程: S1 =5,S2= S1 2x2, S3= S2 2x3階段指標(biāo)函數(shù)階段指標(biāo)函數(shù):V 1= 8x1, V 2= 5x2 ,V 3= 12x3基本方程基本方程: fk(Sk)=maxVk +fk+1(Sk+1)(k=3,2,1) f4(S4)=0求解見板書求解見板書 練習(xí)：某廠生產(chǎn)三種產(chǎn)品，各種產(chǎn)品重量與利潤練習(xí)：某廠生產(chǎn)三種產(chǎn)品，各種產(chǎn)品重量與利潤的關(guān)系如表所示?，F(xiàn)將此三種產(chǎn)品運(yùn)往市場出售，的關(guān)系如表所示?，F(xiàn)將此三種產(chǎn)品運(yùn)往市場出售，運(yùn)輸能力總重量不超過運(yùn)輸能力總重量不超過 6 噸，問如何安排運(yùn)輸，使噸，問如何安排運(yùn)輸，使總利潤最大？總利

33、潤最大？種類種類 1 2 3重量（噸重量（噸/ /公斤）公斤） 2 3 4 單件利潤（元）單件利潤（元） 80 130 180最優(yōu)方案：最優(yōu)方案：X1 = =（0.2.00.2.0）X2 = =（1.0.11.0.1）Z=260=260四、復(fù)合系統(tǒng)工作可靠性問題四、復(fù)合系統(tǒng)工作可靠性問題 某種機(jī)器的工作系統(tǒng)由某種機(jī)器的工作系統(tǒng)由n個(gè)部件串聯(lián)組成，只要有一個(gè)部個(gè)部件串聯(lián)組成，只要有一個(gè)部件失靈，整個(gè)系統(tǒng)就不能正常工作。為了提高系統(tǒng)工作的件失靈，整個(gè)系統(tǒng)就不能正常工作。為了提高系統(tǒng)工作的可靠性，在每個(gè)部件上均裝有主要元件的備用件，并設(shè)計(jì)可靠性，在每個(gè)部件上均裝有主要元件的備用件，并設(shè)計(jì)了備用元件自

34、動(dòng)投入裝備，顯然，備用元件越多，整個(gè)系了備用元件自動(dòng)投入裝備，顯然，備用元件越多，整個(gè)系統(tǒng)工作的可靠性就越大，但備用元件增多也會(huì)導(dǎo)致系統(tǒng)的統(tǒng)工作的可靠性就越大，但備用元件增多也會(huì)導(dǎo)致系統(tǒng)的成本、重量體積相應(yīng)增大，工作精度降低，因此，在考慮成本、重量體積相應(yīng)增大，工作精度降低，因此，在考慮上述限制條件下，如何選擇各部件的備用元件數(shù)，使整個(gè)上述限制條件下，如何選擇各部件的備用元件數(shù)，使整個(gè)系統(tǒng)的工作可靠性最大？系統(tǒng)的工作可靠性最大？ 建模：設(shè)部件建模：設(shè)部件i裝有裝有xi個(gè)備用元件時(shí)，正常工作的概率為個(gè)備用元件時(shí)，正常工作的概率為Pi(xi),那么整個(gè)系統(tǒng)正常工作的概率那么整個(gè)系統(tǒng)正常工作的概率Z

35、= Pi(xi)（i=1，,n）,設(shè)部件設(shè)部件i的單位重量級的單位重量級wi,那么總重量不超那么總重量不超過過w的情況下的情況下,如何配備備用件如何配備備用件,使使Z最大最大?且為整數(shù),0)(max11iniiiiniixxxPz用動(dòng)態(tài)規(guī)劃方法求解階段：階段： k=1，2，n,對應(yīng)給第對應(yīng)給第k個(gè)部件分配配件的過程個(gè)部件分配配件的過程狀態(tài)狀態(tài)Sk:表示可供分配第表示可供分配第k個(gè)到第個(gè)到第n個(gè)部件的總重量個(gè)部件的總重量決策變量決策變量xk:表示分配給第表示分配給第k個(gè)部件配備的備用件數(shù)個(gè)部件配備的備用件數(shù)狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程: Sk+1 =Skwkxk階段指標(biāo)函數(shù)階段指標(biāo)函數(shù):V k=Pk

36、(xk)基本方程基本方程: fk(Sk)=maxVk fk+1(Sk+1)(k=n,2,1) fk+1(Sk+1)=1例例:三個(gè)科研小組分別對某一項(xiàng)目的一個(gè)部件研究三個(gè)科研小組分別對某一項(xiàng)目的一個(gè)部件研究,成功率分成功率分別為別為0.6,0.4,0.2,為提高成功率為提高成功率,可以給各組增加人員可以給各組增加人員,現(xiàn)有現(xiàn)有2個(gè)個(gè)人可以加入到研究工作中人可以加入到研究工作中,問如何分配人手問如何分配人手,使項(xiàng)目總成功率使項(xiàng)目總成功率最大最大?成功率成功率 一 二 三0 0 0.6 0.4 0.21 1 0.8 0.6 0.52 2 0.85 0.8 0.7階段：階段： k=1，2，3,對應(yīng)給第

37、對應(yīng)給第k個(gè)小組分配人手的過程個(gè)小組分配人手的過程狀態(tài)狀態(tài)Sk:表示可供分配第表示可供分配第k個(gè)到第個(gè)到第3個(gè)小組的總?cè)藬?shù)個(gè)小組的總?cè)藬?shù)決策變量決策變量xk:表示分配給第表示分配給第k個(gè)小組的人數(shù)個(gè)小組的人數(shù)狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程: Sk+1 =Skxk階段指標(biāo)函數(shù)階段指標(biāo)函數(shù):V k=Pk(xk)基本方程基本方程: fk(Sk)=maxVk fk+1(Sk+1)(k=3,2,1) f4(S4)=1階段階段k狀態(tài)狀態(tài)Sk決策決策Uk階段指階段指標(biāo)標(biāo)Vk狀態(tài)轉(zhuǎn)狀態(tài)轉(zhuǎn)移移Sk+1fk+1(Sk+1)fk(Sk)最優(yōu)策最優(yōu)策略略Uk*K=30210120.20.50.70001110.20.50.7012K=2000.400.20.0801010.410.50.20.600.20.12020120.40.60.8210.70.50.20.280.300.1601K=120120.60.80.852100.30.20.080.180.160.0680因此因此z*=0.18,X*=(0,1,1) 小組小組人手人手一一二二三三00.60.40.210.80.60.520.850.80.7*例例:分割問題分割問題階段：階段： k