数学建模论文

来源:互联网 由 zpcandzhj 贡献 责任编辑:鲁倩  

所得税缴费点选址问题

作者:李鸣 郭桂江 周鹏程

摘要

近年来,图论在生产生活和科学技术研究中的作用日趋显著,特别是大型电子计算机的出现和计算机科学的迅猛发展,为图论及其算法的解决提供了强大的计算和证明的手段。本文的主要内容是结合图论的相关知识对居民所得税缴费点的选址提出合理的标准,并进行合理优化的选址。通过建立图的邻接矩阵将原始数据存入计算机,并借助MatlAB软件编写求任意两点间最短路径的Floyd算法程序实现最短路径的求解。

通过对原始数据的分析和不断修改计算,本文从缴费点周围的居民数量和居民距离缴费点的距离等方面分析了各种方案的预测数据并得出了一些有社会价值的结论。如果按照最优化方案,即选用2,4,7,12为缴费点,得出最短路径为10850(百米*千人)。按增加一个点的方案则应增加5位置为缴费点,算出最短路径为10724(百米*千人)。如果想在原来基础上迁移一个点,则应撤掉15号点的缴费点,在4号点建缴费点。本次设计很好地将图论应用于实际生活。

关键词:图论 Floyd算法 最短路径 邻接矩阵 MatlAB求解

一、\t问题重述

所得税管理部门计划对某个区域中的缴费点进行重新设计。该区域原来有4各缴费点,分别位于图1的2,6,13,15位置。图1是该区域的一个实际简化,其中连接线表示有道路相通,连接线上数字表示两地距离(单位百米),圆圈内数字是位置序号。

各点代表的居民数见表1。

表1各点居民数(单位千人)

位置

1

2

3

4

5

6

7

8

9

人数

50

45

45

48

40

40

36

32

32

位置

10

11

12

13

14

15

16

17

18

人数

30

30

36

25

20

15

20

10

10

请你解决如下问题:

(1)给出合理选址的标准。

(2)根据你的标准,分析原来的选址是否合理?

(3)如果考虑迁移1个缴费点,应该迁移那个缴费点,迁到那里?

(4)如果在原方案中增加一个新的缴费点,该点最好设在那里?

二、\t模型假设

1.\t假设同一个居民点的所有居民到到同一个缴费点缴费。

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

3.\t假设缴费点的接待能力无限大,过多的人不影响缴费点处的工作效率和工作质量

4.\t假设缴费点每天每时每刻都可以交费。

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

三、符号说明

D —— 两个缴费点(i,j)之间的距离

a —— 题目中给定图的邻接矩阵

path —— 两个缴费点(i,j)之间的路线

floyd —— 佛洛依德算法

B —— 通过floyd算法求得的最短路径矩阵

Shortjourney 最短路径

Sum(i) —— 最短路径长

Position— 所选择的最佳点的位置

an(i) —— 各个方案的距离值

A C P Q W V 表示各个不同的矩阵

四、模型的建立与求解

问题一:

我们可以选择如下选址标准:所选的四个点能够使所有居民到达离自身最近的缴税点的总路程最小,路程是指该点的人数乘以该点到缴税点的距离。如:如①到②距离应为:(居民数50 )*(距离20)=1000(千人*百米),

问题二:

根据该选址标准,可将本问题转化为图论中的最短路径问题,可以通过 Floyd算法编程实现求解,采用的软件是MatlABR2007a.

1.\t数据存储

因为所给图为无向带权图,所以要根据图论和数据结构的知识转化为邻接矩阵,来储存数据,并将数据输入MatlAB中。所得邻接矩阵如下:

a=

[

0 20 18 18 15 inf inf inf inf inf inf inf inf inf inf inf inf inf;

20 0 26 inf 28 inf inf inf 30 28 30 30 inf inf inf inf inf inf;

18 26 0 20 inf inf inf inf inf inf inf 20 inf 26 inf inf inf inf;

18 inf 20 0 18 18 50 inf inf inf inf inf inf inf inf 18 inf inf;

15 28 inf 18 0 inf 38 32 inf inf inf inf inf inf inf inf inf inf;

inf inf inf 18 inf 0 inf inf inf inf inf inf inf inf inf inf inf 36;

inf inf inf 50 38 inf 0 inf inf inf inf inf inf inf inf inf inf 34;

inf inf inf inf 32 inf inf 0 36 inf inf inf inf inf inf inf inf inf;

inf 30 inf inf inf inf inf 36 0 inf inf inf inf inf inf inf inf inf;

inf 28 inf inf inf inf inf inf inf 0 30 inf inf inf inf inf inf inf;

inf 30 inf inf inf inf inf inf inf 30 0 26 32 inf inf inf inf inf;

inf 30 20 inf inf inf inf inf inf inf 26 0 28 inf inf inf inf inf;

inf inf inf inf inf inf inf inf inf inf 32 28 0 32 inf inf inf inf;

inf inf 26 inf inf inf inf inf inf inf inf inf 32 0 34 inf inf inf;

inf inf inf inf inf inf inf inf inf inf inf inf inf 34 0 24 36 inf;

inf inf inf 18 inf inf inf inf inf inf inf inf inf inf 24 0 30 inf;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf 36 30 0 32;

inf inf inf inf inf 36 34 inf inf inf inf inf inf inf inf inf 32 0

]

