ychx4運籌學(xué)4

1、運籌學(xué),動態(tài)規(guī)劃,動態(tài)規(guī)劃的概念與模型,靜態(tài)決策 一次性決策,動態(tài)決策 多階段決策,多段決策過程,…,…,n個決策子問題K稱為階段變量xk描述k階段初的狀態(tài)，稱為狀態(tài)變量一般把輸入狀態(tài)稱為該階段的階段狀態(tài)。uk的取值代表k階段對第k子問題所進行的決策，稱為k階段的決策變量rk為k階段從狀況xk出發(fā),做決策uk之后的后果，稱為k階段的階段效應(yīng)。,具有無后效性的多段決策過程,Xk+1=Tk (xk, uk)系

2、統(tǒng)從k階段往后的決策只與k階段系統(tǒng)的狀態(tài)xk有關(guān),而與系統(tǒng)以前的決策無關(guān)，則稱為具有無后效性的多段決策過程。,K后部子過程,多段決策過程中從第k階段到最終階段的過程稱為k-后部子過程，簡稱k-子過程。,動態(tài)規(guī)劃模型,Opt表示求優(yōu)Xk是一個集合，表示k階段狀態(tài)可能取值的范圍，稱為狀態(tài)可能集合。Uk是一個集合，表示k階段決策可能取值的范圍，稱為決策允許集合，一般來說對于不同狀態(tài)，可以作的決策的范圍是不同的。因此決策允許集合一般寫為Uk

3、(xk)。,動態(tài)規(guī)劃的建模,動態(tài)規(guī)劃建模①確定階段與階段變量②明確狀態(tài)變量和狀態(tài)可能集合。③確定決策變量和決策允許集合。④確定狀態(tài)轉(zhuǎn)移方程。⑤明確階段效應(yīng)和目標。,動態(tài)規(guī)劃的建模,①確定階段與階段變量階段的劃分一般是按照決策進行的時間或空間上的先后順序劃分的，階段數(shù)等于多段決策過程中從開始到結(jié)束所需要作出決策的數(shù)目，階段變量用k表示。②明確狀態(tài)變量和狀態(tài)可能集合。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息

4、。狀態(tài)變量的確定決定了整個決策過程是不是具有無后效性，因而也決定著能不能用動態(tài)規(guī)劃方法來求解。狀態(tài)可能集是關(guān)于狀態(tài)的約束條件，因此為了求解必須正確地確定狀態(tài)可能集。,動態(tài)規(guī)劃的建模,③確定決策變量和決策允許集合。與靜態(tài)問題相同，決策變量應(yīng)能夠反映對問題所作的決策，決策變量也應(yīng)有其相應(yīng)的約束條件，在建模時應(yīng)明確決策允許集合Uk(xk)。④確定狀態(tài)轉(zhuǎn)移方程。系統(tǒng)k階段從狀態(tài)xk出發(fā)作了決策uk(xk)之后的結(jié)果之一是系統(tǒng)狀態(tài)的轉(zhuǎn)移，這

5、一結(jié)果直接影響系統(tǒng)往后的決策過程，因此必須明確狀態(tài)的轉(zhuǎn)移過程，即根據(jù)問題的內(nèi)在關(guān)系，明確xk+1=Tk(xk,uk)中的函數(shù)Tk（ ）。,動態(tài)規(guī)劃的建模,⑤明確階段效應(yīng)和目標。階段效應(yīng)rk(xk,uk)是在階段k以xk出發(fā)作了決策uk之后所產(chǎn)生的后果，必須明確rk與xk，uk的關(guān)系，才能構(gòu)成目標函數(shù)。目標函數(shù)是由階段效應(yīng)經(jīng)過某種集結(jié)而得到的，如何集結(jié)視具體問題而定，同時還應(yīng)根據(jù)問題確定目標是求最大還是最小。由于在經(jīng)濟系統(tǒng)中的大多數(shù)

