運輸問題(運籌學)課件

1、 運 籌 學王 莉 莉四川農(nóng)業(yè)大學數(shù)學系2012年10月運輸問題(運籌學)課件學習目標理解運輸問題的特點；掌握表上作業(yè)法；掌握確定初始調(diào)運方案的方法；掌握最優(yōu)解的檢驗法掌握調(diào)運方案的改進法.第四章運輸問題學習目標第四章運輸問題引 言 在生產(chǎn)經(jīng)營活動中，經(jīng)常碰到大宗物質(zhì)的調(diào)運問題.如煤炭、鋼鐵、木材、糧食等等物質(zhì)，在全國有若干個生產(chǎn)基地，根據(jù)已有的交通網(wǎng)，應如何制定調(diào)運方案，將這些物質(zhì)運到消費地點，而總運費要最小. 引 言 在生產(chǎn)經(jīng)營活動中，經(jīng)常碰到大宗物質(zhì)的調(diào)運輸問題的提法m 個產(chǎn)地 Ai 輸出某種貨物，其量為 ai ( i =1，2，m ). n 個銷地 Bj ，收到某種貨物，其量為 bj

2、( j =1，2，n ) . 從Ai 到 Bj 單位貨物運價為 Cij ，問題是在盡量滿足銷地的需求時總運價最小. 運輸問題的提法2312341供求平衡的運輸問題B1=22B2=13B3=12B4=13A2=27A3=19A1=14供應地運價需求地6753482759106供應量需求量總供應量60噸總需求量60噸供求平衡的運輸問題2312341供求平衡的運輸問題B1=22B2=13B3=113121322銷量196 /x3410 /x339 /x325 /x31A3277 /x242 /x234 /x228 /x21A2143 /x145 /x137 /x126 /x11A1運量B4B3B2B

3、1銷地產(chǎn)地單位 利潤供應地約束需求地約束13121322銷量196 /x3410 /x339 /x3運輸問題約束條件系數(shù)矩陣特點 系數(shù)矩陣元素松散，只有1和0；系數(shù)矩陣每列僅有兩個1，其余均為0運輸問題約束條件系數(shù)矩陣特點 系數(shù)矩陣元素松散，只有1和0；運輸問題1、平衡運輸問題：總產(chǎn)量=總銷量2、產(chǎn)大于銷運輸問題：總產(chǎn)量總銷量3、產(chǎn)小于銷運輸問題：總產(chǎn)量總銷量 運輸問題1、平衡運輸問題：總產(chǎn)量=總銷量平衡運輸問題的數(shù)學模型設(shè)xij 表示從Ai 到Bj 的運量平衡運輸問題的數(shù)學模型設(shè)xij 表示從Ai 到Bj 的運量產(chǎn)大于銷運輸問題的數(shù)學模型設(shè)xij 表示從Ai 到Bj 的運量產(chǎn)大于銷運輸問題的

4、數(shù)學模型設(shè)xij 表示從Ai 到Bj 的產(chǎn)小于銷運輸問題的數(shù)學模型設(shè)xij 表示從Ai 到Bj 的運量產(chǎn)小于銷運輸問題的數(shù)學模型設(shè)xij 表示從Ai 到Bj 的產(chǎn)銷平衡問題總產(chǎn)量等于總銷量的運輸問題 a、建立運輸表，確定初始調(diào)運方案 b、對該方案進行最優(yōu)性檢驗，若是最優(yōu)解，停止計算；否則轉(zhuǎn)入下一步 c、對非最優(yōu)解進行調(diào)整改進(也就是確定換入變量和換出變量)，找到新的可行方案 d、重復b、c步，直到找到最優(yōu)解為止.解法表上作業(yè)法產(chǎn)銷平衡問題總產(chǎn)量等于總銷量的運輸問題解法表上作業(yè)法開始畫出運輸表，確定初始調(diào)運方案(西北角法、最小元素法、沃格爾法)最優(yōu)解檢驗(閉回路法、位勢法)得到最優(yōu)解解的調(diào)整(閉

5、回路法)是否表上作業(yè)法的流程圖結(jié)束開始畫出運輸表，確定初始調(diào)運方案最優(yōu)解檢驗得到最優(yōu)解解的調(diào)整2312341供求平衡的運輸問題B1=22B2=13B3=12B4=13A2=27A3=19A1=14供應地運價需求地6753482759106供應量需求量總供應量60噸總需求量60噸供求平衡的運輸問題2312341供求平衡的運輸問題B1=22B2=13B3=1B1B2B3B4產(chǎn)A1675314A2842727A35910619銷22131213一、確定初始調(diào)運方案根據(jù)已知條件，寫出運輸表運價調(diào)運量，當無調(diào)運量時，填B1B2B3B4產(chǎn)A1675314A2842727A3591B1B2B3B4產(chǎn)A167

