1、1數學模型電子教案數學模型電子教案2第第7章章 動動 態態 規規 劃劃 (Dynamic programming)動態規劃的基本思想動態規劃的基本思想最短路徑問題最短路徑問題投資分配問題投資分配問題背包問題背包問題3 動態規劃是用來解決多階段決策過程最優動態規劃是用來解決多階段決策過程最優化的一種數量方法。其特點在于，它可以把一化的一種數量方法。其特點在于，它可以把一個個n 維決策問題變換為幾個一維最優化問題，從維決策問題變換為幾個一維最優化問題，從而一個一個地去解決。而一個一個地去解決。 需指出：動態規劃是求解某類問題的一種需指出：動態規劃是求解某類問題的一種方法，是考察問題的一種途徑，而不

2、是一種算方法，是考察問題的一種途徑，而不是一種算法。必須對具體問題進行具體分析，運用動態法。必須對具體問題進行具體分析，運用動態規劃的原理和方法，建立相應的模型，然后再規劃的原理和方法，建立相應的模型，然后再用動態規劃方法去求解。用動態規劃方法去求解。4即在系統發展的不同時刻（或階段）根據系統即在系統發展的不同時刻（或階段）根據系統所處的狀態，不斷地做出決策；所處的狀態，不斷地做出決策；每個階段都要進行每個階段都要進行決策決策, ,目的是使整個過程的決策目的是使整個過程的決策 達到最優效果。達到最優效果。動態決策問題的特點：動態決策問題的特點：系統所處的狀態和時刻是進行決策的重要因素；系統所處

3、的狀態和時刻是進行決策的重要因素；找到不同時刻的最優決策以及整個過程的最優策略。找到不同時刻的最優決策以及整個過程的最優策略。多階段決策問題：多階段決策問題：是動態決策問題的一種特殊形式；是動態決策問題的一種特殊形式；在多階段決策過程中在多階段決策過程中, ,系統的動態過程可以按照時間系統的動態過程可以按照時間進程分為進程分為狀態狀態相互相互聯系聯系而又相互而又相互區別區別的各個的各個階段階段；5多階段決策問題的典型例子：多階段決策問題的典型例子： 1 . 1 . 生產決策問題生產決策問題：企業在生產過程中，由于：企業在生產過程中，由于需求是隨時間變化的，因此企業為了獲得全年的最需求是隨時間變

4、化的，因此企業為了獲得全年的最佳生產效益，就要在整個生產過程中逐月或逐季度佳生產效益，就要在整個生產過程中逐月或逐季度地地根據庫存和需求決定生產計劃。根據庫存和需求決定生產計劃。 2. 2. 機器負荷分配問題機器負荷分配問題：某種機器可以在高低兩：某種機器可以在高低兩種不同的負荷下進行生產。在高負荷下進行生產時，種不同的負荷下進行生產。在高負荷下進行生產時，產品的年產量產品的年產量g和投入生產的機器數量和投入生產的機器數量u1的關系為的關系為g=g(u1)12n狀態狀態決策決策狀態狀態決策決策狀態狀態狀態狀態決策決策6 這時，機器的年完好率為這時，機器的年完好率為a，即如果年初完好機，即如果年

5、初完好機器的數量為器的數量為u，到年終完好的機器就為，到年終完好的機器就為au, 0a1。 在低負荷下生產時，產品的年產量在低負荷下生產時，產品的年產量h和投入生產和投入生產的機器數量的機器數量u2的關系為的關系為 h=h(u2) 假定開始生產時完好的機器數量為假定開始生產時完好的機器數量為s s1 1。要求制。要求制定一個五年計劃，在定一個五年計劃，在每年開始時，決定如何重新每年開始時，決定如何重新分配分配完好的完好的機器在兩種不同的負荷下生產的數量機器在兩種不同的負荷下生產的數量，使在五年內產品的總產量達到最高。使在五年內產品的總產量達到最高。 相應的機器年完好率相應的機器年完好率b b,

6、 0 , 0 b b11。 7 3. 3. 航天飛機飛行控制問題：由于航天飛機的航天飛機飛行控制問題：由于航天飛機的運動的環境是不斷變化的，因此就要根據航天飛機運動的環境是不斷變化的，因此就要根據航天飛機飛行在不同環境中的情況，不斷地決定航天飛機的飛行在不同環境中的情況，不斷地決定航天飛機的飛行方向和速度（狀態），使之能最省燃料和實現飛行方向和速度（狀態），使之能最省燃料和實現目的（如軟著落問題）。目的（如軟著落問題）。 不包含時間因素的靜態決策問題（本質上是一不包含時間因素的靜態決策問題（本質上是一次決策問題）也可以適當地引入階段的概念，作為次決策問題）也可以適當地引入階段的概念，作為多階段

