運籌學3運輸問題

1、運輸規(guī)劃問題的數(shù)學模型運輸規(guī)劃問題的數(shù)學模型表上作業(yè)法表上作業(yè)法運輸問題的應(yīng)用運輸問題的應(yīng)用 例例3.1 某公司從兩個產(chǎn)地某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地將物品運往三個銷地B1, B2, B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最??？?。緽1B2B3產(chǎn)量產(chǎn)量A1646200A2655300銷量銷量150150200解：產(chǎn)銷平衡問題：總產(chǎn)量解：產(chǎn)銷平衡問題：總產(chǎn)量 = 總銷量總銷量500 設(shè)設(shè) xij 為從產(chǎn)地為從產(chǎn)地A

2、i運往銷地運往銷地Bj的運輸量，得到下列運輸量的運輸量，得到下列運輸量表：表：B1B2B3產(chǎn)量產(chǎn)量A1x11x12x13200A2x21x22x23300銷量銷量150150200Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3）運輸問題的一般形式：產(chǎn)銷平衡運輸問題的一般形式：產(chǎn)銷平衡A1、 A2、 Am 表示某物資的表

3、示某物資的m個產(chǎn)地；個產(chǎn)地； B1、B2、Bn 表示表示某物質(zhì)的某物質(zhì)的n個銷地；個銷地；ai 表示產(chǎn)地表示產(chǎn)地Ai的產(chǎn)量；的產(chǎn)量； bj 表示銷地表示銷地Bj 的銷量；的銷量； cij 表示把物資從產(chǎn)地表示把物資從產(chǎn)地Ai運往銷地運往銷地Bj的單位運價。設(shè)的單位運價。設(shè) xij 為從產(chǎn)地為從產(chǎn)地Ai運往銷地運往銷地Bj的運輸量，得到下列一般運輸量問題的模型：的運輸量，得到下列一般運輸量問題的模型： minjijijxcz11min111,.1,0,1,;1,nijijmijjiijxaims txbjnxim jnLLLL 已知資料如下：已知資料如下： 銷銷產(chǎn)產(chǎn) 地地 地地產(chǎn)產(chǎn) 量量1nB

