工學第6章運輸問題課件

1、6 運輸問題 運輸問題的數(shù)學模型 運輸問題及其基的特征 表上作業(yè)法 產(chǎn)銷不平衡的運輸問題 轉(zhuǎn)運問題 運輸問題的應用礦業(yè)系統(tǒng)工程電子教案x2x1zo7/27/20221運輸問題6.1 運輸問題的數(shù)學模型7/27/20222運輸問題考察問題 例6.1 某公司經(jīng)營一種產(chǎn)品，它下設三個加工廠和四個銷售點。三個加工廠 A1 , A2 , A3 的產(chǎn)量分別為 7 噸，5 噸，9 噸；四個銷售點 B1 , B2 , B3 , B4 的銷量分別為 3 噸，6 噸，6 噸，6 噸。從各加工廠到各銷售點的每噸產(chǎn)品的運費如表6.1所示。問該公司應如何調(diào)運產(chǎn)品，使總運費最小。 設 xij 為從加工廠 Ai 到銷售點

2、Bj 的產(chǎn)品運輸量 ( i=1, 2, 3; j=1, 2, 3, 4 )，將產(chǎn)銷量和所有可能安排的運輸量列于表6.2，則上述問題可形成一個數(shù)學問題。7/27/20223運輸問題問題的數(shù)學形式min z =5x11+11x12+3x13+9x13 + x21+10 x22+2x23+6x24 +8x31+4x32 +7x33+5x34s.t. x11+ x12 + x13 + x14 =7 x21+ x22 + x23 + x24 =5 x31+ x32 + x33 + x34 =9 x11 + x21 + x31 = 3 x12 + x22 + x32 = 6 x13 + x23 + x33

3、 = 6 x14 + x24 + x33 = 6 xij 0 , i , j表6.1 單位運價表表6.2 產(chǎn)銷平衡表7/27/20224運輸問題運輸問題的一般描述 某種物資有 m 個產(chǎn)地 (也稱為“發(fā)點”或“源”)和 n 個銷地 (也稱為“收點”或“匯”) ，第 i 個產(chǎn)地 Ai 的產(chǎn)量為 ai，i =1, 2, , m，第 j 個銷地 Bj 的銷量為 bj，j = 1, 2, , n，從 Ai 到 Bj 的單位物資運價為 cij。問在產(chǎn)銷平衡的條件下，如何確定總運費最小的物資調(diào)運方案。 設 xij 為從產(chǎn)地 Ai 到銷地 Bj 的物資運輸量，則上述問題可歸結(jié)為一個線性規(guī)劃問題。7/27/20

4、225運輸問題表6.3 單位運價表7/27/20226運輸問題表6.4 產(chǎn)銷平衡表7/27/20227運輸問題運輸問題的模型s.t. x11+x12 +x1n=a1 x21+x22 +x2n=a2 xm1+xm2+xmn=am x11+x21 +xm1=b1 x12+x22 +xm2=b2 x1n+x2n+xmn=bn xij 0 , i , jijijxcmin z =nj1=mi1=7/27/20228運輸問題數(shù)學模型的兩種形式s.t. x11+x12 +x1n=a1 x21+x22 +x2n=a2 xm1+xm2+xmn=am x11+x21 +xm1=b1 x12+x22 +xm2=b

5、2 x1n+x2n+xmn=bn xij 0 , i , jijijxcmin z =nj1=mi1=ijijxcmin z =nj1=mi1=xij 0 , i , jaxiij=nj1=mi1=s.t.,nj1=bxjij=mi1=,=njjb1=miia1ijxnj1=mi1=7/27/20229運輸問題表6.5 運輸表7/27/202210運輸問題表6.6 運輸表(綜合表)7/27/202211運輸問題表6.7 例6.1的運輸表7/27/202212運輸問題表6.8 例6.1的綜合運輸表7/27/202213運輸問題6.2 運輸問題及其基的特征7/27/202214運輸問題6.2.1

