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

1、1 動態(tài)規(guī)劃應用舉例 2 不確定型問題的動態(tài)規(guī)劃算法 3 總結(jié)動態(tài)規(guī)劃的特點 ABC動態(tài)規(guī)劃是一種方法，而不是算法。即對復雜問題需加以分析才能應用動態(tài)規(guī)劃的迭代算法進行求解，而且其中具有很大技巧性。動態(tài)規(guī)劃目前已廣泛用于旅行路徑問題、資源分配問題、生產(chǎn)計劃問題、設備更新問題、排序問題及復合系統(tǒng)可靠性問題等等。一、復合系統(tǒng)可靠性問題例3-10某復合系統(tǒng)由三個部分串聯(lián)而成，其示意圖見圖3-15。知： 圖3-15 A、B、C相互獨立各部分的單件故障率分別為：P1=0.3，P2=0.2，P3=0.4顯然，若各部分只有一個部件時其總可靠率f為：f=(10.3)(10.2)(10.4)=0.336每個部分

2、的單件價格為：A部分單價c1=2萬元； B部分單價c2=3萬元；C部分單價c3=1萬元共投資購置部件額10萬元求A、B、C三部分各應購置多少部件才能使總可靠率最高？ 解采用動態(tài)規(guī)劃法，令A、B、C分別為階段1、2、3。并定義：sk第k階段及以后可用來購買部件總額。xk第k環(huán)節(jié)配備的件數(shù)ck環(huán)節(jié)k部件單價Pk環(huán)節(jié)k單件的故障率顯然，第k環(huán)節(jié)本身的可靠率為：dk(sk，xk)=)(1 kxkP 狀態(tài)轉(zhuǎn)移方程：sk+1=skckxk令：fk(sk，xk)表示第k階段共有資金sk，且買k環(huán)節(jié)的部件數(shù)為xk時的k段及以后各段組成的系統(tǒng)最高可靠率。fk(sk)表示k階段尚有資金sk時，可能獲得k段及以后各

3、段組成系統(tǒng)的最高可靠率。則遞推方程為：fk(sk)= dk(sk，xk)fk+1(skckxk)fN+1(sNcNxN)=1采用后向動態(tài)規(guī)劃法，從第3階段算起。kxmax 第1步：考慮購置部件C的數(shù)量。因為A、B至少各購一件否則，整個可靠性為零）。則用于購置C部件的最高金額為：s3=10c1c2=5(萬元)顯然，由于C是最后階段，故應把剩余金額全部購置C部件，具體計算結(jié)果示如表3-11。 表3-11 階段3計算結(jié)果 s3x3 f3(s3)=d3(s3，x3) x*3 12345123450.6000.8400.9360.9740.99012345例如，當s3=3萬元時，那么： f3(3)=d(

4、3，3)=10.43=0.936。 第2步：退到階段2，此時考慮當把錢用于購置B和C部件時，各應購置多少個部件為最優(yōu)。顯然，此時B、C應至少各配制1個部件，故s2c2+c3=3+1=4；同時，A部件亦至少配備1個部件，故s2102=8。階段2計算結(jié)果示如表3-12。 表3-12 階段2計算結(jié)果s2 x2 d2(s2,x2) s3 f3(s3) f2(s2,x2) f2(s2) x*2 456778811112120.80.80.80.80.960.80.9612341520.6000.8400.9360.9740.6000.9900.8400.4800.6720.7490.7790.5760.

5、7920.8060.4800.6720.7490.779 0.8061111 2例如，當s2=8時，可有2個選擇方案：令x2=1，得f2(8，1)=d2(8，1)f3(831)=(1P2)f3(5)=(10.2)0.990=0.80.990=0.792令x2=2，得f2(8，2)=d2(8，2)f3(832)=(1P22)f3(2)=(10.22)0.840=0.960.84=0.80640.806故應選x2*=2。第3步：退回到A部件處，s1=10萬元。計算結(jié)果示于表3-13。可見最優(yōu)分配資金可獲得最高可靠率為0.682，反向跟蹤所購置部件為：A、B、C、分別購置2、1和3件。表3-13 階

6、段1的計算結(jié)果 s1 x1 d1(s1,x1) s2 f2(s2) f1(s1,x1) f1(s1) x*1 10 1230.70.910.9738640.8060.7490.4800.5640.6820.467 0.682 2 當研究的對象的參量出現(xiàn)不確定狀況和受到隨機干擾時，這樣在根據(jù)某階段的狀態(tài)和決策就不能導出下階段的狀態(tài)確定值，其階段收益函數(shù)也不確定，即變?yōu)椋篺(x，u)f(x，u，e)e為隨機變量，這時，只能求出階段期望值來進行選擇最優(yōu)決策。顯然，前向動態(tài)規(guī)劃無法解決，只能應用后向動態(tài)規(guī)劃算法。不確定型問題的動態(tài)規(guī)劃算法的一般公式可歸納如下。設規(guī)劃中，第末端為0級，始端為n級。這樣后

