三、運輸問題

1、第三章 運輸問題,運輸問題的線性規(guī)劃模型 運輸問題的運輸表初始基礎可行解的求法最優(yōu)解的獲得幾種特殊的運輸問題,,,,,,運輸問題網(wǎng)絡圖,供應地,運價,需求地,供應量,需求量,總供應量60噸,總需求量60噸,供求平衡的運輸問題,1、運輸問題的一般提法,,問：如何合理調運，才能使總運費最少？,（供需平衡）,一、運輸問題線性規(guī)劃模型,,供應地約束,需求地約束,,,設Xij 為發(fā)點運往收點的運輸量.i=1,2,3 j=

2、1,2,3,4,minZ=9X11+18X12+X13+10X14+11X21+6X22+8X23+18X24+14X31+12X32+2X33+16X34,s.t X11+X12+X13+X14 = 9

3、 X21+X22+X23+X24 = 10

4、 X31+X32+X33+X34 = 6,X11 +X21 +X31

5、 = 4 X12 +X22 +X32 = 9 X13 +X23 +X33 = 7

6、 X14 +X24 +X34 = 5,X11 X12 X13 X14 X21 X22 X23 X24 X31 X32 X33 X34 ≥0,,,,,,,,,,,運輸問題線性規(guī)劃模型,Xij ≥0,s.t,2、運

7、輸模型的特點,,,由于前m個供應地約束和后n個需求地約束是線性相關的，因此運輸問題系數(shù)矩陣的秩<m+n。可以證明，運輸問題系數(shù)矩陣的秩為m+n-1,即基可行解只有m+n-1個變量,,3) 對偶問題,,,,2、運輸模型的特點,,,,,,,,,,,,,,,,,,,,Xij,σij,運價,檢驗數(shù),運量,二、 運輸表的表示,運輸問題的表格表示,運價,運量,,檢驗數(shù),,σij,運輸表中一個基必須具備的特點1、一個基應占表中的m+n-1格

8、;2、構成基的同行同列格子不能構成閉回路;3、一個基在表中所占的格子應包括表的每行和每列。,運輸表中一個基必須具備特點,基在運輸表中的表示,運輸表中同行同列的變量組成回路,1、西北角法2、最小元素法,三、初始基礎可行解的求法,1、西北角法,,8,13,13,14,6,6,,,,,2、最小元素法（1）,最小元素法（2）,最小元素法（3）,最小元素法（4）,最小元素法（5）,最小元素法（6）,閉回路——從調運方案的某一空格出發(fā)，沿水平

9、或垂直的方向前進，遇到一個適當?shù)臄?shù)字格便按與前進方向垂直的路徑前進。經(jīng)過若干次后，再回到原來出發(fā)的那個格，由此形成的封閉折線稱為閉回路。 閉回路的性質： 以空格出發(fā)的閉回路存在且唯一； 不存在所有頂點都為數(shù)字格的閉回路。,四、最優(yōu)解的獲得,1、檢驗數(shù)的求法：閉回路法,-5,,,,,非基變量xij的檢驗數(shù)zij-cij—閉回路法(1),算法：空格（i,j)的檢驗系數(shù)σij可表示為：由空格所作出的閉回路中所有偶數(shù)格對應的單位運價之和減

