運籌學動態(tài)規(guī)劃(1)ppt課件

1、動動 態(tài)態(tài) 規(guī)規(guī) 劃劃 (Dynamic programming)動態(tài)規(guī)劃的根本思想動態(tài)規(guī)劃的根本思想最短途徑問題最短途徑問題投資分配問題投資分配問題背包問題背包問題 動態(tài)規(guī)劃是用來處理多階段決策過程最優(yōu)動態(tài)規(guī)劃是用來處理多階段決策過程最優(yōu)化的一種數量方法。其特點在于，它可以把一化的一種數量方法。其特點在于，它可以把一個個n 維決策問題變換為幾個一維最優(yōu)化問題，從維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去處理。而一個一個地去處理。 需指出：動態(tài)規(guī)劃是求解某類問題的一種需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是調查問題的一種途徑，而不是一種算方法，是調查問題的一種途徑，而不是一種算法

2、。必需對詳細問題進展詳細分析，運用動態(tài)法。必需對詳細問題進展詳細分析，運用動態(tài)規(guī)劃的原理和方法，建立相應的模型，然后再規(guī)劃的原理和方法，建立相應的模型，然后再用動態(tài)規(guī)劃方法去求解。用動態(tài)規(guī)劃方法去求解。即在系統(tǒng)開展的不同時辰或階段根據系統(tǒng)即在系統(tǒng)開展的不同時辰或階段根據系統(tǒng)所處的形狀，不斷地做出決策；所處的形狀，不斷地做出決策；每個階段都要進展決策每個階段都要進展決策, ,目的是使整個過程的決策目的是使整個過程的決策 到達最優(yōu)效果。到達最優(yōu)效果。動態(tài)決策問題的特點：動態(tài)決策問題的特點：系統(tǒng)所處的形狀和時辰是進展決策的重要要素；系統(tǒng)所處的形狀和時辰是進展決策的重要要素；找到不同時辰的最優(yōu)決策以及

3、整個過程的最優(yōu)戰(zhàn)略。找到不同時辰的最優(yōu)決策以及整個過程的最優(yōu)戰(zhàn)略。多階段決策問題：多階段決策問題：是動態(tài)決策問題的一種特殊方式；是動態(tài)決策問題的一種特殊方式；在多階段決策過程中在多階段決策過程中, ,系統(tǒng)的動態(tài)過程可以按照時間系統(tǒng)的動態(tài)過程可以按照時間進程分為形狀相互聯絡而又相互區(qū)別的各個階段；進程分為形狀相互聯絡而又相互區(qū)別的各個階段；多階段決策問題的典型例子：多階段決策問題的典型例子： 1 . 1 . 消費決策問題：企業(yè)在消費過程中，消費決策問題：企業(yè)在消費過程中，由于需求是隨時間變化的，因此企業(yè)為了獲由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最正確消費效益，就要在整個消費得全年的最正

4、確消費效益，就要在整個消費過程中逐月或逐季度地根據庫存和需求決議過程中逐月或逐季度地根據庫存和需求決議消費方案。消費方案。 2. 機器負荷分配問題：某種機器可以在高低兩種不同的負荷下進展消費。在高負荷下進展消費時，產品的年產量g和投入消費的機器數量u1的關系為g=g(u1)12n形狀形狀決策決策形狀形狀決策決策形狀形狀形狀形狀決策決策 這時，機器的年完好率為a，即假設年初完好機器的數量為u，到年終完好的機器就為au, 0a1。 在低負荷下消費時，產品的年產量h和投入消費的機器數量u2的關系為 h=h(u2) 假定開場消費時完好的機器數量為s1。要求制定一個五年方案，在每年開場時，決議如何重新分

