系統(tǒng)工程---第六章 動態(tài)規(guī)劃ppt課件

1、山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院第六章第六章 動態(tài)規(guī)劃動態(tài)規(guī)劃l6.1 動態(tài)規(guī)劃的根本原理和根本方程動態(tài)規(guī)劃的根本原理和根本方程l6.2 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題l6.3 資源分配問題資源分配問題l6.4 背包問題背包問題l6.5 延續(xù)型動態(tài)規(guī)劃問題延續(xù)型動態(tài)規(guī)劃問題山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.1 動態(tài)規(guī)劃的根本原理和根本方程動態(tài)規(guī)劃的根本原理和根本方程 l6.1.1 動態(tài)規(guī)劃的最優(yōu)性原理 l6.1.2 動態(tài)規(guī)劃的根本概念l6.1.3 動態(tài)規(guī)劃的根本方程l6.1.4 建立動態(tài)規(guī)劃的數(shù)學(xué)模型l6.1.5 動態(tài)規(guī)劃的求解山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.1

2、.1 動態(tài)規(guī)劃的最優(yōu)性原理動態(tài)規(guī)劃的最優(yōu)性原理6.1 動態(tài)規(guī)劃的根本原理和根本方程動態(tài)規(guī)劃的根本原理和根本方程 動態(tài)規(guī)劃是處理多階段決策問題的一種數(shù)學(xué)方法。 所謂多階段決策問題，是指對系統(tǒng)運(yùn)轉(zhuǎn)過程中假設(shè)干相繼階段的每一段都要作出決策，并使整個過程到達(dá)最優(yōu)的一類問題。 50年代，美國數(shù)學(xué)家貝爾曼(Richard Bellman)等人，根據(jù)多階段決策問題的性質(zhì)，提出理處理這類問題的“最優(yōu)性原理，并研討了許多實(shí)踐問題，從而建立了一種新的最優(yōu)化方法動態(tài)規(guī)劃Dynamic Programming)。 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院表述一：一個最優(yōu)戰(zhàn)略具有這樣的性質(zhì)，不論初始形狀及初始決策如何，

3、表述一：一個最優(yōu)戰(zhàn)略具有這樣的性質(zhì)，不論初始形狀及初始決策如何，對于該決策所呵斥的某一形狀而言，下余的一切決策必構(gòu)成一個最優(yōu)戰(zhàn)對于該決策所呵斥的某一形狀而言，下余的一切決策必構(gòu)成一個最優(yōu)戰(zhàn)略。略。 表述二：假設(shè)對恣意的時(shí)辰表述二：假設(shè)對恣意的時(shí)辰t t，不論過程在時(shí)辰，不論過程在時(shí)辰t t以前的歷史形以前的歷史形狀如何，假設(shè)按時(shí)辰狀如何，假設(shè)按時(shí)辰t t的形狀而言，過程今后的行為是最優(yōu)的。的形狀而言，過程今后的行為是最優(yōu)的。那么整個過程的行為亦必是最優(yōu)的。那么整個過程的行為亦必是最優(yōu)的。( (無后效性無后效性) ) 表述三：如圖，假設(shè)采取了最優(yōu)戰(zhàn)表述三：如圖，假設(shè)采取了最優(yōu)戰(zhàn)略，得到了某個系統(tǒng)

4、運(yùn)動的最優(yōu)軌略，得到了某個系統(tǒng)運(yùn)動的最優(yōu)軌線，該最優(yōu)軌線將形狀空間中的點(diǎn)線，該最優(yōu)軌線將形狀空間中的點(diǎn)起點(diǎn)與點(diǎn)終點(diǎn)銜接起來，起點(diǎn)與點(diǎn)終點(diǎn)銜接起來，如今最優(yōu)軌線上取某個中間點(diǎn)，從如今最優(yōu)軌線上取某個中間點(diǎn)，從而將最優(yōu)線分為而將最優(yōu)線分為、兩段，那么兩段，那么子軌線子軌線也是最優(yōu)的。也是最優(yōu)的。 系系統(tǒng)統(tǒng)運(yùn)運(yùn)動動最最優(yōu)優(yōu)軌軌線線圖圖 0 x 1x vx 2x Tx 6.1 動態(tài)規(guī)劃的根本原理和根本方程動態(tài)規(guī)劃的根本原理和根本方程 6.1.1 動態(tài)規(guī)劃的最優(yōu)性原理動態(tài)規(guī)劃的最優(yōu)性原理山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院 表示每個階段開場所處的自然情況或客觀條件。表示每個階段開場所處的自然情況或客

