運籌學(xué)運輸問題

第五章運輸與指派問題

運輸問題的表示

運輸問題模型、運價表

運輸問題的求解

表上作業(yè)法

指派問題

運輸、指派和轉(zhuǎn)運問題，實際上都可以用

L.P.模型加以描述，所以可以認(rèn)為它們是L.P.的特例單列一章的原因在于：應(yīng)用面極廣，實踐性很強，而特有的數(shù)學(xué)結(jié)構(gòu)使得人們設(shè)計出了特別有效的方法對此類模型進(jìn)行求解本章的重點在：掌握表格化方法求解運輸簡述提出問題有A1，A2，A3三個磚瓦廠月產(chǎn)量分別為14，27，19萬塊，供應(yīng)B1，B2，B3，B4四個工地，月需要量分別為22，13，12，13萬塊，每萬塊運費如下表，求總運費最少的方案。A114A227A31922131213B1B2B3B46(千元）753842759106運輸問題運輸問題線性規(guī)劃模型供應(yīng)地約束需求地約束3.1運輸問題模型與性質(zhì)一、運輸問題的數(shù)學(xué)模型

1、運輸問題的一般提法：某種物資有若干產(chǎn)地和銷地，現(xiàn)在需要把這種物資從各個產(chǎn)地運到各個銷地，產(chǎn)量總數(shù)等于銷量總數(shù)。已知各產(chǎn)地的產(chǎn)量和各銷地的銷量以及各產(chǎn)地到各銷地的單位運價（或運距），問應(yīng)如何組織調(diào)運，才能使總運費（或總運輸量）最??？運輸問題的一般數(shù)學(xué)模型有m個產(chǎn)地生產(chǎn)某種物資，有n個地區(qū)需要該類物資令a1,a2,…,am表示各產(chǎn)地產(chǎn)量，b1,b2,…,bn表示各銷地的銷量，ai=bj

稱為產(chǎn)銷平衡設(shè)xij表示產(chǎn)地i

運往銷地j

的物資量，cij表示對應(yīng)的單位運費，則我們有運輸問題的數(shù)學(xué)模型如下：運輸問題二、運輸問題的特點與性質(zhì)1．約束方程組的系數(shù)矩陣具有特殊的結(jié)構(gòu)寫出式（3-1）的系數(shù)矩陣A，形式如下：m行n行矩陣的元素均為1或0；

每一列只有兩個元素為1，其余元素均為0；列向量Pij=(0,…，0，1，0，…,0,1,0,…0)T，其中兩個元素1分別處于第i行和第m+j行。

三、運輸問題的求解方法1、單純形法（為什麼？）2、表上作業(yè)法

由于問題的特殊形式而采用的更簡潔、更方便的方法3.2運輸問題的表上作業(yè)法

一、表上作業(yè)法的基本思想是:先設(shè)法給出一個初始方案,然后根據(jù)確定的判別準(zhǔn)則對初始方案進(jìn)行檢查、調(diào)整、改進(jìn)，直至求出最優(yōu)方案，如圖3-1所示。表上作業(yè)法和單純形法的求解思想完全一致，但是具體作法更加簡捷。

確定初始方案(初始基本可行解)

改進(jìn)調(diào)整（換基迭代）否

判定是否最優(yōu)？是結(jié)束最優(yōu)方案圖3-1運輸問題求解思路圖二、初始方案的確定

1、作業(yè)表（產(chǎn)銷平衡表）

初始方案就是初始基本可行解。

將運輸問題的有關(guān)信息表和決策變量——調(diào)運量結(jié)合在一起構(gòu)成“作業(yè)表”（產(chǎn)銷平衡表）。

表3-3是兩個產(chǎn)地、三個銷地的運輸問題作業(yè)表。調(diào)銷地運量產(chǎn)地

B1

B2

B3

產(chǎn)量

A1

c11

X11

c12

X12

c13

X13

a1

A2

c21

X21

c22

X22

c23

X23

a2銷量

b1

b2

b3表3-3運輸問題作業(yè)表（運價表）

3、舉例

例3-2甲、乙兩個煤礦供應(yīng)A、B、C三個城市用煤，各煤礦產(chǎn)量及各城市需煤量、各煤礦到各城市的運輸距離見表3-4，求使總運輸量最少的調(diào)運方案。

表3-4例3-2有關(guān)信息表450200150100日銷量（需求量）250756580乙200100

7090甲

日產(chǎn)量（供應(yīng)量）

C

B

A運距城市煤礦例3-2的數(shù)學(xué)模型初始解的確定一、最小元素法&最小元素法的基本思想是“就近供應(yīng)”；二、西北角法&西北角法則不考慮運距（或運價），每次都選剩余表格的左上角（即西北角）元素作為基變量，其它過程與最小元素法相同；三、沃格爾法（VOGLE）調(diào)銷地運量產(chǎn)地

B1

B2

B3

產(chǎn)量

A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250銷量

100

150

200

450用最小元素法確定例3-2初始調(diào)運方案

150100100100100100100調(diào)銷地運量產(chǎn)地

B1

B2

B3

產(chǎn)量

A190

X1170

X12

100

X13200

A280

X21

65

X2275

X23250銷量

100

150

200

450用西北角法確定例3-2初始調(diào)運方案

100100100

5050200200得到初始調(diào)運方案為：

x11=100，x12=100，x22=50，x23=200元素差額法（Vogel近似法）最小元素法只考慮了局部運輸費用最小。有時為了節(jié)省某一處的運費，而在其它處可能運費很大。元素差額法對最小元素法進(jìn)行了改進(jìn)，考慮到產(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?；谝陨纤悸?，元素差額法求初始基本可行解的步驟是：

第一步：求出每行次小運價與最小運價之差，記為ui，i=1,2,…,m；同時求出每列次小運價與最小運價之差，記為vj，j=1，2，…，n；

第二步：找出所有行、列差額的最大值，即L=max{ui，vi}，差額L對應(yīng)行或列的最小運價處優(yōu)先調(diào)運；

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

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

vj=j列次小運價—j例最小運價表5—14

BjAiB1B2B3B4aiuiA158912153A21724251A3610138202bj201052560vj4174【】5××表5-15

BjAiB1B2B3B4aiuiA158912153×A217242535A3610138202×bj201052560vj41－420×××0【】×表5-16

BjAiB1B2B3B4aiuiA158912154×A2172425－5A3610138202×bj201052560vj－2－420×××0【】10×205基本可行解為總運費Z=10×8+20×1+5×2+20×8=270。檢查當(dāng)前調(diào)運方案是不是最優(yōu)方案的過程就是最優(yōu)性檢驗。檢查的方法：計算非基變量（未填上數(shù)值的格，即空格）的檢驗數(shù)（也稱為空格的檢驗數(shù)），若全部大于等于零，則該方案就是最優(yōu)調(diào)運方案，否則就應(yīng)進(jìn)行調(diào)整。一、閉回路法二、對偶變量法

三、最優(yōu)性檢驗1、閉回路法

什么是閉回路？表中的折線構(gòu)成一條封閉曲線，且所有的邊都是水平或垂直的；（a）（b）（c）（d）以確定了初始調(diào)運方案的作業(yè)表為基礎(chǔ)，以一個非基變量作為起始頂點，尋求閉回路。

該閉回路的特點是：除了起始頂點是非基變量外，其他頂點均為基變量（對應(yīng)著填上數(shù)值的格）?？梢宰C明，如果對閉回路的方向不加區(qū)別，對于每一個非基變量而言，以其為起點的閉回路存在且唯一。1、閉回路法

約定作為起始頂點的非基變量為奇數(shù)點1其它頂點順次排列，那麼，該非基變量xij的檢驗數(shù)：現(xiàn)在，在用最小元素法確定例3-2初始調(diào)運方案的基礎(chǔ)上，計算非基變量X12的檢驗數(shù)：=（閉回路上奇數(shù)次頂點運距或運價之和）-（閉回路上偶數(shù)次頂點運距或運價之和）（3-6）調(diào)銷地運量產(chǎn)地

B1

B2

B3

產(chǎn)量

A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250銷量

100

150

200

450100100100150例3-2初始調(diào)運方案中以X12(X21)為起點的閉回路非基變量X12的檢驗數(shù)：非基變量X21的檢驗數(shù)：

=（c12+c23）-（c13+c22）=70+75-（100+65）=-20，=（c21+c13）-（c11+c23）=80+100-（90+75）=15。經(jīng)濟(jì)含義：在保持產(chǎn)銷平衡的條件下，該非基變量增加一個單位運量而成為基變量時目標(biāo)函數(shù)值的變化量。

以例3-2初始調(diào)運方案為例，設(shè)置位勢變量和，在初始調(diào)運方案表的基礎(chǔ)上增加一行和一列（見下頁表格）。2、位勢法

例3-2初始調(diào)運方案位勢變量對應(yīng)表

調(diào)銷地運量產(chǎn)地

B1

B2

B3產(chǎn)量

A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250銷量

100

150

200

450位勢變量vj

v1

v2

v3100100100150位勢變量

uiu1u22、位勢法

然后構(gòu)造下面的方程組：（3-7）方程組的特點：方程個數(shù)是m+n-1=2+3-1=4個，位勢變量共有m+n=2+3=5個，通常稱ui為第i行的位勢，稱vj為第j列的位勢；初始方案的每一個基變量xij對應(yīng)一個方程——-—所在行和列對應(yīng)的位勢變量之和等于該基變量對應(yīng)的運距（或運價）：ui+vj=cij；

方程組恰有一個自由變量，可以證明方程組中任意一個變量均可取作自由變量。

給定自由變量一個值，解方程組式（3-7），即可求得位勢變量的一組值，根據(jù)式（3-6）結(jié)合方程組（3-7），推出計算非基變量xij檢驗數(shù)的公式σij=cij-（ui+vj）（3-8）在式（3-7）中，令u1=0，則可解得v1=90，v3=100，u2=-25，v2=90，于是σ12=c12-（u1+v2）=70-（0+90）=-20σ21=c21-（u2+v1）=80-（-25+90）=15與前面用閉回路法求得的結(jié)果相同。位勢法計算非基變量xij檢驗數(shù)的公式σij=cij-（ui+vj）（3-7）=（閉回路上奇數(shù)頂點運距或運價之和）-（閉回路上偶數(shù)頂點運距或運價之和）（3-6）閉回路法計算非基變量xij檢驗數(shù)的公式：復(fù)習(xí)比較檢驗數(shù)計算的兩種方法

四、方案調(diào)整

當(dāng)至少有一個非基變量的檢驗數(shù)是負(fù)值時，說明作業(yè)表上當(dāng)前的調(diào)運方案不是最優(yōu)的，應(yīng)進(jìn)行調(diào)整。

若檢驗數(shù)σij小于零，則首先在作業(yè)表上以xij為起始變量作出閉回路，并求出調(diào)整量θ：ijθ=min{該閉回路中偶數(shù)頂點調(diào)運量xij}調(diào)銷地運量產(chǎn)地

B1

B2

B3

產(chǎn)量

A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250銷量

100

150

200

4501001001001501342繼續(xù)上例，因σ12=-20，畫出以x12為起始變量的閉回路

計算調(diào)整量：θ=Min（100，150）=100。按照下面的方法調(diào)整調(diào)運量：

閉回路上，偶數(shù)頂點的調(diào)運量減去θ

，奇數(shù)頂點（包括起始頂點）的調(diào)運量加上θ

；閉回路之外的變量調(diào)運量不變。得到新的調(diào)運方案：

調(diào)銷地運量產(chǎn)地

B1

B2

B3

產(chǎn)量

A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250銷量

100

150

200

450100100200

50重復(fù)上面的步驟，直至求出最優(yōu)調(diào)運方案：調(diào)銷地運量產(chǎn)地

B1

B2

B3

產(chǎn)量

A190

X1170

X12

100

X13200

A280

X2165

X2275

X23250銷量

100

150

200

450150

50200

50

結(jié)果

最優(yōu)調(diào)運方案是：

x11=50，x12=150，x21=50，x23=200

相應(yīng)的最小總運輸量為：

Zmin=90×50+70×150+80×50+75×200=34000（噸公里）退化問題1、初始解退化。即初始基變量的個數(shù)少于m+n1。必須補足基變量的個數(shù)，否則不能正常解出m+n個ci和vj2、迭代過程中出現(xiàn)退化閉合回路中標(biāo)有“”的基變量同時有多個達(dá)到最小變換后，有多個原基變量變?yōu)?，選運費最大者為出變量，其余保留在新的基礎(chǔ)解中退化較嚴(yán)重時，可能會出現(xiàn)多次迭代只有值為0的基變量在轉(zhuǎn)移。此時，一要耐心，二要正確選擇出變量運輸問題3.3運輸問題的推廣一、產(chǎn)銷不平衡的運輸問題供大于求供不應(yīng)求增加虛擬銷地

增加虛擬產(chǎn)地

產(chǎn)銷平衡的運輸問題對應(yīng)的運距（或運價）

？轉(zhuǎn)化運輸問題進(jìn)一步討論產(chǎn)銷不平衡產(chǎn)銷平衡供過于求，即ai>bj，增加一個虛收點Dn+1，bn+1=ai-bj,令wi,n+1=0,i=1,2,…,m供小于求，即ai<bj，增加一個虛發(fā)點Wm+1，am+1=bj-ai,令wm+1,j=0,j=1,2,…,n運輸問題應(yīng)用舉例如產(chǎn)地3的產(chǎn)量變?yōu)?30，又B地區(qū)需的115單位必須滿足，試重新確定最優(yōu)調(diào)撥方案B1B2B3B4B5aiA1101520204050A22040153030100A33035405525130A4(虛）0M00020bj25115603070210得到這樣的平衡表后應(yīng)用舉例1杭州某電視機廠在三個經(jīng)濟(jì)區(qū)建立分廠，生產(chǎn)產(chǎn)品銷往上海，北京，廣州。運價表如下，假定產(chǎn)地2的物資至少運出38個單位，產(chǎn)地3的物資至少運出27個電位，試列出新的運價表上海北京廣州虛擬B4aiA1122020A2145M38A2114502A3233M27A3123303bj30202020得到這樣的平衡表后應(yīng)用舉例2已知某運輸問題一個最優(yōu)調(diào)運方案如下表，求K值范圍指派問題例：有一份中文產(chǎn)品說明書需譯成英、日、德、俄四種語言，現(xiàn)有甲、乙、丙、丁四人都可以勝任，他們譯成不同語言所需時間不同，如下表。求如何分配使所需總時間最少（每人只譯一種）

語言人員EJGR甲215134乙1041415丙9141613丁78119整數(shù)規(guī)劃指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型指派問題的標(biāo)準(zhǔn)形式（以人和事為例）是：有n個人和n件事，已知第i人做第j事的費用為Cij（i，j=1，2，…，n），要求確定人和事之間的一一對應(yīng)的指派方案，使完成這件事的總費用最少。如指派問題（assignmentproblem）例：有一份中文產(chǎn)品說明書需譯成英、日、德、俄四種語言，現(xiàn)有甲、乙、丙、丁四人都可以勝任，他們譯成不同語言所需時間不同，如下表。求如何分配使所需總時間最少（每人只譯一種）語言人員EJGR甲215134乙1041415丙9141613丁7811955建立模型：設(shè)xij=10譯英文：x11+x12+x13+x14=1譯日文：x21+x22+x23+x24=1譯德文：x31+x32+x33+x34=1譯俄文：x41+x42+x43+x44=1甲：x11+x21+x31+x41=1乙：x12+x22+x32+x42=1丙：x13+x23+x33+x43=1?。簒14+x24+x34+x44=1xij=0或1(i=1,2,3,4;j=1,2,3,4)Minz=aijxij (aij---效率)i=1j=144若第i項工作交與第j個人完成若第i項工作不交與第j個人完成一般模型指派問題的標(biāo)準(zhǔn)形式，令1當(dāng)指派第i人完成第j項任務(wù)0當(dāng)不指派第i人完成第j項任務(wù)xij=minz=∑∑cijxij∑xij=1，j=1，2，…，n∑xij=1，i=1，2，…，nxij=1或057匈牙利解法標(biāo)準(zhǔn)的指派問題是一類特殊的0-1整數(shù)規(guī)劃問題，可以用多種相應(yīng)的解法來求解。但是，這些方法都沒有充分利用指派問題的特殊性質(zhì)來有效減少計算量。1955年，庫恩（W.W.Kuhn）利用匈牙利數(shù)學(xué)家康尼格（D.K?nig）的關(guān)于矩陣中獨立零元素的定理，提出了指派問題的一種解法，由此，習(xí)慣上稱之為匈牙利解法。58匈牙利解法的關(guān)鍵是利用了指派問題最優(yōu)解的如下性質(zhì)：若從指派問題的系數(shù)矩陣C=（cij）n×n的某行（或某列）各元素分別減去一個常數(shù)k，得到一個新的系數(shù)矩陣C’=（c’ij）則以C和C’為系數(shù)矩陣的兩個指派問題有相同的最優(yōu)解。匈牙利解法59步驟一：變換系數(shù)矩陣。使其每行及每列至少有一個零元素，同時不出現(xiàn)負(fù)元素。步驟二：進(jìn)行試指派，即確定獨立零元素。步驟三：繼續(xù)變換系數(shù)矩陣，然后返回步驟二。匈牙利解法的一般步驟

60以上例說明步驟2151341041415914161378119013112601011057401422497min（cij）=匈牙利解法的一般步驟

61指派問題（assignmentproblem）匈牙利解法的一般步驟以上例說明步驟013112601011047401420042min01370606905320100=（c’ij）指派問題（assignmentproblem）62以上例說明步驟01370606905320100此時加圈0元素的個數(shù)m=n=4，所以得到最優(yōu)解指派問題（assignmentproblem）63匈牙利解法的一般步驟以上例說明步驟0001010010000010（xij）=指派問題（assignmentproblem）64匈牙利解法的一般步驟例任務(wù)人員ABCDE甲乙丙丁戊1287154791714109612677614610969109指派問題（assignmentproblem）65匈牙利解法的一般步驟12797989666717121491514661041071097676450202230000105729800406365指派問題（assignmentproblem）66匈牙利解法的一般步驟50202230000105729800406365此時加圈0元素的個數(shù)m=4，而n=5，所以解題沒有完成。獨立零元素（加圈零元素）少于n個，表示還不能確定最優(yōu)指派方案。此時需確定能覆蓋所有零元素的最少直線數(shù)目的直線集合。方法如下：指派問題（assignmentproblem）67匈牙利解法的一般步驟對沒有加圈零元素的行打√號；對所有打√號行的所有含零元素的列打√號；再對已打√號的列中含零元素的行打√號；重復(fù)2）和3），直到再也不能找到可以打√號行或列為止；對沒有打√號的行畫一橫線，對打√號的列畫一豎線，這樣就得到能覆蓋所有零元素的最少直線數(shù)目的直線集合。指派問題（assignmentproblem）68匈牙利解法的一般步驟50202230000105729800406365√√√指派問題（assignmentproblem）69匈牙利解法的一般步驟繼續(xù)變換系數(shù)矩陣。其方法是在未被直線覆蓋的元素中找出一個最小元素。然后在打√號行各元素都減去這一最小元素，而在打√號列的各元素都加上這一最小元素，以保證原來的0元素不變。這樣得到新系數(shù)矩陣（其最優(yōu)解和原問題相同）。若得到n個獨立的0元素，則已得最優(yōu)解，否則重復(fù)該步驟繼續(xù)變換系數(shù)矩陣。指派問題（assignmentproblem）70匈牙利解法的一般步驟50202230000105729800406365√√√最小元素=270202430000835011800404143指派問題（assignmentproblem）71匈牙利解法的一般步驟70202430000835011800404143此時加圈0元素的個數(shù)m=5，而n=5，獨立零元素（加圈零元素）等于n個，此時已得到最優(yōu)解，其解矩陣為指派問題（assignmentproblem）72匈牙利解法的一般步驟（xij）=01000001000000100010

10000最優(yōu)指派：甲——B乙——C丙——E丁——D戊——A指派問題（assignmentproblem）73在實際應(yīng)用中，常會遇到各種非標(biāo)準(zhǔn)形式的制派問題。一般的處理方法是先將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后再用匈牙利法求解。最大化指派問題——設(shè)最大化指派問題系數(shù)矩陣C=（cij），其中最大元素為m。令矩陣B=（bij）=（m-cij），則以B為系