數(shù)據(jù)、模型與決策（原書第16版）課件 第6章、分配與網絡模型

AnIntroductiontoManagementScience,16e第六章、分配與網絡模型章節(jié)內容6-1 供應鏈模型6-2 指派問題6-3 最短路徑問題6-4 最大流問題6-5 生產和庫存應用章節(jié)目標完成本章后，你將能夠:LO6.1

建立并求解運輸問題的網絡和線性規(guī)劃模型LO6.2 建立并求解指派問題的網絡和線性規(guī)劃模型LO6.3 建立并求解轉運問題的網絡和線性規(guī)劃模型LO6.4 建立并求解最短路徑問題的網絡和線性規(guī)劃模型LO6.5 建立并求解最大流問題的網絡和線性規(guī)劃模型介紹本章討論的模型屬于一類特殊的線性規(guī)劃問題，通常被稱為網絡流問題。網絡流問題包括供應鏈管理中常見的運輸問題和轉運問題，和其他三種類型：指派問題

、最短路徑問題和最大流問題。在每一個問題中，我們將以網絡的形式建立問題的圖解模型，然后說明每個問題是怎樣被構建成線性規(guī)劃模型并進行求解的。6-1供應鏈模型：運輸問題供應鏈供應鏈是一個產品從生產到分銷涉及的所有相互聯(lián)系的資源集合。一般來說，供應鏈的設計目標是以最小的成本滿足顧客對某種產品的需求?？刂乒湹闹黧w必須做出很多決策，比如在哪里生產產品、生產多少產品、在哪里銷售產品。我們將會介紹兩種在供應鏈模型中普遍存在，并且可以使用線性規(guī)劃解決的問題：運輸問題轉運問題運輸問題運輸問題經常出現(xiàn)在規(guī)劃貨物從某些供應地區(qū)到達某些需求地區(qū)之間的配送服務中。通常，每個供應地區(qū)（起點）可提供的貨物量是有限的，并且每個需求地區(qū)（終點）的貨物需求的已知的。運輸問題中常見的目標是要使貨物從起點到終點的運輸總成本最低。現(xiàn)在我們考慮福斯特發(fā)電機公司面臨的運輸問題——將產品從3個工廠運輸?shù)?個配送中心。6-1福斯特發(fā)電機公司：運輸問題供給福斯特發(fā)電機公司希望確定應該從每個加工廠運輸多少產品量到每個配送中心。福斯特發(fā)電機公司在俄亥俄州的克利夫蘭、印第安納州的貝德福德和賓夕法尼亞州的約克有3個加工廠。某一特殊型號的發(fā)電機在今后3個月的計劃期內的生產能力如下：需求公司通過位于波士頓、芝加哥、圣路易斯和萊克星頓的4個配送中心來配送這種發(fā)電機。每個配送中心這3個月的需求預測如下：6-1福斯特發(fā)電機公司：網絡表示（網絡圖）右圖顯示了福斯特可以用的12條配送路線。供給量寫在每個起始節(jié)點的左側，需求量寫在每個目的節(jié)點的右側。每個起點和終點都由節(jié)點表示；每個可能的運輸路線都由弧表示，每條弧都表示出了每條路線上每件貨物的運輸成本。從起始節(jié)點到目的節(jié)點之間運輸?shù)呢浳锪勘硎玖诉@個網絡中的流量。（流向用箭頭表示）福斯特發(fā)電機公司的這個運輸問題的目標是決定要使用哪些線路以及通過每條線路的流量，使總運輸成本最小。6-1福斯特發(fā)電機公司：問題表達方法決策變量

目標函數(shù)

6-1福斯特發(fā)電機公司：約束條件供給

需求

6-1福斯特發(fā)電機公司：完整的LP模型聯(lián)合目標函數(shù)和這些約束條件構成了一個線性規(guī)劃模型，這個福斯特發(fā)電機公司運輸問題是一個含有12個變量和7個約束的線性規(guī)劃模型：s.t.6-1福斯特發(fā)電機公司：結果與解釋福斯特發(fā)電機公司問題的最優(yōu)目標函數(shù)值和最優(yōu)決策變量如右圖所示，其中，最小的總運輸成本為39500美元。該圖表總結了網絡圖的最優(yōu)解，決策變量的值顯示了每條線路運輸?shù)淖顑?yōu)運輸量。例如，應當將3500個單位的發(fā)電機從克利夫蘭運輸?shù)讲ㄊ款D，應當將1500個單位的發(fā)電機從克利夫蘭運輸?shù)街ゼ痈纭?-1運輸問題：一般化的LP模型

