第四章最優(yōu)化理論運(yùn)輸問題詳解演示文稿

第四章最優(yōu)化理論運(yùn)輸問題詳解演示文稿1目前一頁\總數(shù)七十九頁\編于十八點優(yōu)選第四章最優(yōu)化理論運(yùn)輸問題2目前二頁\總數(shù)七十九頁\編于十八點在經(jīng)濟(jì)建設(shè)中，經(jīng)常遇到大宗物資的調(diào)運(yùn)問題，如煤、鋼材、糧食等.如果在我們考慮范圍之內(nèi)有若干個生產(chǎn)基地和若干消費(fèi)地點，根據(jù)已有的交通網(wǎng)絡(luò)，如何制定調(diào)運(yùn)方案，使總的運(yùn)費(fèi)達(dá)到最小，這就是運(yùn)輸問題.運(yùn)輸問題是特殊的線性規(guī)劃問題，故可以用單純形法來求解，又因為它具有特殊性，因而它還具有比單純形法更為簡便的解法，這就是我們專門研究運(yùn)輸問題的目的.4.1運(yùn)輸問題的數(shù)學(xué)模型本節(jié)我們先引入運(yùn)輸問題的數(shù)學(xué)模型，然后討論運(yùn)輸問題數(shù)學(xué)模型的特點.

3目前三頁\總數(shù)七十九頁\編于十八點例1假設(shè)有三家工廠，都將產(chǎn)品運(yùn)往三個不同的商店(如圖)，每家工廠每周的生產(chǎn)能力和每個商店每周的需求量如表4-1和表4-2所示.

工廠1工廠3工廠2商店1商店3商店2表4-1表4-2工廠123供應(yīng)量（噸/周）507020商店123需求量（噸/周）5060304.1.1運(yùn)輸問題的數(shù)學(xué)模型

先通過一個簡單的例子來說明運(yùn)輸問題及其數(shù)學(xué)模型.4目前四頁\總數(shù)七十九頁\編于十八點顯然，每周的供應(yīng)總量與需求總量是相等的，即產(chǎn)銷平衡，這可以用表4-3來表示，稱為產(chǎn)銷平衡表.

由于運(yùn)貨距離和運(yùn)貨公路的路況不同，各個工廠運(yùn)往各商店物資的單位運(yùn)輸費(fèi)用是不同的，單位費(fèi)用如表4-4所示，稱為單位運(yùn)價表.表4-3產(chǎn)銷平衡表單位：噸商店工廠123供應(yīng)量150270320需求量5060305目前五頁\總數(shù)七十九頁\編于十八點商店工廠123供應(yīng)量13235021058703131020需求量506030商店工廠12313232105831310表4-4單位運(yùn)價表單位：元/噸當(dāng)然，我們也可以將產(chǎn)銷平衡表和單位運(yùn)價表放在一個表中，如下表4-5所示.問如何確定調(diào)運(yùn)方案，使總費(fèi)用達(dá)到最?。?目前六頁\總數(shù)七十九頁\編于十八點解模型建立

決策變量用雙下標(biāo)決策變量Xij表示從第i（i=1，2，3）家工廠運(yùn)送到第j（j=1，2，3）家商店產(chǎn)品的數(shù)量。

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

MinZ=3X11+2X12+3X13+10X21+5X22+8X23+X31+3X32+10X337目前七頁\總數(shù)七十九頁\編于十八點

對工廠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約束條件主要是對工廠的產(chǎn)量約束和商店的銷量約束，由于產(chǎn)量與銷量相同，因而有：8目前八頁\總數(shù)七十九頁\編于十八點

于是，解此問題的線性最優(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ī)劃的單純形法對它進(jìn)行求解.但是，當(dāng)用單純形法求解運(yùn)輸問題時，先得給每個約束條件中引入一個人工變量，這樣模型的變量個數(shù)就會達(dá)到15個，求解是比較繁瑣的，因而有必要尋求更簡便的解法.9目前九頁\總數(shù)七十九頁\編于十八點運(yùn)輸問題的一般形式為：已知有m個生產(chǎn)地點Ai，i=1，2，…，m，可供應(yīng)某種物資，其供應(yīng)量是ai，i=1，2，…，m.有n個銷地Bj，需求量是bj，j=1，2，…，n.從Ai到Bj運(yùn)送單位物資的運(yùn)價為cij，i=1，2，…，m；j=1，2，…，n，問如何安排運(yùn)輸可使總運(yùn)費(fèi)最??？這是多個產(chǎn)地供應(yīng)多個銷地的單一物品運(yùn)輸問題，我們用Xij表示從產(chǎn)地Ai到銷地Bj的運(yùn)量，為直觀起見，可以單獨(dú)將Xij列出得該問題的運(yùn)輸表.但我們也可以將運(yùn)輸表和單位運(yùn)價表、產(chǎn)銷量放在一起，如下表4-6所示.為了說明適于求解運(yùn)輸問題的更好的解法，先看一下運(yùn)輸問題的一般描述及模型的一般形式.10目前十頁\總數(shù)七十九頁\編于十八點銷地產(chǎn)地B1

