1SchoolofBusinessAdministrationHunanUniversityLecture5

TransportationProblemLecturer:E-mail:

2LectureOutlineTransportationProblemModel&itsCharacteristicsTableauMethodUnbalancedSupply&DemandTransportationProblemanditsSolution31.ThePresentationoftheProblem

從m個產(chǎn)地A1,

A2,…,Am向n個銷地B1,

B2,…,Bn發(fā)送某種貨物。Ai的發(fā)量為ai，Bj的收量為bj。由Ai

運(yùn)往Bj

單位貨物的運(yùn)費(fèi)為Cij，運(yùn)量為Xij。問如何調(diào)配，才能使運(yùn)費(fèi)最??？產(chǎn)地銷地1.ThePresentationoftheProblem4Thetransportationproblemdealswiththedistributionofgoodsfromseveralpointsofsupply(originsorsources)toanumberofpointsofdemand(destinations).Xij=numberofunitsshippedfromsourceitodestinationjCij=costoneunitfromsourceitodestinationjai=supplyatsourcei

bj=demandatdestinationjTheobjectiveofsuchaproblemistoscheduleshipmentssothattotaltransportationcostsareminimized.Supposetherearemsourcesandndestinations,Let51.TransportationProblemModelExample：ShippingdataforaTransportationProblem單位銷地運(yùn)價產(chǎn)地產(chǎn)量2910291342584257銷量38466SupposeXijisthenumberofunitsshippedfromsourceAi

todestinationBjx11x12x13x14x21x22x23x24A1B1A2A3B2B3B4x31x32x33x34Networkrepresentationofthetransportationproblem.7SupplyDemand8AGeneralLPModelforTransportationProblemParametertableforthetransportationproblem

單位銷運(yùn)價地產(chǎn)地產(chǎn)量銷量AGeneralLPModelforTransportationProblem9x11x12x1nx21x22x2nA1B1A2AmB2Bnxm1xm2xmnNetworkrepresentationofthetransportationproblem.10產(chǎn)銷平衡時——數(shù)學(xué)模型11產(chǎn)大于銷時——數(shù)學(xué)模型12產(chǎn)小于銷時——數(shù)學(xué)模型CharacteristicsofTransportationProblems13TheRequirementsAssumptionEachsourcehasafixedsupplyofunits,wherethisentiresupplymustbedistributedtothedestinations.Eachdestinationhasafixeddemandforunits,wherethisentiredemandmustbereceivedfromthesources.TheCostAssumptionThecostofdistributingunitsfromanyparticularsourcetoanyparticulardestinationisdirectlyproportionaltothenumberofunitsdistributed.Thiscostisjusttheunitcostofdistributiontimesthenumberofunitsdistributed.CharacteristicsofTransportationProblemModel14ConstraintcoefficientsforthetransportationproblemSupplyConstraintsDemandConstraintsCharacteristicsofTransportationProblemModel151.運(yùn)輸問題模型的系數(shù)矩陣每列只有第i行和第m+j行兩個元素為1，其余均為0；2.平衡運(yùn)輸問題必有可行解，也必有最優(yōu)解；

3.運(yùn)輸問題的基本可行解中應(yīng)包括m+n-1個基變量。2.TableauMethod16PrimalProblemDualProblem172.TableauMethod步驟：⑷重復(fù)⑵、⑶，直到找到最優(yōu)解為止。⑴找出初始基本可行解（初始調(diào)運(yùn)方案，一般m+n-1個數(shù)字格），用西北角法、最小元素法或伏格爾法等；⑵求出各非基變量的檢驗(yàn)數(shù)，判別是否達(dá)到最優(yōu)解。如果是停止計(jì)算，否則轉(zhuǎn)入下一步，用位勢法計(jì)算；⑶改進(jìn)當(dāng)前的基本可行解（確定換入、換出變量），用閉合回路法調(diào)整；182.1初始基可行解的確定例一、某運(yùn)輸資料如下表所示單位銷地運(yùn)價產(chǎn)地產(chǎn)量311310719284741059銷量365619⑴西北角法(或左上角法)

Northwestcornerrule優(yōu)先給運(yùn)價表左上角的變量賦值xij=min{ai,bj}，當(dāng)行或列分配完畢后，劃去相應(yīng)的行或列，再在表中余下的左上角賦值，以此類推，直至右下角分配完畢。方法如下：x11=min(7,3)=3=b1,劃掉第一列，

