分配與網(wǎng)絡(luò)模型

第六章分配與網(wǎng)絡(luò)模型教師：朱玉春教授單位：經(jīng)濟管理學(xué)院

2023年西北農(nóng)林科技大學(xué)本章主要內(nèi)容6.1運輸問題6.2指派問題6.3轉(zhuǎn)運問題6.4最短路徑問題6.5最大流問題6.6生產(chǎn)和庫存應(yīng)用運輸問題經(jīng)常出現(xiàn)在方案貨物配送和從某些供給地區(qū)到達某些需求地區(qū)之間的效勞中，特別是每個供給地區(qū)的貨物可獲得量是有限的，每個需求地區(qū)的貨物需求量是的。運輸問題中最常用的目標是要使貨物從起點到目的地的運輸本錢最低。讓我們通過考慮福斯特發(fā)電機公司面臨的這個運輸問題來進行介紹。這個問題包括從3個加工廠運輸一種產(chǎn)品到4個分銷中心。福斯特發(fā)電機公司在俄亥俄州的克里夫蘭、印第安納州的貝德福德和賓夕法尼亞州的約克有3個加工廠，下3個月的方案期內(nèi)的這個特殊型號的發(fā)電機的生產(chǎn)能力以及坐落在波士頓、芝加哥、圣路易斯和萊克星頓的4個分銷中心3個月的需求預(yù)測，詳見教材162頁。6.1運輸問題6.1運輸問題6.1運輸問題管理者想知道從每個加工廠運輸?shù)椒咒N中心的產(chǎn)品運輸量應(yīng)為多少。圖6-1顯示了12條福斯特公司可以用的配送路線。這種圖稱為網(wǎng)絡(luò)圖；圓圈表示節(jié)點，連接節(jié)點的線條表示弧。每個起點和目的地都由節(jié)點表示，每個可能的運輸路線都由弧表示。供給量寫在起始節(jié)點邊上，需求量寫在每個目的地節(jié)點邊上。從起始節(jié)點到目的地節(jié)點之間運輸?shù)呢浳飻?shù)量表示了這個網(wǎng)絡(luò)的流量。注意：直接流量〔從起點到終點〕是用帶箭頭的線條表示的。6.1運輸問題6.1運輸問題對應(yīng)這個福斯特公司的運輸問題的目標是要確定使用哪些路線以及每條線路上的流量是多少時，使得總的運輸本錢最低。每條線路單位產(chǎn)品的運輸費用在圖6-1中的每條弧上標明。線性規(guī)劃模型可以用來解決這類運輸問題，我們將用雙下標決策變量來描述變量。一般情況下，一個有m個起點和n個目的地的運輸問題的決策變量常被表示成以下形式：xij——從起點i到目的地j之間的運輸量式中，i=1,2,3,...,m,j=1,2,3,...,n。根據(jù)所給信息，我們可以構(gòu)建一個有12個變量，7個約束的線性規(guī)劃模型6.1運輸問題Max3x11+2x12+7x13+6x14+7x21+5x22+2x23+3x24+2x31+5x32+4x33+5x34s.t.x11+x12+x13+x14≤5000克里夫蘭供給x21+x22+x23+x24≤6000貝德福德供給x31+x32+x33+x34≤2500約克供給x11+x21+x31=6000波士頓需求x12+x22+x32=4000芝加哥需求x13+x23+x33=2000圣路易斯需求x14+x24+x34=1500萊克星頓需求xij≥0，其中，i=1,2,3；j=1,2,3,4比較線性規(guī)劃模型與圖6-1中的網(wǎng)絡(luò)，會發(fā)現(xiàn)幾個觀察值。所有線性規(guī)劃模型所需的信息都能在網(wǎng)絡(luò)圖中找到，每個節(jié)點需要一個約束條件，每一條弧需要一個變量。對應(yīng)的每個起點節(jié)點出發(fā)的每條弧上的變量值之和必須小于或者等于這個起點節(jié)點的供給，對應(yīng)的去往每個目的地節(jié)點的弧上的變量值之和必須等于這個目的地節(jié)點的需求6.1運輸問題路線運輸量單位成本（美元）總成本（美元）從到克利夫蘭波士頓3500310500克利夫蘭芝加哥150023000貝德福德芝加哥2500512500貝德福德圣路易斯200024000貝德福德萊克星頓150034500約克波士頓2500250006.1.1問題的變化福斯特公司發(fā)電機問題闡述了根本的運輸模型的應(yīng)用，根本運輸模型的變化可能有以下幾種情況：1、總供給不等于總需求通常情況下總供給不等于總需求。如果總供給超過總需求，線性規(guī)劃模型不需要修改。多余的供給總量在線性規(guī)劃解決方案中表現(xiàn)為松弛。而任何起點的松弛都可以被理解為未使用的供給或者未從起點運輸?shù)呢浳飻?shù)量。如果總供給小于總需求，運輸問題的線性規(guī)劃模型沒有可行解，在這種情況下，我們可以對網(wǎng)絡(luò)圖做如下修改：增加一個虛擬起點，這個起點的供給恰好等于不被滿足的需求。增加從這個虛擬起點到每個終點的弧，線性規(guī)劃模型就會有可行的解決方法了。我們規(guī)定每條從虛擬起點出發(fā)的弧上單位的運輸本錢為0。6.1運輸問題這樣，經(jīng)過修改的問題的最優(yōu)解將會代表實際運輸?shù)呢浳锏倪\輸本錢〔從虛擬起點出發(fā)的線路沒有實際運輸發(fā)生〕。當(dāng)我們執(zhí)行這個最優(yōu)解時，目的地節(jié)點處顯示的運輸量是這個節(jié)點需求不被滿足的貨物短缺量。2、最大化目標函數(shù)在某些運輸問題中，目標是要找到最大化利潤或者收入的解決方案。這種情況下我們只要把單位利潤或者收入作為一個系數(shù)列入目標函數(shù)中，簡單地把最小改成最大，約束條件不變，就可求得線性規(guī)劃的最大值而不是最小值。3、路線容量和或路線最小量運輸問題的線性規(guī)劃模型也能夠包含一條或者更多的路線容量或者最小數(shù)量問題。例如，假設(shè)在福斯特公司發(fā)電機問題中，約克——波士頓路線〔起點3到終點1〕因為其常規(guī)的運輸模式中有限空間的限制，只有1000單位的運輸能力。用x31表示約克——波士頓線路的運輸量，那么這條線路的運輸能力約束為：x31≤1000，類似地，路線的最小量也可以確定下來。6.1運輸問題例如，x22≥2000，這個約束條件保證了最優(yōu)解中保存先前承諾的最小2000單位的訂單。4、不可接受的路線最后一種情況，構(gòu)建從每一個起點到終點的路線并不都是可能的。為了處理這種情況，我們只需要簡單地去除網(wǎng)絡(luò)圖中相關(guān)的弧和線性規(guī)劃模型中相關(guān)的變量。例如，如果克里夫蘭——圣路易斯之間的路線是不可接受的或者是不可用的，那么在圖6-1中，從克里夫蘭到圣路易斯之間的這條弧應(yīng)當(dāng)刪除。線性規(guī)劃模型中的變量x13也應(yīng)當(dāng)被刪除。解決這個有11個變量和7個約束條件的線性規(guī)劃模型得出的最優(yōu)解的同時，也保證了克里夫蘭——圣路易斯之間的線路不被使用。6.1運輸問題6.1.2運輸問題的一般線性規(guī)劃模型為了表示這個運輸問題的一般線性規(guī)劃模型，我們將用到以下概念：i——起點下標，i=1，2，...，m；j——終點下標，j=1，2，...，n；xij——起點i到終點j之間的運輸量；cij——起點i到終點j之間的單位運輸本錢；si——起點i的供給量或者生產(chǎn)能力；dj——終點j的需求量。m個起點，n個終點的運輸問題的線性規(guī)劃的一般模型如下：6.1運輸問題6.1運輸問題m個起點，n個終點的運輸問題的線性規(guī)劃的一般模型如下：mins.t.i=1，2，...，m供給j=1，2，...，n需求xij≥0，對所有i和j就如先前我們提到的，如果從起點i到終點j之間的運輸容量為Lij，可以在約束里加一個xij≤Lij，一個包含了這種類型的約束條件的運輸問題就稱為有容量限制的運輸問題。類似地，如果起點i到終點j之間必須處理的運輸容量最小為Mij，那么我們在約束條件里加上最小運輸容量約束xij≥Mij。很多決策過程都會產(chǎn)生指派問題。指派問題中一個很明顯的特征是一個代理只分配給一個任務(wù)，僅僅一個任務(wù)，特別是我們尋找一組能夠最優(yōu)化所設(shè)立的目標的分配，例如本錢最小、時間最短或者利潤最大。為了闡述指派問題，讓我們來看看福爾市場調(diào)查公司的案例，這個公司剛剛從3個新客戶那里獲得市場調(diào)查工程。公司面臨著給每一個客戶分配一個工程負責(zé)人的任務(wù)。最近有3個工程負責(zé)人手上沒有其他任務(wù)，可以被分配。這3個工程具有相似的優(yōu)先順序，公司希望分配的工程負責(zé)人完成這3個工程所需總時間最短。如果每個客戶只需要一個工程負責(zé)人，那么該怎么分配？為了解決這個指派問題，福爾的管理層必須首先考慮所有可能的負責(zé)人——客戶的分配方法，然后預(yù)測相對應(yīng)的完成工程所需的時間。3個工程負責(zé)人和3個客戶可以產(chǎn)生9種分配方案。6.2指派問題6.2指派問題6.2指派問題圖6-2是福爾公司指派問題的一個網(wǎng)絡(luò)圖。節(jié)點對應(yīng)著工程負責(zé)人和客戶，弧代表工程負責(zé)人——客戶之間的可能分配。每個起點節(jié)點的供給和終點節(jié)點的需求都是1；把一個工程負責(zé)人指派給一個客戶的本錢是這個負責(zé)人完成客戶的市場調(diào)研任務(wù)所需的時間。注意指派問題的網(wǎng)絡(luò)圖〔圖6-2〕和運輸問題的網(wǎng)絡(luò)圖〔圖6-1〕之間的相似性。這個指派問題其實就是運輸問題的一個特殊情形，其中所有的供給和需求量都是1，每條弧的運輸量不是1就是0。因為這個指派問題就是運輸問題的一個特殊實例，那么可以設(shè)計一個線性規(guī)劃模型。定義福爾公司指派問題的決策變量為：1，如果項目負責(zé)人i被分配給客戶j0，其他情況xij這里，i=1，2，3；j=1，2，3。

