1、3 物流分配规划物流分配规划任务分配问题数学模型（重点）任务分配问题数学模型（重点）用匈牙利法求解分配问题（自学）用匈牙利法求解分配问题（自学）1物流分配规划课件第1页一一.任务分配问题任务分配问题1.1.介绍介绍 在物流系统中经常面临一个问题：怎样依据有限资源(人力、物力、财力等)，进行工作任务分配，以到达降低成本或提升经济效益目标。如：v运输任务分配问题。有n条航线运输任务指派给n艘船去完成，不一样船完成不一样航线其运输成本不一样。要求每条船完成一条航线，而且一条航线只能由一条船去完成。怎样分配任务，才能使总费用最小？v又如：有A、B、C、D四门课程，上课老师能够从甲、乙、丙、丁四名老师中
2、选择，不一样老师上不一样课程，其费用是不一样，而且要求，每人只讲一门课程，每门课程只需要一人讲授。问：怎样安排，才能使总上课费用最低？q这类问题是常见任务分配问题任务分配问题，也叫指派问题指派问题，它任务是怎样进行合理任务分配，使总费用最小总费用最小。2物流分配规划课件第2页2.任务分配问题数学模型任务分配问题数学模型q以运输问题n项任务由n个司机去完成情况为例：有n个司机被分配完成n项运输任务，不一样司机完成某一项任务费用都不一样。要求每个司机完成其中一项任务，每个任务只能由一名司机完成，怎样分配任务，才能使总费用最小？令：cij表示第i个司机完成第j项任务运输成本（工作成本或工作时间等价值
3、系数）；xij表示第i个司机去完成第j项任务，其值为1或0。q当其值为1时表示第i个司机被分配去完成第j项任务；q其值为0时，表示第i个司机不被分配去完成第j项任务。3物流分配规划课件第3页3.任务分配问题数学模型求解任务分配问题数学模型求解q任务分配问题属于整数规划问题，其变量xij取值为整数。（本例为0或1）。q任务分配问题能够用普通整数规划求解方法进行求解。不过，整数规划问题求解也是非常困难，到当前为止，还缺乏统一求解方法。q本书采取匈牙利法求解任务分配问题。4物流分配规划课件第4页二二.匈牙利法求解分配问题匈牙利法求解分配问题q能够证实，对于分配问题，在其费用矩阵Cij中，各行、各列均
4、减去一个常数，Cij改变以后最优解，仍为原问题最优解。q利用这个性质，经过对Cij行、列进行加减常数计算，把一些矩阵元素变为0，在Cij为0元素上进行分配，就可得到原问题最优解。q该方法应用了匈牙利数学家Konig矩阵性质定理，所以这种方法被称为匈牙利法。5物流分配规划课件第5页4 其它规划问题其它规划问题选址问题选址问题货物配装问题货物配装问题物流服务系统中配置问题物流服务系统中配置问题6物流分配规划课件第6页一一.选址问题选址问题介绍介绍q物流调运规划问题，是一个有固定发点、固定收点和固定道路运输规划问题。q还有一类运输问题，他收货点和发货点是待定，这就是选址问题。这类问题在物流系统规划中
5、经常碰到。q选址问题要考虑各种原因，本节只讨论选址问题中物流问题。分为两个问题：v单一地址选址方法；v图上作业法。7物流分配规划课件第7页1.单一地址选址方法单一地址选址方法q单一选址问题：就是从多个候选地址中选取一个最优地址。（1）问题描述）问题描述 假设地址候选地点有s个，分别用D1,D2,Ds表示；原材料、燃料、零配件供给地有m个，分别用A1,A2,Am表示，其供给量分别用P1,P2,Pm表示；产品销售地有n个，分别用B1,B2,Bn表示，其销售量分别为Q1,Q2,Qn表示。8物流分配规划课件第8页（2）参数及变量说明）参数及变量说明q设cij为供给地Ai到候选厂址Dj单位物资运输成本；
6、qdjk为候选厂址Dj到销售地Bk单位物资运输成本；q设：选址变量为x=(x1,x2,xs)，其中：xj=0或1，1表示在Dj点建厂，0表示不在Dj点建厂。9物流分配规划课件第9页（3 3）目标函数及约束条件）目标函数及约束条件10物流分配规划课件第10页q单一选址问题是一个线性规划问题,而且变量取值为0或1，属于整数规划问题。q单一地址选址模型求解方法比较简单从目标函数表示式右边能够看出：经经过过计计算算模模型型中中括括号号内内算算式式值值，就就能能够够确确定运输成本最小方案。定运输成本最小方案。q当要选定地址不是单一，而是多个时，问题不再属于线性规划问题。（5 5）求解方法）求解方法11物
7、流分配规划课件第11页2.2.图上作业法图上作业法 对于运输路线不含回路运输路线不含回路选址问题，可用图上作业法求解。例题8 假定有六个矿井产量分别为5000吨、6000吨、7000吨、吨、4000吨和3000吨，运输路线如图所表示，这些矿石要经过加工后才能转运到其它地方。这些矿井之间道路不含回路，欲选择一个矿井，在此矿井上建立一个加工厂，使各矿井到工厂运输总费用最低。为了便于分析，用一个新图来代替原图，新图圈内数字表示矿井编号，产量记在圈旁边，道路交叉点看作产量为零矿井，把那些只有一条道路连接矿井称为端点。12物流分配规划课件第12页q首先计算这些矿井总产量，本例为2700027000吨。q
8、然后分析各端点，都没有超出总产量二分之一，所以把各端点数量合并到前一站，即 和 数量合并到；把数量合并到；把 数量合并到，以下列图所表示。3561100090007000q各端点都合并到前一站后，和变成了图中端点。对它们进行分析,其数量都不超出总产量二分之一，所以他们也不是最正确点。q再把它们合并到前一站，即把和数量合并到。则 数量为27000，超出总量二分之一，所以是最正确点。q结论：加工厂应建在第5号矿井。13物流分配规划课件第13页二二.货物配装货物配装 货物配装目标是在车辆载重量为额定值情况下，合理进行货物安排，使车辆装载货物价值最大（如：重量最大、运费最低等）。14物流分配规划课件第
9、14页1.1.装货问题数学模型装货问题数学模型（1）问题描述）问题描述 设货车载重量上限为G，用于运输n种不一样货物，货物重量分别为W1，W2，.，Wn，每一个货物对应于一个价值系数，分别用P1，P2，.，Pn表示，它表示价值、运费或重量等。（2）数学模型）数学模型 设Xk表示第k种货物装入数量，货物配装问题数学模型能够表示为：15物流分配规划课件第15页（3 3）求解方法）求解方法v能够把装入一件货物作为一个阶段，把装货问题看作动态规划问题。v普通情况下，动态规划问题求解过程是从最终一个阶段开始由后向前进行。v因为装入货物先后次序不影响装货问题最优解。能够从第一阶段开始，由前向后逐步进行。（
10、4 4）求解过程）求解过程1）装入第1种货物X1件，其最大价值为 其中：X1表示第1种货物装载数量；其取值范围：0X1 G/W1，方括号表示取整；P1：第1种货物价值系数（重量、运费、价值等）；f1(W)：第一个货物价值。16物流分配规划课件第16页 2)装入第2种货物X2件，其最大价值为 其中：X2表示第2种货物装载数量；其取值范围：0X2 G/W2；P2：第2种货物价值系数（重量、运费、价值等）；：第一个货物重量；：第一个货物价值。3）装入第3种货物X3件，其最大价值为 其中：X3表示第3种货物装载数量；其取值范围：0X3 G/W3；P3：第3种货物价值系数；：前两种货物重量；：前两种货物
11、价值。17物流分配规划课件第17页n)装入第n种货物Xn件，其最大价值为 其中：Xn表示第n种货物装载数量；其取值范围：0Xn G/Wn；Pn：第n种货物价值系数；18物流分配规划课件第18页 例题9 载重量为8t载重汽车，运输4种机电产品，产品重量分别为3吨、3吨、4吨、5吨，试问怎样配装才能充分利用货车运载能力?解：第一步，按照前面公式，分成四个阶段计算每一阶段价值。第一步，按照前面公式，分成四个阶段计算每一阶段价值。计算结果以表格表示以下：（5）货物配装例题求解19物流分配规划课件第19页载重量件数价值(重量)载重量第2种货物件数第1种货物重量价值计算价值Max20物流分配规划课件第20
12、页载重量第3种货物件数第1、2种货物重量价值计算价值Max21物流分配规划课件第21页第二步：寻找最优方案。第二步：寻找最优方案。q寻找最优解方案次序与计算次序相反，由第4阶段向第1阶段进行。q选择最终一个阶段价值最大装载情况，逐步向前寻找最优方案。22物流分配规划课件第22页载重量第3种货物件数第1、2种货物重量价值计算价值24物流分配规划课件第24页载重量第2种货物件数第1种货物重量价值计算价值Max25物流分配规划课件第25页27物流分配规划课件第27页最终最优装载方案为：第一组：X X1 1=1=1，X X2 2=0=0，X X3 3=0=0，X X4 4=1=1；第二组：X X1 1
13、=0=0，X X2 2=1=1，X X3 3=0=0，X X4 4=1=1；第三组：X X1 1=0=0，X X2 2=0=0，X X3 3=2=2，X X4 4=0=0；以上三组装载方案，都最大程度地发挥了车辆载重能力，都是最优方案。28物流分配规划课件第28页2.2.品种混装问题品种混装问题（1）品种混装问题介绍）品种混装问题介绍v在实际物流过程中，储运仓库(或货运车站)要把客户所需零担货物组成整车，运往各地。v不一样客户货物，要分别在一站或多站卸货。v在装货、运输和卸货过程中，为了降低装卸、运输过程中出现差错，普通要按照品种、形状、颜色、规格、抵达地点，把货物分为若干类，在装车时分别进行
14、处理。这就是品种混装品种混装问题。29物流分配规划课件第29页（2）品种混装问题描述）品种混装问题描述v设装车货物能够分为1类，2类，m类。共有N件待运货物。其中：第1类货物有N1件，它们重量分别G11，G12，G1N1；第2类货物有N2件，它们重量分别为G21，G22，G2N2；第s类货物共有Ns件，它们重量分别为Gs1，Gs2，GsNs；以这类推，能够看出：货物总件数：货物总件数：其中，Ns：第s类货物件数；m：货物种类数；N：货物总件数；30物流分配规划课件第30页（3 3）数学模型）数学模型 品种混装问题要求同一货车内每类货物至多装入一件，在此假设条件下，能够建立品种混装问题数学模型：
15、设：其中m：货物类别数；Nr：第r类货物件数；Grs：第r类第s件货物重量；G0：货车载重量上限。31物流分配规划课件第31页（4 4）求解方法）求解方法q品种混装问题数学模型属于整数规划问题，能够用单纯形法进行求解q动态规划法 图5-20表示8件货物分为4类混装网络示意图。在图中同一列方框表示同一类货物，方框内数字(符号)表示货物重量。上述品品种种混混装装问问题题就就是是在在网网络络中中自自右右向向左左寻寻找找一一条条路路线线，使使路路线线所所经经过过方方框中重量之和到达最大，但又不超出货车载重量上限框中重量之和到达最大，但又不超出货车载重量上限GoGo。v能够用穷举法求解。v假如将四类货物
16、看作4个阶段，将上述问题化为动态规划问题求解。32物流分配规划课件第32页（5 5）求解实例）求解实例 例题10 货车载重量上限Go50；第1类货物2件，G11=20，G12=11；第2类货物1件，G21=13；第3类货物3件，G316，G3211，G338；第4类货物2件，G4119，G4217。19176118132011 计算过程见表5-3134，分成四个阶段进行。33物流分配规划课件第33页可装重量实装重量剩下容量第1阶段可装容量W值对应第2阶段剩下容量W-G装载情况计算表装载情况计算表34物流分配规划课件第34页可装重量实装重量剩下容量第1阶段可装容量W值对应第2阶段剩下容量W-G最
17、优解寻找过程最优解寻找过程35物流分配规划课件第35页最终最优解为：G1=20 G2=0 G3=11 G4=19 G1=20 G2=13 G3=0 G4=17每组方案装载量都是50，到达满载，充分利用了货车装载能力。37物流分配规划课件第37页三三.物流服务系统中配置问题物流服务系统中配置问题q随机服务系统v物流服务系统由服务机构和用户组成。v物流服务系统是一个综合服务系统，许多服务项目含有随机性质。如：装卸系统、运输系统。v物流服务系统中用户（人、货物等）到来时间和服务时间随不一样时机和条件而改变，这种改变含有随机性质，这类系统称为随机服务系统。v随机服务系统包含三个过程：用户输入、排队、服
18、务三个过程。v排队论是处理随机服务系统专门理论。q服务系统中设备配置v服务机构越大，用户越方便，但机构过大，造成成本升高或浪费。v服务机构过小，便不能完全满足用户需要，使服务质量降低，造成信誉损失和用户流失。v合理配置服务系统，使他既能满足用户需要，又能使系统花费最为经济，是物流系统配置所关心主要问题。38物流分配规划课件第38页本章重点本章重点q物流调运规划物流调运规划v表上作业法确定产、销地之间供需联络和数量最优搭配表上作业法确定产、销地之间供需联络和数量最优搭配v图上作业法进行运输线路选择图上作业法进行运输线路选择v最短路径与最大流量最短路径与最大流量q分配规划分配规划q选址问题选址问题q货物配装货物配装39物流分配规划课件第39页
