《数学建模2000b题》由会员分享，可在线阅读，更多相关《数学建模2000b题（52页珍藏版）》请在金锄头文库上搜索。
1、2000网易杯全国大学生 数学建模竞赛题目,B题 钢管订购和运输,西北大学数学系,窦霁虹,信息 （语言、数据）,问题 （第一问，,）,问题 所属类型,做题 思路和关键点,结果 表示形式,读 题,要铺设一条 输送天然气的主管道,如图一所示。经筛选后可以生产这种主管道钢管的钢厂有,。图中粗线表示铁路，单细线表示公路，双细,线表示要铺设的管道（假设沿管道或者原来有公路，或者,和管道旁的阿拉伯数字表示里程（单位：Km）。,或者建有施工公路 )，圆圈表示火车站，每段铁路、公路,为方便计，1 Km主管道钢管称为1单位钢管。,一个钢厂如果承担制造这种钢管，至少需要生产500个,单位。钢厂,在指定期限内能生产
2、该钢管的最大数量为,个单位，钢管出厂销价1单位钢管为,万元，如下表：,1单位钢管的铁路运价如下表：,1000km以上每增加1至100km运价增加5万元。,公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。,钢管可由铁路、公路运往铺设地点（不只运到点,，而是管道全线）。,问题： （1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。,（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化,对购运计划和总费用影响最大？哪个钢厂钢管的产量的上限,的变化对购运计划和总费用的影响最大？并给出相应的数字,结果。,（3）如果要铺设的管道不是一条线，而是一个树形图，,铁路
3、、公路和管道构成网络，请就这种更一般的情形给出,一种解决办法，并对图二按（1）的要求给出模型和结果。,问题 所属类型,做题 思路和关键点,结果 表示形式,优化模型,1、问题的分析,优化问题,1）优化模型的数学描述,求函数,在约束条件,下的最大值或最小值，其中,和,设计变量（决策变量）,目标函数,可行域,“受约束于”之意,线性规划（LP）,目标函数和所有的约束条件都是设计变量的线性函数。,西北大学数学系,二次规划问题,目标函数为二次函数，约束条件为线性约束,2）建立优化模型的一般步骤,1.确定设计变量和目标变量； 2.确定目标函数的表达式； 3.寻找约束条件。,设有某物资从m个发点 输送到n个收
4、点 其中每个发点发出量分别为 每个收 点输入量分别为 ，并且满足 从发点A到收点B的距离（或单位运费）是已知的，设为 。 问题：寻求一个调运方案，使总运输费用达到最小。,例 运输问题,B1 B2 . Bn,A1,A2,Am,a1,a2,am,b1 b2 . bn,x11 x12 . x1n,x21 x22 . x2n,xm1 xm2 . xmn,收点,发点,一个调运方案主要由一组从发点 到收点 的输送量来描述。,总的费用,A1的总费用,A2的总费用,s.t.,数学模型,求解：单纯形方法。,问题： （1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。,（2）请就（1）的模型分
5、析：哪个钢厂钢管的销价的变化,对购运计划和总费用影响最大？哪个钢厂钢管的产量的上限,的变化对购运计划和总费用的影响最大？并给出相应的数字,结果。,（3）如果要铺设的管道不是一条线，而是一个树形图，,铁路、公路和管道构成网络，请就这种更一般的情形给出,一种解决办法，并对图二按（1）的要求给出模型和结果。,B1 B2 . Bn,S1,S2,S7,a1,a2,am,b1 b2 . bn,x11 x12 . x1n,x21 x22 . x2n,xm1 xm2 . xmn,收点,发点,订购与运输方案,n=5171,s.t.,数学模型,注1： 表示单位钢管从 运到 的最小费用（含订购费用）,注2：适合第三
6、问，只是 n=5903.,目标变量 ：,总费用=订购费用+运输费用,总费用 W,运输费用=从钢厂到管道关节点,的运输费用 P +,从管道的关节点到铺设点的运输费用 T,即：,钢管的订购计划：,每个钢厂的定货数量。,钢管的运输方案：,从每个钢厂运送到每个管道,区间的钢管量。,1）基本假设：,要铺设的管道侧有公路，可运送所需钢管；,钢管在运输中由铁路运转为公路运时不计换车费；,所需钢管均由 钢厂提供；,在具体铺设每一公里时，只把钢管运输到每一公里开始的地方，沿运输方向向前铺设的费用不予考虑。,2、模型假设与符号说明,：1单位钢管从钢厂 运到 的最小费用（单位： 万元）；,2）符号说明：,：从 到
7、之间的距离（单位：千米）；,：钢厂 的最大生产能力；,：钢厂 的出厂钢管单位价格（单位：万元）；,：公路上1单位钢管的每公里运费（d=0.1万元）；,：铁路上1单位钢管的运费（分段函数见表一）；,：运到 地的钢管向左铺设的数目；,钢厂 提供钢管,钢厂 不提供钢管,： 所求钢管订购、运输的总费用（单位：万元）。,：运到 地的钢管向右铺设的数目；,：钢厂 运到 的钢管数；,目标函数是总费用 ：钢管出厂总价 ,运,，,3、模型的建立,(1)决策变量,(2)目标函数,输费 ,及铺设费 ,即 其中,：1单位钢管从钢厂 运到 的最小费用（单位：万元）,从 开始向左右两个方向铺设，铺设的数量分 别用 与 来
8、表示。,铺设费 可以如下确定：,单位长钢管的费用为,故,（3）约束条件,与,的钢管：,生产能力的限制:,运到 的钢管用完：, 变量非负性限制：,端点限制：,s.t.,(4)数学模型,其中每一 表示单位钢管从 到 的,最小运输费用，因而，求解 实际上是一个求最短,“最短路经”问题是图论中最基本的问题之一。,4、模型的求解,关键1 求出目标函数中的系数,关键2 确定约束条件中的,路径的问题。,“最短路经”问题的标准算法-弗洛伊德算法。,其中 表示从 到 的最短路程，若不能相连，,求出铁路和公路的最短路径矩阵,用 表示。,运用Floyd算法，得出局部最短路径矩阵。,铁路和公路自身分别构成权矩阵，记为
9、 和 。,铁路和公路的最短路径矩阵的统一,对公路，将 为公路局部最小运费矩阵。,对铁路，用铁路的费用 进行转换，得局部铁路,最小运费矩阵 。,令,对得到的A,再使用一次Floyd算法，得到全局的最短,每两点间最小运费矩阵，从中抽取出 到 之间,的子矩阵即为所需的 。,求最小费用矩阵,最小费用矩阵,注：表中的数据乘以0.1为对应的最小费用矩阵的元素。,最小费用矩阵,注：表中的数据乘以0.1为对应的最小费用矩阵的元素。,模型就转化为典型的二次规划问题。,如果其最优解符合原有的约束条件，则便是原问题的最优解。,如果存在 i 使 那么,针对这些 i 分两种情况,找出其中的最优的结果。,s.t.,根据二
10、次规划软件求解模型,或者运用数学软件Lingo5.0,编程求解,将 从供应商中除去，再将第7家工厂的供货量,最优解中,改为0以及不小于500两种情况重做。相比之下，,取0的情况总费用较小，从而也把 删除。,钢管的订购计划：,亿元,5、结果表示,钢管的运输方案：,1）确定哪个钢厂的销价的变化对购运计划和总费用的影响最大,6、灵敏度分析,s.t.,假设该钢厂的销价变化在 万元以内，,结论： 或 的销价的变化影响最大。,钢管的订购计划：,亿元,2）确定哪个钢厂的生产上限的变化对购运计划和总费用的影响最大,在变化 的情况下目标函数减小量及减小的比率,结论： 的生产上限的变化影响最大。,最小费用矩阵,注：表中的数据乘以0.1为对应的最小费用矩阵的元素。,若要铺设的道路不是一条线，而是一个树形图，,7、关于问题（3）,s.t.,数学模型,运用数学软件Lingo5.0编程求出：,亿元,课后练习：,（1）求出最小费用矩阵,（2）求解问题1的二次规划模型,用数学软件Lingo，用软件SAS,定题,做题,建模全程中注意的几个问题,反复读题，查阅资料,齐心协力，分工明确，共克难关,做题开始，写论文就开始,所有的文件名，保存时必须表明内容,摘要在最后一个晚上开始写,论文的风格要一致,论文,祝同学们 在09年建模训练中有所收获,祝长安大学 在09年建模竞赛中取得优异成绩,