根據(jù)所給信息，我們可以得到一個具有9個變量和6個約束條件的福爾公司指派問題的線性規(guī)劃模型：min

10x11+15x12+9x13+9x21+18x22+5x23+6x31+14x32+3x33

s.t.x11+x12+x13≤1對特瑞的指派x21+x22+x23≤1對卡爾的指派x31+x32+x33≤1對邁克孟德的指派x11+x21+x31=1客戶1x12+x22+x32=1客戶2x13+x23+x33=1客戶3

xij≥0，其中，i=1，2，3；j=1，2，3。6.2指派問題模型的計算機計算結(jié)果如下，特瑞被指派給了客戶2，卡爾被指派給了客戶3，邁克孟德被指派給了客戶1?？偟墓こ掏瓿蓵r間為26天。6.2指派問題目標函數(shù)值=26.000變量值成本的減少量X110.0000.000X121.0000.000X130.0003.000X210.0000.000X220.0004.000X231.0000.000X311.0000.000X320.0003.000X330.0001.0006.2.1問題的變化因為指派問題可以被看做一個運輸問題的特例，那么指派問題中可能出現(xiàn)的變化就和運輸問題中出現(xiàn)的變化相似，所以我們能夠處理下面的情形：1.總的代理〔供給〕數(shù)不等于總的任務(wù)〔需求〕數(shù)。2.目標函數(shù)最大化。3.不可接受的分配。代理數(shù)不等于任務(wù)數(shù)時的情形和運輸問題中總供給不等于總需求時類似。在線性規(guī)劃模型中，如果代理數(shù)多于任務(wù)的數(shù)量，多余的代理將不被指派。如果任務(wù)數(shù)多于代理數(shù)，那么線性規(guī)劃模型就沒有可行的解決方案。在這種情況下，一種簡單的修正方法就是參加足夠多的虛擬代理，使代理數(shù)等于任務(wù)數(shù)。6.2指派問題比方說，在福爾公司問題中，我們有5個客戶〔任務(wù)〕和3個工程負責(zé)人〔代理〕。在參加兩個虛擬的工程負責(zé)人后，我們可以建立一個新的工程負責(zé)人與客戶數(shù)量相等的指派問題。虛擬工程負責(zé)人的指派問題的目標函數(shù)系數(shù)設(shè)為0，這樣最優(yōu)解的值就代表進行指派的實際所需天數(shù)〔虛擬負責(zé)人的指派是實際上不進行的〕。如果指派的備選方案是根據(jù)收入或者利潤而不是時間或者本錢進行評價的，那么線性規(guī)劃模型可以處理成最大化而不是最小化問題。另外，如果一個或者更多的指派是不可接受的，那么相對應(yīng)的決策變量應(yīng)當(dāng)從線性規(guī)劃模型中刪除。這種情況可能發(fā)生，例如，如果其中一個代理沒有這個任務(wù)或者更多任務(wù)所需的必要經(jīng)驗。6.2指派問題6.2指派問題6.2.2指派問題的一般線性規(guī)劃模型為了展示包括m個代理和n個任務(wù)的指派問題的一般線性規(guī)劃模型，我們做如下設(shè)定：

