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

關(guān)于最優(yōu)化理論運(yùn)輸問題第一頁，共八十四頁，編輯于2023年，星期一2第四章運(yùn)輸問題◆4.1運(yùn)輸問題的數(shù)學(xué)模型

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

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

第三頁，共八十四頁，編輯于2023年，星期一4例1假設(shè)有三家工廠，都將產(chǎn)品運(yùn)往三個(gè)不同的商店(如圖)，每家工廠每周的生產(chǎn)能力和每個(gè)商店每周的需求量如表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é)模型

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

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

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

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

銷地產(chǎn)地B1

B2…Bn產(chǎn)量A1X11c11X12c12X1nc1na1A2X21c21X22c22X2nc2na2…AmXm1cm1Xm2cm2Xmncmnam銷量b1b2bn表中每格元素Xij代表運(yùn)量，右上角元素cij代表單位運(yùn)價(jià).第十一頁，共八十四頁，編輯于2023年，星期一12如果，就稱此運(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)用最?。磺癿個(gè)約束條件的意義是：由某一產(chǎn)地運(yùn)往各個(gè)銷地的物資數(shù)量之和等于該產(chǎn)地的產(chǎn)量；中間n個(gè)約束條件的意義是：由各產(chǎn)地運(yùn)往某一銷地的物資數(shù)量之和等于該銷地的銷量；后mn個(gè)約束條件是變量的非負(fù)條件.（4.3）第十二頁，共八十四頁，編輯于2023年，星期一134.1.2運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)

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

（4.4）

由此可知，產(chǎn)銷平衡運(yùn)輸問題數(shù)學(xué)模型有下述特點(diǎn)：第十三頁，共八十四頁，編輯于2023年，星期一14（1）約束條件中決策變量的系數(shù)等于0或1.（2）所有約束條件都是等式.（3）約束條件的系數(shù)矩陣中每一列有兩個(gè)非零元素，對應(yīng)于變量Xij的系數(shù)列向量Pij，其分量除第i個(gè)和第m+j個(gè)等于1以外，其余的均為零，即Pij=ei+em+j.這對應(yīng)于每一個(gè)變量在前m個(gè)約束方程中出現(xiàn)一次，在后n個(gè)約束方程中也出現(xiàn)一次.（4）由于（4.2）成立，因而約束條件中m個(gè)約束方程并不是獨(dú)立的，實(shí)際上只有個(gè)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)輸問題的一個(gè)可行解，其中是總產(chǎn)量；另一方面，（4.3）的目標(biāo)函數(shù)有下界，即目標(biāo)函數(shù)不會趨向于負(fù)無窮，從而運(yùn)輸問題必存在有限最優(yōu)解.第十四頁，共八十四頁，編輯于2023年，星期一15例2

某種物品先存放在兩個(gè)倉庫A1和A2中，再運(yùn)往三個(gè)使用地B1，B2和

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

使用地倉庫B1

B2B3供應(yīng)量A133146210A234534需求量356表4-8有4個(gè)填有數(shù)字的格，它們對應(yīng)4個(gè)基變量，兩個(gè)空格對應(yīng)2個(gè)非基變量.可以驗(yàn)證，基可行解對應(yīng)的約束方程組的系數(shù)列向量線性無關(guān).第十七頁，共八十四頁，編輯于2023年，星期一184.2表上作業(yè)法

由于運(yùn)輸問題具有特殊形式，因而我們可以在運(yùn)輸表中直接對問題求解，稱為表上作業(yè)法.表上作業(yè)法是單純形法求解運(yùn)輸問題時(shí)的簡化方法，其實(shí)質(zhì)是單純形法，它的步驟可歸納為：(1)找出初始基可行解，即在m行n列產(chǎn)銷平衡表上給出m+n-1個(gè)數(shù)字格.(2)求各非基變量的檢驗(yàn)數(shù)，即在表上計(jì)算空格的檢驗(yàn)數(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)整是其中幾個(gè)關(guān)鍵點(diǎn).下面我們依次來看.第十八頁，共八十四頁，編輯于2023年，星期一194.2.1確定初始基可行解

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

銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量3656第十九頁，共八十四頁，編輯于2023年，星期一201.西北角法(1)從圖的西北角（即左上方）開始，在(A1,B1)格填入a1和b1中的較小值，這里填入較小值b1=3，即從A1運(yùn)送3個(gè)單位物資到B1，此時(shí)的B1物資已經(jīng)全部滿足，劃去B1列，如下表4-10所示.

