典型问题 运输问题运输问题 Transportation Problem 东北大学 系统工程研究所东北大学 系统工程研究所 2014 09 基本运输问题 运输问题最早是由运输问题最早是由Hitchcock在在1941年提出 年提出 此后 人们对这一问题的研究给予了极大的关注 并对各类运输问题进行了研究 此后 人们对这一问题的研究给予了极大的关注 并对各类运输问题进行了研究 基本的运输问题是基本的运输问题是 线性单目标 线性单目标 运输问题 运输问题 从不同的供给从不同的供给起点起点或或来源来源向不同的向不同的终点终点运送运送同一种物 品 同一种物 品 每个终点需要特定数量的物品 每个终点需要特定数量的物品 问题是如何分配在每个起点的供给 以便在满足每个 终点需求的条件下 优化某个目标 问题是如何分配在每个起点的供给 以便在满足每个 终点需求的条件下 优化某个目标 常用的目标函数有 运输费用最小 加权距离最小或 利润最大 等 常用的目标函数有 运输费用最小 加权距离最小或 利润最大 等 例如 例如 从工厂向仓库运送产品从工厂向仓库运送产品 运输问题的目标就是要找到成本最小的运输模式运输问题的目标就是要找到成本最小的运输模式 2典型优化问题的模型与算法 R03 基本运输问题的网络模型 运输问题可以采用如下网络模型进行描述 运输问题可以采用如下网络模型进行描述 这样的图由起始节点和终止节点及连接他们的边构成 这样的图由起始节点和终止节点及连接他们的边构成 图中一个集合中的所有边直接与另一个集合相连 构 成 图中一个集合中的所有边直接与另一个集合相连 构 成完全二分图完全二分图 complete bipartite graph S1 D1 Dn DjSi Sm plants warehouses supply demand a1 ai am b1 bj bn 3典型优化问题的模型与算法 R03 基本运输问题的模型描述 给定给定 m 个起点和个起点和 n 个终点个终点 运输问题可描述为 运输问题可描述为 jix njbx miax xcxz ij m i jij n j iij m i n j ijij 0 2 1 2 1 t s min 1 1 11 where xij 从起点从起点 i 到终点到终点 j 的物品运输量 的物品运输量 cij 从起点从起点 i 到终点到终点 j 的单位运输费用 的单位运输费用 ai 起点起点 i 的供给量 的供给量 bj 终点终点 j 的需求量 的需求量 4典型优化问题的模型与算法 R03 运输问题的分类 按目标的类型划分按目标的类型划分 线性问题或非线性问题线性问题或非线性问题 单目标问题或多目标问题 单目标问题或多目标问题 按约束的类型划分按约束的类型划分 二维二维 planar 问题或三维问题或三维 solid 问题问题 平衡问题或非平衡问题 平衡问题或非平衡问题 各类运输问题各类运输问题 线性运输问题线性运输问题 双准则线性 双准则三维运输问题双准则线性 双准则三维运输问题 固定费用运输问题固定费用运输问题 容量限制的运输问题容量限制的运输问题 广义运输问题广义运输问题 多目标运输问题多目标运输问题 模糊多准则三维运输问题模糊多准则三维运输问题 带模糊系数的双目标运输问题带模糊系数的双目标运输问题 两阶段运输问题两阶段运输问题 5典型优化问题的模型与算法 R03 特点 是一个基本的是一个基本的网络问题网络问题 问题的问题的约束具有特殊的结构约束具有特殊的结构 线性或非线性问题线性或非线性问题 单目标或多目标问题单目标或多目标问题 6典型优化问题的模型与算法 R03 应用 工厂到仓库的产品运输问题工厂到仓库的产品运输问题 仓库仓库 零售商供应链问题零售商供应链问题 物品从仓库运出物品从仓库运出 到达客户到达客户 以满足客户的 需求 如何分配运输量能使运输成本最低 以满足客户的 需求 如何分配运输量能使运输成本最低 盐业配送问题盐业配送问题 要将食用盐从食盐供应站 配送到下属工 厂或者用盐单位 如何配送能使运输费用 最少 要将食用盐从食盐供应站 配送到下属工 厂或者用盐单位 如何配送能使运输费用 最少 应急物资的紧急调运问题应急物资的紧急调运问题 当发生自然灾害或一些突发事件时 例如 地震 洪水等 经常会出现需要从多个 供应点向多个需求点运输救援物资的问题 这时的目标通常考虑的是运输时间最短 当发生自然灾害或一些突发事件时 例如 地震 洪水等 经常会出现需要从多个 供应点向多个需求点运输救援物资的问题 这时的目标通常考虑的是运输时间最短 在军事上的应用就是军械物资调运问题 在军事上的应用就是军械物资调运问题 7典型优化问题的模型与算法 R03 S1 D1 Dn DjSi Sm 起点终点起点终点 应用 多热源供热管网优化问题多热源供热管网优化问题 例如一个企业有多个热源 热水或蒸汽热 同时 还有一些需要热能的车间或工厂 问题是如何调配 热源 既能满足要求 又能使运费最小 例如一个企业有多个热源 热水或蒸汽热 同时 还有一些需要热能的车间或工厂 问题是如何调配 热源 既能满足要求 又能使运费最小 土地平整中的土方调配问题土地平整中的土方调配问题 从不同的挖方区向不同的填方区运送土方从不同的挖方区向不同的填方区运送土方 每个填方 区需要特定数量的土方 问题是如何分配每个挖方 区的土方供给 每个填方 区需要特定数量的土方 问题是如何分配每个挖方 区的土方供给 以便在满足每个填方区需求的条件下以便在满足每个填方区需求的条件下 使得全部费用最小 使得全部费用最小 公路工程 房屋建设等 都涉及这个问题 公路工程 房屋建设等 都涉及这个问题 原油进口航线优化问题原油进口航线优化问题 我国的原油进口我国的原油进口90 以上采用海上航运 有不同的 原油进口地 和接纳港口 如何优化运输航线 才 能使总的运输费用最少 以上采用海上航运 有不同的 原油进口地 和接纳港口 如何优化运输航线 才 能使总的运输费用最少 军事上的兵力展开问题军事上的兵力展开问题 由数个具有一定数量兵力的集结地或基地将兵力以 最短时间 展开到多个阵地 每个阵地应到达一 定数量的兵力 由数个具有一定数量兵力的集结地或基地将兵力以 最短时间 展开到多个阵地 每个阵地应到达一 定数量的兵力 8典型优化问题的模型与算法 R03 S1 D1 Dn DjSi Sm 起点终点起点终点 多阶段的生产计划和库存控制问题 考虑季节性销售模式的生产商 假设生产保持完全的稳定 或生产的变化 能满足销售模式 考虑季节性销售模式的生产商 假设生产保持完全的稳定 或生产的变化 能满足销售模式 考虑考虑3个周期 各周期的预计需求分别为 个周期 各周期的预计需求分别为 45 64 75个单位 正常时间 单位成本是 个单位 正常时间 单位成本是4 加班时间单位成本是 加班时间单位成本是6 每个周期单位存储成本是 每个周期单位存储成本是1 5 假设每个周期的成本相同 而且在每个周期 正常生产能力是假设每个周期的成本相同 而且在每个周期 正常生产能力是50个单位 加班生产能力是 个单位 加班生产能力是20个单位 个单位 如何安排生产计划才能使总成本最小 如何安排生产计划才能使总成本最小 生产需求生产需求 正常周期正常周期1 周期周期1 加班周期加班周期1 周期周期2 周期周期3 正常周期正常周期2 加班周期加班周期2 正常周期正常周期3 加班周期加班周期3 9典型优化问题的模型与算法 R03 生产计划问题 给定给定 n 个生产目标 个生产目标 m 种用于实现这些目标的方法 固定 的资源 设备等 种用于实现这些目标的方法 固定 的资源 设备等 假设每个目标有若干方法可以实现 则目的是如何分配各 种方法以完成各种目标 达到总成本最小 假设每个目标有若干方法可以实现 则目的是如何分配各 种方法以完成各种目标 达到总成本最小 这里的决策变量这里的决策变量 xij是各方法是各方法 例如资源例如资源 的使用量的使用量 或设备的使用时间或设备的使用时间 cij是使用方法 资源或设备 的单位成本 是使用方法 资源或设备 的单位成本 pij是方法的数量单位 是方法的数量单位 pij xij 表示完成目标的量 表示完成目标的量 jix njbxp miax xcxz ij m i jijij n j iij m i n j ijij 0 2 1 2 1 t s min 1 1 11 10典型优化问题的模型与算法 R03 实现方法生产目标实现方法生产目标 方法方法1目标目标1 方法方法2 目标目标2 目标目标n方法方法m 资源 设备 资源 设备 b1 b2 bn a1 a2 am 求解方法 一般的求解方法一般的求解方法 线性规划的方法线性规划的方法 多目标线性规划的方法多目标线性规划的方法 GA求解求解 人们应用遗传算法 针对各类不同的运输问题进 行了多种尝试 人们应用遗传算法 针对各类不同的运输问题进 行了多种尝试 实践证明 用遗传算法求解运输问题效果很好实践证明 用遗传算法求解运输问题效果很好 11典型优化问题的模型与算法 R03 典型问题 线性运输问题线性运输问题 Linear Transportation Problem 12典型优化问题的模型与算法 R03 线性运输问题 从不同的供给从不同的供给起点起点或或来源来源向不同的向不同的终点终点运送同一种物品 每个终点 需要特定数量的物品 运送同一种物品 每个终点 需要特定数量的物品 问题是 如何分配在每个起点的供给 以便在满足每个终点需求的 条件下 优化某个目标 例如运输费用最小 问题是 如何分配在每个起点的供给 以便在满足每个终点需求的 条件下 优化某个目标 例如运输费用最小 S1 D1 Dn DjSi Sm plants warehouses supply demand a1 ai am b1 bj bn jix njbx miax xcxz ij m j jij n j iij m i n j ijij 0 2 1 2 1 t s min 1 1 11 where xij 从起点从起点i到终点到终点j的运输量 的运输量 cij 从起点从起点i到终点到终点j的单位运输费用 的单位运输费用 ai 起点起点i的供给量 的供给量 bj 终点终点j的需求量 的需求量 13典型优化问题的模型与算法 R03 运输表 运输问题通常可用运输表来表示运输问题通常可用运输表来表示 其中行代表起点 列代表终点其中行代表起点 列代表终点 i 行行 j 列格中的内容代表决策 变量 列格中的内容代表决策 变量 xij 相应的费用系数 相应的费用系数 cij放在放在 i j 格的右上角处 格的右上角处 起点的供给量放在最后一列 终点的需求量放在最后一行 起点的供给量放在最后一列 终点的需求量放在最后一行 14典型优化问题的模型与算法 R03 运输问题解的共同特征 有有 m n 1 个基变量 每个变量对应运输表中的一格 个基变量 每个变量对应运输表中的一格 基必须是一棵基必须是一棵运输树运输树 即 在运输表的每一行和每一 列中至少存在一个基本单位 即 每个起点都至少要 运出物品 每个终点也至少要有物品运入 即 在运输表的每一行和每一 列中至少存在一个基本单位 即 每个起点都至少要 运出物品 每个终点也至少要有物品运入 基不能包含圈基不能包含圈 1614311bj 17BBS3 19BBBS2 8BS1 aiD4D3D2D1 S1 S2 S3 D1 D2 D3 D4 a1 8 a2 19 a3 17 b1 11 b2 3 b3 14 b4 16 8 3 3 13 14 3 15典型优化问题的模型与算法 R03 线性规划问题的基础可行解 njx bmibxats xcf j jj n j jij n j jj 2 1 0 0 2 1 max 1 1 线性规划的 标准形式 线性规划的 标准形式 约束条件的 矩阵表示 约束条件的 矩阵表示 mnmnmm n n b b b