B2…Bn產(chǎn)量A1X11c11X12c12X1nc1na1A2X21c21X22c22X2nc2na2…AmXm1cm1Xm2cm2Xmncmnam銷量b1b2bn表中每格元素Xij代表運(yùn)量，右上角元素cij代表單位運(yùn)價.11目前十一頁\總數(shù)七十九頁\編于十八點如果，就稱此運(yùn)輸問題為非平衡運(yùn)輸問題，包含產(chǎn)大于銷和銷大于產(chǎn)兩種情況，這我們將在第3節(jié)介紹。下面我們只考慮產(chǎn)銷平衡問題，產(chǎn)銷平衡運(yùn)輸問題的一般模型為：在產(chǎn)銷平衡條件下，可知（4.2）其中約束條件右端常數(shù)ai和bj滿足（4.2），在運(yùn)輸問題（4.3）中，目標(biāo)函數(shù)要求運(yùn)輸總費(fèi)用最??；前m個約束條件的意義是：由某一產(chǎn)地運(yùn)往各個銷地的物資數(shù)量之和等于該產(chǎn)地的產(chǎn)量；中間n個約束條件的意義是：由各產(chǎn)地運(yùn)往某一銷地的物資數(shù)量之和等于該銷地的銷量；后mn個約束條件是變量的非負(fù)條件.（4.3）12目前十二頁\總數(shù)七十九頁\編于十八點4.1.2運(yùn)輸問題數(shù)學(xué)模型的特點

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

（4.4）

由此可知，產(chǎn)銷平衡運(yùn)輸問題數(shù)學(xué)模型有下述特點：13目前十三頁\總數(shù)七十九頁\編于十八點（1）約束條件中決策變量的系數(shù)等于0或1.（2）所有約束條件都是等式.（3）約束條件的系數(shù)矩陣中每一列有兩個非零元素，對應(yīng)于變量Xij的系數(shù)列向量Pij，其分量除第i個和第m+j個等于1以外，其余的均為零，即Pij=ei+em+j.這對應(yīng)于每一個變量在前m個約束方程中出現(xiàn)一次，在后n個約束方程中也出現(xiàn)一次.（4）由于（4.2）成立，因而約束條件中m個約束方程并不是獨(dú)立的，實際上只有個m+n-1方程是獨(dú)立的，因而約束方程系數(shù)矩陣的秩為m+n-1.（5）運(yùn)輸問題（4.3）總存在基可行解，下節(jié)我們將給出找基可行解的方法.（6）運(yùn)輸問題存在有限最優(yōu)解這是由于對運(yùn)輸問題（4.3），若令其變量則Xij就是該運(yùn)輸問題的一個可行解，其中是總產(chǎn)量；另一方面，（4.3）的目標(biāo)函數(shù)有下界，即目標(biāo)函數(shù)不會趨向于負(fù)無窮，從而運(yùn)輸問題必存在有限最優(yōu)解.14目前十四頁\總數(shù)七十九頁\編于十八點例2某種物品先存放在兩個倉庫A1和A2中，再運(yùn)往三個使用地B1，B2和

B3，產(chǎn)銷平衡表和單位運(yùn)價表如下表4-7所示，試建立使總運(yùn)費(fèi)最小的運(yùn)輸問題數(shù)學(xué)模型.使用地倉庫B1

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

B2B3供應(yīng)量A133146210A234534需求量356表4-8有4個填有數(shù)字的格，它們對應(yīng)4個基變量，兩個空格對應(yīng)2個非基變量.可以驗證，基可行解對應(yīng)的約束方程組的系數(shù)列向量線性無關(guān).17目前十七頁\總數(shù)七十九頁\編于十八點4.2表上作業(yè)法

由于運(yùn)輸問題具有特殊形式，因而我們可以在運(yùn)輸表中直接對問題求解，稱為表上作業(yè)法.表上作業(yè)法是單純形法求解運(yùn)輸問題時的簡化方法，其實質(zhì)是單純形法，它的步驟可歸納為：(1)找出初始基可行解，即在m行n列產(chǎn)銷平衡表上給出m+n-1個數(shù)字格.(2)求各非基變量的檢驗數(shù)，即在表上計算空格的檢驗數(shù)，并判別是否達(dá)到最優(yōu)解，如果是最優(yōu)解，停止；否則轉(zhuǎn)下一步.(3)確定換入變量和換出變量，找出新的基可行解，在表上進(jìn)行調(diào)整.(4)重復(fù)(2)(3)，直至得到最優(yōu)解.表上作業(yè)法的步驟中，確定初始基可行解、判斷是否達(dá)到最優(yōu)解和確定換入換出變量并在表上進(jìn)行調(diào)整是其中幾個關(guān)鍵點.下面我們依次來看.18目前十八頁\總數(shù)七十九頁\編于十八點4.2.1確定初始基可行解

