多目標(biāo)、動態(tài)優(yōu)化

1、系統(tǒng)分析方法,office: e414 tel: 26035291(o) mobile:email: 2006,第6講 多目標(biāo)、動態(tài)優(yōu)化,一 多目標(biāo)優(yōu)化 二 目標(biāo)規(guī)劃 三 動態(tài)優(yōu)化,一 多目標(biāo)優(yōu)化,多目標(biāo)優(yōu)化模型 多目標(biāo)優(yōu)化解的性質(zhì) 多目標(biāo)優(yōu)化技術(shù)簡介,1.1 多目標(biāo)優(yōu)化模型,決策變量 x（x1，x2， xn） 目標(biāo)函數(shù) zf(x1，x2， xn) 約束條件 g1(x1，x2， xn) gm(x1，x2， xn,系統(tǒng)優(yōu)化模型一般形式,單目標(biāo)優(yōu)化與多目標(biāo)優(yōu)化,單目標(biāo)優(yōu)化： max(min)z=f (x1，x2，xn) 系統(tǒng)期望達到的目標(biāo)可用一個函數(shù)來表達,多目標(biāo)優(yōu)化：

2、max(min)z1=f1 (x1，x2，xn) max(min)z 2 =f 2(x1，x2，xn) max(min)z m =f m(x1，x2，xn) 系統(tǒng)期望達到的m個目標(biāo)應(yīng)該分別用m個函數(shù)來表達,線性多目標(biāo)優(yōu)化,如果多目標(biāo)優(yōu)化問題的所有目標(biāo)和約束條件都可用線性方程來表達，則為線性多目標(biāo)問題，其目標(biāo)函數(shù)可表達為,1.2 多目標(biāo)優(yōu)化問題解的性質(zhì),單目標(biāo)問題中，各種方案的目標(biāo)函數(shù)值具有可比性，可以分出優(yōu)劣，因此一般存在最優(yōu)解 多目標(biāo)問題中，對某個目標(biāo)的“優(yōu)化”可能導(dǎo)致其它目標(biāo)的“劣化” ，因此，一般不存在能夠同時滿足各個目標(biāo)最優(yōu)化的最優(yōu)解 多目標(biāo)優(yōu)化問題的求解，除了要“優(yōu)化”單個目標(biāo)本身，

3、還要平衡各個目標(biāo)間的關(guān)系，因此，多目標(biāo)優(yōu)化問題的解是經(jīng)過各目標(biāo)權(quán)衡后相對滿意的方案,1.3 多目標(biāo)規(guī)劃求解技術(shù)簡介,一般思路為：采取某種方式，平衡各個目標(biāo)間的關(guān)系，將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為單目標(biāo)規(guī)劃問題去處理。平衡的技術(shù)有： 效用最優(yōu)化模型 罰款模型 目標(biāo)規(guī)劃模型 約束模型,1）效用最優(yōu)化模型,按一定方式，將一系列的目標(biāo)函數(shù)與效用函數(shù)建立相關(guān)關(guān)系，對各效用函數(shù)加權(quán)求和，以該和函數(shù)作為的單目標(biāo)規(guī)劃問題的目標(biāo)函數(shù),目標(biāo)函數(shù) fi (x,效用函數(shù) i (x,式中，是與各目標(biāo)函數(shù)相關(guān)的效用函數(shù)的和函數(shù)；權(quán)值i來反映原問題中各目標(biāo)函數(shù)在總體目標(biāo)中的權(quán)重，滿足,效用函數(shù)效益型,效用函數(shù)成本型,效用函數(shù)區(qū)間型

4、,2）罰款模型,如果對每一個目標(biāo)函數(shù)，決策者都能提出一個期望值（或稱滿意值）f *i ，那么，可通過比較實際值與期望值 f *i 之間的偏差來構(gòu)造單目標(biāo)問題,在上式中，i 是與第i個目標(biāo)函數(shù)相關(guān)的權(quán)重,3）目標(biāo)規(guī)劃模型,目標(biāo)規(guī)劃模型與罰款模型類似，它也需要預(yù)先確定各個目標(biāo)的期望值 f *i,4）約束模型,如果規(guī)劃問題的某一目標(biāo)可以給出一個可供選擇的范圍，則該目標(biāo)就可以作為約束條件而被排除出目標(biāo)組，進入約束條件組中 假如，除了第一個目標(biāo)外，其余目標(biāo)都可以提出一個可供選的范圍，則,max(minz)=f1(x1,x2,xn,二 目標(biāo)規(guī)劃,目標(biāo)規(guī)劃由線性規(guī)劃發(fā)展演變而來 處理多目標(biāo)問題的簡單實用的方

5、法 目標(biāo)規(guī)劃與線性規(guī)劃問題的對比 目標(biāo)規(guī)劃問題的數(shù)學(xué)模型 目標(biāo)規(guī)劃求解方法 案例分析,2.1 目標(biāo)規(guī)劃與線性規(guī)劃問題的對比,線性規(guī)劃 單目標(biāo)問題 目標(biāo)值待求 追求目標(biāo)的最優(yōu)值（最大或最?。?目標(biāo)規(guī)劃 單或多目標(biāo)問題 目標(biāo)值（理想值、期望值）已知 追求盡可能接近理想值的解滿意解,例1,某廠生產(chǎn)甲、乙兩種產(chǎn)品，已知單件生產(chǎn)所需工時、可用工時數(shù)、及單件收益,1）從線性規(guī)劃角度考慮,lp： maxz=100x1 + 80x2,x* =(50,100) z* =13000,目標(biāo)：在現(xiàn)有資源條件下，追求最大收益,2）從目標(biāo)規(guī)劃角度考慮理想值,理想值（期望值）：去年總收益9000，期望增長11.1%，即希望

6、今年總收益達到10000 理想值已經(jīng)確定 允許計算值（決策值）小于或大于理想值 希望計算值與理想值之間的（負）差別盡可能小,2）從目標(biāo)規(guī)劃角度考慮正、負偏差,計算值與理想值之間三種可能： 計算值理想值，超過， d- = 0 計算值=理想值，相等， d+ = d- =0,因此：d+ * d- = 0 d+，d- 0,引入正、負偏差變量d+、d- d+：計算值超過理想值部分(正偏差變量) d-：計算值不足理想值部分(負偏差變量,100x1+80x2 -d+d- =10000,2）從目標(biāo)規(guī)劃角度考慮絕對約束與目標(biāo)約束,絕對約束：必須嚴(yán)格滿足的條件，不能滿足絕對約束的解即為非可行解,目標(biāo)約束：目標(biāo)規(guī)劃

7、所特有的一種約束，以目標(biāo)的理想值作為約束方程右端常數(shù)項，不必嚴(yán)格滿足，允許發(fā)生正負偏差,100x1+80x2 -d+d- =10000,2）從目標(biāo)規(guī)劃角度考慮目標(biāo)函數(shù),因為希望,100x1+80x2 -d+d- =10000,100x1+80x2 10000,也就是希望,d- 0,目標(biāo)函數(shù)為,minz= d,2）例1的目標(biāo)規(guī)劃模型,gp： min z= d- 100x1+80x2 -d+d- =10000 4x1+2x2 400 2x1+4x2 500 x1 , x2 , d- , d+ 0 d+ * d- =0,lp： max z=100x1 + 80x2 2x1+4x2 500 4x1+2

8、x2 400 x1 , x2 0,2.2 目標(biāo)規(guī)劃問題的數(shù)學(xué)模型,案例介紹 絕對約束與目標(biāo)約束 目標(biāo)函數(shù) 目標(biāo)優(yōu)先級 目標(biāo)權(quán)因子 小節(jié),例2,某工廠生產(chǎn)i、ii兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需要的原材料及占用設(shè)備臺時、每天擁有的設(shè)備臺時、原材料最大供應(yīng)量、單件產(chǎn)品可獲利潤,工廠在安排生產(chǎn)計劃的考慮,原材料情況：計劃使用原材料不能超過擁有量； 市場情況：產(chǎn)品銷售量有下降趨勢，期望產(chǎn)品的產(chǎn)量不超過產(chǎn)品的產(chǎn)量。 期望充分利用設(shè)備，但不希望加班。 期望達到利潤計劃指標(biāo)56千元,2x1+x2 11,x1 -x2 0,x1 +2x2 =10,8x1 +10x2 56,1）絕對約束與目標(biāo)約束,d1- : x1產(chǎn)量

9、不足x2 部分 d1+ : x1產(chǎn)量超過x2 部分 d2- : 設(shè)備使用不足10 部分 d2+ :設(shè)備使用超過10 部分 d3- : 利潤不足56 部分 d3+ :利潤超過56 部分,設(shè)x1 ，x2為產(chǎn)品，產(chǎn)品產(chǎn)量,2）目標(biāo)函數(shù),市場情況：產(chǎn)品銷售量有下降趨勢，期望產(chǎn)品的產(chǎn)量不超過產(chǎn)品的產(chǎn)量。 期望充分利用設(shè)備，但盡可能不加班。 期望達到利潤計劃指標(biāo)56千元,x1 -x2 0,x1 +2x2 =10,8x1 +10x2 56,x1 -x2 +d1- -d1+=0,x1 +2x2 +d2- -d2+=10,8x1 +10x2 +d3- -d3+=56,minz1 = d1,minz2 = d2-

10、 +d2,minz3 = d3,3）優(yōu)先級,在目標(biāo)規(guī)劃中，多個目標(biāo)之間往往有主次、緩急之區(qū)別 凡要求首先達到的目標(biāo)，賦予優(yōu)先級 p1 凡要求第二位達到的目標(biāo)，賦予優(yōu)先級 p2 優(yōu)化規(guī)則 只有完成了高級別的優(yōu)化后，再考慮低級別的優(yōu)化 再進行低級別的優(yōu)化時，不能破壞高級別以達到的優(yōu)化值,4）權(quán)因子,在同一優(yōu)先級中有幾個不同的偏差變量要求極小，而這幾個偏差變量之間重要性又有區(qū)別可用“權(quán)因子”來區(qū)分同一優(yōu)先級中不同偏差變量重要性不同，如 p2（2d2- + d2+） 表示d2- 的重要程度為d2+ 的兩倍，表明 “充分利用設(shè)備”的愿望 “不希望加班”的愿望 權(quán)因子的數(shù)值一般需要分析者與決策者商討確定,

11、例2的多目標(biāo)規(guī)劃模型,minz=p1d1+p2(2d2-+d2+)+p3(d3,2x1+x2 11 x1 -x2 +d1- -d1+=0 x1 +2x2 +d2- -d2+=10 8x1 +10x2 +d3- -d3+=56 x1 , x2 , di- , di+ 0,小結(jié),1）約束條件 硬約束(絕對約束) 軟約束 (目標(biāo)約束)，引入d -, d + 2）目標(biāo)優(yōu)先級與權(quán)因子 p1 p2 pl 同一級中可以有若干個目標(biāo)：p21 , p22 ,p23 其重要程度用權(quán)重系數(shù)w21 ,w22 ,w23 表示,目標(biāo)規(guī)劃的基本思想是，給定若干目標(biāo)以及實現(xiàn)這些目標(biāo)的優(yōu)先順序，在有限的資源條件下，使總的偏離目

12、標(biāo)值的偏差最小,小結(jié),3）目標(biāo)函數(shù)（準(zhǔn)則函數(shù)） 對目標(biāo)約束：fi(x) +di- -di+=gi,小結(jié),目標(biāo)函數(shù)的實質(zhì)：求一組決策變量的滿意值，使決策結(jié)果與給定目標(biāo)總偏差最小。 目標(biāo)函數(shù)的特點： 目標(biāo)函數(shù)中只有偏差變量 目標(biāo)函數(shù)總是求偏差變量最小 目標(biāo)函數(shù)值的含義： z=0：各級目標(biāo)均已達到 z0：部分目標(biāo)未達到,一般模型,2.3 目標(biāo)規(guī)劃的求解方法,序貫式算法 一種分解的算法，根據(jù)優(yōu)先級的先后次序，將原多目標(biāo)問題分解為一系列傳統(tǒng)的單目標(biāo)線性規(guī)劃問題，然后依次求解,1）序貫式算法的思路,令i=1，建立僅含p1級目標(biāo)的線性規(guī)劃單目標(biāo)模型：min z 1 (d-，d,利用單純形法求解 pi 級單目

13、標(biāo)規(guī)劃，得到min z i (d-，d+) = z*i,令i= i +1，建立僅含 pi 級目標(biāo)的線性規(guī)劃單目標(biāo)模型：min z i =z i (d-，d+)；同時考慮所有比 pi 高級別目標(biāo)相應(yīng)的約束條件；還要增加約束條件： z s(d-，d+) = z*s s = 1, 2, i-1,轉(zhuǎn)第2步，直到考慮完所有級別目標(biāo),第1步：構(gòu)造p1級目標(biāo)構(gòu)成的單目標(biāo)線性,minz= p1d1+p2(2d2-+d2+)+p3(d3-) 2x1+x2 11 x1 -x2 +d1- -d1+=0 x1 +2x2 +d2- -d2+=10 8x1 +10x2 +d3- -d3+=56 x1 , x2 , di-

14、 , di+ 0,minz1=d1+ 2x1+x2 11 x1 -x2 +d1- -d1+=0,在p1級只包含d1+ ，因此只取含有d1+的約束條件,絕對約束,第2步 求解 p1級單目標(biāo)規(guī)劃,minz1=d1+ 2x1+x2 11 x1 -x2 +d1- -d1+=0,計算結(jié)果：min z 1(d-，d+) = d1+ =0,第3步：構(gòu)造p2級目標(biāo)構(gòu)成的單目標(biāo)線性,上一級目標(biāo)所應(yīng)滿足的約束條件,本級目標(biāo)所應(yīng)滿足的約束條件,為保證優(yōu)化時p2，不破壞p1的最優(yōu)值而增加的約束條件,minz= p1d1+p2(2d2-+d2+)+p3(d3-) 2x1+x2 11 x1 -x2 +d1- -d1+=0

15、 x1 +2x2 +d2- -d2+=10 8x1 +10x2 +d3- -d3+=56 x1 , x2 , di- , di+ 0,minz2= 2d2-+d2+ 2x1+x2 11 x1 -x2 +d1- -d1+=0 x1 +2x2 +d2- -d2+=10 d1+ =0,minz2= 2d2-+d2+ 2x1+x2 11 x1 -x2 +d1- -d1+=0 x1 +2x2 +d2- -d2+=10 d1+ =0,第4步：求解 p2級單目標(biāo)規(guī)劃,minz2= 2d2-+d2+ 2x1+x2 11 x1 -x2 +d1- -d1+=0 x1 +2x2 +d2- -d2+=10 d1+ =

16、0,計算結(jié)果： min z 2(d-，d+) = 2d2-+d2+ =0,第5步：構(gòu)造p3級目標(biāo)構(gòu)成的單目標(biāo)線性,minz3= d3- 2x1+x2 11 x1 -x2 +d1- -d1+=0 x1 +2x2 +d2- -d2+=10 8x1 +10x2 +d3- -d3+=56 d1+ =0 2d2-+d2+ =0,較低級目標(biāo)所應(yīng)滿足的約束條件,本級目標(biāo)所應(yīng)滿足的約束條件,為保證優(yōu)化時p2，不破壞p1的最優(yōu)值而增加的約束條件,minz= p1d1+p2(2d2-+d2+)+p3(d3-) 2x1+x2 11 x1 -x2 +d1- -d1+=0 x1 +2x2 +d2- -d2+=10 8x

17、1 +10x2 +d3- -d3+=56 x1 , x2 , di- , di+ 0,第6步： 求解 p3級單目標(biāo)規(guī)劃,minz3= d3- 2x1+x2 11 x1 -x2 +d1- -d1+=0 x1 +2x2 +d2- -d2+=10 8x1 +10x2 +d3- -d3+=56 d1+ =0 2d2-+d2+ =0,計算結(jié)果： min z 3(d-，d+) = 0,例2結(jié)論,variable value d3- 0.0 x1 2.0 x2 4.0 d1- 0.0 d1+ 0.0 d2- 0.0 d2+ 0.0 d3+ 0.0,min z 1(d-，d+) = d1+ =0，第1優(yōu)先級：

18、期望產(chǎn)品的產(chǎn)量不超過產(chǎn)品的產(chǎn)量，得到滿足,min z 2(d-，d+) = 2d2-+d2+ =0，第2優(yōu)先級：期望充分利用設(shè)備，但盡可能不加班，得到滿足,min z3 (d-，d+) = d3- = 0，第3優(yōu)先級：期望達到利潤計劃指標(biāo)56千元,得到滿足,minz= p1d1+p2(2d2-+d2+)+p3(d3-) = 0,三 動態(tài)規(guī)劃,動態(tài)規(guī)劃引論 動態(tài)規(guī)劃的基本原理 動態(tài)規(guī)劃的基本方程 舉例,3.1 動態(tài)規(guī)劃引論,從案例說起 多階段決策問題與動態(tài)規(guī)劃,最短路徑問題,從a 地到d 地要鋪設(shè)一條煤氣管道,其中需經(jīng)過兩級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么路線，使

19、總距離最短,a,b1,b2,c1,c2,c3,d,2,4,3,3,3,3,2,1,1,1,4,機器負荷問題,某種機器可以在高低兩種不同的負荷下進行生產(chǎn)： 在高負荷下生產(chǎn)時，機器的年完好率為70%，且，產(chǎn)品的年產(chǎn)量=8*投入生產(chǎn)的機器數(shù)量 在低負荷下生產(chǎn)時，機器的年完好率為90%，且，產(chǎn)品的年產(chǎn)量=5*投入生產(chǎn)的機器數(shù)量 假定開始生產(chǎn)時完好的機器數(shù)量為1000 要求制定一個五年計劃,在每年開始時決定機器在兩種不同負荷下生產(chǎn)的數(shù)量，使五年內(nèi)產(chǎn)品的總產(chǎn)量最高,多階段決策問題與動態(tài)規(guī)劃,以上兩個問題都可以劃分為多個決策階段。 多階段決策問題：系統(tǒng)運行過程中可劃分為若干相繼的“階段”，每個階段都要進行決

20、策，并使整個過程達到最優(yōu)的一類問題。 階段：階段按時間、空間或其它特征劃分，且各階段相互聯(lián)系，某階段的結(jié)束是下一階段起始 問題的特征：某階段的最優(yōu)策略，而對下一階段未必最有利。為使整個過程效果最優(yōu)，必須將每階段作為整個決策鏈的一環(huán)，從整體考慮。 動態(tài)規(guī)劃：用來多階段決策過程優(yōu)化的一種數(shù)量方法,3.2 動態(tài)規(guī)劃的基本原理,上世紀(jì)50年代，美國數(shù)學(xué)家貝爾曼提出解決多階段決策問題的“最優(yōu)性原理” 假設(shè)采取了最優(yōu)策略，得到某個系統(tǒng)運動的最優(yōu)軌線，該最優(yōu)軌線將s（起點）和t（終點）連接。若在最優(yōu)軌線上取一點k，則子軌線k-s也是最優(yōu)的。 最優(yōu)策略的一部分也是最優(yōu)的,最優(yōu)性原理的應(yīng)用,從a 地到d 地要鋪

21、設(shè)一條煤氣管道,其中需經(jīng)過兩級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短,a,b1,b2,c1,c2,c3,d,2,4,3,3,3,3,2,1,1,1,4,解：整個計算過程分三個階段，從最后一個階段開始,第一階段（c d）： c 有三條路線到終點d,a,b1,b2,c1,c2,c3,d,2,4,3,3,3,3,2,1,1,1,4,d,c1,c2,c3,顯然有 f1 (c1 ) = 1 ； f1(c2 ) = 3 ； f1 (c3 ) = 4,第k階段從sk 到終點最短距離,第二階段（b1 c）： b1 到c有三條路線,a,b1,b2,c1,c2,c3,d

22、,2,4,3,3,3,3,2,1,1,1,4,d,c1,c2,c3,b1,b2,第二階段（b2 c）： b2到c有三條路線,a,b1,b2,c1,c2,c3,d,2,4,3,3,3,3,2,1,1,1,4,d,c1,c2,c3,b1,b2,第三階段（ a b ）： a 到b 有二條路線,f3(a)1 = d(a, b1 ) f2 ( b1 ) 246 f3 (a)2 = d(a, b2 ) f2 ( b2 ) 437,f3 (a) = min = min6,7=6,d(a, b1 ) f2 ( b1 ) d(a, b2 ) f2 ( b2,a,b1,b2,c1,c2,c3,d,2,4,3,3,

23、3,3,2,1,1,1,4,d,c1,c2,c3,b1,b2,3.3動態(tài)規(guī)劃的基本方程,基本概念 動態(tài)規(guī)劃基本方程 動態(tài)規(guī)劃的步驟,3.2.1基本概念,階段 狀態(tài)與狀態(tài)變量 決策 策略 狀態(tài)轉(zhuǎn)移方程 指標(biāo)函數(shù)和最優(yōu)值函數(shù),1）階段,階段（stage）把所研究的決策問題，按先后順序劃分為若干相互聯(lián)系的決策步驟，以便按一定的次序進行求解。 描述階段的變量稱階段變量，常用k表示,a,b1,b2,c1,c2,c3,d,2,4,3,3,3,3,2,1,1,1,4,d,c1,c2,c3,2）狀態(tài)與狀態(tài)變量,狀態(tài)（state）用sk表示階段k的起始狀態(tài)（或輸入狀態(tài)）；用sk+1表示階段k的結(jié)束狀態(tài)（或輸出狀

24、態(tài)） 狀態(tài)變量的取值有一定的允許集合或范圍，此集合稱為狀態(tài)允許集合 例如：最短路徑問題中，第2階段有二個輸入狀態(tài)，三個輸出狀態(tài),a,b1,b2,c1,c2,c3,d,2,4,3,3,3,3,2,1,1,1,4,d,c1,c2,c3,3）決策與決策變量,決策（decision）用xk表示從第k階段狀態(tài)sk到第k+1階段的狀態(tài)sk+1所采取的策略，它使活動過程從狀態(tài)sk轉(zhuǎn)變?yōu)閟k+1。 決策變量的取值往往在某一范圍之內(nèi)，此范圍稱為允許決策集合，可用dk(sk)表示,a,b1,b2,c1,c2,c3,d,2,4,3,3,3,3,2,1,1,1,4,c1,c2,c3,決策：x2(b1)=b1c1,允許

25、決策集合： d2(b1)=b1c1，b1c2 ，b1c3,4）策略,策略：是一個按順序排列的決策組成的集合。在實際問題中，可供選擇的策略有一定的范圍，稱為允許策略集合。從允許策略集合中找出達到最優(yōu)效果的策略稱為最優(yōu)策略,a,b1,b2,c1,c2,c3,d,2,4,3,3,3,3,2,1,1,1,4,c1,c2,c3,策略：ab1c1 d,5）狀態(tài)轉(zhuǎn)移方程,狀態(tài)轉(zhuǎn)移方程：是確定過程由一個狀態(tài)到另一個狀態(tài)的方程，描述了狀態(tài)轉(zhuǎn)移規(guī)律,a,b1,b2,c1,c2,c3,d,2,4,3,3,3,3,2,1,1,1,4,c1,c2,c3,u2(b1)=b1c1 s3=t2(b1,u2)=c1,討論：狀態(tài)

26、的無后效性,一般而言，系統(tǒng)某階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)當(dāng)前狀態(tài)和決策有關(guān)，而且還與系統(tǒng)的歷史狀態(tài)和決策有關(guān) 特殊的，系統(tǒng)狀態(tài)的轉(zhuǎn)移都只僅與前一時刻的狀態(tài)有關(guān)、而與過去的狀態(tài)無關(guān)，稱這樣的狀態(tài)具有“無后效性” 動態(tài)規(guī)劃解決“具有無后效性”的多階段決策問題,6）指標(biāo)函數(shù)和最優(yōu)值函數(shù),指標(biāo)函數(shù)又稱目標(biāo)函數(shù)，它用來表示系統(tǒng)所要實現(xiàn)的目標(biāo)，是衡量策略優(yōu)劣的尺度。 指標(biāo)函數(shù)的含義可能是距離、利潤、成本、產(chǎn)量或資源消耗等 衡量從k階段n階段決策過程總體效果的確定數(shù)量函數(shù)：vk,n 衡量第k階段決策效果的指標(biāo)：dk(sk,xk) 指標(biāo)函數(shù)vk,n最優(yōu)值最優(yōu)值函數(shù)：fk(sk,最短路徑問題中的指標(biāo)函數(shù),vk,n第

27、k階段從sk 到終點的距離 dk(sk,xk)從sk 到xk決策所指節(jié)點的距離 fk(sk)第k階段從sk 到終點最短距離,a,b1,b2,c1,c2,c3,d,2,4,3,3,3,3,2,1,1,1,4,c1,c2,c3,遞推方程式,這樣，就將原來的n階段決策問題化為一系列單變量優(yōu)化問題,fk(sk) opt dk(sk,xk)+fk+1(sk+1) opt dk(sk,xk)+fk+1(t(sk,xk) 0 xkdk,3.2.2 動態(tài)規(guī)劃基本方程,遞推方程式與狀態(tài)轉(zhuǎn)移方程式合稱為動態(tài)規(guī)劃基本方程,遞推方程式：fk(sk) opt dk(sk,xk)+fk+1(sk+1) 0 xkdk 狀態(tài)

28、轉(zhuǎn)移方程式：sk+1=t(sk,xk,3.2.3 動態(tài)規(guī)劃的步驟,1)將所研究問題的過程劃分為n個恰當(dāng)?shù)碾A段 (2)正確地選擇狀態(tài)變量sk，并確定初始狀態(tài)s1的值 (3)確定決策變量xk以及各階段的允許決策集dk(sk) (4) 給出狀態(tài)轉(zhuǎn)移方程； (5) 給出滿足要求的指標(biāo)函數(shù)vk,n及相應(yīng)的最優(yōu)值函 (6) 寫出遞推方程，建立基本方程； (7) 按照基本方程遞推求解,3.4舉例：機器負荷問題,某種機器可以在高低兩種不同的負荷下進行生產(chǎn)： 在高負荷下進行生產(chǎn)時，機器的年完好率為70%，且，產(chǎn)品的年產(chǎn)量=8*投入生產(chǎn)的機器數(shù)量 這時在低負荷下生產(chǎn)時，機器的年完好率為90%，且，產(chǎn)品的年產(chǎn)量=5

29、*投入生產(chǎn)的機器數(shù)量 假定開始生產(chǎn)時完好的機器數(shù)量為1000 要求制定一個五年計劃,在每年開始時決定機器在兩種不同負荷下生產(chǎn)的數(shù)量，使五年內(nèi)產(chǎn)品的總產(chǎn)量最高,機器負荷問題,x1,x2,x5,1)按年數(shù)劃分為5個階段，k=1,2,3,4,5,2)取第k年初完好的機器數(shù)sk為狀態(tài)變量, s1=1000,3)取第k年投入高負荷的機器數(shù)xk為決策變量, 0 xksk,4)狀態(tài)轉(zhuǎn)移方程為 sk+1=0.7xk+0.9(sk-xk)=0.9sk-0.2xk,5)指標(biāo)函數(shù)為vk,5=8xj+5(sj-xj)=(5sj+3xj,解,基本方程,6)基本方程為 fk(sk) max 5sk+3xk +fk+1(s

30、k+1) k=5,4,3,2,1 0 xksk f6(s6)0 根據(jù)狀態(tài)轉(zhuǎn)移方程：sk+1=0.9sk-0.2xk fk(sk) max 5sk+3xk +fk+1(0.9sk-0.2xk ) 因此基本方程fk最終可轉(zhuǎn)化為sk和xk的表達式,當(dāng)k=5時,基本方程為 fk(sk) max 5sj+3xj +fk+1(sk+1) 0 xksk f6(s6)0,當(dāng)k=5時， 0 x5s5,f5(s5) max5s5+3x5+f6(s6) max5s5+3x5 8s5 此時x5*=s5,當(dāng)k=4時,基本方程為 fk(sk) max 5sj+3xj +fk+1(sk+1) k=5,4,3,2,1 0 xksk f5(s5)