運籌學(xué)04-運輸問題

1

運籌學(xué)第五章

運輸問題

TransportationProblems2

本章內(nèi)容重點運輸模型數(shù)學(xué)模型表上作業(yè)法運輸模型的應(yīng)用3人們在從事生產(chǎn)活動中，不可避免地要進行物資調(diào)運工作。如某時期內(nèi)將生產(chǎn)基地的煤、鋼鐵、糧食等各類物資，分別運到需要這些物資的地區(qū)，根據(jù)各地的生產(chǎn)量和需要量及各地之間的運輸費用，如何制定一個運輸方案，使總的運輸費用最小。這樣的問題稱為運輸問題。實際背景4運輸問題舉例某公司有三個生產(chǎn)設(shè)施分別位于杜魯斯

(DL),

納瑞多(LR),和坦帕(TP),三個倉庫分別位于摩德斯托(MD),奧瑪哈(OM)和波斯頓(BS)。各個工廠的生產(chǎn)能力不同，每個倉庫的需求也不同。對于給出的不同的生產(chǎn)和運輸成本，如何編制運輸方案才能使總成本最?。?運輸模型方法舉例DL生產(chǎn)能力：100單位TP生產(chǎn)能力：300單位LR生產(chǎn)能力：300單位工廠位置6MD需求：300單位BS需求：200單位OM需求：200單位DL生產(chǎn)能力：100單位LR生產(chǎn)能力：300單位TP生產(chǎn)能力：300單位運輸模型方法舉例倉庫位置7DL生產(chǎn)能力：100單位TP生產(chǎn)能力：300單位BS需求：200單位OM需求：200單位LR生產(chǎn)能力：300單位運輸模型方法舉例從坦帕發(fā)貨MD需求：300單位8DL生產(chǎn)能力：100單位MD需求：300單位TP生產(chǎn)能力：300單位BS需求：200單位OM需求：200單位LR生產(chǎn)能力：300單位運輸模型方法舉例從杜魯斯發(fā)貨9DL生產(chǎn)能力：100單位MD需求：300單位TP生產(chǎn)能力：300單位BS需求：200單位OM需求：200單位LR生產(chǎn)能力：300單位運輸模型方法舉例從納瑞多發(fā)貨10DL生產(chǎn)能力：100單位MD需求：300單位TP生產(chǎn)能力：300單位BS需求：200單位OM需求：200單位?1984-1994T/MakerCo.LR生產(chǎn)能力：300單位運輸模型方法舉例$5$3$4$7$8$9$5$4$3每條路線上應(yīng)當(dāng)運多少以實現(xiàn)最低成本?11運輸問題的表格

