城区公路选址最优方案设计--数模论文

《城区公路选址最优方案设计--数模论文》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2012年东南大学数学建模竞赛东南大学第六届大学生数学建模竞赛（2012年5月17日13时－5月23日13时）参赛题目AB√（在所选题目上打勾）参赛队员1参赛队员2参赛队员3姓名傅玮烽路畅方晗婧学号040111220401162404011202学院信息科学与工程信息科学与工程学信息科学与工程（系）学院院学院手机158506979691585185699315851836993Email464695699@qq.comLuchangharry@126.com310689057@qq.com东南大学教务处东

2、南大学数学建模竞赛组委会12012年东南大学数学建模竞赛A题城区公路选址问题摘要:本题要求对不同的修路方案进行综合考虑，并从中选出费用最少的方案。该问题可以归结为一个0-1整数规划和动态规划最短路径模型。我们将每个格点定义为0-1变量，建立目标函数—即各0-1变量格点与费用权值的乘积之和，其最小值即费用最小值，取值为1的格点即为最优点。方案一和方案二可归结为离散的点和离散的权值问题，方案三和方案四是连续的点和离散的权值问题，第五问为连续的点和连续的权值问题。问题（1），要求在图1所示的网格上选一个转弯点，

3、使得A点经过该转弯点到达B点的建设费用最低。通过求解A（或B）到网格点上的费用权值，建立线性规划模型，得到从A点经过一个转弯点到达B点的最小费用为14.5746（百万元），最优路径为AB(0,9)(2,8)(9,0)或者AB(0,9)(8,2)(9,0)问题（2），要求在图1所示的网格上找2个转弯点，使得A点经过这两个转弯点到达B点的建设费用最低。将网格点分为三种情形进行讨论，分别建立线性规划模型，得到从A点经过一个转弯点到达B点的最小费用为14.6151（百万元），最优路径为AB(0,9)

4、(2,8)(5,6)(9,0)或者AB(0,9)(6,5)(8,2)(9,0)问题（3），要求在图1所示的网格线找2个转弯点，使得A点经过这两个转弯点到达B点的建设费用最低。与问题（2）类似，建立数学规划模型，得到从A点经过一个转弯点到达B点的最小费用为14.5657（百万元），最优路径为AB(0,9)(1.00,8.43)(5.00,6.28)(9,0)或者AB(0,9)(6.28,5.00)(8.43,1.00)(9,0)问题（4）：要求在图1所示的网格线找2个转弯点，使得A点经过这

5、两个转弯点到达B点的建设费用最低。与问题（2）类似，建立数学规划模型，得到从A点经过一个转弯点到达B点的最小费用为13.5926（百万元），最优路径为AB(0,9)(6.84,5.62)(8.36,1.19)(9,0)或者AB(0,9)(1.19,8.36)(5.62,6.84)(9,0)问题（5）：要求在图1所示的网格线找2个转弯点，使得A点经过这两个转弯点到达B点的建设费用最低。与问题（2）类似，建立数学规划模型，得到从A点经过一个转弯点到达B点的最小费用为14.1312（百万元），最优路

6、径为A(0,9)(1.36,8.47)B(9,0)或者A(0,9)(8.47,1.36)B(9,0)关键字:公路选址费用最省路径0-1整数规划动态规划权值22012年东南大学数学建模竞赛一.问题重述某区政府计划在下列区域（见图1）修建一条从A（0,9）到B（9,0）的直线型公路，由于涉及路面拆迁等因素，各地段建设费用有所不同，图1中的数字代表该区域公路单位建设费用（单位：百万元）。未标数字的任何地方单位建设费用均为1。图1的每个网格长与宽都是1个单位。每个网格的边界上建设费用按该地区最小单位费用计

7、算。现有下列五种方案:（1）公路至多只能有1个转弯点，且转弯点只能建在图1所示的网格点上。（2）公路至多可以有2个转弯点，且转弯点只能建在图1所示的网格点上。（3）公路至多只能有2个转弯点，且转弯点只能建在图1所示的网格线上。（4）公路至多只能有2个转弯点，转弯点可以建在图1所示区域的任何位置。22（5）如果各区域的单位建设费用为1.5-0.1(xy4)(4)（百万元），公路至多只能有1个转弯点，转弯点可以建在图1所示区域的任何位置。图132012年东南大学数学建模竞赛二.问题分析本题要求建立一个从

8、A地到B地修一条穿过不同修路费用区域的直线型公路，并使费用最少的最优方案。该问题可以归结为运筹学中的0-1整数规划与动态规划中最短路径的模型。0—1型整数规划是整数规划的特殊情形，它的决策变量仅取0或1这两个值，这时的决策变量也称为0—1变量。在实际问题中，有些问题只需回答“是”或“否”，问题就解决了，描述这类问题的变量只需取两个值就可以了。例如是否采纳某个方案；某项任务是否可以交某人承担；集装箱内是否装入某种货物等等。对于这