城区公路选址问题论文设计写作

1、城区公路选址问题摘 要城区公路选址是一项利民工程，为将该工程做得更好，建设部门在设计时应最大限度减少造价，从而节约成本，达到经费最省。为此目的，本文利用函数化思想建立模型求解并给出了五种不同要求下的最优方案。由题目所给数据（图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）时，建设费用最小，为14.6241百万元。与问题1的结果比较可知，选择两个转弯点较一个转弯点更优。对于问题3，要求转弯点在网格线上，即至少有一个坐标为整数，分一个转弯点和两个转弯点两种情况。因为整数最优点是最接近理想最优点的整数点，我们可以在问题2解法的基础上，将循环语句中的步长1修改为0.01，运行结果说明，一

3、个转弯点的最优选择是（6，4.57），费用为14.6989百万元；两个转弯点的最优选择是（3.62,7）和（7,3.62），费用为14.6201百万元。因而选择两个转弯点更优。对于问题4，坐标点可以为区间0,9中的任意实数值，我们在问题三解法的基础上对最优点的两个坐标均用步长 0.01循环，得出最优转弯点为(3.58,7.32)和（7.32,3.58），此时最小费用为14.54百万元。可见较问题3的答案更优。对于问题5，每个点的单位建设费用都不同，且单位建设费用是连续函数。我们用曲线积分方法建立总费用模型，求出变下限积分函数的最小值，得出最优点为（5.31,5.31）,最优建设费用为14.70

4、7百万元，与问题1相同。最后，我们针对问题的实际情况，对论文的优缺点做了评价，提出了几个改进方向，以便用于指导实际应用。关键词： 函数化建模 编程 枚举法 最优方案 曲线积分法 一、 问题重述某区政府计划在下列区域（见图1）修建一条从A（0,9）到B（9,0）的直线型公路，由于涉及路面拆迁等因素，各地段建设费用有所不同，图1中的数字代表该区域公路单位建设费用（单位：百万元）。未标数字的任何地方单位建设费用均为1。图1的每个网格长与宽都是1个单位。每个网格的边界上建设费用按该地区最小单位费用计算。 请你按建设部门的如下具体要求，从建设费用最省的角度，给出最优的方案。（1）公路至多只能有1个转弯点

5、，且转弯点只能建在图1所示的网格点上。（2）公路至多可以有2个转弯点，且转弯点只能建在图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，思

7、想同二。针对问题四：需要求出当公路至多只能有2个转弯点但转弯点可以建在图1所示区域的任何位置时所需的费用最省的目标值。此时，坐标点为0-9之间的任意实数，有两种情况：一种为有一个转弯点，另一种为有两个转弯点。在问题一、二的基础上，针对第一种情况，只需将第一问的程序中的步长改为0.01；针对第二种情况，只需将第二问程序中的步长改为0.01，通过比较两种情况下的值，可得出最优方案。针对问题五：如果各区域的单位建设费用为（百万元），公路至多只能有1个转弯点，转弯点可以建在图1所示区域的任何位置。因为每个点的单位建设费用不同，但又是连续变化的，故我们可以利用微积分法思想，假设在极小的一段路程内建设费用

8、是相同的，由此建立一个积分方程，通过编码找出花费最小值，从而得出最优方案。三、 模型的假设1、 区域内所有位置的路面状况均相同2、 区域内所有位置的路面条件均相同3、 不考虑软件计算带来的极小误差4、地理环境对路线的设计没有影响四、 符号说明（1）：单转弯点的坐标；（2）：双转弯点中靠近A点的坐标；（3）：双转弯点中靠近B点的坐标；（4）:总建设费用；（5）：单位区域的公路长度；（6）：第条路段单位建设费用；（7）：第条路段费用；（8）：第条路段与网格线交点的横坐标矩阵；（9）：第条路段与网格线交点的纵坐标矩阵； 五、 模型的建立与求解5.1 至多只能有1个转弯点且转弯点只能建在网格点上。5.