4、BL1mA AM1ma aM1nb bL1 111nmm nc c c cLMMLnijjm1iiba產(chǎn)銷平衡產(chǎn)銷平衡銷銷 量量運價運價的單位運價到為ijijijBAc ) ( 0min11ijjijijiijminjijijxbabxaxxcZ當當產(chǎn)銷平衡產(chǎn)銷平衡時，其模型如下：時，其模型如下：當當產(chǎn)大于銷產(chǎn)大于銷時，其模型如下：時，其模型如下： ) ( 0min11ijjijijiijminjijijxbabxaxxcZ當當產(chǎn)小于銷產(chǎn)小于銷時，其模型如下：時，其模型如下：0, 0, 0)(0min ijjijjiijjijiijijijcbabaxbxaxxcZ并假設(shè)：并假設(shè)： 特征：特征

5、： 1、平衡運輸問題必有可行解，也必有最優(yōu)解；、平衡運輸問題必有可行解，也必有最優(yōu)解； 2、運輸問題的基本可行解中應(yīng)包括、運輸問題的基本可行解中應(yīng)包括 m+n1 個基變量。個基變量。運輸問題約束條件的系數(shù)矩陣運輸問題約束條件的系數(shù)矩陣111111111111111111 L LL LO OL LO OO OO OO Onnmmm nxxxxxxxxx111212122212L LL LL LL Lmn銷銷 產(chǎn)產(chǎn) B1 B2 Bn 產(chǎn)產(chǎn)量量 c11 c12 c1n A1 x11 x12 x1n a1 c21 c22 c2n A2 x21 x22 x2n a2 cm1 cm2 cmn Am xm1

6、 xm2 xmn am 銷銷量量 b1 b1 bn 平平衡衡表表、運運價價表表合合二二為為一一：基本可行解是否最優(yōu)解結(jié)束換基是否 運輸問題的求解思路 計算步驟：計算步驟：(1) 找出初始調(diào)運方案。即在找出初始調(diào)運方案。即在(mn)產(chǎn)銷平衡表上給出產(chǎn)銷平衡表上給出m+n-1個數(shù)字格。個數(shù)字格。(最小元素法、西北角法或伏格爾法）最小元素法、西北角法或伏格爾法）(2) 求檢驗數(shù)。（閉回路法或位勢法）求檢驗數(shù)。（閉回路法或位勢法） 判別是否達到最優(yōu)判別是否達到最優(yōu)解。如已是最優(yōu)解，則停止計算，否則轉(zhuǎn)到下一步。解。如已是最優(yōu)解，則停止計算，否則轉(zhuǎn)到下一步。(3) 對方案進行改善，找出新的調(diào)運方案。（表上

7、閉回對方案進行改善，找出新的調(diào)運方案。（表上閉回路法調(diào)整）路法調(diào)整）確定確定m+n-1個基變量個基變量 (4) 重復（重復（2）、（）、（3），直到求得最優(yōu)調(diào)運方案。），直到求得最優(yōu)調(diào)運方案?？崭窨崭穸?、表上作業(yè)法二、表上作業(yè)法表上作業(yè)法是一種求解運輸問題的特殊方法，其表上作業(yè)法是一種求解運輸問題的特殊方法，其實質(zhì)是單純實質(zhì)是單純形法。形法。步驟步驟描述描述方法方法第一步第一步求初始基行可行解（初始調(diào)運方案）求初始基行可行解（初始調(diào)運方案）最小元素法、最小元素法、西北角法、西北角法、伏格爾法伏格爾法第二步第二步求檢驗數(shù)并判斷是否得到最優(yōu)解當非基變量的求檢驗數(shù)并判斷是否得到最優(yōu)解當非基變量的檢驗

8、數(shù)檢驗數(shù) i j i j全都非負全都非負( (求求min)min)時得到最優(yōu)解，若時得到最優(yōu)解，若存在檢驗數(shù)存在檢驗數(shù) i j i j 00，說明還沒有達到最優(yōu)，轉(zhuǎn)，說明還沒有達到最優(yōu)，轉(zhuǎn)第三步。第三步。閉回路法和位閉回路法和位勢法勢法第三步第三步調(diào)整運量，即換基，選一個變量出基，對原運調(diào)整運量，即換基，選一個變量出基，對原運量進行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步量進行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步例例3.2 3.2 某運輸資料如下表所示：某運輸資料如下表所示：單位單位 銷地銷地 運價運價 產(chǎn)地產(chǎn)地產(chǎn)量產(chǎn)量3 311113 310107 71 19 92 28 84 47 74 410105

9、 59 9銷量銷量3 36 65 56 64321 BBBB321AAA問：應(yīng)如何調(diào)運可使總運輸費用最??？問：應(yīng)如何調(diào)運可使總運輸費用最??？1 1、求初始方案：、求初始方案：最小元素法、西北角法、伏格爾法最小元素法、西北角法、伏格爾法 基本思想是就近供應(yīng)，即從運價最小的地方開始供應(yīng)（調(diào)基本思想是就近供應(yīng)，即從運價最小的地方開始供應(yīng)（調(diào)運），然后次小，直到最后供完為止。運），然后次小，直到最后供完為止。B1B2B3B4產(chǎn)量產(chǎn)量A17A2 4A39銷量銷量3656311310192741058總的運輸費總的運輸費(31)+(64) +(43) +(12)+(310)+(35)=86元元方法方法1：

10、最小元素法：最小元素法341633練習練習 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A1675314A2842727A35910619銷量銷量221312131213131912 （2）西北角法（或左上角法）西北角法（或左上角法）此法是純粹的人為的規(guī)定，沒有理論依據(jù)和實際背景，但此法是純粹的人為的規(guī)定，沒有理論依據(jù)和實際背景，但它易操作，特別適合在計算機上編程計算，因而受歡迎。它易操作，特別適合在計算機上編程計算，因而受歡迎。方法如下：方法如下：3 6 5 63 6 5 67 7 4 4 9 93 34 4 4 4 9 90 6 5 60 6 5 64 40 0 4 4 9 90 2 5 60

11、 2 5 62 20 0 2 2 9 90 0 5 60 0 5 62 20 0 0 0 9 90 0 3 60 0 3 63 63 60 0 0 00 0 0 00 0 0 0 0 03 4 0 03 4 0 00 2 2 00 2 2 00 0 3 60 0 3 6在滿足約束條件下盡可能的給最左上角的變量最大值在滿足約束條件下盡可能的給最左上角的變量最大值. 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A141241116A22103910A38511622銷量銷量8141214488864814所以，初始基可行解為：所以，初始基可行解為：(8,8,4,8,14)目標函數(shù)值目標函數(shù)值Z372例

12、例3.3 3.3 某運輸資料如下表所示：某運輸資料如下表所示：練習練習 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A1675314A2842727A35910619銷量銷量22131213813131466 最小元素法的最小元素法的缺點缺點是：為了節(jié)省一處的費用，有時造成在其他處是：為了節(jié)省一處的費用，有時造成在其他處要多花幾倍的運費。伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最要多花幾倍的運費。伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運費就近供應(yīng)，就考慮次小運費，這就有一個差額。差額越大，小運費就近供應(yīng)，就考慮次小運費，這就有一個差額。差額越大，說明不能按最小運費調(diào)運時，運費增加越多。因而對差額

13、最大處，說明不能按最小運費調(diào)運時，運費增加越多。因而對差額最大處，就應(yīng)當采用最小運費調(diào)運。就應(yīng)當采用最小運費調(diào)運。例如下面兩種運輸方案。例如下面兩種運輸方案。 最小元素法：最小元素法：15152012105815510總運費是總運費是z=108+52+151=10515152012105851510另一種方法：另一種方法：總運費總運費z=105+152+51=85方法方法2：Vogel法法1）從運價表中分別計算出各行和各列的最小運費和次最小運）從運價表中分別計算出各行和各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行。費的差額，并填入該表的最右列和最下行。B1B2B3B4產(chǎn)量產(chǎn)量A

14、17A2 4A39銷量銷量365631131019274105810-3=72-1=15-4=13-1=29-4=53-2=18-5=32）再從差值最大的行或列中找出最小運價確定供需關(guān)系和）再從差值最大的行或列中找出最小運價確定供需關(guān)系和供需數(shù)量。當產(chǎn)地或銷地中有一方數(shù)量供應(yīng)完畢或得到滿足供需數(shù)量。當產(chǎn)地或銷地中有一方數(shù)量供應(yīng)完畢或得到滿足時，劃去運價表中對應(yīng)的行或列。時，劃去運價表中對應(yīng)的行或列。重復重復1)和和2)，直到找出初始解為至。，直到找出初始解為至。B1B2B3B4產(chǎn)量產(chǎn)量A17A2 4A3 9銷量銷量3656311310192741058單位單位 銷地銷地 運價運價 產(chǎn)地產(chǎn)地產(chǎn)量