6、5314A2842727A35910619銷221312131、西北角法思路：優(yōu)先滿足運輸表上西北角(左上角)所在空格的供銷需求.148136613目標函數(shù)z=614 +88 +413 +26 +106 +613=350 .B1B2B3B4產(chǎn)A1675314A2842727A3591B1B2B3B4產(chǎn)A1675314A2842727A35910619銷221312132、最小元素法思路：優(yōu)先滿足最小單位運價所在空格的供銷需求.1132191312目標函數(shù)z=61 +82 +519 +413 +212 +313=232 .B1B2B3B4產(chǎn)A1675314A2842727A35913、沃格爾法思

7、路：首先計算每行和每列最小運價與次小運價之差，該數(shù)值稱為行罰數(shù)和列罰數(shù)，其含義為若不能按照最小運價確定供求關(guān)系，就必須考慮次小運價，這樣它們之間便產(chǎn)生運費的差額. 差額越大說明如果不按照最小運價確定供求關(guān)系運輸，而是按照次小運價由此所增加的運費越多，因而對差額最大處，應該采用最小運價調(diào)運.3、沃格爾法思路：首先計算每行和每列最小運價與次小運價之差，B1B2B3B4產(chǎn)行罰數(shù)A1675314A2842727A35910619銷22131213列罰數(shù)3、沃格爾法211321333B1B2B3B4產(chǎn)行罰數(shù)A1675314A2842727A3B1B2B3B4產(chǎn)行罰數(shù)A1675314A2842727A35

8、910619銷22131213列罰數(shù)3、沃格爾法51132133312B1B2B3B4產(chǎn)行罰數(shù)A1675314A2842727A3B1B2B3B4產(chǎn)行罰數(shù)A1675314A2842727A35910619銷22131213列罰數(shù)3、沃格爾法11133133312131912目標函數(shù)z=61 +82 +519 +413 +212 +313=232 .B1B2B3B4產(chǎn)行罰數(shù)A1675314A2842727A3通常來說，沃格爾法所得到的初始調(diào)運方案要比最小元素法所得到的優(yōu)，最小元素法得到的初始調(diào)運方案又要比西北角法得到的優(yōu).通常來說，沃格爾法所得到的初始調(diào)運方案要比最小元素法所得到的B1B2B3B

9、4產(chǎn)A1675314A2842727A35910619銷22131213二、最優(yōu)解檢驗在運輸表中運價調(diào)運量，當調(diào)運量為零時，填檢驗數(shù)B1B2B3B4產(chǎn)A1675314A2842727A3591二、最優(yōu)解檢驗最優(yōu)解要求：所有格的檢驗數(shù)必須全部為非負.常用方法：閉回路法位勢法二、最優(yōu)解檢驗最優(yōu)解要求：所有格的檢驗數(shù)必須全部為非負.常B1B2B3B4產(chǎn)A1675314A2842727A35910619銷221312131、閉回路法思路：以格為起點和終點，由橫線和豎線組成封閉多邊形，除起點外，其余轉(zhuǎn)折點必須為數(shù)字格. 通過該回路來計算格的檢驗數(shù).148613613B1B2B3B4產(chǎn)A1675314A2

10、842727A3591B1B2B3B4產(chǎn)A1675314A2842727A35910619銷221312131、閉回路法148613613運量：x12每增加一個單位，x22就減少一個單位 從而x21增加一個單位，最后x11減少一個單位.檢驗數(shù)s=7-4+8-6=50，說明運量x12不能增加，為最優(yōu).B1B2B3B4產(chǎn)A1675314A2842727A3591B1B2B3B4產(chǎn)A1675314A2842727A35910619銷221312131、閉回路法1486136135檢驗數(shù)s=5-2+8-6=50，說明運量x13不能增加，為最優(yōu).運量：x13每增加一個單位，x23就減少一個單位 從而x2

11、1增加一個單位，最后x11減少一個單位.B1B2B3B4產(chǎn)A1675314A2842727A3591B1B2B3B4產(chǎn)A1675314A2842727A35910619銷221312131、閉回路法1486136135檢驗數(shù)s=3-6+10-2+8-6=70，說明運量x14不能增加，為最優(yōu).5B1B2B3B4產(chǎn)A1675314A2842727A3591B1B2B3B4產(chǎn)A1675314A2842727A35910619銷221312131、閉回路法1486136135檢驗數(shù)s=7-6+10-2=90，說明運量x24不能增加，為最優(yōu).57B1B2B3B4產(chǎn)A1675314A2842727A359