6、情況下，目標的集結(jié)方法都是求和，因此，在不作說明的情況下，往后的討論都針對目標為和的形式進行。,動態(tài)規(guī)劃解的概念,多段決策過程中所要求解的是，從起始狀態(tài)x1開始，進行一系列的決策，使目標R達到最優(yōu)最優(yōu)目標值 R*,最優(yōu)策略 使得目標達到最優(yōu)的決策序列。,最優(yōu)路線 在采取最優(yōu)策略時，系統(tǒng)從x1開始所經(jīng)過的狀態(tài)序列,求解動態(tài)規(guī)劃模型 找到最優(yōu)策略、最優(yōu)路線和最優(yōu)目標值。,動態(tài)規(guī)劃最優(yōu)性原理,多段決策過程的

7、特點 每個階段都要進行決策 相繼進行的階段決策構(gòu)成的決策序列 前一階段的終止狀態(tài)又是后一階段的初始狀態(tài)階段最優(yōu)決策不能只從本階段的效應(yīng)出發(fā)，必須通盤考慮，整體規(guī)劃。階段k的最優(yōu)決策不應(yīng)該只是本階段效應(yīng)的最優(yōu)，而必須是本階段及其所有后續(xù)階段的總體最優(yōu)，即關(guān)于整個k后部子過程的最優(yōu)決策。,動態(tài)規(guī)劃最優(yōu)性原理,最優(yōu)性原理 “最優(yōu)策略具有的基本性質(zhì)是：無論初始狀態(tài)和初始決策如何，對于前面決策所造成的某一狀態(tài)而

8、言，下余的決策序列必構(gòu)成最優(yōu)策略”。,,動態(tài)規(guī)劃最優(yōu)性原理,最優(yōu)性原理的含意 最優(yōu)策略的任何一部分子策略，也是相應(yīng)初始狀態(tài)的最優(yōu)策略。 每個最優(yōu)策略只能由最優(yōu)子策略構(gòu)成。顯然，對于具有無后效性的多段決策過程而言，如果按照k后部子過程最優(yōu)的原則來求各階段狀態(tài)的最優(yōu)決策，那么這樣構(gòu)成的最優(yōu)決策序列或策略一定具有最優(yōu)性原理所提示的性質(zhì)。,貝爾曼函數(shù),貝爾曼函數(shù)fk(xk)： 在階段k從初始狀態(tài)

9、xk出發(fā)，執(zhí)行最優(yōu)決策序列或策略，到達過程終點時，整個k-子過程中的目標函數(shù)取值，稱為條件最優(yōu)目標函數(shù)，亦稱貝爾曼函數(shù)。,條件最優(yōu)策略 多段決策過程的任一階段狀態(tài)xk的最優(yōu)策略 處于條件xk時的最優(yōu)策略。條件最優(yōu)決策 構(gòu)成條件最優(yōu)策略的決策,貝爾曼函數(shù),條件最優(yōu)目標函數(shù)值fk(xk) 執(zhí)行條件最優(yōu)策略時的目標函數(shù)值,條件最優(yōu)路線 執(zhí)行條件最優(yōu)策略時的階段狀態(tài)序列

10、,貝爾曼函數(shù),條件最優(yōu)k-子策略 系統(tǒng)從xk出發(fā)，在k-后部子過程中的最優(yōu)策略k-子過程條件最優(yōu)目標函數(shù) fk(xk)是從xk出發(fā)系統(tǒng)在k-后部子過程中的最優(yōu)目標值，多段決策問題所求解的最優(yōu)目標函數(shù)值 R*=opt f1(x1*)動態(tài)規(guī)劃基本方程 fk(xk)與fk＋1(xk＋1)之間的遞推關(guān)系動態(tài)規(guī)劃方法的依據(jù)是最優(yōu)性原理,動態(tài)規(guī)劃基本方程,設(shè)在階段k的狀

