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

1、關(guān)于最優(yōu)化理論運(yùn)輸問(wèn)題現(xiàn)在學(xué)習(xí)的是第一頁(yè)，共84頁(yè)2第四章 運(yùn)輸問(wèn)題4.1 運(yùn)輸問(wèn)題的數(shù)學(xué)模型運(yùn)輸問(wèn)題的數(shù)學(xué)模型 4.2 表上作業(yè)法表上作業(yè)法4.3 產(chǎn)銷不平衡的運(yùn)輸問(wèn)題產(chǎn)銷不平衡的運(yùn)輸問(wèn)題 4.4 運(yùn)輸問(wèn)題應(yīng)用舉例運(yùn)輸問(wèn)題應(yīng)用舉例現(xiàn)在學(xué)習(xí)的是第二頁(yè)，共84頁(yè)3n在經(jīng)濟(jì)建設(shè)中，經(jīng)常遇到大宗物資的調(diào)運(yùn)問(wèn)題，如煤、在經(jīng)濟(jì)建設(shè)中，經(jīng)常遇到大宗物資的調(diào)運(yùn)問(wèn)題，如煤、鋼材、糧食等鋼材、糧食等. 如果在我們考慮范圍之內(nèi)有若干個(gè)生產(chǎn)如果在我們考慮范圍之內(nèi)有若干個(gè)生產(chǎn)基地和若干消費(fèi)地點(diǎn)，根據(jù)已有的交通網(wǎng)絡(luò)，如何制定基地和若干消費(fèi)地點(diǎn)，根據(jù)已有的交通網(wǎng)絡(luò)，如何制定調(diào)運(yùn)方案，使總的運(yùn)費(fèi)達(dá)到最小，這就是運(yùn)輸問(wèn)題調(diào)運(yùn)

2、方案，使總的運(yùn)費(fèi)達(dá)到最小，這就是運(yùn)輸問(wèn)題.n運(yùn)輸問(wèn)題是特殊的線性規(guī)劃問(wèn)題，故可以用單純形法來(lái)運(yùn)輸問(wèn)題是特殊的線性規(guī)劃問(wèn)題，故可以用單純形法來(lái)求解，又因?yàn)樗哂刑厥庑?，因而它還具有比單純形法求解，又因?yàn)樗哂刑厥庑?，因而它還具有比單純形法更為簡(jiǎn)便的解法，這就是我們專門研究運(yùn)輸問(wèn)題的目的更為簡(jiǎn)便的解法，這就是我們專門研究運(yùn)輸問(wèn)題的目的.4.1 運(yùn)輸問(wèn)題的數(shù)學(xué)模型運(yùn)輸問(wèn)題的數(shù)學(xué)模型本節(jié)我們先引入運(yùn)輸問(wèn)題的數(shù)學(xué)模型，然后討論運(yùn)輸問(wèn)題數(shù)學(xué)模型的本節(jié)我們先引入運(yùn)輸問(wèn)題的數(shù)學(xué)模型，然后討論運(yùn)輸問(wèn)題數(shù)學(xué)模型的特點(diǎn)特點(diǎn). 現(xiàn)在學(xué)習(xí)的是第三頁(yè)，共84頁(yè)4例例1 假設(shè)有三家工廠，都將產(chǎn)品運(yùn)往三個(gè)不同的商店(如圖)，

3、每家工廠每周的生產(chǎn)能力和每個(gè)商店每周的需求量如表4-1和表4-2所示. 工廠1工廠3工廠2商店1商店3商店2表4-1表4-2 工廠工廠1 2 3供應(yīng)量（噸供應(yīng)量（噸/周）周）50 70 20商店商店1 2 3需求需求量（噸量（噸/周）周）50 60 304.1.1 運(yùn)輸問(wèn)題的數(shù)學(xué)模型運(yùn)輸問(wèn)題的數(shù)學(xué)模型 先通過(guò)一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明運(yùn)輸問(wèn)題及其數(shù)學(xué)模型.現(xiàn)在學(xué)習(xí)的是第四頁(yè)，共84頁(yè)5顯然，每周的供應(yīng)總量與需求總量是相等的，即產(chǎn)銷平衡，這可以用表4-3來(lái)表示，稱為產(chǎn)銷平衡表. 由于運(yùn)貨距離和運(yùn)貨公路的路況不同，各個(gè)工廠運(yùn)往各商店物資的單位運(yùn)輸費(fèi)用是不同的，單位費(fèi)用如表4-4所示，稱為單位運(yùn)價(jià)表. 表

4、4-3 產(chǎn)銷平衡表 單位：噸商店工廠123供應(yīng)量150270320需求量506030現(xiàn)在學(xué)習(xí)的是第五頁(yè)，共84頁(yè)6商店工廠123供應(yīng)量13235021058703131020需求量506030商店工廠12313232105831310表4-4 單位運(yùn)價(jià)表 單位：元/噸當(dāng)然，我們也可以將產(chǎn)銷平衡表和單位運(yùn)價(jià)表放在一個(gè)表中，如下表4-5所示.問(wèn)如何確定調(diào)運(yùn)方案，使總費(fèi)用達(dá)到最??？現(xiàn)在學(xué)習(xí)的是第六頁(yè)，共84頁(yè)7解解 模型建立模型建立 決策變量決策變量 用雙下標(biāo)決策變量用雙下標(biāo)決策變量X Xijij表示從第表示從第i i （i=1i=1，2 2，3 3）家工廠運(yùn)送到第）家工廠運(yùn)送到第j j（j=1j=