9、1.1建立模型（1）没有转弯点时：W=（百万元）（2）有一个转弯点时：利用函数化思想，建立与、的函数关系：第1步：在网格点上任取一点（图1），根据直线两点式方程：，可得直线的方程为P 图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

10、、 PB的解析式直线AP、PB与网格线交点的坐标集合各单位区域的公路长度输出WYy=8 ?单位区域内线段的中点坐标得到权重 x=8?N x=x+1YN y=y+1 x=1图2 求解的流程图从程序运行结果可以看出，使得W最小的点的坐标为（5,6）和（6,5） ，此时，=14.707百万元。因为14.707<14.9907所以，将转弯点设在坐标为（5,6）或（6,5）的网格点上时，能使建设费用最省，即为最优的方案。如图3： 图35.1.3可靠性分析 在该问题中，我们采用枚举法，对所有情况下所需的建设费用进行了全面的求解，从中得到了使得W最小的P点，故结论可靠。5.2至多可以有2个转弯点且转弯

11、点只能建在网格点上。5.2.1判断公路的大致走向5.2.1.1 公路在直线AB的上方以直线AB为对称轴，上方区域的单位建设费用要低于其下方对应区域的单位建设费用。如图4所示，若有某段公路在直线AB的下方，则以直线AB为对称轴，得到与其对称的公路。两公路长度相等，但下方价格明显高与上方，故公路应在直线AB的上方。图45.2.1.2 公路呈向下趋势 若公路趋势如图5所示，路段向上，水平或竖直，则连接,则易得公路的建设费用低于A- P1- P2段的建设费用图5所以，我们得到公路的大致走向，如图6所示：图6其坐标特点为：m < a ; n > b5.2.2 建立模型第一步：根据两点的位置关

12、系，在网格点上任取两点，如图7。根据直线两点式方程：，得到直线A,的方程：A：（y9）m = （m - 9）x :(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，4）取（，）和（，）则可以根据它们的中点得到这两点的路段需要的加权权重，即：第3步：对于有，累加得到A段公路的费用，同理得到,段公路的费用。故整条公路的总费用表达式为：5.2.2 软件求解5.2.2.1当有两个转弯

13、点时编写Matlab编程，利用枚举法，得到所有可能得到的两个转弯点的情况时所需要的总建设费用W，程序见附录二，分析流程图如图8：输出W 输出W 图8 求两个转弯点在网格点上时的流程图输出W 经过分析，得出使得W最小的两点坐标为（4,7）和（7,4），此时，=14.6241百万元。所以，将两转弯点分别设在坐标为（4,7）和（7,4）的网格点上时，能使建设费用最省，即为最优的方案。如图9：图9 两转弯点在网格点上时的最优方案5.3至多只能有2个转弯点且转弯点只能建网格线上。5.3.1 建立模型5.3.1.1 有两个转弯点在第二问的基础上，我们可推出公路的大致走向，如图10图10 公路的大致走向第

14、1 步：根据两点的位置关系，在网格点上任取两点，得到直线A,的方程：A：（y9）m = （m - 9）x :(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为小数，则取n的整数部分再加1，重复上述步骤；如果m为整数，同样方法得到（，），若m为小数，则取m的整数部分，然

15、后计算得到（，）。第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上的整数对

16、应的x放入矩阵z1Nm为整数？Y取m整数部分将0,m上的整数对应的y放入矩阵w1图11 两个转弯点下的部分流程图5.3.2.2设一个转弯点 编程思路与设两个转弯点的情况相同，程序见附录四。5.3.3 结果设一个转弯点时，使W最小的转弯点坐标为（6，4.57），=14.6989；设两个转弯点时，使W最小的转弯点坐标为（3.62,7）和（7,3.62），=14.63。所以最优方案为：设立两个转弯点，其坐标分别是（3.62,7）和（7,3.62）。5.4至多只能有2个转弯点但转弯点可以建在所示区域的任何位置。该问中，转弯点坐标都为实数，在问题二的基础上只需要改变x，y的步长，比较步长0.1和0.01

17、，分析结果为步长是0.01时所花费用最省，即两个转弯点的坐标为(3.58,7.32),（7.32,3.58）时，建设费用为14.54百万元。5.5 单位建设费用连续变化5.5.1缩小转弯点所在区间以AB所在直线为x轴，AB的中垂线为y轴建立平面直角坐标系。以点A、B焦点，任意画一椭圆，如图7：DC图7两圆的半径差为dr，当dr足够小时，我们可将区域内的单位造价视为均匀的，设三个区域内的造价分别为，由条可知，是P沿椭圆逆时针转过某一微小弧度所对应位置, C,D分别是B与圆相交的两个点，分别计算路线A-P-B和路线A-B所对应的总造价：+)+B)= P+PB)= 同理可证得：以此类推可知将转弯点设