cij=把代理i指派給任務(wù)j所花的本錢1，如果項目負責(zé)人i被分配給客戶j0，其他情況xij6.2指派問題該一般線性規(guī)劃模型如下所示：

min

s.t.

i=1，2，...，m代理

j=1，2，...，n任務(wù)

xij≥0，

對所有的i和j在本節(jié)一開始，我們就指出指派問題有一個明顯的特征，一個代理只能被指派給一個任務(wù)。對于一個代理可以被分配給兩個或者更多個任務(wù)的廣義指派問題，我們可以對線性規(guī)劃模型進行簡單修正。例如，假設(shè)福爾公司問題中特瑞能夠被指派給兩個客戶；在這種情況下，代表特瑞指派的約束條件就為x11+x12+x13≤2。一般情況下，如果ai表示代理i能夠被指派的任務(wù)的最高上限，那么我們把代理約束寫成如下形式：i=1，2，...，m因此，我們發(fā)現(xiàn)把指派問題像線性規(guī)劃模型一樣構(gòu)建和求解的一個好處就是，特殊情形，例如涉及多種指派的情況，比較容易處理。6.2指派問題6.3轉(zhuǎn)運問題轉(zhuǎn)運問題是運輸問題的擴展，其中中間節(jié)點代表轉(zhuǎn)運節(jié)點，參加這個節(jié)點的目的是指代地點位置。在更為普遍的指派問題類型中，出貨發(fā)生在3個一般類型節(jié)點的任意兩個之間。這3種節(jié)點為：起點節(jié)點、轉(zhuǎn)運節(jié)點和終點節(jié)點。就如在運輸問題中一樣，每個起點節(jié)點的可得的供給是有限的，每個終點節(jié)點的需求也是確定的。在轉(zhuǎn)運問題中，目標是在滿足終點節(jié)點需求的根底上，確定網(wǎng)絡(luò)圖中每條弧上運輸多少單位，才能使總的運輸本錢最低。瑞恩電子是一家電子公司，其生產(chǎn)線分別位于丹佛和亞特蘭大，在每條生產(chǎn)線上生產(chǎn)出來的商品都可以被運送到公司在堪薩斯或者是路易斯維爾地區(qū)的倉庫中，公司把這些地區(qū)的倉庫中的商品發(fā)給底特律、邁阿密、達拉斯和新奧爾良的零售商。圖6-3顯示了網(wǎng)絡(luò)模型中的每條弧以及這個問題的關(guān)鍵特征。注：每個起點節(jié)點的供給量和每個終點節(jié)點的需求量都在其旁邊標明。6.3轉(zhuǎn)運問題