7、的決策問題用動態規劃方法來解決。多階段的決策問題用動態規劃方法來解決。 4 4 . 線性規劃、非線性規劃等靜態的規劃問題也線性規劃、非線性規劃等靜態的規劃問題也可以通過適當地引入階段的概念，應用動態規劃方可以通過適當地引入階段的概念，應用動態規劃方法加以解決。法加以解決。8 5 . 最短路問題最短路問題：給定一個交通網絡圖如下，其：給定一個交通網絡圖如下，其中兩點之間的數字表示距離（或花費），試求從中兩點之間的數字表示距離（或花費），試求從A點點到到G點的最短距離（總費用最?。｜c的最短距離（總費用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876

8、36853384222133352566439 （一）、基本概念（一）、基本概念 1、階段：、階段： 把一個問題的過程，恰當地分為若干個相互聯系的把一個問題的過程，恰當地分為若干個相互聯系的階段階段，以便于按一定的次序去求解。，以便于按一定的次序去求解。 描述階段的變量稱為描述階段的變量稱為階段變量階段變量。階段的劃分，一般。階段的劃分，一般是根據時間和空間的自然特征來進行的，但要便于問題是根據時間和空間的自然特征來進行的，但要便于問題轉化為多階段決策。轉化為多階段決策。2、狀態：表示每個階段開始所處的、狀態：表示每個階段開始所處的自然狀況或客觀自然狀況或客觀條件條件。通常一個階段有若干個狀態

9、，描述過程狀態的。通常一個階段有若干個狀態，描述過程狀態的變量稱為變量稱為狀態變量狀態變量。年、月、年、月、路段路段一個數、一個數、一組數、一組數、一個向一個向量量 狀態變量的取值有一定的允許集合或范圍，此集合狀態變量的取值有一定的允許集合或范圍，此集合稱為稱為狀態允許集合狀態允許集合。一、動態規劃的基本思想一、動態規劃的基本思想10 3、決策：表示當過程處于某一階段的某個狀態時，、決策：表示當過程處于某一階段的某個狀態時，可以作出不同的決定，從而確定下一階段的狀態可以作出不同的決定，從而確定下一階段的狀態，這這種決定稱為種決定稱為決策決策。 描述決策的變量，稱為描述決策的變量，稱為決策變量決

10、策變量。決策變量是狀態。決策變量是狀態變量的函數。可用一個數、一組數或一向量（多維情變量的函數?？捎靡粋€數、一組數或一向量（多維情形）來描述。形）來描述。 在實際問題中決策變量的取值往往在某一范圍之內，在實際問題中決策變量的取值往往在某一范圍之內，此范圍稱為此范圍稱為允許決策集合允許決策集合。 系統在某一階段的狀態轉移不但與系統的當前的狀態系統在某一階段的狀態轉移不但與系統的當前的狀態和決策有關，而且還與系統過去的歷史狀態和決策有和決策有關，而且還與系統過去的歷史狀態和決策有關。關。 4、多階段決策過程多階段決策過程 可以在各個階段進行決策，去控制過程發展的多段過可以在各個階段進行決策，去控制

