运筹学Ch4运输问题

1、第四章 运输问题,一、运输问题的数学模型,问题的提出,在许多大型连锁超市的商品供应, 物流公司的物资供,应都牵涉到众多货物的运输问题. 这些问题最终都面临,一个如何降低货物运输成本的问题. 该问题可用下面的,方式加以描述:,问题,方案, 使总运输费用为最小.,问题的约束条件为,而相应的总运输成本为,从而得到问题的数学模型,例1 试对下面的运输问题建立相应的数学模型.,解 由前面的讨论容易得到相应的数学模型:,注: 前面所讨论的是产销平衡的运输问题. 若产销不平,衡时, 相应的模型将分为产大于销或销大于产的运输问,题. 当产大于销时, 则问题的模型为:,而当需求量大于供应量时, 相应的模型为,二

2、、表上作业法,在上面的例中可以看到: 运输问题的数学模型最终归,结为一个线性规划的模型, 并可用相应的解法加以求解,但即使是一个简单的运输问题, 涉及到的变量也是比较,多的, 因而求解也较为困难. 这里将介绍一种新的解法:,表上作业法.,表上作业法的求解步骤:,求出一个初始可行解;,判定当前解是否为最优解;,解的调整.,求初始基可行解,1.西北角法,用西北角法求运输问题的初始解的要点是: 从西北角,开始按最大可能进行分配, 直到完成所有分配.,例2 用西北角法求下面运输问题的初始解.,500,100,再对第二列及第三列进行分配, 即有下表,500,100,400,100,500,100,400

3、,100,100,200,最后对第三行进行分配, 得下表,由此得初始解为,此时对应的运输成本为,注 1.用西北角法所得到问题的解与表中的单位运输成,本无关, 因而该解一般与最优解的距离较“远”;,为非基变量.,解是退化的. 对退化问题, 需要虚拟基变量来补充基变量,的个数, 其取值为0.,例3 用西北角法求下面问题的初始解,解 由西北角法, 容易得到问题的初始解,3,4,4,5,4,即: 问题的初始解为,并注意到该解是退化的. 此时可令,来增加基变,量的个数.,2.最小元素法,最小元素法的基本想法是: 按最小成本进行分配.,例4 用最小元素法求下面运输问题的初始解.,300,300,400,2

4、00,300,400,200,100,200,200,由此得到问题的初始解,此时对应的运输成本为,例5 用最小元素法求下面运输问题的初始解.,解 由最小元素法得:,3,1,4,8,3,1,即: 初始解为,最优解的判定,为判断当前解是否为最优解, 需要建立相应的位势.,为此定义位势,的位势.,例6 求下面运输问题的初始解所对应的位势.,即有下表:,又,可得其它位势:,例7 求下面运输问题的初始解所对应的位势,解 由位势的定义可分别得到,3,1,4,8,3,1,下面的例子说明对退化问题的处理方式,例8 求下面运输问题的初始解所对应的位势,解 由位势的定义可分别得到,此时, 因基变量的个数,计算下去

5、. 为此, 虚拟基变量,势:,故位势无法再继续,再进一步计算位,3,4,4,5,4,非基变量, 则,例9 对下面问题求相应的影响系数.,300,400,200,100,200,200,最优解判定方法,解的调整,若当前解不是最优解, 则要进行适当的解的调整, 以,降低运输费用. 其具体步骤为,闭回路: 从当前非基变量出发, 以直线方式向前（后,注意到在闭回路上, 除出发顶点外, 其余顶点均为基,左, 右）前进, 遇到某一个基变量变向, 直到回到起点.,变量顶点.,常见的几种闭回路形式,首先在闭回路上给各顶点以编号: 出发顶点标号为0,依次类推. 例如在下面的回路中, 各个顶点的编号为:,例如在下

6、面问题中, 则最大调整量,量.,4.求出新解,由此得到求解运输问题的具体方法:,1.求出问题的初始解（一般用最小元素法）;,2.求出位势及影响系数, 从而判定是否为最优解;,3.若不是最优解, 则进行解的调整;,4.重新进行判定.,例10 求下面运输问题的最小成本解,解 由西北角法得到问题的初始解:,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

7、,100,200,500,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,最小影响系数为,构造闭回路:,500,100,400,200,200,0,500,100,400,200,200,0,再一次计算位势和影响系数, 得,300,300,200,200,200,200,注 由于在上题的解题中的初始解是通过西北角法得到,的, 因而求解过程比较烦琐. 下面我们用最小元素法求,解该问题.,例11 求下面问题的

8、最小成本解,解 由最小元素法得问题的初始解,300,400,200,100,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,对此初始解, 再求相应的位势和影响系数:,最小影响系数,即有下表:,闭回路为,计算相应的位势及影响系