11、態(tài)xk執(zhí)行了任意選定決策uk后的狀態(tài)是xk+1=Tk(xk,uk)。這時k-后部子過程就縮小為k+1后部子過程。根據(jù)最優(yōu)性原理，對k+1后部子過程應(yīng)采取最優(yōu)策略，由于無后效性，k后部子過程的目標函數(shù)值為,動態(tài)規(guī)劃基本方程,動態(tài)規(guī)劃基本方程,動態(tài)規(guī)劃方法基本原理,動態(tài)規(guī)劃方法基本原理,rk(xk, uk)和xk+1=Tk(xk, uk)都是已知的函數(shù)求fk(xk)需要首先求關(guān)于xk的所有k+1段狀態(tài)xk+1的fk+1(xk+1)逆序地

12、求出條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合狀態(tài)xk+1是由前面階段的狀態(tài)決定的用問題給定的初始條件，即可順序地求出整個多段決策問題的最優(yōu)目標函數(shù)值、最優(yōu)策略和最優(yōu)路線。,動態(tài)規(guī)劃問題求解的一般步驟,逆序地求出條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合k=n時，動態(tài)規(guī)劃基本方程是,邊界條件,k=n時的動態(tài)規(guī)劃基本方程成為,動態(tài)規(guī)劃問題求解的一般步驟,逆序地求出條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合k=n－1時，動態(tài)規(guī)劃的基本方程

13、是,所有的fn(xn)都已經(jīng)求出，因此可以根據(jù)xn=Tn-1(xn-1,un-1)就階段n-1每個可能狀態(tài)xn-1∈Xn-1求條件最優(yōu)決策及相應(yīng)的條件最優(yōu)目標函數(shù)值fn－1(xn－1),動態(tài)規(guī)劃問題求解的一般步驟,逆序地求出條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合k=1時，動態(tài)規(guī)劃的基本方程是,所有的f2(x2)都已經(jīng)求出，因此可以根據(jù)x2=T1(x1,u1)就階段1每個可能狀態(tài)x1∈X1求條件最優(yōu)決策及相應(yīng)的條件最優(yōu)目標函數(shù)值f

14、1(x1),動態(tài)規(guī)劃問題求解的一般步驟,逆序地求出條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合,,動態(tài)規(guī)劃問題求解的一般步驟,順序地求出最優(yōu)目標值、最優(yōu)策略和最優(yōu)路線若x1已知，則,階段1的條件最優(yōu)決策就是階段1的關(guān)于整個過程的最優(yōu)決策若x1未知,,,動態(tài)規(guī)劃問題求解的一般步驟,順序地求出最優(yōu)目標值、最優(yōu)策略和最優(yōu)路線,,,,,,,,動態(tài)規(guī)劃四大要素、一個方程,五個關(guān)鍵因素 四大要素、一個方程：①狀態(tài)變量及其可能集合②決策變量

15、及其允許集合③狀態(tài)轉(zhuǎn)移方程④階段效應(yīng)⑤動態(tài)規(guī)劃基本方程：,動態(tài)規(guī)劃應(yīng)用舉例----定步數(shù)問題,例4－1 某旅行者希望從s地起到t地，其間的道路系統(tǒng)如圖4－7所示，圖上圓圈表示途徑的地方，稱為節(jié)點，連結(jié)兩地的箭線表示道路，其上的數(shù)字表示該段道路長度，箭頭表示通行的方向。試求s到t的最短路。,動態(tài)規(guī)劃應(yīng)用舉例----定步數(shù)問題,第一階段 第二階段 第三階段劃分階段 k=1,2,3 代表

16、三個階段,動態(tài)規(guī)劃應(yīng)用舉例----定步數(shù)問題,狀態(tài)變量xk取為k階段所在地，則有：,動態(tài)規(guī)劃應(yīng)用舉例----定步數(shù)問題,k階段決策是決定下一步走到哪里，uk(xk)取為下一步的所在點。,動態(tài)規(guī)劃應(yīng)用舉例----定步數(shù)問題,逆序求條件最優(yōu)目標函數(shù)集和條件最優(yōu)決策集由于第3階段末已到達t，往后的距離自然是零，因此f4(t)=0對3階段所有可能的狀態(tài)X3={d, e, f}計算f3( )如下,動態(tài)規(guī)劃應(yīng)用舉例----定步數(shù)問題,逆序求條

