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

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

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

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

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

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

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

min

s.t.

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

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

xij≥0，

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

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

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

6.3.1問題的變化

因?yàn)樯婕斑\(yùn)輸和指派問題，轉(zhuǎn)運(yùn)問題可能出現(xiàn)如下幾種變化：

總供給不等于總需求；

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

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

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

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

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

2.所有的道路都是雙向的；因此流向可能在任一方向中。為最短路徑問題建立模型的關(guān)鍵是要理解該問題是轉(zhuǎn)運(yùn)問題的一個(gè)特殊事例。具體來說，Gorman最短路徑問題可以被看成是一個(gè)帶有一個(gè)起始節(jié)點(diǎn)〔節(jié)點(diǎn)1〕、一個(gè)目標(biāo)節(jié)點(diǎn)〔節(jié)點(diǎn)6〕以及4個(gè)轉(zhuǎn)運(yùn)節(jié)點(diǎn)〔節(jié)點(diǎn)2，3，4和5〕的轉(zhuǎn)運(yùn)問題。為了找到節(jié)點(diǎn)1到節(jié)點(diǎn)6的最短路徑，我們認(rèn)為節(jié)點(diǎn)1有一單位的供給量，并且節(jié)點(diǎn)6有一個(gè)單位的需求。令xij為從節(jié)點(diǎn)i到節(jié)點(diǎn)j流動(dòng)或被傳送的單元數(shù)。如果xij=1，那么從節(jié)點(diǎn)i至節(jié)點(diǎn)j的弧線在從節(jié)點(diǎn)1至節(jié)點(diǎn)6的最短路徑上；如果xij=0，那么從節(jié)點(diǎn)i至節(jié)點(diǎn)j的弧線不在該最短路徑上。因?yàn)槲覀冋趯ふ夜?jié)點(diǎn)1到節(jié)點(diǎn)6的最短路徑，得出Gorman問題的目標(biāo)函數(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é)點(diǎn)

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

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

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

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

x26+x46+x56=1目標(biāo)節(jié)點(diǎn)

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

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

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

Min

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

轉(zhuǎn)運(yùn)節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)j6.4最短路徑問題

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

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