《运筹学3运输问题课件》由会员分享，可在线阅读，更多相关《运筹学3运输问题课件（25页珍藏版）》请在金锄头文库上搜索。
1、1,关于退化问题,1、初始解退化 即所求初始基变量的个数少于 m+n1。必须补足基变量的个数，否则不能正常解出 m+n 个ui 和vj （如填写一个数字同时满足了一厂一商，则需在同行或同列中填写一个数字0，以保证恰好有m+n-1个数字），基可行解中不能有某个基变量独占一行一列 2、迭代过程中出现退化 闭合回路中偶数次基变量同时有多个达到最小，变换后，有多个原基变量变为 0，选运费最大者为退基变量，其余保留在新的基解中,2,增加虚拟销地,增加虚拟产地,产销平衡的运输问题,对应的运距（或运价） ？,3.3 运输问题的推广一、产销不平衡的运输问题,3,例2 供大于求的运输问题,运费及产销量表,4,例
2、2 解：,引入虚拟销地B4，（或理解为仓库），就地“销售”，运费为零,5,例2 求初始方案：,用最小元素法，但零视为最大元素。（？）,/20,20,/30,10,/10,10,/10,60,/30,30,/30,/50,6,6/30 4/10 5 0/30 8 3/10 2/30 0 7 5 6 0/50 5 1/20 2 0,1,0,2,3,3,0,-3,3,例2 检验,所以，此方案为最优方案。其调运费用为： 306 + 104 + 103 +302 + 201 = 330,7,例题3：弹性需求问题（P96）,设有三个化肥厂供应四个地区，资料如下：,8,例题3：解题思路：,设法转化为标准型
3、本题产量160万吨，最低需求110万吨，最高需求无限。实质上比较现实的最高需求为210万吨（根据现有产量） 产量大于最低需求；小于最高需求。而标准型是：产量=销量。 处理办法：设想一个虚拟化肥厂D，其年产量50万吨，但这个产量只能供应可有可无的最高需求部分，于是各地的需求也应分为两个部分：基本需求、机动需求 虚拟产量的运输费用为零，但它对于基本需求来讲，运费为无穷大。,9,例题3：建模,1,10,1,30,20,20,30,50,20,10,30,20,20,30,20,0,例题3：求解（Vogel法）,11,/50,/20,/30,/0,/20,/30,/20,7,7,/30,7,12,8,
4、6,7,8,-8,8,/10,得最优调运方案： C供应甲50、A和B供应乙70、B供应丁40（万t），不供应丙。 最低调运费用为： 5019 + 7013 + 4015 = 2460（万元）,例题3：检验,12,特点: 调运的物资不是由产地直接运送到销地，而是经过若干中转站送达。 求解思路：转化成一个等价的产销平衡运输问题，再用表上作业法求出最优调运方案。,如何转化 ？,二、转运问题,13,第一步，将产地、转运点、销地重新编排，转运点既作为产地又作为销地； 第二步，各地之间的运距（或运价）在原问题运距（运价）表基础上进行扩展：从一地运往自身的单位运距（运价）记为零，不存在运输线路的则记为M（一
5、个足够大的正数）；,14,第三步，由于经过转运点的物资量既是该点作为销地的需求量，又是该点作为产地时的供应量，但事先又无法获取该数量的确切值，因此通常将调运总量作为该数值的上界。 对于产地和销地也作类似的处理。 （参见P98例4）,15,三、运输模型的应用,例题4：某机床厂定下一年合同分别于各季度末交货。已知各季度生产成本不同，允许存货，存储费0.12万元/台季，三、四季度可以加班生产，加班生产能力8台/季，加班费用3万元/台,16,例4 分析：,可用线性规划，但用运输问题更简单 要决策的问题是各季度生产量和交货量设xij表示第i季度生产第j季度交货的台数 因加班时间生产成本不同，故要区别开来
6、，三四季度可加班，视同增加两个季度 需求量合计115台，生产能力合计126台，供需不平衡，因此，增加一虚拟季度交货。,17,例4 建模：,.,18,例4 结果,19,例题5 航运调度问题（P1023.6）,某航运公司承担六个城市A、B、C、D、E、F之间的四条航线，已知各航线的起点、终点及每天所需的航班数如下表。又知各城市之间的航行天数，假定船只型号相同，装卸货时间各一天，问该公司至少要配备多少条船才能满足需要？,20,例5 城市之间航行天数表,.,21,例5 问题分析,所需船只分为两部分： （1）各航线航行、装船、卸船所占用的船只,累计共需91条船,22,例5 问题分析（续1）,（2）各港口
7、之间调度所需船只数,A,B,C,D,E,F,1,2,1,3,调度中心,若无空驶，则91条船刚好够用，但虚线箭头都是空驶,23,例5 问题分析（续2）,有的可在一个港口卸货后马上装运（如一条船从E到D后再起程赴B）。若港口没有空船，则要从其它港口调度而来。将船由多余船只的港口调往需用船只的港口为空船行驶。 由上表可知：C、D、F港口有多余船只可供调出，而A、B、E港口则需要调入空船。 问题的核心是：如何使空驶船的数量为最少？亦即如何按照最近原则调度船只。,24,例5 问题分析（续3）,为此建立下表所示的运输问题，其单位运价取为相应一对港口城市间的航行天数。,25,例五 解题结果,由初始方案调整后得最优解,目标值为：2+5+13+17+3=40，说明各港口之间调度所需船只至少为40条。该公司至少要配备 91+40=131条船，才能满足4条航线正常运输的需要。,
