钢管订购和运输数学建模论文

1精品文档——精品文档精品资料精品文档一精品资料钢管订购和运输本文建立了一个运输问题的最优化模型。通过对图(一)的分析，我们首先直观地将路线分成两段，将图分为两个子图建立了模型一，利用分支定界法求得总费用最优解为1279496万元。然后对模型一进行优化，得到全线的最优模型二，求得总费用最优解为1278632万元。通过对最优模型二的分析，我们得出钢厂S1的上限产量和钢厂S6的销价的的变化对运购计划和总费用的影响最大，并给出了数据我们利用截取和连接的方法将树形图转化成为对线性图进行分钢管订购和运输数学建模论文2析，并给出了一般的解决方法。对图(二)给出的具体模型，类似与问题一，分别建立了模型三和模型四，求得最优解分别为1408859.4和1403948万元.钢管订购和运输数学建模论文3一、问题的提出已知有7个钢厂，可生产输送天然气主管道的钢管，用S;表。现有15个地点沿着这15个地点铺设一条输送天然气的主管道。为方便计，1km主管道称为1一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂s;在指定期限内能生产该钢管的最大数量为s;个单位，钢管出厂销价1单位钢管为p,万元，如下表：i12345671单位钢管的铁路运价如下表：里程(km)301～350351～400401～450451～500运价(万元)里程(km)501～600601～700701～800801～900901～10001000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元(不足整公里部分按整公里计算)。钢管可由铁路、公路运往铺设地点(不只是运到点A,A₂,…,A₁s,而是管道全线)。(1)请制定一个主管道钢管的订购和运输计划，使总费用最小(给钢管订购和运输数学建模论文4(2)请就(1)的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。(3)如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按(1)的要求给出模型和结果。二、问题的分析该问题是图论中运输问题的最优化问题。(1)销价和运输钢管至管道结点Aj(i=1,2,…,15)的总费用(称为成本费用)(2)铺设过程中的运输费用；要解决此问题，我们认为有两点关键：(1)如何求出Ai(i=1,2,……,15)至(2)如何调整使得各路径满足题中的最优指标。针对上述问题，我们分别运用了图上作业法、枚举法、逐次修正法、重绕最小生成树法等方法，在综合考虑算法的精度和算法的复杂度后，我们选择了图上作业法、枚举法、逐次修正法对模型进行逐次优化，直至求得最优解。钢管订购和运输数学建模论文5三、模型的基本假设及符号说明(1)运输方式的改变所花费用包含在运费中；(2)铁路线上任意两点可以直达，不需中途转车，即铁路线上两点间运费按线路总长计算；(3)假设一单位钢管可由任意长度钢管组成，购买钢管可以非整数(4)不考虑其它外界因素对费用的影响；(5)钢管在铺设时，先将钢管运到结点处，再由结点处向左右两方相邻结点铺设；(6)在Si厂购买钢管要么为零，要么至少为500单位。(二)符号说明：x₁:从钢厂S;运到结点A;的单位钢管数；f;:单位钢管从钢厂S;运到结点A;的的最少成本费用；t:第A;点与Aj₁点间的路线长度，j=1,2,…,14;y;:从结点A;开始沿管道向右铺设的路线长度，j=1,2,3,…,15;w:钢管订购和运输的总费用；bi:图一中各节点(见附录七)Vi:图二中各节点(见附录八)6四、模型的建立与求解(一)问题一及其求解：针对图(一),我们首先采用图上作业法对所给图进行分析，利用枚举法，我们求出一单位钢管由钢管厂S;运输至管道结点A;的最小成本费用，具体数据如下表：表一单位钢管由S;运输至A;的最小成本费用(单位：万元)O这样，原问题即转化为通常的运输问题。我们进一步对上表数据进行分析，得到结论：结论1:将S4、S5两列数据进行对比，发现同一行中S4列数据均大于S5列。由此得出，应优先考虑钢厂S5,只有当对S5的需求量超过其最大产量时，才需要考虑钢厂S4。进一步对原图进行分析可得：结论2:由于A1点只有通过A2点才能与钢厂Si连接，故模型中不需考虑往A1运输钢管。钢管订购和运输数学建模论文7模型(一):对表一数据进一步分析。将各行数据由小到大排序，发现由A2至A15各行中费用最小的前三个数据均在S5,S6,S7中，直观感觉到：A1至A9需要来自S6及S7等后一部分钢厂的钢管的可能性很小，而且A9至A15不太可能需要S1、S2、S3等前一部分钢厂生厂的钢管，故把原图分为两个子图考虑，分别为A1至A9和A9至A15,即分为两个子模型，分别进行最优化，得到两个子模型(非线性规划子模型1:子模型2:钢管订购和运输数学建模论文8附录一、二)得到：w1=859629.3W2=419866.7模型(二):可能存在一定的误差。下面对模型(一)进行优化，即对主管道建立钢管订购和运输数学建模论文9附录三)运行得出：最优解W=1278632万元，各节点向右铺设的管道单位数：Y14=335表二各钢厂定购计划：数量00表三运输计划如下(bi含义参见附图七):路线运量S1-b7-b6-A6:S2-b8-S1-b7-b6-b5-A5-A4;116S3-b9-b8-b4-b2-b3-A3;319钢管订购和运输数学建模论文S6-b16-b15-b13-b14-A12;86通过模型(二)的求解，我们确定对图(一)仅需要S1、S2、S3、S5、S6承担生产任务即可取得最优解。对模型所用程序进行灵敏度分析，并具体考虑当钢厂钢管的销价增加1万元或产量上限增加1单位时，购运计划和总费用的变化情况，结果如下表：表四钢厂Si的钢管产量上限增加1单位对总费用的影响总费用减少量0000则可以发现：钢厂S1的钢管产量上限的变动对购运计划和总费用表五钢厂Si的钢管销价增加1万元对总费用的影响总费用增加量00则可以发现：钢厂S6的钢管销价的微小变动对购运计划和总费用钢管订购和运输数学建模论文1、一般模型经过对图(一)的分析求解可以看出，订购及运输钢管的总费用可由各段所需费用求和得到。若要铺设的管道是一个树形图，则可以将其转化为线性管道进行分析。具体解题步骤如下：(1)运用图论的最小权匹配法(简单图可利用枚举法),求出从各钢厂定购并运输一单位钢管至主管道各结点的最小成本费用值。(2)将树型图转化为线性图：在树形图中取其最长的线形段，称为主干线形段；将图中剩余分支截取，并通过一个虚拟段(长度t为零)联接至主干线形段上，组成一个新的线性管道；如，图二中A9至A16段，可将该段接到A15点，再分别从原图A9、A16点连一条长度为0的公路，而在A15点之间连一条长度为0的公路并增加一新的结点A9,同时约定A15点不向右铺设管道。其它各段类似处理。(3)按照问题(一)的思路建立模型进行求解。建立如下非线性钢管订购和运输数学建模论文2、问题三图(二)的求解图(二)为树形图，将其转化为类似图(一)的线性图。利用枚举法，求出一单位钢管由钢管厂Si运输至管道结点Ai的最小成本费表六单位钢管由Si运输至Ai的最小成本费用(单位：万元A1410.7410.7435.7A2400.3400.3425.3A3405.2A4A5A6A7A8A9A10A11A12A13A14A15钢管订购和运输数学建模论文A16A17A18A19A20A21模型(三)首先类似于模型一，按分段的思想建立模型。由A1…A9、A16由A21-A20-A19-A17-A11-A12-A13-A14-A15-A9-A10-A11-A17-A18为钢管订购和运输数学建模论文运用LINGO软件进行编程(见附录四、五)运行结果为：费用w1=869127.2w2=539732.2模型(四):对整个图进行考虑，可得如下模型：利用LINGO软件编程(见附录六)运行得出最优解w=1403948万元，同时得出下表数据：表七各钢厂定购计划：数量00表八运输计划如下(Vi含义参见附录八):路线运量S1-V7-V6-A6;200S1-A7;S2-V8-S1-V7-V6-V5-A5;150S3-A16-V8-V4-V2-V3-A3;336S6-A20-A13;393S6-A14;571S6-V11-V12-A15;165S6-A20-A18;130S6-A20-A19;95(五)模型的评价1、本文从简单的角度入手建立模型，运用枚举法、图上作业法、图论等多种方法对模型进行逐步优化。过程严谨，理论性强，逻辑严密，而且易于理解。2、模型一、三为问题的近似解，但涉及变量少，易于求解，且精度较高；模型二、四为问题的精确解，变量多，求解稍难。3、一般模型(1)(2)式具有很强的通用性，网络、树型图转化为线性图的方法也具有一般性；4、本文大量运用了计算机程序，所有数据均由计算机处理，故误差由计算机精度产生，模型具有较好的稳定性。参考文献(1)李德、钱颂迪运筹学清华大学出版社1982年；(2)许卓群等数据结构高等教育出版社1987年；钢管订购和运输数学建模论文(3)滕传琳管理运筹学中国铁道出版社(4)[美]E米涅卡网络和图的最优计算方法1986年；中国道出铁版社1984年；本题是一个典型的离散优化问题，实际上最终归结为两个二次规划模型。求解的关键包括定购和运输单价的计算、二次规划模型的建立和求解。其中的难点是题中复杂图的恰当处理和模型中变量数特别是整型变量数过多的灵活解决。本优秀论文在对这两问题的处理上颇有特色：其一是对问题一的图，作者首先根据直观分析，将原图分成两个小图分别求解，再合二为一建立优化模型；而针对问题二的树形图，通过增加一个长度为零费用为零的线路转化为线性图后，问题二的求解方法就与问题一的求解方法相同了。这是“从简单到复杂，从局部到全局，化繁琐为简单”的建模思想的具体体现。其二是对变量数过多问题的解决，作者经过约束