5、1，2 2，3 3）家商店產(chǎn)品的數(shù)量。）家商店產(chǎn)品的數(shù)量。 目標(biāo)函數(shù)目標(biāo)函數(shù) 利用單位運(yùn)價(jià)表和產(chǎn)銷平衡表中的數(shù)據(jù)，我們希望總的運(yùn)費(fèi)利用單位運(yùn)價(jià)表和產(chǎn)銷平衡表中的數(shù)據(jù)，我們希望總的運(yùn)費(fèi)達(dá)到最小，即達(dá)到最小，即Min Z = Min Z = 由工廠由工廠1 1運(yùn)出產(chǎn)品的總費(fèi)用運(yùn)出產(chǎn)品的總費(fèi)用( 3X( 3X1111+ 2X+ 2X1212+ 3X+ 3X1313) ) + +由工廠由工廠2 2運(yùn)出產(chǎn)品的總費(fèi)用運(yùn)出產(chǎn)品的總費(fèi)用(10X(10X2121+ 5X+ 5X2222+ 8X+ 8X2323) ) + +由工廠由工廠3 3運(yùn)出產(chǎn)品的總費(fèi)用運(yùn)出產(chǎn)品的總費(fèi)用( X( X3131+ 3X+ 3X32

6、32+10X+10X3333) )寫成表達(dá)式就是：寫成表達(dá)式就是： 現(xiàn)在學(xué)習(xí)的是第七頁(yè)，共84頁(yè)8 對(duì)工廠對(duì)工廠1 1必須有必須有 X X1111+X+X1212+X+X1313 = 50 = 50 對(duì)工廠對(duì)工廠2 2必須有必須有 X X2121+X+X2222+X+X2323 = 70 = 70 對(duì)工廠對(duì)工廠3 3必須有必須有 X X3131+X+X3232+X+X3333 = 20 = 20 對(duì)商店對(duì)商店1 1必須有必須有 X X1111+X+X2121+X+X3131 = 50 = 50 對(duì)商店對(duì)商店2 2必須有必須有 X X1212+X+X2222+X+X3232 = 60 = 60

7、對(duì)商店對(duì)商店3 3必須有必須有 X X1313+X+X2323+X+X3333 = 30 = 30約束條件約束條件主要是對(duì)工廠的產(chǎn)量約束和商店的銷量約束，由于主要是對(duì)工廠的產(chǎn)量約束和商店的銷量約束，由于產(chǎn)量與銷量相同，因而有：產(chǎn)量與銷量相同，因而有：現(xiàn)在學(xué)習(xí)的是第八頁(yè)，共84頁(yè)9 于是，解此問(wèn)題的線性最優(yōu)化模型為：于是，解此問(wèn)題的線性最優(yōu)化模型為：Min Z = 3XMin Z = 3X1111+ 2X+ 2X1212+ 3X+ 3X13 13 + 10X+ 10X2121+ 5X+ 5X2222+ 8X+ 8X2323+X+X3131+3X+3X3232+10X+10X3333 X X111

8、1+X+X1212+X+X13 13 = 50 = 50 X X2121+X+X2222+X+X23 23 = 70 = 70 X X3131+X+X3232+X+X33 33 = 20 = 20 X X1111+ X+ X2121+ X+ X3131 = 50 = 50 X X1212+ X+ X2222+ X+ X3232 = 60 = 60 X X1313+ X+ X2323+ X+ X33 33 = 30 = 30 X Xijij0 i=10 i=1，2 2，3 j=13 j=1，2 2，3 3 s. t.上述模型顯然是線性規(guī)劃模型，我們可以使用線性規(guī)劃的單純形法對(duì)它進(jìn)行求解. 但是，

