第三章運輸問題1

1、第三章第三章 運輸問題運輸問題一、運輸問題及其數(shù)學(xué)模型二、表上作業(yè)法三、運輸問題的進一步討論四、應(yīng)用舉例第三章2312341一、運輸問題及其數(shù)學(xué)模型一、運輸問題及其數(shù)學(xué)模型s2=27s3=19s1=14供應(yīng)量供應(yīng)地運價d1=22d2=13d3=12d4=13需求量需求地6753842759106 引例：引例：運輸問題網(wǎng)絡(luò)圖第三章0 xxxxxxxxxxxx13xxx12xxx13xxx22xxx19xxxx27xxxx14xxxxs.t.x6x10 x9x5x7x2x4x8x3x5x7x6zmin3433323124232221141312113424143323133222123121113

2、43332312423222114131211343332312423222114131211供應(yīng)地約束需求地約束一、運輸問題及其數(shù)學(xué)模型一、運輸問題及其數(shù)學(xué)模型第三章運輸問題的描述： 設(shè)某種物品有m個產(chǎn)地A1,A2,.,Am，各產(chǎn)地的產(chǎn)量分別是a1,a2,.,am；有n個銷地B1,B2,.,Bn，各銷地的銷量分別為b1,b2,.bn。假定從產(chǎn)地Ai(i=1,2,m)向銷地出Bj(jl,2,.n)運輸單位物品的運價是cij，問怎樣調(diào)運這些物品才能使總運費最小?一、運輸問題及其數(shù)學(xué)模型一、運輸問題及其數(shù)學(xué)模型第三章運價表 銷地產(chǎn)地B1B2Bn產(chǎn)量A1C11C12C1na1x11x12x1nA2C

3、12C22C2na2x21x22x2n.AmC1mC2mCmnamxm1xm2xmn銷量b1b2bm一、運輸問題及其數(shù)學(xué)模型一、運輸問題及其數(shù)學(xué)模型第三章產(chǎn)銷平衡運輸問題的數(shù)學(xué)模型表示：j xciBA設(shè)ijij njmixnjbxmiaxxCzijmijijnjiijminjijij,.,2 , 1;,.,2 , 10,.2 , 1,.2 , 1min1111（ ）0,ijjiCba其中jiba一、運輸問題及其數(shù)學(xué)模型一、運輸問題及其數(shù)學(xué)模型第三章該模型是一個線性規(guī)劃模型，可以用單純形法求解。但是變量數(shù)目非常多。如3個產(chǎn)地，4個銷地。變量數(shù)目會有19個之多。因此應(yīng)該尋求更簡便的解法。為了說明適

4、于求解運輸問題的更好的解法，先分析運輸問題數(shù)學(xué)模型的特點。一、運輸問題及其數(shù)學(xué)模型一、運輸問題及其數(shù)學(xué)模型第三章運輸問題數(shù)學(xué)模型的特點：運輸問題數(shù)學(xué)模型的特點：1運輸問題有有限最優(yōu)解運輸問題有有限最優(yōu)解jibaQnjmiQbaxjiij,.2,1;,.,2,1,是一個可行解。同時，目標函數(shù)有下界，且不會趨于負無窮。所以，必存在有限最優(yōu)解。一、運輸問題及其數(shù)學(xué)模型一、運輸問題及其數(shù)學(xué)模型第三章2運輸問題約束條件的系數(shù)矩陣運輸問題約束條件的系數(shù)矩陣111.1111.1.1.11.1.1221111mnmnnxxxxxxA =n 行m 行jmiijeeP系數(shù)列向量：TijA)0,.,0,1 ,0,.