15、產(chǎn)量行差額行差額311310719284741059銷量銷量3656列差額列差額4321 BBBB321AAA71352753單位單位 銷地銷地 運價運價 產(chǎn)地產(chǎn)地產(chǎn)量產(chǎn)量行差額行差額311310719284741059銷量銷量3656列差額列差額4321 BBBB321AAA11351536312該方案的總運費該方案的總運費:(13)(46)(35)(210)(18)(35)85元元 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量行差額行差額A1412411160A221039101A385116221銷量銷量814121448列差額列差額251314所以，初始基可行解為：目標函數(shù)值Z244例例3

16、.4 3.4 某運輸資料如下表所示：某運輸資料如下表所示： 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量行差額行差額A1412411160A221039101A385116221銷量銷量814121448列差額列差額21314所以，初始基可行解為：目標函數(shù)值Z2448例例3.4 3.4 某運輸資料如下表所示：某運輸資料如下表所示： 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量行差額行差額A1412411160A221039101A385116221銷量銷量814121448列差額列差額21314所以，初始基可行解為：目標函數(shù)值Z24488例例3.4 3.4 某運輸資料如下表所示：某運輸資料如下表所示：

17、 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量行差額行差額A1412411160A221039101A38511622銷量銷量814121448列差額列差額1314所以，初始基可行解為：目標函數(shù)值Z24488例例3.4 3.4 某運輸資料如下表所示：某運輸資料如下表所示：12 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量行差額行差額A1412411160A221039101A38511622銷量銷量814121448列差額列差額314所以，初始基可行解為：目標函數(shù)值Z24488例例3.4 3.4 某運輸資料如下表所示：某運輸資料如下表所示：1224練習練習 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A1

