第13章運輸問題（TransportationProblem）在線性規劃問題中，有一類特殊類型的問題－－運輸問題。這類問題主要研究把某種物資從若干個產地調運到若干個銷地，每個產地的供應量和每個銷地的銷售量及從一個產地到一個銷地的運輸費用已知，要求確定一個總運費最少的方案。第13章運輸問題在線性規劃問題中，有一類1第13章運輸問題（TransportationProblem）物資調配問題（MaterialTransferringProblem）運輸問題及數學模型（ModelforTransportation）用表上作業法求解運輸問題（SolveTransportationProblembyTable）運輸問題的進-步討論（FurtherDiscussionaboutTransportationProblem）應用問題舉例（Parexample）第13章運輸問題（TransportationProb2物資調配問題在經濟建設中，經常會碰到大宗物資調運問題，如煤、鋼鐵，木材、糧食等物，在全國有若干生產基地，根據已有交通網絡，應如何制訂調運方案，將這些物資運到各銷售地點，而運費最小，效率最高。在物流系統中，物資的調撥和配送是物流管理決策的一項主要工作。在市場經濟條件下，對資源實行市場實行優化配置，有利于國民經濟持續發展。物資調配問題在經濟建設中，經常會碰到大宗物3運輸問題及數學模型本章研究單一品種物資的運輸調度問題。其典型情況是：設某種物品有個產地（或供方）Ai（i=1，2，…，m），各產地的產量分別是ai（i=1，2，…，m），有n個銷地Bj（j=1，2，…，n）,各銷地的銷量分別為bj（j=1，2，…，n）。假定從Ai（i=1，2，…，m）產地向銷地Bj（j=1，2，…，n）運輸單位物品的運價是。問怎樣調運這些物品才能使總運費最小?1.運輸問題數學模型運輸問題及數學模型本章研究單一品種物資的運4這是由多個產地供應多個銷地的單品種物品運輸問題。為直觀起見，可列出該問題的運輸表（見下頁）。表中的變量Xij（i=1，2，…，m；j=1，2，…，n）為由產地Ai運往銷地Bj的物品數量。cij為Ai到Bj的單位運價。有時，將單位運價單獨列入另一個表中，并稱其為運價表。運輸單價cij銷售地Bi供應量B1B2…Bnai產地AiA1c11c12…c1na1A2c21c22…c2na2┆┆┆…┆┆Amcm1cm2…cmnam銷售量bjb1b2…bn分布變量表A1x11x12…x1nA2x21x22…x2n┆┆┆…┆Amxm1xm2…xmn這是由多個產地供應多個銷地的單品種物品運輸問5產銷平衡運輸問題的數學模型可表示如下：其中，約束條件右側常數ai和bj滿足如果運輸問題的總產量等于其總銷量，即有則稱該運輸問題為產銷平衡運輸問題；反之，稱產銷不平衡運輸問題。產銷平衡運輸問題的數學模型可表示如下：其中，約束條件右側常數6（1）運輸問題有有限最優解2.運輸問題數學模型的特點對前述運輸問題，若令其變量其中，，則xij就是前述述運輸問題的一個可行解；另一方面，其目標函數有下界。目標函數值不會趨于-∞。由此可知，運輸問題必存在有限最優解。（1）運輸問題有有限最優解2.運輸問題數學模型的特點對前7（2）運輸問題約束條件的系數矩陣即除第i個和第m+j個分量為l外，其它分量全等于0。其系數列向量的結構是：（2）運輸問題約束條件的系數矩陣即除第i個和第m+j個分量8由此可知，運輸問題具有下述特點：（1）約束條件系數矩陣的元素等于0或1。（2）約束條件系數矩陣的每一列有兩個非零元素，這對應于每一個變量在前m個約束方程中出現一次，在后n個約束方程中也出現一次。對產銷平衡運輸問題，除上述兩個特點外，還有以下特點：所有結構約束條件都是等式約束，各產地產量之和等于各銷地銷量之和。由此可知，運輸問題具有下述特點：9例1：三煤礦A1，A2，A3運往B1，B2，B3，B4三個城市銷售，各煤礦的供應量和需求量如下頁表，各城市的需求量其間的距離(或單位運價)cij如表下頁表方格中的數據所示，試建立使總運輸量(或總運費)最小的運輸問題數學模型。單價cij銷售地Bj供應量aiB1B2B3B4供應地AiA11621020A2735820A3329440需求量bj302510158080例1：三煤礦A1，A2，A3運往B1，B2，B3，B4三個城10解：設Xij為第i煤礦向第j城市的供應量，cij表示為第i煤礦向第j城市供應煤的單位運價。i=1，2，3；j=1，2，3，4。本例中a1+a2+a3=b1+b2+b3+b4=80，故是產銷平衡運輸問題。則可寫出其數學模型。解：設Xij為第i煤礦向第j城市的供應量，cij表示為第i煤11根據運輸問題的數學模型求出的運輸問題的解X=(xij)，代表著一個運輸方案，其中每一個變量xij的值表示由Ai調運數量為xij的物品給Bij。前已指出運輸問題是一種線性規劃問題，可設想用迭代法進行求解，即先找出它的某一個基可行解，再進行解的最優性檢驗，若它不是最優解，就進行迭代調整，以得到一個新的更好的解，繼續檢驗和調整改進，直至得到最優解為止。3.運輸問題的解

