《运输课程讲座ch》PPT课件.ppt

1,设数学模型为,一、运输问题的变体：求极大值问题,2,第一种方法：将极大化问题转化为极小化问题。设极大化问题的运价表为C=（Cij）mn，用一个较大的数M（MmaxCij）去减每一个Cij得到矩阵C/=（Cij）mn ，其中C/ij=MCij0,将C/作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为,例如，下列矩阵C是Ai（I=1，2，3）到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大.,8 14 9,3,用最小元素法求初始方案得,11=8,12=4,21=2,23=2全部非负,得到最优运输方案X,最大利润Z=89+1010+68+54=240,第二种方法:所有非基变量的检验数ij0时最优.求初始运输方案可采用最大元素法.,如上例,用最大元素得到 的初始运输方案:,8 14 9,求检验数:11=8,12=4,21=2,23=2,全部非正,得到最优解运输方案,结果与第一种方法相同.,4,用最小元素法求初始方案得,11=8,12=4,21=2,23=2全部非负,得到最优运输方案X,最大利润Z=89+1010+68+54=240,第二种方法:所有非基变量的检验数ij0时最优.求初始运输方案可采用最大元素法.,如上例,用最大元素得到 的初始运输方案:,8 14 9,求检验数:11=8,12=4,21=2,23=2,全部非正,得到最优解运输方案,结果与第一种方法相同.,5,用最小元素法求初始方案得,11=8,12=4,21=2,23=2全部非负,得到最优运输方案X,最大利润Z=89+1010+68+54=240,第二种方法:所有非基变量的检验数ij0时最优.求初始运输方案可采用最大元素法.,如上例,用最大元素得到 的初始运输方案:,8 14 9,求检验数:11=8,12=4,21=2,23=2,全部非正,得到最优解运输方案,结果与第一种方法相同.,6,二、产销不平衡的运输问题及其求解方法,产大于销,销大于产,7,然后再用产销平衡的运输问题的解法进行解之。,2.解法思路： 将不平衡运输问题转化为平衡运输问题。即当 时，考虑在平衡表中增加一虚拟列，表示增加一个销货点 (j=n+1)如仓库，其销货量为 ，且各运价 Cin+1=0；当 时，考虑在平衡表中增加一虚拟 行，表示增加一个新产地，且各运价Cm+1j=0。其产量为,8,不平衡运输问题 : 当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。,(一) 当产大于销时, 即,数学模型为,9,由于总产量大于总销量，必有部分产地的产量不能全部 运送完，必须就地库存，即每个产地设一个仓库，库存量 为xi，n+1（i=1，2，m），总的库存量为,10,bn+1作为一个虚设的销地Bn+1的销量。各产地Ai到Bn+1的运价为零，即Ci，n+1=0,（i=1，m）。则平衡问题的数学模型为：,具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可,11,（二）当销大于产时,即,数学模型为,12,由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为,xm+1,j 是Am+1运到Bj的运量，也是Bj不能满足需要的数量。Am+1到Bj的运价为零,即Cm+1,j=0(j=1,2, ,n),13,销大于产平衡问题的数学模型为 ：,具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。,14,因为有：,看一个例题：求下列表中极小化运输问题的最优解。,15,所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180160=20，Ci5=0，i=1，2，3，4。表的右边增添一列,这样我们可得新的运价表：,16,下表为计算结果。可看出：产地A4还有20个单位没有运出。,17,案例1 某企业和用户签订了设备交货合同，已知该企业各季度的生产能力、每台设备的生产成本和每季度末的交货量如下表，若生产出的设备当季度不交货，每台设备每季度需支付保管维护费0.1万元,试问在遵守合同的条件下,企业如何安排生产计划,才能使年消耗费用最低?,转化为平衡运输问题的运输表,18,已知某运输问题的资料如下表所示,1、表中的发量、收量单位为：吨，运价单位为：元/吨 试求出最优运输方案.,例2：,2、如将A2的发量改为17，其它资料不变，试求最优调 运方案。,19,20,解：1、用最小元素法求初始方案,运费为108元/吨,2、用位势法判断：,成本表,21,u1+v3=5 u2+v4 =1 u1+v4 =3 u3+v2=2 u2+v1=1 u3+v4 =4 令： u10,u10 v13 u22 v2 1 u3 1 v3 5 v4 3,22,(ui+vj),23,cij,表中还有负数，说明没有得到最优解，调整运输方案。,ij,(ui+vj),24,2,2,2,2,新的运送方案,新的成本表,(ui+vj)1,总的运费 105元/吨,25,表中还有负数，说明没有得到最优解，继续调整运输方案。,cij,(ui+vj)1,(ij)1,26,27,cij,(ui+vj)2,(ij)2,表中没有负数，说明已经得到最优解。但有无穷多最优解。,0,28,29,30,成本表,u1+v1=2 u2+v4 =1 u1+v3 =5 u3+v2 =2 u2+v1=1 u3+v3 =7 令： u10,u10 v12 u21 v2 0 u3 2 v3 5 v4 2,31,(ui+vj),cij,ij,32,33,34,成本表,u1+v3=5 u2+v3 =2 u1+v5 =0 u2+v4 =1 u2+v1=1 u3+v2=2 u3+v4=4 令： u10,u10 v14 u2-3 v2 2 u3 0 v3 5 v4 4 v50,35,(ui+vj),cij,ij,36,37,成本表,u1+v1=2 u2+v4 =1 u1+v3 =5 u3+v2 =2 u1+v5=0 u3+v4=4 u2+v3=2 令： u10,u10 v12 u2-3 v2 2 u3 0 v3 5 v4 4 v50,38,(ui+vj),cij,ij,39,40,C =7