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

1、運(yùn)籌學(xué)第五、六、七、八章答案5.2 用元素差額法直接給出表5-53及表5-54下列兩個(gè)運(yùn)輸問(wèn)題的近似最優(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所示運(yùn)

2、輸問(wèn)題的最優(yōu)方案 （1）用閉回路法求檢驗(yàn)數(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ì)法求檢驗(yàn)數(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ùn)輸問(wèn)題的最優(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)為甲、乙、丙三種型號(hào)的客車每天發(fā)往B1，B2兩城市的臺(tái)班數(shù)，則 (2)寫平衡運(yùn)價(jià)表 將第一、二等式兩邊同除

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 為了平衡表簡(jiǎn)單，故表中運(yùn)價(jià)沒(méi)有乘以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月交貨的臺(tái)數(shù)，則此生產(chǎn)計(jì)劃問(wèn)題的數(shù)學(xué)模型為 （2）化為運(yùn)輸問(wèn)題后運(yùn)價(jià)表（即生產(chǎn)費(fèi)用加上存儲(chǔ)費(fèi)用）如下，

5、其中第5列是虛設(shè)銷地費(fèi)用為零，需求量為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臺(tái)，當(dāng)月交貨50臺(tái)；二月份交貨15臺(tái),二月份生產(chǎn)35臺(tái)，當(dāng)月交貨25臺(tái)，四月份交貨10臺(tái)；三月份生產(chǎn)65臺(tái)，當(dāng)

6、月交貨60臺(tái)，四月份交貨5臺(tái)，4月份生產(chǎn)65臺(tái)當(dāng)月交貨。最小費(fèi)用Z=235萬(wàn)元。5.7 假設(shè)在例5.15中四種產(chǎn)品的需求量分別是1000、2000、3000和4000件，求最優(yōu)生產(chǎn)配置方案 【解】將表5-35所示的單件產(chǎn)品成本乘以需求量，為計(jì)算簡(jiǎ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)表 第一個(gè)工廠加工產(chǎn)品1，第二工廠加工產(chǎn)品4，第三個(gè)工廠加工產(chǎn)品3，第四個(gè)工廠加工產(chǎn)品2； 總成本 Z1000(58

7、920510110)1598000 注：結(jié)果與例5.15的第2個(gè)方案相同，但并不意味著“某列（行）同乘以一個(gè)非負(fù)元素后最優(yōu)解不變”結(jié)論成立。5.8 求解下列最小值的指派問(wèn)題，其中第（2）題某人要作兩項(xiàng)工作，其余3人每人做一項(xiàng)工作 （1） 【解】最優(yōu)解 （2） 【解】虛擬一個(gè)人，其效率取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)解：甲戊完成工作的順序?yàn)?、5、1、2、4，最優(yōu)值Z=165 最優(yōu)分配方案：甲完成第3、4兩

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

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

10、圖所示。圖6-41（b），最小樹(shù)長(zhǎng)為20。最小樹(shù)如下圖所示。6.5 某鄉(xiāng)政府計(jì)劃未來(lái)3年內(nèi)，對(duì)所管轄的10個(gè)村要達(dá)到村與村之間都有水泥公路相通的目標(biāo)。根據(jù)勘測(cè)，10個(gè)村之間修建公路的費(fèi)用如表6-20所示。鄉(xiāng)鎮(zhèn)府如何選擇修建公路的路線使總成本最低。表6-20 兩村莊之間修建公路的費(fèi)用(萬(wàn)元) 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 【解】屬于最小樹(shù)問(wèn)題。用加邊法，得到下圖所示的方案。最低總成本74.3萬(wàn)元。6.6在圖642中，求A到H、I的最短路及最短路長(zhǎng)，并對(duì)圖(a)和(b)的結(jié)果進(jìn)行比較。圖642 【解】圖642(a): A到H的最短路PAH=A,B,F,H,A,C,F,H最短路長(zhǎng)22；A到I的最短路PAI=A,B,F,I,A,C,F,I最短路長(zhǎng)21。對(duì)于圖642(b)： A到H的最短路PAH=A,C,G,F,H,最短路長(zhǎng)21；A到

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

