[理学]运输问题.ppt

一、初始方案(基本可行解)的确定 初始方案(基本可行解)的确定的方法 1.西北角法 2.最小元素法 3.Vogel法 用表上作业法求给出的运输问题的初始解 例3 甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输距离见下表，求使总运输量最少的调运方案。 例3 有关信息表 例3 数学模型 3.伏格尔(Vogel)法 Vogel法步骤： 一、分别计算运价表的每行、每列最小元素与次小元素的差并填入该表的最右列和最下行 二、在行或列差额中选出最大者，选择这所在的行或列中单位运价最小格开始安排 三、划去对应的行或列的元素，再分别计算运价表的每行、每列两最小元素（最小、次小）差并填入该表的最右列和最下行，且不断重复上述步骤，直至给出调运方案。 Vogel法求出的初始解即为近似最优解 应用举例 某百货公司去外地采购A，B，C，D四种规格的服装，数量分别为A--1500套，B--2000套，C--3000套，D--3500套。有三个城市可以供应上述规格服装，供应数量分别为Ⅰ--2500套，Ⅱ--2500套，Ⅲ--5000套。由于这些城市的服装质量、运价的销售情况不同，预计售出后的利润也不同，见下表，请帮该百货公司确定一个预期赢利最大的采购方案。 二、最优性检验 最优性检验方法 1.闭回路法 2.位势法 3 . 判断是否达到最优 若存在某些检验数小于0，则说明调整后运价将减少。（不是最优解） 若存在某些检验数等于0，则说明调整后运价将不发生改变。（存大多个最优解） 若所有检验数大于0，说明调整后运价将增加。（唯一最优解） 当全部空格处检验数大于等于0，则说明方案已达最优。 2.4 运输问题中的悖论 悖论 增加收发（产销）量，总运价反而减少 1971年Charnes与Klingman首次提出且研究了分配模型中的“多反而少”悖论。 1982年我国周奇给出了运输问题中的这种现象。 典型例子 2.3 、产销不平衡的运输问题及其求解方法 1.数学模型： 产大于销 销大于产 然后再用产销平衡的运输问题的解法进行解之。 1.解法思路： 将不平衡运输问题转化为平衡运输问题。即当 时，考虑在平衡表中增加一虚拟列，表示增加一个销货点 (j=n+1)如仓库，其销货量为 ，且各运价 Cin+1=0；当 时，考虑在平衡表中增加一虚拟 行，表示增加一个新产地，且各运价Cm+1j=0。 例 下表是一个运输问题的单位运价表。 60 40 30 20 销量（万吨） 70 8 1 8 7 A3 70 12 3 11 2 A2 50 6 5 3 10 A1 产量（万吨） B4 B3 B2 B1 比较总产量和总销量可知，这是一个非平衡运输问题（属于产大于销的情况），为化为平衡运输问题，需虚设一个销点B5，其运价为0，其销量为40。 B5 0 0 0 40 案例1 某企业和用户签订了设备交货合同，已知该企业各季度的生产能力、每台设备的生产成本和每季度末的交货量如下表，若生产出的设备当季度不交货，每台设备每季度需支付保管维护费0.1万元,试问在遵守合同的条件下,企业如何安排生产计划,才能使年消耗费用最低? 12.5 20 20 4 11.5 25 30 3 11.0 20 35 2 12.0 15 25 1 每台设备生产成本(万元) 交货量(台) 工厂生产能力(台) 季度 30 20 25 20 15 交货量 20 0 12.5 M M M 4 30 0 11.6 11.5 M M 3 35 0 11.2 11.1 11.0 M 2 25 0 12.3 12.2 12.1 12.0 1 生产量 5(虚拟列) 4 3 2 1 交货季 生产季 转化为平衡运输问题的运输表 ? ? ? ? ? ? ? ? ? í ì = = 3 = + = + = + = + + = + + ; 3 , 2 , 1 ; 2 , 1 , 0 200 150 100 250 200 . . 23 13 22 12 21 11 23 22 21 13 12 11 j i x x x x x x x x x x x x x t s + + + + + = 75 65 80 100 70 90 min 23 22 21 13 12 11 x x x x x x Z ij 需求约束 日产量约束 450