1、u運(yùn)輸路線的選擇影響到運(yùn)輸設(shè)備和人員的利用，正確地運(yùn)輸路線的選擇影響到運(yùn)輸設(shè)備和人員的利用，正確地確定合理的運(yùn)輸路線可以降低運(yùn)輸成本，因此運(yùn)輸路線確定合理的運(yùn)輸路線可以降低運(yùn)輸成本，因此運(yùn)輸路線的確定是運(yùn)輸決策的一個(gè)重要領(lǐng)域。安排運(yùn)輸路線和時(shí)的確定是運(yùn)輸決策的一個(gè)重要領(lǐng)域。安排運(yùn)輸路線和時(shí)間的幾個(gè)原則如下：間的幾個(gè)原則如下：1.1.將將相互接近的停留點(diǎn)的貨物裝在一輛車上運(yùn)送，以便停相互接近的停留點(diǎn)的貨物裝在一輛車上運(yùn)送，以便停留點(diǎn)之間的運(yùn)行距離最小化；留點(diǎn)之間的運(yùn)行距離最小化；u車輛的運(yùn)輸路線應(yīng)將鄰近的停留點(diǎn)串起來(lái)，以使停留點(diǎn)之間的車輛的運(yùn)輸路線應(yīng)將鄰近的停留點(diǎn)串起來(lái)，以使停留點(diǎn)之間的運(yùn)輸距離

2、最小化，這樣也就使總的路線上的運(yùn)輸時(shí)間最短。運(yùn)輸距離最小化，這樣也就使總的路線上的運(yùn)輸時(shí)間最短。2.將集聚在一起的停留點(diǎn)安排同一天送貨，要避免不是同將集聚在一起的停留點(diǎn)安排同一天送貨，要避免不是同一天送貨的停留點(diǎn)在運(yùn)行路線上重疊；一天送貨的停留點(diǎn)在運(yùn)行路線上重疊；3. 運(yùn)行路線從離倉(cāng)庫(kù)最遠(yuǎn)的停留點(diǎn)開始。運(yùn)行路線從離倉(cāng)庫(kù)最遠(yuǎn)的停留點(diǎn)開始。u運(yùn)行路線從離倉(cāng)庫(kù)最遠(yuǎn)的停留點(diǎn)開始，送貨車輛依次裝載臨運(yùn)行路線從離倉(cāng)庫(kù)最遠(yuǎn)的停留點(diǎn)開始，送貨車輛依次裝載臨近這個(gè)關(guān)鍵停留點(diǎn)的一些停留點(diǎn)的貨物，這輛貨車滿載后，近這個(gè)關(guān)鍵停留點(diǎn)的一些停留點(diǎn)的貨物，這輛貨車滿載后，再安排另一輛貨車裝載另一個(gè)最遠(yuǎn)的停留點(diǎn)的貨物。再安排

3、另一輛貨車裝載另一個(gè)最遠(yuǎn)的停留點(diǎn)的貨物。倉(cāng)庫(kù)倉(cāng)庫(kù)4.一輛貨車順次途徑各停留點(diǎn)的路線盡量不交叉，要成淚滴一輛貨車順次途徑各停留點(diǎn)的路線盡量不交叉，要成淚滴狀。狀。5.在多種規(guī)格車型的車隊(duì)中，應(yīng)優(yōu)先使用載重量最大的貨在多種規(guī)格車型的車隊(duì)中，應(yīng)優(yōu)先使用載重量最大的貨車。車。u在運(yùn)輸貨物時(shí)，最好是使用一輛載重量大到能將路線上所在運(yùn)輸貨物時(shí)，最好是使用一輛載重量大到能將路線上所有停留點(diǎn)所要求運(yùn)送的貨物都裝載的貨車，這樣可以將服有停留點(diǎn)所要求運(yùn)送的貨物都裝載的貨車，這樣可以將服務(wù)區(qū)停留點(diǎn)的總的運(yùn)行距離或時(shí)間最小化。務(wù)區(qū)停留點(diǎn)的總的運(yùn)行距離或時(shí)間最小化。6.提貨應(yīng)混在送貨過程中進(jìn)行，而不要在運(yùn)行路線結(jié)束后提

4、貨應(yīng)混在送貨過程中進(jìn)行，而不要在運(yùn)行路線結(jié)束后再進(jìn)行。再進(jìn)行。u提貨應(yīng)盡可能在送貨過程中進(jìn)行，以減少交叉路程量，而提貨應(yīng)盡可能在送貨過程中進(jìn)行，以減少交叉路程量，而在送貨結(jié)束后再進(jìn)行提貨經(jīng)常會(huì)發(fā)生路程交叉。在送貨結(jié)束后再進(jìn)行提貨經(jīng)常會(huì)發(fā)生路程交叉。7.對(duì)偏離集聚停留點(diǎn)路線遠(yuǎn)的單獨(dú)的停留點(diǎn)可專門安排車對(duì)偏離集聚停留點(diǎn)路線遠(yuǎn)的單獨(dú)的停留點(diǎn)可專門安排車輛送貨輛送貨 。u偏離集聚停留點(diǎn)少，特別是那些送貨量小的停留點(diǎn)一般要偏離集聚停留點(diǎn)少，特別是那些送貨量小的停留點(diǎn)一般要花費(fèi)大量的時(shí)間和費(fèi)用，因此適用小載重量的車輛專門為花費(fèi)大量的時(shí)間和費(fèi)用，因此適用小載重量的車輛專門為這些停留點(diǎn)送貨是合理的。這些停留點(diǎn)

5、送貨是合理的。l 另一個(gè)可供選擇的方案是租用車輛或采用公共服務(wù)（如另一個(gè)可供選擇的方案是租用車輛或采用公共服務(wù)（如郵政服務(wù)）為這些停車郵政服務(wù)）為這些停車點(diǎn)點(diǎn)送貨。送貨。8. 應(yīng)當(dāng)避免停留點(diǎn)工作時(shí)間太短的約束。應(yīng)當(dāng)避免停留點(diǎn)工作時(shí)間太短的約束。u停留點(diǎn)工作時(shí)間太短會(huì)迫使途經(jīng)停留點(diǎn)的順序偏離理想狀停留點(diǎn)工作時(shí)間太短會(huì)迫使途經(jīng)停留點(diǎn)的順序偏離理想狀態(tài)。態(tài)。運(yùn)輸路線決策就是，找到運(yùn)輸網(wǎng)絡(luò)中的最佳路線，以盡可能縮短運(yùn)輸時(shí)間或運(yùn)輸距離，達(dá)到降低運(yùn)輸成本、改善運(yùn)輸服務(wù)的目標(biāo)。 運(yùn)輸路線決策問題有三種基本類型：運(yùn)輸路線決策問題有三種基本類型： 一是起點(diǎn)和終點(diǎn)不同的單一路徑規(guī)劃； 二是多個(gè)起點(diǎn)和終點(diǎn)的路徑規(guī)劃

6、； 三是起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃。一、起點(diǎn)和終點(diǎn)不同的單一路徑規(guī)劃一、起點(diǎn)和終點(diǎn)不同的單一路徑規(guī)劃 此類問題可以描述為在一個(gè)已知交通運(yùn)輸網(wǎng)絡(luò)中，尋找從出發(fā)地到目的地的最佳路線。這里的“最佳”可以指可以指距離最短、時(shí)間最省或是費(fèi)用最少。距離最短、時(shí)間最省或是費(fèi)用最少。數(shù)學(xué)模型求網(wǎng)絡(luò)圖中二點(diǎn)之間的最短路問題。采用網(wǎng)絡(luò)規(guī)劃中求最短路DijkstraDijkstra算法（標(biāo)號(hào)算法）算法（標(biāo)號(hào)算法）。除了距離以外，還需要考慮通過交通網(wǎng)絡(luò)的時(shí)間長(zhǎng)短時(shí)間長(zhǎng)短。 對(duì)分離的、單個(gè)始發(fā)點(diǎn)和終點(diǎn)的網(wǎng)絡(luò)運(yùn)輸路線對(duì)分離的、單個(gè)始發(fā)點(diǎn)和終點(diǎn)的網(wǎng)絡(luò)運(yùn)輸路線選擇問題，最簡(jiǎn)單和直觀的方法是最短路線法。選擇問題，最簡(jiǎn)單和直觀的方

