動(dòng)態(tài)規(guī)劃的基本概念ppt課件.ppt

運(yùn)籌學(xué) 動(dòng)態(tài)規(guī)劃 1 第五章動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支 它是從1951年開始 由美國人貝爾曼 R Belman 為首的一個(gè)學(xué)派發(fā)展起來的 動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì) 管理 軍事 工程技術(shù)等方面都有廣泛的應(yīng)用 動(dòng)態(tài)規(guī)劃是解決多階段決策過程的最優(yōu)化問題的一種方法 所謂多階段決策過程是指這樣一類決策過程 它可以把一個(gè)復(fù)雜問題按時(shí)間 或空間 分成若干個(gè)階段 每個(gè)階段都需要作出決策 以便得到過程的最優(yōu)結(jié)局 由于在每個(gè)階段采取的決策是與時(shí)間有關(guān)的而且前一階段采取的決策如何 不但與該階段的經(jīng)濟(jì)效果有關(guān) 還影響以后各階段的經(jīng)濟(jì)效果 可見這類多階段決策問題是一個(gè)動(dòng)態(tài)的問題 因此 處理的方法稱為動(dòng)態(tài)規(guī)劃方法 然而 動(dòng)態(tài)規(guī)劃也可以處理一些本來與時(shí)間沒有關(guān)系的靜態(tài)模型 這只要在靜態(tài)模型中人為地引入 時(shí)間 因素 分成時(shí)段 就可以把它看作是多階段的動(dòng)態(tài)模型 用動(dòng)態(tài)規(guī)劃方法去處理 動(dòng)態(tài)規(guī)劃對于解決多階段決策問題的效果是明顯的 但也有一定的局限性 首先 它沒有統(tǒng)一的處理方法 必須根據(jù)問題的各種性質(zhì)并結(jié)合一定的技巧來處理 另外當(dāng)變量的維數(shù)增大時(shí) 總的計(jì)算量及存貯量急劇增大 由于計(jì)算機(jī)的存貯量及計(jì)算速度的限制 目前的計(jì)算機(jī)仍不能用動(dòng)態(tài)規(guī)劃方法來解決較大規(guī)模的問題 這就是所謂 維數(shù)障礙 2 需指出 動(dòng)態(tài)規(guī)劃是求解某類問題的一種方法 是考察問題的一種途徑 而不是一種算法 必須對具體問題進(jìn)行具體分析 運(yùn)用動(dòng)態(tài)規(guī)劃的原理和方法 建立相應(yīng)的模型 然后再用動(dòng)態(tài)規(guī)劃方法去求解 1動(dòng)態(tài)規(guī)劃的基本概念 1 1多階段決策問題在研究社會經(jīng)濟(jì) 經(jīng)營管理和工程技術(shù)領(lǐng)域內(nèi)的有關(guān)問題中 有一類特殊形式的動(dòng)態(tài)決策問題 多階段決策問題 在多階段決策過程中 系統(tǒng)的動(dòng)態(tài)過程可以按照時(shí)間進(jìn)程分為相互聯(lián)系而又相互區(qū)別的各個(gè)階段 在每個(gè)階段都要進(jìn)行決策 系統(tǒng)在每個(gè)階段存在許多不同的狀態(tài) 在某個(gè)時(shí)點(diǎn)的狀態(tài)往往要依某種形式受到過去某些決策的影響 而系統(tǒng)的當(dāng)前狀態(tài)和決策又會影響系統(tǒng)過程今后的發(fā)展 因而在尋求多階段決策問題的最優(yōu)解時(shí) 重要的是不能僅僅從眼前的局部利益出發(fā)進(jìn)行決策 而需要從系統(tǒng)所經(jīng)過的整個(gè)期間的總效應(yīng)出發(fā) 有預(yù)見性地進(jìn)行動(dòng)態(tài)決策 找到不同時(shí)點(diǎn)的最優(yōu)決策及整個(gè)過程的最優(yōu)策略 下面舉例說明什么是多階段決策問題 4 例1 最短路線問題 在線路網(wǎng)絡(luò)圖1中 從A至E有一批貨物需要調(diào)運(yùn) 圖上所標(biāo)數(shù)字為各節(jié)點(diǎn)之間的運(yùn)輸距離 為使總運(yùn)費(fèi)最少 必須找出一條由A至E總里程最短的路線 A B1 B2 E B3 C2 C3 C1 D2 D3 D1 4 5 3 4 4 4 3 1 6 5 8 8 7 7 10 2 9 6 為了找到由A至E的最短線路 可以將該問題分成A B C D E4個(gè)階段 在每個(gè)階段都需要作出決策 即在A點(diǎn)需決策下一步到B1還是到B2或B3 同樣 若到達(dá)第二階段某個(gè)狀態(tài) 比如B1 需決定走向C1還是C2 依次類推 可以看出 各個(gè)階段的決策不同 由A至E的路線就不同 當(dāng)從某個(gè)階段的某個(gè)狀態(tài)出發(fā)作出一個(gè)決策 則這個(gè)決策不僅影響到下一個(gè)階段的距離 而且直接影響后面各階段的行進(jìn)線路 所以這類問題要求在各個(gè)階段選擇一個(gè)恰當(dāng)?shù)臎Q策 使這些決策序列所決定的一條路線對應(yīng)的總路程最短 圖1 5 例2 帶回收的資源分配問題 某廠新購某種機(jī)床125臺 據(jù)估計(jì) 這種設(shè)備5年后將被其它設(shè)備所代替 此機(jī)車如在高負(fù)荷狀態(tài)下工作 年損壞率為1 2 年利潤為10萬元 如在低負(fù)荷狀態(tài)下工作 年損壞率為1 5 年利潤為6萬元 問應(yīng)如何安排這些機(jī)床的生產(chǎn)負(fù)荷 才能使5年內(nèi)獲得的利潤最大 本問題具有時(shí)間上的次序性 在五年計(jì)劃的每一年都要作出關(guān)于這些機(jī)床生產(chǎn)負(fù)荷的決策 并且一旦作出決策 不僅影響到本年利潤的多少 而且影響到下一年初完好機(jī)床數(shù) 從而影響以后各年的利潤 所以在每年初作決策時(shí) 必須將當(dāng)年的利潤和以后各年利潤結(jié)合起來 統(tǒng)籌考慮 與上面例1 例2類似的多階段決策問題還有資源分配 生產(chǎn)存貯 可靠性 背包 設(shè)備更新問題等等 6 1 2動(dòng)態(tài)規(guī)劃的基本概念1 階段動(dòng)態(tài)規(guī)劃問題通常都具有時(shí)間或空間上的次序性 因此求解這類問題時(shí) 首先要將問題按一定的次序劃分成若干相互聯(lián)系的階段 以便能按一定次序去求解 如例1 可以按空間次序劃分為A B C D E4個(gè)階段 而例2 按照時(shí)間次序可分成5個(gè)階段 2 狀態(tài)在多階段決策過程中 每階段都需要作出決策 而決策是根據(jù)系統(tǒng)所處情況決定的 狀態(tài)是描述系統(tǒng)情況所必需的信息 如例1中每階段的出發(fā)點(diǎn)位置就是狀態(tài) 例2中每年初擁有的完好機(jī)床數(shù)是作出機(jī)床負(fù)荷安排的根據(jù) 所以年初完好機(jī)床數(shù)是狀態(tài) 一般地 狀態(tài)可以用一個(gè)變量來描述 稱為狀態(tài)變量 記第k階段的狀態(tài)變量為xk k 1 2 n 7 3 決策 多階段決策過程的發(fā)展是用各階段的狀態(tài)演變來描述的 階段決策就是決策者從本階段某狀態(tài)出發(fā)對下一階段狀態(tài)所作出的選擇 描述決策的變量稱為決策變量 當(dāng)?shù)趉階段的狀態(tài)確定之后 可能作出的決策要受到這一狀態(tài)的影響 這就是說決策變量uk還是狀態(tài)變量xk的函數(shù) 因此 又可將第k階段xk狀態(tài)下的決策變量記為uk xk 在實(shí)際問題中 決策變量的取值往往限制在某一范圍之內(nèi) 此范圍稱為允許決策變量集合 記作Dk uk 如例2中取高負(fù)荷運(yùn)行的機(jī)床數(shù)uk為決策變量 則0 uk xk xk是k階段初完好機(jī)床數(shù) 為允許決策變量集合 4 狀態(tài)轉(zhuǎn)移方程 在多階段決策過程中 如果給定了k階段的狀態(tài)變量xk和決策變量uk 則第k 1階段的狀態(tài)變量xk 1也會隨之而確定 也就是說xk 1是xk和uk函數(shù) 這種關(guān)系可記為xk 1 T xk uk 稱之為狀態(tài)轉(zhuǎn)移方程 8 5 策略 在一個(gè)多階段決策過程中 如果各個(gè)階段的決策變量uk xk k 1 2 n 都已確定 則整個(gè)過程也就完全確定 稱決策序列 u1 x1 u2 x2 un xn 為該過程的一個(gè)策略 從階段k到階段n的決策序列稱為子策略 表示成 uk xk uk 1 xk 1 un xn 如例1中 選取一路線A B1 C2 D2 E就是一個(gè)策略 u1 A B1 u2 B1 C2 u3 C2 D2 u4 D2 E 由于每一階段都有若干個(gè)可能的狀態(tài)和多種不同的決策 因而一個(gè)多階段決策的實(shí)際問題存在許多策略可供選擇 稱其中能夠滿足預(yù)期目標(biāo)的策略為最優(yōu)策略 例1中存在12條不同路線 其中A B2 C1 D2 E是最短線路 6 指標(biāo)函數(shù) 用來衡量過程優(yōu)劣的數(shù)量指標(biāo) 稱為指標(biāo)函數(shù) 在階段k的xk狀態(tài)下執(zhí)行決策uk 不僅帶來系統(tǒng)狀態(tài)的轉(zhuǎn)移 而且也必然對目標(biāo)函數(shù)給予影響 階段效應(yīng)就是執(zhí)行階段決策時(shí)給目標(biāo)函數(shù)的影響 9 多階段決策過程關(guān)于目標(biāo)函數(shù)的總效應(yīng)是各階段的階段效應(yīng)累積形成的 常見的全過程目標(biāo)函數(shù)有以下兩種形式 1 全過程的目標(biāo)函數(shù)等于各階段目標(biāo)函數(shù)的和 即 R r1 x1 u1 r2 x2 u2 rn xn un 2 全過程的目標(biāo)函數(shù)等于各階段目標(biāo)函數(shù)的積 即 R r1 x1 u1 r2 x2 u2 rn xn un 指標(biāo)函數(shù)的最優(yōu)值 稱為最優(yōu)函數(shù)值 一般 f1 x1 表示從第1階段x1狀態(tài)出發(fā)至第n階段 最后階段 的最優(yōu)指標(biāo)函數(shù) fk xk 表示從第k階段xk狀態(tài)出發(fā)至第n階段的最優(yōu)指標(biāo)函數(shù) k 1 2 n 10 2動(dòng)態(tài)規(guī)劃的最優(yōu)性原理 多階段決策過程的特點(diǎn)是每個(gè)階段都要進(jìn)行決策 具有n個(gè)階段的決策過程的策略是由n個(gè)相繼進(jìn)行的階段決策構(gòu)成的決策序列 由于前階段的終止?fàn)顟B(tài)又是后一階段的初始狀態(tài) 因此確定階段最優(yōu)決策不能只從本階段的效應(yīng)出發(fā) 必須通盤考慮 整體規(guī)劃 就是說 階段k的最優(yōu)決策不應(yīng)只是本階段的最優(yōu) 而必須是本階段及其所有后續(xù)階段的總體最優(yōu) 即關(guān)于整個(gè)后部子過程的最優(yōu)決策 對此 貝爾曼在深入研究的基礎(chǔ)上 針對具有無后效性的多階段決策過程的特點(diǎn) 提出了著名的多階段決策的最優(yōu)性原理 整個(gè)過程的最優(yōu)策略具有這樣的性質(zhì) 即無論過程過去的狀態(tài)和決策如何 對前面的決策所形成的狀態(tài)而言 余下的諸決策必須構(gòu)成最優(yōu)策略 簡而言之 最優(yōu)性原理的含意就是 最優(yōu)策略的任何一部分子策略也必須是最優(yōu)的 11 如例1 A B2 C1 D2 E是由A到E的最短路線 我們在該路線上任取一點(diǎn)C1 按照最優(yōu)性原理C1 D2 E應(yīng)該是C1到E的最短路 很容易用反證法證明這一結(jié)論的正確性 從而說明最優(yōu)性原理的正確性 按最優(yōu)性原理 可以將例1分成A B C D E4個(gè)階段 由后向前逐步求出各點(diǎn)到E的最短線路 直至求出A至E的最短線路 K 4時(shí) 出發(fā)點(diǎn)有D1 D2 D3 記f4 Di i 1 2 3 為Di到E的最短距離 u4 Di 表示從狀態(tài)Di出發(fā)采取的決策 顯然 f4 D1 7 u4 D1 Ef4 D2 8 u4 D2 Ef4 D3 6 u4 D3 EK 3時(shí) 出發(fā)點(diǎn)有C1 C2 C3 f3 C1 min d C1D1 f4 D1 d C1D2 f4 D2 min 4 7 2 8 10 u3 C1 D2f3 C2 min d C2D2 f4 D2 d C2D3 f4 D3 min 5 8 7 6 13 u3 C2 D2或D3f3 C3 min d C3D2 f4 D2 d C3D3 f4 D3 min 10 8 9 6 15 u3 C3 D3 12 K 2時(shí) 出發(fā)點(diǎn)有B1 B2 B3f2 B1 min d B1C1 f3 C1 d B1C2 f3 C2 min 6 10 4 13 16 u2 B1 C1f2 B2 min d B2C1 f3 C1 d B2C3 f3 C3 min 3 10 1 15 13 u2 B2 C1f2 B3 min d B3C2 f3 C2 d B3C3 f3 C3 min 8 13 4 15 19 u2 B3 C3K 1時(shí) 出發(fā)點(diǎn)只有Ad AB1 f2 B1 4 16f1 A mind AB2 f2 B2 5 13 18 d AB3 f2 B3 3 19u1 A B2由f1 A 18 可知從起點(diǎn)A到終點(diǎn)E的最短距離為18 13 為了找出最短線路 再按計(jì)算順序反推回去 可求出最優(yōu)決策序列 即由u1 A B2 u2 B2 C1 u3 C1 D2 u4 D2 E組成最優(yōu)策略 也就是最短線路為 A B2 C1 D2 E 從上面的例子不難看出 對于最短線路問題 有如下的遞推關(guān)系 函數(shù)方程 fk xk min d xk uk xk fk 1 T xk uk fn 1 xn 1 0k n n 1 1 一般情況下 多階段決策問題存在下面的遞推關(guān)系 fk xk opt rk xk uk xk fk 1 T xk uk uk Dk uk fn 1 xn 1 Ck n n 1 1這里rk xk uk xk 是第階段采用uk xk 決策產(chǎn)生的階段效應(yīng) fn 1 xn 1 C是邊界條件 號大多數(shù)情況下是 號 也可能是 號 稱上述遞推關(guān)系為動(dòng)態(tài)規(guī)劃的基本方程 這個(gè)方程是最優(yōu)化原理的具體表達(dá)形式 14 在基本方程中 rk xk uk xk 1 T xk uk 都是已知函數(shù) 最優(yōu)子策略fk xk 與fk 1 xk 1 之間是遞推關(guān)系 要求出fk xk 及uk xk 需要先求出fk 1 xk 1 這就決定了應(yīng)用動(dòng)態(tài)規(guī)劃基本方程求最優(yōu)策略總是逆著階段的順序進(jìn)行的 另一方面 由于k 1階段的狀態(tài)xk 1 T xk uk 是由前面的狀態(tài)和決策所形成的 在計(jì)算fk 1 xk 1 時(shí)還不能具體確定xk 1的 這就要求必須就k 1階段的各個(gè)可能狀態(tài)計(jì)算fk 1 xk 1 因此動(dòng)態(tài)規(guī)劃不但能求出整個(gè)問題的最優(yōu)策略和最優(yōu)目標(biāo)值 而且還能求出決策過程中所有可能狀態(tài)的最優(yōu)策略及最優(yōu)目標(biāo)值 15 3建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的步驟 最優(yōu)化原理 是動(dòng)態(tài)規(guī)劃的核心 所有動(dòng)態(tài)規(guī)劃問題的遞推關(guān)系都是根據(jù)這個(gè)原理建立起來的 并且根據(jù)遞推關(guān)系依次計(jì)算 最終可求得動(dòng)態(tài)規(guī)劃問題的解 一般來說 利用動(dòng)態(tài)規(guī)劃求解實(shí)際問題需先建立問題的動(dòng)態(tài)模型 具體步驟如下 將問題按時(shí)間或空間次序劃分成若干階段 有些問題不具有時(shí)空次序 也可以人為地引進(jìn)時(shí)空次序 劃分階段 正確選擇狀態(tài)變量xk 這一步是形成動(dòng)態(tài)模型的關(guān)鍵 狀態(tài)變量是動(dòng)態(tài)規(guī)劃模型中最重要的參數(shù) 一般來說 狀態(tài)變量應(yīng)具有以下三個(gè)特性 要能夠用來描述決策過程的演變特征 要滿足無后效性 即如果某階段狀態(tài)已給定后 則以后過程的進(jìn)展不受以前各狀態(tài)的影響 也就是說 過去的歷史只通過當(dāng)前的狀態(tài)去影響未來的發(fā)展 遞推性 即由k階段的狀態(tài)變量xk及決策變量uk可以計(jì)算出k 1階段的狀態(tài)變量xk 1 16 確定決策變量uk及允許決策變量集合Dk uk 根據(jù)狀態(tài)變量之間的遞推關(guān)系 寫出狀態(tài)轉(zhuǎn)移方程 xk 1 T xk uk xk 建立指標(biāo)函數(shù) 一般用rk xk uk 描寫階段效應(yīng) fk xk 表示k n階段的最優(yōu)子策略函數(shù) 建立動(dòng)態(tài)規(guī)劃基本方程 fk xk opt rk xk uk xk fk 1 xk 1 uk Dk uk fn 1 xn 1 Ck n n 1 1以上是建立動(dòng)態(tài)規(guī)劃模型的過程 這個(gè)過程是正確求解動(dòng)態(tài)規(guī)劃的基礎(chǔ) 在動(dòng)態(tài)規(guī)劃基本方程中 rk xk uk xk 1 T xk uk 都是已知函數(shù) 最優(yōu)子策略fk xk 與fk 1 xk 1 之間是遞推關(guān)系 要求出fk xk 及uk xk 需要先求出fk 1 xk 1 這就決定了應(yīng)用動(dòng)態(tài)規(guī)劃基本方程求最優(yōu)策略總是逆著階段的順序進(jìn)行的 由后向前逐步計(jì)算 最終可以算出全過程的最優(yōu)策略函數(shù)值及最優(yōu)策略 17 另一方面 由于k 1階段的狀態(tài)xk 1 T xk uk 是由前面的狀態(tài)xk和決策uk所形成的 在計(jì)算fk 1 xk 1 時(shí)還不能具體確定xk 1的值 所以 這就要求必須就k 1階段的各個(gè)可能狀態(tài)計(jì)算fk 1 xk 1 因此動(dòng)態(tài)規(guī)劃方法不但能求出整個(gè)問題的最優(yōu)策略和最優(yōu)目標(biāo)值 而且還能求出決策過程中所有可能狀態(tài)的最優(yōu)策略及最優(yōu)目標(biāo)值 下面就按上述步驟求解例2 18 例2 帶回收的資源分配問題 某廠新購某種機(jī)床125臺 據(jù)估計(jì) 這種設(shè)備5年后將被其它設(shè)備所代替 此機(jī)床如在高負(fù)荷狀態(tài)下工作 年損壞率為1 2 年利潤為10萬元 如在低負(fù)荷狀態(tài)下工作 年損壞率為1 5 年利潤為6萬元 問應(yīng)如何安排這些機(jī)床的生產(chǎn)負(fù)荷 才能使5年內(nèi)獲得的利潤最大 解 以年為階段 k 1 2 3 4 5取k年初完好的機(jī)床數(shù)為狀態(tài)變量xk以k年初投入高負(fù)荷運(yùn)行的機(jī)床數(shù)為決策變量uk 則低負(fù)荷運(yùn)行機(jī)床數(shù)是xk uk 于是狀態(tài)轉(zhuǎn)移方程為 xk 1 1 2uk 4 5 xk uk 0 8xk 0 3uk以利潤為目標(biāo)函數(shù) 則k年利潤為 10uk 6 xk uk 4uk 6xk記fk xk 為k年至5年末最大總利潤 則動(dòng)態(tài)規(guī)劃基本方程為 fk xk max 4uk 6xk fk 1 0 8xk 0 3uk 0 uk xkf6 x6 0k 5 4 3 2 1 19 以上是建立動(dòng)態(tài)模型的過程 下面具體求解 注意動(dòng)態(tài)規(guī)劃基本方程