最優(yōu)化理論運輸問題

關于最優(yōu)化理論運輸問題第1頁，課件共84頁，創(chuàng)作于2023年2月2第四章運輸問題◆4.1運輸問題的數學模型

◆4.2表上作業(yè)法◆4.3產銷不平衡的運輸問題

◆4.4運輸問題應用舉例第2頁，課件共84頁，創(chuàng)作于2023年2月3在經濟建設中，經常遇到大宗物資的調運問題，如煤、鋼材、糧食等.如果在我們考慮范圍之內有若干個生產基地和若干消費地點，根據已有的交通網絡，如何制定調運方案，使總的運費達到最小，這就是運輸問題.運輸問題是特殊的線性規(guī)劃問題，故可以用單純形法來求解，又因為它具有特殊性，因而它還具有比單純形法更為簡便的解法，這就是我們專門研究運輸問題的目的.4.1運輸問題的數學模型本節(jié)我們先引入運輸問題的數學模型，然后討論運輸問題數學模型的特點.

第3頁，課件共84頁，創(chuàng)作于2023年2月4例1假設有三家工廠，都將產品運往三個不同的商店(如圖)，每家工廠每周的生產能力和每個商店每周的需求量如表4-1和表4-2所示.

工廠1工廠3工廠2商店1商店3商店2表4-1表4-2

工廠123供應量（噸/周）507020商店123需求量（噸/周）5060304.1.1運輸問題的數學模型

先通過一個簡單的例子來說明運輸問題及其數學模型.第4頁，課件共84頁，創(chuàng)作于2023年2月5顯然，每周的供應總量與需求總量是相等的，即產銷平衡，這可以用表4-3來表示，稱為產銷平衡表.

由于運貨距離和運貨公路的路況不同，各個工廠運往各商店物資的單位運輸費用是不同的，單位費用如表4-4所示，稱為單位運價表.表4-3產銷平衡表單位：噸商店工廠123供應量150270320需求量506030第5頁，課件共84頁，創(chuàng)作于2023年2月6商店工廠123供應量13235021058703131020需求量506030商店工廠12313232105831310表4-4單位運價表單位：元/噸當然，我們也可以將產銷平衡表和單位運價表放在一個表中，如下表4-5所示.問如何確定調運方案，使總費用達到最小？第6頁，課件共84頁，創(chuàng)作于2023年2月7解模型建立

決策變量用雙下標決策變量Xij表示從第i（i=1，2，3）家工廠運送到第j（j=1，2，3）家商店產品的數量。

目標函數利用單位運價表和產銷平衡表中的數據，我們希望總的運費達到最小，即MinZ=由工廠1運出產品的總費用(3X11+2X12+3X13)+由工廠2運出產品的總費用(10X21+5X22+8X23)+由工廠3運出產品的總費用(X31+3X32+10X33)寫成表達式就是：

MinZ=3X11+2X12+3X13+10X21+5X22+8X23+X31+3X32+10X33第7頁，課件共84頁，創(chuàng)作于2023年2月8

對工廠1必須有X11+X12+X13=50

對工廠2必須有X21+X22+X23=70

對工廠3必須有X31+X32+X33=20

對商店1必須有X11+X21+X31=50

對商店2必須有X12+X22+X32=60

對商店3必須有X13+X23+X33=30約束條件主要是對工廠的產量約束和商店的銷量約束，由于產量與銷量相同，因而有：第8頁，課件共84頁，創(chuàng)作于2023年2月9

于是，解此問題的線性最優(yōu)化模型為：MinZ=3X11+2X12+3X13+10X21+5X22+8X23+X31+3X32+10X33

X11+X12+X13=50X21+X22+X23=70X31+X32+X33=20X11+X21+X31=50X12+X22+X32=60X13+X23+X33=30Xij≥0i=1，2，3j=1，2，3s.t.上述模型顯然是線性規(guī)劃模型，我們可以使用線性規(guī)劃的單純形法對它進行求解.但是，當用單純形法求解運輸問題時，先得給每個約束條件中引入一個人工變量，這樣模型的變量個數就會達到15個，求解是比較繁瑣的，因而有必要尋求更簡便的解法.第9頁，課件共84頁，創(chuàng)作于2023年2月10運輸問題的一般形式為：已知有m個生產地點Ai，i=1，2，…，m，可供應某種物資，其供應量是ai，i=1，2，…，m.有n個銷地Bj，需求量是bj，j=1，2，…，n.從Ai到Bj運送單位物資的運價為cij，i=1，2，…，m；j=1，2，…，n，問如何安排運輸可使總運費最?。窟@是多個產地供應多個銷地的單一物品運輸問題，我們用Xij表示從產地Ai到銷地Bj的運量，為直觀起見，可以單獨將Xij列出得該問題的運輸表.但我們也可以將運輸表和單位運價表、產銷量放在一起，如下表4-6所示.為了說明適于求解運輸問題的更好的解法，先看一下運輸問題的一般描述及模型的一般形式.第10頁，課件共84頁，創(chuàng)作于2023年2月11