7、法是最短路線法。初始，除始發(fā)點(diǎn)外，所有節(jié)點(diǎn)都被認(rèn)為是未解的，初始，除始發(fā)點(diǎn)外，所有節(jié)點(diǎn)都被認(rèn)為是未解的，即均未確定是否在選定的運(yùn)輸路線上。始發(fā)點(diǎn)作即均未確定是否在選定的運(yùn)輸路線上。始發(fā)點(diǎn)作為已解的點(diǎn)，計(jì)算從原點(diǎn)開始。為已解的點(diǎn)，計(jì)算從原點(diǎn)開始。 一般的計(jì)算方法是：一般的計(jì)算方法是： (1) (1)第第n n次迭代的目標(biāo)。尋求第次迭代的目標(biāo)。尋求第n n次最近始發(fā)點(diǎn)的節(jié)點(diǎn)，次最近始發(fā)點(diǎn)的節(jié)點(diǎn)，重復(fù)重復(fù)n n1 1，2 2，直到最近的節(jié)點(diǎn)是終點(diǎn)為止。，直到最近的節(jié)點(diǎn)是終點(diǎn)為止。 (2) (2)第第n n次迭代的輸入值。次迭代的輸入值。(n1)(n1)個(gè)最近始發(fā)點(diǎn)的節(jié)點(diǎn)個(gè)最近始發(fā)點(diǎn)的節(jié)點(diǎn)是由以前的迭

8、代根據(jù)離始發(fā)點(diǎn)最短路線和距離計(jì)算而得的。是由以前的迭代根據(jù)離始發(fā)點(diǎn)最短路線和距離計(jì)算而得的。 (3) (3)第第n n個(gè)最近節(jié)點(diǎn)的侯選點(diǎn)。每個(gè)已解的節(jié)點(diǎn)由線路個(gè)最近節(jié)點(diǎn)的侯選點(diǎn)。每個(gè)已解的節(jié)點(diǎn)由線路分支通向一個(gè)或多個(gè)尚未解的節(jié)點(diǎn)，這些未解的節(jié)點(diǎn)中有分支通向一個(gè)或多個(gè)尚未解的節(jié)點(diǎn)，這些未解的節(jié)點(diǎn)中有一個(gè)以最短路線分支連接的是候選點(diǎn)。一個(gè)以最短路線分支連接的是候選點(diǎn)。 (4) (4)第第n n個(gè)最近的節(jié)點(diǎn)的計(jì)算。將每個(gè)已解節(jié)點(diǎn)及其個(gè)最近的節(jié)點(diǎn)的計(jì)算。將每個(gè)已解節(jié)點(diǎn)及其候選點(diǎn)之間的距離和從始發(fā)點(diǎn)到該已解節(jié)點(diǎn)之間的距離加候選點(diǎn)之間的距離和從始發(fā)點(diǎn)到該已解節(jié)點(diǎn)之間的距離加起來(lái)，總距離最短的候選點(diǎn)即是第起

9、來(lái)，總距離最短的候選點(diǎn)即是第n n個(gè)最近的節(jié)點(diǎn)。也就個(gè)最近的節(jié)點(diǎn)。也就是始發(fā)點(diǎn)到達(dá)該點(diǎn)最短距離的路徑。是始發(fā)點(diǎn)到達(dá)該點(diǎn)最短距離的路徑。 以下面的實(shí)例可以具體說明最短運(yùn)輸路線是怎樣計(jì)算以下面的實(shí)例可以具體說明最短運(yùn)輸路線是怎樣計(jì)算的。的?！纠咳鐖D所示是一張公路運(yùn)輸網(wǎng)示意圖，其中【例】如圖所示是一張公路運(yùn)輸網(wǎng)示意圖，其中A是起點(diǎn)，是起點(diǎn)，J是終點(diǎn)，是終點(diǎn)，B、C、D、E、G、H、I是網(wǎng)是網(wǎng)絡(luò)中的結(jié)點(diǎn)，結(jié)點(diǎn)與結(jié)點(diǎn)之間以線路連接，線路絡(luò)中的結(jié)點(diǎn)，結(jié)點(diǎn)與結(jié)點(diǎn)之間以線路連接，線路上標(biāo)明了兩個(gè)結(jié)點(diǎn)的距離，以運(yùn)行時(shí)間（分）表上標(biāo)明了兩個(gè)結(jié)點(diǎn)的距離，以運(yùn)行時(shí)間（分）表示。要求確定一條從起點(diǎn)示。要求確定一條從起

10、點(diǎn)A到終點(diǎn)到終點(diǎn)J的最短的運(yùn)輸?shù)淖疃痰倪\(yùn)輸路線。路線。A起點(diǎn)起點(diǎn)BEIJ終點(diǎn)終點(diǎn)HFCDG8490841383481564813215090601321264812666120 我們首先列出一張如表格我們首先列出一張如表格3 33 3所示的表格。所示的表格。第一個(gè)已解的節(jié)點(diǎn)就是起點(diǎn)或點(diǎn)第一個(gè)已解的節(jié)點(diǎn)就是起點(diǎn)或點(diǎn)A A。與。與A A點(diǎn)直接連點(diǎn)直接連接的解的節(jié)點(diǎn)有接的解的節(jié)點(diǎn)有B B、C C和和D D點(diǎn)。第一步，我們可以看點(diǎn)。第一步，我們可以看到到B B點(diǎn)是距點(diǎn)是距A A點(diǎn)最近的節(jié)點(diǎn)，記為點(diǎn)最近的節(jié)點(diǎn)，記為ABAB。由于。由于B B點(diǎn)是唯點(diǎn)是唯一選擇，所以它成為已解的節(jié)點(diǎn)。一選擇，所以它成為已解

11、的節(jié)點(diǎn)。 隨后，找出距隨后，找出距A A點(diǎn)和點(diǎn)和B B點(diǎn)最近的未解的節(jié)點(diǎn)。只要列出點(diǎn)最近的未解的節(jié)點(diǎn)。只要列出距各個(gè)已解的節(jié)點(diǎn)最近的連接點(diǎn)，我們有距各個(gè)已解的節(jié)點(diǎn)最近的連接點(diǎn)，我們有A-CA-C，B BC C。記。記為第二步。注意從起點(diǎn)通過已解的節(jié)點(diǎn)到某一節(jié)點(diǎn)所需的為第二步。注意從起點(diǎn)通過已解的節(jié)點(diǎn)到某一節(jié)點(diǎn)所需的時(shí)間應(yīng)該等于到達(dá)這個(gè)已解節(jié)點(diǎn)的最短時(shí)間加上已解節(jié)點(diǎn)時(shí)間應(yīng)該等于到達(dá)這個(gè)已解節(jié)點(diǎn)的最短時(shí)間加上已解節(jié)點(diǎn)與未解節(jié)點(diǎn)之間的時(shí)間，也就是說，從與未解節(jié)點(diǎn)之間的時(shí)間，也就是說，從A A點(diǎn)經(jīng)過點(diǎn)經(jīng)過B B點(diǎn)到達(dá)點(diǎn)到達(dá)C C的距離為的距離為AB+BCAB+BC90+6690+66156156分，而

12、從分，而從A A直達(dá)直達(dá)C C的時(shí)間為的時(shí)間為138138分?，F(xiàn)在分?，F(xiàn)在C C也成了已解的節(jié)點(diǎn)。也成了已解的節(jié)點(diǎn)。 第三次迭代要找到與各已解節(jié)點(diǎn)直接連接的最近的未第三次迭代要找到與各已解節(jié)點(diǎn)直接連接的最近的未解節(jié)點(diǎn)。如表解節(jié)點(diǎn)。如表3 33 3所示，有三個(gè)候選點(diǎn)，從起點(diǎn)到這三個(gè)所示，有三個(gè)候選點(diǎn)，從起點(diǎn)到這三個(gè)候選點(diǎn)候選點(diǎn)D D、E E、F F所需的時(shí)間，相應(yīng)為所需的時(shí)間，相應(yīng)為348348、174174、228228分，其分，其中連接中連接BEBE的時(shí)間最短，為的時(shí)間最短，為174174分，因此正點(diǎn)就是第三次迭分，因此正點(diǎn)就是第三次迭代的結(jié)果。代的結(jié)果。 重復(fù)上述過程直到到達(dá)終點(diǎn)重復(fù)上述過

