运筹学06运输题目精华课件.pptx

1、2023-5-1016.1 运输问题的数学模型n若一家公司拥有多个工厂，这些工厂位于不同的地点，若一家公司拥有多个工厂，这些工厂位于不同的地点，并且生产同一种产品。这些产品要运输到不同的地点，并且生产同一种产品。这些产品要运输到不同的地点，以满足用户的需求。以满足用户的需求。n供应节点供应节点：这些工厂，它们是运输的起点；：这些工厂，它们是运输的起点；n需求节点需求节点：用户所在点，它们是运输的终点或目的地。：用户所在点，它们是运输的终点或目的地。n同时假定产品不能在供应节点之间运输，也不能在需求同时假定产品不能在供应节点之间运输，也不能在需求节点之间运输。节点之间运输。n公司面临的问题是：应

2、如何组织运输，才能在满足供应公司面临的问题是：应如何组织运输，才能在满足供应节点的供应量约束和需求节点的需求量约束的前提下，节点的供应量约束和需求节点的需求量约束的前提下，使得运输成本最低。使得运输成本最低。n这类问题就是这类问题就是运输问题运输问题。2023-5-102(1)(1)运输问题数学模型运输问题数学模型xij 供应节点i至需求节点j的运输量；aij 供应节点i的可供应量，i=1,2,m；bij 需求节点j的需求量，j=1,2,n；cij 供应节点i至需求节点j的单位运输成本。ji,0 xn,2,1jbxm,2,1iax.t.sxcZMinijm1ijijin1jijm1in1jij

3、ij和和对所有的对所有的 2023-5-103n根据运输问题中总供应量与总需求量的关系可将运输根据运输问题中总供应量与总需求量的关系可将运输问题分为两类：问题分为两类：n平衡型运输问题平衡型运输问题和和不平衡型运输问题不平衡型运输问题。平衡型运输问题：n1jjm1iiba不平衡型运输问题：n1jjm1iiba对于不平衡型运输问题通常通过设立虚拟供应节点或虚拟需求节点将其转化为平衡型运输问题求解。(2)运输问题的分类2023-5-104ji,0 xn,2,1jbxm,2,1iax.t.sxcZMinijm1ijijin1jijm1in1jijij和和对所有的对所有的 平衡型运输问题的数学模型 1

4、11111111111111111A模型包含变量：mn个约束方程：m+n个秩：r(A)=m+n-1 m 行n 行稀疏矩阵2023-5-105(3)运输问题的特征定理：平衡运输问题必有可行解与最优解。证：对于平衡运输问题令：n1jjm1iibaQji,0 xn,2,1jbxm,2,1iax.t.sxcZMinijm1ijijin1jijm1in1jijij和和对所有的对所有的 n,2,1jm,2,1iQbaxjiij 2023-5-106则有 n,2,1j;m,2,1i0 xij n,2,1jbaQbQbaxm1ijijm1ijim1iij m,2,1iabQaQbaxn1jijin1jjin1

5、jij 所以 是运输问题的一个可行解。n,2,1jm,2,1iQbaxjiij 又由于 n,2,1j;m,2,1i0cij 所以0 xcZm1in1jijij 且为极小化问题，故一定存在最优解。2023-5-107定义：凡能排列成形式的变量集合，用一条封闭折线将它们连接起来形成的图形称之为一个闭回路。构成回路的诸变量称为闭回路的顶点；连接相邻两个顶点的线段称为闭回路的边。1sss232111jijijijijix,x,x,x,x或s1ss321211jijijijijix,x,x,x,x互不相同互不相同其中：其中：s321s321j,j,j,ji,i,i,i每个顶点都是转角点；每一条边都是水平