17、件最優(yōu)目標函數(shù)集和條件最優(yōu)決策集也可以用表格方法計算如下,動態(tài)規(guī)劃應(yīng)用舉例----定步數(shù)問題,逆序求條件最優(yōu)目標函數(shù)集和條件最優(yōu)決策集,動態(tài)規(guī)劃應(yīng)用舉例----定步數(shù)問題,逆序求條件最優(yōu)目標函數(shù)集和條件最優(yōu)決策集對2階段所有可能的狀態(tài)X2={a, b, c}計算f2( )如下,動態(tài)規(guī)劃應(yīng)用舉例----定步數(shù)問題,逆序求條件最優(yōu)目標函數(shù)集和條件最優(yōu)決策集對2階段所有可能的狀態(tài)X2={a, b, c}計算f2( )如下,動態(tài)規(guī)劃應(yīng)

18、用舉例----定步數(shù)問題,逆序求條件最優(yōu)目標函數(shù)集和條件最優(yōu)決策集也可以用表格方法計算如下,動態(tài)規(guī)劃應(yīng)用舉例----定步數(shù)問題,逆序求條件最優(yōu)目標函數(shù)集和條件最優(yōu)決策集,動態(tài)規(guī)劃應(yīng)用舉例----定步數(shù)問題,逆序求條件最優(yōu)目標函數(shù)集和條件最優(yōu)決策集對1階段所有可能的狀態(tài)X1={s}計算f1( )如下,動態(tài)規(guī)劃應(yīng)用舉例----定步數(shù)問題,順序求最優(yōu)策略、最優(yōu)路線和最優(yōu)目標函數(shù)值,,,,,,,,動態(tài)規(guī)劃應(yīng)用舉例----定步數(shù)問題,逆序求

19、條件最優(yōu)目標函數(shù)集和條件最優(yōu)決策集,動態(tài)規(guī)劃應(yīng)用舉例----不定步數(shù)問題,例4－2,用f(i)表示I節(jié)點到t節(jié)點的最短距離，則根據(jù)動態(tài)規(guī)劃原理，應(yīng)該有：,動態(tài)規(guī)劃應(yīng)用舉例----不定步數(shù)問題,例4－2,可用迭代的方法來實現(xiàn)求解。迭代可以針對f( )來進行，稱為函數(shù)迭代法也可以針對策略{u(i)}(i=s, a, b, c, d)進行，稱為策略迭代法,不定步數(shù)問題----函數(shù)迭代法,函數(shù)迭代法步驟選定一初始函數(shù)f1(i),,然后用

20、遞推關(guān)系求{fk(i)},,fk(i)為從i點出發(fā)走k步到t的最短距離 ，若對于某個k，有fk+1(i)=fk(i)，對所有節(jié)點i成立，則fk( )即為條件最優(yōu)目標函數(shù)，求解結(jié)束。 否則重復(fù)上述過程，直至最優(yōu)。,不定步數(shù)問題----函數(shù)迭代法,例4－2,取,不定步數(shù)問題----函數(shù)迭代法,例4－2,不定步數(shù)問題----函數(shù)迭代法,例4－2,不定步數(shù)問題----策略迭代法,策略迭代法步驟： 1 給每個點i選擇一個下一步到達的點u0(

21、i)，i=s, a, b, c, d 取k=0,2 由,算出fk(i),3 由,解出,則已經(jīng)最優(yōu),否則繼續(xù)計算,若,不定步數(shù)問題----策略迭代法,例4－2,取,,,,,,不定步數(shù)問題----策略迭代法,例4－2,不定步數(shù)問題----策略迭代法,例4－2,,,,,,不定步數(shù)問題----策略迭代法,不定步數(shù)問題----策略迭代法,資源分配問題,資源的多元分配 設(shè)有某種資源，總量為M，可以投入n種生產(chǎn)活動。已知用于活動k的資源為uk

