運籌與決策5動態(tài)規(guī)劃(編輯修改稿)
2024-11-12 12:00 本頁面
【文章內容簡介】 0 5x3= x2=0x4=10 0 18 0181 5 10 0 5x4= x3=0x2=10 0 20 0201 5 12 0 5x4= x2=0x3=10 0 30 0301 5 22 0 5x4= x3= x2=0例 4 第二階段 (項目 C)的選擇過程 w 3 = 1 0 v 3 =8s 3 x 3 d 3 ( s 3 , x 3 ) s 2 = s 3 w 3 x 3 f 2 ( s 2 , x 2 *) f 3 ( s 3 , x 3 *) 條件0 0 15 9 9*151 8 5 0 8x 4 =10 0 30 14 14301 8 20 14 22 *x 4 = 0項目 決策 投資額 直接收益 v kA x 4 =0 0 0B x 3 =1 10 8C x 2 =1 12 9D x 1 =1 8 5總額 30 22 例 4 第三階段 (項目 B)的選擇過程 w 4 = 1 5 v 4 = 1 2s 4 x 4 d 4 ( s 4 , x 4 ) s 3 = s 4 w 4 x 4 f 3 ( s 3 , x 3 *) f 4 ( s 4 , x 4 *) 條件0 0 3 0 22 22*3 0 1 12 15 9 21第四階段 (項目 A)的選擇過程 串聯(lián)系統(tǒng)可靠性問題 例 5 有 A, B, C 三部機器串聯(lián)生產某種產品，由于工藝技術問題，產品常出現(xiàn)次品。統(tǒng)計結果表明，機器 A, B, C 產生次品的概率分別為 pA=30%, PB=40%, PC=20%, 而產品必須經過三部機器順序加工才能完成。為了降低產品的次品率，決定撥款 5 萬元進行技術改造，以便最大限度地提高產品的成品率指標?，F(xiàn)提出如下四種改進方案： 方案 1: 不撥款，機器保持原狀； 方案 2: 加裝監(jiān)視設備，每部機器需款 1 萬元； 方案 3: 加裝設備，每部機器需款 2 萬元； 方案 4: 同時加裝監(jiān)視及控制設備，每部機器需款 3 萬元； 采用各方案后，各部機器的次品率如下表。 A B C不撥款 3 0 % 4 0 % 2 0 %撥款 1 萬元 2 0 % 3 0 % 1 0 %撥款 2 萬元 1 0 % 2 0 % 1 0 %撥款 3 萬元 5% 1 0 % 6% 例 5 串聯(lián)機器可靠性問題 解 ：為三臺機器分配改造撥款，設撥款順序為 A, B, C，階段序號反向編號為 k，即第一階段計算給機器 C 撥款的效果。 設 sk 為第 k 階段剩余款，則邊界條件為 s3=5； 設 xk 為第 k 階段的撥款額； 狀態(tài)轉移方程為 sk1=skxk； 目標函數(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 4第二階段最優(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)=(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 1第二階段最優(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 s 3 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)解。 I： x3=1, x2=3, x1=1, R3= ? ?= II： x3=2, x2=2, x1=1, R3= ??= III: x3=2, x2=3, x1=0, R3= ?? = 例 6 用動態(tài)規(guī)劃解非線性規(guī)劃 解 : 這是一個資源分配問題。設分配次序為 x1, x2, x3，階段正向編號，但逆向遞推，由約束條件可得邊界條件 s1=27, s4=0。 第三階段：（給 x3分配） ??????????0,27)(m ax321321321xxxxxxxxxxf333 )( xxf ?由邊界條件和狀態(tài)轉移方程有： s4=s3?x3=0，即 x3*= s3；因此有， 33*3 )( ssf ?第二階段：（給 x2分配） )(),(3*32222 sfxxsf ??由狀態(tài)轉移方程有： s3=s2?x2，代入上式得， 22222222222222222)(,2,02121),(ssfsxxsxxfxsxxsf?????????????解得 例 6 用動態(tài)規(guī)劃解非線性規(guī)劃 第一階段：（給 x1分配） 212*2111
教學課件相關推薦
鄂ICP備17016276號-1