銷地產(chǎn)地B1B2B3B4產(chǎn)量A133113107A219284A3741059銷量3656第二十頁，共八十四頁，編輯于2023年，星期一21（2）向a1,b1中較大數(shù)方向移動一格（或向右，或向下），這里是向右移動一格，移動到(A1,B2)位置.B2需要6個(gè)單位物資，而A1只剩有4個(gè)單位，故在(A1,B2)處填4，A1的物資已經(jīng)全部發(fā)完，劃去A1行，如下表4-11所示.

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A219284A3741059銷量3656第二十一頁，共八十四頁，編輯于2023年，星期一22（3）繼續(xù)按照上述步驟進(jìn)行，可知A2向B2運(yùn)送2個(gè)單位物資，此時(shí)B2的物資已經(jīng)滿足，劃去B2列.

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A2129284A3741059銷量3656第二十二頁，共八十四頁，編輯于2023年，星期一23（4）繼續(xù)按照上述步驟進(jìn)行.

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A21292284A3741059銷量3656第二十三頁，共八十四頁，編輯于2023年，星期一24（5）繼續(xù)進(jìn)行.

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A21292284A37431059銷量3656第二十四頁，共八十四頁，編輯于2023年，星期一25（6）繼續(xù)進(jìn)行.最后在(A3,B4)處填入6，此時(shí)A3和B4的物資已經(jīng)全部發(fā)送和接收完畢，因而同時(shí)劃去A3行和B4列，如下表4-13所示.

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A21292284A374310659銷量3656第二十五頁，共八十四頁，編輯于2023年，星期一26（7）得到初始方案，如下表4-14所示.

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A21292284A374310659銷量3656總運(yùn)費(fèi)第二十六頁，共八十四頁，編輯于2023年，星期一272.最小元素法用西北角法很容易得到初始基可行解，但得到的解往往離最優(yōu)解相差甚遠(yuǎn).為了得到較好的初始基可行解，我們通常希望就近供應(yīng)，即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定供銷關(guān)系，然后次小，一直到給出初始基可行解為止，這種方法稱為最小元素法.我們?nèi)砸员?-9所示的運(yùn)輸問題來說明最小元素法.

銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量3656第二十七頁，共八十四頁，編輯于2023年，星期一28（1）從表中最小單位運(yùn)價(jià)開始確定運(yùn)輸方案，這里(A2,B1)位置的1最小，因而A2優(yōu)先供應(yīng)物資到B1，根據(jù)的A2產(chǎn)量和B1的銷量知，A2只能供應(yīng)3個(gè)單位物資到B1，B1已經(jīng)滿足，劃去B1列，如下表4-15所示.

銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A2319284A3741059銷量3656第二十八頁，共八十四頁，編輯于2023年，星期一29（2）再從未劃去的元素中找最小元素，并從該元素開始確定運(yùn)輸關(guān)系，這里(A2,B3)處2最小，故從此元素開始，即A2優(yōu)先供應(yīng)B3物資，A2只剩1個(gè)單位物資，從而A2只能供應(yīng)1個(gè)單位物資到B3，A2物資已經(jīng)發(fā)完，劃去A2行，如下表4-16所示.

銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A23191284A3741059銷量3656第二十九頁，共八十四頁，編輯于2023年，星期一30（3）再從未劃去的元素中找最小元素，并從該元素開始確定運(yùn)輸關(guān)系，這里(A1,B3)處3最小，故從此元素開始，即A1優(yōu)先供應(yīng)B3物資，根據(jù)A1的產(chǎn)量和B3的銷量知A1供應(yīng)4個(gè)單位物資到B3，B3物資已經(jīng)滿足，劃去B3列，如下表所示.

銷地產(chǎn)地B1B2B3B4產(chǎn)量A131143107A23191284A3741059銷量3656第三十頁，共八十四頁，編輯于2023年，星期一31（4）再從未劃去的元素中找最小元素，并從該元素開始確定運(yùn)輸關(guān)系，這里(A3,B2)處4最小，故從此元素開始，即A3優(yōu)先供應(yīng)B2物資6個(gè)單位，B2物資已經(jīng)滿足，劃去B2列，如下表所示.

銷地產(chǎn)地B1B2B3B4產(chǎn)量A131143107A23191284A37641059銷量3656第三十一頁，共八十四頁，編輯于2023年，星期一32（5）再從未劃去的元素中找最小元素，并從該元素開始確定運(yùn)輸關(guān)系，這里(A3,B4)處5最小，故從此元素開始，即A3優(yōu)先供應(yīng)B4物資3個(gè)單位，A3物資已經(jīng)發(fā)完，劃去A3行，如下表4-17所示.

