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

2012年东南大学数学建模竞赛

东南大学
第六届大学生数学建模竞赛

（2012年5月17日13时－5月23日13时）
参赛题目A√B
（在所选题目上打勾）

参赛队员1参赛队员2参赛队员3
姓名傅玮烽路畅方晗婧
学号040111220401162404011202
学院信息科学与工程信息科学与工程学信息科学与工程
（系）学院院学院
手机158506979691585185699315851836993
[e-mail]@[e-mail]

东南大学教务处

东南大学数学建模竞赛组委会

1

2012年东南大学数学建模竞赛

A题城区公路选址问题
摘要:

本题要求对不同的修路方案进行综合考虑，并从中选出费用最少的方案。该问题可以归结为一
个0-1整数规划和动态规划最短路径模型。我们将每个格点定义为0-1变量，建立目标函数—即各
0-1变量格点与费用权值的乘积之和，其最小值即费用最小值，取值为1的格点即为最优点。方案
一和方案二可归结为离散的点和离散的权值问题，方案三和方案四是连续的点和离散的权值问题，
第五问为连续的点和连续的权值问题。

问题（1），要求在图1所示的网格上选一个转弯点，使得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)(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点经过这两个转弯点到达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（百万元），最优路径为

ABAB(0,9)(1.36,8.47)(9,0)或者(0,9)(8.47,1.36)(9,0)

关键字:

公路选址费用最省路径0-1整数规划动态规划权值

2

2012年东南大学数学建模竞赛

一.问题重述

某区政府计划在下列区域（见图1）修建一条从A（0,9）到B（9,0）的直线型公路，由于涉及

路面拆迁等因素，各地段建设费用有所不同，图1中的数字代表该区域公路单位建设费用（单位：

百万元）。未标数字的任何地方单位建设费用均为1。图1的每个网格长与宽都是1个单位。每个网

格的边界上建设费用按该地区最小单位费用计算。

现有下列五种方案:

（1）公路至多只能有1个转弯点，且转弯点只能建在图1所示的网格点上。

（2）公路至多可以有2个转弯点，且转弯点只能建在图1所示的网格点上。

（3）公路至多只能有2个转弯点，且转弯点只能建在图1所示的网格线上。

（4）公路至多只能有2个转弯点，转弯点可以建在图1所示区域的任何位置。

（5）如果各区域的单位建设费用为1.5-0.1(xy4)22(4)（百万元），公路至多只能有1个转

弯点，转弯点可以建在图1所示区域的任何位置。

图1
3

2012年东南大学数学建模竞赛

二.问题分析

本题要求建立一个从A地到B地修一条穿过不同修路费用区域的直线型公路，并使费用最少的

最优方案。该问题可以归结为运筹学中的0-1整数规划与动态规划中最短路径的模型。0—1型整数

规划