所得税交纳点选址探究

1、数学建模所得税交纳点选址探究- 17 -所得税交纳点选址探究作者：任蕊（0932037）缪崯森（0932102）孙倩倩（0932015）目 录TOC o 1-3 h z u HYPERLINK l _Toc260038862 摘要 PAGEREF _Toc260038862 h - 2 - HYPERLINK l _Toc260038863 一、问题的重述 PAGEREF _Toc260038863 h - 2 - HYPERLINK l _Toc260038864 二、模型假设与符号约定 PAGEREF _Toc260038864 h - 3 - HYPERLINK l _Toc260038

2、865 2.1 模型的假设与说明 PAGEREF _Toc260038865 h - 3 - HYPERLINK l _Toc260038866 2.2符号约定与说明 PAGEREF _Toc260038866 h - 3 - HYPERLINK l _Toc260038867 三、模型的分析 PAGEREF _Toc260038867 h - 3 - HYPERLINK l _Toc260038868 四、模型的建立与求解 PAGEREF _Toc260038868 h - 4 - HYPERLINK l _Toc260038869 4.1 模型I:Dijkstra PAGEREF _Toc

3、260038869 h - 4 - HYPERLINK l _Toc260038870 4.2模型II:Floyd PAGEREF _Toc260038870 h - 6 - HYPERLINK l _Toc260038871 五、模型评价 PAGEREF _Toc260038871 h - 7 - HYPERLINK l _Toc260038872 参考文献 PAGEREF _Toc260038872 h - 8 - HYPERLINK l _Toc260038873 附录一 Dijkstra的MatLab程序 PAGEREF _Toc260038873 h - 9 - HYPERLINK

4、l _Toc260038874 附录二 Floyd的MatLab程序 PAGEREF _Toc260038874 h - 10 - HYPERLINK l _Toc260038875 附录三 任意一节点到其他节点最短的走法 PAGEREF _Toc260038875 h - 11 -摘要本文运用了图论的思想理论，在仔细分析问题的条件和要求的基础上，把城市交通网络等效为有向赋权图，将各个纳税点等效为有向图上的各个顶点，采用求解最短路程问题的迪克斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法对本问题进行求解，并分别通过MatLab、Lingo加以实现，体验在不同环境下两种算法的优劣，继

5、而得出纳税点安排的最佳方案。我们的模型合理、实用、简单易懂，可以通用于以图为基础的最优节点的选择问题中，以指导城市规划部门作出相对正确的选择.关键字纳税点规划；选址；Dijkstra算法；Floyd 算法；最佳路线一、问题的重述所得税管理部门计划对某个城市的所得税交纳点网络进行重新设计.下图是该城市主要区和主要道路的示意图.区旁边的黑体数字表示该区居民数目，单位为千人.在连区之间的弧上标出了它们之间的距离，单位为千米（斜体字）.为覆盖整个城市，所得税管理部门决定在三个区设置纳税点.请建立数学模型给出三个纳税点安排的最佳方案.二、模型假设与符号约定2.1 模型的假设与说明题目中所有居民都要交纳所

6、得税，且每个居民都是独立完成所得税的交纳.三个纳税点均可独立完成纳税工作，且所接待的纳税人无上限.每条道路在任何时段均畅通.符号约定与说明设题目所给的图为G，V为G的顶点集， ，E为G的边集，.那么该图可以被定义为.令图G的每一条边都对应一个实数，则称G为赋权图,并设为节点u到节点v的路径，用表示全部边的集合，记，称F(P)为路径P(u,v)的权或长度.表示每一个交纳点的居民数，.表示最优缴纳点交纳点,.三、模型的分析该问题的目的是对某个城市的所得税交纳点网络进行重新设计，以找出最合理的选址方案，以方便居民生活，有效提高纳税的效率.可把该问题抽象为从拓扑图G中寻找最优节点问题，这样可以采用最短

7、路径算法，Dijkstra和Flody算法加以实现.该模型在不考虑纳税点接待量的限制，交通拥堵等条件下可抽象为求所有居民到达纳税点的总路程最短的问题，以期达到方便纳税人就近纳税，减少不必要的路上时间花费，节约能源，实现建设资源环保型社会的目标.四、模型的建立与求解4.1 模型 = 1 * ROMAN I:Dijkstra若是G中连接u,v的路径，且对任意在G中连接u,v的路径都有，则称是G中连接u,v的最短路径.那么显然，若为从到的最短距离，则，必为从到的最短距离.更具上述原理求G中某一点到其他各点的距离的算法叫Dijkstra算法.可用两种标号T（Temporary Label）标号与P（P

8、ermanent Label）.给节点一个P标号指从到的最短路权，点的标号不再改变.给一个T标号时，表示从到的最短路权的上界，是临时标号，凡没有得到P标号的点都有T标号，到所有的T标号全部得到P标号时，程序结束.Dijkstra标号算法计算步骤赋初值.给以P标号，记录，其余各点给T标号，并将的父节点设为.记录，转向b).更新所有的T标号和其父节点.，如果，则令，并重新记录v的父节点为u，转向c).给出下一个P标号并更新记录u和S. 给以标号P，重新记录，转向d).终止判断.若非空，转向b),否则终止.由于每个节点人口不同，则我们把节点上的人口视为边的权的一部分，因而可有这时可把G视为有向图，我

9、们可得出权矩阵为：根据权矩阵，由Dijkstra算法可以求出到其余各结点的最短距离节点12345678910111210150444990120144019852862488011021340222502647201901248363768546121011591220355522003248072047344826012767417804825400216017028867173631213648176805360380192612086429719231210787038606900520360216180062767215611005894407270330516109813513680

