第3章 運輸問題

1、 運輸問題與有關概念運輸問題與有關概念 運輸問題的求解運輸問題的求解表上作業(yè)法表上作業(yè)法人們在從事生產(chǎn)活動中，不可避免地要進行物資調運工作。如人們在從事生產(chǎn)活動中，不可避免地要進行物資調運工作。如某時期內將生產(chǎn)基地的煤、鋼鐵、糧食等各類物資，分別運到某時期內將生產(chǎn)基地的煤、鋼鐵、糧食等各類物資，分別運到需要這些物資的地區(qū)，根據(jù)各地的需要這些物資的地區(qū)，根據(jù)各地的生產(chǎn)量生產(chǎn)量和和需要量需要量及各地之間及各地之間的的運輸費用運輸費用，如何制定一個運輸方案，使總的運輸費用最小。，如何制定一個運輸方案，使總的運輸費用最小。這樣的問題稱為這樣的問題稱為運輸問題運輸問題。 運輸問題是一類常見而且極其典型的

2、運輸問題是一類常見而且極其典型的LP問題。從問題。從理論上講，運輸問題可以用單純型來求解。但由理論上講，運輸問題可以用單純型來求解。但由于運輸問題數(shù)學模型具有特殊的結構，存在一種于運輸問題數(shù)學模型具有特殊的結構，存在一種比單純型法更簡便的計算方法比單純型法更簡便的計算方法表上作業(yè)法。表上作業(yè)法。用表上作業(yè)法來求解運輸問題比單純型可節(jié)約計用表上作業(yè)法來求解運輸問題比單純型可節(jié)約計算時間與計算費用，但表上作業(yè)法實質上仍是單算時間與計算費用，但表上作業(yè)法實質上仍是單純型法。純型法。 某公司從三個產(chǎn)地某公司從三個產(chǎn)地A1、A2、A3 將物品運將物品運往四個銷地往四個銷地B1、B2、B3、B4，各產(chǎn)地的

3、產(chǎn)量、各，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示如下表所示 問應如何調運，可使得總運輸費最小問應如何調運，可使得總運輸費最小? 這是一個產(chǎn)銷平衡的運輸問題，設這是一個產(chǎn)銷平衡的運輸問題，設 xij 為從產(chǎn)為從產(chǎn)地地 Ai 運往銷地運往銷地 Bj 的運輸量（的運輸量（i = 1，2，3； j = 1，2，3，4）所以此運輸問題的線性規(guī)劃模型如下：所以此運輸問題的線性規(guī)劃模型如下： Min z= 2x11+ 9x12+ 10 x13+ 7x14+ x21+ 3x22 + 4x23+ 2x24+ 8x31+ 4x32+ 2x33

4、+ 5x34s.t. x11+ x12 + x13 + x14 = 9 x21 + x22+ x23 + x24 = 5 x31 + x32+ x33 + x24 = 7 x11 + x21 + x31 = 3 x12 + x22 + x32 = 8 x13 + x23 + x33 = 4 x14 + x24 + x34 = 6 xij 0 ( i = 1 , 2 , 3；j = 1 , 2 , 3,4)其系數(shù)矩陣為其系數(shù)矩陣為 ：1000100010000100010001000010001000100001000100011111000000000000111100000000000011

5、11A 共有共有 3+4 行，分別表示產(chǎn)地和銷地；有行，分別表示產(chǎn)地和銷地；有 3 4 列分列分別表示各變量；每列只有兩個別表示各變量；每列只有兩個 1，其余為，其余為 0 。表表31如果如果a1 + a2 + +am = b1 + b2 + + bn ， 則稱該運輸則稱該運輸問題為產(chǎn)銷平衡問題；否則，稱產(chǎn)銷不平衡。問題為產(chǎn)銷平衡問題；否則，稱產(chǎn)銷不平衡。 BjAiB1B2B3B4aiA1c11c12c13c14 a1x11x12x13x14A2c21c22 c23c24a2x21x22x23x24A3c31c32c2c34a3x31x32x33x34bjb1b2b3b4例如，例如，m=3,n

