《运筹学—运输问题》由会员分享，可在线阅读，更多相关《运筹学—运输问题（242页珍藏版）》请在金锄头文库上搜索。
1、第四章 运输问题,一、运输问题的数学模型,问题的提出,在许多大型连锁超市的商品供应, 物流公司的物资供,应都牵涉到众多货物的运输问题. 这些问题最终都面临,一个如何降低货物运输成本的问题. 该问题可用下面的,方式加以描述:,问题,设有某种物资, 该物资共有 个产地, 产地 的产量,的需求量为 且产量和需求量为相等.,分析 一个合适的运输方案即是要确定从第 个产地,为 该物资另有 个销售点, 销售点,从产地 到销售点 的单位运输成本为 求一个运输,方案, 使总运输费用为最小.,到第 个需求点 的物资供应量. 假设供应量为 则,问题的约束条件为,而相应的总运输成本为,从而得到问题的数学模型,例1
2、试对下面的运输问题建立相应的数学模型.,解 由前面的讨论容易得到相应的数学模型:,注: 前面所讨论的是产销平衡的运输问题. 若产销不平,衡时, 相应的模型将分为产大于销或销大于产的运输问,题. 当产大于销时, 则问题的模型为:,而当需求量大于供应量时, 相应的模型为,二、表上作业法,在上面的例中可以看到: 运输问题的数学模型最终归,结为一个线性规划的模型, 并可用相应的解法加以求解,但即使是一个简单的运输问题, 涉及到的变量也是比较,多的, 因而求解也较为困难. 这里将介绍一种新的解法:,表上作业法.,表上作业法的求解步骤:,求出一个初始可行解;,判定当前解是否为最优解;,解的调整.,求初始基
3、可行解,1.西北角法,用西北角法求运输问题的初始解的要点是: 从西北角,开始按最大可能进行分配, 直到完成所有分配.,例2 用西北角法求下面运输问题的初始解.,解 由西北角法, 首先分配 得,500,100,再对第二列及第三列进行分配, 即有下表,500,100,400,100,500,100,400,100,100,200,最后对第三行进行分配, 得下表,由此得初始解为,此时对应的运输成本为,注 1.用西北角法所得到问题的解与表中的单位运输成,2.在表格中, 凡填入数据的单元 称为基变量, 否则称,3.基变量的个数应 当等式不成立时, 则称该,本无关, 因而该解一般与最优解的距离较“远”;,
4、为非基变量.,解是退化的. 对退化问题, 需要虚拟基变量来补充基变量,的个数, 其取值为0.,例3 用西北角法求下面问题的初始解,解 由西北角法, 容易得到问题的初始解,3,4,4,5,4,即: 问题的初始解为,并注意到该解是退化的. 此时可令,来增加基变,量的个数.,2.最小元素法,最小元素法的基本想法是: 按最小成本进行分配.,例4 用最小元素法求下面运输问题的初始解.,300,解 由最小元素法, 最小成本为 故,剩下的最小成本分别为,300,400,200,300,400,200,最后有,100,200,200,由此得到问题的初始解,此时对应的运输成本为,例5 用最小元素法求下面运输问题
5、的初始解.,解 由最小元素法得:,3,1,4,8,3,1,即: 初始解为,最优解的判定,为判断当前解是否为最优解, 需要建立相应的位势.,若 为基变量, 则有,因基变量的个数为 故令 由此得到所有,为此定义位势,的位势.,例6 求下面运输问题的初始解所对应的位势.,解 由位势的定义, 及 是基变量,由此得到 同样有,得 再由 及 得 同理,即有下表:,又,可得其它位势:,例7 求下面运输问题的初始解所对应的位势,解 由位势的定义可分别得到,3,1,4,8,3,1,下面的例子说明对退化问题的处理方式,例8 求下面运输问题的初始解所对应的位势,解 由位势的定义可分别得到,此时, 因基变量的个数,计
6、算下去. 为此, 虚拟基变量,势:,故位势无法再继续,再进一步计算位,3,4,4,5,4,由位势, 再定义影响系数 其定义关系为: 若 为,非基变量, 则,例9 对下面问题求相应的影响系数.,解 因 为非基变量, 由影响系数的定义, 有,300,400,200,100,200,200,最优解判定方法,当前解是最优解,解的调整,若当前解不是最优解, 则要进行适当的解的调整, 以,1.确定进基变量 :,2.对当前进基变量 构造一条闭回路:,降低运输费用. 其具体步骤为,闭回路: 从当前非基变量出发, 以直线方式向前（后,注意到在闭回路上, 除出发顶点外, 其余顶点均为基,左, 右）前进, 遇到某一
7、个基变量变向, 直到回到起点.,变量顶点.,常见的几种闭回路形式,3.在闭回路上确定最大调整量,首先在闭回路上给各顶点以编号: 出发顶点标号为0,依次类推. 例如在下面的回路中, 各个顶点的编号为:,最大调整量 闭回路上编号为奇数顶点的最小运输,例如在下面问题中, 则最大调整量,量.,4.求出新解,在闭回路上进行解的调整: 偶数顶点+ 奇数顶点,由此得到求解运输问题的具体方法:,1.求出问题的初始解（一般用最小元素法）;,2.求出位势及影响系数, 从而判定是否为最优解;,3.若不是最优解, 则进行解的调整;,4.重新进行判定.,例10 求下面运输问题的最小成本解,解 由西北角法得到问题的初始解
8、:,500,100,400,100,100,200,再求出相应的位势及影响系数.,500,100,400,100,100,200,即有下表,500,100,400,100,100,200,由于 是最小的负数, 故以 为进基变量, 构,即,造闭回路:,500,100,400,100,100,200,由此得最大调整量 从而得到新解. 注意到该解,是退化的, 因而需要虚拟基变量: 令并进一步计,算位势和影响系数:,500,100,400,100,100,200,500,100,400,200,200,0,500,100,400,200,200,0,最小影响系数为,闭回路为:,最大调整量 即有,500
9、,100,400,200,200,0,500,100,400,200,200,0,500,100,400,200,200,0,最小影响系数为,构造闭回路:,500,100,400,200,200,0,最大调整量 由此得到新解:,500,100,400,200,200,0,再一次计算位势和影响系数, 得,300,300,200,200,200,200,由于 故当前解为最优解, 最优解值,注 由于在上题的解题中的初始解是通过西北角法得到,的, 因而求解过程比较烦琐. 下面我们用最小元素法求,解该问题.,例11 求下面问题的最小成本解,解 由最小元素法得问题的初始解,300,400,200,100,
10、200,200,进一步求出位势及影响系数:,300,400,200,100,200,200,最小影响系数为 闭回路为,最大调整量 由此得到新解:,300,400,200,100,200,200,300,300,200,200,200,200,注意到该解即为用西北角法求解过程中所得到的最优解.,此例说明用最小元素法所得到的初始解一般情况下比,用西北角法得到的初始解更为优越.,例12 求下面运输问题的最小成本解.,解 由最小元素法得到问题的初始解:,11,1,7,8,10,3,对此初始解, 再求相应的位势和影响系数:,最小影响系数,即有下表:,闭回路为,最大调整量为 由此得到新解,计算相应的位势及
11、影响系数:,最小影响系数 取 为进基变量, 则闭回,最大调整量为 由此得到新解:,闭回路为,再计算位势及影响系数:,最小影响系数 取 为进基变量, 则闭回路为,最大调整量为,进一步计算位势和影响系数,最小影响系数 回路,最大调整量为 从而得到新解:,计算位势和影响系数, 得,因 故当前解为最优解, 且最小成本为,例13 求解下面的运输问题:,解 由最小元素法得初始解:,4,5,3,5,1,2,计算位势, 得,此时最小影响系数 回路为,最大调整量 由此得到新解,再计算位势和影响系数, 得,此时最小影响系数 回路为,最大调整量 由此得到新解,再计算位势和影响系数, 得,因 故当前解为最优解, 且最
12、小成本为,三、几类特殊的运输问题,在前面所讨论的是产销平衡的运输问题, 实际工作中,遇到的更多的是产销不平衡的运输问题. 由于在处理中,是把产销不平衡的运输问题化为产销平衡的运输问题加,以解决, 故本段中我们将其归为特殊的运输问题来解决.,1.产销不平衡的运输问题,产大于销的运输问题,设运输问题中, 产量总和大于需求量的总和, 即有,为此, 虚拟需求点 需求量为,运输成本均为 从而将问题转化为产销平衡,的问题.,例14 求解运输问题,解 虚拟第四个需求点, 由此得下表,由最小元素法, 容易得到问题的初始解:,计算位势和影响系数得:,10,10,15,10,5,最小影响系数 回路,最大调整量 由此得到新解,相应的位势和影响系数为,因 故当前解为最优解, 且最小成本为,销大于产的运输问题,为此, 虚拟产地 产量为,设运输问题中, 产量总和大于需求量的总和, 即有,运输成本均为,的问题.,从而将问题转化为产销平衡,例15 求下面运输问题的最小费用解.,解 由前面讨论, 虚拟产地 产量为,