6、线段或垂直线段；每一行或列若有闭回路的顶点，则必有两个几何性质2023-5-108b1b2C11C21C31C12C22C32C13C23C33C14C24C34ABCa1a2a3b3b41234x11x21x31x12x22x32x13x23x33x14x24x24(1)x12,x13,x33,x32(2)x23,x13,x14,x34,x31,x21转角点转角点2023-5-109n运输问题是一类特殊的线性规划问题运输问题是一类特殊的线性规划问题n对于平衡型运输问题：对于平衡型运输问题：q约束方程数为约束方程数为m+n个，但有一个冗余方程，所以独个，但有一个冗余方程，所以独立方程数为立方程

7、数为m+n-1个，即秩个，即秩r(A)=m+n-1。q存在最优解存在最优解q当供应量和需求量均为整数时，存在整数最优解。当供应量和需求量均为整数时，存在整数最优解。q基可行解中基变量个数为基可行解中基变量个数为m+n-1个个q基可行解中基变量的重要特征：不含闭回路。基可行解中基变量的重要特征：不含闭回路。q任何一个非基变量与基变量含且仅含一个闭回路。任何一个非基变量与基变量含且仅含一个闭回路。运输问题的基本性质2023-5-1010(4)平衡型运输问题的对偶问题ji,xn,jbxm,iax.t.sxcZMinijmijijinjijminjijij和和对所有的对所有的021211111n,jm

8、iv,ucvu.t.svbuaWMaxjiijjinjjjmiii212111，无符号限制无符号限制由于r(A)=m+n-1，独立的约束方程个数为m+n-1;而变量个数为m+n，则其中有一个自由变量2023-5-1011用户1用户1用户2用户2用户3用户3用户4用户4分厂A分厂A675314分厂B分厂B842727分厂C分厂C5910619下月设备下月设备需求量需求量(吨)(吨)22131213分厂名称分厂名称运输成本(元/台)运输成本(元/台)月生产能月生产能力(吨)力(吨)例：海华设备厂下设三个位于不同地点的分厂A，B，C，该三个分厂生产同一个设备，设每月的生产能力分别为14台、27台和1

9、9台。海华设备厂有四个固定的用户，该四个用户下月的设备需求量分别为22台、13台、12台和13台。设各分厂的生产成本相同，从各分厂到各用户的单位设备运输成本如下表所示，而且各分厂本月末的设备库存量为零。问该厂应如何安排下月的生产与运输，才能在满足四个用户需求的前提下使总运输成本最低。2023-5-10122321341sB=27sC=19d1=22d2=13d3=12d4=13sA=14供应量供应量供应节点供应节点运输成本运输成本需求量需求量需求节点需求节点6753842759106海华设备厂运输问题网络图2023-5-1013海华设备厂运输问题的表格表示22136857495210376AB

10、C14271912131234x11x21x31x12x22x32x13x23x33x14x24x342023-5-1014供应量约束需求量约束海华设备厂运输问题线性规划模型 1,2,3,4j1,2,3i0 x13xxx12xxx13xxx22xxx19xxxx27xxxx14xxxxst6x10 x9x5x7x2x4x8x3x5x7x6xzMinij3424143323133222123121113433323124232221141312113433323124232221141312112023-5-1015不平衡运输问题(1)：供过于求设置虚拟需求节点232131sB=27sC=19d

11、1=22d2=13d3=12sA=14供应量供应量需求量需求量6758425910供应节点供应节点运输成本运输成本需求节点需求节点4d4=130002023-5-1016不平衡运输问题(2)：供不应求设置虚拟供应节点221341sB=27d1=22d2=13d3=12d4=13sA=14供应量供应量需求量需求量67538427供应节点供应节点运输成本运输成本需求节点需求节点3sC=1900002023-5-10176.2 初始基可行解的确定获得初始基可行解的常用方法：获得初始基可行解的常用方法：n西北角法西北角法n最小元素法最小元素法nVogel法法2023-5-1018813131466(1

12、)西北角法2023-5-1019 1 2 3 4 6 7 5 3 A 14 14 8 4 2 7 B 27 27 5 9 10 6 C 19 19 22 13 12 13 22 13 12 13 (2)最小元素法(0)2023-5-1020 1 2 3 4 6 7 5 3 A 14 14 8 4 2 7 B 12 27 15 5 9 10 6 C 19 19 22 13 12 13 22 13 0 13 (2)最小元素法(1)2023-5-1021(2)最小元素法(2)1 2 3 4 6 7 5 3 A 13 14 1 8 4 2 7 B 12 27 15 5 9 10 6 C 19 19 2

