三、運(yùn)輸問題

1、第三章 運(yùn)輸問題,運(yùn)輸問題的線性規(guī)劃模型 運(yùn)輸問題的運(yùn)輸表初始基礎(chǔ)可行解的求法最優(yōu)解的獲得幾種特殊的運(yùn)輸問題,,,,,,運(yùn)輸問題網(wǎng)絡(luò)圖,供應(yīng)地,運(yùn)價,需求地,供應(yīng)量,需求量,總供應(yīng)量60噸,總需求量60噸,供求平衡的運(yùn)輸問題,1、運(yùn)輸問題的一般提法,,問：如何合理調(diào)運(yùn)，才能使總運(yùn)費(fèi)最少？,（供需平衡）,一、運(yùn)輸問題線性規(guī)劃模型,,供應(yīng)地約束,需求地約束,,,設(shè)Xij 為發(fā)點(diǎn)運(yùn)往收點(diǎn)的運(yùn)輸量.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,,,,,,,,,,,運(yùn)輸問題線性規(guī)劃模型,Xij ≥0,s.t,2、運(yùn)

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

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

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

10、去所有 奇數(shù)格對應(yīng)的單位運(yùn)價之和的差。σ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）將具有最大正檢驗(yàn)數(shù)的變量作為入基變量；（2）由入

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

13、,確定進(jìn)基、離基變量,x14進(jìn)基, min{x11,x34}=min{14,13}=13, x34離基,-11,-5,-5,+4,+2,-8,調(diào)整運(yùn)量, 重新計(jì)算檢驗(yàn)數(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)銷不平衡的運(yùn)輸問題,1、供大于求,

14、,,,解決問題的思路：產(chǎn)銷不平衡→產(chǎn)銷平衡,,五、幾種特殊的運(yùn)輸問題,供大于求，則虛設(shè)收地，運(yùn)價為零,這樣就把供求不平衡問題轉(zhuǎn)化為供求平衡問題。,,,7,0,0,4,在新問題中，新得到的問題的最優(yōu)解，實(shí)際上就是各發(fā)地存儲多少、運(yùn)出多少、運(yùn)往何地，使總運(yùn)價最低。,不平衡問題如左圖，相應(yīng)的平衡問題如右圖,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進(jìn)基，x22離基,,,,15,10,0,0,25,,10,+4,+1,-6,X13進(jìn)基，x11離基,,,,15,10,0,0,25,,10,-4,-3,-2,2、供不應(yīng)求,,,,,,,供不應(yīng)求，則虛設(shè)發(fā)地，運(yùn)價為零,,,,3,10,0,0,0,,,,,（二）無運(yùn)輸通路,如：Ａ２至Ｂ３無運(yùn)輸通路,,,無運(yùn)輸通路，則運(yùn)價為M,M,例題，從發(fā)點(diǎn)2到收點(diǎn)2沒

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

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

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

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

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