下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 2000年全国数学建模竞赛B题优秀论文

2000年全国数学建模竞赛B题优秀论文.doc

2000年全国数学建模竞赛B题优秀论文

回忆烧成灰0
2017-09-19 0人阅读 举报 0 0 暂无简介

简介:本文档为《2000年全国数学建模竞赛B题优秀论文doc》,可适用于综合领域

管道订购与运输问题 问题重述 基本假设  ()只考虑订购费用和运输费用不考虑装卸等其它费用.  ()钢管单价与订购量、订购次数、订购日期无关.  ()订购汁划是指对每个厂商的定货数量运输方案是指具有如下属性的一批记录:管道区间供应厂商具体运输路线.  ()将每一单位的管道所在地看成一个需求点向一单位管道的所在地运输钢管即为向一个点运输钢管. 符号说明 M:钢厂总数           n:单位管道总数 第i个钢厂          第i个钢厂的产量上限。 第i个钢厂单位钢管的销售价  管道线上第i个站点。 管道线上第i个单位管道的位置。 F:总费用。 从钢厂到点的最低单位费用。问题的简化求SAP矩阵的基本思路是图的最短路算法由于铁路的运输费用与线路的长度不是线性关系,必须对铁路网做一些预处理才能套用图的标准最短路算法下面叙述求SAP矩阵的过程:利用图的标准最短路算法,从铁路网络得出图中任两个点之间的最短路径表T(如果两个点之间不连通,认为它们之间的最短路长度为∞)利用题中的铁路运价表将T中的每个元素(即最短距离)转化为运输费用,将运输费用表记为C将公路的长度换算为运输费用,由公路路程图(包括要沿线铺设管道的公路)得出公路费用图G,若i,j不连通,则令Gij= ∞对于任一组(i,j)∈{,…n}×{,…m}如果Cij<∞,且小于Gij,那么就在公路费用图中加一条边即令Gij=min{Cij,Gij}利用图的标准最短路算法,求公路费用图中任一个S点到任一个A点的最小费用路径,得出SAP矩阵如表所示:SAP矩阵AS问题分析  运输费用等价转换法则:按单位运费相等原则将任意两点间的最短铁路线转换为公路线.对于铁路线上的任意两点用Foyd算法找出两点间最短铁路路线的长度查铁路运价表求得对应的铁路单位运费又设与该段铁路等费用的公路长度为则:               由此我们就在之间用一条等价的公路线来代替间的最短铁路线.如果之间原来就有公路就选择新旧公路中较短的一条.这样我们就把铁路运输网络转换成了公路运输网络. 销价等价转换法则:按单位费用相等将任意钢厂的单位销价转换为公路单位运价.对于钢厂Si的销售单价Pi我们可以虚设一条公路线连接钢厂Si及另一虚拟钢厂其长度为并且满足从而将钢厂的销售单价转换成公路运输单价而新钢厂的销售价为将铁路和销价转换为公路的过程可以由计算机编程实现.通过上述的分析我们可以将原问题化为一个相对简单的产量未定的运输问题利用之间的管道距离和钢厂和站点之间的公路距离建立一个产量未定的运输问题的模型.但是由于并不能代表所有的实际需求点(实际需求点是n个单位管道)因此我们可以用Foyd算法进一步算出个钢厂到所有实际的n个需求点(对于问题一n=对于问题三n=)的最短路径并由此得出一个具有个供应点、n个需求点的产址未定的运输模型.模型的建立产量未定的运输模型根据假设我们可以将每一单位的管道看成一个需求点向一单位管道的所在地运输钢管即为向一个点运输钢管.对每个点我们可以根据该点的位置和最短等价公路距离求出各钢厂与该点之间最小单位运输费用(销价已经归人运输费用之中了).设总共有m个供应点(钢厂)n个需求点我们就可以得到一个产量未定的运输模型:有m个供应点、n个需求点每个供应点的供应量每个需求点需要单位运输单价矩阵为C求使得总运输费用最小的运输方案.其数学规划模型:                  其中:      为单位费用矩阵         为决策矩阵也为矩阵代码如下 模型的求解对于本题上述规划规模宏大现有的一些算法不能胜任我们必须具体问题具体分析结合本题实际情况寻找行之有效的算法.()初始方案的改进的最小元素法和改进的伏格尔法*改进的最小元素法改进的最小元素法又称为贪婪法或瞎子爬山法它的宗旨是每一步都取当前的最优值算法步骤为对费用矩阵C作n次下列循环:①C中找一个最小值②令③C的第j的所有数据改为④如果第i个供应点的供应量已达上限将C的第i行数据全改为。对于问题一和问题三我们用贪婪法求得的最小总费用的初始分别为万元和万元。()调整优化调整优化是将一个离最优解很近的初始解调整到在调整算法下无法更优的程度.调整优化分两个部分第一部分是用试探法对供应点的供应量进行优化.第二部分是用迭代法对供应点进行两两对调优化.*试探法调整优化实际供应量在以下的供应点对每个实际供应量在以·F的供应点只存在两种合理的优化方法:一种是将其供应量增加到另一种是将其供应量减少到.试探法将分别试探进行下列两种优化:其一是先将供应点的供应量强行提升至使用改进的伏格尔法的优先顺序从其它供应点负责供应的需求点抢夺一部分再用对调法优化至无法更优得出一个总费用F其二是先将该供应点的供应量调整为其原供应的需求点由其它钢厂用改进的伏格尔法的优先顺序补充再用对调法优化至无法更优得出一个总费用F那么就应当采取总费用较小的方法.例如对于第一问按改进的伏格尔法获得的初始方案中S的用量仅为优化时试探将其降为和将其提升为后的最优结果分别为万元和万元则说明应将S降为.*用迭代法进行对调优化改进的伏格尔法给出的初始值虽然很接近最优值但仍有不足之处即可能存在两个需求点调换供应点能使总费用更小例如需求点a和的供应点是x和y费用分别是C(x,a)和C(y,b)如果让y供应ax供应b的话费用将是C(ya)和r(cb)如果:          C(ya)r(xb)<C(xa)C(yb)则说明对调后总费用更低.因此我们可以采用迭代法对任意两个需求点的供应点两两对调至无法更优.由于一共只有m=个供应点所以两两对调的可行方案一共有种因此两两对调供应点的方法是可行的具体步骤如下:Stepl 对于任意两个供应点xi和xj  i=…m j=…m )找出所有由xi供应的需求点构成点集A={a,a,c})找出所有由xj供应的需求点构成点集B={b,b,…})对A中所有点如果改用xj来供应将付出的代价构成向量)对B中所有点如果改用xi来供应将付出的代价构成向量)对分别按升序排序.)同时对从前向后遍历如果(表示对调供应者将降低总费用)则对调其供应者直到出现为止.Step 统计这轮对调后的总费用是否比原来的总费用F有明显的进步即。如果有明显的进步则再回Stepl执行否则结束优化.采用改进的最小元素法和改进的伏格尔法得到问题一的初始方案分别采用这种优化方案后竟都达到了相同的最小费用:万元.结果:通过合理假设并引人等价转换原则将管道订购与运输问题转化为单一的公路运输问题.运用组合优化的思想和方法给出了数学模型·产量未定的运输模型.针对此模型我们设计了“改进的最小元素法”和“改进的伏格尔Ph"先求得了个初始解。再通过“试探法”和“迭代法”进行调调优化.最后得出结果:对第·问.最小总费用为万元对第三问.最小总费用为万元.参考文献薛秀谦等编著.《运筹学》中国矿业大学出版社.年.赵新泽著.《线性规划的新方法和应用》.世界图书出版社年.王树禾著.《图论极其算法》.中国科学技术大学出版社.年.LUCASWF著.《离散与系统模型.国防科技大学出版社年钢管订购和运输策略 符号说明·:钢厂在指定期限内钢管的最大产量·之间铺设管道的里程数·:单位钢管从钢厂运到所需最小订购和运输费用·钢厂是否承担制造这种钢管·钢厂运抵Aj点的钢管数量不含路过Aj的部分·运到Ai的所有钢管沿铺设的数量·:运抵Ai的所有钢管沿铺设的数量·:树中Aj的度数·树中Aj的入度·树中Aj的出度·单位钢管公里的公路运输费用。 基本假设根据题目的要求并为达到简化问题的目的我们有以下假设:.假设运到Aj的钢管只能在之间包含Aj的某个区段内铺设,并且到达Aj的钢管在之间包含Aj的铺设区段和到达Aj的钢管在Aj到Aj之间包含Ajl的铺设区段不相交.否则的话总可以调节铺设方案使得总费用减少..在考虑问题时假设钢管价格不可能有太大幅度变化.所以我们只考虑钢管价格在其原售价%的范围内波动.同时我们假定钢厂的产量不可能成倍的增加或减少.我们在减少个单位增加个单位的范围内讨论这意味着我们不考虑钢厂破产或者超大规模扩大生产的情况..在具体铺设每一公里时我们只把钢管运到每一公里开始的地方沿运送方向向前铺然后往前铺设的运送费用我们不予考虑. 模型建立.问题l的模型()决策变量我们首先引入一组一变量,其中表示钢厂Si是否承担制造这种钢管.如果钢厂Si承担制造这种钢管则否则所有的钢管都是先运用后或者转运到其它地方或者在包含Aj的一个区段内铺设我们设从钢厂Si运抵Aj的一个区段内铺设的钢管数量为,这里我们用变量Zj来表示从所有的钢厂运到Aj的钢管总量中沿铺设的部分这里j=,,,这样我们一共引入了三组决策变量:。()目标函数问题的目的是求好的订购和运输方案使得总费用最小事实上总费用可以分成两部分。第一部分包括钢管的订购费用和钢管从钢厂运抵所需的运费我们用来表示单位钢管从钢厂所需的最小订购和运输费用则第一部分费用为      第二部分费用是指钢管运抵后再运到具体铺设地点的费用由假设从到区段部分所需的费用为        其中表示铺设管道的长度这样我们不难得知第二部分费用为  ()约束条件首先由于一个钢厂如果承担制造这种钢管则至少需要生产个单位而钢厂在指定期限内能生产钢管的最大数量为个单位所以我们得到以下一组约束条件     由于订购的所有钢管总量等于的里程数那么     很显然我们可以设因为如果则相当于有数量的钢管是从Aj直接运送到后再送到具体铺设地点。运抵Aj的钢管总数量等于向包含Aj的区段铺设的里程数那么   并且我们还有()数学模型通过上面的分析我们得到问题的如下模型  可以看出这是一个非线性规划问题。  .问题的模型  为了分析钢厂钢管销价的变化对购运计划和总费用的影响对于每个钢厂利用模型(A)我们分别算出它的钢管销价发生一系列的变化后所得到的总费用和购运计划并根据所得到的数据利用Matlab软件拟合出销价变化和总费用变化量关系的曲线对所得到的曲线进行分析和对比找到钢管销价变化对购运计划和总费用影响最大的钢厂.类似地我们用同样的方法对钢厂产量上限发生变化对购运计划和总费用的影响进行了分析.  .问题的模型如果要铺设的管道不是一条线而是一个树形图我们首先给树形图的每条边指定一个方向使得所得到的有向树有一个度数为的顶点的人度为o而其它每个顶点的人度均为.与问题一样我们可以引入变量以及变量它们的含义与问题中的定义完全一致.类似于问题对于有向树的有向边我们用zij表示运抵Ai的所有钢管沿铺设的里程数.数学模型为  参考文献:甘应爱田丰等等运行学清华大学出版社,北京,。袁亚湘孙文瑜著最优化理论与方法科学出版社北京徐俊明著图论及其应用中国科学技术大学出版社合肥

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/10

2000年全国数学建模竞赛B题优秀论文

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利