銷地產地B1

B2…Bn產量A1X11c11X12c12X1nc1na1A2X21c21X22c22X2nc2na2…AmXm1cm1Xm2cm2Xmncmnam銷量b1b2bn表中每格元素Xij代表運量，右上角元素cij代表單位運價.第11頁，課件共84頁，創(chuàng)作于2023年2月12如果，就稱此運輸問題為非平衡運輸問題，包含產大于銷和銷大于產兩種情況，這我們將在第3節(jié)介紹。下面我們只考慮產銷平衡問題，產銷平衡運輸問題的一般模型為：在產銷平衡條件下，可知（4.2）其中約束條件右端常數ai

和bj滿足（4.2），在運輸問題（4.3）中，目標函數要求運輸總費用最小；前m個約束條件的意義是：由某一產地運往各個銷地的物資數量之和等于該產地的產量；中間n個約束條件的意義是：由各產地運往某一銷地的物資數量之和等于該銷地的銷量；后mn個約束條件是變量的非負條件.（4.3）第12頁，課件共84頁，創(chuàng)作于2023年2月134.1.2運輸問題數學模型的特點

對于產銷平衡運輸問題（4.3），將其約束條件加以整理，可知其系數矩陣具有下述形式：

（4.4）

由此可知，產銷平衡運輸問題數學模型有下述特點：第13頁，課件共84頁，創(chuàng)作于2023年2月14（1）約束條件中決策變量的系數等于0或1.（2）所有約束條件都是等式.（3）約束條件的系數矩陣中每一列有兩個非零元素，對應于變量Xij的系數列向量Pij，其分量除第i個和第m+j個等于1以外，其余的均為零，即Pij=ei+em+j.這對應于每一個變量在前m個約束方程中出現(xiàn)一次，在后n個約束方程中也出現(xiàn)一次.（4）由于（4.2）成立，因而約束條件中m個約束方程并不是獨立的，實際上只有個m+n-1方程是獨立的，因而約束方程系數矩陣的秩為m+n-1.（5）運輸問題（4.3）總存在基可行解，下節(jié)我們將給出找基可行解的方法.（6）運輸問題存在有限最優(yōu)解這是由于對運輸問題（4.3），若令其變量則Xij就是該運輸問題的一個可行解，其中是總產量；另一方面，（4.3）的目標函數有下界，即目標函數不會趨向于負無窮，從而運輸問題必存在有限最優(yōu)解.第14頁，課件共84頁，創(chuàng)作于2023年2月15例2

某種物品先存放在兩個倉庫A1和A2中，再運往三個使用地B1，B2和

B3，產銷平衡表和單位運價表如下表4-7所示，試建立使總運費最小的運輸問題數學模型.

使用地倉庫B1

B2B3產量A134210A23534銷量356解：設表示從Ai運到Bj的物品數量，則由表中數據可知該問題的數學模型為：第15頁，課件共84頁，創(chuàng)作于2023年2月16前面已經指出，運輸問題是特殊的線性規(guī)劃問題，可設想用單純形法進行求解，而單純形法的基本思路是：先找出某個基可行解，再進行解的最優(yōu)性檢驗，若它不是最優(yōu)解，就進行迭代調整，得到新的更好的解，然后繼續(xù)驗證和調整改進，直至得到最優(yōu)解為止.為了按照上述思想求解運輸問題，要求每步得到的解都必須是基可行解，因而解必須滿足模型中所有約束條件，而且由運輸問題的特點（4）知基變量的個數在迭代過程中始終保持為m+n-1個，同時基變量對應的約束方程組的系數列向量是線性無關的.在運輸問題的數學模型中，每個解就代表一個運輸方案，運輸問題解的每一個分量，都唯一對應其運輸表中的一個格.若X是運輸問題的一個基可行解，則將其基變量的值填入到運輸表相應的格處（含填數字0的格），非基變量對應的格不填數字.第16頁，課件共84頁，創(chuàng)作于2023年2月17例如下表4-8表示例2的一個基可行解.

使用地倉庫B1

B2B3供應量A133146210A234534需求量356表4-8有4個填有數字的格，它們對應4個基變量，兩個空格對應2個非基變量.可以驗證，基可行解對應的約束方程組的系數列向量線性無關.第17頁，課件共84頁，創(chuàng)作于2023年2月184.2表上作業(yè)法