13、2 13 12 13 22 13 0 0 2023-5-1022(2)最小元素法(3)1 2 3 4 6 7 5 3 A 13 14 1 8 4 2 7 B 13 12 27 2 5 9 10 6 C 19 19 22 13 12 13 22 0 0 0 2023-5-1023(2)最小元素法(4)1 2 3 4 6 7 5 3 A 13 14 1 8 4 2 7 B 13 12 27 2 5 9 10 6 C 19 19 0 22 13 12 13 3 0 0 0 2023-5-1024(2)最小元素法(5)2023-5-1025(2)最小元素法(6)1 2 3 4 6 7 5 3 A 1

14、13 14 0 8 4 2 7 B 2 13 12 27 0 5 9 10 6 C 19 19 0 22 13 12 13 0 0 0 0 2023-5-1026(3)Vogel 法22113331233113313144131319122023-5-10276.3 最优性检验与基可行解的改进(1)最优性检验n,jm,iij21210 充要条件由于基变量的检验数ij=0,只需确定非基变量的检验数！确定非基变量检验数的常用方法主要是：闭回路法非基变量与基变量构成唯一闭回路位势法利用对偶变量2023-5-1028(2)闭回路法(0)22136857495210376ABC1427191213123

15、41481313662023-5-10295(2)闭回路法(1)12=c12-c11+c21-c22=7-6+8-4=522136857495210376ABC142719121312341481313662023-5-1030-55(2)闭回路法(2)13=c13-c11+c21-c23=5-6+8-2=522136857495210376ABC142719121312341481313662023-5-1031557(2)闭回路法(3)14=c14-c11+c21-c23+c33-c34=3-6+8-2+10-6=722136857495210376ABC14271912131234148

16、1313662023-5-1032755924=c24-c23+c33-c34=7-2+10-6=922136857495210376ABC14271912131234148131366(2)闭回路法(4)2023-5-10337955-1131=c31-c33+c23-c21=5-10+2-8=-11(2)闭回路法(5)22136857495210376ABC142719121312341481313662023-5-10347559-11-332=c32-c33+c23-c22=9-10+2-4=-322136857495210376ABC14271912131234148131366(2

17、)闭回路法(6)2023-5-1035(3)位势法n,jmiv,ucvu.t.svbuaWMaxjiijjinjjjmiii212111，无符号限制无符号限制对偶规划jiijnmijjijjBijijvucvvvuuucYPcPBcc011021211 由于对偶变量的个数为m+n，而系数矩阵的秩为m+n-1，我们可以通过设定自由变量的值得到所有对偶变量。2023-5-1036(3)位势法(0)v1v26857495210376ABCu1u2u3v3v412341481313662023-5-1037选择含基变量最多的行或列，令相应的u或v为零。v1v26857495210376ABCu1u2=

18、0u3v3v41234148131366(3)位势法(1)2023-5-1038v1=c21-u2=8-0=8,v2=c22-u2=4-0=4,v3=c23-u2=2-0=2(3)位势法(2)2023-5-1039u1=c11-v1=6-8=-2,u3=c33-v3=10-2=8(3)位势法(3)v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v412341481313662023-5-1040v4=c34-u3=6-8=-2(3)位势法(4)v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-21234148131366

19、2023-5-1041(3)位势法(5)v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-21234148131366512=c12-(u1+v2)=7-(-2+4)=52023-5-10425(3)位势法(6)v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-21234148131366513=c13-(u1+v3)=5-(-2+2)=52023-5-1043(3)位势法(7)75v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-21234148131366514=c14-