倉庫生產(chǎn)工廠MDOMBS供應(yīng)量DL534100LR834300TP957300需求量30020020012產(chǎn)銷平衡運輸問題的一般數(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，在滿足各地需要的前提下，求總運輸費用最小的調(diào)運方案。設(shè)xij(i=1,2,…，m；j=1,2,…,n)為第i個產(chǎn)地到第j個銷地的運量，則數(shù)學(xué)模型為：13設(shè)平衡運輸問題的數(shù)學(xué)模型為：運輸問題的特點：1.有m+n個約束，mn個變量2.特殊的系數(shù)矩陣3.有m+n－1個基變量4.運輸問題一定存在可行解，也一定存在最優(yōu)解

14m行n行15故r(A)=m+n－1所以運輸問題有m+n－1個基變量。為了在mn個變量中找出m+n－1個變量作為一組基變量，就是要在A中找出m+n-1個線性無關(guān)的列向量，也即是在運輸表格中確定m+n-1個格的運輸量不為零，而剩下的(m-1)(n-1)格為零。16運輸單純形法

表上作業(yè)法17設(shè)平衡運輸問題的數(shù)學(xué)模型為：18運輸單純形法也稱為表上作業(yè)法，是直接在運價表上求最優(yōu)解的一種方法，它的步驟是：

第一步：求初始基行可行解（初始調(diào)運方案）。常用的方法有最小元素法、元素差額法（Vogel近似法）。

第二步：求檢驗數(shù)并判斷是否得到最優(yōu)解。常用求檢驗的方法有閉回路法和位勢法，當(dāng)非基變量的檢驗數(shù)λij全都非負時得到最優(yōu)解，若存在檢驗數(shù)λlk<0，說明還沒有達到最優(yōu)，轉(zhuǎn)第三步。

第三步：調(diào)整運量，即換基。選一個變量出基，對原運量進行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步。19初始基可行解1.最小元素法最小元素法的思想是就近優(yōu)先運送，即最小運價Cij對應(yīng)的變量xij優(yōu)先賦值然后再在剩下的運價中取最小運價對應(yīng)的變量賦值并滿足約束，依次下去，直到最后得到一個初始基可行解。20【例】求表所示的運輸問題的初始基可行解。銷地產(chǎn)地B1B2B3產(chǎn)量A1A2A3847634758304525銷量60301010021

BjAiB1B2B3產(chǎn)量A186730A243545A374825銷量603010100【解】30××15×10×252022【例】求表給出的運輸問題的初始基本可行解．

B1B2B3B4aiA14104420A2773815A31210615bj51025105023

BjAiB1B2B3B4aiA14104420A2773815A31210615bj510251050【解】5××10××××015×101024初始基本可行解可用下列矩陣表示表5－11中，基變量恰好是3+4－1=6個且不包含閉回路，是一組基變量，其余標有符號×的變量是非基變量252．元素差額法（Vogel法）最小元素法只考慮了局部運輸費用最小。有時為了節(jié)省某一處的運費，而在其它處可能運費很大。元素差額法對最小元素法進行了改進，考慮到產(chǎn)地到銷地的最小運價和次小運價之間的差額，如果差額很大，就選最小運價先調(diào)運，否則會增加總運費。例如下面兩種運輸方案前一種按最小元素法求得，總運費是Z1=10×8+5×2+15×1=105后一種方案考慮到C11與C21之間的差額是8－2=6，先調(diào)運x21，再是x22，其次是x12這時總運費Z2=10×5+15×2+5×1=85<Z1。26基于以上思路，元素差額法求初始基本可行解的步驟是：第一步：求出每行次小運價與最小運價之差，記為ui，i=1,2,…,m；同時求出每列次小運價與最小運價之差，記為vj，j=1，2，…，n；第二步：找出所有行、列差額的最大值，即L=max{ui，vi}，差額L對應(yīng)行或列的最小運價處優(yōu)先調(diào)運；

第三步：這時必有一列或一行調(diào)運完畢，在剩下的運價中再求最大差額，進行第二次調(diào)運，依次進行下去，直到最后全部調(diào)運完畢，就得到一個初始調(diào)運方案。用元素差額法求得的基本可行解更接近最優(yōu)解，所以也稱為近似方案。27B1B2B3B4aiA15891215A2172425A361013820bj201052560【例】用元素差額法求表5—13運輸問題的初始基本可行解?！窘狻壳笮胁铑~ui,i=1,2,3及列差額vj,j=1,2,3,4.計算公式為

ui=i行次小運價—i行最小運價

vj=j列次小運價—j例最小運價28

BjAiB1B2B3B4aiuiA158912153A21724251A3610138202bj201052560vj4174【】5××29

BjAiB1B2B3B4aiuiA158912153×A217242535A3610138202×bj201052560vj41－420×××0【】×30

BjAiB1B2B3B4aiuiA158912154×A2172425－5A3610138202×bj201052560vj－2－420×××0【】10×20531基本可行解為總運費Z=10×8+20×1+5×2+20×8=270。32求出一組基可行解后，判斷是否為最優(yōu)解，仍然是用檢驗數(shù)來判斷，記xij的檢驗數(shù)為λij由第一章知，求最小值的運輸問題的最優(yōu)判別準則是：所有非基變量的檢驗數(shù)都非負，則運輸方案最優(yōu)（即為最優(yōu)解）。求檢驗數(shù)的方法有兩種，閉回路法和位勢法。1．閉回路法求檢驗數(shù)求某一非基變量的檢驗數(shù)的方法是：在基本可行解矩陣中，以該非基變量為起點，以基變量為其它頂點，找一條閉回路，由起點開始，分別在頂點上交替標上代數(shù)符號+、-、+、-、…，以這些符號分別乘以相應(yīng)的運價，其代數(shù)和就是這個非基變量的檢驗數(shù)。求檢驗數(shù)33為一個閉回路，集合中的變量稱為回路的頂點，相鄰兩個變量的連線為閉回路的邊。

x25

x23

B1B2B3B4B5A1

A2

A3

x35A4

x43

x11x12x31

x42表3－3表3－3中閉回路的變量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8個頂點，這8個頂點間組成一條封閉的回路。34x11x12x32x33x41

B1B2B3A1

A2

A3

A4

x43閉回路的幾何特征：

1、相鄰兩個頂點的連線都是水平的或者豎直的。2、每個頂點都是直角的拐角點?；芈酚龅巾旤c必須轉(zhuǎn)90度與另一頂點連接3、每一行每一列只要存在某一閉回路的頂點，則必有該閉回路的兩個頂點4、一條回路中的頂點數(shù)一定是4或4以上的偶數(shù)35【定理2】若變量組B

包含有閉回路，則B中的變量對應(yīng)的例向量線性相關(guān)?！咀C】由線性代數(shù)知，向量組中部分向量組線性相關(guān)則該向量組線性相關(guān)，顯然，將C中列向量分別乘以正負號線性組合后等于零，即因而C中的列向量線性相關(guān)，所以B中列向量線性相關(guān)。從每一個空格出發(fā)一定存在和可以找到唯一的閉回路36【解】用最小元素法得到下列一組基本可行解【例】求下列運輸問題的一個初始基本可行解及其檢驗數(shù)。矩陣中的元素為運價Cij

，矩陣右邊的元素為產(chǎn)量ai

，下方的元素為銷量bj

。37矩陣中打“×”的位置是非基變量，其余是基變量，這里只求非基變量的檢驗數(shù)。求λ11，先找出x11的閉回路，對應(yīng)的運價為再用正負號分別交替乘以運價有直接求代數(shù)和得38

BjAiB1B2B3B4aiA1938470×6010×A2765150××2030A3210922010×10×bj1060403080966-339同理可求出其它非基變量的檢驗數(shù)：這里λ34<0，說明這組基本可行解不是最優(yōu)解。只要求得的基變量是正確的且數(shù)目為m+n－1，則某個非基變量的閉回路存在且唯一，因而檢驗數(shù)唯一。402．位勢法求檢驗位勢法求檢驗數(shù)是根據(jù)對偶理論推導(dǎo)出來的一種方法。設(shè)平衡運輸問題為設(shè)前m個約束對應(yīng)的對偶變量為ui,i=1,2,…,m，后n個約束對應(yīng)的對偶變量為vj,j=1,2,…,n則運輸問題的對偶問題是41加入松馳變量λij將約束化為等式ui+vj+λij=cij記原問題基變量XB的下標集合為I，由第二章對偶性質(zhì)知，原問題xij的檢驗數(shù)是對偶問題的松弛變量λij當(dāng)（i，j）∈I時λij=0，因而有解上面第一個方程，將ui、vj代入第二個方程求出λij42【例】用位勢法求例7給出的初始基本可行解的檢驗數(shù)?！窘狻康谝徊角笪粍輚1、u2、u3及v1、v2、v3、v4。10604030令u1=0得到位勢的解為43再由公式求出檢驗數(shù)，其中Cij是非基變量對應(yīng)的運價。44調(diào)整運量前面講過，當(dāng)某個檢驗數(shù)小于零時，基可行解不是最優(yōu)解，總運費還可以下降，這時需調(diào)整運輸量，改進原運輸方案，使總運費減少，改進運輸方案的步驟是：第一步：確定進基變量第二步：確定出基變量在進基變量xik的閉回路中，標有負號的最小運量作為調(diào)整量θ，θ對應(yīng)的基變量為出基變量，并打上“×”以示作為非基變量。第三步：調(diào)整運量在進基變量的閉回路中標有正號的變量加上調(diào)整量θ，標有負號的變量減去調(diào)整量θ，其余變量不變，得到一組新的基可行解，然后求所有非基變量的檢驗數(shù)重新檢驗。45

BjAiB1B2B3B4aiA1589270×40×30A236478045×35×A3101214540×2515×bj45655030190【例】求下列運輸問題的最優(yōu)解【解】用最小元素法求得初始基本可行解如表46求非基變量的檢驗數(shù),用閉回路法得：

BjAiB1B2B3B4aiA1589270×40×30A236478045×35×A3101214540×2515×bj4565503019047因為有4個檢驗數(shù)小于零，所以這組基本可行解不是最優(yōu)解。對應(yīng)的非基變量x11進基.對應(yīng)的非基變量x11進基.x11的閉回路是x33最小，x33是出基量，調(diào)整量θ=15

BjAiB1B2B3B4aiA1589270×40×30A236478045×35×A3101214540×2515×bj4565503019048

BjAiB1B2B3B4ai30A236478030×50×A3101214540×40××bj45655030190在x11的閉回路上x11、x32、x23分別加上15，x12、x33、x21分別減去15，并且在x33處打上記號“×”作為非基變量，其余變量不變，調(diào)整后得到一組新的基可行解：49

BjAiB1B2B3B4ai30A236478030×50×A3101214540×40××bj45655030190重新求所有非基變量的檢驗數(shù)得λ13=3，λ22=0，λ24=7，λ31=1，λ33=4，λ34=－1λ34=－1<0,說明還沒有得到最優(yōu)解，x34進基，在x34的閉回路中，標負號的變量x14和x32，調(diào)整量為50

BjAiB1B2B3B4ai×A236478030×50×A3101214540×10×30bj45655030190x14出基，調(diào)整運量得到：再求非基變量的檢驗數(shù)：λ13=3，λ14=1，λ22=0，λ24=8，λ31=1，λ33=451再求非基變量的檢驗數(shù)：λ13=3，λ14=1，λ22=0，λ24=8，λ31=1，λ33=4所有檢驗數(shù)λij≥0因而得到最優(yōu)解最小運費52解的幾種情況無窮多：某個空格的檢驗數(shù)為0退化解：退化的格中必須要填一個0，表示是數(shù)字格53

當(dāng)總產(chǎn)量與總銷量不相等時,稱為不平衡運輸問題.這類運輸問題在實際中常常碰到,它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。1.當(dāng)產(chǎn)大于銷時,即數(shù)學(xué)模型為不平衡運輸問題54由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運送完，必須就地庫存，即每個產(chǎn)地設(shè)一個倉庫，庫存量為xi，n+1（i=1，2，…，m），總的庫存量為55bn+1作為一個虛設(shè)的銷地Bn+1的銷量。各產(chǎn)地Ai到Bn+1的運價為零，即Ci，n+1=0,（i=1，…，m）。則平衡問題的數(shù)學(xué)模型為：具體求解時,只在運價表右端增加一列Bn+1，運價為零,銷量為bn+1即可562.當(dāng)銷大于產(chǎn)時,即數(shù)學(xué)模型為57由于總銷量大于總產(chǎn)量,故一定有些需求地不完全滿足,這時虛設(shè)一個產(chǎn)地Am+1，產(chǎn)量為xm+1,j是Am+1運到Bj的運量，也是Bj不能滿足需要的數(shù)量。Am+1到Bj的運價為零,即Cm+1,j=0(j=1,2,…,n)58銷大于產(chǎn)平衡問題的數(shù)學(xué)模型為：具體計算時，在運價表的下方增加一行Am+1，運價為零。產(chǎn)量為am+1即可。59B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因為有：【例】求下列表中極小化運輸問題的最優(yōu)解。

所以是一個產(chǎn)大于銷的運輸問題。60表中A2不可達B1，用一個很大的正數(shù)M表示運價C21。虛設(shè)一個銷量為b5=180－160=20的銷地B5，Ci5=0，i=1，2，3，4。表的右邊增添一列這樣可得新的運價表：B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj206035452018061B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180下表為計算結(jié)果?？煽闯觯寒a(chǎn)地A4還有20個單位沒有運出。62上例中，假定B1的需要量是20到60之間，B2的需要量是50到70，試求極小化問題的最優(yōu)解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～210需求量不確定的運輸問題63先作如下分析：

（1）總產(chǎn)量為180，B1，…，B4的最低需求量

20+50+35+45=150，這時屬產(chǎn)大于銷；（2）B1，…，B4的最高需求是60+70+35+45=210，這時屬銷大于產(chǎn)（3）虛設(shè)一個產(chǎn)地A5，產(chǎn)量是210－180=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)銷平衡表。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj204050203545210得到這樣的平衡表后，計算得到最優(yōu)方案表5-29。表5-2865