由于運輸問題具有特殊形式，因而我們可以在運輸表中直接對問題求解，稱為表上作業(yè)法.表上作業(yè)法是單純形法求解運輸問題時的簡化方法，其實質是單純形法，它的步驟可歸納為：(1)找出初始基可行解，即在m行n列產銷平衡表上給出m+n-1個數字格.(2)求各非基變量的檢驗數，即在表上計算空格的檢驗數，并判別是否達到最優(yōu)解，如果是最優(yōu)解，停止；否則轉下一步.(3)確定換入變量和換出變量，找出新的基可行解，在表上進行調整.(4)重復(2)(3)，直至得到最優(yōu)解.表上作業(yè)法的步驟中，確定初始基可行解、判斷是否達到最優(yōu)解和確定換入換出變量并在表上進行調整是其中幾個關鍵點.下面我們依次來看.第18頁，課件共84頁，創(chuàng)作于2023年2月194.2.1確定初始基可行解

我們以一個例子來說明找初始基可行解的方法.下表4-9表示某個運輸問題的產銷平衡表和單位運價表(二表合一).一般來說，找運輸問題的初始基可行解主要有三種方法，即西北角法、最小元素法和差值法（也叫伏格爾法），下面我們用上表4-9依次來說明.

銷地產地B1B2B3B4產量A13113107A219284A3741059銷量3656第19頁，課件共84頁，創(chuàng)作于2023年2月201.西北角法(1)從圖的西北角（即左上方）開始，在(A1,B1)格填入a1和b1中的較小值，這里填入較小值b1=3，即從A1運送3個單位物資到B1，此時的B1物資已經全部滿足，劃去B1列，如下表4-10所示.

銷地產地B1B2B3B4產量A133113107A219284A3741059銷量3656第20頁，課件共84頁，創(chuàng)作于2023年2月21（2）向a1,b1中較大數方向移動一格（或向右，或向下），這里是向右移動一格，移動到(A1,B2)位置.B2需要6個單位物資，而A1只剩有4個單位，故在(A1,B2)處填4，A1的物資已經全部發(fā)完，劃去A1行，如下表4-11所示.

銷地產地B1B2B3B4產量A1334113107A219284A3741059銷量3656第21頁，課件共84頁，創(chuàng)作于2023年2月22（3）繼續(xù)按照上述步驟進行，可知A2向B2運送2個單位物資，此時B2的物資已經滿足，劃去B2列.

銷地產地B1B2B3B4產量A1334113107A2129284A3741059銷量3656第22頁，課件共84頁，創(chuàng)作于2023年2月23（4）繼續(xù)按照上述步驟進行.

銷地產地B1B2B3B4產量A1334113107A21292284A3741059銷量3656第23頁，課件共84頁，創(chuàng)作于2023年2月24（5）繼續(xù)進行.

銷地產地B1B2B3B4產量A1334113107A21292284A37431059銷量3656第24頁，課件共84頁，創(chuàng)作于2023年2月25（6）繼續(xù)進行.最后在(A3,B4)處填入6，此時A3和B4的物資已經全部發(fā)送和接收完畢，因而同時劃去A3行和B4列，如下表4-13所示.

銷地產地B1B2B3B4產量A1334113107A21292284A374310659銷量3656第25頁，課件共84頁，創(chuàng)作于2023年2月26（7）得到初始方案，如下表4-14所示.

銷地產地B1B2B3B4產量A1334113107A21292284A374310659銷量3656總運費第26頁，課件共84頁，創(chuàng)作于2023年2月272.最小元素法用西北角法很容易得到初始基可行解，但得到的解往往離最優(yōu)解相差甚遠.為了得到較好的初始基可行解，我們通常希望就近供應，即從單位運價表中最小的運價開始確定供銷關系，然后次小，一直到給出初始基可行解為止，這種方法稱為最小元素法.我們仍以表4-9所示的運輸問題來說明最小元素法.

銷地產地B1B2B3B4產量A13113107A219284A3741059銷量3656第27頁，課件共84頁，創(chuàng)作于2023年2月28（1）從表中最小單位運價開始確定運輸方案，這里(A2,B1)位置的1最小，因而A2優(yōu)先供應物資到B1，根據的A2產量和B1的銷量知，A2只能供應3個單位物資到B1，B1已經滿足，劃去B1列，如下表4-15所示.

銷地產地B1B2B3B4產量A13113107A2319284A3741059銷量3656第28頁，課件共84頁，創(chuàng)作于2023年2月29（2）再從未劃去的元素中找最小元素，并從該元素開始確定運輸關系，這里(A2,B3)處2最小，故從此元素開始，即A2優(yōu)先供應B3物資，A2只剩1個單位物資，從而A2只能供應1個單位物資到B3，A2物資已經發(fā)完，劃去A2行，如下表4-16所示.

銷地產地B1B2B3B4產量A13113107A23191284A3741059銷量3656第29頁，課件共84頁，創(chuàng)作于2023年2月30（3）再從未劃去的元素中找最小元素，并從該元素開始確定運輸關系，這里(A1,B3)處3最小，故從此元素開始，即A1優(yōu)先供應B3物資，根據A1的產量和B3的銷量知A1供應4個單位物資到B3，B3物資已經滿足，劃去B3列，如下表所示.