7、向遞推從0級開始進行。令： V最優(yōu)函數(shù)值d決策變量e隨機變量f階段收益s狀態(tài)變量E期望值則知： Vn(sn)=max Efn(dn，sn，en)+Vn1(sn1) sn1=tn(dn，sn，en) 起步 V0(s0)=max Ef0(d0，s0，e0)下面舉例說明。例3-12生產(chǎn)計劃問題。廠長需決定當年開始兩個月內(nèi)的最優(yōu)生產(chǎn)計劃，知：產(chǎn)品生產(chǎn)費用1000元/件產(chǎn)品銷售價格2000元/件產(chǎn)品儲存費用100元/件月兩個月后，產(chǎn)品一次性處理，500元/件 目前廠內(nèi)無存貨，且生產(chǎn)周期短，當月生產(chǎn)可滿足當月訂貨需求。貨物需求的概率分布見表3-15。表3-15 工廠貨物需求概率分布需求概率0123 0.2

8、50.400.200.15 求第1個月應生產(chǎn)多少件產(chǎn)品才能使收益期望值最大或損失最少）？ 當?shù)?個月已度過，第2個月應生產(chǎn)多少件產(chǎn)品才能使余下收益期望最大？解 仍需分三個階段走，首先從二月末開始計算，然后倒退到二月初和一月初。1設時間已到二月末，此時庫存水平I0有4種可能性：0、1、2、3因需求最大為3）。則針對這幾種可能性都必定一次性處理，其處理價為500元/件，最后計算結(jié)果示于表3-16。 表3-16 階段0計算結(jié)果 I0 V0 0123 050010001500 2設已到二月初，此時，必已知一月末的庫存I1，針對不同的I1狀態(tài)），決定每一種可能的生產(chǎn)數(shù)量決策），相應收益以及售出水平等。對

9、每一種庫存水平選擇使期望收益最大的生產(chǎn)數(shù)量，其計算結(jié)果于表3-17。其中，*為最優(yōu)決策值。 表3-17 階段1計算結(jié)果 狀態(tài) I1 生產(chǎn)d1 銷售s1 概率 新產(chǎn)生狀態(tài)I0 生產(chǎn)費用 銷售收入 庫存費用 V0（I0） 概率$ 期望收益 0 001.0000000001010.250.7510-1000-100002000-10005000-150750600* 20120.250.400.35 210 -2000-2000-2000 020004000 -200-1000 10005000 -300160700 560 30123 0.250.400.200.15 3210 -3000-300

