1、,運籌學(xué) Operations Research,Chapter 5 運輸問題 Transportation Problem,5.1運輸問題的數(shù)學(xué)模型及其特征 5.2 運輸單純形法 5.3 運輸模型的應(yīng)用,5.1 運輸問題的數(shù)學(xué)模型及其特征 Mathematical Model of Transportation Problems,人們在從事生產(chǎn)活動中，不可避免地要進(jìn)行物資調(diào)運工作。如某時期內(nèi)將生產(chǎn)基地的煤、鋼鐵、糧食等各類物資，分別運到需要這些物資的地區(qū)，根據(jù)各地的生產(chǎn)量和需要量及各地之間的運輸費用，如何制定一個運輸方案，使總的運輸費用最小。這樣的問題稱為運輸問題。,5.1 運輸模型 Mod

2、el of Transportation Problems,5.1.1 數(shù)學(xué)模型,產(chǎn)地,銷地,A1 10,A2 8,B4 3,3,5,4,2,3,1,6,8,2,3,2,9,圖5.1,【例5-1】現(xiàn)有A1，A2，A3三個產(chǎn)糧區(qū)，可供應(yīng) 糧食分別為10，8，5（萬噸），現(xiàn)將糧食運往B1，B2，B3，B4四個地區(qū)，其需要量分別為5，7，8，3（萬噸）。產(chǎn)糧地到需求地的運價（元/噸）如表5-1所示，問如何安排一個運輸計劃，使總的運輸費用最少。,運價表（元/噸）,表5-1,5.1 運輸模型 Model of Transportation Problems,設(shè)xij(i=1,2,3；j=1,2,3,4)

3、為i個產(chǎn)糧地運往第j個需求地的運量，這樣得到下列運輸問題的數(shù)學(xué)模型：,運量應(yīng)大于或等于零（非負(fù)要求），即,5.1 運輸模型 Model of Transportation Problems,5.1 運輸模型 Model of Transportation Problems,有些問題表面上與運輸問題沒有多大關(guān)系，也可以建立與運輸問題形式相同的數(shù)學(xué)模型,看一個例子： 【例5-2】有三臺機(jī)床加工三種零件，計劃第i臺的生產(chǎn)任務(wù)為a i (i=1,2,3)個零件，第j種零件的需要量為bj (j=1,2,3)，第i臺機(jī)床加工第j種零件需要的時間為cij ，如表52所示。問如何安排生產(chǎn)任務(wù)使總的加工時間最少

4、？,表52,5.1 運輸模型 Model of Transportation Problems,【解】 設(shè) xi j (i=1,2,3；j=1,2,3,)為第i臺機(jī)床加工第j種零件的數(shù)量，則此問題的數(shù)學(xué)模型為,5.1 運輸模型 Model of Transportation Problems,5.1.2 模型特征 運輸問題的一般數(shù)學(xué)模型,設(shè)有m個產(chǎn)地（記作A1，A2，A3,Am），生產(chǎn)某種物資，其產(chǎn)量分別為a1,a2，am；有n個銷地（記作B1，B2，Bn），其需要量分別為b1,b2，bn；且產(chǎn)銷平衡，即 。從第i個產(chǎn)地到j(luò) 個銷地的單位運價為cij ，在滿足各地需要的前提下，求總運輸費用最小

5、的調(diào)運方案。,5.1 運輸模型 Model of Transportation Problems,設(shè)xij(i=1,2,，m；j=1,2,n)為第i個產(chǎn)地到第j個銷地的運量， 則數(shù)學(xué)模型為：,5.1 運輸模型 Model of Transportation Problems,m 行,n 行,5.1 運輸模型 Model of Transportation Problems,運輸問題具有如下特點: 1.運輸問題存在可行解，也一定存在最優(yōu)解 2.當(dāng)供應(yīng)量和需求量都是整數(shù)時，則一定存在整數(shù)最優(yōu)解 3.有m+n個約束，mn個變量 4.約束條件系數(shù)矩陣的元素等于0或1 5.約束條件系數(shù)矩陣的每一列有兩個