22、時的收益是gk(uk)，問應(yīng)如何分配資源，使n種生產(chǎn)活動的總收益最大。這種問題就是資源的多元分配問題。,資源分配問題,資源的多元分配 如果將n種活動作為一個互相銜接的整體，對一種活動的資源分配作為一個階段，每個階段確定對一種活動的資源投放量。則該問題成為一個多段決策問題。狀態(tài)變量xk的選取原則是要能夠據(jù)此確定決策uk，以及滿足狀態(tài)轉(zhuǎn)移方程所要求的無后效性。在資源分配問題中，決策變量選為對活動k的資源投放量，因此狀態(tài)變量可以選擇為階

23、段k初所擁有的資源量，即將要在第k種到第n種活動間分配的資源量。,資源的多元分配,關(guān)于狀態(tài)變量xk的約束條件是 0≤xk≤M關(guān)于決策變量uk的約束條件是 0≤uk≤xk 狀態(tài)轉(zhuǎn)移方程為 xk+1=xk-uk 顯然它滿足無后效性要求。階段效應(yīng)為對活動k投放資源uk時的收益， rk(xk, uk)=gk(uk)目標函數(shù)是為n種活動投放資源后的總收益動態(tài)規(guī)劃基本方程,資源的多元分配,例4－

24、3 某公司擬將50萬元資金投放下屬A、B、C三個部門，各部門在獲得資金后的收益如表所示，用動態(tài)規(guī)劃方法求總收益最大的投資分配方案（投資數(shù)以10萬元為單位）。,資源的多元分配,解 該問題可以作為三段決策過程。對A、B、C三個部門分配資金分別形成1，2，3三個階段。xk表示給部門k分配資金時擁有的資金數(shù)。uk表示給部門k分配的資金數(shù)（以10萬元為單位）。狀態(tài)轉(zhuǎn)移方程是xk+1=xk-uk。階段效應(yīng)如表所示。目標函數(shù)是階段效應(yīng)求和。,資源

25、的多元分配,首先逆序求條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合。,從表可知g3( )是單調(diào)遞增的函數(shù)，因此，當(dāng)u3=x3時達到最大。即：,資源的多元分配,逆序求條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合。,資源的多元分配,逆序求條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合。,資源的多元分配,逆序求條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合。k=2時，0≤x2≤5 0≤u2≤x2,資源的多元分配,逆序求條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決

26、策集合。k=2時，0≤x2≤5 0≤u2≤x2,資源的多元分配,逆序求條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合。當(dāng)k=1時，有x1=5，0≤u1≤x1=5,資源的多元分配,逆序求條件最優(yōu)目標函數(shù)值集合和條件最優(yōu)決策集合。當(dāng)k=1時，有x1=5，0≤u1≤x1=5,資源的多元分配,順序求最優(yōu)目標函數(shù)值和最優(yōu)策略、最優(yōu)路線,,,,,,,,,資源的多段分配,將一種有消耗性的資源，多階段地在多種不同的生產(chǎn)活動中投放的問題稱為資源的多

27、段分配問題，下面討論其中包含有兩個生產(chǎn)活動的簡單情況。設(shè)有某種資源，初始的擁有量是M。計劃在A，B兩個生產(chǎn)部門連續(xù)使用n個階段。已知在部門A投入資源uA時的階段收益是g(uA)，在部門B投入資源uB時的階段收益是h(uB)。又資源在生產(chǎn)中將有部分消耗，已知每生產(chǎn)一個階段后部門A，B中的資源完好率分別為a和b，0<(a, b)<1。求n階段間總收益最大的資源分配計劃。,資源的多段分配,n段決策過程狀態(tài)變量xk為階段k初擁有

