運(yùn)籌學(xué)習(xí)題答案(第八章)

1、1同樣適合第三版黃皮版同樣適合第三版黃皮版電話：電話：5108157(H)，5107443(O)E-mail: Hongwen9509_3第八章習(xí)題解答 8.1 證明在證明在9座工廠之間，不可能每座工廠只座工廠之間，不可能每座工廠只與其他與其他3座工廠有業(yè)務(wù)聯(lián)系，也不可能只有座工廠有業(yè)務(wù)聯(lián)系，也不可能只有4座工廠座工廠與偶數(shù)個工廠有業(yè)務(wù)聯(lián)系。與偶數(shù)個工廠有業(yè)務(wù)聯(lián)系。 解：將有聯(lián)系的工廠做一條連線。解：將有聯(lián)系的工廠做一條連線。如果僅有如果僅有9座工廠只與其他座工廠只與其他3座工廠有業(yè)務(wù)聯(lián)系，座工廠有業(yè)務(wù)聯(lián)系，說明頂點(diǎn)次數(shù)之和為說明頂點(diǎn)次數(shù)之和為27，矛盾。，矛盾。如果只有如果只有4座工廠與偶數(shù)

2、個工廠有業(yè)務(wù)聯(lián)系，座工廠與偶數(shù)個工廠有業(yè)務(wù)聯(lián)系，其他其他5個工廠一定與奇數(shù)個工廠有業(yè)務(wù)聯(lián)系，說明個工廠一定與奇數(shù)個工廠有業(yè)務(wù)聯(lián)系，說明頂點(diǎn)次數(shù)之和還是奇數(shù)，矛盾。頂點(diǎn)次數(shù)之和還是奇數(shù)，矛盾。4 8.2 有八種化學(xué)藥品有八種化學(xué)藥品A、B、C、D、E、F、G、H要放進(jìn)貯藏室。從安全角度考慮，下列各組藥品要放進(jìn)貯藏室。從安全角度考慮，下列各組藥品不能貯存在同一室內(nèi)：不能貯存在同一室內(nèi)：AC，AF，AH，BD，BF，BH，CD，CG，DE，DG，EG，EF，F(xiàn)G，GH，問至少需要幾間貯，問至少需要幾間貯藏室存放這些藥品。藏室存放這些藥品。 解：能貯存在同一室內(nèi)的兩種藥品之間作一條解：能貯存在同一室內(nèi)

3、的兩種藥品之間作一條連線。貯存在同一室內(nèi)的藥品應(yīng)該構(gòu)成一個完全圖。連線。貯存在同一室內(nèi)的藥品應(yīng)該構(gòu)成一個完全圖。ABG，CFH，DE構(gòu)成完全圖。故，存放這些藥品構(gòu)成完全圖。故，存放這些藥品最少需要最少需要3間儲藏室。間儲藏室。第八章習(xí)題解答5 8.3 6個人圍成圓圈就座，每個人恰好只與相個人圍成圓圈就座，每個人恰好只與相鄰者不相識，是否可以重新就座，使每鄰者不相識，是否可以重新就座，使每 個人都與鄰個人都與鄰座認(rèn)識座認(rèn)識? 解：兩個人認(rèn)識作一條連線。解：兩個人認(rèn)識作一條連線。第八章習(xí)題解答6第八章習(xí)題解答 8.4 判定圖判定圖8-50中的兩個圖能否一筆畫出，若中的兩個圖能否一筆畫出，若能，則用

4、圖形表示其畫法。能，則用圖形表示其畫法。解：解： (a)圖都是偶點(diǎn)，可以一筆畫出。圖都是偶點(diǎn)，可以一筆畫出。(b)圖只有圖只有兩個奇點(diǎn)，一個奇點(diǎn)為起點(diǎn)，另一個奇點(diǎn)為終點(diǎn)。兩個奇點(diǎn)，一個奇點(diǎn)為起點(diǎn)，另一個奇點(diǎn)為終點(diǎn)。 7 8.5 求解如圖求解如圖8-51所示的中國郵路問題，所示的中國郵路問題，A點(diǎn)點(diǎn)是郵局。是郵局。 第八章習(xí)題解答8第八章習(xí)題解答9 8.6 分別用深探法、廣探法、破圈法找出圖分別用深探法、廣探法、破圈法找出圖8-52所示圖的一個生成樹。所示圖的一個生成樹。 第八章習(xí)題解答10第八章習(xí)題解答11第八章習(xí)題解答12第八章習(xí)題解答13 8.7 設(shè)計如圖設(shè)計如圖5-53所示的鍋爐房到各座

