第3章-運(yùn)輸問(wèn)題

1、 某種物資有若干產(chǎn)地和銷(xiāo)地，現(xiàn)某種物資有若干產(chǎn)地和銷(xiāo)地，現(xiàn)在需要把這種物資從各個(gè)產(chǎn)地運(yùn)到在需要把這種物資從各個(gè)產(chǎn)地運(yùn)到各個(gè)銷(xiāo)地。已知各產(chǎn)地的各個(gè)銷(xiāo)地。已知各產(chǎn)地的和各和各銷(xiāo)地的銷(xiāo)地的以及各產(chǎn)地到各銷(xiāo)地的以及各產(chǎn)地到各銷(xiāo)地的，問(wèn)應(yīng)如何組織調(diào)運(yùn)，才，問(wèn)應(yīng)如何組織調(diào)運(yùn)，才能使能使？例例1： 甲、乙兩個(gè)煤礦供應(yīng)甲、乙兩個(gè)煤礦供應(yīng)A、B、C三三個(gè)城市用煤，各煤礦產(chǎn)量（噸）及各個(gè)城市用煤，各煤礦產(chǎn)量（噸）及各城市需煤量（噸）、各煤礦到各城市城市需煤量（噸）、各煤礦到各城市的單位運(yùn)價(jià)（元的單位運(yùn)價(jià)（元/噸）見(jiàn)下表，求使總噸）見(jiàn)下表，求使總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。運(yùn)費(fèi)最少的調(diào)運(yùn)方案。 200 150 100 日銷(xiāo)

2、量（需求量噸） 250 75 65 80 乙 200 100 70 90 甲 日產(chǎn)量日產(chǎn)量（供應(yīng)量噸）（供應(yīng)量噸） C B A 單位運(yùn)價(jià)單位運(yùn)價(jià) 城市城市 煤礦煤礦數(shù)學(xué)模型數(shù)學(xué)模型; 3 , 2 , 1; 2 , 1, 0200150100250200. .7565801007090min231322122111232221131211232221131211jixxxxxxxxxxxxxt sxxxxxxZij需求約束日產(chǎn)量約束總運(yùn)費(fèi)設(shè)xij是從第i產(chǎn)地到第j銷(xiāo)地的運(yùn)輸量，則：100100010010001001111000000111單位單位 運(yùn)價(jià)運(yùn)價(jià) 銷(xiāo)銷(xiāo) 地地產(chǎn)地產(chǎn)地B1 B2 Bn產(chǎn)

3、產(chǎn) 量量A1 A2 Amc11 c12 c1 n c21 c22 c2n cm1 cm2 cm na1 a2 am銷(xiāo)銷(xiāo) 量量 b1 b2 bn njmixnjbxmiaxtsxcMinZijmijijnjiijminjijij,1;,1,0,1,1.1111minjjiba11產(chǎn)銷(xiāo)平衡條件 單純形法單純形法 表上作業(yè)法表上作業(yè)法（一）、確定初始調(diào)運(yùn)方案（一）、確定初始調(diào)運(yùn)方案（初始基本可行解）（初始基本可行解）； 方法：最小元素法、伏格爾（差值法）方法：最小元素法、伏格爾（差值法）（二）、求檢驗(yàn)數(shù)判別是否為最優(yōu)方案；（二）、求檢驗(yàn)數(shù)判別是否為最優(yōu)方案； 方法：閉回路法、位勢(shì)法方法：閉回路法、位

4、勢(shì)法（三）、若不是最優(yōu)，則需要調(diào)整現(xiàn)有方案，以得（三）、若不是最優(yōu)，則需要調(diào)整現(xiàn)有方案，以得到新的調(diào)運(yùn)方案。到新的調(diào)運(yùn)方案。 方法：閉回路調(diào)整方法：閉回路調(diào)整（四）、不斷反復(fù)，最終得到最優(yōu)調(diào)運(yùn)方案。（四）、不斷反復(fù)，最終得到最優(yōu)調(diào)運(yùn)方案。基本步驟：基本步驟：（一）、確定初始基本可行解1、最小元素法 最小元素法思路： 從單價(jià)中最小運(yùn)價(jià)確定供應(yīng)量 “就近供應(yīng)”例2、某部門(mén)三個(gè)工廠生產(chǎn)同一產(chǎn)品的產(chǎn)量、 四個(gè)銷(xiāo)售點(diǎn)的銷(xiāo)量及單位運(yùn)價(jià)如下表：41228543961111104814121482210163214321AAABBBB銷(xiāo)量產(chǎn)量銷(xiāo)地產(chǎn)地最小元素法4122854396111110481412148