6、非零元素,這對應(yīng)于每一個變量在前m個約束方程中出現(xiàn)一次,在后n個約束方程中也出現(xiàn)一次 6.所有約束方程都是等式方程 7.各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和 8.有m+n1個基變量,因為產(chǎn)銷平衡,所以模型最多只有m+n-1個獨立約束方程,即系數(shù)矩陣的秩最多為m+n-1.,5.2 運輸單純形法 Transportation Simplex Method,設(shè)平衡運輸問題的數(shù)學(xué)模型為：,5.2 運輸單純形法 Transportation Simplex Method,運輸單純形法也稱為表上作業(yè)法，是直接在運價表上求最優(yōu)解的一種方法，它的步驟是：,第一步：求初始基本可行解（初始調(diào)運方案）。 常用的方法有最

7、小元素法、元素差額法（Vogel近似法）、左上角法。,第二步：求檢驗數(shù)并判斷是否得到最優(yōu)解。常用求檢驗的方法有閉回路法和位勢法，當(dāng)非基變量的檢驗數(shù)ij全都非負(fù)時得到最優(yōu)解，若存在檢驗數(shù)lk0，說明還沒有達(dá)到最優(yōu)，轉(zhuǎn)第三步。,第三步：調(diào)整運量，即換基。選一個變量出基，對原運量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步。,5.2 運輸單純形法 Transportation Simplex Method,5.2.1初始基可行解,1. 最小元素法 最小元素法的思想是就近優(yōu)先運送，即最小運價Cij對應(yīng)的變量xij優(yōu)先賦值 然后再在剩下的運價中取最小運價對應(yīng)的變量賦值并滿足約束，依次下去，直到最后得到一個初始基

8、可行解。,5.2 運輸單純形法 Transportation Simplex Method,【例5-3】求表56所示的運輸問題的初始基可行解。,表56,5.2 運輸單純形法 Transportation Simplex Method,表5759,【解】,30,10,10,60,5.2 運輸單純形法 Transportation Simplex Method,20,10,到一組基可行解可用矩陣,表示，矩陣X 中空白處對應(yīng)的變量是非基變量，運量等于零，這組解就是初始調(diào)運方案總運費 Z=360+810+520+130+210+910=500,5.1 運輸模型 Model of Transportat

9、ion Problems,【例5-4】求表5-10給出的運輸問題的初始基本可行解,表5-10,5.2 運輸單純形法 Transportation Simplex Method,表5-11,【解】,5,10,0,15,10,10,5.2 運輸單純形法 Transportation Simplex Method,初始基本可行解可用下列矩陣表示,5.2 運輸單純形法 Transportation Simplex Method,2元素差額法（Vogel近似法）最小元素法只考慮了局部運輸費用最小。有時為了節(jié)省某一處的運費，而在其它處可能運費很大。元素差額法對最小元素法進(jìn)行了改進(jìn)，考慮到產(chǎn)地到銷地的最小運

10、價和次小運價之間的差額，如果差額很大，就選最小運價先調(diào)運，否則會增加總運費。例如下面兩種運輸方案,前一種按最小元素法求得，總運費是 Z1=108+52+151=105 后一種方案考慮到C11與C21之間的差額是82=6，先調(diào)運x21，再是x22，其次是x12這時總運費 Z2=105+152+51=85Z1。,5.2 運輸單純形法 Transportation Simplex Method,基于以上思路，元素差額法求初始基本可行解的步驟是：,第一步：求出每行次小運價與最小運價之差，記為ui，i=1,2,m ；同時求出每列次小運價與最小運價之差，記為vj，j=1，2，n ；,第二步：找出所有行、列

11、差額的最大值，即L=maxui，vi，差額L對應(yīng)行或列的最小運價處優(yōu)先調(diào)運；,第三步：這時必有一列或一行調(diào)運完畢，在剩下的運價中再求最大差額，進(jìn)行第二次調(diào)運，依次進(jìn)行下去，直到最后全部調(diào)運完畢，就得到一個初始調(diào)運方案。,用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。,5.2 運輸單純形法 Transportation Simplex Method,表5-6,【例5-5】用元素差額法求表56運輸問題的初始基本可行解。,【解】 求行差額 ui, i=1,2,3及列差額vj,j=1,2,3,4.計算公式為 ui= i行次小運價i行最小運價 vj= j列次小運價j例最小運價,5.2 運