5、樓鋪設(shè)暖所示的鍋爐房到各座樓鋪設(shè)暖氣管道的路線，使管道總長度最氣管道的路線，使管道總長度最(單位：單位：m)。 第八章習(xí)題解答14第八章習(xí)題解答15 8.8 分別用避圈法和破圈法求圖分別用避圈法和破圈法求圖8-54所示各圖的最所示各圖的最小樹。小樹。 第八章習(xí)題解答16第八章習(xí)題解答17 8.9 給定權(quán)數(shù)給定權(quán)數(shù)1，4，9，16，25，36，49，64，81，構(gòu)造，構(gòu)造棵霍夫曼樹。棵霍夫曼樹。 第八章習(xí)題解答18 8.10 如圖如圖8-55，v0是一倉庫，是一倉庫，v9是商店，求一是商店，求一條從條從v0到到v9的最短路。的最短路。 第八章習(xí)題解答19第八章習(xí)題解答20 8.11 求圖求圖8-

6、56中中v1到各點(diǎn)的最短路。到各點(diǎn)的最短路。 第八章習(xí)題解答21第八章習(xí)題解答22 8.12 求圖求圖8-57網(wǎng)絡(luò)中各頂點(diǎn)間的最短路。網(wǎng)絡(luò)中各頂點(diǎn)間的最短路。 第八章習(xí)題解答23第八章習(xí)題解答091201820014020121650)0(D0912018200321436020121650)1(D0948123201820032143602012191650)2(D0948123201820032143602012191650)3(D24第八章習(xí)題解答0948123201820032143602012191650)4(D094812320182002050321436020121916505

7、4321)5(54321VVVVVDVVVVV25 8.13 某設(shè)備今后五年的價格預(yù)測分別是某設(shè)備今后五年的價格預(yù)測分別是(5，5，6，7，8)，若該設(shè)備連續(xù)使用，其第，若該設(shè)備連續(xù)使用，其第j年的維修費(fèi)年的維修費(fèi)分別為分別為(1，2，3，5，6)，某單位今年購進(jìn)一臺，某單位今年購進(jìn)一臺，問如何確定更新方案可使問如何確定更新方案可使5年里總支出最小年里總支出最小(不管設(shè)不管設(shè)備使用了多少年，其殘值為備使用了多少年，其殘值為0)。解：最優(yōu)解為：先使用兩年，更新后再使用三解：最優(yōu)解為：先使用兩年，更新后再使用三年?；蛳仁褂萌?，更新后再使用兩年。最小總支年?；蛳仁褂萌?，更新后再使用兩年。最小總支

8、出出20。第八章習(xí)題解答26 8.14 求圖求圖8-58中網(wǎng)絡(luò)最大流，邊上數(shù)為中網(wǎng)絡(luò)最大流，邊上數(shù)為(cij，fij)。解：最大流量為解：最大流量為14。 第八章習(xí)題解答27第八章習(xí)題解答28 8.15 如圖如圖8-59，發(fā)點(diǎn)，發(fā)點(diǎn)S1，S2分別可供應(yīng)分別可供應(yīng)10和和15個單位，收點(diǎn)個單位，收點(diǎn)t1，t2可以接收可以接收10和和25個單位，求最大個單位，求最大流，邊上數(shù)為流，邊上數(shù)為cij。 第八章習(xí)題解答29 解：最大流量為解：最大流量為21。第八章習(xí)題解答30 8.16 如圖如圖8-608-60，從，從v v0 0派車到派車到v v8 8，中間可經(jīng)過，中間可經(jīng)過v v1 1，v v7 7

9、各站，若各站間道路旁的數(shù)字表示單位各站，若各站間道路旁的數(shù)字表示單位時間內(nèi)此路上所能通過的最多車輛數(shù)，問應(yīng)如何派時間內(nèi)此路上所能通過的最多車輛數(shù)，問應(yīng)如何派車才能使單位時間到達(dá)車才能使單位時間到達(dá)v v8 8的車輛最多的車輛最多? ?第八章習(xí)題解答31 解：最大流量為解：最大流量為40輛。輛。第八章習(xí)題解答32 8.17 某單位招收懂俄、英、日、德、法文某單位招收懂俄、英、日、德、法文翻譯各翻譯各1人，有人，有5人應(yīng)聘。已知：乙懂俄文，甲、人應(yīng)聘。已知：乙懂俄文，甲、乙、丙懂英文，甲、丙、丁懂日文，乙、戊懂乙、丙懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，問這德文，戊懂法文，問這5個人是

10、否都能得到聘書個人是否都能得到聘書?最多幾人能得到招聘，各從事哪一方面的翻譯最多幾人能得到招聘，各從事哪一方面的翻譯任務(wù)任務(wù)? 解：某人懂某種語言作一條連線，權(quán)數(shù)為解：某人懂某種語言作一條連線，權(quán)數(shù)為1 1。 甲甲-英語英語 乙乙-俄語俄語 丁丁-日語日語 戊戊-法語法語最多招聘最多招聘4 4個人。個人。第八章習(xí)題解答33 8.18 甲、乙、丙、丁、戊、己甲、乙、丙、丁、戊、己6人組成一個人組成一個小組，檢查小組，檢查5個單位的工作，若一單位和乙、丙、個單位的工作，若一單位和乙、丙、丁三人有工作聯(lián)系，則用丁三人有工作聯(lián)系，則用乙，丙，丁乙，丙，丁表示，其余表示，其余四個單位分別為四個單位分別為

11、甲，戊，己甲，戊，己，甲，乙，戊，己甲，乙，戊，己，甲，乙，丁，己甲，乙，丁，己，甲，乙，丙甲，乙，丙。若到一個單位。若到一個單位去檢查工作的人必須是和該單位沒有聯(lián)系的人，問去檢查工作的人必須是和該單位沒有聯(lián)系的人，問應(yīng)如何安排應(yīng)如何安排? 解：此題應(yīng)該假設(shè)解：此題應(yīng)該假設(shè)1 1人只能去人只能去1 1個單位檢查工作。個單位檢查工作。但是一個單位可以有多人去檢查。具體安排如下：但是一個單位可以有多人去檢查。具體安排如下： 甲和己甲和己單位單位1、乙、乙單位單位2 、丙、丙單位單位3 、丁、丁單位單位5 、戊、戊單位單位4 。第八章習(xí)題解答34 8.19 圖圖8-61所示網(wǎng)絡(luò)中，有向邊旁數(shù)字為所示

12、網(wǎng)絡(luò)中，有向邊旁數(shù)字為(cij，dij)，cij表示容量，表示容量，dij表示單位流量費(fèi)用，試求從表示單位流量費(fèi)用，試求從vs到到vt流值為流值為6的最小費(fèi)用流。的最小費(fèi)用流。解：解： 最小費(fèi)用為最小費(fèi)用為3535。流量分布見下一個圖形。流量分布見下一個圖形。第八章習(xí)題解答35第八章習(xí)題解答36 8.20 某種貨物由某種貨物由2個倉庫個倉庫A1，A2運(yùn)送到運(yùn)送到3個配貨中個配貨中心心B1，B2，B3。A1，A2的庫存量分別為每天的庫存量分別為每天13t，9t；B1，B2，B3每天需求分別為每天需求分別為9t，5t，6t。各倉庫到配。各倉庫到配貨中心的運(yùn)輸能力、單位運(yùn)費(fèi)如表貨中心的運(yùn)輸能力、單位

13、運(yùn)費(fèi)如表84，求運(yùn)費(fèi)最省，求運(yùn)費(fèi)最省的運(yùn)輸方案。的運(yùn)輸方案。 第八章習(xí)題解答表表8-4運(yùn)程運(yùn)程運(yùn)量限制運(yùn)量限制( (t td)d)運(yùn)費(fèi)運(yùn)費(fèi)( (百元百元/ /t)t)AlB1AlB183AlB2AlB271lAlB3AlB3510A2B1A2B16SA2B2A2B237A2B3A2B35437 解：最小費(fèi)用流為解：最小費(fèi)用流為105。流量分布如下：。流量分布如下：第八章習(xí)題解答38 8.21 8.21 有有5 5批貨物，要用船只從批貨物，要用船只從x x1 1,x,x2 2地分別地分別運(yùn)往運(yùn)往y y1 1,y,y2 2,y,y3 3地。規(guī)定每批貨物出發(fā)日期如表地。規(guī)定每批貨物出發(fā)日期如表8-58-5所所示，又知船只航行所需時間示，又知船只航行所需時間(d)(d)如表如表8-68-6所示。每批所示。每批貨物只需一條船裝貨物只需一條船裝運(yùn)，在空載和重載時航行時間相運(yùn)，在空載和重載時航行時間相同，要求制定計劃，以最少的船只完成這同，要求制定計劃，以最少的船只完成這5項運(yùn)輸項運(yùn)輸任務(wù)。任務(wù)。 第八章習(xí)題解答表表8-5地點(diǎn)地點(diǎn)y y1 1y y2 2y y3 3x x1 15 51010/ /x x2 2/ /12121,81,8表表8-5地點(diǎn)地點(diǎn)y y1 1y y2 2y y3 3x x1 12 23