運籌學(xué)第五、六、七、八章答案

1、運籌學(xué)第五、六、七、八章答案5.2 用元素差額法直接給出表5-53及表5-54下列兩個運輸問題的近似最優(yōu)解 表5-53 B1 B2 B3 B4 B5 Ai A1 19 16 10 21 9 18 A2 14 13 5 24 7 30 A3 25 30 20 11 23 10 A4 7 8 6 10 4 42 Bj 15 25 35 20 5 表5-54 B1 B2 B3 B4 Ai A1 5 3 8 6 16 A2 10 7 12 15 24 A3 17 4 8 9 30 Bj 20 25 10 15 【解】表5-53。Z=824 表5-54 Z=495 5.3 求表5-55及表5-56所示運

2、輸問題的最優(yōu)方案 （1）用閉回路法求檢驗數(shù)（表5-55） 表5-55 B1 B2 B3 B4 Ai A1 10 5 2 3 70 A2 4 3 1 2 80 A3 5 6 4 4 30 bj 60 60 40 20 （2）用位勢法求檢驗數(shù)（表5-56） 表5-56 B1 B2 B3 B4 Ai A1 9 15 4 8 10 A2 3 1 7 6 30 A3 2 10 13 4 20 A4 4 5 8 3 43 bj 20 15 50 15 【解】（1） (2) 5.4 求下列運輸問題的最優(yōu)解 （1）C1目標(biāo)函數(shù)求最小值；（2）C2目標(biāo)函數(shù)求最大值 15 45 20 40 60 30 50 40

3、 (3)目標(biāo)函數(shù)最小值,B1的需求為30b150, B2的需求為40，B3的需求為20b360,A1不可達(dá)A4 ，B4的需求為30 【解】（1） （2） （3）先化為平衡表 B11 B12 B2 B31 B32 B4 ai A1 4 4 9 7 7 M 70 A2 6 6 5 3 3 2 20 A3 8 8 5 9 9 10 50 A4 M 0 M M 0 M 40 bj 30 20 40 20 40 30 180 最優(yōu)解： 5.5（1）建立數(shù)學(xué)模型 設(shè)xij(I=1,2,3;j=1,2)為甲、乙、丙三種型號的客車每天發(fā)往B1，B2兩城市的臺班數(shù)，則 (2)寫平衡運價表 將第一、二等式兩邊同除

4、以40，加入松馳變量x13,x23和x33將不等式化為等式，則平衡表為： B1 B2 B3 ai 甲 乙 丙 80 60 50 65 50 40 0 0 0 5 10 15 bj 10 15 5 為了平衡表簡單，故表中運價沒有乘以40，最優(yōu)解不變 （3）最優(yōu)調(diào)度方案： 即甲第天發(fā)5輛車到B1城市，乙每天發(fā)5輛車到B1城市，5輛車到B2城市，丙每天發(fā)10輛車到B2城市，多余5輛，最大收入為 Z=40（580+560+550+1040）=54000（元） 5.6（1）設(shè)xij為第i月生產(chǎn)的產(chǎn)品第j月交貨的臺數(shù)，則此生產(chǎn)計劃問題的數(shù)學(xué)模型為 （2）化為運輸問題后運價表（即生產(chǎn)費用加上存儲費用）如下，

5、其中第5列是虛設(shè)銷地費用為零，需求量為30。1 2 3 4 5 ai 1 2 3 4 1 M M M 1.15 1.25 M M 1.3 1.4 0.87 M 1.45 1.55 1.02 0.98 0 0 0 0 65 65 65 65 bj 50 40 60 80 30 (3)用表上作業(yè)法，最優(yōu)生產(chǎn)方案如下表： 1 2 3 4 5 ai 1 2 3 4 50 15 25 60 10 5 65 30 65 65 65 65 Bi 50 40 60 80 30 上表表明：一月份生產(chǎn)65臺，當(dāng)月交貨50臺；二月份交貨15臺,二月份生產(chǎn)35臺，當(dāng)月交貨25臺，四月份交貨10臺；三月份生產(chǎn)65臺，當(dāng)