5、2210163214321AAABBBB銷(xiāo)量產(chǎn)量銷(xiāo)地產(chǎn)地822010100614868000060最小元素法初始運(yùn)輸方案：41228543961111104814121482210163214321AAABBBB銷(xiāo)量產(chǎn)量銷(xiāo)地產(chǎn)地821014682466811632410514280z最小元素法缺點(diǎn)：會(huì)出現(xiàn)顧此失彼 （運(yùn)價(jià)差額問(wèn)題）考慮運(yùn)價(jià)差 200 150 100 日銷(xiāo)量（需求量噸） 250 75 65 80 乙 200 100 70 90 甲 日產(chǎn)量日產(chǎn)量（供應(yīng)量噸）（供應(yīng)量噸） C B A 單位運(yùn)價(jià)單位運(yùn)價(jià) 城市城市 煤礦煤礦例1：運(yùn)輸問(wèn)題基本可行解的特點(diǎn)：運(yùn)輸問(wèn)題基本可行解的特點(diǎn)： 45

6、0 200 150 100 日銷(xiāo)量（需求量噸） 250 10075 1506580 乙 200 100100 70 10090 甲 日產(chǎn)量日產(chǎn)量（供應(yīng)量噸）（供應(yīng)量噸） C B A 單位運(yùn)費(fèi)單位運(yùn)費(fèi) 城市城市 煤礦煤礦特點(diǎn)分析：基變量（數(shù)字格）、非基變量（空格）特點(diǎn)分析：基變量（數(shù)字格）、非基變量（空格）運(yùn)輸問(wèn)題基本可行解的特點(diǎn)：運(yùn)輸問(wèn)題基本可行解的特點(diǎn)： X11X13X21X24X33 B1 B2 B3 B4 A1X12X14 A2X22X23 A3X31X32X34,313424231311xxxxxx X11X13X21X24X33 B1 B2 B3 B4 A1X12X14 A2X22X

7、23 A3X31X32X34,212434331311xxxxxx差額=次小運(yùn)價(jià)-最小運(yùn)價(jià)差額的解釋?zhuān)?差額大，則不按最小運(yùn)費(fèi)調(diào)運(yùn)，運(yùn)費(fèi)增加大。差額大，則不按最小運(yùn)費(fèi)調(diào)運(yùn)，運(yùn)費(fèi)增加大。;差額小，則不按最小運(yùn)費(fèi)調(diào)運(yùn)，運(yùn)費(fèi)增加不大。差額小，則不按最小運(yùn)費(fèi)調(diào)運(yùn)，運(yùn)費(fèi)增加不大。對(duì)差額最大處，采用最小運(yùn)費(fèi)調(diào)運(yùn)。伏格爾法思路：2伏格爾法 結(jié)合例題說(shuō)明這種方法。結(jié)合例題說(shuō)明這種方法。4814121482210163214321AAABBBB4122854396111110銷(xiāo)量產(chǎn)量銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地行差04-4=0第一次第一次4814121482210163214321AAABBBB41228543961111

8、10銷(xiāo)量產(chǎn)量銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地行差013-2=1第一次第一次4814121482210163214321AAABBBB4122854396111110銷(xiāo)量產(chǎn)量銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地行差011第一次第一次4814121482210163214321AAABBBB4122854396111110銷(xiāo)量產(chǎn)量銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地行差011列差4-2=22153第一次第一次4814121482210163214321AAABBBB4122854396111110銷(xiāo)量產(chǎn)量銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地行差011列差21531480優(yōu)先安排銷(xiāo)地，否則運(yùn)價(jià)會(huì)更高2B下次不考慮該列第一次第一次第二次第二次行差012列差213優(yōu)先安排銷(xiāo)地，