我們以一個例子來說明找初始基可行解的方法.下表4-9表示某個運(yùn)輸問題的產(chǎn)銷平衡表和單位運(yùn)價表(二表合一).一般來說，找運(yùn)輸問題的初始基可行解主要有三種方法，即西北角法、最小元素法和差值法（也叫伏格爾法），下面我們用上表4-9依次來說明.銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量365619目前十九頁\總數(shù)七十九頁\編于十八點1.西北角法(1)從圖的西北角（即左上方）開始，在(A1,B1)格填入a1和b1中的較小值，這里填入較小值b1=3，即從A1運(yùn)送3個單位物資到B1，此時的B1物資已經(jīng)全部滿足，劃去B1列，如下表4-10所示.銷地產(chǎn)地B1B2B3B4產(chǎn)量A133113107A219284A3741059銷量365620目前二十頁\總數(shù)七十九頁\編于十八點（2）向a1,b1中較大數(shù)方向移動一格（或向右，或向下），這里是向右移動一格，移動到(A1,B2)位置.B2需要6個單位物資，而A1只剩有4個單位，故在(A1,B2)處填4，A1的物資已經(jīng)全部發(fā)完，劃去A1行，如下表4-11所示.銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A219284A3741059銷量365621目前二十一頁\總數(shù)七十九頁\編于十八點（3）繼續(xù)按照上述步驟進(jìn)行，可知A2向B2運(yùn)送2個單位物資，此時B2的物資已經(jīng)滿足，劃去B2列.銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A2129284A3741059銷量365622目前二十二頁\總數(shù)七十九頁\編于十八點（4）繼續(xù)按照上述步驟進(jìn)行.銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A21292284A3741059銷量365623目前二十三頁\總數(shù)七十九頁\編于十八點（5）繼續(xù)進(jìn)行.銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A21292284A37431059銷量365624目前二十四頁\總數(shù)七十九頁\編于十八點（6）繼續(xù)進(jìn)行.最后在(A3,B4)處填入6，此時A3和B4的物資已經(jīng)全部發(fā)送和接收完畢，因而同時劃去A3行和B4列，如下表4-13所示.銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A21292284A374310659銷量365625目前二十五頁\總數(shù)七十九頁\編于十八點（7）得到初始方案，如下表4-14所示.銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A21292284A374310659銷量3656總運(yùn)費(fèi)26目前二十六頁\總數(shù)七十九頁\編于十八點2.最小元素法用西北角法很容易得到初始基可行解，但得到的解往往離最優(yōu)解相差甚遠(yuǎn).為了得到較好的初始基可行解，我們通常希望就近供應(yīng)，即從單位運(yùn)價表中最小的運(yùn)價開始確定供銷關(guān)系，然后次小，一直到給出初始基可行解為止，這種方法稱為最小元素法.我們?nèi)砸员?-9所示的運(yùn)輸問題來說明最小元素法.銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量365627目前二十七頁\總數(shù)七十九頁\編于十八點（1）從表中最小單位運(yùn)價開始確定運(yùn)輸方案，這里(A2,B1)位置的1最小，因而A2優(yōu)先供應(yīng)物資到B1，根據(jù)的A2產(chǎn)量和B1的銷量知，A2只能供應(yīng)3個單位物資到B1，B1已經(jīng)滿足，劃去B1列，如下表4-15所示.銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A2319284A3741059銷量365628目前二十八頁\總數(shù)七十九頁\編于十八點（2）再從未劃去的元素中找最小元素，并從該元素開始確定運(yùn)輸關(guān)系，這里(A2,B3)處2最小，故從此元素開始，即A2優(yōu)先供應(yīng)B3物資，A2只剩1個單位物資，從而A2只能供應(yīng)1個單位物資到B3，A2物資已經(jīng)發(fā)完，劃去A2行，如下表4-16所示.銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A23191284A3741059銷量365629目前二十九頁\總數(shù)七十九頁\編于十八點（3）再從未劃去的元素中找最小元素，并從該元素開始確定運(yùn)輸關(guān)系，這里(A1,B3)處3最小，故從此元素開始，即A1優(yōu)先供應(yīng)B3物資，根據(jù)A1的產(chǎn)量和B3的銷量知A1供應(yīng)4個單位物資到B3，B3物資已經(jīng)滿足，劃去B3列，如下表所示.銷地產(chǎn)地B1B2B3B4產(chǎn)量A131143107A23191284A3741059銷量365630目前三十頁\總數(shù)七十九頁\編于十八點（4）再從未劃去的元素中找最小元素，并從該元素開始確定運(yùn)輸關(guān)系，這里(A3,B2)處4最小，故從此元素開始，即A3優(yōu)先供應(yīng)B2物資6個單位，B2物資已經(jīng)滿足，劃去B2列，如下表所示.銷地產(chǎn)地B1B2B3B4產(chǎn)量A131143107A23191284A37641059銷量365631目前三十一頁\總數(shù)七十九頁\編于十八點（5）再從未劃去的元素中找最小元素，并從該元素開始確定運(yùn)輸關(guān)系，這里(A3,B4)處5最小，故從此元素開始，即A3優(yōu)先供應(yīng)B4物資3個單位，A3物資已經(jīng)發(fā)完，劃去A3行，如下表4-17所示.銷地產(chǎn)地B1B2B3B4產(chǎn)量A131143107A23191284A376410359銷量365632目前三十二頁\總數(shù)七十九頁\編于十八點（6）最后在(A1,B4)處填3，即A1供應(yīng)B4物資3個單位，A1物資已經(jīng)發(fā)完，劃去A3行，B4物資全部滿足，劃去B4列，如下表所示.銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量365633目前三十三頁\總數(shù)七十九頁\編于十八點（7）得到初始方案，如下表4-18所示.銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656總運(yùn)費(fèi)34目前三十四頁\總數(shù)七十九頁\編于十八點3.差值法（伏格爾法）初看起來，最小元素法十分合理.事實上，最小元素法的缺點是：為了節(jié)省一處的費(fèi)用，有時造成其它處要多花幾倍的運(yùn)費(fèi)，這是因為有時按某一最小單位運(yùn)價優(yōu)先安排物資運(yùn)輸時，卻可能導(dǎo)致不得不采用運(yùn)費(fèi)很高的其它點對，從而使整個運(yùn)輸費(fèi)用增加.伏格爾法考慮到，一個產(chǎn)地的產(chǎn)品假如不能按最小費(fèi)用就近供應(yīng)，就考慮次小費(fèi)用，這樣最小費(fèi)用和次小費(fèi)用就有一個差額，差額越大，說明不按最小費(fèi)用調(diào)運(yùn)時，運(yùn)費(fèi)增加越多，因而對差額最大處，就應(yīng)當(dāng)采用最小調(diào)運(yùn)方案.基于此，伏格爾法的步驟是：每次從當(dāng)前運(yùn)價表上，計算各行各列中最小費(fèi)用與次小費(fèi)用這兩個運(yùn)價的差值，優(yōu)先取最大差值的行或列中最小的單位運(yùn)價來確定運(yùn)輸關(guān)系，直到求出初始方案.35目前三十五頁\總數(shù)七十九頁\編于十八點銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131131070A2192841A37410591銷量3656列差額2513我們?nèi)匀豢紤]表4-9所示的運(yùn)輸問題，伏格爾法確定初始基可行解的步驟如下：（1）先分別計算出各行和各列最小費(fèi)用與次小費(fèi)用的差額，稱為行差額和列差額，并將行差額和列差額填入該表的最右列和最下行，如下表4-19所示.36目前三十六頁\總數(shù)七十九頁\編于十八點銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131131070A2192841A376410591銷量3656列差額2513（2）從行差額和列差額中選出最大者，選擇它所在的行或列中的最小費(fèi)用所在的格作為優(yōu)先的運(yùn)輸關(guān)系.在這里行差額與列差額最大值為5，故選擇5所在的列最小單位運(yùn)價4為優(yōu)先運(yùn)輸關(guān)系，即讓A3優(yōu)先供應(yīng)物資到B2，根據(jù)產(chǎn)、銷量知A3供應(yīng)6個單位物資到B2，此時B2列已滿足，劃去B2列，得下表4-20.37目前三十七頁\總數(shù)七十九頁\編于十八點銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131131070A2192841A3764103592銷量3656列差額2513（3）計算剩余元素的行差額和列差額，選出最大者，選擇它所在的行或列中的最小費(fèi)用所在的格作為優(yōu)先的運(yùn)輸關(guān)系.在這里行差額與列差額最大值為B4列的3，故選擇3所在的列最小單位運(yùn)價5為優(yōu)先運(yùn)輸關(guān)系，即讓A3供應(yīng)物資到B4，由剩余的產(chǎn)、銷量知A3只能供應(yīng)3個單位物資到B4，這時A3已經(jīng)發(fā)貨完畢，劃去A3行，如表4-21所示.38目前三十八頁\總數(shù)七十九頁\編于十八點（4）繼續(xù)計算剩余元素的行差額和列差額，并按照上述步驟確定運(yùn)輸關(guān)系，經(jīng)過若干步以后，最后填2到(A1,B4)格，A1和B4的供應(yīng)量和需求量都得到滿足，此時同時劃去A1行和B4列，可得初始方案，其余變量為0，如下表4-22所示.銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311532107A23192184A376410359銷量3656總運(yùn)費(fèi)為39目前三十九頁\總數(shù)七十九頁\編于十八點從上述計算步驟可見，三種方法除了在確定供求關(guān)系的原則不同外，其余步驟是相同的.表4-9所示的運(yùn)輸問題用三種方法得到的初始方案和總運(yùn)費(fèi)分別是：西北角法得到的初始方案是總運(yùn)費(fèi)為135；最小元素法得到初始方案為總運(yùn)費(fèi)是86；差值法的初始方案是總運(yùn)費(fèi)85.

