线性规划的运输问题(PPT 32)作业讲解

,3.2用表上作业法求解运输问题,作业讲解,1求解初始调运方案,（最小元素法）,5,0,2,1,0,0,1,0,3,0,0,初始运费,3*3+4*1+4*2+2*531(元),0,3.3运输问题的进一步讨论,作业讲解,1求解初始调运方案,（西北角法）,1,2,2,1,2,2,1,0,0,5,初始运费,9*1+3*2+9*1+4*2+2*542(元),0,3.3运输问题的进一步讨论,供大于求的运输问题,1求解初始调运方案,（沃格尔法）,0,4,初始运费,3*3+4*1+4*2+2*531(元),hi,vj,3,2,4,1,3,3,1,1,0,5,0,0,0,2,1,1,0,0,0,1运输问题的类型；,运输问题,课堂内容,一知识点回顾,二新知识点,1产销不平衡运输问题的类型；,2产销不平衡运输问题的数学模型；,3产销不平衡运输问题最优解的计算；,(1)编制初始调运方案,最小元素法、,(2)解的最优性检验,(3)解的改进,闭回路法、,确定换入的非基变量；,确定换出的基变量；,GOTO2,对偶变量法（位势法）,西北角法、,沃格尔法,2产销平衡运输问题的表上作业法;,4运输问题的应用；,3.3运输问题的进一步讨论,运输表,产销不平衡问题,一产销不平衡问题的类型,3.3运输问题的进一步讨论,一、产销不平衡问题的类型,产销不平衡问题,1产量大于销量,目标函数：,st.,3.3运输问题的进一步讨论,2销量大于产量,目标函数：,st.,一、产销不平衡问题的类型,产销不平衡问题,产销不平衡问题,3.3运输问题的进一步讨论,1产销不平衡转化为产销平衡的模型求解；,2方法：增加一个虚拟的产地或销地，从而变成标准型产销平衡问题。,3运输问题产销平衡模型，实质上就是一个求解运输问题的标准型。,二、解题思路,3.3运输问题的进一步讨论,1产量大于销量,增加一个假想的销地Bn+1，其销量为bn+1；,从Ai运到Bn+1的物品数量xi,n+1；,（3）ci,n+1=,0；,因为Bn+1实际上不存在，所以xi,n+1实际上就是就地存储在产地Ai的物品数量。,因为就地存贮的物品无需运输，所以上式结果为,三不平衡模型转化为平衡模型,（1）,（2）,产销不平衡问题,3.3运输问题的进一步讨论,st.,产量大于销量的：,n+1,n+1,n+1,三不平衡模型转化为平衡模型,产销不平衡问题,3.3运输问题的进一步讨论,2销量大于产量,增加一个假想的产地Am+1，其产量为am+1；,从Am+1运到Bj的物品数量xm+1,j；,（3）ci,n+1=,0；,因为Am+1实际上不存在，所以xm+1,j实际上是各销地Bj所需物品的欠缺额。,因为xm+1,j实际上并没有被运输，所以上式结果为,xm+1,j,（1）,（2）,三不平衡模型转化为平衡模型,产销不平衡问题,3.3运输问题的进一步讨论,st.,销量大于产量的：,三不平衡模型转化为平衡模型,产销不平衡问题,m+1,m+1,m+1,m+1,3.3运输问题的进一步讨论,供大于求的运输问题,3.3运输问题的进一步讨论,引入虚拟销地B4，（或理解为仓库），就地“销售”，运费为零,0,0,0,0,80,180,供大于求的运输问题,B4,3.3运输问题的进一步讨论,1求解初始调运方案,（运用最小元素法）,供大于求的运输问题,20,30,20,10,30,60,10,10,30,30,50,10,50,解的改进,3.3运输问题的进一步讨论,0,-3,0,6,-1,0,3,4,-3,-2,-3,-1,-1,-1,-2,-3,-2,供大于求的运输问题,ui,vj,2解的最优性检验,（运用位势法）,3所有非基变量的检验数都小于零，所以该解已经是最优解。,3.3运输问题的进一步讨论,弹性需求问题,设有三煤矿供应四地区，资料如下：,3.3运输问题的进一步讨论,对问题进行分析：,虚拟产量的运输费用为零,但它对于基本需求来讲,运费为无穷大。,本题产量160万吨，最低需求110万吨，最高需求无限。实质上比较现实的最高需求210万吨;(?),1,产量大于最小需求；小于最大需求。而标准型是：产量=销量；,2,处理办法：设想一个虚拟煤矿D，生产50万吨,但这个产量只能供应可有可无的最高需求部分,于是各地的需求也应分为两个部分：基本需求、机动需求；,3,4,弹性需求问题,D,甲2,丁2,1,1,M,M,M,0,0,0,30,20,50,10,30,70,50,19,14,16,25,12,17,设想一个虚拟煤矿D,生产50万吨,这个产量只能供应可有可无的最高需求部分,于是各地的需求分为基本需求和机动需求；,160,110,210,60,3.3运输问题的进一步讨论,求初始调运方案,1,（使用最小元素法）,10,50,50,0,50,20,30,20,20,20,0,30,30,0,0,0,弹性需求问题,3.3运输问题的进一步讨论,解的最优性检验,2,（使用位势法）,0,13,M-13,M-1,6+M,13-M,13-M,13-M,13-M,13-M,-3-M,-3-M,-9-M,-4-M,-4-M,-2,-2,M-1,-7,M-1,-4,-6,-6,-M,-M,有大于零的检验数,所以原初始调运方案不是最优方案,3,解的改进,30,20,20,GOTO2,弹性需求问题,3.3运输问题的进一步讨论,0,13,-12,0,7,12,12,12,12,12,-4,-4,-10,-5,-5,-2,-2,-7,-4,-6,-6,-M,-M,1-M,0,因为所有非基变量的检验数都已经小于等于零，所以该方案就是最优调运方案。,弹性需求问题,4,进行解的最优性检验；,5,X44,X42,3.3运输问题的进一步讨论,三转运与平衡的关联,假定m个产地A1,A2,Am和n个销地B1,B2,Bn都可以作为中间转运站使用，从而发送物品的地点和接收物品的地点都有m+n个。,A1,A2,B1,B2,B3,例,令：,ai,第i个产地的产量（净供应量）；,bj,第j个销地的销量（净需要量）；,xij,由第i个发送地运到第j个接收地的物品数量；,cij,由第i个发送地到第j个接收地的单位运价；,ci,第i个地点转运单位物品的费用；,Q,有转运的运输问题,3.3运输问题的进一步讨论,产销表,转运的运输问题,转运的运输问题,3.3运输问题的进一步讨论,运价表,3.3运输问题的进一步讨论,st.,m+n,m+n,转运模型：,m+n,m+n,Q,+,Q,+,Q,转运的运输问题,转运例题,3.3运输问题的进一步讨论,左图显示出了一个运输系统,它包括二个产地(和)二个销地(和)及一个中间转运站(),各产地的产量和各销地的销量用相应节点处箭线旁的数字表示，节点连线上的数字为该地的转运单价,试确定最优运输方案。,运价表,-4,-1,-3,-5,-3,3,5,2,M,5,2,3,5,4,2,5,M,2,M,6,5,M,5,4,6,10,+,50,40,+,50,50,50,50,50,50,50,30,+,50,30,+,50,表上作业法求解步骤,3.3运输问题的进一步讨论,50,20,50,10,50,30,0,20,40,50,10,20,50,20,1,2,5,4,3,0,6,8,7,20,9,一、初始调运方案,初始调运方案：,x12,x22,x24,x25,x33,x34,x14,，,x44,x55,=,相应运价为：,c12,c22,c24,c25,c33,c34,c14,，,c44,c55,50,50,20,20,50,0,10,，,50,50,=,-4,-1,M,4,-3,5,2,，,-3,-5,二、解的最优性检验和改进,3.3运输问题的进一步讨论,0,M-2,3,-5,-11+M,-4,1-M,6-M,-6,2,-4-2M,2-M,-4-M,-14,-15-M,-11,-4,M-11,6-2M,-22+M,-16,M-10,-9,4-M,-5-M,-15+M,20,30,20,新总运费=,+,=300（元）,2*10,+,4*20,+,2*20,5*20,3*20,+,表上作业法求解步骤,3.3运输问题的进一步讨论,0,8,3,-5,-1,-4,-9,-4,-6,2,-14-M,-8,-14,-14,-5-M,-11,-4,-1,-4-M,-12,-16,-9,-6,-15,-5,10-M,空格检验数都小余零，所以是最优解.,=300,最小运费,三、解的最优性检验,表上作业法求解步骤,x14,x23,x25,x34,=,10,20,20,20,20,x34,知识点回顾,产销不平衡运输问