5、觀條件。又稱不可控要素。描畫過程形狀的變量稱為形狀變又稱不可控要素。描畫過程形狀的變量稱為形狀變量，用量，用si 表示。顯然，表示。顯然，si 既是階段既是階段i-1的終了形的終了形狀，又是階段狀，又是階段 i 的起始形狀。的起始形狀。 將整個系統(tǒng)過程恰當(dāng)?shù)胤譃榧僭O(shè)干個相互聯(lián)絡(luò)的將整個系統(tǒng)過程恰當(dāng)?shù)胤譃榧僭O(shè)干個相互聯(lián)絡(luò)的階段，以便能按一定的次序求解。描畫階段的變量稱階段，以便能按一定的次序求解。描畫階段的變量稱為階段變量，常用為階段變量，常用i 表示。階段數(shù)用表示。階段數(shù)用n表示。表示。(2)形狀形狀State (1)階段階段Stage6.1 動態(tài)規(guī)劃的根本原理和根本方程動態(tài)規(guī)劃的根本原理和根

6、本方程 6.1.2 動態(tài)規(guī)劃的根本概念動態(tài)規(guī)劃的根本概念山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院(3)決策決策Decision (4)戰(zhàn)略戰(zhàn)略Policy各階段的決策組成的一個決策序列稱為各階段的決策組成的一個決策序列稱為一個戰(zhàn)略，記為：一個戰(zhàn)略，記為： nxxxp,21 從階段從階段i開場的過程，稱為開場的過程，稱為i子過程，它包含階段子過程，它包含階段i，階，階段段i+1，階段，階段n。i子過程的決策序列稱為子過程的決策序列稱為i子戰(zhàn)略，記子戰(zhàn)略，記為為1,2, 1,1nixxxpniii6.1 動態(tài)規(guī)劃的根本原理和根本方程動態(tài)規(guī)劃的根本原理和根本方程 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理

