下载

1下载券

加入VIP
  • 专属下载券
  • 上传内容扩展
  • 资料优先审核
  • 免费资料无限下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 数学建模论文

数学建模论文.doc

数学建模论文

kaif
2011-07-17 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《数学建模论文doc》,可适用于高等教育领域

所得税缴费点选址问题作者:李鸣郭桂江周鹏程摘要近年来图论在生产生活和科学技术研究中的作用日趋显著特别是大型电子计算机的出现和计算机科学的迅猛发展为图论及其算法的解决提供了强大的计算和证明的手段。本文的主要内容是结合图论的相关知识对居民所得税缴费点的选址提出合理的标准并进行合理优化的选址。通过建立图的邻接矩阵将原始数据存入计算机并借助MatlAB软件编写求任意两点间最短路径的Floyd算法程序实现最短路径的求解。通过对原始数据的分析和不断修改计算本文从缴费点周围的居民数量和居民距离缴费点的距离等方面分析了各种方案的预测数据并得出了一些有社会价值的结论。如果按照最优化方案即选用,,,为缴费点得出最短路径为(百米*千人)。按增加一个点的方案则应增加位置为缴费点算出最短路径为(百米*千人)。如果想在原来基础上迁移一个点则应撤掉号点的缴费点在号点建缴费点。本次设计很好地将图论应用于实际生活。关键词:图论Floyd算法最短路径邻接矩阵MatlAB求解、​ 问题重述所得税管理部门计划对某个区域中的缴费点进行重新设计。该区域原来有各缴费点分别位于图的,,,位置。图是该区域的一个实际简化其中连接线表示有道路相通连接线上数字表示两地距离(单位百米)圆圈内数字是位置序号。各点代表的居民数见表。表各点居民数(单位千人)位置人数位置人数请你解决如下问题:()给出合理选址的标准。()根据你的标准分析原来的选址是否合理?()如果考虑迁移个缴费点应该迁移那个缴费点迁到那里?()如果在原方案中增加一个新的缴费点该点最好设在那里?、​ 模型假设​ 假设同一个居民点的所有居民到到同一个缴费点缴费。​ 假设每个居民都到离自己最近的点缴费。​ 假设缴费点的接待能力无限大过多的人不影响缴费点处的工作效率和工作质量​ 假设缴费点每天每时每刻都可以交费。​ 假设每条通往缴费点的路在任何时刻都畅通无阻。三、符号说明D两个缴费点(i,j)之间的距离a题目中给定图的邻接矩阵path两个缴费点(i,j)之间的路线floyd佛洛依德算法B通过floyd算法求得的最短路径矩阵Shortjourney最短路径Sum(i)最短路径长Position所选择的最佳点的位置an(i)各个方案的距离值ACPQWV表示各个不同的矩阵四、模型的建立与求解问题一:我们可以选择如下选址标准:所选的四个点能够使所有居民到达离自身最近的缴税点的总路程最小路程是指该点的人数乘以该点到缴税点的距离。如:如①到②距离应为:(居民数)*(距离)=(千人*百米)问题二:根据该选址标准可将本问题转化为图论中的最短路径问题可以通过Floyd算法编程实现求解采用的软件是MatlABRa​ 数据存储因为所给图为无向带权图所以要根据图论和数据结构的知识转化为邻接矩阵来储存数据并将数据输入MatlAB中。所得邻接矩阵如下:a=infinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinf​ 数据分析根据上述矩阵采用floyd算法编制求解最短路径的程序在MatlAB中运行。算法程序如下:functionD,path=floydz(a)定义函数n=size(a,)D=apath=zeros(n,n)设置D和Path的初值fori=:nforj=:nifD(i,j)~=infpath(i,j)=jj是i的后继点endendendfork=:n做n次迭代,每次迭代均更新D(i,j)和path(i,j)fori=:nforj=:nifD(i,k)D(k,j)<D(i,j)D(i,j)=D(i,k)D(k,j)修改长度path(i,j)=path(i,k)修改路径endendendend在MatlAB中运行得出最短路径矩阵B(详细程序见附录):通过进一步编程带入数据求得最佳缴费点:(详细程序见附录)>>position(位置)position=>>>>an(最短路程)an=>>根据以上分析和计算得出如下表格:原始方案最优方案缴费点,,,,,,最短路程(百米*千人)所以经过以上的分析计算得出:根据我们制定的选址标准原方案不合理。问题三:如果要在原始位置的基础上迁移一个缴费点首先考虑迁出的点:分别是迁移号点或号点或号点或号点。再在每一种迁出情况下考虑迁入的点共有种可能(这里为方便程序编制与求解把本身点也包含在内但不影响结果)通过程序计算求得每一种情况下的最短路径再找出个最短路径中最小的即选择该方案。计算机求解的结果比较(详细程序见附录):迁出点最佳迁入点新位置路程(百米*千人)经过分析比较得出:如果要在原始的基础上迁移一个点最好迁移号点到号点位置组成新的缴费点此时的路程最短,为(百米*千人)。问题四:有了前面的分析解决第四个问题的方法类似。因为此时四个点已经确定只要用穷举法计算出增加每一个点情况下的最短路程再从中找出使得总路程最短的一种方案。为了编程和计算的方便还是考虑种情况与自身重复的情况并不影响最终结果因为增加自身(还是原来的个点)的情况下总里程一定比增加别的点大而我们最终要得到的是最小值。通过编程在MatlAB中求解得出(详细程序见附录):>>anan=>>>>positionposition=>>于是得出当增加的点为时居民行走的总路程最短路程为(百米*千人)。五、模型的评价与推广通过对题目中四个问题的分析我们建立了以图论为理论基础的数学模型并且借助于数学软件MatlAB编制基于Floyd算法的程序对模型进行求解找出了最优化的选址方案能够很好地指导缴费点的建设。但是在这个模型中我们忽略了每个居民的个体差异认为他们的选择是一致的其实他们在没有统一规定或者指导的情况下是随意到任意缴费点缴费的。我们也忽略了每个点之间的交通情况每个缴费点的运营能力等等在实际生活中缴费点的建设和选择都应该综合考虑这一系列的因素。本文中的方法还可以解决其它诸如求最短路径的问题。六、参考文献【】李海涛邓樱MATLAB程序设计教程北京:高等教育出版社【】张先迪李正良图论及其应用北京:高等教育出版社【】严蔚敏吴伟明数据结构(C语言版)北京:清华大学出版社【】姜启源谢金星数学建模案例选集北京:高等教育出版社【】屈婉玲耿素云张立昂离散数学北京:高等教育出版社七、附录附一:MatlAB实现floyd算法程序清单:functionD,path=floydz(a)n=size(a,)D=apath=zeros(n,n)fori=:nforj=:nifD(i,j)~=infpath(i,j)=jendendendfork=:nfori=:nforj=:nifD(i,k)D(k,j)<D(i,j)D(i,j)=D(i,k)D(k,j)path(i,j)=path(i,k)endendendend附二:调用floyd算法求最短路径的MatlAB源程序:a=infinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfD,path=floydz(a)B=D附三:求原始选址方案的最短路程程序:A=combntns(:,)People=B=C=B(:,)C=B(:,)C=B(:,)C=B(:,)M=CCCCF=sort(M,)Shortjourney=F(:,)Sum=People*Shortjourney附四:求四个点的最优方案的MatlAB源程序:clearallA=combntns(:,)fori=:nchoosek(,)A=A(i,:)A=A(,)A=A(,)A=A(,)A=A(,)People=B=为节约篇幅省略数据同上!B=B(:,A)B=B(:,A)B=B(:,A)B=B(:,A)C=BBBBD=sort(C,)Shortjourney=D(:,)Sum(i)=People*ShortjourneyendE=reshape(Sum,nchoosek(,),)minposition=find(E==min(E))an=min(E)A=combntns(:,)position=A(minposition,:)附五:迁移一个点情况下最优方案求解程序:clearallP=combntns(:,)fori=:nchoosek(,)P=P(i,:)P=P=P=P=P(,)People=B=为节约篇幅省略数据同上!V=B(:,P)V=B(:,P)V=B(:,P)V=B(:,P)C=VVVVD=sort(C,)Shortjourney=D(:,)Sum(i)=People*ShortjourneyendE=reshape(Sum,nchoosek(,),)minposition=find(E==min(E))an=min(E)P=combntns(:,)position=P(minposition,:)附六:求增加一个点的最优方案MatlAB源程序:clearallW=combntns(:,)fori=:nchoosek(,)X=W(i,:)X=X=X=X=X=X(,)People=B=为节约篇幅省略数据同上!Y=B(:,X)Y=B(:,X)Y=B(:,X)Y=B(:,X)Y=B(:,X)Q=YYYYYD=sort(Q,)Shortjourney=D(:,)Sum(i)=People*ShortjourneyendE=reshape(Sum,nchoosek(,),)minposition=find(E==min(E))an=min(E)W=combntns(:,)position=W(minposition,:)

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/18

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利