运筹基础课程 4

1SchoolofBusinessAdministrationHunanUniversityLecture5

TransportationProblemLecturer:E-mail:

2LectureOutlineTransportationProblemModel&itsCharacteristicsTableauMethodUnbalancedSupply&DemandTransportationProblemanditsSolution31.ThePresentationoftheProblem

从m个产地A1,

A2,…,Am向n个销地B1,

B2,…,Bn发送某种货物。Ai的发量为ai，Bj的收量为bj。由Ai

运往Bj

单位货物的运费为Cij，运量为Xij。问如何调配，才能使运费最省？产地销地1.ThePresentationoftheProblem4Thetransportationproblemdealswiththedistributionofgoodsfromseveralpointsofsupply(originsorsources)toanumberofpointsofdemand(destinations).Xij=numberofunitsshippedfromsourceitodestinationjCij=costoneunitfromsourceitodestinationjai=supplyatsourcei

bj=demandatdestinationjTheobjectiveofsuchaproblemistoscheduleshipmentssothattotaltransportationcostsareminimized.Supposetherearemsourcesandndestinations,Let51.TransportationProblemModelExample：ShippingdataforaTransportationProblem单位销地运价产地产量2910291342584257销量38466SupposeXijisthenumberofunitsshippedfromsourceAi

todestinationBjx11x12x13x14x21x22x23x24A1B1A2A3B2B3B4x31x32x33x34Networkrepresentationofthetransportationproblem.7SupplyDemand8AGeneralLPModelforTransportationProblemParametertableforthetransportationproblem

单位销运价地产地产量销量AGeneralLPModelforTransportationProblem9x11x12x1nx21x22x2nA1B1A2AmB2Bnxm1xm2xmnNetworkrepresentationofthetransportationproblem.10产销平衡时——数学模型11产大于销时——数学模型12产小于销时——数学模型CharacteristicsofTransportationProblems13TheRequirementsAssumptionEachsourcehasafixedsupplyofunits,wherethisentiresupplymustbedistributedtothedestinations.Eachdestinationhasafixeddemandforunits,wherethisentiredemandmustbereceivedfromthesources.TheCostAssumptionThecostofdistributingunitsfromanyparticularsourcetoanyparticulardestinationisdirectlyproportionaltothenumberofunitsdistributed.Thiscostisjusttheunitcostofdistributiontimesthenumberofunitsdistributed.CharacteristicsofTransportationProblemModel14ConstraintcoefficientsforthetransportationproblemSupplyConstraintsDemandConstraintsCharacteristicsofTransportationProblemModel151.运输问题模型的系数矩阵每列只有第i行和第m+j行两个元素为1，其余均为0；2.平衡运输问题必有可行解，也必有最优解；

3.运输问题的基本可行解中应包括m+n-1个基变量。2.TableauMethod16PrimalProblemDualProblem172.TableauMethod步骤：⑷重复⑵、⑶，直到找到最优解为止。⑴找出初始基本可行解（初始调运方案，一般m+n-1个数字格），用西北角法、最小元素法或伏格尔法等；⑵求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用位势法计算；⑶改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；182.1初始基可行解的确定例一、某运输资料如下表所示单位销地运价产地产量311310719284741059销量365619⑴西北角法(或左上角法)

Northwestcornerrule优先给运价表左上角的变量赋值xij=min{ai,bj}，当行或列分配完毕后，划去相应的行或列，再在表中余下的左上角赋值，以此类推，直至右下角分配完毕。方法如下：x11=min(7,3)=3=b1,划掉第一列，

x12=min(6,4)=4=a1-3，划掉第一行，…3656749342236340002200036总运输费用＝(3×3)＋(11×4)＋(9×2)＋(2×2)＋(10×3)＋(5×6)＝135元06560256005600360000449049029009000运量销量20B1B2B3B4产量A17A2

