動態(tài)規(guī)劃運籌學(xué)基礎(chǔ)及其應(yīng)用胡運權(quán)第五版1-閱讀頁
2025-01-11 03:38本頁面
【正文】 68 166 165 165 165 0 1718 180 181 180 180 179 177 176 176 175 1 1819 190 190 191 191 191 190 188 187 186 185 2 , 3 , 4 191s1? 9 8 7 6 5 4 3 2 1 0s 1 0 1 2 3 4 5 6 7 8 9x 1 * 0 1 2 3 4 5 6 7 8 9f 1 * 50 61 72 84 97 109 120 131 140 15019 例 3 第三階段：給第一市場分配 由邊界條件 s3=9，第三階段最優(yōu)決策表如下： x 3 s 3 0 1 2 3 4 5 6 7 8 9 x 3 * f 3 *9 2 1 1 213 218 217 215 208 206 202 201 200 2 218s 2 0 1 2 3 4 5 6 7 8 9x 2 * 0 0 0 0 0 0 0 0 1 2 , 3 , 4f 2 * 90 101 1 1 2 124 137 149 160 171 181 191得決策過程： x3*=2, x2*=0, x1*=7, f3*=218 即 市場 1 分配 2人，市場 2 不分配 ，市場 3 分配 7人 最優(yōu)解與分配的順序有關(guān)嗎 ？ 20 資源分配問題 例 4 項目選擇問題 某工廠預(yù)計明年有 A,B,C,D四個新建項目，每個項目的投資額 wk及其投資后的收益 vk如右表所示。 ? 上述問題的靜態(tài)規(guī)劃模型如下： 項目 w k v kA 15 12B 10 8C 12 9D 8 5? 這是一類 01規(guī)劃問題 ? 該問題是經(jīng)典的 旅行背包問題 (Knapsack) ? 該問題是 NPplete ?????????????項入選項未入選 1 030)(maxkkxxwxvxfkkkkkkk21 例 4 項目選擇問題 解 ：設(shè)項目選擇的順序為 A, B, C, D。下面利用決策樹來確定各階段的可能狀態(tài)。統(tǒng)計結(jié)果表明，機器 A, B, C 產(chǎn)生次品的概率分別為 pA=30%, PB=40%, PC=20%, 而產(chǎn)品必須經(jīng)過三部機器順序加工才能完成?，F(xiàn)提出如下四種改進方案： 方案 1: 不撥款，機器保持原狀； 方案 2: 加裝監(jiān)視設(shè)備，每部機器需款 1 萬元； 方案 3: 加裝設(shè)備，每部機器需款 2 萬元； 方案 4: 同時加裝監(jiān)視及控制設(shè)備，每部機器需款 3 萬元； 采用各方案后，各部機器的次品率如下表。 設(shè) sk 為第 k 階段剩余款，則邊界條件為 s3=5； 設(shè) xk 為第 k 階段的撥款額； 狀態(tài)轉(zhuǎn)移方程為 sk1=skxk； 目標(biāo)函數(shù)為 max R=(1PA)(1PB)(1PC) 仍采用反向遞推 第一階段 ：對機器 C 撥款的效果 R1(s1,x1)=d1(s1,x1)? R0(s0,x0)= d1(s1,x1) x1 s10 1 2 3 x1* R1( s1, x1*)0 0 . 8 0 0 . 81 0 . 8 0 . 9 1 0 . 92 0 . 8 0 . 9 0 . 9 1 , 2 0 . 93 0 . 8 0 . 9 0 . 9 0 . 9 4 3 0 . 9 44 0 . 8 0 . 9 0 . 9 0 . 9 4 3 0 . 9 45 0 . 8 0 . 9 0 . 9 0 . 9 4 3 0 . 9 428 第二階段最優(yōu)決策表 第二階段 ：對機器 B, C 撥款的效果 由于機器 A 最多只需 3 萬元，故 s2 ? 2 遞推公式： R2(s2,x2)=d2(s2,x2)? R1(s1,x1*) 例： R2(3,2)=d2(3,2)? R1(1,1)=() ?= 得 第二階段最優(yōu)決策表 x1 s1x1* R1( s1, x1*)0 0 0 . 81 1 0 . 92 1 , 2 0 . 93 3 0 . 9 44 3 0 . 9 45 3 0 . 9 4x 2 s 20 1 2 3 x 2 * R 2( s 2 , x 2 *)2 0 . 5 4 0 . 6 3 0 . 6 4 2 0 . 6 43 0 . 5 6 4 0 . 6 3 0 . 7 2 0 . 7 2 2 , 3 0 . 7 24 0 . 5 6 4 0 . 6 5 8 0 . 7 2 0 . 8 1 3 0 . 8 15 0 . 5 6 4 0 . 6 5 8 0 . 7 5 2 0 . 8 1 3 0 . 8 129 第二階段最優(yōu)決策表 第三階段 ：對機器 A, B, C 撥款的效果 邊界條件： s3 = 5 遞推公式： R3(s3,x3)=d3(s3,x3)? R2(s2,x2*) 例： R3(5,3)=d3(5,3)? R2(2,2)=() ?= 得 第三階段最優(yōu)決策表 x 2 s 2x 2 * R 2( s 2 , x 2 *)2 2 0 . 6 43 2 , 3 0 . 7 24 3 0 . 8 15 3 0 . 8 1 s3 x 3 0 1 2 3 x 3 * R 3 ( s 3 , x 3 *)5 0 . 5 6 7 0 . 6 4 8 0 . 6 4 8 0 . 6 0 8 1 , 2 0 . 6 4 8回溯 ： 有多組最優(yōu)解 。設(shè)分配次序為 x1, x2, x3，階段正向編號，但逆向遞推，由約束條件可得邊界條件 s1=27, s4=0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1