18、675314A2842727A35910619銷量銷量2213121312131213192、 最優(yōu)解的判別（檢驗數(shù)的求法）最優(yōu)解的判別（檢驗數(shù)的求法）求檢驗數(shù)的方法有兩種：求檢驗數(shù)的方法有兩種： 閉回路法閉回路法 對偶變量法（位勢法）對偶變量法（位勢法） （1 1）閉合回路法：）閉合回路法： ij ij0 0 （因為目標函數(shù)要求最小化）（因為目標函數(shù)要求最小化） 表格中有調(diào)運量的地方為基變量，空格處為非基變量。表格中有調(diào)運量的地方為基變量，空格處為非基變量?；兞康臋z驗數(shù)基變量的檢驗數(shù) ij ij0 0，非基變量的檢驗數(shù)，非基變量的檢驗數(shù) ij ij00。 ij ij 0 0 0 表示運費增

19、加。表示運費增加。 閉回路：從空格出發(fā)順時針閉回路：從空格出發(fā)順時針( (或逆時針或逆時針) )畫水平畫水平( (或垂直或垂直) )直線，遇到填有運量的方格可轉(zhuǎn)直線，遇到填有運量的方格可轉(zhuǎn)9090，然后繼續(xù)前進，直到，然后繼續(xù)前進，直到到達出發(fā)的空格所形成的閉合回路。到達出發(fā)的空格所形成的閉合回路。調(diào)運方案的任意空格存在唯一閉回路。調(diào)運方案的任意空格存在唯一閉回路。注：注：1.1.每一空格有且僅有一條閉回路；每一空格有且僅有一條閉回路； 2.2.如果某數(shù)字格有閉回路，則此解不是可行解。如果某數(shù)字格有閉回路，則此解不是可行解。mnmnzzxxxx0111112122121 L Lm nxxxzz

20、11121101,0 L L若令則運費的增量運費的增量分析：分析：以最小元素法的初始解為例。假設(shè)產(chǎn)地以最小元素法的初始解為例。假設(shè)產(chǎn)地A1供應(yīng)供應(yīng)1個單位的個單位的物品給銷地物品給銷地B1。則解的變化和目標函數(shù)的變化如何。則解的變化和目標函數(shù)的變化如何。 銷地銷地產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量A141241116106A2210391082A38511622148銷量銷量814121448要保證產(chǎn)銷平衡，則要保證產(chǎn)銷平衡，則1, 12344110zz111121231311xxxx 稱為閉回路 21231311xxxx 銷地銷地產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量A141241116106A

21、2210391082A38511622148銷量銷量8141214481 銷地銷地產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量A141241116106A2210391082A38511622148銷量銷量81412144812561112122 銷地銷地產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量A141241116106A2210391082A38511622148銷量銷量81412144811561143102221 銷地銷地產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量A141241116106A2210391082A38511622148銷量銷量8141214481031823411610 211 銷地銷地產(chǎn)地產(chǎn)地

22、 B1B2B3B4產(chǎn)量產(chǎn)量A141241116106A2210391082A38511622148銷量銷量81412144813311411612 211210 銷地銷地產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量A141241116106A2210391082A38511622148銷量銷量814121448124934111 21-11210檢驗數(shù)中有檢驗數(shù)中有負數(shù)負數(shù)，說明原方案不是最優(yōu)解。，說明原方案不是最優(yōu)解。練習練習 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A167531414A28427278136A35910619613銷量銷量221312135579-3-11 uivjm個個 n個個（

23、2 2）對偶變量法（位勢法）對偶變量法（位勢法）設(shè)其對偶變量為：設(shè)其對偶變量為：mnYu uuv vv1212(,.,.,) uivj無約束無約束 （i=1,2, ,m;j=1,2, ,n)標準型運輸問題的對偶問題模型為：標準型運輸問題的對偶問題模型為：1maxnijjjmiiivbuaw=+=ijjicvu則運輸問題變量則運輸問題變量xij的檢驗數(shù)為：的檢驗數(shù)為：ijijijijijijmnijijijczcYPcuuuvvvPcuv1212(, ., .,)() 用位勢法對初始方案進行最優(yōu)性檢驗的方法：用位勢法對初始方案進行最優(yōu)性檢驗的方法：1）在給定初始解的表上增加一行和一列，在列中填入

