运筹学基础OR_3_2ppt课件

东北大学信息科学与工程学院 运筹学 第三章运输问题 3 1运输问题及其数学模型 3 2表上作业法 3 3产销不平衡的运输问题 3 4应用举例 在产销平衡运输问题中 如果取消产销平衡这一限制 比如当供大于求或者供不应求时 那么运输问题将面临产销不平衡的问题 当供大于求 即时 对应的产销不平衡的运输问题模型为 3 3产销不平衡的运输问题 1 问题描述 首先 我们在前m个不等式中引入松弛变量 使之变成然后 再虚拟一个销售地 其需求量所以称为虚拟的销地 是因为该销售地实际上并不存在 第i个产地 i运往虚拟销售地的运量实质上是产地在完成调运方案之后多余的物质 仍存放在的库房内 因此在改进后的模型中 从各个产地运往虚拟销地的物质的单位运价为这样一来 产销不平衡问题转化成一个产销平衡问题 可以用表上作业法求解 3 3产销不平衡的运输问题 续 2 产销不平衡问题的转换 例4设有产量分别为30 50 60的三个原料产地 1 2 3 要将原料运往需求量分别为15 10 40 45的四个销售地 1 2 3 4 单位运价表如表 试求总运费最省的调运方案 销地 产地 解 总产量总销量为总产量大于总销量的不平衡的运输问题 因此增加一个虚拟的销地B5 需求量b5 140 110 30 且单位运价c15 c25 c35 0 3 3产销不平衡的运输问题 续 由此可得产销平衡的运输表 30 B5 45 40 10 15 销量 60 A3 50 A2 30 A1 B4 B3 B2 B1 产量 3 7 5 8 4 8 4 6 3 10 5 2 0 0 0 对上述产销平衡运输表 可用表示作业法求解 3 3产销不平衡的运输问题 续 30 45 40 10 15 销量 60 0 2 45 5 5 3 10 10 A3 50 0 30 6 8 20 4 7 A2 30 0 4 8 15 5 3 15 A1 产量 B5 B4 B3 B2 B1 销售地加工厂 得初始基本可行解总运费Z 470 首先利用最小元素法确定初始基本可行解 15 30 45 10 15 5 3 3产销不平衡的运输问题 续 利用位势法求解非基变量检验数 以判断初始基本可行解是否最优 v5 v4 v3 v2 v1 u3 0 3 2 45 5 5 3 10 10 10 A3 u2 0 30 6 1 8 20 4 2 7 4 A2 u1 0 0 4 1 8 15 5 1 3 15 A1 B5 B4 B3 B2 B1 销售地加工厂 由表可知 为最小的负检验数 因此可将作为换入变量 从出发 作出其它顶点均为基变量的闭回路 3 8 3 5 6 3 3产销不平衡的运输问题 续 从出发的闭回路中 偶顶点 调整量且取为换出变量 可得改进后的基本可行解总运费Z 450 比初始解优 10 10 10 10 3 3产销不平衡的运输问题 续 再利用位势法求解非基变量检验数 以判断改进后的基本可行解是否最优 v5 v4 v3 v2 v1 u3 0 3 2 45 5 15 3 2 10 10 A3 u2 0 30 6 1 8 10 4 10 7 4 A2 u1 0 0 4 1 8 15 5 1 3 15 A1 B5 B4 B3 B2 B1 销售地加工厂 由表可知 为负检验数 因此可将作为换入变量 从出发 作出其它顶点均为基变量的闭回路 3 8 3 5 4 3 3产销不平衡的运输问题 续 从出发的闭回路中 偶顶点 调整量且取为换出变量 可得改进后的基本可行解总运费Z 435 比初始解优 15 15 15 15 3 3产销不平衡的运输问题 续 继续利用位势法求解非基变量检验数 以判断二次改进后的基本可行解是否最优 v5 v4 v3 v2 v1 u3 0 3 2 30 5 30 3 2 10 9 A3 u2 0 30 6 1 8 10 4 10 7 3 A2 u1 0 1 4 15 8 1 5 2 3 15 A1 B5 B4 B3 B2 B1 销售地加工厂 3 7 1 1 2 4 3 得所有非基变量检验数均大于等于零 因此为最优解 即总运费Z 435 3 3产销不平衡的运输问题 续 1 当供应量不能满足需求量 即销量大于产量时 可以增加一个虚拟的产地 m 1 其产量且对应的单位运价 这样可以把产销不平衡运输问题转化成产销平衡的运输问题 求解方法与例4相同 3 3产销不平衡的运输问题 续 3 结论 当供应量超过需求量 即产量大于销量时 可以增加一个虚拟的销售地Bn 1