9、當(dāng)用單純形法求解運(yùn)輸問(wèn)題時(shí)，先得給每個(gè)約束條件中引入一個(gè)人工變量，這樣模型的變量個(gè)數(shù)就會(huì)達(dá)到15個(gè)，求解是比較繁瑣的，因而有必要尋求更簡(jiǎn)便的解法.現(xiàn)在學(xué)習(xí)的是第九頁(yè)，共84頁(yè)10運(yùn)輸問(wè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，問(wèn)如何安排運(yùn)輸可使總運(yùn)費(fèi)最??？ 這是多個(gè)產(chǎn)地供應(yīng)多個(gè)銷地的單一物品運(yùn)輸問(wèn)題，我們用Xij表示從產(chǎn)地Ai到銷地Bj的運(yùn)量，為直觀起見，可以單獨(dú)將Xij列出得該問(wèn)題的運(yùn)輸表. 但我們也可以

10、將運(yùn)輸表和單位運(yùn)價(jià)表、產(chǎn)銷量放在一起，如下表4-6所示.為了說(shuō)明適于求解運(yùn)輸問(wèn)題的更好的解法，先看一下運(yùn)輸問(wèn)題的一般描述及模型的一般形式. 現(xiàn)在學(xué)習(xí)的是第十頁(yè)，共84頁(yè)11 銷地 產(chǎn)地B1 B2 Bn產(chǎn)量A1X11c11X12c12X1nc1na1A2X21c21X22c22X2nc2na2AmXm1cm1Xm2cm2Xmncmnam銷量b1b2bn表中每格元素Xij代表運(yùn)量，右上角元素 cij代表單位運(yùn)價(jià).現(xiàn)在學(xué)習(xí)的是第十一頁(yè)，共84頁(yè)12如果 ，就稱此運(yùn)輸問(wèn)題為非平衡運(yùn)輸問(wèn)題，包含產(chǎn)大于銷和銷大于產(chǎn)兩種情況，這我們將在第3節(jié)介紹。 下面我們只考慮產(chǎn)銷平衡問(wèn)題，產(chǎn)銷平衡運(yùn)輸問(wèn)題的一般模型為：

11、 ), 2 , 1;, 2 , 1(0), 2 , 1(), 2 , 1(.Min1111njmiXnjbXmiaXtsXcZijmijijnjiijminjijij在產(chǎn)銷平衡條件下，可知njjmiiba11（4.2） njjmiiba11其中約束條件右端常數(shù)ai 和bj滿足（4.2），在運(yùn)輸問(wèn)題（4.3）中，目標(biāo)函數(shù)要求運(yùn)輸總費(fèi)用最小；前m個(gè)約束條件的意義是：由某一產(chǎn)地運(yùn)往各個(gè)銷地的物資數(shù)量之和等于該產(chǎn)地的產(chǎn)量；中間n個(gè)約束條件的意義是：由各產(chǎn)地運(yùn)往某一銷地的物資數(shù)量之和等于該銷地的銷量；后mn個(gè)約束條件是變量的非負(fù)條件. （4.3） 現(xiàn)在學(xué)習(xí)的是第十二頁(yè)，共84頁(yè)134.1.2 運(yùn)輸問(wèn)題數(shù)

12、學(xué)模型的特點(diǎn)運(yùn)輸問(wèn)題數(shù)學(xué)模型的特點(diǎn) 對(duì)于產(chǎn)銷平衡運(yùn)輸問(wèn)題（4.3），將其約束條件加以整理，可知其系數(shù)矩陣具有下述形式： 行行nmxxxxxxxxxmnmmnn111111111111111111212222111211（4.4） 由此可知，產(chǎn)銷平衡運(yùn)輸問(wèn)題數(shù)學(xué)模型有下述特點(diǎn)：現(xiàn)在學(xué)習(xí)的是第十三頁(yè)，共84頁(yè)14（1）約束條件中決策變量的系數(shù)等于0或1.（2）所有約束條件都是等式.（3）約束條件的系數(shù)矩陣中每一列有兩個(gè)非零元素，對(duì)應(yīng)于變量Xij的系數(shù)列向量Pij，其分量除第i個(gè)和第m+j個(gè)等于1以外，其余的均為零，即Pij=ei+em+j. 這對(duì)應(yīng)于每一個(gè)變量在前m個(gè)約束方程中出現(xiàn)一次，在后n個(gè)約

13、束方程中也出現(xiàn)一次. （4）由于（4.2）成立，因而約束條件中m個(gè)約束方程并不是獨(dú)立的，實(shí)際上只有個(gè)m+n-1方程是獨(dú)立的，因而約束方程系數(shù)矩陣的秩為m+n-1.（5）運(yùn)輸問(wèn)題（4.3）總存在基可行解，下節(jié)我們將給出找基可行解的方法. （6）運(yùn)輸問(wèn)題存在有限最優(yōu)解這是由于對(duì)運(yùn)輸問(wèn)題（4.3），若令其變量則Xij就是該運(yùn)輸問(wèn)題的一個(gè)可行解，其中 是總產(chǎn)量；另一方面，（4.3）的目標(biāo)函數(shù)有下界，即目標(biāo)函數(shù)不會(huì)趨向于負(fù)無(wú)窮，從而運(yùn)輸問(wèn)題必存在有限最優(yōu)解. njmiQbaXjiji, 2 , 1;, 2 , 1,/Q現(xiàn)在學(xué)習(xí)的是第十四頁(yè)，共84頁(yè)15例例2 某種物品先存放在兩個(gè)倉(cāng)庫(kù)A1和A2中，再運(yùn)往

14、三個(gè)使用地B1， B2和 B3，產(chǎn)銷平衡表和單位運(yùn)價(jià)表如下表4-7所示，試建立使總運(yùn)費(fèi)最小的運(yùn)輸問(wèn)題數(shù)學(xué)模型. 使用地 倉(cāng)庫(kù)B1 B2 B3產(chǎn)量A134210A23534銷量356解：設(shè) 表示從Ai運(yùn)到Bj的物品數(shù)量，則由表中數(shù)據(jù)可知該問(wèn)題的數(shù)學(xué)模型為： )3 , 2 , 1; 2 , 1(jixji3 , 2 , 1; 2 , 1, 0653410.353243min231322122111232221131211232221131211jixxxxxxxxxxxxxtsxxxxxxZji現(xiàn)在學(xué)習(xí)的是第十五頁(yè)，共84頁(yè)16前面已經(jīng)指出，運(yùn)輸問(wèn)題是特殊的線性規(guī)劃問(wèn)題，可設(shè)想用單純形法進(jìn)行求解，

15、而單純形法的基本思路是：先找出某個(gè)基可行解，再進(jìn)行解的最優(yōu)性檢驗(yàn)，若它不是最優(yōu)解，就進(jìn)行迭代調(diào)整，得到新的更好的解，然后繼續(xù)驗(yàn)證和調(diào)整改進(jìn)，直至得到最優(yōu)解為止.為了按照上述思想求解運(yùn)輸問(wèn)題，要求每步得到的解都必須是基可行解，因而解必須滿足模型中所有約束條件，而且由運(yùn)輸問(wèn)題的特點(diǎn)（4）知基變量的個(gè)數(shù)在迭代過(guò)程中始終保持為m+n-1個(gè)，同時(shí)基變量對(duì)應(yīng)的約束方程組的系數(shù)列向量是線性無(wú)關(guān)的.在運(yùn)輸問(wèn)題的數(shù)學(xué)模型中，每個(gè)解就代表一個(gè)運(yùn)輸方案，運(yùn)輸問(wèn)題解的每一個(gè)分量，都唯一對(duì)應(yīng)其運(yùn)輸表中的一個(gè)格. 若X是運(yùn)輸問(wèn)題的一個(gè)基可行解，則將其基變量的值填入到運(yùn)輸表相應(yīng)的格處（含填數(shù)字0的格），非基變量對(duì)應(yīng)的格不填

16、數(shù)字. 現(xiàn)在學(xué)習(xí)的是第十六頁(yè)，共84頁(yè)17例如下表4-8表示例2的一個(gè)基可行解. 使用地 倉(cāng)庫(kù)B1 B2 B3供應(yīng)量A133146210A234534需求量356表4-8有4個(gè)填有數(shù)字的格，它們對(duì)應(yīng)4個(gè)基變量，兩個(gè)空格對(duì)應(yīng)2個(gè)非基變量. 可以驗(yàn)證，基可行解對(duì)應(yīng)的約束方程組的系數(shù)列向量線性無(wú)關(guān). 現(xiàn)在學(xué)習(xí)的是第十七頁(yè)，共84頁(yè)184.2 表上作業(yè)法表上作業(yè)法 由于運(yùn)輸問(wèn)題具有特殊形式，因而我們可以在運(yùn)輸表中直接對(duì)問(wèn)題求解，稱為表上作業(yè)法. 表上作業(yè)法是單純形法求解運(yùn)輸問(wèn)題時(shí)的簡(jiǎn)化方法，其實(shí)質(zhì)是單純形法，它的步驟可歸納為：(1) 找出初始基可行解，即在m行n列產(chǎn)銷平衡表上給出m+n-1個(gè)數(shù)字格.(

17、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). 下面我們依次來(lái)看. 現(xiàn)在學(xué)習(xí)的是第十八頁(yè)，共84頁(yè)194.2.1 確定初始基可行解確定初始基可行解 我們以一個(gè)例子來(lái)說(shuō)明找初始基可行解的方法. 下表4-9表示某個(gè)運(yùn)輸問(wèn)題的產(chǎn)銷平衡表和單位運(yùn)價(jià)表(二表合一).一般來(lái)說(shuō)，找運(yùn)輸問(wèn)題的初始基可行解主要有三種方法，即西北角法、最

18、小元素法和差值法（也叫伏格爾法），下面我們用上表4-9依次來(lái)說(shuō)明. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量3656現(xiàn)在學(xué)習(xí)的是第十九頁(yè)，共84頁(yè)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現(xiàn)在學(xué)習(xí)的是第二十頁(yè)，共84頁(yè)21（2）向a1,b1中較大數(shù)方向移動(dòng)一格（或向右，或向下），這里是向右移動(dòng)

19、一格，移動(dòng)到(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現(xiàn)在學(xué)習(xí)的是第二十一頁(yè)，共84頁(yè)22（3）繼續(xù)按照上述步驟進(jìn)行，可知A2向B2運(yùn)送2個(gè)單位物資，此時(shí)B2的物資已經(jīng)滿足，劃去B2列. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A2129284A3741059銷量3656現(xiàn)在學(xué)習(xí)的是第二十二頁(yè)，共84頁(yè)23（4）繼續(xù)按照上述步驟進(jìn)行. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A

20、21292284A3741059銷量3656現(xiàn)在學(xué)習(xí)的是第二十三頁(yè)，共84頁(yè)24（5）繼續(xù)進(jìn)行. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A21292284A37431059銷量3656現(xiàn)在學(xué)習(xí)的是第二十四頁(yè)，共84頁(yè)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現(xiàn)在學(xué)習(xí)的是第二十五頁(yè)，共84頁(yè)26（7）得到初始方案，如下表4-14所示. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A133411310

21、7A21292284A374310659銷量3656總運(yùn)費(fèi) 13565310222941133Z現(xiàn)在學(xué)習(xí)的是第二十六頁(yè)，共84頁(yè)272. 最小元素法用西北角法很容易得到初始基可行解，但得到的解往往離最優(yōu)解相差甚遠(yuǎn). 為了得到較好的初始基可行解，我們通常希望就近供應(yīng)，即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定供銷關(guān)系，然后次小，一直到給出初始基可行解為止，這種方法稱為最小元素法. 我們?nèi)砸员?-9所示的運(yùn)輸問(wèn)題來(lái)說(shuō)明最小元素法. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量3656現(xiàn)在學(xué)習(xí)的是第二十七頁(yè)，共84頁(yè)28（1）從表中最小單位運(yùn)價(jià)開始確定運(yùn)輸方案，這里(A2

22、,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現(xiàn)在學(xué)習(xí)的是第二十八頁(yè)，共84頁(yè)29（2）再?gòu)奈磩澣サ脑刂姓易钚≡?，并從該元素開始確定運(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)量A13113107A23191284A374

23、1059銷量3656現(xiàn)在學(xué)習(xí)的是第二十九頁(yè)，共84頁(yè)30（3）再?gòu)奈磩澣サ脑刂姓易钚≡?，并從該元素開始確定運(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現(xiàn)在學(xué)習(xí)的是第三十頁(yè)，共84頁(yè)31（4）再?gòu)奈磩澣サ脑刂姓易钚≡兀脑撛亻_始確定運(yùn)輸關(guān)系，這里(A3,B2)處4最小，故從此元素開始，即A3優(yōu)先供應(yīng)B2物資6個(gè)單位，B2物資已經(jīng)滿足，劃去B2列，如下表所示.