x12=min(6,4)=4=a1-3，劃掉第一行，…3656749342236340002200036總運(yùn)輸費(fèi)用＝(3×3)＋(11×4)＋(9×2)＋(2×2)＋(10×3)＋(5×6)＝135元06560256005600360000449049029009000運(yùn)量銷量20B1B2B3B4產(chǎn)量A17A2

4A39銷量3656311310192741058341633⑵最小元素法(minimalelementmethod)基本思想是就近供應(yīng)，即從運(yùn)價最小min(cij)的地方開始調(diào)運(yùn)xij=min{ai,bj}，然后次小，直到最后供完為止?？傔\(yùn)輸費(fèi)用＝（1×3）＋（4×6）＋（3×4）＋（2×1）＋（10×3）＋（5×3）＝86元××××××21⑶差值法(Vogel'sapproximationmethod)

Step1:求出表中每行每列次小運(yùn)價與最小運(yùn)價之差，分別記為ui(i=1,…,m)和vj(j=1,…,n),并分別填入表的最右列和最下行;Step2:找出所有行、列差值的最大值，即L=max{ui,vj}，差值L對應(yīng)行或列的最小運(yùn)價處按最小元素法優(yōu)先調(diào)運(yùn)；Step3:若解的個數(shù)小于m+n-1,返回Step2，否則停止計(jì)算。22B1B2B3B4SuiA170A2

41A391D3656vj25133113101927410586××3××3×1×25總運(yùn)輸費(fèi)用＝（3×2）＋（1×1）＋（4×6）＋（3×5）＋（8×3）＋（5×3）＝85元23Step1:求出表中每行每列次小運(yùn)價與最小運(yùn)價之差，分別記為ui(i=1,…,m)和vj(j=1,…,n),并分別填入表的最右列和最下行;Step2:找出所有行、列差值的最大值，即L=max{ui,vj}，差值L對應(yīng)行或列的最小運(yùn)價處按最小元素法優(yōu)先調(diào)運(yùn)；Step3:若解的個數(shù)小于m+n-1，對表中未劃去的元素再分別計(jì)算出每行每列次小運(yùn)價與最小運(yùn)價之差，并分別填入表的最右列和最下行，返回Step2，否則停止計(jì)算。

改進(jìn)差值法

242.2最優(yōu)解的判定(檢驗(yàn)數(shù)求法)⑴閉回路法(ClosedPathMethod)閉回路特點(diǎn)：①每個頂點(diǎn)都是轉(zhuǎn)角；②每行或每列有且僅有2個頂點(diǎn)；③每個頂點(diǎn)的連線都是水平的或垂直的。從每一個空格出發(fā)一定可以作唯一的閉回路。從某個空格開始，沿水平或垂直方向前進(jìn)，當(dāng)遇到一個數(shù)字，可以越過繼續(xù)前進(jìn)，也可以轉(zhuǎn)900，再沿垂直或水平方向前進(jìn)，如此下去，最終回到原出發(fā)點(diǎn)。25

σij≥0（因?yàn)槟繕?biāo)函數(shù)要求最小化）表格中有調(diào)運(yùn)量的地方為基變量，空格處為非基變量?；兞康臋z驗(yàn)數(shù)σij＝0，非基變量的檢驗(yàn)數(shù)σij≥0。σij<0表示運(yùn)費(fèi)減少，σij>0表示運(yùn)費(fèi)增加。σ的計(jì)算：

調(diào)整運(yùn)輸量，以空格為起點(diǎn)，順時針方向，奇點(diǎn)增加1個單位運(yùn)量，偶點(diǎn)減少1單位運(yùn)量，計(jì)算閉回路運(yùn)費(fèi)的增量。26B1B2B3B4產(chǎn)量A17A24A39銷量3656313463

（＋1）（＋1）（－1）（－1）①②③③

計(jì)算空格處（A1

B1

）＝

(3×1)＋｛3×(－1)｝＋(2×1)＋｛1×(－1)｝＝1

此數(shù)即為該空格處非基變量的檢驗(yàn)數(shù)σ11。127B1B2B3B4產(chǎn)量A17A24A39銷量365631363124（A1

B2

