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

1、设数学模型为 minjijijxCZ11maxnjmixnjbxmiaxijmijijnjiij, 2 , 1;, 2 , 10, 2 , 1, 2 , 111，一、运输问题的变体：求极大值问题一、运输问题的变体：求极大值问题第一种方法：将极大化问题转化为极小化问题。设极大化问题的运价表为C=Cijmn，用一个较大的数MMmaxCij去减每一个Cij得到矩阵C/=Cijmn ，其中C/ij=MCij0,将C/作为极小化问题的运价表，用表上用业法求出最优解，目的函数值为 minjijijxCZ11.例如，以下矩阵C是AiI=1，2，3到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大.45

2、67109852C12109 则取ijijijCCCCM10,10max/22654301258/C用最小元素法求初始方案得048109X11=8,12=4,21=2,23=2全部非负,得到 最 优 运 输 方 案 X , 最 大 利 润Z=89+1010+68+54=240第二种方法:一切非基变量的检验数ij0时最优.求初始运输方案可采用最大元素法.如上例,用最大元素得到 的初始运输方案:048109X4567109852C121098 14 9求检验数:11=8,12=4,21=2,23=2,全部非正,得到最优解运输方案,结果与第一种方法一样.用最小元素法求初始方案得048109X11=8

3、,12=4,21=2,23=2全部非负,得到 最 优 运 输 方 案 X , 最 大 利 润Z=89+1010+68+54=240第二种方法:一切非基变量的检验数ij0时最优.求初始运输方案可采用最大元素法.如上例,用最大元素得到 的初始运输方案:048109X4567109852C121098 14 9求检验数:11=8,12=4,21=2,23=2,全部非正,得到最优解运输方案,结果与第一种方法一样.用最小元素法求初始方案得048109X11=8,12=4,21=2,23=2全部非负,得到 最 优 运 输 方 案 X , 最 大 利 润Z=89+1010+68+54=240第二种方法:一切

4、非基变量的检验数ij0时最优.求初始运输方案可采用最大元素法.如上例,用最大元素得到 的初始运输方案:048109X4567109852C121098 14 9求检验数:11=8,12=4,21=2,23=2,全部非正,得到最优解运输方案,结果与第一种方法一样.二、产销不平衡的运输问题及其求解方法二、产销不平衡的运输问题及其求解方法minjjiijXCZ11min11(1,2,.,)(1,2,., )0(1,2,., ,1,2,., )nijijmijjiijXa imXbjnXim jnminjjiijXC11min11(1,2,.,)(1,2,., )0(1,2,., ,1,2,., )n

5、ijijmijjiijXa imXbjnXim jnnjjmiiba11产大于销11mnijijab销大于产然后再用产销平衡的运输问题的解法进展解之。 2.解法思绪：解法思绪： 将不平衡运输问题转化为平衡运输问题。即当将不平衡运输问题转化为平衡运输问题。即当 时，思索在平衡表中添加一虚拟列，表示添加一个销货点时，思索在平衡表中添加一虚拟列，表示添加一个销货点(j=n+1)如仓库，其销货量为如仓库，其销货量为 ，且各运价，且各运价Cin+1=0；当；当 时，思索在平衡表中添加一虚拟时，思索在平衡表中添加一虚拟行，表示添加一个新产地，且各运价行，表示添加一个新产地，且各运价Cm+1j=0。其产量为

6、。其产量为 njjmiiba11njjmiiba11njjmiiba11miinjjab11不平衡运输问题不平衡运输问题 : 当总产量与总销量不相等时当总产量与总销量不相等时,称为不平称为不平衡运输问题衡运输问题.这类运输问题在实践中经常碰到这类运输问题在实践中经常碰到,它的求解方它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。法是将不平衡问题化为平衡问题再按平衡问题求解。(一一) 当产大于销时当产大于销时, 即即 minjjiba11数学模型为 minjijijxCZ11minnjmixnjbxmiaxijmijijnjiij, 2 , 1;, 2 , 10, 2 , 1, 2 ,