24、）在給定初始解的表上增加一行和一列，在列中填入ui，在，在行中填入行中填入vj。2）令）令u10，再按，再按cij-(ui+vj)=0（基變量的（基變量的cij求出其余的求出其余的ui與與vj。3）由）由 i j=Ci j -（ui+vj），求出非基變量的檢驗數(shù)。），求出非基變量的檢驗數(shù)。B1B2B3B4uiA1A2A3vj311310192741058注意：基變量的檢驗數(shù)注意：基變量的檢驗數(shù) i j=Ci j -（ui+vj）=0436313B1B2B3B4uiA1A2A3vj311310192741058令令u1=0u1+v3=3u1+ v4 =10u2+ v3=2u2+v1=1u3+v2

25、=4u3+ v4=543631321039vj-5A3-1A20A1uiB4B3B2B1436313當存在非基變量的檢驗數(shù)當存在非基變量的檢驗數(shù) ij 0，說明現(xiàn)行方案，說明現(xiàn)行方案為最優(yōu)方案，否則目標成本還可以進一步減小。為最優(yōu)方案，否則目標成本還可以進一步減小。注意：非基變量的檢驗數(shù)注意：非基變量的檢驗數(shù) i j=ci j -（ui+vj） 11=c11 -（u1+v1）=3-(0+2)=1 31=c31 -（u3+v1）=7-(2-5)=10 24=c24 -（u2+v4）=8-(10-1)=-1 22=c22 -（u2+v2）=9-(9-1)=1 12=c12 -（u1+v2）=11-

26、(0+9)=2 33=c33 -（u3+v3）=10-(3-5)=123113101927410583、 解的改進解的改進 閉合回路調(diào)整法（原理同單純形法一樣）閉合回路調(diào)整法（原理同單純形法一樣） 當在表中空格處出現(xiàn)當在表中空格處出現(xiàn)負檢驗數(shù)負檢驗數(shù)時，表明未得最優(yōu)解。時，表明未得最優(yōu)解。若有兩個或兩個以上的負檢驗數(shù)時，一般選用其中最小的若有兩個或兩個以上的負檢驗數(shù)時，一般選用其中最小的負檢驗數(shù)，以它對應(yīng)的空格為調(diào)入格，即以它對應(yīng)的非基負檢驗數(shù)，以它對應(yīng)的空格為調(diào)入格，即以它對應(yīng)的非基變量為換入變量。做一閉合回路。變量為換入變量。做一閉合回路。( 1 ) 確定換入基的變量：確定換入基的變量：當