6-1供應鏈模型：轉運問題轉運問題轉運問題是運輸問題的一種擴展，其中中間節(jié)點代表轉運節(jié)點，加入這個節(jié)點是為了考慮諸如倉庫等的位置。在這種更加普遍的分銷問題中，運輸可能發(fā)生在3個一般類型的節(jié)點的任意兩個之間。這3中節(jié)點為：起始節(jié)點、轉運節(jié)點和目的節(jié)點。就如在運輸問題中一樣，每個起始節(jié)點的可得供應量是有限的，每個目的節(jié)點的需求也是確定的。在轉運問題中，目標是在滿足目的節(jié)點需求的基礎上，確定網絡圖中每條弧線上應該運輸多少單位的貨物，才能使得總運輸成本最低。讓我們看看瑞恩電子所面臨的轉運問題。瑞恩電子是一家電子公司，其加工廠分別位于丹佛和亞特蘭大。從每個工廠生產出來的零件可能被運送到公司在堪薩斯城或路易斯維爾的地區(qū)倉庫中。公司把這些地區(qū)倉庫中的商品供應給底特律、邁阿密、達拉斯和新奧爾良的零售商。瑞恩電子6-1瑞恩電子：網絡表示（網絡圖）

6-1瑞恩電子：約束條件

6-1瑞恩電子：完整的LP模型聯(lián)合目標函數(shù)和這些約束條件構成了一個線性規(guī)劃模型，瑞恩電子公司的轉運問題是一個含有12個變量和8個約束的線性規(guī)劃模型：s.t.6-1瑞恩電子：結果與解釋瑞恩電子轉運問題的最優(yōu)目標函數(shù)值和最優(yōu)決策變量表明其最小的總運輸成本為52000美元。下表顯示了7個節(jié)點的產品運輸量。注意，亞特蘭大-堪薩斯城、堪薩斯城-邁阿密、堪薩斯城-新奧爾良、路易斯維爾-底特律和路易斯維爾-達拉斯這5個節(jié)點不是活動節(jié)點。6-1轉運問題：一般化的LP模型

6-1供應鏈問題的變化基本的運輸問題或者轉運問題的變化可能涉及以下的情況:1、總供應不等于總需求：若總供給大于總需求，不需要修改LP模型，在LP的求解中，用松弛變量來表達過剩供給。若總供給小于總需求，則LP模型沒有可行的解。在這種情況下，需要添加一個虛擬的起始節(jié)點，其供給等于總需求與總供給之差。2、最大化目標函數(shù)：當使用最大化目標函數(shù)來找到一個使利潤或收入最大化的解決方案時，不會對約束條件產生影響。3、路線容量或者路線最小量：運輸問題或者轉運問題的LP模型可以容納對一條或多條線路的容量或最小數(shù)量的約束。4、不可接受的線路：建立從每個起點到每個終點的線路有時是不可能的。為了處理這種情況，我們需要從網絡圖中刪除相應的弧，并從線性規(guī)劃模型中刪除相對應的變量。6-2指派問題介紹指派問題出現(xiàn)在多種決策過程中，典型的指派問題包括:將工作指派給機器，將任務指派給代理商，將銷售人員指派到銷售區(qū)域，將合同指派給投標人等。指派問題的一個顯著特征是只能給一個代理商指派一個任務。特別是我們在尋找一組能夠最優(yōu)化設定的目標的指派，例如成本最小、時間最短或者利潤最大。福爾市場研究公司讓我們來考慮福爾市場研究公司的案例。這個公司剛剛從3個新客戶那里拿到市場研究項目。公司面臨著將項目負責人(代理)指派給每一個客戶(任務)的任務每個市場調研的時間將取決于指派的項目負責人的經驗和能力。這3個項目具有相似的優(yōu)先順序，公司希望指派過去的項目負責人全部完成這3個項目所需的時間最短。每個項目負責人只能指派給一個客戶6-2福爾公司：網絡表示（網絡圖）福爾管理層必須首先考慮所有可能的項目負責人一客戶的指派方法，然后預測相對應的項目完成時間。3個項目負責人和3個客戶可以產生9種可能的指派方案。下表總結了各種可能的指派方案和預計項目完成時間。（注意指派問題的網絡圖和運輸問題的網絡圖之間的相似性。）6-2福爾公司:問題表達方法決策變量

目標函數(shù)和約束條件

6-2福爾公司：完整的LP模型把目標函數(shù)和約束條件組合在一起形成一個模型，下面就是具有9個變量和6個約束條件的福爾公司指派問題的線性規(guī)劃模型：s.t.6-2福爾公司:結果與解釋

6-2指派問題的變化指派問題的變化可能涉及以下一種或多種情況:1.總的代理(供應)數(shù)不等于總的任務(需求)數(shù)：如果代理數(shù)多于任務數(shù)，則不需要修改LP模型，并且多余的代理將不被指派出去。如果代理數(shù)少于任務數(shù)，那么線性規(guī)劃模型就沒有可行解了。在這種情況下,一種簡單的修正方法就是加人足夠多的虛擬代理，使代理數(shù)等于任務數(shù)。目標函數(shù)的最大化:如果指派的備選方案是根據(jù)收益或者利潤而不是時間或者成本進行評價的，那么線性規(guī)劃模型可以被當作最大化而不是最小化問題來處理。不可接受的指派:如果一個或者更多的指派是不可接受的，那么相對應的決策變量應當從線性規(guī)劃模型中刪除。例如，如果其中一個代理沒有這個任務或者更多任務所需的必要經驗，這種情況可能發(fā)生。6-2指派問題：一般化的LP模型

