《钢管订购与运输讲评》由会员分享，可在线阅读，更多相关《钢管订购与运输讲评（12页珍藏版）》请在金锄头文库上搜索。
1、CUMCM2000B 钢管订购的运输i1 2 3 4 5 6 7is800 800 1000 2000 2000 2000 3000ip160 155 155 160 155 150 160一单位钢管的铁路运价如下表？里程（ km）300 及以下 301350 351400 401450 451500运价（万元） 20 23 26 29 32里程（km） 501600 601700 701800 801900 9011000运价（万元） 37 44 50 55 601000 公里友上每增加 100 公里，运价增加 5 万元。公路运输费用为 1 单位钢管每公里 0.1 万元（不足整公里部分按 1
2、 公里计算） 。钢管可由铁路、公路运往铺设地点，不只是运到 ，而是运到管道全线。jA: , , .0 , .1).( , ).( , , ., .1 721521 一一一一一 一一一 一一一 一一一一一一 一一 ii ips SkmkmSAA 赛 题)( , ).1( 一一一一. ,)(2一 一一一一一管道订购与运输问题杨志江， 李国欣， 张 敏指导老师： 中国矿业大学数模教练组(中国矿业大学江苏徐州 221008)点评：本文采用将待铺设管道按单位长度分解成 n 个需求点，建立运输模型的方法避免了问题一和三的差别模型切合原赛题要求并针对原问题的规模，对算法作 y-定的改进，得到了较好的结果摘
3、要：本文在详细分析的基础上，通过合理假设并引人等价转换原则，将管道订购与运输问题转化为单一的公路运输问题运用组合优化的思想和方法，给出了数学模型产量未定的运输模型针对此模型，我们设计了“改进的最小元素法”和“改进的伏格尔 Ph，先求得了 个初始解。再通过“试探法”和“迭代法”进行调调优化最后得出结果：对第问最小总费用为 1279019 万元；对第三问最小总费用为 1407383 万元. (1)2, 2 , ).3(一 一一一一优秀答卷1 问题的重述(略)2 基本假设(1)只考虑订购费用和运输费用，不考虑装卸等其它费用(2)钢管单价与订购量、订购次数、订购日期无关(3)订购汁划是指对每个厂商的定
4、货数量；运输方案是指具有如下属性的(4)订购汁划是指对每个厂商的定货数量；运输方案是指具有如下属性的一批记录：管道区间，供应厂商，具体运输路线(4)将每一单位的管道所在地看成一个需求点，向一单位管道的所在地运输钢管即为向一个点运输钢管3 符号说明M：钢厂总数. n：单位管道总数.第 i 个钢厂 第 i 个钢厂的产量上限。:iS:iS第 i 个钢厂单位钢管的销售价 管道线上第 i 个站点。ipiA管道线上第 i 个单位管道的位置。 F：总费用。id从钢厂 到点 的最低单位费用。:ijC(1,2)iSm (1,2)jdn4 问题分析运输费用等价转换法则：按单位运费相等原则将任意两点间的最短铁路线转
5、换为公路线对于铁路线上的任意两点 ，用 F1oyd 算法找出两点间最短铁路路线的长度 查,ijV ijL铁路运价表求得 ，对应的铁路单位运费 ;又设与该段铁路等费用的公路长度为 ，则：ijLijf ijl0.1ijijfl由此，我们就在 之间用一条等价的公路线来代替 间的最短铁路线如果,ijV,ijV之间原来就有公路，就选择新旧公路中较短的一条这样，我们就把铁路运输网络,ijV转换成了公路运输网络销价等价转换法则：按单位费用相等将任意钢厂的单位销价转换为公路单位运价对于钢厂 Si 的销售单价 Pi，我们可以虚设一条公路线，连接钢厂 Si 及另一虚拟钢厂 ，is其长度为 ，并且满足 ；从而将钢厂
6、的销售单价转换成公路运输单价，而新钢il0.1iilp厂 的销售价为 0.is将铁路和销价转换为公路的过程可以由计算机编程实现通过上述的分析，我们可以将原问题化为一个相对简单的产量未定的运输问题，利用之间的管道距离和钢厂和站点之间的公路距离建立一个产量未定的运输问题的模15A到型但是由于 并不能代表所有的实际需求点 (实际需求点是 n 个单位管道)，因1215,A此，我们可以用 F1oyd 算法进一步算出 7 个钢厂到所有实际的 n 个需求点(对于问题一，n5171;对于问题三，n5903)的最短路径，并由此得出一个具有 7 个供应点、n 个需求点的产址未定的运输模型5 模型的建立产量未定的运
7、输模型根据假设 4，我们可以将每一单位的管道看成一个需求点，向一单位管道的所在地运输钢管即为向一个点运输钢管对每个点，我们可以根据该点的位置和最短等价公路距离，求出各钢厂与该点之间最小单位运输费用 (销价已经归人运输费用之中了) 设总共有 mijC个供应点( 钢厂)，n 个需求点，我们就可以得到一个产量未定的运输模型：有 m 个供应点、n 个需求点，每个供应点的供应量 ；每个需求点需05,i ius要 1 单位，运输单价矩阵为 C，求使得总运输费用最小的运输方案其数学规划模型：1minmnijijFCx105,1,2. ,ij imijijxSmstjnx或其中： 为单位费用矩阵121nmmC
8、 为决策矩阵，也为 0-1 矩阵121nmmxxX6 模型的求解对于本题，上述 0-1 规划规模宏大，现有的一些算法不能胜任，我们必须具体问题具体分析，结合本题实际情况，寻找行之有效的算法(1)初始方案的改进的最小元素法和改进的伏格尔法*改进的最小元素法改进的最小元素法又称为贪婪法或瞎子爬山法，它的宗旨是每一步都取当前的最优值算法步骤为，对费用矩阵 C 作 n 次下列循环：C 中找一个最小值 ；ij令 1;ijxC 的第 j 的所有数据改为+ ；如果 ，第 i 个供应点的供应量已达上限，将 C 的第 i 行数据全改为+ 。1nijis对于问题一和问题三，我们用贪婪法求得的最小总费用的初始分别为
9、 1286692.1 万元和 1414515.2 万元。*改进的伏格尔法改进的最小元素法确定的初始方案往往缺乏全局观念，即为了省节一处的费用，在其它处要花费更多，改进的伏格尔法的主要思想：一个目的地如果不能采用最小值供应（供应点供应不足） ，就必须考虑次小值供应，这里就存在一个差额，差额越大，在不能采用最小值时，损失越大，因此，改进的伏格尔法的宗旨是每一步对当前差值最大的点取当前最小值。算法的步骤为，对矩阵 C 做 n 次下循环：指出每一行最小值与最大值之差最大的一行，第 i 行，找出该行的最小值为 ijC令 ;1ijxC 的第 j 列的所有数据改为 ；如果 ，第 i 个供应点的供应量已达上限
10、，令 C 的第 i 行的所有数据为njiis1。对于问题一和问题三，我们用改进的伏格尔法求得方案的总费用分别为 1279019 万元和 1407383 万元。（2）调整优化调整优化是将一个离最优解很近的初始解调整到在调整算法下无法更优的程度调整优化分两个部分，第一部分是用试探法对供应点的供应量进行优化第二部分是用迭代法对供应点进行两两对调优化*试探法调整优化实际供应量在 500 以下的供应点对每个实际供应量在 500 以F 的供应点，只存在两种合理的优化方法：一种是将其供应量增加到 500，另一种是将其供应量减少到 0试探法将分别试探进行下列两种优化：其一是先将供应点的供应量强行提升至 500
11、，使用改进的伏格尔法的优先顺序，从其它供应点负责供应的需求点抢夺一部分，再用对调法优化至无法更优，得出一个总费用F1；其二是先将该供应点的供应量调整为 0，其原供应的需求点由其它钢厂用改进的伏格尔法的优先顺序补充，再用对调法优化至无法更优，得出一个总费用 F2 那么，就应当采取总费用较小的方法例如，对于第一问，按改进的伏格尔法获得的初始方案中，S 7 的用量仅为 245，优化时，试探将其降为 0 和将其提升为 500 后的最优结果，分别为 1279019 万元和 1280506 万元，则说明应将 S，降为 0*用迭代法进行对调优化改进的伏格尔法给出的初始值虽然很接近最优值，但仍有不足之处，即可
12、能存在两个需求点，调换供应点能使总费用更小，例如，需求点 a 和 6 的供应点是 x 和 y，费用分别是 C(x,a)和 C(y,b)，如果让 y 供应 a，x 供应 b 的话，费用将是 C(y，a)和 r(c，b)，如果：C(y，a)+r(x，b)C(x，a)+C(y，b)则说明对调后总费用更低因此，我们可以采用迭代法对任意两个需求点的供应点两两对调至无法更优由于一共只有 m7 个供应点，所以两两对调的可行方案一共有 种，因此，271C两两对调供应点的方法是可行的，具体步骤如下：Stepl 对于任意两个供应点 xi 和 xj i1，2，m j=1，2，m ij1)找出所有由 xi 供应的需求
13、点，构成点集 Aa 1,a2,c2)找出所有由 xj 供应的需求点，构成点集 Bb 1,b2,3)对 A 中所有点，如果改用 xj 来供应，将付出的代价构成向量 1,Aa4)对 B 中所有点，如果改用 xi 来供应，将付出的代价构成向量 Bb5)对 分别按升序排序和6)同时对 从前向后遍历，如果 (表示对调供应者将降低总费用)，则和 0iab对调其供应者，直到出现 为止0iabStep2 统计这 轮对调后的总费用 是否比原来的总费用 F 有明显的进步，即2mCF。如果有明显的进步，则再回 Stepl 执行，否则结束优()F为 一 固 定 的 较 小 值化令人振奋的是，采用改进的最小元素法和改进
14、的伏格尔法得到问题一的初始方案分别采用这种优化方案后，竟都达到了相同的最小费用：1279019 万元(3)结果(略)参考文献1薛秀谦等编著 运筹学.中国矿业大学出版社1998 年2赵新泽著 线性规划的新方法和应用 世界图书出版社， 1996 年3王树禾著 图论极其算法 中国科学技术大学出版社 1990 年4LUCAS W F 著 离散与系统模型 3国防科技大学出版社， 1996 年钢管订购和运输策略段晓军， 俞昌盛， 吴建德指导老师： 张胜贵(西北工业大学，西安 710072)点评：本文节选的是原沦文中模型的分析与建立以及之前的准备工作部分该部分通过单位钢管的最小运购费，建立了问题求解的二次规
15、划模型特点是思路、表述简明、清晰，尤其是第 3 问的模型具有较强的般性，适用于树形结构的通常情形值得注意的是模型中有关铺设费的假设和表达式与常见情形略有不同摘要：在铺设管道为一条线的情况下我们建立了解决钢管订购和运输问题的非线性规划模型由于变量较少约束条件大都为线性的，口标函数为二次函数所以利用 Lingo 软件可以很快求得比较满意的订购和运输方案我们利用 Matlab 软件，对所得到的数据进行拟合，得到相应的反映销价变化对总费用影响的曲线，然后比较各个钢厂钢管销价变化对总费用影响的大小对于钢厂钢管产量上限变化对总费用和购运计划的影响我们也作了类似的处理如果要铺设的管道是树形图，我们对树形图的每条边定向，建立了与铺设管道为条线时类似的数学模型从而大大拓广了模刑的使用范围在论文中我们还对所建立的模型的优缺点和需要改进的方向进行了讨论1 符号说明 ：钢厂 在指定期限内钢管的最大产量；isi ，之间铺设管道的里程数；,:ijijA到 ：单位钢管从钢厂 运
