第3章-運輸問題

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

2、量（需求量噸） 250 75 65 80 乙 200 100 70 90 甲 日產(chǎn)量日產(chǎn)量（供應量噸）（供應量噸） C B A 單位運價單位運價 城市城市 煤礦煤礦數(shù)學模型數(shù)學模型; 3 , 2 , 1; 2 , 1, 0200150100250200. .7565801007090min231322122111232221131211232221131211jixxxxxxxxxxxxxt sxxxxxxZij需求約束日產(chǎn)量約束總運費設xij是從第i產(chǎn)地到第j銷地的運輸量，則：100100010010001001111000000111單位單位 運價運價 銷銷 地地產(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銷銷 量量 b1 b2 bn njmixnjbxmiaxtsxcMinZijmijijnjiijminjijij,1;,1,0,1,1.1111minjjiba11產(chǎn)銷平衡條件 單純形法單純形法 表上作業(yè)法表上作業(yè)法（一）、確定初始調運方案（一）、確定初始調運方案（初始基本可行解）（初始基本可行解）； 方法：最小元素法、伏格爾（差值法）方法：最小元素法、伏格爾（差值法）（二）、求檢驗數(shù)判別是否為最優(yōu)方案；（二）、求檢驗數(shù)判別是否為最優(yōu)方案； 方法：閉回路法、位勢法方法：閉回路法、位

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

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

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

7、23 A3X31X32X34,212434331311xxxxxx差額=次小運價-最小運價差額的解釋：;差額大，則不按最小運費調運，運費增加大。差額大，則不按最小運費調運，運費增加大。;差額小，則不按最小運費調運，運費增加不大。差額小，則不按最小運費調運，運費增加不大。對差額最大處，采用最小運費調運。伏格爾法思路：2伏格爾法 結合例題說明這種方法。結合例題說明這種方法。4814121482210163214321AAABBBB4122854396111110銷量產(chǎn)量銷地銷地產(chǎn)地產(chǎn)地行差04-4=0第一次第一次4814121482210163214321AAABBBB41228543961111

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

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

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

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

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

13、到檢驗數(shù),0ij表中的解是最優(yōu)解。初始調運方案位勢變量對應表初始調運方案位勢變量對應表 調調 銷地銷地 運運 量量產(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 銷銷 量量 100 150 200 450位勢變量位勢變量vj v1 v2 v3100位勢位勢變量變量 ui u1 u27565100902332222213311111cvucvucvucvu例1中可得到方程組： 答案： （ij調調 銷地銷地 運運 量量產(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 銷銷 量量 100 150 200 450調調 銷地銷地 運運 量量產(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 銷銷 量量 100 150 200 450調調 銷地銷地 運運 量量產(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 銷銷 量量 100 150 200 450 得到了最優(yōu)方案 單純形法與表上作業(yè)法的對應關系：（1）找出初始基本可行解 （2）求各非基變量的檢驗數(shù)（3）判斷是否最優(yōu)解計算表中空格檢驗數(shù)表上給出m+n-1個數(shù)字格判斷方法j0換基：（4）確定進基變量和出基變量，找出新的基本可行解。（5）重復（2）（4）直至求出最優(yōu)解。表上調整（閉回路調整）（運輸問題必有最優(yōu)解）停止最優(yōu)解？是否例2：表上作業(yè)法完整步驟41228543961111104814121482210163214321AAABBBB銷量產(chǎn)量銷地產(chǎn)地1、最小元素法41228543961111104814121

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