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