运筹学运输问题

第四章运输问题 运输问题的表示网络图 线性规划模型 运输表初始基础可行解西北角法 最小元素法非基变量的检验数闭回路法 对偶变量法确定进基变量 调整运量 确定离基变量 运输问题的提出 运输问题的直接背景是单一品种的物质的运输调度问题 其典型情况是 设某物品有m个产地A1 A2 Am 各产地的产量分别为a1 a2 am n个销地B1 B2 Bn 各销地的销量分别为b1 b2 bn 假定从产地Ai i 1 2 m 向销地Bj j 1 2 n 运输单位物质的运价为cij 问怎样调运这些物品才能使得总运费最小 运输问题的表示 网络图 产地 销地 若则称该问题为平衡运输问题 否则称为非平衡运输问题 运输问题的表示 表格表示 这个表常称为运输表 运输问题的数学模型 平衡问题的数学模型为 各产地运出的物资数量等于其产量 各销地接受的物资数量等于其销量 其中 运输问题数学模型的特点 运输问题一定存在最优解实际上是平衡运输问题的一个可行解 此外由于目标函数有下界 因此平衡运输问题存在最优解 运输问题系数矩阵的特点 m n 上述矩阵的列向量具有形式 第i个 第 m j 个 因此运输问题约束条件系数矩阵的元素只能是0或1 对应变量xij列除了第i个与第 m j 个分量为1外 其它分量均为零 此外产销平衡运输问题的数学模型还具有特点 所有约束条件都是等式前m个约束条件的和等于后n个约束条件的和 可以证明尽管有m n个约束条件 但独立的约束条件只有m n 1个 运输问题的例子 表格表示 运输问题的例子 线性规划模型 供应地约束 需求地约束 运输问题的解 运输问题的解可以表示为X xij 它表示一个运输方案 其中xij表示从产地Ai到销地Bj运送的物质数量在用运输表表示运输问题时 也常将xij取的值填入对应的格子表示一个解 但是对基可行解 通常仅将基变量取的值填入相应的格中 称之为数字格 而对应着非基变量的格子 则不填数字 称之为空格 注 在一个基可行解中 所有mn个变量 格子 中 只有m n 1个基变量 数字格 求解运输问题的表上作业法 求初始基可行解 初始调运方案 西北角法最小元素法沃格尔法 初始基可行解 西北角法 8 8 6 4 8 14 初始基可行解 最小元素法 8 2 10 14 8 6 沃格尔 Vogel 法 14 8 8 12 2 4 检验数的计算 两种方法 闭回路法和对偶变量法闭回路法的原理 非基变量的检验数等于非基变量增加一个单位时 目标函数的改变量 检验数的计算 闭回路法 1 8 2 10 14 8 6 1 检验数的计算 闭回路法 2 8 2 10 14 8 6 1 2 检验数的计算 闭回路法 3 8 2 10 14 8 6 1 2 1 检验数的计算 闭回路法 4 8 2 10 14 8 6 1 2 1 1 检验数的计算 闭回路法 5 8 2 10 14 8 6 1 2 1 1 10 检验数的计算 闭回路法 6 8 2 10 14 8 6 1 2 1 1 10 12 检验数的计算 对偶变量法 对偶变量法也称为位势法 它是利用运输问题的对偶问题求检验数 设运输问题的对偶变量矩阵为则对偶问题为 利用单纯形法的矩阵表示可知 变量xij的检验数可以表示为 另一方面 对于 m n 1 个基变量而言 检验数等于零 故可以得到包含 m n 个变量的 m n 1 个方程 由该方程组求出对偶变量后即可计算出所有的检验数 检验数的计算 对偶变量法 8 2 10 14 8 6 u1 0 v3 4 v4 11 u2 1 u3 5 v1 3 v2 10 1 2 1 1 10 12 解的改进 8 2 10 14 8 6 1 解的改进 8 12 14 8 4 2 解的改进 8 12 14 8 4 2 u1 0 v3 4 v4 11 u2 2 u3 5 v1 4 v2 10 最优解 最优调运方案 8 12 14 8 4 2 最小运费 表上作业法的几个问题 换入变量的确定退化 两种情况 无穷多个最优解的判别 产销不平衡的运输问题 解决的基本思路 将其转化为产销平衡的运输问题求解 产大于销的运输问题 这时有 数学模型为 处理的办法为增加一个假想的销地Bn 1 其销量为 各个产地运送物质到假想销地的单位运价为零 即ci n 1 0 假想的销地 这时有 数学模型为 销大于产的运输问题 处理的办法为增加一个假想的产地Am 1 其产量为 假想产地运送物质到各个销地的单位运价为零 即c m 1 1 0 假想的产地 表上作业法的计算步骤 表上作业法计算中的问题 1 若运输问题的某一基可行解有多个非基变量的检验数为负 在继续迭代时 取它们中任一变量为换入变量均可使目标函数值得到改善 但通常取 ij 0中最小者对应的变量为换入变量 2 无穷多最优解产销平衡的运输问题必定存最优解 如果非基变量的 ij 0 则该问题有无穷多最优解 退化解 表格中一般要有 m n 1 个数字格 但有时在分配运量时则需要同时划去一行和一列 这时需要补一个0 以保证有 m n 1 个数字格作为基变量 一般可在划去的行和列的任意空格处加一个0即可 利用进基变量的闭回路对解进行调整时 标有负号的最小运量 超过2个最小值 作为调整量 选择任意一个最小运量对应的基变量作为出基变量 并打上 以示作为非基变量 12 4 11 4 8 3 10 2 9 5 11 6 0 2 9 2 1 12 8 12 4 2 8 14 如下例中 11检验数是0 经过调整 可得到另一个最优解 产销不平衡的运输问题 运输问题 运输问题的应用 例 有三个供应地要将物资运往五个需求地区 各产地的产量和个地区的需求以及运费情况如下表 要求 其中B2地区的115个单位必须满足 问 应如何运输总运费最小 运输问题 运输问题的应用 解 由于产量小于需求 因此虚设以产地A4 其产量为供需的差额20 与此项有关的费用一般设为0 又因为B1地区的需求要保证 所以应该迫使虚设产地运输到该地区的运费成本极高 从而在优化过程中实现0运量 因此取该项费用为一个充分大的数M 由此可以建立如下的产销平衡运输费用表 运输问题 运输问题的应用 运输问题 思考题1 某部有B1 B2 B3三个作战单位 每年分别需要某军用品3500吨 1100吨 2400吨 这些用品都要由A1 A2两兵工厂负责供应 两兵工厂生产的军用品质量均相同 假设A1 A2的供应能力分别为1500吨 4000吨 运价 元 吨 如下表所示 由于需求大于供给 经院研究决定B1区供应量可减少0 900吨 B2区必须满足需求量 B3区供应量不少于1600吨 试求总费用为最低的调运方案 运输问题 思考题1 解 解根据题意以及给定的数据可知 这是一个产销不平衡的运输问题 需求量大于生产量 由于B1区供应量可减少0 900吨 B2区必须满足需求量 B3区供应量不少于1600吨 可以把B1区和B3区分别设为两个区 一个为必须满足需求量的区域 另一个为可以调整供应量的区域 这样 原问题化为五个需求区域B1 B1 B2 B3 B3 的问题 同时增加一个虚设的产地A3 在运输费方面 取M代表一个很大的正数 使必须满足需求量区域的相应变量x31 x33 x34运费的取值为M 可调整需求量区域的相应变量x32 x35运费的取值为0 作出产销平衡的运价表 运输问题 思考题2 已知某运输问题的产销需求及单位运价如下表所示 求解运输费用最少的方案和总运费 运输问题 思考题2 解 因产销不平衡 补充一虚拟销售地B4如下 采用最小元素法可以得到初始可行解如下 运输问题 思考题2 解 计算检验数 位势法 1 0 8 6 2 5 5 0 10 8 5 4 3 1 0 8 6 2 5 8 0 10 8 5 7 3 最优解 运输问题 思考题2 已知某运输问题的产销需求及单位运价如下表所示 求解运输费用最少的方案和总运费 A1 B3 15 A2 B1 18 A3 B2 12 B3 1 B4 4 总费用93 但方案不