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

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

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

3、每家工廠每周的生產(chǎn)能力和每個商店每周的需求量如表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 運輸問題的數(shù)學(xué)模型運輸問題的數(shù)學(xué)模型 先通過一個簡單的例子來說明運輸問題及其數(shù)學(xué)模型.現(xiàn)在學(xué)習(xí)的是第四頁，共84頁5顯然，每周的供應(yīng)總量與需求總量是相等的，即產(chǎn)銷平衡，這可以用表4-3來表示，稱為產(chǎn)銷平衡表. 由于運貨距離和運貨公路的路況不同，各個工廠運往各商店物資的單位運輸費用是不同的，單位費用如表4-4所示，稱為單位運價表. 表

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

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

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

7、對商店對商店3 3必須有必須有 X X1313+X+X2323+X+X3333 = 30 = 30約束條件約束條件主要是對工廠的產(chǎn)量約束和商店的銷量約束，由于主要是對工廠的產(chǎn)量約束和商店的銷量約束，由于產(chǎn)量與銷量相同，因而有：產(chǎn)量與銷量相同，因而有：現(xiàn)在學(xué)習(xí)的是第八頁，共84頁9 于是，解此問題的線性最優(yōu)化模型為：于是，解此問題的線性最優(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ī)劃的單純形法對它進(jìn)行求解. 但是，

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

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

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

12、學(xué)模型的特點運輸問題數(shù)學(xué)模型的特點 對于產(chǎn)銷平衡運輸問題（4.3），將其約束條件加以整理，可知其系數(shù)矩陣具有下述形式： 行行nmxxxxxxxxxmnmmnn111111111111111111212222111211（4.4） 由此可知，產(chǎn)銷平衡運輸問題數(shù)學(xué)模型有下述特點：現(xiàn)在學(xué)習(xí)的是第十三頁，共84頁14（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個約

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

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

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

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

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

18、小元素法和差值法（也叫伏格爾法），下面我們用上表4-9依次來說明. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量3656現(xiàn)在學(xué)習(xí)的是第十九頁，共84頁201. 西北角法(1) 從圖的西北角（即左上方）開始，在(A1,B1)格填入a1和b1中的較小值，這里填入較小值b1=3，即從A1運送3個單位物資到B1，此時的B1物資已經(jīng)全部滿足，劃去B1列，如下表4-10所示. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A133113107A219284A3741059銷量3656現(xiàn)在學(xué)習(xí)的是第二十頁，共84頁21（2）向a1,b1中較大數(shù)方向移動一格（或向右，或向下），這里是向右移動

19、一格，移動到(A1,B2)位置. B2需要6個單位物資，而A1只剩有4個單位，故在(A1,B2)處填4，A1的物資已經(jīng)全部發(fā)完，劃去A1行，如下表4-11所示. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A219284A3741059銷量3656現(xiàn)在學(xué)習(xí)的是第二十一頁，共84頁22（3）繼續(xù)按照上述步驟進(jìn)行，可知A2向B2運送2個單位物資，此時B2的物資已經(jīng)滿足，劃去B2列. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A2129284A3741059銷量3656現(xiàn)在學(xué)習(xí)的是第二十二頁，共84頁23（4）繼續(xù)按照上述步驟進(jìn)行. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A

20、21292284A3741059銷量3656現(xiàn)在學(xué)習(xí)的是第二十三頁，共84頁24（5）繼續(xù)進(jìn)行. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A21292284A37431059銷量3656現(xiàn)在學(xué)習(xí)的是第二十四頁，共84頁25（6）繼續(xù)進(jìn)行. 最后在(A3,B4)處填入6，此時A3和B4的物資已經(jīng)全部發(fā)送和接收完畢，因而同時劃去A3行和B4列，如下表4-13所示. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1334113107A21292284A374310659銷量3656現(xiàn)在學(xué)習(xí)的是第二十五頁，共84頁26（7）得到初始方案，如下表4-14所示. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A133411310

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

22、,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銷量3656現(xiàn)在學(xué)習(xí)的是第二十八頁，共84頁29（2）再從未劃去的元素中找最小元素，并從該元素開始確定運輸關(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)量A13113107A23191284A374

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

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

