调整运价预算约束下的运输问题模型与应用_杨珺.pdf

《调整运价预算约束下的运输问题模型与应用_杨珺.pdf》由会员分享，可在线阅读，更多相关《调整运价预算约束下的运输问题模型与应用_杨珺.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、调整运价预算约束下的运输问题模型与应用杨王 君张敏陈新摘要:研究一类特殊的运输问题,即在运价的调整预算一定的约束下,如何调整单位的运输费用和安排运输计划才能使总运费最省的运输问题。提出了这类运输问题的基本模型和两种变形模型:剖分问题和瓶颈问题,给出实际算例,并用Lingo 求解该类问题。最后通过模拟计算,分析了 Lingo 解决该问题的规模局限性。关键词:运输问题;运价调整;费用约束中图分类号:O122文献标识码:A文章编号:1672-884(2004)03-0255-05收稿日期:2004-08-17基金项目:国家自然科学基金资助项目(70271027)运输问题是运筹学中一类特殊的线性规划问

2、题。最 早 研 究 这 类 问 题 的 是 美 国 学 者Hitchcock 1,后来 Koopman 详细地对此问题加以讨论。由于其模型及解法的独特性,运输问题一直是人们关注的问题。由于实际的运输问题与理想运输问题模型有一些差别,人们提出了各种运输问题的变种或推广模型。从目标函数的角度,在运输问题中有时要同时考虑运输成本最小,运输过程中货物损坏率最低,以及运输危险性最小等多个目标,因此有研究多目标运输问题的数学模型及其算法 2,3,还有运用禁忌搜索算法解决带固定费用的运输问题 4,最短时限的运输问题 5和考虑路线的危险度最小的运输问题 6,7;从约束函数的角度,有研究供给量和需求量在某个区间

3、变化的不确定性运输问题 8,研究带容量限制和手续费用的 运输问题 9,有时间 窗口的运输 问题 10。以上的研究都是探讨改变目标或增加约束的条件下如何安排运输计划的运输问题。还有另一类运输问题,即研究运输计划已拟定的条件下,如何调整单位运价使得运输计划最优的运输问题的逆问题 11。本文研究在运价的调整预算一定的约束下,如何调整单位的运输价格和安排运输计划才能使总运费最省的运输问题调整运价的预算约束下运价调整的运输问题。1模型的建立1.1一般运输问题已知有 m 个生产地点 Ai,i=1,2,+,m 可供应某种物资,其产量分别为 ai=1,2,+,m,另有 n个销地 Bj,j=1,2,+,n,其销

4、量分别为bj,j=1,2,+,n,从 Ai到 Bj运输单位物资的运价 cij,变量xij表示从 Ai运到 Bj的物资量。运输要求总运费最小的调运方案的一般运输问题模型(P1)如下:minZ=6mi=16nj=1cijxij,(1)s.t6mi=1xij=bj,j=1,2,+,n,(2)6nj=1xij=ai,i=1,2,+,m,(3)xij 0,(4)式中,目标函数式(1)代表要求总运费最小;约束方程式(2)每个销地 Bj的销量等于 bj;约束方程式(3)每个产地Ai的产量等于 ai;式(4)是非负约束。1.2 调整运价总预算约束下运输问题运输价格的调整可以通过改变运输方式、运输工具和运输路线

5、等来实现,因此,如何选择恰当的运输方式、运输工具和运输路线是实际运输过程中着重考虑的问题。如果研究在运价的调整总预算一定的约束下,如何调整单位的运输价格和安排运输计划才能使总运费最省的运输问题,这时运输问题就演变成为运价调整总预算约束下的运输问题。假设需要调整运输费用,总的调整预算给定为 D,从Ai到Bj的单位运价 cij的调整量为Hij,则调整后单位运价cij=cij-Hij。设Hij的单位调整费用为 wij。调整运价的总预算约束下运价调整的运输问题就是在调整运价的预算一定的情况下,如何调整单位的运价和安排运输计划才能使总运费最省的运输问题。那么Hij和xij为该问题的决策变量,建立该问题模