6、月交貨60臺，四月份交貨5臺，4月份生產(chǎn)65臺當(dāng)月交貨。最小費用Z=235萬元。5.7 假設(shè)在例5.15中四種產(chǎn)品的需求量分別是1000、2000、3000和4000件，求最優(yōu)生產(chǎn)配置方案 【解】將表5-35所示的單件產(chǎn)品成本乘以需求量，為計算簡便，從表中提出公因子1000 產(chǎn)品1 產(chǎn)品2 產(chǎn)品3 產(chǎn)品4 工廠1 58 138 540 1040 工廠2 75 100 450 920 工廠3 65 140 510 1000 工廠4 82 110 600 1120 用匈牙利法得到最優(yōu)表 第一個工廠加工產(chǎn)品1，第二工廠加工產(chǎn)品4，第三個工廠加工產(chǎn)品3，第四個工廠加工產(chǎn)品2； 總成本 Z1000(58

7、920510110)1598000 注：結(jié)果與例5.15的第2個方案相同，但并不意味著“某列（行）同乘以一個非負(fù)元素后最優(yōu)解不變”結(jié)論成立。5.8 求解下列最小值的指派問題，其中第（2）題某人要作兩項工作，其余3人每人做一項工作 （1） 【解】最優(yōu)解 （2） 【解】虛擬一個人，其效率取4人中最好的，構(gòu)造效率表為 1 2 3 4 5 甲 26 38 41 52 27 乙 25 33 44 59 21 丙 20 30 47 56 25 丁 22 31 45 53 20 戊 20 30 41 52 20 最優(yōu)解：甲戊完成工作的順序為3、5、1、2、4，最優(yōu)值Z=165 最優(yōu)分配方案：甲完成第3、4兩

8、項工作，乙完成第5項工作，丙完成第1項工作，丁完成第2項工作。5.9 求解下列最大值的指派問題： （1） 【解】最優(yōu)解 （2） 【解】最優(yōu)解 第5人不安排工作。表5-58 成績表(分鐘) 游泳 自行車 長跑 登山 甲 20 43 33 29 乙 15 33 28 26 丙 18 42 38 29 丁 19 44 32 27 戊 17 34 30 28 5.10 學(xué)校舉行游泳、自行車、長跑和登山四項接力賽，已知五名運動員完成各項目的成績（分鐘）如表5-58所示如何從中選拔一個接力隊，使預(yù)期的比賽成績最好 【解】設(shè)xij為第i人參加第j項目的狀態(tài)，則數(shù)學(xué)模型為 接力隊最優(yōu)組合 乙 長跑 丙 游泳

9、丁 登山 戊 自行車 甲淘汰。預(yù)期時間為107分鐘。習(xí)題六 圖639 6.1如圖639所示，建立求最小部分樹的01整數(shù)規(guī)劃數(shù)學(xué)模型。【解】邊i，j的長度記為cij，設(shè) 數(shù)學(xué)模型為： 圖640 6.2如圖640所示，建立求v1到v6的最短路問題的01整數(shù)規(guī)劃數(shù)學(xué)模型?！窘狻炕?i，j)的長度記為cij，設(shè) 數(shù)學(xué)模型為： 6.3如圖640所示，建立求v1到v6的最大流問題的線性規(guī)劃數(shù)學(xué)模型?！窘狻?設(shè)xij為?。╥,j）的流量，數(shù)學(xué)模型為 6.4求圖641的最小部分樹。圖6-41（a）用破圈法,圖6-41（b）用加邊法。圖641 【解】圖6-41（a），該題有4個解，最小樹長為21，其中一個解如下

10、圖所示。圖6-41（b），最小樹長為20。最小樹如下圖所示。6.5 某鄉(xiāng)政府計劃未來3年內(nèi)，對所管轄的10個村要達(dá)到村與村之間都有水泥公路相通的目標(biāo)。根據(jù)勘測，10個村之間修建公路的費用如表6-20所示。鄉(xiāng)鎮(zhèn)府如何選擇修建公路的路線使總成本最低。表6-20 兩村莊之間修建公路的費用(萬元) 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 12.8 10.5 9.6 8.5 7.7 13.8 12.7 13.1 12.6 11.4 13.9 11.2 8.6 7.5 8.3 14.8 15.7 8.5 9.6 8.9 8.0 13.2 12.4 10.5 9.