6、運輸問題的解 與一般線性規(guī)劃問題不同，產(chǎn)銷平衡的運輸問題一定存在可行解。因有 則存在可行解 xij 0 = ai bj /Q , i , j 又因 0 xij min ai ,bj 所以運輸問題必存在最優(yōu)解。=njjb1=miia1= Q7/27/202215運輸問題運輸問題解的特性 運輸問題還有一個重要的性質(zhì)，若產(chǎn)銷量 ai 和 bj都是整數(shù)，則必存在整數(shù)最優(yōu)解。因此，將某些整數(shù)規(guī)劃問題化為運輸問題來求解，即便不用整數(shù)限制條件，結(jié)果可自然滿足整數(shù)要求。在“整數(shù)規(guī)劃”一章中，將會看到求解整數(shù)規(guī)劃問題相當費事，而運輸問題解的特性給求解某些整數(shù)規(guī)劃問題帶來了很大方便。7/27/202216運輸問題

7、6.2.2 運輸問題的形式特征 運輸問題的數(shù)學模型具有下列特征：方程組中所有變量的系數(shù)皆為 1和 0 ；任何一個變量 xij 在前 m 個方程中以系數(shù) 1 出現(xiàn)一次，在后 n 個方程也以系數(shù) 1 出現(xiàn)一次；由于要求 ai = bj ，這 (m+n) 個方程是線性相關的。如果從中去掉一個方程 ,剩下的 (m+n-1) 個方程線性無關。7/27/202217運輸問題運輸問題的系數(shù)矩陣(單模)或幺模m行n行7/27/202218運輸問題系數(shù)矩陣的秩假設 m , n 2，則有 m +n m n ，于是矩陣 A 的秩小于或等于m+n。但是A的秩不等于m +n ，這是因為 A 的前 m 行之和恰好等于后

8、n 行之和，所以 A 的 m +n 行是線性相關的。因此，A 的秩小于或等于 m + n -1對于運輸問題的約束方程的增廣矩陣A（就是由矩陣A再增添一列約束方程組的右端項所組成的(m+n)(m+n-1)階矩陣），也有A的秩 = m+n-1.7/27/202219運輸問題001001000010000000000100第 i 行第 m+j 行系數(shù)矩陣列向量的結(jié)構(gòu) 系數(shù)矩陣每一列的元素只有兩個1，其余都為0。 Pij = ei + em+j7/27/202220運輸問題6.2.3 運輸問題的基 同一般的線性規(guī)劃問題一樣，運輸問題的最優(yōu)解一定可以在基可行解中找到。因此，繼考察了約束方程組的系數(shù)矩陣之

9、后，還要進一步研究運輸問題的基及其基變量所具有的特征。 7/27/202221運輸問題 由上面的討論可知，運輸問題基變量的數(shù)目應該是 m+n -1 個，接下來研究怎樣的 m +n -1 個變量 可以組成基變量?；蛘哒f，怎樣的 m +n -1 個變量 (s =m+n-1) 對應的系數(shù)列向量 (s =m+n-1) 是線性無關的。 下面引入有關閉回路的概念，它有助于分析和解決上述問題。基變量與基向量sssjijijijijijixxxxxx122111211, (s =m+n-1)ssjijijiPPP2211,ssjijijixxx2211,7/27/202222運輸問題閉回路及其形式x1 1 ,

10、 x1 3 , x3 3 , x3 17/27/202223運輸問題閉回路的定義 定義6.1 凡是能排成 ( i1 , i2 , , is 互不相同, j1 , j2 , , js 互不相同 ) 形式的變量的集合稱為一個閉回路，而把出現(xiàn)在(1) 中的變量稱為這個閉回路的頂點(或拐角點)，相鄰兩頂點的連線稱為閉回路的邊。(1)132222111,jijijijijijisssxxxxxx7/27/202224運輸問題閉回路的形式之二 x1 1 , x1 2 , x3 2 , x3 4 , x2 4 , x2 1 7/27/202225運輸問題閉回路的形式之三7/27/202226運輸問題閉回路的

