《城区公路选址问题论文设计写作》由会员分享,可在线阅读,更多相关《城区公路选址问题论文设计写作(27页珍藏版)》请在金锄头文库上搜索。
1、word城区公路选址问题摘 要城区公路选址是一项利民工程,为将该工程做得更好,建设部门在设计时应最大限度减少造价,从而节约本钱,达到经费最省。为此目的,本文利用函数化思想建立模型求解并给出了五种不同要求下的最优方案。由题目所给数据图1可知,直线AB右上方单位区域中的单位建设费用小于AB左下的单位建设费用,且数据矩阵关于其次对角线对称。因而转弯点无论一个或两个均应位于AB右上区域。问题1要求至多1个转弯点且在网格点上,可分0个和1个转弯点两种情况。对于0个转弯点,即直线AB,通过几何方法得出建设费用为14.9907百万元。对于1个转弯点在网格点上的问题,我们利用函数化思想建立函数关系模型,运用枚
2、举法和权重法,并利用 编程直接输出最小费用。比拟可知,恰有一个转弯点时较无转弯点为优。其方案是选择坐标为5,6或6,5的点,建设费用最小为14.707百万元。对于问题2,我们在问题1解法的根底上,恰当修改 程序,使之适用于两个转弯点的选择,得出最优转弯点为4,7和7,4时,建设费用最小,为百万元。与问题1的结果比拟可知,选择两个转弯点较一个转弯点更优。对于问题3,要求转弯点在网格线上,即至少有一个坐标为整数,分一个转弯点和两个转弯点两种情况。因为整数最优点是最接近理想最优点的整数点,我们可以在问题2解法的根底上,将循环语句中的步长1修改为0.01,运行结果说明,一个转弯点的最优选择是6,4.5
3、7,费用为14.6989百万元;两个转弯点的最优选择是3.62,7和7,3.62,费用为14.6201百万元。因而选择两个转弯点更优。对于问题4,坐标点可以为区间0,9中的任意实数值,我们在问题三解法的根底上对最优点的两个坐标均用步长 0.01循环,得出最优转弯点为(3.58,7.32)和7.32,3.58,此时最小费用为百万元。可见较问题3的答案更优。对于问题5,每个点的单位建设费用都不同,且单位建设费用是连续函数。我们用曲线积分方法建立总费用模型,求出变下限积分函数的最小值,得出最优点为5.31,5.31,最优建设费用为14.707百万元,与问题1一样。最后,我们针对问题的实际情况,对论文
4、的优缺点做了评价,提出了几个改良方向,以便用于指导实际应用。关键词: 函数化建模 编程 枚举法 最优方案 曲线积分法一、 问题重述某区政府计划在如下区域见图1修建一条从A0,9到B9,0的直线型公路,由于涉与路面拆迁等因素,各地段建设费用有所不同,图1中的数字代表该区域公路单位建设费用单位:百万元。未标数字的任何地方单位建设费用均为1。图1的每个网格长与宽都是1个单位。每个网格的边界上建设费用按该地区最小单位费用计算。 请你按建设部门的如下具体要求,从建设费用最省的角度,给出最优的方案。1公路至多只能有1个转弯点,且转弯点只能建在图1所示的网格点上。2公路至多可以有2个转弯点,且转弯点只能建在
5、图1所示的网格点上。3公路至多只能有2个转弯点,且转弯点只能建在图1所示的网格线上。4公路至多只能有2个转弯点,转弯点可以建在图1所示区域的任何位置。5如果各区域的单位建设费用为百万元,公路至多只能有1个转弯点,转弯点可以建在图1所示区域的任何位置。图1二、 问题分析针对问题一:需要求出当公路至多只能有1个转弯点且转弯点只能建在图1所示的网格点上时所需的费用最省的目标值。首先,我们计算出没有转弯点时花费为14.9907百万元。对于有一个转弯点的,我们利用函数化建模思想将W与、的关系用数学方程式表达出来,接着利用 编程将函数关系式进展运算,使用枚举法得出所有可能的转弯点的值,最后通过查找语句找出
6、所得数据中的最小值,在与没有转弯点的花费比拟,较小的即为可用的最优方案。针对问题二:需要求出当公路至多可以有2个转弯点且转弯点只能建在图1所示的网格点上时所需的费用最省的目标值。在问题1的根底上,依旧利用函数化建模思想,经过分析,将 程序中的一个变量增加为两个,通过枚举法,即可得出使得W最小的两个坐标值。针对问题三:需要求出当公路至多只能有2个转弯点且转弯点只能建在图1所示的网格线上时所需的费用最省的目标值,坐标点至少有一个为小数,在问题二的根底上设定x或y其一必为小数,即步长改为0.01,思想同二。针对问题四:需要求出当公路至多只能有2个转弯点但转弯点可以建在图1所示区域的任何位置时所需的费
7、用最省的目标值。此时,坐标点为0-9之间的任意实数,有两种情况:一种为有一个转弯点,另一种为有两个转弯点。在问题一、二的根底上,针对第一种情况,只需将第一问的程序中的步长改为0.01;针对第二种情况,只需将第二问程序中的步长改为0.01,通过比拟两种情况下的值,可得出最优方案。针对问题五:如果各区域的单位建设费用为百万元,公路至多只能有1个转弯点,转弯点可以建在图1所示区域的任何位置。因为每个点的单位建设费用不同,但又是连续变化的,故我们可以利用微积分法思想,假设在极小的一段路程内建设费用是一样的,由此建立一个积分方程,通过编码找出花费最小值,从而得出最优方案。三、 模型的假设1、 区域内所有
8、位置的路面状况均一样2、 区域内所有位置的路面条件均一样3、 不考虑软件计算带来的极小误差4、地理环境对路线的设计没有影响四、 符号说明1:单转弯点的坐标;2:双转弯点中靠近A点的坐标;3:双转弯点中靠近B点的坐标;4:总建设费用;5:单位区域的公路长度;6:第条路段单位建设费用;7:第条路段费用;8:第条路段与网格线交点的横坐标矩阵;9:第条路段与网格线交点的纵坐标矩阵; 五、 模型的建立与求解至多只能有1个转弯点且转弯点只能建在网格点上。1没有转弯点时:W=百万元2有一个转弯点时:利用函数化思想,建立与、的函数关系:第1步:在网格点上任取一点图1,根据直线两点式方程:,可得直线的方程为P图
9、1 第2步:由直线方程可求得AP与x=i(i=0、1、2)和y=j(j=yp8、9)的所有交点,并按x从小到大的排序, ,i=1,2,3,4取,和,如此可以根据它们的中点得到这两点的路段需要的加权权重,即:因此对于有,累加可得AP段公路的费用。PB段公路的费用同理可得。故此总费用的表达式为:5.1.2 软件求解根据枚举法,利用Matlab软件求解程序见附录一,流程图如图2:x=1 y=1 AP、 PB的解析式直线AP、PB与网格线交点的坐标集合各单位区域的公路长度输出WYy=8 ?单位区域内线段的中点坐标得到权重 x=8?N x=x+1YN y=y+1 x=1图2 求解的流程图从程序运行结果可
10、以看出,使得W最小的点的坐标为5,6和6,5 ,此时,=14.707百万元。所以,将转弯点设在坐标为5,6或6,5的网格点上时,能使建设费用最省,即为最优的方案。如图3: 图3 在该问题中,我们采用枚举法,对所有情况下所需的建设费用进展了全面的求解,从中得到了使得W最小的P点,故结论可靠。至多可以有2个转弯点且转弯点只能建在网格点上。5.2.1.1 公路在直线AB的上方以直线AB为对称轴,上方区域的单位建设费用要低于其下方对应区域的单位建设费用。如图4所示,假如有某段公路在直线AB的下方,如此以直线AB为对称轴,得到与其对称的公路。两公路长度相等,但下方价格明显高与上方,故公路应在直线AB的上
11、方。图45.2.1.2 公路呈向下趋势假如公路趋势如图5所示,路段向上,水平或竖直,如此连接,如此易得公路的建设费用低于A- P1- P2段的建设费用图5所以,我们得到公路的大致走向,如图6所示:图6其坐标特点为:m b5.2.2 建立模型第一步:根据两点的位置关系,在网格点上任取两点,如图7。根据直线两点式方程:,得到直线A,的方程:A:y9m = m - 9x:(y - n)(a-m)=(b-n)(x-m)(y-b)9-a=-b(x-a)P2P1图7 第二步:根据直线方程可求得直线A与x=i(i=0、1、2)和y=j(j=yp8、9)的所有交点,并按x从小到大的排序,即:,i=1,2,3,
12、4取,和,如此可以根据它们的中点得到这两点的路段需要的加权权重,即:第3步:对于有,累加得到A段公路的费用,同理得到,段公路的费用。故整条公路的总费用表达式为:5.2.2 软件求解编写Matlab编程,利用枚举法,得到所有可能得到的两个转弯点的情况时所需要的总建设费用W,程序见附录二,分析流程图如图8:输出W 输出W 图8 求两个转弯点在网格点上时的流程图输出W 经过分析,得出使得W最小的两点坐标为4,7和7,4,此时,=14.6241百万元。所以,将两转弯点分别设在坐标为4,7和7,4的网格点上时,能使建设费用最省,即为最优的方案。如图9:图9 两转弯点在网格点上时的最优方案至多只能有2个转
13、弯点且转弯点只能建网格线上。5.3.1 建立模型5.3.1.1 有两个转弯点在第二问的根底上,我们可推出公路的大致走向,如图10图10 公路的大致走向第 1 步:根据两点的位置关系,在网格点上任取两点,得到直线A,的方程:A:y9m = m - 9x:(y - n)(a-m)=(b-n)(x-m):(y-b)9-a=-b(x-a) 第 2 步:在坐标满足条件的情况下,如果n为整数根据直线方程可求得直线A与x=i(i=0、1、2)和y=j(j=yp8、9)的所有交点,并按x从小到大的排序,即:,i=1,2,3,4取,和,如此可以根据它们的中点得到这两点的路段需要的加权权重,即:假如n为小数,如此
14、取n的整数局部再加1,重复上述步骤;如果m为整数,同样方法得到,假如m为小数,如此取m的整数局部,然后计算得到,。第3步:对于有,累加得到A段公路的费用,同理得到,段公路的费用。故整条公路的总费用表达式为:5.3.1.2 有一个转弯点 与设立两个转弯点相比,只需在网格线上任取一个点P,思想和方法都与之一样5.3.2 软件求解5.3.2.1 有两个转弯点以第二问的程序为根底,将循环中的步长设为0.01,在m或n为整数且a或b为整数的条件下,寻找最优解。程序见附录三,流程图以A为例显示了取整与求取线段与网格线交点的过程,其他步骤同第二问。如图11。m,n,a,b取在0.01,8.99步长为0.01内的所有实数Nm或n为整数且a或b为整数?YNn为整数?取n整数局部加1Y将n,9上的整数对应的x放入矩阵z1Nm为整数?Y取m整数局