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

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