求解钢管订购和运输问题数学模型结业()-本科论文.doc

数学模型课程结业论文题 目钢管订购与运输院 系理学院专 业信息与计算科学学 号学生姓名任课教师单锋沈阳航空航天大学2013年4月任务及要求任 务 书 要求1、将所给的问题翻译成汉语；2、给论文起个题目（名字或标题）3、根据任务来完成数学模型论文；4、论文书写格式要求按给定要求书写； 5、态度要认真，要独立思考，独立完成任务；6、论文上交时间：5月30日前（要求交纸质论文和电子文档）。7、严禁抄袭行为，若发现抄袭，则成绩记为“不及格”。任务钢管订购和运输 要铺设一条的输送天然气的主管道, 如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：1234567800800100020002000200030001601551551601551501601单位钢管的铁路运价如下表：里程(km)300301350351400401450451500运价(万元)2023262932里程(km)5016006017007018008019009011000运价(万元)37445055601000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A11A711A11A8A11A911A11A10A11A12A13A14A15S1S2S3S4S5S6S7图一A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A19130190260100A2A3A4A5A6A7A8A11A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16A17A18A20(A21)图二 成 绩 评 定 单评语：成绩 任课教师签字 年 月 日I摘要摘 要本文讨论了在铺设天然气管道的过程中如何合理订购与运输钢管以使总费用最小的优化问题。问题一是在一定约束条件下以钢管订购和运输的总费用为目标函数的非线性规划问题。总费用由订购钢管的总费用、从钢厂到站点运输钢管的总费用及从站点开始铺设钢管的总费用三部分组成。订购钢管的总费用和从钢厂到各站点运输钢管的总费用分别通过在各厂购买量与各厂出厂销价和各厂购买量与从各钢厂到各站点运输单位钢管的最小费用的线性规划运算得到。从站点开始铺设钢管的总费用通过等差数列求和得到。在求从钢厂到站点的运输钢管的总费用时，关键是采用弗洛伊德算法，用MATLAB软件编程求出单位钢管从各钢厂运往各站点最小运输费用。利用LINGO软件求解此模型，得到钢管订购与运输的最小费用。问题二是对问题一模型的灵敏度分析，通过控制变量法的方法即每次只让一家钢厂的销价或生产线发生变化并且每次的变化是相同，分别得出各变量对购运计划的影响。问题三是对问题一的推广，要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，在问题一的模型中又增加了一些约束条件和变量，同时在目标函数中增加相应的铺设费用。利用LINGO软件编程求解新的模型。关键词：非线性规划；弗洛伊德算法；灵敏度分析；目录目 录钢管订购与运输11.1 问题提出11.2 模型假设31.3 符号说明41.4 问题一的模型建立：求钢管订购和运输最小运费41.5 问题一的求解52.1问题二的模型建立：钢管销价变化对购运计划的影响。62.2问题二的求解63.1问题三的模型建立：直线管道向管道网变化时的购运计划73.2题三的求解94优缺点改进95参考文献106附录10数学模型课程结业论文钢管订购与运输1.1 问题提出要铺设一条的输送天然气的主管道, 如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：1234567800800100020002000200030001601551551601551501601单位钢管的铁路运价如下表：里程(km)300301350351400401450451500运价(万元)2023262932里程(km)5016006017007018008019009011000运价(万元)37445055601000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A11A711A11A8A11A911A11A10A11A12A13A14A15S1S2S3S4S5S6S7图一（3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A19130190260100A2A3A4A5A6A7A8A11A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16A17A18A20(A21)图二1.2 模型假设1.模型只考虑钢管销价费用和钢管从钢管厂运送到铺设点的钢管运费，而不考虑其它费用，如不计换车、转站的时间和费用，不计装卸费用等。2.要铺设的管道侧有公路，可运输所需钢管。2.钢管单价与订购量、订购次数、订购日期无关,即在钢管订购与运输过程中，钢管的单价保持不变。3.将每一单位的管道所在地看成一个需求点，向以单位管道的所在地运输钢管即向一个点运输钢管。4.钢管在运送和使用中没有损耗。5.不计运输时由于运输工具出现故障等意外事故引起工期延误造成损失。1.3 符号说明第个工厂第个钢厂的钢管最大生产数由到的最小路运费用由到的钢管的运量由向段路线铺设的长度由向段路线铺设的长度运输总费用第个钢厂每单位的钢管运价表示0-1变量的长度1.4 问题一的模型建立：求钢管订购和运输最小运费问题一的模型：如上文分析所述，我们采用Floyd算法，用matlab编程求出单位钢管从运输到的最小费用，具体数据如表1： 表1 最优路径单位钢管运输费用S1S2S3S4S5S6S7170.7215.7230.7260.7255.7265.7275.7160.3205.3220.3250.3245.3255.3265.3140.2190.2200.2235.2225.2235.2245.298.6171.6181.6216.6206.6216.6226.63811112115614615616620.595.5105.5140.5130.5140.5150.53.1869613112113114121.271.286.2116.2111.2121.2131.264.2114.248.284.279.284.299.29214282625762769614686513351661061569661514556121.2171.2111.276.271.226.238.2128178118837311261421921329787282目标函数为，表示钢管运输所需的费用，我们通过非线性规划求出问题的模型如下：1.5 问题一的求解所以根据上述的模型，得运输总费用最小为1278632（万元）. 具体的购运计划和铺设方案如表2，表3表2 问题一的订购和调运方案 订购量A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1800004029520026500000000S280017900321003000000000S31000003360000664000000S4000000000000000S510150508920000004150000S6155600000000351086333621165S7000000000000000表3 问题一的铺设方案0.0000000.000000104.000075.00000226.0000282.0000468.00000.000000606.00009.500000184.500015.50000189.500076.00000125.0000175.0000505.0000159.0000321.000030.00000270.0000145.000075.0000011.00000199.0000134.0000286.0000335.0000165.00000.0000002.1问题二的模型建立：钢管销价变化对购运计划的影响。1讨论钢厂钢管的销售价格变化对购运计划和总费用的影响当钢厂钢管销售价格变化时，会对购运计划和总费用造成影响. 为了更好地观察每一个钢厂钢管销售价格所造成的影响，采用比较法，即每次只让一个钢厂钢管的销售价格发生相同的变化，其余钢厂钢管的销售价格不发生变化. 2.2问题二的求解我们将各个钢厂单位钢管的销价分别增加1万元和减少1万元，借助LINGO软件得出相应的总费用、运输方案、订购方案变化情况如表4、表5所示表4 各个钢厂单位钢管的销价分别增加1万元钢厂总费用总费用变化量运输方案变化量订购方案变化量S1127943280000S2127943280000S31279632100000S41278632000S5127963910074030S612798341202712712S71278632000表5 各个钢厂单位钢管的销价分别减少1万元钢厂总费用总费用变化量运输方案变化量订购方案变化量S1127783280000S2127783280000S31277632100000S41278632000S512772631369712712S6127706815644030S71278632000由上述表格观察分析可得： 钢厂销价变化对总费用影响最大，钢厂钢管的销价的变化对购运计划影响最大. 2讨论钢厂钢管产量的上限的变化对购运计划和总费用的影响同样采用比较法，即每次只让一个钢厂钢管产量的上限的发生相同的变化，其余钢厂钢管产量的上限不发生变化. 将各个钢厂的产量的上限分别增加100个单位和减少100个单位，分别计算，得到购运计划和总费用变化情况如表6、表9所示. 表6 各个钢厂钢管的产量的上限分别增加100个单位钢厂总费用总费用变化量运输方案变化量订购方案变化量S1126833210300218200S212751323500404200S3127613225001786200S41278632000S51278632000S6127863208440S71278632000表9 各个钢厂钢管的产量的上限分别减少100个单位钢厂总费用总费用变化量运输方案变化量订购方案变化量S1128893210300260200S2128213235001244200S312811322500200200S41278632000S51278632000S61278632000S71278632000由上述表格观察分析可得：钢厂钢管的产量的上限的变化对总费用影响最大，购运计划影响较小。3.1问题三的模型建立：直线管道向管道网变化时的购运计划问题三与问题一非常类似，其主要区别在于问题三中将线性的管道铺设线变成了树形的铺设线路，多增加了几个节点。当主管道由直线变为树形图，铁路、公路和管道构成的网络时，求从钢厂运单位钢管到主管道结点的最小费用的算法仍旧适用，因此，我们仿照问题一中的思路，求出最小运费表，如表10：表10 问题三的最小运费表S1S2S3S4S5S6S7170.7215.7230.7260.7255.7265.7275.7160.3205.3220.3250.3245.3255.3265.3140.2190.2200.2235.2225.2235.2245.298.6171.6181.6216.6206.6216.6226.63811112115614615616620.595.5105.5140.5130.5140.5150.53.1869613112113114121.271.286.2116.2111.2121.2131.264.2114.248.284.279.284.299.29214282625762769614686513351661061569661514556121.2171.2111.276.271.226.238.2128178118837311261421921329787282 (i=1,.,7) 3.2题三的求解费用800800100001303200001406330得到最优最小费用为万元。4优缺点改进由于总费用由订购费用和运输费用部分组成，运输费又由一般线路上的运输费和铺设管道上的运输费组成. 利用求网络中最短路径的弗洛伊德方法得到新的算法，可对含多种权重计算方式的网络进行搜索，得出最小费用路径（最短路径），算出两点之间的最优路径，进而根据非线性规划，借助于Lingo软件求解即可求出相应的结果. 1优点1）本问题中运用了求网络中最短路径的弗洛伊德思想，改进和修改得到新的算法，可对含多种权重计算方式的网络进行搜索，算出两点之间的最优路径，计算结果准确，从而得出相应的购运单价的矩阵.2）本问题构造出的模型算法较简单，也可以运用相应的其他编程软件来得到比较满意的结果. 3）本模型计算步骤清晰，借助于Lingo软件求解，可靠性较高. 2缺点1）由于题意中不考虑铁路公路间转运的中转费用，也不限制转运次数，因此在算法设计中存在着考虑不周全的缺限，如我们考虑是先通过铁路再通过公路到铺设点，但这不一定是最小费用路径，有可能先通过公路，然后经铁路再经公路运到铺设点，费用更少，这里没有理论证明. 2) 问题二要求根据问题一的分析,指出哪家钢厂销价的变化对购运计划和总费用影响最大，哪家钢厂钢管产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果. 这个问题属于规划问题的灵敏度分析，在此模型中，只是通过说明销价增加一万元，减少一万元来说明，并没有给出一般的理论说明。3模型改进这个数学模型可以应用于西部开发中“西气东送”问题，当然，西部开发中“西气东送”问题远比我们的假设还要复杂的多，但无论如何，他们的本质一样，我们可将本问题运用于时间的变化等范围的推广。文还可以把问题1归结为网络最小费用流问题，建立了线性和非线性最小费用流模型，并运用相应的解法和分支定界法求解，简洁，层次分明。5参考文献1数学模型 单峰 朱丽梅 田贺民 国防工业出版社2.运筹学教程 胡运权 清华大学出版社3.MATLAB程序设计与应用 刘卫国 中国水利水电出版社6附录附录一：Floyd算法函数在matlab下的M函数文件如下：function D,path=floyd(a)n=size(a,1);D=a;path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j)+D1(j-7,k) c(i,k-17)=D(i,j)+D1(j-7,k);%对于所有中转点，在铁路网和公路网上的下标相差8 end end endendfor i=1:7for k=18:32 if c(i,k-17)D(i,1)+D1(33,k) c(i,k-17)=D(i,1)+D1(33,k);%33代表第一个钢管生产厂S1点 end if c(i,k-17)D(i,6)+D1(34,k) c(i,k-17)=D(i,6)+D1(34,k);%34代表第六个钢管生产厂S6点 end if c(i,k-17)D(i,7)+D1(35,k) c(i,k-17)=D(i,7)+D1(35,k);%35代表第七个钢管生产厂S7点 endend%因为S1,S6,S7这三个钢管厂有公路直接连接到铺设节点，所以把这三个点单独处理end 13