2.\t数据分析

根据上述矩阵采用floyd算法编制求解最短路径的程序,在MatlAB中运行 。算法程序如下:

function [D,path]=floydz(a) 定义函数

n=size(a,1);

D=a;path=zeros(n,n); 设置D 和Path 的初值

for i=1:n

for j=1:n

if D(i,j)~=inf

path(i,j)=j; j 是i 的后继点

end

end

end

for k=1:n 做n 次迭代, 每次迭代均更新D(i,j) 和path(i,j)

for i=1:n

for j=1:n

if D(i,k)+D(k,j) D(i,j)=D(i,k)+D(k,j) ; 修改长度

path(i,j)=path(i,k) ; 修改路径

end

end

end

end

在MatlAB中运行得出最短路径矩阵B(详细程序见附录):

通过进一步编程带入数据求得最佳缴费点:(详细程序见附录)

>> position(位置)

position =

2 4 7 12

>>

>> an(最短路程)

an =

10850

>>

根据以上分析和计算得出如下表格:

原始方案

最优方案

缴费点

2,6,13,15

2,4,7,12

最短路程(百米*千人)

13998

10850

所以经过以上的分析计算得出:根据我们制定的选址标准原方案不合理。

问题三:

如果要在原始位置的基础上迁移一个缴费点,首先考虑迁出的点:分别是迁移2号点或6号点或13号点或15号点。再在每一种迁出情况下考虑迁入的点,共有18种可能(这里为方便程序编制与求解把本身点也包含在内,但不影响结果),通过程序计算求得每一种情况下的最短路径,再找出4个最短路径中最小的,即选择该方案。

计算机求解的结果比较(详细程序见附录):

迁出点

2

6

13

15

最佳迁入点

1

4

5

4

新位置

1 6 13 15

2 4 13 15

2 5 6 15

2 4 6 13

路程(百米*千人)

13434

12248

12286

12098

经过分析比较得出:如果要在原始的基础上迁移一个点,最好迁移15号点到4号点位置,组成新的缴费点2 4 6 13,此时的路程最短,为12098(百米*千人)。

问题四:

有了前面的分析,解决第四个问题的方法类似。因为此时四个点已经确定,只要用穷举法计算出增加每一个点情况下的最短路程,再从中找出使得总路程最短的一种方案。为了编程和计算的方便,还是考虑18种情况,与自身重复的情况并不影响最终结果,因为增加自身(还是原来的4个点)的情况下总里程一定比增加别的点大,而我们最终要得到的是最小值。

通过编程在MatlAB中求解得出(详细程序见附录):

>> an3

an3 =

10724

>>

>> position3

position3 =

5

>>

于是得出当增加的点为5时,居民行走的总路程最短,路程为10724(百米*千人)。

五、模型的评价与推广

通过对题目中四个问题的分析,我们建立了以图论为理论基础的数学模型,并且借助于数学软件MatlAB编制基于Floyd算法的程序对模型进行求解,找出了最优化的选址方案,能够很好地指导缴费点的建设。但是在这个模型中我们忽略了每个居民的个体差异,认为他们的选择是一致的,其实他们在没有统一规定或者指导的情况下是随意到任意缴费点缴费的。我们也忽略了每个点之间的交通情况,每个缴费点的运营能力等等,在实际生活中缴费点的建设和选择都应该综合考虑这一系列的因素。本文中的方法还可以解决其它诸如求最短路径的问题。

六、参考文献

【1】李海涛,邓樱,MATLAB程序设计教程,北京:高等教育出版社,2002.

【2】张先迪,李正良,图论及其应用,北京:高等教育出版社,2005.

【3】严蔚敏,吴伟明,数据结构(C语言版),北京:清华大学出版社,2007.

【4】姜启源,谢金星,数学建模案例选集,北京:高等教育出版社,2006.

【5】屈婉玲,耿素云,张立昂,离散数学,北京:高等教育出版社,2008.

七、附录

附一: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

end

for k=1:n

for i=1:n

for j=1:n

if D(i,k)+D(k,j) D(i,j)=D(i,k)+D(k,j) ;

path(i,j)=path(i,k) ;

end

end

end

end

附二:调用floyd算法求最短路径的MatlAB源程序:

