论文题目:钢管订购与运输的优化模型27队队长:杨璐学号:41005234专业:信计队员:高春妮学号:41005155专业:数应队员:贺瑞瑞学号:41012186专业:计科2012年07月19日1钢管订购与运输的优化模型摘要本文讨论了在铺设天然气管道的过程中如何合理订购与运输钢管以使总费用最小的优化问题。问题一是在一定约束条件下以钢管订购和运输的总费用为目标函数的非线性优化问题。总费用由订购钢管的总费用、从钢厂到站点运输钢管的总费用及从站点开始铺设钢管的总费用三部分组成。订购钢管的总费用和从钢厂到站点运输钢管的总费用分别通过在各厂购买量与各厂出厂销价和在各厂购买量与从各钢厂到各站点运输单位钢管的最小费用的线性运算得到。从站点开始铺设钢管的总费用通过等差数列求和得到。在求从钢厂到站点运输钢管的总费用时,关键是采用弗洛伊德算法,用MATLAB软件编程求出单位钢管从各钢厂运往各站点最小运输费用(见表3)。约束条件可由题目相应已知条件给出,故可建立钢管订购与运输的优化模型一。利用LINGO软件编程求解出此模型,得到钢管订购和运输的最小总费用为1280837万元,并经整理分析给出钢管订购与运输方案(见表4)和钢管铺设方案(见表5)。问题二是对问题一中模型的灵敏度分析,通过控制变量的方法即每次只让一家钢厂的销价或生产上线发生变化并且每次的变化是相同的,分别得出:6S钢厂钢管的销价变化对总费用影响最大,5S和6S钢厂钢管的销价变化对购运计划影响最大;1S钢厂钢管的产量上限变化对总费用影响最大,3S钢厂钢管的产量上限变化对购运计划影响最大。问题三是对问题一的推广,站点向左右两边铺设变为向三个方向铺设,在问题一中模型基础上增加一些支路变量和约束条件,同时在目标函数中增加相应的铺设费用,由此建立了钢管订购与运输的优化模型二。利用LINGO软件编程求解得到钢管订购和运输的最小总费用为1414800万元,并给出钢管订购与运输方案(见表11)和钢管铺设方案(见表12)。除问题三中对模型的推广,本文的建模思想还可以用于其他领域诸如煤炭的运输来提供电力等。关键词非线性优化;弗洛伊德算法;灵敏度分析;控制变量2一.问题重述运输是天然气供应链中的重要环节。在我国,管道运输是天然气运输的主要方式。在铺设管道的过程中,为了降低其成本,往往需要制定一个合理的钢管订购和运输方案。现要铺设一条1521AAA的输送天然气的主管道,如图一所示。经筛选后可以生产这种主管道钢管的钢厂有1S,2S,……,7S。图中粗线表示铁路,单细线表示公路,双细线表示要铺设的管道(假设沿管道或者原来有公路,或者建有施工公路),圆圈表示火车站,每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计,1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管,至少需要生产500个单位。钢厂iS在指定期限内能生产该钢管的最大数量为is个单位,钢管出厂销价1单位钢管为ip万元,如下表1:i1234567is80080010002000200020003000ip1601551551601551501601单位钢管的铁路运价如下表2:里程(km)≤300301~350351~400401~450451~500运价(万元)2023262932里程(km)501~600601~700701~800801~900901~1000运价(万元)37445055601000km以上每增加1至100km运价增加5公路运输费用为1单位钢管每公里0.1万元(不足整公里部分按整公里计算)。钢管可由铁路、公路运往铺设地点(不只是运到点1521,,,AAA,而是管道全线)。(1)请制定一个主管道钢管的订购和运输计划,使总费用最小(给出总费用)。(2)请就(1)的模型分析:哪个钢厂钢管的销价的变化对购运计划和总费用影响最大,哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大,并给出相应的数字结果。(3)如果要铺设的管道不是一条线,而是一个树形图,铁路、公路和管道构成网络,请就这种更一般的情形给出一种解决办法,并对图二按(1)的要求给出模型和结果。3A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A11A711A11A8A11A911A11A10A11A12A13A14A15S1S2S3S4S5S6S7图一A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A19130190260100A2A3A4A5A6A7A8A11A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16A17A18A20(A21)图二4二.问题分析问题一是在一定约束条件下的非线性优化问题。由题意知,目标函数是钢管订购和运输的总费用w。总费用w可以分为三个部分:订购钢管的总费用1w、从钢厂到站点运输钢管的总费用2w及从站点开始铺设钢管的总费用3w。订购钢管的总费用1w可通过在各厂购买量ijx与各厂出厂销价ip的线性运算得到。在每个厂购买的钢管量必须不少于500km且不超过该钢厂的生产上限,否则不在该厂购买,此为一约束条件。从钢厂到站点运输钢管的总费用2w同样可由在各厂购买量ijx与从各钢厂到各站点运输单位钢管的最小费用ijc的线性运算得到。关键要先找出各个钢厂到各个站点的最优路径,在此要把铁路和公路最优路径转换为最小费用,采用弗洛伊德算法,用MATLAB软件编程求出单位钢管从iS运输到jA的最小运输费用ijc。在计算从站点开始铺设钢管的总费用3w时,为了计算方便,假设钢管从站点向两边以1km为单位进行铺设,即车到达站点后先放下1km的钢管,以后每向前开1km便将1km的钢管放下。钢管运往各站点jA之后,从此站点向两边开始铺设,且只铺设相邻的两段,则此部分费用可以通过等差数列求和得到。由图一知,站点1A和15A只能向一个方向延伸。又从jA站点向右边和从1jA站点向左边铺设的钢管长度之和等于jA到1jA站点的距离,从jA站点向左右两边铺设的钢管长度之和等于jA站点从7个钢厂总共购买的钢管数量,且铺设长度自然是大于或等于零,由此又得几个约束条件。经过以上分析便可以建立钢管订购与运输的优化模型一。问题二即为对问题一中模型的灵敏度分析,通过分析知:不同钢厂向不同站点销售钢管,不同钢厂对钢管有不同销价,任意一个钢厂销价发生变化都可能会影响购运计划和总费用,而不同钢厂销价发生相同变化,对购运计划和总费用的影响程度不同。因此,可以通过控制变量的方法即每次只让一家钢厂的销价或生产上线发生变化并且每次的变化是相同的,由此找出哪个钢厂钢管的销价变化对购运计划和总费用的影响最大。问题三实际上是对问题一的推广,故此模型的建立和求解与钢管订购与运输的优化模型一类似,只是由于树形图的出现,某些管道处会出现多支路。此时在问题一的基础上将站点向左右两边铺设变为向三个方向铺设,可考虑多增加一些支路变量,并增加约束条件,在这里约束条件的提出思路和模型一的一样,只是比较多而已,同时在目标函数中增加相应的铺设费用。三.基本假设1.假设沿管道或者原来有公路,或者建有施工公路,即在计算运费时,沿管道铺设路线上的公路与其它普通公路相同(1单位钢管每公里0.1万元);2.假设运输费只按铁路、公路里程收取,即不考虑火车、汽车由于停靠站等其他因素带来的费用;3.假设所有钢管在指定期限内都能按时生产并运到指定地点;4.假设钢管可由铁路、公路运往铺设路线任一地点;5.假设订购的钢管总数恰等于需要铺设的管道总数;6.假设钢管在铺设过程中以1km为单位进行铺设;7.假设钢管在铺设过程中由站点向左右两边进行铺设,且只铺设相邻两段。5四.符号说明五.模型建立、求解与结果分析在钢管订购和运输时,有不同的钢厂和站点,根据距离的远近和价格的不同,不同钢厂和站点要选择不同的路径来订购和运输钢管。如何选择最佳路径使得总费用最小是这个过程中面临的一个实际问题。为了合理解决这个问题,要建立最优订购和运输模型。5.1钢管订购与运输的优化模型一在钢管订购与运输过程中,目标函数为所花总费用w。通过对题目的分析,总费用w可以分为三个部分:订购钢管的总费用1w、从钢厂到站点运输钢管的总费用2w及从站点开始铺设钢管的总费用3w,即:123(1)从题目条件知输送天然气主管道有1A,1A,……,15A15个不同站点,有1S,2S,……,7S7个不同的钢厂可以生产该钢管。由表1知不同钢厂有不同的出厂销价is和不同的生产上限ip。因此可以得到第j个站点向第i个钢厂订购钢管的费用为ijixp,故订购钢管的总费用1w为:715111ijiijwxp(2)又由题意知,15个站点或者都不向iS钢厂订购钢管,或者订购钢管数量介于其生产下限500个单位和生产上限is个单位之间,即:1515000,1iijiiijxs(3)其中0i表示15个站点都不向iS钢厂订购钢管,1i表示有站点向iS钢厂订购钢管。由图一知从各钢厂iS到各站点iA运输钢管有多条不同的路径,且运输途中单位钢管公路和铁路运价计费方式不同,所以需要寻找最优路径,使得单位钢管从iS运输到jA的运输费用最小。在此要把铁路和公路最优路径转换为最小费用,符号表示意义ijxjA站点在iS钢厂订购的钢管数量isiS钢厂在指定期限内能生产该钢管的最大数量ipiS钢厂每单位钢管的出厂销价ijc从钢厂iS到站点jA运输单位钢管的最小费用jy从jA站点开始向右边铺设的距离1jy从1jA站点开始向左边铺设的距离jA站点jA到1jA之间的管道距离1w订购钢管的总费用2w从钢厂到站点运输钢管的总费用3w从站点开始铺设钢管的总费用w钢管订购和运输的总费用6采用弗洛伊德算法,用MATLAB求解出最小运输费用ijc,具体数据如下表3所示:表3问题一单位钢管从iS运输到jA的最小运输费用(单位:万元)1S2S3S4S5S6S7S1A170.7215.7230.7260.7255.7265.7275.72A160.3205.3220.3250.3245.3255.3265.33A140.2190.2200.2235.2225.2235.2245.24A98.6171.6181.6216.6206.6216.6226.65A38.0111.0121.0156.0146.0156.0166.06A20.595.5105.5140.5130.5140.5150.57A3.186.096.0131.0121.0131.0141.08A21.271.286.2116.2111.2121.2131.29A64.2114.248.284.279.284.299.210A92.0142.082.062.057.062.077.011A96.0146.086.051.033.051.066.012A106.0156.096.061.051.045.056.013A121.2171.2111.276.271.226.238.214A128.0178.0118.083.073.011.026.015A142.0192.0132.097.087.028.02.0对表3中的数据分析可以得到从钢厂到站点运输钢管的总费用2w:715211ijijijwxc(4)从假设知沿铺设管道或者原来有公路,或者建有施工公路,因此,站点铺设的费用全部以公路的运价计算,即1单位钢管每公里0.1万元。钢管运往各站点jA之后,从此站点向两边开始铺设,且只铺设相邻的两