數(shù)學(xué)建模動(dòng)態(tài)規(guī)劃ppt課件

西安電子科技大學(xué),.,1,動(dòng)態(tài)規(guī)劃TrendsProgram/ProgrammingDynamic,唐厚儉hjTang,西安電子科技大學(xué),.,2,目錄,引例最短路問題動(dòng)態(tài)規(guī)劃基本概念、模型與方法例題1：載貨問題/背包問題例題2：生產(chǎn)問題例題3：采購與庫存例題4：加工順序問題總結(jié)參考書目課后習(xí)題,西安電子科技大學(xué),.,3,引例：求AG的最短線路,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G,5,3,1,3,6,8,7,6,6,8,3,5,3,3,8,4,2,2,1,2,3,3,3,5,5,2,6,6,4,3,西安電子科技大學(xué),.,4,用同一符號改寫,P0,P11,P12,P21,P22,P23,P24,P31,P32,P33,P41,P42,P43,P51,P52,P6,5,3,1,3,6,8,7,6,6,8,3,5,3,3,8,4,2,2,1,2,3,3,3,5,5,2,6,6,4,3,a243=4,a322=1,西安電子科技大學(xué),.,5,P0,P11,P12,P21,P22,P23,P24,P31,P32,P33,P41,P42,P43,P51,P52,P6,5,3,1,3,6,8,7,6,6,8,3,5,3,3,8,4,2,2,1,2,3,3,3,5,5,2,6,6,4,3,f52=3,f51=4,f41=min(3+f51,5+f52)=7,f42=min(5+f51,2+f52)=5,f43=min(6+f51,6+f52)=9,Pkj到終點(diǎn)的最小代價(jià),西安電子科技大學(xué),.,6,問題的解,P018,P1113,P1216,P2113,P2210,P239,P2412,P317,P326,P338,P417,P425,P439,P514,P523,P60,5,3,1,3,6,8,7,6,6,8,3,5,3,3,8,4,2,2,1,2,3,3,3,5,5,2,6,6,4,3,西安電子科技大學(xué),.,7,動(dòng)態(tài)規(guī)劃的基本概念,階段與階段變量一個(gè)問題需要作出決策的步驟描述階段的變量稱為階段變量，常用k表示狀態(tài)與狀態(tài)變量(Status)每個(gè)階段都有一些特征，即狀態(tài)第k階段的狀態(tài)變量用sk來表示決策與決策變量過程處于某一階段時(shí)可以做出不同的決定用xk(sk)表示k階段sk所做的決策在k階段sk狀態(tài)所有允許決策集合用Dk(sk)表示,西安電子科技大學(xué),.,8,(Strategy,Policy),策略按順序排列的決策組成的集合k子過程由第k階段開始到終止?fàn)顟B(tài)的過程pk,n(sk)=xk(sk),xn(sn)k子過程策略k=1時(shí)為全過程策略,西安電子科技大學(xué),.,9,狀態(tài)轉(zhuǎn)移函數(shù)(Transform),如果給定第k階段狀態(tài)變量sk和該階段的決策變量xk(sk)，則k+1階段的狀態(tài)變量sk+1的值也隨之確定，即sk+1隨sk和xk(sk)的變化而變化，記：sk+1=Tk(sk,xk(sk)稱為狀態(tài)轉(zhuǎn)移方程vk(sk,xk)=f(Tk(sk,xk(sk)為轉(zhuǎn)移費(fèi)用value,西安電子科技大學(xué),.,10,指標(biāo)函數(shù)(回收函數(shù)),用來衡量所實(shí)現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)它定義在全過程或所有后部子過程上的數(shù)量函數(shù):,西安電子科技大學(xué),.,11,最優(yōu)值函數(shù),optimalvaluefunction從第k階段的狀態(tài)sk開始到第n階段的終止?fàn)顟B(tài)sn+1的過程,采用最優(yōu)策略(optimalpolicy)所得到的指標(biāo)函數(shù)稱為最優(yōu)值函數(shù)，記為fk(sk)(k=1,2,n),西安電子科技大學(xué),.,12,P018,P1113,P1216,P2113,P2210,P239,P2412,P317,P326,P338,P417,P425,P439,P514,P523,P60,5,3,1,3,6,8,7,6,6,8,3,5,3,3,8,4,2,2,1,2,3,3,3,5,5,2,6,6,4,3,k=1,k=5,西安電子科技大學(xué),.,13,動(dòng)態(tài)規(guī)劃基本條件,1)將問題轉(zhuǎn)化為n個(gè)階段2)正確選擇狀態(tài)變量sk,使它既能表達(dá)過程，又無后效性和可知性后效性：以后過程的發(fā)展不受以前各階段的影響可知性：規(guī)定的各階段狀態(tài)變量的值是可知的3)確定決策變量xk及每一個(gè)階段的允許決策集合4)寫出狀態(tài)轉(zhuǎn)移方程：sk+1=Tk(sk,xk)5)正確寫出指標(biāo)函數(shù)Vk,n的關(guān)系Vk,n具有可分離性和遞歸關(guān)系函數(shù)是關(guān)于Vk+1,n的嚴(yán)格單調(diào)的,西安電子科技大學(xué),.,14,動(dòng)態(tài)規(guī)劃的基本模型,逆序解法模型順序解法模型,西安電子科技大學(xué),.,15,逆序解法模型,指標(biāo)函數(shù)形式,西安電子科技大學(xué),.,16,西安電子科技大學(xué),.,17,動(dòng)態(tài)規(guī)劃的求解方法,階段1,階段1,階段1,西安電子科技大學(xué),.,18,示例：用逆推法求解,西安電子科技大學(xué),.,19,分析,將其看著三階段的決策問題：有三個(gè)決策，且決策是連續(xù)函數(shù)，因此求最大值一般用到微分令,西安電子科技大學(xué),.,20,西安電子科技大學(xué),.,21,練習(xí)(正推),西安電子科技大學(xué),.,22,動(dòng)態(tài)規(guī)劃應(yīng)用案例分析,例1載貨問題設(shè)有一輛載重為15t的卡車，要裝運(yùn)4種貨物，已知4種貨物的單位重量和價(jià)值如表所示，在載重許可的條件下每輛車載某種貨物的條件不限，試問應(yīng)如何搭配才能使裝載的價(jià)值最大？,西安電子科技大學(xué),.,23,設(shè)決策變量x1,x2,x3,x4分別為4種貨物的轉(zhuǎn)載件數(shù)，問題用線性整數(shù)規(guī)劃：,西安電子科技大學(xué),.,24,用動(dòng)態(tài)規(guī)劃方法,將其轉(zhuǎn)化為四個(gè)階段，各階段標(biāo)記的指標(biāo)函數(shù)為狀態(tài)變量:第k種至第4種貨物允許載重重量允許的狀態(tài)集合為最優(yōu)值函數(shù)狀態(tài)轉(zhuǎn)移方程為允許決策集合為,西安電子科技大學(xué),.,25,逆順序法求解過程,1)k=42)k=33)k=24)k=1,西安電子科技大學(xué),.,26,西安電子科技大學(xué),.,27,程序源碼,西安電子科技大學(xué),.,28,討論最大值,最大值點(diǎn)：sk=15時(shí)，值為22,012345678910111213141500000666661212121212180000566610111212151617180004568910121314161718200034679101213151618192122,西安電子科技大學(xué),.,29,西安電子科技大學(xué),.,30,背包問題,有人帶背包上山，其可攜帶的物品容量限度為aml.設(shè)有n種物品可供他選擇，設(shè)其編號為1,2,n,已知第i重物品單個(gè)容積為ciml，在他上山后的利潤是攜帶數(shù)量xi的函數(shù)mi(xi)。試問此人應(yīng)該如何選取攜帶物品所得的利潤最大,西安電子科技大學(xué),.,31,例題,西安電子科技大學(xué),.,32,例2:生產(chǎn)問題,某工廠購進(jìn)1000臺機(jī)器，準(zhǔn)備生產(chǎn)P1,P2兩種產(chǎn)品。生產(chǎn)P1每臺機(jī)器可收入50萬，損壞率達(dá)65%；生產(chǎn)P2每臺機(jī)器可收入40萬，損壞率只有40%；估計(jì)3年后將有新的機(jī)器出現(xiàn)，舊的全部淘汰。試問：應(yīng)如何安排生產(chǎn)，使3年內(nèi)收入最多？計(jì)劃以1年為周期。,生產(chǎn),收入,損耗,P1,50,65%,P2,40,40%,剩余,35%,60%,西安電子科技大學(xué),.,33,整數(shù)規(guī)劃：設(shè)x1,x2,x3分別表示第1，2，3年生產(chǎn)P1的機(jī)器數(shù)量，y1,y2,y3表示生產(chǎn)P2的機(jī)器數(shù)量,西安電子科技大學(xué),.,34,設(shè)fk(n)為n臺機(jī)器在k年內(nèi)的最大收益，若只安排一年的生產(chǎn)，x3為生產(chǎn)P1的機(jī)器數(shù)目k=1即1年后的最大收益k=2即2年后的最大收益,西安電子科技大學(xué),.,35,最后考慮k=3即考慮3年的生產(chǎn)，第一年生產(chǎn)P1的機(jī)器數(shù)目設(shè)為x1，則,三年生產(chǎn)計(jì)劃安排：第一年1000臺機(jī)器一律生產(chǎn)P2第二年把余下的機(jī)器一律生產(chǎn)P2第三年把所有的機(jī)器改為生產(chǎn)P1總收入為82000萬元，即8.2億元,西安電子科技大學(xué),.,36,例3：采購與庫存安排,某公司需要制定一種產(chǎn)品今后四個(gè)時(shí)期的采購計(jì)劃，根據(jù)市場預(yù)測在今后的四個(gè)時(shí)期內(nèi)，該產(chǎn)品的需求量分別為2,3,2,4。如果每批產(chǎn)品的固定采購成本費(fèi)為3萬元，若不采購成本為0元；每單位產(chǎn)品的成本價(jià)為1萬元；每個(gè)時(shí)期所允許的最大采購批量不超過6個(gè)單位；對于每個(gè)時(shí)期末沒能售出的庫存需要存儲費(fèi)0.5萬元/單位。已知第一階段和最后階段末庫存量均為0，試問公司應(yīng)如何安排各個(gè)時(shí)期的采購和庫存，才能在滿足市場需要的前提下總的成本費(fèi)最小。,西安電子科技大學(xué),.,37,符號定義,k階段xk采購量ck(xk)采購成本skk階段末庫存量hk(sk)庫存成本fk(sk)第k階段內(nèi)的最小總成本,西安電子科技大學(xué),.,38,西安電子科技大學(xué),.,39,西安電子科技大學(xué),.,40,西安電子科技大學(xué),.,41,西安電子科技大學(xué),.,42,例題4：加工排序問題,設(shè)有n個(gè)工件需要在機(jī)床A、B上加工，每個(gè)工件必須先經(jīng)過A而后經(jīng)過B的兩道加工工序，以ai,bi分別表示工件i在A、B上的加工時(shí)間，問：應(yīng)該如何在兩機(jī)床上安排加工順序使在機(jī)床A上加工第一個(gè)工件開始到機(jī)床B上將最后一個(gè)工件加工完為止所用的加工時(shí)間最少？,A,B,3,6,7,2,4,7,5,3,7,4,工件號,1,2,3,4,5,西安電子科技大學(xué),.,43,變量定義,X：在機(jī)床A上等待加工一個(gè)排列x:不屬于X的在A上最后加工完的工件t:A上加工完x的時(shí)刻算起到B上加工完x所需的時(shí)間f(X,t):由狀態(tài)(X,t)出發(fā)，對未加工的工件采用“最優(yōu)”加工順序后，將X中所有工件加工完所需要的時(shí)間f(X,t,i):由狀態(tài)(X,t)出發(fā)，在A上加工工件i，然后再對以后的加工工件采用“最優(yōu)”順序f(X,t,i,j):由狀態(tài)(X,t)出發(fā)，在A上加工工件i，再加工j，然后再對以后的加工工件采用“最優(yōu)”順序,西安電子科技大學(xué),.,44,西安電子科技大學(xué),.,45,求解方法,西安電子科技大學(xué),.,46,動(dòng)態(tài)規(guī)劃回顧,階段與階段變量(k)狀態(tài)與狀態(tài)變量(Sk)決策xk(sk)策略按順序排列的決策組成的集合pk,n(sk)=xk(sk),xn(sn)k子過程策略狀態(tài)轉(zhuǎn)移函數(shù)sk+1=Tk(sk,xk(sk),西安電子科技大學(xué),.,47,指標(biāo)函數(shù)(回收函數(shù)),用來衡量所實(shí)現(xiàn)過程優(yōu)劣的一種數(shù)量指標(biāo)它定義在全過程或所有后部子過程上的數(shù)量函數(shù):,西安電子科技大學(xué),.,48,最優(yōu)值函數(shù),optimalvaluefunction從第k階段的狀態(tài)sk開始到第n階段的終止?fàn)顟B(tài)sn+1的過程,采用最優(yōu)策略(optimalpolicy)所得到的指標(biāo)函數(shù)稱為最優(yōu)值函數(shù)，記為fk(sk)(k=1,2,n),西安電子科技大學(xué),.,49,總結(jié),使用動(dòng)態(tài)規(guī)劃的基本條件將問題轉(zhuǎn)化為恰當(dāng)?shù)膎個(gè)階段正確選擇狀態(tài)變量sk,使之既能表達(dá)過程，又具有無后效性和可知性基本模型逆序解法（最短路問題、生產(chǎn)問題、載貨問題）順序解法（采購與庫存計(jì)劃）求解方法逐步寫出各階段的最優(yōu)值遞歸函數(shù),西安電子科技大學(xué),.,50,動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系,動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃（線性和非線性規(guī)劃等）研究的對象本質(zhì)上都是在若干約束條件下的函數(shù)極值問題。兩種規(guī)劃在很多情況下原則上可以相互轉(zhuǎn)換。,西安電子科技大學(xué),.,51,動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn),能夠得到全局最優(yōu)解由于約束條件確定的約束集合往往很復(fù)雜，即使指標(biāo)函數(shù)較簡單，用非線性規(guī)劃方法也很難求出全局最優(yōu)解。而動(dòng)態(tài)規(guī)劃方法把全過程化為一系列結(jié)構(gòu)相似的子問題，每個(gè)子問題的變量個(gè)數(shù)大大減少，約束集合也簡單得多，易于得到全局最優(yōu)解。特別是對于約束集合、狀態(tài)轉(zhuǎn)移和指標(biāo)函數(shù)不能用分析形式給出的優(yōu)化問題，可以對每個(gè)子過程用枚舉法求解，而約束條件越多，決策的搜索范圍越小，求解也越容易?？梢缘玫揭蛔遄顑?yōu)解。動(dòng)態(tài)規(guī)劃得到的是全過程及所有后部子過程的各個(gè)狀態(tài)的一族最優(yōu)解能夠利用經(jīng)驗(yàn)提高求解效率。,西安電子科技大學(xué),.,52,動(dòng)態(tài)規(guī)劃的缺點(diǎn),沒有統(tǒng)一的標(biāo)準(zhǔn)模型也沒有構(gòu)造模型的通用方法，甚至還沒有判斷一個(gè)問題能否構(gòu)造動(dòng)態(tài)規(guī)劃模型的準(zhǔn)則存在維數(shù)災(zāi)(curseofdimensionality)問題若一維狀態(tài)變量有m個(gè)取值，那么對于n維問題，狀態(tài)xk就有個(gè)mn值，對于每個(gè)狀態(tài)值都要計(jì)算、存儲函數(shù)fk(xk)，對于n稍大（即使n=3）的實(shí)際問題的計(jì)算往往是不現(xiàn)實(shí)的。目前還沒有克服維數(shù)災(zāi)的有效的一般方法。,西安電子科技大學(xué),.,53,作業(yè)1：復(fù)合系統(tǒng)工作可靠性問題,設(shè)某電子設(shè)備由三種組件D1,D2,D3組成，三種部件任一部件失靈，整個(gè)設(shè)備就不能正常工作，因此需要在需要的地方安裝有隨時(shí)可替換的備用件。已知三種組件的價(jià)格和可靠性指標(biāo)如表所示，現(xiàn)要求在設(shè)計(jì)中所使用的費(fèi)用不超過105萬元，試問應(yīng)如何設(shè)計(jì)備用件是該電子設(shè)備的可靠性最大？,組件,單價(jià)(萬元),可靠性,D1,D2,D3,30,15,20,0.9,0.8,0.5,西安電子科技大學(xué),.,54,作業(yè)2：項(xiàng)目資金分配問題,某建筑公司現(xiàn)有在建的A,B,C,D四個(gè)項(xiàng)目，按目前所賠給的人力、設(shè)備和材料，預(yù)計(jì)完成這四個(gè)項(xiàng)目分別需要15周、20周、18周和25周的時(shí)間，管理部門希望能夠提前完成這些項(xiàng)目，為此決定追加35萬元分配給這四個(gè)項(xiàng)目。這樣為這四個(gè)項(xiàng)目分配追加的金額和能夠完成任務(wù)的時(shí)間(周數(shù))如表所示。試問：該公司應(yīng)該如何將這35萬資金分配給A,B,C,D四個(gè)項(xiàng)目，使得提前完成任務(wù)的總時(shí)間為最多。這里假設(shè)追加資金只能以5萬元為一組分配。,西安電子科技大學(xué),.,55,附表：追加資金與完成時(shí)間表,西安電子科技大學(xué),.,56,最長公共子序列,LongestCommonSubsequence(LCS)給定兩個(gè)序列x1.m和y1.n，找出它們的最長公共子序列,西安電子科技大學(xué),.,57,最長上升子序列,LongestIncreaseSubsequence(LIS)給定一個(gè)序列，求它的一個(gè)遞增子序列，使它的元素個(gè)數(shù)