高等教育Ch运输问题.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,一、运输问题的数学模型,问题的提出,在许多大型连锁超市的商品供应,物流公司的物资供,应都牵涉到众多货物的运输问题,.,这些问题最终都面临,一个如何降低货物运输成本的问题,.,该问题可用下面的,方式加以描述,:,问题,设有某种物资,该物资共有 个产地,产地 的产量,的需求量为 且产量和需求量为相等,.,分析 一个合适的运输方案即是要确定从第 个产地,为 该物资另有 个销售点,销售点,从产地 到销售点 的单位运输成本为 求一个运输,方案,使总运输费用为最小,.,到第 个需求点 的物资供应量,.,假设供应量为 则,问题的约束条件为,而相应的总运输成本为,从而得到问题的数学模型,例,1,试对下面的运输问题建立相应的数学模型,.,200,55,65,50,30,需求量,60,15,8,6,10,40,8,10,4,12,100,20,12,6,14,产量,销地,产地,解 由前面的讨论容易得到相应的数学模型,:,注,:,前面所讨论的是产销平衡的运输问题,.,若产销不平,衡时,相应的模型将分为产大于销或销大于产的运输问,题,.,当产大于销时,则问题的模型为,:,而当需求量大于供应量时,相应的模型为,二、表上作业法,在上面的例中可以看到,:,运输问题的数学模型最终归,结为一个线性规划的模型,并可用相应的解法加以求解,但即使是一个简单的运输问题,涉及到的变量也是比较,多的,因而求解也较为困难,.,这里将介绍一种新的解法,:,表上作业法,.,表上作业法的求解步骤,:,求出一个初始可行解,;,判定当前解是否为最优解,;,解的调整,.,求初始基可行解,1.,西北角法,用西北角法求运输问题的初始解的要点是,:,从西北角,开始按最大可能进行分配,直到完成所有分配,.,例,2,用西北角法求下面运输问题的初始解,.,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,解 由西北角法,首先分配 得,500,100,再对第二列及第三列进行分配,即有下表,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,500,100,400,100,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,500,100,400,100,100,200,最后对第三行进行分配,得下表,由此得初始解为,此时对应的运输成本为,注,1.,用西北角法所得到问题的解与表中的单位运输成,2.,在表格中,凡填入数据的单元 称为,基变量,否则称,3.,基变量的个数应 当等式不成立时,则称该,本无关,因而该解一般与最优解的距离较“,远,”,;,为非基变量,.,解是退化的,.,对退化问题,需要虚拟基变量来补充基变量,的个数,其取值为,0.,例,3,用西北角法求下面问题的初始解,销地,产地,1,2,3,4,产量,1,3,11,3,10,7,2,1,9,2,8,4,3,7,4,10,5,9,需求量,3,8,5,4,20,解 由西北角法,容易得到问题的初始解,销地,产地,1,2,3,4,产量,1,3,11,3,10,7,2,1,9,2,8,4,3,7,4,10,5,9,需求量,3,8,5,4,20,3,4,4,5,4,即,:,问题的初始解为,并注意到该解是退化的,.,此时可令,来增加基变,量的个数,.,2.,最小元素法,最小元素法的基本想法是,:,按最小成本进行分配,.,例,4,用最小元素法求下面运输问题的初始解,.,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,300,解 由最小元素法,最小成本为 故,剩下的最小成本分别为,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,300,400,200,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,300,400,200,最后有,100,200,200,由此得到问题的初始解,此时对应的运输成本为,例,5,用最小元素法求下面运输问题的初始解,.,销地,产地,1,2,3,4,产量,1,3,11,3,10,7,2,1,9,2,8,4,3,7,4,10,5,9,需求量,3,8,5,4,20,解 由最小元素法得,:,销地,产地,1,2,3,4,产量,1,3,11,3,10,7,2,1,9,2,8,4,3,7,4,10,5,9,需求量,3,8,5,4,20,3,1,4,8,3,1,即,:,初始解为,最优解的判定,为判断当前解是否为最优解,需要建立相应的位势,.,若 为基变量,则有,因基变量的个数为 故令 由此得到所有,为此定义位势,的位势,.,例,6,求下面运输问题的初始解所对应的位势,.,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,100,400,2,7,5,2,3,600,200,200,200,3,1,5,4,6,300,300,需求量,600,400,200,200,解 由位势的定义,及 是基变量,由此得到 同样有,得 再由 及 得 同理,即有下表,:,又,可得其它位势,:,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,100,400,2,7,5,2,3,600,200,200,200,3,1,5,4,6,300,300,需求量,600,400,200,200,例,7,求下面运输问题的初始解所对应的位势,销地,产地,1,2,3,4,产量,1,3,11,3,10,7,4,3,2,1,9,2,8,4,3,1,3,7,4,10,5,9,8,1,需求量,3,8,5,4,20,解 由位势的定义可分别得到,销地,产地,1,2,3,4,产量,1,3,11,3,10,7,2,1,9,2,8,4,3,7,4,10,5,9,需求量,3,8,5,4,20,3,1,4,8,3,1,下面的例子说明对退化问题的处理方式,例,8,求下面运输问题的初始解所对应的位势,销地,产地,1,2,3,4,产量,1,3,11,3,10,7,3,4,2,1,9,2,8,4,4,3,7,4,10,5,9,5,4,需求量,3,8,5,4,20,解 由位势的定义可分别得到,销地,产地,1,2,3,4,产量,1,3,11,3,10,7,3,4,2,1,9,2,8,4,4,3,7,4,10,5,9,5,4,需求量,3,8,5,4,20,此时,因基变量的个数,计算下去,.,为此,虚拟基变量,势,:,故位势无法再继续,再进一步计算位,销地,产地,1,2,3,4,产量,1,3,11,3,10,7,2,1,9,2,8,4,3,7,4,10,5,9,需求量,3,8,5,4,20,3,4,4,5,4,由位势,再定义,影响系数,其定义关系为,:,若 为,非基变量,则,例,9,对下面问题求相应的影响系数,.,6,4,5,1,3,2,5,7,6,7,2,3,200,200,400,600,需求量,300,3,600,2,500,1,产量,4,3,2,1,销地,产地,300,400,200,100,200,200,解 因 为非基变量,由影响系数的定义,有,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,300,400,200,100,200,200,最优解判定方法,当前解是最优解,解的调整,若当前解不是最优解,则要进行适当的解的调整,以,1.,确定进基变量,:,2.,对当前进基变量 构造一条闭回路,:,降低运输费用,.,其具体步骤为,闭回路,:,从当前非基变量出发,以直线方式向前（后,注意到在闭回路上,除出发顶点外,其余顶点均为基,左,右）前进,遇到某一个基变量变向,直到回到起点,.,变量顶点,.,常见的几种闭回路形式,3.,在闭回路上确定最大调整量,首先在闭回路上给各顶点以编号,:,出发顶点标号为,0,依次类推,.,例如在下面的回路中,各个顶点的编号为,:,最大调整量 闭回路上编号为奇数顶点的最小运输,例如在下面问题中,则最大调整量,量,.,4.,求出新解,在闭回路上进行解的调整,:,偶数顶点,+,奇数顶点,由此得到求解运输问题的具体方法,:,1.,求出问题的初始解（一般用最小元素法）,;,2.,求出位势及影响系数,从而判定是否为最优解,;,3.,若不是最优解,则进行解的调整,;,4.,重新进行判定,.,例,10,求下面运输问题的最小成本解,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,解 由西北角法得到问题的初始解,:,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,500,100,400,100,100,200,再求出相应的位势及影响系数,.,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,500,100,400,100,100,200,即有下表,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,500,100,400,100,100,200,由于 是最小的负数,故以 为进基变量,构,即,造闭回路,:,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,500,100,400,100,100,200,由此得最大调整量 从而得到新解,.,注意到该解,是退化的,因而需要虚拟基变量,:,令并进一步计,算位势和影响系数,:,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,500,100,400,100,100,200,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,500,100,400,200,200,0,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,500,100,400,200,200,0,最小影响系数为,闭回路为,:,最大调整量 即有,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,500,100,400,200,200,0,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,500,100,400,200,200,0,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,500,100,400,200,200,0,最小影响系数为,构造闭回路,:,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,500,100,400,200,200,0,最大调整量 由此得到新解,:,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,500,100,400,200,200,0,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,300,200,2,7,5,2,3,600,200,200,200,3,1,5,4,6,300,300,需求量,600,400,200,200,再一次计算位势和影响系数,得,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,300,300,200,200,200,200,由于 故当前解为最优解,最优解值,注 由于在上题的解题中的初始解是通过西北角法得到,的,因而求解过程比较烦琐,.,下面我们用最小元素法求,解该问题,.,例,11,求下面问题的最小成本解,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,解 由最小元素法得问题的初始解,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,300,400,200,100,200,200,进一步求出位势及影响系数,:,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,300,400,200,100,200,200,最小影响系数为 闭回路为,最大调整量 由此得到新解,:,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,300,400,200,100,200,200,销地,产地,1,2,3,4,产量,1,3,2,7,6,500,2,7,5,2,3,600,3,1,5,4,6,300,需求量,600,400,200,200,300,300,200,200,200,200,注意到该解即为用西北角法求解过程中所得到的最优解,.,此例说明用最小元素法所得到的初始解一般情况下比,用西北角法得到的初始解更为优越,.,例,12,求下面运输问题的最小成本解,.,销地,产地,1,2,3,4,产量,1,3,7,6,4,15,2,2,4,3,2,12,3,4,3,8,5,13,需求量,11,10,10,9,40,销地,产地,1,2,3,4,产量,1,3,7,6,4,15,2,2,4,3,2,12,3,4,3,8,5,13,需求量,11,10,10,9,40,解 由最小元素法得到问题的初始解,:,11,1,7,8,10,3,对此初始解,再求相应的位势和影响系数,:,销地,产地,1,2,3,4,产量,1,3,7,6,4,15,7,8,2,2,4,3,2,12,11,1,3,4,3,8,5,13,10,3,需求量,11,10,10,9,40,最小影响系数,即有下表,:,闭回路为,销地,产地,1,2,3,4,产量,1,3,7,6,4,15,7,8,2,2,4,3,2,12,11,1,3,4,3,8,5,13,10,3,需求量,11,10,10,9,40,最大调整量为 由此得到新解,销地,产地,1,2,3,4,产量,1,3,7,6,4,15,7,8,2,2,4,3,2,12,11,1,3,4,3,8,5,13,10,3,需求量,11,10,10,9,40,10,3,5,8,3,4,4,2,3,4,8,2,5,4,10,6,7,3,40,9,10,10,11,需求量,13,3,12,2,15,1,产量,4,3,2,1,销地,产地,计算相应的位势及影响系数,:,销地,产地,1,2,3,4,产量,1,3,7,6,4,15,10,5,2,2,4,3,2,12,8,4,3,4,3,8,5,13,3,10,需求量,11,10,10,9,40,最小影响系数 取 为进基变量,则闭回,最大调整量为 由此得到新解,:,路为,销地,产地,1,2,3,4,产量,1,3,7,6,4,15,10,5,2,2,4,3,2,12,8,4,3,4,3,8,5,13,3,10,需求量,11,10,10,9,40,4,销地,产地,1,2,3,4,产量,1,3,7,6,4,15,6,9,2,2,4,3,2,12,8,4,3,4,3,8,5,13,3,10,需求量,11,10,10,9,40,再计算位势及影响系数,:,销地,产地,1,2,3,4,产量,1,3,7,6,4,15,6,9,2,2,4,3,2,12,8,4,3,4,3,8,5,13,3,10,需求量,11,10,10,9,40,最小影响系数 取 为进基变量,则闭回路为,最大调整量为,销地,产地,1,2,3,4,产量,1,3,7,6,4,15,6,9,2,2,4,3,2,12,8,4,3,4,3,8,5,13,3,10,需求量,11,10,10,9,40,销地,产地,1,2,3,4,产量,1,3,7,6,4,15,6,9,2,2,4,3,2,12,2,10,3,4,3,8,5,13,3,10,需求量,11,10,10,9,40,进一步计算位势和影响系数,销地,产地,1,2,3,4,产量,1,3,7,6,4,15,6,9,2,2,4,3,2,12,2,10,3,4,3,8,5,13,3,10,需求量,11,10,10,9,40,最小影响系数 回路,最大调整量为 从而得到新解,:,销地,产地,1,2,3,4,产量,1,3,7,6,4,15,6,9,2,2,4,3,2,12,2,10,3,4,3,8,5,13,3,10,需求量,11,10,10,9,40,2,销地,产地,1,2,3,4,产量,1,3,7,6,4,15,8,7,2,2,4,3,2,12,10,2,3,4,3,8,5,13,3,10,需求量,11,10,10,9,40,计算位势和影响系数,得,销地,产地,1,2,3,4,产量,1,3,7,6,4,15,8,7,2,2,4,3,2,12,10,2,3,4,3,8,5,13,3,10,需求量,11,10,10,9,40,因 故当前解为最优解,且最小成本为,例,13,求解下面的运输问题,:,销地,产地,1,2,3,4,产量,1,3,4,7,12,8,2,5,1,3,5,7,3,9,5,2,8,5,需求量,5,4,9,2,20,解 由最小元素法得初始解,:,销地,产地,1,2,3,4,产量,1,3,4,7,12,8,2,5,1,3,5,7,3,9,5,2,8,5,需求量,5,4,9,2,20,4,5,3,5,1,2,计算位势,得,销地,产地,1,2,3,4,产量,1,3,4,7,12,8,5,1,2,2,5,1,3,5,7,4,3,3,9,5,2,8,5,5,需求量,5,4,9,2,20,此时最小影响系数 回路为,最大调整量 由此得到新解,销地,产地,1,2,3,4,产量,1,3,4,7,12,8,5,1,2,2,5,1,3,5,7,4,3,3,9,5,2,8,5,5,需求量,5,4,9,2,20,销地,产地,1,2,3,4,产量,1,3,4,7,12,8,5,1,2,2,5,1,3,5,7,4,3,3,9,5,2,8,5,5,需求量,5,4,9,2,20,2,销地,产地,1,2,3,4,产量,1,3,4,7,12,8,5,3,2,5,1,3,5,7,4,1,2,3,9,5,2,8,5,5,需求量,5,4,9,2,20,再计算位势和影响系数,得,销地,产地,1,2,3,4,产量,1,3,4,7,12,8,5,3,2,5,1,3,5,7,4,1,2,3,9,5,2,8,5,5,需求量,5,4,9,2,20,此时最小影响系数 回路为,最大调整量 由此得到新解,销地,产地,1,2,3,4,产量,1,3,4,7,12,8,5,3,2,5,1,3,5,7,4,1,2,3,9,5,2,8,5,5,需求量,5,4,9,2,20,销地,产地,1,2,3,4,产量,1,3,4,7,12,8,5,3,2,5,1,3,5,7,4,1,2,3,9,5,2,8,5,5,需求量,5,4,9,2,20,3,销地,产地,1,2,3,4,产量,1,3,4,7,12,8,5,3,2,5,1,3,5,7,1,4,2,3,9,5,2,8,5,5,需求量,5,4,9,2,20,再计算位势和影响系数,得,销地,产地,1,2,3,4,产量,1,3,4,7,12,8,5,3,2,5,1,3,5,7,1,4,2,3,9,5,2,8,5,5,需求量,5,4,9,2,20,因 故当前解为最优解,且最小成本为,三、几类特殊的运输问题,在前面所讨论的是产销平衡的运输问题,实际工作中,遇到的更多的是产销不平衡的运输问题,.,由于在处理中,是把产销不平衡的运输问题化为产销平衡的运输问题加,以解决,故本段中我们将其归为特殊的运输问题来解决,.,1.,产销不平衡的运输问题,产大于销的运输问题,设运输问题中,产量总和大于需求量的总和,即有,为此,虚拟需求点 需求量为,运输成本均为 从而将问题转化为产销平衡,的问题,.,销地,产地,1,2,3,产量,1,2,9,5,35,2,4,6,10,15,需求量,15,10,15,50,40,例,14,求解运输问题,解 虚拟第四个需求点,由此得下表,销地,产地,1,2,3,4,产量,1,2,9,5,0,35,2,4,6,10,0,15,需求量,15,10,15,10,50,由最小元素法,容易得到问题的初始解,:,销地,产地,1,2,3,4,产量,1,2,9,5,0,35,2,4,6,10,0,15,需求量,15,10,15,10,50,计算位势和影响系数得,:,10,10,15,10,5,销地,产地,1,2,3,4,产量,1,2,9,5,0,35,15,10,10,2,4,6,10,0,15,10,5,需求量,15,10,15,10,50,最小影响系数 回路,最大调整量 由此得到新解,销地,产地,1,2,3,4,产量,1,2,9,5,0,35,15,10,10,2,4,6,10,0,15,10,5,需求量,15,10,15,10,50,5,销地,产地,1,2,3,4,产量,1,2,9,5,0,35,15,15,5,2,4,6,10,0,15,10,5,需求量,15,10,15,10,50,相应的位势和影响系数为,销地,产地,1,2,3,4,产量,1,2,9,5,0,35,15,15,5,2,4,6,10,0,15,10,5,需求量,15,10,15,10,50,因 故当前解为最优解,且最小成本为,销大于产的运输问题,为此,虚拟产地 产量为,设运输问题中,需求量总和大于产量的总和,即有,运输成本均为,的问题,.,从而将问题转化为产销平衡,例,15,求下面运输问题的最小费用解,.,销地,产地,1,2,3,产量,1,8,5,6,120,2,15,10,12,80,3,3,9,10,80,需求量,140,70,90,280,300,解 由前面讨论,虚拟产地 产量为,则有下表,:,销地,产地,1,2,3,产量,1,8,5,6,120,2,15,10,12,80,3,3,9,10,80,4,M,M,M,20,需求量,140,70,90,300,由最小元素法得问题的初始解,并计算位势和影响系数,销地,产地,1,2,3,产量,1,8,5,6,120,2,15,10,12,80,3,3,9,10,80,4,M,M,M,20,需求量,140,70,90,300,20,80,70,50,40,40,销地,产地,1,2,3,产量,1,8,5,6,120,2,15,10,12,80,3,3,9,10,80,4,M,M,M,20,需求量,140,70,90,300,20,80,70,50,40,40,最小影响系数 回路,最大调整量 由此得到新解,销地,产地,1,2,3,产量,1,8,5,6,120,40,70,10,2,15,10,12,80,80,3,3,9,10,80,80,4,M,M,M,20,20,需求量,140,70,90,300,销地,产地,1,2,3,产量,1,8,5,6,120,40,70,10,2,15,10,12,80,80,3,3,9,10,80,80,4,M,M,M,20,20,需求量,140,70,90,300,最小影响系数 回路,最大调整量 由此得到新解,:,销地,产地,1,2,3,产量,1,8,5,6,120,40,80,2,15,10,12,80,70,10,3,3,9,10,80,80,4,M,M,M,20,20,需求量,140,70,90,300,销地,产地,1,2,3,产量,1,8,5,6,120,40,80,2,15,10,12,80,70,10,3,3,9,10,80,80,4,M,M,M,20,20,需求量,140,70,90,300,因 故当前解为最优解,且最小成本为,注,:,在上题中,若先分配,由此得到初始解,:,销地,产地,1,2,3,产量,1,8,5,6,120,50,70,2,15,10,12,80,60,20,3,3,9,10,80,80,4,M,M,M,20,20,需求量,140,70,90,300,再计算相应的位势,有,销地,产地,1,2,3,产量,1,8,5,6,120,2,15,10,12,80,3,3,9,10,80,4,M,M,M,20,需求量,140,70,90,300,20,80,50,70,20,60,最小影响系数为,闭回路为,销地,产地,1,2,3,产量,1,8,5,6,120,2,15,10,12,80,3,3,9,10,80,4,M,M,M,20,需求量,140,70,90,300,20,80,50,70,20,60,此时最大调整量为,20,继续迭代,所得到的解即为前面,解法中的初始解,.,销地,产地,1,2,3,产量,1,8,5,6,120,2,15,10,12,80,3,3,9,10,80,4,M,M,M,20,需求量,140,70,90,300,20,80,50,70,20,60,销地,产地,1,2,3,产量,1,8,5,6,120,2,15,10,12,80,3,3,9,10,80,4,M,M,M,20,需求量,140,70,90,300,20,80,70,50,40,40,2.,存在无通行路的运输问题,所谓存在无通行路的运输问题是指在一个运输问题中,分析,:,对所给条件,为使 不能成为基变量,可使相,产地 与需求点 之间不存在相应的运输线路,.,在此种,情况下,求运输方案,.,应的运输成本为最大的,.,为此可设 再由前面所,提供的方法求出最优解,.,例,16,求解下面的运输问题,:,销地,产地,1,2,3,4,产量,1,7,6,5,4,50,2,9,7,3,6,50,3,8,7,3,50,需求量,20,40,30,60,150,销地,产地,1,2,3,4,产量,1,7,6,5,4,50,2,9,7,3,6,50,3,8,M,7,3,50,需求量,20,40,30,60,150,解 由最小元素法得初始解,50,10,30,40,20,注意到该解是退化的,故需虚拟基变量,.,但基变量需在,求位势的过程中加以解决,.,先求位势,:,销地,产地,1,2,3,4,产量,1,7,6,5,4,50,40,10,2,9,7,3,6,50,20,30,3,8,M,7,3,50,50,需求量,20,40,30,60,150,此时,位势计算中断,问题在于初始解退化,.,为此,虚拟,基变量,令 则有,销地,产地,1,2,3,4,产量,1,7,6,5,4,50,40,10,2,9,7,3,6,50,20,0,30,3,8,M,7,3,50,50,需求量,20,40,30,60,150,此时最小影响系数 回路为,最大调整量 由此得到新解,销地,产地,1,2,3,4,产量,1,7,6,5,4,50,20,20,10,2,9,7,3,6,50,20,30,3,8,M,7,3,50,50,需求量,20,40,30,60,150,计算位势和影响系数后得,:,销地,产地,1,2,3,4,产量,1,7,6,5,4,50,20,20,10,2,9,7,3,6,50,20,30,3,8,M,7,3,50,50,需求量,20,40,30,60,150,因 故当前解为最优解,且最小成本为,例,17,有三个化肥厂供应四个地区农用化肥,.,假设等量,的化肥在这些地区使用效果相同,.,各化肥厂的年产量,各,地区的需要量和各厂到各地的单位运价如下表所示,求,总运费最省的调运方案,.,不限,30,70,50,最高需求,10,0,70,30,最低需求,50,_,23,20,19,3,60,15,19,13,14,2,50,17,22,13,16,1,产量,4,3,2,1,地区,化肥厂,解 此为产销不平衡的运输问题,.,总产量为,160,四个地区的最低需求量为,110,最高需,求量可以设为,210.,因而是需求量大于产量的问题,.,为此,虚设工厂,.,再注意到各地区的需求量分为两部分,一部分,是必须满足的,另一部分是可以不满足的,.,由此产生表,格,.,0,M,0,M,0,M,M,M,23,20,19,19,15,15,19,17,17,22,13,16,13,14,14,16,210,50,10,30,70,20,30,50,4,50,3,60,2,50,1,4,4,3,2,1,1,注意对表中第四行中单位成本的理解,.,由最小元素法得到问题的初始解,:,1,1,2,3,4,4,1,16,16,13,22,17,17,50,50,2,14,14,13,19,15,15,60,30,10,20,3,19,19,20,23,M,M,50,10,10,30,4,M,0,M,0,M,0,50,30,20,30,20,70,30,10,50,210,1,1,2,3,4,4,1,16,16,13,22,17,17,50,50,2,14,14,13,19,15,15,60,30,10,20,3,19,19,20,23,M,M,50,10,10,30,4,M,0,M,0,M,0,50,30,20,30,20,70,30,10,50,210,再计算相应的影响系数,:,此时 为进基变量,由此得新解,1,1,2,3,4,4,1,16,16,13,22,17,17,50,50,2,14,14,13,19,15,15,60,30,10,20,3,19,19,20,23,M,M,50,10,30,10,4,M,0,M,0,M,30,0,50,20,30,20,70,30,10,50,210,再一次计算位势和影响系数有,1,1,2,3,4,4,1,16,16,13,22,17,17,50,50,2,14,14,13,19,15,15,60,30,10,20,3,19,19,20,23,M,M,50,10,10,30,4,M,0,M,0,M,0,50,30,20,30,20,70,30,10,50,210,再计算相应的影响系数,以 为进基变量,则有新解,1,1,2,3,4,4,1,16,16,13,22,17,17,50,50,2,14,14,13,19,15,15,60,30,20,10,3,19,19,20,23,M,M,50,20,30,4,M,0,M,0,M,0,50,30,20,30,20,70,30,10,50,210,经过数次换基后得到问题的最优解,:,4.,具有中转站的运输问题,某类物资有 个产地,产地 的产地为,对该类物,资有 个需求点,第 个需求点的需求量为,从产地到达需求点都需经过 个中转站中的某个中转,站,.,启动第 个中转站将发生固定费用,相应的单位,费用分别为,求运输方案,使总运费为最小,.,中转站的最大转运量为,引入 变量,表示启用第 个中转站,表示经过从 个产地到第 个中转站及从第 个中转站到,第 个需求点的运输量,则问题的目标函数为,产量限制,:,中转站能力限制,:,需求量限制：,供需平衡限制,:,由此得到该问题的数学模型,:,四、指派问题,1.,指派问题的数学模型,问题 设有 项工作,交给 个人去完成,.,每个人只能,如此的问题即称为,指派问题,.,完成其中的一项,.,又每人完成其中任何一项工作的代价,为已知,求这样的任务分配方案,使完成这些工作的总,代价为最小,.,以 表示第 人完成第 项工作所需的代价,由此得,如此的矩阵称为指派问题中的,代价矩阵,.,到矩阵,:,引入决策变量,:,第 人完成第 项工作,;,第 项工作由其他人完成,.,由此得到矩阵 注意到,:,由于每项工作只能由,一人完成及每人只能完成一项工作,故在矩阵中每行和,每列只能有一个,1,其余均为,0.,如此的矩阵称为指派问题中的,指派矩阵,.,例,17,设指派问题中的代价矩阵为,则下列矩阵,均为指派矩阵,其代价分别为 而矩阵,则不是指派矩阵,.,所谓求解指派问题的最小值解,即为求解这样的矩阵,使对应的代价为最小,.,分析,条件,:,矩阵中每行每列的元素只有一个是,1,其余均为,行,:,列,:,零的数学表达式为,:,由此得到问题的模型为,:,而相应的代价为,2.,指派问题的求解方法,设代价矩阵为 我们用下面的方法求其最,每行减去该行的最小数,;,每列减去该列的最小数,;,每行每列至少一个零,.,判断是否有 个独立的零,若有,则在指派矩阵中,小值解,:,相应元素取,1,其余为,0.,所谓有 个独立的零,即指这些零应分布在不同的行,判断方法,:,用最少的横线和竖线将所有的零划去,若最,列上,.,少的线数为 则一定有 个独立的零,.,例,18,求下面指派问题中的最小值解,.,解,行,列,注意到在最后表中,每行每列都有零的存在,.,在下面矩阵中,选独立的零,:,则问题的最优解为 其余,即相应的指派矩阵为,最小代价为,例,19,求下面指派问题的最小值解,:,解,行,列,注意到,对表,可以用,3,条线将所有的零划去,因而没有,4,个独立的零,.,对此我们有下面的迭代次序,:,在所有未划去的数中找最小数,;,未划去的数减去该数,;,交叉点加上该数,其余不变,;,继续判定,.,在上例中,:,最小数为,2,由此得,:,此时有,4,个独立的零,因而最优解为,其余 最小代价为,注意到该问题的最优解是不唯一的,.,但最小值相同,.,例,20,求指派问题的最小值解,:,解,行,列,最小数为,2,继续迭代,最优解为 其余 最小,代价为,3.,两类特殊的指派问题,的指派问题,所谓 的指派问题是指工作数与工人数不相等的,指派问题,.,相应的解决方法是虚拟工作数或工人数,以,达到平衡,.,相应的代价为,0.,例,21,求下面指派问题的最小值解,:,解 此时 故添加,0,列,.,有下表,再由列缩减法,得,列,最小数为,2,继续,则有下表,最小数为,2,继续迭代,:,此时有 个独立的零,.,选择独立的零,:,最优解为 最小成本为,指派问题中的最大值解,在某些问题中,代价矩阵中的元素表示完成工作的