11、3 8.8 12.7 14.8 12.7 13.6 15.8 9.8 8.2 11.7 13.6 9.7 8.9 10.5 13.4 14.6 9.1 10.5 12.6 8.9 8.8 【解】屬于最小樹問題。用加邊法，得到下圖所示的方案。最低總成本74.3萬元。6.6在圖642中，求A到H、I的最短路及最短路長，并對圖(a)和(b)的結(jié)果進(jìn)行比較。圖642 【解】圖642(a): A到H的最短路PAH=A,B,F,H,A,C,F,H最短路長22；A到I的最短路PAI=A,B,F,I,A,C,F,I最短路長21。對于圖642(b)： A到H的最短路PAH=A,C,G,F,H,最短路長21；A到

12、I的最短路PAI=A,C,G,F,I,最短路長20； 結(jié)果顯示有向圖與無向圖的結(jié)果可能不一樣。6.7已知某設(shè)備可繼續(xù)使用5年，也可以在每年年末賣掉重新購置新設(shè)備。已知5年年初購置新設(shè)備的價格分別為3.5、3.8、4.0、4.2和4.5萬元。使用時間在15年內(nèi)的維護(hù)費用分別為0.4、0.9、1.4、2.3和3萬元。試確定一個設(shè)備更新策略，使5年的設(shè)備購置和維護(hù)總費用最小。【解】設(shè)點vj為第j年年初購置新設(shè)備的狀態(tài)，（i，j）為第i年年初購置新設(shè)備使用到第j年年初，弧的權(quán)為對應(yīng)的費用（購置費維護(hù)費），繪制網(wǎng)絡(luò)圖并計算，結(jié)果見下圖所示?？傎M用最小的設(shè)備更新方案為：第一種方案，第1年購置一臺設(shè)備使用到

13、第5年年末；第二種方案，第1年購置一臺設(shè)備使用到第2年年末，第3年年初更新后使用到第5年年末?？傎M用為11.5萬元。圖643 6.8圖643是世界某6大城市之間的航線，邊上的數(shù)字為票價（百美元），用Floyd算法設(shè)計任意兩城市之間票價最便宜的路線表?！窘狻拷處熆衫媚０迩蠼猓篸atachpt6ch6.xls L1 v1 v2 v3 v4 v5 v6 v1 0 8.8 9 5.6 8 6 v2 8.8 0 10 5 100 4 v3 9 10 0 3 4.8 14 v4 5.6 5 3 0 12 100 v5 8 100 4.8 12 0 9 v6 6 4 14 100 9 0 L2 v1 v2

14、 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 8.8 0 8 5 13 4 v3 8.6 8 0 3 4.8 14 v4 5.6 5 3 0 7.8 9 v5 8 13 4.8 7.8 0 9 v6 6 4 14 9 9 0 L3 v1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 8.8 0 8 5 13 4 v3 8.6 8 0 3 4.8 12 v4 5.6 5 3 0 7.8 9 v5 8 13 4.8 7.8 0 9 v6 6 4 12 9 9 0 最優(yōu)票價表： v1 v2 v3 v4 v5 v6 v1 0 8.8 8.6

15、5.6 8 6 v2 0 8 5 13 4 v3 0 3 4.8 12 v4 0 7.8 9 v5 0 9 v6 0 v1、v2、v6到各點的最優(yōu)路線圖分別為： 6.9 設(shè)圖643是某汽車公司的6個零配件加工廠，邊上的數(shù)字為兩點間的距離(km)?，F(xiàn)要在6個工廠中選一個建裝配車間。（1）應(yīng)選那個工廠使零配件的運輸最方便。（2）裝配一輛汽車6個零配件加工廠所提供零件重量分別是0.5、0.6、0.8、1.3、1.6和1.7噸，運價為2元/噸公里。應(yīng)選那個工廠使總運費最小?！窘狻?1)利用習(xí)題6.8表L3的結(jié)果 v1 v2 v3 v4 v5 v6 Max v1 0 8.8 8.6 5.6 8 6 8.