11、過程發展的多段過程；程； 其發展是通過一系列的狀態轉移來實現的；其發展是通過一系列的狀態轉移來實現的；11),(),(),(221112211231112kkkkusususTsususTsusTs 圖示如下：圖示如下：狀態轉移方程是確定狀態轉移方程是確定過程由一個狀態到另過程由一個狀態到另一個狀態的演變過程。一個狀態的演變過程。如果第如果第k階段狀態變量階段狀態變量sk的值、該階段的決策的值、該階段的決策變量一經確定，第變量一經確定，第k+1階段狀態變量階段狀態變量sk+1的值的值也就確定。也就確定。其狀態轉移方程如下（一般形式）其狀態轉移方程如下（一般形式）12ks1u1s2u2s3sku

12、ksk+1 能用動態規劃方法求解的多階段決策過程是一類能用動態規劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即特殊的多階段決策過程，即具有無后效性具有無后效性的多階段的多階段決策過程。決策過程。12 如果狀態變量不能滿足無后效性的要求，應如果狀態變量不能滿足無后效性的要求，應適當地改變狀態的定義或規定方法。適當地改變狀態的定義或規定方法。),(),(),(122231112kkkkusTsusTsusTs 動態規劃中能動態規劃中能處理的狀態轉移處理的狀態轉移方程的形式方程的形式。 狀態具有無后效性的多階段決策過程的狀狀態具有無后效性的多階段決策過程的狀態轉移方程如下態轉移方程如下無后

13、效性無后效性( (馬爾可夫性馬爾可夫性) ) 如果某階段狀態給定后，則在這個階段以后如果某階段狀態給定后，則在這個階段以后過程的發展不受這個階段以前各段狀態的影響；過程的發展不受這個階段以前各段狀態的影響； 過程的過去歷史只能通過當前的狀態去影響過程的過去歷史只能通過當前的狀態去影響它未來的發展；它未來的發展； 構造動態規劃模型時，要充分注意構造動態規劃模型時，要充分注意是否滿足無后效性的要求；是否滿足無后效性的要求；狀態變量要滿足無后效性的要求狀態變量要滿足無后效性的要求；13 5 5、策略：是一個按順序排列的決策組成的集合。在、策略：是一個按順序排列的決策組成的集合。在實際問題中，可供選擇

14、的策略有一定的范圍，稱為實際問題中，可供選擇的策略有一定的范圍，稱為允允許策略集合許策略集合。從允許策略集合中找出達到最優效果的。從允許策略集合中找出達到最優效果的策略稱為策略稱為最優策略最優策略。 6 6、狀態轉移方程：是確定過程由一個狀態到另一、狀態轉移方程：是確定過程由一個狀態到另一個狀態的演變過程，描述了狀態轉移規律。個狀態的演變過程，描述了狀態轉移規律。 7 7、指標函數和最優值函數：用來衡量所實現過程優、指標函數和最優值函數：用來衡量所實現過程優劣的一種數量指標，為劣的一種數量指標，為指標函數指標函數。指標函數的最優值，。指標函數的最優值，稱為稱為最優值函數最優值函數。在不同的問題

15、中，指標函數的含義。在不同的問題中，指標函數的含義是不同的，它可能是距離、利潤、成本、產量或資源是不同的，它可能是距離、利潤、成本、產量或資源消耗等。消耗等。 動態規劃模型的指標函數，應具有可分離性，并滿動態規劃模型的指標函數，應具有可分離性，并滿足足遞推遞推關系關系。14小結小結: :),()(1,susVoptsfnkknkkkuunk),(,111,1nkknkkkksusVus方程方程 : :狀態轉移方程狀態轉移方程),(1kkkkusTs概念概念 : : 階段變量階段變量k k狀態變量狀態變量s sk k決策變量決策變量u uk k; ;指標指標: : ),(111,nkkkknkn

16、ksususVV動態規劃本質上是多階段決策過程動態規劃本質上是多階段決策過程; ; 效益效益指標函數形式指標函數形式: : 和、和、積積無后效性無后效性),(111,nkkkknksususV可遞推可遞推15,*2*1nuuu,*2*1nsss解多階段決策過程問題，求出解多階段決策過程問題，求出 最優策略最優策略，即最優，即最優決策序列決策序列 susvoptsfnkknkkkuunk1, f1(s1) 最優軌線最優軌線，即執行最優策略時的即執行最優策略時的狀態序列狀態序列 最優目標函數值最優目標函數值),(*1*1*,1*,1nnnnususVV從從 k 到終點最優策略到終點最優策略子策略的

17、最優目標函數值子策略的最優目標函數值16 1、動態規劃方法的關鍵在于正確地寫出基本的遞推、動態規劃方法的關鍵在于正確地寫出基本的遞推關系式和恰當的邊界條件（簡稱基本方程）。要做到關系式和恰當的邊界條件（簡稱基本方程）。要做到這一點，就必須將問題的過程分成幾個相互聯系的階這一點，就必須將問題的過程分成幾個相互聯系的階段，恰當的選取狀態變量和決策變量及定義最優值函段，恰當的選取狀態變量和決策變量及定義最優值函數，從而把一個大問題轉化成一組同類型的子問題，數，從而把一個大問題轉化成一組同類型的子問題，然后逐個求解。即從邊界條件開始，逐段遞推尋優，然后逐個求解。即從邊界條件開始，逐段遞推尋優，在每一個

18、子問題的求解中，均利用了它前面的子問題在每一個子問題的求解中，均利用了它前面的子問題的最優化結果，依次進行，最后一個子問題所得的最的最優化結果，依次進行，最后一個子問題所得的最優解，就是整個問題的最優解。優解，就是整個問題的最優解。（二）、動態規劃的基本思想（二）、動態規劃的基本思想17 2、在多階段決策過程中，動態規劃方法是既把當前、在多階段決策過程中，動態規劃方法是既把當前一段和未來一段分開，又把當前效益和未來效益結合一段和未來一段分開，又把當前效益和未來效益結合起來考慮的一種最優化方法。因此，每段決策的選取起來考慮的一種最優化方法。因此，每段決策的選取是從全局來考慮的，與該段的最優選擇答

19、案一般是不是從全局來考慮的，與該段的最優選擇答案一般是不同的同的. 最優化原理：作為整個過程的最優策略具有這樣的最優化原理：作為整個過程的最優策略具有這樣的性質：無論過去的狀態和決策如何，相對于前面的決性質：無論過去的狀態和決策如何，相對于前面的決策所形成的狀態而言，余下的決策序列必然構成最優策所形成的狀態而言，余下的決策序列必然構成最優子策略。子策略?！币簿褪钦f，一個最優策略的子策略也是最也就是說，一個最優策略的子策略也是最優的。優的。 3、在求整個問題的最優策略時，由于初始狀態是、在求整個問題的最優策略時，由于初始狀態是已知的，而每段的決策都是該段狀態的函數，故最優已知的，而每段的決策都是

20、該段狀態的函數，故最優策略所經過的各段狀態便可逐段變換得到，從而確定策略所經過的各段狀態便可逐段變換得到，從而確定了最優路線。了最優路線。18（三）、建立動態規劃模型的步驟（三）、建立動態規劃模型的步驟 1 1、劃分階段、劃分階段劃分階段是運用動態規劃求解多階段決策問題的第一劃分階段是運用動態規劃求解多階段決策問題的第一步，在確定多階段特性后，按時間或空間先后順序，步，在確定多階段特性后，按時間或空間先后順序，將過程劃分為若干相互聯系的階段。對于靜態問題要將過程劃分為若干相互聯系的階段。對于靜態問題要人為地賦予人為地賦予“時間時間”概念，以便劃分階段。概念，以便劃分階段。 2 2、正確選擇狀態

21、變量、正確選擇狀態變量選擇變量既要能確切描述過程演變又要滿足無后效性，選擇變量既要能確切描述過程演變又要滿足無后效性，而且各階段狀態變量的取值能夠確定。一般地，狀態而且各階段狀態變量的取值能夠確定。一般地，狀態變量的選擇是從過程演變的特點中尋找。變量的選擇是從過程演變的特點中尋找。 3 3、確定決策變量及允許決策集合、確定決策變量及允許決策集合通常選擇所求解問題的關鍵變量作為決策變量，同時通常選擇所求解問題的關鍵變量作為決策變量，同時要給出決策變量的取值范圍，即確定允許決策集合。要給出決策變量的取值范圍，即確定允許決策集合。19 4 4、確定狀態轉移方程、確定狀態轉移方程根據根據k 階段狀態變

22、量和決策變量，寫出階段狀態變量和決策變量，寫出k+1階段狀態變階段狀態變量，狀態轉移方程應當具有遞推關系。量，狀態轉移方程應當具有遞推關系。 5 5、確定階段指標函數和最優指標函數，建立動態規、確定階段指標函數和最優指標函數，建立動態規劃基本方程劃基本方程 階段指標函數是指第階段指標函數是指第k 階段的收益，最優指標函數階段的收益，最優指標函數是指從第是指從第k 階段狀態出發到第階段狀態出發到第n 階段末所獲得收益的最階段末所獲得收益的最優值，最后寫出動態規劃基本方程。優值，最后寫出動態規劃基本方程。 以上五步是建立動態規劃數學模型的一般步驟。由于以上五步是建立動態規劃數學模型的一般步驟。由于

23、動態規劃模型與線性規劃模型不同，動態規劃模型沒有統動態規劃模型與線性規劃模型不同，動態規劃模型沒有統一的模式，建模時必須根據具體問題具體分析，只有通過一的模式，建模時必須根據具體問題具體分析，只有通過不斷實踐總結，才能較好掌握建模方法與技巧。不斷實踐總結，才能較好掌握建模方法與技巧。 20例一、從例一、從A 地到地到D 地要鋪設一條煤氣管道地要鋪設一條煤氣管道,其中需經過其中需經過兩級中間站，兩點之間的連線上的數字表示距離，如兩級中間站，兩點之間的連線上的數字表示距離，如圖所示。問應該選擇什么路線，使總距離最短？圖所示。問應該選擇什么路線，使總距離最短？ AB1B2C1C2C3D2433332

24、1114二、最短路徑問題二、最短路徑問題21 解：整個計算過程分三個階段，從最后一個階段開始。解：整個計算過程分三個階段，從最后一個階段開始。 第一階段（第一階段（C D）：）： C 有三條路線到終點有三條路線到終點D 。 AB1B2C1C2C3D24333321114DC1C2C3顯然有顯然有 f1 (C1 ) = 1 ； f1(C2 ) = 3 ； f1 (C3 ) = 4 22 d( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3 d( B1,C3 ) + f1 (C3 ) 1+4 4 = mi

25、n 6 = 4 5第二階段（第二階段（B C）：）： B 到到C 有六條路線。有六條路線。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為最短路線為B1C1 D)23 d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為最短路線為B2C1 D)24第三階段（第三階段（ A B ）：）： A 到到B 有二條路線