11、特點 從上面幾個閉回路的例子中不難看出，如果把一個閉回路的所有頂點都在表上畫出，并且把相鄰的頂點用一條直線連接起來，就可以得到一條封閉的折線，折線的每一條邊或者是水平的，或者是垂直的，即折線是由交替的水平和垂直（聯(lián)接的）線段組成。另外，在表中的每一行和每一列中，至多只有閉回路的兩個頂點；對一條閉回路是按順時針方向還是逆時針方向是無關緊要的。7/27/202227運輸問題 性質(zhì)6.1 若有一閉回路 則 證 根據(jù)列向量的特征 Pij = ei + em+j 可得閉回路及其性質(zhì)132222111-+-+-jijijijijijisssPPPPPP= 0132222111-+-+-jijijijiji

12、jisssPPPPPP()+jmiee32-()+jmiee22-= ()+jmiee11+()+jmiee21-()+jmieess+ += 0()+jmiee1s1ssjijijijijijixxxxxxs32222111,7/27/202228運輸問題srrjijijijijijixxxxxx122111211,(6. 2)122112111- , , ,+-jijijijijijisrrPPPPPP = 0閉回路與列向量 性質(zhì)6.2 若變量組 中有一部分組成閉回路，則(6. 2)對應的列向量 是線性相關的。 證 性質(zhì)6.1表明構(gòu)成閉回路的變量組對應的列向量組是線性相關的，而向量組中有一

13、部分線性相關，則全體也線性相關。 性質(zhì)6.2說明：若變量組(6. 2)對應的列向量線性無關，則該變量組一定不包含有閉回路。7/27/202229運輸問題 定理6.1 變量組 對應的系數(shù)列向量組線性無關的充要條件是：變量組(6. 2)不包含有閉回路。 推論6.1 m + n -1 個變量 (s =m+n-1) 構(gòu)成基變量的充要條件是不含閉回路。運輸問題的基及其構(gòu)成條件ssjijijixxx2211,rrjijijixxx2211,(6. 2)7/27/202230運輸問題6.3 表上作業(yè)法表上作業(yè)法是運用單純形法求解運輸問題的一種形式；表上作業(yè)法的計算步驟和計算內(nèi)容與單純形法完全相同，只是在計算

14、方法上有較大的簡化，其實質(zhì)仍是單純形法；表上作業(yè)法的所有計算可以在運輸表上操作，故得此名。7/27/202231運輸問題6.3.1 初始解的求解方法7/27/202232運輸問題1. 最小元素法最小元素法的基本思想是就近供應，這是因為運輸問題是要確定總運費最小的運輸方案；最小元素法的宗旨是從運價表中依次選擇當前最小運價的格子分配相應的運輸量，由此確定初始運輸方案；最小元素法求得的初始解一般很接近最優(yōu)解。7/27/202233運輸問題最小元素法算例 最小元素法計算程序： (4) 若 xlk(0)=q1, 則 It+1=It - l , Jt+1=Jt(1) t = 0, It=1,m, Jt=1

15、,n 若 xlk(0)=q2, 則 It+1=It , Jt+1=Jt - k (2) clk(t) = min cij | iIt , jJt (5) t = t +1 , 返回 (2) 。(3)(2)(4)(6)(3)(3)1234566z0=85al - , bk - ljxnj1=(0)ikxmi1=(0)(3) xlk(0)=min = minq1, q27/27/202234運輸問題關于最小元素法的定理 定理6.2 用最小元素法得到的變量 xij 的值構(gòu)成一個基可行解，括號中的數(shù)則是基變量的值。有m + n -1個基變量；基變量不包含閉回路。x1x2x3x47/27/202235運

16、輸問題2. 左上角法(西北角法)左上角法的特點是不考慮運輸方案的運費，只要求運輸量滿足產(chǎn)銷平衡便可。因此該法不依賴運價表，可直接在產(chǎn)銷平衡表上操作。左上角法的要點是按產(chǎn)地和銷地的排序從前到后依次確定供銷關系，即每次都是在運價表中選擇當前處在左上角的格子分配運輸量，由此確定初始運輸方案；左上角法的計算量較小，但求得的初始解遠不如最小元素法的好，通常與最優(yōu)解相去甚遠。7/27/202236運輸問題2. 左上角法(西北角法)算例(3)(4)(2)(3)(3)(6)z0=1357/27/202237運輸問題3.伏格爾(Vogel)法伏格爾法的出現(xiàn)早于表上作業(yè)法，原本是一種求解運輸問題的近似算法，亦稱

