数学建模论文

 时间:2011-07-17 13:21:59 贡献者:zpcandzhj

导读:南京财经大学 Nanjing University of Finance & Economics所得税缴费点选址问题作者:李鸣 郭桂江 周鹏程摘要近年来,图论在生产生活和科学技术研究中的作用日趋显著,特别是大型电 子计算机的出

数学建模论文66014new.doc
数学建模论文66014new.doc

南京财经大学 Nanjing University of Finance & Economics所得税缴费点选址问题作者:李鸣 郭桂江 周鹏程摘要近年来,图论在生产生活和科学技术研究中的作用日趋显著,特别是大型电 子计算机的出现和计算机科学的迅猛发展, 为图论及其算法的解决提供了强大的 计算和证明的手段。

本文的主要内容是结合图论的相关知识对居民所得税缴费点 的选址提出合理的标准,并进行合理优化的选址。

通过建立图的邻接矩阵将原始 数据存入计算机,并借助 MatlAB 软件编写求任意两点间最短路径的 Floyd 算法 程序实现最短路径的求解。

通过对原始数据的分析和不断修改计算, 本文从缴费点周围的居民数量和居 民距离缴费点的距离等方面分析了各种方案的预测数据并得出了一些有社会价 值的结论。

如果按照最优化方案,即选用 2,4,7,12 为缴费点,得出最短路径为 10850(百米*千人) 。

按增加一个点的方案则应增加 5 位置为缴费点,算出最短 路径为 10724(百米*千人) 。

如果想在原来基础上迁移一个点,则应撤掉 15 号 点的缴费点,在 4 号点建缴费点。

本次设计很好地将图论应用于实际生活。

关键词: 关键词:图论Floyd 算法最短路径邻接矩阵MatlAB 求解一、 问题重述所得税管理部门计划对某个区域中的缴费点进行重新设计。

该区域原来有 4 各缴费点,分别位于图 1 的 2,6,13,15 位置。

图 1 是该区域的一个实际简化, 其中连接线表示有道路相通,连接线上数字表示两地距离(单位百米) ,圆圈内 数字是位置序号。

1

南京财经大学 Nanjing University of Finance & Economics各点代表的居民数见表 1。

表 1 各点居民数(单位千人)位置 人数 位置 人数1 50 10 302 45 11 303 45 12 364 48 13 255 40 14 206 40 15 157 36 16 208 32 17 109 32 18 10请你解决如下问题: (1)给出合理选址的标准。

(2)根据你的标准,分析原来的选址是否合理? (3)如果考虑迁移 1 个缴费点,应该迁移那个缴费点,迁到那里? (4)如果在原方案中增加一个新的缴费点,该点最好设在那里?2

南京财经大学 Nanjing University of Finance & Economics二、 模型假设1. 假设同一个居民点的所有居民到到同一个缴费点缴费。

2. 假设每个居民都到离自己最近的点缴费。

3. 假设缴费点的接待能力无限大,过多的人不影响缴费点处的工作效率和 工作质量 4. 假设缴费点每天每时每刻都可以交费。

5. 假设每条通往缴费点的路在任何时刻都畅通无阻。

三、符号说明 符号说明D a—— ——两个缴费点(i,j)之间的距离 题目中给定图的邻接矩阵 两个缴费点(i,j)之间的路线佛洛依德算法path ——floyd —— B——通过 floyd 算法求得的最短路径矩阵Shortjourney 最短路径 Sum(i) ——最短路径长 所选择的最佳点的位置 各个方案的距离值Position— an(i) ——A C P Q W V 表示各个不同的矩阵3

南京财经大学 Nanjing University of Finance & Economics四、模型的建立与求解问题一 问题一: 我们可以选择如下选址标准: 所选的四个点能够使所有居民到达离自身 最近的缴税点的总路程最小,路程是指该点的人数乘以该点到缴税点的距 离。

如:如①到②距离应为: ① ② (居民数 50 )*(距离 20)=1000(千人*百米),问题二: 问题二: 根据该选址标准,可将本问题转化为图论中的最短路径问题,可以通过 Floyd 算法编程实现求解,采用的软件是 MatlABR2007a.数据存储 1. 数据存储因为所给图为无向带权图,所以要根据图论和数据结构的知识转化为邻接 矩阵,来储存数据,并将数据输入 MatlAB 中。

