运筹学四运输问题.pptVIP

运输问题 运输问题及其数学模型 运输问题的表上作业法 运输问题的进一步讨论 表上作业法 计算步骤： 1、给出初始方案 2、检验是否最优 3、调整调运方案 , Go to 2 表上作业法 计算步骤： 1、给出初始方案 2、检验是否最优 3、调整调运方案 , Go to 2 表上作业法 计算步骤： 1、给出初始方案 2、检验是否最优 3、调整调运方案 , Go to 2 例题5：弹性需求问题 设有三煤矿供应四地区，资料如下： 解题思路： 设法转化为标准型 本题产量160万吨，最低需求110万吨，最高需求无限。实质上比较现实的最高需求210万吨 产量大于最小需求；小于最大需求。而标准型是：产量=销量。 处理办法：设想一个虚拟煤矿D，生产50万吨，但这个产量只能供应可有可无的最高需求部分，于是各地的需求也应分为两个部分：基本需求、机动需求 虚拟产量的运输费用为零，但它对于基本需求来讲，运费为无穷大。 建模： 最优解： 运输模型的应用 例题5：某机床厂定下一年合同分别于各季度末交货。已知各季度生产成本不同，允许存货，存储费0.12万元/台季，三、四季度可以加班生产，加班生产能力8台/季，加班费用3万元/台 分析： 可用线性规划，但用运输问题更简单 要决策的问题是各季度生产量和交货量设xij表示第i季度生产第j季度交货的台数 因加班时间生产成本不同，故要区别开来，三四季度可加班，视同增加两个季度 需求量合计115台，生产能力合计126台，供需不平衡，因此，增加一项闲置能力。 建模： 结果： 例题5 航运调度问题 某航运公司承担六个城市A、B、C、D、E、F之间的四条航线，已知各航线的起点、终点及每天所需的航班数如下表。又知各城市之间的航行天数，假定船只型号相同，装卸货时间各一天，问该公司至少要配备多少条船才能满足需要？ 城市之间航行天数表 问题分析 问题要求的是在保证需要的前提下，至少需多少船只。 所需船只包括两个部分：载货船、空驶船 。 问题分析（续1） 上表显示：载货船共需91条，此船何来？ 问题分析（续2） 所需91条货船要经调度而来，有的可在一个港口卸货后装运（如一条船从E到D后再起程赴B）。若港口没有空船，则要从其它港口调度而来。（规模效益） 由上表可知：C、D、F港口有多余船只可供调出，而A、B、E港口则需要调入空船。 问题的核心是：如何使空驶船的数量为最少？亦即如何按照最近原则调度船只 问题分析（续3） 为此建立运输问题数学模型。设xij表示每天从i港口调往j港口的空船数，则cijxij就表示 i j航线上周转的船只数，∑cijxij表示各条线上周转的船只总数 解题结果 §3 运输问题的进一步讨论 一、产销不平衡运输问题 对产销不平衡问题，可转化为平衡问题，然后按表上作业 法求解。转换办法： ⒈ 若产大于销，增加一个假想的销地（可视为库存地）其销 量设定为余量，相应的运价设为0。 ⒉ 若销大于产，增加一个虚拟的产地，其产量设定为不足 量，相应的运价也设为0。 例4 某市有3个造纸厂 ， 和 ，有4个集中用户 和 ，各工厂的生产量、各用户的需用量以及各 工厂到用户的单位运价（元/t）示于表3-14中，问如何调运 才能使总运费最小？ 5 1 7 9 5 2 6 11 4 9 5 8 产 量 6 5 3 4 销 量 3 12 3 销地 产地 表 3-14 22 18 可增加一个假想的销地 0 0 0 4 5 1 7 9 5 2 6 11 4 9 5 8 产 量 6 5 3 4 销 量 3 12 3 销地 产地 表 3-14 补充：闭回路的数学定义 定义： 凡是能排成 或 形式的变量的集合称为一个闭回路，并将这些变量称为这个闭回路的顶点。 由此可以看出闭回路的几何特点： 闭回路都是一条封闭折线，每个顶点格子都是转角点 每一行或每一列只有且仅有两个顶点格子 每两个顶点格子的连线都是水平的或垂直的。 可以证明的一个重要结论： m+n-1个变量构成基变量的充要条件是它不含闭回路，即不存在以这些变量为顶点的闭回路 10 不限 0 30 70 70 30 50 最低需求 最高需求 50 60 50 17 15 25 22 19 23 13 13 20 16 14 19 A B C 产量 丁 丙 乙 甲 运价 地区 煤矿 产量 丁2 丁1 丙 乙 甲2 甲1 运价 地区 煤矿 210 210 50 10 30 70 20 30 需求量 50 60 50 50 17 12 25