13、第5年年末；第二種方案，第1年購(gòu)置一臺(tái)設(shè)備使用到第2年年末，第3年年初更新后使用到第5年年末。總費(fèi)用為11.5萬(wàn)元。圖643 6.8圖643是世界某6大城市之間的航線，邊上的數(shù)字為票價(jià)（百美元），用Floyd算法設(shè)計(jì)任意兩城市之間票價(jià)最便宜的路線表?！窘狻拷處熆衫媚０迩蠼猓篸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)票價(jià)表： 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到各點(diǎn)的最優(yōu)路線圖分別為： 6.9 設(shè)圖643是某汽車公司的6個(gè)零配件加工廠，邊上的數(shù)字為兩點(diǎn)間的距離(km)。現(xiàn)要在6個(gè)工廠中選一個(gè)建裝配車間。（1）應(yīng)選那個(gè)工廠使零配件的運(yùn)輸最方便。（2）裝配一輛汽車6個(gè)零配件加工廠所提供零件重量分別是0.5、0.6、0.8、1.3、1.6和1.7噸，運(yùn)價(jià)為2元/噸公里。應(yīng)選那個(gè)工廠使總運(yùn)費(fèi)最小?！窘狻?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個(gè)工廠最好。(2)計(jì)算單件產(chǎn)品的運(yùn)價(jià)，見(jiàn)下表最后一行。計(jì)算單件產(chǎn)品的運(yùn)費(fèi)，見(jiàn)下表最后一列。v1 v2 v3 v4 v5 v6 單件產(chǎn)品運(yùn)費(fèi) 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 運(yùn)價(jià) 1 1.2 1.6 2.6 3.2 3.4 選第4個(gè)工廠最好。圖644 6.10 如圖644，（1）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量?！窘狻拷o出初始流如下 第一輪標(biāo)號(hào)：得到一條增廣鏈，調(diào)整量等于5，如下圖所示 調(diào)整流量。第二輪標(biāo)號(hào)：得到一條增廣鏈，調(diào)整量等于2，如下圖所示 調(diào)整流量。第三輪標(biāo)號(hào)：得到一條增廣鏈，調(diào)整量等于3，如下圖所示 調(diào)整流量。第四輪標(biāo)號(hào)：不存在增廣鏈，最大流量等于45，如下圖所示 取 ，最小截集(3,7),(4,7),(6,9),(8,10)，最小截量等于45。6.11

18、將3個(gè)天然氣田A1、A2、A3的天然氣輸送到2個(gè)地區(qū)C1、C2，中途有2個(gè)加壓站B1、B2，天然氣管線如圖645所示。輸氣管道單位時(shí)間的最大通過(guò)量cij及單位流量的費(fèi)用dij標(biāo)在弧上(cij, dij)。求(1)流量為22的最小費(fèi)用流；（2）最小費(fèi)用最大流。圖645 【解】虛擬一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn) T6.111 得到流量v22的最小費(fèi)用流，最小費(fèi)用為271。求解過(guò)程參看第4章PPT文檔習(xí)題答案。T6.1113 最小費(fèi)用最大流如下圖，最大流量等于27，總費(fèi)用等于351。6.12如圖643所示，（1）求解旅行售貨員問(wèn)題；（2）求解中國(guó)郵路問(wèn)題。圖6-43 【解】（1）旅行售貨員問(wèn)題。距離表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中行列分別減除對(duì)應(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)中國(guó)郵路問(wèn)題。虛擬一條邊 取回路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é)點(diǎn)法和箭線法繪制表7-16的項(xiàng)目網(wǎng)絡(luò)圖，并填寫表中的緊前工序。(2) 用箭線法繪制表7-17的項(xiàng)目網(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é)點(diǎn)圖： （2）箭線圖： 7.3根據(jù)項(xiàng)目工序明細(xì)表7-18： （1