10、0-3000-3000 0200040006000 -300-200-1000 150010005000 -450-80280450 200 例如，當庫存水平I1=0時，有4種可能決策d1=（0，1，2，3）。當選擇d1=2時，其銷售量則僅有0，1，2三種可能性，其概率為：P(0)=0.25；P(1)=0.40；P(2)=P(2)+P(3)=0.35現(xiàn)就分析當I1=0，d1=2，s1=2情況：銷售概率s1(2)=0.35新產(chǎn)生二月末存貨狀態(tài)I0=0生產(chǎn)費用為2000元，即收益為2000元。銷售收入為4000元。 庫存費用為0。轉(zhuǎn)移到0階段的收益V0I0為0。概率收益值為40002000）0.3

11、5=700元。同時也可算出當s1=0和s1=1時的概率收益分別為300和160，其最后知I1=0，d1=2時的期望收益值為700300+160）=560元）。同理知：d1=0 時，總期望收益為0。 d1=1時，總期望收益為600。 d1=3時，總期望收益為200。 最后知，當狀態(tài)I1=0時，最優(yōu)決策d1*(0)=1，V1(0)=600，當I1為其它值時，計算結(jié)果示于表3-18。 表3-18 I1 V1（I1） D1*(I1) 0123 600160025603200 1000 3)退到一月初，此時初始存貨為0，即I2=0，其計算方式同前，其結(jié)果示如表3-19。 表3-19 階段2計算結(jié)果I2=

12、0） 狀態(tài) I2 生產(chǎn)d2 銷售s2 概率 新產(chǎn)生狀態(tài)I1 生產(chǎn)費用 銷售收入 庫存費用 V1（I1） 概率$ 期望收益 0 001.0000006006006001010.250.7510-1000-100002000-10001600600 1251200 1325 20120.250.400.35 210 -2000-2000-2000 020004000 -200-1000 25601600600 90600910 1600* 30123 0.250.400.200.15 3210 -3000-3000-3000-3000 0200040006000 -300-200-1000 320

13、025601600600 -25544500540 1559 綜合結(jié)果知，當I2=0時，d2*(I2)=2，V2(I2)=1600。最后結(jié)果可歸納為決策樹，具體示如圖3-17。從圖3-17看出，從期望收益可找出一月初的最優(yōu)決策，然而找不出向后走的確切軌跡，而需根據(jù)以后發(fā)生的事件從決策樹中找出相應決策。根據(jù)決策樹，便可回答前面提的2個問題： 一月初最優(yōu)期望值收益決策為： 決策d2=2，期望收益為1600元。 當時間指向一月末或二月初），此時決策取決于一月份銷售量，即一月末存貨量I1。 當I1=0，取決策d1=1。 當I1=1，2時，決策d1全為0。 0 -（0.25）1 -（0.40）2 -（0

14、.20）3 -（0.15）0 -（0.25）1 -（0.40）2 -（0.20）3 -（0.15）0 -（0.25）1 -（0.40）2 -（0.20）3 -（0.15）2 1 0 0 0（概率=0.25）（概率=0.40）（概率=0.35） 2 0 1 2或3 2 0圖3-17 例3-12結(jié)果決策樹級數(shù)10 2 1 0 0 1 0 0 0 1 0 0 0 1狀態(tài) 決策 事件 結(jié)果 狀態(tài) 決策 事件 結(jié)果 狀態(tài) 開始存貨 生產(chǎn) 概率需求 需求 存貨 生產(chǎn) 概率需求 需求 存貨 一、動態(tài)規(guī)劃由于具有下述優(yōu)點而得到廣泛的應用1對目標函數(shù)的形式不加限制。2對于約束條件容易處理。3所得結(jié)果，在理論上屬絕對最優(yōu)。（對概率型，屬概率意義上絕對最優(yōu)）4運算過程簡單。5計算結(jié)果為一個“解族”，即獲得了整個決策樹。這樣，當由于干擾使運動過程離開了原最優(yōu)軌跡，則可在新狀態(tài)下沿已計算好的另一條軌跡行進。 108976543211644236136176619103710988,96129109895468444108108圖3-1最優(yōu)旅行路線問題 例 如 ， 在 圖 3 - 1 中