数学建模-钢管订购和运输

1钢管的订购和运输优化模型摘要本文建立的多元非线性优化模型。问题一在保证天然气管道铺设可以顺利实施的情况下，给出了钢管的订购与运输总费用最小的方案。在求钢管由钢厂运输到站点的费用和铺设钢管时产生的运输费，根据图一，我们通过深度优先遍历的方法对整个图一进行路径搜索，然后根据每条搜索到的路径上的铁路和公路上的不同权重，找到了各个钢厂到各个天然气管道上的站点的最佳路径。对于整个优化过程我们给出了相关的算法，并用matlab软件编程，经过一系列计算之后，得出了最优的订购与运输方案。对于问题1，我们求得的最优解为（具体方案见表五）：1S2S3S4S5S6S7S总费用800800100001190118106102786.1对于问题2我们经过计算比较得出：6S钢管销价的变化对购运计划和总费用影响最大。1S的生产上限的变化购运计划和总费用影响最大。对于问题3，当天然气管道呈现的是一个树状图的时候，我们得到的最优解为（具体方案见表六）:1S2S3S4S5S6S7S总费用800800100001450185306104148.1关键字：非线性优化深度优先遍历最佳路径2一、问题重述要铺设一条1521AAA的输送天然气的主管道,如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有721,,SSS。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂iS在指定期限内能生产该钢管的最大数量为is个单位，钢管出厂销价1单位钢管为ip万元，如下表：i1234567is80080010002000200020003000ip1601551551601551501601单位钢管的铁路运价如下表：里程(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二、模型假设1、假设沿管道或者原来有公路，或者建有施工公路；2、运费只按铁路、公路里程收取，即不考虑火车、汽车由于停靠站等其他一切外因带来的费用；3、钢管在铺设过程中以1km为单位进行铺设；4、钢管可由铁路、公路运往铺设路线任一地点；5、所有钢管在指定期限内都能按时生产并运送指定地点；6、钢管铺设过程中由站点向左右两边进行铺设。三、符号说明iS：第i个厂72,1i；jA：第j个站点152,1j；ijm:iS向jA运送的钢管量单位（km）；imax:iS在指定期限内的最大生产量单位（km）；jR:jA向右铺设的钢管量单位（km）；jL:jA向左铺设的钢管量单位（km）；jD:jA到1jA间的距离142,1j单位（km）；0D:管道全线总长单位（km）；iP:iS钢管出厂销价72,1i单位（万元/单位）；ijT:iS向jA运送一单位钢管所需的铁路费单位（万元/单位）；ijD:iS向jA运送一单位钢管所需的公路费单位（万元/单位）；M：购买钢管所花的总费用；Y:由厂到站点所需运输总费；0Y：由站点到铺设地点所需运输总费；W:订购和运输钢管所需总费用单位（万元）。5四、问题分析问题一是在一定约束条件下的非线性优化问题，由题意知，拟建立以总费用为目标函数来寻求最优解。总费用W由钢管的购买费、厂到站点的运输费以及站点到铺设地点的运输费三部分组成。一、钢管的购买费可由在每个厂的购买量与每个厂的出厂销价的线性运算得到。在每个厂购买的钢管量必须大于500km，否则则不在该厂购买。可以构造一个71的矩阵S，那么当iS为0时，表示不在第i个钢厂购买，否则则在第i个钢厂购买大于500km的钢量。二、要求得每个钢厂到站点的运输费需先知道每个厂到各个站点的钢管输送量，以及所选择的路线即铁路总长和公路总长，所以需要首先计算出各个钢厂到每个站点的最佳运输路径，使得平均单位公里的运输费用最小。但是由于铁路每公里的运输费用不是线性变化，而是变化不均匀的分段函数。在这里，我们利用深度优先遍历，找到某个厂到达各个站点的所有路径，然后根据每条路径的铁路和公路里程数计算出平均每公里运输费用最小的一条。以此类推，计算出所有钢厂到所有站点的最佳路径。三、在站点到铺设地点的运输费问题上，如果我们认为车边向前走边进行铺设，即边走边将钢管放下，那么就需要通过积分来计算。但是，尽管用积分算下来结果会很精确，但在实际中不可能这样实施。另外，这也与题目中不足整公里的按整公里计算相矛盾。所以，我们假设以1km为单位进行铺设，即铺设中车每向前开1km便将1km的钢管放下。由于铺设管道是线型的，除了两个端点外，每个站点需要往两边进行铺设管道。所以，假设第j个站点往左、右边铺设管道为jR和jL公里，则由站点到铺设地点的运输费就可以通过等差数列求和得到。问题二即为对问题一中模型的灵敏度分析，在讨论各厂的钢管销价和生产上限对购运计划和总费用的影响时，只让其中一个量变化，其他一切条件皆不变，即逐个变量单独分析。问题三即为问题一中模型的推广，在问题一的基础上将站点向左右两边铺设变为向三个方向铺设，按问题一处理即可。五、模型建立（问题一）总费用W由钢管的购买费M、厂到站点的运输费Y以及站点到铺设地点的运输费0Y三部分组成，则0YYMW在第i个厂的购买费应为15个站点在第i个厂的购买总量与该厂销价的乘积总和，即151jjijPM，则总购买费71151)(ijjijPmM6第i个厂向第j个站点的运输费为运送量ijm与运送1单位所需铁路费和公路费的和的乘积，第i个厂向各个站点运送钢管的总运费即为151jijijijGTm，则各厂到站点的运输费71151ijijijijGTmY要算出钢管由站点运送到铺设地点的费用0Y需知道钢管按何种方式进行铺设的。在问题分析里一讨论边走边铺与实际不符，且有违题目条件，所以我们假设钢管在铺设过程中以1km为单位进行铺设，且由站点向两边进行铺设，则0Y可由等差数列求和公式得到，即15214101.0211.021jjjjjjLLRRY由于一个钢厂如果承担制造这种钢管，至少需要生产500个单位，且各厂在指定期限内有生产上线，则在第i个厂的购买总量需满足ijijmmax500151或1510jijm钢管由站点向左右两边进行铺设，则第j个站点向右铺设部分与第1j个站点向左铺设部分之和应为两站点之间的管道长度，且第一个站点向左铺设部分与最后一站点向右铺设部分都为0，即jjjDLR1142,1j01L015R第j站点向左铺设部分与向右铺设部分之和应为七个厂向第j站点输送钢管总量，即71iijjjmLR152,1j综合考虑钢管的购买费M、厂到站点的运输费Y以及站点到铺设地点的运输费0Y，钢管的订购和运输优化模型建立如下：目标函数7minW71151)(ijjijPm+71151ijijijijGTm+（1521412121jjjjjjLLRR）1.0ijijmmax500151或1510jijm71iijjjmLR152,1js.tjjjDLR1142,1j01L015R六、模型求解由于铁路、公路相互交错，无法直接选出钢厂到站点的费用最小路线，所以此处我们采用深度优先遍历方法。首先建立一个39维数组，将图一中39个交点两两之间有铁路、公路连接的用具体路线长写入数组，且铁路用负数表示，公路用正数表示，而没有路线连接的用无穷大代替，最后换算成到各站点的铁路、公路总费。全过程通过matlab编程完成（程序见附录），。表一iS到iA的最小费用（单位：万元/单位）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.65A381111211561461561666A20.564.6105.5139.6130.5140.5150.57A3.1869613112113114188A21.271.286.2116.2111.2121.2131.29A64.2114.248.284.279.284.299.210A92142826257627611A96146865133516612A106156966151455613A121.2171.2111.276.271.226.238.214A1281781188373112615A1421921329787282因为matlab无法直接对约束条件ijijmmax500151或1510jijm进行处理，所以我们先将此条件改为ijijmmax151，则原模型变为minW71151)(ijjijPm+71151ijijijijGTm+（1521412121jjjjjjLLRR）1.0ijijmmax15171iijjjmLR152,1js.tjjjDLR1142,1j01L015R0ijm72,1,152,1ij通过matlab编程（程序见附录）计算结果见表二9表二各厂的生产量及总费用（生产量可小于500）（单位：单位、万元）1S2S3S4S5S6S7S总费用800800100001190.51135.52456102754.1由表二可知，4S、7S的生产量小于500单位。由于4S的生产量等于0，所以不用考虑，直接取为0；而在7S的生产量问题上，有两种处理方式：（1）7S的生产量为0；（2）7S的生产量大于500单位。两