所得税缴费点选址问题

《所得税缴费点选址问题》由会员分享，可在线阅读，更多相关《所得税缴费点选址问题（34页珍藏版）》请在装配图网上搜索。

1、论文题目： 所得税缴费点选址问题摘 要 本文根据校方给出的题目所给予的数据构建模型，分析缴费点原址是否合理，进一步通过计算给出改址方案。构建模型过程中，我们小组主要根据运筹学原理，通过了解分析各地的人数以及各地两两之间的距离，提出了合理选址标准，并利用C语言编程，辅以字典排序算法和Dijkstra算法，得到提出的每个问题相应的合理解决方案：根据我们的标准，原设址存在不合理的地方；考虑迁移一个缴费点应将13号点迁至1号位置；假设在原方案增加新缴费点，新设址仍在1号位置。之后，我们小组又对程序中的算法进一步优化，使其适用性更强。 问题的提出 所得税管理部门方案对某个区域中的缴费点进行重新设计。该区

2、域原来有4个缴费点，分别位于图1的2，6，13，15位置。图1是该区域的一个实际简化，其中连接线表示有道路相通，连接线上数字表示两地距离单位百米，圆圈内数字是位置序号。位置123456789人数504545484040363232位置101112131415161718人数303036252015201010 各点代表的居民数见表1表1各点居民数单位千人 请你解决如下问题： 1给出合理选址的标准。2根据你的标准，分析原来的选址是否合理？3如果考虑迁移1个缴费点，应该迁移那个缴费点，迁到那里？4如果在原方案中增加一个新的缴费点，该点最好设在那里？ 问题假设（1） 假设每个地点之间人群没有流动，也

3、不存在人群离开本区域或者参加外来人群等现象。（2） 假设本区域内各点经济程度大致同等，去缴费点时使用同层次交通工具的人数比例相同。（3） 假设人们每次缴税费时，走的均是最短路线，不存在绕远路现象。（4） 各地点的所有人都需要去交税。 问题分析此题目实际上是一道优化设计的题目。在运筹学中，与题目最相似的经典问题是最短路问题。进一步，我们考虑到每个地点所拥有的人口数量不同，因此，在考虑最短路计算的根底上，还要考虑到权重比例的问题。从而我们确定了问题1的答案。合理选址标准为：所有点到相应最近的缴费点的总路程X的和最小。其中，X = 某地点总人数 * 该地到最近缴费点的距离注意：下文所提及的“ X 定