銷地產地B1B2B3B4產量A131143107A23191284A3741059銷量3656第30頁，課件共84頁，創(chuàng)作于2023年2月31（4）再從未劃去的元素中找最小元素，并從該元素開始確定運輸關系，這里(A3,B2)處4最小，故從此元素開始，即A3優(yōu)先供應B2物資6個單位，B2物資已經滿足，劃去B2列，如下表所示.

銷地產地B1B2B3B4產量A131143107A23191284A37641059銷量3656第31頁，課件共84頁，創(chuàng)作于2023年2月32（5）再從未劃去的元素中找最小元素，并從該元素開始確定運輸關系，這里(A3,B4)處5最小，故從此元素開始，即A3優(yōu)先供應B4物資3個單位，A3物資已經發(fā)完，劃去A3行，如下表4-17所示.

銷地產地B1B2B3B4產量A131143107A23191284A376410359銷量3656第32頁，課件共84頁，創(chuàng)作于2023年2月33（6）最后在(A1,B4)處填3，即A1供應B4物資3個單位，A1物資已經發(fā)完，劃去A3行，B4物資全部滿足，劃去B4列，如下表所示.

銷地產地B1B2B3B4產量A1311433107A23191284A376410359銷量3656第33頁，課件共84頁，創(chuàng)作于2023年2月34（7）得到初始方案，如下表4-18所示.

銷地產地B1B2B3B4產量A1311433107A23191284A376410359銷量3656總運費第34頁，課件共84頁，創(chuàng)作于2023年2月353.差值法（伏格爾法）初看起來，最小元素法十分合理.事實上，最小元素法的缺點是：為了節(jié)省一處的費用，有時造成其它處要多花幾倍的運費，這是因為有時按某一最小單位運價優(yōu)先安排物資運輸時，卻可能導致不得不采用運費很高的其它點對，從而使整個運輸費用增加.伏格爾法考慮到，一個產地的產品假如不能按最小費用就近供應，就考慮次小費用，這樣最小費用和次小費用就有一個差額，差額越大，說明不按最小費用調運時，運費增加越多，因而對差額最大處，就應當采用最小調運方案.基于此，伏格爾法的步驟是：每次從當前運價表上，計算各行各列中最小費用與次小費用這兩個運價的差值，優(yōu)先取最大差值的行或列中最小的單位運價來確定運輸關系，直到求出初始方案.第35頁，課件共84頁，創(chuàng)作于2023年2月36

銷地產地B1B2B3B4產量行差額A131131070A2192841A37410591銷量3656列差額2513我們仍然考慮表4-9所示的運輸問題，伏格爾法確定初始基可行解的步驟如下：（1）先分別計算出各行和各列最小費用與次小費用的差額，稱為行差額和列差額，并將行差額和列差額填入該表的最右列和最下行，如下表4-19所示.第36頁，課件共84頁，創(chuàng)作于2023年2月37

銷地產地B1B2B3B4產量行差額A131131070A2192841A376410591銷量3656列差額2513（2）從行差額和列差額中選出最大者，選擇它所在的行或列中的最小費用所在的格作為優(yōu)先的運輸關系.在這里行差額與列差額最大值為5，故選擇5所在的列最小單位運價4為優(yōu)先運輸關系，即讓A3優(yōu)先供應物資到B2，根據產、銷量知A3供應6個單位物資到B2，此時B2列已滿足，劃去B2列，得下表4-20.第37頁，課件共84頁，創(chuàng)作于2023年2月38

銷地產地B1B2B3B4產量行差額A131131070A2192841A3764103592銷量3656列差額2513（3）計算剩余元素的行差額和列差額，選出最大者，選擇它所在的行或列中的最小費用所在的格作為優(yōu)先的運輸關系.在這里行差額與列差額最大值為B4列的3，故選擇3所在的列最小單位運價5為優(yōu)先運輸關系，即讓A3供應物資到B4，由剩余的產、銷量知A3只能供應3個單位物資到B4，這時A3已經發(fā)貨完畢，劃去A3行，如表4-21所示.第38頁，課件共84頁，創(chuàng)作于2023年2月39（4）繼續(xù)計算剩余元素的行差額和列差額，并按照上述步驟確定運輸關系，經過若干步以后，最后填2到(A1,B4)格，A1和B4的供應量和需求量都得到滿足，此時同時劃去A1行和B4列，可得初始方案，其余變量為0，如下表4-22所示.

銷地產地B1B2B3B4產量A1311532107A23192184A376410359銷量3656總運費為第39頁，課件共84頁，創(chuàng)作于2023年2月40從上述計算步驟可見，三種方法除了在確定供求關系的原則不同外，其余步驟是相同的.表4-9所示的運輸問題用三種方法得到的初始方案和總運費分別是：西北角法得到的初始方案是總運費為135；最小元素法得到初始方案為總運費是86；差值法的初始方案是總運費85.

