运筹学运输问题(2)

2020/5/20,1,第六章运输问题,6.1运输问题的数学模型6.2初始基可行解的确定6.3最优性检验与基可行解的改进6.4其他运输问题,2020/5/20,2,6.1运输问题的数学模型,若一家公司拥有多个工厂，这些工厂位于不同的地点，并且生产同一种产品。这些产品要运输到不同的地点，以满足用户的需求。供应节点：这些工厂，它们是运输的起点；需求节点：用户所在点，它们是运输的终点或目的地。同时假定产品不能在供应节点之间运输，也不能在需求节点之间运输。公司面临的问题是：应如何组织运输，才能在满足供应节点的供应量约束和需求节点的需求量约束的前提下，使得运输成本最低。这类问题就是运输问题。,2020/5/20,3,(1)运输问题数学模型,xij供应节点i至需求节点j的运输量；aij供应节点i的可供应量，i=1,2,m；bij需求节点j的需求量，j=1,2,n；cij供应节点i至需求节点j的单位运输成本。,2020/5/20,4,根据运输问题中总供应量与总需求量的关系可将运输问题分为两类：平衡型运输问题和不平衡型运输问题。,平衡型运输问题：,不平衡型运输问题：,对于不平衡型运输问题通常通过设立虚拟供应节点或虚拟需求节点将其转化为平衡型运输问题求解。,(2)运输问题的分类,2020/5/20,5,平衡型运输问题的数学模型,模型包含变量：mn个约束方程：m+n个秩：r(A)=m+n-1,m行,n行,稀疏矩阵,2020/5/20,6,(3)运输问题的特征,定理：平衡运输问题必有可行解与最优解。,证：对于平衡运输问题,令：,2020/5/20,7,则有,所以是运输问题的一个可行解。,又由于,所以,且为极小化问题，故一定存在最优解。,2020/5/20,8,定义：凡能排列成,形式的变量集合，用一条封闭折线将它们连接起来形成的图形称之为一个闭回路。构成回路的诸变量称为闭回路的顶点；连接相邻两个顶点的线段称为闭回路的边。,或,每个顶点都是转角点；每一条边都是水平线段或垂直线段；每一行或列若有闭回路的顶点，则必有两个,几何性质,2020/5/20,9,(1)x12,x13,x33,x32,(2)x23,x13,x14,x34,x31,x21,转角点,转角点,2020/5/20,10,运输问题是一类特殊的线性规划问题对于平衡型运输问题：约束方程数为m+n个，但有一个冗余方程，所以独立方程数为m+n-1个，即秩r(A)=m+n-1。存在最优解当供应量和需求量均为整数时，存在整数最优解。基可行解中基变量个数为m+n-1个基可行解中基变量的重要特征：不含闭回路。任何一个非基变量与基变量含且仅含一个闭回路。,运输问题的基本性质,2020/5/20,11,(4)平衡型运输问题的对偶问题,由于r(A)=m+n-1，独立的约束方程个数为m+n-1;而变量个数为m+n，则其中有一个自由变量,2020/5/20,12,例：海华设备厂下设三个位于不同地点的分厂A，B，C，该三个分厂生产同一个设备，设每月的生产能力分别为14台、27台和19台。海华设备厂有四个固定的用户，该四个用户下月的设备需求量分别为22台、13台、12台和13台。设各分厂的生产成本相同，从各分厂到各用户的单位设备运输成本如下表所示，而且各分厂本月末的设备库存量为零。,问该厂应如何安排下月的生产与运输，才能在满足四个用户需求的前提下使总运输成本最低。,2020/5/20,13,海华设备厂运输问题网络图,2020/5/20,14,海华设备厂运输问题的表格表示,2020/5/20,15,海华设备厂运输问题线性规划模型,2020/5/20,16,不平衡运输问题(1)：供过于求设置虚拟需求节点,2020/5/20,17,不平衡运输问题(2)：供不应求设置虚拟供应节点,2020/5/20,18,6.2初始基可行解的确定,获得初始基可行解的常用方法：西北角法最小元素法Vogel法,2020/5/20,19,8,13,13,14,6,6,(1)西北角法,2020/5/20,20,(2)最小元素法(0),2020/5/20,21,(2)最小元素法(1),2020/5/20,22,(2)最小元素法(2),2020/5/20,23,(2)最小元素法(3),2020/5/20,24,(2)最小元素法(4),2020/5/20,25,(2)最小元素法(5),2020/5/20,26,(2)最小元素法(6),2020/5/20,27,(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,2020/5/20,28,6.3最优性检验与基可行解的改进,(1)最优性检验,充要条件,由于基变量的检验数ij=0,只需确定非基变量的检验数！确定非基变量检验数的常用方法主要是：闭回路法非基变量与基变量构成唯一闭回路位势法利用对偶变量,2020/5/20,29,(2)闭回路法(0),2020/5/20,30,5,(2)闭回路法(1),12=c12-c11+c21-c22=7-6+8-4=5,2020/5/20,31,-5,5,(2)闭回路法(2),13=c13-c11+c21-c23=5-6+8-2=5,2020/5/20,32,5,5,7,(2)闭回路法(3),14=c14-c11+c21-c23+c33-c34=3-6+8-2+10-6=7,2020/5/20,33,7,5,5,9,24=c24-c23+c33-c34=7-2+10-6=9,(2)闭回路法(4),2020/5/20,34,7,9,5,5,-11,31=c31-c33+c23-c21=5-10+2-8=-11,(2)闭回路法(5),2020/5/20,35,7,5,5,9,-11,-3,32=c32-c33+c23-c22=9-10+2-4=-3,(2)闭回路法(6),2020/5/20,36,(3)位势法,对偶规划,由于对偶变量的个数为m+n，而系数矩阵的秩为m+n-1，我们可以通过设定自由变量的值得到所有对偶变量。,2020/5/20,37,(3)位势法(0),2020/5/20,38,选择含基变量最多的行或列，令相应的u或v为零。,(3)位势法(1),2020/5/20,39,v1=c21-u2=8-0=8,v2=c22-u2=4-0=4,v3=c23-u2=2-0=2,(3)位势法(2),2020/5/20,40,u1=c11-v1=6-8=-2,u3=c33-v3=10-2=8,(3)位势法(3),2020/5/20,41,v4=c34-u3=6-8=-2,(3)位势法(4),2020/5/20,42,(3)位势法(5),5,12=c12-(u1+v2)=7-(-2+4)=5,2020/5/20,43,5,(3)位势法(6),5,13=c13-(u1+v3)=5-(-2+2)=5,2020/5/20,44,(3)位势法(7),7,5,5,14=c14-(u1+v4)=3-(-2-2)=7,2020/5/20,45,(3)位势法(8),7,5,5,24=c24-(u2+v4)=7-(0-2)=9,9,2020/5/20,46,(3)位势法(9),7,5,5,9,31=c31-(u3+v1)=5-(8+8)=-11,-11,2020/5/20,47,(3)位势法(10),7,5,5,9,-11,32=c32-(u3+v2)=9-(8+4)=-3,-3,2020/5/20,48,(4)基可行解的改进,选择检验数绝对值最大的非基变量为进基变量(存在多个时任选一个),确定进基变量,确定离基变量,选择包含进基变量的闭回路上距进基变量奇次的变量中运量最小的基变量为离基变量。,运量调整,重复上述步骤直至所有检验数大于零，即获得最优解。,2020/5/20,49,9,7,5,5,-11,-3,确定进基变量,选择检验数绝对值最大的非基变量为进基变量,2020/5/20,50,9,7,5,5,-11,-3,确定闭回路,2020/5/20,51,9,7,5,5,-11,-3,确定离基变量,2020/5/20,52,9,7,5,5,-3,调整运量,6,x31=6,x21=8-6=2,x23=6+6=12,2020/5/20,53,-2,-4,5,5,8,进一步优化(0),11,2020/5/20,54,-2,-4,5,5,8,进一步优化(1),11,x13进基，x34离基。,2020/5/20,55,2,4,5,5,8,进一步优化(2),11,所有非基变量的检验数均大于零，即为最优解。,2020/5/20,56,(1)产销不平衡的运输问题例：有三个化肥厂供应四个地区的农用化肥。等量化肥在这些地区使用效果相同。相关数据如下表，试分析总运费最节省的化肥调运方案。,运价：万元/万吨,6.4其他运输问题,2020/5/20,57,分析：这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，地区B4每年最多能分配到60万吨，这样最高总需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个虚拟的化肥厂D，其年产量为50万吨。由于各个地区的需要量包含两部分，如地区B1，其中30万吨是最低需求，故不能由虚拟的化肥厂D供给，令其相应的运输价格为M（任意大正数），而另一部分20万吨满足或不满足均可，因此可以由虚拟的化肥厂D供给，并令其相应的运输价格为0（没有发生的运输）。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以建立这个问题的产销平衡表,2020/5/20,58,产销平衡表,A1A2A3D,B1B1B2B3B4B4产量,销量,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,2020/5/20,59,产销平衡表,A1A2A3D,B1B1B2B3B4B4Ui,Vj,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,2020/5/20,60,产销平衡表,A1A2A3D,B1B1B2B3B4B4Ui,Vj,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,2020/5/20,61,产销平衡表,A1A2A3D,B1B1B2B3B4B4Ui,Vj,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,2020/5/20,62,产销平衡表,A1A2A3D,B1B1B2B3B4B4Ui,Vj,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,2020/5/20,63,产销平衡表,A1A2A3D,B1B1B2B3B4B4Ui,Vj,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,2020/5/20,64,产销平衡表,A1A2A3D,B1B1B2B3B4B4Ui,Vj,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,2020/5/20,65,产销平衡表,A1A2A3D,B1B1B2B3B4B4Ui,Vj,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,2020/5/20,66,产销平衡表,A1A2A3D,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,B1B1B2B3B4B4产量,销量,2020/5/20,67,(2)有转运的运输问题在上面所讨论的问题中，我们都假定物品是由产地直接运