《运筹学3运输问题2》由会员分享，可在线阅读，更多相关《运筹学3运输问题2（25页珍藏版）》请在金锄头文库上搜索。
1、hw关于退化问题1、初始解退化即所求初始基变量的个数少于 m+n1。 必须补足基变量的个数，否则不能正常解出 m+n 个ui 和vj （如填写一个数字同时满足了 一厂一商，则需在同行或同列中填写一个数字 0，以保证恰好有m+n-1个数字），基可行解 中不能有某个基变量独占一行一列 2、迭代过程中出现退化闭合回路中偶数次基变量同时有多个达到 最小，变换后，有多个原基变量变为 0，选运 费最大者为退基变量，其余保留在新的基解中1hw供供大于求大于求供不应求供不应求增加虚拟销地增加虚拟销地 增加虚拟产地增加虚拟产地 产销平衡的运输问题产销平衡的运输问题对应的运距（或运价）对应的运距（或运价） ？转化
2、3.3 3.3 运输问题的推广运输问题的推广一、产销不平衡的运输问题一、产销不平衡的运输问题2hw例2 供大于求的运输问题运费及产销量表B1 B2 B3产量A1A2A3A46 4 58 3 27 5 65 1 27040 5020销量 30 40 30 180 1003hw例2 解：引入虚拟销地B4，（或理解为仓库）， 就地“销售”，运费为零B1 B2 B3 B4产 量A1A2A3A46 4 5 08 3 2 07 5 6 05 1 2 07040 5020销量 30 40 30 80 180 1804hw例2 求初始方案：用最小元素法，但零视为最大元素。（？ ）B1 B2 B3 B4 产 量
3、A1A2A3A46 4 5 08 3 2 07 5 6 05 1 2 070 40 5020 销量 30 40 30 80180 180/2020/3010/1010/1060/3030/30/505hw6/30 4/10 5 0/308 3/10 2/30 07 5 6 0/505 1/20 2 0102330-33例2 检验所以，此方案为最优方案。其调运费用为： 306 + 104 + 103 +302 + 201 = 3306hw例题3：弹性需求问题（P96）设有三个化肥厂供应四个地区，资料如下 ：运价 地区 化肥厂甲乙丙丁产 量ABC16 14 1913 13 2022 19 2317
4、 15-50 60 50 最低需求 最高需求30 5070 700 3010 不限7hw例题3：解题思路：设法转化为标准型 本题产量160万吨，最低需求110万吨，最高需 求无限。实质上比较现实的最高需求为210万吨（ 根据现有产量） 产量大于最低需求；小于最高需求。而标准型是 ：产量=销量。 处理办法：设想一个虚拟化肥厂D，其年产量50 万吨，但这个产量只能供应可有可无的最高需求部 分，于是各地的需求也应分为两个部分：基本需求 、机动需求 虚拟产量的运输费用为零，但它对于基本需求来 讲，运费为无穷大。8hw例题3：建模1运价 地区 煤矿甲1甲2 乙丙丁1 丁2产量ABCD16 14 19 M
5、16 14 19 013 13 20 M22 19 23 017 15 M M17 15 M 050605050 需求量302070301050 210 2109hw1运价 地区 煤矿甲1甲2乙丙丁1丁2产量ABCD16 14 19 M16 14 19 013 13 20 M22 19 23 017 15 M M17 15 M 050 60 50 50 需求量302070301050 210 21030202030502010302020 30200例题3：求解（Vogel法）10hw16 14 19 M16 14 19 013 13 20 M22 19 23 017 15 M M17 15
6、M 050605050302070301050 /50 /20 /30/0 /20/30/2077/307128678-88/10得最优调运方案：C供应甲50、A和B供应乙70、B供应丁40（万t） ，不供应丙。 最低调运费用为：5019 + 7013 + 4015 = 2460（万元）例题3：检验11hw特点特点: : 调运的物资不是由产地直接运送到调运的物资不是由产地直接运送到 销地，而是经过若干中转站送达。销地，而是经过若干中转站送达。求解思路求解思路：转化成一个等价的产销平衡：转化成一个等价的产销平衡 运输问题，再用表上作业法求出最运输问题，再用表上作业法求出最 优调运方案。优调运方案
7、。如何转化如何转化 ？二、转运问题二、转运问题12hw第一步，将产地、转运点、销地重新编排第一步，将产地、转运点、销地重新编排 ，转运点既作为产地又作为销地；，转运点既作为产地又作为销地；第二步，各地之间的运距（或运价）在原第二步，各地之间的运距（或运价）在原 问题运距（运价）表基础上进行扩展：从问题运距（运价）表基础上进行扩展：从 一地运往自身的单位运距（运价）记为零一地运往自身的单位运距（运价）记为零 ，不存在运输线路的则记为，不存在运输线路的则记为MM（一个足够一个足够大的正数）；大的正数）；13hw第三步，由于经过转运点的物资量既第三步，由于经过转运点的物资量既 是该点作为销地的需求量
8、，又是该点是该点作为销地的需求量，又是该点 作为产地时的供应量，但事先又无法作为产地时的供应量，但事先又无法 获取该数量的确切值，因此通常将调获取该数量的确切值，因此通常将调 运总量作为该数值的上界。运总量作为该数值的上界。对于产地和销地也作类似的处理。对于产地和销地也作类似的处理。（参见P98例4）14hw三、运输模型的应用例题4：某机床厂定下一年合同分别于各 季度末交货。已知各季度生产成本不同， 允许存货，存储费0.12万元/台季，三、四 季度可以加班生产，加班生产能力8台/季 ，加班费用3万元/台季度 正常生产能力单位成本（万元 ）交货台数1 2 3 430 32 20 2810.55
9、10.8 11 11.125 30 15 4515hw例4 分析：可用线性规划，但用运输问题更简单要决策的问题是各季度生产量和交货量 设xij表示第i季度生产第j季度交货的台数因加班时间生产成本不同，故要区别开 来，三四季度可加班，视同增加两个季度需求量合计115台，生产能力合计126台 ，供需不平衡，因此，增加一虚拟季度交 货。16hw例4 建模：.成本 交货 生产虚拟1 2 3 4 季度产量1季度正常生产 2季度正常生产 3季度正常生产 3季度加班生产 4季度正常生产 4季度加班生产10.55 10.67 10.79 10.91 0M 10.8 10.92 11.04 0M M 11 11
10、.12 0M M 14 14.12 0M M M 11.1 0M M M 14.1 03032208288需求量 25 30 15 45 11 126 12617hw例4 结果生产 交货 生产虚拟1 2 3 4 季度产量1季度正常生产 2季度正常生产 3季度正常生产 3季度加班生产 4季度正常生产 4季度加班生产25 530 210 10 8285 33032208288需求量 25 30 15 45 11 126 12618hw例题5 航运调度问题（P1023.6）某航运公司承担六个城市A、B、C、D、E、F 之间的四条航线，已知各航线的起点、终点及每 天所需的航班数如下表。又知各城市之间的
11、航行 天数，假定船只型号相同，装卸货时间各一天， 问该公司至少要配备多少条船才能满足需要？航 线起点 终 点每天航班数1 2 3 4E B A DD C F B321119hw例5 城市之间航行天数表.Ci jA B C D E FA B C D E F0 1 2 14 7 71 0 3 13 8 82 3 0 15 5 514 13 15 0 17 207 8 5 17 0 37 8 5 20 3 020hw例5 问题分析所需船只分为两部分： （1）各航线航行、装船、卸船所占用的船只航线航行 天数装卸 天数小计 航班数 所需 船数 1 2 3 417 3 7 132 2 2 219 5 9
12、153 2 1 157 10 9 15累计共需91条船 21hw例5 问题分析（续1）（2）各港口之间调度所需船只数港口 到达开出 余缺A B C D E F0 1 2 3 0 11 2 0 1 3 0-1 -1 2 2 -3 1ABCDEF12 13调度中心若无空驶，则91条船刚好够 用，但虚线箭头都是空驶22hw例5 问题分析（续2）有的可在一个港口卸货后马上装运（如一条 船从E到D后再起程赴B）。若港口没有空船， 则要从其它港口调度而来。将船由多余船只的 港口调往需用船只的港口为空船行驶。由上表可知：C、D、F港口有多余船只可供 调出，而A、B、E港口则需要调入空船。问题的核心是：如何使空驶船的数量为最少 ？亦即如何按照最近原则调度船只。23hw例5 问题分析（续3）为此建立下表所示的运输问题，其单位运 价取为相应一对港口城市间的航行天数。至 由A B E每天多 余船数CDF2147313851732 2 1每天缺 少船数1 1 324hw例五 解题结果由初始方案调整后得最优解A B E每天多 余船只CDF1 1111221 每天缺 少船只1 1 3目标值为：2+5+13+17+3=40，说明各港口之间调度 所需船只至少为40条。该公司至少要配备 91+40=131 条船，才能满足4条航线正常运输的需要。 25