5、,0,1 ,0,.,0(第i個第m+ j個一、運輸問題及其數(shù)學(xué)模型一、運輸問題及其數(shù)學(xué)模型第三章由此可知，運輸問題具有下述特點： (1)約束條件系數(shù)矩陣的元素等于0或1； (2)約束條件系數(shù)矩陣的每一列有兩個非零元素，這對應(yīng)于每一個變量在前m個約束方程中出現(xiàn)一次，在后n個約束方程中也出現(xiàn)一次；對產(chǎn)銷平衡運輸問題，除上述兩個特點外，還有以下特點：(3)所有結(jié)構(gòu)約束條件都是等式約束；(4)各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和。 秩 ( A) =m+n-1運輸問題的基可行解中應(yīng)包含m+n-1個基變量.一、運輸問題及其數(shù)學(xué)模型一、運輸問題及其數(shù)學(xué)模型第三章3.運輸問題的解運輸問題的解(1)解x必須滿足模型

6、中的所有約束條件；(2)基變量對應(yīng)的約束方程組的系數(shù)列向量線性無關(guān)；(3)解中非零變量xij的個數(shù)不能大于(m+n-1)個，原因是運輸問題中雖有(m+n)個結(jié)構(gòu)約束條件，但由于總產(chǎn)量等于總銷量，故只有(m+n-1)個結(jié)構(gòu)約束條件是線性獨立的；(4)為使迭代順利進行，基變量的個數(shù)在迭代過程中保持為 (m+n-1)個。運輸問題解的每一個分量，都唯一對應(yīng)其運輸表中的一個格 填有數(shù)字的格 或 空格一、運輸問題及其數(shù)學(xué)模型一、運輸問題及其數(shù)學(xué)模型第三章 銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116826A2210391010A38511622148銷量814121448下表給出了例下表給出了例1的一

7、個解。的一個解。一、運輸問題及其數(shù)學(xué)模型一、運輸問題及其數(shù)學(xué)模型第三章二、表上作業(yè)法二、表上作業(yè)法 表上作業(yè)法是一種迭代法，迭代步驟為： 1、先按某種規(guī)則找出一個初始解(初始調(diào)運方案)； 2、再對現(xiàn)行解作最優(yōu)性判別； 3、若這個解不是最優(yōu)解，就在運輸表上對它進行調(diào)整改進，得出個新解； 4、再判別，再改進； 5、直至得到運輸問題的最優(yōu)解為止。 迭代過程中得出的所有解都要求是運輸問題的基可行解。第三章例1： 銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量814121448二、表上作業(yè)法二、表上作業(yè)法第三章 銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A

8、22103910A38511622銷量81412144882101486所以，初始基可行解為：目標函數(shù)值Z246二、表上作業(yè)法二、表上作業(yè)法1、初始基可行解最小元素法、初始基可行解最小元素法第三章在滿足約束條件下盡可能的給最左上角的變量最大值. 銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量8141214488864814所以，初始基可行解為：目標函數(shù)值Z3721、初始基可行解西北角法、初始基可行解西北角法二、表上作業(yè)法二、表上作業(yè)法第三章沃格爾法計算步驟：1) 分別算出各行、各列的罰數(shù)。2) 從行、列中選出差額最大者，選擇它所在行、列中的最小元素，進

9、行運量調(diào)整。3) 對剩余行、列再分別計算各行、列的差額。返回1)、2)。二、表上作業(yè)法二、表上作業(yè)法1、初始基可行解沃格爾法、初始基可行解沃格爾法第三章 銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量81412144814所以，初始基可行解為：目標函數(shù)值Z244881224二、表上作業(yè)法二、表上作業(yè)法第三章 銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量814121448821014861211012-1二、表上作業(yè)法二、表上作業(yè)法2、解的最優(yōu)性檢驗閉回路法、解的最優(yōu)性檢驗閉回路法某空格的檢驗數(shù)是以該空格為第一