6、型(P2)如下:minZ=6mi=16nj=1cijxij=6mi=16nj=1(cij-Hij)xij,(5)s.t6mi=1xij=bj,j=1,2,+,n,(6)255调整运价预算约束下的运输问题模型与应用杨王 君张敏陈新6nj=1xij=ai,i=1,2,+,n,(7)6mi=16nj=1wijHij D,(8)Xij 00 Hij Aijcij,(9)式中,目标函数式(5)代表要求调整单位运费后完成运输计划的总运费最小;约束方程式(6)与式(2)相同,表示每个销地Bj的销量等于bj;约束方程式(8)与式(3)相同,表示每个产地 Ai的产量等于 ai;约束条件式(8)是总的调整运价的成

7、本不超过预算 D。约束条件式(9)是调整后的运输价格最低限制,其中 Aij为已知系数;各条路线上的运输量都为非负数。以上模型的目标函数是二次函数,约束条件全是线性的,显然是一个二次规划问题。2 变形问题在(P2)问题的基础上,由于实际问题给出的条件和约束的不同,我们再讨论两种此类问题的变形问题:带剖分限制的运价调整运输问题和带瓶颈限制的运价调整运输问题。2.1 带剖分限制的运价调整运输问题由于客观条件的限制,能够允许调整的线路数目是给定的,例如主管部门审批数目限制,或者为了保障运输的正常进行,由于调整过程需要时间,防止造成运输的中断等不利状况,运价调整的路线只能限制在给定数目以内。此时该问题定

8、义如下:假设调整运价的线路数限定为 L,且对于每个从生产点 Ai到销售点 Bj运价调整费用的最大限额为Dij的条件下,如何调整运价和安排运输计划使总运费和调整费用之和最省。那么,我们需要再引入一个决策变量 kij,当决定调整从生产点 Ai到销售点Bj运费时,kij为1;否则,kij为0。那么带剖分限制的运价调整运输问题的模型(P3)如下:minZ=6mi=16nj=1(cij-Hij)xij+6mi=16nj=1wijHij,(10)s.t.6mi=1xij=bj,j=1,2,+,n,(11)6nj=1xij=ai,i=1,2,+,m,(12)wijHij Diji=1,2,+,mj=1,2,

9、+,n,(13)Hij Aijkijciji=1,2,+,mj=1,2,+,n,(14)6mi=16nj=1kij L,(15)xij,Hij 0kij=0,1,(16)式中,目标函数式(10)代表要求调整单位运费后,总运费和调整运价的费用之和最省;约束方程式(11)与式(2)仍相同,表示每个销地Bj的销量等于bj;约束方程式(12)与(3)相同,表示每个产地 Ai的产量等于 ai;约束条件式(13)是每条线路调整运价的成本不超过预算 Dij;约束条件式(14)表示如果调整从 Ai到 Bj的运价,那么调整量不超 过原运价;如果不调整从 Ai到 Bj的运价,则调整量为0;约束条件式(15)是指调

10、整运价的线路总数不超过 L条。约束条件式(16)是非负约束和 0-1 约束。以上模型的 目标函数是二次函数,约束条件也全是线性的,因此(P3)问题仍然是一个二次规划问题。2.2 带瓶颈限制的运价调整运输问题在(P2)问题的基础上,我们假设在调整运价的总预算一定的条件下,目标函数改变为调整运价后使从产地Ai,i=1,2,+,m 到销地Bj,j=1,2,+,n 的每条路线花费的运费中最大值最小,这个问题我们称为带瓶颈限制的运价调整运输问题。那么,(P2)问题的模型中约束条件不变,只是目标函数变为以下形式:minHij,xijmaxi,j(cij-Hij)xij,(17)显然,这是一个最大最小问题。

11、3 计算机求解实际问题Lingo 是一种专门用于求解数学规划问题的软件包。由于其执行速度很快,易于方便输入、求解和分析数学规划问题,因此在数学、科研和工业界得到广泛应用。已知某小型运输问题的产销平衡表、单位运价表和调整运价的费用表(见表 1、表 2)。以下分别用 Lingo 求解上面谈到的总调整预算一定的运价调整运输问题,以及其两种变形问题。表 1 目前的运价和产销平衡表元/t产地销 地B1B2B3B4B5B6B7B8产量 ai/tA16267425960A24953858255A35219743351A47673927143A52395726541A65522814352销量 bj/t 35