16、8 v2 8.8 0 8 5 13 4 12.8 v3 8.6 8 0 3 4.8 12 12 v4 5.6 5 3 0 7.8 9 9 v5 8 13 4.8 7.8 0 9 12.8 v6 6 4 12 9 9 0 12 選第1個工廠最好。(2)計算單件產(chǎn)品的運價，見下表最后一行。計算單件產(chǎn)品的運費，見下表最后一列。v1 v2 v3 v4 v5 v6 單件產(chǎn)品運費 v1 0 8.8 8.6 5.6 8 6 84.88 v2 8.8 0 8 5 13 4 89.16 v3 8.6 8 0 3 4.8 12 82.16 v4 5.6 5 3 0 7.8 9 71.96 v5 8 13 4.8

17、7.8 0 9 81.92 v6 6 4 12 9 9 0 82.2 運價 1 1.2 1.6 2.6 3.2 3.4 選第4個工廠最好。圖644 6.10 如圖644，（1）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量?！窘狻拷o出初始流如下 第一輪標(biāo)號：得到一條增廣鏈，調(diào)整量等于5，如下圖所示 調(diào)整流量。第二輪標(biāo)號：得到一條增廣鏈，調(diào)整量等于2，如下圖所示 調(diào)整流量。第三輪標(biāo)號：得到一條增廣鏈，調(diào)整量等于3，如下圖所示 調(diào)整流量。第四輪標(biāo)號：不存在增廣鏈，最大流量等于45，如下圖所示 取 ，最小截集(3,7),(4,7),(6,9),(8,10)，最小截量等于45。6.11

18、將3個天然氣田A1、A2、A3的天然氣輸送到2個地區(qū)C1、C2，中途有2個加壓站B1、B2，天然氣管線如圖645所示。輸氣管道單位時間的最大通過量cij及單位流量的費用dij標(biāo)在弧上(cij, dij)。求(1)流量為22的最小費用流；（2）最小費用最大流。圖645 【解】虛擬一個發(fā)點和一個收點 T6.111 得到流量v22的最小費用流，最小費用為271。求解過程參看第4章PPT文檔習(xí)題答案。T6.1113 最小費用最大流如下圖，最大流量等于27，總費用等于351。6.12如圖643所示，（1）求解旅行售貨員問題；（2）求解中國郵路問題。圖6-43 【解】（1）旅行售貨員問題。距離表C 1 2

19、 3 4 5 6 1 8.8 9 5.6 8 6 2 8.8 10 5 4 3 9 10 3 4.8 14 4 5.6 5 3 12 5 8 4.8 12 9 6 6 4 14 9 在C中行列分別減除對應(yīng)行列中的最小數(shù)，得到距離表C1。距離表C1 1 2 3 4 5 6 1 3.2 3.4 0 0.6 0.4 2 2.8 6 1 0 3 4 7 0 0 11 4 0.6 2 0 7.2 5 1.2 0 7.2 9 6 0 0 10 3.2 由距離表C1，v1到v4， H1= v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1, C(H1)=5.6+3+4.8+9+4+8.8=35.2 去掉第

20、1行第四列，d41=，得到距離表C2。得到距離表C2 1 2 3 5 6 2 2.8 6 0 3 4 7 0 11 4 2 0 7.2 5 1.2 0 9 6 0 0 10 3.2 距離表C2的每行每列都有零，H2= H1= v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1就是總距離最小的Hamilton回路，C(H1) =35.2。(2)中國郵路問題。虛擬一條邊 取回路H1v1，v3，v4，C(H1)=9+5+3=17,C(v1，v3)=9 C(H1)/2，調(diào)整回路。所有回路滿足最短回路的準(zhǔn)則，上圖是最短的歐拉回路，其中邊(v1, v4)和(v4, v3)各重復(fù)一次。習(xí)題七 7.2(1)

