運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃ppt課件(2)-在線瀏覽
2025-06-20 18:35本頁(yè)面
【正文】 等于 1,2,3,4 。 1 2 3 4 2）、 狀態(tài) ( state) 各階段開(kāi)始時(shí)的出發(fā)點(diǎn)稱(chēng)作狀態(tài)。 在例 ７ .1 中，第一階段的狀態(tài)為 A ，第二階段的狀態(tài)為城市 B1， B2 和 B3。 1 2 3 4 3）、 決策 （ Decision ) 當(dāng)各階段的狀態(tài)確定以后，就可以做出不同的決定或選擇，從而確 定下一階段的狀態(tài)，這種決定就是決策，表示決策的變量稱(chēng)為決策變量。 1 2 3 4 4）、策略（ Policy） 在各階段決策確定以后， 整個(gè)問(wèn)題的決策序列就構(gòu)成了一個(gè) 策略 , 用 P1n(s1)表示。 1 2 3 4 5）、目標(biāo)函數(shù) 用于衡量所選定策略?xún)?yōu)劣的數(shù)量指標(biāo)稱(chēng)作 目標(biāo)函數(shù)。 目標(biāo)函數(shù)的最優(yōu)值稱(chēng)為 最優(yōu)目標(biāo)函數(shù) ，最優(yōu)目標(biāo)函數(shù)記為 fk(sk)， 它表示從第 K階段的狀態(tài) Sk出發(fā)采用的最優(yōu)策略。 , 在例 ７ .1中，目標(biāo)函數(shù)就是距離。本問(wèn)題的總目標(biāo)是求 f 1(A), 即從 A到 E的最短距離。所以如果給 定了第 K 階段的狀態(tài) k s 和該階段的決策 k x ( k s ) ，則第 K+1 段的狀態(tài) 1 + k s 由于 K 階段決策的完成也就完全確定了 , 它們之間的關(guān)系可用如下公式表示： 1 + k s ＝ k T （ k s ， k x ） 其中， k T 表示從狀態(tài) k s 出發(fā)經(jīng)過(guò) k x 向下一階段的轉(zhuǎn)移 ( Transfer) ，換 言之， 即 1 + k s 是從狀態(tài) k s 出發(fā)經(jīng)過(guò)決策 k x 轉(zhuǎn)移的結(jié)果。在例 ７ .1 中 , 狀態(tài)轉(zhuǎn)移方程即 1 + k s ＝ k x 。不難知道 ,從 A到E共有 18條不同的路線 ,每條路線有四個(gè)階段 ,要做 3次加法 ,要求出最短路線需做 54次加法運(yùn)算和 17次比較運(yùn)算 ,這叫做 窮舉法 。 下面應(yīng)用動(dòng)態(tài)規(guī)劃方法求解例７ .1。 運(yùn)用逆序遞推方法的好處是可以始終盯住目標(biāo) ,不致脫離最終目標(biāo)。 為方便應(yīng)用，規(guī)定用 d(sk， sk+1)表示由狀態(tài) sk出發(fā)，到達(dá)下一階段 sk+1時(shí)的兩點(diǎn)距離。 3 f （ 3 C ）＝ min + + ) ( ) , ( ) ( ) , ( 2 4 2 3 1 4 1 3 D f D C d D f D C d =min + + 3 3 4 1 =5 1 2 3 4 S1 S2 S3 S4 第三步 , K=2 由于第 3 段各點(diǎn) C1,C2,C3 到終點(diǎn) E 的最短距離 f 3 (C1), f 3 (C2), f 3 (C3), 已知 , 所以要求城市 B1 到 E 的最短距離 , 只需以它們?yōu)榛A(chǔ) , 分別加上 B1 到達(dá) C1,C2,C3 的一段距離 , 加以比較取其最短者即可。把各段的最優(yōu)決策按計(jì)算順序 反推 , 即得到最優(yōu)決策序列 , 即 * 1 x （ A ）＝ 1 B , * 2 x （ 1 B ） = 2 C , * 3 x （ 2 C ） ＝ 2 D ， * 4 x （ 2 D ）＝ E ，所以最短路線為 :A → B1 → C2 → D2 → E. 1 2 3 4 圖 例 ７ .1 各點(diǎn) 到終點(diǎn) 的最短路徑 根據(jù)例 ７ .1, 動(dòng)態(tài)規(guī)劃的基本思想可總結(jié)如下： 一、 將多階段決策過(guò)程劃分階段 , 恰當(dāng)?shù)剡x取狀態(tài)變量 , 決策變量和定 義最優(yōu)目標(biāo)函數(shù) , 從而把問(wèn)題化成一族同類(lèi)型的子問(wèn)題，然后逐個(gè)求解。在每一 個(gè)子問(wèn)題求解時(shí) , 都要利用它前邊已求出的子問(wèn)題的最優(yōu)結(jié)果 , 最后一個(gè)子問(wèn) 題的最優(yōu)解 , 就是整個(gè)問(wèn)題的最優(yōu)解。 在例７ .1的求解過(guò)程中 , 各段的計(jì)算都利用了第 K 段和第 K+1 段的如下 關(guān)系： k f （ k s ）＝ min{ k d （ k s ， sk+1 ）＋ ) ( 1 1 + + k k s f (k=4,3,2,1) (1) ) ( 5 5 s f ＝ 0 (2) 這種遞推關(guān)系稱(chēng)為 動(dòng)態(tài)規(guī)劃的基本方程 ,(2) 式稱(chēng)邊界條件 , 容易算出 , 運(yùn)用動(dòng)態(tài)規(guī)劃方法解例 ７ .1 只進(jìn)行了 17 次加法運(yùn)算 ,11 次比較運(yùn)算，就 獲得了最優(yōu)解 , 比窮舉法的計(jì)算量明顯地要少 , 而且隨著問(wèn)題段數(shù)的增加 和變量程度的提高 , 計(jì)算量將呈指數(shù)規(guī)律減少。 這可由圖 ７ .2 來(lái)描述 ( 用彩色線表示最優(yōu)路線 , 各點(diǎn)上的數(shù)字表最短距離 ) ７ . 最優(yōu)化原理 動(dòng)態(tài)規(guī)劃方法是由美國(guó)數(shù)學(xué)家貝爾曼 () 等人于本世紀(jì) 50 年 代提出的。 最優(yōu)化 原理 可以表述為： “ 一個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì) , 即無(wú)論初始狀態(tài) 和初始決策如何 , 對(duì)于先前決策所形成的狀態(tài)而言 , 其以后的所有決策必構(gòu)成 最優(yōu)策略 。 如果把最優(yōu)化原理用數(shù)學(xué)語(yǔ)言描述 ,就得到了動(dòng)態(tài)規(guī)劃的基本方程： k f （ k s ）＝ opt [ ] ) ( ) , ( 1 1 + + + k k k k k s f x s d (k=n,n 1,…,1) 1 + k f （ 1 + k s ）＝ 0 其中 , opt 可依題意取 max 或 min 7 . 動(dòng)態(tài)規(guī)劃求解的基本步驟 求解動(dòng)態(tài)規(guī)劃 , 就是分析問(wèn)題并建立問(wèn)題的動(dòng)態(tài)規(guī)劃基本方程。 在于識(shí)別問(wèn)題的多階段特征 , 將問(wèn)題 分解成可用遞推關(guān)系式聯(lián)系起來(lái)的若干子問(wèn)題 , 或者說(shuō)是 要正確地建立具 體問(wèn)題的 基本方程 。 1 + k s ＝ ) , ( k k k x s T 。 1 2 3 4 S1 S2 S3 S4 例 P184 某公司有資金１０萬(wàn)元，擬投資于３個(gè)項(xiàng)目，其收益分別為 21 1 1 2 2 2 3 3 3( ) 4 , ( ) 9 , ( ) 2g x x g x x g x x? ? ?可建立以下模型： 21 2 31 2 31 2 3m a x z = 4x 9 2 x 10 x , , 0xxxxxx+++ + ??7 . 動(dòng)態(tài)規(guī)劃求解的基本步驟 2. 狀態(tài)變量 k s ：表示第 K 段可用于剩余的 n k+1 個(gè)項(xiàng)目的資金數(shù) , 顯 然有 1 s =10, 4 s =0 。 ： K=1， 2，３ 4. 狀態(tài)轉(zhuǎn)移方程： k k k x s s ? + 1 5. 最優(yōu)目標(biāo)函數(shù) k f （ k s ）：表示當(dāng)可投資金數(shù)為 k s 時(shí) , 投資于剩余的 n k+1 個(gè)項(xiàng)目的最大收益。 方法是將投資項(xiàng)目排序 , 假想對(duì)各個(gè)投資項(xiàng)目有先后順序。 接下來(lái)的問(wèn)題，便是如 何 選擇正確的 狀態(tài)變量 , 并使各后部子過(guò)程間具有遞推關(guān)系。 3. 決策變量 k x ： 即應(yīng)分配第 K 個(gè)項(xiàng)目上的投資額。 6. 基本方程為： ? ? ? ? + ? + + + + 0 ) ( )] ( ) ( ma
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1