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

1、实用文档城区公路选址问题摘要城区公路选址是一项利民工程，为将该工程做得更好，建设部门在设计时应最大限度减少造价，从而节约成本，达到经费最省。为此目的，本文利用函数化思想建立模型求解并给出了五种不同要求下的最优方案。由题目所给数据（图1）可知，直线AB右上方单位区域中的单位建设费用小于AB左下的单位建设费用，且数据矩阵关于其次对角线对称。因而转弯点（无论一个或两个）均应位于AB右上区域。问题1要求至多1个转弯点且在网格点上，可分0个和1个转弯点两种情况。对于0个转弯点，即直线AB,通过几何方法得出建设费用为14.9907百万元。对于1个转弯点在网格点上的问题，我们利用函数化思想建立函数关系模型，

2、运用枚举法和权重法，并利用MATLAB编程直接输出最小费用。比较可知，恰有一个转弯点时较无转弯点为优。其方案是选择坐标为（5,6）或（6的点，建设费用最小为14.707百万元。对于问题2,我们在问题1解法的基础上，恰当修改MATLAB程序，使之适用于两个转弯点的选择，得出最优转弯点为（4,7）和（7,4）时，建设费用最小，为14.6241百万元。与问题1的结果比较可知，选择两个转弯点较一个转弯点更优。对于问题3,要求转弯点在网格线上，即至少有一个坐标为整数，分一个转弯点和两个转弯点两种情况。因为整数最优点是最接近理想最优点的整数点，我们可以在问题2解法的基础上，将循环语句中的步长1修改为0.0

3、1,运行结果说明，一个转弯点的最优选择是（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）最优建设

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

5、至多只能有1个转弯点，且转弯点只能建在图1所示的网格点上。(2)公路至多可以有2个转弯点，且转弯点只能建在图1所示的网格点上。(3)公路至多只能有2个转弯点，且转弯点只能建在图1所示的网格线上。(4)公路至多只能有2个转弯点，转弯点可以建在图1所示区域的任何位置。(5)如果各区域的单位建设费用为1.5-0.1j(x4)2(y4)2(百万元)，公路至多只能有1个转弯点，转弯点可以建在图1所示区域的任何位置。问题分析LiXKLILI1.1LIL11.2XL2ULIL1L2LIyL3L3*LI111.2LIL，UUL11.213L4L4XL2L111ISL3L31.3XL1ItL21.212LILI

6、XL1LILILILILILI11AB图1针对问题一：需要求出当公路至多只能有1个转弯点且转弯点只能建在图1所示的网格点上时所需的费用最省的目标值。首先，我们计算出没有转弯点时花费为14.9907百万元。对于有一个转弯点的，我们利用函数化建模思想将W与、0的关系用数学方程式表达出来，接着利用MATLAB编程将函数关系式进行运算，使用枚举法得出所有可能的转弯点的值，最后通过查找语句找出所得数据中的最小值，在与没有转弯点的花费比较，较小的即为可用的最优方案。针对问题二：需要求出当公路至多可以有2个转弯点且转弯点只能建在图1所示的网格点上时所需的费用最省的目标值。在问题1的基础上，依旧利用函数化建模

7、思想，经过分析，将MATLAB程序中的一个变量增加为两个，通过枚举法，即可得出使得W最小的两个坐标值。针对问题三：需要求出当公路至多只能有2个转弯点且转弯点只能建在图1所示的网格线上时所需的费用最省的目标值，坐标点至少有一个为小数，在问题二的基础上设定x或y其一必为小数，即步长改为0.01,思想同二。针对问题四：需要求出当公路至多只能有2个转弯点但转弯点可以建在图1所示区域的任何位置时所需的费用最省的目标值。此时，坐标点为0-9之间的任意实数，有两种情况：一种为有一个转弯点，另一种为有两个转弯点。在问题一、二的基础上，针对第一种情况，只需将第一问的程序中的步长改为0.01;针对第二种情况，只需

8、将第二问程序中的步长改为0.01,通过比较两种情况下的值，可得出最优方案。针对问题五：如果各区域的单位建设费用为1.5-0.1/(x4)2(y4)2(百万元)，公路至多只能有1个转弯点，转弯点可以建在图1所示区域的任何位置。因为每个点的单位建设费用不同，但又是连续变化的，故我们可以利用微积分法思想，假设在极小的一段路程内建设费用是相同的，由此建立一个积分方程，通过MATLAB编码找出花费最小值，从而得出最优方案。三、模型的假设1、区域内所有位置的路面状况均相同2、区域内所有位置的路面条件均相同3、不考虑软件计算带来的极小误差4、地理环境对路线的设计没有影响四、符号说明(1) P(m,n)：单转

