数学建模2000B题

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2000网易杯全国大学生 数学建模竞赛题目,B题 钢管订购和运输,西北大学数学系,窦霁虹,信息,语言、数据,问题,第一问，,问题,所属类型,做题,思路和关键点,结果,表示形式,读 题,要铺设一条,输送天然气的主管道,如图一所示。经筛选后可以生产这种主管道钢管的钢厂有,。图中粗线表示铁路，单细线,表示公路,，,双细,线表示要铺设的管道假设沿管道或者原来有公路，或者,和管道旁的阿拉伯数字表示里程单位：Km。,或者建有施工公路 )，圆圈表示火车站，每段铁路、公路,为方便计，1 Km主管道钢管称为1单位钢管。,A,1,3,2,5,80,10,10,31,20,12,42,70,10,88,10,70,62,70,30,20,20,30,450,104,301,750,606,194,205,201,680,480,300,220,210,420,500,600,3060,195,202,720,690,520,170,690,462,160,320,160,110,290,1150,1100,1200,A,2,A,3,A,4,A,5,A,6,A,7,A,8,A,9,A,10,A,11,A,12,A,13,A,14,A,15,S,1,S,2,S,3,S,4,S,5,S,6,S,7,图一,一个钢厂如果承担制造这种钢管，至少需要生产500个,单位。钢厂,在指定期限内能生产该钢管的最大数量为,个单位，钢管出厂销价1单位钢管为,万元，如下表：,1,2,3,4,5,6,7,800,800,1000,2000,2000,2000,3000,160,155,155,160,155,150,160,1单位钢管的铁路运价如下表：,里程(km),300,301350,351400,401450,451500,运价（万元）,20,23,26,29,32,里程(km),501600,601700,701800,801900,9011000,运价(万元),37,44,50,55,60,1000km以上每增加1至100km运价增加5万元。,公路运输费用为1单位钢管每公里0.1万元缺乏整公里局部按整公里计算。,钢管可由铁路、公路运往铺设地点不只运到点,，而是管道全线。,问题：,1请制定一个主管道钢管的订购和运输方案，使总费用最小给出总费用)。,2请就1的模型分析：哪个钢厂钢管的销价的变化,对购运方案和总费用影响最大？哪个钢厂钢管的产量的上限,的变化对购运方案和总费用的影响最大？并给出相应的数字,结果。,3如果要铺设的管道不是一条线，而是一个树形图，,铁路、公路和管道构成网络，请就这种更一般的情形给出,一种解决方法，并对图二按1的要求给出模型和结果。,A,1,3,2,5,80,10,10,31,20,12,42,70,10,88,10,70,62,70,30,20,20,30,450,104,301,750,606,194,205,201,680,480,300,220,210,420,500,600,3060,195,202,720,690,520,170,690,462,160,320,160,110,290,1150,1100,1200,A,2,A,3,A,4,A,5,A,6,A,7,A,8,A,9,A,10,A,11,A,12,A,13,A,14,A,15,S,1,S,2,S,3,S,4,S,5,S,6,S,7,图一,A,1,3,2,5,80,10,10,31,20,12,42,70,10,88,10,70,62,70,30,20,20,30,450,104,301,750,606,194,205,201,680,480,300,220,210,420,500,600,3060,195,202,720,690,520,170,690,462,160,320,160,110,290,1150,1100,1200,A,19,130,190,260,100,A,2,A,3,A,4,A,5,A,6,A,7,A,8,A,9,A,10,A,11,A,12,A,13,A,14,A,15,S,1,S,2,S,3,S,4,S,5,S,6,S,7,A,16,A,17,A,18,A,20,(,A,21),图二,问题,所属类型,做题,思路和关键点,结果,表示形式,优化模型,1、问题的分析,优化问题,1优化模型的数学描述,求函数,在约束条件,下的最大值或最小值，其中,和,设计变量决策变量,目标函数,可行域,“受约束于之意,线性规划LP,目标函数和所有的约束条件都是设计变量的线性函数。,西北大学数学系,二次规划问题,目标函数为二次函数，约束条件为线性约束,2建立优化模型的一般步骤,1.确定设计变量和目标变量；,2.确定目标函数的表达式；,3.寻找约束条件。,设有某物资从m个发点 输送到n个收点,其中每个发点发出量分别为 每个收,点输入量分别为 ，并且满足,从发点A到收点B的距离或单位运费是的，设为,。,问题：寻求一个调运方案，使总运输费用到达最小。,例 运输问题,B1 B2 . Bn,A1,A2,Am,a,1,a,2,a,m,b,1,b,2,. b,n,.,.,x,11,x,12,.,x,1n,x,21,x,22,.,x,2n,x,m1,x,m2,.,x,mn,收点,发点,一个调运方案主要由一组从发点 到收点 的输送量来描述。,总的费用,A1的总费用,A2的总费用,s.t.,数学模型,求解：单纯形方法。,问题：,1请制定一个主管道钢管的订购和运输方案，使总费用最小给出总费用)。,2请就1的模型分析：哪个钢厂钢管的销价的变化,对购运方案和总费用影响最大？哪个钢厂钢管的产量的上限,的变化对购运方案和总费用的影响最大？并给出相应的数字,结果。,3如果要铺设的管道不是一条线，而是一个树形图，,铁路、公路和管道构成网络，请就这种更一般的情形给出,一种解决方法，并对图二按1的要求给出模型和结果。,B1 B2 . Bn,S1,S2,S7,a,1,a,2,a,m,b,1,b,2,. b,n,.,.,x,11,x,12,.,x,1n,x,21,x,22,.,x,2n,x,m1,x,m2,.,x,mn,收点,发点,订购与运输方案,Si,1,2,3,4,5,6,7,供货量,？,？,？,？,？,？,？,n=5171,s.t.,数学模型,注1： 表示单位钢管从 运到 的最小费用含订购费用,注2,：适合第三问，只是 n=5903.,目标变量 ：,总费用=订购费用+运输费用,总,费用 W,运输费用=从钢厂到管道关节点,的,运输费用 P +,从管道的关节点到铺设点的运输费用 T,即：,钢管的订购方案：,每个钢厂的定货数量。,钢管的运输方案：,从每个钢厂运送到每个管道,区间的钢管量。,1根本假设：,要铺设的管道侧有公路，可运送所需钢管；,钢管在运输中由铁路运转为公路运时不计换车费；,所需钢管均由 钢厂提供；,在具体铺设每一公里时，只把钢管运输到每一公里开场的地方，沿运输方向向前铺设的费用不予考虑。,2、模型假设与符号说明,：1单位钢管从钢厂 运到 的最小费用单位：,万元；,2符号说明：,：从 到 之间的距离单位：千米；,：钢厂 的最大生产能力；,：钢厂 的出厂钢管单位价格单位：万元；,：公路上1单位钢管的每公里运费d=0.1万元；,：铁路上1单位钢管的运费分段函数见表一；,：运到 地的钢管向左铺设的数目；,钢厂 提供钢管,钢厂 不提供钢管,： 所求钢管订购、运输的总费用单位：万元。,：运到 地的钢管向右铺设的数目；,：钢厂 运到 的钢管数；,目标函数是总费用 ：钢管出厂总价 ,运,，,3、模型的建立,(1)决策变量,(2)目标函数,输费 ,及铺设费 ,即 其中,：1单位钢管从钢厂 运到 的最小费用单位：万元,从 开场向左右两个方向铺设，铺设的数量分,别用 与 来表示。,铺设费 可以如下确定：,单位长钢管的费用为,故,3约束条件,与,的钢管：,生产能力的限制,:,运到 的钢管用完：, 变量非负性限制：,端点限制：,s.t.,(4)数学模型,其中每一 表示单位钢管从 到 的,最小运输费用，因而，求解 实际上是一个求最短,“最短路经问题是图论中最根本的问题之一。,4、模型的求解,关键1 求出目标函数中的系数,关键2 确定约束条件中的,路径的问题。,“最短路经问题的标准算法-弗洛伊德算法。,A,1,3,2,5,80,10,10,31,20,12,42,70,10,88,10,70,62,70,30,20,20,30,450,104,301,750,606,194,205,201,680,480,300,220,210,420,500,600,3060,195,202,720,690,520,170,690,462,160,320,160,110,290,1150,1100,1200,A,2,A,3,A,4,A,5,A,6,A,7,A,8,A,9,A,10,A,11,A,12,A,13,A,14,A,15,S,1,S,2,S,3,S,4,S,5,S,6,S,7,图一,其中 表示从 到 的最短路程，假设不能相连，,求出铁路和公路的最短路径矩阵,用 表示。,运用Floyd算法，得出局部最短路径矩阵。,铁路和公路自身分别构成权矩阵，记为 和 。,铁路和公路的最短路径矩阵的统一,对公路，将 为公路局部最小运费矩阵。,对铁路，用铁路的费用 进展转换，得局部铁路,最小运费矩阵 。,令,对得到的A,再使用一次Floyd算法，得到全局的最短,每两点间最小运费矩阵，从中抽取出 到 之间,的子矩阵即为所需的 。,求最小费用矩阵,最小费用矩阵,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,1,1707,1603,1402,986,380,205,31,212,642,920,960,1060,1212,1280,1420,2,2157,2053,1902,1716,1110,955,860,712,1142,1420,1460,1560,1712,1780,1920,3,2307,2203,2002,1816,1210,1055,960,862,482,820,860,960,1112,1180,1320,4,2607,2503,2352,2166,1560,1405,1310,1162,842,620,510,610,762,830,970,5,2557,2453,2252,2066,1460,1305,1210,1112,792,570,330,510,712,730,870,6,2657,2553,2352,2166,1560,1405,1310,1212,842,620,510,450,262,110,280,7,2757,2653,2452,2266,1660,1505,1410,1312,992,760,660,560,382,260,20,注：表中的数据乘以0.1为对应的最小费用矩阵的元素。,最小费用矩阵,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,1,1707,1603,1402,986,380,205,31,212,642,920,960,1060,1212,1280,1420,2,2157,2053,1902,1716,1110,955,860,712,1142,1420,1460,1560,1712,1780,1920,3,2307,2203,2002,1816,1210,1055,960,862,482,820,860,960,1112,1180,1320,4,2607,2503,2352,2166,1560,1405,1310,1162,842,620,510,610,762,830,970,5,2557,2453,2252,2066,1460,1305,1210,1112,792,570,330,510,712,730,870,6,2657,2553,2352,2166,1560,1405,1310,1212,842,620,510,450,262,110,280,7,2757,2653,2452,2266,1660,1505,1410,1312,992,760,660,560,382,260,20,注：表中的数据乘以0.1为对应的最小费用矩阵的元素。,模型就转化为典型的二次规划问题。,如果其最优解符合原有的约束条件，那么便是原问题的最优解。,如果存在,i,使 那么,针对这些,i,分两种情况,找出其中的最优的结果。,s.t.,根据二次规划软件求解模型,或者运用数学软件Lingo5.0,编程求解,将 从供给商中除去，再将第7家工厂的供货量,最优解中,改为0以及不小于500两种情况重做。相比之下，,取0的情况总费用较小，从而也把 删除。,钢管的订购方案：,1,2,3,4,5,6,7,供货量,800,800,1000,0,1366,1205,0,1,2,3,4,5,6,7,供货量,800,800,1000,0,1015,1556,0,亿元,5、结果表示,钢管的运输方案：,334,200,266,179,321,300,187,149,664,600,351,415,351,86,333,621,165,合计,179,508,0,1083,200,266,300,664,351,415,86,333,621,165,0,104,226,0,1074,185,190,125,505,321,270,75,199,286,165,0,75,282,0,9,15,76,175,159,30,145,11,134,335,0,1确定哪个钢厂的销价的变化对购运方案和总费用的影响最大,6、灵敏度分析,s.t.,假设该钢厂的销价变化在 万元以内，,1,2,3,4,5,6,7,160,155,155,160,155,150,160,176,170.5,170.5,176,170.5,165,176,154,139.5,139.5,154,139.5,135,154,结论： 或 的销价的变化影响最大。,钢管的订购方案：,1,2,3,4,5,6,7,供货量,800,800,1000,0,1366,1205,0,1,2,3,4,5,6,7,供货量,800,800,1000,0,1015,1556,0,亿元,2确定哪个钢厂的生产上限的变化对购运方案和总费用的影响最大,在变化 的情况下目标函数减小量及减小的比率,1%,872,0.068,328,0.025,310,0.024,0,0,0,0,2%,1744,0.136,656,0.051,620,0.048,0,0,0,0,4%,3488,0.272,1312,0.102,1240,0.096,0,0,0,0,6%,5232,0.408,1968,0.153,1860,0.145,0,0,0,0,8%,6976,0.544,2624,0.204,2480,0.193,0,0,0,0,10%,8720,0.685,3280,0.256,3100,0.242,0,0,0,0,结论：,的生产上限的变化影响最大。,最小费用矩阵,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,1,1707,1603,1402,986,380,205,31,212,642,920,960,1060,1212,1280,1420,2,2157,2053,1902,1716,1110,955,860,712,1142,1420,1460,1560,1712,1780,1920,3,2307,2203,2002,1816,1210,1055,960,862,482,820,860,960,1112,1180,1320,4,2607,2503,2352,2166,1560,1405,1310,1162,842,620,510,610,762,830,970,5,2557,2453,2252,2066,1460,1305,1210,1112,792,570,330,510,712,730,870,6,2657,2553,2352,2166,1560,1405,1310,1212,842,620,510,450,262,110,280,7,2757,2653,2452,2266,1660,1505,1410,1312,992,760,660,560,382,260,20,注：表中的数据乘以0.1为对应的最小费用矩阵的元素。,A,1,3,2,5,80,10,10,31,20,12,42,70,10,88,10,70,62,70,30,20,20,30,450,104,301,750,606,194,205,201,680,480,300,220,210,420,500,600,3060,195,202,720,690,520,170,690,462,160,320,160,110,290,1150,1100,1200,A,19,130,190,260,100,A,2,A,3,A,4,A,5,A,6,A,7,A,8,A,9,A,10,A,11,A,12,A,13,A,14,A,15,S,1,S,2,S,3,S,4,S,5,S,6,S,7,A,16,A,17,A,18,A,20,(,A,21),图二,假设要铺设的道路不是一条线，而是一个树形图，,7、关于问题3,s.t.,数学模型,运用数学软件Lingo5.0编程求出：,亿元,1,2,3,4,5,6,7,供货量,800,800,1000,0,1303,2000,0,课后练习：,1求出最小费用矩阵,2求解问题1的二次规划模型,用数学软件Lingo，用软件SAS,定题,做题,建模全程中注意的几个问题,反复读题，查阅资料,齐心协力，分工明确，共克难关,做题开场，写论文就开场,所有的文件名，保存时必须说明内容,摘要在最后一个晚上开场写,论文的风格要一致,论文,祝同学们,在09年建模训练中有所收获,祝长安大学,在09年建模竞赛中取得优异成绩,