分享
分销 收藏 举报 申诉 / 39

类型第3-2章-物流系统规划(二).ppt

  • 上传人:仙人****88
  • 文档编号:14772567
  • 上传时间:2026-11-19
  • 格式:PPT
  • 页数:39
  • 大小:448.50KB
  • 下载积分:10 金币
  • 配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    物流 系统 规划
    资源描述:
    ,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,物流系统工程,第,5,章 物流系统规划,3,物流分配规划,任务分配问题的数学模型(重点),用匈牙利法求解分配问题(自学),1,一,.,任务分配问题,1.,简介,在物流系统中经常面临的一个问题:如何根据有限的资源,(,人力、物力、财力等,),,进行工作任务分配,以达到降低成本或提高经济效益的目的。如:,运输任务的分配问题。有,n,条航线的运输任务指派给,n,艘船去完成,不同的船完成不同的航线其运输成本不同。要求每条船完成一条航线,并且一条航线只能由一条船去完成。如何分配任务,才能使总的费用最小?,又如:有,A,、,B,、,C,、,D,四门课程,上课的老师可以从甲、乙、丙、丁四名老师中选择,不同的老师上不同的课程,其费用是不同的,并且规定,每人只讲一门课程,每门课程只需要一人讲授。问:如何安排,才能使总的上课费用最低?,这类问题是常见的,任务分配问题,,也叫,指派问题,,它的任务是如何进行合理的任务分配,使,总的费用最小,。,2,2.,任务分配问题的数学模型,以运输问题的,n,项任务由,n,个司机去完成的情况为例:有,n,个司机被分配完成,n,项运输任务,不同的司机完成某一项任务的费用都不一样。要求每个司机完成其中一项任务,每个任务只能由一名司机完成,如何分配任务,才能使总的费用最小?,令:,c,ij,表示第,i,个司机完成第,j,项任务的运输成本(工作成本或工作时间等价值系数);,x,ij,表示第,i,个司机去完成第,j,项任务,其值为1或0。,当其值为1时表示第,i,个司机被分配去完成第,j,项任务;,其值为0时,表示第,i,个司机不被分配去完成第,j,项任务。,3,3.,任务分配问题数学模型的求解,任务分配问题属于整数规划问题,其变量,x,ij,的取值为整数。(本例为,0,或,1,)。,任务分配问题可以用一般的整数规划求解方法进行求解。但是,整数规划问题的求解也是非常困难的,到目前为止,还缺乏统一的求解方法。,本书采用匈牙利法求解任务分配问题。,4,二,.,匈牙利法求解分配问题,可以证明,对于分配问题,在其费用矩阵,C,ij,中,各行、各列均减去一个常数,,C,ij,改变以后的最优解,仍为原问题的最优解。,利用这个性质,通过对,C,ij,的行、列进行加减常数的计算,把一些矩阵元素变为,0,,在,C,ij,为,0,的元素上进行分配,就可得到原问题的最优解。,该方法应用了匈牙利数学家,Konig,矩阵性质定理,因此这种方法被称为匈牙利法。,5,4,其他规划问题,选址问题,货物配装问题,物流服务系统中的配置问题,6,一,.,选址问题,简介,物流调运规划问题,是一种有固定发点、固定收点和固定道路的运输规划问题。,还有一类运输问题,他的收货点和发货点是待定的,这就是选址问题。这类问题在物流系统规划中经常遇到。,选址问题要考虑多种因素,本节只讨论选址问题中的物流问题。分为两个问题:,单一地址选址方法;,图上作业法。,7,1.,单一地址选址方法,单一选址问题:就是从多个候选地址中选取一个最优地址。,(,1,)问题描述,假设地址候选地点有,s,个,分别用,D,1,D,2,D,s,表示;原材料、燃料、零配件的供应地有,m,个,分别用,A,1,A,2,A,m,表示,其供应量分别用,P,1,P,2,P,m,表示;产品销售地有,n,个,分别用,B,1,B,2,B,n,表示,其销售量分别为,Q,1,Q,2,Q,n,表示。,8,(,2,)参数及变量说明,设,c,ij,为,供应,地,A,i,到,候选厂址,D,j,的单位物资运输成本;,d,jk,为,候选厂址,D,j,到,销售地,B,k,的单位物资运输成本;,设:选址变量为,x=,(x,1,x,2,x,s,),,,其中:,x,j,=0,或,1,,,1,表示在,D,j,点建厂,,0,表示不在,D,j,点建厂,。,9,(,3)目标函数及约束条件,10,单一选址问题是一种线性规划问题,并且变量的取值为,0,或,1,,属于整数规划问题,。,单一地址的选址模型的求解方法比较简单从目标函数表达式的右边可以看出:,通过计算模型中括号内的算式值,就能够确定运输成本最小的方案。,当要选定的地址不是单一的,而是多个时,问题不再属于线性规划问题。,(,5)求解方法,11,2.,图上作业法,对于,运输路线不含回路,的选址问题,可用图上作业法求解。,例题,8,假定有六个矿井产量分别为,5000,吨、,6000,吨、,7000,吨、,2000,吨、,4000,吨和,3000,吨,运输路线如图所示,这些矿石要经过加工后才能转运到其他地方。这些矿井之间道路不含回路,欲选择一个矿井,在此矿井上建立一个加工厂,使各矿井到工厂的运输总费用最低。,为了便于分析,用一个新的图来代替原图,新图圈内数字表示矿井编号,产量记在圈的旁边,道路交叉点看作产量为零的矿井,把那些只有一条道路连接的矿井称为端点。,12,首先计算这些矿井的总产量,本例为,27000,吨。,然后分析各端点,都没有超过总产量的一半,因此把各端点的数量合并到前一站,即 和 的数量合并到;把的数量合并到,;,把,的,数量合并到,如下图所示。,3,5,6,11000,9000,7000,各端点都合并到前一站后,和变成了图中的端点。对它们进行分析,其数量都不超过总产量的一半,所以他们也不是最佳点。,再把它们合并到前一站,即把和的数量合并到。则 的数量为27000,超过总量的一半,所以是最佳点。,结论:加工厂应建在第5号矿井。,13,二,.,货物配,装,货物配装的目的是在车辆载重量为额定值的情况下,合理进行货物的安排,使车辆装载货物的价值最大(如:重量最大、运费最低等)。,14,1.,装货问题的数学模型,(,1,)问题描述,设货车的载重量上限为,G,,,用于运送,n,种不同的货物,货物的重量分别为,W,1,,,W,2,,,.,,,W,n,,,每一种货物对应于一个价值系数,分别用,P,1,,,P,2,,,.,,,P,n,表示,它表示价值、运费或重量等。,(,2,)数学模型,设,X,k,表示第,k,种货物的装入数量,货物配装问题的数学模型可以表示为:,15,(,3,)求解方法,可以把装入一件货物作为一个阶段,把装货问题看作动态规划问题。,一般情况下,动态规划问题的求解过程是从最后一个阶段开始由后向前进行的。,由于装入货物的先后次序不影响装货问题的最优解。可以从第一阶段开始,由前向后逐步进行。,(,4,)求解过程,1,)装入第,1,种货物,X,1,件,其最大价值为,其中:,X,1,表示第1种货物的装载数量;其取值范围:0,X,1,G/W,1,,,方括号表示取整;,P,1,:,第1种货物的价值系数(重量、运费、价值等);,f,1,(W),:,第一种货物的价值。,16,2),装入第,2,种货物,X,2,件,其最大价值为,其中:,X,2,表示第,2,种货物的装载数量;其取值范围:,0X,2,G/W,2,;,P,2,:,第,2,种货物的价值系数(重量、运费、价值等);,:第一种货物的重量;,:第一种货物的价值。,3,)装入第,3,种货物,X3,件,其最大价值为,其中:,X,3,表示第,3,种货物的装载数量;其取值范围:,0X,3,G/W,3,;,P,3,:,第,3,种货物的价值系数;,:前两种货物的重量;,:前两种货物的价值。,17,n),装入第,n,种货物,Xn,件,其最大价值为,其中:,X,n,表示第,n,种货物的装载数量;,其取值范围:,0,Xn,G/,W,n,;,P,n,:第,n,种货物的价值系数;,18,例题,9,载重量为,8t,的载重汽车,运输,4,种机电产品,产品重量分别为,3,吨、,3,吨、,4,吨、,5,吨,试问如何配装才能充分利用货车的运载能力,?,解:,第一步,按照前面的公式,分成四个阶段计算每一阶段的价值。,计算结果以表格表示如下:,(,5,)货物配装例题求解,19,载重量,件数,价值(重量),载重量,第2种,货物的件数,第1种,货物的重量,价值计算,价值,Max,20,载重量,第,3种货物的件数,第,1、2种货物的重量,价值计算,价值,Max,21,第二步:寻找最优方案。,寻找最优解方案的次序与计算顺序相反,由第,4,阶段向第,1,阶段进行。,选择最后一个阶段价值最大的装载情况,逐步向前寻找最优方案。,22,第二步:寻找最优方案。,寻找最优解方案的次序与计算顺序相反,由第,4,阶段向第,1,阶段进行。从价值最大的装载情况,逐步向前寻找最优方案。,(,1,)在第,4,阶段计算表中,在载重量为,8,时,价值,(,本例为载重量,),最大,值,f,4,(W),8,,,对应两组数据,(,加*号的数据,),:,1,),X,4,0,;,2,),X,4,1,;,先看,X,4,1,时的情况:,当,X,4,1,时,即第,4,种货物装入,1,件,(5,吨,),,表中第,3,列数字表示其余种类货物的装载量。,当,X,4,1,时,其他,3,种货物装载量为,3,吨,;,(,2,)按相反方向,,在第,3,阶段计算表中,查,W=3,吨时,得到最大价值,f,3,(W),3,,,对应的,X,3,=0,。,查表中第,3,列数字,,W=3,,,X,3,=0,时,其余两类货物装入重量,3,;,(,3,)在,第,2,阶段计算表中,查,W=3,,,f,2,(W)=3,对应两组数据:,1,),X,2,=0,;,2),X,2,=1,;,即,当,X,2,=1,或,0,时,其他,(,第,1,种,),货物装载量为,3,或,0,;,(,4,)查第,1,阶段计算表,,1,)当,W,3,时,对应,X,1,=1,;,2,)当,W,0,时,对应,X,1,=0,;,根据当前面的寻找过程,可以得到,两组最优解,:,第一组:,X,1,=1,,,X,2,=0,,,X,3,=0,,,X,4,=1,;,第二组:,X,1,=0,,,X,2,=1,,,X,3,=0,,,X,4,=1,;,这两组最优解的实际载重量为:,第一组:,X,1,*3+X,4,*5=1*3+1*5=8,第二组:,X,2,*3+X,4,*5=1*3+1*5=8,23,载重量,第,3,种货物的件数,第,1,、,2,种货物的重量,价值计算,价值,24,载重量,第2种,货物的件数,第1种,货物的重量,价值计算,价值,Max,25,前面的最优方案是在第四阶段取,X,4,1,时得出的方案。,如果在第,4,阶段计算表中取,X,4,0,,,则其余种类的货物装载量,W-W,4,X,4,=8,;,在第,3,阶段计算表中,查,W=8,一栏,,f,3,(w)=8,对应,X,3,2,,,再仿照前面的方法,可以得到第,3,组最优解:,第三组:,X,1,=0,,,X,2,=0,,,X,3,=2,,,X,4,=0,;,装载量为:,X,3,*2=2*4=8,以上三组装载方案,都最大限度地发挥了车辆的载重能力,都是最优方案。,26,27,最终的最优装载方案为:,第一组:,X,1,=1,,,X,2,=0,,,X,3,=0,,,X,4,=1,;,第二组:,X,1,=0,,,X,2,=1,,,X,3,=0,,,X,4,=1,;,第三组:,X,1,=0,,,X,2,=0,,,X,3,=2,,,X,4,=0,;,以上三组装载方案,都最大限度地发挥了车辆的载重能力,都是最优方案。,28,2.,品种混装问题,(,1,)品种混装问题简介,在实际的物流过程中,储运仓库,(,或货运车站,),要把客户所需的零担货物组成整车,运往各地。,不同客户的货物,要分别在一站或多站卸货。,在装货、运输和卸货过程中,为了减少装卸、运输过程中出现差错,一般要按照品种、形状、颜色、规格、到达地点,把货物分为若干类,在装车时分别进行处理。这就是,品种混装,问题。,29,(,2,)品种混装问题描述,设装车的货物可以分为,1,类,,2,类,,,,m,类。共有,N,件待运货物。,其中:第,1,类货物有,N,1,件,它们的重量分别,G,11,,,G,12,,,,,G,1N1,;,第,2,类货物有,N,2,件,它们的重量分别为,G,21,,,G,22,,,,,G,2N2,;,第,s,类货物共有,Ns,件,它们的重量分别为,G,s1,,,G,s2,,,,,G,sNs,;,以此类推,可以看出:,货物总的件数:,其中,,Ns,:第,s,类货物的件数;,m,:,货物的种类数;,N,:,货物的总件数;,30,(,3,)数学模型,品种混装问题要求同一货车内每类货物至多装入一件,在此假设条件下,可以建立品种混装问题的数学模型:,设:,其中,m:,货物的类别数;,Nr:,第,r,类货物的件数;,Grs,:,第,r,类第,s,件货物的重量;,G,0,:,货车载重量的上限。,31,(,4,)求解方法,品种混装问题的数学模型属于整数规划问题,可以用单纯形法进行求解,动态规划法,图,5-20,表示,8,件货物分为,4,类的混装网络示意图。在图中同一列的方框表示同一类货物,方框内的数字,(,符号,),表示货物重量。,上述,品种混装问题就是在网络中自右向左寻找一条路线,使路线所经过的方框中的重量之和达到最大,但又不超过货车的载重量的上限,Go,。,可以用穷举法求解。,如果将四类货物看作,4,个阶段,将上述问题化为动态规划问题求解。,32,(,5,)求解实例,例题,10,货车载重量上限,Go,50,;,第,1,类货物,2,件,,G,11,=20,,,G,12,=11,;,第,2,类货物,1,件,,G,21,=13,;,第,3,类货物,3,件,,G,31,6,,,G,32,11,,,G,33,8,;,第,4,类货物,2,件,,G,41,19,,,G,42,17,。,19,17,6,11,8,13,20,11,计算过程见表5-3134,分成四个阶段进行。,33,可装,重量,实装,重量,剩余容量,第1,阶段的可装容量,W,值对应第2阶段的剩余容量,W-G,装载情况计算表,34,可装,重量,实装,重量,剩余容量,第1,阶段的可装容量,W,值对应第2阶段的剩余容量,W-G,最优解的,寻找过程,35,寻找最优解的次序与计算顺序相反,从第一阶段计算表开始,直到第四阶段。,要使装载量达到最大,对应的剩余余量应当最小。,(,1,)在第一阶段计算表中,,余量,W-G1,的最小值为零,,为最好的方案,此时,对应的实际装载量,G1,为,20,,可装载容量,W,值为,20,。,(,2,)第一阶段的可装载容量,W=20,为第二阶段的剩余装载容量,即,W-G2,的值为,20,,从表中可以看出第二阶段的剩余装载容量为,20,的实际装载方式有两种,分别是:,G2=0,和,G2=13,对应的可装容量分别为,W=20,和,33,。,(,3,)第二阶段的可装容量,W=20,和,33,为第三阶段的剩余装载容量,查表可得:,对应于剩余可装载容量为,20,的实际装载量为,G3=11,可,装载容量为,W=31,。,对应于剩余可装载容量为,33,的实际装载量为,G3=0,可装载容量为,W=33,。,(,4,),同理可得第四阶段的,G4,为,19,和,17,。,36,最后的最优解为:,G1=20 G2=0 G3=11 G4=19,G1=20 G2=13 G3=0 G4=17,每组方案的装载量都是,50,,达到满载,充分利用了货车的装载能力。,37,三,.,物流服务系统中的配置问题,随机服务系统,物流服务系统由服务的机构和顾客组成。,物流服务系统是一个综合服务系统,许多服务项目具有随机性质。如:装卸系统、运输系统。,物流服务系统中的顾客(人、货物等)到来的时间和服务时间随不同的时机和条件而变化,这种变化具有随机性质,这类系统称为随机服务系统。,随机服务系统包含三个过程:顾客输入、排队、服务三个过程。,排队论是处理随机服务系统的专门理论。,服务系统中的设备配置,服务机构越大,顾客越方便,但机构过大,导致成本升高或浪费。,服务机构过小,便不能完全满足顾客的需要,使服务质量降低,导致信誉损失和顾客流失。,合理配置服务系统,使他既能满足顾客的需要,又能使系统的花费最为经济,是物流系统配置所关心的主要问题。,38,本章,重点,物流调运规划,表上作业法确定产、销地之间的供需联系和数量最优搭配,图上作业法进行运输线路的选择,最短路径与最大流量,分配规划,选址问题,货物配装,39,
    展开阅读全文

    开通VIP折扣优惠下载文档

    提示  咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。

    咨信网小贴示:
    1、浏览或下载可查看了解,请点击【咨信网告知】。
    2、下载文件中如有侵权或不适当内容,将立即纠正。
    3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
    4、开具发票登录电脑端申请,请点击【索取发票】。

    咨信网客服组:【微信客服】

    自信AI创作助手
    关于本文
    本文标题:第3-2章-物流系统规划(二).ppt
    链接地址:https://www.zixin.com.cn/doc/14772567.html

    Copyright ©2010-2026   All Rights Reserved  宁波自信网络信息技术有限公司 版权所有   |  客服电话:0574-28810668    微信客服:咨信网客服    投诉电话:18658249818   

    违法和不良信息举报邮箱:help@zixin.com.cn    文档合作和网站合作邮箱:fuwu@zixin.com.cn    意见反馈和侵权处理邮箱:1219186828@qq.com   | 证照中心

    12321jubao.png12321网络举报中心 电话:010-12321  jubao.png中国互联网举报中心 电话:12377   gongan.png浙公网安备33021202000488号  icp.png浙ICP备2021020529号-1 浙B2-20240490   


    关注我们 :微信公众号  抖音  微博  LOFTER               

    自信网络  |  ZixinNetwork