Ch4运输问答.ppt

《Ch4运输问答.ppt》由会员分享，可在线阅读，更多相关《Ch4运输问答.ppt（248页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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,最小影响系数 回路,最大调整量 由此得

13、到新解,相应的位势和影响系数为,因 故当前解为最优解, 且最小成本为,销大于产的运输问题,为此, 虚拟产地 产量为,设运输问题中, 需求量总和大于产量的总和, 即有,运输成本均为,的问题.,从而将问题转化为产销平衡,例15 求下面运输问题的最小费用解.,解 由前面讨论, 虚拟产地 产量为,则有下表:,由最小元素法得问题的初始解, 并计算位势和影响系数,20,80,70,50,40,40,20,80,70,50,40,40,最小影响系数 回路,最大调整量 由此得到新解,最小影响系数 回路,最大调整量 由此得到新解:,因 故当前解为最优解, 且最小成本为,注: 在上题中, 若先分配,由此得到初始解

14、:,再计算相应的位势, 有,20,80,50,70,20,60,最小影响系数为,闭回路为,20,80,50,70,20,60,此时最大调整量为20, 继续迭代, 所得到的解即为前面,解法中的初始解.,20,80,50,70,20,60,20,80,70,50,40,40,2.存在无通行路的运输问题,所谓存在无通行路的运输问题是指在一个运输问题中,分析: 对所给条件, 为使 不能成为基变量, 可使相,产地 与需求点 之间不存在相应的运输线路. 在此种,情况下, 求运输方案.,应的运输成本为最大的. 为此可设 再由前面所,提供的方法求出最优解.,例16 求解下面的运输问题:,解 由最小元素法得初始

15、解,50,10,30,40,20,注意到该解是退化的, 故需虚拟基变量. 但基变量需在,求位势的过程中加以解决. 先求位势:,此时, 位势计算中断, 问题在于初始解退化. 为此, 虚拟,基变量, 令 则有,此时最小影响系数 回路为,最大调整量 由此得到新解,计算位势和影响系数后得:,因 故当前解为最优解, 且最小成本为,例17 有三个化肥厂供应四个地区农用化肥. 假设等量,的化肥在这些地区使用效果相同. 各化肥厂的年产量, 各,地区的需要量和各厂到各地的单位运价如下表所示, 求,总运费最省的调运方案.,解 此为产销不平衡的运输问题.,总产量为160, 四个地区的最低需求量为110, 最高需,求

16、量可以设为210. 因而是需求量大于产量的问题. 为此,虚设工厂. 再注意到各地区的需求量分为两部分, 一部分,是必须满足的, 另一部分是可以不满足的. 由此产生表,格.,注意对表中第四行中单位成本的理解.,由最小元素法得到问题的初始解:,再计算相应的影响系数:,此时 为进基变量, 由此得新解,再一次计算位势和影响系数有,再计算相应的影响系数,以 为进基变量, 则有新解,经过数次换基后得到问题的最优解:,4.具有中转站的运输问题,某类物资有 个产地, 产地 的产地为,对该类物,资有 个需求点, 第 个需求点的需求量为,从产地到达需求点都需经过 个中转站中的某个中转,站.,启动第 个中转站将发生

17、固定费用,相应的单位,费用分别为,求运输方案, 使总运费为最小.,中转站的最大转运量为,引入 变量,表示启用第 个中转站,表示经过从 个产地到第 个中转站及从第 个中转站到,第 个需求点的运输量, 则问题的目标函数为,产量限制:,中转站能力限制:,需求量限制：,供需平衡限制:,由此得到该问题的数学模型:,四、指派问题,1.指派问题的数学模型,问题 设有 项工作, 交给 个人去完成. 每个人只能,如此的问题即称为指派问题.,完成其中的一项. 又每人完成其中任何一项工作的代价,为已知, 求这样的任务分配方案, 使完成这些工作的总,代价为最小.,以 表示第 人完成第 项工作所需的代价, 由此得,如此

18、的矩阵称为指派问题中的代价矩阵.,到矩阵:,引入决策变量 :,由此得到矩阵 注意到: 由于每项工作只能由,一人完成及每人只能完成一项工作, 故在矩阵中每行和,每列只能有一个1, 其余均为0.,如此的矩阵称为指派问题中的指派矩阵.,例17 设指派问题中的代价矩阵为,则下列矩阵,均为指派矩阵, 其代价分别为 而矩阵,则不是指派矩阵.,所谓求解指派问题的最小值解, 即为求解这样的矩阵,使对应的代价为最小.,分析,条件: 矩阵中每行每列的元素只有一个是1, 其余均为,行:,列:,零的数学表达式为:,由此得到问题的模型为:,而相应的代价为,2.指派问题的求解方法,设代价矩阵为 我们用下面的方法求其最,每

19、行减去该行的最小数;,每列减去该列的最小数;,判断是否有 个独立的零, 若有, 则在指派矩阵中,小值解:,相应元素取1, 其余为0.,所谓有 个独立的零, 即指这些零应分布在不同的行,判断方法: 用最少的横线和竖线将所有的零划去, 若最,列上.,少的线数为 则一定有 个独立的零.,例18 求下面指派问题中的最小值解.,解,注意到在最后表中, 每行每列都有零的存在.,在下面矩阵中, 选独立的零:,则问题的最优解为 其余,即相应的指派矩阵为,最小代价为,例19 求下面指派问题的最小值解:,解,注意到, 对表,可以用3条线将所有的零划去, 因而没有4个独立的零.,对此我们有下面的迭代次序:,在所有未

20、划去的数中找最小数;,未划去的数减去该数;,交叉点加上该数, 其余不变;,继续判定.,在上例中:,最小数为2, 由此得:,此时有4个独立的零,因而最优解为,其余 最小代价为,注意到该问题的最优解是不唯一的. 但最小值相同.,例20 求指派问题的最小值解:,解,最小数为2, 继续迭代,最优解为 其余 最小,代价为,3.两类特殊的指派问题, 的指派问题,所谓 的指派问题是指工作数与工人数不相等的,指派问题. 相应的解决方法是虚拟工作数或工人数, 以,达到平衡. 相应的代价为0.,例21 求下面指派问题的最小值解:,解 此时 故添加0列. 有下表,再由列缩减法, 得,最小数为2, 继续, 则有下表,

21、最小数为2, 继续迭代:,此时有 个独立的零. 选择独立的零:,最优解为 最小成本为,指派问题中的最大值解,在某些问题中, 代价矩阵中的元素表示完成工作的收,矩阵 称为收益矩阵.,益, 此时问题将转化为求相应的极大值问题.,问题,求收益矩阵中的最大值解.,解法,令,记,则代价矩阵 的最小值解即为原问题的最大值解.,例22 求下面指派问题的最大值解,解,此时 故要添加零行, 即有,最小数为2, 进一步有,最小数=1,在最后一个矩阵中, 有4个独立的零, 选择,即原问题的最优解为 最大收益为,多任务要求的指派问题,在某些具体问题中, 当任务数大于人数时, 而工作又,必须完成时, 则可通过虚拟第 人, 其代价为每个,人中最小的.,例23 求下面指派问题中的最小值解,解 引入,则有,最小数为1,最小数为4,此时有5个独立的零:,最优解为,注意到 即第二人完成了两项工作.,在可重复情况下, 如何求相应的最大值解?,例24 求下面指派问题的最大值解,