比較三種方法給出的初始基可行解，伏格爾法給出的解的目標(biāo)函數(shù)值最小，最小元素法次之，西北角法給出的解的目標(biāo)函數(shù)值最大.一般來說，伏格爾法確定的初始基可行解更接近最優(yōu)解，常用來作為運(yùn)輸問題的初始基可行解進(jìn)行迭代40目前四十頁\總數(shù)七十九頁\編于十八點需要注意的是三種方法給出的初始方案都是運(yùn)輸問題的基可行解，這是因為：（1）在產(chǎn)銷平衡表上，選擇表中某一元素以后，要比較產(chǎn)量和銷量，當(dāng)產(chǎn)大于銷，劃去該元素所在列；當(dāng)產(chǎn)小于銷，劃去該元素所在行，然后在未劃去的元素中繼續(xù)選另一元素.表中共有m行n列，總共可劃條m+n直線，但當(dāng)表中只剩一個元素時，同時劃去一行和一列.因而表中共填了m+n-1個數(shù)字，即給出了m+n-1個基變量的值.注：選擇表中某一個元素后，有可能同時劃去一行和一列，這就出現(xiàn)退化，退化的處理我們在后文中講述.（2）這m+n-1個基變量對應(yīng)的系數(shù)列向量是線性獨(dú)立的.這是因為若表中確定了某一個基變量以后，它對應(yīng)的系數(shù)列向量，給定的值以后，將劃去第i行或第j列，即其后的系數(shù)列向量中不再出現(xiàn)或，因而不可能用其它向量的線性組合表示.所以這m+n-1個基變量對應(yīng)的系數(shù)列向量是線性獨(dú)立的.41目前四十一頁\總數(shù)七十九頁\編于十八點4.2.2解的最優(yōu)性檢驗及改進(jìn)

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

