钢管订购和运输问题的数学模型..docVIP

钢管订购和运输问题的数学模型 摘要 本文根据问题的条件和要求，建立了两个模型，模型一为单目标非线性规划模型；模型二为双容量最小费用循环流模型，并通过求解这两个模型，完整地解决了问题。 由于铁路运输费用函数具有不可加性，不能直接应用现有的最短路算法来求铁路和公路交通网中任意两点间最小费用路问题。本文采用了一种启发式递推算法，巧妙地解决了这一问题。 在单目标非线性规划模型中，将管道铺设分为两个过程。先将钢管从钢管厂运到管道和路道交叉口，再从交叉口铺设到管道线上。这样，总的运输费用就化为两个过程的运输费用之和。由于本模型的目标函数是非线性的，这里采用遗传算法对其求解。所得问题（1）的最小费用为127.9661亿元。问题（2）的结果为的钢管销售价格的变化对购运计划及总费用影响最大，而的钢管产量的上限变化对购运计划及费用影响最大。 把5171公里长的主管道线路按每公里划分一段，分为5171个点，每个点对应一个单位的钢管。从钢管厂运送5171个单位的钢管到5171个点，每个钢厂的容量有上、下限，由此可以将该问题转化为图论中的一个双容量最小费用循环流模型。文中设计了一个近似有效的算法，对该模型进行求解，所得问题（1）的最小费用为128.025亿元；问题（2）的结果与模型一得结果相同，问题（3）的费用为130.9840305亿元。 文中对两个模型都作了一定的理论分析，具有较广泛的适应性。由于模型二将连续的管道线简化分成了5171个点，求解所得到的结果稍劣于模型一得结果，但模型二具有较高的理论价值。对于实际中，将一些实际问题抽象简化为数学问题来解决，从方法上具有一定的启发性。 最后，对该问题进行了深刻探讨，不仅解决了管道线为树形图的情况，还解决了管道线为一个网络的情况，同时将此问题推广到了一个更一般的网络图问题。对于n=1,n=2的情形已完全解决，对于问题提出了它是一个NP完全问题的猜想。 关键词：运输问题 非线性规划 双容量最小费用循环流 效益问题 1问题的重述 要铺设一条的输送天然气的主管道，入附图6-1所示。经筛选后可以生产这种主管道的钢管厂有。图中粗线表示铁路，单线条表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站（图中的T（），每段铁路、公路和管道旁的数字表示里程（单位km）。1km主管道成为1单位钢管。 如果一个钢管厂承担制造这种钢管任务，至少需要生产500个单位。钢管厂S在指定期限内能生产该钢管的最大数量为s个单位，钢管出厂销售1个单位的钢管为p万元，具体数据如表6-1所示。1个单位钢管的铁路运价如表6-2所示，1000km以上每增加1至100km运价增加5万元。 表6-1 钢管厂的销售单价 i 1 2 3 4 5 6 7 s 800 800 1000 2000 2000 2000 3000 p 160 155 155 160 155 150 16 表6-2 钢管的铁路运输单价 里程/km 300 301~350 351~400 401~450 451~500 运价/万元 20 23 26 29 32 里程/km 501~600 601~700 701~800 801~900 901~1000 运价/万元 37 44 50 55 60 公路运输费用为1单位0.1万元/km（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运送到,而是管道全线）。需要解决的问题是： 制定一个主管道的订购和运输计划，使总费用最小（给出总费用）。 就问题（1）的模型进行分析，哪个钢管厂的钢管销售价格变化对购运计划和总费用影响最大，并给出相应的数字结果。 如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，对这种更为一般的情形给出一种解决办法，并对于附图6-2按问题（1）的要求给出模型结果。 2.模型的假设 (1)在制定订购钢管计划时，数据加精确到0.001个单位，即精确到米。此假设保证在理论上得到精确的结果。 （2）在运输和铺设的过程中钢管数量无损耗。 不需要考虑钢管运输过程中除运费外的其他费用。 3.符号及文字说明 A表示住管道树型图的第j（）个顶点； S表示第个钢铁厂； c表示从S运送一个单位的钢管到A得最小费用； T表示铁路树形图除S外的顶点（具体标号见附图6-1）; U表示钢厂S（）生产这种钢管的数量； t表示第第k（）段管道的长度； v表示铁路、公路和管道构成网络的所有节点； V表示所有v的集合； （y）表示y的小数部分； [y]表示不超过y的整数部分； “最小费用路”表示从S (i=1,2,)运输1个单位钢管道A（）运输费用最小的路。 4.问题的分析 无论采用哪一条运输路线，最终铺设到主管线上的每单位钢管均要经过与它所在位置相邻