25、產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656現(xiàn)在學(xué)習(xí)的是第三十三頁，共84頁34（7）得到初始方案，如下表4-18所示. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656總運費 863564123131043Z現(xiàn)在學(xué)習(xí)的是第三十四頁，共84頁353. 差值法（伏格爾法）初看起來，最小元素法十分合理. 事實上，最小元素法的缺點是：為了節(jié)省一處的費用，有時造成其它處要多花幾倍的運費，這是因為有時按某一最小單位運價優(yōu)先安排物資運輸時，卻可能導(dǎo)致不得不采用運費很高的其它點對，從而使整個運輸費用增加.

26、 伏格爾法考慮到，一個產(chǎn)地的產(chǎn)品假如不能按最小費用就近供應(yīng)，就考慮次小費用，這樣最小費用和次小費用就有一個差額，差額越大，說明不按最小費用調(diào)運時，運費增加越多，因而對差額最大處，就應(yīng)當(dāng)采用最小調(diào)運方案.基于此，伏格爾法的步驟是：每次從當(dāng)前運價表上，計算各行各列中最小費用與次小費用這兩個運價的差值，優(yōu)先取最大差值的行或列中最小的單位運價來確定運輸關(guān)系，直到求出初始方案.現(xiàn)在學(xué)習(xí)的是第三十五頁，共84頁36 銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131131070A2192841A37410591銷量3656列差額2513我們?nèi)匀豢紤]表4-9所示的運輸問題，伏格爾法確定初始基可行解的步驟如下： （1

27、）先分別計算出各行和各列最小費用與次小費用的差額，稱為行差額和列差額，并將行差額和列差額填入該表的最右列和最下行，如下表4-19所示.現(xiàn)在學(xué)習(xí)的是第三十六頁，共84頁37 銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131131070A2192841A376410591銷量3656列差額2513（2）從行差額和列差額中選出最大者，選擇它所在的行或列中的最小費用所在的格作為優(yōu)先的運輸關(guān)系.在這里行差額與列差額最大值為5，故選擇5所在的列最小單位運價4為優(yōu)先運輸關(guān)系，即讓A3優(yōu)先供應(yīng)物資到B2，根據(jù)產(chǎn)、銷量知A3供應(yīng)6個單位物資到B2，此時B2列已滿足，劃去B2列，得下表4-20. 現(xiàn)在學(xué)習(xí)的是第三十七頁

28、，共84頁38 銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A131131070A2192841A3764103592銷量3656列差額2513（3）計算剩余元素的行差額和列差額，選出最大者，選擇它所在的行或列中的最小費用所在的格作為優(yōu)先的運輸關(guān)系. 在這里行差額與列差額最大值為B4列的3，故選擇3所在的列最小單位運價5為優(yōu)先運輸關(guān)系，即讓A3供應(yīng)物資到B4，由剩余的產(chǎn)、銷量知A3只能供應(yīng)3個單位物資到B4，這時A3已經(jīng)發(fā)貨完畢，劃去A3行，如表4-21所示. 現(xiàn)在學(xué)習(xí)的是第三十八頁，共84頁39（4）繼續(xù)計算剩余元素的行差額和列差額，并按照上述步驟確定運輸關(guān)系，經(jīng)過若干步以后，最后填2到(A1,B4)

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

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

31、產(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ù)列向量是線性獨立的. 這是因為若表中確定了某一個基變量 以后，它對應(yīng)的系數(shù)列向量 ，給定 的值以后，將劃去第i行或第j列，即其后的系數(shù)列向量中不再出現(xiàn) 或 ，因而 不可能用其它向量的線性組合表示. 所以這m+n-1個基變量對

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

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

34、4頁46下面我們看用閉回路法計算非基變量（空格點）檢驗數(shù)的計算方法. 首先考慮表4-23的空格點(A1,B1), 假設(shè)產(chǎn)地A1運送1個單位的物資到銷地B1，為使運入銷地B1物資的數(shù)量等于它的銷量，就應(yīng)當(dāng)將原來A2運送到的B1物資數(shù)量減去1個單位，即將(A2,B1)格的3變?yōu)?；另一方面，為使運出產(chǎn)地A2物資的數(shù)量等于它的產(chǎn)量，就應(yīng)當(dāng)將原來(A2,B3)格的數(shù)1加上1，再考慮B3知應(yīng)將(A1,B3)格的4變?yōu)?，從而得到一個新的運輸方法. 顯然這樣的調(diào)整將影響到空格(A1,B1)閉回路上的各個數(shù)據(jù). 按照上述假設(shè)，如果由產(chǎn)地A1運送1個單位的物資到銷地B1，由此引起的總費用變化是 ，即總費用增加

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

