资源描述：
《具有运输次序的运输问题研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第7卷第5期广州大学学报(自然科学版)Vol.7No.52008年10月JournalofGuangzhouUniversity(NaturalScienceEdition)Oct.2008文章编号:167124229(2008)0520001204具有运输次序的运输问题研究吴唤群郭成(广州大学商学院,广东广州,510006)摘要:研究了一类新的运输问题———具有运输次序的运输问题,建立了这类运输问题的网络流模型,证明了该模型的有效性,根据解最小费用流问题的思路设计出求解该模型的实用算法,同时通过定义修正权将负权转化为非负权,从而可以用Dijkstra算法找最短路,使
2、算法得到改进。关键词:运输问题;运输次序;网络流模型;最小费用流;Dijkstra算法中图分类号:U11【文献标识码】A1问题的提出2网络流模型的建立产地群共有n个产地,生产a种产品H1,⋯,一般的线性规划模型对运输次序无法给出有Ha,销地群共有m个销地,接受这a种产品.产地效的表达,这里我们建立一个网络流模型,将具有i(i=1,⋯,n)发送产品Hj的数量为pij,发送次序运输次序的运输问题转化为一个最小费用流为Hi1,⋯,Hia,这里(i1,⋯,ia)为{1,2,⋯,a}的一问题.种指定排列.销地j(j=1,⋯,m)有次序地接收这我们提出的具有运输次序的运输问题的网
3、络a种产品,第s次可接收的产品为Hjs1,⋯,Hjsk(k≤流模型N=(V,A,L,H,B)如图1所示.a),这里Hjs1,⋯,Hjsk为(H1,⋯,Ha)的子集,产品图1中:Vs为源点,Vt为汇点;Pi(i=1,2,⋯,Hjsg的接收量为qjsg(g=1,⋯,k),第s次接收的产n)为产地节点;Qj(j=1,2,⋯,m)为销地节点;Pijk(i=1,2,⋯,n;j=1,2,⋯,a)为产品发送节点;Wi品总量为qjs=∑qjsg,这里的接收次序是指在接(i=1,2,⋯,c)为产地后备仓库节点;Qij(i=1,2,g=1收了第s-1次运输后才可接收第s次的运输,销地⋯,
4、m;j=1,2,⋯,r)为产品接收节点;Ti(i=1,2,r⋯(i=1,2,⋯,n;j=,d)为销地库存仓库节点;Iijj共r次接收产品的总量为qj=∑qjs.产地i到销s=11,2,⋯,a)、Jij(i=1,2,⋯,m;j=1,2,⋯,a+1)为地j的运价为bij(i=1,⋯,n;j=1,⋯,m).产地有中间节点.c个后备仓库W1,⋯,Wc,有一种替代产品,记为第下面对网络流模型N=(V,A,L,H,B)中的各(a+1)种产品,其数量为pn+1,⋯,pn+c,可满足任参数进行描述:一销地任一次序的要求,Wi到销地j的运价为点集:V={vs,vt}∪P∪Q∪I∪J∪X
5、∪Y∪Wbn+i,j.销地有d个库存仓库T1,⋯,Td,可接收任一∪Tnmna产地任一次序的供给,其可接收量为qm+1,⋯,其中,P=∪{Pi},Q=∪{Qi},I=∪∪{Iij},J=i=1i=1i=1j=1qm+d,产地i到Tj的运价为bi,m+j.现在要求将所有ma+1namr产地的货物全部运出,并使所有销地得到全部的∪∪{Jij},X=∪∪{Pij},Y=∪∪{Qij},W=i=1j=1i=1j=1i=1j=1需求cd,找出总运输费用最低的运输方案.我们称这∪{Wi},T=∪{Ti}.i=1i=1样的运输问题为具有运输次序的运输问题.收稿日期:2007-10-
6、30;修回日期:2008-04-02作者简介:吴唤群(1958-),男,教授,主要从事运筹学、工程项目管理研究.2广州大学学报(自然科学版)第7卷图1网络流模型的有向网络图Fig.1Directivenetworkchartofnetworkflowmodel12n(v),A对于A6中的弧(Iik,Jjk)(i=1,⋯,n;j=1,⋯,弧集:A=∪Ai,其中A1=∪s,Pi2=i=1i=1)=b)=0,m;k=1,⋯,a):b(Iik,Jjkij,L(Iik,Jjknna-1∪(Pi,Pi1),A3=∪∪(Pij,Pi(j+1)),A4=H(Iik,Jjk)=pik;
7、i=1i=1j=1nacnma对于A7中的弧(Wi,Jj(a+1))(i=1,⋯,c;j=1,∪∪(Pij,Iij),A5=∪(vs,Wi),A6=∪∪∪(Iik,i=1j=1i=1i=1j=1k=1⋯,m):b(Wi,Jj(a+1))=b(n+i)j,L(Wi,Jj(a+1))=0,cmndaJjk),A7=∪∪(Wi,Jj(a+1)),A8=∪∪∪(Iik,Tj),H(Wi,Jj(a+1))=pn+i;i=1j=1i=1j=1k=1ma+1rmr对于A8中的弧(Iik,Tj)(i=1,⋯n;j=1,⋯,A9=j∪=1k∪=1g∪=1(Jjk,Qj