對于運輸和指派問題，我們可以構(gòu)建一個線性規(guī)劃模型；對于網(wǎng)絡(luò)圖表示的轉(zhuǎn)運問題，我們也可以構(gòu)建一個線性規(guī)劃模型。同樣，我們也需要給每一個節(jié)點和每條弧上的變量一個約束。令xij表示從節(jié)點i運輸?shù)焦?jié)點j的運輸數(shù)量。根據(jù)所給信息，我們可得到一個具有12個變量、8個約束條件的線性規(guī)劃模型：

min

2x13+3x14+3x23+x24+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48

s.t.x13+x14≤600x23+x24≤400-x13-x23+x35+x36+x37+x38=0-x14-x24+4x45+4x46+6x47+5x48=06.3轉(zhuǎn)運問題

x35+x45=200x36+x46=150x37+x47=350x38+x48=300xij≥0，對所有的i和j正如在本節(jié)開始時，提到的那樣，在轉(zhuǎn)運問題中弧可以任意連接兩個節(jié)點。所有的運輸方式在轉(zhuǎn)運問題中都是可能的。對每個節(jié)點，我們?nèi)匀恍枰覂H需要一個約束條件，此約束條件必須包含每條弧進入或者離開該節(jié)點的每個變量。對于初始節(jié)點，輸出的總量減去輸入的總量必須小于或者等于該節(jié)點的商品供給量。對目標節(jié)點來說，輸入的總數(shù)減去輸出的總數(shù)必須等于該節(jié)點的需求。對轉(zhuǎn)運節(jié)點來說，輸出的總數(shù)必須等于輸入的總數(shù)。6.3轉(zhuǎn)運問題