9、否則運(yùn)價(jià)會(huì)更高4B84814121482210163214321AAABBBB4122854396111110銷(xiāo)量產(chǎn)量銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地148006下次不考慮該行行差01列差21284814121482210163214321AAABBBB4122854396111110銷(xiāo)量產(chǎn)量銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地148006下次不考慮該列802第三次第三次行差76列差1284814121482210163214321AAABBBB4122854396111110銷(xiāo)量產(chǎn)量銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地1480068024120下次不考慮該列第四次第四次行差00列差2284814121482210163214321AAABBBB4

10、122854396111110銷(xiāo)量產(chǎn)量銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地148006802412004第五次第五次4 用伏格爾法得到的初始基本可行解4814121482210163214321AAABBBB4122854396111110銷(xiāo)量產(chǎn)量銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地48148122244685149228114412z目標(biāo)函數(shù)值目標(biāo)函數(shù)值用最小元素法求出的目標(biāo)函數(shù)z=246練習(xí)練習(xí)1：最小元素法、伏格爾法求初：最小元素法、伏格爾法求初始運(yùn)輸方案始運(yùn)輸方案.收收點(diǎn)點(diǎn)發(fā)發(fā)點(diǎn)點(diǎn)B1B2B3B4發(fā)發(fā)量量A16533414A24244756A376583 3收收量量243413 若在（i,j）格填入數(shù)字后，出現(xiàn)ai處的供應(yīng)量

11、正好等于bj 處的需求量。這時(shí)在產(chǎn)銷(xiāo)平衡表上填一個(gè)數(shù)，而在單位運(yùn)價(jià)表上相應(yīng)要?jiǎng)澣ヒ恍泻鸵涣?。為使產(chǎn)銷(xiāo)平衡表上有（m+n-1）個(gè)數(shù)字格，需要添加一個(gè)“0”。它的位置可在對(duì)應(yīng)同時(shí)劃去的行或列得任一空格處。特殊情況處理： （判別定理：檢驗(yàn)數(shù)全部大于或等于0，即為最優(yōu)。檢驗(yàn)數(shù)計(jì)算方法：檢驗(yàn)數(shù)計(jì)算方法：ij例例1：在最小元素法確定的初始調(diào)運(yùn)方案的基：在最小元素法確定的初始調(diào)運(yùn)方案的基礎(chǔ)上，計(jì)算非基變量的檢驗(yàn)數(shù)礎(chǔ)上，計(jì)算非基變量的檢驗(yàn)數(shù) ：1221例2：最小元素法得到的初始方案，試計(jì)算檢驗(yàn)數(shù)。41228543961111104814121482210163214321AAABBBB銷(xiāo)量產(chǎn)量銷(xiāo)地產(chǎn)地8210

12、14682466811632410514280z閉回路法計(jì)算檢驗(yàn)數(shù)41228543961111104814121482210163214321AAABBBB銷(xiāo)量產(chǎn)量銷(xiāo)地產(chǎn)地82101468211-11012,0124表中的解不是最優(yōu)解。用伏格爾法得到的初始運(yùn)輸方案：4814121482210163214321AAABBBB4122854396111110銷(xiāo)量產(chǎn)量銷(xiāo)地銷(xiāo)地產(chǎn)地產(chǎn)地48148122244685149228114412z目標(biāo)函數(shù)值目標(biāo)函數(shù)值41228543961111104814121482210163214321AAABBBB銷(xiāo)量產(chǎn)量銷(xiāo)地產(chǎn)地821214482209112閉回路法得

