运输课程讲座.pptx

《运输课程讲座.pptx》由会员分享，可在线阅读，更多相关《运输课程讲座.pptx（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第一种方法：将极大化问题转化为极小化问题。设极大化问题的运价表为C=（Cij）mn，用一个较大的数M（MmaxCij）去减每一个Cij得到矩阵C/=（Cij）mn，其中C/ij=MCij0,将C/作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为 例如，下列矩阵C是Ai（I=1，2，3）到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大.8 14 9第1页/共41页2用最小元素法求初始方案得11=8,12=4,21=2,23=2全部非负,得到最 优 运 输 方 案 X,最 大 利 润Z=89+1010+68+54=240第二种方法:所有非基变量的检验数ij0时最优.求初始运输

2、方案可采用最大元素法.如上例,用最大元素得到 的初始运输方案:8 14 9求检验数:11=8,12=4,21=2,23=2,全部非正,得到最优解运输方案,结果与第一种方法相同.第2页/共41页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,全部非正,得到最优解运输方案,结果与第一种方法相同.第3页/共41页4

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页/共41页5二、产销不平衡的运输问题及其求解方二、产销不平衡的运输问题及其求解方法法产大于销销大于产第5页/共41页6然后再用产销平衡的运输问题的解法进行解之。2.解法思路：将不平衡运输问题转化为平衡运输问

4、题。即当 时，考虑在平衡表中增加一虚拟列，表示增加一个销货点(j=n+1)如仓库，其销货量为 ，且各运价Cin+1=0；当 时，考虑在平衡表中增加一虚拟行，表示增加一个新产地，且各运价Cm+1j=0。其产量为 第6页/共41页7不平衡运输问题不平衡运输问题:当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。(一)当产大于销时,即 数学模型为 第7页/共41页8由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，库存量为xi，n+1（i=1，2，m），总的库存量为 第8页/共

5、41页9bn+1作为一个虚设的销地Bn+1的销量。各产地Ai到Bn+1的运价为零，即Ci，n+1=0,（i=1，m）。则平衡问题的数学模型为：具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可第9页/共41页10（二）当销大于产时,即数学模型为 第10页/共41页11由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为 xm+1,j 是Am+1运到Bj的运量，也是Bj不能满足需要的数量。Am+1到Bj的运价为零,即Cm+1,j=0(j=1,2,n)第11页/共41页12销大于产平衡问题的数学模型为：具体计算时，在运价表的下方增加一行Am+1，

6、运价为零。产量为am+1即可。第12页/共41页13B1B2B3B4aiA1592360A2-47840A3364230A448101150bj20603545180160因为有：看一个例题：求下列表中极小化运输问题的最优解。第13页/共41页14 所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180160=20，Ci5=0，i=1，2，3，4。表的右边增添一列 这样我们可得新的运价表：B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180第14页/共41页15

7、B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180下表为计算结果。可看出：产地A4还有20个单位没有运出。第15页/共41页16案例1 某企业和用户签订了设备交货合同，已知该企业各季度的生产能力、每台设备的生产成本和每季度末的交货量如下表，若生产出的设备当季度不交货，每台设备每季度需支付保管维护费0.1万元,试问在遵守合同的条件下,企业如何安排生产计划,才能使年消耗费用最低?季度季度工厂生产能力工厂生产能力(台台)交货量交货量(台台)每台设备生产成本每台设备生产成本(万元万元)1251512.02352011.03302511

8、.54202012.5 交货季交货季生产季生产季12345(虚拟列虚拟列)生产量生产量112.012.112.212.30252M11.011.111.20353MM11.511.60304MMM12.5020交货量交货量1520252030转化为平衡运输问题的运输表第16页/共41页17 已知某运输问题的资料如下表所示已知某运输问题的资料如下表所示B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125 1 1、表中的发量、收量单位为：吨，运价单位为：元、表中的发量、收量单位为：吨，运价单位为：元/吨吨 试求出最优运输方案试求出最优运输方案.例例2：2

9、2、如将、如将A2的发量改为的发量改为1717，其它资料不变，试求最优调，其它资料不变，试求最优调 运方案。运方案。第17页/共41页18B1B2B3B4发量发量A112315A210212A313013收量收量1013125B1B2B3B4发量发量A1265315A2132112A3327413收量收量1013125第18页/共41页19解：解：1、用最小元素法求初始方案、用最小元素法求初始方案B1B2B3B4发量发量A112315A210212A313013收量收量1013125B1B2B3B4A153A211A324运费为运费为108108元元/吨吨2 2、用位势法判断：、用位势法判断：

10、B1B2B3B4ui A153u1A211u2A324u3vj v1v2v3v4成本表成本表第19页/共41页20B1B2B3B4ui 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 第20页/共41页21B1B2B3B4ui A1530A2112A3241vj 3153B1B2B3B4ui A131530A211312A342641vj 3153(ui+vj)第21页/共41页22B1B2B3B4A12653A2