5、配完好的機器在兩種不同的負荷下消費的數量，使在五年內產品的總產量到達最高。 相應的機器年完好率b, 0 b1。 3. 航天飛機飛行控制問題：由于航天飛機的運動的環(huán)境是不斷變化的，因此就要根據航天飛機飛行在不同環(huán)境中的情況，不斷地決議航天飛機的飛行方向和速度形狀，使之能最省燃料和實現目的如軟下落問題。 不包含時間要素的靜態(tài)決策問題本質上是一次決策問題也可以適當地引入階段的概念，作為多階段的決策問題用動態(tài)規(guī)劃方法來處理。 4 . 線性規(guī)劃、非線性規(guī)劃等靜態(tài)的規(guī)劃問題也可以經過適當地引入階段的概念，運用動態(tài)規(guī)劃方法加以處理。 5 . 最短路問題：給定一個交通網絡圖如下，其中兩點之間的數字表示間隔或破

6、費，試求從A點到G點的最短間隔總費用最小。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643 一、根本概念一、根本概念 1、階段：、階段： 把一個問題的過程，恰當地分為假設干個相互聯絡把一個問題的過程，恰當地分為假設干個相互聯絡的階段，以便于按一定的次序去求解。的階段，以便于按一定的次序去求解。 描畫階段的變量稱為階段變量。階段的劃分，普通描畫階段的變量稱為階段變量。階段的劃分，普通是根據時間和空間的自然特征來進展的，但要便于問題是根據時間和空間的自然特征來進展的，但要便于問題轉化為多階段決策。轉化為多階段決策。

7、2、形狀：表示每個階段開場所處的自然情況或客觀、形狀：表示每個階段開場所處的自然情況或客觀條件。通常一個階段有假設干個形狀，描畫過程形狀條件。通常一個階段有假設干個形狀，描畫過程形狀的變量稱為形狀變量。的變量稱為形狀變量。年、月、年、月、路段路段一個數、一個數、一組數、一組數、一個向一個向量量 形狀變量的取值有一定的允許集合或范圍，此集合形狀變量的取值有一定的允許集合或范圍，此集合稱為形狀允許集合。稱為形狀允許集合。一、動態(tài)規(guī)劃的根本思想一、動態(tài)規(guī)劃的根本思想 3、決策：表示當過程處于某一階段的某個形狀時，、決策：表示當過程處于某一階段的某個形狀時，可以作出不同的決議，從而確定下一階段的形狀，

8、這可以作出不同的決議，從而確定下一階段的形狀，這種決議稱為決策。種決議稱為決策。 描畫決策的變量，稱為決策變量。決策變量是形狀描畫決策的變量，稱為決策變量。決策變量是形狀變量的函數。可用一個數、一組數或一向量多維情變量的函數?？捎靡粋€數、一組數或一向量多維情形來描畫。形來描畫。 在實踐問題中決策變量的取值往往在某一范圍之內，在實踐問題中決策變量的取值往往在某一范圍之內，此范圍稱為允許決策集合。此范圍稱為允許決策集合。 系統(tǒng)在某一階段的形狀轉移不但與系統(tǒng)的當前的形狀系統(tǒng)在某一階段的形狀轉移不但與系統(tǒng)的當前的形狀和決策有關，而且還與系統(tǒng)過去的歷史形狀和決策有和決策有關，而且還與系統(tǒng)過去的歷史形狀和