所得邻接矩阵如下:a= [ 0 20 18 18 15 20 0 26 18 26 0 18 15 inf inf inf inf inf inf inf inf inf inf inf inf inf; inf inf inf 30 28 30 30 inf inf inf inf inf inf; inf 26 inf inf inf inf; inf inf;inf 28 20 0inf inf inf inf inf inf inf 20 18 0 18 50inf 20 28inf inf inf inf inf inf inf inf 18 32inf 18inf 38inf inf inf inf inf inf inf inf inf inf;inf inf inf 18 inf inf inf 50inf 0 38inf inf inf inf inf inf inf inf inf inf inf 36; inf inf inf inf inf inf inf inf inf inf 34; 36 0 inf inf inf inf inf inf inf inf inf; inf inf inf inf inf inf inf inf inf; 30 0 inf inf inf inf inf inf inf; 26 0 28 32 28 0 inf inf inf inf inf; inf inf inf inf inf; 32 0 inf inf inf inf; 34 inf inf inf;inf 0inf inf inf inf 32 inf 30 inf 28 inf 30 inf 30inf inf 0inf inf inf inf inf 36inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf 30 20inf inf inf inf inf inf inf 26inf inf inf inf inf inf inf inf inf inf 32 inf inf 26inf inf inf inf inf inf inf inf inf 324

南京财经大学 Nanjing University of Finance & Economicsinf inf inf inf inf inf inf inf inf inf inf inf inf 34 inf inf inf 18024 0 3036 30 0inf; inf; 32; 0inf inf inf inf inf inf inf inf inf inf 24inf inf inf inf inf inf inf inf inf inf inf inf inf inf 36 inf inf inf inf inf 36 34inf inf inf inf inf inf inf inf inf 32]数据分析 2. 数据分析 根据上述矩阵采用floyd算法编制求解最短路径的程序,在MatlAB中运行 。

算法程序如下:function [D,path]=floydz(a) n=size(a,1); D=a;path=zeros(n,n);定义函数设置 D 和 Path 的初值fori=1:n for j=1:n if D(i,j)~=inf path(i,j)=j; end end j 是i 的后继点endfor k=1:n for i=1:n for j=1:n做 n 次迭代, 每次迭代均更新 D(i,j) 和 path(i,j)if D(i,k)+D(k,j)

南京财经大学 Nanjing University of Finance & Economicsend end end end在 MatlAB 中运行得出最短路径矩阵 B(详细程序见附录) :通过进一步编程带入数据求得最佳缴费点:(详细程序见附录)>> position(位置) position = 2 >> 4 7 12>> an(最短路程) an = 10850>>6

南京财经大学 Nanjing University of Finance & Economics根据以上分析和计算得出如下表格:原始方案 缴费点 最短路程 (百米*千人) 2,6,13,15 13998最优方案 2,4,7,12 10850所以经过以上的分析计算得出:根据我们制定的选址标准原方案不合理。

问题三: 问题三: 如果要在原始位置的基础上迁移一个缴费点,首先考虑迁出的点:分别 是迁移 2 号点或 6 号点或 13 号点或 15 号点。

再在每一种迁出情况下考虑迁 入的点,共有 18 种可能(这里为方便程序编制与求解把本身点也包含在内, 但不影响结果) ,通过程序计算求得每一种情况下的最短路径,再找出 4 个 最短路径中最小的,即选择该方案。

计算机求解的结果比较(详细程序见附录) : 迁出点 最佳迁入点 新位置 路程(百米*千人) 2 1 1 6 13 15 13434 6 4 2 4 13 15 12248 13 5 2 5 6 15 12286 15 4 2 4 6 13 12098经过分析比较得出:如果要在原始的基础上迁移一个点,最好迁移 15 号点到 4 号点位置,组成新的缴费点 2 12098(百米*千人)。

4 6 13,此时的路程最短,为7

南京财经大学 Nanjing University of Finance & Economics问题四: 问题四: 有了前面的分析,解决第四个问题的方法类似。

因为此时四个点已经确 定,只要用穷举法计算出增加每一个点情况下的最短路程,再从中找出使得 总路程最短的一种方案。