10、個某空格的檢驗數(shù)是以該空格為第一個頂點，某回路的奇數(shù)頂點運價和減去頂點，某回路的奇數(shù)頂點運價和減去其偶數(shù)頂點運價和。其偶數(shù)頂點運價和。第三章原問題設(shè)其對偶變量為：njmixnjbxmiaxxCzijmijijnjiijminjijij,.,2 , 1;,.,2 , 10,.2 , 1,.2 , 1min1111),.,.,(2121nmvvvuuuY 2、解的最優(yōu)性檢驗對偶變量法、解的最優(yōu)性檢驗對偶變量法二、表上作業(yè)法二、表上作業(yè)法第三章對偶問題:考慮原問題變量xj的檢驗數(shù)為：符號不限,.2 , 1,.2 , 1max11jiijjiminjjjiivunjmicvuvbuazjjjBjjjj

11、YPcPBCczc1jmiijeeP二、表上作業(yè)法二、表上作業(yè)法第三章假設(shè)已得到一個基可行解，其基變量為：則有：ssjijijixxx,.,2211s=m+n-1ssssjijijijijijicvucvucvu.22221111則運輸問題變量xij的檢驗數(shù)為：)(),.,.,(2121jiijijnmijijijijijijvucPvvvuuucYPczc二、表上作業(yè)法二、表上作業(yè)法第三章方程組有m+n-1個方程。因為運輸表中每行和每列均有基變量，因此上面方程組含有全部m+n個對偶變量。故解不唯一，其解稱為位勢。若上述方程的某組解滿足對偶問題的所有條件，即：此時，原問題與對偶問題均可行，故達

12、到最優(yōu)。其解分別為：0)(jiijijvucTjijijiTNBssxxxXXX)0,.,0 , 0 ,.,(),(2211二、表上作業(yè)法二、表上作業(yè)法第三章例：例： 銷地產(chǎn)地B1B2B3B4產(chǎn)量UiA141241116A22103910A38511622銷量814121448Vj82101486二、表上作業(yè)法二、表上作業(yè)法第三章 改進的方法是在運輸表中找出這個空格對應(yīng)的閉回路，在滿足所有約束條件的前提下，使xij盡量增大并相應(yīng)調(diào)整此閉回路上其它頂點的運輸量，以得到另一個更好的基可行解。3、解的改進閉回路調(diào)整法、解的改進閉回路調(diào)整法二、表上作業(yè)法二、表上作業(yè)法第三章 解改進的具體步驟解改進的具

13、體步驟(1)以xij為換入變量，找出它在運輸表中的閉回路；(2)以空格(Ai,Bj)為第一個奇數(shù)頂點，沿閉回路的順(或逆)時針方向前進，對閉回路上的頂點依次編號；(3)在閉回路上的所有偶數(shù)頂點中，找出運輸量最小的頂點(格子)，以該格中的變量為換出變量；(4)以換出變量的運輸量為調(diào)整量，將該閉回路上所有奇數(shù)頂點處的運輸量都增加這一數(shù)值，所有偶數(shù)頂點處的運輸量都減去這一數(shù)值，從而得出一新的運輸方案。該運輸方案的總運費比原運輸方案減少，改變量等于換出變量的檢驗數(shù)。 然后，再對得到的新解進行最優(yōu)性檢驗，加不是最優(yōu)解，就重復(fù)以上步驟繼續(xù)進行調(diào)整，一直到得出最優(yōu)解為止。二、表上作業(yè)法二、表上作業(yè)法第三章

14、銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量814121448例：821014861211012-1二、表上作業(yè)法二、表上作業(yè)法第三章 銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量814121448例：821214840229121由于所有非基變量的檢驗數(shù)全非負，故這個解為最優(yōu)解。又由于非基變量有零檢驗數(shù)，所以有無窮多最優(yōu)解。二、表上作業(yè)法二、表上作業(yè)法第三章練習(xí)題練習(xí)題 銷地產(chǎn)地B1B2B3B4產(chǎn)量A167531414A28427278136A35910619613銷量22131213二、表上作業(yè)法二、表

15、上作業(yè)法練習(xí)題練習(xí)題第三章練習(xí)題練習(xí)題 銷地產(chǎn)地B1B2B3B4產(chǎn)量A167531414557A284272781369A35910619-11-3613銷量22131213二、表上作業(yè)法二、表上作業(yè)法練習(xí)題練習(xí)題第三章練習(xí)題練習(xí)題 銷地產(chǎn)地B1B2B3B4產(chǎn)量A16753141455-4A284272721312-2A35910619681113銷量22131213二、表上作業(yè)法二、表上作業(yè)法第三章 銷地產(chǎn)地B1B2B3B4產(chǎn)量A167531415513A2842727213122A35910619198114銷量22131213 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1675314113A2842

16、72721312A3591061919銷量22131213答案答案二、表上作業(yè)法二、表上作業(yè)法第三章1）若運輸問題的某一基可行解有幾個非基變量的檢驗數(shù)均為負，在繼續(xù)進行迭代時，取它們中的任一變量為換入變量均可使目標函數(shù)值得到改善，但通常取小于零的檢驗數(shù)中最小者對應(yīng)的變量為換入變量。 2）當(dāng)?shù)竭\輸問題的最優(yōu)解時，如果有某非基變量的檢驗數(shù)等于零，則說明該運輸問題有多重(無窮多)最優(yōu)解。 4、需要說明的幾個問題、需要說明的幾個問題二、表上作業(yè)法二、表上作業(yè)法第三章3）（二 ）退化 某一基變量 的值為0初始解 在確定初始解的供需關(guān)系時，若在確定（i, j ） 的數(shù)字時，要劃去第i行,第j列。為使在

