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

1、5.3 物流分配规划义务分配问题的数学模型用匈牙利法求解分配问题一. 义务分配问题的数学模型在物流系统中或其它的管理任务中，管理人员经常面临的一个问题是：如何根据有限的资源(人力、物力、财力等)，进展任务义务分配，以到达降低本钱或提高经济效益的目的。如：有A、B、C、D四门课程，上课的教师可以从甲、乙、丙、丁四名教师中选择，不同的教师上不同的课程，其费用是不同的，并且规定，每人只讲一门课程，每门课程只需求一人讲授。问：如何安排，才干使总的上课费用最低？又如：运输义务的分配问题。有n条航线的运输义务指派给n艘船去完成，不同的船完成不同的航线其运输本钱不同。要求每条船完成一条航线，并且一条航线只能

2、由一条船去完成。如何分配义务，才干使总的费用最小？这类问题是常见的义务分配问题，也叫指派问题，它的义务是如何进展合理的义务分配，使总的费用最小。一. 义务分配问题的数学模型以运输问题的n项义务由n个司机去完成的情况为例，有n个司机被分配完成n项运输义务，不同的司机完成义务某一项义务的费用都不一样。要求每个司机完成其中一项义务，每个义务只能由一名司机完成，如何分配义务，才干使总的费用最小？ 令： cij表示第i个司机完成第j项义务的运输本钱任务本钱或任务时间等价值系数； xij表示第i个司机去完成第j项义务，其值为1或0。当其值为1时表示第i个司机被分配去完成第j项义务；其值为0时，表示第i个司

3、机不被分配去完成第j项义务。一. 义务分配问题的数学模型义务分配问题属于整数规划问题，其变量xij的取值为整数，本例为0或1。义务分配问题可以用普通的整数规划求解方法进展求解。但是，整数规划问题的求解也是非常困难的，到目前为止，还缺乏一致的求解方法。本书采用匈牙利法求解义务分配问题。二. 匈牙利法求解分配问题可以证明，对于分配问题，在其费用矩阵Cij中，各行、各列均减去一个常数，Cij改动以后的最优解，仍为原问题的最优解。利用这个性质，经过对Cij的行、列进展加减常数的计算，把一些矩阵元素变为0，在Cij为0的元素上进展分解，就可得到原问题的最优解。该方法运用了匈牙利数学家Konig矩阵性质定

4、理，因此这种方法被称为匈牙利法。5.4 其他规划问题选址问题货物装配问题物流效力系统中的配置问题一. 选址问题物流调运规划问题，是一种有固定发点、固定收点和固定道路的运输规划问题。还有一类运输问题，他的收货点和发货点是待定的，这就是选址问题。这类问题在物流系统规划中经常遇到。选址问题要思索多种要素，本节只讨论选址问题中的物流问题。分为两个问题：单一地址选址方法；图上作业法。1. 单一地址选址方法 建立一个新工厂或仓库，应合理选择厂址或库址。所谓选址问题，就是从多个候选厂址中选取一个最优地址建厂，使物流费用到达最低。 问题描画：假设厂址候选地点有s个，分别用D1,D2,Ds表示；原资料、燃料、零

5、配件的供应地有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点建厂。单一选址问题是一种线性规划问题,并且变量的取值为0或1，属于整数规划问题。单一地址的选址模型的求解方法比较简单从目的函数表达式的右边可以看出：经过计算模型中括号内的算式值，就可以确定运输本钱最小的方案。当要选定的地址不是单一的，而是多个时

6、，问题不再属于线性规划问题。2. 图上作业法 对于运输道路不含回路的选址问题，可用图上作业法求解。 下面以一个实践例子来阐明图上作业法的选址问题： 例题8 假定有六个矿井产量分别为5000吨、6000吨、7000吨、2000吨、4000吨和3000吨，运输道路如下图，这些矿石要经过加工后才干转运到其他地方。这些矿井之间道路不含回路，欲选择一个矿井，在此矿井上建立一个加工厂，使各矿井到工厂的运输总费用最低。 为了便于分析，用一个新的图来替代原图，新图圈内数字表示矿井编号，产量记在圈的旁边，道路交叉点看作产量为零的矿井，把那些只需一条道路衔接的矿井称为端点。首先计算这些矿井的总产量，本例为2700