6.3.1問題的變化

因為涉及運輸和指派問題，轉(zhuǎn)運問題可能出現(xiàn)如下幾種變化：

總供給不等于總需求；

最大化目標函數(shù)；

路線容量或者路線最小量；

不可接受的路線。線性規(guī)劃模型的修改需要包含這些變化的修正，就如同在6.1節(jié)中所談到的運輸問題中所需要的一些修正。當(dāng)我們?yōu)榱孙@示從節(jié)點i到節(jié)點j的路線運輸容量為Lij，在約束條件中增加一條或者更多像xij≤Lij這樣的表達式，我們稱這樣的轉(zhuǎn)運問題為有容量限制的轉(zhuǎn)運問題。6.3轉(zhuǎn)運問題6.3.2轉(zhuǎn)運問題的一般線性規(guī)劃模型轉(zhuǎn)運問題的一般線性規(guī)劃模型如下：mins.t.起點節(jié)點i轉(zhuǎn)運節(jié)點終點節(jié)點j其中，xij≥0，對所有的i，jxij——節(jié)點i到節(jié)點j之間的運輸量；cij——節(jié)點i到節(jié)點j之間的單位運輸本錢；Si——起點節(jié)點i的供給量；dj——終點節(jié)點的需求量。6.3轉(zhuǎn)運問題6.4最短路徑問題本節(jié)我們將探討這樣一個問題，它的目標是確定一個網(wǎng)絡(luò)內(nèi)兩個節(jié)點間的最短路徑或路線。我們將通過分析Gorman建筑公司所面臨的情況來講解最短路徑問題。Gorman的辦事處和每一個建筑地點之間的行程選擇可以用公路網(wǎng)絡(luò)來描述，如圖6-4所示。節(jié)點之間的道路距離顯示在相應(yīng)弧線的上面。Gorman想要確定一條能夠最小化Gorman的辦事處〔坐落在節(jié)點1〕和坐落在節(jié)點6的建筑地點間的總行程距離的路徑。

Gorman辦事處圖6-4路程的英里數(shù)2552012337466451446.4最短路徑問題注意：

1.每一條弧的長度不是必然和它代表的行駛路程成正比例