21、分別用節(jié)點法和箭線法繪制表7-16的項目網(wǎng)絡(luò)圖，并填寫表中的緊前工序。(2) 用箭線法繪制表7-17的項目網(wǎng)絡(luò)圖，并填寫表中的緊后工序 表7-16 工序 A B C D E F G 緊前工序 A C A F、D、B、E 緊后工序 D,E G E G G G 表7-17 工序 A B C D E F G H I J K L M 緊前工序 - - - B B A,B B D,G C,E,F,H D,G C,E I J,K,L 緊后工序 F E,D,F,G I,K H,J I,K I H,J I L M M M 【解】（1）箭線圖： 節(jié)點圖： （2）箭線圖： 7.3根據(jù)項目工序明細(xì)表7-18： （1

22、）畫出網(wǎng)絡(luò)圖。（2）計算工序的最早開始、最遲開始時間和總時差。（3）找出關(guān)鍵路線和關(guān)鍵工序。表7-18 工序 A B C D E F G 緊前工序 - A A B,C C D,E D,E 工序時間（周） 9 6 12 19 6 7 8 【解】(1)網(wǎng)絡(luò)圖 (2)網(wǎng)絡(luò)參數(shù) 工序 A B C D E F G 最早開始 0 9 9 21 21 40 40 最遲開始 0 15 9 21 34 41 40 總時差 0 6 0 0 13 1 0 (3)關(guān)鍵路線：；關(guān)鍵工序：A、C、D、G；完工期：48周。7.4 表7-19給出了項目的工序明細(xì)表。表7-19 工序 A B C D E F G H I J K

23、 L M N 緊前工序 - - - A,B B B,C E D,G E E H F,J I,K,L F,J,L 工序時間(天) 8 5 7 12 8 17 16 8 14 5 10 23 15 12 （1）繪制項目網(wǎng)絡(luò)圖。（2）在網(wǎng)絡(luò)圖上求工序的最早開始、最遲開始時間。（3）用表格表示工序的最早最遲開始和完成時間、總時差和自由時差。（4）找出所有關(guān)鍵路線及對應(yīng)的關(guān)鍵工序。（5）求項目的完工期?！窘狻?1)網(wǎng)絡(luò)圖 （2）工序最早開始、最遲開始時間 （3）用表格表示工序的最早最遲開始和完成時間、總時差和自由時差 工序 t TES TEF TLS TLF 總時差S 自由時差F A 8 0 8 9 1

24、7 9 0 B 5 0 5 0 5 0 0 C 7 0 7 7 7 0 0 D 12 8 20 17 29 9 9 E 8 5 13 5 13 0 0 F 17 7 24 7 24 0 0 G 16 13 29 13 29 0 0 H 8 29 37 29 37 0 0 I 14 13 27 33 47 20 20 J 5 13 18 19 24 6 6 K 10 37 47 37 47 0 0 L 23 24 47 24 47 0 0 M 15 47 62 47 62 0 0 N 12 47 59 50 62 3 3 (4)關(guān)鍵路線及對應(yīng)的關(guān)鍵工序 關(guān)鍵路線有兩條，第一條：；關(guān)鍵工序：B,E

25、,G,H,K,M 第二條：；關(guān)鍵工序：C,F,L,M （5）項目的完工期為62天。7.5已知項目各工序的三種估計時間如表7-20所示。求： 表7-20 工序 緊前工序 工序的三種時間（小時） a m b A 9 10 12 B A 6 8 10 C A 13 15 16 D B 8 9 11 E B,C 15 17 20 F D,E 9 12 14 （1）繪制網(wǎng)絡(luò)圖并計算各工序的期望時間和方差。（2）關(guān)鍵工序和關(guān)鍵路線。（3）項目完工時間的期望值。（4）假設(shè)完工期服從正態(tài)分布，項目在56小時內(nèi)完工的概率是多少。（5）使完工的概率為0.98，最少需要多長時間。【解】（1）網(wǎng)絡(luò)圖 工序 緊前工序

26、工序的三種時間（小時） 期望值 方差 a m b A 9 10 12 10.17 0.25 B A 6 8 10 8 0.4444 C A 13 15 16 14.83 0.25 D B 8 9 11 9.167 0.25 E B,C 15 17 20 17.17 0.6944 F D,E 9 12 14 11.83 0.6944 (2)關(guān)鍵工序：A,C,E,F；關(guān)鍵路線： (3) 項目完工時間的期望值：10.17+14.83+17.17+11.8354(小時) 完工期的方差為0.25+0.25+0.6944+0.69441.8889 (4)X0=56， 56天內(nèi)完工的概率為0.927 (5)

