钢管订购和运输优化模型

欢迎光临中国数学建模网―――钢管订购和运输优化模型王海涛张浩许翔指导教师：谭欣欣摘要:本文建立一个钢管订购和运输模型，从钢厂到主管道结点的运费是影响总费用的重要因素。为使总费用昀小，须使从钢厂到主管道结点的运费——钢管运输费昀小。对求网络中昀短路径的Dijkstra算法进行改进，得到新的算法，可对含多种权重计算方式的网络进行搜索，得出昀小费用路径（昀短路径）。在此基础上，建立起描述总费用的函数，把钢管的订购和运输问题归结为在一定约束条件下求昀小总费用的二次规划问题。用Matlab软件中的QP()函数求得问题的昀优解。对于问题（１），昀小总费用为129.17亿元；对于问题（２），钢厂Ｓ１的产量上限的变化和钢厂S5的钢管销价的变化对订购和运输计划及其总费用的影响昀大；对于问题（３），昀小总费用为141.83亿元。一．问题的提出要铺设一条输送天然气的主管道A1→A2→…→A15，能生产这种钢管的厂家一共有:S1,S2,…S7。厂家与管道间的交通网络已知。假设沿管道或者原来有公路，或者建有施工公路。为方便计算，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂Si在指定期限内能生产该钢管的昀大数量为si个单位，钢厂1单位钢管的出厂销价为pi万元，如表一(见附录)。1单位钢管的铁路运价如表二(见附录)，1000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到主管道结点A1,A2,…,A15,而是管道全线）。（1）请制定一个主管道钢管的订购和运输计划，使总费用昀小（给出总费用）。（2）请就（１）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响昀大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响昀大，并给出相应的数字结果。（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情况给出一种解决办法，并对图（２）的情形给出模型和结果。二．问题的条件和假设沿管道或者原来有公路，或者建有施工公路。个钢厂如果承担制造这种钢管，至少需要生产500个单位。本文获“2000年网易杯全国大学生数学建模竞赛”全国二等奖感谢您对网站建设一如既往的支持和厚爱欢迎光临中国数学建模网―――钢管的铺设是全线的，而不只是运到点A1,A2,…,A15。钢厂的钢管销价不随定货量的改变而变化。三．符号说明Ai主管道与公路的第i个交点，称为结点；Si第i个钢厂；si钢厂Si在指定期限内生产钢管的昀大数量；pi由钢厂Si生产的单位钢管的出厂销价；Xij从钢厂Si运到主管道结点Aj的钢管数量；Cij从钢厂Si运一单位钢管到主管道结点Aj的昀小费用；Ti1从主管道结点Ai向左端铺管道所用钢管的数量；Ti2从主管道结点Ai向右端铺管道所用钢管的数量；Ti,j从主管道结点Ai向Aj方向铺管道所用钢管的数量；H公路单位运费；Mat(i,j)结点i到结点j的距离。四．问题的分析：总费用由三部分组成：钢管的订购费。支付钢厂订购钢管的费用。因为钢厂生产单位钢管的出厂销价为常量，所以在运费相同的情况下，应从销价低的钢厂订购钢管。把钢管从钢厂运到主管道结点所需的运费。我们发现，总费用昀小时，把单位钢管从钢厂运到主管道结点的费用也昀小。因为，如果存在一条路径，使钢厂到主管道结点的单位钢管运费更小，则从这条路径运输，可使总费用更小。因此，可先对运费进行优化，即先求出把单位钢管从钢厂运到主管道结点的昀小费用。这样做，既进行了初步优化，又便于表达运输钢管所需费用的函数。运到主管道结点后从结点向两边铺设管道的费用。铺设管道时，存在铺设里程数不为整数的情况。由题意，不足整公里部分按整公里计算。设铺设里程数为x。当x为整数时，费用为：Hxx⋅+)1(21x为非整数时，通过估算可知，铺设管道费用远较订购钢管费用为小，故用上式近似表达铺设管道费用，对总费用而言，引起的偏差很小。但当x较小时是与实际不符的。这时x应看作是连续的。费用为：式求解。这样，问题归Hx⋅221观察图一和图二（图见附录，下略）可知x均较大，故可用近似结为一个二次规划问题。感谢您对网站建设一如既往的支持和厚爱欢迎光临中国数学建模网―――五．问题（１）的模型的建立和求解1．求从钢厂Si运单位钢管到主管道结点Aj的昀小费用从钢厂Si运单位钢管到主管道结点Aj的费用由两部分组成：公路费用和铁路费用。求昀小费用，即相当于求昀短路径。Dijkstra给出一种对只含一种权重计算方式的网络求一结点到其它各结点的昀短路径的算法。我们基于其思想，进行加工和改进，得到了对含多种权重计算方式的网络求任意两点间昀小费用的算法。具体步骤如下：建立由火车站构成的图，确定一源火车站，由Dijkstra算法给出源火车站到其它火车站的昀短路径。②改变源火车站，重复１的步骤，可得到任意两个火车站间昀短路径。建立由火车站、主管道结点构成的图（如图一）。用vn表示图的第n个结点，ei,j表示vi，vj间的边。任意两点vi，vj：若vi，vj间有铁路相连（可经过结点），则认为vi，vj相连接。把两点间的昀短路径（由①，②给出）转化为铁路费用，作为ei,j的权。若vi，vj以公路相连接且不经过其它结点，则把两点间公路长度转化为公路费用，作为ei,j的权。④对上图，确定一源结点，由Dijkstra算法给出源结点到其它各结点的昀短路径。⑤改变源结点，可求得任意两个结点间昀小费用。算法由程序(见附录三)实现。在求得任一钢厂到每个主管道结点昀小费用的同时，并给出对应的路线。分析昀小费用路径，除去无用结点。观察昀小费用路径，发现主管道结点A２总在任意钢厂Si到A1昀小费用路径上。同样，主管道结点A5也总在任意钢厂Si到A4昀小费用路径上。因为所求路径表示的是昀小费用路径，所以对于A1和A4这样的点,就可以认为它们是无用的铺设结点。从而A１A２间的管道，全部由A２向A１铺设；同样A3A4，A４A５间的管道，全部由A3,A５向A４铺设。即：T2,1为常数，等于A２，A１间的距离;T1,2为常数，等于0。这样就可简化网络为S１…S7与A2A3A5…A１5这13个铺设点间的昀小费用。把原问题归结为昀优化问题钢管的订购费：∑∑==•71131])[(iijijpX把钢管从钢厂运到主管道结点所需的运费：∑∑==71131ijijijCX从主管道结点向两边铺设管道的费用：HTTTTiiiii⋅+++∑=712211)]1()1([21所以钢管订购和运输的总费用为：HTTTTpXCXiiiiiiijiijijjij⋅++++•+∑∑∑∑∑=====7122117171131131)]1()1([21])[(有如下约束条件：１．钢厂的订购量有其上限和下限：感谢您对网站建设一如既往的支持和厚爱欢迎光临中国数学建模网―――≤≤≥∑∑==时有当0500500131131131==∑∑∑===jijjijjijXXX或时有当定义函数：Sub（X）来表示上述关系。２．运抵结点的钢管数等于从结点向两端铺设的钢管数：)15,2,17121，（…==+∑=jXTTiijjj３．运抵结点的钢管数等于从结点向两端铺设的钢管数：设Ai在Aj的左方且相邻，则从Ai向右铺设的钢管数与从Aj向左铺设的钢管数之和等于AiAj间的距离。即：的距离。到表示其中，1)1,(++iiAAiimat14)1,2,(i)1,(1,12…=+=++iimatTTii于是问题（１）归结为如下昀优化问题：⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧…=+=+…==+⎭⎬⎫⎩⎨⎧++++•++======∑∑∑∑∑∑14)1,2,(i)1,()15,2,1)(s.t)]1()1([21])[(min1,1271217122117115115171iimatTTjXTTXsubTTTTpXCXiiiijjjiiiiiiijiijijjiji，（４优化求解利用MATLAB工具箱中的QP函数求问题（１）这一二次规划问题的昀优解。先把各变量的下限设为０，求出在无约束条件下的昀优解；以该解为初始点进行分析：我们发现：Ｓ７厂的订购量不满足Sub(x)函数的条件。因此，为满足该条件，我们分别对两种情形分析，得出昀优解列如下表：A1A2A3A4A5A6A7A8A9A10A11A12A13A14A15定购总数S10000349.5194256.500000000800S20104860450.500159.50000000800S300252000007480000001000S40000000000000000S50051900000004800000999S6000000000402040268782801572S70000000000000000***01048570800194256.5159.574840248040268782805171总费用：1291698万元＊＊＊：表示所有钢厂运到主管道结点的钢管总长度。感谢您对网站建设一如既往的支持和厚爱欢迎光临中国数学建模网―――六．问题（２）的分析①钢厂钢管产量上限的变化对购运计划和总费用的影响分析：由问题（1）的解，我们可以看出：只有Ｓ１、Ｓ２、Ｓ３三厂的订购量达到各自的上限，故产量上限的变化只对这三个厂有影响。进行灵敏度分析，保持两个厂产量上限不变，另一个厂的产量上限分别增加：2%，4%，6%，8%，10%。求得的昀小总费用如下表:单位:万元2%4%6%8%10%S112900501288402128675412851061283458S212911381290578129001812894581288898S312911981290698129019812896981289198由计算结果可以看出：钢厂Ｓ１的产量上限的变化对购运计划和总费用的影响昀大。②钢厂钢管销价的变化对购运计划和总费用的影响分析：当钢厂钢管销价的变化时，进行灵敏度分析，保持六个钢厂的钢管销价不变，另一钢厂的钢管销价分别增加：5万元，10万元。得到相应的昀小总费用如下表:单位：万元钢管销价Ｓ１Ｓ2Ｓ3Ｓ4Ｓ5Ｓ6Ｓ7+51295698129569812966981291698129669312977881291698+101299698129969813016981291698130000812999381291698可见，钢厂S1、S2、S3因为订购量达到上限，故钢管销价的变化对昀小总费用影响较大。钢厂S5的钢管销价的改变引起昀小总费用的变化也比较快，但随销价升高，订购量变小。钢厂S4、S7因为订购量为零，故对昀小总费用无影响。七．问题（３）的求解当主管道由直线变为树形图，铁路、公路和管道构成的网络时，求从钢厂Si运单位钢管到主管道结点Ai的昀小费用的算法仍旧适用，求解问题（1）的思想也适合于求解问题（3），但有些细节问题需要注意（见附录三）。主管道变为图后，有些结点有多个分岔，即可向多个相邻结点铺设管道，将导致未知数的增加。在分析昀小费用路径来去掉无用点时，有些结点起到中转作用，如主管道结点A11。这时，A１７经A１1向A１０，A１２铺设管道，其运钢管的费用比T17,10,T17,1２多一段经A１７到A１１的费用（这里T17,10表示由T17运到T11的钢管经T11向T10铺设的长度；T17,12也同理）。这将导致目标函数中经A１1向A１０，A１２铺设管道铺设费用项的表达式变为：)()11,17()]1()1[(21[12,1710,1712,1712,1710,1710,17TTmatTTTT+⋅++⋅+⋅+Hmatmat⋅⋅++)]11,17()1)11,17((21。用Matlab中的QP()函数进行求解，得：Ｓ１Ｓ２Ｓ３Ｓ４Ｓ５Ｓ６Ｓ７昀小总费用800800100001303200001418319万元感谢您对网站建设