1.閉回路法閉回路方法是在初始調(diào)運(yùn)方案表中，從任意空格出發(fā)，沿著縱向或橫向行進(jìn)，遇到適當(dāng)填有數(shù)據(jù)的方格后90度轉(zhuǎn)彎，繼續(xù)行進(jìn)，總能回到原來空格，這個封閉的曲線稱為閉回路.可以證明每個空格都對應(yīng)著唯一的閉回路.42目前四十二頁\總數(shù)七十九頁\編于十八點銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656在表4-9所表示的運(yùn)輸問題中，用最小元素法得到的初始調(diào)運(yùn)方案是表4-18，我們以此調(diào)運(yùn)方案為例作閉回路.對空格(A1,B1)，它的閉回路如表4-23所示.43目前四十三頁\總數(shù)七十九頁\編于十八點銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656再如對空格(A1,B2)，它的閉回路如下表4-24所示.44目前四十四頁\總數(shù)七十九頁\編于十八點銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656同樣，空格(A3,B1)的閉回路如下表4-25所示.45目前四十五頁\總數(shù)七十九頁\編于十八點下面我們看用閉回路法計算非基變量（空格點）檢驗數(shù)的計算方法.首先考慮表4-23的空格點(A1,B1),假設(shè)產(chǎn)地A1運(yùn)送1個單位的物資到銷地B1，為使運(yùn)入銷地B1物資的數(shù)量等于它的銷量，就應(yīng)當(dāng)將原來A2運(yùn)送到的B1物資數(shù)量減去1個單位，即將(A2,B1)格的3變?yōu)?；另一方面，為使運(yùn)出產(chǎn)地A2物資的數(shù)量等于它的產(chǎn)量，就應(yīng)當(dāng)將原來(A2,B3)格的數(shù)1加上1，再考慮B3知應(yīng)將(A1,B3)格的4變?yōu)?，從而得到一個新的運(yùn)輸方法.顯然這樣的調(diào)整將影響到空格(A1,B1)閉回路上的各個數(shù)據(jù).按照上述假設(shè)，如果由產(chǎn)地A1運(yùn)送1個單位的物資到銷地B1，由此引起的總費(fèi)用變化是，即總費(fèi)用增加1.按照檢驗數(shù)的定義知它正是非基變量（即空格(A1,B1)）的檢驗數(shù).同理按空格(A1,B2)的閉回路知它的檢驗數(shù)為，空格(A3,B1)的檢驗數(shù)為10.46目前四十六頁\總數(shù)七十九頁\編于十八點銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107[1][2]A23191284[1][-1]A376410359[10][12]銷量3656從這幾個檢驗數(shù)的計算過程可以看出，非基變量的檢驗數(shù)等于其閉回路上偶數(shù)次拐角點運(yùn)價之和減去奇數(shù)次拐角點運(yùn)價之和.用此方法可以計算出各個空格的檢驗數(shù)（數(shù)字格表示的基變量的檢驗數(shù)始終為0），如下表4-26中方括弧中數(shù)字所示.

