运筹学案例.ppt

转运问题 某公司经销某种产品 它下设三个加工厂 每日的产量分别为 A1为7吨 A2为4吨 A3为9吨 该公司把这些产品分别运往四个销售点 各销售点每日销量分别为 B1为3吨 B2为6吨 B3为5吨 B4为6吨 已知从各加工厂到各销售点的单位产品的运价如下表1所示 问该公司应如何调运产品 在满足各销售点需求量的前提下 使总运费为最少 表1 在本章的例1中 如果假定 每个工厂生产的产品不一定直接发运到销售点 可以将其中几个产地集中一起运 运往各销地的产品可以先运给其中几个销地 再转运给其他销地 除产 销地之外 中间还可以有几个转运站 在产地之间 销地之间或产地与销地间转运 已知各产地 销地 中间转运站及相互之间每吨产品的运价如表2所示 问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下 如何将三个厂每天生产的产品运往销售地 使总的运费最少 表2 从表3 40中看出 从A1B2 直接运费为11元 从A1A3B2 运费为3 4 7元 从A1T2B2 运费仅为1 5 6元 而从A1到B2运费最少的路径是 从A1A2B1B2 每吨产品的运费只需1 1 1 3元 可见这个问题中从每个产地到各销地之间的运输方案是很多的 引入 转运问题的特点就是 所调运的物资不是由产地直接运往销地 而是经过若干中转站后才到达 求解通常是设法将其转化为一个等价的产销平衡的运输问题 然后再用表上作业法求出最优调配方案 其大体思路如下 1 将产地 中间转运站 销地既看作销地 又看作产地 重新排码 形成一个扩大的运输问题 2 各地之间的运费在原问题运费表的基础上进行扩展 从一地运往自身的单位运费记为0 不存在的运输路径记为M 或一个足够大的正数 3 由于经过转运点的物资量既是该点作为产地的产量 又是该点作为销地的销量 但事先又无法获得该运量的确切值 因此通常将调运总量作为该数值的上限 对于产地和销地也做类似处理 通过上述处理 就可以将转运问题转化为产销平衡的运输问题 进而可以采用表上作业法进行求解 具体的操作步骤如下 1 由于问题中所有产地 中间转运站 销地都可以看作产地 又可看作销地 因此把整个问题当作有11个产地和11个销地的扩大的运输问题 2 对扩大的运输问题建立单位运价表 方法将表3 40中不可能的运输方案的运价用任意大的正数M代替 3 所有中间转运站的产量等于销量 由于运费最少时不可能出现一批物资来回倒运的现象 所以每个转运站的转运数不超过20吨 可以规定T1 T2 T3 T4的产量和销量均为20吨 由于实际的转运量 可以在每个约束条件中增加一个松弛变量xii xii相当于一个虚构的转运站 意义就是自己运给自己 20 xii 就是每个转运站的实际转运量 xii的对应运价cii 0 4 扩大的运输问题中原来的产地与销地因为也有转运站的作用 所以同样在原来产量与销量的数字上加20吨 即三个厂每天糖果产量改成27 24 29吨 销量均为20吨 四个销售点的每天销量改为23 26 25 26吨 产量均为20吨 同时引进xii作为松弛变量 下面就写出扩大得运输问题的产销平衡表与单位运价表 见表3 这是一个产销平衡的运输问题 所以可以