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

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

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

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

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

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

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

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

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