【正文】 法求解原問題的松弛問題，計算結(jié)果如表 31 所示。z=13/3。 表 32 cj 1 1 0 0 0 CB XB b x1 x2 x3 x4 x5 1 x1 5/3 1 0 5/6 1/6 0 1 x2 8/3 0 1 2/3 1/3 0 0 x5 2 0 0 1 [ 1 ] 1 cjzj 0 0 1/6 1/30 0 1 x1 2 1 0 1 0 1/6 1 x2 2 0 1 1 0 1/3 0 x4 2 0 0 1 1 1 cjzj 0 0 0 0 1/6 由于 12,xx的值均為整數(shù)，所以得到原問題的最優(yōu)解為 **(2, 2) , 4Txz?? 某廠新購 4 臺不同類型機器，可以把它們安裝在 4 個不同的地點。估計的費用見表 33，試制定使得總安裝費用最小的安裝方案。建立該問題的數(shù)學(xué)模型如下： 目標(biāo)函數(shù)： 4411m in ij ijijz cx??? ?? 約束條件： (1)每一部機器只分配在一個地點，即 41 1 1, 2 , 3 , 4ijj xi? ??? (2)每一個地點只能有一臺機器， 即 41 1 1, 2 , 3, 4iji xj? ??? (3) 01ijx ? 或 工作指派問題可以看成是一類特殊的運輸問題，每個供應(yīng)點的供應(yīng)量為 1，每個需求點的需求量也為 1。計算得到的最佳安裝方案為：機器 1 安裝在地點 機器 2 安裝在地點 機器 3安裝在地點 機器 4 安裝在地點 2，最小總安裝費為 14 元。假定等量的化肥在這些地區(qū)使用的效果相同。試確定使總運費最少的化肥調(diào)撥方案。根據(jù)現(xiàn)有產(chǎn)量 ，第 IV 個地區(qū)每年最多能分配到 60 萬 t，這樣最高需求就為 210 萬 t，大于產(chǎn)量。由于各地區(qū)的需求量包含兩部分，如地區(qū) I，其中 30 萬 t 是最低需求，故不能由假想化肥廠 D 供給，令相應(yīng)的單位運價為 M（任意大的正數(shù)）；而另一部分 20 萬t 滿足或不滿足均可以，因此可以由假想化肥廠 D 供給，按前述，可令相應(yīng)的單位運價為 0。這樣可以寫出這個問題的產(chǎn)銷平衡表（表 318）和單位運價表（表 319）。 表 318 銷地 產(chǎn)地 I I’ II III IV IV’ 產(chǎn)量 A 50 B 60 8 C 50 D 50 銷量 30 20 70 30 10 50 表 319 銷地 產(chǎn)地 I I’ II III IV IV’ A 16 16 13 22 17 17 B 14 14 13 19 15 15 C 19 19 20 23 M M D M 0 M 0 M 0 表 320 銷地 產(chǎn)地 I I’ II III IV IV’ 產(chǎn)量 A 50 50 B 20 10 30 60 C 30 20 0 50 D 30 20 50 銷量 30 20 70 30 10 50 利用單純形法求解下列目標(biāo)規(guī)劃模型。并計算出各非基變量的檢驗數(shù)，得到初始的單純形表如表 41 所示。用最小比值法確定 1d? 應(yīng)當(dāng)出基。 表 41 cj 0 0 P1 0 0 P1 P2 0 ? CB XB b x1 x2 1d? 1d? 2d? 2d? 3d? 3d? P1 1d? 50 1 [ 2 ] 1 1 0 0 0 0 25 9 0 2d? 40 2 1 0 0 1 1 0 0 40 P2 3d? 80 2 2 0 0 0 0 1 1 40 σj P1 1 2 0 1 0 1 0 0 P2 2 2 0 0 0 0 0 1 表 42 cj 0 0 P1 0 0 P1 P2 0 ? CB XB b x1 x2 1d? 1d? 2d? 2d? 3d? 3d? 0 x2 25 1/2 1 1/2 1/2 0 0 0 0 50 0 2d? 15 [ 3/2 ] 0 1/2 1/2 1 1 0 0 10 P2 3d? 30 1 0 1 1 0 0 1 1 30 σj P1 0 0 1 0 0 1 0 0 P2 1 0 1 1 0 0 0 1 盡管 x1與 1d? 具有相同的負(fù)檢驗數(shù)，但根據(jù)前面討論的原則，由于 x1是決策變量，選擇x1 進基，用最小比值法確定 2d? 出基，換基后，計算所得新的基本可行解如表 43 所示。 表 44 cj 0 0 P1 0 0 P1 P2 0 ? CB XB b x1 x2 1d? 1d? 2d? 2d? 3d? 3d? 0 x2 40 2 1 0 0 1 1 0 0 0 1d? 30 3 0 1 1 2 2 0 0 P2 3d? 0 2 0 0 0 2 2 1 1 σj P1 0 0 1 0 0 1 0 0 10 P2 2 0 0 0 2 2 0 1 此時所有變量的檢驗數(shù)的首項系數(shù)都已經(jīng)大于等于零，因此獲得了滿意解如下： x1=0,x2 =40, 1d? =30，其他偏差變量都等于零。 該廠經(jīng)營目標(biāo)如下：（ 1）利潤指標(biāo)為每月 16000 元，爭取超額完成；（ 2）充分利用現(xiàn)有生產(chǎn)能力；（ 3）可以適當(dāng)加班，但加班時間不得超過 24 小時；（ 4）產(chǎn)量以預(yù)計銷售量為準(zhǔn)。 解： 該問題的數(shù)學(xué)模型如下： 1 1 2 2 3 34 4 4 5 5 6 61 2 3 1 11 2 3 2 22 3 31 4 42 5 53 6 61 2 3m i n ( )500 650 800 160 006 8 10 20024 . 12106, , 0 , , 0iiZ p d p d p dp d d d d d dx x x d dx x x d dd d dx d dx d dx d dx x x d d? ? ?? ? ? ? ? ?????? ? ?????????? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? ?? ? ?? ? ?? ? ??? ( 1 , 2 , , 6)i?????????????? 計算從 A 到 B、 C 和 D 的最短路。 圖 51 解： 求從 A 到 B、 C 和 D 的最短路等價于求從 B、 C 和 D 到 A 的最短路。 0k k kf v f k f?? ? ? ? 計算過程如表 51 所示。 表 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ù)國家計劃的安排，擬將某種高效率的設(shè)備 5 臺，分配給所屬的甲、乙、丙三個工廠，各工廠若獲得這種設(shè)備之后，可以為國家提供的盈利如表 52 所示。 由以上的假設(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???? ? ? ??????? 下面采用逆推法進行 計算。 因為此時只有一個工廠，有多少臺設(shè)備就全部分配給工廠丙，故它的盈利值就 是該段的最大盈利值。 表 53 表中 *3x 表示使 33()fs為最大值時的最優(yōu)決策。 因為給乙工廠 x2 臺，其盈利為 P2(x2)，余下的 s2x2 臺就給丙工廠，則它的盈利最大值為f3(s2x2)。其數(shù)值計算 如表 54 所示。 因為給甲工廠 x1臺，其盈利為 P1(x1)，剩下的 5x1臺就分給一合丙兩個工廠，則它的盈利最大值為 f2(5x1)。 表 55 然后按計算表格的順序反推算，可知最優(yōu)方案有兩個： （ 1）由于 *1 0x? ，根據(jù) s2=s1 *1x =5 0=5，查表 54 知 *2 2x? ，由 s3=s2 *2x =52=3，故*333xs??。 （ 2）由于 *1 2x? ，根據(jù) s2=s1 *1x =5 2=3，查表 54 知 *2 2x? ，由 s3=s2 *2x =32=1，故*331xs??。 以上兩個分配方案所得的總盈利均為 21 萬元。 當(dāng)設(shè)備臺數(shù)位 3 臺時，最優(yōu)分配方案為： * * *1 2 30, 2, 1x x x? ? ?，總盈利為 14 萬元。已知 4 種貨物的單位重量和價值如表 56 所示，在裝載重量許可的情況下每輛車裝載某種貨物的條件不限，試問如何搭配這 4 種貨物才能使每輛車裝載貨物的價值最大？ 表 56 貨物代號 重量 (噸 ) 價值 (千元 ) 貨物代號 重量 (噸 ) 價值 (千元 ) 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)化為動態(tài)規(guī)劃問題，分為 4 個階段，每個階段的指標(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 中貨物的價值，則動態(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ù)。 最后得到問題的最優(yōu)解為 * * * *1 2 3 46 , 1, 0 , 0x x x x? ? ? ?，最優(yōu)值為 22 千克。 即局中人 1 以 (,)的概率分別出策略 2 和 3，其贏得值為 。 即局中人 1 以 、 的概率分別出策略 1 和策略 2，贏得值為 . （ 3 ）根據(jù)贏得矩陣有31m a x m in m in m a x 3i j i jjjiia a a? ? ?，所以 G 的解為31( , ), 3Gv?? ? 。 甲、乙兩家公司生產(chǎn)同一種產(chǎn)品，爭奪市場的占有率。若公司甲可以采用的商業(yè)策略為 A A A3，公司乙可以采用的商業(yè)策略為 B B B3。在此情況下，請為這兩家公司選擇他們的最優(yōu)策略。 從計算結(jié)果可以看出，局中人甲采用策略 A局中人乙采用策略 B1，各獲得 50%的市場占有率。 表 101 單位：元 （ 1）若各事件發(fā)生的概率 jP 是未知的，分別用 max min 決策準(zhǔn)則、 max max 決策準(zhǔn)則、拉普拉斯準(zhǔn)則和最小機會損失準(zhǔn)則選出決策方案。 （ 2） ； （ 3）方案 S1 或 S3?，F(xiàn)從這 100 盒中任取一盒，請你猜，如這盒內(nèi)裝的是白球，猜對了得 500 分，猜錯了罰 200 分；如這盒