9、決策有關。關。 4、多階段決策過程、多階段決策過程 可以在各個階段進展決策，去控制過程開展的多段過可以在各個階段進展決策，去控制過程開展的多段過程；程； 其開展是經過一系列的形狀轉移來實現的；其開展是經過一系列的形狀轉移來實現的；),(),(),(221112211231112kkkkusususTsususTsusTs 圖示如下：圖示如下：形狀轉移方程是確定形狀轉移方程是確定過程由一個形狀到另過程由一個形狀到另一個形狀的演化過程。一個形狀的演化過程。假設第假設第k k階段形狀變量階段形狀變量sksk的值、該階段的決的值、該階段的決策變量一經確定，第策變量一經確定，第k+1k+1階段形狀變量階

10、段形狀變量sk+1sk+1的值也就確定。的值也就確定。其形狀轉移方程如下普通方式其形狀轉移方程如下普通方式12ks1u1s2u2s3skuksk+1 能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即具有無后效性的多階段特殊的多階段決策過程，即具有無后效性的多階段決策過程。決策過程。 假設形狀變量不能滿足無后效性的要求，應假設形狀變量不能滿足無后效性的要求，應適當地改動形狀的定義或規(guī)定方法。適當地改動形狀的定義或規(guī)定方法。),(),(),(122231112kkkkusTsusTsusTs 動態(tài)規(guī)劃中能動態(tài)規(guī)劃中能處置的形狀轉移處置的形

11、狀轉移方程的方式。方程的方式。 形狀具有無后效性的多階段決策過程的形形狀具有無后效性的多階段決策過程的形狀轉移方程如下狀轉移方程如下無后效性無后效性( (馬爾可夫性馬爾可夫性) ) 假設某階段形狀給定后，那么在這個階段以假設某階段形狀給定后，那么在這個階段以后過程的開展不受這個階段以前各段形狀的影響；后過程的開展不受這個階段以前各段形狀的影響； 過程的過去歷史只能經過當前的形狀去影響過程的過去歷史只能經過當前的形狀去影響它未來的開展；它未來的開展； 構造動態(tài)規(guī)劃模型時，要充分留意構造動態(tài)規(guī)劃模型時，要充分留意能否滿足無后效性的要求；能否滿足無后效性的要求；形狀變量要滿足無后效性的要求；形狀變量

12、要滿足無后效性的要求； 5 5、戰(zhàn)略：是一個按順序陳列的決策組成的集合。在、戰(zhàn)略：是一個按順序陳列的決策組成的集合。在實踐問題中，可供選擇的戰(zhàn)略有一定的范圍，稱為允實踐問題中，可供選擇的戰(zhàn)略有一定的范圍，稱為允許戰(zhàn)略集合。從允許戰(zhàn)略集合中找出到達最優(yōu)效果的許戰(zhàn)略集合。從允許戰(zhàn)略集合中找出到達最優(yōu)效果的戰(zhàn)略稱為最優(yōu)戰(zhàn)略。戰(zhàn)略稱為最優(yōu)戰(zhàn)略。 6 6、形狀轉移方程：是確定過程由一個形狀到另一、形狀轉移方程：是確定過程由一個形狀到另一個形狀的演化過程，描畫了形狀轉移規(guī)律。個形狀的演化過程，描畫了形狀轉移規(guī)律。 7 7、目的函數和最優(yōu)值函數：用來衡量所實現過程優(yōu)、目的函數和最優(yōu)值函數：用來衡量所實現過程

13、優(yōu)劣的一種數量目的，為目的函數。目的函數的最優(yōu)值，劣的一種數量目的，為目的函數。目的函數的最優(yōu)值，稱為最優(yōu)值函數。在不同的問題中，目的函數的含義稱為最優(yōu)值函數。在不同的問題中，目的函數的含義是不同的，它能夠是間隔、利潤、本錢、產量或資源是不同的，它能夠是間隔、利潤、本錢、產量或資源耗費等。耗費等。 動態(tài)規(guī)劃模型的目的函數，應具有可分別性，并滿動態(tài)規(guī)劃模型的目的函數，應具有可分別性，并滿足遞推關系。足遞推關系。小結小結: :),()(1,susVoptsfnkknkkkuunk),(,111,1nkknkkkksusVus方程方程 : :形狀轉移方程形狀轉移方程),(1kkkkusTs概念概念

14、: : 階段變量階段變量k k形狀變量形狀變量sksk決策變量決策變量uk;uk;目的目的: : ),(111,nkkkknknksususVV動態(tài)規(guī)劃本質上是多階段決策過程動態(tài)規(guī)劃本質上是多階段決策過程; ; 效益目的函數方式目的函數方式: : 和、積積無后效性無后效性),(111,nkkkknksususV可遞推可遞推,*2*1nuuu,*2*1nsss解多階段決策過程問題，求出解多階段決策過程問題，求出 最優(yōu)戰(zhàn)略，即最優(yōu)決策序列 susvoptsfnkknkkkuunk1, f1(s1) 最優(yōu)軌線，即執(zhí)行最優(yōu)戰(zhàn)略時的形狀序列 最優(yōu)目的函數值最優(yōu)目的函數值),(*1*1*,1*,1nnnn

15、ususVV從從 k k 到終點最優(yōu)戰(zhàn)略到終點最優(yōu)戰(zhàn)略子戰(zhàn)略的最優(yōu)目的函數值子戰(zhàn)略的最優(yōu)目的函數值 1、動態(tài)規(guī)劃方法的關鍵在于正確地寫出根本、動態(tài)規(guī)劃方法的關鍵在于正確地寫出根本的遞推關系式和恰當的邊境條件簡稱根本方的遞推關系式和恰當的邊境條件簡稱根本方程。要做到這一點，就必需將問題的過程分程。要做到這一點，就必需將問題的過程分成幾個相互聯絡的階段，恰當的選取形狀變量成幾個相互聯絡的階段，恰當的選取形狀變量和決策變量及定義最優(yōu)值函數，從而把一個大和決策變量及定義最優(yōu)值函數，從而把一個大問題轉化成一組同類型的子問題，然后逐個求問題轉化成一組同類型的子問題，然后逐個求解。即從邊境條件開場，逐段遞推

16、尋優(yōu)，在每解。即從邊境條件開場，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結果，依次進展，最后一個子問題題的最優(yōu)化結果，依次進展，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。所得的最優(yōu)解，就是整個問題的最優(yōu)解。二、動態(tài)規(guī)劃的根本思想二、動態(tài)規(guī)劃的根本思想 2、在多階段決策過程中，動態(tài)規(guī)劃方法是既把當前、在多階段決策過程中，動態(tài)規(guī)劃方法是既把當前一段和未來一段分開，又把當前效益和未來效益結合一段和未來一段分開，又把當前效益和未來效益結合起來思索的一種最優(yōu)化方法。因此，每段決策的選取起來思索的一種最優(yōu)化方法。因此，每段決策的選

17、取是從全局來思索的，與該段的最優(yōu)選擇答案普通是不是從全局來思索的，與該段的最優(yōu)選擇答案普通是不同的同的. 最優(yōu)化原理：作為整個過程的最優(yōu)戰(zhàn)略具有這樣的最優(yōu)化原理：作為整個過程的最優(yōu)戰(zhàn)略具有這樣的性質：無論過去的形狀和決策如何，相對于前面的決性質：無論過去的形狀和決策如何，相對于前面的決策所構成的形狀而言，余下的決策序列必然構成最優(yōu)策所構成的形狀而言，余下的決策序列必然構成最優(yōu)子戰(zhàn)略。也就是說，一個最優(yōu)戰(zhàn)略的子戰(zhàn)略也是最子戰(zhàn)略。也就是說，一個最優(yōu)戰(zhàn)略的子戰(zhàn)略也是最優(yōu)的。優(yōu)的。 3、在求整個問題的最優(yōu)戰(zhàn)略時，由于初始形狀是、在求整個問題的最優(yōu)戰(zhàn)略時，由于初始形狀是知的，而每段的決策都是該段形狀的函

18、數，故最優(yōu)戰(zhàn)知的，而每段的決策都是該段形狀的函數，故最優(yōu)戰(zhàn)略所經過的各段形狀便可逐段變換得到，從而確定了略所經過的各段形狀便可逐段變換得到，從而確定了最優(yōu)道路。最優(yōu)道路。三、建立動態(tài)規(guī)劃模型的步驟三、建立動態(tài)規(guī)劃模型的步驟 1、劃分階段、劃分階段劃分階段是運用動態(tài)規(guī)劃求解多階段決策問題的第一劃分階段是運用動態(tài)規(guī)劃求解多階段決策問題的第一步，在確定多階段特性后，按時間或空間先后順序，步，在確定多階段特性后，按時間或空間先后順序，將過程劃分為假設干相互聯絡的階段。對于靜態(tài)問題將過程劃分為假設干相互聯絡的階段。對于靜態(tài)問題要人為地賦予要人為地賦予“時間概念，以便劃分階段。時間概念，以便劃分階段。 2

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

20、階段形狀變量和決策變量，寫出階段形狀變量和決策變量，寫出k+1k+1階段形狀變階段形狀變量，形狀轉移方程該當具有遞推關系。量，形狀轉移方程該當具有遞推關系。 5 5、確定階段目的函數和最優(yōu)目的函數，建立動態(tài)規(guī)、確定階段目的函數和最優(yōu)目的函數，建立動態(tài)規(guī)劃根本方程劃根本方程 階段目的函數是指第階段目的函數是指第k k 階段的收益，最優(yōu)目的函數階段的收益，最優(yōu)目的函數是指從第是指從第k k 階段形狀出發(fā)到第階段形狀出發(fā)到第n n 階段末所獲得收益的階段末所獲得收益的最優(yōu)值，最后寫出動態(tài)規(guī)劃根本方程。最優(yōu)值，最后寫出動態(tài)規(guī)劃根本方程。 以上五步是建立動態(tài)規(guī)劃數學模型的普通步驟。由于以上五步是建立動態(tài)

21、規(guī)劃數學模型的普通步驟。由于動態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動態(tài)規(guī)劃模型沒有一動態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動態(tài)規(guī)劃模型沒有一致的方式，建模時必需根據詳細問題詳細分析，只需經過致的方式，建模時必需根據詳細問題詳細分析，只需經過不斷實際總結，才干較好掌握建模方法與技巧。不斷實際總結，才干較好掌握建模方法與技巧。 例一、從例一、從A 地到地到D 地要鋪設一條煤氣管道地要鋪設一條煤氣管道,其中需經過其中需經過兩級中間站，兩點之間的連線上的數字表示間隔，如兩級中間站，兩點之間的連線上的數字表示間隔，如下圖。問應該選擇什么道路，使總間隔最短？下圖。問應該選擇什么道路，使總間隔最短？ AB1B2C1C2

22、C3D24333321114二、最短途徑問題二、最短途徑問題 解：整個計算過程分三個階段，從最后一個階段開場。解：整個計算過程分三個階段，從最后一個階段開場。 第一階段第一階段C D： C 有三條道路到終點有三條道路到終點D 。 AB1B2C1C2C3D24333321114DC1C2C3顯然有顯然有 f1 (C1 ) = 1 ； f1(C2 ) = 3 ； f1 (C3 ) = 4 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

23、n 6 = 4 5第二階段第二階段B C： B 到到C 有六條道路。有六條道路。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短道路為最短道路為B1C1 D) 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)第三階段第三階段 A B ： A 到到B 有二條道路。有二條道路。 f3(A)1

