運籌學(xué)運籌帷幄之中決勝千里之外運輸問題TransportationProblem第三章第三章運輸問題本章主要內(nèi)容：運輸規(guī)劃問題的數(shù)學(xué)模型表上作業(yè)法運輸問題的應(yīng)用第三章運輸問題例3.1某公司從兩個產(chǎn)地A1、A2將物品運往三個銷地B1,B2,B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最小？B1B2B3產(chǎn)量A1646200A2655300銷量150150200第三章運輸問題解：產(chǎn)銷平衡問題：總產(chǎn)量=總銷量＝500

設(shè)xij為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列運輸量表：B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200第三章運輸問題MinC=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）第三章運輸問題-數(shù)學(xué)模型運輸問題的一般形式：產(chǎn)銷平衡A1、A2、…、Am

表示某物資的m個產(chǎn)地；B1、B2、…、Bn

表示某物質(zhì)的n個銷地；ai

表示產(chǎn)地Ai的產(chǎn)量；bj

表示銷地Bj

的銷量；cij表示把物資從產(chǎn)地Ai運往銷地Bj的單位運價。設(shè)xij為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列一般運輸量問題的模型：第三章運輸問題-數(shù)學(xué)模型已知資料如下：

銷產(chǎn)地地產(chǎn)量產(chǎn)銷平衡銷量運價第三章運輸問題-數(shù)學(xué)模型當(dāng)產(chǎn)銷平衡時，其模型如下：第三章運輸問題-數(shù)學(xué)模型運輸問題約束條件的系數(shù)矩陣mn第三章運輸問題-數(shù)學(xué)模型

特征：

1、平衡運輸問題必有可行解，也必有最優(yōu)解；

2、運輸問題的基本可行解中應(yīng)包括m+n－1

個基變量。第三章運輸問題-數(shù)學(xué)模型當(dāng)產(chǎn)大于銷時，其模型如下：第三章運輸問題-數(shù)學(xué)模型當(dāng)產(chǎn)小于銷時，其模型如下：第三章運輸問題第三章運輸問題

運輸問題的求解思路第三章運輸問題-表上作業(yè)法計算步驟：(1)找出初始調(diào)運方案。即在(m×n)產(chǎn)銷平衡表上給出m+n-1個數(shù)字格。(最小元素法、西北角法或伏格爾法）(2)求檢驗數(shù)。（閉回路法或位勢法）判別是否達(dá)到最優(yōu)解。如已是最優(yōu)解，則停止計算，否則轉(zhuǎn)到下一步。(3)對方案進(jìn)行改善，找出新的調(diào)運方案。（表上閉回路法調(diào)整）確定m+n-1個基變量(4)重復(fù)（2）、（3），直到求得最優(yōu)調(diào)運方案?？崭竦谌逻\輸問題-表上作業(yè)法表上作業(yè)法是一種求解運輸問題的特殊方法，其實質(zhì)是單純形法。步驟描述方法第一步求初始基行可行解（初始調(diào)運方案）最小元素法、西北角法、伏格爾法第二步求檢驗數(shù)并判斷是否得到最優(yōu)解當(dāng)非基變量的檢驗數(shù)σij全都非負(fù)(求min)時得到最優(yōu)解，若存在檢驗數(shù)σij<0，說明還沒有達(dá)到最優(yōu)，轉(zhuǎn)第三步。閉回路法和位勢法第三步調(diào)整運量，即換基，選一個變量出基，對原運量進(jìn)行調(diào)整得到新的基可行解，轉(zhuǎn)入第二步第三章運輸問題-表上作業(yè)法例3.2某運輸資料如下表所示：單位銷地運價產(chǎn)地產(chǎn)量311310719284741059銷量3656問：應(yīng)如何調(diào)運可使總運輸費用最?。?、求初始方案：最小元素法、西北角法、伏格爾法第三章運輸問題-表上作業(yè)法

基本思想是就近供應(yīng)，即從運價最小的地方開始供應(yīng)（調(diào)運），然后次小，直到最后供完為止。B1B2B3B4產(chǎn)量A17A2

4A39銷量3656311310192741058總的運輸費＝(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元方法1：最小元素法341633第三章運輸問題-表上作業(yè)法練習(xí)

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1675314A2842727A35910619銷量221312131213131912第三章運輸問題-表上作業(yè)法

（2）西北角法（或左上角法）此法是純粹的人為的規(guī)定，沒有理論依據(jù)和實際背景，但它易操作，特別適合在計算機上編程計算，因而受歡迎。方法如下：365674934490656404902562029005620090036360000000340002200036第三章運輸問題-表上作業(yè)法在滿足約束條件下盡可能的給最左上角的變量最大值.

銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116A22103910A38511622銷量8141214488864814所以，初始基可行解為：(8,8,4,8,14)目標(biāo)函數(shù)值Z＝372例3.3某運輸資料如下表所示：第三章運輸問題-表上作業(yè)法練習(xí)

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1675314A2842727A35910619銷量22131213813131466第三章運輸問題-表上作業(yè)法

最小元素法的缺點是：為了節(jié)省一處的費用，有時造成在其他處要多花幾倍的運費。伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運費就近供應(yīng)，就考慮次小運費，這就有一個差額。差額越大，說明不能按最小運費調(diào)運時，運費增加越多。因而對差額最大處，就應(yīng)當(dāng)采用最小運費調(diào)運。例如下面兩種運輸方案。

最小元素法：15152012105815510總運費是z=10×8+5×2+15×1=10515152012105851510另一種方法：總運費z=10×5+15×2+5×1=85第三章運輸問題-表上作業(yè)法方法2：Vogel法1）從運價表中分別計算出各行和各列的最小運費和次最小運費的差額，并填入該表的最右列和最下行。B1B2B3B4產(chǎn)量行差額A170A2

41A391銷量3656列差額25133113101927410583-3=02-1=15-4=13-1=29-4=53-2=18-5=3第三章運輸問題-表上作業(yè)法2）再從差值最大的行或列中找出最小運價確定供需關(guān)系和供需數(shù)量。當(dāng)產(chǎn)地或銷地中有一方數(shù)量供應(yīng)完畢或得到滿足時，劃去運價表中對應(yīng)的行或列。重復(fù)1)和2)，直到找出初始解為至。B1B2B3B4產(chǎn)量行差額A170A2