13、到檢驗(yàn)數(shù),0ij表中的解是最優(yōu)解。初始調(diào)運(yùn)方案位勢(shì)變量對(duì)應(yīng)表初始調(diào)運(yùn)方案位勢(shì)變量對(duì)應(yīng)表 調(diào)調(diào) 銷(xiāo)地銷(xiāo)地 運(yùn)運(yùn) 量量產(chǎn)地產(chǎn)地 B1 B2 B3產(chǎn)產(chǎn) 量量 A1 90 X11=100 70 X12 100X13=100 200 A2 80 X21 65 X22=150 75X23=100 250 銷(xiāo)銷(xiāo) 量量 100 150 200 450位勢(shì)變量位勢(shì)變量vj v1 v2 v3100位勢(shì)位勢(shì)變量變量 ui u1 u27565100902332222213311111cvucvucvucvu例1中可得到方程組： 答案： （ij調(diào)調(diào) 銷(xiāo)地銷(xiāo)地 運(yùn)運(yùn) 量量產(chǎn)地產(chǎn)地 B1 B2 B3 產(chǎn)產(chǎn) 量量 A1 90

14、 X11=100 7012 = -20 100 X13=100 200 A2 80 21=15 65 X22=150 75 X23=100 250 銷(xiāo)銷(xiāo) 量量 100 150 200 450調(diào)調(diào) 銷(xiāo)地銷(xiāo)地 運(yùn)運(yùn) 量量產(chǎn)地產(chǎn)地 B1 B2 B3 產(chǎn)產(chǎn) 量量 A1 90 X11=100 70X12 = 100 100 200 A2 80 65 X22=50 75 X23=200 250 銷(xiāo)銷(xiāo) 量量 100 150 200 450調(diào)調(diào) 銷(xiāo)地銷(xiāo)地 運(yùn)運(yùn) 量量產(chǎn)地產(chǎn)地 B1 B2 B3 產(chǎn)產(chǎn) 量量 A1 90 X11=50 70 X12=150 100 X13 200 A2 80 X21=50 65 X

15、22 75 X23=200 250 銷(xiāo)銷(xiāo) 量量 100 150 200 450 得到了最優(yōu)方案 單純形法與表上作業(yè)法的對(duì)應(yīng)關(guān)系：（1）找出初始基本可行解 （2）求各非基變量的檢驗(yàn)數(shù)（3）判斷是否最優(yōu)解計(jì)算表中空格檢驗(yàn)數(shù)表上給出m+n-1個(gè)數(shù)字格判斷方法j0換基：（4）確定進(jìn)基變量和出基變量，找出新的基本可行解。（5）重復(fù)（2）（4）直至求出最優(yōu)解。表上調(diào)整（閉回路調(diào)整）（運(yùn)輸問(wèn)題必有最優(yōu)解）停止最優(yōu)解？是否例2：表上作業(yè)法完整步驟41228543961111104814121482210163214321AAABBBB銷(xiāo)量產(chǎn)量銷(xiāo)地產(chǎn)地1、最小元素法41228543961111104814121

16、482210163214321AAABBBB銷(xiāo)量產(chǎn)量銷(xiāo)地產(chǎn)地821014682466811632410514280z2、檢驗(yàn)數(shù)表41228543961111104814121482210163214321AAABBBB銷(xiāo)量產(chǎn)量銷(xiāo)地產(chǎn)地82101468211-11012,0124表中的解不是最優(yōu)解。3、解的調(diào)整 調(diào)整位置（2，4）非空，回路角上的格至少為空，且保證數(shù)字的非負(fù)性。41228543961111104814121482210163214321AAABBBB銷(xiāo)量產(chǎn)量銷(xiāo)地產(chǎn)地82101468-1（-2）（-2）（+2）（+2） 調(diào)整后的解為：41228543961111104814121482210163214321AAABBBB銷(xiāo)量產(chǎn)量銷(xiāo)地產(chǎn)地8212144822091122246244689211441251428, 0zij此時(shí)的解為最優(yōu)解。 觀察檢驗(yàn)數(shù)41228543961111104814121482210163214321AAABBBB銷(xiāo)量產(chǎn)量銷(xiāo)地產(chǎn)地821214482209112有多個(gè)最優(yōu)解 另一最優(yōu)運(yùn)輸方案為：41228543961111104814121482210163214321AAABBBB銷(xiāo)量產(chǎn)量銷(xiāo)地產(chǎn)地82121448（+4）（-4）（+4）（-4） 即：41228543961111104814121482210163214321AA