26、。有二條路線。 f3(A)1 = d(A, B1 ) f2 ( B1 ) 246 f3 (A)2 = d(A, B2 ) f2 ( B2 ) 437 f3 (A) = min = min6,7=6d(A, B1 ) f2 ( B1 )d(A, B2 ) f2 ( B2 )(最短路線為最短路線為AB1C1 D)AB1B2C1C2C3D24333321114DC1C2C3B1B2A25AB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路線為最短路線為 AB1C1 D 路長為路長為 626練習練習1：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876

27、368533842221333525664最優路線為：最優路線為：A B1 C2 D1 E2 F2 G 路長路長18求從求從A到到G的最短路徑的最短路徑327k=5k=5，出發點，出發點E1E1、E2E2、E3E3 73543min,min2621516115FfFEdFfFEdu5(E1)=F1E1 F1 G 53245min,min262251612525FfFEdFfFEdfEAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643)(15Efu5(E2)=F2E2 F2 G 93646min,min262351613535

28、FfFEdFfFEdfEu5(E3)=F2E3 F2 Gk=6k=6,F1 G f f6 6(F1)=4(F1)=4F F2 2 G ,f,f6 6(F2)=3(F2)=328k=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)+ f2(B1)

29、 d1(A,B2)+ f2(B2)5+133+16=18k=1,u1(A)=B1 u2(B1)=C2u3(C2)=D1u4(D1)=E229u1(A)=B1 u2(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最優策略最優策略AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664330求從求從A到到E的最短路徑的最短路徑路線為路線為AB2C1 D1 E ，最短路徑為最短路徑為1919AB2

30、B1B3C1C3D1D2EC25214112610104312111396581052練習練習2：131 現有數量為現有數量為a（萬元）的資金，計劃分配給（萬元）的資金，計劃分配給n 個工廠個工廠,用于擴大再生產。用于擴大再生產。 假設：假設：xi 為分配給第為分配給第i 個工廠的資金數量（萬元）個工廠的資金數量（萬元） ；gi(xi)為第為第i 個工廠得到資金后提供的利潤值（萬元）。個工廠得到資金后提供的利潤值（萬元）。 問題是如何確定各工廠的資金數，使得總的利潤為問題是如何確定各工廠的資金數，使得總的利潤為最大。最大。 nixaxxgZiniiniii.2.1 0)(max11據此，有下式

31、：據此，有下式：三、投資分配問題三、投資分配問題32 令：令：fk(x) = 以數量為以數量為x 的資金分配給前的資金分配給前k 個工廠，所個工廠，所得到的最大利潤值。得到的最大利潤值。 用動態規劃求解，就是求用動態規劃求解，就是求 fn(a) 的問題。的問題。 當當 k=1 時，時， f1(x) = g1(x) （因為只給一個工廠）（因為只給一個工廠） 當當1kn 時，其遞推關系如下：時，其遞推關系如下： 設：設：y 為分給第為分給第k 個工廠的資金（其中個工廠的資金（其中 0y x ），此時），此時還剩還剩 x y（萬元）的資金需要分配給前（萬元）的資金需要分配給前 k-1 個工廠個工廠,

32、如如果采取最優策略，則得到的最大利潤為果采取最優策略，則得到的最大利潤為fk1(xy) ,因此因此總的利潤為：總的利潤為： gk(y) fk1(xy) 33nkyxfygxfkkxyk.3.2)()(max)(10其其中中 如果如果a 是以萬元為資金分配單位，則式中的是以萬元為資金分配單位，則式中的y 只取只取非負整數非負整數0，1，2，x。上式可變為：。上式可變為：)()(max)(1,2,1 ,0yxfygxfkkxyk所以，根據動態規劃的最優化原理，有下式：所以，根據動態規劃的最優化原理，有下式：34 例題：例題： 設國家撥給設國家撥給60萬元投資，供四個工廠擴建使用，每萬元投資，供四個

33、工廠擴建使用，每個工廠擴建后的利潤與投資額的大小有關，投資后的個工廠擴建后的利潤與投資額的大小有關，投資后的利潤函數如下表所示。利潤函數如下表所示。解：依據題意，是要求解：依據題意，是要求 f4(60) 。35按順序解法計算。按順序解法計算。第一階段：求第一階段：求 f1(x)。顯然有。顯然有 f1(x) g1(x)，得到下表，得到下表第二階段：求第二階段：求 f2(x)。此時需考慮第一、第二個工廠如。此時需考慮第一、第二個工廠如何進行投資分配，以取得最大的總利潤。何進行投資分配，以取得最大的總利潤。)60()(max)60(1260,10,02yfygfy361200652060505565

34、5080408520850max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max12121212121212fgfgfgfgfgfgfg最優策略為（最優策略為（40，20），此時最大利潤為），此時最大利潤為120萬元。萬元。同理可求得其它同理可求得其它 f2(x) 的值。的值。37105)0()50()10()40()20()30()30()20()40()10()50()0( )50()(max)50(1212121212121250,10,02fgfgfgfgfgfgyfygfy最優策略為（最優策略為（30，20），此時最大

35、利潤為），此時最大利潤為105萬元。萬元。3890 )40()(max)40(1240,10,02yfygfy最優策略為（最優策略為（20，20），此時最大利潤為），此時最大利潤為90萬元。萬元。70 )30()(max)30(1230,20,10,02yfygfy最優策略為（最優策略為（20，10），此時最大利潤為），此時最大利潤為70萬元。萬元。3950 )20()(max)20(1220,10,02yfygfy20 )10()(max)10(12,10,02yfygfy最優策略為（最優策略為（10，0）或（）或（ 0 ， 10 ） ，此時最大利潤，此時最大利潤為為20萬元。萬元。 f2(

36、0) 0。最優策略為（最優策略為（0，0），最大利潤為），最大利潤為0萬元。萬元。 得到下表得到下表最優策略為（最優策略為（20，0），此時最大利潤為），此時最大利潤為50萬元。萬元。40第三階段：求第三階段：求 f3(x)。此時需考慮第一、第二及第三個。此時需考慮第一、第二及第三個工廠如何進行投資分配，以取得最大的總利潤。工廠如何進行投資分配，以取得最大的總利潤。)60()(max)60(2360,10,03yfygfy411550115201105010070859060105251200max)0()60()10()50()20()40()30()30()40()20()50()10()