27、 p=0.98， 要使完工期的概率達(dá)到0.98，則至少需要56.82小時。7.6 表7-21給出了工序的正常、應(yīng)急的時間和成本。表7-21 工序 緊前工序 時間(天) 成本 時間的最大縮量(天) 應(yīng)急增加成本（萬元/天） 正常 應(yīng)急 正常 應(yīng)急 A 15 12 50 65 3 5 B A 12 10 100 120 2 10 C A 7 4 80 89 3 3 D B,C 13 11 60 90 2 15 E D 14 10 40 52 4 3 F C 16 13 45 60 3 5 G E,F 10 8 60 84 2 12 （1）繪制項目網(wǎng)絡(luò)圖，按正常時間計算完成項目的總成本和工期。（2）

28、按應(yīng)急時間計算完成項目的總成本和工期。（3）按應(yīng)急時間的項目完工期，調(diào)整計劃使總成本最低。（4）已知項目縮短1天額外獲得獎金4萬元，減少間接費用2.5萬元，求總成本最低的項目完工期。(1) 正常時間項目網(wǎng)絡(luò)圖 項目網(wǎng)絡(luò)圖 總成本為435，工期為64。(2)應(yīng)急時間項目網(wǎng)絡(luò)圖 總成本為560，工期為51。(3)應(yīng)急時間調(diào)整 工序C、F按正常時間施工，總成本為560-9-15536，完工期為51。(4) 總成本最低的項目完工期 工序A、E分別縮短3天，總成本為435+15+12-6.57416.5，完工期為57。7.7繼續(xù)討論表7-21。假設(shè)各工序在正常時間條件下需要的人員數(shù)分別為9、12、12、

29、6、8、17、14人。（1）畫出時間坐標(biāo)網(wǎng)絡(luò)圖 （2）按正常時間計算項目完工期，按期完工需要多少人。（3）保證按期完工，怎樣采取應(yīng)急措施，使總成本最小又使得總?cè)藬?shù)最少，對計劃進(jìn)行系統(tǒng)優(yōu)化分析?！窘狻浚?）正常時間的時間坐標(biāo)網(wǎng)絡(luò)圖 (2) 按正常時間調(diào)整非關(guān)鍵工序的開工時間 (3)略，參看教材。7.8用WinQSB軟件求解7.5。7.9用WinQSB軟件求解7.6。習(xí)題八 8.1 在設(shè)備負(fù)荷分配問題中，n=10，a=0.7，b=0.85，g=15，h=10，期初有設(shè)備1000臺。試?yán)霉?8.7)確定10期的設(shè)備最優(yōu)負(fù)荷方案?！窘狻繉⒔滩闹衋的下標(biāo)i去掉。由公式得 (g-h)/g(b-a)0.

30、2222，a0a1a21+0.70.492.192.222a0+a1a2a32.533，nt12，t=7，則16年低負(fù)荷運行，710年為高負(fù)荷運行。各年年初投入設(shè)備數(shù)如下表。年份 1 2 3 4 5 6 7 8 9 10 設(shè)備臺數(shù) 1000 850 723 614 522 444 377 264 184.8 129 8.2如圖84，求A到F的最短路線及最短距離?！窘狻緼到F的最短距離為13；最短路線 A B2 C3 D2 E2 F及AC2 D2 E2 F 8.3求解下列非線性規(guī)劃 (1) (2) （3） (4) (5) （6） 【解】（1）設(shè)s3=x3 , s3+x2=s2，s2+x1=s1=

31、C 則有 x3= s3 ，0x2s2，0x1s1=C 用逆推法，從后向前依次有 k3， 及最優(yōu)解 x3*=s3 k2， 由 故 為極大值點。所以 及最優(yōu)解x2*=s2 k=1時， ， 由，得 故 已知知x1 + x2+ x3 = C，因而按計算的順序推算，可得各階段的最優(yōu)決策和最優(yōu)解如下 ， 由s2=s1x1*=2C/3， 由s3=s2x2*=C/3， 最優(yōu)解為： 【解】（2）設(shè)s3=x3 , s3+x2=s2，s2+x1=s1=C 則有 x3= s3 ，0x2s2，0x1s1=C 用逆推法，從后向前依次有 k3， 及最優(yōu)解 x3*=s3 k2， 由 =40,故 x2=為極小值點。因而有 k1