比較三種方法給出的初始基可行解，伏格爾法給出的解的目標函數值最小，最小元素法次之，西北角法給出的解的目標函數值最大.一般來說，伏格爾法確定的初始基可行解更接近最優(yōu)解，常用來作為運輸問題的初始基可行解進行迭代第40頁，課件共84頁，創(chuàng)作于2023年2月41需要注意的是三種方法給出的初始方案都是運輸問題的基可行解，這是因為：（1）在產銷平衡表上，選擇表中某一元素以后，要比較產量和銷量，當產大于銷，劃去該元素所在列；當產小于銷，劃去該元素所在行，然后在未劃去的元素中繼續(xù)選另一元素.表中共有m行n列，總共可劃條m+n直線，但當表中只剩一個元素時，同時劃去一行和一列.因而表中共填了m+n-1個數字，即給出了m+n-1個基變量的值.

注：選擇表中某一個元素后，有可能同時劃去一行和一列，這就出現(xiàn)退化，退化的處理我們在后文中講述.（2）這m+n-1個基變量對應的系數列向量是線性獨立的.這是因為若表中確定了某一個基變量以后，它對應的系數列向量，給定的值以后，將劃去第i行或第j列，即其后的系數列向量中不再出現(xiàn)或，因而不可能用其它向量的線性組合表示.所以這m+n-1個基變量對應的系數列向量是線性獨立的.第41頁，課件共84頁，創(chuàng)作于2023年2月424.2.2解的最優(yōu)性檢驗及改進

前面三種方法可以很容易找出運輸問題的初始基可行解，但初始基可行解未必是最優(yōu)解.按照表上作業(yè)法的步驟，給出初始基可行解后，還要計算各非基變量的檢驗數，即在表上計算各空格的檢驗數，以判別基可行解是否達到最優(yōu).由于運輸問題的目標函數是要求實現(xiàn)最小化，因而所有的檢驗數大于等于零時基可行解為最優(yōu)解.判別初始基可行解是否為最優(yōu)解一般有兩種常用方法：閉回路法和位勢法，下面我們依次來介紹.

1.閉回路法閉回路方法是在初始調運方案表中，從任意空格出發(fā)，沿著縱向或橫向行進，遇到適當填有數據的方格后90度轉彎，繼續(xù)行進，總能回到原來空格，這個封閉的曲線稱為閉回路.可以證明每個空格都對應著唯一的閉回路.第42頁，課件共84頁，創(chuàng)作于2023年2月43

銷地產地B1B2B3B4產量A1311433107A23191284A376410359銷量3656在表4-9所表示的運輸問題中，用最小元素法得到的初始調運方案是表4-18，我們以此調運方案為例作閉回路.對空格(A1,B1)，它的閉回路如表4-23所示.第43頁，課件共84頁，創(chuàng)作于2023年2月44

銷地產地B1B2B3B4產量A1311433107A23191284A376410359銷量3656再如對空格(A1,B2)，它的閉回路如下表4-24所示.第44頁，課件共84頁，創(chuàng)作于2023年2月45

銷地產地B1B2B3B4產量A1311433107A23191284A376410359銷量3656同樣，空格(A3,B1)的閉回路如下表4-25所示.第45頁，課件共84頁，創(chuàng)作于2023年2月46下面我們看用閉回路法計算非基變量（空格點）檢驗數的計算方法.首先考慮表4-23的空格點(A1,B1),假設產地A1運送1個單位的物資到銷地B1，為使運入銷地B1物資的數量等于它的銷量，就應當將原來A2運送到的B1物資數量減去1個單位，即將(A2,B1)格的3變?yōu)?；另一方面，為使運出產地A2物資的數量等于它的產量，就應當將原來(A2,B3)格的數1加上1，再考慮B3知應將(A1,B3)格的4變?yōu)?，從而得到一個新的運輸方法.顯然這樣的調整將影響到空格(A1,B1)閉回路上的各個數據.按照上述假設，如果由產地A1運送1個單位的物資到銷地B1，由此引起的總費用變化是，即總費用增加1.按照檢驗數的定義知它正是非基變量（即空格(A1,B1)）的檢驗數.同理按空格(A1,B2)的閉回路知它的檢驗數為，空格(A3,B1)的檢驗數為10.第46頁，課件共84頁，創(chuàng)作于2023年2月47

銷地產地B1B2B3B4產量A1311433107[1][2]A23191284[1][-1]A376410359[10][12]銷量3656從這幾個檢驗數的計算過程可以看出，非基變量的檢驗數等于其閉回路上偶數次拐角點運價之和減去奇數次拐角點運價之和.用此方法可以計算出各個空格的檢驗數（數字格表示的基變量的檢驗數始終為0），如下表4-26中方括弧中數字所示.