47目前四十七頁\總數(shù)七十九頁\編于十八點由于運(yùn)輸問題的目標(biāo)函數(shù)是要求實現(xiàn)最小化，因而對該問題的某個基可行解，如果所有空格的檢驗數(shù)中沒有負(fù)值，則該基可行解就是最優(yōu)解；如果某個空格處出現(xiàn)負(fù)檢驗數(shù)，表明調(diào)運(yùn)方案不是最優(yōu)解，這時就要進(jìn)行調(diào)解.和單純形法類似，當(dāng)有兩個和兩個以上空格的檢驗數(shù)為負(fù)時，一般選其中最小的負(fù)檢驗數(shù)，以它對應(yīng)的空格作為調(diào)入格，即該空格對應(yīng)的變量為進(jìn)基變量.在進(jìn)基變量的回路中，比較奇數(shù)拐角點的運(yùn)量，為了使新得到的解仍為基可行解，應(yīng)當(dāng)選擇一個具有最小運(yùn)量的基變量作為出基變量，并使調(diào)整的運(yùn)量為各個奇數(shù)拐角點運(yùn)量的最小值.在表4-26中，只有空格(A2,B4)處的檢驗數(shù)為負(fù)，因而它對應(yīng)的變量為進(jìn)基變量，它的閉回路如表4-27所示.48目前四十八頁\總數(shù)七十九頁\編于十八點銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656奇數(shù)拐點處運(yùn)量的最小值為1,因而為了保持平衡，將奇數(shù)拐點處的運(yùn)量減去1，偶數(shù)拐點處的運(yùn)量加1，調(diào)整后的運(yùn)輸方案如下表4-28所示.49目前四十九頁\總數(shù)七十九頁\編于十八點銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311532107A23192184A376410359銷量3656調(diào)整以后，再計算各個空格的檢驗數(shù)，如果所有的檢驗數(shù)均大于等于零，則這個運(yùn)輸方案就是最優(yōu)解；如果還有某個空格的檢驗數(shù)為負(fù)數(shù)，則再以這個空格為調(diào)入格，作相應(yīng)的基變換，直到所有的檢驗數(shù)為非負(fù).上述表中得到的所有的檢驗數(shù)為非負(fù)，因而此運(yùn)輸方案是最優(yōu)方案.50目前五十頁\總數(shù)七十九頁\編于十八點2.位勢法

在閉回路法中，為了計算一個空格點處的檢驗數(shù)，就要畫出該空格的閉回路，當(dāng)空格點較多時，計算很繁.位勢法是另一種計算每個空格檢驗數(shù)的方法，這個方法比閉回路法更加簡潔.51目前五十一頁\總數(shù)七十九頁\編于十八點位勢法的基本思想是：

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

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

由于基變量的檢驗數(shù)始終為0，因而對于基變量，始終有，所以我們可以根據(jù)基變量對應(yīng)的單位運(yùn)輸費(fèi)用算出所有ui與vj的值，再根據(jù)ui與vj的值算出非基變量的檢驗數(shù)。52目前五十二頁\總數(shù)七十九頁\編于十八點例如在表4-9所表示的運(yùn)輸問題中，用最小元素法得到的初始調(diào)運(yùn)方案如下表所示.銷地產(chǎn)地B1B2B3B4uiA131143310u1A2319128u2A37641035u3vjv1v2v3v4在此調(diào)運(yùn)方案中，我們可以根據(jù)基變量對應(yīng)的單位運(yùn)輸費(fèi)用cij算出ui和vj.計算方程組是：53目前五十三頁\總數(shù)七十九頁\編于十八點銷地產(chǎn)地B1B2B3B4uiA1311433100A2319128-1A37641035-5vj29310該方程組含6個方程和7個未知數(shù)，因而有一個未知數(shù)是自由變量，通常我們令u1=0，此時可得到所有ui(i=1,2,…m)和vj(j=1,2,…,n)的值，如下表4-29所示.54目前五十四頁\總數(shù)七十九頁\編于十八點根據(jù)ui和vj的值算出所有空格處（即非基變量）的檢驗數(shù)，計算公式為cij-(ui+vj)，計算結(jié)果如下表4-30方括號數(shù)字所示，這和用閉回路法得到的檢驗數(shù)結(jié)果一致.銷地產(chǎn)地B1B2B3B4uiA1311433100[1][2]A2319128-1[1][-1]A37641035-5[10][12]vj29310因為檢驗數(shù)，故這個解不是最優(yōu)解，因此我們再根據(jù)閉回路法進(jìn)行調(diào)整，直至得出最優(yōu)解.55目前五十五頁\總數(shù)七十九頁\編于十八點表上作業(yè)法在計算中可能還會出現(xiàn)一些問題，這里我們需要說明.1.當(dāng)?shù)竭\(yùn)輸問題的最優(yōu)解時，如果有某個非基變量的檢驗數(shù)等于零，則說明該運(yùn)輸問題有無窮多最優(yōu)解.2.退化(1)當(dāng)確定供需關(guān)系時，如果某個產(chǎn)地的剩余產(chǎn)量等于某個銷地的需量，這時就要劃去一行和一列，此時需要添加一個0，它的位置可在對應(yīng)劃去的那行或那列的任意處.(2)在用閉回路法調(diào)整時，如果閉回路奇數(shù)拐彎處具有兩個或兩個以上相等的最小值，此時經(jīng)調(diào)整后，得到退化解，這時有一個數(shù)字格必須填0，以表示它是基變量.56目前五十六頁\總數(shù)七十九頁\編于十八點4.3產(chǎn)銷不平衡的運(yùn)輸問題

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