24、銷地產(chǎn)地B1B2B3B4產(chǎn)量A131143107A23191284A37641059銷量3656現(xiàn)在學(xué)習(xí)的是第三十一頁(yè)，共84頁(yè)32（5）再?gòu)奈磩澣サ脑刂姓易钚≡?，并從該元素開始確定運(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現(xiàn)在學(xué)習(xí)的是第三十二頁(yè)，共84頁(yè)33（6）最后在(A1,B4)處填3，即A1供應(yīng)B4物資3個(gè)單位，A1物資已經(jīng)發(fā)完，劃去A3行， B4物資全部滿足，劃去B4列，如下表所示. 銷地

25、產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656現(xiàn)在學(xué)習(xí)的是第三十三頁(yè)，共84頁(yè)34（7）得到初始方案，如下表4-18所示. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656總運(yùn)費(fèi) 863564123131043Z現(xiàn)在學(xué)習(xí)的是第三十四頁(yè)，共84頁(yè)353. 差值法（伏格爾法）初看起來(lái)，最小元素法十分合理. 事實(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)對(duì)，從而使整個(gè)運(yùn)輸費(fèi)用增加.

26、 伏格爾法考慮到，一個(gè)產(chǎn)地的產(chǎn)品假如不能按最小費(fèi)用就近供應(yīng)，就考慮次小費(fèi)用，這樣最小費(fèi)用和次小費(fèi)用就有一個(gè)差額，差額越大，說(shuō)明不按最小費(fèi)用調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加越多，因而對(duì)差額最大處，就應(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à)來(lái)確定運(yùn)輸關(guān)系，直到求出初始方案.現(xiàn)在學(xué)習(xí)的是第三十五頁(yè)，共84頁(yè)36 銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131131070A2192841A37410591銷量3656列差額2513我們?nèi)匀豢紤]表4-9所示的運(yùn)輸問(wèn)題，伏格爾法確定初始基可行解的步驟如下： （1

27、）先分別計(jì)算出各行和各列最小費(fèi)用與次小費(fèi)用的差額，稱為行差額和列差額，并將行差額和列差額填入該表的最右列和最下行，如下表4-19所示.現(xiàn)在學(xué)習(xí)的是第三十六頁(yè)，共84頁(yè)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. 現(xiàn)在學(xué)習(xí)的是第三十七頁(yè)

28、，共84頁(yè)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所示. 現(xiàn)在學(xué)習(xí)的是第三十八頁(yè)，共84頁(yè)39（4）繼續(xù)計(jì)算剩余元素的行差額和列差額，并按照上述步驟確定運(yùn)輸關(guān)系，經(jīng)過(guò)若干步以后，最后填2到(A1,B4)