6、=4，將，將xij與運價與運價Cij放在同一張表中，如表所示。放在同一張表中，如表所示。運輸表運輸表 設設xij為從產(chǎn)地為從產(chǎn)地Ai運往銷地運往銷地Bj的物資數(shù)量的物資數(shù)量（i=1，m；j=1，n），由于從），由于從Ai運出運出的物資總量應等于的物資總量應等于Ai的產(chǎn)量的產(chǎn)量ai，因此，因此xij應滿應滿足：足： miaxnjiij, 2 , 11同理，運到同理，運到Bj的物資總量應該等于的物資總量應該等于Bj的銷量的銷量bj，所以，所以xij還應滿足：還應滿足： 總運費為：總運費為： mijijnjbx1, 1minjijijxcz11產(chǎn)銷平衡的運輸問題的數(shù)學模型為： mnmmnnxxxxx

7、xxxx,;,212222111211111111111111111111m行行n行行可以看出，可以看出，A是一個結構特殊的稀疏矩陣，其特點為是一個結構特殊的稀疏矩陣，其特點為 （1）A有有mn列，每列有（列，每列有（m+n)個元素，其中只有兩個為個元素，其中只有兩個為1，其余元素為，其余元素為0。nmbbbaaaA1111111111111111112121mnmmnnxxxxxxxxx,;,212222111211三、三、 產(chǎn)銷平衡運輸問題必存在可行解產(chǎn)銷平衡運輸問題必存在可行解 運輸問題是一種特殊的線性規(guī)劃問題，在求解運輸問題是一種特殊的線性規(guī)劃問題，在求解時依然可以采用單純形法的思路，

8、如時依然可以采用單純形法的思路，如圖圖3-1所示。所示。由于運輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用由于運輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計算，則無法利用這些有利線性規(guī)劃單純形法求解計算，則無法利用這些有利條件。人們在分析運輸規(guī)劃系數(shù)矩陣特征的基礎上條件。人們在分析運輸規(guī)劃系數(shù)矩陣特征的基礎上建立了針對運輸問題的表上作業(yè)法。在這里需要討建立了針對運輸問題的表上作業(yè)法。在這里需要討論基本可行解、檢驗數(shù)以及基的轉換等問題。論基本可行解、檢驗數(shù)以及基的轉換等問題。 ( (初初 始始 基本可行解基本可行解) ) （換基迭代）（換基迭代） 圖圖3-1 運輸問題求解思路圖運輸問題求解

9、思路圖小結：1.產(chǎn)銷平衡的運輸問題存在可行解，也一定存產(chǎn)銷平衡的運輸問題存在可行解，也一定存在最優(yōu)解在最優(yōu)解 ；2.有有m+n個約束，個約束，mn個變量；個變量；3.有有m+n1個基變量個基變量.3.2 表上作業(yè)法 運輸問題仍為線性規(guī)劃問題，可用單純形法運輸問題仍為線性規(guī)劃問題，可用單純形法解決，但是，解決，但是，（1）涉及變量多造成單純形表太大；）涉及變量多造成單純形表太大；（2）若把系數(shù)矩陣）若把系數(shù)矩陣0迭代為非零，使問題更迭代為非零，使問題更復雜；以上兩個原因使得我們不得不利用復雜；以上兩個原因使得我們不得不利用運輸問題的特點設計它的特殊解法運輸問題的特點設計它的特殊解法表表上作業(yè)法（

10、實質仍為單純形法）上作業(yè)法（實質仍為單純形法） 步驟：步驟：（1）找初始基本可行解（初始可調運方案）找初始基本可行解（初始可調運方案）可通過最小元素法、西北角法、伏格爾法可通過最小元素法、西北角法、伏格爾法完成完成（2）檢驗當前可行方案是否最優(yōu)（閉回路法）檢驗當前可行方案是否最優(yōu)（閉回路法和位勢法）如果是最優(yōu)解則停止計算，否和位勢法）如果是最優(yōu)解則停止計算，否則轉入下一步則轉入下一步（3）確定換入變量和換出變量，找出新的基）確定換入變量和換出變量，找出新的基可行解（方案調整）（閉回路法）可行解（方案調整）（閉回路法）（4）重復（）重復（2）（）（3）直到得到最優(yōu)解為止）直到得到最優(yōu)解為止一、初

