最优化理论运输问题.ppt

*例3某市有三个造纸厂A1，A2，A3和四个批发用户B1，B2，B3，B4，各造纸厂纸的产量、各批发用户的需求量及各造纸厂到各批发用户的单位运价如下表4-32所示，试确定运输总费用最小的调运方案.批发用户造纸厂B1B2B3B4产量A1312348A2112595A367159需求量4356第61页,共84页，2024年2月25日，星期天*解由于该问题中总产量为22，总销量为18，因而该问题是总产量大于总销量的产销不平衡运输问题.按照模型（4.5）的分析知，增加一个假想销地B5，其需求量为22-18=4，可将该问题表示的运输问题转化为下表4-33所示的产销平衡运输问题.用户造纸厂B1B2B3B4B5产量A13123408A21125905A3671509需求量435622-18=4根据表上作业法，可得该问题的最优运输方案如下表4-34所示第62页,共84页，2024年2月25日，星期天*用户造纸厂B1B2B3B4B5产量A1431234408A2113259205A3675125209销量435622-18=4在以上讨论中，我们都假定物资由产地直接运送到销售目的地，不经过中间转运.在实际问题中，还会遇到将物资运到某个中间转运站（包括产地、销地或中间转运仓库），然后再运往销售目的地的情况.有时经转运比直接运往目的地更为经济，在决定运输方案时有必要将转运也考虑进去.当然考虑转运将使问题变得复杂，有兴趣的读者可以参阅相关文献.第63页,共84页，2024年2月25日，星期天*下面我们通过几个例子介绍运输问题的一些实际应用.例4设有三个化肥厂供应四个地区的农用化肥，假定等量的化肥在这些地区试用效果相同.各化肥厂年产量、各地区年需求量（单位：万吨）及从各化肥厂到各地区运送单位化肥的单位运价（单位：万元/万吨）如表4-35所示，试给出总运费最小的化肥调拨方案.4.4运输问题应用举例第64页,共84页，2024年2月25日，星期天*需求地区化肥厂ⅠⅡⅢⅣ产量11613221750214131915603192023—50最低需求最高需求3050707003010不限解这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求不限，但根据现有产量，第Ⅳ个地区每年最多能分配到60万吨，因而最高需求为210万吨，大于总产量.为了求得平衡，在产销表中增加一个假想的化肥厂4，其年产量为50万吨.第65页,共84页，2024年2月25日，星期天*各地区的需求量包含最低需求和额外需求两部分.如地区Ⅰ，其中30万吨是最低需求，故不能由假想化肥厂Ⅳ供给，因而令假想化肥厂4到地区Ⅰ的单位运价为M（M为任意大的数），而额外需求20万吨对地区Ⅰ来说可以满足，也可以不满足，因此额外需求可以由假想化肥厂4供给，而且相应的运价为0.事实上，对凡是需求分两种情况的地区，我们按照两个地区看待，这样可将原问题转化为产销平衡运输问题，其产销平衡表与单位运价表如下表4-36所示.第66页,共84页，2024年2月25日，星期天*需求地区化肥厂Ⅰ?Ⅰ?ⅡⅢⅣ?Ⅳ?产量116161322171750214141319151560319192023MM504M0M0M050需求量302070301050根据表上作业法进行计算，可以求得最优方案如下表4-37所示.第67页,共84页，2024年2月25日，星期天*需求地区化肥厂Ⅰ?Ⅰ?ⅡⅢⅣ?Ⅳ?产量1161650132217175021414201319101530156033019201902023MM504M0M300M20050需求量302070301050从表4-37可以看出，地区Ⅰ满足最高需求量50万吨，地区Ⅲ没有接收到任何物资，只满足最低需求0，而地区Ⅳ满足了40万吨第68页,共84页，2024年2月25日，星期天*使用者产地ⅠⅡⅢ产量124321563324使用量1046