29、格，A1和B4的供應(yīng)量和需求量都得到滿足，此時(shí)同時(shí)劃去A1行和B4列，可得初始方案 ，其余變量為0，如下表4-22所示. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311532107A23192184A376410359銷量36563, 6, 1, 3, 2, 5343224211413xxxxxx總運(yùn)費(fèi)為 853564183121053Z現(xiàn)在學(xué)習(xí)的是第三十九頁(yè)，共84頁(yè)40從上述計(jì)算步驟可見，三種方法除了在確定供求關(guān)系的原則不同外，其余步驟是相同的. 表4-9所示的運(yùn)輸問(wèn)題用三種方法得到的初始方案和總運(yùn)費(fèi)分別是：西北角法得到的初始方案是總運(yùn)費(fèi)為135；最小元素法得到初始方案為總運(yùn)費(fèi)是86；差值法的初始

30、方案是總運(yùn)費(fèi)85. 比較三種方法給出的初始基可行解，伏格爾法給出的解的目標(biāo)函數(shù)值最小，最小元素法次之，西北角法給出的解的目標(biāo)函數(shù)值最大. 一般來(lái)說(shuō)，伏格爾法確定的初始基可行解更接近最優(yōu)解，常用來(lái)作為運(yùn)輸問(wèn)題的初始基可行解進(jìn)行迭代 6, 6, 2, 2, 4, 3343323221211xxxxxx3, 6, 1, 3, 3, 4343223211413xxxxxx3, 6, 1, 3, 2, 5343224211413xxxxxx現(xiàn)在學(xué)習(xí)的是第四十頁(yè)，共84頁(yè)41需要注意的是三種方法給出的初始方案都是運(yùn)輸問(wèn)題的基可行解，這是因?yàn)椋海?）在產(chǎn)銷平衡表上，選擇表中某一元素以后，要比較產(chǎn)量和銷量，當(dāng)

31、產(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)退化，退化的處理我們?cè)诤笪闹兄v述.（2）這m+n-1個(gè)基變量對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的. 這是因?yàn)槿舯碇写_定了某一個(gè)基變量 以后，它對(duì)應(yīng)的系數(shù)列向量 ，給定 的值以后，將劃去第i行或第j列，即其后的系數(shù)列向量中不再出現(xiàn) 或 ，因而 不可能用其它向量的線性組合表示. 所以這m+n-1個(gè)基變量對(duì)

32、應(yīng)的系數(shù)列向量是線性獨(dú)立的. jixjmijieePiejmejiPjix現(xiàn)在學(xué)習(xí)的是第四十一頁(yè)，共84頁(yè)424.2.2解的最優(yōu)性檢驗(yàn)及改進(jìn)解的最優(yōu)性檢驗(yàn)及改進(jìn) 前面三種方法可以很容易找出運(yùn)輸問(wèn)題的初始基可行解，但初始基可行解未必是最優(yōu)解.按照表上作業(yè)法的步驟，給出初始基可行解后，還要計(jì)算各非基變量的檢驗(yàn)數(shù)，即在表上計(jì)算各空格的檢驗(yàn)數(shù)，以判別基可行解是否達(dá)到最優(yōu). 由于運(yùn)輸問(wèn)題的目標(biāo)函數(shù)是要求實(shí)現(xiàn)最小化，因而所有的檢驗(yàn)數(shù)大于等于零時(shí)基可行解為最優(yōu)解. 判別初始基可行解是否為最優(yōu)解一般有兩種常用方法：閉回路法和位勢(shì)法，下面我們依次來(lái)介紹. 1. 閉回路法閉回路方法是在初始調(diào)運(yùn)方案表中，從任意空格

33、出發(fā)，沿著縱向或橫向行進(jìn)，遇到適當(dāng)填有數(shù)據(jù)的方格后90度轉(zhuǎn)彎，繼續(xù)行進(jìn)，總能回到原來(lái)空格，這個(gè)封閉的曲線稱為閉回路. 可以證明每個(gè)空格都對(duì)應(yīng)著唯一的閉回路. 現(xiàn)在學(xué)習(xí)的是第四十二頁(yè)，共84頁(yè)43 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656現(xiàn)在學(xué)習(xí)的是第四十三頁(yè)，共84頁(yè)44 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656現(xiàn)在學(xué)習(xí)的是第四十四頁(yè)，共84頁(yè)45 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656現(xiàn)在學(xué)習(xí)的是第四十五頁(yè)，共8

34、4頁(yè)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)將原來(lái)A2運(yùn)送到的B1物資數(shù)量減去1個(gè)單位，即將(A2,B1)格的3變?yōu)?；另一方面，為使運(yùn)出產(chǎn)地A2物資的數(shù)量等于它的產(chǎn)量，就應(yīng)當(dāng)將原來(lái)(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)用增加

35、1. 按照檢驗(yàn)數(shù)的定義知它正是非基變量 （即空格(A1,B1)）的檢驗(yàn)數(shù). 同理按空格(A1,B2)的閉回路知它的檢驗(yàn)數(shù)為 ，空格(A3,B1)的檢驗(yàn)數(shù)為10. 1123321231311cccc11x245101132341412cccc現(xiàn)在學(xué)習(xí)的是第四十六頁(yè)，共84頁(yè)47 銷地產(chǎn)地B1B2B3B4產(chǎn)量A131143310712A231912841-1A3764103591012銷量3656 現(xiàn)在學(xué)習(xí)的是第四十七頁(yè)，共84頁(yè)48由于運(yùn)輸問(wèn)題的目標(biāo)函數(shù)是要求實(shí)現(xiàn)最小化，因而對(duì)該問(wèn)題的某個(gè)基可行解，如果所有空格的檢驗(yàn)數(shù)中沒(méi)有負(fù)值，則該基可行解就是最優(yōu)解；如果某個(gè)空格處出現(xiàn)負(fù)檢驗(yàn)數(shù)，表明調(diào)運(yùn)方案不

36、是最優(yōu)解，這時(shí)就要進(jìn)行調(diào)解. 和單純形法類似，當(dāng)有兩個(gè)和兩個(gè)以上空格的檢驗(yàn)數(shù)為負(fù)時(shí)，一般選其中最小的負(fù)檢驗(yàn)數(shù)，以它對(duì)應(yīng)的空格作為調(diào)入格，即該空格對(duì)應(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ù)，因而它對(duì)應(yīng)的變量 為進(jìn)基變量，它的閉回路如表4-27所示.24x現(xiàn)在學(xué)習(xí)的是第四十八頁(yè)，共84頁(yè)49 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656奇數(shù)拐點(diǎn)處運(yùn)