57目前五十七頁\總數(shù)七十九頁\編于十八點由于總產(chǎn)量大于總銷量，因而要考慮多余物資就地貯存的問題.為借助產(chǎn)銷平衡運(yùn)輸問題的表上作業(yè)法，可增加一個假想的銷地Bn+1，由各產(chǎn)地Ai(i=1,2,…,m)運(yùn)送到這個銷地Bn+1物資的數(shù)量設(shè)為，實際上就是產(chǎn)地Ai就地貯存物資的數(shù)量，顯然單位運(yùn)價.因此假想后原問題的最優(yōu)總費(fèi)用與假想之前的最優(yōu)總費(fèi)用是一致的.

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

（4.6）

58目前五十八頁\總數(shù)七十九頁\編于十八點銷地產(chǎn)地B1

B2…BnBn+1產(chǎn)量A1X11c11X12c12X1nc1nX1，n+10a1A2X21c21X22c22X2nc2nX2，n+10a2…AmXm1cm1Xm2cm2XmncmnXm，n+10am銷量b1b2bn可以看出，模型（4.6）是有m個產(chǎn)地，n+1個銷地的產(chǎn)銷平衡運(yùn)輸問題，因而通過假想銷地，可將產(chǎn)大于銷的運(yùn)輸問題轉(zhuǎn)化為產(chǎn)銷平衡運(yùn)輸問題.和模型（4.6）對應(yīng)的運(yùn)輸表如下表所示.59目前五十九頁\總數(shù)七十九頁\編于十八點如果總銷量大于總產(chǎn)量，即可仿照產(chǎn)大于銷的操作過程，增加一個假想的產(chǎn)地Am+1，它的產(chǎn)量為由于這個假想的產(chǎn)地并不存在，求出的由它發(fā)往各個銷地的物資數(shù)量實際上是各銷地所需物資的欠缺額，這部分物資的運(yùn)輸并未發(fā)生，因而單位運(yùn)價.這樣也可以將原問題化為產(chǎn)銷平衡運(yùn)輸問題.60目前六十頁\總數(shù)七十九頁\編于十八點例3某市有三個造紙廠A1，A2，A3和四個批發(fā)用戶B1，B2，B3，B4，各造紙廠紙的產(chǎn)量、各批發(fā)用戶的需求量及各造紙廠到各批發(fā)用戶的單位運(yùn)價如下表4-32所示，試確定運(yùn)輸總費(fèi)用最小的調(diào)運(yùn)方案.批發(fā)用戶造紙廠B1B2B3B4產(chǎn)量A1312348A2112595A367159需求量435661目前六十一頁\總數(shù)七十九頁\編于十八點解由于該問題中總產(chǎn)量為22，總銷量為18，因而該問題是總產(chǎn)量大于總銷量的產(chǎn)銷不平衡運(yùn)輸問題.按照模型（4.5）的分析知，增加一個假想銷地B5，其需求量為22-18=4，可將該問題表示的運(yùn)輸問題轉(zhuǎn)化為下表4-33所示的產(chǎn)銷平衡運(yùn)輸問題.用戶造紙廠B1B2B3B4B5產(chǎn)量A13123408A21125905A3671509需求量435622-18=4根據(jù)表上作業(yè)法，可得該問題的最優(yōu)運(yùn)輸方案如下表4-34所示62目前六十二頁\總數(shù)七十九頁\編于十八點用戶造紙廠B1B2B3B4B5產(chǎn)量A1431234408A2113259205A3675125209銷量435622-18=4在以上討論中，我們都假定物資由產(chǎn)地直接運(yùn)送到銷售目的地，不經(jīng)過中間轉(zhuǎn)運(yùn).在實際問題中，還會遇到將物資運(yùn)到某個中間轉(zhuǎn)運(yùn)站（包括產(chǎn)地、銷地或中間轉(zhuǎn)運(yùn)倉庫），然后再運(yùn)往銷售目的地的情況.有時經(jīng)轉(zhuǎn)運(yùn)比直接運(yùn)往目的地更為經(jīng)濟(jì)，在決定運(yùn)輸方案時有必要將轉(zhuǎn)運(yùn)也考慮進(jìn)去.當(dāng)然考慮轉(zhuǎn)運(yùn)將使問題變得復(fù)雜，有興趣的讀者可以參閱相關(guān)文獻(xiàn).63目前六十三頁\總數(shù)七十九頁\編于十八點