4A39销量3656311310192741058341633⑵最小元素法(minimalelementmethod)基本思想是就近供应，即从运价最小min(cij)的地方开始调运xij=min{ai,bj}，然后次小，直到最后供完为止。总运输费用＝（1×3）＋（4×6）＋（3×4）＋（2×1）＋（10×3）＋（5×3）＝86元××××××21⑶差值法(Vogel'sapproximationmethod)

Step1:求出表中每行每列次小运价与最小运价之差，分别记为ui(i=1,…,m)和vj(j=1,…,n),并分别填入表的最右列和最下行;Step2:找出所有行、列差值的最大值，即L=max{ui,vj}，差值L对应行或列的最小运价处按最小元素法优先调运；Step3:若解的个数小于m+n-1,返回Step2，否则停止计算。22B1B2B3B4SuiA170A2

41A391D3656vj25133113101927410586××3××3×1×25总运输费用＝（3×2）＋（1×1）＋（4×6）＋（3×5）＋（8×3）＋（5×3）＝85元23Step1:求出表中每行每列次小运价与最小运价之差，分别记为ui(i=1,…,m)和vj(j=1,…,n),并分别填入表的最右列和最下行;Step2:找出所有行、列差值的最大值，即L=max{ui,vj}，差值L对应行或列的最小运价处按最小元素法优先调运；Step3:若解的个数小于m+n-1，对表中未划去的元素再分别计算出每行每列次小运价与最小运价之差，并分别填入表的最右列和最下行，返回Step2，否则停止计算。

改进差值法

242.2最优解的判定(检验数求法)⑴闭回路法(ClosedPathMethod)闭回路特点：①每个顶点都是转角；②每行或每列有且仅有2个顶点；③每个顶点的连线都是水平的或垂直的。从每一个空格出发一定可以作唯一的闭回路。从某个空格开始，沿水平或垂直方向前进，当遇到一个数字，可以越过继续前进，也可以转900，再沿垂直或水平方向前进，如此下去，最终回到原出发点。25

σij≥0（因为目标函数要求最小化）表格中有调运量的地方为基变量，空格处为非基变量。基变量的检验数σij＝0，非基变量的检验数σij≥0。σij<0表示运费减少，σij>0表示运费增加。σ的计算：

调整运输量，以空格为起点，顺时针方向，奇点增加1个单位运量，偶点减少1单位运量，计算闭回路运费的增量。26B1B2B3B4产量A17A24A39销量3656313463

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

计算空格处（A1

B1

）＝

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

此数即为该空格处非基变量的检验数σ11。127B1B2B3B4产量A17A24A39销量365631363124（A1

B2

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

+(4×-1)=2=σ1228B1B2B3B4产量A17A24A39销量36563136312-14（A2

B4

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

+(10×-1)=-1=σ2429B1B2B3B4产量A17A24A39销量365631363121-14（A2

B2

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

+(10×-1)+(5×1)+(4×-1)=1=σ2230B1B2B3B4产量A17A24A39销量365631363121-1124（A3

B3

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

+(5×-1)=12=σ3331B1B2B3B4产量A17A24A39销量365631363121-112104（A3

B1

）=（7×1）+（1×-1）+(2×1)+(3×-1)+(10×1)+(5×-1)=10=σ3132B1B2B3B4产量A17A24A39销量365600000121-112100检验数中有负数，说明原方案不是最优解。33

运输问题的约束条件共有m+n个，其中,m个产地产量的限制；n个销地销量的限制。其对偶问题也应有m+n个变量，其中前m个计为ui(i=1,2,…,m),后n个计为vj

,(j=1,2,…,n)。据此：σ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)据对偶理论有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)

计算检验数，并以σij

0

检验，或用(ui+vj)

－cij

0检验。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A3－34-25(ui+vj)B1B2B3B4A11200A2010－1A3100120表中还有负数，说明还未得到最优解，应继续调整。σij372.3基可行解的转换(改进方法)

闭回路调整法（原理同单纯形法一样）（1）以min{σij|σij<0}对应的变量xij作为入基变量；（2）以所选的xij为第一个顶点作闭回路，该闭回路除xij外，其余顶点都是基变量，并排序；（3）以顺序为偶数的顶点的基变量最小值min{(xij)k|k为偶数}作为调整量，在顺序为奇数的顶点加上该调整量，在顺序为偶数的顶点上减去该调整量，即可得到新的基可行解。示例38B1B2B3B4产量A17A24A39销量3656313463（＋1）（＋1）（－1）（－1）接上例：39B1B2B3B4产量A1527A2314A3639销量3656B1B2B3B4产量A1(+1)4(-1)37A23(-1)1(+1)4A3639销量365640B1B2B3B4A10200A20210A390120经检验所有σij