7、學(xué)院 階段目的階段目的(或階段收益或階段收益)，是衡量每一階段決策優(yōu)劣，是衡量每一階段決策優(yōu)劣的數(shù)量目的。目的函數(shù)是衡量全過程戰(zhàn)略或的數(shù)量目的。目的函數(shù)是衡量全過程戰(zhàn)略或i子過程戰(zhàn)子過程戰(zhàn)略優(yōu)劣的數(shù)量目的略優(yōu)劣的數(shù)量目的,目的函數(shù)的最優(yōu)值稱為最優(yōu)目的函目的函數(shù)的最優(yōu)值稱為最優(yōu)目的函數(shù)，記為數(shù)，記為 f1(s1) 或或 fi (si)。5形狀轉(zhuǎn)移方程形狀轉(zhuǎn)移方程 由某一階段的一個形狀到下一階段的另一形狀的演由某一階段的一個形狀到下一階段的另一形狀的演化稱為形狀轉(zhuǎn)移。描畫形狀轉(zhuǎn)移規(guī)律的方程稱為形狀轉(zhuǎn)化稱為形狀轉(zhuǎn)移。描畫形狀轉(zhuǎn)移規(guī)律的方程稱為形狀轉(zhuǎn)移方程。記為移方程。記為si+1 = gi (si

8、, xi)gi稱為形狀轉(zhuǎn)移函數(shù)。稱為形狀轉(zhuǎn)移函數(shù)。6階段目的、目的函數(shù)、最優(yōu)目的函數(shù)階段目的、目的函數(shù)、最優(yōu)目的函數(shù)6.1 動態(tài)規(guī)劃的根本原理和根本方程動態(tài)規(guī)劃的根本原理和根本方程 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.1 動態(tài)規(guī)劃的根本原理和根本方程動態(tài)規(guī)劃的根本原理和根本方程 6.1.3 動態(tài)規(guī)劃的根本方程動態(tài)規(guī)劃的根本方程(1) 動態(tài)規(guī)劃的根本方程動態(tài)規(guī)劃的根本方程(逆序遞推公式逆序遞推公式)1 , 1,)(),()(1*1*nnisfxsvoptsfiiiixiii),(1iiixsgs，0)(1*1nnxf(2) 動態(tài)規(guī)劃的根本方程動態(tài)規(guī)劃的根本方程(正序遞推公式正序遞推公式)

9、nisfxsvoptsfiiiixiii, 2 , 1)(),()(1*1*),(1iiixsgs，),()(111*11xsvoptsfx山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.1 動態(tài)規(guī)劃的根本原理和根本方程動態(tài)規(guī)劃的根本原理和根本方程 6.1.4 建立動態(tài)規(guī)劃的數(shù)學(xué)模型建立動態(tài)規(guī)劃的數(shù)學(xué)模型1劃分階段劃分階段 按照時(shí)間、空間、變量等進(jìn)展劃分。按照時(shí)間、空間、變量等進(jìn)展劃分。2確定形狀變量確定形狀變量Si和形狀集合和形狀集合3確定決策變量確定決策變量xi及允許決策集合及允許決策集合4建立形狀轉(zhuǎn)移方程建立形狀轉(zhuǎn)移方程 si-1= g(si, xi) 或或 si+1= g(si, xi)5

10、確定各階段的階段收益確定各階段的階段收益6確定目的函數(shù)，建立動態(tài)規(guī)劃的根本方程確定目的函數(shù)，建立動態(tài)規(guī)劃的根本方程7確定邊境條件確定邊境條件山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.1 動態(tài)規(guī)劃的根本原理和根本方程動態(tài)規(guī)劃的根本原理和根本方程 6.1.5 動態(tài)規(guī)劃的求解動態(tài)規(guī)劃的求解(1) 動態(tài)規(guī)劃求解的根本方程動態(tài)規(guī)劃求解的根本方程(逆序遞推公式逆序遞推公式)1 , 1,)(),()(1*1*nnisfxsvoptsfiiiixiii),(1iiixsgs，0)(1*1nnxf(2) 動態(tài)規(guī)劃的求解的根本方程動態(tài)規(guī)劃的求解的根本方程(正序遞推公式正序遞推公式)nisfxsvoptsfiii

11、ixiii, 2 , 1)(),()(1*1*),(1iiixsgs，),()(111*11xsvoptsfx山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.1 動態(tài)規(guī)劃的根本原理和根本方程動態(tài)規(guī)劃的根本原理和根本方程 6.1.5 動態(tài)規(guī)劃的求解動態(tài)規(guī)劃的求解子問題n即原問題子問題 n-1子問題 2子問題 1解題方向階段1，階段2，階段n-1，階段n過程開展方向 動態(tài)規(guī)劃算法的基本思路動態(tài)規(guī)劃算法的基本思路山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.1 動態(tài)規(guī)劃的根本原理和根本方程動態(tài)規(guī)劃的根本原理和根本方程 6.1.5 動態(tài)規(guī)劃的求解動態(tài)規(guī)劃的求解例：用動態(tài)規(guī)劃方法例：用動態(tài)規(guī)劃方法(逆序遞推公

12、式逆序遞推公式)求解下面求解下面問題問題 A B1 B2 C1 C2 C3 D 4 6 5 5 3 4 6 1 5 3 6 試確定一條由試確定一條由A到到D的最短鋪設(shè)管道道路。的最短鋪設(shè)管道道路。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院解：整個計(jì)算過程分為三個階段來進(jìn)展，首先從最后一個階段開場按照逆序算法進(jìn)展計(jì)算。 第三階段：找出第三階段各起點(diǎn)C1, C2, C3到終點(diǎn)D的最短道路。 在第三階段，由始點(diǎn)C1, C2, C3到終點(diǎn)D的可行道路是獨(dú)一的，因此有 DCCfDCCfDCCf3332231136)(3)(5)(，最短路線為，最短路線為，最短路線為 A B1 B2 C1 C2 C3 D 4

13、 6 5 5 3 4 6 1 5 3 6 6.1 動態(tài)規(guī)劃的根本原理和根本方程動態(tài)規(guī)劃的根本原理和根本方程 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院 A B1 B2 C1 C2 C3 D 4 6 5 5 3 4 6 1 5 3 6 第二階段：找出第二階段的始點(diǎn)第二階段：找出第二階段的始點(diǎn)B1, B2B1, B2到終點(diǎn)到終點(diǎn)D D的最短道路。的最短道路。 835633555min)(),()(),()(),(min)(33312232121311212CfCBXCfCBXCfCBXBf最短道路為B1C2D。 761613554min)(),()(),()1()1,(min)(3332223222

14、32222CfCBXCfCBXCfCBXBf最短道路B2C3D。 6.1 動態(tài)規(guī)劃的根本原理和根本方程動態(tài)規(guī)劃的根本原理和根本方程 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院 A B1 B2 C1 C2 C3 D 4 6 5 5 3 4 6 1 5 3 6 第一階段：找出第一階段的起點(diǎn)第一階段：找出第一階段的起點(diǎn)A A到終點(diǎn)到終點(diǎn)D D的的最短道路最短道路 12847684min)(),()(),(min)(222112111BfBAXBfBAXAf于是得到該問題的最優(yōu)戰(zhàn)略為3 , 5 , 4,*3*2*1xxxp即最短道路為AB1C2D，相應(yīng)的最短間隔為12。6.1 動態(tài)規(guī)劃的根本原理和根本方

15、程動態(tài)規(guī)劃的根本原理和根本方程 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.2 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題 l6.2.1 問題描畫 l6.2.2 靜態(tài)規(guī)劃模型l6.2.3 動態(tài)規(guī)劃模型及其求解山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.2.1 問題描畫問題描畫6.2 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題 有某種機(jī)器有某種機(jī)器Q Q臺臺 可以在高、低兩種負(fù)荷下安排消費(fèi)可以在高、低兩種負(fù)荷下安排消費(fèi) 機(jī)器的月完好率分別為機(jī)器的月完好率分別為a(a(高負(fù)荷高負(fù)荷) )與與 b (b (低負(fù)荷低負(fù)荷) ) 每臺機(jī)器的月收益分別為每臺機(jī)器的月收益分別為c (c (高負(fù)荷高負(fù)荷) )和和d (d (低負(fù)

16、荷低負(fù)荷) ) 。 要求要求: :制定延續(xù)幾個月的消費(fèi)方案，制定延續(xù)幾個月的消費(fèi)方案，合理分配機(jī)器負(fù)荷，使總收益為最高。合理分配機(jī)器負(fù)荷，使總收益為最高。 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.2.2 靜態(tài)規(guī)劃模型靜態(tài)規(guī)劃模型6.2 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題 設(shè)xij為第j月在第i種負(fù)荷下安排消費(fèi)的機(jī)器臺數(shù)，其中i=1表示高負(fù)荷，i=2表示底負(fù)荷，j=1,2,n無妨假設(shè)方案期是從1月份開場，那么根據(jù)題意，可以建立下面的線性規(guī)劃模型 且為整數(shù), 0)(max1,21, 12122122313211122122111121ijnnnnnjjjxbxaxxxbxaxxxbxaxxxQx

17、xdxcxf山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.2.3 動態(tài)規(guī)劃模型及其求解動態(tài)規(guī)劃模型及其求解6.2 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題 設(shè)：設(shè)：Q=100臺，臺，a=0.5，b=0.8，c=10萬元，萬元，d=6萬元，萬元，n=4個個月。月。 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院max6.2 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院求解過程求解過程6.2 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院即，前兩個月全部安排低負(fù)荷消費(fèi)，后兩個月全部安排高負(fù)荷消費(fèi)，這樣可以獲得最高總收益2040萬元。 6.2 機(jī)器負(fù)荷分配問

18、題機(jī)器負(fù)荷分配問題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院,6.2 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.3 資源分配問題資源分配問題 l6.3.1 問題描畫 l6.3.2 靜態(tài)規(guī)劃模型l6.3.3 動態(tài)規(guī)劃模型及其求解山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.3.1 問題描畫問題描畫6.3 資源分配問題資源分配問題 設(shè)有數(shù)量為a的資源，方案分配給n個工程。設(shè)xi (i=1, 2, , n)為分配給第i個工程的資源量，gi(xi)為第i個工程得到數(shù)量為xi的資源后可提供的收益，問如何分配資源a，可使總收益為最高？ 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理

19、學(xué)院6.3.2 靜態(tài)規(guī)劃模型靜態(tài)規(guī)劃模型6.3 資源分配問題資源分配問題 nixaxxgfiniiniii,.,2, 1,0)(max11山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.3.3 動態(tài)規(guī)劃模型及其求解動態(tài)規(guī)劃模型及其求解6.3 資源分配問題資源分配問題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院 例： 某工業(yè)部門擬將40萬元的資金分配給4個工廠供擴(kuò)建用。各個工廠獲得投資可提高的利潤如下表所列。試確定使總利潤為最大的資金分配方案。 利潤0102030400205065800204050550254585100030405060 投資工廠 各個工廠運(yùn)用資金可提供利潤情況各個工廠運(yùn)用資金可提

20、供利潤情況 單位：萬元單位：萬元6.3 資源分配問題資源分配問題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院求解過程求解過程 分析：這個問題屬于資源分配問題，這里的資源是分析：這個問題屬于資源分配問題，這里的資源是資金。設(shè)資金的分配是以資金。設(shè)資金的分配是以10萬元為單位的，故萬元為單位的，故xi的的取值為取值為0，10，si 。 把該問題分為四個階段來思索：把該問題分為四個階段來思索： 6.3 資源分配問題資源分配問題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院niixisifixigisixisif, 2 , 1,)(1)(0max)(6.3 資源分配問題資源分配問題 山東理工大學(xué)管理學(xué)院山東

21、理工大學(xué)管理學(xué)院6.3 資源分配問題資源分配問題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.3 資源分配問題資源分配問題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院niixisifixigisixisif, 2 , 1, )(1)(0max)(6.3 資源分配問題資源分配問題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.3 資源分配問題資源分配問題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.3 資源分配問題資源分配問題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院niixisifixigisixisif, 2 , 1,)(1)(0max)(6.3 資源分配問題資源分配問題 山東理工大學(xué)管理學(xué)院山

22、東理工大學(xué)管理學(xué)院6.4 背包問題背包問題 l6.4.1 問題描畫 l6.4.2 靜態(tài)規(guī)劃模型l6.4.3 動態(tài)規(guī)劃模型及其求解山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.4.1 問題描畫問題描畫6.4 背包問題背包問題 背包問題的原始意義：一個游覽者要從n種物品的每一種中挑選假設(shè)干件裝入他的背包中，知第i種物品的分量及價(jià)值分別為ai和ci (i=1, 2, n)，又知這位游覽者所能接受的最大分量為a。問他應(yīng)如何選擇這n種物品的件數(shù)，才干使得價(jià)值為最大？ 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.4.2 靜態(tài)規(guī)劃模型靜態(tài)規(guī)劃模型6.4 背包問題背包問題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)