12、輸單純形法 Transportation Simplex Method,表512,【0】,10,5.2 運輸單純形法 Transportation Simplex Method,表5-13,10,5.2 運輸單純形法 Transportation Simplex Method,【 】,5.2 運輸單純形法 Transportation Simplex Method,表5-14,【 】,20,表5-15,【 】,60,30,10,5.2 運輸單純形法 Transportation Simplex Method,基本可行解為,總運費Z=360+810530+120+210+210=470 比最小元

13、素法的總運費（500）要小30,5.2 運輸單純形法 Transportation Simplex Method,3. 左上角法。左上角法(亦稱西北角法)是優(yōu)先從運價表的左上角的變量賦值，當(dāng)行或列分配完畢后，再在表中余下部分的左上角賦值，依次類推，直到右下角元素分配完畢當(dāng)出現(xiàn)同時分配完一行和一列時，仍然應(yīng)在打“”的位置上選一個變量作基變量，以保證最后的基變量數(shù)等于m+n1,【例5-6】用左上角法求例5-3中表5-6的初始基本可行解,表5-16,10,60,0,10,20,5.2 運輸單純形法 Transportation Simplex Method,40,基本可行解為,用左上角法求得的基本可

14、行解對應(yīng)的目標(biāo)函數(shù)值（總運費）是 Z91036080540110+220=520,求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗數(shù)來判斷，記xij的檢驗數(shù)為ij由第一章知，求最小值的運輸問題的最優(yōu)判別準(zhǔn)則是：,所有非基變量的檢驗數(shù)都非負(fù)，則運輸方案最優(yōu)（即為最優(yōu)解）。,求檢驗數(shù)的方法有兩種，閉回路法和位勢法。,1閉回路法求檢驗數(shù) 求某一非基變量的檢驗數(shù)的方法是：在單位運價表中，以該非基變量為起點，以基變量為其它頂點，找一條閉回路，由起點開始，分別在頂點上交替標(biāo)上+1、-1、+1、-1、，分別乘以相應(yīng)的運價，其代數(shù)和就是這個非基變量的檢驗數(shù)。,5.2 運輸單純形法 Transportatio

15、n Simplex Method,5.2.2求檢驗數(shù),【解】用最小元素法 求得的初始基可行解,【例5-7】用閉回路法求例53表59的檢驗數(shù)。,5.2 運輸單純形法 Transportation Simplex Method,30,10,10,60,20,10,矩陣中打“”的位置是非基變量，其余是基變量，這里只求非基變量的檢驗數(shù)。,求11，先找出x11的閉回路 ，對應(yīng)的運價為 再用正負(fù)1分別交替乘以運價有 直接求代數(shù)和得,5.2 運輸單純形法 Transportation Simplex Method,5.2 運輸單純形法 Transportation Simplex Method,同理可求出其

16、它非基變量的檢驗數(shù)：,這里340，說明這組基本可行解不是最優(yōu)解。,只要求得的基變量是正確的且數(shù)目為m+n1，則某個非基變量的閉回路存在且唯一，因而檢驗數(shù)唯一。,5.2 運輸單純形法 Transportation Simplex Method,2位勢法求檢驗 位勢法求檢驗數(shù)是根據(jù)對偶理論推導(dǎo)出來的一種方法。,設(shè)平衡運輸問題為,設(shè)前m個約束對應(yīng)的對偶變量為ui,i=1,2,m，后n個約束對應(yīng)的對偶變量為vj,j=1,2,n則運輸問題的對偶問題是,5.2 運輸單純形法 Transportation Simplex Method,m 行,n 行,5.1 運輸模型 Model of Transporta