为了编程和计算的方便,还是考虑 18 种情况,与 自身重复的情况并不影响最终结果,因为增加自身(还是原来的 4 个点)的 情况下总里程一定比增加别的点大,而我们最终要得到的是最小值。

通过编程在 MatlAB 中求解得出(详细程序见附录) :>> an3 an3 = 10724 >> >> position3 position3 = 5 >>于是得出当增加的点为 5 时, 居民行走的总路程最短, 路程为 10724(百 米*千人)。

8

南京财经大学 Nanjing University of Finance & Economics五、模型的评价与推广通过对题目中四个问题的分析, 我们建立了以图论为理论基础的数学模 型,并且借助于数学软件 MatlAB 编制基于 Floyd 算法的程序对模型进行求 解,找出了最优化的选址方案,能够很好地指导缴费点的建设。

但是在这个 模型中我们忽略了每个居民的个体差异,认为他们的选择是一致的,其实他 们在没有统一规定或者指导的情况下是随意到任意缴费点缴费的。

我们也忽 略了每个点之间的交通情况,每个缴费点的运营能力等等,在实际生活中缴 费点的建设和选择都应该综合考虑这一系列的因素。

本文中的方法还可以解 决其它诸如求最短路径的问题。

六、参考文献【1】李海涛,邓樱,MATLAB 程序设计教程,北京:高等教育出版社,2002. 【2】张先迪,李正良,图论及其应用,北京:高等教育出版社,2005. 【3】严蔚敏,吴伟明,数据结构(C 语言版),北京:清华大学出版社,2007. 【4】姜启源,谢金星,数学建模案例选集,北京:高等教育出版社,2006. 【5】屈婉玲,耿素云,张立昂,离散数学,北京:高等教育出版社,2008.9

南京财经大学 Nanjing University of Finance & Economics七、附录附一:MatlAB 实现 floyd 算法程序清单:function [D,path]=floydz(a) n=size(a,1); D=a;path=zeros(n,n); for i=1:n for j=1:n if D(i,j)~=inf path(i,j)=j; end end endfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)

南京财经大学 Nanjing University of Finance & Economics附二:调用floyd算法求最短路径的MatlAB源程序:a=[ 0 20 18 18 15 20 0 26 18 26 0 18 15 inf inf inf inf inf inf inf inf inf inf inf inf inf; inf inf inf 30 28 30 30 inf inf inf inf inf inf; inf 26 inf inf inf inf; inf inf;inf 28 20 0inf inf inf inf inf inf inf 20 18 0 18 50inf 20 28inf inf inf inf inf inf inf inf 18 32inf 18inf 38inf inf inf inf inf inf inf inf inf inf;inf inf inf 18 inf inf inf 50inf 0 38inf inf inf inf inf inf inf inf inf inf inf 36; inf inf inf inf inf inf inf inf inf inf 34; 36 0 inf inf inf inf inf inf inf inf inf; inf inf inf inf inf inf inf inf inf; 30 0 inf inf inf inf inf inf inf; 26 0 28 32 28 0 inf inf inf inf inf; inf inf inf inf inf; 32 0 inf inf inf inf; 34 0 inf inf inf; 24 0 30 36 30 0 inf; inf; 32; 0inf 0inf inf inf inf 32 inf 30 inf 28 inf 30 inf 30inf inf 0inf inf inf inf inf 36inf inf inf inf inf inf inf 0 inf inf inf inf inf inf inf 30 20inf inf inf inf inf inf inf 26inf inf inf inf inf inf inf inf inf inf 32 inf inf 26inf inf inf inf inf inf inf inf inf 32inf inf inf inf inf inf inf inf inf inf inf inf inf 34 inf inf inf 18inf inf inf inf inf inf inf inf inf inf 24inf inf inf inf inf inf inf inf inf inf inf inf inf inf 36 inf inf inf inf inf 36 ] ; [D,path]= floydz (a); B=D; 34inf inf inf inf inf inf inf inf inf 3211