11、1321A33274B1B2B3B4A13153A21131A34264cijB1B2B3B4A11500A20410A31010表中还有负数，说表中还有负数，说明没有得到最优解，明没有得到最优解，调整运输方案。调整运输方案。ij(ui+vj)第22页/共41页23B1B2B3B4A1123A2102A3130B1B2B3B4A1105A2102A31302222新的运送方案新的运送方案B1B2B3B4A153A212A324新的成本表新的成本表B1B2B3B4ui A141530A212203A352641vj 4153(ui+vj)1 总的运费总的运费 105元元/吨吨第23页/共41页2

12、4B1B2B3B4A14153A21220A35264B1B2B3B4A12653A21321A33274B1B2B3B4A12500A20501A32010表中还有负数，说表中还有负数，说明没有得到最优解，明没有得到最优解，继续调整运输方案。继续调整运输方案。cij(ui+vj)1 (ij)1 第24页/共41页25013A3210A2510A1B4B3B2B13512vj 14623A330221A203512A1ui B4B3B2B1(ui+vj)2 42A32A2352A1B4B3B2B1新的成本表新的成本表013A312A25010A1B4B3B2B1新的运送方案新的运送方案总的运费

13、总的运费 85元元/吨吨第25页/共41页26B1B2B3B4A12653A21321A33274cijB1B2B3B4A12153A21 220A33264(ui+vj)2 B1B2B3B4A10500A22501A30010(ij)2 表中没有负数，说表中没有负数，说明已经得到最优解。明已经得到最优解。但有无穷多最优解。但有无穷多最优解。0第26页/共41页2713A312A2510A1B4B3B2B1最终的运送方案最终的运送方案总的运费总的运费 85元元/吨吨第27页/共41页28B1B2B3B4发量发量A131215A27512A313013收量收量1013125B1B2B3B4发量发

14、量A1265315A2132112A3327413收量收量1013125第28页/共41页29B1B2B3B4A125A211A327B1B2B3B4ui A125u1A211u2A327u3vj v1v2v3v4成本表成本表 u1+v1=2 u2+v4=1 u1+v3=5 u3+v2=2 u2+v1=1 u3+v3=7 令：令：u10u10 v12u21 v2 0u3 2 v3 5 v4 2 第29页/共41页30B1B2B3B4ui A120520A21-141-1A342742vj 2052(ui+vj)B1B2B3B4A12653A21321A33274cijB1B2B3B4ui A1

15、0601A204-20A3-1000vj ij第30页/共41页31B1B2B3B4发量发量A131215A27512A313013收量收量1013125B1B2B3B4发量发量A110515A27512A313013收量收量1013125第31页/共41页32B1B2B3B4B5发量发量A110515A2102517A313013收量收量10131255B1B2B3B4B5发量发量A12653015A21321017A33274013收量收量10131255第32页/共41页33B1B2B3B4B5A150A2121A324B1B2B3B4B5ui A150u1A2121u2A324u3vj

16、 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 v50第33页/共41页34B1B2B3B4B5ui A1425400A21-121-3-3A3425400vj 42540(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5 A1-240-10A204004A3-10200ij第34页/共41页35505B45121310收量收量1313A317210A215510A1发

17、量发量B5B3B2B1B1B2B3B4B5发量发量A1100515A212517A313013收量收量10131255第35页/共41页36B1B2B3B4B5A1250A221A324B1B2B3B4B5ui A1250u1A221u2A324u3vj v1v2v3v4v5成本表成本表 u1+v1=2 u2+v4=1 u1+v3=5 u3+v2=2 u1+v5=0 u3+v4=4 u2+v3=2 令：令：u10u10 v12u2-3 v2 2u3 0 v3 5 v4 4 v50第36页/共41页37B1B2B3B4B5ui A1225400A2-1-121-3-3A3225400vj 225

18、40(ui+vj)B1B2B3B4B5A126530A213210A332740cijB1B2B3B4B5 A1040-10A224004A310200ij第37页/共41页38B1B2B3B4B5发量发量A1100515A212517A313013收量收量10131255B1B2B3B4B5发量发量A1100515A212517A313013收量收量10131255第38页/共41页39B1B2B3B4B5发量发量A110515A212517A31313收量收量10131255C=75第39页/共41页40本章介绍了运输模型的特征；运输模型的特殊求解方法；不平衡问题、需求量不确定问题、极大值问题的求解方法；运输问题的应用。The End of Chapter 3 第四章 目标规划作业：教材 P99 T3.3（3）（4）3.5 3.6 T3.7Exit第40页/共41页41感谢您的观看！第41页/共41页