17、產(chǎn)銷平衡表上有m+n-1個數(shù)字格，須在第i 行或j列中 （ 非i,j ) 選一數(shù)字格為0。退化解 閉回路中有（ - ）標記中有兩個或以上相等的最小數(shù)。調(diào)整后出現(xiàn)退化解，必須在一數(shù)字格中填入0，以表明其為基變量。二、表上作業(yè)法二、表上作業(yè)法第三章三、運輸問題的進一步討論三、運輸問題的進一步討論 上一節(jié)講述的運輸問題的算法，是以總產(chǎn)量等于總銷量(產(chǎn)銷平衡)為前提的。實際上，在很多運輸問題中，總產(chǎn)量不等于總銷量。 第三章0,ijjiCba其中njmixnjbxmiaxxCzijmijijnjiijminjijij1 ,10,.2 , 1,.2 , 1min1111（ ）表上作業(yè)法 以產(chǎn)銷平衡 為前提

18、。jiba1、產(chǎn)銷不平衡的運輸問題、產(chǎn)銷不平衡的運輸問題三、運輸問題的進一步討論三、運輸問題的進一步討論第三章2321341s2=27s3=19d1=22d2=13d3=12d4=13s1=14供應(yīng)量供應(yīng)地運價需求量需求地6753842759106 例：假設(shè)供應(yīng)量大于需求量例：假設(shè)供應(yīng)量大于需求量+55d5=5 假想銷地0 0 0s3=24三、運輸問題的進一步討論三、運輸問題的進一步討論第三章0,.2 , 1,.2 , 1min1111ijmijijnjiijminjijijxnjbxmiaxxCzjiba 產(chǎn)大于銷 產(chǎn)銷不平衡產(chǎn)銷平衡模型：三、運輸問題的進一步討論三、運輸問題的進一步討論第三

19、章設(shè) 為Ai的貯存量。1, nixmiaxxxinjijninjij,.,2 , 1111,1jininijmiijbaxnjbx11,1,.,2 , 1將多余物原地貯存。令：101njnjCCijij三、運輸問題的進一步討論三、運輸問題的進一步討論第三章111njjmiiba理解： 產(chǎn) 銷 假想有一銷地 j=n+1 銷量為 運價 njjmiiba1101,niC01,.2, 1,.2, 1min111111 ijmijijnjiijminjijijxnjbxmiaxxCz模型：三、運輸問題的進一步討論三、運輸問題的進一步討論第三章 銷地產(chǎn)地B1B2BnBn+1 （貯存） 產(chǎn)量A1C11C12