6-3最短路徑問題介紹最短路徑問題的目標是確定一個網絡內它的兩個節(jié)點間的最短路徑或線路。如果網絡中所有的弧線都是非負值，則可以使用標號法來尋找從特定節(jié)點到網絡中所有其他節(jié)點的最短路徑。在最短路徑問題中，盡管使用了“最短”一詞來描述過程，但最小化的準則并不局限于距離。其他標準包括時間和成本。(時間和成本都不一定與距離成線性關系)Gorman建筑公司Gomman建筑公司想要確定一條能夠最小化Gomman建筑公司的辦事處(坐落在節(jié)點1)和坐落在節(jié)點6的建筑工地間的總行程距離的路徑。6-3Gorman公司:網絡表示（網絡圖）為最短路徑問題建立模型的關鍵是要理解該問題是轉運問題的一個特例。起始節(jié)點：節(jié)點1；轉運節(jié)點：節(jié)點2-5；目的節(jié)點：節(jié)點6增加到弧線上的箭頭顯示了貨流的方向，它們總是從起始節(jié)點出來，并進人目的節(jié)點。注意到在成對轉運節(jié)點之間也存在兩個方向的孤線。在任何一個方向上，兩個轉運節(jié)點間的距離是相同的。為了找到節(jié)點1到節(jié)點6的最短路徑，我們認為節(jié)點1有1單位的供應量，并且節(jié)點6有1單位的需求。6-3Gorman公司:問題表達方法決策變量和目標函數(shù)

約束條件

6-3Gorman公司:完整的LP模型把目標函數(shù)和約束條件組合在一起形成一個模型，下面就是具有13個變量和6個約束條件的Gorman公司最短路徑問題的線性規(guī)劃模型：s.t.6-3Gorman公司:結果與解釋

6-3最短路徑問題:一般化的LP模型

6-4最大流問題介紹最大流問題的目標是確定最大數(shù)量的流量(交通工具、信息、液體等)，它們能夠在一個給定時期內流入和流出一個網絡系統(tǒng)。由于網絡不同弧線上的能力限制，流量的數(shù)量也被限制了。例如，在交通系統(tǒng)中，高速公路的類型限制交通工具的流量。而在石油分配系統(tǒng)中，管道的大小限制石油流量。弧線上流量的最大或最高限制被稱作弧線的流通能力。即使不明確說明各節(jié)點的能力，我們也要假定流出一個節(jié)點的流量等于流人該節(jié)點的流量。辛辛那提高速公路系統(tǒng)每條弧的流向被指明了，而且弧的通過能力標注在每條弧的旁邊。注意，大部分的街道是單向的。然而,在節(jié)點2和節(jié)點3之間，以及節(jié)點5和節(jié)點6之間存在雙向的街道。6-4高速公路系統(tǒng):網絡表示（網絡圖）

6-4高速公路系統(tǒng):約束條件對于每一個節(jié)點，流量守恒約束條件表示需要流出必須等于流入。或者用另一種方式陳述是，流出減去流人必須等于0。節(jié)點流出流入1234567

6-4高速公路系統(tǒng):結果和解釋這個擁有15個變量、21個約束條件的線性規(guī)劃問題的最優(yōu)解表明穿過高速公路系統(tǒng)的最大流量是每小時14000輛車。下圖顯示了車流量（以千輛車為單位）是怎樣穿過起始的高速公路網的。6-5生產和庫存應用運輸和轉運模型涉及從幾個供應地或產地到幾個需求地或目的地之間的貨物運輸?shù)膽?。轉運模型能夠被用來求解生產調度和庫存問題?？低兴姑簭S是一家生產家用和辦公室毛毯的小型生產商。其生產能力、需求和生產成本隨著季度的不同而變化，然而庫存成本從一個季度到下一個季度一直是0.25美元/碼?？低兴姑簭S要決定每個季度生產多少平方碼的毛毯，才能使這4個季度的總生產和庫存成本最低。6-5康托斯毛毯廠:網絡表示（網絡圖）我們先建立這個問題的網絡圖。創(chuàng)建對應于每個季度生產的4個節(jié)點，和對應于每個季度需求的4個節(jié)點。每個生產節(jié)點由一條流出的弧線連接到同一時期的需求節(jié)點，弧線上的流量表示這個季度生產的毛毯的平方碼數(shù)。對于每個需求節(jié)點，流出的弧線代表了庫存中持有到下一個季度需求節(jié)點的數(shù)量(毛毯的平方碼數(shù))。節(jié)點1到節(jié)點4表示每個季度的生產量，節(jié)點5到節(jié)點8表示每個季度的需求量。每個季度的生產能力顯示在左邊緣，每個季度的需求顯示在右邊緣。6-5康托斯毛毯廠:問題表達方法決策變量和目標函數(shù)

約束條件

6-5康托斯毛毯廠:完整的LP模型把目標函數(shù)和約束條件組合在一起形成一個模