運(yùn)籌學(xué)第章動態(tài)規(guī)劃.ppt

2019/7/9,1,第六章 動態(tài)規(guī)劃 Dynamic Programming，DP,美國數(shù)學(xué)家貝爾曼 （Richard. Bellman, (19201984) ),創(chuàng)始時(shí)間,上個世紀(jì)50年代,創(chuàng)始人,動態(tài)規(guī)劃是運(yùn)籌學(xué)的一個主要分支, 同時(shí)也是現(xiàn)代企業(yè)管理中的一種重要決策方法, 它是解決多階段決策過程的最優(yōu)化的一種方法。,2019/7/9,2,動態(tài)規(guī)劃 模型分類,離散確定型,離散隨機(jī)型,連續(xù)確定型,連續(xù)隨機(jī)型,動態(tài)規(guī)劃解決問題的思路獨(dú)特,在處理某些優(yōu)化問題時(shí), 有時(shí)比線性規(guī)劃或者非線性規(guī)劃更有效.需要豐富的想象力去建立模型，并能用創(chuàng)造性的技巧去求解。,其中離散確定性是最基本的, 本章主要介紹這種類型的問題,介紹動態(tài)規(guī)劃的基本思想、原理和方法.,2019/7/9,3,本章主要內(nèi)容,多階段決策過程及其問題舉例 最短路問題 動態(tài)規(guī)劃的基本概念和基本方程 動態(tài)規(guī)劃應(yīng)用舉例 資源分配問題 背包問題 生產(chǎn)庫存問題 ,2019/7/9,4,6.1 多階段決策過程及其問題舉例,動態(tài)規(guī)劃研究的問題-多階段決策問題（順序決策問題） 研究的問題可以在時(shí)間或空間上劃分為若干個相互聯(lián)系階段，稱為”時(shí)段”。 在每一個時(shí)段都需要做出決策,每時(shí)段的決策將影響到下一時(shí)段的決策, 因此決策者每段決策時(shí), 不僅要考慮本階段目標(biāo)最優(yōu),還應(yīng)考慮最終目標(biāo)的最優(yōu), 最終達(dá)到整個決策活動的總體目標(biāo)最優(yōu).,2019/7/9,5,動態(tài)規(guī)劃方法與“時(shí)間”關(guān)系很密切，隨著時(shí)間過程的發(fā)展而決定各時(shí)段的決策，產(chǎn)生一個決策序列，這就是“動態(tài)”的意思。 然而，它也可以處理與時(shí)間無關(guān)的靜態(tài)問題，只要在問題中人為地引入“時(shí)段”因素，就可以將其轉(zhuǎn)化為一個多階段決策問題。,2019/7/9,6,例1 最短路徑問題,求從A到E的最短路徑。 顯然，這種運(yùn)輸網(wǎng)絡(luò)問題是靜態(tài)決策問題。但是，按照網(wǎng)絡(luò)中點(diǎn)的分布，可以把它分為4個階段，而作為多階段決策問題來研究。,2019/7/9,7,第一種方法稱做全枚舉法或窮舉法。它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對它們一一進(jìn)行比較，求出最優(yōu)方案。這里從A到E的路程共有332118條可能的路線，分別算出各條路線的距離，最后進(jìn)行比較，可知最優(yōu)路線。顯然，當(dāng)組成交通網(wǎng)絡(luò)的節(jié)點(diǎn)很多時(shí)，用窮舉法求最優(yōu)路線的計(jì)算工作量將會十分龐大，而且其中包含著許多重復(fù)計(jì)算 第二種方法貪心算法，即所謂“局部最優(yōu)路徑”法，是說某人從k出發(fā)，他并不顧及全線是否最短，只是選擇當(dāng)前最短途徑，“逢近便走”，錯誤地以為局部最優(yōu)會致整體最優(yōu)，在這種想法指導(dǎo)下，所取決策必是 A B3 C3 D1 E. 距離為：1+11+8+5=25,2019/7/9,8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,第1階段,第4階段,第3階段,第2階段,狀態(tài),第三種方法是動態(tài)規(guī)劃方法。,2019/7/9,9,基本思想：如果起點(diǎn)A經(jīng)過B1,C1,D1而到終點(diǎn)E，則由C1出發(fā)經(jīng)D1到E點(diǎn)這條子路線，是從C1到E的最短路線。所以，尋找最短路線，應(yīng)該從最后一段開始找，然后往前遞推. 設(shè) sk：第k階段初的狀態(tài)（所處的結(jié)點(diǎn)）; xk (sk)：在sk狀態(tài)時(shí)第k階段所作的決策, 決定下一個狀態(tài)的位置； d(sk,xk)：第k階段，采取策略xk 所發(fā)生的距離; fk (sk)：在第k階段，由sk狀態(tài)開始到終點(diǎn)E的最短距離.,2019/7/9,10,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f5(E)=0,2019/7/9,11,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D1)=5,f5(E)=0,2019/7/9,12,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f4(D1)=5,2019/7/9,13,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C1)=8,f4(D1)=5,2019/7/9,14,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C2)=7,f4(D1)=5,f3(C1)=8,2019/7/9,15,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f3(C1)=8,f3(C2)=7,2019/7/9,16,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B1)=20,f3(C2)=7,f3(C1)=8,2019/7/9,17,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B2)=14,f3(C2)=7,f3(C1)=8,f2(B1)=20,2019/7/9,18,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f2(B1)=20,f2(B2)=14,2019/7/9,19,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=20,2019/7/9,20,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=20,狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài) 最優(yōu)決策 狀態(tài),A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E 從A到E的最短路徑為19，路線為AB 2C1 D1 E,2019/7/9,21,多階段決策過程及實(shí)例-標(biāo)號法,4,3,7,5,9,7,6,8,13,10,9,12,13,16,18,該點(diǎn)到G點(diǎn)的最短距離,從G到A的解法稱為逆序解法。,注：因?yàn)閺腁到G的最短路與從G到A的最短路是一樣的， 因此也可以從A出發(fā)來找。從A到G的解法稱為順序解法。,2019/7/9,22,綜上所述可見，全枚舉法雖可找出最優(yōu)方案，但不是個好算法，局部最優(yōu)法則完全是個錯誤方法，只有動態(tài)規(guī)劃方法屬較科學(xué)有效的算法。它的基本思想是，把一個比較復(fù)雜的問題分解為一系列同類型的更易求解的子問題，便于應(yīng)用計(jì)算機(jī)。,2019/7/9,23,6.2 動態(tài)規(guī)劃的基本概念和基本方程,(一) 基本概念和基本方程,(1) 階段：k=1,，n,(2) 狀態(tài)變量sk ：第k階段的狀態(tài). 狀態(tài)變量取值的集合成為狀態(tài)集合，用Sk表示。狀態(tài)集合可以是一離散取值的集合，也可以為一連續(xù)的取值區(qū)間，視具體問題而定,(3) 決策變量uk(sk) ：第k階段的決定，Dk(sk)為決策變量的取值范圍. 狀態(tài)轉(zhuǎn)移方程sk1 T (sk,uk)：描述第k階段與第k+1階段的狀態(tài)變量的關(guān)系,2019/7/9,24,(5)指標(biāo) v(sk ,uk) ：第k階段狀態(tài)sk情況下采取決策uk得到的結(jié)果（距離、得益、成本等） 指標(biāo)函數(shù)是指各階段指標(biāo)的累計(jì)。即 V (sk,uk, , sn,un, sn+1)=vk(sk,uk)*vk+1(sk+1,uk+1)*vn(sn,un) 它表示從第k階段的狀態(tài)sk開始到第n階段的終止?fàn)顟B(tài)的指標(biāo)累計(jì)。式中*表示某種運(yùn)算符，一般為加法運(yùn)算或者乘積運(yùn)算。,(6)最優(yōu)指標(biāo)函數(shù)fk (sk) ：它表示從第k階段的狀態(tài)sk開始到第n階段的終止?fàn)顟B(tài)的過程，采取最優(yōu)策略得到的指標(biāo)函數(shù)值,階段函數(shù),2019/7/9,25,逆推公式,或,多階段決策問題中，常見的目標(biāo)函數(shù)形式之一是取各階段效益之和的形式.有些問題，如系統(tǒng)可靠性問題，其目標(biāo)函數(shù)是取各階段效益的連乘積形式. 總之，具體問題的目標(biāo)函數(shù)表達(dá)形式需要視具體問題而定。,Max或者min,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,第1階段,第4階段,第3階段,第2階段,對例1,(1) 階段：k1，2，4,(2) 狀態(tài)變量：sk第k階段初所處的位置, 狀態(tài)集合 Sk 如S2 :=B1 , B2 , B3.,2019/7/9,27,(3) 決策變量uk ：在第k段sk狀態(tài)時(shí)決定選取的下一段的某點(diǎn).,(4) 狀態(tài)轉(zhuǎn)移方程 ：sk1 uk ( sk),(5) 階段效益： d(sk,uk)為第k段，采取決策uk 到下一狀態(tài)的距離.,(6) 最優(yōu)指標(biāo)函數(shù)： fk (sk)：第k段，在sk狀態(tài)時(shí)到終點(diǎn)E的最短距離.,逆推公式：,2019/7/9,28,（二）貝爾曼最優(yōu)化原理： 一個最優(yōu)策略具有這樣的性質(zhì)，即不論初始狀態(tài)與初始策略如何，對于先前決策所造成的狀態(tài)而言，余下所有決策必構(gòu)成最優(yōu)決策。 也即：一個最優(yōu)策略的子策略也是最優(yōu)的。,2019/7/9,29,（三）解法步驟 反向條件優(yōu)化 正向求最優(yōu)解,2019/7/9,30,6.3 應(yīng)用舉例,例2 資源分配問題-1 例3 資源分配問題-2 例4 背包問題 例5 生產(chǎn)庫存問題 例6 可靠性問題 例7 機(jī)器負(fù)荷分配問題 等等,2019/7/9,31,例 2 資源分配問題-1,某公司準(zhǔn)備將5臺設(shè)備分配給所屬的三個子工廠，各工廠獲得設(shè)備后的可盈利情況如表所示。問：如何分配這五臺設(shè)備，才能使公司獲得的收益最大？,2019/7/9,32,分析,(1) 階段：k=1,2,3.,(3) 決策變量uk ：對第k個企業(yè)的分配數(shù).,(2) 狀態(tài)變量sk ：對第k至3個企業(yè)可分配的設(shè)備數(shù) 或：第k階段初可分配的設(shè)備數(shù).,(4) 狀態(tài)轉(zhuǎn)移方程： sk1 sk uk.,(5) 最優(yōu)指標(biāo)函數(shù)fk (sk) ：第k至3個企業(yè)采取最優(yōu)分配策略可產(chǎn)生的最大收益.,設(shè)分配給第k個工廠的機(jī)器數(shù)為uk,工廠1,工廠2,工廠3,2019/7/9,33,其中，gk (uk)是階段函數(shù),逆推公式：,sk+1,2019/7/9,34,k=3 ,S3 = 0,1,2,3,4,5 , f3(s3) maxg3(u3)+0,2019/7/9,35,k=2 ,S2 = 0,1,2,3,4,5 , f2(s2) maxg2(u2)+ f3(s3),S3=S2-u3,2019/7/9,36,k=1 ,S1 = 5, f1(s1) max g1(u1)+ f2(s2),得到兩種方案： u1*0，u2*2，u3*3: 工廠1分配0臺，工廠2 分配2臺，工廠3分配3臺; u1*2，u2*2，u3*1: 工廠1分配2臺，工廠2 分配2臺，工廠3分配1臺。 總盈利均為21萬元。,同理得到另一組最優(yōu)解,2019/7/9,37,一般分配問題,某種資源，總量為a，分配于n種生產(chǎn)。若分配 ui 用于第 i 種生產(chǎn)，收益為gi (ui ) 。 問：應(yīng)如何分配才能使總收入最大？ 容易建立其數(shù)學(xué)模型：,2019/7/9,38,逆推公式：,sk: 第k階段初可分配的資源數(shù)。 uk:對第k個企業(yè)的分配資源數(shù). 狀態(tài)轉(zhuǎn)移方程: sk+1 = sk -uk,例3 資源分配問題-2,某工廠要進(jìn)行A,B,C三種新產(chǎn)品的試制，為提高三種產(chǎn)品研制成功的概率，決定調(diào)撥經(jīng)費(fèi)2百萬，并要求資金集中使用，也即以百萬為單位進(jìn)行分配，其增加研發(fā)費(fèi)與新產(chǎn)品不成功概率的關(guān)系如表所示。問如何分配資金，可使三種產(chǎn)品都研制不成功的概率最小。,分析,(1) 階段：k=1，2，3,(3) 決策變量uk ：對第k階段分配金額,(2) 狀態(tài)變量sk ：第k階段初的可用金額,(4) 狀態(tài)轉(zhuǎn)移方程： sk1 sk - uk,產(chǎn)品A,產(chǎn)品B,產(chǎn)品C,逆推公式：,其中，gk (uk)是階段指標(biāo)函數(shù),(5) 最優(yōu)指標(biāo)函數(shù)fk (sk) ：第k至3階段采取最優(yōu)分配策略，得到不成功概率最小,k=3 ,S3 = 0,1,2, f3(s3) ming3(u3)*1,k=2 ,S2 = 0,1,2 , f2(s2) ming2(u2)*f2(s2),k=1 ,S1 = 2, f1(s1) max g1(u1)* f2(s2),得到方案： u1*1，u2*0，u3*1: 產(chǎn)品 A分配1百萬，產(chǎn)品 B分配0，產(chǎn)品 C分配1百萬 f*=0.06,2019/7/9,45,例4 背包問題 某卡車載重能力為10噸，現(xiàn)要裝三種產(chǎn)品，已知每件產(chǎn)品的重量和利潤如表： 又規(guī)定產(chǎn)品3至多裝2件。 問如何安排運(yùn)輸可使總利潤最大？,設(shè)u1,u2,u3分別為1、2、3貨物的裝載件數(shù)，得到數(shù)學(xué)模型：,階段 k=1,2,3， 狀態(tài)變量sk 第k階段初的可裝載能力， 決策變量uk 第k階段的裝載件數(shù)， 狀態(tài)轉(zhuǎn)移方程: （tk為k產(chǎn)品的單件重量） 遞推公式: f4(s4)=0, k=3,2,1,動態(tài)規(guī)劃方法求解,產(chǎn)品A,產(chǎn)品B,產(chǎn)品C,物品A,物品B,物品C,k=1,k=2,k=3,k=4,s1=10,s2,s3,s4,階段k,狀態(tài)變量： 裝載前背包的容量,決策變量： 裝載的件數(shù),u1,u2,u3,決策允許集合： 裝載件數(shù)的范圍,0u1s1/t1 u1為整數(shù),狀態(tài)轉(zhuǎn)移方程：背包容量和裝載件數(shù)的關(guān)系,階段指標(biāo)： vk(sk,uk)=rkuk 在背包中第k種物品的價(jià)值,最優(yōu)指標(biāo)： fk(sk)=maxrkuk+fk+1(sk+1),終端條件：,f4(s4)=0,s2s1-t1x1,s3=s2-t2x2,s4=s3-t3x3,0u2s2/t2 u2為整數(shù),0u3s3/t3, 2 u3為整數(shù),k=3,C的單件重量為2 , 限制最多裝2件,k=2, 裝載物品B，f2(s2),B的單件重量為3,k=1，裝載物品A， f1(u1),最優(yōu)解為： 物品A裝0件，物品B裝2件，物品C裝2件。最大價(jià)值為400元。,A的單件重量為4,2019/7/9,52,例5 生產(chǎn)庫存問題 某廠在年末估計(jì)，下年4個季度市場對該廠某產(chǎn)品的需求量均為dk=3 (k=1,2,3,4)，該廠每季度生產(chǎn)此產(chǎn)品的能力為bk=5 (k=1,2,3,4,)。 每季度生產(chǎn)這種產(chǎn)品的固定成本為F=13（不生產(chǎn)時(shí)為0），每一產(chǎn)品的單位變動成本為C=2。 本季度產(chǎn)品如不能售出，則需發(fā)生庫存費(fèi)用g=1/件，倉庫能貯存產(chǎn)品的最大數(shù)量Ek=4。 年初年末庫存為0， 試問如何安排4個季度的生產(chǎn)，以保證在滿足市場需求的前提下，使生產(chǎn)和庫存總費(fèi)用最小?,2019/7/9,53,假設(shè)：第 k季度可以銷售的產(chǎn)品是本季度初的庫存及本季度的產(chǎn)量,(1) 階段：k=1,2,3,4 n=4.,(2)狀態(tài)變量sk ：第k季度初的庫存量.,(3)決策變量uk ：第k 個季度的產(chǎn)量.,(4) 轉(zhuǎn)移方程： sk1 sk +uk- dk.,(5) 最優(yōu)指標(biāo)函數(shù) fk (sk) ：第k季度至第4個季度采取最優(yōu)策略時(shí)的最小總費(fèi)用.,2019/7/9,54,逆推公式：,k=4,k=3,K=2,k=1,2019/7/9,60,例5 可靠性問題,某機(jī)器工作系統(tǒng)由n個部件組成，這些部件正常工作關(guān)系為串聯(lián)，每個部件都裝有主要元件的備用件，并可自動投入工作。顯然備用件越多，可靠性越大，但系統(tǒng)的成本、重量、體積會變大。 若已知備用件總費(fèi)用為 C，總重量為W. ck 為第 k個部件裝配一個備用件的費(fèi)用,問：在這兩個限制條件下，應(yīng)如何選用部件的備用件個數(shù)，使得正常工作的可靠性最大？,wk 為第 k個部件裝配一個備用件的重量,Pk 第 k個部件的故障概率,設(shè)uk 為第 k個部件裝配備用件個數(shù),dk (sk, uk)為第 k個部件裝配uk個備用件時(shí)，機(jī)器正常工作的概率,動態(tài)規(guī)劃模型：,(1) 階段：k=1,2,n,(2) 決策變量：uk ：第k個部件上裝 備用件個數(shù),(4) 狀態(tài)轉(zhuǎn)移： sk+1 =sk - ck uk tk+1 =tk - wk uk,(5) fk (sk ，tk)：第k-n個部件，采取最優(yōu)策略時(shí)機(jī)器正常工作的概率。,某復(fù)合系統(tǒng)由A,B,C三個部分串聯(lián)而成，已知： A、B、C相互獨(dú)立； 各部分的單件故障率分別為：P1=0.4，P2=0.2，P3=0.5； 每個部分的單件價(jià)格為：A部分單價(jià)c1=1萬元； B部分單價(jià)c2=2萬元；C部分單價(jià)c3=3萬元； 可投資購置部件金額為10萬元。 求A、B、C三部分各應(yīng)購置多少部件才能使系統(tǒng)的總可靠率最大？,令A(yù)、B、C分別為階段1、2、3。 sk第k階段及以后可用來購買部件總額 uk第k環(huán)節(jié)配備的件數(shù) 狀態(tài)轉(zhuǎn)移方程：sk+1=skckuk 第k環(huán)節(jié)本身的可靠率為： 令：fk(sk)表示k階段尚有資金sk時(shí)，可能獲得k段及以后各段組成系統(tǒng)的最高可靠率。 遞推方程為： fk(sk)= max dk(sk，uk)fk+1(skckuk)， f4(s4)=1,采用后向動態(tài)規(guī)劃法，從第3階段算起。,階段2，此時(shí)考慮當(dāng)把錢用于購置B和C部件時(shí)，各應(yīng)購置多少個部件為最優(yōu)。 顯然，此時(shí)B、C應(yīng)至少各配制1個部件，故s2c2+c3=2+3=5；同時(shí)，A部件亦至少配備1