銷地產(chǎn)地B1B2B3B4產(chǎn)量A131143107A23191284A376410359銷量3656第三十二頁，共八十四頁，編輯于2023年，星期一33（6）最后在(A1,B4)處填3，即A1供應(yīng)B4物資3個(gè)單位，A1物資已經(jīng)發(fā)完，劃去A3行，B4物資全部滿足，劃去B4列，如下表所示.

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656第三十三頁，共八十四頁，編輯于2023年，星期一34（7）得到初始方案，如下表4-18所示.

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656總運(yùn)費(fèi)第三十四頁，共八十四頁，編輯于2023年，星期一353.差值法（伏格爾法）初看起來，最小元素法十分合理.事實(shí)上，最小元素法的缺點(diǎn)是：為了節(jié)省一處的費(fèi)用，有時(shí)造成其它處要多花幾倍的運(yùn)費(fèi)，這是因?yàn)橛袝r(shí)按某一最小單位運(yùn)價(jià)優(yōu)先安排物資運(yùn)輸時(shí)，卻可能導(dǎo)致不得不采用運(yùn)費(fèi)很高的其它點(diǎn)對，從而使整個(gè)運(yùn)輸費(fèi)用增加.伏格爾法考慮到，一個(gè)產(chǎn)地的產(chǎn)品假如不能按最小費(fèi)用就近供應(yīng)，就考慮次小費(fèi)用，這樣最小費(fèi)用和次小費(fèi)用就有一個(gè)差額，差額越大，說明不按最小費(fèi)用調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多，因而對差額最大處，就應(yīng)當(dāng)采用最小調(diào)運(yùn)方案.基于此，伏格爾法的步驟是：每次從當(dāng)前運(yùn)價(jià)表上，計(jì)算各行各列中最小費(fèi)用與次小費(fèi)用這兩個(gè)運(yùn)價(jià)的差值，優(yōu)先取最大差值的行或列中最小的單位運(yùn)價(jià)來確定運(yùn)輸關(guān)系，直到求出初始方案.第三十五頁，共八十四頁，編輯于2023年，星期一36

銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131131070A2192841A37410591銷量3656列差額2513我們?nèi)匀豢紤]表4-9所示的運(yùn)輸問題，伏格爾法確定初始基可行解的步驟如下：（1）先分別計(jì)算出各行和各列最小費(fèi)用與次小費(fèi)用的差額，稱為行差額和列差額，并將行差額和列差額填入該表的最右列和最下行，如下表4-19所示.第三十六頁，共八十四頁，編輯于2023年，星期一37

銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131131070A2192841A376410591銷量3656列差額2513（2）從行差額和列差額中選出最大者，選擇它所在的行或列中的最小費(fèi)用所在的格作為優(yōu)先的運(yùn)輸關(guān)系.在這里行差額與列差額最大值為5，故選擇5所在的列最小單位運(yùn)價(jià)4為優(yōu)先運(yùn)輸關(guān)系，即讓A3優(yōu)先供應(yīng)物資到B2，根據(jù)產(chǎn)、銷量知A3供應(yīng)6個(gè)單位物資到B2，此時(shí)B2列已滿足，劃去B2列，得下表4-20.第三十七頁，共八十四頁，編輯于2023年，星期一38

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

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311532107A23192184A376410359銷量3656總運(yùn)費(fèi)為第三十九頁，共八十四頁，編輯于2023年，星期一40從上述計(jì)算步驟可見，三種方法除了在確定供求關(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)行迭代第四十頁，共八十四頁，編輯于2023年，星期一41需要注意的是三種方法給出的初始方案都是運(yùn)輸問題的基可行解，這是因?yàn)椋海?）在產(chǎn)銷平衡表上，選擇表中某一元素以后，要比較產(chǎn)量和銷量，當(dāng)產(chǎn)大于銷，劃去該元素所在列；當(dāng)產(chǎn)小于銷，劃去該元素所在行，然后在未劃去的元素中繼續(xù)選另一元素.表中共有m行n列，總共可劃條m+n直線，但當(dāng)表中只剩一個(gè)元素時(shí)，同時(shí)劃去一行和一列.因而表中共填了m+n-1個(gè)數(shù)字，即給出了m+n-1個(gè)基變量的值.

注：選擇表中某一個(gè)元素后，有可能同時(shí)劃去一行和一列，這就出現(xiàn)退化，退化的處理我們在后文中講述.（2）這m+n-1個(gè)基變量對應(yīng)的系數(shù)列向量是線性獨(dú)立的.這是因?yàn)槿舯碇写_定了某一個(gè)基變量以后，它對應(yīng)的系數(shù)列向量，給定的值以后，將劃去第i行或第j列，即其后的系數(shù)列向量中不再出現(xiàn)或，因而不可能用其它向量的線性組合表示.所以這m+n-1個(gè)基變量對應(yīng)的系數(shù)列向量是線性獨(dú)立的.第四十一頁，共八十四頁，編輯于2023年，星期一424.2.2解的最優(yōu)性檢驗(yàn)及改進(jìn)

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