32、時， 由知 得到最優(yōu)解 【解】(3) 設(shè)s3=x3 , s3+x2=s2，s2+x1=s1=10 則有 x3= s3 ，0x2s2，0x1s1=10 用逆推法，從后向前依次有 k3時， 及最優(yōu)解 x3=s3 k2時， 而 。討論端點：當(dāng) x2=0時, x2= s2時 如果s23時, k1時， 同理有, x1=0, f1（s1）= s12= 100，x1= s1, f1（s1）= 2s1= 20 (舍去) 得到最優(yōu)解 【解】(4) 設(shè)s3=x3 ,2s3+4x2=s2，s2+x1=s1=10 則有 x3= s3 ，0x2s2/4，0x1s1=10 用逆推法，從后向前依次有 k1， 及最優(yōu)解 x3

33、*=s3 k2， 由=s2-4x2=0,則 x2=s2 ,故 為極大值點。則 及最優(yōu)解x2*=s2/8 k1， ，故 得到最優(yōu)解 【解】(5) 按問題中變量的個數(shù)分為三個階段s1 ，s2 ，s3 ，且s310，x1，x2，x3為各階段的決策變量，各階段指標(biāo)函數(shù)相乘。設(shè)s1=2x1 , s1+4x2=s2，s2+x3=s310，則有 x1= s1/2 ，0x2s2/4，0x3s3=10 用順推法，從前向后依次有 k1， 及最優(yōu)化解 x1*=s1/2 k2， 由,則 ,故 為極大值點。則 k3， 由 故，由于s310，則s3=10時取最大值，x310/3，s2=s3x320/3，x25/6，s1=

34、s24x210/3，x15/3 得到最優(yōu)解 【解】（6）設(shè)s1=x1, s1+x2=s2，s2+x3=s3=8 k1， 及最優(yōu)化解 x1*=s1 k2， x2*=0時，f2（s2）=s22+2s2, x2*= s2時，f2（s2）=2s22 故 k3， 當(dāng)x2*=0時， 同樣得x3*=0時 ，f3（s3）=s32+2s3 x3*=s3時，f3（s3）=s3 所以， f3（s3）= s32+2s3=80 當(dāng)x2*= s2時，f3（s3）=x3+2（s3-x3）2 同樣得x3*=0時 ，f3（s3）=2s32 =128 x3*=s3時，f3（s3）=s3 =8 所以， f3（s3）= 2s32=1

35、28 最優(yōu)解為 8.4用動態(tài)規(guī)劃求解下列線性規(guī)劃問題?！窘狻吭O(shè)s2=x2 ,s2+2x1=s16 則有 0x2=s24，0x1s1/2 用逆推法，從后向前依次有 及最優(yōu)解 x2*=s2 由 s2=s12x14， s16，取s16， 又1x12，取x11， 最優(yōu)解 8.5 10噸集裝箱最多只能裝9噸，現(xiàn)有3種貨物供裝載，每種貨物的單位重量及相應(yīng)單位價值如表8.24所示。應(yīng)該如何裝載貨物使總價值最大。表8.24 貨物編號 1 2 3 單位加工時間 2 3 4 單位價值 3 4 5 【解】設(shè)裝載第I種貨物的件數(shù)為xi（ i =1,2,3）則問題可表為： 利用背包問題的前向動態(tài)規(guī)劃計算，建立動態(tài)規(guī)劃模

36、型。由于決策變量離散型值，所以可用列表法求解。當(dāng)R=1時， 。計算結(jié)果如下： s2 0 1 2 3 4 5 6 7 8 9 f1（s2） 0 0 3 3 6 6 9 9 12 12 x1* 0 0 1 1 2 2 3 3 4 4 當(dāng)R=2時，f2（s3）=4x2+f1（s3-3x2） 計算結(jié)果如下： s3 0 1 2 3 4 5 6 7 8 9 x2 0 0 0 0 1 0 1 0 1 0 1 2 0 1 2 0 1 2 0 1 2 3 C2+f2 0 0 3 3 4 6 4 6 7 9 7 8 9 10 8 12 10 11 12 13 11 12 f2（s3） 0 0 3 4 6 7 9