4、义与此处相同。 在此根底上，分别计算出各种设址可能性下的X值的和的大小，得到最优解。 模型的建立与求解在求解模型之前，我们小组先做准备工作。输入数据，构建18 * 18的矩阵，生成文件“matrix.txt，矩阵截图如下： 图中小于1000的数字均表示相连两地之间的距离，而数字1000那么是表示两地之间并不直接相连，当作无穷远。一、针对问题2提出的根据标准分析原来选址的合理性，我们小组通过编辑C语言程序，计算了在18个地点中任选4个作为缴费点时所需总路程和X分别是多少，并列表格比拟。 1、产生组合 long shumu=0; if(select=4) int list4; for(list0=

5、1;list0=summer-3;list0+) for(list1=list0+1;list1=summer-2;list1+) for(list2=list1+1;list2=summer-1;list2+) for(list3=list2+1;list3=summer;list3+) ofilelist0 list1 list2 list3endl; shumu+; ofileshumu; else if(select=5) int list5; for(list0=1;list0=summer-4;list0+) for(list1=list0+1;list1=summer-3;lis

6、t1+) for(list2=list1+1;list2=summer-2;list2+) for(list3=list2+1;list3=summer-1;list3+) for(list4=list3+1;list4=summer;list4+) ofilelist0 list1 list2 list3 list4endl; shumu+; ofileshumu; else cout暂不支持endl; 2、通过下述程序段，将各点人数文件“people.txt与文件“matrix.txt载入C语言程序中进行初始化。void matrix:load() ifstream infile(matr

7、ix.txt); for(int i=0;i18;i+) for(int j=0;jcostij; infile.close(); infile.clear(); infile.open(number.txt); infilepointsetpoint; infile.close(); infile.clear(); infile.open(people.txt); for(int k=0;kpeoplek; infile.close();3、通过下述程序段，计算一个点到其他所有点的最短路径*人数的值，即X的大小。其中计算最短路线的时候，我们运用了Dijkstra算法。其根本思想是：从某点出发

8、设为X，逐步向外探寻最短路。执行过程中，与每个点对应，记录下一个数称为这个点的标号，它或者表示从X到该点的最短路的权标号P，或者是从X到该点的最短路的权的上界标号T，方法的每一步是去修改T标号，并且把某一个具有标号T的点改变为具有P标号的点，从而使D中具有P标号的点数多了一个，这样就可以求的X到各点的最短距离。此处引出Dijkstra算法，如下Procedure Dijkstra (G：所有权都为正数的带权连通简单图)G带有的顶点a=v0，v1， vn=z和权wvi，vj，其中假设vi，vj不是G里的边，那么wvi，vj= for i : 1 to n L(vi): =L(a): =0S:=

9、现在初始化标记，使得a的标记为0而所有其余标记为，S是空集While z Sbegin u：=不属于S的Lu最小的一个顶点 S：=Sufor 所有不属于S的顶点v if L(u) + w( u , v) L(v) then L(v)：= L(u) + w( u , v) 这样就给S里添加带最小标记的顶点，并且更新不在S里的顶点的标记 end L(z)=从a到z的最短通路的长度代码如下：void matrix:paths() int i,u,w; for(i=0;ipoint;i+) foundi=false; distancei=coststarti; foundstart=true; dis

10、tancestart=0; for(i=0;ipoint-2;i+) u=choose(); foundu=true; for(w=0;wpoint;w+) if(!foundw) if(distanceu+costuwdistancew) distancew=distanceu+costuw; for(int temp =0;temp18;temp+) shorteststarttemp=distancetemp*peoplestart; choose()函数局部的代码： int matrix:choose() int i,min=2000,minpos=-1; for(i=0;ipoint

11、;i+) if(distanceisum; infilep1p2p3p4; q1=p1;q2=p2;q3=p3;q4=p4; for(int i=1;i=sum;i+) long temp; for(int j=0;jshortestjp2) temp=shortestjp2; if(tempshortestjp3) temp=shortestjp3; if(tempshortestjp4) temp=shortestjp4; mcost+=temp; outfilep1 p2 p3 p4 mcostendl; if(mcostp1p2p3p4; coutThe best :q1 q2 q3

12、q4endl; coutThe Sum :bestcostsum; infilep1p2p3p4p5; q1=p1;q2=p2;q3=p3;q4=p4,q5=p5; for(int i=1;i=sum;i+) long temp; for(int j=0;jshortestjp2) temp=shortestjp2; if(tempshortestjp3) temp=shortestjp3; if(tempshortestjp4) temp=shortestjp4; if(tempshortestjp5) temp=shortestjp5; mcost+=temp; outfilep1 p2

13、p3 p4 p5 mcostendl; if(mcostp1p2p3p4p5; coutThe best:q1 q2 q3 q4 q5endl; coutThe Sum :bestcostendl; infile.close(); outfile.close();结果截图如下：模型建立结果简单分析根本模型已经建立完毕。从题目给的图中我们可以看到，无论是合理的设置缴费点，或者是在原本根底上改迁抑或增设缴费点，地点1都显得相当重要。特别是对于问题34，从外表上看来，按照分析所得改址和增设地址之后，缴费地点显得相对集中。一开始得到这个结论我们小组成员也觉得很奇怪。但通过各地点人数的比拟，可以发现标号

14、靠前的地点所拥有的人数比重比拟大。因此经过初步检查和分析，我们认为这一模型建立以及结果分析根本成立和有效。 模型讨论以及程序优化考虑到该模型可以有更广的适用性，我们小组成员查阅资料，逐步改良了程序算法。利用字典排序法，我们将程序改良为适用于从M个数据中任选N个进行组合，同时利用动态数组及指针组成程序。这样一来，不仅算法本身更加具有严谨性，同时还降低程序的局限性，不再受限制于此题目。只要拥有相应的数据，就能对另一个地区的选址问题进行相关分析。此处，我们运用了字典排序法的定理：令 a1a2ar是1，2，3，.，n的一个r- 组合。在字典排序中，第一个r- 组合是12r 。 最后一个r-组合是n-r

15、+1(n-r+2)n。设a1a2arn-r+1(n-r+2)n。令k是满足akn且使得ak+1不同于a1，a2，ar中的任一个数的最大整数。那么，在字典排序中，a1a2ar的直接后继r-组合是 a1a2ak-1ak+1ak+2ak+ r - k+1从该定理我们断言，以下算法生成1，2 n的字典序的所有组合r- 组合： 生成1，2 n的字典序的所有组合r- 组合的算法。从r- 组合a1a2ar = 12r开始1确定最大的整数k，使得akn且使得ak+1不同于a1，a2，ar。2用r-组合 a1a2ak-1ak+1ak+2ak+ r - k+1替换a1a2ar 。所以，改动的程序段如下：1、产生组

16、合的子程序段:bool listmake:make() / 产生组合的优化 ： 可以实现N取M Msummer-select;count-) jiecheng=jiecheng*count; for(int count=select;count0;count-) change=change*count; jiecheng=jiecheng/change; ofilejiechengendl; / 组合个数 int* seat = new intselect; for(int i=0;i=0;j-) bool find=false; if(seatj+1summer ) continue; in

17、t k=0; for(;kselect;k+) if(seatj+1)=seatk) find=true; break; if(!find) break; int m=0; for(;mselect;m+) ofileseatm ; ofileendl; m=1; int temp=seatj; for(;jselect;j+) seatj=temp+m; m+; m=summer-select+1; bool equal=true; for(j=0;jselect;j+) if(seatj!=m) equal=false; break; m+; if(equal) pass=false; i

18、nt m=0; for(;mselect;m+) ofileseatm ; ofilesum; / 读文件 for(int count=0;countpcount; qcount=pcount; for(int i=1;i=sum;i+) long temp; for(int j=0;jpoint;j+) temp=shortestj*point+p0; for(int count=0;countshortestj*point+pcount) temp=shortestj*point+pcount; mcost+=temp; for(int count=0;countsetpoint;coun

19、t+) outfilepcount ; outfilemcostendl; if(mcostbestcost) /比拟得出最优组合 bestcost=mcost; for(int count=0;countsetpoint;count+) qcount=pcount; mcost=0; for(int count=0;countpcount; coutThe best : ; for(int count=0;countsetpoint;count+) coutqcount ; coutendl; coutThe Sum :bestcostendl; infile.close(); outfil

20、e.close(); delete p; delete q; 参考文献1、?运筹学? 清华大学出版社2、?数据结构根底? 清华大学出版社 Ellis Horowita , Sartaj Sahni 著3、?离散数学及其应用? 机械工业出版社 美 Kenneth H.Rosen 著 4、?组合数学? 机械工业出版社 美Richard A.Brualdi 著附 录程序代码改良前代码段#include#includeusing namespace std;class matrix public: matrix(); matrix(); public: void paths(); void load(

21、); void initstart(int n); void show(); void makeall(); void final4(); void final5(); private: int choose(); private: bool ok; public: int cost1818; int setpoint; int start; int distance18; int point; bool found18; int shortest1818; int people18; ;void matrix:makeall() / 所有点到其他点的最短路径 for(int i=0;i18;

22、i+) start=i; paths(); matrix:matrix() ok=true;matrix:matrix()void matrix:initstart(int n) start=n-1;void matrix:load() / 初始化 ifstream infile(matrix.txt); for(int i=0;i18;i+) for(int j=0;jcostij; infile.close(); infile.clear(); infile.open(number.txt); infilepointsetpoint; infile.close(); infile.clea

23、r(); infile.open(people.txt); for(int k=0;kpeoplek; infile.close();int matrix:choose() / int i,min=2000,minpos=-1; for(i=0;ipoint;i+) if(distanceimin & !foundi) min=distancei; minpos=i; return minpos;void matrix:paths() /最短总路程 = 该点人数* 该点到另外一点的最短距离 shorteststarttemp=distancetemp*peoplestart; int i,u,

24、w; for(i=0;ipoint;i+) foundi=false; distancei=coststarti; foundstart=true; distancestart=0; for(i=0;ipoint-2;i+) u=choose(); foundu=true; for(w=0;wpoint;w+) if(!foundw) if(distanceu+costuwdistancew) distancew=distanceu+costuw; for(int temp =0;temp18;temp+) shorteststarttemp=distancetemp*peoplestart;

25、 void matrix:show() / 输出 for(int i=0;i18;i+) for(int j=0;j18;j+) coutshortestij ; coutsum; infilep1p2p3p4; q1=p1;q2=p2;q3=p3;q4=p4; for(int i=1;i=sum;i+) long temp; for(int j=0;jshortestjp2) temp=shortestjp2; if(tempshortestjp3) temp=shortestjp3; if(tempshortestjp4) temp=shortestjp4; mcost+=temp; ou

26、tfilep1 p2 p3 p4 mcostendl; if(mcostp1p2p3p4; coutThe best :q1 q2 q3 q4endl; coutThe Sum :bestcostsum; infilep1p2p3p4p5; q1=p1;q2=p2;q3=p3;q4=p4,q5=p5; for(int i=1;i=sum;i+) long temp; for(int j=0;jshortestjp2) temp=shortestjp2; if(tempshortestjp3) temp=shortestjp3; if(tempshortestjp4) temp=shortest

27、jp4; if(tempshortestjp5) temp=shortestjp5; mcost+=temp; outfilep1 p2 p3 p4 p5 mcostendl; if(mcostp1p2p3p4p5; coutThe best :q1 q2 q3 q4 q5endl; coutThe Sum :bestcostendl; infile.close(); outfile.close();int main() matrix a; a.load(); a.makeall(); a.final4(); return 0;程序段#include#includeusing namespac

28、e std;class listmake public: listmake(); listmake(); public: bool make(); void init(); public: short summer; short select; ofstream ofile; ifstream ifile; bool ok;void listmake:init() ifilesummerselect; if(!(summer=select)|(summer255)|(select=0) ok=true; else coutenter errorendl;listmake:listmake()

29、summer=select=0; ok=false; ofile.open(list.dat); ifile.open(number.txt);listmake:listmake() ofile.close(); ifile.close();bool listmake:make() if(ok=false) return false; long shumu=0; if(select=4) int list4; for(list0=1;list0=summer-3;list0+) for(list1=list0+1;list1=summer-2;list1+) for(list2=list1+1

30、;list2=summer-1;list2+) for(list3=list2+1;list3=summer;list3+) ofilelist0 list1 list2 list3endl; shumu+; ofileshumu; else if(select=5) int list5; for(list0=1;list0=summer-4;list0+) for(list1=list0+1;list1=summer-3;list1+) for(list2=list1+1;list2=summer-2;list2+) for(list3=list2+1;list3=summer-1;list

31、3+) for(list4=list3+1;list4=summer;list4+) ofilelist0 list1 list2 list3 list4endl; shumu+; ofileshumu; else coutnot supportendl; return true;int main() listmake ls; ls.init(); ls.make(); return 0;改良后程序段如下：#include#includeusing namespace std;class matrix public: matrix(); matrix(); public: void paths

32、(); void load(); void initstart(int n); void show(); void makeall(); void final(); private: int choose(); private: bool ok; public: int* cost;/两地距离 int setpoint;/设置点个数 int start;/出发城市号 从0开始 int* distance;/某城市到其他所有城市的距离数组 int point;/城市点数 bool* found;/ 是否到达 int* shortest;/矩阵 人数*最短路径 int* people;/数组 各城

33、市人数 ;void matrix:makeall() for(int i=0;ipointsetpoint; infile.close(); cost= new intpoint*point; distance= new intpoint; shortest= new intpoint*point; found= new boolpoint; people= new intpoint;matrix:matrix() delete cost; delete distance; delete shortest; delete found; delete people;void matrix:ini

34、tstart(int n)start=n-1;void matrix:load()/初始化数据 ifstream infile; infile.clear(); infile.open(matrix.txt); for(int i=0;ipoint;i+) for(int j=0;jcosti*point+j; infile.close(); infile.clear(); infile.open(people.txt); for(int k=0;kpeoplek; infile.close();int matrix:choose() int i,min=2000,minpos=-1; for(i=0;ipoint;i+) if(distanceimin & !foundi) min=distancei; minpos=i; return minpos;void matrix:paths() / 算法 求最短路径 int i,u,w; for(i=0;ipoint;i+) found