第5章物流系统规划(二)

物流系统工程——物流系统规划15.3物流分配规划任务分配问题的数学模型用匈牙利法求解分配问题物流系统工程——第5章物流系统规划2一.任务分配问题的数学模型在物流系统中或其它的管理工作中，管理人员经常面临的一个问题是：如何根据有限的资源(人力、物力、财力等)，进行工作任务分配，以达到降低成本或提高经济效益的目的。如：有A、B、C、D四门课程，上课的老师可以从甲、乙、丙、丁四名老师中选择，不同的老师上不同的课程，其费用是不同的，并且规定，每人只讲一门课程，每门课程只需要一人讲授。问：如何安排，才能使总的上课费用最低？又如：运输任务的分配问题。有n条航线的运输任务指派给n艘船去完成，不同的船完成不同的航线其运输成本不同。要求每条船完成一条航线，并且一条航线只能由一条船去完成。如何分配任务，才能使总的费用最小？这类问题是常见的任务分配问题，也叫指派问题，它的任务是如何进行合理的任务分配，使总的费用最小。物流系统工程——第5章物流系统规划3一.任务分配问题的数学模型以运输问题的n项任务由n个司机去完成的情况为例，有n个司机被分配完成n项运输任务，不同的司机完成任务某一项任务的费用都不一样。要求每个司机完成其中一项任务，每个任务只能由一名司机完成，如何分配任务，才能使总的费用最小？1011..1111或ijniijnjijniniijijxxxtsxcMinZ令：cij表示第i个司机完成第j项任务的运输成本（工作成本或工作时间等价值系数）；xij表示第i个司机去完成第j项任务，其值为1或0。当其值为1时表示第i个司机被分配去完成第j项任务；其值为0时，表示第i个司机不被分配去完成第j项任务。物流系统工程——第5章物流系统规划4一.任务分配问题的数学模型任务分配问题属于整数规划问题，其变量xij的取值为整数，（本例为0或1）。任务分配问题可以用一般的整数规划求解方法进行求解。但是，整数规划问题的求解也是非常困难的，到目前为止，还缺乏统一的求解方法。本书采用匈牙利法求解任务分配问题。物流系统工程——第5章物流系统规划5二.匈牙利法求解分配问题可以证明，对于分配问题，在其费用矩阵Cij中，各行、各列均减去一个常数，Cij改变以后的最优解，仍为原问题的最优解。利用这个性质，通过对Cij的行、列进行加减常数的计算，把一些矩阵元素变为0，在Cij为0的元素上进行分解，就可得到原问题的最优解。该方法应用了匈牙利数学家Konig矩阵性质定理，因此这种方法被称为匈牙利法。物流系统工程——物流系统规划65.4其他规划问题选址问题货物装配问题物流服务系统中的配置问题物流系统工程——第5章物流系统规划7一.选址问题物流调运规划问题，是一种有固定发点、固定收点和固定道路的运输规划问题。还有一类运输问题，他的收货点和发货点是待定的，这就是选址问题。这类问题在物流系统规划中经常遇到。选址问题要考虑多种因素，本节只讨论选址问题中的物流问题。分为两个问题：单一地址选址方法；图上作业法。物流系统工程——第5章物流系统规划81.单一地址选址方法建立一个新工厂（或仓库），应合理选择厂址（或库址）。所谓选址问题，就是从多个候选厂址中选取一个最优地址建厂，使物流费用达到最低。问题描述：假设厂址候选地点有s个，分别用D1,D2,…,Ds表示；原材料、燃料、零配件的供应地有m个，分别用A1,A2,…,Am表示，其供应量分别用P1,P2,…,Pm表示；产品销售地有n个，分别用B1,B2,…,Bn表示，其销售量分别为Q1,Q2,…,Qn表示。设cij为供应地Ai到候选厂址Dj的单位运输成本；djk为候选厂址Dj到销售地Bk的单位运输成本；设选址变量为xj(j=1,2,…,s)，其中：xj=0或1，1表示在Dj点建厂，0表示不在Dj点建厂。011minDBDDc运输DA11111111jkj1jji或以表示为：选址问题的数学模型可为：所有候选地的运输成本费用为：到所有的销售地的运输候选地的运输费用为：到销售地从候选地的运输费用为：所有的供应点到候选地费用为：点的到候选地从供应点jsjjjsjnkkjkmiiijsjnkjkjkmijiijnkjkjkjkjkmijiijjiijxxs.t.x)QdPc(Z)xQdxPc(xQdxQdxPcxP单一选址问题是一种线性规划问题,并且变量的取值为0或1，属于整数规划问题。单一地址的选址模型的求解方法比较简单．从目标函数表达式的右边可以看出：通过计算模型中括号内的算式值，就能够确定运输成本最小的方案。当要选定的地址不是单一的，而是多个时，问题不再属于线性规划问题。物流系统工程——第5章物流系统规划122.图上作业法对于运输路线不含回路的选址问题，可用图上作业法求解。下面以一个实际例子来说明图上作业法的选址问题：例题8假定有六个矿井．产量分别为5000吨、6000吨、7000吨、2000吨、4000吨和3000吨，运输路线如图所示，这些矿石要经过加工后才能转运到其他地方。这些矿井之间道路不含回路，欲选择一个矿井，在此矿井上建立一个加工厂，使各矿井到工厂的运输总费用最低。为了便于分析，用一个新的图来代替原图，新图圈内数字表示矿井编号，产量记在圈的旁边，道路交叉点看作产量为零的矿井，把那些只有一条道路连接的矿井称为端点。首先计算这些矿井的总产量，本例为27000吨。然后分析各端点，都没有超过总产量的一半，因此把各端点的数量合并到前一站，即①和②的数量合并到③；把④的数量合并到⑤；把⑦的数量合并到⑥，如下图所示。3561100090007000各端点都合并到前一站后，③和⑥变成了图中的端点。对它们进行分析．其数量都不超过总产量的一半，所以他们不是最佳点。再把它们合并到前一站，即把②和⑥的数量合并到⑤。则⑤的数量为27000，超过总量的一半，所以⑤是最佳点。结论：加工厂应建在第5号矿井。物流系统工程——第5章物流系统规划14二.货物装配货物配装的目的是在车辆载重量为额定值的情况下，合理进行货物的安排，使车辆装载货物的价值最大（如：重量最大、运费最低等）。物流系统工程——第5章物流系统规划151.运用动态规划解装货问题设货车的载重量上限为G，用于运送n种不同的货物，货物的重量分别为W1，W2，...，Wn，每一种货物对应于一个价值系数，分别用P1，P2，...，Pn表示，它表示价值、运费或重量等。设Xk表示第k种货物的装入数量，货物配装问题的数学模型可以表示为：),...,1(0..)(max11nkXGXWtsXPxfkknkknkkk可以把装入一件货物作为一个阶段，把装货问题看作动态规划问题。一般情况下，动态规划问题的求解过程是从最后一个阶段开始由后向前进行的。由于装入货物的先后次序不影响装货问题的最优解。所以我们的求解过程可以从第一阶段开始，由前向后逐步进行。求解过程：（1）装入第1种货物X1件，其最大价值为111max)(XPWf其中：X1表示第1种货物的装载数量；其取值范围：0X1[G/W1]，方括号表示取整；P1：第1种货物的价值系数（重量、运费、价值等）；f1(W)：第一种货物的价值。(2)装入第2种货物X2件，其最大价值为其中：X2表示第2种货物的装载数量；其取值范围：0X2[G/W2]；P2：第2种货物的价值系数（重量、运费、价值等）；：第一种货物的重量；：第一种货物的价值。（3）装入第3种货物X3件，其最大价值为其中：X3表示第3种货物的装载数量；其取值范围：0X3[G/W3]；P3：第3种货物的价值系数；)(max)(221222XWWfXPwf22XWW)(221XWWf)(max)(332333XWWfXPwf……(n)装入第n种货物Xn件，其最大价值为其中：Xn表示第n种货物的装载数量；其取值范围：0Xn[G/Wn]；Pn：第n种货物的价值系数；)(max)(1nnnnnnXWWfXPwf例题9载重量为8t的载重汽车，运输4种机电产品，产品重量分别为3吨、3吨、4吨、5吨，试问如何配装才能充分利用货车的运载能力?解：第一步，按照前面的公式，分成四个阶段计算每一阶段的价值。计算结果以表格表示如下：货物装配例题载重量件数价值(重量)载重量第2种货物的件数第1种货物的重量价值计算价值Max载重量第3种货物的件数第1、2种货物的重量价值计算价值Max第二步：寻找最优方案。寻找最优解方案的次序与计算顺序相反，由第4阶段向第1阶段进行。从价值最大的装载情况，逐步向前寻找最优方案。（1）在第4阶段计算表中，在载重量为8时，价值(本例为载重量)最大值f4(W)＝8，对应两组数据(加*号的数据)：1）X4＝0；2）X4＝1；先看X4＝1时的情况：当X4＝1时，即第4种货物装入1件(5吨)，表中第3列数字表示其余种类货物的装载量。当X4＝1时，其他3种货物装载量为3吨；（2）按相反方向，在第3阶段计算表中，查W=3吨时，得到最大价值f3(W)＝3，对应的X3=0。查表中第3列数字，W=3，X3=0时，其余两类货物装入重量3；（3）在第2阶段计算表中，查W=3，f2(W)=3对应两组数据：1）X2=0；2)X2=1；即当X2=1或0时，其他(第1种)货物装载量为3或0；（4）查第1阶段计算表，1）当W＝3时，对应X1=1；2）当W＝0时，对应X1=0；根据当前面的寻找过程，可以得到两组最优解：第一组：X1=1，X2=0，X3=0，X4=1；第二组：X1=0，X2=1，X3=0，X4=1；这两组最优解的实际载重量为：第一组：X1*3+X4*5=1*3+1*5=8第二组：X2*3+X4*5=1*3+1*5=8前面的最优方案是在第四阶段取X4＝1时得出的方案。如果在第4阶段计算表中取X4＝0，则其余种类的货物装载量W-W4X4=8；在第3阶段计算表中，查W=8一栏，f3(w)=8对应X3＝2，再仿照前面的方法，可以得到第3组最优解：第三组：X1=0，X2=0，X3=2，X4=0；装载量为：X3*2=2*4=8以上三组装载方案，都最大限度地发挥了车辆的载重能力，都是最优方案。最终的最优装载方案为：第一组：X1=1，X2=0，X3=0，X4=1；第二组：X1=0，X2=1，X3=0，X4=1；第三组：X1=0，X2=0，X3=2，X4=0；物流系统工程——第5章物流系统规划272.品种混装问题在实际的物流过程中，储运仓库(或货运车站)要把客户所需的货物组成整车，运往各地。不同客户的货物，要分别在一站或多站卸货。在装货、运输和卸货过程中，为了减少装卸、运输过程中出现差错，一般要按照品种、形状、颜色、规格、到达地点，把货物分为若干类，在装车时分别进行处理。这就是品种混装问题。设装车的货物可以分为1类，2类，…，m类。共有N件(捆)待运货物，其中1类货物有N1件(捆)，它们的重量分别G11，G12，……，G1N1；2类货物有N2件(捆)，它们的重量分别为G21，G22，……，G2N2；第s类货物共有Ns件，它们的重量分别为Gs1，Gs2，……，GsNs；以此类推，可以看出：货物总的件数：其中，Ns：第s类货物的件数；m：货物的种类数；N：货物的总件数；设：品种混装问题要求同一货车内每类货物至多装入一件（捆），同一客户的多件同类货物可记作一件（捆）。在这样的假设条件下，可以把品种混装问题的数学模型表示如下：msNNmss,....,2,11件货物不装入类第第件货物装入类第第srsrXrs01该数学模型的目的是对合理进行分类后的货物进行装载，使实际载重量G的值最大。该数学模型属于整数规划的问题，可以用单纯形法进行求解。mrNsrsrsmsrsmrNsrsrsrrGXGmrXtsXGG110111,...,2,11..max其中m：货物的类别数；Nr：第r