36、是最優(yōu)解，這時就要進(jìn)行調(diào)解. 和單純形法類似，當(dāng)有兩個和兩個以上空格的檢驗數(shù)為負(fù)時，一般選其中最小的負(fù)檢驗數(shù)，以它對應(yīng)的空格作為調(diào)入格，即該空格對應(yīng)的變量為進(jìn)基變量. 在進(jìn)基變量的回路中，比較奇數(shù)拐角點的運量，為了使新得到的解仍為基可行解，應(yīng)當(dāng)選擇一個具有最小運量的基變量作為出基變量，并使調(diào)整的運量為各個奇數(shù)拐角點運量的最小值. 在表4-26中，只有空格(A2,B4)處的檢驗數(shù)為負(fù)，因而它對應(yīng)的變量 為進(jìn)基變量，它的閉回路如表4-27所示.24x現(xiàn)在學(xué)習(xí)的是第四十八頁，共84頁49 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311433107A23191284A376410359銷量3656奇數(shù)拐點處運

37、量的最小值為1, 因而為了保持平衡，將奇數(shù)拐點處的運量減去1，偶數(shù)拐點處的運量加1，調(diào)整后的運輸方案如下表4-28所示. 現(xiàn)在學(xué)習(xí)的是第四十九頁，共84頁50 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1311532107A23192184A376410359銷量3656調(diào)整以后，再計算各個空格的檢驗數(shù)，如果所有的檢驗數(shù)均大于等于零，則這個運輸方案就是最優(yōu)解；如果還有某個空格的檢驗數(shù)為負(fù)數(shù)，則再以這個空格為調(diào)入格，作相應(yīng)的基變換，直到所有的檢驗數(shù)為非負(fù). 上述表中得到的所有的檢驗數(shù)為非負(fù)，因而此運輸方案是最優(yōu)方案. 現(xiàn)在學(xué)習(xí)的是第五十頁，共84頁512. 位勢法位勢法 在閉回路法中，為了計算一個空格點處的

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

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

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

41、至得出最優(yōu)解. 0124現(xiàn)在學(xué)習(xí)的是第五十五頁，共84頁56表上作業(yè)法在計算中可能還會出現(xiàn)一些問題，這里我們需要說明.1. 當(dāng)?shù)竭\輸問題的最優(yōu)解時，如果有某個非基變量的檢驗數(shù)等于零，則說明該運輸問題有無窮多最優(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，以表示它是基變量. 現(xiàn)在學(xué)習(xí)的是第五十六頁，共84頁574.3產(chǎn)銷不平衡的運輸問題

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

43、的表上作業(yè)法，可增加一個假想的銷地Bn+1，由各產(chǎn)地Ai(i=1,2,m)運送到這個銷地Bn+1物資的數(shù)量設(shè)為 ，實際上就是產(chǎn)地Ai就地貯存物資的數(shù)量，顯然單位運價 . 因此假想后原問題的最優(yōu)總費用與假想之前的最優(yōu)總費用是一致的. 由于總產(chǎn)量剩余為使產(chǎn)銷平衡，可假設(shè)銷地Bn+1的銷量此時模型（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í)的是第五十八頁，共84頁59 銷地 產(chǎn)地B1 B2 BnBn+1產(chǎn)量A1X11c11X12c12X1nc1nX1，n+10a1A2X21c21X22c22X2nc2nX2，n+10a2AmXm1cm1Xm2cm2XmncmnXm，n+10am銷量b1b2bn可以看出，模型（4.6）是有m個產(chǎn)地，n+1個銷地的產(chǎn)銷平衡運輸問題，因而通過假想銷地，可將產(chǎn)大于銷的運輸問題轉(zhuǎn)化為產(chǎn)銷平衡運輸問題. 和模型（4.6）對應(yīng)的運輸表如下表所示. njjmiiba11現(xiàn)在學(xué)習(xí)的是第五十九頁，共84頁60如果總銷量大于總產(chǎn)量，即可仿照產(chǎn)大于銷的操作過程，增加一個假想的產(chǎn)地Am+1，它的產(chǎn)量為由于這個

