资源描述：
《物流系统规划（二）课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、3物流分配规划任务分配问题的数学模型（重点）用匈牙利法求解分配问题（自学）1一.任务分配问题1.简介在物流系统中经常面临的一个问题：如何根据有限的资源(人力、物力、财力等)，进行工作任务分配，以达到降低成本或提高经济效益的目的。如：运输任务的分配问题。有n条航线的运输任务指派给n艘船去完成，不同的船完成不同的航线其运输成本不同。要求每条船完成一条航线，并且一条航线只能由一条船去完成。如何分配任务，才能使总的费用最小？又如：有A、B、C、D四门课程，上课的老师可以从甲、乙、丙、丁四名老师中选择，不同的老师上不
2、同的课程，其费用是不同的，并且规定，每人只讲一门课程，每门课程只需要一人讲授。问：如何安排，才能使总的上课费用最低？这类问题是常见的任务分配问题，也叫指派问题，它的任务是如何进行合理的任务分配，使总的费用最小。22.任务分配问题的数学模型以运输问题的n项任务由n个司机去完成的情况为例：有n个司机被分配完成n项运输任务，不同的司机完成某一项任务的费用都不一样。要求每个司机完成其中一项任务，每个任务只能由一名司机完成，如何分配任务，才能使总的费用最小？令：cij表示第i个司机完成第j项任务的运输成本（工作成本或
3、工作时间等价值系数）；xij表示第i个司机去完成第j项任务，其值为1或0。当其值为1时表示第i个司机被分配去完成第j项任务；其值为0时，表示第i个司机不被分配去完成第j项任务。33.任务分配问题数学模型的求解任务分配问题属于整数规划问题，其变量xij的取值为整数。（本例为0或1）。任务分配问题可以用一般的整数规划求解方法进行求解。但是，整数规划问题的求解也是非常困难的，到目前为止，还缺乏统一的求解方法。本书采用匈牙利法求解任务分配问题。4二.匈牙利法求解分配问题可以证明，对于分配问题，在其费用矩阵Cij中，
4、各行、各列均减去一个常数，Cij改变以后的最优解，仍为原问题的最优解。利用这个性质，通过对Cij的行、列进行加减常数的计算，把一些矩阵元素变为0，在Cij为0的元素上进行分配，就可得到原问题的最优解。该方法应用了匈牙利数学家Konig矩阵性质定理，因此这种方法被称为匈牙利法。54其他规划问题选址问题货物配装问题物流服务系统中的配置问题6一.选址问题简介物流调运规划问题，是一种有固定发点、固定收点和固定道路的运输规划问题。还有一类运输问题，他的收货点和发货点是待定的，这就是选址问题。这类问题在物流系统规划中经
5、常遇到。选址问题要考虑多种因素，本节只讨论选址问题中的物流问题。分为两个问题：单一地址选址方法；图上作业法。71.单一地址选址方法单一选址问题：就是从多个候选地址中选取一个最优地址。（1）问题描述假设地址候选地点有s个，分别用D1,D2,…,Ds表示；原材料、燃料、零配件的供应地有m个，分别用A1,A2,…,Am表示，其供应量分别用P1,P2,…,Pm表示；产品销售地有n个，分别用B1,B2,…,Bn表示，其销售量分别为Q1,Q2,…,Qn表示。8（2）参数及变量说明设cij为供应地Ai到候选厂址Dj的单位
6、物资运输成本；djk为候选厂址Dj到销售地Bk的单位物资运输成本；设：选址变量为x=(x1,x2,…,xs)，其中：xj=0或1，1表示在Dj点建厂，0表示不在Dj点建厂。9（3）目标函数及约束条件10单一选址问题是一种线性规划问题,并且变量的取值为0或1，属于整数规划问题。单一地址的选址模型的求解方法比较简单．从目标函数表达式的右边可以看出：通过计算模型中括号内的算式值，就能够确定运输成本最小的方案。当要选定的地址不是单一的，而是多个时，问题不再属于线性规划问题。（5）求解方法112.图上作业法对于运输路
7、线不含回路的选址问题，可用图上作业法求解。例题8假定有六个矿井．产量分别为5000吨、6000吨、7000吨、2000吨、4000吨和3000吨，运输路线如图所示，这些矿石要经过加工后才能转运到其他地方。这些矿井之间道路不含回路，欲选择一个矿井，在此矿井上建立一个加工厂，使各矿井到工厂的运输总费用最低。为了便于分析，用一个新的图来代替原图，新图圈内数字表示矿井编号，产量记在圈的旁边，道路交叉点看作产量为零的矿井，把那些只有一条道路连接的矿井称为端点。12首先计算这些矿井的总产量，本例为27000吨。然后分析
8、各端点，都没有超过总产量的一半，因此把各端点的数量合并到前一站，即①和②的数量合并到③；把④的数量合并到⑤；把⑦的数量合并到⑥，如下图所示。3561100090007000各端点都合并到前一站后，③和⑥变成了图中的端点。对它们进行分析,其数量都不超过总产量的一半，所以他们也不是最佳点。再把它们合并到前一站，即把③和⑥的数量合并到⑤。则⑤的数量为27000，超过总量的一半，所以⑤是最佳点。结论：加工厂应建在第5号矿
