运筹学06-运输问题

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第六章 运输问题,6.1 运输问题的数学模型,6.2 初始基可行解的确定,6.3 最优性检验与基可行解的改进,6.4 其他运输问题,9/22/2024,1,6.1 运输问题的数学模型,若一家公司拥有多个工厂，这些工厂位于不同的地点，并且生产同一种产品。这些产品要运输到不同的地点，以满足用户的需求。,供应节点,：这些工厂，它们是运输的起点；,需求节点,：用户所在点，它们是运输的终点或目的地。,同时假定产品不能在供应节点之间运输，也不能在需求节点之间运输。,公司面临的问题是：应如何组织运输，才能在满足供应节点的供应量约束和需求节点的需求量约束的前提下，使得运输成本最低。,这类问题就是,运输问题,。,9/22/2024,2,(1) 运输问题数学模型,x,ij, 供应节点i至需求节点j的运输量；,a,ij, 供应节点i的可供应量，i=1,2, ,m；,b,ij, 需求节点j的需求量，j=1,2,n；,c,ij, 供应节点i至需求节点j的单位运输成本。,9/22/2024,3,根据运输问题中总供应量与总需求量的关系可将运输问题分为两类：,平衡型运输问题,和,不平衡型运输问题,。,平衡型运输问题：,不平衡型运输问题：,对于不平衡型运输问题通常通过设立,虚拟供应节点,或,虚拟需求节点,将其转化为平衡型运输问题求解。,(2) 运输问题的分类,9/22/2024,4,平衡型运输问题的数学模型,模型包含,变量：,mn,个,约束方程：,m+n,个,秩：,r(A)=m+n-1,m 行,n 行,稀疏矩阵,9/22/2024,5,(3) 运输问题的特征,定理：平衡运输问题必有可行解与最优解。,证：对于平衡运输问题,令：,9/22/2024,6,则有,所以 是运输问题的一个可行解。,又由于,所以,且为极小化问题，,故一定存在最优解。,9/22/2024,7,定义：凡能排列成,形式的变量集合，用一条封闭折线将它们连接起来形成的图形称之为一个,闭回路,。,构成回路的诸变量称为闭回路的,顶点,；,连接相邻两个顶点的线段称为闭回路的,边,。,或,每个顶点都是转角点；,每一条边都是水平线段或垂直线段；,每一行或列若有闭回路的顶点，则必有两个,几何,性质,9/22/2024,8,(1),x,12,x,13,x,33,x,32,(2),x,23,x,13,x,14,x,34,x,31,x,21,转角点,转角点,9/22/2024,9,运输问题是一类特殊的线性规划问题,对于平衡型运输问题：,约束方程数为m+n个，但有一个冗余方程，所以独立方程数为m+n-1个，即秩r(A)=m+n-1。,存在最优解,当供应量和需求量均为整数时，存在整数最优解。,基可行解中基变量个数为m+n-1个,基可行解中基变量的重要特征：不含闭回路。,任何一个非基变量与基变量含且仅含一个闭回路。,运输问题的基本性质,9/22/2024,10,(4) 平衡型运输问题的对偶问题,由于r(A)=m+n-1，独立的约束方程个数为m+n-1;,而变量个数为m+n，则其中有一个自由变量,9/22/2024,11,例：,海华设备厂下设三个位于不同地点的分厂A，B，C，该三个分厂生产同一个设备，设每月的生产能力分别为14台、27台和19台。海华设备厂有四个固定的用户，该四个用户下月的设备需求量分别为22台、13台、12台和13台。设各分厂的生产成本相同，从各分厂到各用户的单位设备运输成本如下表所示，而且各分厂本月末的设备库存量为零。,问该厂应如何安排下月的生产与运输，才能在满足四个用户需求的前提下使总运输成本最低。,9/22/2024,12,2,3,2,1,3,4,1,s,B,=27,s,C,=19,d,1,=22,d,2,=13,d,3,=12,d,4,=13,s,A,=14,供应量,供应节点,运输成本,需求量,需求节点,6,7,5,3,8,4,2,7,5,9,10,6,海华设备厂,运输问题网络图,9/22/2024,13,海华设备厂,运输问题的表格表示,9/22/2024,14,供应量约束,需求量约束,海华设备厂,运输问题线性规划模型,9/22/2024,15,不平衡运输问题(1)：供过于求,设置虚拟需求节点,2,3,2,1,3,1,s,B,=27,s,C,=19,d,1,=22,d,2,=13,d,3,=12,s,A,=14,供应量,需求量,6,7,5,8,4,2,5,9,10,供应节点,运输成本,需求节点,4,d,4,=13,0,0,0,9/22/2024,16,不平衡运输问题(2)：供不应求,设置虚拟供应节点,2,2,1,3,4,1,s,B,=27,d,1,=22,d,2,=13,d,3,=12,d,4,=13,s,A,=14,供应量,需求量,6,7,5,3,8,4,2,7,供应节点,运输成本,需求节点,3,s,C,=19,0,0,0,0,9/22/2024,17,6.2 初始基可行解的确定,获得初始基可行解的常用方法：,西北角法,最小元素法,Vogel,法,9/22/2024,18,8,13,13,14,6,6,(1) 西北角法,9/22/2024,19,(2) 最小元素法(,0,),9/22/2024,20,(2) 最小元素法(,1,),9/22/2024,21,(2) 最小元素法(,2,),9/22/2024,22,(2) 最小元素法(,3,),9/22/2024,23,(2) 最小元素法(,4,),9/22/2024,24,(2) 最小元素法(,5,),9/22/2024,25,(2) 最小元素法(,6,),9/22/2024,26,(3),Vogel,法,2,2,1,1,3,3,3,12,3,3,1,1,3,3,13,1,4,4,1,3,13,19,1,2,9/22/2024,27,6.3 最优性检验与基可行解的改进,(1) 最优性检验,充要条件,由于基变量的检验数,ij,= 0,只需确定非基变量的检验数！,确定非基变量检验数的常用方法主要是：,闭回路法,非基变量与基变量构成唯一闭回路,位势法,利用对偶变量,9/22/2024,28,(2) 闭回路法,(0),9/22/2024,29,5,(2) 闭回路法,(1),12,=,c,12,-c,11,+c,21,-c,22,=7-6+8-4=5,9/22/2024,30,-5,5,(2) 闭回路法,(2),13,=,c,13,-c,11,+c,21,-c,23,=5-6+8-2=5,9/22/2024,31,5,5,7,(2) 闭回路法,(3),14,=,c,14,-c,11,+c,21,-c,23,+c,33,-c,34,=3-6+8-2+10-6=7,9/22/2024,32,7,5,5,9,24,=,c,24,-c,23,+c,33,-c,34,=7-2+10-6=9,(2) 闭回路法,(4),9/22/2024,33,7,9,5,5,-11,31,=,c,31,-c,33,+c,23,-c,21,=5-10+2-8=-11,(2) 闭回路法,(5),9/22/2024,34,7,5,5,9,-11,-3,32,=,c,32,-c,33,+c,23,-c,22,=9-10+2-4=-3,(2) 闭回路法,(6),9/22/2024,35,(3) 位势法,对偶规划,由于对偶变量的个数为m+n，而系数矩阵的秩为m+n-1，我们可以通过设定自由变量的值得到所有对偶变量。,9/22/2024,36,(3) 位势法,(0),9/22/2024,37,选择含基变量最多的行或列，令相应的,u,或,v,为零。,(3) 位势法,(1),9/22/2024,38,v,1,=c,21,- u,2,=8-0=8, v,2,=c,22,- u,2,=4-0=4, v,3,=c,23,- u,2,=2-0=2,(3) 位势法,(2),9/22/2024,39,u,1,=c,11,-v,1,=6-8=-2, u,3,=c,33,- v,3,=10-2=8,(3) 位势法,(3),9/22/2024,40,v,4,=c,34,-u,3,=6-8=-2,(3) 位势法,(4),9/22/2024,41,(3) 位势法,(5),5,12,=c,12,-(u,1,+,v,2,) =7-(-2+4)=5,9/22/2024,42,5,(3) 位势法,(6),5,13,=c,13,-(u,1,+,v,3,) =5-(-2+2)=5,9/22/2024,43,(3) 位势法,(7),7,5,5,14,=c,14,-(u,1,+,v,4,) =3-(-2-2)=7,9/22/2024,44,(3) 位势法,(8),7,5,5,24,=c,24,-(u,2,+,v,4,) =7-(0-2)=9,9,9/22/2024,45,(3) 位势法,(9),7,5,5,9,31,=c,31,-(u,3,+,v,1,) =5-(8+8)=-11,-11,9/22/2024,46,(3) 位势法,(10),7,5,5,9,-11,32,=c,32,-(u,3,+,v,2,) =9-(8+4)=-3,-3,9/22/2024,47,(4) 基可行解的改进,选择检验数绝对值最大的非基变量为进基变量,(,存在多个时任选一个,),确定进基变量,确定离基变量,选择包含进基变量的闭回路上距进基变量奇次的变量中运量最小的基变量为离基变量。,运量调整,重复上述步骤直至所有检验数大于零，即获得最优解。,9/22/2024,48,9,7,5,5,-11,-3,确定进基变量,选择检验数绝对值最大的非基变量为进基变量,9/22/2024,49,9,7,5,5,-11,-3,确定闭回路,9/22/2024,50,9,7,5,5,-11,-3,确定离基变量,9/22/2024,51,9,7,5,5,-3,调整运量,6,x,31,=6, x,21,=8-6=2, x,23,=6+6=12,9/22/2024,52,-2,-4,5,5,8,进一步优化(0),11,9/22/2024,53,-2,-4,5,5,8,进一步优化(1),11,x,13,进基，,x,34,离基。,9/22/2024,54,2,4,5,5,8,进一步优化(2),11,所有非基变量的检验数均大于零，即为最优解。,9/22/2024,55,(1) 产销不平衡的运输问题,例：,有三个化肥厂供应四个地区的农用化肥。等量化肥在这些地区使用效果相同。相关数据如下表，试分析总运费最节省的化肥调运方案。,需求地区,化肥厂,B,1,B,2,B,3,B,4,产量（万吨）,A,1,16,13,22,17,50,A,2,14,13,19,15,60,A,3,19,20,23,-,50,最低需求（万吨）,最高需求（万吨）,30,50,70,70,0,30,10,不限,运价：万元/万吨,6.4 其他运输问题,9/22/2024,56,分析：,这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，地区B,4,每年最多能分配到60万吨，这样最高总需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个虚拟的化肥厂D ，其年产量为50万吨。由于各个地区的需要量包含两部分，如地区B,1,，其中30万吨是最低需求，故不能由虚拟的化肥厂D供给，令其相应的运输价格为M（任意大正数），而另一部分20万吨满足或不满足均可，因此可以由虚拟的化肥厂D供给，并令其相应的运输价格为0（没有发生的运输）。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以建立这个问题的产销平衡表,9/22/2024,57,产销平衡表,A,1,A,2,A,3,D,B,1,B,1,B,2,B,3,B,4,B,4,产量,销量,17,17,14,14,13,19,15,15,19,19,20,23,M,M,M,0,M,0,M,0,50,60,50,50,30,20,70,30,10,50,16,16,22,13,50,14,19,0,16,50,M,M,0,M,0,70,17,17,16,13,13,40,13,20,14,19,60,15,M,13,15,20,50,M,9/22/2024,58,产销平衡表,A,1,A,2,A,3,D,B,1,B,1,B,2,B,3,B,4,B,4,U,i,V,j,13,50,14,30,13,20,19,0,15,10,23,30,M,20,0,20,0,30,0,13,0,14,19,15,4,-4+M,4-M,-4+M,2,20-M,3,2,21-M,18-M,19-M,1,19-M,3,M-19,2M-18,2M-17,M-23,2M-19,16,22,17,17,14,15,19,19,20,M,M,M,0,M,16,0,30,20,20,30,9/22/2024,59,产销平衡表,A,1,A,2,A,3,D,B,1,B,1,B,2,B,3,B,4,B,4,U,i,V,j,50,14,30,14,0,13,20,15,10,23,30,M,20,0,20,0,30,0,0,-14+M,-14,14,14,13,37-M,15,14,2,2,-15+M,2,3,-18+,M,1,19-M,19-M,21-M,-1,M,1+M,-23+M,-1+M,10,20,0,50,20,16,13,22,17,17,19,15,19,19,20,M,M,M,0,M,16,9/22/2024,60,产销平衡表,A,1,A,2,A,3,D,B,1,B,1,B,2,B,3,B,4,B,4,U,i,V,j,16,13,50,22,17,17,14,10,14,20,13,20,19,15,10,15,19,20,19,20,23,30,M,M,0,M,0,M,0,M,0,50,16,0,0,5,5-M,14,14,13,18,15,-5+,M,2,2,4,2,22-,M,1,20-M,0,2,-20+M,-19+2M,-19+M,-18+M,-23+M,-20+2M,10,20,0,9/22/2024,61,产销平衡表,A,1,A,2,A,3,D,B,1,B,1,B,2,B,3,B,4,B,4,U,i,V,j,16,13,50,22,17,17,14,10,14,20,13,20,19,15,10,15,0,19,20,19,20,23,30,M,M,M,0,M,0,M,0,50,16,0,0,6,0,14,14,13,17,15,15,2,2,5,2,2,2,-1,1,-21+,M,-21+M,-14+M,-14,-13+M,-17,-15+M,10,10,30,20,40,9/22/2024,62,产销平衡表,A,1,A,2,A,3,D,B,1,B,1,B,2,B,3,B,4,B,4,U,i,V,j,13,50,14,20,13,20,15,10,15,10,19,30,23,20,0,10,0,40,0,0,8,-15,11,14,13,15,15,15,5,2,7,2,2,3,4,-3,-1,M-23,M-23,M+4,1,M+2,M,30,0,30,20,20,16,22,17,17,14,19,19,20,M,M,M,0,M,M,16,9/22/2024,63,产销平衡表,A,1,A,2,A,3,D,B,1,B,1,B,2,B,3,B,4,B,4,U,i,V,j,16,13,50,22,17,17,14,14,13,20,19,15,10,15,30,19,30,19,20,20,23,0,M,M,M,0,M,0,30,M,0,20,16,0,0,8,-15,11,11,13,15,15,15,5,5,7,2,2,3,3,4,-1,M-23,M-23,M+4,4,M+2,M,20,30,30,20,0,9/22/2024,64,产销平衡表,A,1,A,2,A,3,D,B,1,B,1,B,2,B,3,B,4,B,4,U,i,V,j,13,50,13,20,15,10,15,30,19,30,19,20,20,0,0,30,0,20,0,0,7,-15,12,12,13,15,15,15,4,4,7,2,2,2,2,4,1,M-22,M-22,M+3,3,M+2,M,16,22,17,17,14,14,19,23,M,M,M,0,M,M,16,9/22/2024,65,产销平衡表,A,1,A,2,A,3,D,16,13,50,22,17,17,14,14,13,20,19,15,10,15,30,19,30,19,20,20,0,23,M,M,M,0,M,0,30,M,0,20,50,60,50,50,30,20,70,30,10,50,16,B,1,B,1,B,2,B,3,B,4,B,4,产量,销量,9/22/2024,66,(2) 有转运的运输问题,在上面所讨论的问题中，我们都假定物品是由产地直接运送到目的地的，没有经过任何中间转运。然而，在实际当中常常会遇到一种情形：需要先将物品由产地运到某个中间转运站（可能是另外的产地、销地或中间转运仓库），然后再转运到目的地。有时，可能经过转运比直接运到目的地更加经济。因此，在决定运输方案时有必要把转运也考虑进去。这样，将使运输问题更加复杂。,例：,已知A1、A2、A3三个工厂生产同一种产品，用相同的价格供应B1、B2、B3三个销售点，有2个转运站T1、T2。允许产品在各工厂、销售点和转运站间转运，已知各工厂、销售点、转运站之间的单位运价和产销量如下表所示。试求最经济运输方案。,9/22/2024,67,产地,转运站,销地,产量,A1,A2,A3,T1,T2,B1,B2,B3,产地,A1,8,6,2,-,4,10,8,30,A2,8,5,1,3,9,5,9,10,A3,6,5,4,2,2,8,7,20,转运站,T1,2,1,4,8,4,6,3,T2,-,3,2,8,2,3,2,销地,B1,4,9,2,4,2,-,5,B2,10,5,8,6,3,-,4,B3,8,9,7,3,2,5,4,销量,15,35,10,9/22/2024,68,解：,将此转运问题化为等价的运输问题需作如下处理：,将所有的产地、转运站和销地都作为产地与销地，则此问题转化为,8,个产地与,8,个销地运输问题；,对扩大的运输问题建立运价表，没有运输路线的运价设为,M,，自我运输的运价为,0,；,所有转运站的产量等于销量，且为最大可能调运量，即均为,60,；,在扩大的运输问题中，由于原产地与销地均具有转运功能，所以原产地的产量两于原销地的销量均需加上最大可能调运量，即在原数值上加上,60,。,扩大的运输表如下表所示。,9/22/2024,69,产地,转运站,销地,产量,A1,A2,A3,T1,T2,B1,B2,B3,产地,A1,0,8,6,2,M,4,10,8,90,A2,8,0,5,1,3,9,5,9,70,A3,6,5,0,4,2,2,8,7,80,转运站,T1,2,1,4,0,8,4,6,3,60,T2,M,3,2,8,0,2,3,2,60,销地,B1,4,9,2,4,2,0,M,5,60,B2,10,5,8,6,3,M,0,4,60,B3,8,9,7,3,2,5,4,0,60,销量,60,60,60,60,60,75,95,70,9/22/2024,70,产地,转运站,销地,产量,A1,A2,A3,T1,T2,B1,B2,B3,产地,A1,60,15,15,90,A2,60,10,70,A3,60,20,80,转运站,T1,45,5,10,60,T2,40,20,60,销地,B1,60,60,B2,60,60,B3,60,60,销量,60,60,60,60,60,75,95,70,最优调运方案如下表所示,9/22/2024,71,销地,产地,B1,B2,B3,产量,A1,8,2,4,10,2,2,6,A2,1,4,3,4,4,销量,6,2,6,销地,产地,B1,B2,B3,产量,A1,8,2,4,10,8,2,A2,1,4,3,10,6,4,销量,6,8,6,Z=48,Z=42,悖论,9/22/2024,72,第六章作业题,2 、 3 、4、6,9/22/2024,73,(20050810)已知某运输问题的初始调运方案，试求全部最优调运方案。,产地销地,B1,B2,B3,B4,产量,A1,(2),(2),4,2,6,2,1,A2,(4),(2),6,10,8,5,4,A3,(2),(3),5,7,6,6,9,销量,4,3,4,4,9/22/2024,74,销地,产地,S1,S2,S3,S4,产量,P1,6,4,7,8,50,P2,5,6,6,7,60,P3,-,7,6,10,50,最低需求,30,70,0,10,最高需求,50,70,30,50,9/22/2024,75,产粮区,化肥厂,甲,乙,丙,丁,A,5,8,7,3,B,4,9,10,7,C,8,4,2,9,9/22/2024,76,