运输问题时间优化算法

中国管理科学990405中国管理科学R资源系统CHINESE JOURNAL OF MANAGEMENT数字化期刊WANFANG DATA ( CHINAINFO)SCIENCEDIGITIZED PE RIODICAL1999年第7卷第4期vol.7 No.4 1999运输问题时间优化算法杨建军郭乃林韩晓明李仲强摘要:运输问题是线性规划中的一类特殊问题,适用于求解目标函数符合线性叠加关系的费用或距离问题,对于实际运输问题中的运输时间优化问题则难以给出优化解。本文结合科研实践提出了运输问题中有关时间优化的迭代算法模型,此模型可给出整体运输时间最优的运输方案,通过实际检验证明,此算法简便、稳定、计算结果符合实际情况。关键词:线性规划;运输问题;时间优化;算法模型.Time Optimization Algorithm for Transportation ProblemY angJianjunGuo N ailinH an Xiaoming(TheAir ForceMissile Insitute, Sanyuan713800)Li Zhongqiang(TheAir ForceOil Institute,Sanyuan713800)Abstract:T ransportation problem is a special problem in linear programming.This paper setsupan iteration algorithm for time optimization related to transportation problem,which can giveaglobal transportation time optimized project.A practical verification shows, this algorithm is simpleand stalble,the results accord with the fact.KeyW ords.linear programmingtransportation problem;time optimization;algorithm1线性 规划中的运输问题运输问题是线性规划中的-类特殊问题,在实践中常用来解决运输计划制定、物资调运、运费优化等实际问题,在解决此类问题中，目标函数为符合线性叠加原理的费用,此时线性规划中的运输问题模型可称之为费用优化运输问题模型。费用优化运输问题的数学模型为:minz=，(目标函数)中国煤化工MHCNM HGEx=b, j-=.2-,n(约束条件)fel//E/2/7平据ggg9904/990495.htm,(第1/ 8页) 2010-3-23 14:57:17中国管理科学990405高x≤a, 1=.,..m(约束条件)Xj≥0(非负条件)式中: Z-费用优化运输问题模型的目标函数;Xx;供应点到需求点j的供樱峥;Ci;供应点i到需求点j的单位运费;b;需求点j的需求量;a供应点i的可供应量。.当各供应点的可供应量之和等于各需求点需求量之和，即鸣一点时,为产销平衡运输问题,可通过表上作业法进行求解。对于产销不平衡的运输问题可通过增加虚供点或虚收点将问题转化为产销平衡的运输问题进行求解。费用优化运输问题模型的目标函数为运输费用的线性叠加,因此费用优化运输问题模型:是对于符合线性叠加原理的运输费用的优化。对于通常运输费用作为决定因素的运输问题,费用优化运输问题时间优化算法第4期运输问题模型是-种行之有效的数学模型。2时间优化运输问题的特点对战时军用物资运输或在某些紧急条件下,运输时间成为最主要的决定因素,即整体运输时间最短成为优化的第- -目标,这时运用费用优化运输问题模型就难以给出满意的结果。费用优化运输问题模型的优化目标为整体运输费用最小,运输费用具有线性叠加特性,或认为具有串联特性,即整体运输费用等于各分段费用的线性叠加;而运输时间则.不具有线性叠加特性,因为各供应点的操作(装卸和运输)可同时或平行进行,整体完成时间并不是各分段时间的线性叠加,而是由各分段时间中的最大值控制, 运输时间的这一特点使运输时间的优化具有明显的并联特性。对于具有并联特性的运输时间的优化，目前尚无十分成熟的算法。在对运输问题进行时间优化时,在所有的供应点中必有一个或多个控制点,即这些供应点的供应时间(包括装卸时间和运输时间两项之和)在所有的供应点中最大,只有缩短控制点的供应时间才对运输方案的整体供应时间的优化具有直接意义，因为即使缩.短其它供应点的供应时间,整体供应时间并没有得到改进。在对运输问题进行时间优化时,在保证运输时间最优的条件下，可同时考虑经济性因素,即把运输经济性因素作为第二优化目标。3时间优化运输问题算法模型的建立和模型框图在研究时间优化运输问题特点的基础上,建立了以费用优中国煤化工基础,控制点供应时间调整、供应点优化选择为辅助的时间优化运输MYHCN MH9NMH.型。此模型所给出的运输方案是在满足时间最优条件下的最经济的运输方案。fl/ Iv0万教据ggg9904/990495.htm,(第2/ 8页) 2010-3-23 14:57:17中国管理科学990405在考虑供应点的供应时间时, 考虑两个时间因素,即装卸时间和运输时间。装卸时间指供应点装卸物资所需的时间,运输时间指供应点到需求点的运输时间,两个时间因素之和即为供应点的供应时间。在实际问题中, 某些供应点与某些需求点间可能不存在供应关系,在制定优化运输方案中应考虑到这一因素。在模型的初始数据中令这些供应点与需求点之间的距离为一个足够大的数字,如99999千米,则程序在优化运算时就自动不选取这些供应点来供应那些不存在供应关系的需求点。在计算各供应点的保障时间时,常遇到一个供应点供应多个需求点的情况,在这种.情况下依据发运先远后近的原则计算此供应点的供应时间,即认为供应点可连续装卸，在装卸的过程中可同时发运,发运采用先给距离远的需求点发运,后给距离近的需求点发运,此时的供应时间为总装卸时间和与总装卸时间不重合的运输时间之和。可以证明对于一个供应点供应多个需求点的情况,这种供应方式所需的供应时间最短。时间优化运输问题数学模型对费用优化运输问题数学模型的重要改进是在费用优化运输问题数学模型的基础上增加了控制点供应时间调整模型和供应点选择模型。在控制点供应时间调整模型中采用供应时间排序的方法确定各供应点供应时间的序列。在装卸时间远大于运输时间的条件下,为减少运算量可采用平均时间替代供应时间,平均时间定义为供应点的供应量除以供应点的装卸能力,可以证明在忽略运输时间的条件下,总平均时间(所有供应点的供应量之和除以所有供应点的装卸能力之和)是最理想时间,最大供应时间等于总平均时间的供应方案是时间最优方案。在运输时间不.能忽略或计算精度要求较高时,不能采用平均时间替代供应时间。在确定了各供应点供应时间的序列后,则将供应时间最大的供应点的部分供应量调整到供应时间最小的供应.点去,调整的前提是这两个供应点对某-或某些需求点同时具有供应关系，反复迭代进行排序和调整, 直至调整过程不能再进行为止。供应点选择模型的主要部分仍为费用优化运输问题模型,对供应点的选择仍以就近供应为原则,在此基础上,增加供应点供应量限制准则。若供应点在优化供应量条件下不能满足供应时间限制,则限制供应点的供应量,使其满足供应时间要求。时间优化运输问题模型的数学表达为:费用优化运输问题数学模型(略)3.2 控制点供应时间调整模型(推导见附寻)xz=(XmaxX QminXminX Qmax+QmaxX Qmin(mx~Tmin)Nys)/(Qmax+Qmin)Xmax2=Xmax1-XtXmin2= EXmin1+Xu式中: xc最优调整量;Xmax供应时间最大的供应点的总供应量;Xmin供应时间最小的供应点的总供应量;Xmax1供应时间最大的供应点调整前的总供应量;Xmx2供应时间最大的供应点调整后的总供应量;中国煤化工Xmin1供应时间最小的供应点调整前的总供应量;MHCNM HGXmn2供应时间最小的供应点调整后的总供应量;fel//E/2/7平据gggg9904/990405.htm,(第3/ 8页) 20103-23 14:57:17中国管理科学990405Qmax供应时间最大的供应点的装卸能力;Qmin供应时间最小的供应点的装卸能力;Cmax供应时间最大的供应点到所供需求点的距离中的最小值;Cmin供应时间最小的供应点到所供需求点的距离中的最小值;V供应时间到所供需求点的平均运输速度。供应点选择模型供应点供应量限制准则Xx=(xCi;/ys)x Qi式中: Xixz供应点i的限制供应量;tx2需求点j的限制供应时间;q;供应点i到需求点j的距离;Q;供应点i的装卸能力。依据以.上数学模型,编制计算程序,计算程序流程框图见图1。计算步骤如下:数据输人和整理l 费用优化运输问题模型] ￥↓求各供应点的总供应量|计算供应时间Y可调整否?> +供应时间调整N<供应时 间满足要求否?> +| 供应点选择输出结果图1计算程 序流程框图( 1)数据输入和整理模块的功用为输入原始数据;对输)中国煤化干序以减少优化送代次数;各需求点的需求量为实际需求量,各供应MHCNMH各供应点的可供量。( 2)以各需求点的实际需求量、各供应点的初始可供应量、各供应点与各需求点fle// 0亳螯掘zgg/gg999005.htm (第4/ 8页) 2010-3-23 14:57:17中国管理科学990405间的距离矩阵(或费用矩阵)为依据进行距离优化(或费用优化) ,产生初始供应点、初始供应点的初始供应量和分配方案,这- -过程实际上就是线性规划运输问题求解;(3)在获得供应量和分配方案后,依据各供应点的装卸能力和运输距离计算供应时间;( 4)进行供应时间调整,产生初始供应点调整后的供应量、以各需求点的实际需求量、各供应点调整后的供应量、各供应点与各需求点间的距离矩阵(或费用矩阵)为依据重新进行距离优化(或费用优化) , 产生初始供应点新一轮的供应量和分配方案;(5)循环进行第(3)-(4)步,直至调整前后的结果趋于一致,即无法再进行新一轮的调整, 如再进行调整,分配结果将保持不变。(6)调整完成后,计算供应时间;( 7)若供应时间已满足要求,则输出结果;若供应时间不能满足要求,则进行供应点选择;(8)供应点选择,在限制不满足供应时间要求的初始供应点的供应量的条件下,增加新的供应点。若在所有供应点已全部参加供应后,仍不能满足供应时间要求,则按限定供应时间要求确定各供应点的供应量,并给出提示,此时的总供应量不能满足总需求。4计算实例和结果分析在以.上模型的基础上,编制了计算机程序。通过课题数据的实际检验, 证明计算模型合理、稳定、计算速度较快、计算结果符合实际情况要求。为进一步说明时间优化运输问题模型在时间优化方面的优势,本文结合实际情况给出一套模拟数据,分别采用费用优化运输问题模型和时间优化运输问题模型进行了对比计算。计算实例:有甲、乙、丙、丁四个需求点,A、B、C、D、E、F、G、H、J、K、L、M十一个供应点;已知数据为,需求点的需求量和供应点的可供应量、需求点和供应点间的运输距离、供应点的装卸能力、运输速度(取平均值, 每小时30千米)。计算实例的原始数据见表1。为便于对比,对于以上数据分别采用费用优化运输问题模型和时间优化运输问题模型形成两个运输方案,采用费用优化运输问题模型所形成的分配方案见表2;采用时间优化运输问题模型所形成的分配方案见表3。从表1和表2中可看出,费用优化运输问题模型计算生成的分配方案按距离最近原则进行分配,获得的结果为运输费用最小的分配方案。从表3所示的时间优化运输问题模型分配方案可看出,采用时间优化后, 最大供应时间从原费用优化分配方案的263小时减少到118小时,供应点供应顺序仍保持就近供应的特点,这一点可从表1和表3的对照中看出。对于单一供应点即可满足供应时间要求的情况,时间优化运输问题模型所给出的分配方案仍遵循费用优化运输问题模型的分配结果,给出的供应方案仍为最经济的供应方案。由此可见,时间优化运输问题模型给出的分配方案是在满足限定供应时间要求下的最经济的运输方案。中国煤化工表1原始数据(距离阵单位:kmYHCNM HGfel//E/2/7平据ggg9904/990495.htm,(第5/ 8页) 2010-3-23 14:57:17中国管理科学990405供应点装卸能供应点可供量供应点/需求点|甲需求点|乙需求点丙需求点丁需求点(吨/小时)力(吨)A供应点999999290045B供应点15005776000C供应点2017000D供应点40080090000E供应点2035901171120F供应点16062220000G供应点9999914869560000H供应点1319150000J供应点30000K供应点2308060000L供应点5005080000M供应点52需求点总需求75000需求量(吨)91916403156142892注:若表中距离为99999，则表明该供应点与该需求点之间无供应关系。表2费用优化运输问题模型分配方案 (分配量(供应时间)单位:吨(小时) )供应点装卸供应点可供供应点/需能力甲需求点乙需求点|丙需 求点丁需求点.量求点(吨/小时)09191 ( 177 )E供应点.640 ( 14)1500( 20 )931561 ( 263 )C中国煤化工0YHCNMHGOfle//E Vv0万教据gggg9904/990405.htm,(第6/ 8页) 20103-23 14:57:17中国管理科学990405需求点总需求需求量1500919164031561(吨)42892注:表中括号中的数字表示供应时间(单位:小时)表3时间优化运输问题模型分配方案 (分配量(供应时间)单位:吨(小时) )供应点装卸供应点可供供应点/需能力甲需求点乙需求点|丙需求点丁需求点量求点(吨/小.时)A供应点045B供应点57C供应点4325( 83 )524325D供应点3086( 118 )3086E供应点9546( 118 )1209546F供应点4866( 83 )624866G供应点640 ( 14)69H供应点1500( 20 )91J供应点14148 ( 118 )14148K供应点8L供应点60M供应点4781 ( 118)47819191.对于调整后供应时间仍不能满足要求的情况,程序将给出提示,供决策者选择,选择退出系统修改供应时间要求或选择按限定供应时间供应,生成限定供应时间要求下的分配方案,此时总需求量不能得到满足,程序将给出提示并标明各需求点需求量被满足的百分比。通过大量的实际计算可知,时间优化运输问题模型的优化结果符合实际情况,程序运行稳定、计算速度较快,模型对于解决运输问题的时间优化行之有效。5结束语.中国煤化工.MHCNMHG时间优化运输问题模型解决了物资调运中时间因素位于第L位的九化叫越,通过实际课题运用考验证明, 模型的建立是合理、简洁和实用的。fl/ Iv0万教据zg9/gg9904/99005.htm (第7/ 8页) 2010-3- 23 14:57:17中国管理科学990405本文所介绍的时间优化运输问题模型是我们所研制的计算机辅助决策系统中的一个关键模块,为充分利用决策者的经验和智慧,时间优化运输问题模型在程序设计上采用了人工干预技术,对于实际应用中可能出现的多种情况,程序均会给出提示,提示情况出现的现象并给出处理建议,由决策者做出选择,控制程序的跳转, 程序则对不同情况做出相应的处理和调整。时间优化运输问题模型是对费用优化运输问题模型的改进,使用者可根据课题的实际要求,参考此模型的思路建立符合自身实际情况的模型。作者单位:杨建军郭乃林 韩晓明 (空军导弹学院,三原713800 )李仲强(空军油料研究所,三原713800 )参考文献[1]《运筹学》教材编写组.运筹学(修订版).清华大学出版社, 1997.[2]胡运权.运筹学基础及应用.哈尔滨工业大学出版社, 1993.[3]五院校合编运筹学-经济管理决策方法.四川大学出版社, 1989.[4]李书涛.决策支持系统原理与技术.北京理工大学出版社, 1996.[5]马绍民综合保障I程.北京.国防工业出版社, 1995.附录:控制点供应时间调整模型的推导设最优调整量为xz,则在供应时间最大的供应点的供应时间等于供应时间最小的供应点的供应时间条件下,有Xmax Xrq/Qmax+ CmaxN ys=(Xmin+ x)/Qmin+ CminN ys此式经过变换,解出最优调整量xt的表达式。xz=(XmaxX Qmin-XminX 9max+QmaX Qmin( Cmax Cmin)N y)(Qmax+ Qmin)将供应时间最大的供应点的总供应量减去最优调整量,供应时间最小的供应点的总供应量加上最优调整量,即得到两供应点新一轮的总供应量。Xmax2= EXmax1-XtXmin2=Xmin1+Xx收稿日期: 1999-04-05中国煤化工MHCNM HGfel//E/2/7平据ggg9904/990495.htm,(第8/ 8页) 2010-3-23 14:57:17