18、在y轴上可使建设费用最省。在如图8所示的坐标系下，转弯点在直线y =x上Py = x图8 转弯点的位置5.5.2 建立模型第一步：在线段上取极小的一段dS，此时，其建设费用可看作是均匀的，设此时 t = （1）第二步：对线段上的任意一点（x , y），设其参数方程为：且令x = x( z ) =z ;第三步： 因为x = x( z ) =z ，所以是公路所在直线的斜率，用k 表示，所以； （2）第四步：根据直线两点式方程：，得到直线AP、PB的直线方程：AP： PB：由于点P在直线y = x上，所以：AP： （3） PB： （4）第五步：对x积分，得到W的表达式： （5）将（1）-（4）代入（

19、5）得： （6）所以，该问题转化求函数式（6）的最小值问题5.2.3 模型求解5.2.3.1 缩小转弯点的范围单位建设费用的分布如图9所示：图 9如图8和图9，（4,4）处单位建设费用最高，以直线AB为对称轴，上方区域的单位建设费用要低于其下方对应区域的单位建设费用。所以，转弯点应选在直线y=x上且位于直线AB的上方，即m>4，可缩短程序运行的时间。利用Matlab软件编程，以0.01为步长，解出W在区间4,8.99上的最小值。程序见附录五。5.2.3.2结果当m循环132次即m=4+1.32=5.32时，W最小，Wmin=14.707百万元。所以，将转弯点设在（5.32,5.32）处，

20、可使建设费用最少，为最优方案。六、 模型的推广与改进方向1、 函数化思想渗透于生活的各个方面，然而枚举法在个体数量不多的情况下不失为一个很好的计算方法，而且计算结果可靠性高。2、 根据题目要求，分析出合适区域，在不影响最优方案的选择情况下适当缩短步长，以减少程序中不必要的循环计算进而缩短运算时间。七、 模型的优缺点1、 模型的优点（1）模型运用函数化思想建模，使得解题过程更容易；（2）由于模型运用了枚举法，从而使得建立出该模型后比较直观，易于理解且算法的正确性比较容易证明。 （3）利用 编程可以减少很多的代码量，特别是在数据处理方面，对于庞大的数据量计算更是方便，减少了模型的复杂程度。2、模型

21、的缺点当数据量庞大时，程序运行时间稍长，对计算机的性能要求过高。参考文献 1谢军占，吕常影. 亚当·斯密的公路经济理论J. 长安大学学报(社会科学版).第8卷 第3期. 2006年9月2徐秀华. Matlab软件在数学建模中的应用J. 科技与生活.2010年第13期3飞思科技产品研发中心. MATLAB6.5辅助优化计算与设计. 北京；电子工业出版社，20034 赵修坤 微积分第三版 国防工业出版社 2012 年8月附录附录一： clear allclcq=;zuixiao=0;for x=1:1:8 for y=1:1:8 k=0; g=0; v=0; z=; w=; p=; l=