7、111，由于总产量大于总销量，必有部分产地的产量不能全部运送完，必需就地库存，即每个产地设一个仓库，库存量为xi，n+1i=1，2，m，总的库存量为 njjmiimininmnnnbaxxxxb1111,1,1,21, 11bn+1作为一个虚设的销地作为一个虚设的销地Bn+1的销量。各产地的销量。各产地Ai到到Bn+1的运价为零，即的运价为零，即Ci，n+1=0,i=1，m。那么平衡问。那么平衡问题的数学模型为：题的数学模型为： minjijijxCZ11min, 2 , 1, 2 , 1, 01, 2 , 1, 2 , 1111jmixnjbxmiaxijmijijnjiij；详细求解时,只

8、在运价表右端添加一列Bn+1，运价为零,销量为bn+1即可二当销大于产时二当销大于产时,即即minjjiba11数学模型为 minjijijxCZ11minnjmixnjbxmiaxijmijijnjiij, 2 , 1;, 2 , 1, 0, 2 , 1, 2 , 111由于总销量大于总产量由于总销量大于总产量,故一定有些需求地不完全满足故一定有些需求地不完全满足,这时虚设一这时虚设一个产地个产地Am+1，产量为，产量为 nmmmmxxxa,121111，njmiijnjjmabx1111,xm+1,j 是是Am+1运到运到Bj的运量，也是的运量，也是Bj不能满足需求的数量。不能满足需求的数

9、量。Am+1到到Bj的运价为零的运价为零,即即Cm+1,j=0(j=1,2, ,n) 销大于产平衡问题的数学模型为销大于产平衡问题的数学模型为 ： minjijijxCZ11minnjmixnjbxmiaxijmijijnjiji, 2 , 11, 2 , 1, 0, 2 , 11, 2 , 1111；详细计算时，在运价表的下方添加一行Am+1，运价为零。产量为am+1即可。 B1B2B3B4aiA1592360A2-47840A3364230A448101150bj206035451801604141160180ijjiba由于有：看一个例题：求以下表中极小化运输问题的最优解。 所以是一个产

10、大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180160=20，Ci5=0，i=1，2，3，4。表的右边增添一列 这样我们可得新的运价表：这样我们可得新的运价表：B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180下表为计算结果。可看出：产地A4还有20个单位没有运出。案例案例1 某企业和用户签署了设备交货合同，知该企业各季度的某企业和用户签署了设备交货

11、合同，知该企业各季度的消费才干、每台设备的消费本钱和每季度末的交货量如下表，消费才干、每台设备的消费本钱和每季度末的交货量如下表，假设消费出的设备当季度不交货，每台设备每季度需支付保管假设消费出的设备当季度不交货，每台设备每季度需支付保管维护费维护费0.1万元万元,试问在遵守合同的条件下试问在遵守合同的条件下,企业如何安排消费方案企业如何安排消费方案,才干使年消耗费用最低才干使年消耗费用最低?季度季度工厂生产能力工厂生产能力(台台)交货量交货量(台台)每台设备生产成本每台设备生产成本(万元万元)1251512.02352011.03302511.54202012.5 交货季交货季生产季生产季1

12、2345(虚拟列虚拟列)生产量生产量112.012.112.212.30252M11.011.111.20353MM11.511.60304MMM12.5020交货量交货量1520252030转化为平衡运输问题的运输表转化为平衡运输问题的运输表例例2： 知某运输问题的资料如下表所示知某运输问题的资料如下表所示B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125 1 1、表中的发量、收量单位为：吨，运价单位为：元、表中的发量、收量单位为：吨，运价单位为：元/ /吨吨 试求出最优运输方案试求出最优运输方案. . 2 2、如将、如将A2A2的发量改为的发量改