41A3

91銷量3656列差額25133113101927410586第三章運輸問題-表上作業(yè)法單位銷地運價產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額0231216×××3×第三章運輸問題-表上作業(yè)法該方案的總運費:(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元單位銷地運價產(chǎn)地產(chǎn)量行差額311310719284741059銷量3656列差額021216×××3×3×1×52第三章運輸問題-表上作業(yè)法

銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A1412411160A221039101A385116221銷量814121448列差額251314例3.4某運輸資料如下表所示：第三章運輸問題-表上作業(yè)法

銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A1412411160A221039101A385116222銷量814121448列差額251314例3.4某運輸資料如下表所示：88第三章運輸問題-表上作業(yè)法

銷地產(chǎn)地B1B2B3B4產(chǎn)量行差額A1412411160A221039101A38511622銷量814121448列差額314881224第三章運輸問題-表上作業(yè)法練習(xí)

銷地產(chǎn)地B1B2B3B4產(chǎn)量A1675314A2842727A35910619銷量221312131213121319第三章運輸問題-表上作業(yè)法2、最優(yōu)解的判別（檢驗數(shù)的求法）求檢驗數(shù)的方法有兩種：閉回路法位勢法（對偶變量法）

（1）閉合回路法：

σij≥0（因為目標(biāo)函數(shù)要求最小化）表格中有調(diào)運量的地方為基變量，空格處為非基變量?；兞康臋z驗數(shù)σij＝0，非基變量的檢驗數(shù)σij≥0。σij<0表示運費減少，σij>0表示運費增加。第三章運輸問題-表上作業(yè)法

閉回路：從空格出發(fā)順時針(或逆時針)畫水平(或垂直)直線，遇到填有運量的方格可轉(zhuǎn)90°，然后繼續(xù)前進(jìn)，直到到達(dá)出發(fā)的空格所形成的閉合回路。調(diào)運方案的任意空格存在唯一閉回路。注：1.每一空格有且僅有一條閉回路；

2.如果某數(shù)字格有閉回路，則此解不是可行解。若令則—運費的增量分析：第三章運輸問題-表上作業(yè)法以最小元素法的初始解為例。假設(shè)產(chǎn)地A1供應(yīng)1個單位的物品給銷地B1。則解的變化和目標(biāo)函數(shù)的變化如何。

銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116106A2210391082A38511622148銷量814121448第三章運輸問題-表上作業(yè)法要保證產(chǎn)銷平衡，則

稱為閉回路

銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116106A2210391082A38511622148銷量8141214481第三章運輸問題-表上作業(yè)法

銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116106A2210391082A38511622148銷量81412144812第三章運輸問題-表上作業(yè)法

銷地產(chǎn)地B1B2B3B4產(chǎn)量A141241116106A2210391082A38511622148銷量814121448121-11210檢驗數(shù)中有負(fù)數(shù)，說明原方案不是最優(yōu)解。練習(xí)

銷地產(chǎn)地B1B2B3B4產(chǎn)量A167531414A28427278136A35910619613銷量221312135579-3-11第三章運輸問題-表上作業(yè)法第三章運輸問題-表上作業(yè)法

uivjm個n個（2）位勢法（對偶變量法）設(shè)其對偶變量為：第三章運輸問題-表上作業(yè)法

ui?vj無約束（i=1,2,…,m;j=1,2,…,n)標(biāo)準(zhǔn)型運輸問題的對偶問題模型為：則運輸問題變量xij的檢驗數(shù)為：第三章運輸問題-表上作業(yè)法用位勢法對初始方案進(jìn)行最優(yōu)性檢驗的方法：1）在給定初始解的表上增加一行和一列，在列中填入ui，在行中填入vj。2）令u1＝0，再按cij-(ui+vj)=0（基變量的檢驗數(shù)=0），求出其余的ui與vj。3）由ij=Cij-（ui+vj），求出非基變量的檢驗數(shù)。第三章運輸問題-表上作業(yè)法B1B2B3B4uiA1A2A3vj311310192741058u1u2u3v3v4v1v2注意：基變量的檢驗數(shù)i