第47頁，課件共84頁，創(chuàng)作于2023年2月48由于運輸問題的目標函數是要求實現(xiàn)最小化，因而對該問題的某個基可行解，如果所有空格的檢驗數中沒有負值，則該基可行解就是最優(yōu)解；如果某個空格處出現(xiàn)負檢驗數，表明調運方案不是最優(yōu)解，這時就要進行調解.和單純形法類似，當有兩個和兩個以上空格的檢驗數為負時，一般選其中最小的負檢驗數，以它對應的空格作為調入格，即該空格對應的變量為進基變量.在進基變量的回路中，比較奇數拐角點的運量，為了使新得到的解仍為基可行解，應當選擇一個具有最小運量的基變量作為出基變量，并使調整的運量為各個奇數拐角點運量的最小值.在表4-26中，只有空格(A2,B4)處的檢驗數為負，因而它對應的變量為進基變量，它的閉回路如表4-27所示.第48頁，課件共84頁，創(chuàng)作于2023年2月49

銷地產地B1B2B3B4產量A1311433107A23191284A376410359銷量3656奇數拐點處運量的最小值為1,因而為了保持平衡，將奇數拐點處的運量減去1，偶數拐點處的運量加1，調整后的運輸方案如下表4-28所示.第49頁，課件共84頁，創(chuàng)作于2023年2月50

銷地產地B1B2B3B4產量A1311532107A23192184A376410359銷量3656調整以后，再計算各個空格的檢驗數，如果所有的檢驗數均大于等于零，則這個運輸方案就是最優(yōu)解；如果還有某個空格的檢驗數為負數，則再以這個空格為調入格，作相應的基變換，直到所有的檢驗數為非負.上述表中得到的所有的檢驗數為非負，因而此運輸方案是最優(yōu)方案.第50頁，課件共84頁，創(chuàng)作于2023年2月512.位勢法

在閉回路法中，為了計算一個空格點處的檢驗數，就要畫出該空格的閉回路，當空格點較多時，計算很繁.位勢法是另一種計算每個空格檢驗數的方法，這個方法比閉回路法更加簡潔.第51頁，課件共84頁，創(chuàng)作于2023年2月52位勢法的基本思想是：

設一組新的變量ui和vj(i=1,2,…m;j=1,2,…n)是對應運輸問題的m+n個約束條件的對偶變量，B是原問題的初始基矩陣，則由單純形法知

而每個決策變量的系數向量，所以有，于是檢驗數

由于基變量的檢驗數始終為0，因而對于基變量，始終有

，所以我們可以根據基變量對應的單位運輸費用算出所有ui與vj的值，再根據ui與vj的值算出非基變量的檢驗數。第52頁，課件共84頁，創(chuàng)作于2023年2月53例如在表4-9所表示的運輸問題中，用最小元素法得到的初始調運方案如下表所示.

銷地產地B1B2B3B4uiA131143310u1A2319128u2A37641035u3vjv1v2v3v4在此調運方案中，我們可以根據基變量對應的單位運輸費用cij算出ui和vj.計算方程組是：第53頁，課件共84頁，創(chuàng)作于2023年2月54

銷地產地B1B2B3B4uiA1311433100A2319128-1A37641035-5vj29310該方程組含6個方程和7個未知數，因而有一個未知數是自由變量，通常我們令u1=0，此時可得到所有ui(i=1,2,…m)和vj(j=1,2,…,n)的值，如下表4-29所示.第54頁，課件共84頁，創(chuàng)作于2023年2月55根據ui和vj的值算出所有空格處（即非基變量）的檢驗數，計算公式為cij-(ui+vj)，計算結果如下表4-30方括號數字所示，這和用閉回路法得到的檢驗數結果一致.

銷地產地B1B2B3B4uiA1311433100[1][2]A2319128-1[1][-1]A37641035-5[10][12]vj29310因為檢驗數，故這個解不是最優(yōu)解，因此我們再根據閉回路法進行調整，直至得出最優(yōu)解.第55頁，課件共84頁，創(chuàng)作于2023年2月56表上作業(yè)法在計算中可能還會出現(xiàn)一些問題，這里我們需要說明.1.當迭代到運輸問題的最優(yōu)解時，如果有某個非基變量的檢驗數等于零，則說明該運輸問題有無窮多最優(yōu)解.2.退化

(1)當確定供需關系時，如果某個產地的剩余產量等于某個銷地的需量，這時就要劃去一行和一列，此時需要添加一個0，它的位置可在對應劃去的那行或那列的任意處.(2)在用閉回路法調整時，如果閉回路奇數拐彎處具有兩個或兩個以上相等的最小值，此時經調整后，得到退化解，這時有一個數字格必須填0，以表示它是基變量.第56頁，課件共84頁，創(chuàng)作于2023年2月574.3產銷不平衡的運輸問題