22、; t=0; r=0; for m=0:1:x z=z,m; end for n=9:-1:y d=(n-9)*x/(y-9); z=z,d; end z=unique(z); m=size(z,2); for i=1:1:m p(i)=(y-9)/x)*z(i)+9; end for i=2:1:m n=(z(i)-z(i-1)2+(p(i)-p(i-1)2)0.5; if (z(i)+z(i-1)/2>3 & (z(i)+z(i-1)/2<5 & (p(i)+p(i-1)/2>3 & (p(i)+p(i-1)/2<5 r=1.4; elsei

23、f (z(i)+z(i-1)/2>2 & (z(i)+z(i-1)/2<6 & (p(i)+p(i-1)/2>2 & (p(i)+p(i-1)/2<6 r=1.3; elseif (z(i)+z(i-1)/2>1 & (z(i)+z(i-1)/2<7 & (p(i)+p(i-1)/2>1 & (p(i)+p(i-1)/2<7 r=1.2; elseif (z(i)+z(i-1)/2>0 & (z(i)+z(i-1)/2<8 & (p(i)+p(i-1)/2>0 &a

24、mp; (p(i)+p(i-1)/2<8 r=1.1; else r=1; end v=v+n*r; end for s=y:-1:0 w=w,s; end for d=x:1:9 c=(d-9)*y/(x-9); w=w,c; end w=unique(w); n=size(w,2); for i=1:1:n l(i)=w(i)*(x-9)/y+9; end for i=2:1:n u=(l(i)-l(i-1)2+(w(i)-w(i-1)2)0.5; if (l(i)+l(i-1)/2>3 & (l(i)+l(i-1)/2<5 & (w(i)+w(i-1)/

25、2>3 & (w(i)+w(i-1)/2<5 t=1.4; elseif (l(i)+l(i-1)/2>2 & (l(i)+l(i-1)/2<6 & (w(i)+w(i-1)/2>2 & (w(i)+w(i-1)/2<6 t=1.3; elseif (l(i)+l(i-1)/2>1 & (l(i)+l(i-1)/2<7 & (w(i)+w(i-1)/2>1 & (w(i)+w(i-1)/2<7 t=1.2; elseif (l(i)+l(i-1)/2>0 & (l(

26、i)+l(i-1)/2<8 & (w(i)+w(i-1)/2>0 & (w(i)+w(i-1)/2<8 t=1.1; else t=1; end g=g+t*u; end k=g+v; q=round(q,k.*10000)./10000; q endendzsb=min(q)col=find(q=zsb);b=ceil(col/8)c=(mod(col,8) 附录二： clear allclco=;for x1=1:1:8 for x2=1:1:8 for y1=1:1:8 for y2=1:1:8 if x1<x2 & y1>y2 &a

27、mp; x1+y1>=9 & x2+y2>=9 v=0; l=0; t=0; z=;z11=;z12=;z21=;z22=;z31=;z32=; w=;w11=;w12=;w21=;w22=;w31=;w32=; q=; k1=(y1-9)/x1; k2=(y2-y1)/(x2-x1); k3=y2/(x2-9); for e=y1:1:9 f=(e-9)/k1; z11=z11,f; %将第一段直线y取整数对应的x装入矩阵z1 w11=w11,e; end for e=0:1:x1 f=e*k1+9; z12=z12,e; w12=w12,f; end for e=y2:

28、1:y1 f=(e-y1)/k2+x1; z21=z21,f ; %将第二段直线y取整数对应的x装入矩阵z2 w21=w21,e; end for e=x1:1:x2 f=(e-x1)*k2+y1; z22=z22,e; w22=w22,f; end for e=0:1:y2 f=e/k3+9; z31=z31,f; %将第三段直线y取整数对应的x装入矩阵z3 w31=w31,e; end for e=x2:1:9 f=(e-9)*k3; z32=z32,e; w32=w32,f; end z=unique(sort(z11,z12,z21,z22,z31,z32); w=fliplr(uni

29、que(sort(w11,w12,w21,w22,w31,w32); n=size(z,2); for e=1:1:(n-1) r1=(z(e)+z(e+1)/2; r2=(w(e)+w(e+1)/2; if r1>3 & r1<5 & r2>3 & r2<5 t=1.4; elseif r1>2 & r1<6 & r2>2 & r2<6 t=1.3; elseif r1>1 & r1<7 & r2>1 & r2<7 t=1.2; elseif r1&

30、gt;0 & r1<8 & r2>0 & r2<8 t=1.1; else t=1; end l=(z(e+1)-z(e)2+(w(e+1)-w(e)2)0.5; v=l*t; q=q,v; end o=o;sum(q),x1,y1,x2,y2; end end end endendb=o(find(o=min(o(:,1),:)附录三： clear allclco=;b=0;for x1=0.01:0.01:8.99for x2=0.01:0.01:8.99 for y1=0.01:0.01:8.99 for y2=0.01:0.01:8.99 if

31、 mod(x1*10,10)=0 | mod(y1*10,10)=0 if mod(x2*10,10)=0 | mod(y2*10,10)=0 if x1<x2 & y1>y2 & x1+y1>=9 & x2+y2>=9 v=0; l=0; t=0; z=;z11=;z12=;z21=;z22=;z31=;z32=; z41=;z42=; w=;w11=;w12=;w21=;w22=;w31=;w32=;w41=;w42=; q=; s=0; k1=(y1-9)/x1; k2=(y2-y1)/(x2-x1); k3=y2/(x2-9); if m

32、od(y1*10,10)=0 for e=y1:1:9 f=(e-9)/k1; z11=z11,f; w11=w11,e; end else for e=fix(y1)+1:1:9 f=(e-9)/k1; z11=z11,f; w11=w11,e; end end for e=0:1:fix(x1) f=e*k1+9; z12=z12,e; w12=w12,f; end if mod(y1*10,10)=0 for e=fix(y2):1:y1 f=(e-y1)/k2+x1; z21=z21,f ; w21=w21,e; end else for e=fix(y2):1:fix(y1+1) f

33、=(e-y1)/k2+x1; z21=z21,f; w21=w21,e; end end for e=0:1:fix(x1) f=e*k2+9; z22=z22,e; w22=w22,f; end if mod(x1*10,10)=0 for e=x1:1:fix(x2) f=(e-x1)*k4+y1; z41=z41,e; w41=w41,f; end else for e=fix(x1)+1:1:fix(x2) f=(e-x1)*k4+y1; z41=z41,e; w41=w41,f; end end for e=0:1:fix(x1) f=e/k4+9; z42=z42,e; w42=w

34、42,f; end for e=0:1:fix(y2) f=e/k3+9; z31=z31,f; w31=w31,e; end if mod(x2*10,10)=0 for e=x2:1:9 f=(e-9)*k3; z32=z32,e; w32=w32,f; end else for e=fix(x2)+1:1:9 f=(e-9)*k3; z32=z32,e; w32=w32,f; end end z=unique(sort(z11,z12,z21,z22,z31,z32,z41,z42,x1,x2); w=fliplr(sort(w11,w12,w21,w22,w31,w32,w41,w42

35、,y1,y2); n=size(z,2); for e=1:1:(n-1) r1=(z(e)+z(e+1)/2; r2=(w(e)+w(e+1)/2; if r1>3 & r1<5 & r2>3 & r2<5 t=1.4; elseif r1>2 & r1<6 & r2>2 & r2<6 t=1.3; elseif r1>1 & r1<7 & r2>1 & r2<7 t=1.2; elseif r1>0 & r1<8 & r2>0 & r2<8 t=1.1; el