運籌學課程07-動態(tài)規(guī)劃

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