37、量的最小值為1, 因而為了保持平衡，將奇數(shù)拐點(diǎn)處的運(yùn)量減去1，偶數(shù)拐點(diǎn)處的運(yùn)量加1，調(diào)整后的運(yùn)輸方案如下表4-28所示. 現(xiàn)在學(xué)習(xí)的是第四十九頁(yè)，共84頁(yè)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)方案. 現(xiàn)在學(xué)習(xí)的是第五十頁(yè)，共84頁(yè)512. 位勢(shì)法位勢(shì)法 在閉回路法中，為了計(jì)算一個(gè)空格點(diǎn)處的

38、檢驗(yàn)數(shù)，就要畫出該空格的閉回路，當(dāng)空格點(diǎn)較多時(shí)，計(jì)算很繁. 位勢(shì)法是另一種計(jì)算每個(gè)空格檢驗(yàn)數(shù)的方法，這個(gè)方法比閉回路法更加簡(jiǎn)潔.現(xiàn)在學(xué)習(xí)的是第五十一頁(yè)，共84頁(yè)52位勢(shì)法的基本思想是： 設(shè)一組新的變量ui和vj(i=1,2,m;j=1,2,n)是對(duì)應(yīng)運(yùn)輸問(wèn)題的m+n個(gè)約束條件的對(duì)偶變量，B是原問(wèn)題的初始基矩陣，則由單純形法知而每個(gè)決策變量 的系數(shù)向量 ，所以有 ，于是檢驗(yàn)數(shù) 由于基變量的檢驗(yàn)數(shù)始終為0，因而對(duì)于基變量，始終有 ，所以我們可以根據(jù)基變量對(duì)應(yīng)的單位運(yùn)輸費(fèi)用算出所有ui與vj的值，再根據(jù)ui與vj的值算出非基變量的檢驗(yàn)數(shù)。),(21211nmBvvvuuuBCjmiijeePjiij

39、BvuPBC1)(1jiijijBijijvucPBCcBjivucjiij,0)(jix現(xiàn)在學(xué)習(xí)的是第五十二頁(yè)，共84頁(yè)53例如在表4-9所表示的運(yùn)輸問(wèn)題中，用最小元素法得到的初始調(diào)運(yùn)方案如下表所示. 銷地產(chǎn)地B1B2B3B4uiA131143310u1A2319128u2A37641035u3vjv1v2v3v4在此調(diào)運(yùn)方案中，我們可以根據(jù)基變量對(duì)應(yīng)的單位運(yùn)輸費(fèi)用cij算出ui和vj .計(jì)算方程組是： . 5; 4; 2; 1;10; 3432332124131vuvuvuvuvuvu現(xiàn)在學(xué)習(xí)的是第五十三頁(yè)，共84頁(yè)54 銷地產(chǎn)地B1B2B3B4uiA1311433100A2319128-

40、1A37641035-5vj29310該方程組含6個(gè)方程和7個(gè)未知數(shù)，因而有一個(gè)未知數(shù)是自由變量，通常我們令u1=0，此時(shí)可得到所有ui(i=1,2,m)和vj(j=1,2,n)的值，如下表4-29所示. 現(xiàn)在學(xué)習(xí)的是第五十四頁(yè)，共84頁(yè)55根據(jù)ui和vj的值算出所有空格處（即非基變量）的檢驗(yàn)數(shù)，計(jì)算公式為cij-(ui+vj)，計(jì)算結(jié)果如下表4-30方括號(hào)數(shù)字所示，這和用閉回路法得到的檢驗(yàn)數(shù)結(jié)果一致. 銷地產(chǎn)地B1B2B3B4uiA131143310012A2319128-11-1A37641035-51012vj29310因?yàn)闄z驗(yàn)數(shù) ，故這個(gè)解不是最優(yōu)解，因此我們?cè)俑鶕?jù)閉回路法進(jìn)行調(diào)整，直

41、至得出最優(yōu)解. 0124現(xiàn)在學(xué)習(xí)的是第五十五頁(yè)，共84頁(yè)56表上作業(yè)法在計(jì)算中可能還會(huì)出現(xiàn)一些問(wèn)題，這里我們需要說(shuō)明.1. 當(dāng)?shù)竭\(yùn)輸問(wèn)題的最優(yōu)解時(shí)，如果有某個(gè)非基變量的檢驗(yàn)數(shù)等于零，則說(shuō)明該運(yùn)輸問(wèn)題有無(wú)窮多最優(yōu)解.2. 退化 (1) 當(dāng)確定供需關(guān)系時(shí)，如果某個(gè)產(chǎn)地的剩余產(chǎn)量等于某個(gè)銷地的需量，這時(shí)就要?jiǎng)澣ヒ恍泻鸵涣?，此時(shí)需要添加一個(gè)0，它的位置可在對(duì)應(yīng)劃去的那行或那列的任意處. (2) 在用閉回路法調(diào)整時(shí)，如果閉回路奇數(shù)拐彎處具有兩個(gè)或兩個(gè)以上相等的最小值，此時(shí)經(jīng)調(diào)整后，得到退化解，這時(shí)有一個(gè)數(shù)字格必須填0，以表示它是基變量. 現(xiàn)在學(xué)習(xí)的是第五十六頁(yè)，共84頁(yè)574.3產(chǎn)銷不平衡的運(yùn)輸問(wèn)題