11、始基本可行解的確定一、初始基本可行解的確定（一）最小元素法（一）最小元素法： 基本思想：基本思想：優(yōu)先滿足單位運價最小的供銷優(yōu)先滿足單位運價最小的供銷業(yè)務。業(yè)務。首先找出運價最小的，并以最大限首先找出運價最小的，并以最大限度滿足其供銷量為原則確定供銷業(yè)務。然度滿足其供銷量為原則確定供銷業(yè)務。然后，在余下的未確定的供銷業(yè)務中找運價后，在余下的未確定的供銷業(yè)務中找運價最小的，同樣以最大限度滿足其供銷量為最小的，同樣以最大限度滿足其供銷量為原則確定供銷業(yè)務，同樣的方法反復進行原則確定供銷業(yè)務，同樣的方法反復進行直到確定了所有的供銷業(yè)務，得到一個完直到確定了所有的供銷業(yè)務，得到一個完整的調運方案即初始

12、基本可行解為止。由整的調運方案即初始基本可行解為止。由于該方法基于優(yōu)先滿足單位運價最小的供于該方法基于優(yōu)先滿足單位運價最小的供銷業(yè)務，故稱為最小元素法銷業(yè)務，故稱為最小元素法。 BjAiB1B2B3B4aiA129107 9A213425A384257bj384621運輸表運輸表 銷地銷地 產(chǎn)地產(chǎn)地 B B1 1 B B2 2 B B3 3 B B4 4 產(chǎn)量產(chǎn)量 A A1 1 5 5 4 4 9 9 A A2 2 3 3 2 2 5 5 A A3 3 3 3 4 4 7 7 銷量銷量 3 3 8 8 4 4 6 6 2121 注注（1）有數(shù)格是基變量共）有數(shù)格是基變量共個，空格是非變量。共劃

13、去個，空格是非變量。共劃去 條線條線（2）如添上一個運量之后，能同時劃去兩條）如添上一個運量之后，能同時劃去兩條線（一行和一列）這時不能同時劃去行和線（一行和一列）這時不能同時劃去行和列，只能劃去一行或一列。列，只能劃去一行或一列。134 16mn 7mn（二）西北角法 西北角法與最小元素法不同，它不是優(yōu)先西北角法與最小元素法不同，它不是優(yōu)先考慮具有最小單位運價的供銷業(yè)務，而是考慮具有最小單位運價的供銷業(yè)務，而是優(yōu)先滿足運輸表中西北角（左上角）上空優(yōu)先滿足運輸表中西北角（左上角）上空格的供銷需求。按以上方法進行下去，最格的供銷需求。按以上方法進行下去，最后可得到初始方案。后可得到初始方案。 B

14、jAiB1B2B3B4aiA129107 9A213425A384257bj384621（三）伏格爾法（三）伏格爾法 最小元素法的缺點是：為了節(jié)省一處的費最小元素法的缺點是：為了節(jié)省一處的費用，有時造成在其它處要多花幾倍的運價。用，有時造成在其它處要多花幾倍的運價。伏格爾法考慮到，某產(chǎn)地的產(chǎn)品假如不能伏格爾法考慮到，某產(chǎn)地的產(chǎn)品假如不能按最小運價就近供應，就考慮次小運價，按最小運價就近供應，就考慮次小運價，這就有一個差額。差額越大，說明不能按這就有一個差額。差額越大，說明不能按最小運價調運時，運費增加越多。因而對最小運價調運時，運費增加越多。因而對差額最大的行或列，就應當采用最小運價差額最大的