17、Vogel 近似法，簡稱 V A M。伏格爾法給出的解也是基解，因此可以把它當作一種求初始解的方法。伏格爾法的出發(fā)點與最小元素法相同。由于局部最優(yōu)的疊加并不等于全局最優(yōu)，最小元素法往往會顧此失彼，即為了節(jié)省一處的費用有時造成別處要多花幾倍的運費。相比之下，伏格爾法是一種“顧全大局” 的最小元素法。根據(jù)計算特點，伏格爾法也稱元素差額法。伏格爾法求得的初始解更接近或者就是最優(yōu)解。7/27/202238運輸問題例6.2的初始解(最小元素法)7/27/202239運輸問題212-123例6.2的解(伏格爾法)5121123-2258221-52(3)(5)(4)(3)(1)(5)z1 = 887/27

18、/202240運輸問題例6.2的最優(yōu)解7/27/202241運輸問題伏格爾法求解例6.17/27/202242運輸問題 最小元素法求解例6.17/27/202243運輸問題6.3.2 當前解的判別和調(diào)整 當前解的判別仍然是依據(jù)非基變量的檢驗數(shù)，檢驗數(shù)的計算公式為 ij = cij - CBB-1Pij , i , j N 因為運輸問題的目標函數(shù)是要求實現(xiàn)最小化，所以必須滿足條件 ij = cij - CBB-1Pij 0 , i , j N 當前解就是最優(yōu)解。 下面介紹兩種求非基變量檢驗數(shù)的方法：閉回路法和位勢法。7/27/202244運輸問題1.閉回路法 運輸問題非基變量的檢驗數(shù)有特定的經(jīng)濟

19、含義，按照這種含義計算檢驗數(shù)的方法稱為閉回路法； 當前解若不是最優(yōu)解，就要對其進行調(diào)整或變換。求解運輸問題時，當前解的調(diào)整不必進行一般意義上的旋轉(zhuǎn)變化，只要在相應的閉回路上操作就可以了。7/27/202245運輸問題數(shù)字格和空格 運輸表中的每個格子都對應著一個變量，為了在表上能夠看出哪些變量是基變量、哪些變量是非基變量，可以約定：在選為基變量的格子中打一個括號，把基變量的值填在這個括號里，并把這種格子叫數(shù)字格 (或稱開發(fā)格子) ；非基變量的值都為 0，但這個 0 不用填，這樣就把非基變量對應的格子稱為空格(或稱關閉格子)。7/27/202246運輸問題 數(shù)字格和空格示例非基變量與空格基變量與數(shù)

20、字格7/27/202247運輸問題x13 , x14 , x21 , x23 , x32 , x34非基變量和閉回路x11 , x13 , x14 , x21 , x23 , x32 , x34x11 , x21 , x23 , x13 , 基變量組關于變量 x11的閉回路是否含閉回路7/27/202248運輸問題svvkijijijijlklxxxxxxvpoooo211, 定理6.3 設運輸問題的基變量組為 xl k是一個非基變量，則變量組 中存在一個包含xl k的閉回路，并且這個閉 回路是唯一的。非基變量對應的閉回路ssjijijixxx2211,s = m + n -1sssjijij

21、ijikljixxxxxx1221111,sssjijijijlkljixxxxxx1221111,7/27/202249運輸問題 x11 , x13 , x23 , x21 z1= z0 + c11 - c13 + c23 - c21 11 = z1 - z0 = c11 - c13 + c23 - c21 = 5 - 3 + 2 - 1 = 3檢驗數(shù)的意義7/27/202250運輸問題 x24 , x23 , x13 , x14 z1= z0 + c24 - c23 + c13 - c14 24 = z1 - z0 = c24 - c23 + c13 - c14 = 6 - 2 + 3 -