12、37223241324338表 2 调整单位运价的费用元产地销 地B1B2B3B4B5B6B7B8A1101285781410A25911861387A312796109512A4869411997A516961086126A685813591193.1 求解调整总预算约束下运价调整的运输问题假设总运价调整费用 D=500,Aij=0.5,将表1和表2的数据代入模型(P2),Lingo 求解该问256管理学报第 1卷第 3期 2004 年 11 月题结果见表 3、表 4。表 3 各条运输线路运费的调整量计算结果 元/t产地销 地B1B2B3B4B5B6B7B8A13.01.03.03.02.0

13、1.02.54.5A22.04.52.51.54.02.54.01.0A32.51.00.54.53.52.01.51.5A43.53.03.51.54.51.03.50.5A51.01.54.52.53.51.03.02.5A62.52.51.01.04.00.52.01.5表 4 运输计划的运量安排t产地销 地B1B2B3B4B5B6B7B8A10190041000A2100320000A30110000400A4000005038A5347000000A60022002730 最后得到的目标函数总的最小运输费用为332。3.2 求解带剖分限制的运价调整运输问题假设每条线路调整运价的最大费

14、用 D*=50,调整的线路数最多为 L=4,Aij=0.5。将表 1和表 2 的数据代入模型(P3),Lingo 求解该问题得:该调整 的线路为 A1B5,A2B4,A3B7,A5B1;调整量分别为 2、1.5、1.5、1。运输计划的运量安排与表 4 相同。最后得到的目标函数总的运输费用与调整运价的成本之和为 489.5。3.3 求解带瓶颈限制的运价调整运输问题仍假设总运价调整费用 D=500,Aij=0.5,将表1和2的数据代入模型(P4),Lingo 求解该问题的结果见表 5、表 6。表 5 各条运输线路运费的调整量计算结果 元/t产地销 地B1B2B3B4B5B6B7B8A13.01.0

15、3.03.52.01.02.54.5A22.04.52.51.54.02.54.01.0A32.51.00.54.53.52.01.51.5A43.53.03.51.54.51.03.50.5A51.01.54.52.53.51.03.02.5A62.52.51.01.04.00.52.01.5 最后得到的目标函数各条路线中花费的运输费用的最大值为 22.858 41。由上面的计算结果可以看出,这 3 种不同运价调整运输问题背景下的运价调整量,每条运输路线的运量是不同的,在解决实际问题时,要根据实际情况具体分析得出相对最优的调整方式和运输计划。表 6 运输计划的运量安排t产地销 地B1B2B3

16、B4B5B6B7B8A17.612 34215.039 02006.435 18411.429 20009.087 4214.997 468A211.291 8702.879 95107.944 4235.714 60202.270 4108.298 105A35.353 8986.478 298222.516 5776.530 97306.623 6861.496 568A45.604 4586.473 351015.103 8205.079 64606.114 7564.623 973A506.129 383006.530 97317.480 3007.497 6783.361 665A6

17、5.137 4290005.714 60214.519 700 11.406 050 15.222 2204模拟计算Arena 模拟系统随机生成不同规模的调整总预算约束下运价调整的运输问题,其中产量和销量是保持产销平衡的在 20,70 区间产生的随机数,各条线路运输单位费用和单位运价的调整费用都是 2,10 区间的随机数。运用 Lingo5.0(变量、约束、非线性变量和整数变量不受约束,工作内存为 64M)在 Pentium 计算机上对不同规模的调整总预算约束下运价调整的运输问题运行求解。图1 和图2 分别为运算规模为(16,22)的运价调整量和运量安排计划,图 3 和图 4 分别为运算规模为

18、(28,40)的运价调整量和运量安排计划。根据不同运输问题的产地和销地的规模,得出计算的迭代次数和运行时间(见表 7)。表 7运算规模的迭代次数和运行时间问题规模(产地,销地)迭代次数运行时间(6,8)6000001(12,18)30000011(24,36)49000432(28,40)45000855(48,72)20002706(64,84)68034346(84,94)41030919257调整运价预算约束下的运输问题模型与应用杨王 君张敏陈新图 1运算规模为(16,22)的运价调整量图 2运算规模为(16,22)的运量安排图 3运算规模为(28,40)的运价调整量图 4运算规模为(2

19、8,40)的运量安排通过对不同规模的调整总预算约束下运价调整的运输问题模拟计算,可以得出运用 Lingo5.0解决该问题有一定的局限性,随着问题规模的逐步增加,迭代次数和运行时间也急剧增加。当本文研究的调整总预算约束下运价调整的运输问题的运 算 规 模 超 过(80,100)或(100,80)以 后,Lingo5.0没有足够的工作空间来支持运算。对于大型的运输问题,需要很长的运算时间或者无法计算出结果。因此,在后续研究中,将考虑运用模拟退火、禁忌搜索、遗传算法等,得到高效且实用258管理学报第 1卷第 3期 2004 年 11 月的启发式算法来解决本问题。5结语本文主要研究了在运价的调整预算一

