【文章內(nèi)容簡(jiǎn)介】 B→C 3→C 2→B 1→A ，最距離為 16；從 C 到 A 的最短路線為 C→C 3→C 2→B 1→A 或 C→D 3→C 2→B 1→A ，最短距離為 21；從 D到 A 的最短路線為 D→D 3→C 2→B 1→A ，最短距離為 20。 表 51 k sk xk vk vk4=vk+fk+1 fk xk* 4 B1 A 3 3+0 3 A C1 A 8 8+0 8 A D1 A 7 7+0 7 A 3 B2 B1 4 4+3 7 B1 C1 2 2+8 C2 B1 3 3+3 6 B1 C1 8 8+8 D1 7 7+7 D2 C1 4 4+8 12 C1 D1 6 6+7 2 B3 B2 10 10+7 17 B2 C2 13 13+6 C3 B2 12 12+7 11 C2 C2 5 5+6 D2 6 6+12 D3 C2 7 7+6 13 C2 D2 8 8+12 1 B B3 9 9+17 16 C3 C3 5 5+11 C B3 10 10+17 21 C D3 C3 10 10+11 D3 8 8+13 D C3 15 15+11 20 D3 D3 7 7+13 12 某工業(yè)部門根據(jù)國(guó)家計(jì)劃的安排，擬將某種高效率的設(shè)備 5 臺(tái)，分配給所屬的甲、乙、丙三個(gè)工廠，各工廠若獲得這種設(shè)備之后，可以為國(guó)家提供的盈利如表 52 所示。 表 52 設(shè)備數(shù) 工廠 0 1 2 3 4 5 甲 0 3 7 9 12 13 乙 0 5 10 11 11 11 丙 0 4 6 11 12 12 問：這 5 臺(tái)設(shè)備如何分配給 各工廠，才能使國(guó)家得到的盈利最大？ 解： 將問題按工廠分為 3 個(gè)階段，甲、乙、丙 3 個(gè)工廠分別編號(hào)為 3； 設(shè) sk 表示分配給第 k 個(gè)工廠至第 n 個(gè)工廠的設(shè)備臺(tái)數(shù)； xk 表示分配給第 k 個(gè)工廠的設(shè)備臺(tái)數(shù)； 則 sk+1=sk xk 為分配給第 k+1 個(gè)工廠至第 n 個(gè)工廠的設(shè)備臺(tái)數(shù)； Pk(xk)表示 xk 臺(tái)設(shè)備分配給第 k 個(gè)工廠所得得盈利值； fk(sk)表示 sk 臺(tái)設(shè)備分配給第 k 個(gè)工廠至第 n 個(gè)工廠時(shí)所得到得最大贏利值。 由以上的假設(shè)可寫出逆推關(guān)系式為 1044( ) m a x [ ( ) ( ) ] , 3 , 2 , 1( ) 0 kkk k k k k k kxsf s P x f s x kfs???? ? ? ??????? 下面采用逆推法進(jìn)行 計(jì)算。 第 3 階段： 設(shè) s3 臺(tái)設(shè)備 (s3=0,1,2,3,4,5)全部分配給工廠丙時(shí)，則最大贏利值為 33 3 3 3( ) max[ ( )]xf s P x? 其中 x3=s3=0,1,2,3,4,5。 因?yàn)榇藭r(shí)只有一個(gè)工廠，有多少臺(tái)設(shè)備就全部分配給工廠丙，故它的盈利值就 是該段的最大盈利值。其數(shù)值計(jì)算如表 53 所示。 表 53 表中 *3x 表示使 33()fs為最大值時(shí)的最優(yōu)決策。 第 2 階段： 13 設(shè)把 s2臺(tái)設(shè)備 (s2=0,1,2,3,4,5)分配給工廠乙和工廠丙時(shí)，則對(duì)每個(gè) s2 值有一種最優(yōu)分配方案，使最大盈利值為 22 2 2 2 3 2 2( ) m a x [ ( ) ( ) ]xf s P x f s x? ? ? 其中 x2=0,1,2,3,4,5。 因?yàn)榻o乙工廠 x2 臺(tái)，其盈利為 P2(x2)，余下的 s2x2 臺(tái)就給丙工廠，則它的盈利最大值為f3(s2x2)?，F(xiàn)要選擇 x2 的值使 2 2 3 2 2( ) ( )P x f s x??取最大值。其數(shù)值計(jì)算 如表 54 所示。 表 54 第 1 階段： 設(shè)把 s1 臺(tái) (這里只有 s1=5 的情況 )設(shè)備分配給甲乙丙 3 個(gè)工廠，則最大盈利值為 11 1 1 2 1( 5 ) m a x [ ( ) ( 5 ) ]xf P x f x? ? ? 其中 x1=0,1,2,3,4,5。 因?yàn)榻o甲工廠 x1臺(tái)，其盈利為 P1(x1)，剩下的 5x1臺(tái)就分給一合丙兩個(gè)工廠，則它的盈利最大值為 f2(5x1)?，F(xiàn)要選擇 x1值使 1 1 2 1( ) (5 )P x f x??取最大值，它就 是所求的總盈利最大值，其數(shù)值計(jì)算如表 55 所示。 表 55 然后按計(jì)算表格的順序反推算，可知最優(yōu)方案有兩個(gè)： （ 1）由于 *1 0x? ，根據(jù) s2=s1 *1x =5 0=5，查表 54 知 *2 2x? ，由 s3=s2 *2x =52=3，故*333xs??。即甲工廠分配 0 臺(tái)、乙工廠分配 2 臺(tái)、丙工廠分配 3 臺(tái)。 （ 2）由于 *1 2x? ，根據(jù) s2=s1 *1x =5 2=3，查表 54 知 *2 2x? ，由 s3=s2 *2x =32=1，故*331xs??。即甲工廠分配 2 臺(tái)、乙工廠分配 2 臺(tái)、丙工廠分配 1 臺(tái)。 以上兩個(gè)分配方案所得的總盈利均為 21 萬元。 在此問題中，如果原設(shè)備的太熟不是 5 臺(tái)，而是 4 臺(tái)或 3 臺(tái)，用其他方法求解時(shí)，往往需要從頭再算，但用動(dòng)態(tài)規(guī)劃求解時(shí)，這些列出的表仍舊有用，只需要修改最后的表格就 14 可得到： 當(dāng)設(shè)備臺(tái)數(shù)位 4 臺(tái)時(shí)，最優(yōu)分配方案為 * * *1 2 31, 2, 1x x x? ? ?或 * * *1 2 32, 2, 0x x x? ? ?，總盈利為 17 萬元。 當(dāng)設(shè)備臺(tái)數(shù)位 3 臺(tái)時(shí)，最優(yōu)分配方案為： * * *1 2 30, 2, 1x x x? ? ?，總盈利為 14 萬元。 設(shè)有一輛載重量為 15 噸的卡車，要裝運(yùn) 4 種貨物。已知 4 種貨物的單位重量和價(jià)值如表 56 所示，在裝載重量許可的情況下每輛車裝載某種貨物的條件不限，試問如何搭配這 4 種貨物才能使每輛車裝載貨物的價(jià)值最大？ 表 56 貨物代號(hào) 重量 (噸 ) 價(jià)值 (千元 ) 貨物代號(hào) 重量 (噸 ) 價(jià)值 (千元 ) 1 2 3 3 4 5 2 3 4 4 5 6 解： 設(shè)決策變量 1 2 3 4, , ,x x x x 分別為 4 種貨物的裝載件數(shù)，則問題為一線性整數(shù)規(guī)劃： 1 2 3 41 2 3 4m a x 3 4 5 62 3 4 5 1 5..0 , ( 1 , 2 , 3 , 4 )iz x x x xx x x xstxi? ? ? ?? ? ? ?????? 且 為 整 數(shù) 將其轉(zhuǎn)化為動(dòng)態(tài)規(guī)劃問題，分為 4 個(gè)階段，每個(gè)階段的指標(biāo)函數(shù)記為 1 1 1( ) 3g x x? ， 2 2 2( ) 4g x x? ， 3 3 3( ) 5g x x? ， 4 4 4( ) 6g x x? 狀態(tài)變量 sk 表示第 k 種至第 4 種貨物 總允許載重量，即 4 ( 1 ) ( 1 , 2 , 3 , 4)kiiks i x k?? ? ?? 允許狀態(tài)集合為 { 0 ,1, 2 , ,1 5 } , 1, 2 , 3 , 4kSk??，最優(yōu)值函數(shù) ()kkfs表示裝載第 k 種至第 4 中貨物的價(jià)值，則動(dòng)態(tài)規(guī)劃模型為 ? ?11()55( ) m a x ( ) ( )( ) 0 ( 4 , 3 , 2 , 1 )k k kk k k k k kx D sf s g x f sf s k???? ? ??????? 狀態(tài)轉(zhuǎn)移方程為 1 ( 1 ) , 1 , 2 , 3 , 4k k ks s k x k? ? ? ? ? 允許決策集合為 ( ) 0 , 1 , 2 , , , ( 1 , 2 , 3 , 4 )1kkk sD s kk??????????????? 即表示在載重量允許的范圍內(nèi)可能裝載第 k 種貨物的件數(shù)。 用 逆推方法求解如下： 4 4 4 4 4 4 4 44 : ( ) m a x { 6 } , ( ) ,k f s x x D s s S? ? ? ? 44 4 4( ) 0 , 1 , 2 , , , { 0 , 1 , 2 , , 1 5 }5sD s S??????????????； 3 3 3 4 4 3 3 3 3 33 : ( ) m a x { 5 ( ) } , ( ) ,k f s x f s x D s s S? ? ? ? ? 15 33 3 3 4 3 3( ) 0 , 1 , 2 , , , { 0 , 1 , 2 , , 1 5 } , 44sD s S s s x?? ??? ? ? ??? ??????； 2 2 2 3 3 2 2 2 2 22 : ( ) m a x { 4 ( ) } , ( ) ,k f s x f s x D s s S? ? ? ? ? 22 2 2 3 2 2( ) 0 , 1 , 2 , , , { 0 , 1 , 2 , , 1 5 } , 33sD s S s s x?? ??? ? ? ??? ??????； 1 1 1 2 2 1 1 11 : ( ) m a x { 3 ( ) } , ( 1 5 ) , 1 5k f s x f s x D s? ? ? ? ? ? ?1 2 1(1 5 ) 0 ,1 , 2 , , 7 , 1 5 2D s x? ? ?。 最后得到問題的最優(yōu)解為 * * * *1 2 3 46 , 1, 0 , 0x x x x? ? ? ?，最優(yōu)值為 22 千克。 求解下列矩陣對(duì)策，其中贏得矩陣 A 分別為 （ 1） 1/ 2 1 11 1/ 2 11 1 1???????????? （ 2） 2 2 1 61 4 5 1????????? （ 3）2 7 2 12 2 3 43 5 4 42 3 1 6???????? （ 4）9 3 1 8 06 5 4 6 72 4 3 3 85 6 2 2 13 2 3 5 4???????? 解： （ 1）由于 m a x m in 1 , m in m a x 1 / 2i j i jjjiiaa? ? ?，所以 A 所對(duì)應(yīng)的支付矩陣沒有純 對(duì)策。 即局中人 1 以 (,)的概率分別出策略 2 和 3，其贏得值為 。 （ 2）由于 m a x m i n 1 , m i n m a x 2i j i jjjiiaa? ? ?，所以 A 所對(duì)應(yīng)的支付矩陣沒有純對(duì)策。 即局中人 1 以 、 的概率分別出策略 1 和策略 2，贏得值為 . （ 3 ）根據(jù)贏得矩陣有31m a x m in m in m a x 3i j i jjjiia a a? ? ?，所以 G 的解為31( , ), 3Gv?? ? 。 （ 4 ） 根 據(jù) 贏 得 矩陣 有23m a x m i n m i n m a x 4i j i jjjiia a a? ? ?，所以 G 的解 為23( , ), 4Gv?? ? 。 甲、乙兩家公司生產(chǎn)同一種產(chǎn)品，爭(zhēng)奪市場(chǎng)的占有率。假設(shè)兩家公司市場(chǎng)占有率之和為 100％，即顧客只購(gòu)買這兩家公司的產(chǎn)品，無其他選擇。若公司甲可以采用的商業(yè)策略為 A A A3，公司乙可以采用的商業(yè)策略為 B B B3。表 71 給出在不同策略下公司甲的市場(chǎng)占有率。在此情況下，請(qǐng)為這兩家公司選擇他們的最優(yōu)策略。 表 71 B1 B2 B3 A1 A2 16 A3 解： 若完全采用二人常數(shù)和對(duì)策的方法確定最優(yōu)純策略，則由 m a x m i n m i n m a x 0 .5ABij ijjjiiaa?? 可得，局中人甲采用策略 A局中人乙采用策略 B1，各獲得 50%的市場(chǎng)占有率。 從計(jì)算結(jié)果可以看出，局中人甲采用策略 A局中人乙采用策略 B1，各獲得 50%的市場(chǎng)占有率。 某一決策問題的損益矩陣如表 101 所示，其中矩陣元素值為年利潤(rùn)。 表 101 單位：元 （ 1）若各事件發(fā)生的概率 jP 是未知的，分別用 max min 決策準(zhǔn)則、 max max 決策準(zhǔn)則、拉普拉斯準(zhǔn)則和最小機(jī)會(huì)損失準(zhǔn)則選出決策方案。 （ 2）若 jP 值仍是未知的，并且 ? 是樂觀系數(shù)，問 ? 取何值時(shí)，方案 S1 和 S3 是不偏不倚的？ （ 3）若 P1=,P2=,P3=,那么用 EMV 準(zhǔn)則 會(huì)選擇哪個(gè)方案？ 解： （ 1）采用 maxmin 準(zhǔn)則應(yīng)選擇方案 S2，采用 maxmax 決策準(zhǔn)則應(yīng)選擇方案 S1，采用 Laplace 準(zhǔn)則應(yīng)選擇方案 S1，采用最小機(jī)會(huì)損失準(zhǔn)則應(yīng)選擇方案 S1。 （ 2） ； （ 3）方案 S1 或 S3。 假設(shè)有外表完全相同的木盒 100 只，將其分為兩組，一組內(nèi)裝白球，有 70 盒，另一組內(nèi)裝