9、弯点的坐标；(2) Pi(m,n)：双转弯点中靠近A点的坐标；(3) Pz(a,b):双转弯点中靠近B点的坐标；(4) W:总建设费用；(5) 6：单位区域的公路长度；(6) ti：第i条路段单位建设费用；(7) Vi:第i条路段费用;(8)4：第i条路段与网格线交点的横坐标矩阵;(9) wi：第i条路段与网格线交点的纵坐标矩阵；五、模型的建立与求解9.1 至多只能有1个转弯点且转弯点只能建在网格点上。9.1.1 建立模型(1)没有转弯点时：W=/22(11.11.21.31.4)14.9907(百万元)(2)有一个转弯点时：利用函数化思想，建立W与与、ti的函数关系：第1步：在网格点上任取一

10、点P(x,y)(图1),根据直线两点式方程:(yy)(x2X1)(y2y1)(xx1)，可得直线AP、PB的方程为AP:(yn)(m)(9n)xPB:(yn)(9m)(x9)nL1X口LILILI1.1LIL1XLiyPU.l14L：L3LlJ14L1L11.4XL31.111L1L3L4L4XLil11L：L314LSL3XpL111L1Li12LSuXVLI11L11.1LLU11LI图1第2步：由直线方程可求得AP与x=i(i=0、1、2xp)和y=j(j=yp8、9)的所有交点，并按x从小到大的排序，(Zi,Wi)(i=1,2,3,4)取(Zi,Wi)和(Zi1,Wi1)则可以根据它们

11、的中点得到这两点的路段需要的加权权重，即:1.4.A1(x,y)|3x5,3y51.3A2(x,y)|2x6,2y61At1.2A3(x,y)|1x7,1y7/(4队)1.1A4(x,y)|0x8,01.A5(x,y)|0x9,8y8/(A3UA2UA1)y9.或.8x9,0y9因此对于Si，(ZiZi1)2(WiWi1)2有ViSit,累加可得AP段公路的费用。PB段公路的费用同理可得。故此总费用的表达式为：Wvisit1.1.2 软件求解(程序见附录一)，流程图如图2：Y根据枚举法，利用Matlab软件求解图2求解W的流程图从MATLAB程序运行结果可以看出，使得W最小的点的坐标为（5,6

12、）和（6,5）,此时，Wmin=14.707百万元。因为14.707LlL4XLlLlLl1.1Ll14MXLlxlL，LJL)L3L：LSLlXLlllLlItllLlLlLlLlLl11LlLlLlLl所以，我们得到公路的大致走向，如图6所示:L1LI五LILILILI11LIVXLtLI1.1LIllLIXLILI1J14LI111.1X141.1LILILIL414LILI14LSL)111.1XX11J.211Li1!LtLIXLI1.1LILILILILILIY其坐标特点为：mb5.2.2建立模型第一步：根据两点的位置关系，在网格点上任取两点P1(m,n),P2(a,b),如图7。