37、10 12 13 x2* 0 0 0 1 0 1 0 1 0 1 當(dāng)R=3時，f3（9）=5x3+f2（9-4x3） （x3為整數(shù)）=f2（9），5+f2（5），10+f2（1）=max13，12，10=13 8.6 有一輛貨車載重量為10噸 ，用來裝載貨物A、B時成本分別為5元/噸和4元/噸?，F(xiàn)在已知每噸貨物的運價與該貨物的重量有如下線性關(guān)系： A：P1=10-2x1 ，B：P2=12-3x2 其中x1 、x2 分別為貨物A、B的重量。如果要求貨物滿載，A和B各裝載多少，才能使總利潤最大 【解】將原題改為A：P1=15-x1 ，B：P2=18-2x2 由題意可得各種貨物利潤函數(shù)為 原問題的數(shù)

38、學(xué)模型歸結(jié)為 最優(yōu)解：x1 =6，x2 =4；z48 8.7 現(xiàn)有一面粉加工廠，每星期上五天班。生產(chǎn)成本和需求量見表8-25。表8-25 星期(k) 1 2 3 4 5 需求量(dk) 單位：袋 10 20 25 30 30 每袋生產(chǎn)成本(ck) 8 6 9 12 10 面粉加工沒有生產(chǎn)準(zhǔn)備成本，每袋面粉的存儲費為hk0.5元/袋，按天交貨，分別比較下列兩種方案的最優(yōu)性，求成本最小的方案。（1）星期一早上和星期五晚的存儲量為零，不允許缺貨，倉庫容量為S=40袋； （2）其它條件不變，星期一初存量為8?！窘狻縿討B(tài)規(guī)劃求解過程如下： 階段k：日期，k=1,2,6 狀態(tài)變量sk：第k天早上（發(fā)貨以前

39、）的冷庫存量 決策變量xk：第k天的生產(chǎn)量 狀態(tài)轉(zhuǎn)移方程：sk+1=sk+xkdk； 決策允許集合： 階段指標(biāo)： vk(sk，xk)=ckxk+0.5sk 終端條件：f6(s6)=0, s6=0； 遞推方程： 當(dāng)k=5時，因為s6=0，有 由于s515， k=4時， k=3時，當(dāng)0s430時，得 有 當(dāng)30s440時，有 顯然此決策不可行。當(dāng)k=2時，由x2的決策允許集合為 當(dāng)k=1時，由，則x1的決策允許集合為 因為 (2)期初存儲量s1=8, 與前面計算相似，x1=2. Min Z=772.5+2.5x1-5s1=737.5 則總成本最小的方案是第二種。8.8 某企業(yè)計劃委派10個推銷員到

40、4個地區(qū)推銷產(chǎn)品，每個地區(qū)分配14個推銷員。各地區(qū)月收益（單位：10萬元）與推銷員人數(shù)的關(guān)系如表826所示。表8-26 地區(qū) 人數(shù) A B C D 1 4 5 6 7 2 7 12 20 24 3 18 23 23 26 4 24 24 27 30 企業(yè)如何分配4個地區(qū)的推銷人員使月總收益最大?！窘狻吭O(shè)xk為第k種貨物的運載重量，該問題的靜態(tài)規(guī)劃模型為 利用圖表法： X1 X2 X3 X4 X5 0 0 0 8 30 0 0 2 6 32 0 2 0 6 31 0 0 8 0 27 0 8 0 0 24 0 0 6 2 30 0 2 6 0 28 0 2 2 4 35 0 4 0 4 36 0 0 4 4 44 0 2 4 2 32 0 4 4 0 32 0 4 2 2 25 2 0 0 6 30 2 0 6 0 27 2 6 0 0 27 2 2 0 4 33 2 0 2 4 34 2 2 4 0 29 2 0 4 2 31 2 4 2