管道订购与运输问题-2000年全国数学建模竞赛B题优秀论文.docx
《管道订购与运输问题-2000年全国数学建模竞赛B题优秀论文.docx》由会员分享,可在线阅读,更多相关《管道订购与运输问题-2000年全国数学建模竞赛B题优秀论文.docx(18页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、管道订购与运输问题1 问题重述2 基本假设 (1)只考虑订购费用和运输费用,不考虑装卸等其它费用 (2)钢管单价与订购量、订购次数、订购日期无关 (3)订购汁划是指对每个厂商的定货数量;运输方案是指具有如下属性的一批记录:管道区间,供应厂商,具体运输路线 (4)将每一单位的管道所在地看成一个需求点,向一单位管道的所在地运输钢管即为向一个点运输钢管3 符号说明 M:钢厂总数. n:单位管道总数. 第i个钢厂 第i个钢厂的产量上限。 第i个钢厂单位钢管的销售价 管道线上第i个站点。 管道线上第i个单位管道的位置。 F:总费用。 从钢厂到点的最低单位费用。4 问题的简化求 S AP 矩阵的基本思路是
2、图的最短路算法 . 由于铁路的运输费用与线路的长度不是线性关系 ,必须对铁路网做一些预处理才能套用图的标准最短路算法 . 下面叙述求 S AP 矩阵的过程:1. 利用图的标准最短路算法 ,从铁路网络得出图中任两个点之间的最短路径表 T (如 果两个点之间不连通 ,认为它们之间的最短路长度为+ ) .2. 利用题中的铁路运价表将 T 中的每个元素 (即最短距离 )转化为运输费用 ,将运输费 用表记为 C.3. 将公路的长度换算为运输费用 ,由公路路程图 (包括要沿线铺设管道的公路 )得出公路费用图 G,若 i, j 不连通 ,则令 Gij = + .4.对于任一组 ( i , j) 1, n 1
3、, m 如果 Cij + ,且小于 Gij ,那么就在公路费 用图中加一条边. 即令 Gij = minCij , Gij .5.利用图的标准最短路算法 ,求公路费用图中任一个 S 点到任一个 A 点的最小费用 路径 ,得出 S AP 矩阵. 如表 1所示:SAP 矩阵A123456789101112131415S1170716031402986380205312126429209601060121212801420221572053190217161110955860712114214201460156017121780192032307220320021816121010559608624
4、8282086096011121180132042607250323522166156014051310116284262051061076283097052557245322522066146013051210111279257033051071273087062657255323522166156014051310121284262051045026211028072757265324522266166015051410131299276066056038226020 5问题分析 运输费用等价转换法则:按单位运费相等原则将任意两点间的最短铁路线转换为公路线对于铁路线上的任意两点,用F1oy
5、d算法找出两点间最短铁路路线的长度查铁路运价表求得,对应的铁路单位运费;又设与该段铁路等费用的公路长度为,则: 由此,我们就在之间用一条等价的公路线来代替间的最短铁路线如果之间原来就有公路,就选择新旧公路中较短的一条这样,我们就把铁路运输网络转换成了公路运输网络 销价等价转换法则:按单位费用相等将任意钢厂的单位销价转换为公路单位运价对于钢厂Si的销售单价Pi,我们可以虚设一条公路线,连接钢厂Si及另一虚拟钢厂,其长度为,并且满足;从而将钢厂的销售单价转换成公路运输单价,而新钢厂的销售价为0.将铁路和销价转换为公路的过程可以由计算机编程实现通过上述的分析,我们可以将原问题化为一个相对简单的产量未
6、定的运输问题,利用之间的管道距离和钢厂和站点之间的公路距离建立一个产量未定的运输问题的模型但是由于并不能代表所有的实际需求点(实际需求点是n个单位管道),因此,我们可以用F1oyd算法进一步算出7个钢厂到所有实际的n个需求点(对于问题一,n5171;对于问题三,n5903)的最短路径,并由此得出一个具有7个供应点、n个需求点的产址未定的运输模型6 模型的建立产量未定的运输模型根据假设4,我们可以将每一单位的管道看成一个需求点,向一单位管道的所在地运输钢管即为向一个点运输钢管对每个点,我们可以根据该点的位置和最短等价公路距离,求出各钢厂与该点之间最小单位运输费用(销价已经归人运输费用之中了)设总
7、共有m个供应点(钢厂),n个需求点,我们就可以得到一个产量未定的运输模型:有m个供应点、n个需求点,每个供应点的供应量;每个需求点需要1单位,运输单价矩阵为C,求使得总运输费用最小的运输方案其数学规划模型: 其中: 为单位费用矩阵 为决策矩阵,也为0-1矩阵代码如下7 模型的求解对于本题,上述0-1规划规模宏大,现有的一些算法不能胜任,我们必须具体问题具体分析,结合本题实际情况,寻找行之有效的算法(1)初始方案的改进的最小元素法和改进的伏格尔法*改进的最小元素法改进的最小元素法又称为贪婪法或瞎子爬山法,它的宗旨是每一步都取当前的最优值算法步骤为,对费用矩阵C作n次下列循环:C中找一个最小值;令
8、C的第j的所有数据改为+;如果,第i个供应点的供应量已达上限,将C的第i行数据全改为+。对于问题一和问题三,我们用贪婪法求得的最小总费用的初始分别为1286692.1万元和1414515.2万元。(2)调整优化调整优化是将一个离最优解很近的初始解调整到在调整算法下无法更优的程度调整优化分两个部分,第一部分是用试探法对供应点的供应量进行优化第二部分是用迭代法对供应点进行两两对调优化*试探法调整优化实际供应量在500以下的供应点对每个实际供应量在500以F的供应点,只存在两种合理的优化方法:一种是将其供应量增加到500,另一种是将其供应量减少到0试探法将分别试探进行下列两种优化:其一是先将供应点的
9、供应量强行提升至500,使用改进的伏格尔法的优先顺序,从其它供应点负责供应的需求点抢夺一部分,再用对调法优化至无法更优,得出一个总费用F1;其二是先将该供应点的供应量调整为0,其原供应的需求点由其它钢厂用改进的伏格尔法的优先顺序补充,再用对调法优化至无法更优,得出一个总费用F2那么,就应当采取总费用较小的方法例如,对于第一问,按改进的伏格尔法获得的初始方案中,S7的用量仅为245,优化时,试探将其降为0和将其提升为500后的最优结果,分别为1279019万元和1280506万元,则说明应将S,降为0*用迭代法进行对调优化改进的伏格尔法给出的初始值虽然很接近最优值,但仍有不足之处,即可能存在两个
10、需求点,调换供应点能使总费用更小,例如,需求点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个供应点,所以两两对调的可行方案一共有种,因此,两两对调供应点的方法是可行的,具体步骤如下:Stepl 对于任意两个供应点xi和xj i1,2,m j=1,2,m 1)找出所有由xi供应的需求点,构成点集Aa1,a2,c2)找出所有由xj供应的需求点,构成点集B
11、b1,b2,3)对A中所有点,如果改用xj来供应,将付出的代价构成向量4)对B中所有点,如果改用xi来供应,将付出的代价构成向量5)对分别按升序排序6)同时对从前向后遍历,如果(表示对调供应者将降低总费用),则对调其供应者,直到出现为止Step2 统计这轮对调后的总费用是否比原来的总费用F有明显的进步,即。如果有明显的进步,则再回Stepl执行,否则结束优化采用改进的最小元素法和改进的伏格尔法得到问题一的初始方案分别采用这种优化方案后,竟都达到了相同的最小费用:1279019万元 8 结果:通过合理假设并引人等价转换原则,将管道订购与运输问题转化为单一的公路运输问题运用组合优化的思想和方法,给
12、出了数学模型产量未定的运输模型针对此模型,我们设计了“改进的最小元素法”和“改进的伏格尔Ph,先求得了个初始解。再通过“试探法”和“迭代法”进行调调优化最后得出结果:对第问最小总费用为1279019万元;对第三问最小总费用为1407383万元参考文献1薛秀谦等编著运筹学.中国矿业大学出版社1998年2赵新泽著线性规划的新方法和应用世界图书出版社,1996年3王树禾著图论极其算法中国科学技术大学出版社1990年4LUCAS W F著离散与系统模型3国防科技大学出版社,1996年钢管订购和运输策略1 符号说明:钢厂在指定期限内钢管的最大产量;,之间铺设管道的里程数;:单位钢管从钢厂运到,所需最小订
13、购和运输费用;钢厂是否承担制造这种钢管;钢厂运抵Aj点的钢管数量,不含路过Aj的部分;运到Ai的所有钢管沿铺设的数量;:运抵Ai的所有钢管沿铺设的数量;:树中Aj的度数;树中Aj的入度;树中Aj的出度;单位钢管1公里的公路运输费用。2 基本假设根据题目的要求,并为达到简化问题的目的,我们有以下假设:1假设运到Aj的钢管,只能在之间包含Aj的某个区段内铺设,并且到达Aj的钢管在之间包含Aj的铺设区段和到达Aj+1,的钢管在Aj到Aj+2之间包含Aj+l的铺设区段不相交否则的话,总可以调节铺设方案,使得总费用减少2在考虑问题2时,假设钢管价格不可能有太大幅度变化所以,我们只考虑钢管价格在其原售价1
14、0的范围内波动同时,我们假定,钢厂的产量不可能成倍的增加或减少我们在减少300个单位,增加600个单位的范围内讨论,这意味着我们不考虑钢厂破产或者超大规模扩大生产的情况3在具体铺设每一公里时,我们只把钢管运到每一公里开始的地方,沿运送方向向前铺,然后往前铺设的运送费用我们不予考虑3 模型建立1问题l的模型(1)决策变量我们首先引入一组0一1变量,其中表示钢厂Si是否承担制造这种钢管如果钢厂Si承担制造这种钢管,则,否则.所有的钢管,都是先运用后,或者转运到其它地方,或者在包含Aj的一个区段内铺设,我们设从钢厂Si运抵Aj的一个区段内铺设的钢管数量为,这里我们用变量Zj来表示从所有的钢厂运到Aj
15、的钢管总量中沿铺设的部分,这里j=1,2, ,14.这样,我们一共引入了三组决策变量:。(2)目标函数问题的目的是求好的订购和运输方案,使得总费用最小,事实上,总费用可以分成两部分。第一部分包括钢管的订购费用和钢管从钢厂运抵所需的运费;我们用来表示单位钢管从钢厂所需的最小订购和运输费用,则第一部分费用为 第二部分费用是指钢管运抵后,再运到具体铺设地点的费用,由假设3,从到区段部分所需的费用为 其中表示铺设管道的长度,这样,我们不难得知第二部分费用为 (3)约束条件首先,由于一个钢厂如果承担制造这种钢管,则至少需要生产500个单位,而钢厂在指定期限内能生产钢管的最大数量为个单位,所以,我们得到以
16、下一组约束条件 由于订购的所有钢管总量等于的里程数,那么 很显然,我们可以设,因为如果,则相当于有数量的钢管是从Aj直接运送到后再送到具体铺设地点。运抵Aj的钢管总数量,等于向包含Aj的区段铺设的里程数,那么 并且,我们还有(4)数学模型通过上面的分析,我们得到问题1的如下模型 可以看出,这是一个非线性规划问题。 2问题2的模型 为了分析钢厂钢管销价的变化对购运计划和总费用的影响,对于每个钢厂,利用模型(A),我们分别算出它的钢管销价发生一系列的变化后,所得到的总费用和购运计划;并根据所得到的数据,利用Matlab软件拟合出销价变化和总费用变化量关系的曲线,对所得到的曲线进行分析和对比,找到钢
17、管销价变化对购运计划和总费用影响最大的钢厂类似地,我们用同样的方法,对钢厂产量上限发生变化对购运计划和总费用的影响进行了分析 3问题3的模型如果要铺设的管道不是一条线,而是一个树形图,我们首先给树形图的每条边指定一个方向,使得所得到的有向树有一个度数为1的顶点的人度为o,而其它每个顶点的人度均为1与问题1一样,我们可以引入01变量以及变量,它们的含义与问题1中的定义完全一致类似于问题1,对于有向树的有向边我们用zij表示运抵Ai的所有钢管沿,铺设的里程数数学模型为 参考文献:1甘应爱,田丰等等.运行学.清华大学出版社,北京,1994。2袁亚湘.孙文瑜著.最优化理论与方法.科学出版社,北京,19
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 管道 订购 运输 问题 2000 全国 数学 建模 竞赛 优秀论文
限制150内