20、(u1+v4)=3-(-2-2)=72023-5-1044(3)位势法(8)75v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-21234148131366524=c24-(u2+v4)=7-(0-2)=992023-5-1045(3)位势法(9)75v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=2v4=-212341481313665931=c31-(u3+v1)=5-(8+8)=-11-112023-5-1046(3)位势法(10)75v1=8v2=46857495210376ABCu1=-2u2=0u3=8v3=

21、2v4=-2123414813136659-1132=c32-(u3+v2)=9-(8+4)=-3-32023-5-1047(4)基可行解的改进选择检验数绝对值最大的非基变量为进基变量(存在多个时任选一个)确定进基变量确定离基变量选择包含进基变量的闭回路上距进基变量奇次的变量中运量最小的基变量为离基变量。运量调整 奇奇次次的的基基变变量量闭闭回回路路上上距距进进基基变变量量为为:xxminxttl 奇次的基变量奇次的基变量闭回路上距进基变量为闭回路上距进基变量为偶次的基变量偶次的基变量闭回路上距进基变量为闭回路上距进基变量为：离基变量：离基变量：进基变量；：进基变量；lktlktktljljx

22、xxxxxxxx重复上述步骤直至所有检验数大于零，即获得最优解。2023-5-104822136857495210376ABC142719121312341481313669755-11-3确定进基变量选择检验数绝对值最大的非基变量为进基变量2023-5-104922136857495210376ABC142719121312341481313669755-11-3确定闭回路2023-5-105022136857495210376ABC142719121312341481313669755-11-366,8min,min3321xxxl确定离基变量2023-5-1051221368574952

23、10376ABC1427191213123414213131209755-3调整运量6x31=6,x21=8-6=2,x23=6+6=122023-5-105222136857495210376ABC142719121312341421313126-2-4558进一步优化(0)112023-5-105322136857495210376ABC142719121312341421313126-2-4558进一步优化(1)11x13 进基，x34离基。2023-5-105422136857495210376ABC14271912131234121313121924558进一步优化(2)11所有非基

24、变量的检验数均大于零，即为最优解。2023-5-1055(1)(1)产销不平衡的运输问题产销不平衡的运输问题例：例：有三个化肥厂供应四个地区的农用化肥。等量化肥在有三个化肥厂供应四个地区的农用化肥。等量化肥在这些地区使用效果相同。相关数据如下表，试分析总运费这些地区使用效果相同。相关数据如下表，试分析总运费最节省的化肥调运方案。最节省的化肥调运方案。需求地区需求地区化肥厂化肥厂A1A2A3最低需求（万吨）最低需求（万吨）最高需求（万吨）最高需求（万吨）B11614193050B21313207070B3221923030B41715-10不限不限产量（万吨）产量（万吨）506050运价：万元/

25、万吨6.4 6.4 其他运输问题其他运输问题2023-5-1056分析：分析：这是一个产销不平衡的运输问题，总产量为这是一个产销不平衡的运输问题，总产量为160万吨，万吨，四个地区的最低需求为四个地区的最低需求为110万吨，最高需求为无限。根据现万吨，最高需求为无限。根据现有产量，地区有产量，地区B4每年最多能分配到每年最多能分配到60万吨，这样最高总需万吨，这样最高总需求为求为210万吨，大于产量。为了求得平衡，在产销平衡表中万吨，大于产量。为了求得平衡，在产销平衡表中增加一个虚拟的化肥厂增加一个虚拟的化肥厂D，其年产量为，其年产量为50万吨。由于各个万吨。由于各个地区的需要量包含两部分，如

26、地区地区的需要量包含两部分，如地区B1，其中，其中30万吨是最低万吨是最低需求，故不能由虚拟的化肥厂需求，故不能由虚拟的化肥厂D供给，令其相应的运输价供给，令其相应的运输价格为格为M（任意大正数），而另一部分（任意大正数），而另一部分20万吨满足或不满足万吨满足或不满足均可，因此可以由虚拟的化肥厂均可，因此可以由虚拟的化肥厂D供给，并令其相应的运供给，并令其相应的运输价格为输价格为0（没有发生的运输）。对凡是需求分两种情况的（没有发生的运输）。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以建立这个问地区，实际上可按照两个地区看待。这样可以建立这个问题的产销平衡表题的产销平衡表2