20、C1n0a1x11x12x1nx1,n+1A2C12C22C2n0a2x21x22x2nx2 ,n+1.AmC1mC2mCmn0amxm1xm2xmnxm ,n+1銷量b1b2bma- b三、運輸問題的進一步討論三、運輸問題的進一步討論第三章例： 某市有三個造紙廠A1，A2，A3，其紙的產(chǎn)量分別為8，5和9個單位，有4個集中用戶B1，B2，B3，B4，其需用量分別為4，3，5和6個單位。由各造紙廠到各用戶的單位運價如表315所示，請確定總運費最少的調(diào)運方案。 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1312348A2112595A367159銷量4356三、運輸問題的進一步討論三、運輸問題的進一步討論第

21、三章 解：由于總產(chǎn)量22大于總銷量18，故本問題是個產(chǎn)銷不平衡運輸問題。增加一假想銷地B5，用表上作業(yè)法求解。 銷地產(chǎn)地B1B2B3B4B5(貯存) 產(chǎn)量A13123408A21125905A3671509銷量43564三、運輸問題的進一步討論三、運輸問題的進一步討論第三章 銷地產(chǎn)地B1B2B3B4B5(貯存)產(chǎn)量A13123408418634A211259050302-8A3671509-2954-4銷量43564 銷地產(chǎn)地B1B2B3B4B5(貯存)產(chǎn)量A1312340844A21125905032A367150954銷量43564三、運輸問題的進一步討論三、運輸問題的進一步討論第三章2、

22、有轉(zhuǎn)運的運輸問題、有轉(zhuǎn)運的運輸問題在以上討論中，假定物品由產(chǎn)地直接運送到銷售目的地，不經(jīng)中間轉(zhuǎn)運。但是，常常會遇到這種情形：需先將物品由產(chǎn)地運列某個中間轉(zhuǎn)運站(可能是另外的產(chǎn)地、銷地或中間轉(zhuǎn)運倉庫)，然后再轉(zhuǎn)運到銷售目的地。有時，經(jīng)轉(zhuǎn)運比直接運到目的地更為經(jīng)濟。因此，在決定運輸方案時有必要把轉(zhuǎn)運也考慮進去。三、運輸問題的進一步討論三、運輸問題的進一步討論第三章2、有轉(zhuǎn)運的運輸問題、有轉(zhuǎn)運的運輸問題第三章轉(zhuǎn)運量 t1t2t3t4t5t6t7A2A3A1a2=27a3=19a1=14供應(yīng)量需求量B2B3B4B1a5=0a6=0a4=0a7=0A2A3A1b4=22b5=13b6=12b7=13B2

23、B3B4B1b1=0b2=0b3=0 xij轉(zhuǎn)運量 t1t2t3t4t5t6t7第三章假設(shè)單位運轉(zhuǎn)費用為ti，則線性規(guī)劃模型為：7711767623232121171713131212.mintctcxcxcxcxcxcxcz717171iiijiiijjijijtcxc7,.,2 , 1, 022144746454342414171615141312144746454342411171615141312jixtxxxxxxtxxxxxxtxxxxxxtxxxxxxij三、運輸問題的進一步討論三、運輸問題的進一步討論第三章7711767623232121171713131212.mintctc

24、xcxcxcxcxcxcz717171iiijiiijjijijtcxc7,.,2 , 1, 022144746454342414171615141312144746454342411171615141312jixtxxxxxxtxxxxxxtxxxxxxtxxxxxxij141716151413121xxxxxxt141716151413121QxxxxxxtQ1417161514131211QxxxxxxxQxxxxxxxQxxxxxxxQxxxxxxx22746454443424147161514131211147464544434241717171iiijijijQcxciiicx的系

25、數(shù)為注意717171)(iiiijiiijjijijxQcxc第二項為常數(shù)，對求解結(jié)果無影響，可去掉。第三章7171minijijijxcz1417161514131211QxxxxxxxQxxxxxxxQxxxxxxxQxxxxxxx227464544434241471615141312111474645444342417,.,2 , 1, 0jixij模型變?yōu)橄铝行问剑哼@是一個產(chǎn)銷平衡運輸問題的數(shù)學(xué)模型?？梢粤谐銎溥\價表，用表上作業(yè)法求解。 銷地產(chǎn)地A1A2A3B1B2B3B4產(chǎn)量A1A2A3B1B2B3B4銷量其運價表形式如下（注意其中對角線上的運價值）：第三章建立一般意義上的數(shù)學(xué)模型，

