運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用第五版-胡運(yùn)權(quán)(參考版)
2024-08-27 00:27本頁面
【正文】 238。239。 + + ＃239。11231 1 1 12301 1 1 11 2 3 2 1 6 , 0 x 1m a x2 7 6 9 , 1 x 3xsx x xx x x＃236。+ + 239。= 237。239。238。239。 + +239。22 ?s70 當(dāng) K=1時(shí) ， 第一個(gè)變量的取值為 1x11231 1 111 2 3 301 1 1 2 21 2 3 2 1 6( ) m a x1 2 3 2 1 2xsx x xfsx x x s s＃236。 狀態(tài)變量 表示第 K個(gè)階段初約束條件右端項(xiàng)的剩余值 。 ???????????0,3.122312m a x212132231211xxxxtsxxxxxz68 解： 設(shè)將確定變量 的值作為兩個(gè)階段 ， K=1， 2。 5 一般數(shù)學(xué)規(guī)劃模型的動態(tài)規(guī)劃解法 用動態(tài)規(guī)劃的方法求解一般數(shù)學(xué)規(guī)劃模型思想： ?將取定每個(gè)變量的值作為一個(gè)階段，則有 n個(gè)變量的 數(shù)學(xué)規(guī)劃問題，可看作是有 n 個(gè)階段 的多階段決策問題。 x1 s1 v1(x1)+f2(s1x1) f1(s1) x1* 2 3 4 12 18+80 14+84 10+87 97 4 63 第四節(jié) 離散隨機(jī)型動態(tài)規(guī)劃 模型求解 Solution of Discrete Stochastic DP Model 64 隨機(jī)型的動態(tài)規(guī)劃 ? 指狀態(tài)的轉(zhuǎn)移律是不確定的 ， 即對給定的狀態(tài)和決策，下一階段的到達(dá)狀態(tài)是具有確定概率分布的隨機(jī)變量，這個(gè)概率分布由本階段的狀態(tài)和決策完全確定 第 k+1階段可能的狀態(tài)數(shù) 給定狀態(tài) xk和決策 uk的情況下，下一個(gè)可能到達(dá)的狀態(tài)的概率 從 k階段狀態(tài) sk轉(zhuǎn)移到 k+1階段狀態(tài)為 i時(shí)的指標(biāo)函數(shù)值 隨機(jī)性動態(tài)規(guī)劃的基本結(jié)構(gòu)圖 sk xk Sk+1 65 指標(biāo)函數(shù)為和函數(shù)的轉(zhuǎn)換方程 ? 在隨機(jī)性的動態(tài)規(guī)劃問題下，由于下一階段到達(dá)的狀態(tài)和階段的效益值不確定，只能根據(jù)各階段的期望效益值進(jìn)行優(yōu)化。 ? 狀態(tài)變量 sk：表示每個(gè)階段初擁有的可派遣的巡邏隊(duì)數(shù)是前面階段決策的結(jié)果，也是本階段決策的依據(jù) ? 決策變量 xk： 表示各階段對各部位派出的巡邏隊(duì)數(shù)， ? 各階段允許的 決策集合 Dk(sk)為： ? Dk(sk)={xk|2≤xk≤4|} (k=1,2,3,4) 56 [解 ]2 ? 狀態(tài)轉(zhuǎn)移方程： sk+1=skxk (k=1,2,3,4) ? 每階段初擁有可派遣的巡邏隊(duì)數(shù)量等于上階段初擁有的數(shù)量減去上階段派出的數(shù)量 ? 過程函數(shù)為階段指標(biāo)函數(shù)之和： ? 階段指標(biāo)函數(shù) vk(xk)表示 k階段派出的巡邏隊(duì)數(shù)為 xk時(shí)，該階段的部位的預(yù)期損失值 44, 4 1 , 41( ) ( ) ( ) ( )k i i k k i i k k ki k i kV v x v x v x v x V ?? ? ?? ? ? ? ???57 [解 ]3 ? fk(sk)：表示從 k階段狀態(tài)為 sk出發(fā)，采用最優(yōu)子策略到過程結(jié)束時(shí)的預(yù)期損失值，有 ? 先考慮給 D部位派巡邏隊(duì)，即 k=4，上式可寫為 ? 邊界條件 f5(s5)=0 ，所以 11()( ) m in { ( ) ( ) }k k kk k k k k kx D sf s v x f s?????4 4 44 4 4 4 5 5()( ) m in { ( ) ( ) }x D sf s v x f s???4 4 44 4 4 4()( ) m in { ( ) }x D sf s v x??58 [解 ]4 x4 s4 v4(x4) f4(s4) x4* 2 3 4 2 34 — — 34 2 3 34 31 — 31 3 4 34 31 25 25 4 5 34 31 25 25 4 6 34 31 25 25 4 因 D4（ s4） ={2， 3， 4}，又 s4的可能值是 2≤s4≤6，故由表 81的數(shù)據(jù)，可得下表的結(jié)果 4 4 44 4 4 4()( ) m in { ( ) }x D sf s v x??總共 12支巡邏隊(duì)，每部位 2~4支巡邏隊(duì)。 ? 問該警衛(wèi)部門應(yīng)往各部位分別派多少支巡邏隊(duì)，使總的預(yù)期損失為最小 。52 (2)當(dāng)指標(biāo)函數(shù)為階段指標(biāo)積形式 逆序解法 基本方程為： 基本方程為： 順序解法 ??? nkjjjjnk usvV ),( ,????kjjjjk usvV11,1 ),( 1111( ) { ( , ) ( ) } , 1 , .. ., 2 , 1( ) 1kkk k k k k k kuDnnf s o p t v s u f s k n nfs?????? ? ? ???????????????? ????1)(,...,2,1)}(),({)(10111sfnksfusvoptsf kkkkkDukkkk53 第 3節(jié) 離散確定型動態(tài)規(guī)劃 模型求解 Solution of Discrete Certain DP Model 54 例 4 ? 某一警衛(wèi)部門共有 12支巡邏隊(duì)，負(fù)責(zé) 4個(gè)要害部位 A、 B、 C、 D的警衛(wèi)巡邏。 =239。239。239。 = + =239。1 1 101( ) { ( , ) ( ) } 1 , 2 , .. .,( ) 0kkk k k k k k kuDf s o p t v s x f s k nfs+ + 206。239。239。239。 = + = 239。1111( ) { ( , ) ( ) } , 1 , .. ., 2 , 1( ) 0kkk k k k k k kuDnnf s o p t v s x f s k n nfs++206。 51 3. 基本方程形式不同 (1)當(dāng)指標(biāo)函數(shù)為階段指標(biāo)和形式 逆序解法 則基本方程為： 則基本方程為： 順序解法 , ( , )nk n j j jjkV v s x== 229。 順序解法中，定義最優(yōu)指標(biāo)函數(shù) fk(sk+1)表示第 k段時(shí)從起點(diǎn)到狀態(tài) sk+1的前部子過程最優(yōu)效益值。 43 第一步： k=0 狀態(tài)： s1＝ A f0(A)＝ 0 求解步驟 順序解法求解 44 第二步： k=1 狀態(tài)： B1 B2 x1*(B1)=A x1*(B2)=A f1(B1)＝ 4 f1(B2)
物理相關(guān)推薦
鄂ICP備17016276號-1