245 如果問題是二進位制整數線性規劃，則需要在 Solver Parameters 對話方塊中設定選擇 “bin”，而不選擇 “int” 不同的整數線性規劃，求解最優解所需的時間會相差很大。如果在一段合理的時間內仍得不出最優結果， 則可以嘗試把公差調到5%，甚至更高值。這樣，當在給定的公差之內，找到最接近最優解的解時就停止計算。 重新設定公差時，在Solver Options 對話方塊中點選 Integer Options（參見圖8-16）。然後會出現 Integer Options 對話框，在Tolerance一欄中輸人你想設定的公差（見圖8-17）。圖8-17中顯示伊斯特伯恩公司房地產問題的公差一欄填成0。在更為難求的問題中，可以輸人0.05，此時，當軟體得到一個與最優解的公差在5%之內的解時就停止計算。 100 0.000001 0.000001 0.000001 5000 圈8-16 伊斯特伯恩公司房地產問題的 Solver Options 對話方塊圖8-17 伊斯特伯恩公司房地產問題的 Integer Option 對話方塊第9章網路模型運輸系統設計、資訊系統設計和專案進度安排等許多管理問題已經在網路模型和網路分析技術的幫助下得以成功解決。在第7章中我們介紹了由節點和弧組成的網路是如何用來提供運輸、指派以及轉運問題的圖形表示的。在本章中我們介紹另外3個網路問題：最短路問題、最小支撐樹問題和最大流量問題。在每一個部分中，我們將介紹為了提供問題的最佳解決方案，一個網路模型是如何被構造和如何求解的。專欄9-1介紹了 AT&T 在設計其傳輸網路時是如何解決最短路和最大流量問題的。 專欄9-1實踐中的管理科學 AT&T 公司的最優恢復能力 AT&T公司是一家提供遠距離聲訊、資料、影象、無線、衛星和網路服務的全球電信公司。該公司運用最新水平的轉換和傳輸裝置來為8000 多萬名客戶提供服務。在美國本土的大陸上，AT&T 公司的傳輸網路由4萬多英里的纖維光纜組成。在高峰時間，AT&T公司要處理大約2.90化各種各樣的呼叫。 能源耗損、自然災害、光纜斷裂或其他的一些事件會使部分傳輸網路癱痰。當這樣的事件發生時，為了使服務不被幹擾，包含恢復性網路的備用能力必須立即起用。關於恢復性網路的重要問題包括：多少備用能力是必要的？應位於何處？1997年，AT&T公司組織了一個RestNet 工作組來處理這些問題。 為了最佳化恢復能力，RestNet 工作組發展了一個大型的線性規劃模型。模型中的一個子問題包含每當在傳輸網路範圍內出現錯誤，連線起點與終點之間最短路的決定問題。另外一個子問題是解答為了找到從每一個轉換器到災難恢復轉換器的最佳恢復線路的最大流量問題。 該工作組是成功的，而它的工作則成為管理科學方法論對公司重要性的例證。根據C.Michael Armstrong—AT&T 公司童事長兼執行長所說：“去年RestNet 工作組的工作使我們減少好幾千萬美元的資金花費。" 資料來源：蒸於：Ken Ambs, Sebastian Cwilich,Mei Deng, David J. Houck, David F. Lynch and Dicky Yan "0ptimizing Restoration Capacity in the AT&T Network， "Interfaces （January/February 3000）： 26-44.
第9章網路模型 247 9.1 最短路問題在這一部分中，我們將探討網路應用路程（英里） 問題，其中的基本目標是確定在任意兩個網路節點間的最短路。我們以探討戈曼建築公司的現實狀況來解釋最短路問題。戈曼公司的幾個建築工程專案位於包括3個縣的區域內。建築工地有時位於距戈曼總部遠達50英里之外的地方。由於每天在總部 10 4 與工地之間需要多次往返運送員工、裝置戈曼公司總部和物料，因此與運輸活動有關的成本相當高。對於任一給定的建築工地，在工地與圖9-1 戈曼公司的路線網路最短路問題總部間的運輸線路可被看成一個由小路、 注：每條孤的長度並不與它實際代表的距離成比例。 街道和高速公路組成的網路。在圖9-1 中顯示的網路描述了往返於戈曼總部和6個最新建築工地的運輸線路，那些小圓圖或稱網路節點表示建築工地所在地；那些小路、街道以及高速公路用弧表示。工地間的距離在相對應的弧上有所標明。現在戈曼公司希望確定一條路徑或線路，使得從總部到每個工地地點整個運輸路程最小化。 最短路箅法為了解決戈曼公司的問題，我們需要確定從戈曼公司總部（節點1）到網路上任意其他節點的最短路。我們這裡提到的演算法使用了一種標識法來尋找從節點1到每一個其他節點的最短路。當我們實施標識法的步驟時，會發現每一個節點都有一個由括號中的兩個數字組成的標識。對應某一特定節點的標識上的第一個數字指的是從節點1到那個節點的距離。而第二個數字指從節點1到那個節點路線上的前一節點。我們將會在網路每一個節點的上方或是下方進行直接標識。例如，某一特定節點的標識可能會如同圖9-2展示的那樣。 在標識法的任何步驟中，一個節點可以是已標識或是未標識的。一個已標識的節點是我們已確認了從節點1到那個節點的路線；一個未標識的節點是指該路線我們還沒有確認。一個標識過的節點既可是永久性的標識，也可是暫時性的標識。只要從節點1到某一特定節點的最短路已確定，該節點就有了永久性標識。然而，如果從節點1到某一特定已標識節點的最短路還未確定，我們就說該節點具有一個暫時性標識。現在，讓我們說明這些標識是如何計算出來以及這種標識方法是如何用於決定網絡中的每一個節點的最短路的。 節點1至該節點的距離是20 節點1至該節點的這條路徑上的前 -節點是節點4 17 T0.S］ 120.4］ 如節點標識圖9-2 節點標識示例圖9-3 戈費公司最短路問題的最初網路認定我們從給定節點1一個永久性標識［O，S］開始介紹標識過程。“0” 表示從節點1到它自己的距
248 資料、模型與決策：管理科學篇離是零。“S” 表示把節點1看成起始節點。 為了區分暫時性和永久性的已標識節點，在網路中我們使用黑色陰影表示所有永久性標識節點。此外，箭頭指明標識演算法的每一步正在研究的永久性已標識節點。當僅有節點 1 被永久標識時，戈曼公司網路的最初認定情況見圖9-3。 為了執行第一個步驟或啟動標識過程， 我們必須考慮所有能從節點1直接到達的節點。因此，我們會先考慮節點2，然後是節點3。我們看到從節點1到節點2的直接距離是15 英里。於是，節點2被暫時標識為 【15，1］。第二個數字表示在到達節點2的路線上的前一點是節點1。下一步，我們考慮節點3，並且發現從節點1到節點3的直接距離是10英里。於是，節點3的暫時性標識為［10，1］。圖9-4展示了到目前為止節點 2 和節點3被暫時標識後的結果。 參考圖9-4，現在我們考慮所有暫時性已標識的節點並確認其標識為最小距離值的節點。這樣，距離為10英里的節點3被選中。我們可以沿著一個更短路線到達節點嗎？ 因為任何其他到達節點3的路線總是要經過其他節點，同時從節點1到其他節點的距離大於或等於10英里，所以一條到達節點3的更短路線是找不到的。因此，節點3被永久標識的距離為10英里。陰影表示節點3是一個永久性已標識節點。箭頭表示節點3會被用於下一步的標識法。該步驟結果見圖9-5。 我們接下來考察所有還未被永久標識的並且可以從節點3直接到達的節點。它們是節點3和節點5。記住，從節點3到節點2的直接臣離為3英里，同時從節點3到節點5 的距離為4英里。又因節點3的永久性標識表明到節點3的最短距離為10英里，所以我們可以算出到達節點2的距離為10+3=13 （英里）；到達節點5的距離為10+4=14 （英里）。因此，節點2的暫時性標識被改為 ［13，3］。這表明我們現在已找到了一條從節點1到節點2的只有13英里的路線，並且經過節點3。節點5的暫時性標識定為［14， 3］。圖9-6展示了對於此點的網路計算結果。 為了找到在其標識上具有最小距離值的節點，我們下一步考察所有暫時性已標識節 ［15,1］ ［0S］ 心 10 ［10,1］ 圖9-4 戈曼公司網路一節點2和節點3為暫時性標識 ［15,1］ 心 ［0,S］ ~ 10 ［10,1］ 圖 9-5 戈曼公司網路一節點3為永久性標識 ［13,3］ 9 ［0,S］ 10 ［14,3］ ［10,1］ 圖9-6 戈曼公司網路一一節點2和節點5被暫時標識 ［30,2］ ［13,3］ 5 6 ［19,2］ 心 ［0,S］ 10 ［14,3］ 圖 9-7 ［10,1］ 艾要公司網路——節點2被永久標識， 節點4 和節點7被督時標識點。從圖9-6中我們看到了距離為13英里的節點 2。現在節點2被永久標識，因為我們知道從節點 1經過節點3到節點2的最短距離為13英里。 從節點2這個最近被永久標識的點開始，我們進入下一步。和從前一樣，我們考察每一個非永久性標識的，並可以從節點2直接到達的節點。它們是節點4 和節點7。以永久性標識節點2的距離值13為基數，加上從節點2到節點 4 和節點7的距離值，我們可以得出到達節點4 的距離為13+6=19（英里）；到達節點7的臣離為13+17=30（英里）。因而，節點4 和節點7的暫時性標識如圖9-7所示。 從這些暫時性已標識節點中（節點4、5 和7），我們選擇具有最小距離值的節點並宣佈此節點被水久標識。因此，距離為14英里的節點5成了新的永久性已標識節點。然後，從節點5，我們考察所有可以從其直接到達的非永久性已標識節點。於是，節點4的暫時性標識被更改，同時節點6被暫時性標識。圖9-8描述了這一步驟的計算過程。 餘下的暫時性已標識節點的最短距離要被再次計算。這次，節點6被永久標識。從節點 6 我們可以確定一個新的暫時性標識，即距離值為22英里的節點7。完成這一步後，新的網絡面貌如圖9-9所示。 現在我們僅剩兩個非永久性已標識節點了。 因為節點4的距離值小於節點7，所以節點 4 成了新的永久性已標識節點。又因節點7是僅剩的一個非永久性已標識的，又可從節點4直接到達的節點，我們將其距離值22英里同節點 4 距離值與從節點4到節點7的距離值之和， 也就是18+5=23（英里）進行比較。因為節點7的暫時性標識［22，6］ 要小些，所以它保持不變。圖9-10為此點的網路圖。 因為節點7是僅剩的具有暫時性標識的節點，所以它現在也被永久標識。圖9-11 展示了所有節點被永久標識後的最終網路圖。 我們現在可以利用永久標識的資訊在網路中尋找從節點1到每個節點的最短路。例如， 節點7的永久標識告訴我們，從節點1到節點 7的最短距離為22英里。為了找到使我們能夠以22英里的距離到達節點7的這條待定路線， 我們從節點7開始倒推回節點1。節點7的標識為我們指明下一個連結—節點6，節點6 第9章網路模型 249 17 ［18,5］ +19:27 130,2） ［0,S］ ［0,S］ ［0.S］ ［13,3］ 10 ［14,3］ ［10.1］ 田9-8， 戈曼公司網路—節點5被永久標識，節點4 和節點6被暫時標識 ［13,3］ 118,5 心 10 4 ［14,3） ［10,1］ 圖9-9 戈曼公司網路——節點6 被永久標識，節點7被暫時標識 ［13,3］ 17 6 ［18,5 心 10 4 ［14,3］ ［10,1］ ［16.5］ ［22,6］ ［16,5］ ［22,6］ ［16,5］ 圖 9-10 戈愛公司網路一一節點4被永久標識 ［22,6］ ［13,3］ 6 9 118,51 心 T0,S］ ［16,5］ 10 4 ［14,3］ 圈 9-11 ［10,1］ 戈曼公司網路——所有節點被永久標識後
250 資料、模型與決策：管理科學篇的標識表示節點5是下一個最短連結。繼續此過程，我們從節點3到節點5，最後，從節點1到達節點3。因此，從節點1到達節點7的最短路為1-3-5—6—7。利用此方法，找到戈曼公司網路中的最短路，如下所示： 節點 2 3 4 從節點1的最短路距窩（英里） 節點從節點1的最短路距腐（英里） 1—3 2 13 1—3 5 14 1—3 10 6 1-3-5-6 16 1—3--5—4 18 7 1—3-5-6-7 22 或許透過觀察，對於一個像戈曼公司遇到的這樣的小問題，你可能已經很快，即使不是馬上，找到最短路了。然而，當我們開始研究一個具有15~20個或更多節點的問題時，如果還是透過觀察找最短路的話，那將會很費時。實際上，在一個更大的網路中，由於大量增加的可選路線，我們很容易遺漏一條或更多的路線而得到錯誤的答案。因此，對於更大的問題，一種系統的方法，例如前面提到的標識法，就很必要了。即便有了標識法，我們發現隨著網路的增大，人們也有必要藉助電腦來執行計算。 在我們總結最短路方法的同時，思考一下由N個節點組成的網路。下面的方法可用於查詢從節點 1到網路中任何其他節點的最短路。 第一步：分配節點1永久標識【0，S］。“0”指從節點1到其自身的距離為零。“S”指節點1為起始節點。 第二步：計算可從節點1直接到達的暫時標識節點數。每個標識中的第一個數字是從節點1到該未確定節點路線上的前一個節點。因此，此步前一個節點值為1，因為我們考察的僅是可以從節點1 直接到達的節點。 第三步：確定具有最小距離值的暫時性已標識節點並且宣佈該節點被永久標識。如果所有節點都被永久標識，跳到第五步。 第四步：考察剩餘的那些在第三步中已確認的從新的永久性已標識節點所能到達的，且未被永久標識的節點。計算這些新的暫時性標識節點的過程如下。 8.如果待確定的節點有一個暫時性標識，那麼則將新的永久標識節點的距離值與從該新永久性標識節點到待確認節點間的直接距離相加。如果其和小於這個待確定節點的距離值，那麼該節點的距離值就等於這個和。另外，具有更小臣離值的新的永久性已標識節點與前一個節點值相等。返回第三步。 b.如果該待確定的節點還未被標識，則透過將新的永久性標識節點的距離值與從該新永久性標識節點到待確認節點間的直接距離相加，為該節點建立一個暫時性標識。前一節點值與新的永久性已標識節點值相等。返回第三步。 第五步：永久性標識既確認了從節點1到每個節點的最短路，也確定了最短路上前一個節點值。 一個給定節點的最短路，可以透過從該給定節點開始倒推至其前一個節點的方法找到。在網路上繼續此倒推過程，就會得出從節點1到待確定節點的最短路。 這種演算法可用以確定網路中節點1到任意其他節點的最節最短路問題可以按轉運問題列公式短路。對於找到所有其他節點的最短距離來說，該演算法並得以解決。我們只需偷單地將起始節點 N-1次的重複是必要的。如果每一個節點並不需要最小距的供給和終點節點的需求設為1就可以了。 離值，那麼當這些相關節點被永久標識後，此計算停止。為但是，與標識演算法不同，這種方法無法找了找到從任何一點開始到網路其他節點的最短路，比如k，到從起始節點到其他每個節點的最短略。 此方法也很容易隨之改變。在此變化下，我們將僅僅從把後點水久標識為［0，S］開始就可以了。然後，透過運用標識法的其他步驟，我們就可以找到從節點h 到網路中其他任意節點的最短路了。 管理科學家軟體包可被用於解決小型最短路問題。該程式的輸入包括節點的個數、弧的條數以及每條弧的長度等資料。圖9-12所示輸出結果為戈曼公司問題的答案，即從節點1到節點7的最短路。
第9童網路模型 251 註釋與評論 1. 在許多最短路演算法的應用中並不是以距離而是以時間和成本為標準。在這樣的情況下，最短路法也提供了最少時間與最低成本解決法。然而，由於最短路法總是一種最小值法，所以它對於一些以收益為標準的問題並不遠用。 2.在一些應用中，與孤長有關的值可能是負的。例如，在以成本為標準的情況下，負的孤長度值表示負的成本。換句話說，經過這條孤就可獲利。在本節中，我們提到的最短路法僅適用於非負孤長度值的網路。在更高階的課本中討論的演算法可以解決負弧長度值的問題。 **大女 NETWORK DESCRIPTION 7 NODES AND 10 ARCS **火* ARC START NODE 11 2 3 4 5 5 7 8 9 10 1 1 2 2 2 3 4 4 5 6 END NODE ---- 2 3 4 7 5 5 7 6 7 DISTANCE ------⋯ 15 10 3 6 17 4 4 5 2 6 THE SHORTEST ROUTE FROM NODE 1 TO NODE 7 *為女*青*女*女*火女*女火大為女大女女***為女女*女**文*大女太**** START NODE 1 3 5 6 END NODE =-- -- 3 5 6 7 DISTANCE 10 4 2 6 TOTAL DISTANCE 22 團9-12 用管理科學象軟體求解戈費公司最短路問題 9.2 最小支撐樹問題在網路術語中，最小支撐樹問題涉及以用弧總長最小化的方式透過網路線路到達所有網路中的節點。為了更好地理解這個問題，讓我們先看一個區域性電腦中心遇到的通訊系統設計問題。 西南部地區電腦中心為了將一個新的中心電腦與5個通訊衛星使用者相連，需要裝配專用電腦通訊線。電話公司也將裝配這個新的通訊網路。然而，安裝工作的花費很大。為了減少成本，該中心的管理層希望這個新的通訊線路越短越好。儘管中心電腦可以與每個使用者直接聯絡，但如果給一些使用者裝一根直達線，而讓其他使用者透過與那些已與系統相連使用者的連線而進入，則會更加經濟實惠。這個最小通訊系統設計長度的確定就是一個最小支撐樹問題的例子。有關此問題的網路以及可能的可選連線和距離等資料如圖9-13所示。下面介紹一種可用以解決此網路模型問題的方法。
252 資料、模型與決策：管理科學篇 40 50 地區電腦中心 40 30 40 50 各點之間要求的通訊線長度（英里） 圖9-13 地區電腦系統通訊網路最小支撐樹演算法一個具有 N個節點的支撐樹是一套由N-1 條連線每一具有N個節點的網路，1個支撐樹將包節點與其他節點的弧組成的。最小支撐樹提供了這套以最小含N-1條弧。 成本、最短距離或根據一些其他標準構成的弧。用於解決最小支撐樹問題的網路演算法很簡單。此演算法的步驟如下： 第一步：從任意一個節點開始，根據所用標準（例如時間、成本或距離等），與其最近一點相連。 這兩個點被看成是兩相連節點，剩下的為未相連節點。 第二步：確認與某一相連節點距離最近的未相連節點。如果有兩個或兩個以上的節點符合條件，那麼任意選擇一點。然後，把此新節點加入到相連節點的網路中。重複此步驟，直到所有節點被連線為止。 透過在網路上直接做出連線決定，這個網路演算法容易執行。 參考地區電腦中心的通訊網路並且隨意地從節點1開始，我們發現最近一點為節點2，距離為20。 用一條粗線將節點1與節點2相連。該演算法中步驟1的結果如下圖。 40 50 40 30 40 臺0 在該演算法的第二步中，我們發現在未連線的節點中，最接近已連線節點的是節點4，它距離節點 130英里。把節點4加入到相連節點網路中，其結果如下。 40 50 40 30 40
第9童網路模型 253 不斷重複，把最近未連線節點加入網路的已連線部分中，就會得到如圖9-14所示的最小支撐樹。 按照此演算法的步驟，看看你是否也能得到相同的結果。支撐樹的最小長度為組成支撐樹的弧長的總和。因此，電腦中心通訊網路的總距離為110英里。注意，雖然電腦中心網路的弧以臣離來衡量，其他網路模型在衡量弧時可能會依據其他標準，例如成本、時間，等等。在這樣的例子中，最小支撐樹法將會為所用標準確定最佳方案（最小成本、最少時間，等等）。 地區電腦中心問題的電腦解決方案如圖9-15所示。用管理科學家軟體進行最小支撐樹法求解的結果 110英里。 30 圖9-14 地區電腦中心通訊網路——最小支撐樹 ARC -11 2 3 4 5 8 9 10 11 **女* NETWORK DESCRIPTION 6 NODES AND 11 ARCS START NODE ------⋯--… 1 1 EIND NODE -------- 2 3 4 3 6 5 4 5 6 5 6 MINIMAL SPANNING TREE ***女*******火****女女*** END NODE 11-， ---- 2 4 3 6 5 **** DISTANCE •⋯⋯-⋯⋯-- 20 40 30 50 40 40 10 30 30 20 40 START NODE —-- 1 1 4 4 3 TOTAL LENGTH DISTANCE -------- 20 30 10 20 30 110 團 9-15 用管理科學象軟體進行最小支擇樹法求解
254 資料、模型與決策：管理科學篇註釋與評論 1. 專欄9-2 描述了最小支撐樹法有趣的應用。 2. 最小支撐樹法被認為是一種貪婪的演算法，因為我們在每一步都會儘可能選擇最好的方案。在每一步中都遵循此戰略，我們就會得到全部最佳方案。用這種貪婪方法得到最佳方案的案倒是很少的。然而，對於許多問題，此方法是很好的啟發式研究。 專欄9-2 實踐中的管理科學 EDS 設計的通訊網路° 總部設在得克薩斯州普菜諾的 EDS 公司是提供資訊科技服務的全球先鋒。該公司為世界各地的政府和公司提供各種硬體、軟體、通訊及過程解決方案。 EDS 為其許多客戶設計了通訊系統和資訊網路。在一次應用中，一個EDS的客戶要求將用於資訊流通和通訊的64 個地點連線起來。互動傳輸資料，包括聲音、影象及數碼資料必須被容納到不同地點間的資訊流中。該客戶的服務地點包括50個左右的辦公室及在美國大陸地區內的資訊中心，其範圈為康涅狄格一佛羅里達一密歇根一得克薩斯—加利福尼亞，一些附屬點分佈在加拿大、墨西哥、夏成夷和波多黎各。這全部的64 個地點構成了資訊網路的節點。 EDS 公司的任務是找出最節省成本的方式，在整個網路範圍內使客戶的64 個服務點之間彼此相連並與 EDS的資料中心連線起來。網路中的弧線為成對的節點提供通訊連線。在地面通訊線路有效的情況下，這些孤是由光纖電話線路構成的，而在其他情況下，這些弧表示衛星通訊網路。 以成本為標準，EDS 為客戶開發資訊網路是透過解決很小的支撐樹問題實現的，最低成本的網路設計使客戶所有地點之間及其與EDS資料中心的通訊成為可能。 9.3最大流量問題最大流量問題的目標是決定在給定的一段時間內進入或流出網路系統的最大流量（車輛、資訊、流動性，等等）。在此問題中，我們旨在儘可能高效地透過網路的弧傳送流量。其流量受到網路中各種不同弧能量限定的限制。例如，公路的型別在運輸系統中限制車的流量；管道的尺寸在石油運送系統中限制石油流量。弧的最大或是最高限度流量指此弧的流量。儘管我們並不具體指定節點能力，但我們假定其節點流出量與節點流入量相等。 作為最大流量問題的一個示例， 流量：從節點5至節點7 為每小時8 000輛我們來看一下貫通俄亥俄州辛辛那提市的南北向州際公路系統。在高峰時段，南北向車輛流動達到每小時 15 000輛的水平。由於一項要求離開辛辛那提（南方） 暫時性關閉車道以及降低時速限制進入辛辛那提（北方） 的夏季公路保養計劃，交通計劃委員叭會已給出了透過辛辛那提市的替代路線網路。此替代網路包括其他高速公路及城市街道。因為速度限制以及交留 9-16 辛辛那提市的公路網路系統以及流量（1000輛/小時） 通方式的不同，其流量根據所用不同的街道與道路而變化。此網路以及弧的流量如圖9-16所示。 每條弧的流動方向已標明，其流量也在弧上加以標註。注意大多數的道路是單向的。然而，我們 ◎本書作者非常感謝 EDS的 Greg A. Dennis 提供這篇應用性文章。
第9章網路模型 255 也可以在節點2和節點3之間以及節點5和節點6之間找到雙向的道路。在這兩種情況下，在每個方向上的流量是相同的。 對於最大流量問題，我們將向大家展示如何開發一個能夠勝任的轉載模型 （參見第7章）。首先，我們在節點7和節點1之間增加一條弧來表示透過公路系統的總流量。圖9-17展示了更改後的網路圖。此新增弧並沒有流量；實際 の 上我們是希望使此弧的流量最大化。從節點7到節點1這段弧上的流量最大化是與經過辛辛那提市南北向公路系統的汽車數量最大化相同的。 正如我們在第7章所做的，我們按以下方式定義我們的決策變數： 圖9-17 從節點7到節點1的流最代表透過辛辛那提市公路系統的總流量 *。—從節點i到節點j的車流量。 最大化經過公路系統的流量的目標函式為 maX OPTIMAL SOLUTION Objective Function Value = 14.000 Variable X12 X13 X14 X23 X25 X34 X35 ×36 ×32 X46 X56 ×57 X65 X67 ×71 Value --- 對於所有轉運問題，每一條弧都會產生一個變數，每一個節點都會產生一個約束條件。對於每一個節點，其流量約束守恆表示要求流入與流出量必須相等。或者，換一種說法，流出量減去流入量必須等於零。對於節點1，流出量為*12+213+44，流入量為。因此， 節點1的約束條件為 i2 + 14-2=0 其他6個節點的流量約束守恆式以相似形式表示如下： 5.000 6.000 3.000 2.000 3.000 0.000 3.000 5.000 0.000 3.000 0.000 7.000 1.000 7.000 14.000 *2s +%zs -X12 -X32 =0 節點2 *g2 +Xg4 + $gs +33-X3-X23 =0 節點3 Xiss-2y-2g4 =0 節點4 Xisd + Xsy -Xzs -Xgs -Xos =0 節點5 *os +Xgg-Xg6-146-Xs6 =0 節點6 Xinl Sisn-46=0 節點7 為了加強弧的運輸能力，我們需要其他一些限制條件。這14個簡單的上 6一 5一限條件如下： X2≤S X≤6 Xu≤5 *28≤2 22s≤3 4ig2 ≤2 Xs4 ≤3 2gs≤3 *s6 ≤7 *goMS Xs≤1 x's ≤8 圖 9-19 辛辛那提公路系統網路的最大流最模型
256 資料、模型與決策：管理科學篇 26s ≤1 2o≤7 注意，僅有一條弧沒有流量，就是我們所增加的從節點！到節點7的那條弧。 用管理科學家軟體對這個有15個變數、21個約束條件的線性規劃問題進行求解，結果如圖9-18 所示。我們注意到最佳方案的值為14。此結果意味著公路系統的最大流量為14000輛。圖9-19展示了車流是怎樣穿越原有公路網路的。例如，我們注意到，在節點1和節點2之間每小時有5000輛車透過，在節點2和節點3之間每小時有2000輛車透過，等等。 最大流量分析的結果表明，計劃的公路網路系統並不能處理高峰期每小時15 000輛的流量。交通規劃者們將不得不擴充套件網路系統並且增加現有弧的流量，否則他們將面臨嚴重的交通問題。如果網路被擴充套件或是改善，那麼最大流量分析將會決定已提高流量的程度。 註釋與評論 1.如果不使用那條節點1與節點7之間新增的弧，本節中最大流量問題也是可以解決的，只不過計算方法稍有不同。該可選方法就是最大化進入節點7（xsg +x0）的流量，同時對降低節點7和節點 1 流量的限制。然而，本節中用到的模型在實踐中很常用。 2. 網路模型可被用於描述很多管理科學問題。但不幸的是，沒有一個網路解決演算法可用於解決所有網路問題。為了選擇正確且專門的解決演算法，確認將要被模擬問題的具體型別是重要的。 本章小結在本章中，我們將網路模型使用的討論擴充套件到管理決策制定之中。我們介紹了最短路、最小支撐樹以及最大流量問題，並且介紹了對於最短路和最小支撐樹問題的具體解決演算法。我們展示瞭如何像對待轉運問題一樣來對最大流量問題建模，並用線性規劃法求解。解決問題的網路方法成功的關鍵在於一個問題如何以網路模型來表示。一些網路模型唾手可得，但另一些問題可能需要很多創造力去開發恰當的網路模型。無論如何，一旦網路表示被建立，具體解決此同題的方法就可以獲得。 專業術語 shortest route 最短路網路中兩節點之間的最短路。 minimal spanning tree 最小支撐樹支撐樹的最小長度。 spanning free 支擦樹由N-1條弧組成，網路中每一個節點都與其他節點相連，N 表示節點的數量。 maximal flow 最大流量在給定時間內流人或流出網路系統的最大流量值。 flow capacity 流量網路中一條弧的最大流量。在一個方向上的流量可能並不等於在其反方向上的流量。 問題 2. 對於戈曼建築公司的問題（見圖9-1），如果我們現在假定節點7是公司的倉庫和物料中心。每天兒次往返都會發生在節點7和其他節點或建築工地之間。把節點7看做是起始節點，在網路中找到從此節點到其他節點的最短路。 4. 在下面的網路圖中找出從節點1到節點8的最短路。
第9章網路模型 257 6.摩根運輸公司在包括4個州的範圍內，即芝加哥和10個其他城市之間經營一項特的快速投遞服務。 當摩根公司收到服務請求時，它會儘可能快地派遣一輛車從芝加哥趕往所需服務城市。對把快速服務和最低往返成本作為目標的摩根公司來說，所派車輛選擇從芝加哥到所需服務城市的最短路尤其重要。 假定下面標有距離的網路圖是表示此問題的公路網路，請找到從芝加哥到其他所有城市的最短路。 70 40 30 60 芝加問 20 30 A0 40 60 40 8.韋斯曼糖果公司生產幾種糖果製品。公司的貨車直接將貨物送到零售商手中。當生意小時，卡車司機們在運送貨物時可以自由決定選擇什麼樣的路線到達零售地點。然而，當生意很大時，運輸與投遞成本會變得非常高。為了提高投遞效率，韋斯曼公司的管理者們決定找出零售點之間的最短路。例如，下面的網路圖展示了從節點1到節點11之間可能被選擇的路線。現在，請找出從節點1到節點11的最短路。 10 10 10. 俄亥銀州近來購買了一塊土地用於建設一個公園。公園設計者已經為住宿地點、茅屋、野餐圓、船塢和景點確定了具體位置。這些位置如下圖網路中的節點所示。網路上的弧表示的是公園中可能的路線連線。如
258 資料、模型與決策：管理科學篇 12. 在大型的肥皂工廠中，質檢員會從不同的生產區中選取不同產品的樣品帶到實驗室中進行分析。檢查過程是緩慢的，質檢員要花費大量的時間把樣品從生產區帶到實驗室。公司正考慮建立一個可以在生產區與實驗室之間運送樣品的管道運輸系統。下面的網路圖展示了選取樣品的實驗室和生產區的地點。圖中的弧表示管道運輸系統的可選線路。可以使所有要選送樣品的生產區到實驗室的最短管道運輸系統應怎樣佈局？ 實驗室 14. 地下光纜公司剛剛接到通知，允許其在田納西州孟菲斯市郊區提供有線電視服務。下面網路中的節點展示了公司電須線所必須要達到的分支點。網路弧上標出了分支點之間相睡的英里數。確定可以使該公司到達所有分支點的纜線的最小長度。 ~ 16.如果問題15中所說的奧爾巴尼公路系統改變了其流量，如下圖所示。那麼每小時透過此係統的最大流量為多少？為了達到最大流量，每小時應有多少輛車透過每條公路？ 4 4 2 2 18.高價油公司擁有一個從採集地到幾個儲存點之間傳送石油的管道網路系統。其部分網路系統如下圖所示：