動態(tài)規(guī)劃(ppt)

1、動態(tài)規(guī)劃李孟濤動態(tài)規(guī)劃是運(yùn)籌學(xué)的一個分支，是求解多階段決策過程最優(yōu)化問題的數(shù)學(xué)方法。動態(tài)規(guī)劃在經(jīng)濟(jì)管理、工程技術(shù)、工農(nóng)業(yè)生產(chǎn)及軍事部門中都有著廣泛的應(yīng)用，并且獲得了顯著的效果。學(xué)習(xí)動態(tài)規(guī)劃，我們首先要了解多階段決策問題。最短路徑問題：給定一個交通網(wǎng)絡(luò)圖如下，其中兩點之間的數(shù)字表示距離（或運(yùn)費），試求從A點到G點的最短距離（總運(yùn)輸費用最?。?23456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643背包問題 有一個徒步旅行者，其可攜帶物品重量的限度為a 公斤，設(shè)有n 種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（

2、作用），問此人應(yīng)如何選擇攜帶的物品（各幾件），使所起作用（使用價值）最大？物品 1 2 j n重量（公斤/件） a1 a2 aj an每件使用價值 c1 c2 cj cn 類似的還有工廠里的下料問題、運(yùn)輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題等。 生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計劃。機(jī)器負(fù)荷分配問題：某種機(jī)器可以在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機(jī)器在兩種不同的負(fù)荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達(dá)到最高。航天飛機(jī)

3、飛行控制問題：由于航天飛機(jī)的運(yùn)動的環(huán)境是不斷變化的，因此就要根據(jù)航天飛機(jī)飛行在不同環(huán)境中的情況，不斷地決定航天飛機(jī)的飛行方向和速度（狀態(tài)），使之能最省燃料和完成飛行任務(wù)（如軟著陸）。根據(jù)過程的特性可以將過程按空間、時間等標(biāo)志分為若干個互相聯(lián)系又互相區(qū)別的階段。在每一個階段都需要做出決策，從而使整個過程達(dá)到最好的效果。各個階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個階段的決策確定后，就組成了一個決策序列，因而也就決定了整個過程的一條活動路線，這樣的一個前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策問題。多階段決策過程的特點：針對多階段決策過程的最優(yōu)化問題，美國

4、數(shù)學(xué)家Bellman等人在20世紀(jì)50年代初提出了著名的最優(yōu)化原理，把多階段決策問題轉(zhuǎn)化為一系列單階段最優(yōu)化問題，從而逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法：動態(tài)規(guī)劃。對最佳路徑（最佳決策過程）所經(jīng)過的各個階段，其中每個階段始點到全過程終點的路徑，必定是該階段始點到全過程終點的一切可能路徑中的最佳路徑（最優(yōu)決策），這就是Bellman提出的著名的最優(yōu)化原理。簡言之， 一個最優(yōu)策略的子策略必然也是最優(yōu)的。Bellman在1957年出版的Dynamic Programming是動態(tài)規(guī)劃領(lǐng)域的第一本著作。動態(tài)規(guī)劃的基本概念階段；狀態(tài)；決策和策略；狀態(tài)轉(zhuǎn)移；指標(biāo)函數(shù)。1 階段（Stage） 將所

5、給問題的過程，按時間或空間特征分解成若干個相互聯(lián)系的階段，以便按次序去求每階段的解，常用k表示階段變量。2 狀態(tài)（State） 各階段開始時的客觀條件叫做狀態(tài)。描述各階段狀態(tài)的變量稱為狀態(tài)變量，常用sk表示第k階段的狀態(tài)變量，狀態(tài)變量的取值集合稱為狀態(tài)集合，用Sk表示。 動態(tài)規(guī)劃中的狀態(tài)具有如下性質(zhì)： 當(dāng)某階段狀態(tài)給定以后，在這階段以后的過程的發(fā)展不受這段以前各段狀態(tài)的影響。即：過程的過去歷史只能通過當(dāng)前狀態(tài)去影響它未來的發(fā)展，這稱為無后效性。如果所選定的變量不具備無后效性，就不能作為狀態(tài)變量來構(gòu)造動態(tài)規(guī)劃模型。3 決策和策略（Decision and Policy） 當(dāng)各段的狀態(tài)確定以后，就

6、可以做出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策。決策變量用dk(Sk)表示，允許決策集合用Dk(Sk)表示。 各個階段決策確定后，整個問題的決策序列就構(gòu)成一個策略，用p1,n(d1,d2,dn)表示。對每個實際問題，可供選擇的策略有一定的范圍，稱為允許策略集合，用P表示。使整個問題達(dá)到最優(yōu)效果的策略就是最優(yōu)策略。4 狀態(tài)轉(zhuǎn)移方程 動態(tài)規(guī)劃中本階段的狀態(tài)往往是上一階段的決策結(jié)果。如果給定了第k段的狀態(tài)Sk ，本階段決策為dk(Sk) ，則第k+1段的狀態(tài)Sk+1由公式： Sk+1=Tk（ Sk， dk）確定，稱為狀態(tài)轉(zhuǎn)移方程。5 指標(biāo)函數(shù) 用于衡量所選定策略優(yōu)劣的數(shù)量指標(biāo)

7、稱為指標(biāo)函數(shù)。最優(yōu)指標(biāo)函數(shù)記為fk(Sk)。 例1、從A 地到E 地要鋪設(shè)一條煤氣管道,其中需經(jīng)過三級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。問應(yīng)該選擇什么路線，使總距離最短？ 二. 最短路徑問題C1AB2B1B3C3D1D2E52141126101043121113965810521C2 解：整個計算過程分四個階段，從最后一個階段開始。 第四階段（D E）： D 有兩條路線到終點E 。 顯然有AB2B1B3C1C3D1D2E52141126101043121113965810521C2首先考慮經(jīng)過 的兩條路線第三階段（C D）： C 到D 有 6 條路線。(最短路線為 )AB2B1

8、B3C1C3D1D2E5214126101043121113965810521C2AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為 )考慮經(jīng)過 的兩條路線AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為 )考慮經(jīng)過 的兩條路線AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為 )第二階段（B C）： B 到C 有 9 條路線。首先考慮經(jīng)過 的3條路線AB2B1B3C1C3D1D2E5214126101043121113965810521C2(最短路線為 )考慮經(jīng)過 的3條路線AB2B1B3C1C3D1D2E52141261