南京财经大学 Nanjing University of Finance & Economics附三:求原始选址方案的最短路程程序:A=combntns(1:18,4); People=[50 45 45 48 40 40 36 32 32 30 30 36 25 20 15 20 10 10]; B=[0 44 20 52 18 26 18 46 15 59 36 64 53 118 47 113 50 82 110 48 80 108 50 64 38 46 80 98 91 96 60 60 42 60 80 6020 36 0 56 26 38 38 18 28 36 56 36 66 92 60 92 30 86 28 84 30 84 30 5818 66 26 86 0 68 20 48 33 66 38 66 70 68 65 68 56 116 54 114 46 114 20 8818 72; 38 92; 20 74; 0 54; 18 72; 18 36; 50 66 50 98 6815365347504850386628566660302830305833387065565446204818185050686666406803638325856585381360686886848458863868 34;070969496903268 104;7003688908558869636058606088122; 66 56 84 94 88 58 0 30 56 62120; 66 120; 40 94;125884969060300263253589085605626028

南京财经大学 Nanjing University of Finance & Economics66 0 32 44 32 60 66 36 86 66 102 72 122 ]; 100 70 58 34 058 66 52 34 80 0 56 24 86 36 92 6848 86 26 58 60 24 38 0 68 30 74 6268 102 46 70 42 36 18 30 48 0 54 3281 122; 59 100; 60 68; 36 62; 6686118113886232286496918280644660929211010898803668688684845866 32;66981161141148872 0363410412212012094C1=B(:,2); C2=B(:,6); C3=B(:,13); C4=B(:,15); M=[C1 C2 C3 C4]; F=sort(M,2); Shortjourney2=F(:,1); Sum2=People*Shortjourney2;13

南京财经大学 Nanjing University of Finance & Economics附四:求四个点的最优方案的MatlAB源程序:clear all; A=combntns(1:18,4); for i=1:nchoosek(18,4) A2=A(i,:); A3=A2(1,1); A4=A2(1,2); A5=A2(1,3); A6=A2(1,4); People=[50 45 45 48 40 40 36 32 32 30 30 36 25 20 15 20 10 10]; B=[ 为节约篇幅省略,数据同上! ]; B1=B(:,A3); B2=B(:,A4); B3=B(:,A5); B4=B(:,A6); C=[B1 B2 B3 B4]; D=sort(C,2); Shortjourney=D(:,1); Sum(i)=People*Shortjourney; endE=reshape(Sum,nchoosek(18,4),1); minposition=find(E==min(E)); an=min(E); A=combntns(1:18,4); position=A(minposition,:);14

南京财经大学 Nanjing University of Finance & Economics附五:迁移一个点情况下最优方案求解程序:clear all; P=combntns(1:18,1); for i=1:nchoosek(18,1) P2=P(i,:); P3=6; P4=13; P5=15; P6=P2(1,1); People=[50 45 45 48 40 40 36 32 32 30 30 36 25 20 15 20 10 10];B=[ 为节约篇幅省略,数据同上! ]; V1=B(:,P3); V2=B(:,P4); V3=B(:,P5); V4=B(:,P6); C=[V1 V2 V3 V4]; D4=sort(C,2); Shortjourney4=D4(:,1); Sum4(i)=People*Shortjourney4; endE4=reshape(Sum4,nchoosek(18,1),1); minposition4=find(E4==min(E4)); an4=min(E4); P=combntns(1:18,1); position4=P(minposition4,:) ;15

南京财经大学 Nanjing University of Finance & Economics附六:求增加一个点的最优方案MatlAB源程序:clear all; W=combntns(1:18,1); for i=1:nchoosek(18,1) X1= W(i,:); X2=2; X3=6; X4=13; X5=15; X6=X1(1,1); People=[50 45 45 48 40 40 36 32 32 30 30 36 25 20 15 20 10 10];B=[ 为节约篇幅省略,数据同上!]; Y1=B(:,X2); Y2=B(:,X3); Y3=B(:,X4); Y4=B(:,X5); Y5=B(:,X6); Q=[Y1 Y2 Y3 Y4 Y5]; D3=sort(Q,2); Shortjourney3=D3(:,1); Sum3(i)=People*Shortjourney3; endE3=reshape(Sum3,nchoosek(18,1),1);16

南京财经大学 Nanjing University of Finance & Economicsminposition3=find(E3==min(E3)); an3=min(E3); W=combntns(1:18,1); position3=W(minposition3,:) ;17

 
 

微信关注公众号,送福利!