24、 = 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)AB1B2C1C2C3D24333321114DC1C2C3B1B2AAB1B2C1C2C3D24333321114DC1C2C3B1B2A最短道路為最短道路為 AB1C1 D 路長為路長為 6練習練習1：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525

25、664最優(yōu)道路為：最優(yōu)道路為：A B1 C2 D1 E2 F2 G 路長路長18求從求從A A到到G G的最短途徑的最短途徑3k=5k=5，出發(fā)點，出發(fā)點E1E1、E2E2、E3E3 73543min,min2621516115FfFEdFfFEdu5(E1)=F1E1 F1 G 53245min,min262251612525FfFEdFfFEdfEAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643)(15Efu5(E2)=F2E2 F2 G 93646min,min262351613535FfFEdFfFEdfEu5(E

26、3)=F2E3 F2 Gk=6,k=6,F1 G f6(F1)=4F2 G ,f6(F2)=3k=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) d1(A,B2)+ f2(B2)5+133+16=18k=1,u1(A)=B1

27、u2(B1)=C2u3(C2)=D1u4(D1)=E2u1(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最優(yōu)戰(zhàn)略最優(yōu)戰(zhàn)略AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643求從求從A A到到E E的最短途徑的最短途徑道路為道路為AB2C1 D1 E AB2C1 D1 E ，最短途徑為，最短途徑為1919AB2B1B3C1C3D1D2EC252141126101043

28、12111396581052練習練習2：1 現有數量為現有數量為a萬元的資金，方案分配給萬元的資金，方案分配給n 個工廠個工廠,用于擴展再消費。用于擴展再消費。 假設：假設：xi 為分配給第為分配給第i 個工廠的資金數量萬元個工廠的資金數量萬元 ；gi(xi)為第為第i 個工廠得到資金后提供的利潤值萬元。個工廠得到資金后提供的利潤值萬元。 問題是如何確定各工廠的資金數，使得總的利潤為問題是如何確定各工廠的資金數，使得總的利潤為最大。最大。 nixaxxgZiniiniii.2.1 0)(max11據此，有下式：據此，有下式：三、投資分配問題三、投資分配問題 令：令：fk(x) = 以數量為以數

29、量為x 的資金分配給前的資金分配給前k 個工廠，所個工廠，所得到的最大利潤值。得到的最大利潤值。 用動態(tài)規(guī)劃求解，就是求用動態(tài)規(guī)劃求解，就是求 fn(a) 的問題。的問題。 當當 k=1 時，時， f1(x) = g1(x) 由于只給一個工廠由于只給一個工廠 當當1kn 時，其遞推關系如下：時，其遞推關系如下： 設：設：y 為分給第為分給第k 個工廠的資金其中個工廠的資金其中 0y x ，此，此時還剩時還剩 x y萬元的資金需求分配給前萬元的資金需求分配給前 k-1 個工廠個工廠,假設采取最優(yōu)戰(zhàn)略，那么得到的最大利潤為假設采取最優(yōu)戰(zhàn)略，那么得到的最大利潤為fk1(xy) ,因此總的利潤為：因此

30、總的利潤為： gk(y) fk1(xy) nkyxfygxfkkxyk.3.2)()(max)(10其其中中 假設假設a 是以萬元為資金分配單位，那么式中的是以萬元為資金分配單位，那么式中的y 只只取非負整數取非負整數0，1，2，x。上式可變?yōu)椋?。上式可變?yōu)椋?()(max)(1,2,1 ,0yxfygxfkkxyk所以，根據動態(tài)規(guī)劃的最優(yōu)化原理，有下式：所以，根據動態(tài)規(guī)劃的最優(yōu)化原理，有下式： 例題：例題： 設國家撥給設國家撥給60萬元投資，供四個工廠擴建運萬元投資，供四個工廠擴建運用，每個工廠擴建后的利潤與投資額的大小有用，每個工廠擴建后的利潤與投資額的大小有關，投資后的利潤函數如下表所示

31、。關，投資后的利潤函數如下表所示。 投資投資利潤利潤0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：根據題意，是要求解：根據題意，是要求 f4(60) 。按順序解法計算。按順序解法計算。第一階段：求第一階段：求 f1(x)。顯然有。顯然有 f1(x) g1(x)，得到下表，得到下表 投資投資利潤利潤0102030405060f1(x) g1(x)0205065808585最優(yōu)戰(zhàn)略最優(yōu)戰(zhàn)略0102030405060第二階段：求第二階段：求 f2(x)。此時需思索第一

32、、第二個工廠如。此時需思索第一、第二個工廠如何進展投資分配，以獲得最大的總利潤。何進展投資分配，以獲得最大的總利潤。)60()(max)60(1260,10,02yfygfy12006520605055655080408520850max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max12121212121212fgfgfgfgfgfgfg最優(yōu)戰(zhàn)略為最優(yōu)戰(zhàn)略為40，20，此時最大利潤為，此時最大利潤為120萬元。萬元。同理可求得其它同理可求得其它 f2(x) 的值。的值。105)0()50()10()40()20()30()30