26、設(shè)：建立一般意義上的數(shù)學(xué)模型，設(shè)：ai：第：第i個產(chǎn)地的產(chǎn)量個產(chǎn)地的產(chǎn)量(凈供應(yīng)量凈供應(yīng)量)；bj：第：第j個銷地的銷量個銷地的銷量(凈需要量凈需要量)；xij：由第：由第i個發(fā)送地運到第個發(fā)送地運到第j個接收地的物品數(shù)量；個接收地的物品數(shù)量；cij：由第：由第i個發(fā)送地到第個發(fā)送地到第j個接收地的單位運價，個接收地的單位運價，ti：第：第i個地點轉(zhuǎn)運物品的數(shù)量；個地點轉(zhuǎn)運物品的數(shù)量；ci：第：第i個地點轉(zhuǎn)運單位物品的費用。個地點轉(zhuǎn)運單位物品的費用。 將產(chǎn)地和銷地統(tǒng)一編號，并把產(chǎn)地排在前面。銷地排在將產(chǎn)地和銷地統(tǒng)一編號，并把產(chǎn)地排在前面。銷地排在后面，則有：后面，則有：第三章nmiiinmji

27、inmijjijijtcxcz111min令：令：iiitQxjjjtQx建立數(shù)學(xué)模型：建立數(shù)學(xué)模型：)(,.,2 , 1, 0,.,2, 1,.,.,.,2 , 1,.,.,.,2, 1,.,.,.,2 , 1,.,., 1, 121, 1, 121,1,1,21,1,1,21jinmjixnmmmitbxxxxxmjtxxxxxnmmmitxxxxxmitaxxxxxijjjjnmjjjjjjjjnmjjjjjjinmiiiiiiiiinmiiiiiii第三章注：所有i=j，cij=-ci第三章第三章a1a5b1b5Qc1c5c11c55 例：如圖所示是一個運輸系統(tǒng)，它包括二個產(chǎn)地（例：如

28、圖所示是一個運輸系統(tǒng)，它包括二個產(chǎn)地（1和和2）、二）、二個銷地個銷地(4和和5)及一個中間轉(zhuǎn)運站及一個中間轉(zhuǎn)運站(3)，各產(chǎn)地的產(chǎn)量和各銷地的，各產(chǎn)地的產(chǎn)量和各銷地的銷量用相應(yīng)節(jié)點處箭線旁的數(shù)字表示，節(jié)點聯(lián)線上的數(shù)字表示銷量用相應(yīng)節(jié)點處箭線旁的數(shù)字表示，節(jié)點聯(lián)線上的數(shù)字表示其間的運輸單價，節(jié)點旁的數(shù)字為該地的轉(zhuǎn)運單價，試確定最其間的運輸單價，節(jié)點旁的數(shù)字為該地的轉(zhuǎn)運單價，試確定最優(yōu)運輸方案。優(yōu)運輸方案。第三章 銷地產(chǎn)地A1A2B3C4C5產(chǎn)量A1A2B3C4C5銷量第三章 銷地產(chǎn)地A1A2B3C4C5產(chǎn)量A1-4532M60A25-12M490B332-35550C42M5-3650C5M4

29、56-550銷量5050508070第三章運用最小元素法，求初始運輸方案，如下表：最優(yōu)運輸方案如下表：302020第三章一、回答問題1、在運輸問題數(shù)學(xué)模型中，為什么模型的(m+n)個約束中最多只有(m+n-1)個是獨立的?2試述用最小元素法確定運輸問題的初始基可行解的基本思路。3如何用閉回路法求檢驗數(shù)？4 沃格爾法的基本思想是什么？什么是罰數(shù)？5在解的改進過程中，如何確定調(diào)整量？6如何把一個產(chǎn)銷不平衡的運輸問題(含產(chǎn)大于銷和銷大于產(chǎn))轉(zhuǎn)化為產(chǎn)銷平衡的運輸問題。練習(xí)題練習(xí)題第三章二、判斷下列說法是否正確(1)運輸問題是一種特殊的線性規(guī)劃模型，因而求解結(jié)果也可能出現(xiàn)下列四種情況之一：有唯一最優(yōu)解，

30、有無窮多最優(yōu)解，無界解，無可行解；(2)在運輸問題中，只要給出一組合(m+n-1)個非零的xij，且滿足xij=ai， xij=bj，就可以作為一個初始基可行解；(3)表上作業(yè)法實質(zhì)上就是求解運輸問題的單純形法；(4)按最小元素法(或伏格爾法)給出的初始基可行解，從每一空格出發(fā)可以找出而且僅能找出唯一的閉回路；練習(xí)題練習(xí)題第三章(5)如果運輸問題單位運價表的某一行(或某一列)元素分別加上一個常數(shù)k，最優(yōu)調(diào)運方案將不會發(fā)生變化；(6)如果運輸問題單位運價表的某一行(或某一列)元素分別乘上一個常數(shù)k，最優(yōu)調(diào)運方案將不會發(fā)生變化；(7)當(dāng)所有產(chǎn)地產(chǎn)量和銷地的銷量均為整數(shù)值時，運輸問題的最優(yōu)解也為整數(shù)

31、值1，2，6不對練習(xí)題練習(xí)題第三章三、用位勢法（對偶變量法）求其檢驗數(shù)。三、用位勢法（對偶變量法）求其檢驗數(shù)。練習(xí)題練習(xí)題第三章四、運用舉例四、運用舉例例 1 、某飛機制造廠生產(chǎn)一種民用噴氣式飛機，生產(chǎn)的最后階段是制造噴氣發(fā)動機，以及把發(fā)動機安裝到已完成的飛機骨架上（一種很快的操作）。為了不誤合同規(guī)定的交貨期，第一.二.三.四月必須安裝發(fā)動機的臺數(shù)分別為：10 ,15, 25 ,20。但受生產(chǎn)能力等條件的限制，這些月份的最高生產(chǎn)臺數(shù)分別為：25,35 ,30 , 10。每月單臺發(fā)動機的存儲費用為1.5萬元。已知一、二、三、四月份的單臺生產(chǎn)費用各為：108 、111、 110、113萬元。試安排

32、這四個月的生產(chǎn)計劃，使生產(chǎn)費用和存儲費用之和最小。 1）建立此問題的一般LP模型。 2）把此問題作為運輸問題來處理，試建立相應(yīng)的運輸表格。 3）求此“運輸問題”的最優(yōu)解。第三章 解：1）設(shè)xi表示第i個月生產(chǎn)發(fā)動機的臺數(shù)，yi表示第個月的存儲臺數(shù)，則一般LP模型為：0,1030352570502510)(5 . 1113110111108min43214432133212211143214321iiyxxxxxyxxxxyxxxyxxyxyyyyxxxx四、運用舉例四、運用舉例第三章個月發(fā)動機的安裝。第收點個月發(fā)動機的生產(chǎn)。第設(shè)發(fā)點jjii、)2(用之和。月的單臺發(fā)動機存儲費存儲到第月生產(chǎn)第個

33、月的單臺生產(chǎn)費用與第數(shù)。個月安裝的發(fā)動機的臺個月生產(chǎn)供第第j、iicjixijij 由于不能缺貨，并考慮到是不平衡問題（虛設(shè)收點5）建立如下運輸表格四、運用舉例四、運用舉例第三章：計算得最優(yōu)生產(chǎn)安排為10410203525101014321最小費用為： w*=7730(萬元）123451108109.5111112.50252M111112.51140353MM110111.50304MMM1130101015252030四、運用舉例四、運用舉例第三章例2 某航運公司承擔(dān)六個港口城市A.B.C.D.E.F的四條固定航線的物資運輸任務(wù)。已知各條航線的起點、終點城市及每天航班數(shù)見表：航線起點城市終點城市每天航線1ED32BC23AF14DB1每條航線使用相同型號的船只，各城市間的航程天數(shù)如表：