27、023-5-1057产销平衡表产销平衡表A1A2A3DB1 B1 B2 B3 B4 B4 产量销量171714141319151519192023MMM0M0M0506050503020703010501616221350141901650MM0M070171716131340132014196015M13152050M2023-5-1058产销平衡表产销平衡表A1A2A3DB1 B1 B2 B3 B4 B4 Ui Vj13501430132019015102330M2002003001301419154-4+M4-M-4+M220-M3221-M18-M19-M119-M3M-192M-18

28、2M-17 M-232M-19162217171415191920MMM0M160302020302023-5-1059产销平衡表产销平衡表 A1A2A3DB1 B1 B2 B3 B4 B4 Ui Vj501430140132015102330M2002003000-14+M-1414141337-M151422-15+M 23-18+M119-M19-M21-M-1M1+M-23+M-1+M10200502016132217171915191920MMM0M162023-5-1060产销平衡表产销平衡表A1A2A3DB1 B1 B2 B3 B4 B4 Ui Vj161350221717141

29、01420132019151015192019202330MM0M0M0M050160055-M1414131815-5+M224222-M120-M02-20+M-19+2M-19+M-18+M-23+M-20+2M102002023-5-1061产销平衡表产销平衡表A1A2A3DB1 B1 B2 B3 B4 B4 Ui Vj161350221717141014201320191510150192019202330MMM0M0M050160060141413171515225222-11-21+M-21+M-14+M-14-13+M-17-15+M10103020402023-5-1062产

30、销平衡表产销平衡表A1A2A3DB1 B1 B2 B3 B4 B4 Ui Vj1350142013201510151019302320010040008-151114131515155272234-3-1M-23M-23M+41M+2M3003020201622171714191920MMM0MM162023-5-1063产销平衡表产销平衡表A1A2A3DB1 B1 B2 B3 B4 B4 Ui Vj1613502217171414132019151015301930192020230MMM0M030M02016008-1511111315151555722334-1M-23M-23M+44M

31、+2M2030302002023-5-1064产销平衡表产销平衡表A1A2A3DB1 B1 B2 B3 B4 B4 Ui Vj135013201510153019301920200030020007-15121213151515447222241M-22M-22M+33M+2M1622171714141923MMM0MM162023-5-1065产销平衡表产销平衡表A1A2A3D1613502217171414132019151015301930192020023MMM0M030M0205060505030207030105016B1 B1 B2 B3 B4 B4 产量 销量2023-5-10

32、66(2)有转运的运输问题有转运的运输问题 在上面所讨论的问题中，我们都假定物品是由产地直在上面所讨论的问题中，我们都假定物品是由产地直接运送到目的地的，没有经过任何中间转运。然而，在实接运送到目的地的，没有经过任何中间转运。然而，在实际当中常常会遇到一种情形：需要先将物品由产地运到某际当中常常会遇到一种情形：需要先将物品由产地运到某个中间转运站（可能是另外的产地、销地或中间转运仓个中间转运站（可能是另外的产地、销地或中间转运仓库），然后再转运到目的地。有时，可能经过转运比直接库），然后再转运到目的地。有时，可能经过转运比直接运到目的地更加经济。因此，在决定运输方案时有必要把运到目的地更加经济

33、。因此，在决定运输方案时有必要把转运也考虑进去。这样，将使运输问题更加复杂。转运也考虑进去。这样，将使运输问题更加复杂。例：例：已知已知A1、A2、A3三个工厂生产同一种产品，用相同三个工厂生产同一种产品，用相同的价格供应的价格供应B1、B2、B3三个销售点，有三个销售点，有2个转运站个转运站T1、T2。允许产品在各工厂、销售点和转运站间转运，已知各工厂、允许产品在各工厂、销售点和转运站间转运，已知各工厂、销售点、转运站之间的单位运价和产销量如下表所示。试销售点、转运站之间的单位运价和产销量如下表所示。试求最经济运输方案。求最经济运输方案。2023-5-1067产地产地转运站转运站销地销地产产