13、程直到到達(dá)終點(diǎn)J J，即第八步。最小的路，即第八步。最小的路線時(shí)間是線時(shí)間是384384分，連線在表分，連線在表3 33 3上以星上以星( (并并) )符號(hào)標(biāo)出者，符號(hào)標(biāo)出者，最優(yōu)路線為最優(yōu)路線為A-B-E-I-JA-B-E-I-J。 在節(jié)點(diǎn)很多時(shí)用手工計(jì)算比較繁雜，如果把網(wǎng)絡(luò)的節(jié)在節(jié)點(diǎn)很多時(shí)用手工計(jì)算比較繁雜，如果把網(wǎng)絡(luò)的節(jié)點(diǎn)和連線的有關(guān)數(shù)據(jù)存入數(shù)據(jù)庫(kù)中，絕對(duì)的最短距離路徑點(diǎn)和連線的有關(guān)數(shù)據(jù)存入數(shù)據(jù)庫(kù)中，絕對(duì)的最短距離路徑并不說明穿越網(wǎng)絡(luò)的最短時(shí)間，因?yàn)樵摲椒]有考慮各條并不說明穿越網(wǎng)絡(luò)的最短時(shí)間，因?yàn)樵摲椒]有考慮各條路線的運(yùn)行質(zhì)量。路線的運(yùn)行質(zhì)量。 因此，對(duì)運(yùn)行時(shí)間和距離都設(shè)定權(quán)數(shù)就可以

14、得出比較因此，對(duì)運(yùn)行時(shí)間和距離都設(shè)定權(quán)數(shù)就可以得出比較具有實(shí)際意義的路線。具有實(shí)際意義的路線?！揪毩?xí)】如圖所示是一張公路運(yùn)輸網(wǎng)示意圖，其中【練習(xí)】如圖所示是一張公路運(yùn)輸網(wǎng)示意圖，其中A是起點(diǎn)，是起點(diǎn)，I是終點(diǎn)，是終點(diǎn)，B、C、D、E、G、H是網(wǎng)絡(luò)是網(wǎng)絡(luò)中的結(jié)點(diǎn)，結(jié)點(diǎn)與結(jié)點(diǎn)之間以線路連接，線路上中的結(jié)點(diǎn)，結(jié)點(diǎn)與結(jié)點(diǎn)之間以線路連接，線路上標(biāo)明了兩個(gè)結(jié)點(diǎn)的距離，以運(yùn)行時(shí)間（分）表示。標(biāo)明了兩個(gè)結(jié)點(diǎn)的距離，以運(yùn)行時(shí)間（分）表示。要求確定一條從起點(diǎn)要求確定一條從起點(diǎn)A到終點(diǎn)到終點(diǎn)I的最短的運(yùn)輸路線。的最短的運(yùn)輸路線。A起點(diǎn)起點(diǎn)BCDEFGHI終點(diǎn)終點(diǎn)204060603060505050502045308

15、0100物流管理人員經(jīng)常遇到的一個(gè)路線選擇問題是始發(fā)點(diǎn)就是終物流管理人員經(jīng)常遇到的一個(gè)路線選擇問題是始發(fā)點(diǎn)就是終點(diǎn)的路線選擇。這類問題通常在運(yùn)輸工具是同一部門所有點(diǎn)的路線選擇。這類問題通常在運(yùn)輸工具是同一部門所有的情況下發(fā)生。始發(fā)點(diǎn)和終點(diǎn)相合的路線選擇問題通常被的情況下發(fā)生。始發(fā)點(diǎn)和終點(diǎn)相合的路線選擇問題通常被稱為稱為“旅行推銷員旅行推銷員”問題，對(duì)這類問題應(yīng)用經(jīng)驗(yàn)探試法比問題，對(duì)這類問題應(yīng)用經(jīng)驗(yàn)探試法比較有效。較有效。 經(jīng)驗(yàn)告訴我們，當(dāng)運(yùn)行路線不發(fā)生交叉時(shí)，經(jīng)過各經(jīng)驗(yàn)告訴我們，當(dāng)運(yùn)行路線不發(fā)生交叉時(shí)，經(jīng)過各停留點(diǎn)的次序是合理的，同時(shí)，如有可能應(yīng)盡量使運(yùn)行路停留點(diǎn)的次序是合理的，同時(shí)，如有可能

16、應(yīng)盡量使運(yùn)行路線形成淚滴狀。圖線形成淚滴狀。圖3 32 2所示是通過各點(diǎn)的運(yùn)行路線示意圖，所示是通過各點(diǎn)的運(yùn)行路線示意圖，其中圖其中圖3 32(a)2(a)是不合理的運(yùn)行路線，圖是不合理的運(yùn)行路線，圖3 32(b)2(b)是合理的是合理的運(yùn)行路線。根據(jù)上述運(yùn)行路線。根據(jù)上述“運(yùn)行路線不發(fā)生交叉運(yùn)行路線不發(fā)生交叉”“”“運(yùn)行路線運(yùn)行路線形成淚滴狀形成淚滴狀”兩點(diǎn)原則。兩點(diǎn)原則。（1 1）人工計(jì)算方法）人工計(jì)算方法掃描法掃描法 問題：對(duì)于若干個(gè)停車點(diǎn)（客戶）安排最優(yōu)行車路線。問題：對(duì)于若干個(gè)停車點(diǎn)（客戶）安排最優(yōu)行車路線。第一步，將倉(cāng)庫(kù)（出發(fā)點(diǎn)）和所有的停車點(diǎn)位置畫在地圖第一步，將倉(cāng)庫(kù)（出發(fā)點(diǎn)）和

17、所有的停車點(diǎn)位置畫在地圖上或坐標(biāo)圖上；上或坐標(biāo)圖上；第二步，通過倉(cāng)庫(kù)位置放置一直尺，然后順時(shí)針或逆時(shí)針第二步，通過倉(cāng)庫(kù)位置放置一直尺，然后順時(shí)針或逆時(shí)針方向轉(zhuǎn)動(dòng)，直到直尺交到一個(gè)停車點(diǎn)。詢問：方向轉(zhuǎn)動(dòng)，直到直尺交到一個(gè)停車點(diǎn)。詢問：累計(jì)的裝貨累計(jì)的裝貨量是否超過送貨的載重量或容積（首先要使用最大的送貨量是否超過送貨的載重量或容積（首先要使用最大的送貨車輛）車輛）。如是，最后的停車點(diǎn)排除，將路線確定下來(lái)。然。如是，最后的停車點(diǎn)排除，將路線確定下來(lái)。然后再?gòu)倪@個(gè)停車點(diǎn)開始繼續(xù)掃描，開始一條新的路線。這后再?gòu)倪@個(gè)停車點(diǎn)開始繼續(xù)掃描，開始一條新的路線。這樣掃描下去，直至全部的停留點(diǎn)都被分配到路線上。樣

18、掃描下去，直至全部的停留點(diǎn)都被分配到路線上。 第三步，對(duì)每條路線安排運(yùn)行順序，以求運(yùn)行距離最小化。第三步，對(duì)每條路線安排運(yùn)行順序，以求運(yùn)行距離最小化。方案的誤差率在方案的誤差率在10%10%左右。左右。掃描法掃描法 是是是是開始開始將所有的停留點(diǎn)位置畫在地圖上將所有的停留點(diǎn)位置畫在地圖上選擇適當(dāng)?shù)能囕v裝載這個(gè)停留點(diǎn)的貨物選擇適當(dāng)?shù)能囕v裝載這個(gè)停留點(diǎn)的貨物然后順時(shí)針或逆時(shí)針方向轉(zhuǎn)動(dòng)直尺，直到直尺交到一個(gè)停留點(diǎn)。然后順時(shí)針或逆時(shí)針方向轉(zhuǎn)動(dòng)直尺，直到直尺交到一個(gè)停留點(diǎn)。通過倉(cāng)庫(kù)位置放置一直尺，直尺指向任何方向均可通過倉(cāng)庫(kù)位置放置一直尺，直尺指向任何方向均可是否超過車輛容積或體積是否超過車輛容積或體積