20、定的约束下,如何调整单位的运输费用和安排运输计划才能使总运费最省的运输问题和相应的模型。并在此基础上,给出了两类变形问题:带剖分限制的运费调整运输问题和带瓶颈限制的运费调整运输问题的模型和实际算例。最后通过模拟计算,分析了 Lingo 解决该问题的规模局限性和将来的后续研究方向。对这类问题的研究对交通运输系统、物流系统、管道配送系统和电力系统的运价调整和配送计划的制订有指导意义和参考价值。参考文献 1 Hitchcock F L.The distribution of a product fromseveral sources to numerous locationsJ.Journal of

21、Mathematical Physics,1941,20(2):224305 2 Gupta B,Gupta R.Multi-criteria simplex methodfor a linear multiple objective transportation problemJ.IndianJournalofPureandAppliedMathematics,1983,14(2):222232 3 宋业新,陈绵云,吴晓平.具有模糊信息的多目标运输问题求解J.模糊系统与数学,2001(3):8689 4Minghe Sun,Jay E Aronson.A tabu search heuris

22、ticprocedureforthefixedchargetransportationproblem J.EuropeanJournalofOperationResearch,1998,106(2-3):441456 5 李珍萍.最短时限运输问题及解法J.中国管理科学,2001(1):5056 6M avrommatisG,PanayiotopoulosJC.RisktransportationviaacliquenumberproblemformulationJ.European Journal of OperationResearch,2004,152(2):500506 7 高尚.最安全

23、路线运输问题研究 J.交通运输系统工程与信息,2001(4):328330 8 ShangtaiLiu.T hetotalcostboundofthetransportation problem with varyingdemand andsupplyJ.Omega,2003,31(4):247251 9 谢政,多磊,汤泽滢.带容量限制和手续费用的运输问题J.系统工程,1998(5):2531 10 李军.有时间窗的车辆调度问题的网络启发式算法 J.系统工程,1999(2):6671 11 王洪国,马绍汉.对称的运输问题及其逆问题J.经济数学,1999(4):4553作者简介:杨王 君(197

24、6),女,汉族,湖北武汉人。华中科技大学(武汉市430074)管理学院博士研究生。研究方向为管理科学。张敏,陈新,华中科技大学管理学院。管理学报 稿约1稿件内容(1)剖析我国大型企业的成功案例,从中提炼出符合我国文化的管理理论。(2)中国管理论坛、管理科学、管理工程(工商管理、公共管理)、管理艺术、基金项目巡礼、企业实证、管理文化、管理评论、学术探索、中国管理理论介绍、项目管理、域外传真、最新文萃、英文论文等领域的最新科研成果或各领域的学术进展评述。(3)国外管理科学领域重要佳作的译文(应取得作者的授权)。(4)国内外管理科学领域最新论文的文摘(每条 5001000字)。(5)针对新近出版的管

25、理类书刊重要热点的评论(推介或商榷)。2稿件规范(1)文稿内容不得有侵权和泄密问题,不得一稿两(多)投。(2)论文格式请按GB7713-87 科学技术报告、学位论文和学术论文的编写格式 书写,亦可参照本刊已发表的论文格式。(3)参考文献可择重要的列入,并请标出每一参考文献的类型,即专著M、论文集C、报纸文章N、期刊文章J、学位论文D、研究报告R、标准S、专刊P。未公开发表的资料请勿引用。(4)凡参考过本刊已发表的论文者,务请在论文的参考文献中标出。(5)提供以下英文:题名、作者姓名、工作单位、摘要、关键词。(6)第一作者需提供姓名、出生年、性别、民族、籍贯、工作单位、邮政编码、职务、职称、研究