17、tion Problems,u1 um,v1 vn,加入松馳變量ij將約束化為等式,ui+vj+ij=cij,記原問題基變量XB的下標(biāo)集合為I，由第二章對偶性質(zhì)知，原問題xij的檢驗數(shù)是對偶問題的松弛變量ij，當(dāng)（i，j）I 時ij=0，因而有,解上面第一個方程，將ui、vj代入第二個方程求出ij,5.2 運輸單純形法 Transportation Simplex Method,【例5-8】用位勢法求例5-3表59給出的初始基本可行解的檢驗數(shù)。,【解】第一步求位勢u1、u2、u3及v1、v2、v3、v4。,10 60 40 30,令u1=0得到位勢的解為,5.2 運輸單純形法 Transpor

18、tation Simplex Method,再由公式 求出檢驗數(shù)，其中Cij是非基變量對應(yīng)的運價。,計算結(jié)果與例5-7結(jié)果相同。,5.2 運輸單純形法 Transportation Simplex Method,5.2.3調(diào)整運量,前面講過，當(dāng)某個檢驗數(shù)小于零時，基可行解不是最優(yōu)解，總運費還可以下降，這時需調(diào)整運輸量，改進(jìn)原運輸方案，使總運費減少，改進(jìn)運輸方案的步驟是：,第一步：確定進(jìn)基變量,第二步：確定出基變量 在進(jìn)基變量xik的閉回路中，標(biāo)有負(fù)號的最小運量作為調(diào)整量，對應(yīng)的基變量為出基變量，并打上“”以示作為非基變量。,第三步：調(diào)整運量 在進(jìn)基變量的閉回路中標(biāo)有正號的變量加上調(diào)整量，標(biāo)有負(fù)

19、號的變量減去調(diào)整量，其余變量不變，得到一組新的基可行解，然后求所有非基變量的檢驗數(shù)重新檢驗。,5.2 運輸單純形法 Transportation Simplex Method,5.2 運輸單純形法 Transportation Simplex Method,因為有一個檢驗數(shù)小于零，所以這組基本可行解不是最優(yōu)解。對應(yīng)的非基變量x34進(jìn)基.,x34的閉回路是,x33最小，x33是出基量，調(diào)整量=10,5.2 運輸單純形法 Transportation Simplex Method,在x34的閉回路上x34、x23分別加上10，x33、x24分別減去10，其余變量不變，調(diào)整后得到一組新的基可行解：,

20、非基變量的檢驗數(shù)：,11=5，14=0，21=6，22=6，32=9，33=3,所有檢驗數(shù)ij 0因而得到最優(yōu)解,最小運費,5.2 運輸單純形法 Transportation Simplex Method,5.2 運輸單純形法 Transportation Simplex Method,5.2 運輸單純形法 Transportation Simplex Method,5.2 運輸單純形法 Transportation Simplex Method,【例5-9】求下列運輸問題的最優(yōu)解,表5-19,5.2 運輸單純形法 Transportation Simplex Method,【解】 用最小元素

21、法求得初始基本可行解如表5-19,5.2 運輸單純形法 Transportation Simplex Method,因為有4個檢驗數(shù)小于零，所以這組基本可行解不是最優(yōu)解。對應(yīng)的非基變量x11進(jìn)基.,對應(yīng)的非基變量x11進(jìn)基.,x11的閉回路是,x33最小，x33是出基量，調(diào)整量=15,5.2 運輸單純形法 Transportation Simplex Method,在x11的閉回路上x11、x32、x23分別加上15，x12、x33、x21分別減去15，并且在x33處打上記號“”作為基變量，其余變量不變，調(diào)整后得到一組新的基可行解：,5.2 運輸單純形法 Transportation Simp

22、lex Method,5.2 運輸單純形法 Transportation Simplex Method,非基變量的檢驗數(shù)：,13=3，14=1，22=0，24=8，31=1，33=4,所有檢驗數(shù)ij 0因而得到最優(yōu)解,最小運費,5.2 運輸單純形法 Transportation Simplex Method,【例5-10】有四項工作指派給甲、乙兩人完成，每人完成兩項工作兩人完成各項工作的時間（小時）見表5-18，怎樣安排工作使總時間最少,表5-18,【解】 設(shè)xij(i=1,2；j=1,2,3,4)為第i人完成第j項工作的狀態(tài),數(shù)學(xué)模型為,5.2 運輸單純形法 Transportation S

