運(yùn)輸問題模型和表上作業(yè)法步驟完整版

TransportationProblem

運(yùn)輸問題

運(yùn)輸問題的表示 網(wǎng)絡(luò)圖、線性規(guī)劃模型、運(yùn)輸表

初始基礎(chǔ)可行解 西北角法、最小元素法

非基變量的檢驗(yàn)數(shù) 閉回路法、對偶變量法

確定進(jìn)基變量，調(diào)整運(yùn)量，確定離基 變量運(yùn)輸問題人們在從事生產(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)用最小。這樣的問題稱為運(yùn)輸問題。2321341運(yùn)輸問題網(wǎng)絡(luò)圖s2=27s3=19d1=22d2=13d3=12d4=13s1=14供應(yīng)量供應(yīng)地運(yùn)價(jià)需求量需求地6753842759106運(yùn)輸問題線性規(guī)劃模型供應(yīng)地約束需求地約束現(xiàn)有A1，A2，A3三個(gè)產(chǎn)糧區(qū)，可供應(yīng)糧食分別為10，8，5（萬噸），現(xiàn)將糧食運(yùn)往B1，B2，B3，B4四個(gè)地區(qū)，其需要量分別為5，7，8，3（萬噸）。產(chǎn)糧地到需求地的運(yùn)價(jià)（元/噸）如表5-1所示，問如何安排一個(gè)運(yùn)輸計(jì)劃，使總的運(yùn)輸費(fèi)用最少。地區(qū)產(chǎn)糧區(qū)B1B2B3B4產(chǎn)量A1326310A253828A341295需要量578323產(chǎn)銷平衡表與單位運(yùn)價(jià)表（元/噸）運(yùn)輸模型ModelofTransportationProblems設(shè)xij(i=1,2,3；j=1,2,3,4)為i個(gè)產(chǎn)糧地運(yùn)往第j個(gè)需求地的運(yùn)量，這樣得到下列運(yùn)輸問題的數(shù)學(xué)模型：運(yùn)量應(yīng)大于或等于零（非負(fù)要求），即

運(yùn)輸模型ModelofTransportationProblems運(yù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)量，表1產(chǎn)銷平衡表與單位運(yùn)價(jià)表

銷地產(chǎn)地

B1

B2

Bn產(chǎn)量

A1

c11

c12

c1n

a1

A2

c21

c22

c2n

a2

Am

cm1

cm2

cmn

am銷量

b1

b2

bn假設(shè)xij

表示從Ai

到Bj

的運(yùn)量,則所求的數(shù)學(xué)模型為:

對于產(chǎn)銷不平衡的情況，我們將另行處理。運(yùn)輸模型特征1.運(yùn)輸問題存在可行解，也一定存在最優(yōu)解

2.當(dāng)供應(yīng)量和需求量都是整數(shù)時(shí)，則一定存在整數(shù)最優(yōu)解3.有m+n個(gè)約束，mn個(gè)變量4.有m+n－1個(gè)基變量在運(yùn)輸問題的數(shù)學(xué)模型里，包含m·n

變量,m+n

個(gè)約束條件。如果用單純形法求解，先得在各約束條件上加入一個(gè)人工變量(以便求出初始基可行解)。因此，即使是m

=3，n=4這樣的簡單問題,變量數(shù)就有19個(gè)之多，計(jì)算起來非常復(fù)雜。因此，我們有必要針對運(yùn)輸問題的某些特點(diǎn)，來尋求更為簡單方便的求解方法。表上作業(yè)法1.表上作業(yè)法的基本概念與重要結(jié)論

針對運(yùn)輸問題的數(shù)學(xué)模型結(jié)構(gòu)的特殊性，它的約束方程組的系數(shù)矩陣具有如下形式(具體見下一張幻燈片)，在該矩陣中，每列只有兩個(gè)元素為1，其余都是0。根據(jù)這個(gè)特點(diǎn)，在單純形法的基礎(chǔ)上，創(chuàng)造出一種專門用來求解運(yùn)輸問題的方法，這種方法我們稱為表上作業(yè)法。運(yùn)輸問題也是一個(gè)線性規(guī)劃問題，當(dāng)用單純形法進(jìn)行求解時(shí)，我們首先應(yīng)當(dāng)知道它的基變量的個(gè)數(shù)；其次，要知道這樣一組基變量應(yīng)當(dāng)是由哪些變量來組成。由運(yùn)輸問題系數(shù)矩陣的形式并結(jié)合第一章單純形算法的討論可以知道:運(yùn)輸問題的每一組基變量應(yīng)由m+n-1個(gè)變量組成。(即基變量的個(gè)數(shù)=產(chǎn)地個(gè)數(shù)+銷售地個(gè)數(shù)–1)進(jìn)一步我們想知道,怎樣的m+n-1個(gè)變量會(huì)構(gòu)成一組基變量？

表2—2

銷地產(chǎn)地B1B2B3B4A1x11x12A2x21x24A3x32x34x11、x12、x32、x34、x24、x21

構(gòu)成一個(gè)閉回路.這里有：i1=1，i2=3，i3=2；j1=1，j2=2，j3=4.若把閉回路的頂點(diǎn)在表中畫出,并且把相鄰兩個(gè)變量用一條直線相連（今后就稱這些直線為閉回路的邊）。而表2—3，即頂點(diǎn)為{x12、x13、x23、x22}和表2—4，即頂點(diǎn)為{x11、

x12、x22、x24、x34、x31}也分別構(gòu)成兩個(gè)閉回路。表2—3