12、1B1B2B3B4產(chǎn)A1675314A2842727A35910619銷221312131、閉回路法1486136135檢驗數(shù)s=9-4+2-10=-30，說明運量x32可以增加，從而非最優(yōu).579B1B2B3B4產(chǎn)A1675314A2842727A3591B1B2B3B4產(chǎn)A1675314A2842727A35910619銷221312131、閉回路法1486136135檢驗數(shù)s=5-8+2-10=-110，說明運量x31可以增加，從而非最優(yōu).579-3B1B2B3B4產(chǎn)A1675314A2842727A3591B1B2B3B4產(chǎn)A1675314A2842727A35910619銷22131

13、2131、閉回路法1486136135由于存在檢驗數(shù)小于零，說明此運輸方案非最優(yōu)，需改進.579-3-11B1B2B3B4產(chǎn)A1675314A2842727A3591B1B2B3B4產(chǎn)uiA1675314A2842727A35910619銷22131213vj2、位勢法sij = cij - ui - vj148613613數(shù)字格的檢驗數(shù)s為0B1B2B3B4產(chǎn)uiA1675314A2842727A35B1B2B3B4產(chǎn)uiA1675314A2842727A35910619銷22131213vj2、位勢ij = cij - ui - vj0- 42106令u1=0B1

14、B2B3B4產(chǎn)uiA1675314A2842727A35B1B2B3B4產(chǎn)uiA1675314A2842727A35910619銷22131213vj2、位勢法148613613020- 421065579-3-11B1B2B3B4產(chǎn)uiA1675314A2842727A35B1B2B3B4產(chǎn)uiA1675314A2842727A35910619銷22131213vj2、位勢法148613613020- 421065579-3-11由于存在檢驗數(shù)小于零，說明此運輸方案非最優(yōu)，需改進.B1B2B3B4產(chǎn)uiA1675314A2842727A35三、解的改進 若格的檢驗數(shù)存在負數(shù)，說明當前調(diào)運方案

15、不是最優(yōu)解，需要進行改進. 若格的檢驗數(shù)存在一個以上的檢驗數(shù)為負，一般應選取其中檢驗數(shù)最小的所在空格進行調(diào)整.調(diào)整方法：閉回路法三、解的改進 若格的檢驗數(shù)存在負數(shù)，說明當前調(diào)B1B2B3B4產(chǎn)A1675314A2842727A35910619銷22131213步驟1486136135(1)以該格為出發(fā)點，做一閉回路.579-3-11B1B2B3B4產(chǎn)A1675314A2842727A3591B1B2B3B4產(chǎn)A1675314A2842727A35910619銷22131213步驟1486136135(2)以格不在的對角線上最小運量作為調(diào)整量，格的運量增加調(diào)整量，其余各頂點的運量對應改變.579

16、-3-1162120B1B2B3B4產(chǎn)A1675314A2842727A3591B1B2B3B4產(chǎn)A1675314A2842727A35910619銷22131213步2)以格不在的對角線上最小運量作為調(diào)整量，格的運量增加調(diào)整量，其余各頂點的運量對應改變.B1B2B3B4產(chǎn)A1675314A2842727A3591B1B2B3B4產(chǎn)uiA1675314A2842727A35910619銷22131213vj142131261302sij = cij - ui - vj072-16令u1=0步驟(3)繼續(xù)計算調(diào)整后所有空格的檢驗數(shù)，若均非負，則已經(jīng)得到最優(yōu)解，否則返回步

17、驟(1).B1B2B3B4產(chǎn)uiA1675314A2842727A35B1B2B3B4產(chǎn)uiA1675314A2842727A35910619銷22131213vj142131261302sij = cij - ui - vj072-16令u1=0步驟55-4-2811由于存在小于零的檢驗數(shù)，故此方案也非最優(yōu)方案，還需進一步調(diào)整. 再次進入步驟(1)檢驗.B1B2B3B4產(chǎn)uiA1675314A2842727A35B1B2B3B4產(chǎn)A1675314A2842727A35910619銷221312131413136212130191步驟B1B2B3B4產(chǎn)A1675314A2842727A3591

18、B1B2B3B4產(chǎn)A1675314A2842727A35910619銷22131213又得到新的調(diào)整方案，重新檢驗.1132191312B1B2B3B4產(chǎn)A1675314A2842727A3591B1B2B3B4產(chǎn)uiA1675314A2842727A35910619銷22131213vj113213121902sij = cij - ui - vj032-16令u1=0B1B2B3B4產(chǎn)uiA1675314A2842727A35B1B2B3B4產(chǎn)uiA1675314A2842727A35910619銷22131213vj121312191302sij = cij - ui - vj032-16步驟5528114由于此時所有的檢驗數(shù)都大于0，則此時目標函數(shù)值最小Min