1.閉回路法閉回路方法是在初始調(diào)運(yùn)方案表中，從任意空格出發(fā)，沿著縱向或橫向行進(jìn)，遇到適當(dāng)填有數(shù)據(jù)的方格后90度轉(zhuǎn)彎，繼續(xù)行進(jìn)，總能回到原來空格，這個(gè)封閉的曲線稱為閉回路.可以證明每個(gè)空格都對應(yīng)著唯一的閉回路.第四十二頁，共八十四頁，編輯于2023年，星期一43

銷地產(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所示.第四十三頁，共八十四頁，編輯于2023年，星期一44

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656再如對空格(A1,B2)，它的閉回路如下表4-24所示.第四十四頁，共八十四頁，編輯于2023年，星期一45

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656同樣，空格(A3,B1)的閉回路如下表4-25所示.第四十五頁，共八十四頁，編輯于2023年，星期一46下面我們看用閉回路法計(jì)算非基變量（空格點(diǎn)）檢驗(yàn)數(shù)的計(jì)算方法.首先考慮表4-23的空格點(diǎn)(A1,B1),假設(shè)產(chǎn)地A1運(yùn)送1個(gè)單位的物資到銷地B1，為使運(yùn)入銷地B1物資的數(shù)量等于它的銷量，就應(yīng)當(dāng)將原來A2運(yùn)送到的B1物資數(shù)量減去1個(gè)單位，即將(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)?，從而得到一個(gè)新的運(yùn)輸方法.顯然這樣的調(diào)整將影響到空格(A1,B1)閉回路上的各個(gè)數(shù)據(jù).按照上述假設(shè)，如果由產(chǎn)地A1運(yùn)送1個(gè)單位的物資到銷地B1，由此引起的總費(fèi)用變化是，即總費(fèi)用增加1.按照檢驗(yàn)數(shù)的定義知它正是非基變量（即空格(A1,B1)）的檢驗(yàn)數(shù).同理按空格(A1,B2)的閉回路知它的檢驗(yàn)數(shù)為，空格(A3,B1)的檢驗(yàn)數(shù)為10.第四十六頁，共八十四頁，編輯于2023年，星期一47

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

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

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656奇數(shù)拐點(diǎn)處運(yùn)量的最小值為1,因而為了保持平衡，將奇數(shù)拐點(diǎn)處的運(yùn)量減去1，偶數(shù)拐點(diǎn)處的運(yùn)量加1，調(diào)整后的運(yùn)輸方案如下表4-28所示.第四十九頁，共八十四頁，編輯于2023年，星期一50

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311532107A23192184A376410359銷量3656調(diào)整以后，再計(jì)算各個(gè)空格的檢驗(yàn)數(shù)，如果所有的檢驗(yàn)數(shù)均大于等于零，則這個(gè)運(yùn)輸方案就是最優(yōu)解；如果還有某個(gè)空格的檢驗(yàn)數(shù)為負(fù)數(shù)，則再以這個(gè)空格為調(diào)入格，作相應(yīng)的基變換，直到所有的檢驗(yàn)數(shù)為非負(fù).上述表中得到的所有的檢驗(yàn)數(shù)為非負(fù)，因而此運(yùn)輸方案是最優(yōu)方案.第五十頁，共八十四頁，編輯于2023年，星期一512.位勢法

在閉回路法中，為了計(jì)算一個(gè)空格點(diǎn)處的檢驗(yàn)數(shù)，就要畫出該空格的閉回路，當(dāng)空格點(diǎn)較多時(shí)，計(jì)算很繁.位勢法是另一種計(jì)算每個(gè)空格檢驗(yàn)數(shù)的方法，這個(gè)方法比閉回路法更加簡潔.第五十一頁，共八十四頁，編輯于2023年，星期一52位勢法的基本思想是：

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

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

由于基變量的檢驗(yàn)數(shù)始終為0，因而對于基變量，始終有

，所以我們可以根據(jù)基變量對應(yīng)的單位運(yùn)輸費(fèi)用算出所有ui與vj的值，再根據(jù)ui與vj的值算出非基變量的檢驗(yàn)數(shù)。第五十二頁，共八十四頁，編輯于2023年，星期一53例如在表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.計(jì)算方程組是：第五十三頁，共八十四頁，編輯于2023年，星期一54

銷地產(chǎn)地B1B2B3B4uiA1311433100A2319128-1A37641035-5vj29310該方程組含6個(gè)方程和7個(gè)未知數(shù)，因而有一個(gè)未知數(shù)是自由變量，通常我們令u1=0，此時(shí)可得到所有ui(i=1,2,…m)和vj(j=1,2,…,n)的值，如下表4-29所示.第五十四頁，共八十四頁，編輯于2023年，星期一55根據(jù)ui和vj的值算出所有空格處（即非基變量）的檢驗(yàn)數(shù)，計(jì)算公式為cij-(ui+vj)，計(jì)算結(jié)果如下表4-30方括號數(shù)字所示，這和用閉回路法得到的檢驗(yàn)數(shù)結(jié)果一致.

銷地產(chǎn)地B1B2B3B4uiA1311433100[1][2]A2319128-1[1][-1]A37641035-5[10][12]vj29310因?yàn)闄z驗(yàn)數(shù)，故這個(gè)解不是最優(yōu)解，因此我們再根據(jù)閉回路法進(jìn)行調(diào)整，直至得出最優(yōu)解.第五十五頁，共八十四頁，編輯于2023年，星期一56表上作業(yè)法在計(jì)算中可能還會出現(xiàn)一些問題，這里我們需要說明.1.當(dāng)?shù)竭\(yùn)輸問題的最優(yōu)解時(shí)，如果有某個(gè)非基變量的檢驗(yàn)數(shù)等于零，則說明該運(yùn)輸問題有無窮多最優(yōu)解.2.退化