28、的資源量，0≤xk≤M，x1=M決策變量選為階段k在部門A的資源投放量，即uA=uk，這里顯然有uB=xk- uk，決策變量的約束條件是 0≤uk≤xk即最多將所擁有的資源都投入部門A，其時uB=0階段k末部站A的剩余資源auk，部門B中則為b(xk-uk)，因此狀態(tài)轉(zhuǎn)移方程xk+1=T(xk, uk)是 xk+1=auk+b(xk-uk) 滿足無后效性階段效應(yīng)rk(xk, uk)即階段收益rk(xk, uk)=g(uk

29、)+h(xk-uk)目標函數(shù)是n個階段的總收益，即階段效應(yīng)求和。,資源的多段分配,例4－4 今有1000臺機床，要投放到A、B兩個生產(chǎn)部門，計劃連續(xù)使用3年。已知對A部門投入uA臺機器時的年收益是g(uA)=4(uA)2（元），機器完好率a=0.5，相應(yīng)的B部門的年收益是h(uB)=2(uB)2 （元），完好率b= 0.9。試求使3年間總收益最大的年度機器分配方案。 解 以每年作為一個階段，設(shè)狀態(tài)變量和決策變量都是連續(xù)取值的。

30、K階段狀態(tài)變量xk取為該年度初完好的設(shè)備數(shù)，決策變量取為該年度投入A活動的設(shè)備數(shù)，則有 0≤xk≤1000， 0≤uk≤xk狀態(tài)轉(zhuǎn)移方程為：xk+1=0.5uk+0.9(xk-uk),資源的多段分配,例4－4解 以每年作為一個階段，設(shè)狀態(tài)變量和決策變量都是連續(xù)取值的。K階段狀態(tài)變量xk取為該年度初完好的設(shè)備數(shù)，決策變量取為該年度投入A活動的設(shè)備數(shù)，則有 0≤xk≤1000，

31、 0≤uk≤xk狀態(tài)轉(zhuǎn)移方程為：xk+1=0.5uk+0.9(xk-uk)動態(tài)規(guī)劃基本方程,資源的多段分配,逆序求條件最優(yōu)目標函數(shù)值fk(xk)和條件最優(yōu)決策k=3時，0≤u3≤x3，注意到f4(x4)=0，有,k=2時，0≤u2≤x2，有,資源的多段分配,逆序求條件最優(yōu)目標函數(shù)值fk(xk)和條件最優(yōu)決策k=1時，0≤u1≤x1，x2=0.5u1+0.9(x1-u1)，f2(x2),,,,,,,,串聯(lián)系統(tǒng)可靠性問題,系統(tǒng)

32、可靠性是指系統(tǒng)在規(guī)定的條件下能正常工作的概率，它是管理和工程技術(shù)設(shè)計中經(jīng)常要研究的問題。這兒要研究的是串聯(lián)系統(tǒng)可靠性問題。例如某種儀器設(shè)備由N個部件串聯(lián)構(gòu)成，凡其中有一個部件出現(xiàn)故障，則整個系統(tǒng)便不能正常工作。為了提高系統(tǒng)工作的可靠性，一種方法是可以在每個部件上裝有主要元件的相同性能的備用件，并且?guī)в袀溆迷詣油度胙b置。自然備用元件越多，系統(tǒng)的可靠性越高，但也會相應(yīng)增加系統(tǒng)重量、體積和費用，有時也會降低工作精度。因此，在成本、

33、重量、體積等一定的條件限制下，應(yīng)如何選擇各部件的備用元件數(shù)，使得整個系統(tǒng)的可靠性最大，就可以歸結(jié)為一個動態(tài)規(guī)劃問題。,串聯(lián)系統(tǒng)可靠性問題,例4－5 某電氣設(shè)備由三個部件串聯(lián)而成，為提高該種設(shè)備在指定工作條件下正常工作的可靠性，需在每個部件上安裝一個、兩個或三個主要元件的相同備件。假設(shè)對部件i(i=1，2，3)配備j個備件后的可靠性Rij和所需費用cij均已知，如表所示，若可用的總資金數(shù)量為1萬元，問如何配備各部件的備用元件數(shù)，才能使該

34、設(shè)備在給定工作條件下的可靠性最大？,串聯(lián)系統(tǒng)可靠性問題,例4－5 解 以給不同的部件決定備件作為不同的階段，則該問題是3階段決策問題設(shè)狀態(tài)變量xk表示從第k個部件到第3個部件允許使用的總費用（k=1,2,3）決策變量uk為第k部件配備的備用元件數(shù)（k=1，2，3）。則據(jù)題意有：x1=10千元，且每個部件都最少有一個備件，即uk≥1，若令sk表示為保障以后各部件均能獲得一個備件所需的資金數(shù)，則應(yīng)有：,串聯(lián)系統(tǒng)可靠性問題,例4－5

