第一篇：運籌學教程(第三版)清華大學出版社出版 郭耀煌 胡遠權編著 習題答案習題答案專題

運籌學教程（第二版）

習題解答

8.1 證明在9座工廠之間，不可能每座工廠只與其他3座工廠有業務聯系，也不可能只有4座工廠與偶數個工廠有業務聯系。

解：將有聯系的工廠做一條連線。

如果僅有9座工廠只與其他3座工廠有業務聯系，說明頂點次數之和為27，矛盾。

如果只有4座工廠與偶數個工廠有業務聯系，其他5個工廠一定與奇數個工廠有業務聯系，說明頂點次數之和還是奇數，矛盾。

8.2 有八種化學藥品A、B、C、D、E、F、G、H要放進貯藏室。從安全角度考慮，下列各組藥品不能貯存在同一室內：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—G，G—H，問至少需要幾間貯藏室存放這些藥品。

解：能貯存在同一室內的兩種藥品之間作一條連線。貯存在同一室內的藥品應該構成一個完全圖。ABG，CFH，DE構成完全圖。故，存放這些藥品最少需要3間儲藏室。

8.3

6個人圍成圓圈就座，每個人恰好只與相鄰者不相識，是否可以重新就座，使每 個人都與鄰座認識?

解：兩個人認識作一條連線。

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

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

8.5 求解如圖8-51所示的中國郵路問題，A點是郵局。

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

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

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

8.9 給定權數1，4，9，16，25，36，49，64，81，構造—棵霍夫曼樹。

8.10 如圖8-55，v0是一倉庫，v9是商店，求一條從v0到v9的最短路。

8.11 求圖8-56中v1到各點的最短路。

8.12 求圖8-57網絡中各頂點間的最短路。

8.13 某設備今后五年的價格預測分別是(5，5，6，7，8)，若該設備連續使用，其第j年的維修費分別為(1，2，3，5，6)，某單位今年購進一臺，問如何確定更新方案可使5年里總支出最小(不管設備使用了多少年，其殘值為0)。

解：最優解為：先使用兩年，更新后再使用三年。或先使用三年，更新后再使用兩年。最小總支出20。

8.14 求圖8-58中網絡最大流，邊上數為(cij，fij)。

解：最大流量為14。

8.15 如圖8-59，發點S1，S2分別可供應10和15個單位，收點t1，t2可以接收10和25個單位，求最大流，邊上數為cij。

解：最大流量為21。

0

8.16 如圖8-60，從v派車到v，中間可經過v，?-，v各站，若各

817站間道路旁的數字表示單位時間內此路上所能通過的最多車輛數，問應如何派車才能使單位時間到達v8的車輛最多?

解：最大流量為40輛。

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

解：某人懂某種語言作一條連線，權數為1。

甲---英語 乙-----俄語

丁---日語 戊-----法語

最多招聘4個人。

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

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

甲和己→單位

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

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

解： 最小費用為35。流量分布見下一個圖形。

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

解：最小費用流為105。流量分布如下：

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

解：兩條船就夠了。

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

另一條船完成：T1→T2。