23、院6.4.3 動態(tài)規(guī)劃模型及其求解動態(tài)規(guī)劃模型及其求解6.4 背包問題背包問題 iiiniiiisxaasxass0 ,1山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院 例： 用動態(tài)規(guī)劃方法求解以下的背包問題 6.4 背包問題背包問題 3211258maxxxxf5523321xxx0,321xxx，且為整數(shù)山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院求解過程求解過程把該問題分為三個階段來思索：把該問題分為三個階段來思索： 6.4 背包問題背包問題 分析：這個問題屬于背包問題，其中分析：這個問題屬于背包問題，其中n=3，a=5，我們的問題是求我們的問題是求)5(3f)55(12max)5(max)5(3

24、2355033233503333xfxxafxcfxax第三階段：第三階段： )0(12)5(0max)55(12max223231 , 03ffxfxx第二階段：第二階段： ) 1 (10) 3(5)5(0max)25(5max)25(5max)5(max)5(1112122 . 1 , 0212250221225022222fffxfxxfxxafxcfxxax)0(max)0(22122100222xafxcfax)0()0(0)20(5max1121202ffxfxx山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.4 背包問題背包問題 第一階段：第一階段： 1,818)3/5(8)/5()

25、5(*1111xINTaINTcf1,818)3/3(8)/3()3(*1111xINTaINTcf0,008)3/1 (8)/1 () 1 (*1111xINTaINTcf0,008)/0()0(*1111xaINTcf 如今回過頭來求如今回過頭來求 和和 )5(2f)0(2f ) 1 , 1 (),(ax) 1 (10) 3(5)5(0max)5(*2*11112xxffff）（）0,0,(,0)0()0(*2*112xxff 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.4 背包問題背包問題 最后，再計(jì)算)5(3f）（0, 1 , 1),

26、ax)0(12)5(0max)5(*3*2*1223xxxfff故該背包問題的最優(yōu)解為 0, 1, 1321xxx相應(yīng)的目的函數(shù)最大值為13。山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.5 延續(xù)型動態(tài)規(guī)劃問題延續(xù)型動態(tài)規(guī)劃問題 l6.5.1 問題描畫 l6.5.2 延續(xù)型動態(tài)規(guī)劃模型及其求解l作業(yè)山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.5.1 問題描畫問題描畫6.5 延續(xù)型動態(tài)規(guī)劃問題延續(xù)型動態(tài)規(guī)劃問題 動態(tài)規(guī)劃按其形狀變量的取值情況動態(tài)規(guī)劃按其形狀變量的取值情況可以分為離散型和延續(xù)型?？梢苑譃殡x散型和延續(xù)型。 假設(shè)形狀變量取值為離散數(shù)據(jù)，那假設(shè)形狀變量取值為離散數(shù)據(jù)，那么稱為離散型動態(tài)規(guī)

27、劃；么稱為離散型動態(tài)規(guī)劃； 假設(shè)形狀變量取值為延續(xù)數(shù)據(jù)，那假設(shè)形狀變量取值為延續(xù)數(shù)據(jù)，那么稱為延續(xù)型動態(tài)規(guī)劃。么稱為延續(xù)型動態(tài)規(guī)劃。 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院1 , 1,)(),()(1*1*nnisfxsvoptsfiiiixiii),(1iiixsgs，0)(1*1nnxfnisfxsvoptsfiiiixiii, 2 , 1)(),()(1*1*),(1iiixsgs，),()(111*11xsvoptsfx(1) 延續(xù)型動態(tài)規(guī)劃的根本方程延續(xù)型動態(tài)規(guī)劃的根本方程(逆序遞推公式逆序遞推公式)(2) 延續(xù)型動態(tài)規(guī)劃的根本方程延續(xù)型動態(tài)規(guī)劃的根本方程(正序遞推公式正序遞推公式)6.5 延續(xù)型動態(tài)規(guī)劃問題延續(xù)型動態(tài)規(guī)劃問題 6.5.2 延續(xù)型動態(tài)規(guī)劃模型及其求解延續(xù)型動態(tài)規(guī)劃模型及其求解山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院 例： 用動態(tài)規(guī)劃方法求解以下的非線性規(guī)劃問題 6.5.2 延續(xù)型動態(tài)規(guī)劃模型及其求解延續(xù)型動態(tài)規(guī)劃模型及其求解6.5 延續(xù)型動態(tài)規(guī)劃問題延續(xù)型動態(tài)規(guī)劃問題 0,16442max3213212321xxxxxxxxxf山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院求解過程求解過程6.5 延續(xù)型動態(tài)規(guī)劃問題延續(xù)型動態(tài)規(guī)劃問題 山東理工大學(xué)管理學(xué)院山東理工大學(xué)管理學(xué)院6.5 延續(xù)型動態(tài)規(guī)劃問題延續(xù)型