13、为1717，其它资料不变，试求最优调，其它资料不变，试求最优调 运方案。运方案。B1B2B3B4发量发量A112315A210212A313013收量收量1013125B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125解：解：1、用最小元素法求初始方案、用最小元素法求初始方案B1B2B3B4发量发量A112315A210212A313013收量收量1013125B1B2B3B4A153A211A324运费为运费为108108元元/ /吨吨2 2、用位势法判别：、用位势法判别：B1B2B3B4ui A153u1A211u2A324u3vj v1v2v3

14、v4本钱表本钱表B1B2B3B4ui A153u1A211u2A324u3vj v1v2v3v4 u1+v3=5 u2+v4 =1 u1+v4 =3 u3+v2=2 u2+v1=1 u3+v4 =4 令：令： u10u10 v13u22 v2 1u3 1 v3 5 v4 3 B1B2B3B4ui A1530A2112A3241vj 3153B1B2B3B4ui A131530A211312A342641vj 3153(ui+vj)B1B2B3B4A12653A21321A33274B1B2B3B4A13153A21131A34264cijB1B2B3B4A11500A20410A31010表中

15、还有负数，阐表中还有负数，阐明没有得到最优解，明没有得到最优解，调整运输方案。调整运输方案。ij(ui+vj)B1B2B3B4A1123A2102A3130B1B2B3B4A1105A2102A31302222新的运送方案新的运送方案B1B2B3B4A153A212A324新的本钱表新的本钱表B1B2B3B4ui A141530A212203A352641vj 4153(ui+vj)1 总的运费总的运费 105元元/吨吨B1B2B3B4A14153A21220A35264B1B2B3B4A12653A21321A33274B1B2B3B4A12500A20501A32010表中还有负数，阐表中

16、还有负数，阐明没有得到最优解，明没有得到最优解，继续调整运输方案。继续调整运输方案。cij(ui+vj)1 (ij)1 013A3210A2510A1B4B3B2B13512vj 14623A330221A203512A1ui B4B3B2B1(ui+vj)2 42A32A2352A1B4B3B2B1新的本钱表新的本钱表013A312A25010A1B4B3B2B1新的运送方案新的运送方案总的运费总的运费 85元元/吨吨B1B2B3B4A12653A21321A33274cijB1B2B3B4A12153A21 220A33264(ui+vj)2 B1B2B3B4A10500A22501A30

17、010 (ij)2 表中没有负数，阐表中没有负数，阐明曾经得到最优解。明曾经得到最优解。但有无穷多最优解。但有无穷多最优解。013A312A2510A1B4B3B2B1最终的运送方案最终的运送方案总的运费总的运费 85元元/吨吨B1B2B3B4发量发量A131215A27512A313013收量收量1013125B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125B1B2B3B4A125A211A327B1B2B3B4ui A125u1A211u2A327u3vj v1v2v3v4本钱表本钱表 u1+v1=2 u2+v4 =1 u1+v3 =5 u3+

18、v2 =2 u2+v1=1 u3+v3 =7 令：令： u10u10 v12u21 v2 0u3 2 v3 5 v4 2 B1B2B3B4ui A120520A21-141-1A342742vj 2052(ui+vj)B1B2B3B4A12653A21321A33274cijB1B2B3B4ui A10601A204-20A3-1000vj ijB1B2B3B4发量发量A131215A27512A313013收量收量1013125B1B2B3B4发量发量A110515A27512A313013收量收量1013125B1B2B3B4B5发量发量A110515A2102517A313013收量收量

19、10131255B1B2B3B4B5发量发量A12653015A21321017A33274013收量收量10131255B1B2B3B4B5A150A2121A324B1B2B3B4B5ui A150u1A2121u2A324u3vj v1v2v3v4v5本钱表本钱表 u1+v3=5 u2+v3 =2 u1+v5 =0 u2+v4 =1 u2+v1=1 u3+v2=2 u3+v4=4 令：令： u10u10 v14u2-3 v2 2u3 0 v3 5 v4 4 v50B1B2B3B4B5ui A1425400A21-121-3-3A3425400vj 42540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5 A1-240-10A204004A3-10200ij505B45121310收量收量1313A31721