第四章-运输问题

运筹学 Operation sResearch 北京理工大学珠海学院吴浩然 运输问题模型 第四章运输问题 1 表上作业法 2 运输问题的应用 3 1 运输问题模型 问题提出 某企业从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往各销地每件物品的运费如下表所示 请问 应如何调运可使总运输费用最小 产地 销地 元素等于0或1 每列只有两个元素为1 其余为0 对于每个变量 前m个约束方程只出现一次 后n个约束方程也只出现一次 运输问题约束条件系数矩阵的特点 是否最优解 寻找新的基本可行解 2 表上作业法 步骤 西北角法 从x11开始分配 从西北向东南方向逐个分配 最小元素法 采用最小费用优先分配的原则 步骤1 初始基本可行解的确定 检验数的公式为 其中分别称为行位势 列位势 结论 1 基变量所对应的检验数 步骤2 最优解的检验 位势法 2 若非基变量所对应的检验数当前解即为最优解 闭回路 从进基变量的空格出发 沿水平或垂直方向前进 每碰到数字格转90o 有些情况也可以不改变方向 继续前进 直到回到出发的空格为止 由此形成的封闭的折线称为闭回路 步骤3 寻找新的基本可行解 闭回路法 某企业从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往各销地每件物品的运费如下表所示 请问 应如何调运可使总运输费用最小 产地 销地 某公司有从三个产地A1 A2 A3 将物品运送到四个销地B1 B2 B3 B4 各产地的产量 各销地的销量 各产地到各销地的单位运价如下表所示 请问 应如何调运产品 使得总运费最少 课堂练习 从每一个非基变量的空格出发 构造闭回路 若非基变量所对应的检验数 则当前解即为最优解 其中 闭回路奇数顶点运费之和 闭回路偶数顶点运费之和 闭回路法检验解的最优性 某公司有从三个产地A1 A2 A3 将物品运送到四个销地B1 B2 B3 B4 各产地的产量 各销地的销量 各产地到各销地的单位运价如下表所示 请用最小元素法确定初始基本可行解 并用闭回路法检验初始基本可行解是否为最优解 课堂练习 总产量 总销量 2 表上作业法 产销不平衡的运输问题 某公司有从三个产地A1 A2 A3 将物品运送到三个销地B1 B2 B3 各产地的产量 各销地的销量 各产地到各销地的单位运价如下表所示 请问 应如何调运产品 使得总运费最少 某公司有从三个产地A1 A2 A3 将物品运送到四个销地B1 B2 B3 B4 各产地的产量 各销地的销量 各产地到各销地的单位运价如下表所示 请问 应如何调运产品 使得总运费最少 课堂练习 总销量 总产量 某公司有从三个产地A1 A2 A3 将物品运送到五个销地B1 B2 B3 B4 B5 各产地的产量 各销地的销量 各产地到各销地的单位运价如下表所示 请问 应如何调运产品 使得总运费最少 1 判别下表中的调运方案能否作为表上作业法的初始解 2 请用最小元素法确定下述运输问题的初始基本可行解 3 某公司有从两个产地A1 A2 将物品运送到三个销地B1 B2 B3 各产地的产量 各销地的销量 各产地到各销地的单位运价如下表所示 其中 B3的销量必须得到满足 请问 应如何调运产品 使得总运费最少 4 某公司有从三个产地A1 A2 A3 将物品运送到三个销地B1 B2 B3 各