运筹学_运输问题.ppt

2 7运输问题 一 运输问题及其数学模型线性规划模型 运输表二 初始基本可行解西北角法 最小元素法三 非基变量的检验数对偶变量法四 运输表迭代 典型背景 单一物资运输调度问题设某种物品有 m个产地 产量 n个销地 销量 从产地到销地的单位运价是 求总运费最小的调度方案 一 运输问题及其数学模型 产销平衡问题 总产量 总销量 产销不平衡问题 总产量 总销量 典型背景 单一物资运输调度问题设某种物品有 m个产地 产量 n个销地 销量 从产地到销地的单位运价是 求总运费最小的调度方案 产销平衡问题的数学模型 产能约束 需求约束 运输问题数学模型的特点 1 运输问题存在有限最优解2 运输问题约束条件的系数矩阵结构约束条件系数矩阵每一列只有两个1 其余为0 产销平衡问题约束条件均为等式 且产量之和 销量之和 约束条件的独立方程最多有m n 1个 即 i m j 其中 运输问题的对偶 对偶变量与原问题检验数的关系 对产销平衡运输问题 若用分别表示前m个约束等式相应的对偶变量 用分别表示后n个约束等式相应的对偶变量 即对偶变量为 平衡运输问题的对偶问题可写为 线性规划问题变量的检验数为 对偶变量与原问题检验数的关系 变量的检验数为 设运输问题的一个基可行解的变量为 由于基变量的检验数为零 故有 对偶变量与原问题检验数的关系 方程组含有m n 1个方程 m n个变量 可证明方程组有解 且不唯一 求出方程组的解 称为位势 则变量的检验数为 对偶变量与原问题检验数的关系 运输问题的求解 根据运输问题的数学模型 及其约束方程组的系数矩阵结构 我们可以构造比单纯形法更为简便的求解运输问题的方法 运输表迭代方法 运输表迭代是应用单纯形法求解运输问题时得到的一种特殊方法 单纯形法过程与运输表迭代的过程 1 找出初始基可行解 2 求各非基变量的检验数 3 判断是否最优解 换基 4 确定换入变量和换出变量找出新的基可行解 5 重复 2 4 直至求出最优解 停止 A2 A3 B2 A1 B3 B4 B1 实例分析运输问题的运输表迭代 确定初始基本可行解 计算非基变量检验数 换基迭代 s2 27 s3 19 d1 22 d2 13 d3 12 d4 13 s1 14 供应量 供应地 运价 需求量 需求地 6 7 5 3 8 4 2 7 5 9 10 6 线性规划模型 供应地约束 需求地约束 运输表 二 初始基本可行解1 西北角法 优先满足左上角运输量 350 8 13 13 14 6 6 二 初始基础可行解2 最小元素法 优先考虑运价最低的运输量 2 最小元素法 2 最小元素法 2 最小元素法 2 最小元素法 2 最小元素法 232 三 检验数的计算对偶变量法 先确定基变量的位势 再据此计算非基变量检验数 三 检验数的计算对偶变量法 先确定基变量的位势 再据此计算非基变量检验数 三 检验数的计算对偶变量法 三 检验数的计算对偶变量法 三 检验数的计算对偶变量法 四 运输表迭代确定包含最大检验数所属变量 即将进基 的闭回路 找出回路中偶数顶点最小运输量 改进运输方案 四 运输表迭代确定包含最大检验数所属变量 即将进基 的闭回路 找出回路中偶数顶点最小运输量 改进运输方案 四 运输表迭代确定包含最大检验数所属变量 即将进基 的闭回路 找出回路中偶数顶点最小运输量 改进运输方案 四 运输表迭代确定包含最大检验数所属变量 即将进基 的闭回路 找出回路中偶数顶点最小运输量 改进运输方案 几点说明 1 当大于零的检验数超过两个 选择最大者对应的变量进基 2 在最优解的运输表中 若有检验数 0 则该运输问题有无穷多最优解 3 迭代过程中 若某一格运输量增加时 其同行和同列基变量均出现零 则出现退化 为保证m n 1个非空格 需保留一个基变量 取值为0 例 求有6个发点和8个收点的最小费用运输问题 产销单位运价如下表 分析 先建立该运输问题的数学模型 xij表示从第i个发点到第j个收点的货物运输量 记cij表示从第i个发点到第j个收点的单位货物运价 ai表示第i个发点的最大供货量 dj表示第j个收点的需求量 总运输费用最少 决策变量 目标函数 约束条件 各发点运出货物量不超过其产量 各收点收到货物量等于其销量 决策变量非负限制 各产 销点的产量和销量约束 决策变量限制 线性规划模型 model 6发点8收点运输问题 sets 集合段 wh w1 w6 ai vd v1 v8 dj links wh vd C X endsetsmin sum links C X 目标函数 for vd J sum wh I X I J dj J 需求约束 for wh I sum vd J X I J ai I 产量约束 data 数据段 ai 605551434152 dj 3537223241324338 C 626742954953858252197433767392712395726555228143 enddataend 集合段 Sets endsets 数据段 data enddata 目标函数与约束条件段 Globaloptimalsolutionfoundatiteration 20Objectivevalue 664 0000VariableValueReducedCostX W1 V1 0 0000005 000000X W1 V2 19 000000 000000 X W6 V7 3 0000000 000000X W6 V8 0 0000003 000000 20次迭代后得到全局最优解 总费用最少为664 最优运输方案 最优解行数太多 略 运输问题的进一步讨论 前面讨论了产销平衡的运输问题 可以采用表上作业法求解 我们还可以讨论更多类型的运输问题 如 2 有转运的运输问题 1 产销不平衡的运输问题 1 产销不平衡的运输问题 若总产量大于总销量 即 假设有一个虚拟销地 其单位运费为0 它的销量为 原产大于销运输问题的数学模型 修改后产销平衡问题的数学模型 若总产量小于总销量 即 假设有一个虚拟产地 其单位运费为0 它的产量为 1 产销不平衡的运输问题 仿照上述类似处理 2 有转运的运输问题 中间转运站 产地 销地 中转站 建模思路 从发送及接受角度考虑 最坏计算复杂性的LP实例 可行域有2n个顶点 如果从初始顶点