13、根据直线两点式方程：(yyi)(x2xi)(y2y1)(xXi),得到直线APi,P1P2,P2B的方程:AR：(y9)m=(m-9)xP1P2:(y-n)(a-m)=(b-n)(x-m)P2B(y-b)(9-a)=-b(x-a)LIX4F1LILI11LILIVLILIVLILILILJXULILli14LILIKXLI1.1LI1.1LIL4XLILI11UUUL3LlLILILIuLIL!KdLILILI11LILILILl图7第二步：根据直线方程可求得直线AP,与x=i(i=0、1、2xpDy=j(j=yp8、9)的所有交点,并按x从小到大的排序,即：(Zi,Wi)(i=1,2,3,4

14、取(Zi,Wi)和(Zi1,Wi1)则可以根据它们的中点得到这两点的路段需要的加权权重，即：1.4.Ai1.3A2t1.2A3(x,y)|3x5,3(x,y)|2x6,2(x,y)|1x7,1y5y6/A1y7/(A2UA1)1.1A4(x,y)|0x8,01.A5(x,y)|0x9,8y8/(A3UA2UA1)y9.或.8x9,0y9第3步：对于SiJ(Zi41)2(Wiw)2有ms，累加彳4到AP段公路的费用,同理得到P1P2,P2B段公路的费用。故整条公路的总费用表达式为:Wvist5.2.2 软件求解5.2.2.1 当有两个转弯点时编写Matlab编程，利用枚举法，得到所有可能得到的两

15、个转弯点的情况时所需要的总建设费用W,程序见附录二，分析流程图如图8:如四上分别在L刃区间上期直整数*W图8求两个转弯点在网格点上时的流程图经过分析，得出使得W最小的两点坐标为（4,7）和（7,4）,此时，Wmin=14,6241百万元。所以，将两转弯点分别设在坐标为(4,7)和(7,4)的网格点上时，能使建设费用最省，即为最优的方案。如图9:11X五LILI1.11.1LILtX11XLILI.lL112LIXLI1.111L1L3L4XLI1.11111LIL4L47UR；11414LL*UuxLILILILiLIL2LIxdLLLILILILILILILI图9两转弯点在网格点上时的最优方

16、案5.3 至多只能有2个转弯点且转弯点只能建网格线上。5.3.1 建立模型5.3.1.1 有两个转弯点在第二问的基础上第1步：根据两点的位置关系，在网格点上任取两点P1(m,n),P2(a,b),得到直线APi,P1P2,P2B的方程:AP1：(y9)m=(m-9)xP1P2:(y-n)(a-m)=(b-n)(x-m)P2B：(y-b)(9-a)=-b(x-a)第2步：在坐标满足条件的情况下，如果n为整数根据直线方程可求得直线AR与x=i(i=0、1、2Xp)fty=j(j=yp8、9)的所有交点，并按x从小到大的排序，即:(乙，w。(i=1,2,3,4取(Zi,Wi)和(Zi1,Wi1)则可

17、以根据它们的中点得到这两点的路段需要的加权权重，即：1.4.A11.3A2t1.2A3(x,y)|3x5,3(x,y)|2x6,2(x,y)|1x7,1y5y6/Ay7/(A2UA1)1.1A4(x,y)|0x8,01.A5(x,y)|0x9,8y8/(A3UA2UA1)y9.或.8x9,0y9若n为小数，则取n的整数部分再加1,重复上述步骤;如果m为整数,同样方法得到(Zi,w。，若m为小数，则取m的整数部分，然后计算得到(zi,wi)第3步：对于6J(Zi41)2(wiw)2有ms，累加彳4到APi段公路的费用,同理得到PiP2,P2B段公路的费用。故整条公路的总费用表达式为：Wvist5

18、.3.1.2 有一个转弯点与设立两个转弯点相比，只需在网格线上任取一个点P,思想和方法都与之相同5.3.2 软件求解5.3.2.1 有两个转弯点以第二问的程序为基础，将循环中的步长设为0.01,在m或n为整数且a或b为整数的条件下，寻找最优解。程序见附录三，流程图以AR为例显示了取整与求取线段与网格线交点的过程，其他步骤同第二问。如图11。图11两个转弯点下的部分流程图5.3.2.2 设一个转弯点编程思路与设两个转弯点的情况相同，程序见附录四。5.3.3 结果设一个转弯点时，使W最小的转弯点坐标为（6,4.57）,Wmin=14.6989;设两个转弯点时，使W最小的转弯点坐标为（3.62,7）

19、和（7,3.62）,Wmin=14.63。所以最优方案为：设立两个*$弯点，其坐标分别是（3.62,7）和（7,3.62）。5.4 至多只能有2个转弯点但转弯点可以建在所示区域的任何位置。该问中，转弯点坐标都为实数，在问题二的基础上只需要改变x,y的步长，比较步长0.1和0.01,分析结果为步长是0.01时所花费用最省，即两个转弯点的坐标为（3.58,7.32）,（7.32,3.58）时，建设费用为14.54百万元。5.5 单位建设费用连续变化5.5.1 缩小转弯点所在区间以AB所在直线为x轴，AB的中垂线为y轴建立平面直角坐标系。以点A、B焦点,任意画一椭圆，如图7:图7两圆的半径差为dr,

20、当dr足够小时，我们可将区域内的单位造价视为均匀的，设三个区域内的造价分别为，t2,t3,由条可知，tit2t3,P1是P沿椭圆逆时针转过某一微小弧度所对应位置,C,D分别是PiB与圆相交的两个点，分别计算路线A-P-B和路线A-Pi-B所对应的总造价：Wapbm3(AP+PB)Warbm3(APi+PiC+DB)+m2CDWaPiBm3(APi+PiB尸m3(Ap+PB尸Wapb同理可证得：Wa?bWa.b以此类推可知将转弯点设在y轴上可使建设费用最省。在如图8所示的坐标系下,转弯点在直线y=x5.5.2建立模型第一步：在线段上取极小的一段dS,此时，其建设费用可看作是均匀的，设此时t=1.

21、5-0.，(x4)2(y4)2(1)第二步：对线段上的任意一点(x,y),设其参数方程为：xx(z)yy(z)且令x=x(z)=z;第三步：dSx(z)2y(z)2dz因为x=x(z)=z,所以dS小y(z)2dzy(z)是公路所在直线的斜率，用k表示，所以dS出k2dx；(2)第四步：根据直线两点式方程：(yyjaxi)(y2y1)(xxj,得到直线AP、PB的直线方程:ap：yPB：y99nm9由于点P在直线y=x上，所以:AP:y(3)PB：ym(x9)(4)第五步：对x积分，得到W的表达式:mW0ZApdS9mzPBdS(5)将（1）-（4）代入（5）得:2zm92m9.2.(6)。5

22、O.jx4)(mx5),.1(m)dx2/m9m八2、/m(1-5；(x4)(m9xm94).1(m9)dx所以，该问题转化求函数式（6）的最小值问题5.2.3模型求解5.2.3.1 缩小转弯点的范围单位建设费用的分布如图9所示：图9如图8和图9,（4,4）处单位建设费用最高，以直线AB为对称轴，上方区域的单位建设费用要低于其下方对应区域的单位建设费用。所以，转弯点应选在直线尸x上且位于直线AB的上方，即m4,可缩短程序运行的时间。利用Matlab软件编程，以0.01为步长，解出W在区间4,8.99上的最小值。程序见附录五5.2.3.2 结果当m循环132次即m=4+1.32=5.32时，W最

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

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

25、;r=0;form=0:1:xz=z,m;endforn=9:-1:yd=(n-9)*x/(y-9);z=z,d;endz=unique(z);m=size(z,2);fori=1:1:mp(i)=(y-9)/x)*z(i)+9;endfori=2:1:mn=(z(i)-z(i-1)A2+(p(i)-p(i-1)A2)A0.5;if亿(i)+z(i-1)/23&亿(i)+z(i-1)/23&(p(i)+p(i-1)/22&亿(i)+z(i-1)/22&(p(i)+p(i-1)/21&亿(i)+z(i-1)/21&(p(i)+p(i-1)/20&亿(i)+z(i-1)/20&(p(i)+p(i-

26、1)/23&(l(i)+l(i-1)/23&(w(i)+w(i-1)/22&(l(i)+l(i-1)/22&(w(i)+w(i-1)/21&(l(i)+l(i-1)/21&(w(i)+w(i-1)/20&(l(i)+l(i-1)/20&(w(i)+w(i-1)/28t=1.1;elset=1;endg=g+t*u;endk=g+v;q=round(q,k.*10000)./10000;qendendzsb=min(q)col=find(q=zsb);b=ceil(col/8)c=(mod(col,8)附录二：clearallclco=;forx1=1:1:8forx2=1:1:8fory1=1

27、:1:8fory2=1:1:8ifx1y2&x1+y1=9&x2+y2=9v=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);fore=y1:1:9f=(e-9)/k1;z11=z11,f;%将第一段直线y取整数又t应的x装入!阵z1w11=w11,e;endfore=0:1:x1f=e*k1+9;z12=z12,e;w12=w12,f;endfore=y2:1:y1f=(e-y1)/k2+x1;

28、z21=z21,f;%将第二段直线y取整数又t应的x装入矩阵z2w21=w21,e;endfore=x1:1:x2f=(e-x1)*k2+y1;z22=z22,e;w22=w22,f;endfore=0:1:y2f=e/k3+9;z31=z31,f;%将第三段直线y取整数又t应的x装入矩阵z3w31=w31,e;endfore=x2:1:9f=(e-9)*k3;z32=z32,e;w32=w32,f;endz=unique(sort(z11,z12,z21,z22,z31,z32);w=fliplr(unique(sort(w11,w12,w21,w22,w31,w32);n=size(z,2

29、);fore=1:1:(n-1)r1=(z(e)+z(e+1)/2;r2=(w(e)+w(e+1)/2;ifr13&r13&r22&r12&r21&r11&r20&r10&r28t=1.1;elset=1;endl=(z(e+1)-z(e)A2+(w(e+1)-w(e)A2)A0.5;v=l*t;q=q,v;endo=o;sum(q),x1,y1,x2,y2;endendendendendb=o(find(o=min(o(:,1),:)附录三：clearallclco=;b=0;forx1=0.01:0.01:8.99forx2=0.01:0.01:8.99fory1=0.01:0.01:8.

30、99fory2=0.01:0.01:8.99ifmod(x1*10,10)=0|mod(y1*10,10)=0ifmod(x2*10,10)=0|mod(y2*10,10)=0ifx1y2&x1+y1=9&x2+y2=9v=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);ifmod(y1*10,10)=0fore=y1:1:9f=(e-9)/k1;z11=z11,f;w11=w11,e;endelsefore=fix(y1)+1:1:9f=(e-9)/k1;z11=z11,f;w11=w11,e;endendfore=0:1:fix(x1)f=e*k1+9;z12=z12,e;w12=w12,f;endifmod(y1*10,10)=0fore=fix(y2):1:y1f=(e-y1)/k2+x1;z21=z21,f;w21=w21,e;endelsefore=fix(y2):1:fix(y1+1)f=(e-y1)/k2+x1;z21=z21,f;w21=