a=[

0 20 18 18 15 inf inf inf inf inf inf inf inf inf inf inf inf inf;

20 0 26 inf 28 inf inf inf 30 28 30 30 inf inf inf inf inf inf;

18 26 0 20 inf inf inf inf inf inf inf 20 inf 26 inf inf inf inf;

18 inf 20 0 18 18 50 inf inf inf inf inf inf inf inf 18 inf inf;

15 28 inf 18 0 inf 38 32 inf inf inf inf inf inf inf inf inf inf;

inf inf inf 18 inf 0 inf inf inf inf inf inf inf inf inf inf inf 36;

inf inf inf 50 38 inf 0 inf inf inf inf inf inf inf inf inf inf 34;

inf inf inf inf 32 inf inf 0 36 inf inf inf inf inf inf inf inf inf;

inf 30 inf inf inf inf inf 36 0 inf inf inf inf inf inf inf inf inf;

inf 28 inf inf inf inf inf inf inf 0 30 inf inf inf inf inf inf inf;

inf 30 inf inf inf inf inf inf inf 30 0 26 32 inf inf inf inf inf;

inf 30 20 inf inf inf inf inf inf inf 26 0 28 inf inf inf inf inf;

inf inf inf inf inf inf inf inf inf inf 32 28 0 32 inf inf inf inf;

inf inf 26 inf inf inf inf inf inf inf inf inf 32 0 34 inf inf inf;

inf inf inf inf inf inf inf inf inf inf inf inf inf 34 0 24 36 inf;

inf inf inf 18 inf inf inf inf inf inf inf inf inf inf 24 0 30 inf;

inf inf inf inf inf inf inf inf inf inf inf inf inf inf 36 30 0 32;

inf inf inf inf inf 36 34 inf inf inf inf inf inf inf inf inf 32 0

] ;

[D,path]= floydz (a);

B=D;

附三:求原始选址方案的最短路程程序:

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 20 18 18 15 36 53 47 50 48 50 38 66 44 60 36 66 72;

20 0 26 38 28 56 66 60 30 28 30 30 58 52 80 56 86 92;

18 26 0 20 33 38 70 65 56 54 46 20 48 26 60 38 68 74;

18 38 20 0 18 18 50 50 68 66 66 40 68 46 42 18 48 54;

15 28 33 18 0 36 38 32 58 56 58 53 81 59 60 36 66 72;

36 56 38 18 36 0 68 68 86 84 84 58 86 64 60 36 66 36;

53 66 70 50 38 68 0 70 96 94 96 90 118 96 92 68 66 34;

47 60 65 50 32 68 70 0 36 88 90 85 113 91 92 68 98 104;

50 30 56 68 58 86 96 36 0 58 60 60 88 82 110 86 116 122;

48 28 54 66 56 84 94 88 58 0 30 56 62 80 108 84 114 120;

50 30 46 66 58 84 96 90 60 30 0 26 32 64 98 84 114 120;

38 30 20 40 53 58 90 85 60 56 26 0 28 46 80 58 88 94;

66 58 48 68 81 86 118 113 88 62 32 28 0 32 66 86 102 122;

44 52 26 46 59 64 96 91 82 80 64 46 32 0 34 58 70 100;

60 80 60 42 60 60 92 92 110 108 98 80 66 34 0 24 36 68;

36 56 38 18 36 36 68 68 86 84 84 58 86 58 24 0 30 62;

66 86 68 48 66 66 66 98 116 114 114 88 102 70 36 30 0 32;

72 92 74 54 72 36 34 104 122 120 120 94 122 100 68 62 32 0

];

C1=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;

附四:求四个点的最优方案的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;

end

E=reshape(Sum,nchoosek(18,4),1);

minposition=find(E==min(E));

an=min(E);

A=combntns(1:18,4);

position=A(minposition,:);

附五:迁移一个点情况下最优方案求解程序:

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;

end

E4=reshape(Sum4,nchoosek(18,1),1);

minposition4=find(E4==min(E4));

an4=min(E4);

P=combntns(1:18,1);

position4=P(minposition4,:) ;

附六:求增加一个点的最优方案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;

end

E3=reshape(Sum3,nchoosek(18,1),1);

minposition3=find(E3==min(E3));

an3=min(E3);

W=combntns(1:18,1);

position3=W(minposition3,:) ;

  • 与《数学建模论文》相关:
  • 数学教学方式论文数学建模论文
  • 数学建模的能力培养论文:数学建模的能力培养
  • [数学]数学建模论文写作
  • 数学建模论文75922
  • 数学建模优秀论文.
  • 股市中的成交量数学建模论文
  • 数学建模论文书写基本框架.
  • [理学]数学建模论文模板
  • 数学建模竞赛论文写作及相关注意事项
  • 全国大学英语六级考试CET考生报名指导快速教程
  • 本站网站首页首页教育资格全部考试考试首页首页考试首页职业资格考试最近更新儿童教育综合综合文库22文库2建筑专业资料考试首页范文大全公务员考试首页英语首页首页教案模拟考考试pclist学路首页日记语文古诗赏析教育教育资讯1高考资讯教育头条幼教育儿知识库教育职场育儿留学教育高考公务员考研考试教育资讯1问答教育索引资讯综合学习网站地图学习考试学习方法首页14托福知道备考心经冲刺宝典机经真题名师点睛托福课程雅思GREGMATSAT留学首页首页作文
    免责声明 - 关于我们 - 联系我们 - 广告联系 - 友情链接 - 帮助中心 - 频道导航
    Copyright © 2017 www.xue63.com All Rights Reserved