23、implex Method,寫出表5-18的平衡運輸表5-19, 用運輸單純形法求解得到最優(yōu)表5-20,表5-19,表5-20,最優(yōu)的工作分配是：甲完成工作C和D，乙完成工作A和B，總時間Z47（小時）,5.2 運輸單純形法 Transportation Simplex Method,設(shè)數(shù)學(xué)模型為,5.2.4 最大值問題,5.2 運輸單純形法 Transportation Simplex Method,第一種方法：將極大化問題轉(zhuǎn)化為極小化問題。設(shè)極大化問題的運價表為C=（Cij）mn，用一個較大的數(shù)M（MmaxCij）去減每一個Cij得到矩陣C=（Cij）mn ，其中C/ij=MCij0,將C

24、/作為極小化問題的運價表，用表上用業(yè)法求出最優(yōu)解，目標(biāo)函數(shù)值為,例如，下列矩陣C是Ai（I=1，2，3）到Bj的單位貨物利潤,運輸部門如何安排運輸方案使總利潤最大.,8 14 9,5.2 運輸單純形法 Transportation Simplex Method,用最小元素法求初始方案得,11=8,12=4,21=2,23=2全部非負(fù),得到最優(yōu)運輸方案X,最大利潤Z=89+1010+68+54=240,第二種方法:所有非基變量的檢驗數(shù)ij0時最優(yōu).求初始運輸方案可采用最大元素法.如上例,用最大元素得到 的初始運輸方案:,8 14 9,求檢驗數(shù):11=8,12=4,21=2,23=2,全部非正,得

25、到最優(yōu)解運輸方案,結(jié)果與第一種方法相同.,5.2 運輸單純形法 Transportation Simplex Method,當(dāng)總產(chǎn)量與總銷量不相等時,稱為不平衡運輸問題.這類運輸問題在實際中常常碰到,它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。,1.當(dāng)產(chǎn)大于銷時,即,數(shù)學(xué)模型為,5.2.5 不平衡運輸問題,5.2 運輸單純形法 Transportation Simplex Method,由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部 運送完，必須就地庫存，即每個產(chǎn)地設(shè)一個倉庫，庫存量 為xi，n+1（i=1，2，m），總的庫存量為,5.2 運輸單純形法 Transportatio

26、n Simplex Method,bn+1作為一個虛設(shè)的銷地Bn+1的銷量。各產(chǎn)地Ai到Bn+1的運價為零，即Ci，n+1=0,（i=1，m）。則平衡問題的數(shù)學(xué)模型為：,具體求解時,只在運價表右端增加一列Bn+1，運價為零,銷量為bn+1即可,5.2 運輸單純形法 Transportation Simplex Method,2.當(dāng)銷大于產(chǎn)時,即,數(shù)學(xué)模型為,5.2 運輸單純形法 Transportation Simplex Method,由于總銷量大于總產(chǎn)量,故一定有些需求地不完全滿足,這時虛設(shè)一個產(chǎn)地Am+1，產(chǎn)量為,xm+1,j 是Am+1運到Bj的運量，也是Bj不能滿足需要的數(shù)量。Am+

27、1到Bj的運價為零,即Cm+1,j=0(j=1,2, ,n),5.2 運輸單純形法 Transportation Simplex Method,銷大于產(chǎn)平衡問題的數(shù)學(xué)模型為 ：,具體計算時，在運價表的下方增加一行Am+1，運價為零。產(chǎn)量為am+1即可。,5.2 運輸單純形法 Transportation Simplex Method,因為有：,【例5-11】求下列表中極小化運輸問題的最優(yōu)解。,所以是一個產(chǎn)大于銷的運輸問題。,5.2 運輸單純形法 Transportation Simplex Method,表5-21,表中A2不可達(dá)B1，用一個很大的正數(shù)M表示運價C21。虛設(shè)一個銷量為b5=18

