运输问题模型.ppt

运输问题模型 杭州电子科技大学 数学教研室 杭州电子科技大学 沈灏二0一0年四月 运输问题的一般描述 设某种物资有m个产地A1 A2 Am 和n个销地B1 B2 Bn 其中Ai的产量为ai Bj的销量为bj 产地Ai运往销地Bj的单位运价Cij i 1 2 m j 1 2 n 求尽可能满足销地需求且总费用最小的运输方案 运输问题的数学模型可以分以下3种情况讨论 1 产销平衡问题2 销大于产问题产大于销问题 解 设产地Ai运往销地Bj的运量为 1 产销平衡问题的数学模型 产销平衡时 各个产地的物资总和正好满足所有销地的需求 运输问题的数学模型为 2 销大于产问题的数学模型 销大于产时 各个销地的需求不一定能够得到满足 运输问题的数学模型为 2 产大于销问题的数学模型 销大于产时 各个销地的需求一定能够得到满足 但各个产地的物资不一定全部运走 运输问题的数学模型为 运输问题本质是一个线性规划问题 运输问题变量比较多 系数矩阵为0 1矩阵 其中大部分元素为零 计算运输问题我们有比单纯形法更好的专门求解运输问题的算法 产销平衡运输问题的求解 定理产销平衡运输问题一定存在最优解 产销平衡运输问题的Lingo模型 MODEL sets row 1 m a arrange 1 n b link row arrange c x endsetsdata a a 1 a 2 a m b b 1 b 2 b n C c 1 1 c 1 2 c 1 n c 2 1 c 2 2 c 2 n c m 1 c m 2 c m n enddata OBJ min sum link i j c i j x i j for row i sum arrange j x i j a i for arrange j sum row i x i j b j for link i j x i j 0 END 产销不平衡运输问题也有类似的Lingo模型 产销平衡运输问题的初始解 1 西北角法在运价表的西北角选择运量和销量中的较小数作为运量 初始基变量 每确定一个初始基变量后 划去需求变成零的剩余列元素或划去运量变成零的剩余行元素 填上x33 1后 自然少去一列 第3列 这时不要再去掉第3行 注意到每填一个数据恰好减少一行或一列 总共填写m n个数据 填上去的m n个数据为基变量 产销平衡运输问题的初始解 2 最小元素法选择运价表中最小运价 运量和销量中的较小数作为运量 初始基变量 每确定一个初始基变量后 划去需求变成零的剩余列元素或划去运量变成零的剩余行元素 填上x14 4后 第4列自然被去掉 记住每填一个数据减少一行或一列 3 位势法求检验数 对每个基变量xij 计算ui和vj 使ui vj cij其中u1 0 再计算非基变量检验数 ij cij ui vj 11 4x11每增加一个单位 目标函数可以减少4个单位 目标可以减少 说明当前解不是最优解 闭回路法调整 选x11进基 找到闭回路x11x144 x21x242 3 闭回路法调整 为了保证所有xij非负 x11最多增加3 取x11 3x11 3x144 3x21x242 33 3 重新计算检验数 22 1x22每增加一个单位 目标函数可以减少1个单位 目标可以减少 说明当前解不是最优解 闭回路法调整 选x22进基 找到闭回路x125 x141 x22 x245 X22最多增加5 x125 5x141 5x22 5x245 5 X22进基 x12和x24经过调整同时变成零 但是要注意只有一个变量出基 例如 令x12出基得调整后的运输表为 重新计算检验数 所有非基变量检验数均非负 当前解为最优解 最优解为 X11 3 x14 6 x22 5 x32 3 x33 4 其余xij 0最优目标值为Z 3 2 6 7 5 3 3 4 4 2 83 运输问题数学模型的应用实例 设某制造企业根据合同要求 从当年起需连续三年在年末提供3套型号规格相同的大型设备 已知该厂的生产能力及生产成本如下表所示 生产能力与生产成本表 年度正常生产可加班生产可正常生产完成设备数完成设备数成本 万 第一年23500第二年42600第三年13550设加班生产情况下每套设备成本比正常生产时高70万元 每套设备不及时交货积压一年的维护费用为40万元 该厂现库存有2套设备 希望第三年末完成合同要求后还能储存1台设备 问如何安排生产 才能使总成本最低 解 设xj为初始存货用于第j年交货的设备数 yij为第i年正常生产用于第j年交货的设备数 zij为第i年加班生产用于第j年交货的设备数 cj为初始库存设备第j年交货时每台设备维护费 aij为第i年正常生产到第j年交货的每台设备成本费 bij为第i年加班生产到第j年交货的每台设备成本费 上述生产计划问题的数学模型为 记A为正常生产时的费用矩阵 B为加班生产时的费用矩阵 C 0 40 80 生产计划问题的Lingo模型为 MODEL sets row 1 2 3 arrange 1 2 3 c x link row arrange a b y z Endsetsdata c 0 40 80 a 500 540 580 0 600 640 0 0 550 b 570 610 650 0 670 710 0 0 620 enddata OBJ min sum arrange j c j x j sum link i j a i j y i j sum link i j b i j z i j sum arrange j x j 2 sum arrange j y 1 j 2 sum arrange j z 1 j 3 y 2 2 y 2 3 4 z 2 2 z 2 3 2 y 3 3 1 z 3 3 3 x 1 y 1 1 z 1 1 3 x 2 y 1 2 z 1 2 y 2 2 z 2 2 3 x 3 y 1 3 z 1 3 y 2 3 z 2 3 y 3 3 z 3 3 4 for arrange j x j 0 for link i