10、去所有 奇數(shù)格對應的單位運價之和的差。σ12=z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5,-5,,,,,σ13=z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5,-5,閉回路法(2),-5,,,,,z14-c14=(c11-c21+ c21 - c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7,-7,-5,,,閉回路法(3),-5,,,z24-c24=(c

11、23-c33+ c34)-c24=(2-10+6)-7=-9,-9,-5,,,-7,閉回路法(4),-5,,,z31-c31=(c21-c23+ c33)-c31=(8-2+10)-5=+11,+11,-5,,,-7,-9,閉回路法(5),-5,,,z32-c32=(c22-c23+ c33)-c32=(4-2+10)-9=+3,+3,-5,,,-7,-9,+11,閉回路法(6),（1）將具有最大正檢驗數(shù)的變量作為入基變量；（2）由入

12、基變量出發(fā)，找出一條閉合回路，在其偶數(shù)號中，取值最小的變量為出基變量；（3）運輸量的調整，對所有奇數(shù)號的變量都加上調整量的值，所有偶數(shù)號的變量減掉調整量的值；（4）在新的基礎可行解的基礎上重新計算檢驗數(shù)，直到所有的檢驗數(shù)都小于零。,2、進基和離基變量的選擇,x31進基, min{x21,x33}=min{8,6}=6, x33離基,+3,-5,-5,-7,-9,+11,,,,,例題，入基變量與進基變量的選擇,調整運量,重新計算檢驗數(shù)

13、,確定進基、離基變量,x14進基, min{x11,x34}=min{14,13}=13, x34離基,-11,-5,-5,+4,+2,-8,調整運量, 重新計算檢驗數(shù),所有zij-cij<0,得到最優(yōu)解。Min z=6×1+3 ×13+8 ×2+4 ×13+2 ×12+5 ×19=142,-11,-5,-5,-4,-8,-2,（一）產(chǎn)銷不平衡的運輸問題,1、供大于求,

14、,,,解決問題的思路：產(chǎn)銷不平衡→產(chǎn)銷平衡,,五、幾種特殊的運輸問題,供大于求，則虛設收地，運價為零,這樣就把供求不平衡問題轉化為供求平衡問題。,,,7,0,0,4,在新問題中，新得到的問題的最優(yōu)解，實際上就是各發(fā)地存儲多少、運出多少、運往何地，使總運價最低。,不平衡問題如左圖，相應的平衡問題如右圖,1525,,,1,,2,,1,,,2,,3,,,,,,,,10,10,10,3,,2,,,4,1,2,1,,,,,,,,,,0,0,

15、利用西北角法給出初始解,,,,15,10,0,0,25,,10,-2,-5,+6,X21進基，x22離基,,,,15,10,0,0,25,,10,+4,+1,-6,X13進基，x11離基,,,,15,10,0,0,25,,10,-4,-3,-2,2、供不應求,,,,,,,供不應求，則虛設發(fā)地，運價為零,,,,3,10,0,0,0,,,,,（二）無運輸通路,如：Ａ２至Ｂ３無運輸通路,,,無運輸通路，則運價為M,M,例題，從發(fā)點2到收點2沒

16、有路線，虛設一條通路，并設c22=M,,8-M,,X12進基，x22離基,,,X13進基，x11離基,,,（三）運輸問題的退化基礎可行解：基變量的個數(shù)小于m+n-1,,為了使基變量的個數(shù)保持m+n-1個，需要增加一個xij=0的基變量，但不能構成閉回路。,確定初始基礎可行解,西北角法,最小元素法,求非基變量的檢驗數(shù),閉回路法,確定進基變量,確定離基變量,得到新的基礎可行解,運輸問題單純形法總結,沿回路調整運量,35,6,38,4,22,

17、5,30,,,,,,,z=1428,例題：用西北角法得到初始基礎可行解,-3,z12-c12=(c11-c21+c22)-c12=(8-9+10)-12=-3,,,,,z=1428,用閉回路法求各非基變量的檢驗數(shù),35,6,38,4,22,5,30,-3,-2,,,,,用閉回路法求各非基變量的檢驗數(shù),35,6,38,4,22,5,30,-3,-2,-9,,,,,,,用閉回路法求各非基變量的檢驗數(shù),35,6,38,4,22,5,30,-3

18、,-2,-9,-11,,,,,用閉回路法求各非基變量的檢驗數(shù),35,6,38,4,22,5,30,-3,-2,-9,-11,+5,,,,,用閉回路法求各非基變量的檢驗數(shù),35,6,38,4,22,5,30,-3,-2,-9,-11,+5,+14,,,,,用閉回路法求各非基變量的檢驗數(shù),35,6,38,4,22,5,30,-3,-2,-9,-11,+5,+14,+9,,,,,,,用閉回路法求各非基變量的檢驗數(shù),35,6,38,4,22,5

19、,30,-3,-2,-9,-11,+5,+14,+9,+4,,,,,,,用閉回路法求各非基變量的檢驗數(shù),35,6,38,4,22,5,30,-3,-2,-9,-11,+5,+14,+9,+4,+2,,,,,用閉回路法求各非基變量的檢驗數(shù),35,6,38,4,22,5,30,-3,-2,-9,-11,+5,+14,+9,+4,+2,,,,,x32進基，x33離基,35,6,16,26,22,5,30,-3,-2,+5,+3,-9,-14,

20、-5,-10,-12,重新用閉回路法計算非基變量的檢驗數(shù),35,6,16,26,22,5,30,-3,-2,+5,+3,-9,-14,-5,-10,-12,x14進基，x34離基,,,,,,,30,11,11,26,27,5,30,-3,-2,-5,-2,-9,-14,0,-5,-7,重新計算各非基變量的檢驗數(shù),已獲得最優(yōu)解。x11=30，x14=5，x21=11，x22=11，x23=26，x32=27，x44=30，min z=10