運(yùn)輸問(wèn)題(運(yùn)籌學(xué))課件

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

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

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

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

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

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

7、路：首先計(jì)算每行和每列最小運(yùn)價(jià)與次小運(yùn)價(jià)之差，該數(shù)值稱為行罰數(shù)和列罰數(shù)，其含義為若不能按照最小運(yùn)價(jià)確定供求關(guān)系，就必須考慮次小運(yùn)價(jià)，這樣它們之間便產(chǎn)生運(yùn)費(fèi)的差額. 差額越大說(shuō)明如果不按照最小運(yùn)價(jià)確定供求關(guān)系運(yùn)輸，而是按照次小運(yùn)價(jià)由此所增加的運(yùn)費(fèi)越多，因而對(duì)差額最大處，應(yīng)該采用最小運(yùn)價(jià)調(diào)運(yùn).3、沃格爾法思路：首先計(jì)算每行和每列最小運(yùn)價(jià)與次小運(yùn)價(jià)之差，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目標(biāo)函數(shù)z=61 +82 +519 +413 +212 +313=232 .B1B2B3B4產(chǎn)行罰數(shù)A1675314A2842727A3通常來(lái)說(shuō)，沃格爾法所得到的初始調(diào)運(yùn)方案要比最小元素法所得到的優(yōu)，最小元素法得到的初始調(diào)運(yùn)方案又要比西北角法得到的優(yōu).通常來(lái)說(shuō)，沃格爾法所得到的初始調(diào)運(yùn)方案要比最小元素法所得到的B1B2B3B

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

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

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

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

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

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

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

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

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

18、B1B2B3B4產(chǎn)A1675314A2842727A35910619銷22131213又得到新的調(diào)整方案，重新檢驗(yàn).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í)所有的檢驗(yàn)數(shù)都大于0，則此時(shí)目標(biāo)函數(shù)值最小Min