運(yùn)籌學(xué)課程07-動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃 DynamicProgramming 不要過(guò)河拆橋追求全局最優(yōu) 多階段決策過(guò)程的最優(yōu)化 動(dòng)態(tài)規(guī)劃的基本概念和基本原理 動(dòng)態(tài)規(guī)劃方法的基本步驟 動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例 本章內(nèi)容 一 多階段決策過(guò)程的最優(yōu)化 示例1 工廠生產(chǎn)安排 某種機(jī)器可以在高 低兩種負(fù)荷下生產(chǎn) 高負(fù)荷生產(chǎn)條件下機(jī)器完好率為0 7 即如果年初有u臺(tái)完好機(jī)器投入生產(chǎn) 則年末完好的機(jī)器數(shù)量為0 7u臺(tái) 系數(shù)0 7稱為完好率 年初投入高負(fù)荷運(yùn)行的u臺(tái)機(jī)器的年產(chǎn)量為8u噸 系數(shù)8稱為單臺(tái)產(chǎn)量 低負(fù)荷運(yùn)行時(shí) 機(jī)器完好率為0 9 單臺(tái)產(chǎn)量為5噸 設(shè)開(kāi)始時(shí)有1000臺(tái)完好機(jī)器 要制訂五年計(jì)劃 每年年初將完好的機(jī)器一部分分配到高負(fù)荷生產(chǎn) 剩下的機(jī)器分配到低負(fù)荷生產(chǎn) 使五年的總產(chǎn)量為最高 設(shè)有數(shù)量為y的某種資源 將它分別投入兩種生產(chǎn)方式A和B 已知收益函數(shù)分別是g x 和h x x為資源投入量 設(shè)這種資源用于生產(chǎn)后還可以回收一部分用于生產(chǎn) A B的回收率分別為a和b 0 a 1 0 b 1 問(wèn) 對(duì)總數(shù)量為y的資源進(jìn)行n個(gè)階段的生產(chǎn) 應(yīng)如何分配每個(gè)階段投入A B的資源數(shù)量 才能使總收益最大 推廣 多階段資源分配問(wèn)題 示例2 設(shè)備更新問(wèn)題 一般企業(yè)用于生產(chǎn)活動(dòng)的設(shè)備 剛買來(lái)時(shí)故障少 經(jīng)濟(jì)效益高 即使進(jìn)行轉(zhuǎn)讓 處理價(jià)值也高 隨著使用年限的增加 就會(huì)逐漸變?yōu)楣收隙?維修費(fèi)用增加 可正常使用的工時(shí)減少 加工質(zhì)量下降 經(jīng)濟(jì)效益差 并且 使用的年限越長(zhǎng) 處理價(jià)值也越低 自然 如果賣去舊的買新的 還需要付出更新費(fèi) 因此就需要綜合權(quán)衡決定設(shè)備的使用年限 使總的經(jīng)濟(jì)效益最好 一般化工生產(chǎn)過(guò)程中 常包含一系列完成生產(chǎn)過(guò)程的設(shè)備 前一工序設(shè)備的輸出則是后一工序設(shè)備的輸入 因此 應(yīng)該如何根據(jù)各工序的運(yùn)行工況 控制生產(chǎn)過(guò)程中各設(shè)備的輸入和輸出 以使總產(chǎn)量最大 示例3 連續(xù)生產(chǎn)過(guò)程的控制問(wèn)題 示例4 最短路徑問(wèn)題 給定一個(gè)交通網(wǎng)絡(luò)圖如下 其中兩點(diǎn)之間的數(shù)字表示距離 或花費(fèi) 試求從A點(diǎn)到G點(diǎn)的最短距離 總費(fèi)用最小 1 2 3 4 5 6 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 3 6 8 5 3 3 8 4 2 2 2 1 3 3 3 5 2 5 6 6 4 3 示例5 生產(chǎn)與存儲(chǔ)問(wèn)題 某工廠生產(chǎn)并銷售某種產(chǎn)品 已知今后四個(gè)月市場(chǎng)需求預(yù)測(cè)及每月生產(chǎn)j個(gè)單位產(chǎn)品的費(fèi)用如下 每月庫(kù)存i個(gè)單位產(chǎn)品的費(fèi)用E i 0 5i 千元 該廠最大庫(kù)存容量為3個(gè)單位 每月最大生產(chǎn)能力為6個(gè)單位 計(jì)劃開(kāi)始和計(jì)劃期末庫(kù)存量都是零 試制定四個(gè)月的生產(chǎn)計(jì)劃 在滿足用戶需求條件下 使總費(fèi)用最小 每個(gè)月視為一個(gè)階段 每個(gè)階段都須決定生產(chǎn)幾個(gè) 庫(kù)存幾個(gè) 上一個(gè)階段的決策直接影響下一個(gè)階段的決策 由于航天飛機(jī)的運(yùn)動(dòng)的環(huán)境是不斷變化的 因此就要根據(jù)航天飛機(jī)飛行在不同環(huán)境中的情況 不斷地決定航天飛機(jī)的飛行方向和速度 狀態(tài) 使之能最省燃料和實(shí)現(xiàn)目的 如軟著落問(wèn)題 示例6 航天飛機(jī)飛行控制問(wèn)題 10 所謂多階段決策問(wèn)題是指一類活動(dòng)過(guò)程 它可以分為若干個(gè)相互聯(lián)系的階段 在每個(gè)階段都需要作出決策 這個(gè)決策不僅決定這一階段的效益 而且決定下一階段的初始狀態(tài) 每個(gè)階段的決策均確定以后 就得到一個(gè)決策序列 稱為策略 多階段決策問(wèn)題就是求一個(gè)策略 使各階段的效益的總和達(dá)到最優(yōu) 動(dòng)態(tài)規(guī)劃是用來(lái)解決多階段決策過(guò)程最優(yōu)化的一種數(shù)量方法 其特點(diǎn)在于 它可以把一個(gè)n維決策問(wèn)題變換為幾個(gè)一維最優(yōu)化問(wèn)題 從而一個(gè)一個(gè)地去解決 1 2 n 狀態(tài) 決策 狀態(tài) 決策 狀態(tài) 狀態(tài) 決策 不包含時(shí)間因素的靜態(tài)決策問(wèn)題 本質(zhì)上是一次決策問(wèn)題 也可以適當(dāng)?shù)匾腚A段的概念 作為多階段的決策問(wèn)題用動(dòng)態(tài)規(guī)劃方法來(lái)解決 某些線性規(guī)劃 非線性規(guī)劃等靜態(tài)規(guī)劃問(wèn)題也可以通過(guò)適當(dāng)?shù)匾腚A段的概念 應(yīng)用動(dòng)態(tài)規(guī)劃方法加以解決 DP是上個(gè)世紀(jì)五十年代貝爾曼 B E Bellman 為代表的研究成果 屬于現(xiàn)代控制理論的一部分 其最優(yōu)化原理 可歸結(jié)為一個(gè)遞推公式 注意 動(dòng)態(tài)規(guī)劃是求解某類多階段決策問(wèn)題的一種方法 是考察問(wèn)題的一種途徑 不是一種算法 必須對(duì)具體問(wèn)題進(jìn)行具體分析 運(yùn)用動(dòng)態(tài)規(guī)劃的原理和方法 建立相應(yīng)的模型 然后再用動(dòng)態(tài)規(guī)劃方法去求解 動(dòng)態(tài)規(guī)劃思想示例 B C B D B C D E C 4 1 2 3 1 2 3 1 2 3 2 2 1 6 4 7 2 4 8 3 8 6 7 5 6 1 10 6 3 7 5 1 以上求從A到E的最短路徑問(wèn)題 可以轉(zhuǎn)化為四個(gè)性質(zhì)完全相同 但規(guī)模較小的子問(wèn)題 即分別從A到E的最短路徑問(wèn)題 第四階段 兩個(gè)始點(diǎn)和 終點(diǎn)只有一個(gè) 分析得知 從和到E的最短路徑唯一 第三階段 有三個(gè)始點(diǎn)C1 C2 C3 終點(diǎn)有D1 D2 對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求C1 C2 C3到D1 D2的最短路徑問(wèn)題 分析得知 如果經(jīng)過(guò)C1 則最短路為C1 D2 E 如果經(jīng)過(guò)C2 則最短路為C2 D2 E 如果經(jīng)過(guò)C3 則最短路為C3 D1 E 第二階段 有4個(gè)始點(diǎn)B1 B2 B3 B4 終點(diǎn)有C1 C2 C3 對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求B1 B2 B3 B4到C1 C2 C3的最短路徑問(wèn)題 分析得知 如果經(jīng)過(guò)B1 則走B1 C2 D2 E 如果經(jīng)過(guò)B2 則走B2 C3 D1 E 如果經(jīng)過(guò)B3 則走B3 C3 D1 E 如果經(jīng)過(guò)B4 則走B4 C3 D1 E 第一階段 只有1個(gè)始點(diǎn)A 終點(diǎn)有B1 B2 B3 B4 對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求A到B1 B2 B3 B4的最短路徑問(wèn)題 最后 可以得到 從A到E的最短路徑為A B4 C3 D1 E 以上計(jì)算過(guò)程及結(jié)果 可用下圖表示 可以看到 以上方法不僅得到了從A到D的最短路徑 同時(shí) 也得到了從圖中任一點(diǎn)到E的最短路徑 以上過(guò)程 僅用了22次加法 計(jì)算效率遠(yuǎn)高于窮舉法 B C B D B C D E C 4 1 2 3 1 2 3 1 2 3 3 2 1 6 4 7 2 4 8 3 8 6 7 5 1 6 10 6 0 10 6 12 11 11 12 13 14 14 12 7 5 1 2 二 動(dòng)態(tài)規(guī)劃的基本概念和基本原理 基本概念1 階段 把一個(gè)問(wèn)題的過(guò)程 恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段 以便于按一定的次序去求解 描述階段的變量稱為階段變量 階段的劃分 一般是根據(jù)時(shí)間和空間的自然特征來(lái)進(jìn)行的 但要便于問(wèn)題轉(zhuǎn)化為多階段決策 2 狀態(tài) 表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件 通常一個(gè)階段有若干個(gè)狀態(tài) 描述過(guò)程狀態(tài)的變量稱為狀態(tài)變量 一個(gè)數(shù)一組數(shù)一個(gè)向量 狀態(tài)變量的取值有一定的允許集合或范圍 此集合稱為狀態(tài)允許集合 3 決策 表示當(dāng)過(guò)程處于某一階段的某個(gè)狀態(tài)時(shí) 可以作出不同的決定 從而確定下一階段的狀態(tài) 這種決定稱為決策 描述決策的變量 稱為決策變量 決策變量是狀態(tài)變量的函數(shù) 可用一個(gè)數(shù) 一組數(shù)或一向量 多維情形 來(lái)描述 在實(shí)際問(wèn)題中決策變量的取值往往在某一范圍之內(nèi) 此范圍稱為允許決策集合 系統(tǒng)在某一階段的狀態(tài)轉(zhuǎn)移不但與系統(tǒng)的當(dāng)前的狀態(tài)和決策有關(guān) 而且還與系統(tǒng)過(guò)去的歷史狀態(tài)和決策有關(guān) 4 多階段決策過(guò)程 可以在各個(gè)階段進(jìn)行決策 去控制過(guò)程發(fā)展的多段過(guò)程 其發(fā)展是通過(guò)一系列的狀態(tài)轉(zhuǎn)移來(lái)實(shí)現(xiàn)的 圖示如下 狀態(tài)轉(zhuǎn)移方程是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程 如果第k階段狀態(tài)變量sk的值 該階段的決策變量一經(jīng)確定 第k 1階段狀態(tài)變量sk 1的值也就確定 其狀態(tài)轉(zhuǎn)移方程如下 一般形式 能用動(dòng)態(tài)規(guī)劃方法求解的多階段決策過(guò)程是一類特殊的多階段決策過(guò)程 即具有無(wú)后效性的多階段決策過(guò)程 如果狀態(tài)變量不能滿足無(wú)后效性的要求 應(yīng)適當(dāng)?shù)馗淖儬顟B(tài)的定義或規(guī)定方法 動(dòng)態(tài)規(guī)劃中能處理的狀態(tài)轉(zhuǎn)移方程的形式 狀態(tài)具有無(wú)后效性的多階段決策過(guò)程的狀態(tài)轉(zhuǎn)移方程如下 無(wú)后效性 馬爾可夫性 如果某階段狀態(tài)給定后 則在這個(gè)階段以后過(guò)程的發(fā)展不受這個(gè)階段以前各段狀態(tài)的影響 過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它未來(lái)的發(fā)展 狀態(tài)變量要滿足無(wú)后效性的要求 5 策略 是一個(gè)按順序排列的決策組成的集合 在實(shí)際問(wèn)題中 可供選擇的策略有一定的范圍 稱為允許策略集合 從允許策略集合中找出達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略 6 狀態(tài)轉(zhuǎn)移方程 是確定過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過(guò)程 描述了狀態(tài)轉(zhuǎn)移規(guī)律 7 指標(biāo)函數(shù)和最優(yōu)值函數(shù) 用來(lái)衡量所實(shí)現(xiàn)過(guò)程優(yōu)劣的一種數(shù)量指標(biāo) 為指標(biāo)函數(shù) 指標(biāo)函數(shù)的最優(yōu)值 稱為最優(yōu)值函數(shù) 在不同的問(wèn)題中 指標(biāo)函數(shù)的含義是不同的 它可能是距離 利潤(rùn) 成本 產(chǎn)量或資源消耗等 動(dòng)態(tài)規(guī)劃模型的指標(biāo)函數(shù) 應(yīng)具有可分離性 并滿足遞推關(guān)系 小結(jié) 指標(biāo)函數(shù)形式 和 積 無(wú)后效性 可遞推 原過(guò)程的一個(gè)后部子過(guò)程 原過(guò)程的一個(gè)后部子過(guò)程的策略 對(duì)于任意給定的k 1 k n 從第k段到第n段的過(guò)程稱為原過(guò)程的一個(gè)后部子過(guò)程 最優(yōu)策略 解多階段決策過(guò)程問(wèn)題 求出 f1 s1 從k到終點(diǎn)最優(yōu)策略子策略的最優(yōu)目標(biāo)函數(shù)值 問(wèn)題分成4個(gè)階段 k 1 2 3 4 線路 線路 k 1 k 3 階段 狀態(tài) 第一階段的狀態(tài) 第二階段的狀態(tài) sk s4 Sk sk S3 s3 5 6 7 注 n個(gè)階段的決策過(guò)程有個(gè)n 1狀態(tài)變量 sn 1表示sn演變的結(jié)果 S5 10 決策 決策 可取值為 5 6 7 5 6 7 允許決策集合 策略 最短路問(wèn)題 策略 行進(jìn)方案 如 允許策略集合 最優(yōu)策略 使整個(gè)問(wèn)題達(dá)到最優(yōu)效果的策略 策略 最優(yōu)策略 最短的行進(jìn)路線 策略 最短路問(wèn)題 原過(guò)程的一個(gè)策略 后部子過(guò)程的策略 后部子過(guò)程的策略 后部子過(guò)程的策略 or 每月庫(kù)存i個(gè)單位產(chǎn)品的費(fèi)用E i 0 5i 千元 該廠最大庫(kù)存容量為3個(gè)單位 每月最大生產(chǎn)能力為6個(gè)單位 計(jì)劃開(kāi)始和計(jì)劃期末庫(kù)存量都是零 試制定四個(gè)月的生產(chǎn)計(jì)劃 在滿足用戶需求條件下 使總費(fèi)用最小 k 1 2 3 4 階段 第k階段的狀態(tài)變量sk S1 0 S2 0 1 2 3 S3 0 1 2 3 S4 0 1 2 3 第k個(gè)月月初的庫(kù)存量 生產(chǎn)與存儲(chǔ)問(wèn)題 某工廠生產(chǎn)并銷售某種產(chǎn)品 已知今四個(gè)月市場(chǎng)需求預(yù)測(cè)如下表 又每月生產(chǎn)j個(gè)單位產(chǎn)品的費(fèi)用為 2 3 4 5 2 3 4 5 0 1 2 3 3 一個(gè)策略 一個(gè)生產(chǎn)方案 2 5 0 4 2 3 2 4 費(fèi)用 21 千元 費(fèi)用 23 千元 最優(yōu)策略 使總費(fèi)用最小的生產(chǎn)方案 最優(yōu)化原理 基本原理 作為整個(gè)過(guò)程的最優(yōu)策略具有這樣的性質(zhì) 無(wú)論過(guò)去的狀態(tài)和決策如何 相對(duì)于前面的決策所形成的當(dāng)前狀態(tài)而言 余下的決策序列必然構(gòu)成最優(yōu)子策略 也就是說(shuō) 一個(gè)最優(yōu)策略的子策略也是最優(yōu)的 對(duì)最短路問(wèn)題 最短路問(wèn)題的基本方程 k 4 3 2 1 從最后一階段開(kāi)始 用由后向前的方法 求出各點(diǎn)到終點(diǎn)的最短路線 最后 求得由起點(diǎn)到終點(diǎn)的最短路線 對(duì)于生產(chǎn)與存儲(chǔ)問(wèn)題 某工廠生產(chǎn)并銷售某種產(chǎn)品 已知今四個(gè)月市場(chǎng)需求預(yù)測(cè)如下表 又每月生產(chǎn)j個(gè)單位產(chǎn)品費(fèi)用為每月庫(kù)存i個(gè)單位產(chǎn)品的費(fèi)用E i 0 5i 千元 該廠最大庫(kù)存容量為3個(gè)單位 每月最大生產(chǎn)能力為6個(gè)單位 計(jì)劃開(kāi)始和計(jì)劃期末庫(kù)存量都是零 試制定四個(gè)月的生產(chǎn)計(jì)劃 在滿足用戶需求條件下 使總費(fèi)用最小 階段k 1 2 3 4 狀態(tài)變量 第k個(gè)月月初的庫(kù)存量 狀態(tài)轉(zhuǎn)移方程 當(dāng)k 4時(shí) u4 s4 對(duì)應(yīng)的總費(fèi)用 生產(chǎn)費(fèi) 庫(kù)存費(fèi) 庫(kù)存費(fèi)E i 0 5i 最大庫(kù)存容量為3個(gè)單位 最大生產(chǎn)能力為6個(gè)單位 計(jì)劃開(kāi)始和計(jì)劃期末庫(kù)存量為零 0 1 2 3 4 7 4 3 6 5 3 2 6 2 1 5 5 1 當(dāng)k 3時(shí) 庫(kù)存費(fèi)E i 0 5i 最大庫(kù)存容量為3個(gè)單位 最大生產(chǎn)能力為6個(gè)單位 計(jì)劃開(kāi)始和計(jì)劃期末庫(kù)存量為零 0 1 2 3 0 1 2 3 0 u3 3 對(duì)應(yīng)的總費(fèi)用 生產(chǎn)費(fèi) 庫(kù)存費(fèi) 庫(kù)存費(fèi)E i 0 5i 最大庫(kù)存容量為3個(gè)單位 最大生產(chǎn)能力為6個(gè)單位 計(jì)劃開(kāi)始和計(jì)劃期末庫(kù)存量為零 0 2345 12 12 5 13 13 5 12 2 1 1234 11 5 12 12 5 13 11 5 1 2 0123 811 51212 5 8 0 3 012 8 8 0 11 5 12 0 1 2 3 4 7 4 3 6 5 3 2 6 2 1 5 5 1 當(dāng)k 2時(shí) u2 s2 對(duì)應(yīng)的總費(fèi)用 生產(chǎn)費(fèi) 庫(kù)存費(fèi) 0 2345 12 12 5 13 13 5 12 2 1 1234 11 5 12 12 5 13 11 5 1 2 0123 811 51212 5 8 0 3 012 811 512 8 0 k 3 當(dāng)k 2時(shí) 0 1 2 3 3456 18 18 5 16 17 16 5 2345 17 51815 516 5 1234 17 0123 13 51714 515 5 15 5 4 15 3 13 5 0 17 5 15 16 當(dāng)k 1時(shí) u1 0 對(duì)應(yīng)的總費(fèi)用 生產(chǎn)費(fèi) k 2 0 1 2 3 3456 18 18 5 16 17 16 5 2345 17 51815 516 5 1234 1717 51516 0123 13 51714 515 5 15 5 4 15 3 13 5 0 當(dāng)k 1時(shí) 0 2345 2221 5 21 2 21 21 5 生產(chǎn)存儲(chǔ)問(wèn)題的基本方程 最短路問(wèn)題的基本方程 k 4 3 2 1 三 動(dòng)態(tài)規(guī)劃方法建?；疽笈c步驟 建模要素 1 階段數(shù)k 2 狀態(tài)變量sk 3 決策變量uk sk 4 指標(biāo)函數(shù)Vk n 狀態(tài)轉(zhuǎn)移方程 5 最優(yōu)值函數(shù)fk sk DP建?；疽?1 所研究的問(wèn)題必須能夠分成幾個(gè)相互聯(lián)系的階段 而且在每一個(gè)階段都具有需要進(jìn)行決策的問(wèn)題 2 在每一階段都必須有若干個(gè)與該階段相關(guān)的狀態(tài) 建模時(shí)總是從與決策有關(guān)的條件中 或是從問(wèn)題的約束條件中去選擇狀態(tài)變量 一般情況下 狀態(tài)是所研究系統(tǒng)在該階段可能處于的情況或條件 3 具有明確的指標(biāo)函數(shù) 且階段指標(biāo)值可以計(jì)算 4 能正確列出最優(yōu)值函數(shù)的遞推公式和邊界條件 b 能通過(guò)現(xiàn)階段的決策 使當(dāng)前狀態(tài)轉(zhuǎn)移成下一階段的狀態(tài) 反映過(guò)程的演變性 即能夠給出狀態(tài)轉(zhuǎn)移方程 c 狀態(tài)的無(wú)后效性 狀態(tài)的選取必須注意以下幾個(gè)要點(diǎn) a 在所研究問(wèn)題的各階段 都能直接或間接確定狀態(tài)變量的取值 可知性 建立DP模型的步驟1 劃分階段劃分階段是運(yùn)用動(dòng)態(tài)規(guī)劃求解多階段決策問(wèn)題的第一步 在確定多階段特性后 按時(shí)間或空間先后順序 將過(guò)程劃分為若干相互聯(lián)系的階段 對(duì)于靜態(tài)問(wèn)題要人為地賦予 時(shí)間 概念 以便劃分階段 2 正確選擇狀態(tài)變量選擇變量既要能確切描述過(guò)程演變又要滿足無(wú)后效性 而且各階段狀態(tài)變量的取值能夠確定 一般地 狀態(tài)變量的選擇是從過(guò)程演變的特點(diǎn)中尋找 3 確定決策變量及允許決策集合通常選擇所求解問(wèn)題的關(guān)鍵變量作為決策變量 同時(shí)要給出決策變量的取值范圍 即確定允許決策集合 4 確定狀態(tài)轉(zhuǎn)移方程根據(jù)k階段狀態(tài)變量和決策變量 寫出k 1階段狀態(tài)變量 狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系 5 確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù) 建立動(dòng)態(tài)規(guī)劃基本方程階段指標(biāo)函數(shù)是指第k階段的收益 最優(yōu)指標(biāo)函數(shù)是指從第k階段狀態(tài)出發(fā)到第n階段末所獲得收益的最優(yōu)值 最后寫出動(dòng)態(tài)規(guī)劃基本方程 以上五步是建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟 由于動(dòng)態(tài)規(guī)劃模型與線性規(guī)劃模型不同 動(dòng)態(tài)規(guī)劃模型沒(méi)有統(tǒng)一的模式 建模時(shí)必須根據(jù)具體問(wèn)題具體分析 只有通過(guò)不斷實(shí)踐總結(jié) 才能較好掌握建模方法與技巧 四 動(dòng)態(tài)規(guī)劃方法應(yīng)用舉例 動(dòng)態(tài)規(guī)劃常用基本方程 從A地到D地要鋪設(shè)一條煤氣管道 其中需經(jīng)過(guò)兩級(jí)中間站 兩點(diǎn)之間的連線上的數(shù)字表示距離 如圖所示 問(wèn)應(yīng)該選擇什么路線 使總距離最短 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 1 最短路徑問(wèn)題 解 整個(gè)計(jì)算過(guò)程分三個(gè)階段 從最后一個(gè)階段開(kāi)始 第一階段 C D C有三條路線到終點(diǎn)D A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 顯然有f1 C1 1 f1 C2 3 f1 C3 4 d B1 C1 f1 C1 3 1f2 B1 mind B1 C2 f1 C2 min3 3d B1 C3 f1 C3 1 44 min6 45 第二階段 B C B到C有六條路線 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 B1 B2 最短路線為B1 C1 D d B2 C1 f1 C1 2 1f2 B2 mind B2 C2 f1 C2 min3 3d B2 C3 f1 C3 1 43 min6 35 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 B1 B2 最短路線為B2 C1 D 第三階段 A B A到B有二條路線 f3 A 1 d A B1 f2 B1 2 4 6f3 A 2 d A B2 f2 B2 4 3 7 f3 A min min 6 7 6 d A B1 f2 B1 d A B2 f2 B2 最短路線為A B1 C1 D A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 B1 B2 A A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 B1 B2 A 最短路線為A B1 C1 D路長(zhǎng)為6 2 資源分配問(wèn)題 某公司有資金a萬(wàn)元 擬投資于n個(gè)項(xiàng)目 已知對(duì)第i個(gè)項(xiàng)目投資xi萬(wàn)元 收益為gi xi 問(wèn)應(yīng)如何分配資金可使總收益最大 解 階段k 1 2 n 狀態(tài)變量sk 決策變量uk 第k個(gè)項(xiàng)目的投資額 在第k階段時(shí)可以用于投資第k到第n個(gè)項(xiàng)目的資金數(shù) 狀態(tài)轉(zhuǎn)移方程 sk 1 sk uk 指標(biāo)函數(shù)Vk n 第k至第n個(gè)項(xiàng)目的最大總收益 最優(yōu)值函數(shù) 邊界條件 k n n 1 2 1 資源分配問(wèn)題的動(dòng)態(tài)規(guī)劃基本方程 建立遞推公式 投資額 收益 工廠 某有色金屬公司擬撥出50萬(wàn)元對(duì)所屬三家冶煉廠進(jìn)行技術(shù)改造 若以十萬(wàn)元為最少分割單位 各廠收益與投資的關(guān)系如下表 問(wèn) 對(duì)三個(gè)工廠如何分配 才能使總收益達(dá)到最大 狀態(tài)變量sk 階段k 1 2 3 決策變量uk 給工廠k的投資額 在第k階段時(shí)可供工廠k到工廠3分配的資金數(shù) 狀態(tài)轉(zhuǎn)移方程 sk 1 sk uk gk uk 給工廠k投資uk 十萬(wàn)元 的收益 指標(biāo)函數(shù)Vk n 資源分配問(wèn)題示例 fk sk 投資工廠k至工廠3所得的最大總收益 求f1 5 在工廠k 可供分配的資金數(shù)為sk時(shí) 基本方程 k 3 0 0 1 1 2 2 3 3 0 5 7 8 4 5 4 5 10 13 投資額 收益 工廠 k 2 0 0 0 0 1 0 2 3 0123 8 9 9 5 7 5 2 9 5 4 5 投資額 收益 工廠 sk 1 sk uk 0 0 1 1 2 2 3 3 0 5 7 8 4 5 4 5 10 13 k 1 sk 1 sk uk 投資額 收益 工廠 5 16 012345 12 1 17 最大總收益 最優(yōu)策略 0 0 0 0 1 0 2 3 0123 8 9 9 5 7 5 2 9 5 4 5 系統(tǒng)由n個(gè)部件串聯(lián)組成 每一個(gè)部件上裝有備用件 部件i i 1 2 n 上裝有xi個(gè)備用元件時(shí) 正常工作的概率為pi xi 設(shè)裝一個(gè)i部件的設(shè)備元件費(fèi)用為ci 重量wi為 要求總費(fèi)用不超過(guò)C 總重量不超過(guò)W 問(wèn)如何選擇各個(gè)部件的備用元件數(shù) 使整個(gè)系統(tǒng)的工作可靠性最大 3 復(fù)合系統(tǒng)工作可靠性問(wèn)題 設(shè)A 整個(gè)系統(tǒng)正常工作 Ai 部件i正常工作 滿足 非線性規(guī)劃問(wèn)題 解 n個(gè)部件 n個(gè)階段 決策變量uk 部件k上所裝的備用元件數(shù)xk 狀態(tài)變量 sk 第k個(gè)到第n個(gè)部件可使用的總費(fèi)用 yk 第k個(gè)到第n個(gè)部件容許的總重量 狀態(tài)轉(zhuǎn)移方程 指標(biāo)函數(shù)Vk n 最優(yōu)指標(biāo)函數(shù)fk sk yk 在部件k 可使用的總費(fèi)用為sk 總重量為yk時(shí) 從部件k到部件n的系統(tǒng)工作可靠性的最大值 復(fù)合系統(tǒng)工作可靠性的動(dòng)態(tài)規(guī)劃基本方程為 與問(wèn)題無(wú)關(guān) 有一個(gè)徒步旅行者 其可攜帶物品重量的限度為a公斤 設(shè)有n種物品可供他選擇裝入包中 已知每種物品的重量及使用價(jià)值 作用 問(wèn)此人應(yīng)如何選擇攜帶的物品 各幾件 使所起作用 使用價(jià)值 最大 這就是背包問(wèn)題 類似的還有工廠里的下料問(wèn)題 運(yùn)輸中的貨物裝載問(wèn)題 人造衛(wèi)星內(nèi)的物品裝載問(wèn)題等 4 背包問(wèn)題 設(shè)xj為第j種物品的裝件數(shù) 非負(fù)整數(shù) 則問(wèn)題的數(shù)學(xué)模型如下 用動(dòng)態(tài)規(guī)劃方法求解 令fx y 總重量不超過(guò)y公斤 包中只裝有前k種物品時(shí)的最大使用價(jià)值 其中y 0 k 1 2 n 所以問(wèn)題就是求fn a 其遞推關(guān)系式為 當(dāng)k 1時(shí) 有 求下面背包問(wèn)題的最優(yōu)解 解 a 5 問(wèn)題是求f3 5 所以 最優(yōu)解為X 1 1 0 最優(yōu)值為Z 13 一種機(jī)器能在高低兩種不同的負(fù)荷狀態(tài)下工作 設(shè)機(jī)器在高負(fù)荷下生產(chǎn)時(shí) 產(chǎn)量函數(shù)為P1 8u1 其中u1為在高負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目 年完好率為a 0 7 即到年底有70 的機(jī)器保持完好 在低負(fù)荷下生產(chǎn)時(shí) 產(chǎn)量函數(shù)為P2 5u2 其中u2為在低負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目 年完好率為b 0 9 設(shè)開(kāi)始生產(chǎn)時(shí)共有1000臺(tái)完好的機(jī)器 請(qǐng)問(wèn)每年應(yīng)該如何把完好機(jī)器分配給高 低兩種負(fù)荷下生產(chǎn) 才能使得5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高 5 機(jī)器負(fù)荷分配問(wèn)題 解建立動(dòng)態(tài)規(guī)劃模型 分為5個(gè)階段 每個(gè)階段為1年 設(shè)狀態(tài)變量sk表示在第k階段初擁有的完好機(jī)器數(shù)目 k 1 2 3 4 5 決策變量xk表示第k階段中分配給高負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目 k 1 2 3 4 5 顯然sk xk為分配給低負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目 狀態(tài)轉(zhuǎn)移方程為階段指標(biāo)rk sk xk 8xk 5 sk xk 最優(yōu)指標(biāo)函數(shù)其中k 1 2 3 4 5 f6 s6 0 第5階段 因?yàn)閒5 s5 是x5的線性單調(diào)增函數(shù) 故有x5 s5 于是有f5 s5 8s5 第4階段 同樣地 f4 s4 是x4的線性單調(diào)增函數(shù) 有x4 s4 f4 s4 13 6s4 對(duì)前幾個(gè)階段依次類推 可得f3 s3 17 5s3 f2 s2 20 75s2 f1 s1 23 72s1 因?yàn)槠诔豕灿型旰脵C(jī)器1000臺(tái) 故s1 1000 有f1 s1 23 72s1 23720 即5年最大的產(chǎn)量為23720臺(tái) 得最優(yōu)解為 這意味著前兩年應(yīng)把年初完好機(jī)器完全投入低負(fù)荷生產(chǎn) 后三年應(yīng)把年初完好機(jī)器完全投入高負(fù)荷生產(chǎn) 下一步工作是確定每年初的狀態(tài) 按照從前向后的順序依次計(jì)算出每年年初完好的機(jī)器數(shù)目 已知s1 1000 根據(jù)狀態(tài)轉(zhuǎn)移方程 有 上面所討論的最優(yōu)策略過(guò)程 初始端狀態(tài)s1 1000臺(tái)是固定的 終點(diǎn)狀態(tài)s6沒(méi)有要求 這種情況下得到最優(yōu)決策稱為初始端固定終點(diǎn)自由的最優(yōu)策略 如果終點(diǎn)附加一定的條件 則問(wèn)題就稱為 終端固定問(wèn)題 例如 規(guī)定在第5年度結(jié)束時(shí)仍要保持500臺(tái)機(jī)器完好 而不是278臺(tái) 應(yīng)如何安排生產(chǎn)才能使得總產(chǎn)量最大 下面來(lái)分析 根據(jù)終點(diǎn)條件有可得 顯然 由于固定了終點(diǎn)的狀態(tài) x5的取值受到了約束 因此有類似 容易解得 f4 s4 21 7s4 7500 依次類推 得f3 s3 24 5s3 7500f2 s2 27 1s2 7500f1 s1 29 4s1 7500再采用順序方法遞推計(jì)算各年的狀態(tài) 有s1 1000 可見(jiàn) 為了使終點(diǎn)完好的機(jī)器數(shù)量增加到500臺(tái) 需要安排前四年中全部完好機(jī)器都要投入低負(fù)荷生產(chǎn) 且在第5年 也只能全部投入高負(fù)荷 相應(yīng)的最優(yōu)指標(biāo)為f1 s1 29 4s1 7500 21900 可以看到 因?yàn)樵黾恿烁郊訔l件 總產(chǎn)量f1 s1 要比終點(diǎn)自由情況下的產(chǎn)量要低 一臺(tái)設(shè)備的價(jià)格為P 運(yùn)行壽命為n年 每年的維修費(fèi)用是設(shè)備役齡的函數(shù) 記為C t 新設(shè)備的役齡為t 0 舊設(shè)備出售的價(jià)格是設(shè)備役齡的函數(shù) 記為S t 在n年末 役齡為t的設(shè)備殘值為R t 現(xiàn)有一臺(tái)役齡為T的設(shè)備 在使用過(guò)程中 使用者每年都面臨 繼續(xù)使用 或 更新 的策略 7 設(shè)備更新問(wèn)題 設(shè)具體數(shù)據(jù)如下 97 由以上計(jì)算可知 本問(wèn)題有兩個(gè)決策 它們對(duì)應(yīng)的最小費(fèi)用都是115 這兩個(gè)決策是 例 季節(jié)工問(wèn)題 某工廠的生產(chǎn)任務(wù)隨季節(jié)波動(dòng) 為降低成本宜用季節(jié)臨時(shí)工 但熟練的生產(chǎn)工人臨時(shí)難以聘到 培訓(xùn)新手費(fèi)用又高 各季節(jié)工人需用量如下表所示 每季節(jié)超過(guò)需用量聘用 每人浪費(fèi)2000元 聘用或解聘費(fèi)為200元乘上兩個(gè)季節(jié)聘用人數(shù)之差的平方 問(wèn)廠長(zhǎng)一年中應(yīng)如何聘用工人可使總花費(fèi)最小 假定工資按實(shí)際工作時(shí)間計(jì)算 則聘用人數(shù)可為分?jǐn)?shù) 季度i春夏秋冬春 需用量gk255220240200255 方案1 255220240200255 總費(fèi)用 200 352 200 552 200 202 200 402 1249000 方案2 255245245245255 總費(fèi)用 200 102 200 102 2000 25 2000 5 2000 45 190000 解 階段1 狀態(tài)變量sk 第k 1季度聘用人數(shù) 決策變量uk 第k季度聘用人數(shù) 狀態(tài)轉(zhuǎn)移方程 sk 1 uk fk sk 第k 1季度聘用人數(shù)為sk人時(shí) 第k季度到第4季度的最小總費(fèi)用 220 s2 255 gk uk 255 季度i春夏秋冬春 需用量gk255220240200255 2 3 4