動(dòng)態(tài)規(guī)劃運(yùn)籌學(xué)基礎(chǔ)及其應(yīng)用胡運(yùn)權(quán)第五版1

第五章動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃Dynamicprogramming五十年代貝爾曼(B.E.Bellman)為代表的研討成果屬于現(xiàn)代控制實(shí)際的一部分以長(zhǎng)久利益為目的的一系列決策最優(yōu)化原理，可歸結(jié)為一個(gè)遞推公式5.1動(dòng)態(tài)規(guī)劃的最優(yōu)化原理及其算法5.1.1求解多階段決策過程的方法例5.1.1最短路問題2決策樹法可以枚舉出20條途徑，其中最短的途徑長(zhǎng)度為163例5.1.1最短路問題表現(xiàn)為明顯的階段性一條從A到B的最短途徑中的任何一段都是最短的最優(yōu)性原理“最優(yōu)戰(zhàn)略的一部分也是最優(yōu)的〞每步的決策只與相鄰階段形狀有關(guān)，而與如何到達(dá)這一形狀無關(guān)因此我們可以從B向回搜索最短路標(biāo)志法如何找出最短途徑45.1.2動(dòng)態(tài)規(guī)劃的根本概念及遞推公式形狀(每階段初始的出發(fā)點(diǎn))最短路問題中，各個(gè)節(jié)點(diǎn)就是形狀消費(fèi)庫(kù)存問題中，庫(kù)存量是形狀物資分配問題中，剩余的物資量是形狀控制變量(決策變量)最短路問題中，走哪條路消費(fèi)庫(kù)存問題中，各階段的產(chǎn)品消費(fèi)量物資分配問題中，分配給每個(gè)地域的物資量階段的編號(hào)與遞推的方向普通采用反向遞推，所以階段的編號(hào)也是逆向的當(dāng)然也可以正向遞推5動(dòng)態(tài)規(guī)劃的步驟1、確定問題的階段和編號(hào)2、確定形狀變量用Sk表示第k階段的形狀變量及其值3、確定決策變量用xk表示第k階段的決策變量，并以xk*表示該階段的最優(yōu)決策4、形狀轉(zhuǎn)移方程sk-1=g(sk,xk)反向編號(hào)sk+1=g(sk,xk)正向編號(hào)5、直接效果直接一步轉(zhuǎn)移的效果dk(sk,xk)6、總效果函數(shù)指某階段某形狀下到終端形狀的總效果，它是一個(gè)遞推公式6動(dòng)態(tài)規(guī)劃的步驟hk是普通表達(dá)方式，求當(dāng)前階段當(dāng)前形狀下的階段最優(yōu)總效果(1)如最短路問題，是累加方式，此時(shí)有終端的邊沿效果普通為f0(s0,x0)=0(2)如串聯(lián)絡(luò)統(tǒng)可靠性問題，是連乘方式，此時(shí)有終端的邊沿效果普通為f0(s0,x0)=1從第1階段開場(chǎng)，利用邊沿效果和邊境條件，可以遞推到最后階段75.2動(dòng)態(tài)規(guī)劃模型舉例5.2.1產(chǎn)品消費(fèi)方案安排問題例1某工廠消費(fèi)某種產(chǎn)品的月消費(fèi)才干為10件，知今后四個(gè)月的產(chǎn)品本錢及銷售量如表所示。假設(shè)本月產(chǎn)量超越銷售量時(shí)，可以存儲(chǔ)起來備以后各月銷售，一件產(chǎn)品的月存儲(chǔ)費(fèi)為2元，試安排月消費(fèi)方案并做到：1、保證滿足每月的銷售量，并規(guī)定方案期初和期末庫(kù)存為零；2、在消費(fèi)才干允許范圍內(nèi)，安排每月消費(fèi)量方案使產(chǎn)品總本錢(即消費(fèi)費(fèi)用加存儲(chǔ)費(fèi))最低。8例1產(chǎn)品消費(fèi)方案安排設(shè)xk為第k階段消費(fèi)量，那么有直接本錢dk(sk,xk)=ckxk+2sk形狀轉(zhuǎn)移公式為sk-1=sk+xk-yk總本錢遞推公式第一階段：(即第4月份)由邊境條件和形狀轉(zhuǎn)移方程s0=s1+x1y1=s1+x16=0得s1+x1=6或x1=6s10估計(jì)第一階段，即第4月份初庫(kù)存的能夠形狀：0s1306712=5，所以，s1[0,5]9第一階段最優(yōu)決策表第二階段：最大能夠庫(kù)存量7件由形狀轉(zhuǎn)移方程：s1=s2+x2120及x210，可知s2[2,7]，minx2=5由階段效果遞推公式有：f2(2,10)=d2(2,10)+f1*(0,6) =22+8010+456=1260得第二階段最優(yōu)決策表，如下10第二階段最優(yōu)決策表第三階段：最大能夠庫(kù)存量4件由形狀轉(zhuǎn)移方程：s2=s3+x372及x310，可知s3[0,4]，minx3=5由階段效果遞推公式有：f3(1,10)=d3(1,10)+f2*(4,8) =21+7210+1104=1826得第三階段最優(yōu)決策表，如下11第三階段最優(yōu)決策表第四階段：初始庫(kù)存量s4=0由形狀轉(zhuǎn)移方程：s3=s4+x460可知x46，由階段效果遞推公式有：f4(0,6)=d4(0,6)+f3*(0,10) =706+1902=2322得第四階段最優(yōu)決策表，如下回溯得此表12例2消費(fèi)–庫(kù)存管理問題(延續(xù)變量)設(shè)某廠方案全年消費(fèi)某種產(chǎn)品A。其四個(gè)季度的訂貨量分別為600公斤，700公斤，500公斤和1200公斤。知消費(fèi)產(chǎn)品A的消費(fèi)費(fèi)用與產(chǎn)品的平方成正比，系數(shù)為0.005。廠內(nèi)有倉(cāng)庫(kù)可存放產(chǎn)品，存儲(chǔ)費(fèi)為每公斤每季度1元。求最正確的消費(fèi)安排使年總本錢最小。解：四個(gè)季度為四個(gè)階段，采用階段編號(hào)與季度順序一致。設(shè)sk為第k季初的庫(kù)存量，那么邊境條件為s1=s5=0設(shè)xk為第k季的消費(fèi)量，設(shè)yk為第k季的訂貨量；sk，xk，yk都取實(shí)數(shù)，形狀轉(zhuǎn)移方程為sk+1=sk+xk-yk仍采用反向遞推，但留意階段編號(hào)是正向的目的函數(shù)為13例2消費(fèi)–庫(kù)存管理問題(延續(xù)變量)第一步：(第四季度)總效果f4(s4,x4)=0.005x42+s4由邊境條件有：s5=s4+x4–y4=0，解得：x4*=1200–s4將x4*代入f4(s4,x4)得：f4*(s4)=0.005(1200–s4)2+s4=7200–11s4+0.005s42第二步：(第三、四季度)總效果f3(s3,x3)=0.005x32+s3+f4*(s4)將s4=s3+x3–500代入f3(s3,x3)得：14例2消費(fèi)–庫(kù)存管理問題(延續(xù)變量)第三步：(第二、三、四季度)總效果f2(s2,x2)=0.005x22+s2+f3*(s3)將s3=s2+x2700代入f2(s2,x2)得：留意：階段最優(yōu)總效果僅是當(dāng)前形狀的函數(shù)，與其后的決策無關(guān)15例2消費(fèi)–庫(kù)存管理問題(延續(xù)變量)第四步：(第一、二、三、四季度)總效果f1(s1,x1)=0.005x12+s1+f2*(s2)將s2=s1+x1–600=x1–600代入f1(s1,x1)得：由此回溯：得最優(yōu)消費(fèi)–庫(kù)存方案x1*=600，s2*=0；x2*=700，s3*=0；x3*=800，s4*=300；x4*=900。165.2.2資源分配問題例3某公司有9個(gè)推銷員在全國(guó)三個(gè)不同市場(chǎng)推銷貨物，這三個(gè)市場(chǎng)里推銷人員數(shù)與收益的關(guān)系如下表，試作出使總收益最大的分配方案。解：設(shè)分配人員的順序?yàn)槭袌?chǎng)1,2,3，采用反向階段編號(hào)。設(shè)sk為第k階段尚未分配的人員數(shù)，邊境條件為s3=9設(shè)xk為第k階段分配的推銷人員數(shù)；仍采用反向遞推，形狀轉(zhuǎn)移方程為sk–1=sk–xk目的函數(shù)為17例3第一階段：給第三市場(chǎng)分配s1有0~9種能夠，第一階段最優(yōu)決策表如下：為什么與例1的第一階段的表有差別？由于不存在邊境條件s0=018例3第二階段：給第二市場(chǎng)分配s2有0~9種能夠，第二階段最優(yōu)決策表如下：19例3第三階段：給第一市場(chǎng)分配由邊境條件s3=9，第三階段最優(yōu)決策表如下：得決策過程：x3*=2,x2*=0,x1*=7,f3*=218即市場(chǎng)1分配2人，市場(chǎng)2不分配，市場(chǎng)3分配7人最優(yōu)解與分配的順序有關(guān)嗎？205.2.2資源分配問題例4工程選擇問題某工廠估計(jì)明年有A,B,C,D四個(gè)新建工程，每個(gè)工程的投資額wk及其投資后的收益vk如右表所示。投資總額為30萬元，問如何選擇工程才干使總收益最大。上述問題的靜態(tài)規(guī)劃模型如下：這是一類0-1規(guī)劃問題該問題是經(jīng)典的游覽背包問題(Knapsack)該問題是NP-complete21例4工程選擇問題解：設(shè)工程選擇的順序?yàn)锳,B,C,D;1、階段k=1,2,3,4分別對(duì)應(yīng)D,C,B,A工程的選擇過程2、第k階段的形狀sk，代表第k階段初尚未分配的投資額3、第k階段的決策變量xk,，代表第k階段分配的投資額4、形狀轉(zhuǎn)移方程為sk–1=sk–wkxk5、直接效益dk(sk,xk)=vk或06、總效益遞推公式該問題的難點(diǎn)在于各階段的形狀確實(shí)定，當(dāng)階段添加時(shí)，形狀數(shù)成指數(shù)增長(zhǎng)。下面利用決策樹來確定各階段的能夠形狀。2223例4第一階段(工程D)的選擇過程s1<8時(shí)，x1只能取0；w1=8,v1=524例4第二階段(工程C)的選擇過程25例4第三階段(工程B)的選擇過程第四階段(工程A)的選擇過程265.2.3串聯(lián)絡(luò)統(tǒng)可靠性問題例5有A,B,C三部機(jī)器串聯(lián)消費(fèi)某種產(chǎn)品，由于工藝技術(shù)問題，產(chǎn)品常出現(xiàn)次品。統(tǒng)計(jì)結(jié)果闡明，機(jī)器A,B,C產(chǎn)生次品的概率分別為pA=30%,PB=40%,PC=20%,而產(chǎn)品必需經(jīng)過三部機(jī)器順序加工才干完成。為了降低產(chǎn)品的次品率，決議撥款5萬元進(jìn)展技術(shù)改造，以便最大限制地提高產(chǎn)品的廢品率目的?，F(xiàn)提出如下四種改良方案：方案1:不撥款，機(jī)器堅(jiān)持原狀；方案2:加裝監(jiān)視設(shè)備，每部機(jī)器需款1萬元；方案3:加裝設(shè)備，每部機(jī)器需款2萬元；方案4:同時(shí)加裝監(jiān)視及控制設(shè)備，每部機(jī)器需款3萬元；采用各方案后，各部機(jī)器的次品率如下表。27例5串聯(lián)機(jī)器可靠性問題解：為三臺(tái)機(jī)器分配改造撥款，設(shè)撥款順序?yàn)锳,B,C，階段序號(hào)反向編號(hào)為k，即第一階段計(jì)算給機(jī)器C撥款的效果。設(shè)sk為第k階段剩余款，那么邊境條件為s3=5；設(shè)xk為第k階段的撥款額；形狀轉(zhuǎn)移方程為sk-1=sk-xk；目的函數(shù)為maxR=(1-PA)(1-PB)(1-PC)仍采用反向遞推第一階段：對(duì)機(jī)器C撥款的效果R1(s1,x1)=d1(s1,x1)R0(s0,x0)=d1(s1,x1)28第二階段最優(yōu)決策表第二階段：對(duì)機(jī)器B,C撥款的效果由于機(jī)器A最多只需3萬元，故s22遞推公式：R2(s2,x2)=d2(s2,x2)R1(s1,x1*)例：R2(3,2)=d2(3,2)R1(1,1)=(1-0.2)0.9=0.72得第二階段最優(yōu)決策表29第二階段最優(yōu)決策表第三階段：對(duì)機(jī)器A,B,C撥款的效果邊境條件：s3=5遞推公式：R3(s3,x3)=d3(s3,x3)R2(s2,x2*)例：R3(5,3)=d3(5,3)R2(2,2)=(1-0.05)0.64=0.608得第三階段最優(yōu)決策表回溯：有多組最優(yōu)解。I：x3=1,x2=3,x1=1,R3=0.80.90.9=0.648II：x3=2,x2=2,x1=1,R3=0.90.80.9=0.648III:x3=2,x2=3,x1=0,R3=0.90.90.8=0.64830例6用動(dòng)態(tài)