27、存在非基變量的檢驗數(shù)當存在非基變量的檢驗數(shù) kl 0 且且 kl =min ij時，時，以以Xkl為換入變量，找出它在運輸表中為換入變量，找出它在運輸表中的閉合回路。的閉合回路。接上例：接上例：pqijj , i)(min 0Xpq=X24為換入變量為換入變量解的改進的具體步驟：解的改進的具體步驟：21039vj-5A3-1A20A1uiB4B3B2B1436313311310192741058( 2 ) 頂點編號：以空格頂點編號：以空格(Ak,Bl)(或進基變量或進基變量xik）為第一個）為第一個奇數(shù)頂點，沿閉回路的順（或逆）時針方向前進，對閉回奇數(shù)頂點，沿閉回路的順（或逆）時針方向前進，對

28、閉回路上的頂點依次編號。路上的頂點依次編號。132421039vj-5A3-1A20A1uiB4B3B2B1436313311310192741058( 2 ) 頂點編號：以空格頂點編號：以空格(Ak,Bl)(或進基變量或進基變量xik）為第一個）為第一個奇數(shù)頂點，沿閉回路的順（或逆）時針方向前進，對閉回奇數(shù)頂點，沿閉回路的順（或逆）時針方向前進，對閉回路上的頂點依次編號。路上的頂點依次編號。1324換出變量換出變量X23 13 , 1minmin14,23 xx( 3 ) 確定換出基的變量：在該閉回路上，從所有偶數(shù)號格確定換出基的變量：在該閉回路上，從所有偶數(shù)號格點的調(diào)運量中選出最小值點的調(diào)

29、運量中選出最小值 的頂點（格子），的頂點（格子），以該格子中的變量為換出變量。以該格子中的變量為換出變量。ijxmin ( 4 ) 確定新的運輸方案：確定新的運輸方案：以換出變量的運輸量為調(diào)整量以換出變量的運輸量為調(diào)整量 ，將該閉回路上將該閉回路上所有奇數(shù)號格的調(diào)運量加上調(diào)整量所有奇數(shù)號格的調(diào)運量加上調(diào)整量 ，所有偶，所有偶數(shù)號格的調(diào)運量減去數(shù)號格的調(diào)運量減去 ，其余的不變，這樣就得到一個新的，其余的不變，這樣就得到一個新的調(diào)運方案調(diào)運方案。該運輸方案的總運費比原運輸方案減少，改變量。該運輸方案的總運費比原運輸方案減少，改變量等于換出變量的檢驗數(shù)。等于換出變量的檢驗數(shù)。( 5 )然后，再對得到

30、的新解進行最優(yōu)性檢驗，加不是最優(yōu)解，然后，再對得到的新解進行最優(yōu)性檢驗，加不是最優(yōu)解，就重復以上步驟繼續(xù)進行調(diào)整，一直到得出最優(yōu)解為止。就重復以上步驟繼續(xù)進行調(diào)整，一直到得出最優(yōu)解為止。21039vj-5A3-1A20A1uiB4B3B2B136313113101927410584331039vj-5A3-2A20A1uiB4B3B2B1536312311310192741058重新求所有非基變量的檢驗數(shù)：重新求所有非基變量的檢驗數(shù)：31039vj-5A3-2A20A1uiB4B3B2B1536312當所有非基變量的檢驗數(shù)均非負時，則當前調(diào)運方案即為最當所有非基變量的檢驗數(shù)均非負時，則當前調(diào)運

31、方案即為最優(yōu)方案，如表此時最小總運費：優(yōu)方案，如表此時最小總運費：Z =(13)(46)(35)(210)(18)(35)85元元311310192741058表上作業(yè)法的計算步驟：表上作業(yè)法的計算步驟：分析實際問題列出產(chǎn)銷平分析實際問題列出產(chǎn)銷平衡表及單位運價表衡表及單位運價表確定初始調(diào)運方案（最小確定初始調(diào)運方案（最小元素法或元素法或Vogel法）法）求檢驗數(shù)（位勢法）求檢驗數(shù)（位勢法）所有檢驗數(shù)所有檢驗數(shù)0找出絕對值最大的負檢驗數(shù)，用閉合找出絕對值最大的負檢驗數(shù)，用閉合回路調(diào)整，得到新的調(diào)運方案回路調(diào)整，得到新的調(diào)運方案得到最優(yōu)方案，得到最優(yōu)方案，算出總運價算出總運價（1）若運輸問題的某

32、一基可行解有多個非基變量的檢驗數(shù)）若運輸問題的某一基可行解有多個非基變量的檢驗數(shù)為負，在繼續(xù)迭代時，取它們中任一變量為換入變量均可使為負，在繼續(xù)迭代時，取它們中任一變量為換入變量均可使目標函數(shù)值得到改善，但通常取目標函數(shù)值得到改善，但通常取ij0中最小者對應(yīng)的變量為中最小者對應(yīng)的變量為換入變量。換入變量。（2）無窮多最優(yōu)解）無窮多最優(yōu)解產(chǎn)銷平衡的運輸問題必定存最優(yōu)解。如果非基變量的產(chǎn)銷平衡的運輸問題必定存最優(yōu)解。如果非基變量的ij0，則該問題有無窮多最優(yōu)解。，則該問題有無窮多最優(yōu)解。如上例：如上例： 11的檢驗數(shù)是的檢驗數(shù)是 0，經(jīng)過調(diào)整，可得到另一個最，經(jīng)過調(diào)整，可得到另一個最優(yōu)解。優(yōu)解。

33、退化解：退化解： 表格中一般要有表格中一般要有(m+n-1)個數(shù)字格。但有時在分配運量個數(shù)字格。但有時在分配運量時則需要同時劃去一行和一列，這時需要補一個時則需要同時劃去一行和一列，這時需要補一個0，以保證，以保證有有(m+n-1)個數(shù)字格作為基變量。一般可在劃去的行和列的個數(shù)字格作為基變量。一般可在劃去的行和列的任意空格處加一個任意空格處加一個0即可。即可。 利用進基變量的閉回路對解進行調(diào)整時，標有負號的利用進基變量的閉回路對解進行調(diào)整時，標有負號的最小運量（超過最小運量（超過2個最小值）作為調(diào)整量個最小值）作為調(diào)整量，選擇任意一個最，選擇任意一個最小運量對應(yīng)的基變量作為出基變量，并打上小運

34、量對應(yīng)的基變量作為出基變量，并打上“”以示作為以示作為非基變量。非基變量。 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A116A210A322銷量銷量81412141241148310295116(0)(2)(9)(2)(1)(12)如下例中如下例中11檢驗數(shù)是檢驗數(shù)是 0，經(jīng)過調(diào)整，可得到另一個最優(yōu)解。，經(jīng)過調(diào)整，可得到另一個最優(yōu)解。 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A17A24A39銷量銷量365620114431377821060在在x12、x22、x33、x34中任選一個變量作為基變量，例如選中任選一個變量作為基變量，例如選x34例：用最小元素法求初始可行解例：用最小元素法求初始

35、可行解當總產(chǎn)量與總銷量不相等時當總產(chǎn)量與總銷量不相等時,稱為不平衡運輸問題稱為不平衡運輸問題.這類這類運輸問題在實際中常常碰到運輸問題在實際中常常碰到,它的求解方法是將不平衡問題它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解?；癁槠胶鈫栴}再按平衡問題求解。 當產(chǎn)大于銷時，即：當產(chǎn)大于銷時，即： minjjiba11數(shù)學模型為：數(shù)學模型為： minjijijxcZ11minnijijmijjiijxaimxbjnximjn111, 2,1, 2,01, 2,;1, 2, L LL LL LL L，由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運送完，由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的

36、產(chǎn)量不能全部運送完，必須就地庫存，即每個產(chǎn)地設(shè)一個倉庫，假設(shè)該倉庫為一個虛擬必須就地庫存，即每個產(chǎn)地設(shè)一個倉庫，假設(shè)該倉庫為一個虛擬銷地銷地Bn+1， bn+1作為一個虛設(shè)銷地作為一個虛設(shè)銷地Bn+1的銷量的銷量(即庫存量即庫存量)。各產(chǎn)地。各產(chǎn)地Ai到到Bn+1的運價為零，即的運價為零，即Ci,n+1=0,（i=1，m）。則平衡問題的）。則平衡問題的數(shù)學模型為：數(shù)學模型為： minjijijxcZ11min , 2 , 1, 2 , 1, 01, 2 , 1, 2 , 1111jmixnjbxmiaxijmijijnjiij；具體求解時具體求解時, ,只只在運價表右端在運價表右端增加一列增加

37、一列B Bn n+1+1，運價為零運價為零, ,銷量銷量為為b bn n+1+1即可即可 當銷大于產(chǎn)時，即：當銷大于產(chǎn)時，即： minjjiba11 minjijijxCZ11minnijijmijjiijxaimxbjnxim j111,2,1,2,0,1,2,;1,2, L LL LL LL L數(shù)學模型為：數(shù)學模型為：由于總銷量大于總由于總銷量大于總產(chǎn)量產(chǎn)量, ,故一定有些需故一定有些需求地不完全滿足求地不完全滿足, ,這這時虛設(shè)一個產(chǎn)地時虛設(shè)一個產(chǎn)地Am+1Am+1，產(chǎn)量為：，產(chǎn)量為：nmjijiba11 銷大于產(chǎn)化為平衡問題的數(shù)學模型為銷大于產(chǎn)化為平衡問題的數(shù)學模型為 ： minjij

38、ijxcZ11minni jijmijjiijxaimxbjnximjn1111,2,11,2,0,1,2,11,2, L LL LL LL L；具體計算時，在運價表的下方增加一行具體計算時，在運價表的下方增加一行Am+1，運價為零。產(chǎn)，運價為零。產(chǎn)量為量為am+1即可。即可。 例例3.4 求下列表中極小化運輸問題的最優(yōu)解。求下列表中極小化運輸問題的最優(yōu)解。 B1B2B3B4aiA1592360A2-47840A3364230A448101150bj20603545180160 4141160180ijjiba因為有：因為有：所以是一個產(chǎn)大于銷的運輸問題。表中所以是一個產(chǎn)大于銷的運輸問題。表中

39、A2不可達不可達B1，用一個，用一個很大的正數(shù)很大的正數(shù)M表示運價表示運價C21。虛設(shè)一個銷量為。虛設(shè)一個銷量為b5=180-160=20，Ci5=0，i=1,2,3,4，表的右邊增添一列，表的右邊增添一列 ，得到新的運價表。，得到新的運價表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180下表為計算結(jié)果?？煽闯觯寒a(chǎn)地下表為計算結(jié)果?？煽闯觯寒a(chǎn)地A4還有還有20個單位沒有運出。個單位沒有運出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180用前

40、面的方法求運輸方案：用前面的方法求運輸方案：例例3.5 某市有三個造紙廠某市有三個造紙廠A1，A2，A3，其紙的產(chǎn)量分別為，其紙的產(chǎn)量分別為8，5和和9個單位，有個單位，有4個集中用戶個集中用戶B1，B2，B3，B4，其需用量分，其需用量分別為別為4，3，5和和6個單位。由各造紙廠到各用戶的單位運價個單位。由各造紙廠到各用戶的單位運價如表如表314所示，請確定總運費最少的調(diào)運方案。所示，請確定總運費最少的調(diào)運方案。 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4 產(chǎn)量產(chǎn)量A1312348A2112595A367159銷量銷量4356解：由于總產(chǎn)量解：由于總產(chǎn)量22大于總銷量大于總銷量18，故本問題是個產(chǎn)銷不

41、平，故本問題是個產(chǎn)銷不平衡運輸問題。增加一假想銷地衡運輸問題。增加一假想銷地B5，用表上作業(yè)法求解。，用表上作業(yè)法求解。 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4B5(貯存貯存)產(chǎn)量產(chǎn)量A13123408A21125905A3671509銷量銷量43564 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4B5(貯存貯存)產(chǎn)量產(chǎn)量A13123408418634A211259050302-8A3671509-2954-4銷量銷量43564例例3.5 由由n個地區(qū)需要某種物資，需要量分別不少于個地區(qū)需要某種物資，需要量分別不少于bj（j=1,n）。這些物資均由某公司分設(shè)在）。這些物資均由某公司分設(shè)在m個地區(qū)的工廠供個地區(qū)的

42、工廠供應(yīng)，各工廠的產(chǎn)量分別不大于應(yīng)，各工廠的產(chǎn)量分別不大于ai（i=1,m）,已知從第已知從第i個地個地區(qū)至第區(qū)至第j個需求地區(qū)單位物資的運價為個需求地區(qū)單位物資的運價為cij，又，又 ，試，試寫出其對偶問題，并解釋對偶變量的經(jīng)濟意義。寫出其對偶問題，并解釋對偶變量的經(jīng)濟意義。 由于在變量相等的情況下，表上作業(yè)法的計算遠比單由于在變量相等的情況下，表上作業(yè)法的計算遠比單純形法簡單得多。所以在解決實際問題時，人們常常盡可純形法簡單得多。所以在解決實際問題時，人們常常盡可能把某些線性規(guī)劃的問題化為運輸問題的數(shù)學模型。能把某些線性規(guī)劃的問題化為運輸問題的數(shù)學模型。mnijijab11 解：由題給出的條件，數(shù)學模型可寫為解：由題給出的條件，數(shù)學模型可寫為:mnijijijzc x11min nijijmijjiijxa im stxb jn x 11(1,).(1,)0 L LL L對偶問題可寫為對偶問