二三版兼用《運籌學教程》胡運權主編課后習題答案第八章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.36個人圍成圓圈就座，每個人恰好只與相鄰者不相識，是否可以重新就座，使每個人都與鄰座認識?

解：兩個人認識作一條連線。二三版兼用《運籌學教程》胡運權主編課后習題答案第八章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。二三版兼用《運籌學教程》胡運權主編課后習題答案第八章

8.16如圖8-60，從v0派車到v8，中間可經過v1，…，v7各站，若各站間道路旁的數字表示單位時間內此路上所能通過的最多車輛數，問應如何派車才能使單位時間到達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，求運費最省的運輸方案。

表8-4運程運量限制(t／d)運費(百元/t)Al—B183Al—B271lAl—B3510A2—B16SA2—B237A2—B354二三版兼用《運籌學教程》胡運權主編課后習題答案第八章

解：最小費用流為105。流量分布如下：二三版兼用《運籌學教程》胡運權主編課后習題答案第八章

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