）=（11×1）+（10×-1）+(5×1）

+(4×-1)=2=σ1228B1B2B3B4產(chǎn)量A17A24A39銷量36563136312-14（A2

B4

）=（8×1）+（2×-1）+(3×1）

+(10×-1)=-1=σ2429B1B2B3B4產(chǎn)量A17A24A39銷量365631363121-14（A2

B2

）=（9×1）+（2×-1）+(3×1）

+(10×-1)+(5×1)+(4×-1)=1=σ2230B1B2B3B4產(chǎn)量A17A24A39銷量365631363121-1124（A3

B3

）=（10×1）+（3×-1）+(10×1）

+(5×-1)=12=σ3331B1B2B3B4產(chǎn)量A17A24A39銷量365631363121-112104（A3

B1

）=（7×1）+（1×-1）+(2×1)+(3×-1)+(10×1)+(5×-1)=10=σ3132B1B2B3B4產(chǎn)量A17A24A39銷量365600000121-112100檢驗(yàn)數(shù)中有負(fù)數(shù)，說明原方案不是最優(yōu)解。33

運(yùn)輸問題的約束條件共有m+n個，其中,m個產(chǎn)地產(chǎn)量的限制；n個銷地銷量的限制。其對偶問題也應(yīng)有m+n個變量，其中前m個計(jì)為ui(i=1,2,…,m),后n個計(jì)為vj

,(j=1,2,…,n)。據(jù)此：σij=cij－(ui+vj),

由單純形法可知，基變量的σij＝

0∴cij－(ui+vj)＝0，因此ui,vj可以求出。⑵位勢法(Stepping-StoneMethod)34minZ=CXAX=bX≥0maxZ=YbYA≤CY無限制σij=cij-CBB-1pijY=(u1,…,um,v1,…,vn)據(jù)對偶理論有Y=CBB-1σij=cij-Ypijσij=cij－(ui+vj)

35接上例：B1B2B3B4A1310u1A212u2A345u3v1v2v3v4成本表B1B2B3B4A1293100A21829－1A3－34－25－529310

u2+v1=1

u2+v3=2

u3+v2=4u1+v4=10

u1+v3=3u3+v4=5

令：u1＝0u1＝0v1＝2u2＝－1v2＝9u3＝－5v3＝3

v4＝10(ui+vj)36

按σij=cij－(ui+vj)

計(jì)算檢驗(yàn)數(shù)，并以σij

0

檢驗(yàn)，或用(ui+vj)

－cij

0檢驗(yàn)。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A3－34-25(ui+vj)B1B2B3B4A11200A2010－1A3100120表中還有負(fù)數(shù)，說明還未得到最優(yōu)解，應(yīng)繼續(xù)調(diào)整。σij372.3基可行解的轉(zhuǎn)換(改進(jìn)方法)

閉回路調(diào)整法（原理同單純形法一樣）（1）以min{σij|σij<0}對應(yīng)的變量xij作為入基變量；（2）以所選的xij為第一個頂點(diǎn)作閉回路，該閉回路除xij外，其余頂點(diǎn)都是基變量，并排序；（3）以順序?yàn)榕紨?shù)的頂點(diǎn)的基變量最小值min{(xij)k|k為偶數(shù)}作為調(diào)整量，在順序?yàn)槠鏀?shù)的頂點(diǎn)加上該調(diào)整量，在順序?yàn)榕紨?shù)的頂點(diǎn)上減去該調(diào)整量，即可得到新的基可行解。示例38B1B2B3B4產(chǎn)量A17A24A39銷量3656313463（＋1）（＋1）（－1）（－1）接上例：39B1B2B3B4產(chǎn)量A1527A2314A3639銷量3656B1B2B3B4產(chǎn)量A1(+1)4(-1)37A23(-1)1(+1)4A3639銷量365640B1B2B3B4A10200A20210A390120經(jīng)檢驗(yàn)所有σij

0得到最優(yōu)解，最小運(yùn)費(fèi)為85元。0v4v3v2v1u354A3u281A2u1103A1B4B3B2B1成本表10393－55－24－2A3－28171A2010393A1B4B3B2B1(ui+vj)σij41表上作業(yè)法計(jì)算中的問題⑴無窮多最優(yōu)解：產(chǎn)銷平衡的運(yùn)輸問題必定存最優(yōu)解。如果非基變量的σij＝0，則該問題有無窮多最優(yōu)解。如上例：（A1,B1）中的檢驗(yàn)數(shù)是0，經(jīng)過調(diào)整，可得到另一個最優(yōu)解。