上一節(jié)講到運輸問題的表上作業(yè)法，是以總產量等于總銷量（即產銷平衡）為前提的.實際上，在很多運輸問題中，總產量并不等于總銷量.為了使用表上作業(yè)法求解，我們可以將產銷不平衡的運輸問題轉化為產銷平衡運輸問題.如果總產量大于總銷量，即這時運輸問題的數學模型為：

（4.5）

第57頁，課件共84頁，創(chuàng)作于2023年2月58由于總產量大于總銷量，因而要考慮多余物資就地貯存的問題.為借助產銷平衡運輸問題的表上作業(yè)法，可增加一個假想的銷地Bn+1，由各產地Ai(i=1,2,…,m)運送到這個銷地Bn+1物資的數量設為，實際上就是產地Ai就地貯存物資的數量，顯然單位運價.因此假想后原問題的最優(yōu)總費用與假想之前的最優(yōu)總費用是一致的.

由于總產量剩余為使產銷平衡，可假設銷地Bn+1的銷量此時模型（4.5）可以變?yōu)椋?/p>

（4.6）

第58頁，課件共84頁，創(chuàng)作于2023年2月59

銷地產地B1

B2…BnBn+1產量A1X11c11X12c12X1nc1nX1，n+10a1A2X21c21X22c22X2nc2nX2，n+10a2…AmXm1cm1Xm2cm2XmncmnXm，n+10am銷量b1b2bn可以看出，模型（4.6）是有m個產地，n+1個銷地的產銷平衡運輸問題，因而通過假想銷地，可將產大于銷的運輸問題轉化為產銷平衡運輸問題.和模型（4.6）對應的運輸表如下表所示.第59頁，課件共84頁，創(chuàng)作于2023年2月60如果總銷量大于總產量，即可仿照產大于銷的操作過程，增加一個假想的產地Am+1，它的產量為由于這個假想的產地并不存在，求出的由它發(fā)往各個銷地的物資數量實際上是各銷地所需物資的欠缺額，這部分物資的運輸并未發(fā)生，因而單位運價.這樣也可以將原問題化為產銷平衡運輸問題.第60頁，課件共84頁，創(chuàng)作于2023年2月61例3

某市有三個造紙廠A1，A2，A3和四個批發(fā)用戶B1，B2，B3，B4，各造紙廠紙的產量、各批發(fā)用戶的需求量及各造紙廠到各批發(fā)用戶的單位運價如下表4-32所示，試確定運輸總費用最小的調運方案.

批發(fā)用戶造紙廠B1B2B3B4產量A1312348A2112595A367159需求量4356第61頁，課件共84頁，創(chuàng)作于2023年2月62解由于該問題中總產量為22，總銷量為18，因而該問題是總產量大于總銷量的產銷不平衡運輸問題.按照模型（4.5）的分析知，增加一個假想銷地B5，其需求量為22-18=4，可將該問題表示的運輸問題轉化為下表4-33所示的產銷平衡運輸問題.用戶造紙廠B1B2B3B4B5產量A13123408A21125905A3671509需求量435622-18=4根據表上作業(yè)法，可得該問題的最優(yōu)運輸方案如下表4-34所示第62頁，課件共84頁，創(chuàng)作于2023年2月63用戶造紙廠B1B2B3B4B5產量A1431234408A2113259205A3675125209銷量435622-18=4在以上討論中，我們都假定物資由產地直接運送到銷售目的地，不經過中間轉運.在實際問題中，還會遇到將物資運到某個中間轉運站（包括產地、銷地或中間轉運倉庫），然后再運往銷售目的地的情況.有時經轉運比直接運往目的地更為經濟，在決定運輸方案時有必要將轉運也考慮進去.當然考慮轉運將使問題變得復雜，有興趣的讀者可以參閱相關文獻.第63頁，課件共84頁，創(chuàng)作于2023年2月64

下面我們通過幾個例子介紹運輸問題的一些實際應用.例4

設有三個化肥廠供應四個地區(qū)的農用化肥，假定等量的化肥在這些地區(qū)試用效果相同.各化肥廠年產量、各地區(qū)年需求量（單位：萬噸）及從各化肥廠到各地區(qū)運送單位化肥的單位運價（單位：萬元/萬噸）如表4-35所示，試給出總運費最小的化肥調撥方案.4.4運輸問題應用舉例

第64頁，課件共84頁，創(chuàng)作于2023年2月65