42、產(chǎn)銷不平衡的運(yùn)輸問(wèn)題 上一節(jié)講到運(yùn)輸問(wèn)題的表上作業(yè)法，是以總產(chǎn)量等于總銷量（即產(chǎn)銷平衡）為前提的. 實(shí)際上，在很多運(yùn)輸問(wèn)題中，總產(chǎn)量并不等于總銷量. 為了使用表上作業(yè)法求解，我們可以將產(chǎn)銷不平衡的運(yùn)輸問(wèn)題轉(zhuǎn)化為產(chǎn)銷平衡運(yùn)輸問(wèn)題.如果總產(chǎn)量大于總銷量，即njjmiiba11這時(shí)運(yùn)輸問(wèn)題的數(shù)學(xué)模型為： ), 2 , 1;, 2 , 1(. 0), 2 , 1(,), 2 , 1(,.min1111njmixnjbxmiaxtsxcZjimijjinjijiminjjiji（4.5） 現(xiàn)在學(xué)習(xí)的是第五十七頁(yè)，共84頁(yè)58由于總產(chǎn)量大于總銷量，因而要考慮多余物資就地貯存的問(wèn)題. 為借助產(chǎn)銷平衡運(yùn)輸問(wèn)題

43、的表上作業(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à) . 因此假想后原問(wèn)題的最優(yōu)總費(fèi)用與假想之前的最優(yōu)總費(fèi)用是一致的. 由于總產(chǎn)量剩余為使產(chǎn)銷平衡，可假設(shè)銷地Bn+1的銷量此時(shí)模型（4.5）可以變?yōu)椋?1, nixmicni, 2 , 1, 01, njjmiiba11njjmiinbab111) 1, 2 , 1;, 2 , 1(. 0) 1, 2 , 1(,), 2 , 1(,.min111111njmixnjbxmiaxtsxcZjimijjinjijiminjjiji（4.6

44、） 現(xiàn)在學(xué)習(xí)的是第五十八頁(yè)，共84頁(yè)59 銷地 產(chǎn)地B1 B2 BnBn+1產(chǎn)量A1X11c11X12c12X1nc1nX1，n+10a1A2X21c21X22c22X2nc2nX2，n+10a2AmXm1cm1Xm2cm2XmncmnXm，n+10am銷量b1b2bn可以看出，模型（4.6）是有m個(gè)產(chǎn)地，n+1個(gè)銷地的產(chǎn)銷平衡運(yùn)輸問(wèn)題，因而通過(guò)假想銷地，可將產(chǎn)大于銷的運(yùn)輸問(wèn)題轉(zhuǎn)化為產(chǎn)銷平衡運(yùn)輸問(wèn)題. 和模型（4.6）對(duì)應(yīng)的運(yùn)輸表如下表所示. njjmiiba11現(xiàn)在學(xué)習(xí)的是第五十九頁(yè)，共84頁(yè)60如果總銷量大于總產(chǎn)量，即可仿照產(chǎn)大于銷的操作過(guò)程，增加一個(gè)假想的產(chǎn)地Am+1，它的產(chǎn)量為由于這個(gè)

45、假想的產(chǎn)地并不存在，求出的由它發(fā)往各個(gè)銷地的物資數(shù)量 實(shí)際上是各銷地所需物資的欠缺額，這部分物資的運(yùn)輸并未發(fā)生，因而單位運(yùn)價(jià) . 這樣也可以將原問(wèn)題化為產(chǎn)銷平衡運(yùn)輸問(wèn)題.miinjjab11miinjjmaba111), 2 , 1(, 1njxjm), 2 , 1(0, 1njcjm現(xiàn)在學(xué)習(xí)的是第六十頁(yè)，共84頁(yè)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

46、需求量4356現(xiàn)在學(xué)習(xí)的是第六十一頁(yè)，共84頁(yè)62解解 由于該問(wèn)題中總產(chǎn)量為22，總銷量為18，因而該問(wèn)題是總產(chǎn)量大于總銷量的產(chǎn)銷不平衡運(yùn)輸問(wèn)題. 按照模型（4.5）的分析知，增加一個(gè)假想銷地B5，其需求量為22-18=4，可將該問(wèn)題表示的運(yùn)輸問(wèn)題轉(zhuǎn)化為下表4-33所示的產(chǎn)銷平衡運(yùn)輸問(wèn)題. 用戶造紙廠B1B2B3B4B5產(chǎn)量A13123408A21125905A3671509需求量435622-18=4根據(jù)表上作業(yè)法，可得該問(wèn)題的最優(yōu)運(yùn)輸方案如下表4-34所示 現(xiàn)在學(xué)習(xí)的是第六十二頁(yè)，共84頁(yè)63用戶造紙廠B1B2B3B4B5產(chǎn)量A1431234408A2113259205A367512520

47、9銷量435622-18=4在以上討論中，我們都假定物資由產(chǎn)地直接運(yùn)送到銷售目的地，不經(jīng)過(guò)中間轉(zhuǎn)運(yùn). 在實(shí)際問(wèn)題中，還會(huì)遇到將物資運(yùn)到某個(gè)中間轉(zhuǎn)運(yùn)站（包括產(chǎn)地、銷地或中間轉(zhuǎn)運(yùn)倉(cāng)庫(kù)），然后再運(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)將使問(wèn)題變得復(fù)雜，有興趣的讀者可以參閱相關(guān)文獻(xiàn). 現(xiàn)在學(xué)習(xí)的是第六十三頁(yè)，共84頁(yè)64 下面我們通過(guò)幾個(gè)例子介紹運(yùn)輸問(wèn)題的一些實(shí)際應(yīng)用.例例4 設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥，假定等量的化肥在這些地區(qū)試用效果相同. 各化肥廠年產(chǎn)量、各地區(qū)年需求量（單位：萬(wàn)噸）及從各化肥廠到各地區(qū)運(yùn)送單位化肥

48、的單位運(yùn)價(jià)（單位：萬(wàn)元/萬(wàn)噸）如表4-35所示，試給出總運(yùn)費(fèi)最小的化肥調(diào)撥方案. 4.4運(yùn)輸問(wèn)題應(yīng)用舉例運(yùn)輸問(wèn)題應(yīng)用舉例 現(xiàn)在學(xué)習(xí)的是第六十四頁(yè)，共84頁(yè)65 需求地區(qū)化肥廠產(chǎn)量1161322175021413191560319202350最低需求最高需求3050707003010不限解解 這是一個(gè)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題，總產(chǎn)量為160萬(wàn)噸，四個(gè)地區(qū)的最低需求為110萬(wàn)噸，最高需求不限，但根據(jù)現(xiàn)有產(chǎn)量，第個(gè)地區(qū)每年最多能分配到60萬(wàn)噸，因而最高需求為210萬(wàn)噸，大于總產(chǎn)量. 為了求得平衡，在產(chǎn)銷表中增加一個(gè)假想的化肥廠4，其年產(chǎn)量為50萬(wàn)噸. 現(xiàn)在學(xué)習(xí)的是第六十五頁(yè)，共84頁(yè)66各地區(qū)的需求量包

49、含最低需求和額外需求兩部分. 如地區(qū)，其中30萬(wàn)噸是最低需求，故不能由假想化肥廠供給，因而令假想化肥廠4到地區(qū)的單位運(yùn)價(jià)為M（M為任意大的數(shù)），而額外需求20萬(wàn)噸對(duì)地區(qū)來(lái)說(shuō)可以滿足，也可以不滿足，因此額外需求可以由假想化肥廠4供給，而且相應(yīng)的運(yùn)價(jià)為0. 事實(shí)上，對(duì)凡是需求分兩種情況的地區(qū)，我們按照兩個(gè)地區(qū)看待，這樣可將原問(wèn)題轉(zhuǎn)化為產(chǎn)銷平衡運(yùn)輸問(wèn)題，其產(chǎn)銷平衡表與單位運(yùn)價(jià)表如下表4-36所示. 現(xiàn)在學(xué)習(xí)的是第六十六頁(yè)，共84頁(yè)67需求地區(qū)化肥廠產(chǎn)量116161322171750214141319151560319192023MM504M0M0M050需求量302070301050根據(jù)表上作業(yè)法進(jìn)

50、行計(jì)算，可以求得最優(yōu)方案如下表4-37所示. 現(xiàn)在學(xué)習(xí)的是第六十七頁(yè)，共84頁(yè)68需求地區(qū)化肥廠產(chǎn)量1161650132217175021414201319101530156033019201902023MM504M0M300M20050需求量302070301050從表4-37可以看出，地區(qū)滿足最高需求量50萬(wàn)噸，地區(qū)沒(méi)有接收到任何物資，只滿足最低需求0，而地區(qū)滿足了40萬(wàn)噸現(xiàn)在學(xué)習(xí)的是第六十八頁(yè)，共84頁(yè)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所示. 由于銷售需要

51、及客觀條件的限制，產(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)輸問(wèn)題的最優(yōu)調(diào)運(yùn)方案. 43a72a現(xiàn)在學(xué)習(xí)的是第六十九頁(yè)，共84頁(yè)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的方法，可將原問(wèn)題表示成下表4-39所示的產(chǎn)銷平衡運(yùn)輸問(wèn)題.由表4-39求解該產(chǎn)銷平衡運(yùn)輸問(wèn)題解的過(guò)程及結(jié)果請(qǐng)讀者自己完成. 現(xiàn)在學(xué)習(xí)的是第七十頁(yè)，共84頁(yè)

52、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)地有物資沒(méi)有運(yùn)出，就發(fā)生存儲(chǔ)費(fèi)用，假設(shè)三個(gè)產(chǎn)地單位物資存儲(chǔ)費(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)輸方案.現(xiàn)在學(xué)習(xí)的是第七十一頁(yè)，共84頁(yè)72解解 這是一個(gè)有存儲(chǔ)形式的產(chǎn)銷不平衡運(yùn)輸問(wèn)題.為使問(wèn)題化為無(wú)存儲(chǔ)費(fèi)用的產(chǎn)銷平衡運(yùn)輸問(wèn)題，可將產(chǎn)地1,2,3設(shè)想為三個(gè)銷地,，考慮到物資存儲(chǔ)的費(fèi)用，可將單位存儲(chǔ)費(fèi)按單位運(yùn)價(jià)來(lái)表示. 如產(chǎn)地

