数学建模 2000B题

.,2000网易杯全国大学生数学建模竞赛题目,B题钢管订购和运输,西北大学数学系,窦霁虹,.,信息（语言、数据）,问题（第一问，,）,问题所属类型,做题思路和关键点,结果表示形式,读题,.,要铺设一条输送天然气的主管道,如图一所示。经筛选后可以生产这种主管道钢管的钢厂有,。图中粗线表示铁路，单细线表示公路，双细,线表示要铺设的管道（假设沿管道或者原来有公路，或者,和管道旁的阿拉伯数字表示里程（单位：Km）。,或者建有施工公路)，圆圈表示火车站，每段铁路、公路,为方便计，1Km主管道钢管称为1单位钢管。,.,.,一个钢厂如果承担制造这种钢管，至少需要生产500个,单位。钢厂,在指定期限内能生产该钢管的最大数量为,个单位，钢管出厂销价1单位钢管为,万元，如下表：,.,1单位钢管的铁路运价如下表：,1000km以上每增加1至100km运价增加5万元。,公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。,钢管可由铁路、公路运往铺设地点（不只运到点,，而是管道全线）。,.,问题：（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。,（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化,对购运计划和总费用影响最大？哪个钢厂钢管的产量的上限,的变化对购运计划和总费用的影响最大？并给出相应的数字,结果。,（3）如果要铺设的管道不是一条线，而是一个树形图，,铁路、公路和管道构成网络，请就这种更一般的情形给出,一种解决办法，并对图二按（1）的要求给出模型和结果。,.,.,问题所属类型,做题思路和关键点,结果表示形式,优化模型,.,1、问题的分析,优化问题,1）优化模型的数学描述,求函数,在约束条件,下的最大值或最小值，其中,和,设计变量（决策变量）,目标函数,可行域,.,“受约束于”之意,.,线性规划（LP）,目标函数和所有的约束条件都是设计变量的线性函数。,西北大学数学系,.,二次规划问题,目标函数为二次函数，约束条件为线性约束,.,2）建立优化模型的一般步骤,1.确定设计变量和目标变量；2.确定目标函数的表达式；3.寻找约束条件。,.,设有某物资从m个发点输送到n个收点其中每个发点发出量分别为每个收点输入量分别为，并且满足从发点A到收点B的距离（或单位运费）是已知的，设为。问题：寻求一个调运方案，使总运输费用达到最小。,例运输问题,.,B1B2.Bn,A1,A2,Am,a1,a2,am,b1b2.bn,.,.,x11x12.x1n,x21x22.x2n,xm1xm2.xmn,收点,发点,一个调运方案主要由一组从发点到收点的输送量来描述。,.,总的费用,A1的总费用,A2的总费用,.,s.t.,数学模型,求解：单纯形方法。,.,问题：（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。,（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化,对购运计划和总费用影响最大？哪个钢厂钢管的产量的上限,的变化对购运计划和总费用的影响最大？并给出相应的数字,结果。,（3）如果要铺设的管道不是一条线，而是一个树形图，,铁路、公路和管道构成网络，请就这种更一般的情形给出,一种解决办法，并对图二按（1）的要求给出模型和结果。,.,B1B2.Bn,S1,S2,S7,a1,a2,am,b1b2.bn,.,.,x11x12.x1n,x21x22.x2n,xm1xm2.xmn,收点,发点,订购与运输方案,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确定约束条件中的,路径的问题。,“最短路经”问题的标准算法-弗洛伊德算法。,.,.,其中表示从到的最短路程，若不能相连，,求出铁路和公路的最短路径矩阵,用表示。,运用Floyd算法，得出局部最短路径矩阵。,铁路和公路自身分别构成权矩阵，记为和。,铁路和公路的最短路径矩阵的统一,对公路，将为公路局部最小运费矩阵。,.,对铁路，用铁路的费用进行转换，得局部铁路,最小运费矩阵。,令,对得到的A,再使用一次Floyd算法，得到全局的最短,每两点间最小运费矩阵，从中抽取出到之间,的子矩阵即为所需的。,求最小费用矩阵,.,最小费用矩阵,注：表中的数据乘以0.1为对应的最小费用矩阵的元素。,.,最小费用矩阵,注：表中的数据乘以0.1为对应的最小费用矩阵的元素。,.,模型就转化为典型的二次规划问题。,如果其最优解符合原有的约束条件，则便是原问题的最优解。,如果存在i使那么,针对这些i分两种情况,找出其中的最优的结果。,.,s.t.,根据二次规划软件求解模型,或者运用数学软件Lingo5.0,编程求解,.,将从供应商中除去，再将第7家工厂的供货量,最优解中,改为0以及不小于500两种情况重做。相比之下，,取0的情况总费用较小，从而也把删除。,.,钢管的订购计划：,亿元,5、结果表示,.,钢管的运输方案：,.,1）确定哪个钢厂的销价的变化对购运计划和总费用的影响最大,6、灵敏度分析,s.t.,.,假设该钢厂的销价变化在万元以内，,结论：或的销价的变化影响最大。,.,钢管的订购计划：,亿元,.,2）确定哪个钢厂的生产上限的变化对购运计划和总费用的影响最大,在变化的情况下目标函数减小量及减小的比率,结论：的生产上限的变化影响最大。,.,最小费用矩阵,注：表中的数据乘以0.1为对应的最小费用矩阵的元素。,.,若要铺设的道路不是一条线，而是一个树形图，,7、关于问题（3）,.,s.t.,数学模型,.,运用数学软件Lingo5.0编程求出：,亿元,.,课后练习：,（1）求出最小费用矩阵,（2）求解问题1的二次规