35、,且據(jù)此可得：s1=6，s2=5，s3=2。從而可知：對uk有,即當(dāng)期所耗資金加上k+1期往后所用資金sk+1不超過當(dāng)前擁有資金數(shù)。,串聯(lián)系統(tǒng)可靠性問題,例4－5,根據(jù)上述分析可以寫出各階段的狀態(tài)可能集合和決策允許集合如下： x1=10 X2＝{9，7，5} X3＝{2，3，4，5，6} U1＝{1，2，3}U2(9)＝{1，2，3} U2(7)＝{1，2

36、} U2(5)＝{1} U3(2)＝{1} U3(3)＝{1，2} U3(4)＝{1，2，3} U3(5)＝{1，2，3} U3(6)＝{1，2，3},串聯(lián)系統(tǒng)可靠性問題,例4－5,狀態(tài)轉(zhuǎn)移方程為：,階段效應(yīng)為,目標函數(shù)為是階段效應(yīng)乘積的形式,若以fk(xk)表示在階段k擁有資金xk時采用最優(yōu)決策序列所得的k階段往后的系統(tǒng)的可靠性，則動態(tài)規(guī)劃基

37、本方程為：,串聯(lián)系統(tǒng)可靠性問題,例4－5,串聯(lián)系統(tǒng)可靠性問題,例4－5,串聯(lián)系統(tǒng)可靠性問題,例4－5,,生產(chǎn)－庫存問題,生產(chǎn)計劃周期分為n個階段，即k=1~n；已知最初庫存量為x1；階段需求量為dk；單位產(chǎn)品的消耗費用為Lk；單位產(chǎn)品的階段庫存費用為hk；倉庫容量為Mk；階段生產(chǎn)能力為Bk；生產(chǎn)的準備費用為：,生產(chǎn)－庫存問題,問應(yīng)如何安排各階段產(chǎn)量，使計劃期總費用最小。這里狀態(tài)變量xk應(yīng)選為階段k的初始庫存量，計劃初期的庫

38、存量x1是已知的，末期的庫存量通常也是給定的，為簡單起見這里假定xn+1=0，于是問題是始端末端固定的問題。關(guān)于狀態(tài)xk的約束條件是,即階段k的庫存既不能超過庫存容量，也不應(yīng)超過階段k至階段n的需求總量（dk+dk+1+…+dn），否則將與xn+1=0的假設(shè)相違背。,生產(chǎn)－庫存問題,決策變量uk選為階段k的生產(chǎn)量。階段產(chǎn)量要在不超過生產(chǎn)能力Bk的條件下，充分滿足該階段的需求dk，同時還要滿足計劃末期的庫存量為0的要求。因此關(guān)于決策變量的

39、約束條件就是,期末庫存=期初庫存+生產(chǎn)量-本期需求,生產(chǎn)－庫存問題,階段k的生產(chǎn)費用是,庫存費用按階段k末期的庫存量xk+1計算,生產(chǎn)－庫存問題舉例,例4－5 求解生產(chǎn)－庫存問題。已知其n=3，ck=8，Lk=2，hk=1.5，x1=1，Mk=4，x4=0（計劃周期末期的庫存量為0），Bk＝6，d1=3，d2=4，d3=3。,生產(chǎn)－庫存問題舉例,例4－5 求解生產(chǎn)－庫存問題。已知其n=3，ck=8，Lk=2，hk=1.5，x1=1，

40、Mk=4，x4=0（計劃周期末期的庫存量為0），Bk＝6，d1=3，d2=4，d3=3。,生產(chǎn)－庫存問題舉例,例4－5 求解生產(chǎn)－庫存問題。已知其n=3，ck=8，Lk=2，hk=1.5，x1=1，Mk=4，x4=0（計劃周期末期的庫存量為0），Bk＝6，d1=3，d2=4，d3=3。,生產(chǎn)－庫存問題舉例,生產(chǎn)－庫存問題舉例,生產(chǎn)－庫存問題舉例,,,,,,,,生產(chǎn)－庫存問題舉例,,,,,,,,,,,,,,二維背包問題,背包問題的特征類