銷地產(chǎn)地B1B2B3B4A1x12x12A2x12x12A3表2—4銷地產(chǎn)地B1B2B3B4A1x11x12A2x22x24A3x31x34從上面的幾個(gè)例子中不難看出，如果把一個(gè)閉回路的所有頂點(diǎn)都在表中畫出，并且把相鄰的頂點(diǎn)都用一條直線連接起來，就可以得到一條封閉的折線，折線的每一條邊或者是水平的，或者是垂直的。另外，在表中的每一行或每一列中，至多只有兩個(gè)閉回路的頂點(diǎn)。定理：m+n-1個(gè)變量

構(gòu)成基變量的充分和必要條件是它不包含有任何閉回路。以上的結(jié)果給出了運(yùn)輸問題的基的一個(gè)特征，這個(gè)結(jié)論是非常重要的，因?yàn)槔盟鼇砼袛鄊+n-1個(gè)變量是否構(gòu)成基變量比直接判斷這些變量所對應(yīng)的系數(shù)列向量組是否線性無關(guān)要簡單和直觀。另外，在以后還將看到利用基的這個(gè)特征可以導(dǎo)出求運(yùn)輸問題的第一個(gè)基可行解的一種簡便的方法。2.表上作業(yè)法表上作業(yè)法是單純形法在求解運(yùn)輸問題時(shí)的一種簡化運(yùn)輸問題表上作業(yè)法步驟1.初始調(diào)運(yùn)方案（1）西北角法（2）最小元素法（3）Vogel法（伏格爾法）2.計(jì)算空格處（即非基變量）的檢驗(yàn)數(shù)（1）閉回路法（2）位勢法（對偶變量法）3.用閉回路法調(diào)整優(yōu)化方案方法，其實(shí)質(zhì)是單純形算法。只是具體計(jì)算和術(shù)語有所不同，可歸納為：（1）找出初始基可行解，即在(m

n)產(chǎn)銷平衡表上給出m+n-1個(gè)有數(shù)字的格，這些有數(shù)字的格不能構(gòu)成閉回路，且行和等于產(chǎn)量，列和等于銷售量；（2）求各非基變量的檢驗(yàn)數(shù)，即在表上求空格的檢驗(yàn)數(shù)，判別是否達(dá)到最優(yōu)解。如果達(dá)到最優(yōu)解，則停止計(jì)算，否則轉(zhuǎn)入下一步；（3）確定換入變量和換出變量，找出新的基可行解，在表上用閉回路法進(jìn)行調(diào)整。（4）重復(fù)（2）、（3）步，直到求得最優(yōu)解為止。以下我們就具體給出求解運(yùn)輸問題表上作業(yè)法的計(jì)算步驟。第一步

確定初始基可行解確定初始基可行解即首先給出初始的調(diào)運(yùn)方案，共有3種方法：西北角法，最小元素法和伏格爾法

最小元素法的基本思想就是就近供應(yīng)。即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定產(chǎn)銷關(guān)系,依次類推,直到給出初始方案為止。舉例如下：某公司經(jīng)銷甲產(chǎn)品，它下設(shè)三個(gè)加工廠，每日的產(chǎn)量分別為：A1—7噸、A2—4噸、A3—9噸。該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn).各銷售點(diǎn)每日銷售量為：B1—3噸、B2—6噸、B3—5噸、B4—6噸。已知從各工廠到各銷售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)如表2—5所示。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿足各銷售點(diǎn)的需要量的前提下,使總的運(yùn)費(fèi)為最小。解：先畫出這個(gè)問題的產(chǎn)銷平衡表。板書演示補(bǔ)0的問題運(yùn)輸問題的表格表示初始基礎(chǔ)可行解—西北角法813131466初始基礎(chǔ)可行解—最小元素法（1）133322133最小元素法（2）最小元素法（3）最小元素法（4）最小元素法（5）最小元素法（6）5非基變量xij的檢驗(yàn)數(shù)zij-cij—閉回路法(1)z12-c12=(c11-c21+c22)-c12=6-8+4-7=-55閉回路法(2)z13-c13=(c11-c21+c23)-c13=6-8+2-5=-555閉回路法(3)z14-c14=(c11-c21+c21-c23+c33-c14)-c13=(6-8+2-10+6)-3=-7755閉回路法(4)z24-c24=(c23-c33+c34)-c24=(2-10+6)-7=-99575閉回路法(5)z31-c31=(c21-c23+c33)-c31=(8-2+10)-5=+11-115795閉回路法(6)z32-c32=(c22-c23+c33)-c32=(4-2+10)-9=+3-3579-11非基變量xij的檢驗(yàn)數(shù)zij-cij—對偶變量法(位勢法)v4=0檢驗(yàn)數(shù)=Cij-(u1,u2,u3,v1,v2,v3,v4)(0…1…0…1….0)=Cij-(ui+vj)對偶變量法(位勢法)u3+v4=c34 u3=6對偶變量法(位勢法)u3+v3=c33 v3=4對偶變量法(位勢法)u2+v3=c23 u2=-2對偶變量法(位勢法)u2+v2=c22 v2=6對偶變量法(位勢法)u2+v1=c21 v1=10對偶變量法(位勢法)u1+v1=c11 u1=-4對偶變量法(位勢法)z12-c12=u1+v2-c12=(-4)+6-7=-55對偶變量法(位勢法)z13-c13=u1+v3-c13=(-4)+4-5=-555對偶變量法(位勢法)z14-c14=u1+v4-c14=(-4)+0-3=-7755對偶變量法(位勢法)z24-c24=u2+v4-c24=(-2)+0-7=-99557對偶變量法(位勢法)z31-c31=u3+v1-c31=6+10-5=11-115579對偶變量法(位勢法)z32-c32=u3+v2-c32=6+6-