34、量量A1A2A3T1T2B1B2B3产产地地A1862-410830A2851395910A3654228720转转运运站站T12148463T2-328232销销地地B149242-5B2105863-4B38973254销量销量1535102023-5-1068解：解：将此转运问题化为等价的运输问题需作如下处理：将此转运问题化为等价的运输问题需作如下处理：1.1.将所有的产地、转运站和销地都作为产地与销地，则将所有的产地、转运站和销地都作为产地与销地，则此问题转化为此问题转化为8 8个产地与个产地与8 8个销地运输问题；个销地运输问题；2.2.对扩大的运输问题建立运价表，没有运输路线的运价

35、对扩大的运输问题建立运价表，没有运输路线的运价设为设为M M，自我运输的运价为，自我运输的运价为0 0；3.3.所有转运站的产量等于销量，且为最大可能调运量，所有转运站的产量等于销量，且为最大可能调运量，即均为即均为6060；4.4.在扩大的运输问题中，由于原产地与销地均具有转运在扩大的运输问题中，由于原产地与销地均具有转运功能，所以原产地的产量两于原销地的销量均需加上功能，所以原产地的产量两于原销地的销量均需加上最大可能调运量，即在原数值上加上最大可能调运量，即在原数值上加上6060。n扩大的运输表如下表所示。扩大的运输表如下表所示。2023-5-1069产地产地转运站转运站销地销地产产量量

36、A1A2A3T1T2B1B2B3产产地地A10862M410890A28051395970A36504228780转转运运站站T12140846360T2M328023260销销地地B1492420M560B2105863M0460B38973254060销量销量60606060607595702023-5-1070产地产地转运站转运站销地销地产产量量A1A2A3T1T2B1B2B3产产地地A160151590A2601070A3602080转转运运站站T14551060T2402060销销地地B16060B26060B36060销量销量6060606060759570最优调运方案如下表所示2

37、023-5-1071销地销地产地产地A1A2销量销量B181624B22422B34366产产量量104销地销地产地产地A1A2销量销量B18166B22488B343624产产量量1010Z=48Z=42悖论2023-5-1072第六章作业题2、3、4、62023-5-1073(20050810)已知某运输问题的初始调运方案，试求全部最优调运方案。产地产地销地销地 B1B2B3B4产量产量A1(2)(2)42621A2(4)(2)610854A3(2)(3)57669销量销量43442023-5-1074路线。路线。之间不存在运输之间不存在运输与与”表示”表示中“中“试求最优调运方案。表试求

38、最优调运方案。表成本如下表，成本如下表，基地到销售基地的运输基地到销售基地的运输四个销售基地，有生产四个销售基地，有生产三个生产基地，有三个生产基地，有某公司有某公司有S4P3S4,S3,S2,S1P3,P2,P120020610销地销地产地产地P1P2P3最低需求最低需求最高需求最高需求S165-3050S24677070S3766030S487101050产量产量5060502023-5-1075吨吨表中单位：元表中单位：元运价如下表所示运价如下表所示到各产粮区的每吨化肥到各产粮区的每吨化肥万吨。已知从各化肥厂万吨。已知从各化肥厂万吨和万吨和吨、吨、万万万吨、万吨、其化肥需求量分别为其化肥需求量分别为记为甲、乙、丙、丁，记为甲、乙、丙、丁，化肥化肥要该种要该种万吨。有四个产粮区需万吨。有四个产粮区需万吨和万吨和万吨、万吨、年产量分别为年产量分别为，其，其、记为记为某地区有三个化肥厂，某地区有三个化肥厂，华工华工/3366,387CBA-20040425产粮区产粮区化肥厂化肥厂ABC甲甲548乙乙894丙丙7102丁丁379。为最少的化肥调拨方案为最少的化肥调拨方案试制定一个使总的运费试制定一个使总的运费