22、 9 = -2檢驗數(shù)的計算(閉回路法)7/27/202251運輸問題檢驗數(shù)的計算結(jié)果(一)7/27/202252運輸問題當前解的判別 由最優(yōu)解的判別依據(jù)可知，在計算表中若所有的檢驗數(shù)都大于或等于零，則表明對當前解作出任何改變都不會使運費下降，所以當前解就是最優(yōu)解。反之，說明當前解不是最優(yōu)解，需要加以調(diào)整。7/27/202253運輸問題當前解的調(diào)整 當前解的調(diào)整方法如下：選擇一個負檢驗數(shù) (當不止一個負檢驗數(shù)時，一般選一個最小的負檢驗數(shù) ) lk 0 ，以它對應的非基變量 xpq 作為換入變量；找出換入變量對應的閉回路，將閉回路的頂點按順序編號，換入變量xlk作為第一個頂點，因此這條閉回路的頂點

23、分為奇數(shù)號頂點和偶數(shù)號頂點兩類。在所有偶數(shù)號頂點中找出運輸量最小的頂點 xrs 作為換出變量；7/27/202254運輸問題當前解的調(diào)整(續(xù))將換出變量 xrs 的運輸量作為調(diào)整量 ，對當前解調(diào)整如下：閉回路中所有奇數(shù)號頂點(包括換入變量xpq)的運輸量加上 ；閉回路中所有偶數(shù)號頂點(包括換出變量 xrs)的運輸量減去 ；不屬于閉回路的變量對應的運輸量不變。 上述當前解的調(diào)整方法稱為閉回路調(diào)整法。顯然，調(diào)整后的解仍是基可行解。7/27/202255運輸問題用閉回路法對表中的解進行調(diào)整7/27/202256運輸問題換入變量為： x24對應的閉回路： = x24 , x23 , x13 , x14

24、 調(diào)整量 ： =minx23(0), x14 (0)=min2,3=2換出變量為： x23換入、換出變量和調(diào)整量7/27/202257運輸問題 當前解調(diào)整的算例cij(xij)sijB1B2B3B4ai51139A1 (4+q )(3-q )711026A2(3)(2-q )+q58475A3(6)(3)9bj3666z0=85 xij(0) + , xij(0)+ xij(0) - , xij(0) - xij(0) , xij(0) xij(1) =7/27/202258運輸問題調(diào)整后的基可行解7/27/202259運輸問題檢驗數(shù)的計算結(jié)果(二)7/27/202260運輸問題2. 位勢法7

25、/27/202261運輸問題 設給定了一個初始調(diào)運方案，其基變量為 對應的運價為 引入 m + n 個待定的未知量 u1, u2 , um , v1, v2 , vn，把各 ui 寫在運輸表各行 Ai 的右邊，把 vj 寫在各列 Bj 的下邊，并使上述各基變量的運價恰好就等于它所在行的 ui 與所在列的 vj 之和。即有如下方程組： 注意這個方程組中一共有m+n個未知數(shù)，m+n-1=s個方程。基變量對應的方程組ssjijijixxx2211,s = m + n -1ssjijijiccc2211。,11jijicvu11=+21jijicvu22=+s1jijicvuss=+ (6. 3)7/

26、27/202262運輸問題基變量對應的方程組舉例 x13 , x14 , x21 , x23 , x32 , x34 u1+ v3 = 3 = c13 , u1+ v4 = 9 = c14 u2+ v1 = 1 = c21 , u2+ v3 = 2 = c23 u3+ v2 = 4 = c32 , u3+ v4 = 5 = c347/27/202263運輸問題位勢的求解cij(xij)B1B2B3B4ui51139A1(4)(3)11026A2(3)(2)8475A3(6)(3)vjz0=85 x13 , x14 , x21 , x23 , x32 , x34 u1+ v3 = 3 = c13

