運籌學(xué)基礎(chǔ)及應(yīng)用第五版 胡運權(quán)ppt課件

.,1,第八章動態(tài)規(guī)劃,8.1多階段決策問題8.2最優(yōu)化原理與動態(tài)規(guī)劃的數(shù)學(xué)模型8.3離散確定性動態(tài)規(guī)劃模型的求解8.4離散隨機性動態(tài)規(guī)劃模型的求解8.5一般數(shù)學(xué)規(guī)劃模型的動態(tài)規(guī)劃解法,.,2,理解動態(tài)規(guī)劃基本概念、最優(yōu)化原理和基本方程，逆序法和順序解法，學(xué)習(xí)應(yīng)用動態(tài)規(guī)劃解決多階段決策問題。重點:掌握動態(tài)規(guī)劃模型結(jié)構(gòu)、逆序法算法原理、資源分配、設(shè)備更新、生產(chǎn)與存貯等問題。,學(xué)習(xí)要點：,.,3,第一節(jié)多階段的決策問題,.,4,動態(tài)規(guī)劃（DynamicProgramming）,動態(tài)規(guī)劃是解決復(fù)雜系統(tǒng)優(yōu)化問題的一種方法。是解決動態(tài)系統(tǒng)多階段決策過程的基本方法之一。,.,5,動態(tài)規(guī)劃：是解決多階段決策過程最優(yōu)化問題的一種方法，無特定的數(shù)學(xué)模型。,可解決與時間有關(guān)的動態(tài)問題與時間無關(guān)的靜態(tài)問題,.,6,多階段決策問題1）動態(tài)決策將時間作為變量的決策問題稱為動態(tài)決策。其基本特點是多次決策。2）多階段決策問題是一類特殊形式的動態(tài)決策問題。是指這樣一類活動過程：系統(tǒng)的動態(tài)過程可以按照時間進程分為狀態(tài)互相聯(lián)系而又互相區(qū)別的各個階段，而且在每個階段都要進行決策，當每一個階段的決策確定以后，就完全確定了一個過程的活動路線。,.,7,引例1最短路線問題,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,C1,C3,D1,A,B1,B3,B2,D2,E,C2,.,8,引例2生產(chǎn)與存貯問題要求確定一個逐月的生產(chǎn)計劃，在滿足需求條件下，使一年的生產(chǎn)與存貯費用之和最??？引例3投資決策問題某公司現(xiàn)有資金Q萬元，在今后5年內(nèi)考慮給A，B，C，D4個項目投資？引例4設(shè)備更新問題現(xiàn)企業(yè)要決定一臺設(shè)備未來8年的更新計劃，問應(yīng)在哪些年更新設(shè)備可使總費用最小？,.,9,動態(tài)規(guī)劃方法的特點,優(yōu)點：1）許多問題用動態(tài)規(guī)劃求解比線性規(guī)劃、非線性規(guī)劃更有效，特別是離散性問題，解析數(shù)學(xué)無用武之地，而動態(tài)規(guī)劃成為得力工具。2）某些情況下，用動態(tài)規(guī)劃處理不僅能作定性描述分析，且可利用計算機給出求其數(shù)值解的方法。,.,10,動態(tài)規(guī)劃方法的特點,缺點：1）沒有統(tǒng)一的處理方法，求解時要根據(jù)問題的性質(zhì)，結(jié)合多種數(shù)學(xué)技巧。因此，實踐經(jīng)驗及創(chuàng)造性思維將起重要作用。2）“維數(shù)障礙”：當變量個數(shù)太多時，由于計算機內(nèi)存和速度的限制導(dǎo)致問題無法解決。有些問題由于涉及的函數(shù)沒有理想的性質(zhì)使問題只能用動態(tài)規(guī)劃描述，而不能用動態(tài)規(guī)劃方法求解。,.,11,第二節(jié)最優(yōu)化原理與動態(tài)規(guī)劃的數(shù)學(xué)模型一最短路線問題求解,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(E)=0,.,12,考慮一個階段的最優(yōu)選擇,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D1)=3,f(E)=0,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,.,13,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(D1)=3,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,考慮一個階段的最優(yōu)選擇,.,14,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C1)=4,f(D1)=3,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,考慮二個階段的最優(yōu)選擇,.,15,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C2)=7,f(D1)=3,f(C1)=4,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,2,5,3,4,考慮二個階段的最優(yōu)選擇,.,16,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(C1)=4,f(C2)=7,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,考慮二個階段的最優(yōu)選擇,.,17,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B1)=11,f(C2)=7,f(C1)=4,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,考慮三個階段的最優(yōu)選擇,.,18,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B2)=7,f(C2)=7,f(C1)=4,f(B1)=11,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,考慮三個階段的最優(yōu)選擇,.,19,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,f(C1)=4,f(B1)=11,f(B2)=7,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,考慮三個階段的最優(yōu)選擇,.,20,10,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,f(C1)=4,f(A)=11,f(B2)=7,f(B1)=11,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,四個階段聯(lián)合考慮從A點到E點的最優(yōu)選擇,.,21,6,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,f(C1)=4,f(A)=11,f(B2)=7,f(B1)=11,狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài),A（A，B3）B3,7,5,3,2,4,5,5,1,2,5,3,1,4,6,3,3,3,3,4,.,22,6,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,f(C1)=4,f(A)=11,f(B2)=7,f(B1)=11,狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài),A（A，B3）B3（B3，C2）C2,7,5,3,2,4,5,5,1,2,5,3,1,4,6,3,3,3,3,4,.,23,6,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,f(C1)=4,f(A)=11,f(B2)=7,f(B1)=11,狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài),A（A，B3）B3（B3，C2）C2（C2，D2）D2,7,5,3,2,4,5,5,1,2,5,3,1,4,6,3,3,3,3,4,.,24,6,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,f(C1)=4,f(A)=11,f(B2)=7,f(B1)=11,狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài),A（A，B3）B3（B3，C2）C2（C2，D2）D2（D2，E）E,7,5,3,2,4,5,5,1,2,5,3,1,4,6,3,3,3,3,4,從A到E的最短路徑為11，路線為AB3C2D2E,.,25,通過上例的討論，可以看到多級決策過程具有以下特點：,（1）把整個過程看成（或認為地分成）n個具有遞推關(guān)系的單級過程。（2）采取逐級分析的方法，一般由最后一級開始倒向進行。（3）在每一級決策時，不只考慮本級的性能指標的最優(yōu)，而且同時考慮本級及以后的總性能指標最優(yōu)，因此它是根據(jù)“全局”最優(yōu)作出本級決策的。,.,26,動態(tài)規(guī)劃法較之窮舉法的優(yōu)點:(1)容易計算出結(jié)果；(2)動態(tài)規(guī)劃的計算結(jié)果不僅得到了從起始點到最終點的最短路線，而且得到了中間段任一點到最終點的最短路線。,.,27,動態(tài)規(guī)劃方法的基本思想：(1)將多階段決策過程劃分階段，恰當?shù)剡x取狀態(tài)變量、決策變量及定義最優(yōu)指標函數(shù)從而把問題化成一族同類型的子問題，然后逐個求解。(2)求解時從邊界條件開始，逆(或順)過程行進方向，逐段遞推尋優(yōu)。在每一個子問題求解時，都要使用它前面已求出的子問題的最優(yōu)結(jié)果，最后一個子問題的最優(yōu)解，就是整個問題的最優(yōu)解。(3)動態(tài)規(guī)劃方法是既把當前一段與未來各段分開，又把當前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法，因此每段的最優(yōu)決策選取是從全局考慮的，與該段的最優(yōu)選擇一般是不同的。,.,28,二、基本概念和基本原理,動態(tài)規(guī)劃模型要用到的概念：(1)階段;(2)狀態(tài);(3)決策和策略;(4)狀態(tài)轉(zhuǎn)移律;(5)指標函數(shù)。,1、階段：將所給問題的過程，按時間或空間特征分解成若干互相聯(lián)系的階段，以便按次序去求每階段的解，常用字母k表示階段變量。,.,29,2、狀態(tài)：各階段開始時的客觀條件叫做狀態(tài)。狀態(tài)變量：描述各階段狀態(tài)的變量，用sk表示第k階段的狀態(tài)變量。狀態(tài)集合：狀態(tài)變量的取值集合，用Sk表示。,一階段：S1A二階段：S2B1,B2,B3三階段：S3C1,C2,C3四階段：S4D1,D2,一階段：S1A二階段：S2B1,B2,B3三階段：S3C1,C2,C3四階段：S4D1,D2,二、基本概念和基本原理,.,30,二、基本概念和基本原理,二、基本概念和基本原理,3、決策：當各段的狀態(tài)取定以后，就可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策。決策變量：表示決策的變量，稱為決策變量，常用xk(sk)表示第k階段當狀態(tài)為sk時的決策變量。允許決策集合：決策變量的取值往往限制在一定范圍內(nèi)，我們稱此范圍為允許決策集合，用Dk(sk)表示第k階段從狀態(tài)sk出發(fā)的允許決策集合。,D2(B1)=C1,C2D2(B2)=C1,C2,C3如狀態(tài)為B1時選擇C2，可表示為：u2(B1)=C2,D2(B1)=C1,C2D2(B2)=C1,C2,C3如狀態(tài)為B1時選擇C2，可表示為：x2(B1)=C2,.,31,二、基本概念和基本原理,4策略：各段決策確定后，整個問題的決策序列就構(gòu)成一個策略，用p1,nx1(s1),x2(s2),.xn(sn)表示。允許策略集合：對每個實際問題，可供選擇的策略有一定范圍，稱為允許策略集合，記作P1,n，使整個問題達到最優(yōu)效果的策略就是最優(yōu)策略。,.,32,二、基本概念和基本原理,5、狀態(tài)轉(zhuǎn)移方程：動態(tài)規(guī)劃中本階段的狀態(tài)往往是上一階段狀態(tài)和上一階段的決策結(jié)果。第k段的狀態(tài)sk，本階段決策為xk(sk)，則第k+1段的狀態(tài)sk+1也就完全確定，它們的關(guān)系可用公式表示：sk+1=Tk(sk,xk),.,33,6、指標函數(shù)：用于衡量所選定策略優(yōu)劣的數(shù)量指標。它分為階段指標函數(shù)和過程指標函數(shù)。階段指標函數(shù)是指第k段，從狀態(tài)sk出發(fā)，采取決策xk時的效益，用Vk(sk,uk)表示。過程指標函數(shù)記為fk(sk)：表示從第k段狀態(tài)sk按預(yù)定指標到過程終止時的效益值。,二、基本概念和基本原理,.,34,最簡單的方法窮舉法。共有多少條路徑，依次計算并比較。動態(tài)規(guī)劃方法本方法是從過程的最后一段開始，用逆序遞推方法求解，逐步求出各段各點到終點的最短路線，最后求得起始點到終點的最短路線。,三、最優(yōu)化原理與動態(tài)規(guī)劃的數(shù)學(xué)模型,.,35,最優(yōu)化原理OptimizationPrinciple,作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，對先前決策所形成的狀態(tài)而言，余下的諸決策必構(gòu)成最優(yōu)策略。,若M是從A到B的最優(yōu)路線上的一點，則從M到B的路線也是最優(yōu)的。,.,36,動態(tài)規(guī)劃的基本方程（最優(yōu)化原理的應(yīng)用）,根據(jù)最優(yōu)化原理得到的計算動態(tài)規(guī)劃問題的遞（逆）推關(guān)系式：,邊界條件：k=n時，fn+1(sn+1)=0,邊界條件：k=n時，fn+1(sn+1)=1,Opt:optimization,maxorminvk:k階段的指標函數(shù)fk+1:k+1階段的最優(yōu)指標函數(shù)值fk:k階段的最優(yōu)指標函數(shù)值,.,37,構(gòu)成動態(tài)規(guī)劃模型的條件-1,根據(jù)時間或空間的自然特征，實際問題能恰當?shù)貏澐譃槿舾呻A段，形成多階段決策的過程,.,38,構(gòu)成動態(tài)規(guī)劃模型的條件-2,正確的選擇狀態(tài)變量S動態(tài)規(guī)劃的狀態(tài)應(yīng)具有三個特征：能夠用來描述受控過程的演變特征；滿足無后效性：如果某階段狀態(tài)給定，則在這階段以后過程的發(fā)展只與當前的狀態(tài)有關(guān)，而與過去的歷史無關(guān)?；虍斍暗臓顟B(tài)是過去歷史發(fā)展的一個總結(jié)，過程的過去歷史只能通過當前的狀態(tài)影響未來的發(fā)展。可知性：各階段狀態(tài)變量的值，直接或間接地都是可以知道的。,.,39,構(gòu)成動態(tài)規(guī)劃模型的條件-3,確定決策變量sk的含義及每階段的允許決策集合Dk(sK),.,40,構(gòu)成動態(tài)規(guī)劃模型的條件-4,正確寫出狀態(tài)轉(zhuǎn)移方程sk+1=T(sk,xk(sk)或sk+1=T(sk,xk),.,41,構(gòu)成動態(tài)規(guī)劃模型的條件-5,明確指標函數(shù)Vk,n的關(guān)系一般有兩種形式和式積式,.,42,四逆序解法與順序解法如果尋優(yōu)的方向與多階段決策過程的實際行進方向相反，從最后一段開始計算逐段前推，求得全過程的最優(yōu)策略，稱為逆序解法。順序解法的尋優(yōu)方向同于過程的行進方向，計算時從第一段開始逐段向后遞推，計算后一階段要用到前一階段的求優(yōu)結(jié)果，最后一段計算的結(jié)果就是全過程的最優(yōu)結(jié)果。,.,43,第一步：k=0狀態(tài)：s1A,f0(A)0,求解步驟,順序解法求解,.,44,第二步：k=1狀態(tài)：B1B2,x1*(B1)=A,x1*(B2)=A,f1(B1)4,f1(B2)5,(4),(5),.,45,第三步：k=2狀態(tài)：C1C2C3C4,u2*(C1)=B1,x2*(C2)=B1,x2*(C3)=B1,f2(C1)6,f2(C2)7,f2(C3)10,x2*(C4)=B2,f2(C4)12,(6),(7),(10),(12),x2*(C1)=B1,.,46,第四步：k=3狀態(tài)：D1D2D3,x3*(D1)=C1或C2,x3*(D2)=C2,x3*(D3)=C3,f3(D1)11,f3(D2)12,f3(D3)14,(11),(12),(14),.,47,第五步：k=4狀態(tài)：E1E2,x4*(E1)=D1,x4*(E2)=D2,f4(E1)14,f4(E2)14,(14),(14),.,48,第六步：k=5狀態(tài)：F,u5*(F)=E2,f5(F)17,(17),即從A到F的最短距離為17。最優(yōu)路線為：AB1C2D2E2F,.,49,逆序解法與順序解法建模的不同點,1狀態(tài)轉(zhuǎn)移方式不同sk+1=Tk(sk,xk)sk=Tk(sk+1,xk),.,50,2指標函數(shù)的定義不同逆序解法中，我們定義最優(yōu)指標函數(shù)fk(sk)表示第k段從狀態(tài)sk出發(fā)，到終點后部子過程最優(yōu)效益值，f1(s1)是整體最優(yōu)函數(shù)值。順序解法中，定義最優(yōu)指標函數(shù)fk(sk+1)表示第k段時從起點到狀態(tài)sk+1的前部子過程最優(yōu)效益值。fn(sn+1)是整體最優(yōu)函數(shù)值。,.,51,3.基本方程形式不同(1)當指標函數(shù)為階段指標和形式逆序解法,則基本方程為：,則基本方程為：,順序解法,.,52,(2)當指標函數(shù)為階段指標積形式逆序解法,基本方程為：,基本方程為：,順序解法,.,53,第3節(jié)離散確定型動態(tài)規(guī)劃模型求解,SolutionofDiscreteCertainDPModel,.,54,例4,某一警衛(wèi)部門共有12支巡邏隊，負責(zé)4個要害部位A、B、C、D的警衛(wèi)巡邏。對每個部位可分別派出2-4支巡邏隊，并且由于派出巡邏隊數(shù)的不同，各部位預(yù)期在一段時期內(nèi)可能造成的損失有差別，具體數(shù)字見表8-1。問該警衛(wèi)部門應(yīng)往各部位分別派多少支巡邏隊，使總的預(yù)期損失為最小。,.,55,解-1,階段變量k：把12支巡邏隊往4個部位派遣看成依次分四個階段(k=1，2，3，4)。狀態(tài)變量sk：表示每個階段初擁有的可派遣的巡邏隊數(shù)是前面階段決策的結(jié)果，也是本階段決策的依據(jù)決策變量xk：表示各階段對各部位派出的巡邏隊數(shù)，各階段允許的決策集合Dk(sk)為：Dk(sk)=xk|2xk4|(k=1,2,3,4),.,56,解-2,狀態(tài)轉(zhuǎn)移方程：sk+1=sk-xk(k=1,2,3,4)每階段初擁有可派遣的巡邏隊數(shù)量等于上階段初擁有的數(shù)量減去上階段派出的數(shù)量過程函數(shù)為階段指標函數(shù)之和：階段指標函數(shù)vk(xk)表示k階段派出的巡邏隊數(shù)為xk時，該階段的部位的預(yù)期損失值,.,57,解-3,fk(sk)：表示從k階段狀態(tài)為sk出發(fā)，采用最優(yōu)子策略到過程結(jié)束時的預(yù)期損失值，有先考慮給D部位派巡邏隊，即k=4，上式可寫為邊界條件f5(s5)=0，所以,.,58,解-4,因D4（s4）=2，3，4，又s4的可能值是2s46，故由表8-1的數(shù)據(jù)，可得下表的結(jié)果,總共12支巡邏隊，每部位24支巡邏隊。,.,59,解-5,聯(lián)合考慮對C、D兩個部位派巡邏隊，k=3，有：因D3(s3)=2,3,4，4s38，可得如下結(jié)果,.,60,解-6,考慮對B、C、D三個部位派巡邏隊，k=2，有由D2(s2)=2,3,4，8s210，可得如下結(jié)果,.,61,解-7,考慮對A、B、C、D四個部隊派巡邏隊，即k=1時，有因s1=12,D1(s1)=2,3,4,可得如下結(jié)果,.,62,解-8,最優(yōu)策略