9、数:,路为,再计算位势及影响系数:,进一步计算位势和影响系数,计算位势和影响系数, 得,例13 求解下面的运输问题:,解 由最小元素法得初始解:,4,5,3,5,1,2,计算位势, 得,再计算位势和影响系数, 得,再计算位势和影响系数, 得,三、几类特殊的运输问题,在前面所讨论的是产销平衡的运输问题, 实际工作中,遇到的更多的是产销不平衡的运输问题. 由于在处理中,是把产销不平衡的运输问题化为产销平衡的运输问题加,以解决, 故本段中我们将其归为特殊的运输问题来解决.,1.产销不平衡的运输问题,产大于销的运输问题,设运输问题中, 产量总和大于需求量的总和, 即有,的问题.,例14 求解运输问题,

10、解 虚拟第四个需求点, 由此得下表,由最小元素法, 容易得到问题的初始解:,计算位势和影响系数得:,10,10,15,10,5,相应的位势和影响系数为,销大于产的运输问题,设运输问题中, 需求量总和大于产量的总和, 即有,运输成本均为,的问题.,从而将问题转化为产销平衡,例15 求下面运输问题的最小费用解.,则有下表:,由最小元素法得问题的初始解, 并计算位势和影响系数,20,80,70,50,40,40,20,80,70,50,40,40,注: 在上题中, 若先分配,由此得到初始解:,再计算相应的位势, 有,20,80,50,70,20,60,最小影响系数为,闭回路为,20,80,50,70

11、,20,60,此时最大调整量为20, 继续迭代, 所得到的解即为前面,解法中的初始解.,20,80,50,70,20,60,20,80,70,50,40,40,2.存在无通行路的运输问题,所谓存在无通行路的运输问题是指在一个运输问题中,情况下, 求运输方案.,提供的方法求出最优解.,例16 求解下面的运输问题:,解 由最小元素法得初始解,50,10,30,40,20,注意到该解是退化的, 故需虚拟基变量. 但基变量需在,求位势的过程中加以解决. 先求位势:,此时, 位势计算中断, 问题在于初始解退化. 为此, 虚拟,计算位势和影响系数后得:,例17 有三个化肥厂供应四个地区农用化肥. 假设等量

12、,的化肥在这些地区使用效果相同. 各化肥厂的年产量, 各,地区的需要量和各厂到各地的单位运价如下表所示, 求,总运费最省的调运方案.,解 此为产销不平衡的运输问题.,总产量为160, 四个地区的最低需求量为110, 最高需,求量可以设为210. 因而是需求量大于产量的问题. 为此,虚设工厂. 再注意到各地区的需求量分为两部分, 一部分,是必须满足的, 另一部分是可以不满足的. 由此产生表,格.,注意对表中第四行中单位成本的理解.,由最小元素法得到问题的初始解:,再计算相应的影响系数:,再一次计算位势和影响系数有,再计算相应的影响系数,经过数次换基后得到问题的最优解:,4.具有中转站的运输问题,

13、对该类物,站.,相应的单位,费用分别为,求运输方案, 使总运费为最小.,中转站的最大转运量为,产量限制:,中转站能力限制:,需求量限制：,供需平衡限制:,由此得到该问题的数学模型:,四、指派问题,1.指派问题的数学模型,如此的问题即称为指派问题.,完成其中的一项. 又每人完成其中任何一项工作的代价,为已知, 求这样的任务分配方案, 使完成这些工作的总,代价为最小.,如此的矩阵称为指派问题中的代价矩阵.,到矩阵:,一人完成及每人只能完成一项工作, 故在矩阵中每行和,每列只能有一个1, 其余均为0.,如此的矩阵称为指派问题中的指派矩阵.,例17 设指派问题中的代价矩阵为,则下列矩阵,则不是指派矩阵

14、.,所谓求解指派问题的最小值解, 即为求解这样的矩阵,使对应的代价为最小.,分析,条件: 矩阵中每行每列的元素只有一个是1, 其余均为,行:,列:,零的数学表达式为:,由此得到问题的模型为:,而相应的代价为,2.指派问题的求解方法,每行减去该行的最小数;,每列减去该列的最小数;,小值解:,相应元素取1, 其余为0.,判断方法: 用最少的横线和竖线将所有的零划去, 若最,列上.,例18 求下面指派问题中的最小值解.,解,注意到在最后表中, 每行每列都有零的存在.,在下面矩阵中, 选独立的零:,即相应的指派矩阵为,最小代价为,例19 求下面指派问题的最小值解:,解,注意到, 对表,可以用3条线将所

15、有的零划去, 因而没有4个独立的零.,对此我们有下面的迭代次序:,在所有未划去的数中找最小数;,未划去的数减去该数;,交叉点加上该数, 其余不变;,继续判定.,在上例中:,最小数为2, 由此得:,此时有4个独立的零,因而最优解为,注意到该问题的最优解是不唯一的. 但最小值相同.,例20 求指派问题的最小值解:,解,最小数为2, 继续迭代,代价为,3.两类特殊的指派问题,指派问题. 相应的解决方法是虚拟工作数或工人数, 以,达到平衡. 相应的代价为0.,例21 求下面指派问题的最小值解:,再由列缩减法, 得,最小数为2, 继续, 则有下表,最小数为2, 继续迭代:,指派问题中的最大值解,在某些问题中, 代价矩阵中的元素表示完成工作的收,益,