2.所有的道路都是雙向的；因此流向可能在任一方向中。為最短路徑問題建立模型的關(guān)鍵是要理解該問題是轉(zhuǎn)運問題的一個特殊事例。具體來說，Gorman最短路徑問題可以被看成是一個帶有一個起始節(jié)點〔節(jié)點1〕、一個目標節(jié)點〔節(jié)點6〕以及4個轉(zhuǎn)運節(jié)點〔節(jié)點2，3，4和5〕的轉(zhuǎn)運問題。為了找到節(jié)點1到節(jié)點6的最短路徑，我們認為節(jié)點1有一單位的供給量，并且節(jié)點6有一個單位的需求。令xij為從節(jié)點i到節(jié)點j流動或被傳送的單元數(shù)。如果xij=1，那么從節(jié)點i至節(jié)點j的弧線在從節(jié)點1至節(jié)點6的最短路徑上；如果xij=0，那么從節(jié)點i至節(jié)點j的弧線不在該最短路徑上。因為我們正在尋找節(jié)點1到節(jié)點6的最短路徑，得出Gorman問題的目標函數(shù)是：min25x12+20x13+3x23+3x32+5x24+5x42+14x26+6x35+6x53+4x45+4x54+4x46+7x56再加上一些約束條件，我們可以得到Gorman問題的線性規(guī)劃模型如下：6.4最短路徑問題

min25x12+20x13+3x23+3x32+5x24+5x42+14x26+6x35+6x53+4x45+4x54+4x46+7x56

s.t.

x12+x13=1起始節(jié)點

-x12+x23-x32+x24-x42+x26=0轉(zhuǎn)運節(jié)點

-x13-x23+x32+x35-x53=0轉(zhuǎn)運節(jié)點

-x24+x42+x45-x54+x46=0轉(zhuǎn)運節(jié)點

-x35+x53-x45+x54+x56=0轉(zhuǎn)運節(jié)點

x26+x46+x56=1目標節(jié)點

對于所有的i和j，xij≥06.4最短路徑問題

為了表示最短路徑問題的一般線性規(guī)劃模型，我們使用下面的定義：cij=與從節(jié)點i到節(jié)點j的弧線相關(guān)的距離，時間或費用。最短路徑問題的一般線性規(guī)劃模型如下所示：

xij=0反之1如果從節(jié)點i到節(jié)點j的弧線在最短路徑上6.4最短路徑問題

Min

s.t.起始節(jié)點i

轉(zhuǎn)運節(jié)點目標節(jié)點j6.4最短路徑問題

最大流問題的目標是確定最大數(shù)量的流量，它們能夠在一個給定時期內(nèi)進入和退出一個網(wǎng)絡(luò)系統(tǒng)。在這個問題中，我們嘗試著通過網(wǎng)絡(luò)的所有弧線盡可能有效地傳遞流量。由于網(wǎng)絡(luò)不通弧線上的能力限制，流量的數(shù)量也被限制了?；【€上流量的最大或最高限制被稱為弧線的流通能力。在我們不明確說明各節(jié)點的能力時，我們都假定流出一個節(jié)點的流量等于進入該節(jié)點的流量。作為最大流問題的一個例子，我們考慮穿過辛辛那提和俄亥俄的南北向洲際高速公路系統(tǒng)。我們將出示怎樣為這個最大流問題建立一個限制容量的轉(zhuǎn)運模型。首先，我們添加一條從節(jié)點7回到節(jié)點1的弧線，來表示穿過高速公路系統(tǒng)的總流量。圖6-5是標有弧流通能力的網(wǎng)絡(luò)圖，每條弧的流向被指明了，而且弧能力標注在每條弧的旁邊6.5最大流問題6.5最大流問題6.5最大流問題

新增的弧線沒有通過能力限制，事實上，我們希望最大化通過那條弧線的流量。最大化從節(jié)點7到節(jié)點1弧線的流量等于穿過途徑辛辛那提的南北向高速公路系統(tǒng)的汽車數(shù)量。決策變量為：xij=從節(jié)點i到節(jié)點j的交通流量數(shù)。能最大化高速公路系統(tǒng)流量的目標函數(shù)是：maxx71。對于所有轉(zhuǎn)運問題，每個弧產(chǎn)生一個變量，并且每個節(jié)點產(chǎn)生一個約束。對于每一個節(jié)點，流量守恒約束表示需要流出必須等于流入。對于節(jié)點1，其流出是x12+x13+x14，流入是x71。故而，節(jié)點1的約束是：x12+x13+x14-x71=