19、的限度的限度是否掃描完所有是否掃描完所有停留點(diǎn)停留點(diǎn)安排下一輛車裝載貨物，得到一條運(yùn)行線路安排下一輛車裝載貨物，得到一條運(yùn)行線路結(jié)束結(jié)束繼續(xù)轉(zhuǎn)動(dòng)直尺，掃描到下一個(gè)停留點(diǎn)，分配該車輛繼續(xù)轉(zhuǎn)動(dòng)直尺，掃描到下一個(gè)停留點(diǎn)，分配該車輛裝載貨物裝載貨物優(yōu)化每條運(yùn)行路線的停留點(diǎn)順序，以求運(yùn)行距離最小優(yōu)化每條運(yùn)行路線的停留點(diǎn)順序，以求運(yùn)行距離最小化化否否否否l【例】某公司從其所屬的倉(cāng)庫(kù)用送貨車輛到各客戶點(diǎn)提貨，【例】某公司從其所屬的倉(cāng)庫(kù)用送貨車輛到各客戶點(diǎn)提貨，然后將客戶的貨物運(yùn)回倉(cāng)庫(kù)，以便集運(yùn)成大的批量再進(jìn)行然后將客戶的貨物運(yùn)回倉(cāng)庫(kù)，以便集運(yùn)成大的批量再進(jìn)行遠(yuǎn)程運(yùn)輸。全天的提貨量見下圖，提貨量以件為單位。送

20、遠(yuǎn)程運(yùn)輸。全天的提貨量見下圖，提貨量以件為單位。送貨車每次可運(yùn)載貨車每次可運(yùn)載1萬(wàn)件，完成一次運(yùn)行路線一般需要一天萬(wàn)件，完成一次運(yùn)行路線一般需要一天時(shí)間。該公司要求確定：需多少條路線（即多少輛送貨時(shí)間。該公司要求確定：需多少條路線（即多少輛送貨車）；每條路線上有哪幾個(gè)客戶點(diǎn)；送貨車輛途經(jīng)有關(guān)客車）；每條路線上有哪幾個(gè)客戶點(diǎn)；送貨車輛途經(jīng)有關(guān)客戶點(diǎn)的順序。戶點(diǎn)的順序。400040001000100030003000200020001000100020002000200020002000200020002000300030002000200030003000【例例】某運(yùn)輸公司為其客戶企業(yè)提供取貨服

21、務(wù)，貨物運(yùn)回倉(cāng)庫(kù)某運(yùn)輸公司為其客戶企業(yè)提供取貨服務(wù)，貨物運(yùn)回倉(cāng)庫(kù)集中后，將以更大的批量進(jìn)行長(zhǎng)途運(yùn)輸。所有取貨任務(wù)均由集中后，將以更大的批量進(jìn)行長(zhǎng)途運(yùn)輸。所有取貨任務(wù)均由載重量為載重量為1010噸的貨車完成?，F(xiàn)在有噸的貨車完成?，F(xiàn)在有1313家客戶有取貨要求，各家客戶有取貨要求，各客戶的去貨量、客戶的地理位置坐標(biāo)見表客戶的去貨量、客戶的地理位置坐標(biāo)見表7-107-10。運(yùn)輸公司倉(cāng)。運(yùn)輸公司倉(cāng)庫(kù)的坐標(biāo)為（庫(kù)的坐標(biāo)為（19.5019.50，5.565.56）。要求合理安排車輛，并確定各）。要求合理安排車輛，并確定各車輛行駛路線，使總運(yùn)輸里程最短。車輛行駛路線，使總運(yùn)輸里程最短。 3 2 2.4 2.

22、8 3.11.8 2.5 2.25 2.6 2.11.5 1.9 1.6 1#線路 2#線路 3#線路 11 12 9 10 7 8 2 1 5 4 3 13 6 0 (2)節(jié)約里程法 基本原理 基本原理是幾何學(xué)中三角形一邊之長(zhǎng)必定小于另外兩邊之和。 節(jié)約里程法核心思想是依次將運(yùn)輸問題中的兩個(gè)回路合并為一個(gè)回路，每次使合并后的總運(yùn)輸距離減小的幅度最大，直到達(dá)到一輛車的裝載限制時(shí)，再進(jìn)行下一輛車的優(yōu)化。優(yōu)化過程分為并行方式和串行方式兩種。 假如一家配送中心（DC）向兩個(gè)用戶A、B運(yùn)貨，配送中心到兩用戶的最短距離分別是La和Lb，A和B間的最短距離為L(zhǎng)ab，A、B的貨物需求量分別是Qa和Qb，且（

23、Qa+Qb）小于運(yùn)輸裝載量Q，如圖所示，如果配送中心分別送貨，那么需要兩個(gè)車次，總路程為：L1=2（La+Lb）。ABDCLaLbABDCLaLb Lab 如果改用一輛車對(duì)兩客戶進(jìn)行巡回送貨，則只需一個(gè)車次,行走的總路程為： L2=La+Lb+Lab 有三角形的性質(zhì)我們知道： LabL/2lL外外75+70145L/2lL內(nèi)內(nèi)大于全圈長(zhǎng)的一半，不是最優(yōu)方案，應(yīng)重新甩段大于全圈長(zhǎng)的一半，不是最優(yōu)方案，應(yīng)重新甩段破圈，甩內(nèi)圈運(yùn)量最小區(qū)段破圈，甩內(nèi)圈運(yùn)量最小區(qū)段a A，尋找最優(yōu)方案。，尋找最優(yōu)方案。150100CAD17016010011080130Babcd130807090803020l計(jì)算內(nèi)外

24、圈長(zhǎng)：計(jì)算內(nèi)外圈長(zhǎng)：lL/2（220+180+65+80+70+60+75+90）/2420lL內(nèi)內(nèi)180+80+60+90410L/2lL外外70+75+220365L/2l將上述運(yùn)輸結(jié)果填入平衡表：將上述運(yùn)輸結(jié)果填入平衡表：運(yùn)量運(yùn)量abcd產(chǎn)量產(chǎn)量A8080B13020150C8090170D7030100銷量銷量130100160110500接收地接收地發(fā)送地發(fā)送地【練習(xí)】某地區(qū)物資供銷情況如圖所示，現(xiàn)要求得物【練習(xí)】某地區(qū)物資供銷情況如圖所示，現(xiàn)要求得物資調(diào)運(yùn)的最優(yōu)方案。資調(diào)運(yùn)的最優(yōu)方案。3020502030607010020364523251823ABCDEFGHI302050203

25、06070100202020802030304010ABCDEFGHIl根據(jù)圖中箭頭將內(nèi)外圈貨流里程匯總，檢查是否超根據(jù)圖中箭頭將內(nèi)外圈貨流里程匯總，檢查是否超過全圈長(zhǎng)的一半。過全圈長(zhǎng)的一半。lL/2（45+23+25+18+23+36）/285lL內(nèi)內(nèi)25+18+2366L/2lL外外23+3659L/2l將上述運(yùn)輸結(jié)果填入平衡表：將上述運(yùn)輸結(jié)果填入平衡表：送貨量送貨量BCEGI產(chǎn)量產(chǎn)量A2020D2020F10302040100H303060銷量銷量3050207030200接收地接收地發(fā)送地發(fā)送地運(yùn)量運(yùn)量BCEGI產(chǎn)量產(chǎn)量A2020D2020F102070100H303060銷量銷量30

26、50207030200接收地接收地發(fā)送地發(fā)送地l當(dāng)運(yùn)輸路線有幾個(gè)圈的情況，應(yīng)逐圈檢查并調(diào)整，當(dāng)運(yùn)輸路線有幾個(gè)圈的情況，應(yīng)逐圈檢查并調(diào)整，直到每個(gè)圈都能符合要求，此時(shí)才能得到物資調(diào)撥直到每個(gè)圈都能符合要求，此時(shí)才能得到物資調(diào)撥的最優(yōu)方案。的最優(yōu)方案?！揪毩?xí)】【練習(xí)】29006002000100057ABCDEFHI900130032001000G1500900900784575132743257554174J166K290060020001000ABCDEFHI900130032001000G1500900900J150010009009009008005001009001500K距離距離ACE

