177 其原先的右端值分別為6，=550，b=700，b，=200。 8.計算b，的可行範圍。 b.計算6的可行範圍。？計算6；的可行範圍。 16.回憶愛尼斯公司的投資問題（參見第2章的問題37）。設 x—股票市場的投資量； x——貨幣市場的投資量。 匯出如下模型： min S.t. &x+ 3x2 5Ox； + 100x ≤ 1200 000 5x，+ 4x2≥ 60 000 1x2≥ 3000 51½2≥0 總風險可利用的資金最年收入貨幣市場的敏大投入量日，用單純形法解這個問題。 b.最優解的值是衡量證券風險程度的尺度。增加對每年收入的要求會對證券組合的風險產生什麼影響？ c.求b的可行範圍。 d.如果對每年收入的要求從60 000美元增加到65 000美元，那麼最優解和它的值會如何變化？ e.如果對股票市場資金風險指數的評定從8增加到9，那麼最優解和它的值如何變化？ 18. 找到下列線性規劃的對偶問題： min 2 800xj + 6 000x2+ 1 200xg s.t. 15x，+1582+ 1x≥5 4xg + 8x ≥5 12%1 + 8x ≥ 24 X1，22： ≥0 20. 光電化學藥品公司生產兩種相片沖洗液，每加侖的成本為1美元。令 x，—1號產品的加侖數； *—2號產品的加侖數。 光電化學藥品公司的管理層規定，必須至少生產30加侖的1號產品和20加侖的2號產品。同時還規定， 生產過程中必須至少使用80磅的某種容易腐爛的原材料。這一問題的線性規劃模型如下： min lxy + lxz S.t. Ix ≥30 1×2 ≥20 1x+28≥80 X122≥0 1號產品的最小量 2號產品的最小量原材料的最小呈 8.列出對偶問題。 b.求解對偶問題。用對偶解說明最優生產計劃安排為x， =30，x=25。 c.第三個約束條件包括管理層規定目前要使用80磅的某種容易腐爛的原材料。然而，在得知最優解要求多生產5單位的2號產品後，管理層開始重新考慮關於原材料的要求。特別是，如果這個約束條件被放松，你需要確定實際成本。如果只需要使用79磅原材料，請用對偶變數表示成本的變化。 22. 有一個銷售代表銷售兩種產品。他想算出下月促銷每種產品所需要撥打的銷售電話。根據以往經驗，1號產品每打一個電話有10美元的佣金，2號產品每打一個電話有5美元的佣金。公司規定每個月每種產品至少要撥打20個電話，至多不能超過100 個電話。此外，對於1號產品，銷售代表的每個電話大約為3個小時，2號產品則為1個小時。如果下個月共有175小時的銷售時間，那麼要想使佣金達到最大化，兩種產
178 資料、模型與決策：管理科學箱品應分別撥打多少個電話？ a.為此向題建立一個線性規劃。 b.建立並解決對偶問題。 c.用對偶問題的最終單純形表決定應撥打銷售電話的最優數量。佣金的最大數為多少？ d. 解釋對偶變數的值。 24.假設一個有3個變數的線性規劃問題的最優解為x， =10，*2=30， 掉了以下兩個約束條件： 6r +4%-1g≤170 ¼×+ 1×2 ≥ 25 如果可能的話，求出新的最優解。如果不可能的話，請說明原因。 =15。後來發現，在建立模型時，漏第7章運輸、指派與轉運問題運輸、指派與轉運問題屬於線性規劃問題中的特分類，常被人們稱為網路流量問題。因為大量的運輸、指派和轉運模型被運用子現實生活，所以我們把這一章獨立出來。美國海軍陸戰隊在發生世界性危機事件和戰爭時運用運輸模型來派遺部隊。Heery 國際公司運用指派模型來分配建築經理到各個專案中去。寶潔公司將轉運模型作為它重新設計北美產品配送系統的一個工具。網路流量問題中的數學結構的特性，甚至包含成千上萬個變數的大型問題，也可以用計算機在幾秒鐘內計算出來。 我們透過闡述一個特殊領域應用中的每個問題介紹網路流量問題。首先我們設計出一個圖表的描述方式，稱之為網路圖，然後看看每個問題是怎麼被構成和如何當做線性規劃問題來解決的。 第7.1~7.4 節都是一個對運輸、指派與轉運問題以應用為導向的介紹，第7.5 節和第7.6節包含的特殊目標的演算法部分可選擇閱讀，即使跳過也不影響閱讀的連續性。 7. 1 運輸問題：網路模型與線性規劃模型運輸問題經常出現在計劃貨物配送和從某些供給地區到達某些需求地區之同的服務中，特別是每個供給地區（起點）的貨物可獲得量是有限的，每個需求地區（目的地）的貨物需求量是已知的。運輸問題中最常用的目標是要使貨物從起點到目的地的運輸成本最低。 讓我們透過考慮福斯特發電機公司面臨的這個運輸起點加工廠問題來進行介紹。這個問題包括從3個加工廠運輸一種 1 克利夫蘭產品到4個分銷中心。福斯特發電機公司在俄亥俄州的 2 貝德福德克利夫蘭、印第安納州的貝德福德和賓夕法尼亞州的約 3 約克克有3個加工廠，下3個月的計劃期內的這個特殊型號 3個月的生產能力（單位） 5000 6000 2 500 總計：13 500 的發電機的生產能力如下： 公司透過坐落在波士頓、芝加哥、聖路易斯和萊剋星頓的4個分銷中心來分銷這種發電機：每個分銷中心3個月的需求預測如下：
180 資料、模型與決策：管理科學篇目的地 I 2 加工廠波士頓芝加哥 3個月的生產能力（單位） 6 000 4 000 目的地 3 4 加工廠聖路易斯藜剋星頓 3個月的生產能力（單位） 2000 1 500 總計：13 500 管理層想知道從每個加工廠運輸到分銷中心的產品運輸量應為多少。圖7-1 顯示了12 分銷中心（目的地節點） 條福斯特公司可以用的配送路線。這種圖稱為單位運輸成本網路圖；圓圈表示節點，連線節點的線條表示工廠（起點節點） 6 000 波士頓弧。每個起點和目的地都由節點表示，每個可能的運輸路線都由弧表示。供給量寫在起始節 5 000 點邊上，需求量寫在每個目的地節點邊上。從起始節點到目的地節點之間運輸的貨物數量表示了這個網路的流量。注意：直接流量（從芝加概 4-000 起點到終點）是用帶箭頭的線條表示的。 對應這個福斯特公司的運輸問題的目標是 6000 貝德福德要確定使用哪些路線以及每條線路上的流量是多少時，使得總的運輸成本最低。每條線路單 2 000 位產品的運輸費用在表7-1中給定並在圖7-1 中的每條弧上標明。 線性規劃模型可以用來解決這類運輸問 2 500 約克題，我們將用雙下標決策變數來描述變數，用 *，來表示從起點節點1（克利夫蘭）到目的地 1500 節點1（波士頓）之間的運輸量；用x12來表示從起點節點1（克利夫蘭）到目的地節點2 （芝加哥）之間的運輸量，其他類似。一般情供給分銷路線（弧） 需求祝下，一個有m個起點和7個目的地的運輸問題的決策變數常被表示成以下形式： 圖7-1 福斯特公司發電機運輸問題的網路團 *—從起點i到目的地j之間的運輸量。 表7-1 福斯特公司發電機運輸問題的單位運輸成本其中，i=1，2,3， …，m, j=1, 2,3， 目的地因為運輸問題的目標是最小化運輸成本， 起點波士頓我們可以使用表7-1 中的成本資料或者圖 7-1 芝加酐聖路易斯萊剋星頓中弧上的資料來構造如下所示的成本表示式： 克利夫蘭 3 2 7 6 貝德福德 7 5 2 3 從克利夫蘭出運的所有運輸成本=3%1+ 約克 2 s 4 5 2%12 +7413 +6x4 從貝德福德出運的所有運輸成本=7x21+5*22 +2*2+ 3%24 從約克出運的所有運輸成本=2231+5x32 +4xss +Sxs4 這些表示式加起來的總和就是福斯特公司發電機運輸總成本的目標函式。 每個起點的供給能力和目的地的特定需求量是有限的，所以運輸問題需要有約束條件。我們先考慮供給約束條件，克利夫蘭工廠的生產能力是5000單位，從克利夫蘭出發運出的所有運輸成本=X1！ +X12 +413 +x14，所以克利夫蘭的供給約束為 Xi +212 +213 +214 ≤5 000 克利夫蘭供給福斯特公司運輸問題有3個起點（工廠），所以這個運輸模型就有3個供給約束條件。貝德福德工廠的6000單位的生產能力，約克工廠的2500單位的生產能力決定了下面兩個供給約束條件：
第7章運輸、指派與轉運問題 181 X21 +X22 +X2s +$a≤6 000 貝德福德供紿 X31 + X32 +$33 +834≤2 500 約克供給由於有4個分銷終點，所以要有4個需求約束來確保終點需求被滿足： X.11+*21+231=6 000 波士頓需求 Xi2 +#22 +132=4 000 芝加哥需求 X13 + 22s+233=2 000 聖路易斯需求 Xie +X24 +234 =1 500 萊剋星頓需求聯合這些目標函式和約束條件構成一個線性規劃模型，這個福斯特公司運輸問題是一個有12個變數，7個約束的線性規劃模型： min 3xil + 2x12 + 7xi3 + 6xja + 7x21 + 5x22 + 2x23 + 3824 + 2x31 + 5X32 + 4xss + 5t34 X2l + Xz+ Xzs + X24 + X2l X2 + Xz2 Xis + X23 + 231 + X32 + X33 X14 + X24 ≤5000 ≤600 232+ 23a + Xs4 ≤2500 =6 000 =4 000 =2 000 + X34 =1 500 2，≥0，其中，i=1，2,3；j=1,2,3,4。 比較線性規劃模型與圖7-1 中的網路，會發現幾個觀察值。所有線性規劃模型所需的資訊都能在目標函式值= 39500.000 變數值 ----- 降低的成本 •---------- ×11 3500.000 —：000 ×12 1500.000 0.000 ×13 0.000 8.000 ×14 0.000 6.000 ×21 0.000 1.000 ×22 2500.000 0.000 ×23 2000.000 0.000 ×24 1500.000 0.000 ×31 2500.000 0.000 ×32 0.000 4.000 ×33 0.000 6.000 X34 0.000 6.000 圖7-2 使用普理科學寂軟體解決福斯特公司發電機運輸問題網路圖中找到，每個節點需要一個約束條件， 表7-2 福斯特公司發電機運輸問題的最優解每一條弧需要一個變數。對應的每個起點節點路線運輸量單位成本出發的每條弧上的變數值之和必須小於或者等總成本從到於這個起點節點的供給。對應的去往每個目的克利夫蘭波士頓 3 500 $3 $10 500 地節點的弧上的變數值之和必須等於這個目的克利夫蘭芝加哥 1500 2 3000 地節點的需求。 貝德福德芝加哥 2 500 5 12 500 貝褣福德聖路易斯 2000 2 4000 我們利用管理科學家軟體的線性規劃模型貝德福𢔓 萊剋星頓 1500 4 500 解決了福斯特公司發電機的問題。計算機的計約克波士梗 2500 2 5000 算結果（見圖7-2）顯示最小的總運輸成本為 $39 500
182 資料、模型與決策：管理科學篇 39 500美元。決策變數的值表示了每條線路運輸的最優運輸量。例如，x =3 500，意味著從克利夫蘭到芝加哥這條線路上應當運輸3500單位的發電機，*12 =1 500 意味著應當將1500單位的發電機從克利夫蘭運送到芝加哥。決策變數的其他值指明瞭剩餘的運輸數量和路線。表7-2是在最低運輸成本下的運輸計劃表，圖7-3總結了網路圖的最優解。 分銷中心（目的地節點） 6000 工廠（起點節點） 波士頓 5 000 克利夫蘭 3500 500 芝加霰 4 000 6 000 貝笱襭鏈 2 000 聖路易斯 2000 2 500 米克星額 1500 供給圖7-3 分銷路線（弧）和運輸量福斯特公司發電機運輸問題的最優解需求 7.1.1 問題的變化福斯特公司發電機問題闡述了基本的運輸模型的應用，基本運輸模型的變化可能有以下幾種情況： 1.總供給不等於總需求。 2. 最大化目標函式。 3.路線容量或者路線最小量。 4. 不可接受的路線。 只要對線性規劃模型進行輕微修改就能很容易地適應這些情況了。 總供給不等於總需求通常情況下總供給不等於總需求。如果總供給超過總需求，線性規劃模型不需要進行修改。多餘的供給總量線上性規劃解決方案中表現為鬆弛。而任何起點的鬆弛都可以被理解為未使用的供給或者未從起點運輸的貨物數量。 如果總供給小於總需求，運輸問題的線性規劃模型沒有可行解，在這種情況下，我們可以對網路圖做如下修改：增加一個虛擬起點，這個起點的供給恰好等於不被滿足的需求。增加從這個虛擬起點到每個終點的弧，線性規劃模型就會有可行的解決方法了。我們規定每條從虛擬起點出發的弧上單位第7章運輸、指派與轉運問題 183 的運輸成本為零。這樣，經過修改的問題的最優解將會代表實際運輸的貨物的運輸成本（從虛擬起點出發的線路沒有實際運輸發生）。當我們執行這個最優解時，目的地節點處顯示的運輸量為這個節點需求不被滿足的貨物短缺量。 最大化目標函式在某些運輸問題中，目標是要找到最大化利潤或者收人的解決方案。這種情況下我們只要把單位利潤或者收人作為一個係數列入目標函式中，簡單地把最小改成最大，約束條件不變，就可求得線性規劃的最大值而不是最小值。 路線容量和/或路線最小量運輸問題的線性規劃模型也能夠包含一條或者更多的路線容量或者最小數量問題。例如，假設在福斯特公司發電機問題中，約克一波士頓路線（起點3到終點1）因為其常規的運輸模式中有限空間的限制，只有1000單位的運輸能力。用x；表示約克一波士頓線路的運輸量，那麼這條線路的運輸能力約束為： xs1 ≤1 000 類似地，路線的最小量也可以確定下來。例如， *22 ≥2000 這個約束條件保證了最優解中保留先前承諾的最小2000單位的訂單。 不可接受的路線最後一種情況，構建從每一個起點到終點的路線並不都是可能的。為了處理這種情況，我們只需要簡單地去除網路圖中相關的弧和線性規劃模型中相關的變數。例如，如果克利夫蘭一聖路易斯之間的路線是不可接受的或者是不可用的，那麼在圖7-1 中，從克利夫蘭到聖路易斯之間的這條弧應當被刪除。線性規劃模型中的變數x也應當被刪除。解決這個有11 個變數和7個約束條件的線性規劃模型得出的最優解的同時，也保證了克利夫蘭一聖路易斯之間的路線不被使用。 7.1.2 運輸問題的一般線性規劃模型為了表示這個運輸問題的一般線性規劃模型，我們將要用到下列概念： —起點的下標，i=1，2， ⋯，m； 一終點的下標，j=1，2，⋯，n； 一起點i到終點j之間的運輸量； 一起點i到終點j之間的單位運輸成本； 一起點；的供應量或者生產能力； d，—終點j的需求量。 m個起點，n個終點的運輸問題的線性規劃的一般模型如下： min =1/=1 s.t. ASi i= 1,2•m 供給 Zv=d j= 1,2，••，n 需求 i=1 Xy≥0，對所有j 就如先前我們提到的，可以在約束里加一個x， ≤Ly。如果從起點；到終點j之間的運輸容量為L』， 一個包含了這種型別的約束條件的運輸問題就稱為有容量限制的運輸問題。類似地，如果起點i到終點j之間必須處理的運輸容量最小為 Mu，那麼我們在約束條件里加上最小運輸容量約束*≥Mg。 註釋與評論 1. 實際生活中遇到的運輸問題往往需要大的線性規則模型來處理，有100 個起點和100個終，點的
184 資料、模型與決策：管理科學篇運輸問題並不少見，這樣的問題將包含100 ×100=10 000 個變數。 2. 為了處理帶有不可用路線的情形，我們可以從網路圖中刪除相應的弧，並從線性規劃模型中刪除相對應的變數。另外一種常用的方法就是賦予這些不可用路線以非常高的目標函式成本系數。如果問題已經構建好了，另外一種選擇就是給模型增加一個約東條件，這個約來條件把你想刪除的變數設置成零。 3.如果所有的需求和供給都是整數的話，這個運輸模型的決策變數的最優解將由整數值構成。這是由線性規劃模型中的特殊數學結構決定的，且每個變數只在一個供給約束和一個需求約束條件中出現，所有約東條件方程式中的係數都為1或者0。 4.雖然很多運輸問題都是求解各個節點間的運輸費用最小，但是運輸模型還有很多其他應用。專欄7-1闡述的就是利用一個運輸模型把海軍陸戰隊的軍官派遣到適當的職位。 專欄7-1 實踐中的管理科學海軍陸戰隊的調濾美國海軍陸戰隊已經建立了一個網路模型，以備在世界危機或者戰爭中用來調遣軍官。這個問題要解決的就是儘可能快地把每個軍官指派到合適的位置（職位指派），設計出來解決這個運輸問題的模型跟這一章我們討論過的很相似，只是這個模型更大。起點節點或者供應節點代表現有的軍官，目標節點或者需求節點代表的是職位。實際執行時有40000 個軍官和25000 個職位。如果所有軍官一職位的連線弧都是可行的，那麼這個運輸問題就有1億條孤。為了減小問題的規模，相似條件的軍官可以彙整合一個供應節點，相似的職位可以彙整合一個需求節點。用這個方法將不可行的弧刪除，海軍陸戰隊在10秒鐘之內就透過一臺個人電腦解決了包含27000個軍官和10000個工作職位的指派問題。 結果是令人滿意的：合適級別和工作資歷的軍官都被派遣到了需要的工作崗位上。遇到危機時， 如果能夠獲得並使用這套系統的話，它能夠決定我們將對此做出適當的反應還是將去面對一場災難。 先前的系統需要2~4天來產生這麼一個完整的分配計劃且這個計劃的軍官資歷和職位需求之間的四配度比較低。海軍陸戰隊利用現在這個分配模型提高了它在和平時期的運作能力。 資料來源：D. O.Bausch, G.C. Brown, D. R. Hundley, S. H. Rapp, and R. E. Rosenthal， "Mobilizing Marine Corpe Officers，” Interfaces （July/ August 1991）：26-38. 7.2 指派問題：網路模型與線性規劃模型很多決策過程中都會產生指派問題；典型的指派問題有：將工作分配給機器，對代理分配任務， 將銷售人員分配給銷售區域，將合同分配給投標人，等等。指派問題中一個很明顯的特徵是一個代理只分配給一個任務，僅僅一個任務，特別是我們尋找一組能夠最最佳化所設立的目標的分配，例如成本最小、時間最短或者利潤最大。 為了闡述指派問題，讓我們來看看福爾市場調查公司的案例，這個公司剛剛從3個新客戶那裡獲得市場調查專案。公司面臨著給每一個客戶分配一個專案負責人的任務。最近，有3個專案負責人手上沒有其他的任務，可以被分配。福爾的管理層意識到完成每個市場調研的時間取決於專案負責人的經驗和能力。這3個專案具有相似的表7-3 福爾公司指派問題的預計完成專案時間 （單位：天） 優先順序，公司希望分配的專案負責人完成這專案負責人 3個專案所需的總時間最短。如果每個客戶只需要一個專案負責人，那麼怎麼進行分配呢？ 為了解決這個指派問題，福爾的管理層必須首先考慮所有可能的負責人一客戶的分配 1. 特瑞 2. 卡爾 3，五克孟罐 1 10 9 6 客戶（任務） 2 15 18 14 3 5 3
第7章運輸、指派與轉運問題 185 方法，然後預測相對應的完成專案所需的時間。3個專案負責人和3個客戶可以產生9種分配方案。 表7-3總結了各種可能的分配方案和預測出來的完成專案所需時間。 圖7-4是福爾公司指派問題的一個網路專案負責人圖。節點對應著專案負責人和客戶，弧代表項 （起始節點） 完成任務所需天數客戶 （終點節點） 目負責人一客戶之間的可能的分配。每個起點節點的供給和終點節點的需求都是1；把一個 10 稱瓏專案負責人指派給一個客戶的成本是這個負責人完成客戶的市場調研任務所需的時間。注意指派問題的網路圖（圖7-4）和運輸問題的網絡圖（7-1）之間的相似性。這個指派問題其實就是運輸問題的一個特殊情形，其中所有的供 18 給和需求量都是1，每條弧的運輸量不是1就 I 是0。 因為這個指派問題就是運輸問題的一個特殊例項，那麼可以設計出一個線性規劃模型。 我們仍然需要每個節點的約束條件和每條弧上 1 c 3 客） 的變數。就像在運輸模型中那樣，我們使用雙邁克孟機下標決策變數：*表示負責人1（特瑞）是否分配給客戶1，x12表示負責人1（特瑞）是否分配給客戶2，其他類似。因此，福爾公司指供給可能的指派（弧） 需求派問題的決策變數為： *，=｛，如果現目負責人；截分配給客戶） 圖7-4 福爾公司指派問題的網路模型 10，其他情況這裡，i=1，2,3；j=1,2,3。 使用表7-3的符號和完成專案時間的資料，我們得出完成專案時間的表示式： 特瑞完成任務所需的天數=10x+15x,2+9x13 卡爾完成任務所需的天數=9x21+ 18*22 + 5825 邁克孟德完成任務所需的天數=6x31+14x32 +3233 3個負責人的完成專案時間之和就是完成3項任務所需的總天數，因此，目標函式如下： min 10xu + 15x2 +9xig +9x21 + 18xz2 + 5x23 + 6xi31 + 14x32 + 3$33 這個指派問題的約束條件是為了保證每個負責人能夠被至多分配給一個客戶且每個客戶必須有一個分配過來的負責人。這些約束條件可以寫成以下形式： 加1+X12+X13≤1 對特瑞的指派 X2i +X22 +X2s≤1 對卡爾的指派 Xgi +X32 +Xgs≤l 對邁克孟德的指派 Xl+X21 +X3=1 客戶1 X12+X22+X32=1 客戶2 X13 +X23 +X3s=1 客戶3 注意，一個約束條件對應圖7-4中的一個節點。 把目標函式和約束條件組合在一起形成一個模型，就是下面的具有9個變數和6個約東條件的福爾公司指派問題的線性規劃模型： min 10xi + 15xiz + 9xis + 9xzl + 18x22 + 5x2s + 6rsi + 14xsz + 3x33 S.t. X1+X12+ X13 ≤1
186 資料、模型與決策：管理科學箱 Xal + Xzt Xzs + X21 + Xz2 + 1g1 + ≤1 Xgz+Xs1 =1 Xsz = 1 + Xg=1 xiz + X23 *，≥0，其中，i=1，2，3；j=1，2,3。 圖7-5是這個模型的計算機計算結果。特瑞被指派給了客戶2（xn2=1），卡爾被指派給了客戶3 （x:s=1），邁克孟德被指派給了客戶1（x1=1）。總的專案完成時間為26天。這個解列在表7-4中。 目標函式值= 變數 ×11 ×12 ×13 ×21 ×22 ×23 ×31 X32 ×33 26.000 值 ------ --- 0.000 1.000 0.000 0.000 0.000 1.000 1.000 0.000 0.000 成本的減少量 --- 0.000 0.000 3.000 0.000 4.000 0.000 0.000 3.000 1.000 圈7-5 用管理科學寂軟體解決福爾公司指派問願專案負責人特瑠卡爾邁克盂德衰7-4 福爾公司問題的最優專案負責人指派指派客戶 2 3 1 天 15 s 6 總計 26 7.2.1 問題的變化因為指派問題可以被看做一個運輸問題的特例，那麼指派問題中可能出現的變化就和運輸問題中出現的變化相似，所以，我們能夠處理下面的情形： 1.總的代理（供給）數不等於總的任務（需求）數。 2. 目標函式最大化。 3. 不可接受的分配。 代理數不等於任務數時的情形和運輸問題中總供給不等於總需求時類似。線上性規劃模型中，如果代理數多於任務的數量，多餘的代理將不被指派。如果任務數多於代理數，那麼線性規劃模型就沒有可行的解決方案。在這種情況下，一種簡單的修正方法就是加人足夠多的虛擬代理，使代理數等於任務數。比如說，在福爾公司問題中，我們有5個客戶（任務）和3個專案負責人（代理）。在加入兩個康擬的專案負責人後，我們可以建立一個新的專案負責人與客戶數量相等的指派問題。虛擬專案負責人的指派的目標函式係數設為0，這樣最優解的值就代表進行指派的實際所需天數（虛擬負責人 -
第7章運輸、指派與轉運問題 187 的指派是實際上不進行的）。 如果指派的備選方案是根據收人或者利潤而不是時間或者成本進行評價的，那麼線性規劃模型可以處理成最大化而不是最小化問題。另外，如果一個或者更多的指派是不可接受的，那麼相對應的決策變數應當從線性規劃模型中刪除。這種情況可能發生，例如，如果其中一個代理沒有這個任務或者更多工所需的必要經驗。 7.2.2 指派問題的一般線性規劃模型一般指派問題包括 n個代理和n個任務。如果我們令x=1或者0來表示代理；是否分配給任務 j，如果c，表示把代理；分配給任務j所花的成本，我們可以把一般分配模型寫成如下形式： min i j=1 S.t. i=1,2，m代理 j1 Zx=1 j=1,2，n任務 xy≥0，對所有的和j 7.2.3 多種指派在本節一開始，我們就指出指派問題有一個顯著的特徵，一個代理只能被指派給一個任務。對於一個代理可以被配給兩個或者更多個任務的廣義指派問題，我們可以對線性規劃模型進行簡單修改。 例如，假設福爾公司問題中特瑞能夠被指派給兩個客戶；在這種情況下，代表特瑞指派的約束條件就為2+X12+218≤2。一般情況下，如果a，表示代理；能夠被指派的任務的最高上限，那麼我們把代理約束寫成如下形式： A ≤ Q.，i = 1,2，'，m 因此，我們發現把指派問題像線性規劃模型一樣構建和求解的一個好處就是，特殊情形，例如涉及多種指派的情況，比較容易處理。 註釋與評論 1.如前所述，指派模型是一種特殊的運輸模型。我們在前一節結尾處的註釋與評論中提到，運輸問題的最優解是由決策變數的整數值組成的，因為需求和供給都是整數。而在這個指派問題中，所有的需求和供給相等，都汐1；因此，這個問題的最優解也是整數值，且不是為0就是為1。 2. 將解決多種指派的方法與虛擬代理的概念組合起來，得到解決任務數超過代理人數情況的另外一種方法。也就是，我們加入一個虛擬代理，並賦予這個虛擬代理多種指派的能力。此虛擬代理能夠被指派的任務數量可以處理成等於任務數與實際代理數的差額。 3. 專欄7-2介紹瞭如何把管理人員指派給建設專案，這個應用中包括了多種指派。 專欄7-2 實踐中的管理科學 Heery Interational Heery Interational與田納西州等多方客戶簽訂了各種建設專案的合同，包括高等教育設施、旅館和停車場。在任何一個時間點上，Heery 都有100多個正在進行的專案。每個專案都必須單獨指派一
188 資料、模型與決策：管理科學篇個主管。如果有7個主管可以指派的話，有多於700=7×100種可能的指派。在外來顧問的協助下， Heery Interational 設計出了一個給專案指派建築主管的數學模型。 Heery設計出的指派模型對於每個主管和專案組合使用0/1決策變數，就如前邊討論過的指派問題一樣。指派主管的目標是為了平衡每個主管之間的工作負擔，在同一個時間內最小化從主管案到建築專案的工作地，點之間的交通成本。由此得出了關於每個可能的指派目標函式係數：將專案強度（一個關於專案預算大小的函式）和從主管人員的家到建築工地的交通距離組合起來。目標函教要求所有的指派變數的係數總和最小。 由於建築專案多於主管人數，所以必須考慮對包含了多種指派的標準指派問題進行修改。有兩組約束條件，一組要求每個專案有一個並只有一個主管；另一組透過限制所有被指派專案的總的可接受強廣來限制每個主管接到的指派的任務量。 Heery International 實行了這個指派模型，產生了很好的效果。據副總裁Emory F. Redden 稱：“最最佳化模型對於我們指派主管到專案很有幫助，我們對於納什維爾分部的指派就很滿意，我們希望將這種模型應用於我們的亞特蘭大及 Heery集團的每一個分部。” 資料來源：Larry J. LeBlanc, Dale Randels, Jr.， and T. K. Swann， " Heery International’s Spreadsheet Optimization Model for Assigning Managers to Conetruction Projects， " Interfaces （November/December 2000）： 95-106. 7.3 轉運問題：網路圖與線性規劃模型轉運問題是運輸問題的擴充套件，其中中間節點代表轉運節點，加人這個節點的目的是指代地點位置，例如倉庫。在更為普遍的指派問題型別中，出貨發生在3個一般型別節點的任意兩個之間。這3 種節點為：起點節點、轉運節點和終點節點。例如，轉運問題允許貨物從起點節點運到轉運節點，再運到終點節點，從一個起點節點運到另一個起點節點，或者是從一個終點節點運到另一個終點節點或者直接從起點節點運到終點節點。 就如在運輸問題中的一樣，每個起點節點的可得的供給是有限的，每個終點節點的需求也是確定的。在轉運問題中，目標是在滿足終點節點需求的基礎上，確定網路圖中每條弧上運輸多少單位，才能使得總的運輸成本最低。 讓我們看看珊恩電子所面臨的轉運問題。瑞恩電子是一家電子公司，其生產線分別位於丹佛和亞特蘭大，在每條生產線上生產出來的商品都可以被運送到公司在堪薩斯城或者是路易斯維爾地區的倉庫中，公司把這些地區的倉庫中的商品發給底特律、邁阿密、達拉斯和新奧爾良的零售商。表7-5是每條發貨線路上單位商品的運輸成本，圖7-6顯示了網路模型中的每條弧以及這個問題的關鍵特徵。 注：每個起點節點的供給量和每個終點節點的需求量都在其旁邊標明。節點1，2是起點節點，3，4 是轉運節點，S，6，7，8是目標節點。 工廠表7-5 瑞思電子轉運問題的運輸成本倉庫丹佛亞特蘭大堪薩斯城 2 3 路鬍斯埲爾 3 暈售商堪薩斯城路易斯維爾鹿禱律 2 4 邁阿密 6 4 達拉斯 3 6 新奧爾庾 6 5
第7童運輸、指派與轉運問題 189 零售商（終點節點） 底狩律 200 600 T廠（起點節點） 丹佛倉庫（轉運節點） 3 堪薩斯城邁阿密 150 350 400 亞特蘭大好斯灘 6 S 達鉸斯 300 新奧爾糕供給分銷路線（弧） 需求圖7-6 瑞惠電子轉運問題的網路圈對於運輸和指派問題，我們可以構建一個線性規劃模型；對網路圖表示的轉運問題，我們也可以構建一個線性規劃模型。同樣，我們也需要給每一個節點和每條弧上的變數一個約束。令xy表示從節點i運輸到節點j的運輸量。例如，“表示從節點丹佛運了x個單位的商品到堪薩斯城的倉庫裡，*4 表示從節點丹佛運了x4個單位的商品到路易斯維爾的倉庫裡，其他的類似。如果丹佛能供給600單位，那麼從丹佛運出的商品就必須小於或者等於600。數學上的供給約束表示式可以寫成： 21+44≤600 類似地，對亞特蘭大工廠的供給約束如下： *23 +%24 ≤400 現在，我們考慮如何確定兩個轉運節點的約束表示式。對節點了（堪薩斯城的倉庫）來說，我們必須確保從這個節點運出的貨物必須等於運人這個節點的。因為節點3的運出量 =835 +X36 +X3n + 238 且節點3的運人量=X13+X28 所以我們得到 23s +X36 + X3 + 438 = X1s + 423 把所有變數都移到等式左邊，那麼節點3對應的約束表示式為： -Xia -X2s +23s +$36 +$37 +$38 =0 同樣，節點4對應的約束表示式為： 一X4-$24 +84s +$46 +Xa7 +148=0 為了獲得目標節點的約束條件，我們認識到對運輸到每個目標節點的商品總量應當等於該節點的需求。例如，為了滿足節點5上的200個單位的需求（底特律零售商），我們將這個約束表示如下： *gs + &as =200 同樣，對節點6，7，8，我們有如下約束表示式：
190 資料、樓型與決策：管理科學篇 2so +4a6 =150 Xiga +4an =350 X38 +4 8 =300 如同往常一樣，目標函式反映了12條運輸路線的總運輸成本。把目標函式和約束條件組合起來， 就形成了一個具有12個變數、8個約束條件的線性規劃模型（見圖7-7）。我們用管理科學家軟體中的線性規劃模組計算出了最優解，圖7-8就是計算機的計算結果，表7-6總結了這個最優解。 min 2x13 + 3xi4 + 3xzs + 1524 + 2kgs + 6x36 + 3x37 + 6x38 + 4xas + 4xg6 + 6x47 + 5x48 S.t. X13+ X14 起點節點約束 ~X13 X23+X24 - X23 + xgs + xs6+X37+X38 - X4 - X24 Xss 436 X3z Xy≥0，對所有的：和j X38 ≤600 M400J =0 + Xast 546+ X47+ X48=0 + X45 =200 + X46 = 150 + X47 =350 + X48 =300 轉運節點約束終點節點約束圖7-7 瑞思電子問題的線性規劃模型正如在本節開始時提到的那樣，在轉運問題中弧可以任意連線兩個節點。所有的運輸方式在轉運問題中都是有可能的。對每個節點，我們仍然需要且僅需要一個約束條件，此約束條件必須包含每條弧進入或者離開該節點的每個變數。對於初始節點，輸出的總量減去輸人的總量必須小於或者等於該節點的商品供給量。對目標節點來說，輸入的總數減去輸出的總數必須等於該節點的需求。對轉運節點來說，輸出的總效必須等於輸人的總數。 目標函式值= 變數 ×13 X14 X23 X24 X35 X36 X37 X38 X45 X46 X47 X48 5200.000 為了闡述更一般的轉運問題，我們對瑞恩電子的問題進行修改，假設可以直接從亞特蘭大運輸商品到新奧爾良，單位運費值 550.000 50.000 0.000 400.000 200.000 0.000 350.000 0.000 0.000 150.000 0.000 300.000 圈7-8 瑞思電子轉運問題用普理科學寂教件計算的結果表7-6 瑞思電子轉運問題的最優解成本的減少最 0.000 0.000 3.000 0.000 0.000 1.000 0.000 0.000 3.000 0.000 4.000 0.000 為4美元，且從達拉斯運到新奧路運輸歲起點單位運輸成本爾良的單位運費為1美元。這個修改後的瑞恩電子問題的網路圖如圖7-9所示，線性規劃模型如圖7-10所示。 在圖7-9中我們給網路模型加入了兩條新的弧，因此兩個新的變數需要加入線性規劃模型中丹佛丹佛亞特蘭大堪薩斯城堪薩斯城路易斯維爾路易斯維爾到往堪薩斯城酪易斯維爾路易斯維爾底特律達拉斯邁阿巒新奧爾良總運輸成本 550 s0 400 200 350 150 300 去。圖7-10顯示，這兩個新變 $2 3 1 2 3 4 s 合計 $1 100 150 400 400 1 050 600 1500 量x28和 8出現在目標函式中， $5200 連線這兩條新弧的節點對應的約束表示式中也包含了這兩個變數。圖7-11 顯示最優解的值透過增加兩條運輸線路而減少了 600美元；*28=250個單位的商品從亞特蘭大直接運到了新奧爾良，*78 =50個單位的商品從達拉斯運到新奧爾良。
第7章運輸、指派與轉運問題零售商（終點節點） 成特律 200 191 600 工廠（起點節點） 丼佛倉庫（轉運節點） 6 150 6 350 400 300 供給 \ 分銷路線（弧） 需求圖 7-9 修改後的瑞恩電子轉運問題的網路表示圖 min 2xi3 + 3x1a + 3x23 + lx24 + 283s + 6836+ 3837 + 6x38+ 4x45 +4 46+6847+ 5 48+ 4828+1878 s.t. X13+X14 -X13 X23 +X24 - X23 + Xas t X36 + X37 +X38 -X14 - X24 X3s + + X45 X45+ X46+ X47+ X48 X36 + X46 X37 + X47 X38 + ≤600 + X28 ≤400 0 = 0 =200 = 150 - X78 =350 X48+ X28+ X78 =300 xy≥0，對所有的圖7-10 修改後的瑞思電子轉運問題的線性規劃模型目標函式值= 受量 ------- X13 X14 X23 X24 X35 X36 X37 X38 X45 X46 X47 X48 X28 X78 4600.000 —---__值 --- 600.000 0.000 0.000 150.000 200.000 0.000 400.000 0.000 0.000 150.000 0.000 0.000 250.000 50.000 ----- 成本的減少量 •--~。 0.000 0.000 3.000 0.000 0.000 1.000 0.000 2.000 3.000 0.000 4.000 2.000 0.000 0.000 圖7-11 用管理科學案軟體得出的修改後的瑞思電子轉運問題的最優解起點節點約束轉運節點約束終點節點約束
192 資料、模型與決策：管理科學篇 7.3.1 問題的變化因為涉及到運輸和指派問題，轉運問題可能出現如下幾種變化： 1. 總供給不等於總需求。 2. 最大化目標函式。 3. 路線容量或者路線最小量。 4. 不可接受的路線。 線性規劃模型的修改需要包含這些變化的修正，就如同在第7.1 節中所談到的運輸問題中所需要的一些修正。當我們為了顯示從節點；到節點j的路線運輸容量為L，在約束條件中增加一條或者更多像x，≤L，這樣的表示式，我們稱這樣的轉運問題為有容量限制的轉運問題。 7.3.2 轉運問題的一般線性規劃模型轉運問題的一般線性規劃模型如下： s.t 蒸 ≤S.起點節點： 轉運節點 *，≥0，對所有的i，j 其中， S： 一節點i到節點j之間的運輸量； -節點i到節點）之間的單位運輸成本； 一起點節點i的供給量； 一終點節點的需求量。 註釋與評論 1.專欄7-3描述了寶潔公司如何使用轉運模型來重新設計其北美的配送系統。 2. 在更先進的對待線性規劃和網路流量問題的方法裡，容量轉運問題被稱為純粹的網路流量問題。有效的特殊目標下的最優方案對於網路流量問題以及它的一些特殊例項是可以求得的。 3. 在更一般的線性規劃模型裡，終點節點的約束條件經常表述成： 這樣表述約束條件的好處在於公式的左邊的每個約束條件都代表了流出節點減去流入節點的量。 但是這些約來條件必須乘以-1，以使右端值為非負，該問題可以被很多線性規劃程式碼計算出來。 專欄7-3、實踐中的管理科學寶潔公司在產品供應上的啟發式探索幾年前，寶潔公司開始了一個重大戰略計劃，稱為北美產品供應研究。寶潔公司想綜合運用它的資源供應，最最佳化其北美的產品配送系統。一個決策支援系統用於輔助這個被稱為產品供應啟發式探索的專案（PSH），這個系統是基於和本章我們描述的轉運模型非常相似的轉運模型。 以前，很多寶潔公司的產品聚整合幾個組，這些組是共享相同的技術且可以在同一個工廠生產的。應用了轉運模型的 PSH 專案被用於設計這些產品組的採購選擇時的產品策略團隊的對策中。生產第7章運輸、指派與轉運問題 193 產品組的工廠為資源節點，公司區域配送中心為轉運節點，顧客需求區域為終點節點，直接運輸到顧客區域或者透過配送中心運送都是可行的。 產品策略小組用相互影響的啟發式演算法解決了各種產品供應和配送相關的問題。例如，小組想知道如果關掉5個工廠中的2個，把產品集中在剩下的3個工廠中生產，那麼會產生什麼影響？PSH 將會刪除兩個相應的供應節點，還要對剩下3個工廠的生產能力進行必要的修改，然後求解這個轉運問題。產品策略小組然後可以檢查新的最優解，接著再對模型做進一步修改，再求解，再檢查結果，如此迴圈。 PSHI被所有使用者看成是一個非常有價值的決策支援系統。當寶潔公司按照研究得出的結果進行實施時，它實現了每年2億美元的節約。寶潔應用PSH 在北美市場獲得了極大的成功。 資料來源：寶潔公司的 Franz Dill and Tom Chorman。 7.4 生產與庫存應用在第7.1 節和第7.3 節中我們介紹了運輸和轉運問題，並舉了在幾個供給點到幾個需求點之間的貨物運輸的例子。雖然貨物的運輸是許多運輸和轉運問題的主題，但是運輸或者轉運模型能夠被用於起點和終點之間沒有任何物質實物運輸的情況。在這一節，我們來看看如何運用轉運模型解決生產安排和庫存問題。 康託斯毛毯廠是一個小型的毛毯生產廠商， 它一直致力於生產家用和辦公用的毛毯。 表7-7是該廠接下來4個季度的生產能力、市場需求、每平方碼的生產成本以及每平方碼的庫存成本。需要特別注意的是，生產能力、市場需求和每平方碼的生產成本隨著季度不同而變化，而運輸存貨的費用從一個季度到下一個季度一直保持在0.25 美元每平方碼。康託斯毛毯廠要確定在這4個季度裡每個季度生產多少平方碼的毛毯，才能保證總生產和庫存費用最小。 我們先設計這個問題的網路示意圖。第一步，建立對應著每個季度的生產的4個節點和對應著每個季度的需求的4個節點。每個生產節點由一個流出弧連線對應的需求節點，弧的流量代表了這個季度生產的毛毯的平方碼數。 對於每個需求節點，流出的弧代表了庫存中被用於下一個季度的需求節點的數量（多少平方碼毛毯）。圖7-12顯示了這個網路模型，特別需要注意的是，節點1~4代表了每個季度的產量，節點5~8代表了每個季度的需求。每個季度的生產能力在節點的左側顯示，每個季度的需求在節點的右側顯示。 決定生產計劃和庫存策略的依據是最小化 4 個季度的總的生產和庫存成本，並對每個季表7-7 康託斯毛毯廠的生產能力、市場需求和生產成本及庫存成本預測度生產能力 ｛平方碼） 市場需求生產成本 （平方碼）（＄/平方碼） 庫存成本 （$/平方碼） 1 300 500 400 500 400 5 3 4 600 400 2 0.25 400 0.25 0.25 0.25 生產節點需求節點 600 2 1季皮的生茂量 400 0.25 300 500 2季度的生產量 5 500 3半度的 0.25 茶皮的 0.25 400 400 4季度的生產量 3 400 ^ 需求生產能力圖7-12 生產 （弧） 康託斯毛毯廠問題的網路表示團
194 資料、模型與決策：管理科學籍度的生產能力和需求給定約束條件。一般來講，可根據每個節點的約束條件和每條弧上的變數構建出一個線性規劃模型。 條件為： 讓我們定義xi為1季度生產的毛毯量，由於1季度的生產能力為600平方碼，所以生產能力約束 Xis ≤600 使用同樣的決策變數，我們可以得到第2~第4季度的生產能力約束條件： 426 ≤300 437 ≤500 * 8 ≤400 現在我們考慮每個需求節點的約束條件。對於節點5來說，進人該節點的弧代表1季度的毛毯生產量（平方碼），離開該節點的弧表示了！季度沒有賣出去的毛毯量，這些都要留到下一個季度出售。 一般來講，每個季度的期初庫存量加上本季度的生產量，再減去季度末的庫存剩餘量，必須等於這個李度的需求量。但是，1季度沒有期初庫存，所以，節點5的約束條件為： *is -Xso =400 相對應的需求節點2，3，4季度的約束條件如下： Xiso + 426 -Xs1 =500 Xon +xs X8 =400 Xne +&as =400 注意，節點8的約束條件（4季度的需求）只有兩個變數，因為沒有提供第5個季度的庫存總量。 目標是最小化4個季度的總生產和庫存開支，所以我們可以寫出目標函式： min 2xjs +5xzs +383n + 3%as +0.25xss +0.25xon +0.252g8 康託斯毛毯廠問題的完整線性規劃模型如下： min 2x1s + Sxzs + 38i3n +3848 +0. 25xiso + 0. 25 ton + 0. 25x78 3.t. Xs *26 Xis $26 tsi X48 - Xso + xs6- + *4s $67- + ≤600 ≤300 ≤500 ≤400 =400 =500 $8 =400 xe =400 *。≥0，對所有的i和； 目標函式值= 變數 ×15 ×26 ×37 X48 ×56 X67 X78 5150.000 值 ---- 600.000 300.000 400.000 400.000 200.000 0.000 0.000 成本的減少量 0.000 0.000 0.000 0.000 0.000 2.250 0.000 田7-13 康託斯毛毯廠問題用管理科學家軟體求出的量優解我們用管理科學家軟體中的線性規劃模組求出這個線性規劃模型，解決康託斯毛毯廠的問題。圖 7-13 顯示了該問題的最優解：康託斯毛毯廠應該在1季度生產600平方碼的毛毯，2季度生產1300平第7章運輸、指派與轉運問題 195 方碼的毛毯，3季度生產2400平方碼的毛毯，4季度生產400平方碼的毛毯。注意：1季度應該剩餘 200平方碼的毛毯給2季度，總的生產和庫存成本為5150美元。 註釋與評論 1. 同一個問題可以用不同的方法建模。本節我們用轉運模型來給康託斯毛毯廠問題建模。這個問題還可以用運輸模型來建模。對本章問題部分的第39題，請你用運輸模型來給這個問題建模。 2. 在我們給轉運問題建立的網路圖模型裡面，離開起點節點的弧上的運輸量經常是等於進入終，點節點的弧上的運輸量。如果這個網路模型存在一種損失或者收益弧貫穿這個圖時，進入終點節點的數量可能大於或者小於從起始節點出來的量。例如，如果孤上的現金流量是商品流帶來的，由於存在利息，所以，進入下一個節點的現金流一定大於從上一個節點出來的現金流，這個差額部分就是公司獲得的利息。這種帶有損失或者收益的網路圖是一種更高階的網路流規劃。 7.5 運輸單純形法：帶特殊目標解決方案的步驟（選讀） 用一般目的的線性規劃編碼解決運輸問題，對中小型規模問題比較有效。然而，這些問題往往會變得很大（比如說一個100 個起點節點和100個終點節點的問題將會有100 000個變數），那麼我們就需要一個更有效的方法來解決這類問題。運輸問題的網路結構模型可以用管理科學家軟體來設計出特殊目標的解決方案，這樣能夠更加簡化計算過程。 在第7.1節中，我們介紹了福斯特發電機運輸問題並給出如何用線性規劃模型來構建和解決這類問題的過程。這個線性規劃模型包含12個變數和7個約束條件。在本節中我們將描述用於一個特定目標的解決方法——運輸單純形法，它融合了運輸問題的網路流結構的優點，並使大型運輸問題的求解可以在計算機中進行，使得求解大型問題變成可能。 運輸單純形法，正如線性規劃的單純形法，是一個兩階段的過程。第一步，先找到初始的可行解，接著反覆進行修正，得出一個更好的解，直到找到一個比較理想的解為止。為了方便概括計算過程，我們使用一個運輸表。福斯特公司問題的運輸表如表7-8所示。 特別需要注意的是，表裡的12個單元格對應著圖7-1 裡的12條弧，也就是說每一個單元格對應著從起點到終點節點的路線。因此，運輸表裡的表7-8 針對福斯特公司運輸問題的運輸表每個單元格對應的是線性規劃模型中的一個變量。表右邊的條目輸人的資料是起點節點的供給起點量，表底部輸人的資料是終點節點的需求量。每波士頓 3 芝加哥 2 聖路易斯菜剋星頓總點供給 6 一行對應的是網路模型中的供給節點，每一列對克利夫蘭 5000 應的是網路模型中的需求節點。根據列的數量和 7 5 2 3 行數，就可知道這個問題的線性規劃模型有多少貝德福徳 6000 個約束條件。右上方小單元格內輸人的資料表示的是對應路線上的單位運輸費用。還要注意，福 2 _5 ［4 斯特公司問題的總供給等於總需求，運輸問題的單純形法只能被用於平衡問題（總需求=總供給）；如果間題不是平衡的，那麼就必須加人虛擬起點節點或者虛擬終點節點。虛擬起點節點和終點節點的使用將在這一節稍後部分討論。 約克踐點需求 6000 4000 單元格對應的數字是從貝德福德到波上頓之間的運輸量 2.500 2000 1500 13500 總供給和總需求 7.5.1 第一階段：找出初始可行解運輸問題的單純形法的第一步就是要找出初始可行解。這個初始解提供了弧上的流量，孤上的流
196 資料、模型與決策：管理科學篇量滿足每個需求約束條件，而且不能出現從起點節點運出的貨物大於它的最大供給能力的情況。這些用於尋找初始可行解的步驟被稱為啟發式。啟發式是一個具有常識性的過程，為的是儘快找到問題的一個初始可行解。 為了尋找運輸問題的初始可行解，人們想出了一些啟發式方法。雖然透過這些方法能夠很快找到初始可行解，但是找到的可行解往往不是那些能夠最小化總運輸成本的初始解。有些方法可能不能那麼快地得到可行解，但是最終這個可行解比較接近最優解，從可行解到最優解的計算成本最少。我們所描述的這種為了尋找能夠解決運輸問題的初始解的啟發式方法叫做成本最小化法。這種啟發式方法力求在儘快找到可行解和找到接近最優解的可行解之間尋求平衡點。 首先，我們分配成本最小的弧儘可能大的流量。在表7-8中，我們可以看到克利夫蘭一芝加哥、 貝德福德一聖路易斯和約克一波士頓這3條路線比較符合成本最小的弧這個標準，因為它們的單位運輸成本只表7-9 有2美元。當各條弧之間的價格一樣時，我們選擇運輸波士頓 3 量最大的那條弧，在此，相對應的就是克利夫蘭一芝加克利夫蘭運用一次成本最小化方法後的運輸表芝加哥聖路易斯萊剋星頓供頸 2 7 6 1000 4000 $-000 哥這條路線，最多可以運輸4000個單位，所以我們在克利夫蘭一芝加哥這條孤對應的運輸表中的單元格內輸 7 5 2 3 人4000。這一選擇使得在克利夫蘭的供給從5000減貝德福徳 6 000 少到1000。從而，我們去掉5000單位的供給，以 2 _4 L5 1000單位代之。同時，在這條弧上分配的4000單位正約 2 500 好符合芝加哥的需要，所以我們把芝加哥的需求減少到 0，並且在相應的一欄畫上一條線，去掉這一欄不再考需求 6 000 4000 2 000 1500 慮。現在，運輸表就如表7-9所示。 現在，我們看這個減少後的運輸表，它由所有沒有畫線的單元格組成，我們從這個新的運輸表中尋找下一個最低成本弧。貝德福德一聖路易斯和約克一波士頓這兩條弧的單位成本都為2美元，但是約克一波士頓的路線上的運輸容量大些，所以我們選擇約克一波士頓。為了更新運輸表，我們減少 2500單位的波士頓的需求，使其變為3500，減少約克的供給到0個單位，然後在這一行上畫條線， 不再考慮。繼續使用這種方法，我們得到的結表7-10 果是在貝德福德一聖路易斯路線上分配2000 單位，並去掉聖路易斯這一行，因為其需求已波士頓 3次重複使用成本最小化法之後的運輸表芝加哥聖路易斯菜剋星頓 1供絲 2 經減到O了。經過第二次和第三次的這樣的重克利夫蘭 4 000 復之後，我們得到如表7-10所示的運輸表。 1000 $000 我們現在有兩條弧符合成本最低的要求， 7 5 它們的值為3；克利夫蘭一波士頓和貝德福德貝德福德 2 000 一菜剋星頓。我們可以給克利夫蘭一波士頓的每條路線分配1000單位，且給貝德福德一菜 5 2 4 3 4 000 6-000 剋星頓的每條路線分配1500單位，我們因此約克 2 2-$00 5 0 -2500 給貝德福德一菜剋星頓的路線分配1 500單位。 這樣做的結果是，菜剋星頓的需求為0，從而 6-000 3500 4600 2000 1500 消除了列。最小化成本的下一個步驟是給克利夫蘭一波士頓的路線分析1 000單位。經過這兩次分配之後，運輸表如表7-11 所示。 惟一剩下的沒有被畫線的單元格是貝德福德一波士頓。我們根據貝德福德的剩餘供給量給對給的弧分配2500單位的產品，這樣就滿足了所有的波士頓的需求。相應的運輸表如表7-12所示。 這是一個可行解，因為所有的需求被滿足了，所有的供給都用上了。初始可行解的總運輸成本的計算過程如表7-13所示。運輸單純形法的第一階段現在已經完成了，我們得到了初始可行解。這個解對應的總運輸成本為42000美元。
第7章運輸、指派與轉運問題 197 成本最小化法總結進人運輸單純形法第二階段之前，讓我們總結一下使用成本最小化法得到初始可行解的步驟。 第一步，確定運輸表中成本最低的單元格 （弧），然後儘可能多地把流量分配到這一單元格。如果出現了單位成本相等的狀況，就需要貝德福德找出運輸容量最大的單元格。如果仍然相等， 可以選擇相等單元格中的任何一個。 第二步，根據第一步得到的結果分配單元約克一格的流量，減少行的供給量和列的需求量。 第三步，如果各行的供給量和各列的需求需求量都減至O，就應停止。這些分配就構成了初始可行解。否則，便需要進行第四步。 第四步，如果現在某行的供給量是0，就表7-12 在這一行上畫線，不再考慮。如果現在某列的需求量是0，就畫線去掉這一列。 第五步，對那些未畫線的行和列，重新執克利大蘭行第一步。 表7-11 5 次靈復使用成本最小化法之後的運輸表波士頓芝加部 ¥路易斯菜剋星頓供結 _3 2 7 6 0 1-000 克利夫”—1000 4060 -008 2 000 2 2-500 5 2 4 1500 3 5 2500 4000 6-000 0 2-6066000 3-$00 2500 -4-000 2-000 1-$00 重複使用成本最小化法之後的得到了初始可行解的最終運輸表波士頓 3 1 000 芝加問聖路易斯 L2 7 萊剋星頓冼 6 4000 7.5.2 第二階段：修改，直至找到最優解貝德福德 7 2500 5 2000 3 1500 運輸單純形法的第二階段是對第一階段得出的初始可行解修改直至找到最優解的過程。 回顧一下，運輸表中的每個單元格對應著運輸問題網路模型中的一條運輸路線。第二階段的第一步是要確定一條入弧，這條人弧是指當前還未被使用過的弧（未佔用單元格），而且分配這條弧將最大程度地減少總的運輸成本。給這條弧分配流量，而先前其他路線所承載的貨運量（已經佔用單元格）將隨之變動，但是這種變動要在方案的可行性基礎上。在變動單元格的分配過程中，我們將找出一條出弧，並將它摒棄。因而，在第二階段的每一次修改中， 我們將在方案中引入一條當前沒有使用過的路線，同時再從中刪除一條先前承載貨運量的路線。 約克 12 2 500 5 4 5 0 +-000 $-000 0 2-500 4-000 6-000 0 2-500 需求 6000 3-500 -2-500 0 -4-000 0 2-000 0 1$00 0 表7-13 利用成本最小化法獲得的初始可行方案的總運輸成本路線運輸量起始克利夫蘭克利夫蘭貝德福德貝德福德貝德福德約克前往波士頓芝加哥波士頓聖路易斯萊剋星頓波士頓單位運輸成本總成本 （美元） （美元） 3 1 000 4 000 2 500 2 000 1 500 2 500 3 000 8 000 17 500 4 000 4 500 5 000 為解釋運輸單純形法的第二階段是如何進 2 合計 42 000 行的，我們有必要先弄清楚下列問題：如何找出人弧（單元格），如何對先前已經承載的路線做變動，以及如何找出出弧。我們先來考慮如何找出人弧。 如前所述，人弧是一條能引起當前方案總的運輸成本最大程度降低的路線。要找出這條路線，首先要計算出使用每一條尚未使用的路線對總成本的影響。MODI法（分配修正法）就是這樣一種計算方法。 MODI法需要我們定義表中每一行的指數 44，和表中每一列的指數1。在計算這些指數時，要求每個已經佔用的單元格的成本系數等於1，+1。c，是從起點節點；到終點節點j這條路線的單位運輸成本。
198 資料、模型與決策：管理科學篇因此，每個已經佔用的單元格必須滿足 14，+1， =C。讓我們返回福斯特公司問題的初始可行解，這個可行解是用成本最小化法找到的（見表7-14），然後我們用MODI 法來確定入弧。 在初始可行方案中，對每一個已經佔用的單元格應用公式1，+， =Cw，我們得到6 個等式和7個指數（或稱變數）： 已經佔用的單元格 M；+V=C 已經佔用的單元格 M：+Y=00 克利夫蘭一波士頓 E+ =3 貝德福德一波士頓 42+1=7 克利大蘭一芝加哥 ui+lg =2 貝德福德一聖路易斯 142+$s=2 已經佔用的單元格貝德福德一菜剋星頓約克一波士頓 42+¾=3 43 +U=2 由於指數（變數）比等式多一個，所以我們可以為其中任意一個指數取一個值，並由此解出其他指數的值。令1，=0，那麼我們可以得到如下等式： 0+2=3 L2+V：=7 a+。=3 0+2=2 U2+ =2 Hs+2，=2 透過這些等式可以計算出其他指數的值，如下： 4=0 4 lg = -1 =3 =2 V=-2 =-1 管理科學家軟體顯示了：對每一個未經佔用的單元格，由等式e=C 一1， 2；確定給末佔用的單元格分配一個單位流量，能對總的運輸成本產生多大變化。因此，我們稱e為淨評估指數。由於已經佔用的單元格的3：和也，是透過上述方式算出來的，所以已經佔用的單元格的淨評估指數為0。 重新輸人福斯特公司運輸問題的初始可行解，並替換出先前的z，和也，值，我們可以得到表7-15。我們計算出每個未佔用的單元格的淨評估指數（eg），即表中帶圖圈的數字。由表中可見，從起點節點1運送單位貨物到終點節點3（克利夫蘭一聖路易斯）將使成本增加9 美元；從起點節點1運送單位貨物到終點節點 4（克利夫蘭一菜剋星頓）將使成本增加7美元；從起點節點2運送單位貨物到終點節點2 （貝德福德一芝加哥）將使成本減少1 美元； 其他由此類推。 基於這些淨評估指數，成本減少輻度最大的最優的路線是貝德福德一芝加哥，即選中第二行，第二列的單元格作為收人單元格。給這個單元格分配一個單位就能減少總運輸成本1 美元。現在的問題是：我們應該給這條弧分配多少個單位呢？因為這個單元格能降低總的運輸成本，所以我們應當儘可能地多分配。為了找到這個分配的最大量，我們必須意識到可行性，分配給這個單元格的每單位流量都是透過表7-14 福斯特公司運輸問題的初始可行方案波士頓芝加哥聖路易斯菜剋星頓供齡 ［3 L2 6 克利夫蘭 1000 4000 5 000 ［7 Ls 貝德福德 2500 ［2 2000 ［3 1500 6 000 _2 2500 ［4 5 約謝求克 2500 6000 4 000 2000 1500 表7-15 用 MODI法算出的斯特公司問題的初始可行方案的淨評估指數 3 -2 -1 3 2 7 6 0 1 000 4 000 7 5 2 3 4 2 500 2000 1500 2 5 4 5 -1 2500
第7章運輸、指派與轉運問題 199 調：其他當前被使用的單元格流量得來的。我們將用臺階法來確定必要的調整並找出出弧。 臺階法假設給入弧（貝德福德一芝加哥）分配1單位的流量。為了保證可行性，也就是說，這個分配給這條弧的流量不能超過芝加哥總的需求量，我們不得不減少克利夫蘭一芝加哥路線表7-16 分配1單位給貝德福德一芝加哥入弧之後， 上的流量至3999（減少了1單位）。同時我為了保證可行性，已佔用單元格的一系列調整們還得增加克利夫蘭一波士頓的流量至1001 波士頓芝加哥聖路易斯萊克尾頓 （增加了1單位），以使克利夫蘭的總供給量5 3 2 7 6 000單位的產品能夠全部被運走。最後，我們克利夫蘭 1 001 3999 5000 再使貝德福德一波士頓路線上的流量減少1單 -1-008 4008 位，使得波士頓的總需求量不變。表7-16描 7 5 2 3 述了這一系列的調整。 貝德福德 2499 2 000 1 500 6000 分配1單位給入弧（貝德福德一芝加哥） 2500 引起了一系列必要的調整，這些調整將引起4 2 5 4 5 個單元格的變化：1個收入單元格和4個已佔 2500 用單元格。我們把這4個單元格在表中組成臺約克 2500 階，而已佔用單元格作為路的轉彎處。取名為需求 6 000 4000 2000 1500 “臺階”，意在將整個表視為一個池塘，而已佔用單元格則是其中突起的石頭。要找出人弧表7-17 貝德福德一芝加哥作為入弧的臺階法的臺階，我們從收入單元格出發，將已佔用單波士頓芝加哥 ¥路易斯菜剋星頓元格作為臺階的轉彎處的石頭，這些石頭可以 + 3 2 7 6 上下左右移動。最終目的是石頭與石頭之間的克利夫蘭 5000 移動，最後回到起始的收人單元格。為了使作為臺階一部分的已佔用單元格更為醒目，我們 7 5 L2 3 將每一個臺階上的已佔用單元格畫成圓柱狀， 貝徳福德 2000 1 500 6 000 以加強這些單元作為鞏固池塘臺階的形象。表 2 5 4 7-17 描述了與貝德福德一芝加哥人弧相關的 5 臺階路徑。 約克 2500 2 500 在表7-17中，我們在每個已佔用的單元 6 000 4 000 2000 1 500 格中加入了加號（+）和減號（一）。加號表不在臺階路徑上未佔用單元格示分配給這個單元格的流量將增加，增加的流的已佔用單元格量等於我們分配給收人單元格的流量。減號表在臺階路徑上的已佔用單元格示我們分配給這個單元格的流量將減少，減少的流量等於我們分配給收人單元格的流量。因表7-18 運輸單純形法經過一次調整後的新的解決方案此，為了確定這個最大的可以分配給收入單元波士頓芝加哥聖路易斯萊剋星頓你維格的流量，我們只要看臺階路徑中帶有減號的 L3 ［2 |7 單元格就行了。帶減號的單元格最小可以被分克利夫蘭 3500 1500 5000 配的量決定了收入單元格最大可以被分配的量。分配完收人單元格這個最大量之後，我們 ［7 ［2 ［3 再根據臺階路徑做所有必要的調整以保證可行貝德福德 2500 2000 1500 6000 性。收人單元格將成為已經佔用單元格，支出單元格將從當前方案中被刪除。 ［2 5 4 5 在福斯特公司問題中，貝德福德一波士頓約克 2500 2500 和克利夫蘭一芝加哥這兩個單元格的流量將被減少（單元格帶減號）。這個減少的流量將作 6000 4000 2000 1500
200 資料、模型與決策：管理科學寫為收入單元格的流量。我們可以看到貝德福德一波士頓單元格的流量為2500，比克利夫蘭一芝加哥單元格的4000要少，所以我們把貝德福德一波士頓作為出弧。新的調整方案就是： 表7-19 用 MODI法對每個單元格進行評估把貝德福德一波士頓單元格的2500單位分配給貝德福德一芝加哥單元格，然後刪除貝 3 2 -I 0 德福德一波士頓單元格（它的分配減為O）。 3 2 7 6 表7-18 是一個新的解決方案的運輸表。注 0 3 500 1 500 （8 意：它與先前的運輸表的惟一不同是從貝德福德一波士頓單元格開始的臺階路線。 7 5 2 3 現在我們再試著改進當前方案。第一步 3 ① 2 500 2 000 1 500 還是運用MODI方法來找到最佳的入弧。再次計算行列指數。所有已經佔用單元格必須 2 5 4 5 滿足1，+1，=Cy。1，和t，的值很容易在運輸 -I 2 500 4 6 表中直接計算得出。回顧一下一開始我們用 MODI 計算行列指數時，設定w，=0，因此， 第一行的兩個已佔用單元格中也 =cv，最後表7-20 算出v，=3，”：=2。順著新計算出來的列指福斯特公司運輸問題的最優解數往下，我們用cv一，計算相應的有效單元路線單位運輸成本總成本運輸靂格的行指數。知道列指數的值、 後，可超始前往 （美元） （美元） 以得出行指數1=5-2=3，I=2-3= 克利夫蘭波士頓 3 500 3 10 500 -1。下一步，我們用這些行指數計算對應克利夫蘭芝加哥 1 500 2 3 000 單元格列指數的值，得到1=2-3=-1， 貝德福德波士頓 2 500 5 12500 2。=3-3=0。表7-19顯示了新的行列指數。 貝德福德聖路易斯 2 000 4 000 表7-19中還顯示了每個單元格的淨變貝德福德菜剋星頓 1 500 3 4 500 化值（帶圓圈的數字），這個淨值指的是如約克波士頓 2 500 2 5 000 果分配1單位給每個未佔用單元格將引起的合計 39 500 總成本變化。回顧一下，這個數值是透過公表7-21 產生退化的初始可行方案的運輸表注意，每個未佔用單元格的淨評估指數現在供筇都大於0。也就是說，如果使用這些單元格將會引起總運輸成本增加。已經沒有哪條弧的引人會降低成本了，也就是說我們已經達 0 3 3 35 L6 25 7 60 到最優解了。表7-20總結了這個最優解並標出了最優解決方案的總成本。跟預期的一 8 5 7 樣，這個最優解的結果和線性規劃模型解出 -1 來的最優解一樣（圖7-2）。 30 30 保持n+n-1個有效（被佔用）單元格n表示起點節點的個數，n表示終點節 4 9 1I 點的個數。對於運輸問題，少於m +n-1 30 30 個有效單元格的方案被稱為退化方案。福斯特公司問題的解決方案不是退化方案，它有露求 35 55 30 6個有效單元格，剛好m+n-1=3+4-1 =6。要用MODI 方法計算出行列指數，必須有m+n-1個有效單元格才能算出所有的行列指數。當退化問題發生時，為了計算出所有行列指數，我們必須人為建立一個有效單元格。下面我們來演示一第7章運輸、指派與轉運問題 201 下退化的產生和解決過程。 表7-21 中列示了一個運輸問題用成本最小化法得到的初始可行解，這個問題包含m=3個起點， n=3個終點。為了用 MODI 方法計算行列指數，必須確保有m +n-1=3+3-1=5個有效單元格。但是初始可行解卻只有4個有效單元格，產生了退化。 假設我們在這個問題的第二階段試著用 MODI 方法來計算行列指數。令比」=0，為每個已經佔用單元格計算它的行列指數。第一行中可以得到第一、二格的列指數1」=3， =6（見表7-21）。繼續計算第一、二列中已佔用單元格的行指數，得到u=5-6=-1。這時，我們不能再接著計算行列指數了，因為第三行中的頭兩格和第三列中的頭兩格都沒有有效單元格了。 當有效單元格小於m+1-1時，為了計算出所有的行列指數，我們必須建立出一個或者更多人為的有效單元格，並令這些單元格的流量為0。在表7-21 中，我們建立了一個有效單元格，使得有效單元格為5個。並非任何當前未佔用單元格都可以作為有效單元格，只有那些能繼續計算行列指數的單元格才行。例如，把表7-21中的第二行第三列的單元格作為有效單元格，我們就能計算出也，44s。但是，如果設第二行第一列的單元格為有效單元格則不行。 如前所述，在建立有效單元格時，我們爽 7-22 設第二行第三列的單元格作為人為的有效單元格後的運輸表分配0流量到相對應的弧上。表7-22列出了在表7-21中的第二行第三列建立有效單 3 8 供絲元格後的結果。 3 6 7 透過使用第二行的行指數和第二行新創 0 35 25 60 建的有效單元格（在第三列），我們可以計算出第三列的列值，也就是說 2=C28 - 42 = 8 5 7 7-（-1） =8，然後，我們用剛算出來的第 -一 30 0 30 三列的列指數8以及第三行第三列的有效單元格，計算出第三行的行指數：44，=C38 2= 4 9 11 人為佔用單元格 11-8=3。表7-22列出了所有的行與列的 3 指數以及每一個無效單元格的淨評估值。 （3 ◎ 30 30 回顧表7-22中的淨評估值，我們可以 35 55 30 將第三行第一列的單元格（淨評估指數= -2）作為收入單元格。為了保證可行性的臺階路徑和必要的修改如表7-23所示。注表7-23 第三行第一列的單元格為收入單元格的臺階路徑意，臺階路徑會比福斯特公司問題中的收入單元格更加複雜。表7-23 中的路徑需要對 3 供給所有5個有效單元格進行調整，以保證可行 3 + 6 7 性。加號和減號只是表示在流量被分配給收 0 60 人單元格時，別的有效單元格的分配是增加還是減少。在流量分配減少的所有單元格中 8 5 的最小流量是第二行第二列單元格和第三行 + 7 第三列單元格的連線。 -I 30 因為這個最小流量是30，所以我們分配給收入單元格的流量也是30。當我們分 4 9 配30個單位到收人單元格，並對臺階路徑 3 30 上的有效單元格進行調整時，到這兩個單元格（第二行第二列單元格和第三行第三列 35 $5 30
202 資料、模型與決策：管理科學篇單元格）的流量就減為0了。我們可以把其中任何一個單元格作為支出單元格，但一次不能同時選擇兩個。其中一個可設為無效單元格，另一個可以看做零流量的有效單元格，這樣做的原因是避免出現退化現象。當選擇支出單元格時，如果出現兩個一樣數值的單元格，則可以任意選擇一個有效單元格作為支出單元格，然後用MODI 方法重新計算行列指數，只要每次迴圈中得到的單元格不多於1個，MODI方法就會有效。 在第三行第一列的收人單元格內分配了 30個單位並根據臺階路徑做了必要修改之表7-24 給收入單元格分配了30 個單位之後得到的新的行列指數後得到的新的解決方案和運輸表如表7-24 所示（注意，我們把第二行第二列的單元 3 6 8 供絲格看做是人為的有效單元格）。在計算完新 3 6 7 的行列指數之後，我們把第一行第三列的單 0 5 55 60 元格作為下一個收人單元格。分配給這個單元格的每單位流量將會減少一個單位的最終 8 5 7 解的值（比如說最優解的總的運輸成本）。 -1 ⑥ 0 30 30 和這個收人單元格相關聯的臺階路徑在表 7-25 中顯示。第二行第三列的單元格是支 4 9 11 出單元格；一次迭代之後的運輸表如表7-26 - 30 2 ② 30 所示。注意，我們已經找到了最優解，且雖然先前的幾次迭代出現了退化現象，但是最謝求 35 55 30 終的解決方案不是退化的。 喪7-25 第一行第三列的單元格表7-26 作為收入單元格的臺階路徑一個初始解出現退化的問題的最優解 3 6 8 供統 3 6 7 0 5 60 8 + 5 -一 30 4 9 1I 一 30 30 35 55 30 7.5.3 運輸單純形法小結 3 6 7 3 6 7 0 5 25 30 8 5 7 -1 30 ① 4 9 11 1 30 ② （3 35 55 30 供絲 60 30 30 運輸單純形法可應用於任何具有特結構的運輸問題的任何網路模型中，可以解決帶任何特殊目標的最優解的求解問題。運用線性規劃的一般單純形法是一種更為聰明的選擇；但是因為運輸問題的特殊數學結構，運輸單純形法比一般單純形法快幾百倍。 只有在總需求等於總供給的運輸問題中才能應用運輸單純形法，因此對有些問題，必須要加入虛擬的起點或者終點節點，使運輸問題成為這種形式。運輸單純形法需要分兩個階段來求解。第一階段，用成本最小化法找出初始可行解。第二階段，從初始可行解開始選代，一直到找到最優解。解決第7章運輸、指派與轉運問題 203 最小化問題的運輸單純形法的步驟總結如下： 第一階段用成本最小化法找出初始可行解。 第二階段第一步，如果初始可行解出現退化現象且有效單元格小於m+n-1個，增加一個人為的有效單元格，使得有效單元格數=m+n-1個，這樣才能用MODI方法。 第二步，用 MODI 方法計算出行指數1，和列指數1。 第三步，利用公式e=C一1，一2，計算出每個未佔用單元格（無效單元格）的淨評估指數。 第四步，如果所有無效單元格的e，都是大於等於0的，則已經找到了總成本最小的解決方案。否則繼續第五步。 第五步，用最小淨評估指數的方法確定無效單元格中的哪一個作為收人單元格。 第六步，找到連線收人單元格的臺階路徑，用加號標出臺階路徑中的哪些單元格的流量是增加的，用減號標出臺階路徑中的哪些單元格的流量是減少的。 第七步，選擇臺階路徑上帶有負號且流量最小的單元格作為支出單元格。如果出現有多個符合相同要求的單元格，選擇其中的任何一個。而那些符合條件沒被選中的單元格將會在下一次迭代中被人為地分配零流量。 第八步，把當前支出單元格內的流量分配給將要引入的收人單元格，對所有位於臺階路徑上的單元格進行正確合適的調整，然後繼續第二步。 7.5.4 問題的變化以下的問題變化可以透過細微的調整，運用運輸單純形法來解決： 1. 總供給不等於總需求。 2. 目標函式最大化。 3.不可接受的路線。 對總供給不等於總需求的情況，我們可以先引人一個虛擬起點或者終點，並運用運輸單純形法輕松地解決。如果總供給大於總需求，我們引入一個虛擬終點，其需求為總供給減去總需求部分。相似地，如果總需求大於總供給，我們則引入一個虛擬起點，其供給等於總需求減去總供給的那部分。在任何一種情況下，虛擬終點或者虛擬起點的使用都會平衡總供給和總需求的，以便我們可以用運輸單純形法。如果存在虛擬終點或者起點，我們分配零成本給每一條進人虛擬終點的弧或者每一條起點與虛擬起點的弧。原因在於：當把計算結果運用於實際時，沒有真正的運輸發生在虛擬起點或者虛擬終點相關聯的路線上，所以要把單位運輸成本設定為0。 這種運輸單純形法也可以用於解決最大化問題，不過需要改變即將引入的單元格的選擇依據。與最小化同題相反，我們要選擇的不是最小的e。值的單元格，而是選擇最大的e值的單元格作為收入單元格引人。也就是說，我們選出能導致目標函式值最大程度增加的單元格。如果所有非有效單元格的 e≤0，我們就停止計算：最大化解決方法已經找到了。 關於解決最小化問題的不可接受路徑問題，不可行弧必須具有極高的成本，才可能不被選人最優解中。我們用M表示這個極高的成本。這樣，如果我們有一條從一個起點到一個終點的路線，但由於某種原因，它不能被使用，我們就可以簡單地將這條弧的單位運輸成本定為M。如此，它就不會進入最後的結果中。在最大化問題中，不可接受的弧（單元格）會被賦予-M的單位利潤。 註釋與評論 1. 致力於開發有效的網路模型的特殊目標的求解過程的研究表明，運輸單純形法是最好的方法之一。它被用於管理科學家軟體包的運輸和指派模組中。此方法的一個簡單擴充套件也可用於解決轉運問題。 2. 正如我們在先前註釋與評論部分提到的，運輸表中的每個單元格和問題網路模型中的孤（路
204 資料、模型與決策：管理科學篇線）與線性規劃模型中的變數相對應。所以運輸單純形法的第二階段與線性規劃的一般單純形法的第二階段是一樣的。在每次選代中，最終結果將引入一個變數，丟棄一個變數。此方法對於運輸問題這麼有效，原因是約東條件方程式的特數學結構，這個精殊數學結構決定了只需要增加或者減少操作。我們用運輸表來實施整個求解過程，運輸表的每一行代表一個起點節點，每一列代表一個終點節點。然而這樣的問題如果用一般單純形表表示，那麼就需要用行來表示每個起點節點，用列來表示每個終點節點和每條弧。這樣，單純形表就會大得多。 7.6 指派問題：帶特殊目標的求解步驟（最最佳化） 如前所述，指派問題是運輸問題的一個特殊例子，因此，運輸單純形法也能被用於指派問題。然而，指派問題的結構更加特殊：所有的供給和需求都等於1。因為這個特殊的結構，帶特殊目標的求解過程就要被特殊設計，用來解決指派問題。這樣的一個求解過程，我們稱為匈牙利法。這一節中， 我們介紹匈牙利法是如何解決福爾公司指派問題的。 回想一下福爾公司中分配專案負責人的問題（見第7.2節）。有3個負責人，3個調查專案分別屬於3個客戶。福爾公司的分配選擇和預計的專案總共完成時間（單位天）見表7-3。 匈牙利法涉及到矩陣簡化法的應用，在矩陣中，減少和增加合適的值會產生指派問題的最優解。 這個方法有3個主要的步驟，第一步是行和列的減少。 第一步，透過減少每行中的所有元素中最小的那個元素來減小起始矩陣。然後，在減少了行的新矩陣中找每一列中最小的元素，並減去這個最小值。 因此，我們先對錶7-3中列出的矩陣進行第一步操作，減去每行中的最小值。第一行中的最小值為9，第二行中的最小值為5，第三行中的最小值為3，行的最小值減去後得出的新矩陣如表1所示。 這個新矩陣代表的指派問題的最優解與原來的指派問題的最優解是表一樣的。為了理解其原因，首先注意第一行的最小元素9被減去，特瑞是必須要被分配到一個專案中去的，所以這個修改後的模型的惟一改變特瑞就是特瑞的任一分配所需的時間都必須小於9天。同樣，卡爾和邁克孟卡爾德的完成時間也必須分別小於5和3天。 邁克孟禟 1 4 3 2 6 13 11 3 0 0 0 繼續矩陣減少過程中的第一步，我們現在從行減少的矩陣的每一列中減去最小的元素。這樣導致了等同的指派問題。也就是說，同樣的解決方法仍是最優。但是，完成每一個程式所要求的時間被減少了，第一列的最小值為1，第二列的為6，第三列的為0，這個減少的矩陣變成了表2。 匈牙利法的目標是繼續減少矩陣，直到解決方法之一的值為0。也就是說，直到專案負責人全部分派給顧客。從減少矩陣來看，總體時間支出為0天，這樣只要在矩陣中沒有負面的因素，等價值的方案則為最優。透過這種方法我們繼續減少矩陣，進一步認識到如何透過下面兩步特瑞卡爾邁克孟德表2 1 0 3 2 2 0 7 5 3 0 0 0 達到最優解。 第二步，用最少的行列直線把矩陣中的0都連起來，如果這些直線的最小數目等於矩陣行數（或者等於列數），一個值為0的最優分配則被找到了。如果線的最小數目小於行的數目，則進行第三步。 實施第二步，我們看到了要求覆蓋所有的0的直線的最小數目為2，這樣我們必須進行第三步。 1 2 3 特瑙卡爾邁克盂德 0 7 ② 5 兩條直線將穖蓋所有的Q（第二步）
第7章運輸、指派與轉運問題 205 第三步，從沒有畫線的元素中找到最小的，並在所有未畫線的元素上減去這個最小值，然後增加一個相同數值給兩條線交叉處的那個元素，所有的其他元素保持不變。回到第二步，並繼續求解能覆蓋矩陣中所有0的必需的直線的最小數目等於行的數目。 最小的未畫線的元素是2。在先前的矩陣中我們圈上了這個元素。從所有未畫線的元素中減去2 並增加2給特瑞和顧客3交叉的那個元素。這樣新的矩陣就形成了，如下： 1 2 特瑞卡爾邁克盂德二步的計算。 0 0 5 0 3 3 2 0 0 回到第二步，我們發現要求覆蓋目前矩陣中所有0的直線的最小數目為3。以下的矩陣說明了第特瑞 d 卡爾 2 0 s 3 邁克盂德必須畫上3條線才能積蓋所有的0，因此，最優解得到了這樣依照第二步，我們找到一種值為0的分配方法是可能的。為了達到這個目的，我們首先定位那些只包含一個零的任何一行或者列。如果所有的行或列中0的個數都超過了一個，那麼我們選擇有最少0的行或列。我們在選擇的行或列的0上畫上一個正方形，表明一次分配，並刪除那一行或列， 不再進一步考慮。在福爾公司問題中，第二行只有一個0，所以我們分派卡爾給顧客3並刪除第二行和第三列，不予進一步的考慮。邁克孟德必須分配給顧客1（第三行中剩下惟一個0）並最終把特瑞分配給顧客 2。從減少的矩陣來看，福爾公司問題的解決方法要求0天的時間支出，如表3。 我們透過參考最初的指派問題，總結了最優分配所需的完成專案的總時間。在這個例子中，特瑞分配給顧客2完成專案需要15天，卡爾分配給顧客3完成專案所需時間為5天，邁克孟德分配給顧客1所需時間為6天，因此，我們得出總的完成專案時間為15+5+6=26（天）。 表3 1 特璇 0 卡爾 1 邁克孟德回 2 5 3 3 2 回 0 7.6.1 求出直線的最小數目有時候最少需要多少條直線才能覆蓋所有的行列中的0，答案不明顯。在這些例子中，以下的選代是很有效的。選擇任意一個只有一個0的行或者列，如果它是行，畫一條直線穿過這個0所在的列； 如果它是列，則畫一條直線穿過這個0所在的行。如此繼續下去，直到覆蓋了所有的0。 如果你在這個最小直線數目上錯誤地畫了太多的直線，並錯誤地認為已經找到了最優解，那麼你將不能識別一個0價值的分配。這樣的話，如果你認為已經找到了最優解但是沒能找到一組0價值的分配，則需要返回上面一步並檢查是否能用更少的線來覆蓋所有的0。 7.6.2 問題的變化現在我們討論如何用匈牙利法來處理下面這些變化了的問題： 1.總的代理數不等於總的任務數。 2. 目標函式最大化。 3. 不可接受的分配。 總的代理數不等於總的任務數匈牙利法需要行（代理）列（任務）數相等。假設在福爾公司問題中，有4個專案負責人可以分配給3個客戶（專案）。福爾公司面對的問題仍然一樣，還是如何分
206 資料、模型與決策：管理科學篇配負責人使得總的完成專案所需時間最短。表7-27是這4個負責人完成每個專案時間的估計。 表7-27 福爾公司指派問題中的4個負責人的專案完成時間的估計 （單位：天） 客戶專案負責人專案負責人表7-28 福爾公司問題中帶虛擬客戶的專案完成時間的估計害戶 3 特瑞卡爾邁克盂德海利 1 10 9 6 8 2 15 18 3 9 5 14 16 6 特瑙卡爾邁克孟德海利 1 10 9 6 8 2 15 18 14 16 D K 9 5 3 6 0 0 0 0 廬擬客戶我們知道在行列數相等的時候如何應用匈牙利法來解決指派問題，不相等的情況下，如果是代理多，我們就增加一個虛擬的客戶，如果是客戶多，我們就增加一個虛擬的代理，然後用同樣的程式解決指派問題。這個虛擬的客戶或者代理是不存在的。所以最優解中分配給這個虛擬客戶的專案負責人實際上並沒有指派。 那麼對於這個虛擬的列（客戶），我們估計每個負責人完成專案所需的時間為多少呢？這個虛擬客戶的分配實際上是不會發生的，也就是說完成時間為0。表7-28是帶虛擬客戶的福爾公司指派問題，這個虛擬客戶稱為D（本章後面的問題第42題請要求用匈牙利法計算這個問題的最優解）。 注意，如果我們考慮的是4個客戶只有3個專案負責人的情況，先要增加一個虛擬的行（虛擬的專案負責人），這樣才能用匈牙利法解決這個問題。客戶接受到的虛擬負責人，實際上由於缺人沒有立即被分配專案負責人，客戶要等一段時間才可能被分配負責人。為了能夠與求解演算法相容，我們可以增加虛擬的行或者列，但是它們不能同時增加。 目標最大化為了揭示最大化指派問題，讓我們考忠索爾斯伯利•帝斯康特有限公司管理層面臨的問題。設想公司剛租用了一個新店鋪，正試圖決定在店鋪內如何安置各個部門。店鋪經理有4個空地還沒有表7-29 針對每個部門在每個空地的預計年盈利 （單位：1000美元） 空地分配部門，正在考慮5個部門應該怎樣分配到這4個部門 1 空地上。這5個部門是：鞋、玩具、機動部件、家庭用品和錄影裝置。對剩餘部分的佈局進行仔細的研究之後，店鋪經理針對每一個部門在每一個點每年可能的盈利做了估計，這些估計值顯示在表7-29中。 這個分配需要目標最大化，然而問題是行比列鞋玩具機動部件家庭用品錄影裝置 10 15 17 14 14 2 6 18 10 12 16 3 4 12 5 13 13 6 8 11 16 10 12 多。因此，為了應用匈牙利法解決這個問題，我們必須增加一個虛擬的列，對應一個虛擬的空地。增加一個虛擬列後，我們得到一個5x5 的指派問題，如表 7-30所示。 透過轉換矩陣中所有元素為機會損失，我們可以得到同等的最小化指派問題。我們用每一列中的最大部門元素減去列中的每一個元素即可。透過找到最小化機會損失的分配，我們可以得到與最初的最大化指派問 4 8 題中價值同樣的最優分配。這樣，我們只要把分配矩陣換成元素的機會損失，那麼任何一個最大化指派問題都可以轉化為最小化指派問題。因此，我們構建一個每個元素都代表沒有做出最佳分配的機會損失的分鞋玩具機動部件家用品錄影裝置表7-30 包含一個虛擬空地的針對每個部門在每個空地的預計年盈利 （單位：1000美元） 空地 3 12 s 13 13 6 虛擬地點 1 2 10 6 15 18 17 10 14 12 14 16 0 o 16 10 12 o 0
第了章運輸、指派與轉運問題 207 配矩陣後，就可以解決這個最大化指派問題了。表7-31是這一步操作之後的機會損失表。 在空地1分配鞋店而造成的機會損失是 7000美元，也就是說如果我們放置鞋店而不是最佳的機動部件部門在空地1上，我們就會丟失額外創收7000美元的機會。而放置玩具部門在部門空地2引起的機會損失為0，因為它在那個空地 5 創收的利潤最高。那麼虛擬列對應的機會損失為鞋多少呢？分配部門到虛擬的空地意味著這個部門玩具因為空地不夠沒有被分配。所有部門在這個虛擬機動部件表7-31 每個部門一空地組合的機會損失 （單位：1000美元） 空地 3 1 8 o 虛擬地，點空地的年盈利都一樣為0，這樣每個部門的機會家寲用品損失都為0了。 錄影裝置 1 7 2 0 3 3 2 12 4 8 0 8 6 2 0 0 透過匈牙利法的第一、二、三步處理後，得7 4 到最小化機會損失及最大利潤的分配，見表7-31。 不可接受的分配為了描述我們如何處理不可接受的分配情形，我們假設在索爾斯伯利•蒂斯康特公司的指派問題中，店鋪經理認為玩具部門不應該被安置在空地2上，並且機動部件部門也不應該被安置在空地4上。店鋪經理說：基於其他的考慮，如地點的大小、鄰近的店面等，這兩種分配都是不可接受的。 用我們解決運輸問題中的指派問題的方法， 我們在最小化指派問題中定義M為不可接受分表7-32 對部門一空地組合的預計盈利 （單位：1000美元） 配的機會損失。在最大化分配中，我們定義—M 為不可接受分配的盈利。事實上，我們認定M 鬱門為無限大，所以M無論是增加了還是減少了多少，還是無限大的。這樣，在分配矩陣中，帶M 值的單元格在矩陣減少計算中始終保持值不變， 即帶M值的單元格的值不會為0。 在表7-32 中顯示了有兩個不可接受分配的鞋玩具機動部件家庭用品錄影裝置 1 10 15 17 14 14 2 6 -M 10 zI 16 3 12 s 13 13 6 4 8 1］ -M 10 12 5 0 索爾斯伯利•蒂斯康特公司問題，當這個分配矩陣被轉換為機會損失矩陣時，-M的盈利會變成M。 本章小結在這一章中，我們介紹了運輸問題、指派問題和轉運問題。這3種型別的問題都屬於稱為網路流量問題的線性規劃的一種特殊形式。一個運輸問題的網路模式包括一組起點節點和一組終點節點。在基本模型中，弧代表從每個起點到每個終點的路線，每個起點有一個供給，每個終點有一個需求，模型的基本目的就在於確定從每一個起點到每一個終點運輸的最最佳化的量。 指派模式是運輸模式的一個特例子，其中所有的需求和供給值都等於1，我們把每一個代理都表示為一個起點節點，而每一項任務都表示為終點節點。轉運模型是運輸模型向指派問題的一個擴展，這個模型包括中間轉運節點。在更為通用的模型中，我們允許任意兩個節點之間都可能存在弧。 轉運問題的一種變化就是弧上有運輸容量限制，我們稱其為容量轉運問題，這在網路模型文獻中被稱為純網路同題。 這一章中，我們還闡述了每一個網路流量問題是如何透過線性規劃建模的，並用通用的線性規劃軟體包求解了這些模型。然而許多實際生活中，網路流量模型的應用都會導致一般目的的線性規劃軟件包無法有效求解的大型問題。運輸單純形法被看做是一個有效的解決這類問題的方法。針對大規模的運輸問題和轉運問題，運輸單純形法的求解過程和轉運問題的擴充套件比那些通用的單純形法要快成百上幹倍。匈牙利法被看做是轉運問題的特目標的求解工具。
208 資料、模型與決策：管理科學篇在網路流量問題中，只要所有的供給和需求是完整的，那麼最優解也是完整的。因此，在解決任何供給和需求都是完整的運輸、轉運和指派問題時，我們便可能找到完整價值的解。 專業術語 transportation problem 運輸問題一種網路流問題，經常涉及到從一系列的起點到終點最小化運輸成本問題。 這類問題可以用線性規劃來建模和求解，其中每一條弧代表一個線性規劃模型中的變數，網路模型中的每個節點都對應著線性規劃模型中的一個約束條件。 network 網路圖一個問題的網路圖示，它包含標有數字的圓圈（代表節點）和連線節點的直線（弧）；弧上的箭頭表示流量的方向。運輸、轉運和指派問題都是網路流問題。 nodes 節點網路中的交叉點或者連線點。 arcs 弧網路中連線節點的線。 capacitated Transportation problem 有容量限制的運輸問題一些或者所有曲線有容量限制的運輸問題的一種變化形式。 assignment problem 指派問題是指給代理分配任務的網路流問題；可以用線性規劃建模，是一種特的運輸問題。 transshipment problem 轉運問題從運輸問題到指派問題的一種延伸，它包含轉運節點和任意兩個節點之間可能出現的貨物運輸。 capacitated transshipment problem 有容量限制的轉運問題一些或者所有弧有運輸容量限制的轉運問題。 transportation simplex method 運輸單純形法為解決運輸問題的一個帶特殊目標的求解過程。 transportation tableau 運輸表用以表示運輸問題的表，其中，各個單元格與相應的變數或弧對應。 heuristic 啟發式快速尋找問題的初始可行解的一個常識性的過程。啟發式常用於尋找運輸單純形法的初始可行解或者其他方面。 minimum cost method 成本最小化法用於尋找運輸問題初始可行解的一種啟發式演算法；這種方法用起來很方便且得出的初始可行解比較好（非最優）。 incoming arc 入弧沒有被使用的弧（代表運輸表中未佔用單元格）且在運輸單純形法每一次迭代中被分配流量的弧。 outgoing arc 出弧在運輸單純形法每一次迭代中被拋棄的弧（從已佔用單元格中選出）。 MODl method MODI 法在運輸單純形法中確定人弧的一種修正分配法。 net evaluation index 淨評估指數在運輸單純形法中，給未使用弧分配流量而引起的目標函式的單位變化。 stepping-stone method 臺階法在運輸單純形法的選代中，當流量被分配到一條未使用弧上時，運用已佔用單元格的序列或路徑找出必要的調整流量。這個步驟能夠確定出弧。 degenerate solution 退化解運輸問題的一種解，其中有正流量的弧少於m+n-1 條；m代表起點數目，幾代表終點數目。 dummy destination 盧擬終點運輸問題中當總需求小於總供給時加人的終點，其目的是為了使總的供給等於總需求。增加的虛擬終點數目等於總供給節點和總需求節點之差。 dummy origin 虛擬起點運輸問題中當總需求大於總供給時加入的起點節點，代表虛擬的供給，使得總需求等於總供給。增加的虛擬起點的數目等於總需求減去總供給之差。 hungarian method 飼牙利法解決指派問題的一種特殊求解過程。 opportunity loss 機會損失指派矩陣的每一個單元格所在列的最大值與該單元格值之差。指派矩陣單元格中的值必須轉為機會損失，才能用匈牙利法來解決最大化指派問題。 問題注意：第1~32 題可以運用多種解決方法。在大多數情況下，題目要求用線性規則來構建和求解問題。當解決方法沒有明確指出時，可以用管理科學家軟體中的運輸或者分配模組或者一些其他軟體包求解。第 33~45 題要求用第7.5節和第7.6 節介紹的特辣目的演算法來求解。頭32 道題中的許多問題也可以用這些特珠目的演算法。 2. 考慮下面這個運輸問題的網路模型：
第7章運輸、指派與轉運問題 209 得梅因 25 30傑斐遜城堪薩斯城 15 20 奧馬哈聖路易期 10 供給需求此網路圖註明了每個節點的供給量和需求量以及單位運輸成本。 a. 為這個問題構建一個線性規劃模型，記得在模型中定義所有的變數。 b. 求解這個線性規劃模型，找出最優解。 4. 某種產品在3個不同的工廠生產後被運輸到3個不同的倉庫（下表顯示了每件的運輸成本），相關信倉息如表4。 工廠 a.設計一個網路模型來求解這個問題。 P， b.設計一個線性規劃模型，該模型的目標是最小化總運輸成本；求解最低成本方案。 c.假設表中的資料表示在工廠；生產出來的運到倉庫j的每件產品的利潤，你在（b）部分所建 P 倉庫需求 W， 20 10 12 200 表4 We 16 10 18 400 庫工廠生產能力 Ws 24 8 10 300 300 500 100 的模型該如何變動？ 6.呵挪富製造商生產中央處理器（CPU），這些CPU是在西雅圖、哥倫比亞和紐約生產的，並被運到位於匹茲堡、 莫比爾、丹佛市、洛杉磯和華盛頓市的倉庫中，以等待進一步的銷售。以下所示的運輸表顯示了每一工廠所能提供的CPU 數量。同時，每個單元格中的資料表示由生產地運到每個倉庫的單位運輸成本（美元/單位）。 倉庫匹茲堡 10 莫比爾 20 丹佛市 5 洛杉磯 9 華盛頓 10 供紿擸西雅閣 9000 2 10 8 30 6 哥倫比亞 4000 1 20 7 10 4 紐約 8000 需求肚 3000 5000 4000 6000 3000 21000 a.設計一個表示該問題的網路圖。 b.確定每個工廠運送多少貨物到每個倉庫中去，使得總的運輸成本最低。 c.匹茲堡倉庫新近增加了1000個單位的訂單，且阿挪富已授權匹茲堡工廠增加1000個單位的生產量。這一變化將導致總運輸成本增加還是減少？請求出一個新的最佳解決方案。
210 資料、模型與決策：管理科學篇 8.克雷爾化工公司生產一種特殊的油基原料。最近此原料非常短缺，克雷爾公司的4個客戶已經下了訂單， 總額超過了克雷爾公司旗下的兩個工廠的生產能力。克雷爾公司的管理層要決定給每個客戶多少單客戶工廠位的原料。因為這4 個客戶屬於不同的行業，所以基於行業的價格結恟不同，可以向它們收取不同的原料價格。然而、兩個工廠的生產成本不同，工廠克利夫•斯普林丹威爾 ＄32 $34 D $34 $30 Ds $32 ＄28 $40 ＄38 與客戶之間的運輸成本也不同，所以，這使得“賣給最高出價者”的決策並不可取。綜合考慮價格、生產成本和運輸成本之後，克雷爾公司計算出下表中所示的每個I廠一客戶組合中每單位原材料的利潤率。工廠的生產能力以及客戶的訂單如下所示： 工廠的生產能力（單位） 客戶的訂單（單位） D，2000 克利夫 •斯普林 5 000 D：5000 丹威爾 3 000 D：3000 D.2000 為了最大化公司利潤，每個工廠給每個客戶提供多少單位的產品？哪個客戶的需求將不被滿足？構建網路模型和線性規劃模型。 10. Ace 製造公司收到3種相似產品的訂單： 產品訂單（單位） A B C 2000 500 1 200 該公司有3套裝置可以以同樣的生產率製造這些產品。然而，由於每套裝置生產產品的次品率不同， 所以產品的單位成本也不同。裝置下個星期的生產能力以及單位生產成本如下所示： 裝置 1 2 3 生產能力（單位） 裝置產品A 1 500 1 $1.00 1 500 2 $1.30 1000 3 $1.10 產品B $1.20 $1.40 $1.00 產品C $0.90 $61.20 $1.20 構建和求解線性規劃模型，並由此得出產品和裝置的生產成本最低的分配方案。 12. 斯科特是一家會計公司，它有3個客戶，專案負責人將被分配到這3個客戶中去。基於負責人的不同背景和經歷，不同的負責人一客戶分配將有不同的專案完成時間。所有可能的分配和預計的專案完成時間如下； 專案負責人 1 傑克遜 10 愛麗斯 14 史密斯 22 2 16 22 24 3 32 40 34 日.改計一個表述該問題的網路圖。 b. 構建該問題的線性規劃模型並求解，並求出總的時間需求為多少。 14.地毯安裝公司為金融大廈銷售和安裝地毯。布拉德是這家公司的業務主管，他剛剛獲得5個專案的合同， 現在必須給每個專案分配一組工作人員。因為布拉德所獲得的佣金取決於地毯安裝公司的利潤，他將決定如何分配以使得總的安裝成本最小。目前，有5個安裝小組可以被分配，每個小組用顏色來編號。下面這個表格顯示了每個小組完成每個專案所需要的時間：
第7章運輸、指派與轉運問題 211 項目紅色白色小組藍色綠色櫬色 1 30 25 23 26 26 2 44 32 40 38 34 3 38 45 37 37 44 4 47 44 39 45 43 5 31 25 29 28 28 a.設計一個表述該問題的網路圖。 b.構建一個該問題的線性規劃模型，並求解得出使總成本最小的最優解。 16.a. 利用估計的年盈利資料（見表7-29），設計一個解決索爾斯伯利•蒂斯康特公司部門一空地組合問題的網路模型。 b.內建一個線性規劃模型，求解模型，得出使得利潤最大化的部門一空地分配。 18. 美國電纜公司利用包括5個分銷中心、8個客戶區域的分銷系統分銷產品。配給每個客戶區域一個專門的資源供應商，且其所有電纜產品都來自同一分銷中心。為了能平衡分銷中心的客戶需求和僱員的工作量， 公司負責物流的副總裁特別指明一個分銷中心最多負責3個客戶區。下面的表格就是這5個分銷中心以及每個客戶區的供給成本（單位：1000美元）： 日.求出能使總成本最小的客戶區一分銷中心的組合方式。 b.如果有，哪一分銷中心沒有分派任務？？假設每個分銷中心最多隻能負責2個客戶區，那麼這個限制條件將如何改變指派和客戶區的供給成本？ 客戶區分銷中心洛杉磯芝加哥哥倫比亞亞特蘭大普萊諾 70 47 22 53 納什維爾 75 38 19 58 弗拉各斯塔夫 15 78 37 82 斯普林菲爾德 60 23 8 39 博爾德 45 40 29 75 紐納 98 90 11 82 86 堪薩斯丹佛 21 27 34 40 40 29 36 32 25 11 達拉斯 13 26 32 45 37 20. 美國中西部大學的管理科學系主任計劃在下一個秋季給每門課分配教授。4門核心課程需要分配數授，分別是UG、MBA、MS 和 Ph. D水平的課程。有4 課程位教授可以被分配，每位教授只接一門課。已知前教授一個學期學生對教授的評價分5個等級：4（優秀）、3（好）、2（一般）、1（及格）、0（不及格）。每個教授的平均得分如右表。 教授D沒有獲得博士學位，因此不能教授 A B c D uG 2.8 3.2 3.3 3.2 MBA MS 2.2 3.3 3.0 3.6 3.2 3.5 Ph.D水平的學生，所以D一Ph.D這個組合是不可 2.8 2.5 Ph. D. 3.0 3.6 3.5 一接受的。如果系主任基於最大化4門課總的學生評價來分配教學任務的話，那麼該如何分配教授？ 22. 海齊公司的5個部門在生產過程中使用一種叫 Rbase 的化學物質，這種物質只有6個供應商能夠滿足海齊公司的質量控制標準。所有6家供應商都可以生產足夠的 Rbase 滿足海齊公司任一部門的需求。下表顯示了海齊公司不同部門對Rbase 的需求量，以及不同供應商每加侖 Rbase 的報價： 部門需求量（1000加侖） 供應商 1 40 2 3 4 5 45 2 3 SO 4 35 s 45 6 每加侖單價（$） 12.60 14.00 10.20 14.20 12.00 13.00 下表顯示了從不同供應商到不同部門的每加侖Rbase 的運輸成本（單位：美元）：
212 資料、樸型與決策：管理科學篇供應商部門 1 2 3 4 5 1 2.75 2.50 3.15 2.80 2.75 2 0.80 0.20 5.40 1.20 3.40 3 4.70 2.60 5.30 2.80 6.00 4 2.60 1.80 4.40 2.40 5.00 5 3.40 0.40 5.00 1.20 2.60 6 2.75 1∞0 •5.60 2.80 3.60 海齊公司堅信，將其採購分散給不同的供應商會減輕公司對供應商的依賴（例如，供應商發生罷工或者原材料短缺都不會對公司造成太大的影響）。公司的這種政策需要每個部門都必須有一個獨立的供應商。 8.對每組供應商一部門組合，計算出滿足部門需求的總供給成本為多少？ b.得出最優的供應商一部門指派。 24.參考第23題。假設兩個倉庫之間的運輸成本被限制在每單位2美元，且直接從工廠3運輸到客戶區4的單位成本為7美元。 a. 設計該問題的網路圖。 b.構建該問題的線性規劃模型。 c•求解最優的運輸方案。 26.阿帝挪貝克造紙集團在緬的奧古斯塔、紐約的塔珀湖分別有一家造紙廠。公司倉庫位於紐約的奧爾巴尼和新漢普頓的樸獲茅斯。分銷商分佈在波士頓、紐約和費城。造紙廠下個月的生產量和分銷商下個月的需求意如下表所示： 工廠奧古斯塔塔珀糊生產量（箱） 300 100 分銷商' 波士頓紐約費城需求量（箱） 150 100 150 從兩個工廠到兩個倉庫之間的單位運輸成本（$）和從兩個倉庫到3個分銷商之間的單位運輸成本 （單位：美元）如下所示： 倉庫工廠奧爾巴尼朴茨茅斯倉串奧古斯塔 7 5 波士頓 8 塔珀湖 3 4 奧爾巴尼朴茨茅斯倉庫紐約 5 6 費城一 10 a.畫出表述阿帝挪貝克造紙集團轉運問題的網路圖。 b.構建阿帝挪貝克造紙集團轉運問題的線性規劃模型。 c.求解模型，得出這個問題的成本最小化運輸方案。 28. 審爾•哈曼公司正在從事穀類買賣業務。該公司此業務一個非常重要的方面就是把買來的穀物運送到客戶手中。如果公司能夠保持低水平的運輸費用，那麼公司的利潤將會提高。 目前，公司在印第安納州的曼西和巴西城各買了3車皮和6車皮的穀物，在俄亥俄州的齊尼亞購買了5車皮的穀物。公司已經銷售出去12 車皮的穀物。各地區名字以及在該地區銷售出去的數量如地點梅肯，喬治亞州格林伍德，南卡羅來納州康科德，南卡羅來納州查塔姆，北卡羅來納州銷售車皮數 2 4 3 3 右表所示。 所有裝運的貨物都必須取道路易斯維爾或辛辛那提運往目的地。下表所示的是從起點到路易斯維爾和辛辛那提的每蒲式耳的運輸費用（單位：美分），以及從路易斯維爾和辛辛那提到目的地的每蒲式耳運輸費用（單位：美分）。
第7章運輸、指派與轉運問題 213 到達起點曼西巴西城齊尼亞起點路易斯維爾辛辛那提路易斯維爾 8 3 9 到辛辛那提 6 8 3 達從曼西到辛辛那提的每蒲式耳運費是6美分梅肯 44 57 袼林伍德 34 35 康科德 34 28 查塔姍 32 24 從辛辛那提到格林伍德的每蒲式耳運費是35 美分。 制定一個運輸方案，使得總的運輸成本在滿足所有需求的基礎上最小。哪些車皮的穀物（若有的話） 需要留在起始節點等待被賣出。 30.下面是一個轉運問題的線性規劃模型： min 11xs + 12xg4 + 10x21 + 8xga + 10xss + 11xa2 + 9xas + 12xs2 s.t. xs+ M4X21 X21 X42 X13 -X14 Xg4一 X34 Xss + Xss X42+ Xas + Xas- ≤5 Xs2 ≤3 =6 ≤2 Xsz =4 x≥0，對所有的i，； 設計該問題的網路模型。 32. 佛羅里達州那不勒斯市的Sanders 漁業供應公司生產一系列的漁具，這些產品銷往整個美國。公司預計3 種特產品下3個月的需求分別為150、250 和300個單位，Sanders公司可以透過正常生產或者加班來滿足這些需求。因為還有其他的訂貨要求，所以預計下3個月的生產成本會增加。生產能力（單位）以及單位生產成本如表5所示。 表5 庫存量可以從這個月留到下個月，但是每個月的庫存單位成本為20（美元）。例如，正常狀態下1月份生產出來的滿足2月的需求的產品單位成本為：50+20=70（美元）。同樣，1月生產出來滿足3月需求的產品的單位成本為50+2x 20=90（美元）。 日，把這個問題看成一個運輸問題，設計表述該生生產狀態 1月—常態 1月—超時 2月一常態 2月——加班 3月—常態 3月—加班生產能力 275 100 200 S0 100 50 單位成本（$） S0 80 S0 80 60 100 產安排向題的網路模型。（提示：用6個起始節點，起始節點1的最大供給量是它能在常態下生產的最大量）。 b.設計一個線性規劃模型，用它來安排下3個月的常態下的生產和超時加班的生產。 c•生產如何安排？每月存貨為多少單位？總成本為多少？ d.還有空閒的生產能力嗎？如果有，在哪裡？ 注：下面的問題涉及到在第7.5 節和第7.6節中描述的特殊目標的演算法的使用，這些演算法用於求解運輸問題和轉運問題。 34. 考慮下面的成本最小化運輸問題。
214 資料、模型與決策：管理科學篇 a. 用成本最小化法找出初始可行解。 b.用運輸單純形法找出最優解。 c•如果你必須從圖森運100單位產品到聖地亞哥，那麼這個最優解有什麼變化？ d.由於道路施T問題，拉斯維加斯一條地亞哥的路線現在不可接受，重新求解這個問題。 起點洛杉磯 4 舉喬斯舊金山聖地業哥供給 10 ［6 100 8 L16 L6 拉斯維加斯 300 14 ［18 Lo 圖森 300 200 300 200 1700 36.參見第4題，用運輸單純形法找出最優解。 38. 用表7-15中末佔用單元格每單位成本的變化回答下面的問題。 a. 考思連線貝德福德和芝加哥的略線，把它當做入弧的候選弧。分配一單位產品給這條弧，為保證可行性，用臺階法做必要的修改。計算新解決方案的值，並顯示由每單位成本變化帶來的價值變化，這種成本的變化透過 MODI方法獲得。 b.對弧約克一萊剋星頓重複（a）過程。 40.參見第12題，用匈牙利法求解最優解決方案。 42. 參見第15題，用創牙利法求解最優解決方案。 44.用匈牙利法解決第17題中的索爾斯伯利•帝斯康特公司的問題。 案例問題分銷系統設計大比公司是一家電力消耗測量儀的製造商和銷售商，該公司在埃爾帕索以一間小型工廠起家，逐漸建立起了一個遍及得克薩斯州的客戶基地。它的第一個分銷中心在得克薩斯的沃斯，然後業務又擴充套件到北方，第二個分銷中心在新墨西哥州的聖菲建立。 公司在亞利桑那州、加利福尼亞州、內華達州和猶他州開啟了測量儀市場，埃爾帕索加工廠隨著得以擴大。隨著西部海岸線沿岸業務的發展，大比公司在拉斯維加斯建立了第三個分銷中心。就在兩年前，又在加利福尼亞州的聖伯納迪諾建立了第二家生產工廠。 不同生產工廠的製造成本是不同的，在埃爾帕索加工廠生產出來的產品單位成本為10.50美元，聖伯納迪諾工廠生產的測量儀單位成本比埃爾帕索加工廠的低0.50美元。 公司的快速增長意味著沒有太多的精力去提高分銷系統的效率。大比公司管理層決定現在把這個問題提到日程上來。表7-33顯示了從兩個工廠運輸一臺測量儀到3個分銷中心的單位成本。 表7-33 從工廠到分銷中心的單位運輸成本 （單位：美元） 分銷中心加工廠埃爾帕索蚤伯納迪諾沃斯 3.20 - 蚤菲 2.20 3.90 拉斯維加斯 4.20 1.20 埃爾帕索加工廠的季度生產能力為30000臺測量儀，聖伯納迪諾加工廠的季度生產能力為20000臺。注意，從聖伯納迪諾加工廠到在得克薩斯的沃斯分銷中心之間的運輸是不被允許的。 這3個分銷中心要負責9個客戶區的需求。預計下季度的每個客戶區的需求量如表7-34所示。 從每個分銷中心到每個客戶區之間的單位運輸成本在表7-35中給定。注意：有些分銷中心是不可以服務某第7章運輸、指派與轉運問題 215 特定的客戶區的。 在日前分銷系統下，達拉斯、聖安東尼奧、威齊託和堪薩斯城的客戶區需求是透過沃斯分銷中心來滿足的。同樣，聖菲銷售中心為丹佛市、鹽湖城和鳳凰城提供服務；拉斯維加斯分銷中心滿足洛杉磯和聖地亞哥客戶區的需求。 客戶區達拉斯聖安東尼與威齊託堪薩斯城丹佛需求（測最儀） 6 300 4 880 2 130 1 210 6 120 表7-34 季度需求預測客戶區鹽溯城鳳凰城洛杉磯聖地亞哥需求（測最儀） 4 830 2750 8580 4 460 分銷中心達拉斯 0.3 表7-35 分銷中心到顧客區之間的單位運輸成本顧客區聖安東尼奧威齊託堪薩斯城丹佛鹽湖城 2.1 3.1 6.0 （單位：美元） 鳳麗城洛杉磯聖地亞哥沃斯聖菲拉斯維加斯 5. 2 5.4 4.5 4.4 6.0 2.7 5.4 4.7 3.3 3.4 3.3 2.4 2.1 2.7 2.5 管理報告請對改進該分銷系統提出建議。你的報告應該考慮下面的兒個問題： 1.如果公司不改變當前的分銷戰略，那麼下季度的製造和分銷成本為多少？ 2. 假設公司將考慮放鬆當前對分銷中心的限制；也就是說，客戶可以從任何一個分銷中心訂貨。這樣，分銷成本是不是會降低？降低多少？ 3.該公司希望能從加工廠直接為某些客戶提供銷售服務。特別是聖伯納迪諾加工廠到洛杉磯客戶區的運輸成本為0.30美元，從聖伯納迪諾到聖地亞謝的單位運輸成本為0.70美元。直接從埃爾帕索加工廠到聖安東尼奧客戶區的單位運輸成本為3.50美元。在考慮了這些直接運到客戶區的路線之後，分銷成本是不是會減少很多呢？ 4. 經過5年的發展之後，大比公司開始以穩健的速度增長（5000臺測量儀），業務延伸到了北方和西方。 你是否會建議它在這個時候考慮擴建工廠呢？ 附錄7A運輸、指派與轉運問題的 Excel 解本附錄中，我們將介紹如何用 Excel Solver 來解決運輸、指派和轉運問題。我們以福斯特公司的問題為例 （見7.1節）。 7A.1 運輸問題第一步，在工作表的頂端部分輸入運輸成本、起點節點供給量和終點節點需求量。然後在工作表的底端構建這個問題的線性規劃模型。所有的線性規劃模型都包含4個要素：決策變數、目標函式、左端值約束條件以及右端值約束條件。對於一個運輸問題，決策變數個數等於從起點節點到終點節點所有可能的連線弧數；目標函式是總運輸成本最小化；左端值為從每個起點節點運出的貨物量和運人每個終點節點的貨物量；右端值為每個起點節點的供給量和每個終點節點的需求量。 福斯特公司問題的模型和最終解都列在圖7-14上，資料在工作表的頂部，模型出現在工作表的底部；關鍵元素都被塗上了陰影。 7A. 1.1 模型 A1:F8 單元格描述了所有資料和描述性標誌，運輸成本在單元格 B5:E7，起點節點供給資料在單元格 F5: F7，終點節點的需求在單元格B8:E8。Excel Solver 需要的4個模型關鍵因素為：決策變數、目標函式、左端值約束條件和右端值約束條件。這些都在工作表的底部，並被塗上了陰影。
216 資料、模型與決策：管理科學篇決策變鬣 B17:E19 單元格是為決策變數保留的。最優值顯示為x=3 500，X： = 1 500， 422 =2 500，*23 =2000，*z =1 500， *a1 =2 500。所有其他決策變數都等於0，也就是說這些變數對應的弧上沒有流量。 福斯特發電機起點克利大蘭貝德福德約克需求波士頓 3 7 2 6000 模型終芝加哥 2 5 5 4000 點聖路易斯|萊剋星頓 7 2 4 2000 6 3 5 1500 供給 5000 6000 2500 最小成本波士頓終芝加哥起點克利大” 貝德福德約克總計點聖路易斯菜剋星頓總計八約 6000 圖7-14 福斯特公司問題的 Excel 求解目標函式在單元格C13 中輸人公式=SUM PRODUCT （B5: E7,B17:E19），用來計算每個解的總運輸成本。最小運輸成本為39 500美元。 左端億單元格 F17:F19為左端值供給約束條件，單元格 D20:E20是左端值需求約束條件。 單元格 F17= SUM（B17:E17）（複製到 F18:F19） 單元格 B20 = SUM（B17:B19）（複製到C20:E20） 右端儢單元格 H17:H19為右端值供給約束條件，單元格 B22:E22 為右端值需求約束條件。 單元格 H17= F5（複製到H17:H19） 單元格 B22 =B8（複製到C22:E22） 7A. 1.2 Excel 的解決方案圖7-14中的解決方案是透過選擇“工具欄（Tools）”下面的“解決（Solver）”得到 $8$17:E$19 的，在 Solver Parameters 對話方塊中輸人正確的 tenderd Simplex UP 值，並選擇標準“單純線性規劃（Stadard $B$20：$E$20 = $B$22:4E$22 $F$17：$F＄19 <= $-$17：$-$$19 Simplex LP）”，指定選項“假設非負”（A8sume Non-Negative），然後確認單擊“解決” （Solver）。圖7-15 是 Solver Parameters 對話方塊中輸人的資訊。 圖7-15 Solver Parameters 對話方塊中 7A.2 指派問題輸入的福斯特公司問題的資訊第一步，在工作表的頂部輸人指派成本資料。將指派問題看成運輸問題的一個特例，沒有必要輸人起點節點的供給量和終點節點的需求量，因為這些數值都等於1。 在工作表底部列出該問題的線性規劃模型。跟所有線性規劃模型一樣，它有4個關鍵元素：決策變數、目標函式、左端值約束條件和右端值約束條件。對於轉運問題，決策變數代表著代理是否被指派給任務（1代表