15、行或列，就應當采用最小運價調運。調運。基于此思想，伏格爾法給出的初始基于此思想，伏格爾法給出的初始解比用最小元素法給出的初始解更接近最解比用最小元素法給出的初始解更接近最優(yōu)解優(yōu)解。步驟：步驟： （1）分別計算各行和各列的最小運價和次小運價的差額）分別計算各行和各列的最小運價和次小運價的差額（2）從行差額或列差額中選出最大者，選擇它所在行或列中的最小元素）從行差額或列差額中選出最大者，選擇它所在行或列中的最小元素 銷地銷地 產(chǎn)地產(chǎn)地 B B1 1 B B2 2 B B3 3 B B4 4 產(chǎn)量產(chǎn)量 A A1 1 5 5 1 1 9 9 A A2 2 5 5 5 5 A A3 3 3 3 4 4

16、7 7 銷量銷量 3 3 8 8 4 4 6 6 2121 3二、解的最優(yōu)性檢驗二、解的最優(yōu)性檢驗 在單純形法中，為了檢驗一個基本可行解是不是在單純形法中，為了檢驗一個基本可行解是不是最優(yōu)解，需要求出所有非基變量的檢驗數(shù)。在運最優(yōu)解，需要求出所有非基變量的檢驗數(shù)。在運輸問題中，每個空格對應一個非基變量。輸問題中，每個空格對應一個非基變量。 銷地銷地 產(chǎn)地產(chǎn)地 B B1 1 B B2 2 B B3 3 B B4 4 產(chǎn)量產(chǎn)量 A A1 1 5 5 4 4 9 9 A A2 2 3 3 2 2 5 5 A A3 3 3 3 4 4 7 7 銷量銷量 3 3 8 8 4 4 6 6 2121 132

17、222111,jijijijijijisssxxxxxxsssjijijijijijixxxxxx123221211,siii,21sjjj,21 若把閉回路的各變量格看作節(jié)點，在表中可若把閉回路的各變量格看作節(jié)點，在表中可以畫出如下形式的閉回路：以畫出如下形式的閉回路：閉回路示意圖閉回路示意圖 閉回路均為一封閉折線，它的每一條邊，閉回路均為一封閉折線，它的每一條邊，或為水平的，或為垂直的；或為水平的，或為垂直的； 閉回路的每一條邊（水平的或垂直的）閉回路的每一條邊（水平的或垂直的）均有且僅有兩個閉回路的頂點（基變量格）。均有且僅有兩個閉回路的頂點（基變量格）。 （a） （b） （c） （d）

18、 （e） BjAiB1B2B3B4aiA129107 9A213425A384257bj384621需計算非空格基變量檢驗數(shù)需計算非空格基變量檢驗數(shù) 閉回路法的主要缺點是：閉回路法的主要缺點是：當變量個數(shù)較多時，尋當變量個數(shù)較多時，尋找閉回路以及計算都會產(chǎn)生困難。找閉回路以及計算都會產(chǎn)生困難。則檢驗數(shù)為：則檢驗數(shù)為： ij = cij - ui - vj (非基變量檢驗數(shù)非基變量檢驗數(shù)) i = 1, , m ; j = 1, , n(基變量基變量)三、解的改進三、解的改進 (1) 找閉回路：找閉回路：以最小的負檢驗數(shù)對應的非基以最小的負檢驗數(shù)對應的非基變量為起始頂點尋找一個閉回路。變量為起始頂點尋找一個閉回路。 (2) 求調整量：求調整量： 閉回路上偶數(shù)次頂點運量的最閉回路上偶數(shù)次頂點運量的最小值為調整量，記作小值為調整量，記作: (3) 調整：調整： 閉回路上的偶數(shù)次頂點的調運量減閉回路上的偶數(shù)次頂點的調運量減去去 ； 閉回路上的奇數(shù)次頂點的調運量加上閉回路上的奇數(shù)次頂點的調運量加上 ；非閉回路頂點的其他變量調運量不變；再去掉閉回非閉回路頂點的其他變量調運量不變；再去掉閉回路上的一個零運量。路上的一個零運量。 銷銷產(chǎn)產(chǎn)A13519A255A3347需需求求384621 11= 4，作，作 x11 的閉回路，調整數(shù)的閉回路，調整數(shù)=3，調整得，調整得 銷銷產(chǎn)產(chǎn)