⑵退化：表格中一般要有(m+n-1)個數(shù)字格。但有時，在分配運(yùn)量時則需要同時劃去一行和一列，這時需要補(bǔ)一個0，以保證有(m+n-1)個數(shù)字格。一般可在劃去的行和列的任意空格處加一個0

即可。42例1(西北角法)：B1B2B3B4A178143A226355A3142782176213552682176

例2(最小元素法)：B1B2B3A11221A23132A32314124B1B2B3A111A222A344124000433.產(chǎn)銷不平衡運(yùn)輸問題及其求解(1)產(chǎn)大于銷數(shù)學(xué)模型

方法是先將原問題變成平衡問題，需假設(shè)一個銷地(Bn+1)(實(shí)際上考慮產(chǎn)地的存量)，44

模型為：(2)銷大于產(chǎn)：同樣假設(shè)一個產(chǎn)地即可，變化同上。單位運(yùn)價表中的單位運(yùn)價為45B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5

A121134070A210359050A378120702030406040B1B2B3B4B5

A170A250A370203040604040303020302020用最小元素法求初始方案例題(產(chǎn)大于銷)：46練習(xí)已知某運(yùn)輸問題的資料如下表所示B1B2B3B4發(fā)量A1265315A2132112A3327413收量10131251、表中的發(fā)量、收量單位為：噸，運(yùn)價單位為：元/噸試求出最優(yōu)運(yùn)輸方案.2、如將A2的發(fā)量改為17，其它資料不變，試求最優(yōu)調(diào)運(yùn)方案。47B1B2B3B4發(fā)量A112315A210212A31313收量1013125B1B2B3B4發(fā)量A1265315A2132112A3327413收量1013125解

(1)

初始基可行解的確定(最小元素法)48B1B2B3B4發(fā)量A112315A210212A313013收量1013125B1B2B3B4A153A211A324(2)最優(yōu)解的判定(位勢法)B1B2B3B4ui

A153u1A211u2A324u3vj

v1v2v3v4成本表退化處理(補(bǔ)0)(ui+vj)49B1B2B3B4ui

A153u1A211u2A324u3vj

v1v2v3v4

u1+v3=5u2+v4=1

u1+v4=3u3+v2=2

u2+v1=1u3+v4=4

令：u1＝0u1＝0v1＝3u2＝－2v2＝1u3＝1v3＝5

v4＝350B1B2B3B4ui

A1530A211－2A3241vj

3153B1B2B3B4ui

A131530A21－131－2A342641vj

3153(ui+vj)51B1B2B3B4A12653A21321A33274B1B2B3B4A13153A21－131A34264cij－B1B2B3B4A1－1500A204－10A3－1010＝表中還有負(fù)數(shù)，說明沒有得到最優(yōu)解，調(diào)整運(yùn)輸方案。σij(ui+vj)52B1B2B3B4A1123A2102A3130B1B2B3B4A1105A2102A3130＋2＋2－2－2新的運(yùn)送方案B1B2B3B4A153A212A324新的成本表B1B2B3B4ui

A141530A21－220－3A352641vj

4153(ui+vj)1

總的運(yùn)費(fèi)105元(3)基可行解的轉(zhuǎn)換53B1B2B3B4A14153A21－220A35264B1B2B3B4A12653A21321A33274－＝B1B2B3B4A1－2500A20501A3－2010表中還有負(fù)數(shù)，說明沒有得到最優(yōu)解，繼續(xù)調(diào)整運(yùn)輸方案。cij(ui+vj)1

(σij)1

54013A3210A2510A1B4B3B2B13512vj

14623A3－302－2－1A203512A1ui

B4B3B2B1(ui+vj)2

42A32A2352A1B4B3B2B1新的成本表013A312A25010A1B4B3B2B1新的運(yùn)送方案總的運(yùn)費(fèi)85元55B1B2B3B4A12653A21321A33274cijB1B2B3B4A12153A2－1－220A33264(ui+vj)2

－＝B1B2B3B4A10500A22501A30010

(σij)2