33、()20()40()10()50()0( )50()(max)50(1212121212121250,10,02fgfgfgfgfgfgyfygfy最優(yōu)戰(zhàn)略為最優(yōu)戰(zhàn)略為30，20，此時最大利潤為，此時最大利潤為105萬元。萬元。90 )40()(max)40(1240,10,02yfygfy最優(yōu)戰(zhàn)略為最優(yōu)戰(zhàn)略為20，20，此時最大利潤為，此時最大利潤為90萬元。萬元。70 )30()(max)30(1230,20,10,02yfygfy最優(yōu)戰(zhàn)略為最優(yōu)戰(zhàn)略為20，10，此時最大利潤為，此時最大利潤為70萬元。萬元。50 )20()(max)20(1220,10,02yfygfy20 )10()(

34、max)10(12,10,02yfygfy最優(yōu)戰(zhàn)略為最優(yōu)戰(zhàn)略為10，0或或 0 ， 10 ，此時最大利潤，此時最大利潤為為20萬元。萬元。 f2(0) 0。最優(yōu)戰(zhàn)略為0，0，最大利潤為0萬元。 得到下表最優(yōu)戰(zhàn)略為最優(yōu)戰(zhàn)略為20，0，此時最大利潤為，此時最大利潤為50萬元。萬元。 投資投資利潤利潤0102030405060f2(x)020507090105120最優(yōu)戰(zhàn)略最優(yōu)戰(zhàn)略(0,0)(10,0)(0,10)(20,0) (20,10) (20,20) (30,20) (40,20)第三階段：求第三階段：求 f3(x)。此時需思索第一、第二及第三個。此時需思索第一、第二及第三個工廠如何進展投資

35、分配，以獲得最大的總利潤。工廠如何進展投資分配，以獲得最大的總利潤。)60()(max)60(2360,10,03yfygfy1550115201105010070859060105251200max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max23232323232323fgfgfgfgfgfgfg最優(yōu)戰(zhàn)略為最優(yōu)戰(zhàn)略為20，10，30，最大利潤為，最大利潤為155萬元。萬元。同理可求得其它同理可求得其它 f3(x) 的值。得到下表的值。得到下表 投資投資利潤利潤0102030405060f3(x)0256085110155最

36、優(yōu)最優(yōu)戰(zhàn)略戰(zhàn)略(0,0,0) (0,0,10) (0,0,20) (0,0,30) (20,0,20) (20,0,30) (20,10,30)第四階段：求第四階段：求 f4(60)。即問題的最優(yōu)戰(zhàn)略。即問題的最優(yōu)戰(zhàn)略。)60()(max)60(3460,10,04yfygfy16007025656060855011040135251550max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max34343434343434fgfgfgfgfgfgfg最優(yōu)戰(zhàn)略為最優(yōu)戰(zhàn)略為20，0，30，10，最大利潤為，最大利潤為160萬元。萬元。

37、 練習：練習： 求投資分配問題得最優(yōu)戰(zhàn)略，其中求投資分配問題得最優(yōu)戰(zhàn)略，其中a50 萬元，萬元，其他資料如表所示。其他資料如表所示。 投資投資利潤利潤01020304050g1(x)02140528085g2(x)015365073100g3(x)02560656870例：某公司計劃在例：某公司計劃在3 3個不同的地域設置個不同的地域設置4 4個銷售點，個銷售點，根據市場部門估計，在不同地域設置不同數量的銷根據市場部門估計，在不同地域設置不同數量的銷售點每月可得到的利潤如表所示。試問在各地域如售點每月可得到的利潤如表所示。試問在各地域如何設置銷售點可使每月總利潤最大。何設置銷售點可使每月總利潤

38、最大。 地地域域銷售點銷售點01234123000161210251714302116322217 x1=2，x2=1，x3=1，f3(4)=47 有一個徒步游覽者，其可攜帶物品分量的限制為有一個徒步游覽者，其可攜帶物品分量的限制為a 公公斤，設有斤，設有n 種物品可供他選擇裝入包中。知每種物品種物品可供他選擇裝入包中。知每種物品的分量及運用價值作用，問此人應如何選擇攜帶的分量及運用價值作用，問此人應如何選擇攜帶的物品各幾件，使所起作用運用價值最大？的物品各幾件，使所起作用運用價值最大？物品物品 1 2 j n分量公斤分量公斤/ /件件 a1 a2 aj an每件運用價值每件運用價值 c1 c

39、2 cj cn 這就是背包問題。類似的還有工廠里的下料問題、這就是背包問題。類似的還有工廠里的下料問題、運輸中的貨物裝載問題、人造衛(wèi)星內的物品裝載問題運輸中的貨物裝載問題、人造衛(wèi)星內的物品裝載問題等。等。四、背包問題四、背包問題設設xj 為第為第j 種物品的裝件數非負整數那么問題的數種物品的裝件數非負整數那么問題的數學模型如下：學模型如下： ). 2 . 1(0max1njxaxaxcZjnijjjnjjj 且且為為整整數數用動態(tài)規(guī)劃方法求解，令用動態(tài)規(guī)劃方法求解，令 fx(y) = 總分量不超越總分量不超越 y 公斤，包中只裝有前公斤，包中只裝有前k 種物品種物品時的最大運用價值。時的最大運

40、用價值。 其中其中y 0， k 1,2, , n 。所以問題就是求。所以問題就是求 fn(a) 其遞推關系式為：其遞推關系式為： nkxayfxcyfkkkkkayxkkk 2)(max)(10 其其中中當當 k=1 時，有：時，有：的的最最大大整整數數表表示示不不超超過過其其中中1111111 , )(ayayayxaycyf例題：求下面背包問題的最優(yōu)解例題：求下面背包問題的最優(yōu)解 且且為為整整數數0,55231258max321321321xxxxxxxxxZ物品物品 1 2 3分量公斤分量公斤 3 2 5運用價值運用價值 8 5 12解：解：a5 ，問題是求，問題是求 f3(5) )55