需求地區(qū)化肥廠ⅠⅡⅢⅣ產量11613221750214131915603192023—50最低需求最高需求3050707003010不限解這是一個產銷不平衡的運輸問題，總產量為160萬噸，四個地區(qū)的最低需求為110萬噸，最高需求不限，但根據現(xiàn)有產量，第Ⅳ個地區(qū)每年最多能分配到60萬噸，因而最高需求為210萬噸，大于總產量.為了求得平衡，在產銷表中增加一個假想的化肥廠4，其年產量為50萬噸.第65頁，課件共84頁，創(chuàng)作于2023年2月66各地區(qū)的需求量包含最低需求和額外需求兩部分.如地區(qū)Ⅰ，其中30萬噸是最低需求，故不能由假想化肥廠Ⅳ供給，因而令假想化肥廠4到地區(qū)Ⅰ的單位運價為M（M為任意大的數），而額外需求20萬噸對地區(qū)Ⅰ來說可以滿足，也可以不滿足，因此額外需求可以由假想化肥廠4供給，而且相應的運價為0.事實上，對凡是需求分兩種情況的地區(qū)，我們按照兩個地區(qū)看待，這樣可將原問題轉化為產銷平衡運輸問題，其產銷平衡表與單位運價表如下表4-36所示.第66頁，課件共84頁，創(chuàng)作于2023年2月67需求地區(qū)化肥廠ⅠⅠⅡⅢⅣⅣ產量116161322171750214141319151560319192023MM504M0M0M050需求量302070301050根據表上作業(yè)法進行計算，可以求得最優(yōu)方案如下表4-37所示.第67頁，課件共84頁，創(chuàng)作于2023年2月68需求地區(qū)化肥廠ⅠⅠⅡⅢⅣⅣ產量1161650132217175021414201319101530156033019201902023MM504M0M300M20050需求量302070301050從表4-37可以看出，地區(qū)Ⅰ滿足最高需求量50萬噸，地區(qū)Ⅲ沒有接收到任何物資，只滿足最低需求0，而地區(qū)Ⅳ滿足了40萬噸第68頁，課件共84頁，創(chuàng)作于2023年2月69

使用者產地ⅠⅡⅢ產量124321563324使用量1046例5

設有三個產地生產同一種產品并供應給三個使用者，各產地到各使用者的單位運價及使用者的需求量如下表4-38所示.由于銷售需要及客觀條件的限制，產地1至少要發(fā)出6個單位的產品，它最多只能生產11個單位的產品；產地2的產量為7個單位；產地3至少要發(fā)出4個單位的產品，試根據上述條件用表上作業(yè)法求該運輸問題的最優(yōu)調運方案.第69頁，課件共84頁，創(chuàng)作于2023年2月70使用者產地ⅠⅡⅢⅣ產量1243M61243052156M73324M4332403使用量10465解由表4-38可知，若產地1、2的產量按最小值計算，在產銷平衡條件下，產地3的產量最多等于7.用類似于例4的方法，可將原問題表示成下表4-39所示的產銷平衡運輸問題.由表4-39求解該產銷平衡運輸問題解的過程及結果請讀者自己完成.第70頁，課件共84頁，創(chuàng)作于2023年2月71

銷地產地ⅠⅡⅢ產量112220214540323330銷量302020例6

三個產地欲將同一種物資運送到三個銷地，各產地產量、各銷地銷量以及各產地運送物資到各銷地的單位運價如下表4-40所示.若各產地有物資沒有運出，就發(fā)生存儲費用，假設三個產地單位物資存儲費分別為4,4,3；產地2的物資最多運出35個單位，產地3的物資至少運出28個單位，試給出使總運輸費用最小的運輸方案.第71頁，課件共84頁，創(chuàng)作于2023年2月72解這是一個有存儲形式的產銷不平衡運輸問題.為使問題化為無存儲費用的產銷平衡運輸問題，可將產地1,2,3設想為三個銷地Ⅳ,Ⅴ,Ⅵ，考慮到物資存儲的費用，可將單位存儲費按單位運價來表示.如產地1到銷地Ⅳ（即產地1）的單位運輸費用為4，產地1不能運送物資到產地2（即銷地Ⅴ），因而產地1到銷地Ⅴ的單位運輸費用為M（M任意大）.又由于產地2的物資最多運出35個單位，因而產地2至少存儲5個單位物資，即銷地Ⅴ的需求量至少為5個單位，同理銷地Ⅵ需求量至多為2個單位，為保持運輸平衡，銷地Ⅳ的需求量是0~15之間使產銷平衡的值，因而原問題轉化為下表4-41所示的產銷平衡運輸問題.第72頁，課件共84頁，創(chuàng)作于2023年2月73銷地產地ⅠⅡⅢⅣⅤⅥ產量11224MM202145M4M403233MM330銷量3020200~15≥5≤2表4-41第73頁，課件共84頁，創(chuàng)作于2023年2月74銷地產地ⅠⅡⅢⅣⅤⅥ產量181212204MM20222145M184M403220383MM2330銷量3020200~15≥5≤2通過表上作業(yè)法可得該問題的最優(yōu)方案如下表4-42所示，總費用為216.第74頁，課件共84頁，創(chuàng)作于2023年2月75例7

某工廠根據合同，要在下一年每個季度末向銷售公司提供某種產品，該工廠的生產能力、生產成本以及銷售公司的需求量如下4-43表所示季度生產能力（噸）生產成本（萬元/噸）需求量（噸）123430402010151415.314.820203010若當季生產的產品過