下面我們通過幾個例子介紹運(yùn)輸問題的一些實際應(yīng)用.例4設(shè)有三個化肥廠供應(yīng)四個地區(qū)的農(nóng)用化肥，假定等量的化肥在這些地區(qū)試用效果相同.各化肥廠年產(chǎn)量、各地區(qū)年需求量（單位：萬噸）及從各化肥廠到各地區(qū)運(yùn)送單位化肥的單位運(yùn)價（單位：萬元/萬噸）如表4-35所示，試給出總運(yùn)費(fèi)最小的化肥調(diào)撥方案.4.4運(yùn)輸問題應(yīng)用舉例

64目前六十四頁\總數(shù)七十九頁\編于十八點需求地區(qū)化肥廠ⅠⅡⅢⅣ產(chǎn)量11613221750214131915603192023—50最低需求最高需求3050707003010不限解這是一個產(chǎn)銷不平衡的運(yùn)輸問題，總產(chǎn)量為160萬噸，四個地區(qū)的最低需求為110萬噸，最高需求不限，但根據(jù)現(xiàn)有產(chǎn)量，第Ⅳ個地區(qū)每年最多能分配到60萬噸，因而最高需求為210萬噸，大于總產(chǎn)量.為了求得平衡，在產(chǎn)銷表中增加一個假想的化肥廠4，其年產(chǎn)量為50萬噸.65目前六十五頁\總數(shù)七十九頁\編于十八點各地區(qū)的需求量包含最低需求和額外需求兩部分.如地區(qū)Ⅰ，其中30萬噸是最低需求，故不能由假想化肥廠Ⅳ供給，因而令假想化肥廠4到地區(qū)Ⅰ的單位運(yùn)價為M（M為任意大的數(shù)），而額外需求20萬噸對地區(qū)Ⅰ來說可以滿足，也可以不滿足，因此額外需求可以由假想化肥廠4供給，而且相應(yīng)的運(yùn)價為0.事實上，對凡是需求分兩種情況的地區(qū)，我們按照兩個地區(qū)看待，這樣可將原問題轉(zhuǎn)化為產(chǎn)銷平衡運(yùn)輸問題，其產(chǎn)銷平衡表與單位運(yùn)價表如下表4-36所示.66目前六十六頁\總數(shù)七十九頁\編于十八點需求地區(qū)化肥廠ⅠⅠⅡⅢⅣⅣ產(chǎn)量116161322171750214141319151560319192023MM504M0M0M050需求量302070301050根據(jù)表上作業(yè)法進(jìn)行計算，可以求得最優(yōu)方案如下表4-37所示.67目前六十七頁\總數(shù)七十九頁\編于十八點需求地區(qū)化肥廠ⅠⅠⅡⅢⅣⅣ產(chǎn)量1161650132217175021414201319101530156033019201902023MM504M0M300M20050需求量302070301050從表4-37可以看出，地區(qū)Ⅰ滿足最高需求量50萬噸，地區(qū)Ⅲ沒有接收到任何物資，只滿足最低需求0，而地區(qū)Ⅳ滿足了40萬噸68目前六十八頁\總數(shù)七十九頁\編于十八點使用者產(chǎn)地ⅠⅡⅢ產(chǎn)量124321563324使用量1046例5設(shè)有三個產(chǎn)地生產(chǎn)同一種產(chǎn)品并供應(yīng)給三個使用者，各產(chǎn)地到各使用者的單位運(yùn)價及使用者的需求量如下表4-38所示.由于銷售需要及客觀條件的限制，產(chǎn)地1至少要發(fā)出6個單位的產(chǎn)品，它最多只能生產(chǎn)11個單位的產(chǎn)品；產(chǎn)地2的產(chǎn)量為7個單位；產(chǎn)地3至少要發(fā)出4個單位的產(chǎn)品，試根據(jù)上述條件用表上作業(yè)法求該運(yùn)輸問題的最優(yōu)調(diào)運(yùn)方案.69目前六十九頁\總數(shù)七十九頁\編于十八點使用者產(chǎn)地ⅠⅡⅢⅣ產(chǎn)量1243M61243052156M73324M4332403使用量10465解由表4-38可知，若產(chǎn)地1、2的產(chǎn)量按最小值計算，在產(chǎn)銷平衡條件下，產(chǎn)地3的產(chǎn)量最多等于7.用類似于例4的方法，可將原問題表示成下表4-39所示的產(chǎn)銷平衡運(yùn)輸問題.由表4-39求解該產(chǎn)銷平衡運(yùn)輸問題解的過程及結(jié)果請讀者自己完成.70目前七十頁\總數(shù)七十九頁\編于十八點銷地產(chǎn)地ⅠⅡⅢ產(chǎn)量112220214540323330銷量302020例6三個產(chǎn)地欲將同一種物資運(yùn)送到三個銷地，各產(chǎn)地產(chǎn)量、各銷地銷量以及各產(chǎn)