41、(12max)5(323503333xfxfxax 整整數數 )1()0(223231032355032350333333333)0(12),5(0max)55(12max)55(12max)55(12max)5(xxxxxxaxffxfxxfxxfxf ，整整數數整整數數 5 5 )( 2)1()0(1112122, 10212250212502222222222)1(10),3(5),5(0max)25(max)25(max)25(5max)5(xxxxxxxaxfffxfxxfxxfxf，整整數數整整數數 )0()0(0max)20(max)20(max)20(5max)0(1)0(12

42、1202122002120022222222ffxfxxfxxfxfxxxxxax 5 5 整數整數整數整數)0(0308)0()0(0318)1()1(8338)3()1(8358)5(1111111111111111 xxcfxxcfxxcfxxcf ) 1, 1(1310, 85, 8max) 1 (10),3(5),5(0max)5(212)1()0(1112222 xxffffxxx )( )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所以，最優(yōu)解為所以，最優(yōu)解為 X1 . 1 . 0，最優(yōu)值為，最優(yōu)值為 Z = 13。 練習練習1：某廠消費三種產品，各種產品分量與利：某廠消費三種產品，各種產品分量與利潤的關系如表所示?，F將此三種產品運往市場出賣，潤的關系如表所示?，F將此三種產品運往市場出賣，運輸才干總分量不超越運輸才干總分量不超越 6 噸，問如何安排運輸，使噸，問如何安排運輸，使總利潤最大？總利潤最大？種類種類 1 2 3分量噸分量噸/ /公斤公斤 2 3 4 單件利潤元單件利潤元 80 130 180最優(yōu)方案：最優(yōu)方案：X1 =X1 =0,2,00