根據運輸問題的數學模型求出的運輸問題的解X=(xij12例1的一個基可行解：單價cij銷售地Bj供應量aiB1B2B3B4供應地AiA11621020x11=20A2735820x21=10x22=10A3329440x32=15x33=15x34=15需求量bj30251015 8080例1的一個基可行解：單價cij銷售地Bj供應量aiB1B2B13用表上作業法求解運輸問題表上作業法是求解運輸問題的一種簡便而有效的方法，其求解工作在運輸表上進行。表上作業法是一種迭代法，迭代步驟為：先按某種規則找出一個初始解(初始調運方案)；再對現行解作最優性判別；若這個解不是最優解，就在運輸表上對它進行調整改進，得出一個新解；再判別，再改進；直至得到運輸問題的最優解為止。如前所述，迭代過程得出的所有解都要求是運輸問題的基可行解。用表上作業法求解運輸問題表上作業法是求解運輸問題的14步驟：（1）找出初始即可行解，即在產銷平衡表上分配初始調運方案，保證xij≥0，，并且xij>0的格（又稱實格）必須有m+n-1個；（2）求出各非基變量的檢驗數σij（空格檢驗數），σij≥0時停止計算；σij<0時在繼續調整調運方案（換基迭代法）；（3）確定進基變量（空格換入變量）和出基變量（實格調出變量），找出新的基可行解（用空格閉回路法調整）；（4）重復第1-3步，直至獲得σij≥0，輸出xij*和minZ=Z*為止。步驟：151.給出運輸問題的初始基可行解(初始調運方案)結合例1詳細說明表上作業法的解題步驟:（1）畫出運輸問題的求解作業表（見例1），由于，可以轉入（2）；（2）找出初始基可行解（又稱分配初始調運方案）。確定初始調運方案的方法很多，下面介紹三種常用的方法。單價cij銷售地Bj供應量aiB1B2B3B4供應地AiA11621020x11=20A2735820x21=10x22=10A3329440x32=15x33=15x34=15需求量bj30251015 80801.給出運輸問題的初始基可行解(初始調運方案)16a.最小元素法容易直觀想到，為了減少運費，應優先考慮單位運價最小(或運距最短)的供銷業務，最大限度地滿足其供銷量。即對所有i和j，找出ci0j0=min(cij)，并將xi0j0=min(ai0,bj0)的物品量由Ai0供應給Bj0；若xi0j0=ai0，則產地Ai0的可供物品己用完，以后不再繼續考慮這個產地，且Bj0的需求量由bj0減少為bj0-ai0。如果xi0j0=bj0，則銷地bj0的需求已全部得到滿足，以后不再考慮這個銷地，且Ai0的可供量由ai0減少為ai0-bj0。a.最小元素法17然后，在余下的供、銷點的供銷關系中，繼續按上述方法安排調運，直至安排完所有供銷任務，得到一個完整的調運方案(完整的解)為止。這樣就得到了運輸問題的一個初始基可行解(初始調運方案)。由于該方法基于優先滿足單位運價(或運距)最小的供銷業務．故稱為最小元素法。然后，在余下的供、銷點的供銷關系中，繼續按上述18最小元素法分配的初始調運方案單價cij銷售地Bj供應量aiB1B2B3B4供應地AiA11621020x11=20A2735820x23=10x24=10A3329440x31=10x32=25x34=5需求量bj30251015 8080最小元素法分配的初始調運方案單價cij銷售地Bj供應B1B19b.西北角法西北角法與最小元素法不同，它不是優先考慮具有最小單位運價的供銷業務，而是優先滿足運輸表中西北角(即左上角)上空格的供銷需求。b.西北角法20西北角法分配初始調運方案單價cij銷售地Bj供應量aiB1B2B3B4供應地AiA11621020x11=20A2735820x21=10x22=10A3329440x32=15x33=15x34=15需求量bj30251015 8080西北角法分配初始調運方案單價cij銷售地Bj供應B1B2B21c.沃格爾法使用最小元素法有時按某一最小單位運價優先安排調運時，可能導致不得不采用運費很高的其它供銷點對，使整個運輸費用增加。對每一個供應地或銷售地，均可由它到各銷售地或到各供應地的單位運價中找出最小單位運價和次小單位運價，并稱這兩個單位運價之差為該地的罰數。若罰數的值不大，當不能按最小單位運價安排運輸時造成的運費損失不大；反之，如果罰數的值很大，不按最小運價組織運輸就會造成很大損失，故應盡量按最小單位運價安排運輸。沃格爾法就是基于這種考慮提出來的。c.沃格爾法22沃格爾法分配初始調運方案單價cij銷售地Bj供應量ai行罰數B1B2B3B412345供應A1162102011⑤00x11=10x13=10地AiA2735820224④x22=20A332944011111x31=20x32=5x34=15需求量bj30251015

列罰數1213④

221③0

32100

44100

5④200

沃格爾法分配初始調運方案單價cij銷售地Bj供應量ai23對比以上3種方法的初始調運方案，可看出，伏格爾法優于其他方法，也就是說伏格爾法確定的初始解得目標函數距離最優解目標函數最近，因而迭代運算數為最少，效率高。方法西北角法最小元素法伏格爾法目標函數Z300250220對比以上3種方法的初始調運方案，可看出，伏格242.解的最優性檢驗要判定運輸問題的某個解是否為最優解，可仿照一般單純形法，檢驗這個解的各非基變量(對應于運輸表中的空格)的檢驗數，苦有某空格的檢驗數為負，說明將變為基變量將使運輸費用減少，故當前這個解不是最優解。若所有空格的檢驗數全非負，則不管樣變換解均能使運輸費用降低，即目標函數值已無法改進，這個解就是最優解。a.閉回路法2.解的最優性檢驗要判定運輸問題的某個解25現結合例1中用最小元素法給出的初始解，說明檢驗數的計算方法。其中一條閉回路檢驗數表銷售地供應地B1B2B3B4A1σ12=6σ13=3σ14=8A2σ21=0σ22=-–3*A3σ33=8因σ22=–3<0，故知該解不是最優解，還有待調整改正。現結合例1中用最小元素法給出的初始解，說明檢26閉回路可以是一個簡單的矩形，也可以是由水平和豎直邊線組成的其它更為復雜的封閉多邊形.閉回路可以是一個簡單的矩形，也可以是由水平和27運輸問題的進—步討論

上—節講述的運輸問題的算法，是以總產量等于總銷量(產銷平衡)為前提的。實際上在很多運輸問題中，總產量不等于總銷量。這時，為了使用前述表上作業法求解，就需將產銷不平衡運輸問題化為產銷平衡運輸問題。1.產銷不平衡的運輸問題運輸問題的進—步討論上—節講述的運輸問題的28如果總產量大于總銷量，即這時的數學模型是如果總產量大于總銷量，即29為借助于產銷平衡時的表上作業法求解，可增加一個假想的銷地Bn+1，由于實際上它不存在，因而由產地Ai(i=1,2,…,m)調運到這個假想銷地的物品數量xi,n+1(相當于松弛變量)，實際上是就地存貯在Ai的物品數量。就地存貯的物品不經運輸，故其單位運價ci,n+1(i=1,2,…,m)。為借助于產銷平衡時的表上作業法求解，可增加一個假想的30若令假想銷地的銷量為bn+1，且則模型變為對應的運輸表見下頁。若令假想銷地的銷量為bn+1，且對應的運輸表見下頁。31單價cij銷售地Bj供應量aiB1…BnBn+1供應地AiA1C11c12c1n0a1X11A2c21c22c2n0a2x21x22Amcm1cm2cmn0amx32x33x34需求量bjb1…Bn單價cij銷售地Bj供應B1…BnBn+1供A1C11c1232總銷量大于總產量的情形可仿照上述類似處理，即增加一個假想的產地Am+1，它的產量等于

由于這個假想的產地并不存在，求出的由它發往各個銷地的物品數量，實際上是各銷地所需物品的欠缺額，顯然有總銷量大于總產量的情形可仿照上述類似處理，即33單價cij銷售地Bj供應量aiB1B2B2B4供應地AiA1413459A21236106A3782610需求量bj54672522例：由各煤廠到各用戶的單位運價如表所示，請確定總運費最少的調運方案。單價cij銷售地Bj供應B1B2B2B4供A1413459A34單價cij銷售地BjB1B2B2B4供應地AiA141345A2123610A37826需求量bj546725-22=3供應量ai9610

555B5單價cij銷售地BjB1B2B2B435在以上討論中，假定物品由產地直接運送到銷售目的地，不經中間轉運。但是，常常會遇到這種情形：需先將物品由產地運到某個中間轉運站(可能是另外的產、銷地或中間轉運倉庫)，然后再轉運到銷售地。有時，經轉運比直接運到目的地更為經濟。總之，很多情況下，在決定運輸方案時有必要把轉運也考慮進去。顯然．考慮轉運將使運輸問題變得更為復雜。2.有轉運的運輸問題

(a)無轉運(b)包含轉運在以上討論中，假定物品由產地直接運送到銷售目36

假定m個產地A1,A2,…,Am和n個銷地B1,B2,…,Bn都可以作為中間轉運站使用，從而發送物品的地點相接收物品的地點都有m+n個。這樣一來，我們就得到了一個擴大了的運輸問題。為建立其數學模型，令：ai：第個i產地的產量(凈供應量)；bj：第j個銷地的銷量(凈需要量)；xij：由第i個發送地運到第j個接收地的物品數量；cij：由第i個發送地到第j個接收地的單位運價；ti：第i個地點轉運物品的數量；ci：第i個地點轉運單位物品的費用。假定m個產地A1,A2,…,Am和n個銷地B37現將產地和銷地統一編號，并把產地排在前面，銷地排在后面，則有假定為平衡運輸問題，即有現將產地和銷地統一編號，并把產地排在前面，銷地排在后面，則有38根據前面對平衡運輸問題的討論，可得該擴大了的運輸問題的數學模型如下：根據前面對平衡運輸問題的討論，可得該擴大了的運輸問題的數學模39將上述模型中的各約束等式右側的ti或tj移到等號左側，然后在各式等號兩端分別加上Q，并今，則可把模型寫成：將上述模型中的各約束等式右側的ti或tj移到等號左側，然后在40要特別注意，在此模型中，對所有i=j，cij=-ci。由于目標函數中這一項為常數，它不影響求最優解，在優化過程中可不予考慮。該模型的運輸表和運價表見下頁。當不考慮轉運費時，可令。要特別注意，在此模型中，對所有i=j，cij41運輸表接收地供應地供應地銷售地發送量1…mm+1…m+n供應地1x11…x1mx1,m+1…x1,m+nQ+a1……………………mxm.,1…xmmxm,m+1…xm,m+nQ+am銷售地m+1xm+1,1…xm+1,mxm+1,m+1…xm+1,m+nQ……………………m+nxm+n,1xm+1,n+mxm+n,m+1…xm+n,m+nQ接收量Q…QQ+bm+1…Q+bm+n運輸表接收地供應地銷售地42運價表接收地供應地供應地銷售地發送量1…mm+1…m+n供應地1-c1…c1mc1,m+1…c1,m+nQ+a1……………………mcm.,1…-cmcm,m+1…cm,m+nQ+am銷售地m+1cm+1,1…cm+1,mcm+1…cm+1,m+nQ……………………m+ncm+n,1cm+n,mvm+n,m+1…-cm+nQ接收量Q…QQ+bm+1…Q+bm+n運價表接收地供應地銷售地發送量1…m43例2：已知A1，A2，A3三個飲料廠生產同一規格的飲料，用相同價格供應B1，B2，B3三個銷售網點銷售。有兩個轉運站T1，T2，并且產品運輸可以在各產地，各銷售地及各轉運站之間轉運。已知各產地、銷地、中轉站相互之間每噸貨物的單位運價和產量，見下頁表。例2：已知A1，A2，A3三個飲料廠生產同一44各產地、銷地、中轉站之間的關系產地轉運站銷售地產量A1A2A3T1T2B1B2B3產地A1862━410830A2851395910A3654228720轉運站T12148463T2━328232銷售地B149242━5B2105863━4B38973254銷售量153510（1）對擴大的運輸問題建立運價表。對于沒有運輸路線的去任意大的正數M；對自己運輸的運價cij=0。（2）所有轉運站的轉運量等于銷量，即Q=30+20+10=15+35+10=60,取T1，T2的產量與運量均為60t。（3）在原來的產量與銷量的數值在加上調運量，三個產地的產量為90t，70t，80t,銷量均為60t；三個銷量為75t,95t,70t,產量均為60t.如下頁表所示。各產地、銷地、中轉站之間的關系產地轉運站銷售地產量A1A2A45用表上作業法求解的最優方案運量銷售地產量A1A2A3T1T2B1B2B3產地A160151590A2551570A3602080T15451060T2402060B16060B26060B36060銷售量6060606060759570用表上作業法求解的最優方案運量銷售地產量A1A246實際最優方案及最優運輸路線如圖，最小費用為300。A1A2A3B1B2B3T1T23015102015152020510實際最優方案及最優運輸路線如圖，最小費用為300。A1A2A47第11、12、13章知識小結預測概述時間序列預測技術移動平均預測法指數平滑預測法回歸分析預測技術一元線性回歸預測法多元線性回歸預測分析庫存優化確定性庫存模型確定性庫存基本模型缺貨事后補足的模型批量折扣庫存模型運輸問題物資調配問題運輸問題及數學模型用表上作業法求解運輸問題運輸問題的進-步討論應用問題舉例第11、12、13章知識小結預測概述庫存優化運輸問題48第13章運輸問題（TransportationProblem）在線性規劃問題中，有一類特殊類型的問題－－運輸問題。這類問題主要研究把某種物資從若干個產地調運到若干個銷地，每個產地的供應量和每個銷地的銷售量及從一個產地到一個銷地的運輸費用已知，要求確定一個總運費最少的方案。第13章運輸問題在線性規劃問題中，有一類49第13章運輸問題（TransportationProblem）物資調配問題（MaterialTransferringProblem）運輸問題及數學模型（ModelforTransportation）用表上作業法求解運輸問題（SolveTransportationProblembyTable）運輸問題的進-步討論（FurtherDiscussionaboutTransportationProblem）應用問題舉例（Parexample）第13章運輸問題（TransportationProb50物資調配問題在經濟建設中，經常會碰到大宗物資調運問題，如煤、鋼鐵，木材、糧食等物，在全國有若干生產基地，根據已有交通網絡，應如何制訂調運方案，將這些物資運到各銷售地點，而運費最小，效率最高。在物流系統中，物資的調撥和配送是物流管理決策的一項主要工作。在市場經濟條件下，對資源實行市場實行優化配置，有利于國民經濟持續發展。物資調配問題在經濟建設中，經常會碰到大宗物51運輸問題及數學模型本章研究單一品種物資的運輸調度問題。其典型情況是：設某種物品有個產地（或供方）Ai（i=1，2，…，m），各產地的產量分別是ai（i=1，2，…，m），有n個銷地Bj（j=1，2，…，n）,各銷地的銷量分別為bj（j=1，2，…，n）。假定從Ai（i=1，2，…，m）產地向銷地Bj（j=1，2，…，n）運輸單位物品的運價是。問怎樣調運這些物品才能使總運費最小?1.運輸問題數學模型運輸問題及數學模型本章研究單一品種物資的運52這是由多個產地供應多個銷地的單品種物品運輸問題。為直觀起見，可列出該問題的運輸表（見下頁）。表中的變量Xij（i=1，2，…，m；j=1，2，…，n）為由產地Ai運往銷地Bj的物品數量。cij為Ai到Bj的單位運價。有時，將單位運價單獨列入另一個表中，并稱其為運價表。運輸單價cij銷售地Bi供應量B1B2…Bnai產地AiA1c11c12…c1na1A2c21c22…c2na2┆┆┆…┆┆Amcm1cm2…cmnam銷售量bjb1b2…bn分布變量表A1x11x12…x1nA2x21x22…x2n┆┆┆…┆Amxm1xm2…xmn這是由多個產地供應多個銷地的單品種物品運輸問53產銷平衡運輸問題的數學模型可表示如下：其中，約束條件右側常數ai和bj滿足如果運輸問題的總產量等于其總銷量，即有則稱該運輸問題為產銷平衡運輸問題；反之，稱產銷不平衡運輸問題。產銷平衡運輸問題的數學模型可表示如下：其中，約束條件右側常數54（1）運輸問題有有限最優解2.運輸問題數學模型的特點對前述運輸問題，若令其變量其中，，則xij就是前述述運輸問題的一個可行解；另一方面，其目標函數有下界。目標函數值不會趨于-∞。由此可知，運輸問題必存在有限最優解。（1）運輸問題有有限最優解2.運輸問題數學模型的特點對前55（2）運輸問題約束條件的系數矩陣即除第i個和第m+j個分量為l外，其它分量全等于0。其系數列向量的結構是：（2）運輸問題約束條件的系數矩陣即除第i個和第m+j個分量56由此可知，運輸問題具有下述特點：（1）約束條件系數矩陣的元素等于0或1。（2）約束條件系數矩陣的每一列有兩個非零元素，這對應于每一個變量在前m個約束方程中出現一次，在后n個約束方程中也出現一次。對產銷平衡運輸問題，除上述兩個特點外，還有以下特點：所有結構約束條件都是等式約束，各產地產量之和等于各銷地銷量之和。由此可知，運輸問題具有下述特點：57例1：三煤礦A1，A2，A3運往B1，B2，B3，B4三個城市銷售，各煤礦的供應量和需求量如下頁表，各城市的需求量其間的距離(或單位運價)cij如表下頁表方格中的數據所示，試建立使總運輸量(或總運費)最小的運輸問題數學模型。單價cij銷售地Bj供應量aiB1B2B3B4供應地AiA11621020A2735820A3329440需求量bj302510158080例1：三煤礦A1，A2，A3運往B1，B2，B3，B4三個城58解：設Xij為第i煤礦向第j城市的供應量，cij表示為第i煤礦向第j城市供應煤的單位運價。i=1，2，3；j=1，2，3，4。本例中a1+a2+a3=b1+b2+b3+b4=80，故是產銷平衡運輸問題。則可寫出其數學模型。解：設Xij為第i煤礦向第j城市的供應量，cij表示為第i煤59根據運輸問題的數學模型求出的運輸問題的解X=(xij)，代表著一個運輸方案，其中每一個變量xij的值表示由Ai調運數量為xij的物品給Bij。前已指出運輸問題是一種線性規劃問題，可設想用迭代法進行求解，即先找出它的某一個基可行解，再進行解的最優性檢驗，若它不是最優解，就進行迭代調整，以得到一個新的更好的解，繼續檢驗和調整改進，直至得到最優解為止。3.運輸問題的解

根據運輸問題的數學模型求出的運輸問題的解X=(xij60例1的一個基可行解：單價cij銷售地Bj供應量aiB1B2B3B4供應地AiA11621020x11=20A2735820x21=10x22=10A3329440x32=15x33=15x34=15需求量bj30251015 8080例1的一個基可行解：單價cij銷售地Bj供應量aiB1B2B61用表上作業法求解運輸問題表上作業法是求解運輸問題的一種簡便而有效的方法，其求解工作在運輸表上進行。表上作業法是一種迭代法，迭代步驟為：先按某種規則找出一個初始解(初始調運方案)；再對現行解作最優性判別；若這個解不是最優解，就在運輸表上對它進行調整改進，得出一個新解；再判別，再改進；直至得到運輸問題的最優解為止。如前所述，迭代過程得出的所有解都要求是運輸問題的基可行解。用表上作業法求解運輸問題表上作業法是求解運輸問題的62步驟：（1）找出初始即可行解，即在產銷平衡表上分配初始調運方案，保證xij≥0，，并且xij>0的格（又稱實格）必須有m+n-1個；（2）求出各非基變量的檢驗數σij（空格檢驗數），σij≥0時停止計算；σij<0時在繼續調整調運方案（換基迭代法）；（3）確定進基變量（空格換入變量）和出基變量（實格調出變量），找出新的基可行解（用空格閉回路法調整）；（4）重復第1-3步，直至獲得σij≥0，輸出xij*和minZ=Z*為止。步驟：631.給出運輸問題的初始基可行解(初始調運方案)結合例1詳細說明表上作業法的解題步驟:（1）畫出運輸問題的求解作業表（見例1），由于，可以轉入（2）；（2）找出初始基可行解（又稱分配初始調運方案）。確定初始調運方案的方法很多，下面介紹三種常用的方法。單價cij銷售地Bj供應量aiB1B2B3B4供應地AiA11621020x11=20A2735820x21=10x22=10A3329440x32=15x33=15x34=15需求量bj30251015 80801.給出運輸問題的初始基可行解(初始調運方案)64a.最小元素法容易直觀想到，為了減少運費，應優先考慮單位運價最小(或運距最短)的供銷業務，最大限度地滿足其供銷量。即對所有i和j，找出ci0j0=min(cij)，并將xi0j0=min(ai0,bj0)的物品量由Ai0供應給Bj0；若xi0j0=ai0，則產地Ai0的可供物品己用完，以后不再繼續考慮這個產地，且Bj0的需求量由bj0減少為bj0-ai0。如果xi0j0=bj0，則銷地bj0的需求已全部得到滿足，以后不再考慮這個銷地，且Ai0的可供量由ai0減少為ai0-bj0。a.最小元素法65然后，在余下的供、銷點的供銷關系中，繼續按上述方法安排調運，直至安排完所有供銷任務，得到一個完整的調運方案(完整的解)為止。這樣就得到了運輸問題的一個初始基可行解(初始調運方案)。由于該方法基于優先滿足單位運價(或運距)最小的供銷業務．故稱為最小元素法。然后，在余下的供、銷點的供銷關系中，繼續按上述66最小元素法分配的初始調運方案單價cij銷售地Bj供應量aiB1B2B3B4供應地AiA11621020x11=20A2735820x23=10x24=10A3329440x31=10x32=25x34=5需求量bj30251015 8080最小元素法分配的初始調運方案單價cij銷售地Bj供應B1B67b.西北角法西北角法與最小元素法不同，它不是優先考慮具有最小單位運價的供銷業務，而是優先滿足運輸表中西北角(即左上角)上空格的供銷需求。b.西北角法68西北角法分配初始調運方案單價cij銷售地Bj供應量aiB1B2B3B4供應地AiA11621020x11=20A2735820x21=10x22=10A3329440x32=15x33=15x34=15需求量bj30251015 8080西北角法分配初始調運方案單價cij銷售地Bj供應B1B2B69c.沃格爾法使用最小元素法有時按某一最小單位運價優先安排調運時，可能導致不得不采用運費很高的其它供銷點對，使整個運輸費用增加。對每一個供應地或銷售地，均可由它到各銷售地或到各供應地的單位運價中找出最小單位運價和次小單位運價，并稱這兩個單位運價之差為該地的罰數。若罰數的值不大，當不能按最小單位運價安排運輸時造成的運費損失不大；反之，如果罰數的值很大，不按最小運價組織運輸就會造成很大損失，故應盡量按最小單位運價安排運輸。沃格爾法就是基于這種考慮提出來的。c.沃格爾法70沃格爾法分配初始調運方案單價cij銷售地Bj供應量ai行罰數B1B2B3B412345供應A1162102011⑤00x11=10x13=10地AiA2735820224④x22=20A332944011111x31=20x32=5x34=15需求量bj30251015

列罰數1213④

221③0

32100

44100

5④200

沃格爾法分配初始調運方案單價cij銷售地Bj供應量ai71對比以上3種方法的初始調運方案，可看出，伏格爾法優于其他方法，也就是說伏格爾法確定的初始解得目標函數距離最優解目標函數最近，因而迭代運算數為最少，效率高。方法西北角法最小元素法伏格爾法目標函數Z300250220對比以上3種方法的初始調運方案，可看出，伏格722.解的最優性檢驗要判定運輸問題的某個解是否為最優解，可仿照一般單純形法，檢驗這個解的各非基變量(對應于運輸表中的空格)的檢驗數，苦有某空格的檢驗數為負，說明將變為基變量將使運輸費用減少，故當前這個解不是最優解。若所有空格的檢驗數全非負，則不管樣變換解均能使運輸費用降低，即目標函數值已無法改進，這個解就是最優解。a.閉回路法2.解的最優性檢驗要判定運輸問題的某個解73現結合例1中用最小元素法給出的初始解，說明檢驗數的計算方法。其中一條閉回路檢驗數表銷售地供應地B1B2B3B4A1σ12=6σ13=3σ14=8A2σ21=0σ22=-–3*A3σ33=8因σ22=–3<0，故知該解不是最優解，還有待調整改正。現結合例1中用最小元素法給出的初始解，說明檢74閉回路可以是一個簡單的矩形，也可以是由水平和豎直邊線組成的其它更為復雜的封閉多邊形.閉回路可以是一個簡單的矩形，也可以是由水平和75運輸問題的進—步討論

上—節講述的運輸問題的算法，是以總產量等于總銷量(產銷平衡)為前提的。實際上在很多運輸問題中，總產量不等于總銷量。這時，為了使用前述表上作業法求解，就需將產銷不平衡運輸問題化為產銷平衡運輸問題。1.產銷不平衡的運輸問題運輸問題的進—步討論上—節講述的運輸問題的76如果總產量大于總銷量，即這時的數學模型是如果總產量大于總銷量，即77為借助于產銷平衡時的表上作業法求解，可增加一個假想的銷地Bn+1，由于實際上它不存在，因而由產地Ai(i=1,2,…,m)調運到這個假想銷地的物品數量xi,n+1(相當于松弛變量)，實際上是就地存貯在Ai的物品數量。就地存貯的物品不經運輸，故其單位運價ci,n+1(i=1,2,…,m)。為借助于產銷平衡時的表上作業法求解，可增加一個假想的78若令假想銷地的銷量為bn+1，且則模型變為對應的運輸表見下頁。若令假想銷地的銷量為bn+1，且對應的運輸表見下頁。79單價cij銷售地Bj供應量aiB1…BnBn+1供應地AiA1C11c12c1n0a1X11A2c21c22c2n0a2x21x22Amcm1cm2cmn0amx32x33x34需求量bjb1…Bn單價cij銷售地Bj供應B1…BnBn+1供A1C11c1280總銷量大于總產量的情形可仿照上述類似處理，即增加一個假想的產地Am+1，它的產量等于

由于這個假想的產地并不存在，求出的由它發往各個銷地的物品數量，實際上是各銷地所需物品的欠缺額，顯然有總銷量大于總產量的情形可仿照上述類似處理，即81單價cij銷售地Bj供應量aiB1B2B2B4供應地AiA1413459A21236106A3782610需求量bj54672522例：由各煤廠到各用戶的單位運價如表所示，請確定總運費最少的調運方案。單價cij銷售地Bj供應B1B2B2B4供A1413459A82單價cij銷售地BjB1B2B2B4供應地AiA141345A2123610A37826需求量bj546725-22=3供應量ai9610

555B5單價cij銷售地BjB1B2B2B483在以上討論中，假定物品由產地直接運送到銷售目的地，不經中間轉運。但是，常常會遇到這種情形：需先將物品由產地運到某個中間轉運站(可能是另外的產、銷地或中間轉運倉庫)，然后再轉運到銷售地。有時，經轉運比直接運到目的地更為經濟。總之，很多情況下，在決定運輸方案時有必要把轉運也考慮進去。顯然．考慮轉運將使運輸問題變得更為復雜。2.有轉運的運輸問題

(a)無轉運(b)包含轉運在以上討論中，假定物品由產地直接運送到銷售目84

假定m個產地A1,A2,…,Am和n個銷地B1,B2,…,Bn都可以作為中間轉運站使用，從而發送物品的地點相接收物品的地點都有m+n個。這樣一來，我們就得到了一個擴大了的運輸問題。為建立其數學模型，令：ai：第個i產地的產量(凈供應量)；bj：第j個銷地的銷量(凈需要量)；xij：由第i個發送地運到第j個接收地的物品數量；cij：由第i個發送地到第j個接收地的單位運價；ti：第i個地點轉運物品的數量；ci：第i個地點轉運單位物品的費用。假定m個產地A1,A2,…,Am和n個銷地B85現將產地和銷地統一編號，并把產地排在前面，銷地排在后面，則有假定為平衡運輸問題，即有現將產地和銷地統一編號，并把產地排在前面，銷地排在后面，則有86根據前面對平衡運輸問題的討論，可得該擴大了的運輸問題的數學模型如下：根據前面對平衡運輸問題的討論，可得該擴大了的運輸問題的數學模87將上述模型中的各約束等式右側的ti或tj移到等號左側，然后在各式等號兩端分別加上Q，并今，則可把模型寫成：將上述模型中的各約束等式右側的ti或tj移到等號左側，然后在88要特別注意，在此模型中，對所有i=j，cij=-ci。由于