第一篇：運(yùn)籌學(xué)教程(第三版)清華大學(xué)出版社出版 郭耀煌 胡遠(yuǎn)權(quán)編著 習(xí)題答案習(xí)題答案專題

運(yùn)籌學(xué)教程（第二版）

習(xí)題解答

8.1 證明在9座工廠之間，不可能每座工廠只與其他3座工廠有業(yè)務(wù)聯(lián)系，也不可能只有4座工廠與偶數(shù)個(gè)工廠有業(yè)務(wù)聯(lián)系。

解：將有聯(lián)系的工廠做一條連線。

如果僅有9座工廠只與其他3座工廠有業(yè)務(wù)聯(lián)系，說(shuō)明頂點(diǎn)次數(shù)之和為27，矛盾。

如果只有4座工廠與偶數(shù)個(gè)工廠有業(yè)務(wù)聯(lián)系，其他5個(gè)工廠一定與奇數(shù)個(gè)工廠有業(yè)務(wù)聯(lián)系，說(shuō)明頂點(diǎn)次數(shù)之和還是奇數(shù)，矛盾。

8.2 有八種化學(xué)藥品A、B、C、D、E、F、G、H要放進(jìn)貯藏室。從安全角度考慮，下列各組藥品不能貯存在同一室內(nèi)：A—C，A—F，A—H，B—D，B—F，B—H，C—D，C—G，D—E，D—G，E—G，E—F，F(xiàn)—G，G—H，問(wèn)至少需要幾間貯藏室存放這些藥品。

解：能貯存在同一室內(nèi)的兩種藥品之間作一條連線。貯存在同一室內(nèi)的藥品應(yīng)該構(gòu)成一個(gè)完全圖。ABG，CFH，DE構(gòu)成完全圖。故，存放這些藥品最少需要3間儲(chǔ)藏室。

8.3

6個(gè)人圍成圓圈就座，每個(gè)人恰好只與相鄰者不相識(shí)，是否可以重新就座，使每 個(gè)人都與鄰座認(rèn)識(shí)?

解：兩個(gè)人認(rèn)識(shí)作一條連線。

8.4 判定圖8-50中的兩個(gè)圖能否一筆畫出，若能，則用圖形表示其畫法。

解：(a)圖都是偶點(diǎn)，可以一筆畫出。(b)圖只有兩個(gè)奇點(diǎn)，一個(gè)奇點(diǎn)為起點(diǎn)，另一個(gè)奇點(diǎn)為終點(diǎn)。

8.5 求解如圖8-51所示的中國(guó)郵路問(wèn)題，A點(diǎn)是郵局。

8.6 分別用深探法、廣探法、破圈法找出圖8-52所示圖的一個(gè)生成樹(shù)。

8.7 設(shè)計(jì)如圖5-53所示的鍋爐房到各座樓鋪設(shè)暖氣管道的路線，使管道總長(zhǎng)度最(單位：m)。

8.8 分別用避圈法和破圈法求圖8-54所示各圖的最小樹(shù)。

8.9 給定權(quán)數(shù)1，4，9，16，25，36，49，64，81，構(gòu)造—棵霍夫曼樹(shù)。

8.10 如圖8-55，v0是一倉(cāng)庫(kù)，v9是商店，求一條從v0到v9的最短路。

8.11 求圖8-56中v1到各點(diǎn)的最短路。

8.12 求圖8-57網(wǎng)絡(luò)中各頂點(diǎn)間的最短路。

8.13 某設(shè)備今后五年的價(jià)格預(yù)測(cè)分別是(5，5，6，7，8)，若該設(shè)備連續(xù)使用，其第j年的維修費(fèi)分別為(1，2，3，5，6)，某單位今年購(gòu)進(jìn)一臺(tái)，問(wèn)如何確定更新方案可使5年里總支出最小(不管設(shè)備使用了多少年，其殘值為0)。

解：最優(yōu)解為：先使用兩年，更新后再使用三年?；蛳仁褂萌?，更新后再使用兩年。最小總支出20。

8.14 求圖8-58中網(wǎng)絡(luò)最大流，邊上數(shù)為(cij，fij)。

解：最大流量為14。

8.15 如圖8-59，發(fā)點(diǎn)S1，S2分別可供應(yīng)10和15個(gè)單位，收點(diǎn)t1，t2可以接收10和25個(gè)單位，求最大流，邊上數(shù)為cij。

解：最大流量為21。

0

8.16 如圖8-60，從v派車到v，中間可經(jīng)過(guò)v，?-，v各站，若各

817站間道路旁的數(shù)字表示單位時(shí)間內(nèi)此路上所能通過(guò)的最多車輛數(shù)，問(wèn)應(yīng)如何派車才能使單位時(shí)間到達(dá)v8的車輛最多?

解：最大流量為40輛。

8.17 某單位招收懂俄、英、日、德、法文翻譯各1人，有5人應(yīng)聘。已知：乙懂俄文，甲、乙、丙懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，問(wèn)這5個(gè)人是否都能得到聘書?最多幾人能得到招聘，各從事哪一方面的翻譯任務(wù)?

解：某人懂某種語(yǔ)言作一條連線，權(quán)數(shù)為1。

甲---英語(yǔ) 乙-----俄語(yǔ)

丁---日語(yǔ) 戊-----法語(yǔ)

最多招聘4個(gè)人。

8.18 甲、乙、丙、丁、戊、己6人組成一個(gè)小組，檢查5個(gè)單位的工作，若一單位和乙、丙、丁三人有工作聯(lián)系，則用{乙，丙，丁}表示，其余四個(gè)單位分別為{甲，戊，己}，{甲，乙，戊，己}，{甲，乙，丁，己}，{甲，乙，丙}。若到一個(gè)單位去檢查工作的人必須是和該單位沒(méi)有聯(lián)系的人，問(wèn)應(yīng)如何安排?

解：此題應(yīng)該假設(shè)1人只能去1個(gè)單位檢查工作。但是一個(gè)單位可以有多人去檢查。具體安排如下：

甲和己→單位

1、乙→單位2、丙→單位3、丁→單位5、戊→單位4。

8.19 圖8-61所示網(wǎng)絡(luò)中，有向邊旁數(shù)字為(cij，dij)，cij表示容量，dij表示單位流量費(fèi)用，試求從vs到vt流值為6的最小費(fèi)用流。

解： 最小費(fèi)用為35。流量分布見(jiàn)下一個(gè)圖形。

8.20 某種貨物由2個(gè)倉(cāng)庫(kù)A1，A2運(yùn)送到3個(gè)配貨中心B1，B2，B3。A1，A2的庫(kù)存量分別為每天13t，9t；B1，B2，B3每天需求分別為9t，5t，6t。各倉(cāng)庫(kù)到配貨中心的運(yùn)輸能力、單位運(yùn)費(fèi)如表8—4，求運(yùn)費(fèi)最省的運(yùn)輸方案。

解：最小費(fèi)用流為105。流量分布如下：

8.21 有5批貨物，要用船只從x1,x2地分別運(yùn)往y1,y2,y3地。規(guī)定每批貨物出發(fā)日期如表8-5所示，又知船只航行所需時(shí)間(d)如表8-6所示。每批貨物只需一條船裝運(yùn)，在空載和重載時(shí)航行時(shí)間相同，要求制定計(jì)劃，以最少的船只完成這5項(xiàng)運(yùn)輸任務(wù)。

解：兩條船就夠了。

一條船完成：T4→T5→T3；

另一條船完成：T1→T2。