0得到最优解，最小运费为85元。0v4v3v2v1u354A3u281A2u1103A1B4B3B2B1成本表10393－55－24－2A3－28171A2010393A1B4B3B2B1(ui+vj)σij41表上作业法计算中的问题⑴无穷多最优解：产销平衡的运输问题必定存最优解。如果非基变量的σij＝0，则该问题有无穷多最优解。如上例：（A1,B1）中的检验数是0，经过调整，可得到另一个最优解。

⑵退化：表格中一般要有(m+n-1)个数字格。但有时，在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格。一般可在划去的行和列的任意空格处加一个0

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

例2(最小元素法)：B1B2B3A11221A23132A32314124B1B2B3A111A222A344124000433.产销不平衡运输问题及其求解(1)产大于销数学模型

方法是先将原问题变成平衡问题，需假设一个销地(Bn+1)(实际上考虑产地的存量)，44

模型为：(2)销大于产：同样假设一个产地即可，变化同上。单位运价表中的单位运价为45B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5

A121134070A210359050A378120702030406040B1B2B3B4B5

A170A250A370203040604040303020302020用最小元素法求初始方案例题(产大于销)：46练习已知某运输问题的资料如下表所示B1B2B3B4发量A1265315A2132112A3327413收量10131251、表中的发量、收量单位为：吨，运价单位为：元/吨试求出最优运输方案.2、如将A2的发量改为17，其它资料不变，试求最优调运方案。47B1B2B3B4发量A112315A210212A31313收量1013125B1B2B3B4发量A1265315A2132112A3327413收量1013125解

(1)

初始基可行解的确定(最小元素法)48B1B2B3B4发量A112315A210212A313013收量1013125B1B2B3B4A153A211A324(2)最优解的判定(位势法)B1B2B3B4ui

A153u1A211u2A324u3vj

v1v2v3v4成本表退化处理(补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＝表中还有负数，说明没有得到最优解，调整运输方案。σij(ui+vj)52B1B2B3B4A1123A2102A3130B1B2B3B4A1105A2102A3130＋2＋2－2－2新的运送方案B1B2B3B4A153A212A324新的成本表B1B2B3B4ui

A141530A21－220－3A352641vj

4153(ui+vj)1

总的运费105元(3)基可行解的转换53B1B2B3B4A14153A21－220A35264B1B2B3B4A12653A21321A33274－＝B1B2B3B4A1－2500A20501A3－2010表中还有负数，说明没有得到最优解，继续调整运输方案。cij(ui+vj)1

(σij)1

54013A3210A2510A1B4B3B2B13512vj

14623A3－302－2－1A203512A1ui

B4B3B2B1(ui+vj)2

42A32A2352A1B4B3B2B1新的成本表013A312A25010A1B4B3B2B1新的运送方案总的运费85元55B1B2B3B4A12653A21321A33274cijB1B2B3B4A12153A2－1－220A33264(ui+vj)2

－＝B1B2B3B4A10500A22501A30010

(σij)2

表中没有负数，说明已经得到最优解。但有无穷多最优解。05613A312A2510A1B4B3B2B1最终的运送方案总的运费85元57B1B2B3B4发量A131215A27512A313013收量1013125B1B2B3B4发量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发量A131215A27512A313013收量1013125B1B2B3B4发量A110515A27512A313013收量101312561B1B2B3B4B5发量A110515A2102517A313013收量10131255B1B2B3B4B5发量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发量B5B3B2B1B1B2B3B4B5发量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发量A1100515A212517A313013收量10131255B1B2B3B4B5发量A1100515A212517A313013收量1013125568B1B2B3B4B5发量A110515A212517A31313收量10131255C=7569作业已知资料如下表所示，问如何供电能使总的输电费用为最小？发电厂发电量A1700A2200A3100城市需电量B1500B2250B3100B4150电力供需表B1B2B3B4A110523A24312A35634单位输电费用70B1B2B3B4A1A2A3初始方案10010050250400100B1B2B3B4A110523A24312A35634单位输电费用发电厂发电量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)

调运方案73B1B2B3B4ui

A100-50A20405A30616vj

σij-(ui+vj)

=cijB1B2B3B4A1300250150A2100100A3100B1B2B3B4A1200250100150A2200A3100B1B2B3B4A110523A24A35成本表调运方案74B1B2B3B4ui

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

10523(ui+vj)

B1B2B3B4ui

A10000A20455A30666vj

σij-(