運籌學課件17運輸問題

1、第七節(jié)第七節(jié) 運輸規(guī)劃問題運輸規(guī)劃問題1、供求平衡的運輸規(guī)劃問題2、供求不平衡運輸問題的解法3、運輸問題的應用舉例一、供求平衡運輸規(guī)劃問題供求平衡運輸問題及其數(shù)學模型l例1-10l供求平衡運輸問題l數(shù)學模型表上作業(yè)法l求初始基本可行解l計算檢驗數(shù)及最優(yōu)解檢驗l調整求新解解的退化問題二、供求不平衡運輸問題的解法供大于求的情況求大于供的情況都應化為供求平衡問題后再求解三、運輸規(guī)劃問題的應用舉例例1-11l供求不平衡問題l按最低需求量計算是供大于求，首先增加一個銷地將銷地4增加一個分部l按最高需求量計算是可能求大于供，增加一產(chǎn)地4。例1-10設有三個電視機廠。生產(chǎn)同一種彩色電視機，日生產(chǎn)能力分別是：

2、50，60，50，供應四個門市部，日銷售量分別是：40，40，60，20臺，從各分廠運往各門市部的運費如表1-23所示，試安排一個運費最低的運輸計劃。 門市部工廠1234供應總計12397612359796711506050需求總計40406020供求平衡的運輸問題：供：50+60+50=160 需：40+40+60+20=160數(shù)學模型04 , 3 , 2 , 1,3 , 2 , 1,. .min31413141ijjiijijijijijijxjdxisxtsxcz表上作業(yè)法運輸問題的單純形法運輸問題總有最優(yōu)解。求解步驟l確定初始可行解l求空格檢驗數(shù)，檢驗最優(yōu)解l調整（換基、求新解）可行解

3、l重復作上述2、3兩步，直至求得最優(yōu)解。初始可行解（西北角法） 門市部工廠1234供應總計19129650273776036591150需求總計40406020初始可行解（西北角法） 門市部工廠1234供應總計19129650273776036591150需求總計40406020401030303020 門市部工廠1234供應總計19129650273776036591150需求總計40406020初始可行解（最小元素法）404020203010366799 門市部工廠1234供應總計19129650 401027377603030365911502030需求總計40406020計算檢驗數(shù)（閉