27、FGIJK銷量銷量B15008009003200D5009006009002900H10010009002000產(chǎn)量產(chǎn)量15001300900600100010009009008100發(fā)送地發(fā)送地接收地接收地l表上作業(yè)法是單純形法在求解運(yùn)輸問題時(shí)的一表上作業(yè)法是單純形法在求解運(yùn)輸問題時(shí)的一種簡(jiǎn)化方法。它包括以下步驟：種簡(jiǎn)化方法。它包括以下步驟：1.確定初始可行方案。方法比較多，一般希望方確定初始可行方案。方法比較多，一般希望方法既簡(jiǎn)單，又盡可能接近最優(yōu)解，常用最小元法既簡(jiǎn)單，又盡可能接近最優(yōu)解，常用最小元素法、伏格爾法和左上角法。素法、伏格爾法和左上角法。2.最優(yōu)方案的判別。判別的方法是計(jì)算空

28、格的檢最優(yōu)方案的判別。判別的方法是計(jì)算空格的檢驗(yàn)數(shù)，常用閉回路法和位勢(shì)法。驗(yàn)數(shù)，常用閉回路法和位勢(shì)法。3.改進(jìn)方案。常使用閉回路調(diào)整法進(jìn)行調(diào)整以得改進(jìn)方案。常使用閉回路調(diào)整法進(jìn)行調(diào)整以得到最優(yōu)的方案。到最優(yōu)的方案。確定初始基可行解確定初始基可行解 |與一般的線性規(guī)劃不同，與一般的線性規(guī)劃不同，產(chǎn)銷平衡的運(yùn)輸問產(chǎn)銷平衡的運(yùn)輸問題一定具有可行解（同時(shí)也一定存在最優(yōu)解題一定具有可行解（同時(shí)也一定存在最優(yōu)解）。）。|最小元素法（最小元素法（the least cost rule）、伏格爾法）、伏格爾法（Vogels approximation method）和左上角）和左上角法。法。 z最小元素法的基

29、本思想是就近供應(yīng)，即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定產(chǎn)銷關(guān)系，依此類推，一直到給出基本方案為止.最小元素法|找出最小運(yùn)價(jià)，確定供求關(guān)系，最大量的供找出最小運(yùn)價(jià)，確定供求關(guān)系，最大量的供應(yīng)應(yīng) ；|劃掉已滿足要求的行或劃掉已滿足要求的行或 ( (和和) ) 列，如果需要列，如果需要同時(shí)劃去行和列，必須要在該行或列的任意同時(shí)劃去行和列，必須要在該行或列的任意位置填個(gè)位置填個(gè)“0”“0”；|在剩余的運(yùn)價(jià)表中重復(fù)在剩余的運(yùn)價(jià)表中重復(fù)1 1、2 2兩步，直到得到兩步，直到得到初始基可行解。初始基可行解。 最小元素法的基本步驟最小元素法的基本步驟|最小元素法最小元素法l最小元素法的基本思想是就近供應(yīng)，即最小

30、元素法的基本思想是就近供應(yīng)，即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定產(chǎn)從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定產(chǎn)銷關(guān)系，依此類推，一直到給出基本方銷關(guān)系，依此類推，一直到給出基本方案為止。案為止。l【例【例7】有某公司經(jīng)銷一產(chǎn)品，它下設(shè)三個(gè)加工廠，每日的產(chǎn)】有某公司經(jīng)銷一產(chǎn)品，它下設(shè)三個(gè)加工廠，每日的產(chǎn)量分別為量分別為A17噸、噸、A24噸，噸，A39噸，該公司把這些產(chǎn)品噸，該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)。各個(gè)銷售點(diǎn)每日銷量為分別運(yùn)往四個(gè)銷售點(diǎn)。各個(gè)銷售點(diǎn)每日銷量為B13噸，噸，B26噸，噸，B35噸，噸，B46噸，已知從各工廠到各銷售點(diǎn)的單噸，已知從各工廠到各銷售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)如表所示，問該公司應(yīng)

31、如何調(diào)運(yùn)產(chǎn)品，在滿足位產(chǎn)品的運(yùn)價(jià)如表所示，問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿足各銷點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)最少。各銷點(diǎn)的需要量的前提下，使總運(yùn)費(fèi)最少。B1B2B3B4A1311310A21928A374105銷地銷地加工廠加工廠B1B2B3B4產(chǎn)量產(chǎn)量A13113107A219284A3741059銷量銷量3656銷地銷地加工廠加工廠314633B1B2B3B4A143A231A363銷地銷地加工廠加工廠l【例【例8】編制被運(yùn)輸商品的產(chǎn)銷平衡表和單位運(yùn)輸價(jià)格如下表】編制被運(yùn)輸商品的產(chǎn)銷平衡表和單位運(yùn)輸價(jià)格如下表所示，試用最小元素法求出最優(yōu)運(yùn)輸方案的初始方案。所示，試用最小元素法求出最優(yōu)運(yùn)輸方案的

32、初始方案。ABCDE發(fā)運(yùn)量發(fā)運(yùn)量甲甲32353100乙乙33134300丙丙78422600丁丁54778800需求量需求量2503003504005001800銷地銷地加工廠加工廠ABCDE發(fā)運(yùn)量發(fā)運(yùn)量甲甲32353100乙乙33134300丙丙78422600丁丁54778800需求量需求量2503003504005001800銷地銷地加工廠加工廠30010050010020025030050 應(yīng)注意的問題 l【練習(xí)】最小元素法【練習(xí)】最小元素法123產(chǎn)量產(chǎn)量15181222411433674銷量銷量91011銷地銷地加工廠加工廠1011342l最小元素法的缺點(diǎn)是：為了節(jié)省一處的費(fèi)用，最小

33、元素法的缺點(diǎn)是：為了節(jié)省一處的費(fèi)用，有時(shí)造成在其它處要多花幾倍的運(yùn)費(fèi)。有時(shí)造成在其它處要多花幾倍的運(yùn)費(fèi)。l伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有一個(gè)差額，有一個(gè)差額，差額越大，說明不能按最小運(yùn)差額越大，說明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多，因而對(duì)差額最大費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多，因而對(duì)差額最大處，就應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)運(yùn)處，就應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)運(yùn)。伏格爾法的基本步驟：伏格爾法的基本步驟：1.1.計(jì)算每行、列兩個(gè)最小運(yùn)價(jià)的差；計(jì)算每行、列兩個(gè)最小運(yùn)價(jià)的差；2.2.找出最大差所在的行或

34、列；找出最大差所在的行或列；3.3.找出該行或列的最小運(yùn)價(jià)，確定供求關(guān)系，最大量找出該行或列的最小運(yùn)價(jià)，確定供求關(guān)系，最大量的供應(yīng)的供應(yīng) ；4.4.劃掉已滿足要求的行或劃掉已滿足要求的行或 ( (和和) ) 列，如果需要同時(shí)劃列，如果需要同時(shí)劃去行和列，必須要在該行或列的任意位置填個(gè)去行和列，必須要在該行或列的任意位置填個(gè)“0”“0”；5.5.在剩余的運(yùn)價(jià)表中重復(fù)在剩余的運(yùn)價(jià)表中重復(fù)1414步，直到得到初始基可步，直到得到初始基可行解。行解。l【例【例9】試用伏格爾求運(yùn)輸?shù)淖顑?yōu)方案?！吭囉梅駹柷筮\(yùn)輸?shù)淖顑?yōu)方案。銷地銷地加工廠加工廠B1B2B3B4產(chǎn)量產(chǎn)量A13113107A219284A37

35、41059銷量銷量3656銷地銷地加工廠加工廠B1B2B3B4產(chǎn)量產(chǎn)量A13113107A219284A3741059銷量銷量365601125136行差額行差額列差額列差額銷地銷地加工廠加工廠B1B2B3B4產(chǎn)量產(chǎn)量A13113107A219284A3741059銷量銷量365625136行差額行差額列差額列差額0123銷地銷地加工廠加工廠B1B2B3B4產(chǎn)量產(chǎn)量A13113107A219284A3741059銷量銷量36562126行差額行差額列差額列差額01233銷地銷地加工廠加工廠B1B2B3B4產(chǎn)量產(chǎn)量A13113107A219284A3741059銷量銷量3656126行差額行差額

36、列差額列差額7633521銷地銷地加工廠加工廠B1B2B3B4產(chǎn)量產(chǎn)量A17A24A39銷量銷量365663352112345產(chǎn)量產(chǎn)量11023159252510152430315514715204201513M830銷量銷量2020301025l【練習(xí)】伏格爾法，【練習(xí)】伏格爾法，M為無(wú)窮大的正數(shù)為無(wú)窮大的正數(shù)銷地銷地加工廠加工廠行差額行差額列差額列差額12255310542512345產(chǎn)量產(chǎn)量11023159252510152430315514715204201513M830銷量銷量2020301025銷地銷地加工廠加工廠行差額行差額列差額列差額1225105154252012345產(chǎn)量產(chǎn)