7、0吨。然后分析各端点，都没有超越总产量的一半，因此把各端点的数量合并到前一站，即 和 的数量合并到；把的数量合并到 ；把 的数量合并到 ，如以下图所示。3561100090007000各端点都合并到前一站后， 和变成了图中的端点。对它们进展分析其数量都不超越总产量的一半，所以他们不是最正确点。再把它们合并到前一站，即把和的数量合并到 。那么 的数量为27000，超越总量的一半，所以是最正确点。结论：加工厂应建在第5号矿井。 二. 货物装配 货物配装的目的是在车辆载分量为额定值的情况下，合理进展货物的安排，使车辆装载货物的价值最大如：分量最大、运费最低等。 1. 运用动态规划解装货问题 设货车的

8、载分量上限为G，用于运送n种不同的货物，货物的分量分别为W1，W2，.，Wn，每一种货物对应于一个价值系数，分别用P1，P2，.，Pn表示，它表示价值、运费或分量等。设Xk表示第k种货物的装入数量，货物配装问题的数学模型可以表示为： 可以把装入一件货物作为一个阶段，把装货问题看作动态规划问题。普通情况下，动态规划问题的求解过程是从最后一个阶段开场由后向前进展的。由于装入货物的先后次序不影响装货问题的最优解。所以我们的求解过程可以从第一阶段开场，由前向后逐渐进展。求解过程：1装入第1种货物X1件，其最大价值为 其中：X1表示第1种货物的装载数量；其取值范围：0X1 G/W1 ，方括号表示取整；

9、P1：第1种货物的价值系数分量、运费、价值等； f1(W)：第一种货物的价值。 (2)装入第2种货物X2件，其最大价值为 其中：X2表示第2种货物的装载数量； 其取值范围：0X2 G/W2 ； P2：第2种货物的价值系数分量、运费、价值等； ：第一种货物的分量； ：第一种货物的价值。3装入第3种货物X3件，其最大价值为 其中：X3表示第3种货物的装载数量； 其取值范围：0X3 G/W3； P3：第3种货物的价值系数；(n) 装入第n种货物Xn件，其最大价值为 其中：Xn表示第n种货物的装载数量； 其取值范围：0Xn G/Wn ； Pn：第n种货物的价值系数；例题9 载分量为8t的载重汽车，运输

10、4种机电产品，产品分量分别为3吨、3吨、4吨、5吨，试问如何配装才干充分利用货车的运载才干?解： 第一步，按照前面的公式，分成四个阶段计算每一阶段的价值。 计算结果以表格表示如下：货物装配例题载分量件数价值(分量)载分量第2种货物的件数第1种货物的分量价值计算价值Max载分量第3种货物的件数第1、2种货物的分量价值计算价值Max第二步：寻觅最优方案。寻觅最优解方案的次序与计算顺序相反，由第4阶段向第1阶段进展。从价值最大的装载情况，逐渐向前寻觅最优方案。1在第4阶段计算表中，在载分量为8时，价值(本例为载分量)最大值f4(W)8，对应两组数据(加*号的数据)： 1X40； 2X41； 先看X4

11、1时的情况： 当X41时，即第4种货物装入1件(5吨)，表中第3列数字表示其他种类货物的装载量。当X41时，其他3种货物装载量为3吨；2按相反方向，在第3阶段计算表中，查W=3吨时，得到最大价值f3(W)3，对应的X3=0。查表中第3列数字，W=3，X3=0时，其他两类货物装入分量3；3在第2阶段计算表中，查W=3，f2(W)=3对应两组数据： 1X2=0； 2) X2=1； 即 当X2 =1或0时，其他(第1种)货物装载量为3或0；4查第1阶段计算表， 1当W3时，对应X1=1； 2当W0时，对应X1=0；根据当前面的寻觅过程，可以得到两组最优解： 第一组：X1=1，X2=0，X3=0，X4

12、=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 前面的最优方案是在第四阶段取X41时得出的方案。 假设在第4阶段计算表中取X40，那么其他种类的货物装载量W - W4X4=8； 在第3阶段计算表中，查W=8一栏，f3(w)=8对应X32，再仿照前面的方法，可以得到第3组最优解： 第三组：X1=0，X2=0，X3=2，X4=0； 装载量为：X3 * 2 = 2*4 = 8以上三组装载方案，都最大限制地发扬了车辆的载重才干，都