4、合回路法）計算檢驗數(shù)（閉合回路法）對于空格（1，4）其它的空格12)11712(936140)93(754)399(12762)117(977)39(1277)712(393231242113計算檢驗數(shù)（位勢法）對偶問題的變量為 ，則約束條件為又因為檢驗數(shù)當 時，取得最優(yōu)解，同時對偶問題的基本解可行（也最優(yōu)）。根據(jù)單純形法，對于基變量 。),(jivuy ijjicvujiijijijijvucyPc0ij0ij方程共有m+n-1個方程，但有m+n個變量，一般令 。因此可求得這些變量。我們稱 分別為產(chǎn)地位勢和銷地位勢。對于本例：計算檢驗數(shù)（位勢法）ijjicvu01ujivu 和11,97,3

5、0,12,94333322212111vuvuvuvuuvuvu解得：因而可計算得計算檢驗數(shù)（位勢法）18;7;16;9;12;9433221vuvuvv0, 4, 27127323124122121411414311313vucvucvuc調整基本解（換基和求新解）-閉合回路法取負檢驗數(shù)中絕對值最大的空格作回路。從空格開始依次給回路頂點格標“+”和“-”找出“-”格中運量最小者，作為調整量，將每個“+”格的運量加上該調整量，每個“-”格的運量減去該調整量。即得新的基本可行解。再計算空格檢驗數(shù)和調整基本解，直到檢驗數(shù)非負為止。例1-10西北角法初始解的調整 門市部工廠1234供應總計19129

6、650 + 4010 -273776030 -30+3659115020 -30+需求總計40406020調整的結果 門市部工廠1234供應總計19129650（5） 1040（12）273776020（-2）(-5)403659115010（-8） （0）40需求總計40406020調整的結果 門市部工廠1234供應總計19129650 104027377602040365911501040需求總計40406020+-+203010調整的結果 門市部工廠1234供應總計19129650-3 104042737760206340365911508040需求總計40406020203010最優(yōu)解

7、（運費=980） 門市部工廠1234供應總計1912965030 20 （3）（7）273776020（3）（3）4036591150（5）40（0）10需求總計40406020最優(yōu)解無窮多和解的退化問題因為 ，因此最優(yōu)解有無窮多個。如何求其它最優(yōu)解？出現(xiàn)零的數(shù)字格，即為解的退化問題l在求初始解時，添進一個數(shù)字格，若供和求同時滿足，則引進一個零數(shù)字格；l在調整時，若有兩個及以上最小運量的“-”格，調整后，將出現(xiàn)零數(shù)字格。如何添零數(shù)字格？（分兩個情況考慮）032表1-35 初始解時的退化問題12345s1769355 2 3 2823576 5 135410695 1 4d235240表1-31

8、 調整引起的退化問題12s18730 20 1026920 (-4) 20d203012s18730 (4) 3026920 20 0d2030供大于求的情況數(shù)學模型0, 2 , 1, 2 , 1,. .min1111ijjmiijinjijminjijijxnjdxmisxtsxcz特點與處理辦法特點處理辦法：設置一個虛銷售點n+1，使且 ，因而化為平衡問題。njjmiids11njjmiindsd11101,nic結果01, 2 , 1, 2 , 1,. .min11111ijjmiijinjijminjijijxnjdxmisxtsxcz求大于供數(shù)學模型0, 2 , 1, 2 , 1,.

9、 .min1111ijjmiijinjijminjijijxnjdxmisxtsxcz特點與處理辦法特點處理辦法：增加一個虛產(chǎn)地m+1，使且 ，化為平衡問題。njjmiids11miinjjmsds1110, 1jmc結果0, 2 , 1,1, 2 , 1,. .min11111ijjmiijinjijminjijijxnjdxmisxtsxcz例1-11 物資調度問題有一批物資在三個供應點，供應給四個需求點，運價如表1-36所示，但第三供應點不能向第四需求點運送該物資，求總運費最少的調運方案。1234s1231614191313202219231715M506050dmin3070010dm

10、ax507030不限化不平衡為平衡問題對第四需求點的最大供應量：160-100=60噸按最大需求計算，需求為：150+60=210噸因此設置虛的第四供應點，供應量：50噸1234s1231614191614191313202219231715M1715M506050d302070301050M0M0M0450初始可行解1234s116161322171750214141319151560319192023MM504M0M0M050d30207030105050502030101030100檢驗數(shù)1234s116161322171750（2） （2）50(4)021414131915156030

11、1020(-1)（-2）319192023MM50(0)10（2）30104M0M0M050(M)(3)(M)(-1)50d302070301050-M+22-M+20第一次調整1234s116161322171750500214141319151560301020319192023MM501030104M0M0M05050d302070301050(-M+20)10200第一次調整檢驗數(shù)1234s116161322171750（2） （2）50(4)（2）021414131915156030020(1)10(-2)319192023MM50（0）20（2）30(M)(M)4M0M0M050(

12、M)(3)(M)(-1)(M)50d302070301050第二次調整1234s11616132217175050021414131915156030020100319192023MM5020304M0M0M05050d302070301050第二次調整檢驗數(shù)1234s1161613221717502250422214141319151560300201100319192023MM500202304M0M0M0501-350d302070301050第三次調整1234s1161613221717505021414131915156030020100319192023MM5020304M0M0M

13、050050d302070301050第三次調整檢驗數(shù)1234s116161322171750(2)(5)50(7)(2)(2)21414131915156030（3）20(4)10319192023MM50（-3）20（-1）30(M)(M)4M0M0M050(4)(M)50d30207030105000第四次調整1234s11616132217175050214141319151560302010319192023MM5020304M0M0M05050d30207030105000第四次調整檢驗數(shù)1234s1161613221717505550722214141319151560332041030319192023MM503020-104M0M0M05043020d302070301050第五次調整1234s11616132217175050214141319151560201030319192023MM50302004M0M0M0503020d302070301050第五次調