B3B4aiA1

352560A2

40

40A30

10

2030A42030

50A5

10

20

30bj204050203545210

表中：x131=0是基變量,說明這組解是退化基本可行解,空格處的變量是非基變量。B1，B2，B3，B4實際收到產(chǎn)品數(shù)量分別是50，50，35和45個單位。66運輸模型的應(yīng)用67DF公司在接下來的三個月內(nèi)每月都要按照銷售合同生產(chǎn)出兩種產(chǎn)品。表中給出了在正常時間（RegularTime，縮寫為RT）和加班時間（OverTime，縮寫為OT）內(nèi)能夠生產(chǎn)這兩種產(chǎn)品的總數(shù)。月最大生產(chǎn)總量產(chǎn)品1/產(chǎn)品2銷售產(chǎn)品1/產(chǎn)品2單位生產(chǎn)成本(1000元/件)單位儲存成本（1000元/件）RTOTRTOT123108103235/33/54/415/1617/1519/1718/2020/1822/221/22/1（1）對這個問題進行分析，描述成一個運輸問題的產(chǎn)銷平衡表，使之可用運輸單純形法求解．（2）建立總成本最小的數(shù)學(xué)模型并求出最優(yōu)解68【解】表中括號內(nèi)的數(shù)據(jù)為產(chǎn)品序號

i↓j→123456生產(chǎn)能力ai1月(1)1月(2)2(1)2(2)3(1)3(2)11月RTx11x12x13x14

x15x161021月OTx21x22x23x24x25x26332月RTx33x34x35x36842月OTx43x44x45x46253月RTx55x561063月OTx65x663需要量bj533544691月(1)1月(2)2(1)2(2)3(1)3(2)剩余能力生產(chǎn)能力1月RT15