37、量11023159252510152430315514715204201513M830銷量銷量2020301025銷地銷地加工廠加工廠行差額行差額列差額列差額12251051542520100l（有時(shí)在產(chǎn)銷平衡表上填入一個(gè)運(yùn)量后，在單位運(yùn)價(jià)表上同時(shí)（有時(shí)在產(chǎn)銷平衡表上填入一個(gè)運(yùn)量后，在單位運(yùn)價(jià)表上同時(shí)劃去一行和一列，這時(shí)需要添一個(gè)劃去一行和一列，這時(shí)需要添一個(gè)“0”，它的位置可在對(duì)應(yīng)同，它的位置可在對(duì)應(yīng)同時(shí)劃去的那行或列的任一空格處）時(shí)劃去的那行或列的任一空格處）12345產(chǎn)量產(chǎn)量11023159252510152430315514715204201513M830銷量銷量2020301025銷

38、地銷地加工廠加工廠行差額行差額列差額列差額12951017252010202550012345產(chǎn)量產(chǎn)量125230320430銷量銷量2020301025銷地銷地加工廠加工廠2520102025500l【練習(xí)】伏格爾法【練習(xí)】伏格爾法123產(chǎn)量產(chǎn)量15181222411433674銷量銷量91011銷地銷地加工廠加工廠413行差額行差額136列差額列差額11l【練習(xí)】【練習(xí)】123產(chǎn)量產(chǎn)量15181222411433674銷量銷量91011銷地銷地加工廠加工廠423行差額行差額13列差額列差額1110342 左上角法左上角法 除了最小費(fèi)用法外，左上角法也是求得運(yùn)輸初始除了最小費(fèi)用法外，左上角法

39、也是求得運(yùn)輸初始方案的一種途徑，并通過霍撤克法則最終得出最方案的一種途徑，并通過霍撤克法則最終得出最優(yōu)運(yùn)輸方案。具體做法是：優(yōu)運(yùn)輸方案。具體做法是： 例現(xiàn)有三個(gè)生產(chǎn)地例現(xiàn)有三個(gè)生產(chǎn)地A、B、C供應(yīng)某種商品；供應(yīng)某種商品；有四個(gè)銷售地有四個(gè)銷售地1、2、3、4，各自供應(yīng)量和需求量，各自供應(yīng)量和需求量如表所示，試用左上角法求出最優(yōu)運(yùn)輸方案。如表所示，試用左上角法求出最優(yōu)運(yùn)輸方案。 第一步第一步 以運(yùn)輸表左上角的格子作為開端。以運(yùn)輸表左上角的格子作為開端。 第二步第二步 對(duì)這一格子可用的供應(yīng)量與需求量作對(duì)這一格子可用的供應(yīng)量與需求量作比較，安排兩個(gè)值中較小的一個(gè)作為運(yùn)量，然比較，安排兩個(gè)值中較小的一

40、個(gè)作為運(yùn)量，然后，把這個(gè)數(shù)字圈起來(lái)。這一格可用的供應(yīng)量后，把這個(gè)數(shù)字圈起來(lái)。這一格可用的供應(yīng)量( (或需求量或需求量) )減去安排的運(yùn)量就是剩余的供應(yīng)量減去安排的運(yùn)量就是剩余的供應(yīng)量( (或需求量或需求量) )。上表中有。上表中有5050個(gè)單位的供應(yīng)量和個(gè)單位的供應(yīng)量和3030個(gè)單位的需求量。因此，可以安排個(gè)單位的需求量。因此，可以安排3030單位的運(yùn)單位的運(yùn)量到量到A1A1格。格。 第三步第三步 如果安排運(yùn)量的格子正好是在運(yùn)輸表如果安排運(yùn)量的格子正好是在運(yùn)輸表的最右下角，就停止安排。這時(shí)，初始方案已的最右下角，就停止安排。這時(shí)，初始方案已找到。如果這一格不在最右下角，就進(jìn)入到第找到。如果這一

41、格不在最右下角，就進(jìn)入到第四步。四步。 第四步第四步 根據(jù)以下規(guī)劃，移到下一格：根據(jù)以下規(guī)劃，移到下一格： a a如果已安排的這一格行和列比較，供應(yīng)如果已安排的這一格行和列比較，供應(yīng)量超過需求量，下一格移到同一行相鄰的量超過需求量，下一格移到同一行相鄰的格子。格子。 b b如果需求量超過供應(yīng)量，下一格移到同如果需求量超過供應(yīng)量，下一格移到同一列相鄰的格子。一列相鄰的格子。 c c如果需求量等于供應(yīng)量，下一格是對(duì)角如果需求量等于供應(yīng)量，下一格是對(duì)角線上相鄰的格子線上相鄰的格子。 d d回到第二步?；氐降诙健?根據(jù)左上角法求出運(yùn)輸初始方案后，為了進(jìn)根據(jù)左上角法求出運(yùn)輸初始方案后，為了進(jìn)一步算出最

42、優(yōu)方案，仍需要運(yùn)用霍撒克法一步算出最優(yōu)方案，仍需要運(yùn)用霍撒克法則進(jìn)行優(yōu)化則進(jìn)行優(yōu)化單位單位 銷地銷地 運(yùn)價(jià)運(yùn)價(jià) 產(chǎn)地產(chǎn)地產(chǎn)量產(chǎn)量4124111621039108511522銷量銷量8141214484321 BBBB321AAA練習(xí) 某部門有3個(gè)生產(chǎn)同類產(chǎn)品的工廠（產(chǎn)地）,生產(chǎn)的產(chǎn)品由4個(gè)銷售點(diǎn)（銷地）出售，各工廠的生產(chǎn)量、個(gè)銷售點(diǎn)的銷售量（假定單位均為t)以及各工廠到個(gè)銷售點(diǎn)的單位云價(jià)（元/t)示于下表，試研究如何調(diào)運(yùn)才能使總的運(yùn)費(fèi)最小？ (1) 最小元素法 (2)西北角法 2 2 最優(yōu)方案的判別最優(yōu)方案的判別n對(duì)初始基可行解的最優(yōu)性檢驗(yàn)有對(duì)初始基可行解的最優(yōu)性檢驗(yàn)有閉合回路法閉合回路法和和

43、位勢(shì)法位勢(shì)法兩種基本方法。兩種基本方法。n閉合回路法具體、直接，并為方案調(diào)整指明閉合回路法具體、直接，并為方案調(diào)整指明了方向；了方向；n而位勢(shì)法具有批處理的功能，提高了計(jì)算效而位勢(shì)法具有批處理的功能，提高了計(jì)算效率。率。|所謂閉合回路法，就是對(duì)于代表非基變量的所謂閉合回路法，就是對(duì)于代表非基變量的空格（其調(diào)運(yùn)量為零），把它的調(diào)運(yùn)量調(diào)整空格（其調(diào)運(yùn)量為零），把它的調(diào)運(yùn)量調(diào)整為為1 1，由于產(chǎn)銷平衡的要求，由于產(chǎn)銷平衡的要求, ,我們必須對(duì)這個(gè)我們必須對(duì)這個(gè)空格的閉回路的頂點(diǎn)的調(diào)運(yùn)量加上或減少空格的閉回路的頂點(diǎn)的調(diào)運(yùn)量加上或減少1 1。最后我們計(jì)算出由這些變化給整個(gè)運(yùn)輸方案最后我們計(jì)算出由這些變化