表中沒有負(fù)數(shù)，說明已經(jīng)得到最優(yōu)解。但有無窮多最優(yōu)解。05613A312A2510A1B4B3B2B1最終的運(yùn)送方案總的運(yùn)費(fèi)85元57B1B2B3B4發(fā)量A131215A27512A313013收量1013125B1B2B3B4發(fā)量A1265315A2132112A3327413收量1013125(1)

初始基可行解的確定(最小元素法)另一情況58B1B2B3B4A125A211A327B1B2B3B4ui

A125u1A211u2A327u3vj

v1v2v3v4成本表

u1+v1=2u2+v4=1

u1+v3=5u3+v2=2

u2+v1=1u3+v3=7

令：u1＝0u1＝0v1＝2u2＝－1v2＝0u3＝2v3＝5

v4＝259B1B2B3B4ui

A120520A21-141-1A342742vj

2052(ui+vj)B1B2B3B4A12653A21321A33274cijB1B2B3B4ui

A10601A204-20A3-1000vj

σij60B1B2B3B4發(fā)量A131215A27512A313013收量1013125B1B2B3B4發(fā)量A110515A27512A313013收量101312561B1B2B3B4B5發(fā)量A110515A2102517A313013收量10131255B1B2B3B4B5發(fā)量A12653015A21321017A33274013收量1013125562B1B2B3B4B5A150A2121A324B1B2B3B4B5ui

A150u1A2121u2A324u3vj

v1v2v3v4v5成本表

u1+v3=5u2+v3=2

u1+v5=0u2+v4=1

u2+v1=1u3+v2=2

u3+v4=4令u1＝0u1＝0v1＝4u2＝-3v2＝2u3＝0v3＝5

v4＝4

v5＝063B1B2B3B4B5ui

A1425400A21-121-3-3A3425400vj

42540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5

A1-240-10A204004A3-10200σij64505B45121310收量1313A317210A215510A1發(fā)量B5B3B2B1B1B2B3B4B5發(fā)量A1100515A212517A313013收量1013125565B1B2B3B4B5A1250A221A324B1B2B3B4B5ui

A1250u1A221u2A324u3vj

v1v2v3v4v5成本表

u1+v1=2u2+v4=1

u1+v3=5u3+v2=2

u1+v5=0u3+v4=4

u2+v3=2令u1＝0u1＝0v1＝2u2＝-3v2＝2u3＝0v3＝5

v4＝4

v5＝066B1B2B3B4B5ui

A1225400A2-1-121-3-3A3225400vj

22540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5

A1040-10A224004A310200σij67B1B2B3B4B5發(fā)量A1100515A212517A313013收量10131255B1B2B3B4B5發(fā)量A1100515A212517A313013收量1013125568B1B2B3B4B5發(fā)量A110515A212517A31313收量10131255C=7569作業(yè)已知資料如下表所示，問如何供電能使總的輸電費(fèi)用為最??？發(fā)電廠發(fā)電量A1700A2200A3100城市需電量B1500B2250B3100B4150電力供需表B1B2B3B4A110523A24312A35634單位輸電費(fèi)用70B1B2B3B4A1A2A3初始方案10010050250400100B1B2B3B4A110523A24312A35634單位輸電費(fèi)用發(fā)電廠發(fā)電量A1700A2200A3100城市需電量B1500B2250B3100B4150電力供需表71B1B2B3B4A11053A212A35B1B2B3B4ui

A1105230A29412-1A350-3-2-5vj

10523B1B2B3B4ui

A10000A2-5-100A30666vj

σij成本表-(ui+vj)

=cij(ui+vj)

A3A2A1B4B3B2B1初始方案1001005025040010072B1B2B3B4A140025050A2100100A3100B1B2B3B4A1300250150A2100100A3100B1B2B3B4A11053A241A35成本表B1B2B3B4ui

A1105730A24-11-3-6A3502-2-5vj

10573(ui+vj)

調(diào)運(yùn)方案73B1B2B3B4ui

A100-50A20405A30616vj

σij-(ui+vj)

=cijB1B2B3B4A1300250150A2100100A3100B1B2B3B4A1200250100150A2200A3100B1B2B3B4A110523A24A35成本表調(diào)運(yùn)方案74B1B2B3B4ui

A1105230A24-1-4-3-6A350-3-2-5vj

10523(ui+vj)

B1B2B3B4ui

A10000A20455A30666vj

σij-(