PAGE\*MERGEFORMAT92011高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：我们的参赛报名号为（如果赛区设置报名号的话）：10所属学校（请填写完整的全名）：参赛队员(打印并签名)：1.肖柳青2.程祺3.赵育兴指导教师或指导教师组负责人(打印并签名)：日期：2012年8月12日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：题目：基于Floyd算法的钢管运输最优化模型摘要为了在不太影响结果的前提下大幅降低思维难度，从实际情况出发，我们假设“运输钢管的时候先走铁路后走公路，最后沿钢管路线的公路运输”。在此假设前提下，即可将原来复杂的问题分解为几个较为简单的问题，即“最少总费用=钢厂到中转站的铁路运输最少费用+中转站到节点（）的公路运输最少费用+钢管购买和铺设的最少费用”。在求解“钢厂到中转站的铁路运输最少费用”和“中转站到节点（）的公路运输最少费用”的时候，我们采用Floyd算法，先求出铁路网上钢管厂到铁路上任意两点的最短路线的长度,用Matlab求得相应的铁路运费；同理用Floyd算法求出公路网上的任意两点的最短公路的长度，结果乘以0.1得到公路运费。这样就得到从钢厂到铺设点运输钢管的最少费用。根据前面所求的从钢厂到铺设点运输钢管的最少费用，每个铺设点分别向左右两边展开，用Lingo求出最小铺设费用。运输费用加上购买费用再加上铺设费用就是总费用。图一的最少费用是1278632万元。经灵敏度分析7个钢厂的产量上限的影子价格，得1号厂的产量上限对结果影响最大。再次分析钢厂销价的影子价格，得6厂的价格对结果影响最大。与图一的模型相似，在建立图二模型时只需要在图一所建模型的基础上加几个约束条件，在Lingo中运行即可得到图二的最少费用是1429907万元。不过此时所得“最少总费用”还不是“最终最少总费用”。经参阅数篇相关论文，他们默认为如果乘铁路距离越长那么单位距离的的运费就越少。实际上依据单位钢管的铁路运价表可知，当铁路长为601~650km或701~750km时，如果中间恰好有一中转站，那么就有可能经过中途转乘后反而比连续运输的费用要低。例如A到C为625km，AC之间距A点290km处有一中转站B点，依据单位钢管的铁路运价表可知，直接从A到C的费用为44万元，而经过B点中转后的费用为43万元。所以凡是没有考虑“中转后的费用可能比不中转的费用低”这中情况的都存在顶层思维上的错误。为解决这种特殊情况，我们在建立图一模型的时候为了简化思维难度，同样采取先假设“铁路不中转时的费用最低”，得出在这一假设下的最优解后，判别所有连续铁路的路程是否在601~650km或701~750km的范围内。如果都不在这两个范围内，那么原最优解即为最终的最优解，如果有一条或几条铁路的路程在此范围内，那么分别查看这段铁路之间是否有且只有一个中转站，而且此中转站恰好将该段铁路分为0~300km、301~350km或301~350km、351~400km，如果成立，那么将整段铁路划分为两段来计算运费，从而将其作为最终最优解，否则原最优解即为最终最优解。关键词：Floyd算法、非线性规划、运输规划一问题重述要铺设一条的输送天然气的主管道,如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：1234567800