28、0160=20的銷地B5，Ci5=0，i=1，2，3，4。表的右邊增添一列,這樣可得新的運價表：,5.2 運輸單純形法 Transportation Simplex Method,下表為計算結(jié)果。可看出：產(chǎn)地A4還有20個單位沒有運出。,5.2 運輸單純形法 Transportation Simplex Method,【例5-12】在例5-11中，假定B1的需要量是20到60之間，B2的需要量是50到70，試求極小化問題的最優(yōu)解。,5.2.6 需求量不確定的運輸問題,5.2 運輸單純形法 Transportation Simplex Method,先作如下分析：（1）總產(chǎn)量為180，B1，B4

29、的最低需求量 20+50+35+45=150，這時屬產(chǎn)大于銷；,（2）B1，B4的最高需求是60+70+35+45=210，這時屬銷大于產(chǎn),（3）虛設(shè)一個產(chǎn)地A5，產(chǎn)量是210180=30，A5的產(chǎn)量只能供應(yīng)B1或B2。,（4）將B1與B2各分成兩部分 的需求量是20， 的需求量是40， 的需求量分別是50與20，因此 必須由A1，A4供應(yīng)， 可由 A1、A5供應(yīng)。,（5）上述A5不能供應(yīng)某需求地的運價用大M表示，A5到 、 的運價為零。得到下表的產(chǎn)銷平衡表。,5.2 運輸單純形法 Transportation Simplex Method,得到這樣的平衡表后，計算得到最優(yōu)方案表5-23。,5

30、.2 運輸單純形法 Transportation Simplex Method,表5-22,表中：x131=0是基變量,說明這組解是退化基本可行解,空格處的變量是非基變量。B1，B2，B3，B4實際收到產(chǎn)品數(shù)量分別是50，50，35和45個單位。,5.2 運輸單純形法 Transportation Simplex Method,表5-23,5.2.7 中轉(zhuǎn)問題,產(chǎn)地,銷地,3,5,4,2,3,1,6,8,2,3,2,9,圖5.2,A4,A5,2,2,7,15,中轉(zhuǎn)地,3,4,1,3,5.2 運輸單純形法 Transportation Simplex Method,5.2 運輸單純形法 Tran

31、sportation Simplex Method,設(shè)xij為Ai到Aj的運量，i，j=1，2，m+n+r則中轉(zhuǎn)運輸問題的數(shù)學(xué)模型為,產(chǎn)大于銷時將式(5-3a)改為“”約束，銷大于產(chǎn)時將式(5-3c)改為“”約束,5.2 運輸單純形法 Transportation Simplex Method,5.4 指派問題 assignment problem,5.4 指派問題assignment problem,5.4.1問題的提出與數(shù)學(xué)模型 指派問題也稱分配問題,是一種特殊的整數(shù)規(guī)劃問題,是0-1整數(shù)線性規(guī)劃問題.在生活中經(jīng)常會遇到這樣的問題,某單位需要指派m個人去完成m項任務(wù),每個人只做一工作,同時

32、,每項工作只由一個人完成.由于各人的專長不同,每個人完成各項任務(wù)的效率也不同.于是產(chǎn)生了應(yīng)指派哪一個人去完成哪一項任務(wù),使完成項任務(wù)的總效率最高(如所用的時間為最少)的問題.這類問題為指派問題或分配問題.,5.4 指派問題assignment problem,引例 人事部門欲安排四人到四個不同的崗位工作，每個崗位一個人經(jīng)考核四人在不同崗位的成績（百分制）如下表所示，如何安排他們的工作使總成績最好。,5.4 指派問題assignment problem,5.4 指派問題assignment problem,數(shù)學(xué)模型為：,甲,乙,丙,丁,A,B,C,D,圖5. 3,5.4 指派問題assignment problem,5.4 指派問題assignment problem,5.4 指派問題assignment problem,5.4 指派問題assignment problem,5.4 指派問題assignment problem,5.4 指派問題assignment problem,5.4 指派問題assignment problem,5.4 指派問題assignment problem,5.4 指派問題assignment problem,5.4 指派問題assignment problem,5.4 指派問題assignment problem,5.4 指派問題