10、24058548476012208495480336828601008165039081447592097204202404321202884954800836361380106005506961116245120024259249403618001187061046877418574444040024741804201210056104686122155286717362478803990表格 SEQ 表格 * ARABIC 1各节点相互最小距离在MatLab中，用枚举法求，对上述矩阵任选三行，记为（i,j,k=1,2,12且ijk），则这样的组合有种。a列的最小值记为(a=1,2,12)。

11、再对上述最小值求和，记为S=，这样的S有个，再用find函数找出S的最小值对应在矩阵中的位置. 容易得到，最优解对应的矩阵为也可以用lingo枚举得出最优解.model: sets: point/1.12/:p,x; way(point,point):d,c; endsetsdata: d= 0 15 37 45 24 60 18 33 48 40 58 67 15 0 22 40 38 52 33 48 42 55 61 61 37 22 0 18 16 30 43 28 20 58 39 39 45 40 18 0 34 12 61 46 24 62 43 34 24 38 16 34 0

12、 36 27 12 24 49 43 43 60 52 30 12 36 0 57 42 12 50 31 22 18 33 43 61 27 57 0 15 45 22 40 61 33 48 28 46 12 42 15 0 30 37 25 46 48 42 20 24 24 12 45 30 0 38 19 19 40 55 58 62 49 50 22 37 38 0 19 40 58 61 39 43 43 31 40 25 19 19 0 21 67 61 39 34 43 22 61 46 19 40 21 0; p=15 10 12 18 5 24 11 16 13 22 1

13、9 20; enddatamin=sum(way(i,j):d(i,j)*p(i)*c(i,j); for(point(i):sum(point(j):c(i,j)=1); Lingo解的结果，划线部分为最优解sum(point:x)=3; for(way(i,j):c(i,j)12-13-4-64-65-16-67-18-119-610-1111-1112-11表格2各节点到纳税点的最佳路径图表3最佳纳税点覆盖的范围五、模型评价1、本模型综合运用了图论中的的赋权图,Dijkstra算法,Floyd算法以及排列组合等数学方法.2、本模型求解最短路径时所使用的方法：其一为Dijkstra算法，该

14、算法的优点在于简单且能快速得出结果，具有贪心算法的特性，相比于和他同类型的Bellman ford，能够更快速的解决问题.但该算法要求所有边的权值非负，又由于它遍历计算的节点很多，所以效率低。其二为Floyd算法，该算法适用于APSP(All Pairs Shortest Paths),是一种动态规划算法，稠密图效果佳，边权可正可负，此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行V次Dijkstra算法，但是该算法时间复杂度高，不适合计算大量数据。3、本题所选的是三个交纳点，根据此模型我们能够求出选取任意多个点时的最优解。本模型具有普遍性，能够运用到其他选址问题上，譬如医院、

15、消防站等的选址问题。参考文献1E.米涅卡.网络和图的最优化算法.北京：中国铁道出版设，1984.2刘承平.数学建模方法.北京：高等教育出版社,2002.3钱颂迪等.运筹学(修订版).北京:清华大学出版社,2000.附录一Dijkstra的MatLab程序clear;clc;M=Inf;Pop=15 10 12 18 5 24 11 16 13 22 19 20;a=0 15 M M 24 M 18 M MMMM;zeros(1,2) 22 M MMMMMMMM;zeros(1,3) 18 16 M MM 20 M MM;zeros(1,4) M 12 M MMMMM; zeros(1,5) M

16、 M 12 24 M MM;zeros(1,6) M M 12 M M 22;zeros(1,7) 15 M 22 M M;zeros(1,8) 30 M 25 M;zeros(1,9) M 19 19;zeros(1,10) 19 M;zeros(1,11) 21;zeros(1,12);a=a+a;for i=1:length(a)pb(1:length(a)=0;pb(i)=1; d(1:length(a)=M;d(i)=0;temp=i;while sum(pb)length(a)tb=find(pb=0); d(tb)=min(d(tb),d(temp)+a(temp,tb);tmp

17、b=find(d(tb)=min(d(tb);temp=tb(tmpb(1);pb(temp)=1; end;ShortPath(i,:)=d.*Pop;end;ShortPathidx=nchoosek(1:12,3);for n=1:nchoosek(12,3)Bn=ShortPath(idx(n,:),:);endC=;for i=1:1:220 A=min(Bi); C=C;A;endfinal=sum(C);X1 I=min(final);BIrow,col = find(ans=0);result=col附录二 Floyd的MatLab程序M=inf;a=0 150 M M 120

18、 M 198 M MMM M;225 0 264 M MMMMMMMM;M 220 0 324 80 M MM 260 M M M;M M 216 0 M 288 M MMMMM;360 M 192 M 0 M M 192 312 M M M;M M M 216 M 0 M M 156 M M 440;270 M MMMM 0 240 M 484 M M;M M MM 60 M 165 0 390 M 475 M;M M 240 M 120 288 M 480 0 M 361 M;M M MMMM 242 M M 0 361 M;M MMMMMM 400 247 418 0 420;M M MMM 528 M M 47 M 399 0n=size(a,1);D=a;Pop=15 10 12 18 5 24 11 16 13 22 19 20;d=Pop;Pop;Pop;Pop;Pop;Pop;Pop;Pop;Pop;Pop;Pop;Pop;for i=1:nfor j=1:nRi,j=num2str(i),num2str(j);endendfor k=1:nfor i=1:nfor j=1:nif D(