运输问题进一步探讨.pptVIP

运输问题 第三节 运输问题的 进一步讨论 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题的表上作业算法 表上作业法步骤: 初始方案?最优性检验?改进方案 一、初始方案的确定 1.最小元素法 2.Vogel法 二、最优性检验 1.闭回路法 2.位势法 三、方案改进方法 在闭回路内改进。 表上作业法适合于产销平衡的运输问题 第三节 运输问题的 进一步讨论 上节给出产销平衡运输问题的表上作业法，本节以下问题进一步讨论： 产销不平衡的运输问题 运输问题 表上作业法是以产销平衡为前提的，即当实际问题产销不平衡时，需要转化为产销平衡的运输问题，具体来说有两种情况： （1）产大于销，即 此时增加一个假想的销地n+1，该销地的销量为 ，而各产地到假想销地的单位运价定为0，就转化成产销平衡的运输问题。 （2）销大于产，即 此时增加一个假想的产地m+1，该产地的产量为 ，而假想产地到各销地的单位运价定为0，就转化成产销平衡的运输问题。 产销不平衡的运输问题 运输问题 一、产销不平衡的运输问题 （Ⅰ）若总产量大于总销量，即 令假象销地的销量为： 运输问题 决策变量 表示由 到 的物品数量。 销地 产地 销量 产量 注意：用最小元素法求初始调运方案时，最后一列的零运价最后考虑。 运输问题 原产大于销平衡问题的数学模型 运输问题 修改后产大于销平衡问题的数学模型 增加一个销地 产大于销 销地 产地 B1 B2 B3 产量 A1 5 9 2 15 A2 3 1 7 18 A3 6 2 8 17 销量 18 12 16 销地 产地 B1 B2 B3 产量 A1 5 9 2 15 A2 3 1 7 18 A3 6 2 8 17 销量 18 12 16 50-46 B4 0 0 0 4 50 46 50 50 初始基可行解（最小元素法） 销地 产地 B1 B2 B3 B4 产量 A1 5 9 2 0 15 A2 3 1 7 0 18 A3 6 2 8 0 17 销量 18 12 16 4 12 15 6 12 1 4 初始基可行解：x13=15,x21=6,x22=12,x31=12,x33=1,x34=4，Z=140 6 1 12 5 4 运输问题 （Ⅱ）若总产量小于总销量，即 令假象产地的销量为： 仿照上述类似处理。 增加一个产地 产小于销 销地 产地 B1 B2 B3 产量 A1 4 1 2 10 A2 3 4 3 12 销量 8 10 5 销地 产地 B1 B2 B3 产量 A1 4 1 2 10 A2 3 4 3 12 A3 销量 8 10 5 23-22 0 0 0 1 22 23 23 23 产销不平衡的运输问题总结 供大于求 供不应求 增加虚拟销地 增加虚拟产地 产销平衡的运输问题 对应的运价（或运距） ？ 转化 运输问题 求解线性规划问题 可转化为运输问题来求解 运输问题 计算机求解运输问题 销地 产地 B1 B2 B3 B4 供应量 A1 4 8 6 10 8 A2 10 7 3 6 12 A3 12 5 1 9 10 需求量 6 8 7 4 30 25 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题