44、給整個(gè)運(yùn)輸方案的總運(yùn)輸費(fèi)帶來(lái)的變化。的總運(yùn)輸費(fèi)帶來(lái)的變化。如果所有代表非基如果所有代表非基變量的空格的檢驗(yàn)數(shù)也即非基變量的檢驗(yàn)數(shù)變量的空格的檢驗(yàn)數(shù)也即非基變量的檢驗(yàn)數(shù)都大于等于零，則已求得最優(yōu)解，否則繼續(xù)都大于等于零，則已求得最優(yōu)解，否則繼續(xù)迭代找出最優(yōu)解。迭代找出最優(yōu)解。( (1 1) ). .閉合回路法閉合回路法 ijij 0 表示運(yùn)費(fèi)增加。表示運(yùn)費(fèi)增加。l所謂所謂閉合回路閉合回路是是在已給出的調(diào)運(yùn)方案的在已給出的調(diào)運(yùn)方案的運(yùn)輸表上從一個(gè)代表非基變量的空格出運(yùn)輸表上從一個(gè)代表非基變量的空格出發(fā)，沿水平或垂直方向前進(jìn)，發(fā)，沿水平或垂直方向前進(jìn)，只有遇到只有遇到代表基變量的填入數(shù)字的格才能向左

45、或代表基變量的填入數(shù)字的格才能向左或右轉(zhuǎn)右轉(zhuǎn)9090度（當(dāng)然也可以不改變方向）繼度（當(dāng)然也可以不改變方向）繼續(xù)前進(jìn)，這樣繼續(xù)下去，直至回到出發(fā)續(xù)前進(jìn)，這樣繼續(xù)下去，直至回到出發(fā)的那個(gè)空格，由此形成的封閉折線叫做的那個(gè)空格，由此形成的封閉折線叫做閉合回路閉合回路。一個(gè)空格存在唯一的閉回路一個(gè)空格存在唯一的閉回路。例一、某運(yùn)輸資料如下表所示：例一、某運(yùn)輸資料如下表所示：?jiǎn)挝粏挝?銷地銷地 運(yùn)價(jià)運(yùn)價(jià) 產(chǎn)地產(chǎn)地產(chǎn)量產(chǎn)量311310719284741059銷量銷量36564321 BBBB321AAAB1B2B3B4產(chǎn)量產(chǎn)量A13113107A219284A3741059銷量銷量3656銷地銷地加工廠加

46、工廠314633B1B2B3B4A143A231A363銷地銷地加工廠加工廠B1B2B3B4產(chǎn)量產(chǎn)量A17A24A39銷量銷量3656313463（1）（1）（1）（1） 計(jì)算如下：空格處（計(jì)算如下：空格處（ A1 B1 ） (13) (1)3 (12) (1)1 1 此數(shù)即為該空格處的檢驗(yàn)數(shù)。此數(shù)即為該空格處的檢驗(yàn)數(shù)。1B1B2B3B4產(chǎn)量產(chǎn)量A17A24A39銷量銷量365631363124B1B2B3B4產(chǎn)量產(chǎn)量A17A24A39銷量銷量36563136312-14B1B2B3B4產(chǎn)量產(chǎn)量A17A24A39銷量銷量365631363121-14B1B2B3B4產(chǎn)量產(chǎn)量A17A24A39銷

47、量銷量365631363121-1124B1B2B3B4產(chǎn)量產(chǎn)量A17A24A39銷量銷量365631363121-112104 檢驗(yàn)數(shù)中有負(fù)數(shù)，說明原方案不是最優(yōu)解。檢驗(yàn)數(shù)中有負(fù)數(shù)，說明原方案不是最優(yōu)解。B1B2B3B4產(chǎn)量產(chǎn)量A17A24A39銷量銷量365600000121-112100l使用位勢(shì)法求出檢驗(yàn)數(shù)，若檢驗(yàn)數(shù)都不使用位勢(shì)法求出檢驗(yàn)數(shù)，若檢驗(yàn)數(shù)都不為負(fù)數(shù)，則原方案為最優(yōu)解，若有負(fù)檢為負(fù)數(shù)，則原方案為最優(yōu)解，若有負(fù)檢驗(yàn)數(shù)存在，則負(fù)檢驗(yàn)數(shù)所在空格需進(jìn)行驗(yàn)數(shù)存在，則負(fù)檢驗(yàn)數(shù)所在空格需進(jìn)行調(diào)整。調(diào)整。l只有沒有運(yùn)量的空格處需要計(jì)算檢驗(yàn)數(shù)。只有沒有運(yùn)量的空格處需要計(jì)算檢驗(yàn)數(shù)。l檢驗(yàn)數(shù)的計(jì)算

48、方法如下：檢驗(yàn)數(shù)的計(jì)算方法如下：設(shè)有運(yùn)量的格子數(shù)最多的行或列的位勢(shì)設(shè)有運(yùn)量的格子數(shù)最多的行或列的位勢(shì)0有運(yùn)量格子的運(yùn)價(jià)行位勢(shì)有運(yùn)量格子的運(yùn)價(jià)行位勢(shì)+列位勢(shì)列位勢(shì)空格的檢驗(yàn)數(shù)運(yùn)價(jià)空格的檢驗(yàn)數(shù)運(yùn)價(jià)-（行位勢(shì)（行位勢(shì)+列位勢(shì)）列位勢(shì)） 接上例：接上例：B1B2B3B4A1310u1A212u2A345u3v1v2v3v4成本表成本表B1B2B3B4A1293100A218291A33425529310 u2+v1=1 u2+ v3 =2 u3+v2=4 u1+ v4 =10 u1+v3=3 u3+ v4 =5 令：令： u10u10 v12u2 1 v2 9u3 5 v3 3 v4 10 (ui+v

49、j) 按按ij=cij(ui+vj) 計(jì)算檢驗(yàn)數(shù)，并以計(jì)算檢驗(yàn)數(shù)，并以ij0 檢驗(yàn)，檢驗(yàn)，或用或用(ui+vj) cij 0 檢驗(yàn)。檢驗(yàn)。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A334-25(ui+vj)B1B2B3B4A11200A20101A3100120表中還有負(fù)數(shù)，表中還有負(fù)數(shù)，說明還未得到最說明還未得到最優(yōu)解，應(yīng)繼續(xù)調(diào)優(yōu)解，應(yīng)繼續(xù)調(diào)整。整。ijABCDE發(fā)運(yùn)量發(fā)運(yùn)量甲甲32353100乙乙33134300丙丙78422600丁丁54778800需求量需求量2503003504005001800銷地銷地加工廠加工廠30

50、01005005050250250300l【練習(xí)】下面是用最小元素法的得出的運(yùn)輸方案，【練習(xí)】下面是用最小元素法的得出的運(yùn)輸方案，試用位勢(shì)法判斷是否最優(yōu)。試用位勢(shì)法判斷是否最優(yōu)。 ABCDE行位勢(shì)行位勢(shì)甲甲32 3 53乙乙331 34丙丙7842 2 丁丁5 4 77 8列位勢(shì)列位勢(shì)銷地銷地加工廠加工廠0547-25-4-5700-2230179421從負(fù)檢驗(yàn)數(shù)所在格子出發(fā)找一條閉合回路，從負(fù)檢驗(yàn)數(shù)所在格子出發(fā)找一條閉合回路，用水平或垂直線向前劃，每碰到數(shù)字格可以用水平或垂直線向前劃，每碰到數(shù)字格可以轉(zhuǎn)轉(zhuǎn)90度，然后繼續(xù)前進(jìn)，直到回到起始空格度，然后繼續(xù)前進(jìn)，直到回到起始空格為止。為止。并從

51、出發(fā)格開始依次標(biāo)上正負(fù)號(hào)。并從出發(fā)格開始依次標(biāo)上正負(fù)號(hào)。將所有標(biāo)有負(fù)號(hào)的轉(zhuǎn)角格中的最小運(yùn)量作為將所有標(biāo)有負(fù)號(hào)的轉(zhuǎn)角格中的最小運(yùn)量作為調(diào)整數(shù)。調(diào)整數(shù)。各正號(hào)加上調(diào)整數(shù)，負(fù)號(hào)減去調(diào)整數(shù)。各正號(hào)加上調(diào)整數(shù)，負(fù)號(hào)減去調(diào)整數(shù)。l【例【例11】使用閉合回路法對(duì)例】使用閉合回路法對(duì)例10進(jìn)行調(diào)整。進(jìn)行調(diào)整。B1B2B3B4行位勢(shì)行位勢(shì)A1311310 A21 92 8A374 105 列位勢(shì)列位勢(shì)銷地銷地加工廠加工廠0310-1-529121-11012B1B2B3B4產(chǎn)量產(chǎn)量A13113107A219284A3741059銷量銷量3656銷地銷地加工廠加工廠314633+-152ABCDE行位勢(shì)行位勢(shì)甲甲

