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

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

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

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

目標(biāo)函數(shù)

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

需求

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

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

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

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

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

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

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

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

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

約束條件

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

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

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

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

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

約束條件

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