45、假想的產(chǎn)地并不存在，求出的由它發(fā)往各個銷地的物資數(shù)量 實際上是各銷地所需物資的欠缺額，這部分物資的運輸并未發(fā)生，因而單位運價 . 這樣也可以將原問題化為產(chǎn)銷平衡運輸問題.miinjjab11miinjjmaba111), 2 , 1(, 1njxjm), 2 , 1(0, 1njcjm現(xiàn)在學(xué)習(xí)的是第六十頁，共84頁61例例3 某市有三個造紙廠A1，A2，A3和四個批發(fā)用戶B1，B2，B3，B4，各造紙廠紙的產(chǎn)量、各批發(fā)用戶的需求量及各造紙廠到各批發(fā)用戶的單位運價如下表4-32所示，試確定運輸總費用最小的調(diào)運方案. 批發(fā)用戶造紙廠B1B2B3B4產(chǎn)量A1312348A2112595A367159

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

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

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

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

50、行計算，可以求得最優(yōu)方案如下表4-37所示. 現(xiàn)在學(xué)習(xí)的是第六十七頁，共84頁68需求地區(qū)化肥廠產(chǎn)量1161650132217175021414201319101530156033019201902023MM504M0M300M20050需求量302070301050從表4-37可以看出，地區(qū)滿足最高需求量50萬噸，地區(qū)沒有接收到任何物資，只滿足最低需求0，而地區(qū)滿足了40萬噸現(xiàn)在學(xué)習(xí)的是第六十八頁，共84頁69 使用者產(chǎn)地產(chǎn)量124321563324使用量1046例例5 設(shè)有三個產(chǎn)地生產(chǎn)同一種產(chǎn)品并供應(yīng)給三個使用者，各產(chǎn)地到各使用者的單位運價及使用者的需求量如下表4-38所示. 由于銷售需要

51、及客觀條件的限制，產(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ōu)調(diào)運方案. 43a72a現(xiàn)在學(xué)習(xí)的是第六十九頁，共84頁70使用者產(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)銷平衡運輸問題.由表4-39求解該產(chǎn)銷平衡運輸問題解的過程及結(jié)果請讀者自己完成. 現(xiàn)在學(xué)習(xí)的是第七十頁，共84頁

52、71 銷地產(chǎn)地產(chǎn)量112220214540323330銷量302020例例6 三個產(chǎn)地欲將同一種物資運送到三個銷地，各產(chǎn)地產(chǎn)量、各銷地銷量以及各產(chǎn)地運送物資到各銷地的單位運價如下表4-40所示. 若各產(chǎn)地有物資沒有運出，就發(fā)生存儲費用，假設(shè)三個產(chǎn)地單位物資存儲費分別為4,4,3；產(chǎn)地2的物資最多運出35個單位，產(chǎn)地3的物資至少運出28個單位，試給出使總運輸費用最小的運輸方案.現(xiàn)在學(xué)習(xí)的是第七十一頁，共84頁72解解 這是一個有存儲形式的產(chǎn)銷不平衡運輸問題.為使問題化為無存儲費用的產(chǎn)銷平衡運輸問題，可將產(chǎn)地1,2,3設(shè)想為三個銷地,，考慮到物資存儲的費用，可將單位存儲費按單位運價來表示. 如產(chǎn)地

53、1到銷地（即產(chǎn)地1）的單位運輸費用為4，產(chǎn)地1不能運送物資到產(chǎn)地2（即銷地），因而產(chǎn)地1到銷地的單位運輸費用為M（M任意大）. 又由于產(chǎn)地2的物資最多運出35個單位，因而產(chǎn)地2至少存儲5個單位物資，即銷地的需求量至少為5個單位，同理銷地需求量至多為2個單位，為保持運輸平衡，銷地的需求量是015之間使產(chǎn)銷平衡的值，因而原問題轉(zhuǎn)化為下表4-41所示的產(chǎn)銷平衡運輸問題.現(xiàn)在學(xué)習(xí)的是第七十二頁，共84頁73銷地產(chǎn)地產(chǎn)量11224MM202145M4M403233MM330銷量30202001552表4-41現(xiàn)在學(xué)習(xí)的是第七十三頁，共84頁74銷地產(chǎn)地產(chǎn)量181212204MM20222145M184M

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