13、是最优方案。最终的最优装载方案为： 第一组：X1=1，X2=0，X3=0，X4=1； 第二组：X1=0，X2=1，X3=0，X4=1； 第三组：X1=0，X2=0，X3=2，X4=0；2. 种类混装问题在实践的物流过程中，储运仓库(或货运车站)要把客户所需的货物组成整车，运往各地。不同客户的货物，要分别在一站或多站卸货。在装货、运输和卸货过程中，为了减少装卸、运输过程中出现过失，普通要按照种类、外形、颜色、规格、到达地点，把货物分为假设干类，在装车时分别进展处置。这就是种类混装问题。设装车的货物可以分为1类，2类，m类。共有N件(捆)待运货物，其中1类货物有N1件(捆)，它们的分量分别G11，

14、G12，G1N1；2类货物有N2件(捆)，它们的分量分别为G21，G22，G2N2；第s类货物共有Ns件，它们的分量分别为Gs1，Gs2，GsNs；以此类推，可以看出：货物总的件数： 其中，Ns：第s类货物的件数； m：货物的种类数； N：货物的总件数； 设： 种类混装问题要求同一货车内每类货物至多装入一件捆，同一客户的多件同类货物可记作一件捆。在这样的假设条件下，可以把种类混装问题的数学模型表示如下：该数学模型的目的是对合理进展分类后的货物进展装载，使实践载分量G的值最大。该数学模型属于整数规划的问题，可以用单纯形法进展求解。其中m：货物的类别数；Nr：第r类货物的件数；Grs：第r类第s件

15、货物的分量；G0：货车载分量的上限。 图5-20表示8件货物分为4类，在图中同一列的方框表示同一类货物，方框内的数字(符号)表示货物分量。 上述种类混装问题就是在网络中自右向左寻觅一条道路，使道路所经过的方框中的分量之和到达最大，但又不超越货车的载分量的上限Go。这种问题可以用穷举法求解，即比较各条道路的载分量从而求出不超越Go的最大装载量的道路；也可以将四类货物看作4个阶段，将上述问题化为动态规划问题求解。下面引见动态规划的解法。 例题10 货车载分量上限Go50；第1类货物2件，G11=20，G12=11；第2类货物1件，G21=13；第3类货物3件，G316，G3211，G338；第4类

16、货物2件，G4119，G4217。19176118132011 计算过程见表5-3134，分成四个阶段进展。可装分量实装分量剩余容量第1阶段的可装容量W值对应第2阶段的剩余容量W-G 寻觅最优解的次序与计算顺序相反，从第一阶段计算表开场，直到第四阶段。 要使装载量到达最大，对应的剩余余量该当最小。 1在第一阶段计算表中，余量W-G1的最小值为零，为最好的方案，此时，对应的实践装载量G1为20，可装载容量W值为20。 2第一阶段的可装载容量W=20为第二阶段的剩余装载容量，即W-G2的值为20，从表中可以看出第二阶段的剩余装载容量为20的实践装载方式有两种，分别是： G2=0 和 G2=13 对

17、应的可装容量分别为W=20和33。 3第二阶段的可装容量W=20和33为第三阶段的剩余装载容量，查表可得： 对应于剩余可装载容量为20的实践装载量为G3=11,可装载容量为W=31。 对应于剩余可装载容量为33的实践装载量为G3=0,可装载容量为W=33。 4同理可得第四阶段的G4为19和17。 最后的最优解为：G1=20 G2=0 G3=11 G4=19 G1=20 G2=13 G3=0 G4=17每组方案的装载量都是50，到达满载，充分利用了货车的装载才干。可装分量实装分量剩余容量第1阶段的可装容量W值对应第2阶段的剩余容量W-G三. 物流效力系统中的配置问题随机效力系统物流效力系统由效力

18、的机构和顾客组成。物流效力系统是一个综合效力系统，许多效力工程具有随机性质。如：装卸系统、运输系统。物流效力系统中的顾客人、货物等到来的时间和效力时间随不同的时机和条件而变化，这种变化具有随机性质，这类系统称为随机效力系统。随机效力系统包含三个过程：顾客输入、排队、效力三个过程。排队论是处置随机效力系统的专门实际。效力系统中的设备配置效力机构越大，顾客越方便，但机构过大，导致本钱升高或浪费。效力机构过小，便不能完全满足顾客的需求，使效力质量降低，导致信誉损失和顾客流失。合理配置效力系统，使他既能满足顾客的需求，又能使系统的破费最为经济，是物流系统配置所关怀的主要问题。例题， (P110)，按某仓库的统计数听阐明，该仓库必要的车辆数量有一定的分布规律，如表5-35和图5-21所示。每台车辆每天的费用如下：自备车辆运