22、）畫出網(wǎng)絡(luò)圖。（2）計(jì)算工序的最早開(kāi)始、最遲開(kāi)始時(shí)間和總時(shí)差。（3）找出關(guān)鍵路線和關(guān)鍵工序。表7-18 工序 A B C D E F G 緊前工序 - A A B,C C D,E D,E 工序時(shí)間（周） 9 6 12 19 6 7 8 【解】(1)網(wǎng)絡(luò)圖 (2)網(wǎng)絡(luò)參數(shù) 工序 A B C D E F G 最早開(kāi)始 0 9 9 21 21 40 40 最遲開(kāi)始 0 15 9 21 34 41 40 總時(shí)差 0 6 0 0 13 1 0 (3)關(guān)鍵路線：；關(guān)鍵工序：A、C、D、G；完工期：48周。7.4 表7-19給出了項(xiàng)目的工序明細(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 工序時(shí)間(天) 8 5 7 12 8 17 16 8 14 5 10 23 15 12 （1）繪制項(xiàng)目網(wǎng)絡(luò)圖。（2）在網(wǎng)絡(luò)圖上求工序的最早開(kāi)始、最遲開(kāi)始時(shí)間。（3）用表格表示工序的最早最遲開(kāi)始和完成時(shí)間、總時(shí)差和自由時(shí)差。（4）找出所有關(guān)鍵路線及對(duì)應(yīng)的關(guān)鍵工序。（5）求項(xiàng)目的完工期。【解】(1)網(wǎng)絡(luò)圖 （2）工序最早開(kāi)始、最遲開(kāi)始時(shí)間 （3）用表格表示工序的最早最遲開(kāi)始和完成時(shí)間、總時(shí)差和自由時(shí)差 工序 t TES TEF TLS TLF 總時(shí)差S 自由時(shí)差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)鍵路線及對(duì)應(yīng)的關(guān)鍵工序 關(guān)鍵路線有兩條，第一條：；關(guān)鍵工序：B,E

25、,G,H,K,M 第二條：；關(guān)鍵工序：C,F,L,M （5）項(xiàng)目的完工期為62天。7.5已知項(xiàng)目各工序的三種估計(jì)時(shí)間如表7-20所示。求： 表7-20 工序 緊前工序 工序的三種時(shí)間（小時(shí)） 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ò)圖并計(jì)算各工序的期望時(shí)間和方差。（2）關(guān)鍵工序和關(guān)鍵路線。（3）項(xiàng)目完工時(shí)間的期望值。（4）假設(shè)完工期服從正態(tài)分布，項(xiàng)目在56小時(shí)內(nèi)完工的概率是多少。（5）使完工的概率為0.98，最少需要多長(zhǎng)時(shí)間。【解】（1）網(wǎng)絡(luò)圖 工序 緊前工序