52、32 3 53乙乙331 34丙丙7842 2 丁丁5 4 77 8列位勢(shì)列位勢(shì)銷地銷地加工廠加工廠0547-25-4-5700-2230179421l【練習(xí)】使用閉合回路法對(duì)上一個(gè)練習(xí)題進(jìn)行調(diào)整?！揪毩?xí)】使用閉合回路法對(duì)上一個(gè)練習(xí)題進(jìn)行調(diào)整。 ABCDE發(fā)運(yùn)量發(fā)運(yùn)量甲甲32353100乙乙33134300丙丙78422600丁丁54778800需求量需求量2503003504005001800銷地銷地加工廠加工廠3001005005050250250300+-ABCDE發(fā)運(yùn)量發(fā)運(yùn)量甲甲32353100乙乙33134300丙丙78422600丁丁54778800需求量需求量2503003504

53、005001800銷地銷地加工廠加工廠3001504505050300250250+-l【例【例12】試用伏格爾法求，并檢驗(yàn)，得出最優(yōu)運(yùn)輸】試用伏格爾法求，并檢驗(yàn)，得出最優(yōu)運(yùn)輸方案。方案。1234供應(yīng)量供應(yīng)量A1067124B1610599C5410104銷量銷量5246銷地銷地加工廠加工廠費(fèi)用費(fèi)用1234供應(yīng)量供應(yīng)量A1067124B1610599C5410104銷量銷量5246銷地銷地加工廠加工廠費(fèi)用費(fèi)用行差額行差額14列差額列差額2115241234供應(yīng)量供應(yīng)量A1067124B1610599C5410104銷量銷量5246銷地銷地加工廠加工廠費(fèi)用費(fèi)用行差額行差額14列差額列差額2316

54、4411234供應(yīng)量供應(yīng)量A1067124B1610599C5410104銷量銷量5246銷地銷地加工廠加工廠費(fèi)用費(fèi)用行差額行差額14列差額列差額2344141234供應(yīng)量供應(yīng)量A1067124B1610599C5410104銷量銷量5246銷地銷地加工廠加工廠費(fèi)用費(fèi)用行差額行差額61列差額列差額2344142151234行位勢(shì)行位勢(shì)A106712B161059C541010列位勢(shì)列位勢(shì)銷地銷地加工廠加工廠費(fèi)用費(fèi)用414215010612-3-58-1973731234行位勢(shì)行位勢(shì)A106712B161059C541010列位勢(shì)列位勢(shì)銷地銷地加工廠加工廠費(fèi)用費(fèi)用414215+-+-136123

55、4行位勢(shì)行位勢(shì)A106712B161059C541010列位勢(shì)列位勢(shì)銷地銷地加工廠加工廠費(fèi)用費(fèi)用41213601067-2-5111863841234行位勢(shì)行位勢(shì)ABC列位勢(shì)列位勢(shì)銷地銷地加工廠加工廠運(yùn)量運(yùn)量412136l最優(yōu)運(yùn)輸方案如下最優(yōu)運(yùn)輸方案如下l【練習(xí)】試用伏格爾法求，并檢驗(yàn)，得出最優(yōu)運(yùn)輸【練習(xí)】試用伏格爾法求，并檢驗(yàn)，得出最優(yōu)運(yùn)輸方案。方案。1234供應(yīng)量供應(yīng)量A1518191350B2014151730C2512172270銷量銷量30602040150銷地銷地加工廠加工廠費(fèi)用費(fèi)用1234供應(yīng)量供應(yīng)量A1518191350B2014151730C2512172270銷量銷量306

56、02040150銷地銷地加工廠加工廠費(fèi)用費(fèi)用行差額行差額215列差額列差額5224601234供應(yīng)量供應(yīng)量A1518191350B2014151730C2512172270銷量銷量30602040150銷地銷地加工廠加工廠費(fèi)用費(fèi)用行差額行差額225列差額列差額522460301234供應(yīng)量供應(yīng)量A1518191350B2014151730C2512172270銷量銷量30602040150銷地銷地加工廠加工廠費(fèi)用費(fèi)用行差額行差額625列差額列差額52246030201234供應(yīng)量供應(yīng)量A1518191350B2014151730C2512172270銷量銷量30602040150銷地銷地加工廠

57、加工廠費(fèi)用費(fèi)用行差額行差額25列差額列差位勢(shì)行位勢(shì)A15 181913 B201415 17 C2512 17 22列位勢(shì)列位勢(shì)銷地銷地加工廠加工廠費(fèi)用費(fèi)用015134116612814431234供應(yīng)量供應(yīng)量A50B30C70銷量銷量30602040150銷地銷地加工廠加工廠運(yùn)量運(yùn)量603020201010l最優(yōu)運(yùn)輸方案如下最優(yōu)運(yùn)輸方案如下l【練習(xí)】試用最小元素法求，并檢驗(yàn)，得出最優(yōu)運(yùn)【練習(xí)】試用最小元素法求，并檢驗(yàn)，得出最優(yōu)運(yùn)輸方案。輸方案。123供應(yīng)量供應(yīng)量A51312B24114C3674銷量銷量91011銷地銷地加工廠加工廠費(fèi)用費(fèi)用123供應(yīng)量

58、供應(yīng)量A51312B24114C3674銷量銷量91011銷地銷地加工廠加工廠費(fèi)用費(fèi)用1011342123行位勢(shì)行位勢(shì)A513B241C367列位勢(shì)列位勢(shì)銷地銷地加工廠加工廠費(fèi)用費(fèi)用10113420523-4-1-1675123行位勢(shì)行位勢(shì)A513B241C367列位勢(shì)列位勢(shì)銷地銷地加工廠加工廠費(fèi)用費(fèi)用1011342+-+-123行位勢(shì)行位勢(shì)A513B241C367列位勢(shì)列位勢(shì)銷地銷地加工廠加工廠費(fèi)用費(fèi)用10954+-+-2123行位勢(shì)行位勢(shì)A513B241C367列位勢(shì)列位勢(shì)銷地銷地加工廠加工廠費(fèi)用費(fèi)用109542013-24-11565123行位勢(shì)行位勢(shì)ABC列位勢(shì)列位勢(shì)銷地銷地加工廠加工

59、廠運(yùn)量運(yùn)量109542l最優(yōu)運(yùn)輸方案如下最優(yōu)運(yùn)輸方案如下l在運(yùn)輸?shù)膶?shí)際工作中，由于經(jīng)濟(jì)活動(dòng)和市在運(yùn)輸?shù)膶?shí)際工作中，由于經(jīng)濟(jì)活動(dòng)和市場(chǎng)環(huán)境的多變性，經(jīng)常會(huì)存在供求不平衡場(chǎng)環(huán)境的多變性，經(jīng)常會(huì)存在供求不平衡的現(xiàn)象，此時(shí)應(yīng)對(duì)上述的方法進(jìn)行一定的的現(xiàn)象，此時(shí)應(yīng)對(duì)上述的方法進(jìn)行一定的修正。修正。l修正的基本思路是：修正的基本思路是：化不均衡為均衡，如化不均衡為均衡，如果出現(xiàn)供求不平衡，則設(shè)一個(gè)虛銷點(diǎn)或虛果出現(xiàn)供求不平衡，則設(shè)一個(gè)虛銷點(diǎn)或虛發(fā)點(diǎn)，得出最優(yōu)方案后再去掉虛設(shè)的點(diǎn)發(fā)點(diǎn)，得出最優(yōu)方案后再去掉虛設(shè)的點(diǎn)。l【例【例12】1234供應(yīng)量供應(yīng)量A1518191350B2014151755C25121722

60、70銷量銷量30602040銷地銷地加工廠加工廠費(fèi)用費(fèi)用l【例【例12】12345供應(yīng)量供應(yīng)量20141517055C25121722070銷量銷量3060204025銷地銷地加工廠加工廠費(fèi)用費(fèi)用l解決供求不均衡問題時(shí)，可使用解決供求不均衡問題時(shí)，可使用西北角法西北角法來(lái)求得初始可來(lái)求得初始可行方案。行方案。3020401554025l【例【例12】12345行位勢(shì)行位勢(shì)A151819130B201415170C251217220列位勢(shì)列位勢(shì)銷地銷地加工廠加工廠費(fèi)用費(fèi)用3020401554025002217-2162130-9-29-312-42l【例【例12】123