j=Ci

j-（ui+vj）=0436313第三章運輸問題-表上作業(yè)法B1B2B3B4uiA1A2A3vj3113101927410580-1-531029令u1=0u1+v3=3u1+v4=10u2+v3=2u2+v1=1u3+v2=4u3+v4=5436313第三章運輸問題-表上作業(yè)法21039vj-5A3-1A20A1uiB4B3B2B1436313（1）（2）（1）（-1）（10）（12）當(dāng)存在非基變量的檢驗數(shù)ij≥0，說明現(xiàn)行方案為最優(yōu)方案，否則目標(biāo)成本還可以進(jìn)一步減小。注意：非基變量的檢驗數(shù)i

j=cij-（ui+vj）11=c11-（u1+v1）=3-(0+2)=131=c31-（u3+v1）=7-(2-5)=1024=c24-（u2+v4）=8-(10-1)=-112=c12-（u1+v2）=11-(0+9)=233=c33-（u3+v3）=10-(3-5)=1231131019274105822=c22-（u2+v2）=9-(9-1)=1第三章運輸問題-表上作業(yè)法3、解的改進(jìn)——閉合回路調(diào)整法（原理同單純形法）

當(dāng)在表中空格處出現(xiàn)負(fù)檢驗數(shù)時，表明未得最優(yōu)解。若有兩個或兩個以上的負(fù)檢驗數(shù)時，一般選用其中最小的負(fù)檢驗數(shù)，以它對應(yīng)的空格為調(diào)入格，即以它對應(yīng)的非基變量為換入變量。做一閉合回路。(1)確定換入基的變量：當(dāng)存在非基變量的檢驗數(shù)kl<0且kl=min{ij}時，以Xkl為換入變量，找出它在運輸表中的閉合回路。接上例：ijj,i)(minσ=-1<0Xpq=X24為換入變量解的改進(jìn)的具體步驟：第三章運輸問題-表上作業(yè)法21039vj-5A3-1A20A1uiB4B3B2B1436313311310192741058（1）（2）（1）（-1）（10）（12）(2)頂點編號：以空格(Ak,Bl)(或進(jìn)基變量xik）為第一個奇數(shù)頂點，沿閉回路的順（或逆）時針方向前進(jìn)，對閉回路上的頂點依次編號。1324第三章運輸問題-表上作業(yè)法21039vj-5A3-1A20A1uiB4B3B2B1436313311310192741058（1）（2）（1）（-1）（10）（12）(2)頂點編號：以空格(Ak,Bl)(或進(jìn)基變量xik）為第一個奇數(shù)頂點，沿閉回路的順（或逆）時針方向前進(jìn)，對閉回路上的頂點依次編號。1324換出變量X23第三章運輸問題-表上作業(yè)法(3)確定換出基的變量：在該閉回路上，從所有偶數(shù)號格點的調(diào)運量中選出最小值的頂點（格子），以該格子中的變量為換出變量。(4)確定新的運輸方案：以換出變量的運輸量為調(diào)整量θ

，將該閉回路上所有奇數(shù)號格的調(diào)運量加上調(diào)整量θ

，所有偶數(shù)號格的調(diào)運量減去θ

，其余的不變，這樣就得到一個新的調(diào)運方案。該運輸方案的總運費比原運輸方案減少，改變量等于換出變量的檢驗數(shù)×θ。(5)然后，再對得到的新解進(jìn)行最優(yōu)性檢驗，加不是最優(yōu)解，就重復(fù)以上步驟繼續(xù)進(jìn)行調(diào)整，一直到得出最優(yōu)解為止。第三章運輸問題-表上作業(yè)法21039vj-5A3-1A20A1uiB4B3B2B13631(＋1)(＋1)(－1)(－1)31131019274105843第三章運輸問題-表上作業(yè)法31039vj-5A3-2A20A1uiB4B3B2B1536312311310192741058重新求所有非基變量的檢驗數(shù)：第三章運輸問題-表上作業(yè)法31039vj-5A3-2A20A1uiB4B3B2B1536312（2）（2）（1）（12）（9）（0）當(dāng)所有非基變量的檢驗數(shù)均非負(fù)時，則當(dāng)前調(diào)運方案即為最優(yōu)方案，如表此時最小總運費：Z=(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元311310192741058第三章運輸問題-表上作業(yè)法分析實際問題列出產(chǎn)銷平衡表及單位運價表確定初始調(diào)運方案（最小元素法或Vogel法）求檢驗數(shù)（位勢法）所有檢驗數(shù)≥0找出絕對值最大的負(fù)檢驗數(shù)，用閉合回路調(diào)整，得到新的調(diào)運方案得到最優(yōu)方案，算出總運價第三章運輸問題-表上作業(yè)法表上作業(yè)法計算中的問題：（1）若運輸問題的某一基可行解有多個非基變量的檢驗數(shù)為負(fù)，在繼續(xù)迭代時，取它們中任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善，但通常取σij<0中最小者對應(yīng)的變量為換入變量。（2）無窮多最優(yōu)解 產(chǎn)銷平衡的運輸問題必定存最優(yōu)解。如果非基變量的σij＝0，則該問題有無窮多最優(yōu)解。如上例：σ11的檢驗數(shù)是0，經(jīng)過調(diào)整，可得到另一個最優(yōu)解。第三章運輸問題-表上作業(yè)法⑵退化解：

※表格中一般要有(m+n-1)個數(shù)字格。但有時在分配運量時則需要同時劃去一行和一列，這時需要補一個0，以保證有(m+n-1)個數(shù)字格作為基變量。一般可在劃去的行和列的任意空格處加一個0即可。

※利用進(jìn)基變量的閉回路對解進(jìn)行調(diào)整時，標(biāo)有負(fù)號的最小運量（超過2個最小值）作為調(diào)整量θ，選擇任意一個最小運量對應(yīng)的基變量作為出基變量，并打上“×”以示作為非基變量。第三章運輸問題-表上作業(yè)法

銷地產(chǎn)地B1B2B3B4產(chǎn)量A116A210A322銷量81412141241148310295116(0)(2)(9)(2)(1)(12)81242814如下例中σ11檢驗數(shù)是0，經(jīng)過調(diào)整，可得到另一個最優(yōu)解。第三章運輸問題-表上作業(yè)法

銷地產(chǎn)地B1B2B3B4產(chǎn)量A17A24A39銷量36562011443137782106×3×416×06×××在x12、x22、x33、x34中任選一個變量作為基變量，例如選x34例：用最小元素法求初始可行解第三章運輸問題-產(chǎn)銷不平衡一、產(chǎn)銷不平衡的運輸問題 當(dāng)總產(chǎn)量與總銷量不相等時,稱為不平衡運輸問題，這類運輸問題在實際中常常碰到,它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。

當(dāng)產(chǎn)大于銷時，即：數(shù)學(xué)模型為：第三章運輸問題-產(chǎn)銷不平衡由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運送完，必須就地庫存，即每個產(chǎn)地設(shè)一個倉庫，假設(shè)該倉庫為一個虛擬銷地Bn+1，bn+1作為一個虛設(shè)銷地Bn+1的銷量(即庫存量)。各產(chǎn)地Ai到Bn+1的運價為零，即Ci,n+1=0,（i=1，…，m）。則平衡問題的數(shù)學(xué)模型為：具體求解時,只在運價表右端增加一列Bn+1，運價為零,銷量為bn+1即可第三章運輸問題-產(chǎn)銷不平衡當(dāng)銷大于產(chǎn)時，即：數(shù)學(xué)模型為：由于總銷量大于總產(chǎn)量,故一定有些需求地不完全滿足,這時虛設(shè)一個產(chǎn)地Am+1，產(chǎn)量為：第三章運輸問題-產(chǎn)銷不平衡銷大于產(chǎn)化為平衡問題的數(shù)學(xué)模型為：具體計算時，在運價表的下方增加一行Am+1，運價為零。產(chǎn)量為am+1即可。第三章運輸問題-產(chǎn)銷不平衡例3.4求下列表中極小化運輸問題的最優(yōu)解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因為有：第三章運輸問題-產(chǎn)銷不平衡所以是一個產(chǎn)大于銷的運輸問題。表中A2不可達(dá)B1，用一個很大的正數(shù)M表示運價C21。虛設(shè)一個銷量為b5=180-160=20，Ci5=0，i=1,2,3,4，表的右邊增添一列，得到新的運價表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180第三章運輸問題-產(chǎn)銷不平衡下表為計算結(jié)果?？煽闯觯寒a(chǎn)地A4還有20個單位沒有運出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180用前面的方法求運輸方案：第三章運輸