26、工序的三種時(shí)間（小時(shí)） 期望值 方差 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) 項(xiàng)目完工時(shí)間的期望值：10.17+14.83+17.17+11.8354(小時(shí)) 完工期的方差為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小時(shí)。7.6 表7-21給出了工序的正常、應(yīng)急的時(shí)間和成本。表7-21 工序 緊前工序 時(shí)間(天) 成本 時(shí)間的最大縮量(天) 應(yīng)急增加成本（萬(wàn)元/天） 正常 應(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）繪制項(xiàng)目網(wǎng)絡(luò)圖，按正常時(shí)間計(jì)算完成項(xiàng)目的總成本和工期。（2）

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

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

30、2222，a0a1a21+0.70.492.192.222a0+a1a2a32.533，nt12，t=7，則16年低負(fù)荷運(yùn)行，710年為高負(fù)荷運(yùn)行。各年年初投入設(shè)備數(shù)如下表。年份 1 2 3 4 5 6 7 8 9 10 設(shè)備臺(tái)數(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， 由 故 為極大值點(diǎn)。所以 及最優(yōu)解x2*=s2 k=1時(shí)， ， 由，得 故 已知知x1 + x2+ x3 = C，因而按計(jì)算的順序推算，可得各階段的最優(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=為極小值點(diǎn)。因而有 k1

32、時(shí)， 由知 得到最優(yōu)解 【解】(3) 設(shè)s3=x3 , s3+x2=s2，s2+x1=s1=10 則有 x3= s3 ，0x2s2，0x1s1=10 用逆推法，從后向前依次有 k3時(shí)， 及最優(yōu)解 x3=s3 k2時(shí)， 而 。討論端點(diǎn)：當(dāng) x2=0時(shí), x2= s2時(shí) 如果s23時(shí), k1時(shí)， 同理有, 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 ,故 為極大值點(diǎn)。則 及最優(yōu)解x2*=s2/8 k1， ，故 得到最優(yōu)解 【解】(5) 按問(wèn)題中變量的個(gè)數(shù)分為三個(gè)階段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， 由,則 ,故 為極大值點(diǎn)。則 k3， 由 故，由于s310，則s3=10時(shí)取最大值，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時(shí)，f2（s2）=s22+2s2, x2*= s2時(shí)，f2（s2）=2s22 故 k3， 當(dāng)x2*=0時(shí)， 同樣得x3*=0時(shí) ，f3（s3）=s32+2s3 x3*=s3時(shí)，f3（s3）=s3 所以， f3（s3）= s32+2s3=80 當(dāng)x2*= s2時(shí)，f3（s3）=x3+2（s3-x3）2 同樣得x3*=0時(shí) ，f3（s3）=2s32 =128 x3*=s3時(shí)，f3（s3）=s3 =8 所以， f3（s3）= 2s32=1

35、28 最優(yōu)解為 8.4用動(dòng)態(tài)規(guī)劃求解下列線性規(guī)劃問(wèn)題?！窘狻吭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)單位價(jià)值如表8.24所示。應(yīng)該如何裝載貨物使總價(jià)值最大。表8.24 貨物編號(hào) 1 2 3 單位加工時(shí)間 2 3 4 單位價(jià)值 3 4 5 【解】設(shè)裝載第I種貨物的件數(shù)為xi（ i =1,2,3）則問(wèn)題可表為： 利用背包問(wèn)題的前向動(dòng)態(tài)規(guī)劃計(jì)算，建立動(dòng)態(tài)規(guī)劃模

36、型。由于決策變量離散型值，所以可用列表法求解。當(dāng)R=1時(shí)， 。計(jì)算結(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時(shí)，f2（s3）=4x2+f1（s3-3x2） 計(jì)算結(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時(shí)，f3（9）=5x3+f2（9-4x3） （x3為整數(shù)）=f2（9），5+f2（5），10+f2（1）=max13，12，10=13 8.6 有一輛貨車載重量為10噸 ，用來(lái)裝載貨物A、B時(shí)成本分別為5元/噸和4元/噸。現(xiàn)在已知每噸貨物的運(yùn)價(jià)與該貨物的重量有如下線性關(guān)系： A：P1=10-2x1 ，B：P2=12-3x2 其中x1 、x2 分別為貨物A、B的重量。如果要求貨物滿載，A和B各裝載多少，才能使總利潤(rùn)最大 【解】將原題改為A：P1=15-x1 ，B：P2=18-2x2 由題意可得各種貨物利潤(rùn)函數(shù)為 原問(wèn)題的數(shù)

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

39、）的冷庫(kù)存量 決策變量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時(shí)，因?yàn)閟6=0，有 由于s515， k=4時(shí)， k=3時(shí)，當(dāng)0s430時(shí)，得 有 當(dāng)30s440時(shí)，有 顯然此決策不可行。當(dāng)k=2時(shí)，由x2的決策允許集合為 當(dāng)k=1時(shí)，由，則x1的決策允許集合為 因?yàn)?(2)期初存儲(chǔ)量s1=8, 與前面計(jì)算相似，x1=2. Min Z=772.5+2.5x1-5s1=737.5 則總成本最小的方案是第二種。8.8 某企業(yè)計(jì)劃委派10個(gè)推銷員到

40、4個(gè)地區(qū)推銷產(chǎn)品，每個(gè)地區(qū)分配14個(gè)推銷員。各地區(qū)月收益（單位：10萬(wàn)元）與推銷員人數(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個(gè)地區(qū)的推銷人員使月總收益最大?！窘狻吭O(shè)xk為第k種貨物的運(yùn)載重量，該問(wèn)題的靜態(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