運(yùn)籌學(xué)04-運(yùn)輸問(wèn)題

1

運(yùn)籌學(xué)第五章

運(yùn)輸問(wèn)題

TransportationProblems2

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

(DL),

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

倉(cāng)庫(kù)生產(chǎn)工廠MDOMBS供應(yīng)量DL534100LR834300TP957300需求量30020020012產(chǎn)銷平衡運(yùn)輸問(wèn)題的一般數(shù)學(xué)模型設(shè)有m個(gè)產(chǎn)地（記作A1，A2，A3,…,Am），生產(chǎn)某種物資，其產(chǎn)量分別為a1,a2，…，am；有n個(gè)銷地（記作B1，B2，…，Bn），其需要量分別為b1,b2，…，bn；且產(chǎn)銷平衡，即。從第i個(gè)產(chǎn)地到j(luò)個(gè)銷地的單位運(yùn)價(jià)為cij，在滿足各地需要的前提下，求總運(yùn)輸費(fèi)用最小的調(diào)運(yùn)方案。設(shè)xij(i=1,2,…，m；j=1,2,…,n)為第i個(gè)產(chǎn)地到第j個(gè)銷地的運(yùn)量，則數(shù)學(xué)模型為：13設(shè)平衡運(yùn)輸問(wèn)題的數(shù)學(xué)模型為：運(yùn)輸問(wèn)題的特點(diǎn)：1.有m+n個(gè)約束，mn個(gè)變量2.特殊的系數(shù)矩陣3.有m+n－1個(gè)基變量4.運(yùn)輸問(wèn)題一定存在可行解，也一定存在最優(yōu)解

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

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

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

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

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

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

B1B2B3B4aiA14104420A2773815A31210615bj51025105023

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

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

ui=i行次小運(yùn)價(jià)—i行最小運(yùn)價(jià)

vj=j列次小運(yùn)價(jià)—j例最小運(yùn)價(jià)28

BjAiB1B2B3B4aiuiA158912153A21724251A3610138202bj201052560vj4174【】5××29

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

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

x25

x23

B1B2B3B4B5A1

A2

A3

x35A4

x43

x11x12x31

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

B1B2B3A1

A2

A3

A4

x43閉回路的幾何特征：

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

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

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

，下方的元素為銷量bj

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

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

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

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

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

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

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

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

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

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

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

20+50+35+45=150，這時(shí)屬產(chǎn)大于銷；（2）B1，…，B4的最高需求是60+70+35+45=210，這時(shí)屬銷大于產(chǎn)（3）虛設(shè)一個(gè)產(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)某需求地的運(yùn)價(jià)用大M表示，A5到、的運(yùn)價(jià)為零。得到下表的產(chǎn)銷平衡表。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj204050203545210得到這樣的平衡表后，計(jì)算得到最優(yōu)方案表5-29。表5-2865

B3B4aiA1

352560A2

40

40A30

10

2030A42030

50A5

10

20

30bj204050203545210

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

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