53、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至少存儲(chǔ)5個(gè)單位物資，即銷地的需求量至少為5個(gè)單位，同理銷地需求量至多為2個(gè)單位，為保持運(yùn)輸平衡，銷地的需求量是015之間使產(chǎn)銷平衡的值，因而原問(wèn)題轉(zhuǎn)化為下表4-41所示的產(chǎn)銷平衡運(yùn)輸問(wèn)題.現(xiàn)在學(xué)習(xí)的是第七十二頁(yè)，共84頁(yè)73銷地產(chǎn)地產(chǎn)量11224MM202145M4M403233MM330銷量30202001552表4-41現(xiàn)在學(xué)習(xí)的是第七十三頁(yè)，共84頁(yè)74銷地產(chǎn)地產(chǎn)量181212204MM20222145M184M

54、403220383MM2330銷量30202001552通過(guò)表上作業(yè)法可得該問(wèn)題的最優(yōu)方案如下表4-42所示，總費(fèi)用為216. 現(xiàn)在學(xué)習(xí)的是第七十四頁(yè)，共84頁(yè)75例例7 某工廠根據(jù)合同，要在下一年每個(gè)季度末向銷售公司提供某種產(chǎn)品，該工廠的生產(chǎn)能力、生產(chǎn)成本以及銷售公司的需求量如下4-43表所示季度生產(chǎn)能力 （噸）生產(chǎn)成本 （萬(wàn)元/噸）需求量（噸）123430402010151415.314.820203010jajjd若當(dāng)季生產(chǎn)的產(chǎn)品過(guò)多，就要進(jìn)行儲(chǔ)存，已知每季度儲(chǔ)存每噸產(chǎn)品需0.2萬(wàn)元，試給出該廠在完成合同的情況下的最佳生產(chǎn)方案，使全年的生產(chǎn)費(fèi)用最低.我們已經(jīng)知道，運(yùn)輸問(wèn)題是線性規(guī)劃問(wèn)題的特殊形式，由于在變量個(gè)數(shù)相等的情況下，運(yùn)輸問(wèn)題表上作業(yè)法的計(jì)算遠(yuǎn)比單純形法簡(jiǎn)單得多，所以在解決實(shí)際問(wèn)題時(shí)，人們常常盡可能將某些線性規(guī)劃問(wèn)題轉(zhuǎn)化為運(yùn)輸問(wèn)題的數(shù)學(xué)模型. 下面我們看一個(gè)具體例子. 現(xiàn)在學(xué)習(xí)的是第七十五頁(yè)，共84頁(yè)76解解 這個(gè)問(wèn)題在第二章例15解法2中已給出了線性規(guī)劃模型，設(shè)第i季度生產(chǎn)而用于第j季度交貨的產(chǎn)品數(shù)量為 噸，則原問(wèn)題的數(shù)學(xué)模型為：ijx在這里，我們可以將其化為產(chǎn)銷平衡運(yùn)輸問(wèn)題，從而簡(jiǎn)化