26、方向、联系电话。其他作者只需提供工作单位。(7)获得各种基金资助的稿件,务请注明基金名称及编号。3稿件处理(1)本刊接受电子稿件。(2)2个月后稿件若未被采用,可以另行处理。(3)本刊对被采用稿件可作技术性修改,若不同意请在来稿中注明。(4)刊出论文的版权属本刊所有,其他媒体转载需征得本刊同意,本刊亦可向其他数据库推荐。(5)稿件一经采用,酌付稿酬,并赠当期刊物 1 册。4联系方式通讯地址:武汉市华中科技大学管理学院管理学报编辑部邮政编码:430074电话/传真:027-87542154电子邮箱:glxb 259调整运价预算约束下的运输问题模型与应用杨王 君张敏陈新ISSN 1672-884C

27、HINESE JOURNAL OF MANAGEMENTVol.1,No.3,Nov.,2004Bimonthly(Serial No.3)Edited and Published by:CHINESE JOURNALOF MANAGEMENT Magazine OfficeAdd:HuazhongUniversityofScienceandT echnology Wuhan ChinaDistributer:China National Publications Import&Export(Group)CorporationCode:1725BMMAIN TOPICS,ABSTRACTS&K

28、EY WORDSStrategic Supply Chain A New Focus onCompetition Among EnterprisesXIE Qihua(ShanghaiBaosteelGroupCorporation,Shanghai,China)p 249-254Abstract:The strategic supply chain,aquasi-marketstructure,placesweightoncompetition-based integration,distinguishingitself distinctly from the conventional su

29、pplychain of market transaction type and integratedsupply chain of internal transaction type.In thisstrueture the strategic synergy was pursuiedamongtheenterprisesandtheverticalintegrationofcorecompetitivenessconcentrated,beingcharacteristicallycoordinative,quick-responding and divergentinbusinessor

30、ientation.Chineseenterpriseswould bring full play to their advantages,adopttheconceptofthecompetition-basedintegration,step up the system innovation andestablish strategic supply chain,to pursuit longand durable the competition.Key words:strategic supply chain;quasi-marketstructure;strategicsynergy;

31、corecompetitivenessModel ofTransportation and its Applicationwith Freight Adjustment Budget LimitationYANG Jun(Huazhong University of Science&Technology,Wuhan,China)ZHANG MinCHEN xinp 255-259Abstract:A special type of transportationproblem was studied to optimally adjust freightandtransportgoodswith

32、thelimitationoffreight adjustment budget.The basic model ofthis problem was formulated and two variantmodels,split model and bottleneck one wereproposed.The computational example of thisproblem was given.T wo variant problems weresolved by Lingo.T he scale limitation solved byLingo was analyzed by t

33、he simulation process.Key words:transportation;freight adjust;budget limitationStudy of Value-allocation of Supply chainGameAnalysisofPricingofIntermediateProductsDU Yifei(University of ElectronicScience and Technology of China,Chengdu,China)LI Shimingp 260-263Abstract:Agameofhowtopriceintermediatep

34、roductinthebasic two-firmsupply chain was studied.How to ascertain theprice of intermediate product respectively wasdiscussed under the conditions that the leadingfirmhasdominantrightofpricingofintermediate product and that the supplying firmhas the right.By assuming and calculating amodel,itwas con

35、cludedthat who has thedominant right of pricing intermediate productwill win more profit.T he sum of two firmsprofit and the industrial chain maximal profitswere compared.It was found that the former issmaller than latter in two conditions.Key word:industrial chain;intermediateproduct;non-cooperatio

36、n game;pricingDevelopments of Enterprise Strategic Theoriesand Their Research Trend ZHANG Yi(Chongqing Jiaotong University,Chongqing,China)ZHANG Ruip 264-272,284Abstract:Traditionalstrategictheoryieshave already beenchallenged owingtothechange of the new reality environment.Internaland external scho

37、lars have expanded enterprisestrategic theories from their different views,8branchfieldsweresummarized,including:organization viewpoint,cooperate one,naturalone,social one,political one,network one,comprehensive one and ecologic one.Their basicthoughtstheandresearchsituationswereenpounded.T he ecologic development tread oftheenterprisestrategictheorieswerealsorevealed,to provide the complete view angle forthe research of strategic theory.Key words:enterprise;strategic theory;3MAIN TOPICS,ABSTRACT S&KEY WORDS