27、 , u1+ v4 = 9 = c14 u2+ v1 = 1 = c21 , u2+ v3 = 2 = c23 u3+ v2 = 4 = c32 , u3+ v4 = 5 = c3401-318277/27/202264運輸問題 11 = c11 - c13 + c23 - c21 = c11 - ( u1+v3) + ( u2+v3) - ( u2+v1) = c11 - u1- v1 = c11 - ( u1+v1)檢驗數(shù)的計算(位勢法)7/27/202265運輸問題 ij = cij - CBB-1Pij ij = cij - ( ui + vj )檢驗數(shù)的計算公式及結(jié)果7/27/202

28、266運輸問題7/27/202267運輸問題7/27/202268運輸問題7/27/202269運輸問題7/27/202270運輸問題表上作業(yè)法計算中的問題7/27/202271運輸問題初始退化解的給定(2)(2)(3)(3)(0)(0)7/27/202272運輸問題7/27/202273運輸問題退化解的調(diào)整( = 0)7/27/202274運輸問題退化解的調(diào)整( 不是唯一的)7/27/202275運輸問題退化的最優(yōu)解7/27/202276運輸問題6.4 產(chǎn)銷不平衡的運輸問題7/27/202277運輸問題例6.3 產(chǎn)大于銷問題的運輸表7/27/202278運輸問題產(chǎn)大于銷的運輸問題 假若有一個

29、虛擬的銷地 Bn+1，它的銷量為并且設 xi n+1 ( i = 1 m ) 為從產(chǎn)地 Ai 到虛擬銷地 Bn+1 的物資運輸量，即產(chǎn)地 Ai的就地儲存量，ci n+1= 0 ( i = 1 m )，原問題可轉(zhuǎn)化為平衡問題。ijijxcmin z =nj1=mi1=xij 0 , i , js.t.mi1=axiij nj1=,nj1=bxjij=mi1=,=njjb1=miia1-=njjb1=miia1bn+1 =7/27/202279運輸問題運輸模型的轉(zhuǎn)化 假若有一個虛擬的銷地 Bn+1，它的銷量為并且設 xi n+1 ( i = 1 m ) 為從產(chǎn)地 Ai 到虛擬銷地 Bn+1 的物資

30、運輸量，即產(chǎn)地 Ai的就地儲存量，ci n+1= 0 ( i = 1 m )，原問題可轉(zhuǎn)化為平衡問題。ijijxcmin z =nj1=mi1=xij 0 , i , jnj1=bxjij=mi1=,-=njjb1=miia1bn+1 =bn+1=xi n+1mi1=ijxnj1=+ xi n+1 = ai, i =1 m7/27/202280運輸問題ijijxcmin z =nj1=mi1=xij 0 , i , jnj1=bxjij=mi1=,bn+1=xi n+1mi1=ijxnj1=+ xi n+1 = ai, i =1 m7/27/202281運輸問題轉(zhuǎn)化后的平衡問題 ijijxcm

31、in z =nj1=mi1=xij 0 , i , js.t.nj1=bxjij=mi1=,ijxnj1=+ xi n+1 = aibn+1=xi n+1mi1=ijijxcmin z =n+1j1=mi1=xij 0 , i , jxijn+1j1=mi1=s.t.ai=,n +1j1=bxjij=mi1=,7/27/202282運輸問題產(chǎn)大于銷的運輸問題舉例7/27/202283運輸問題產(chǎn)大于銷的運輸問題舉例(續(xù))7/27/202284運輸問題銷大于產(chǎn)的運輸問題 假若有一個虛擬的產(chǎn)地 Am+1，它的產(chǎn)量為并且設 xm+1 j ( j = 1 n ) 為從虛擬產(chǎn)地 Am+1 到銷地 Bj 的物資缺貨量，即銷地 Bj 的自給儲存量，cm+1 j = 0 ( j = 1 n )，原問題可轉(zhuǎn)化為平衡問題。ijijxcmin z =nj1=mi1=xij 0 , i , js.t.mi1=axiij =nj1=,jijnj1=b x mi1=,=njjb1=miia1 -=miia1=njjb1