运输问题和指派问题.ppt

第四章运输问题 物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地 sources 如工厂 仓库 运输到一系列终点地 destinations 如仓库 顾客 你怎么去分析这类问题呢 实例 某公司从两个产地A1 A2将物品运往三个销地B1 B2 B3 各产地的产量 各销地的销量及各产地运往各销地的单位运费如表所示 如何调运 使总运费最少 单位运费 x11x12x13 x21x22x23 运输问题的说明 需求假设 每一个出发地都有一个固定的供应量 所有的供应量都必须配送到目的地 与之相类似 每一个目的地都有一个固定的需求量 整个需求量都必须由出发地满足 成本假设 从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系 因此这个成本就等于配送的单位成本乘以所配送的数量 整数解性质 只要它的供应量和需求量都是整数 任何运输问题必然有所有决策变量都是整数的最优解 因此 没有必要加上所有变量都是整数的约束条件 该运输问题的线性模型 minz 6x11 4x12 6x13 6x21 5x22 5x23s t x11 x12 x13 200 x21 x22 x23 300 x11 x21 150 x12 x22 150 x13 x23 200 xij 0 推广为一般 平衡 运输问题的线性规划模型 Minz S t 运输问题属于线性规划问题 其变量个数为mn个 约束个数为 m n 个 当m n比较大时 若用单纯形法求解 计算工作是就相当大 运输问题是类特殊的线性规划问题 其特殊性体现在系数矩阵上 运输问题的系数矩阵A是0和1组成 0的个数远远大于1的个数 的稀疏阵 且r A m n 1 定理1 运输问题的任何一组基变量都由m n 1个变量组成定理2 运输问题中m n 1个变量构成基的充分必要条件是它不包含闭回路 平衡 运输问题的求解 表上作业法 找一个初始基可行解 方法 最小元素法 Vogel近似法 VAM 检验 若所有的检验数都小于零 最优解已得 否则继续下一步 方法 位势检验法调整 实质是换基 得到一个新的基可行解 重复第二步 方法 闭回路法 举例 150 200 50 100 第一步 找初始方案 第二步 位势检验 以上所有检验数 0 故初始方案已是最优方案不用进行第三步的调整 不平衡运输问题 当总供应量 总需求量时 称为不平衡运输问题不平衡运输问题的求解 先化为平衡的运输问题 再用表上作业法供 求 虚设一个收点 收量为供求之差 各发点到该虚收点的单位运价为0供 求 虚设一个发点 发量为供求之差 该虚发点到各收点的单位运价为0 运输问题的计算机求解 用线性规划程序求解 输出部分信息多 但变量和约束输入较麻烦 用运输问题程序求解 只需输入产地个数 销地个数 各产地的产量 各销地的销量 各产地到各销地的单位运价 前例输入后 得到的最优运输方案为 运输问题的应用 一 配送问题东风电机公司接到上海一家商场 B1 青岛一家商场 B2 西安一家商场 B3 各一份订单 要求下月供应电机 B1的需求量为100台 B2的需求量为80台 而B3要求供应120台 该公司在北京和武汉设有两个仓库 A1 A2 预计A1 A2下月的库存量分别为200台和150台 已知每个仓库到每家商场运送1台电机的费用如表所示 问该公司应如何调运电机 才能既满足用户的需要又使总的运费最少 二 短缺资源的分配问题 石家庄北方研究院有三个区 一区 二区 三区 每年分别需要生活用煤和取暖用煤3000 1000 2000吨 由河北 山西两处煤矿负责供应 这两处的煤矿的价格相同 煤的质量也基本相同 山西和河北两处煤矿能供应北方研究院的数量分别为4000 1500吨 由煤矿至北方研究院的单位运价 百元 吨 如表 由于供应不足 经院研究平衡决定一区供应量可减少0 200吨 二区需要量应全部满足 三区供应量不少于1700吨 请提交一个总运费最低的调运方案 三 生产与存贮问题 某厂按合同规定须于当年每个季度末分别提供10 15 25 20台同一规格的柴油机 已知该厂各季度的生产能力及生产每台柴油机的成本如表所示 如果生产出来的柴油机当季不交货 每台每积压一个季度需储存 维护等费用0 15万元 要求在完成合同的情况下 做出使该厂全年生产费用最小的决策 四 转运问题 广州 大连 600 400 产地 4 1 3 3 2 中转站 供应量 1 2 3 4 5 6 7 8 P G重新设计制造和配送体系 90 S成百上千个供应商50多个产品类别超过60个的工厂15个配送中心超过1000个的顾客群体 为每个单独的产品种类设计并求解运输问题对于针对还在运行的工厂的每一个选择 为每一个产品种类解决相应的运输问题体现了从这些工厂运送产品到配送中心或顾客区所需要的配送成本是多少 在找出最好的新生产和配送系统的过程之中解决了许多这样的运输问题北美工厂数减少了20 并且公司每年节省了2亿美元的税前费用 运输问题的扩展 指派问题 现实生活之中 我们也经常遇到指派人员做某项工作的情况 指派问题的许多应用都用来帮助管理人员解决如何为一项将要开展进行的工作指派人员的问题 其他的一些应用如为一项任务指派机器 设备或者是工厂 还有哪些这样的问题呢 实例 有4个工人 要指派他们分别完成4项工作 每人做各项工作所消耗的时间如下表 要求1人只做1件事 如何指派使总的消耗时间最少 模型 用0 1变量表示 是非 决策 1 第i人去做第j件事xij 0 第i人不做第j件事minz 15x11 18x12 21x13 24x14 19x21 23x22 22x23 18x24 26x31 17x32 16x33 19x34 19x41 21x42 23x43 17x44s t x11 x12 x13 x14 1 A1只能干一件事 x21 x22 x23 x24 1 A2只能干一件事 x31 x32 x33 x34 1 A3只能干一件事 x41 x42 x43 x44 1 A4只能干一件事 x11 x21 x31 x41 1 B1只能由一个人干 x12 x22 x32 x42 1 B2只能由一个人干 x13 x23 x33 x43 1 B3只能由一个人干 x14 x24 x34 x44 1 B4只能由一个人干 xij 0或1 指派问题的一般描述 有n个人A1 A2 An 要分派去做n件事B1 B2 Bn 要求每一件事都必须有一个人去做 而且不同的事由不同的人去做 已知每个人Ai做每件事Bj的效率 如劳动工时或成本 或创造的价值等 为Cij 应如何进行指派 哪个人做哪件事 才能使工作效益最好 如工时最少 或成本最低 或创造的价值最大 指派问题既可以说是运输问题的特殊情形 也可以说是整数规划的特殊情形 指派问题的一般模型 min max z S t 指派问题的变形 人的数量 任务的数量人的数量 任务的数量 一般模型中前面的约束 xij 1改为 xij 1 由于某种原因 不能指派某个人做某件事如A1由于技能不达标 不能做B3 只须在一般模型中去掉x13变量 多重指派 一个人可以被分派做几件事 则一般模型中前面的约束 xij 1改为 xij ai ai为第i人最多能承担的任务数 平衡指派问题的求解 匈牙利法 适用 min 第一步 使指派问题的效率矩阵经变换 在各行各列中都出现0从效率矩阵的每行减去该行的最小元素没有0的各列再减去该列的最小元素第二步 按下述规则圈0划线 若划掉所有0元素的直线个数 n 则计算停止 否则 转第三步找出矩阵中含0最少的一行 或一列 从该行 或该列 中圈出一个0 再通过此0作一竖 横 线划去该列 或行 对余下各行各列重复进行 但已圈0的行或列不再圈第三步 在未划去的各数中找出最小值 作为调整量d调整 未划去的各数减d 两线交叉处的各数加d 其余不变 得一新矩阵 对此新矩阵重复第二步 不平衡指派问题的求解 先化为平衡的指派问题 再用匈牙利法 max 型的指派问题 先转化为 min 型指派问题 再用匈牙利法取一个比效率矩阵中所有系数都大的常数减去该效率矩阵得一新矩阵 则解以新矩阵为效率矩阵的最小化问题就等于解原效率矩阵的最大化问题 指派问题的计算机求解 用整数规划程序求解 输入 目标函数 约束条件直接用指派问题程序求解 输入