(1)當(dāng)確定供需關(guān)系時(shí)，如果某個(gè)產(chǎn)地的剩余產(chǎn)量等于某個(gè)銷地的需量，這時(shí)就要?jiǎng)澣ヒ恍泻鸵涣校藭r(shí)需要添加一個(gè)0，它的位置可在對應(yīng)劃去的那行或那列的任意處.(2)在用閉回路法調(diào)整時(shí)，如果閉回路奇數(shù)拐彎處具有兩個(gè)或兩個(gè)以上相等的最小值，此時(shí)經(jīng)調(diào)整后，得到退化解，這時(shí)有一個(gè)數(shù)字格必須填0，以表示它是基變量.第五十六頁，共八十四頁，編輯于2023年，星期一574.3產(chǎn)銷不平衡的運(yùn)輸問題

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

（4.5）

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

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

（4.6）

第五十八頁，共八十四頁，編輯于2023年，星期一59

銷地產(chǎn)地B1

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

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

批發(fā)用戶造紙廠B1B2B3B4產(chǎn)量A1312348A2112595A367159需求量4356第六十一頁，共八十四頁，編輯于2023年，星期一62解由于該問題中總產(chǎn)量為22，總銷量為18，因而該問題是總產(chǎn)量大于總銷量的產(chǎn)銷不平衡運(yùn)輸問題.按照模型（4.5）的分析知，增加一個(gè)假想銷地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所示第六十二頁，共八十四頁，編輯于2023年，星期一63用戶造紙廠B1B2B3B4B5產(chǎn)量A1431234408A2113259205A3675125209銷量435622-18=4在以上討論中，我們都假定物資由產(chǎn)地直接運(yùn)送到銷售目的地，不經(jīng)過中間轉(zhuǎn)運(yùn).在實(shí)際問題中，還會遇到將物資運(yùn)到某個(gè)中間轉(zhuǎn)運(yùn)站（包括產(chǎn)地、銷地或中間轉(zhuǎn)運(yùn)倉庫），然后再運(yùn)往銷售目的地的情況.有時(shí)經(jīng)轉(zhuǎn)運(yùn)比直接運(yùn)往目的地更為經(jīng)濟(jì)，在決定運(yùn)輸方案時(shí)有必要將轉(zhuǎn)運(yùn)也考慮進(jìn)去.當(dāng)然考慮轉(zhuǎn)運(yùn)將使問題變得復(fù)雜，有興趣的讀者可以參閱相關(guān)文獻(xiàn).第六十三頁，共八十四頁，編輯于2023年，星期一64

下面我們通過幾個(gè)例子介紹運(yùn)輸問題的一些實(shí)際應(yīng)用.例4

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

第六十四頁，共八十四頁，編輯于2023年，星期一65

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

使用者產(chǎn)地ⅠⅡⅢ產(chǎn)量124321563324使用量1046例5

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

銷地產(chǎn)地ⅠⅡⅢ產(chǎn)量112220214540323330銷量302020例6

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

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