37、60()0(max23232323232323fgfgfgfgfgfgfg最優策略為（最優策略為（20，10，30），最大利潤為），最大利潤為155萬元。萬元。同理可求得其它同理可求得其它 f3(x) 的值。得到下表的值。得到下表42第四階段：求第四階段：求 f4(60)。即問題的最優策略。即問題的最優策略。)60()(max)60(3460,10,04yfygfy4316007025656060855011040135251550max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max34343434343434fgfgfgfg

38、fgfgfg最優策略為（最優策略為（20，0，30，10），最大利潤為），最大利潤為160萬元。萬元。44 練習：練習： 求投資分配問題得最優策略，其中求投資分配問題得最優策略，其中a50 萬元，其余萬元，其余資料如表所示。資料如表所示。45例：某公司打算在例：某公司打算在3個不同的地區設置個不同的地區設置4個銷售點，個銷售點，根據市場部門估計，在不同地區設置不同數量的銷根據市場部門估計，在不同地區設置不同數量的銷售點每月可得到的利潤如表所示。試問在各地區如售點每月可得到的利潤如表所示。試問在各地區如何設置銷售點可使每月總利潤最大。何設置銷售點可使每月總利潤最大。 地地區區銷售點銷售點0123

39、4123000161210251714302116322217 x1=2，x2=1，x3=1，f3(4)=47 46 有一個徒步旅行者，其可攜帶物品重量的限度為有一個徒步旅行者，其可攜帶物品重量的限度為a 公公斤，設有斤，設有n 種物品可供他選擇裝入包中。已知每種物品種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應如何選擇攜帶的重量及使用價值（作用），問此人應如何選擇攜帶的物品（各幾件），使所起作用（使用價值）最大？的物品（各幾件），使所起作用（使用價值）最大？ 這就是背包問題。類似的還有工廠里的下料問題、運這就是背包問題。類似的還有工廠里的下料問題、運輸中的貨物裝載問

40、題、人造衛星內的物品裝載問題等。輸中的貨物裝載問題、人造衛星內的物品裝載問題等。四、背包問題四、背包問題47設設xj 為第為第j 種物品的裝件數（非負整數）則問題的數學種物品的裝件數（非負整數）則問題的數學模型如下：模型如下： ). 2 . 1(0max1njxaxaxcZjnijjjnjjj 且且為為整整數數用動態規劃方法求解，令用動態規劃方法求解，令 fx(y) = 總重量不超過總重量不超過 y 公斤，包中只裝有前公斤，包中只裝有前k 種物品種物品時的最大使用價值。時的最大使用價值。 其中其中y 0， k 1,2, , n 。所以問題就是求所以問題就是求 fn(a) 48其遞推關系式為：其

41、遞推關系式為： nkxayfxcyfkkkkkayxkkk 2)(max)(10 其其中中當當 k=1 時，有：時，有：的最大整數表示不超過其中1111111 , )(ayayayxaycyf49例題：求下面背包問題的最優解例題：求下面背包問題的最優解 且且為為整整數數0,55231258max321321321xxxxxxxxxZ解：解：a5 ，問題是求，問題是求 f3(5) )55(12max)5(323503333xfxfxax 整整數數50 )1()0(223231032355032350333333333)0(12),5(0max)55(12max)55(12max)55(12max

42、)5(xxxxxxaxffxfxxfxxfxf ，整整數數整整數數51 5 5 )( 2)1()0(1112122, 10212250212502222222222)1(10),3(5),5(0max)25(max)25(max)25(5max)5(xxxxxxxaxfffxfxxfxxfxf，整整數數整整數數52 )0()0(0max)20(max)20(max)20(5max)0(1)0(121202122002120022222222ffxfxxfxxfxfxxxxxax 5 5 整數整數整數整數53)0(0308)0()0(0318)1()1(8338)3()1(8358)5(1111

43、111111111111 xxcfxxcfxxcfxxcf ) 1, 1(1310, 85, 8max) 1 (10),3(5),5(0max)5(212)1()0(1112222 xxffffxxx )( 54 )0, 0(0)0()0(0max)0(211)0(122 xxfffx )0,1,1(13012,130max)0(12),5(0max)5(321)1()0(22333 xxxfffxx所以，最優解為所以，最優解為 X（1 . 1 . 0），），最優值為最優值為 Z = 13。55 練習練習1：某廠生產三種產品，各種產品重量與利：某廠生產三種產品，各種產品重量與利潤的關系如表所示

44、。現將此三種產品運往市場出售，潤的關系如表所示?，F將此三種產品運往市場出售，運輸能力總重量不超過運輸能力總重量不超過 6 噸，問如何安排運輸，使噸，問如何安排運輸，使總利潤最大？總利潤最大？最優方案：最優方案：X1 = =（0.2.00.2.0）X2 = =（1.0.11.0.1）Z=260=26056 練習練習2：求下列問題的最優解：求下列問題的最優解 且且為為整整數數0,10543654max321321321xxxxxxxxxZ X=(2. 1. 0) 最優值為最優值為 Z = 1357 排序問題指排序問題指n 種零件經過不同設備加工是的順序問題。種零件經過不同設備加工是的順序問題。其目

45、的是使加工周期為最短。其目的是使加工周期為最短。 1、n 1 排序問題排序問題 即即n 種零件經過種零件經過1 種設備進行加工，如何安排？種設備進行加工，如何安排？14682023交貨日期（交貨日期（d）45173加工時間（加工時間（t）零件代號零件代號2j1j3j4j5j例例1 五、排序問題五、排序問題58 （1）平均通過設備的時間最?。┢骄ㄟ^設備的時間最小 按零件加工時間非負次序排列順序，其時間最小。（即按零件加工時間非負次序排列順序，其時間最小。（即將加工時間由小到大排列即可）將加工時間由小到大排列即可）1j2j3j4j5j零件加工順序零件加工順序 工序時間工序時間13457 實際通過

46、時間實際通過時間1481320 交貨時間交貨時間82314620 平均通過時間平均通過時間2 .9)1481320(51 x59延遲時間延遲時間 = 13 6 = 7 （2）按時交貨排列順序）按時交貨排列順序1j2j3j4j5j零件加工順序零件加工順序 工序時間工序時間13457 實際通過時間實際通過時間56101720 交貨時間交貨時間82314620 平均通過時間平均通過時間6 .11)56101720(51 x延遲時間延遲時間 = 060 （3）既滿足交貨時間，又使平均通過時間最小）既滿足交貨時間，又使平均通過時間最小1j2j3j4j5j零件加工順序零件加工順序 工序時間工序時間1345

47、7 實際通過時間實際通過時間1691320 交貨時間交貨時間82314620延遲時間延遲時間 = 0 平均通過時間平均通過時間8 .9)1691320(51 x61 2、n 2 排序問題排序問題 即即n 種零件經過種零件經過2 種設備進行加工，如何安排？種設備進行加工，如何安排？例二、例二、49523B53786A 零件零件2j1j3j4j5j設備設備ABT62經變換為經變換為49523B53786A 零件零件2j1j3j4j5j設備設備加工順序圖如下：加工順序圖如下：ABT3j1j2j4j5j3756895432+2+2-5 加工周期加工周期 T = 3+7+5+6+8+2 = 31小小即即

48、BAtti 63 3、n 3 排序問題排序問題 即即n 種零件經過種零件經過 3 種設備進行加工，如何安排？種設備進行加工，如何安排？例三、例三、3468564683579310CBA1j2j3j4j5j64ABCT變換變換4+36+45+86+56+48+65+37+53+910+3B + CA+B1j2j3j4j5j65排序排序4+36+45+86+56+48+65+37+53+910+3B + CA+B1j2j3j4j5j復原復原3468564683579310CBA1j2j3j4j5j66計算計算T = 6+10+8+7+6+4+3 = 44計算依據：計算依據：ABcCBABCBAtt

49、ttttttttiiiiii maxmin maxmin或或即即可可按按下下式式計計算算或或67練習：練習：11851079827746CBA1j2j3j4jT=451j2j3j4j68一一 動態規劃的基本概念和最優化原理動態規劃的基本概念和最優化原理1、引例（最短路問題）、引例（最短路問題） 假如上圖是一個線路網絡，兩點之間連線上的數字表示假如上圖是一個線路網絡，兩點之間連線上的數字表示兩點間的距離（或費用），我們的問題是要將貨物從兩點間的距離（或費用），我們的問題是要將貨物從A地運地運往往E地，中間通過地，中間通過B、C、D三個區域，在區域內有多條路徑三個區域，在區域內有多條路徑可走，現求

50、一條由可走，現求一條由A到到E的線路，使總距離最短（或總費用的線路，使總距離最短（或總費用最小）。最?。?。AB1B2B3C1C2C3D1D2E2437463242653463333469第四階段，由第四階段，由D1到到E只有一條路線，其長度只有一條路線，其長度f4（D1）=3，同理同理f4（D2）=4。 第三階段，由第三階段，由Cj到到Di分別均有兩種選擇，即分別均有兩種選擇，即64433minDfDCDfDCminCf2421141113，決策點為D1643*33minDfDCDfDCminCf2423141333,決策點為D17*4336minDfDCDfDCminCf2422141223，決策點為D270第二階段，由Bj到Cj分別均有三種選擇，即： 11667467minCfCBCfCBCfCBminBf*33332322131112決策點為C2 96472*63minCfCBCfCBCfCBminBf*33332322132222決策點為C1或C296