41、似于往旅行背包里面裝用品的問題，要求在旅行袋容積和／或載重量的限制下，所裝物品的總價值最大。這一類問題在海運、航運以及航天等領(lǐng)域都有應(yīng)用。若只考慮重量或體積限制，則稱為一維背包問題，若同時考慮重量和體積限制，則稱為二維背包問題?？紤]有N種物品需要裝船。第i種物品單位的重量為ωi，單件體積為υi，而價值為pi。最大的裝載重量為W，最大體積為V。現(xiàn)在要確定在不超過船的最大載重量和最大體積（不考慮貨物形狀）的條件下，使所載物品價值最大的裝

42、載方案。,二維背包問題,例4－6 已知貨物的單位重量ωi，單位體積υi及價值pi如表所示，船的最大載重能力為W＝5，最大裝載體積為V＝8，求最優(yōu)裝載方案。,二維背包問題,例4－6 W＝5，V＝8,解 該問題中有三種物品需要裝載，因此可以作為三段決策問題，每階段為一個物品決定裝船的數(shù)量。k階段系統(tǒng)的狀態(tài)為在給第k物品決定裝載數(shù)量時，船上還剩余的載重能力xk和剩余體積yk，因此狀態(tài)變量是二維的，記為（xk, yk）。

43、 有0≤xk≤5， 0≤yk≤8決策變量uk表示裝載第k種物品的數(shù)量。,二維背包問題,例4－6 W＝5，V＝8,解 狀態(tài)轉(zhuǎn)移方程為： xk+1=xk-uk·ωk yk+1=yk-uk·υk階段效應(yīng)為 rk(xk, yk, uk)=pk·uk各階段的狀態(tài)可能集與決策允許集為：,二維背包問題,解 狀態(tài)轉(zhuǎn)移方程為： xk+1=xk-uk·

44、ωk yk+1=yk-uk·υk,二維背包問題,解 當(dāng)k＝3時，由f4(x4, y4)=0,二維背包問題,解 當(dāng)k＝2時，由f3(x3, y3)已知,二維背包問題,解 當(dāng)k＝1時，W=5,V=8,,,,,,,,設(shè)備更新問題,設(shè)備更新問題的一般提法隨著使用年限的增加，設(shè)備性能會變差，故障會增加，需要維修或更新。設(shè)備使用時間愈長，積累效益愈高，但隨著設(shè)備陳舊，維修使用費用也會提高，而且，設(shè)備使用年限

45、愈久，處理價格愈低，更新費用也要增加。因此，處于某個階段的各種設(shè)備，總是面臨著保留還是更新的問題，這個問題應(yīng)該從整個計劃期間的總回收額，而不應(yīng)從局部的某個階段的回收額來考慮。由于每個階段都面臨著保留還是更新的兩種選擇，因此，它是一個多階段的決策過程，可以用動態(tài)規(guī)劃方法求解。,設(shè)備更新問題,今有一設(shè)備更新問題如下：已知 n為計算設(shè)備回收額的總期數(shù)； t為某個階段的設(shè)備役齡； γ(t)為從役齡為t的設(shè)備得到的

46、階段收益； μ(t)為役齡為t的設(shè)備的階段使用費用； s(t)是役齡為t的設(shè)備的處理價格； p為新設(shè)備的購置價格；求n期內(nèi)使回收額最大的設(shè)備更新政策。,設(shè)備更新問題,狀態(tài)變量選為設(shè)備的役齡t，即xk=t，決策只有兩種可能，即保留或更新，記為K（保留）或P（更新）。狀態(tài)轉(zhuǎn)移方程,相應(yīng)的階段效應(yīng)即階段的回收額也有兩種可能,設(shè)備更新問題,例4－7 假定n＝6年，新設(shè)備購買價格為10萬元。役齡為t時