所得税缴费点选址问题

论文题目： 所得税缴费点选址问题摘 要 本文根据校方给出的题目所给予的数据构建模型，分析缴费点原址是否合理，进一步通过计算给出改址方案。构建模型过程中，我们小组主要根据运筹学原理，通过了解分析各地的人数以及各地两两之间的距离，提出了合理选址标准，并利用C语言编程，辅以字典排序算法和Dijkstra算法，得到提出的每个问题相应的合理解决方案：根据我们的标准，原设址存在不合理的地方；考虑迁移一个缴费点应将13号点迁至1号位置；假设在原方案增加新缴费点，新设址仍在1号位置。之后，我们小组又对程序中的算法进一步优化，使其适用性更强。 问题的提出 所得税管理部门方案对某个区域中的缴费点进行重新设计。该区域原来有4个缴费点，分别位于图1的2，6，13，15位置。图1是该区域的一个实际简化，其中连接线表示有道路相通，连接线上数字表示两地距离单位百米，圆圈内数字是位置序号。位置123456789人数504545484040363232位置101112131415161718人数303036252015201010 各点代表的居民数见表1表1各点居民数单位千人 请你解决如下问题： 1给出合理选址的标准。2根据你的标准，分析原来的选址是否合理？3如果考虑迁移1个缴费点，应该迁移那个缴费点，迁到那里？4如果在原方案中增加一个新的缴费点，该点最好设在那里？ 问题假设（1） 假设每个地点之间人群没有流动，也不存在人群离开本区域或者参加外来人群等现象。（2） 假设本区域内各点经济程度大致同等，去缴费点时使用同层次交通工具的人数比例相同。（3） 假设人们每次缴税费时，走的均是最短路线，不存在绕远路现象。（4） 各地点的所有人都需要去交税。 问题分析此题目实际上是一道优化设计的题目。在运筹学中，与题目最相似的经典问题是最短路问题。进一步，我们考虑到每个地点所拥有的人口数量不同，因此，在考虑最短路计算的根底上，还要考虑到权重比例的问题。从而我们确定了问题1的答案。合理选址标准为：所有点到相应最近的缴费点的总路程X的和最小。其中，X = 某地点总人数 * 该地到最近缴费点的距离注意：下文所提及的“ X 定义与此处相同。 在此根底上，分别计算出各种设址可能性下的X值的和的大小，得到最优解。 模型的建立与求解在求解模型之前，我们小组先做准备工作。输入数据，构建18 * 18的矩阵，生成文件“matrix.txt，矩阵截图如下： 图中小于1000的数字均表示相连两地之间的距离，而数字1000那么是表示两地之间并不直接相连，当作无穷远。一、针对问题2提出的根据标准分析原来选址的合理性，我们小组通过编辑C语言程序，计算了在18个地点中任选4个作为缴费点时所需总路程和X分别是多少，并列表格比拟。 1、产生组合 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;list2<=summer-1;list2+) for(list3=list2+1;list3<=summer;list3+) ofile<<list0<<" "<<list1<<" " <<list2<<" "<<list3<<endl; shumu+; ofile<<shumu; 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;list3+) for(list4=list3+1;list4<=summer;list4+) ofile<<list0<<" "<<list1<<" " <<list2<<" "<<list3<<" "<<list4<<endl; shumu+; ofile<<shumu; else cout<<"暂不支持"<<endl; 2、通过下述程序段，将各点人数文件“people.txt与文件“matrix.txt载入C语言程序中进行初始化。void matrix:load() ifstream infile("matrix.txt"); for(int i=0;i<18;i+) for(int j=0;j<18;j+) infile>>costij; infile.close(); infile.clear(); infile.open("number.txt"); infile>>point>>setpoint; infile.close(); infile.clear(); infile.open("people.txt"); for(int k=0;k<18;k+) infile>>peoplek; infile.close();3、通过下述程序段，计算一个点到其他所有点的最短路径*人数的值，即X的大小。其中计算最短路线的时候，我们运用了Dijkstra算法。其根本思想是：从某点出发设为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:= Ø现在初始化标记，使得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;i<point;i+) foundi=false; distancei=coststarti; foundstart=true; distancestart=0; for(i=0;i<point-2;i+) u=choose(); foundu=true; for(w=0;w<point;w+) if(!foundw) if(distanceu+costuw<distancew) distancew=distanceu+costuw; for(int temp =0;temp<18;temp+) shorteststarttemp=distancetemp*peoplestart; choose()函数局部的代码： int matrix:choose() int i,min=2000,minpos=-1; for(i=0;i<point;i+) if(distancei<min && !foundi) min=distancei; minpos=i; return minpos;4、18个点中任选4个作为缴费点，一共有3060种情况。从所得的程序显示和数据表格中，可以发现，当设置点分别为1，3，6，11时，总路程和X是最小的，为10850百米。相应程序段编写如下：void matrix:final4() ifstream infile("list4.dat"); ofstream outfile("list4cost.txt"); int p1,p2,p3,p4; int q1=0,q2=0,q3=0,q4=0; long mcost=0; long bestcost=69999; int sum; infile>>sum; infile>>p1>>p2>>p3>>p4; q1=p1;q2=p2;q3=p3;q4=p4; for(int i=1;i<=sum;i+) long temp; for(int j=0;j<18;j+) temp=shortestjp1; if(shortestjp1>shortestjp2) temp=shortestjp2; if(temp>shortestjp3) temp=shortestjp3; if(temp>shortestjp4) temp=shortestjp4; mcost+=temp; outfile<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<" "<<mcost<<endl; if(mcost<bestcost) bestcost=mcost; q1=p1;q2=p2;q3=p3;q4=p4; mcost=0; infile>>p1>>p2>>p3>>p4; cout<<"The best :"<<q1<<" "<<q2<<" "<<q3<<" "<<q4<<endl; cout<<"The Sum :"<<bestcost<<endl; infile.close(); outfile.close();输出结果以及局部截图如下： 二、针对问题3，考虑迁移原本4个缴费点中的一个，仍旧根据先前提出的标准，编辑程序，计算迁移其中一点之后的总路程和X，共有56中情况。结果截图：根据程序显示，应将原本位于13号的缴费点迁移至1号缴费点。此时总路程和X是56种情况中最小的，为12384百米。三、对于问题5，只需要稍微改动程序，可以得到：假设要在原方案中增加一个新的缴费点，有14种情况。设址在1号位置比拟合理。即5个缴费点分别是1、2、6、13、15位置，此时总路程和X为11464百米。void matrix:final5() ifstream infile("list5.dat"); ofstream outfile("list5cost.txt"); int p1,p2,p3,p4,p5; int q1=0,q2=0,q3=0,q4=0,q5=0; long mcost=0; long bestcost=69999; int sum; infile>>sum; infile>>p1>>p2>>p3>>p4>>p5; q1=p1;q2=p2;q3=p3;q4=p4,q5=p5; for(int i=1;i<=sum;i+) long temp; for(int j=0;j<18;j+) temp=shortestjp1; if(shortestjp1>shortestjp2) temp=shortestjp2; if(temp>shortestjp3) temp=shortestjp3; if(temp>shortestjp4) temp=shortestjp4; if(temp>shortestjp5) temp=shortestjp5; mcost+=temp; outfile<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<" "<<p5<<" "<<mcost<<endl; if(mcost<bestcost) bestcost=mcost; q1=p1;q2=p2;q3=p3;q4=p4;q5=p5; mcost=0; infile>>p1>>p2>>p3>>p4>>p5; cout<<"The best:"<<q1<<" "<<q2<<" "<<q3<<" "<<q4<<" "<<q5<<endl; cout<<"The Sum :"<<bestcost<<endl; infile.close(); outfile.close();结果截图如下：模型建立结果简单分析根本模型已经建立完毕。从题目给的图中我们可以看到，无论是合理的设置缴费点，或者是在原本根底上改迁抑或增设缴费点，地点1都显得相当重要。特别是对于问题34，从外表上看来，按照分析所得改址和增设地址之后，缴费地点显得相对集中。一开始得到这个结论我们小组成员也觉得很奇怪。但通过各地点人数的比拟，可以发现标号靠前的地点所拥有的人数比重比拟大。因此经过初步检查和分析，我们认为这一模型建立以及结果分析根本成立和有效。 模型讨论以及程序优化考虑到该模型可以有更广的适用性，我们小组成员查阅资料，逐步改良了程序算法。利用字典排序法，我们将程序改良为适用于从M个数据中任选N个进行组合，同时利用动态数组及指针组成程序。这样一来，不仅算法本身更加具有严谨性，同时还降低程序的局限性，不再受限制于此题目。只要拥有相应的数据，就能对另一个地区的选址问题进行相关分析。此处，我们运用了字典排序法的定理：令 a1a2ar是1，2，3，.，n的一个r- 组合。在字典排序中，第一个r- 组合是12r 。 最后一个r-组合是n-r+1(n-r+2)n。设a1a2arn-r+1(n-r+2)n。令k是满足ak<n且使得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，使得ak<n且使得ak+1不同于a1，a2，ar。2用r-组合 a1a2ak-1ak+1ak+2ak+ r - k+1替换a1a2ar 。所以，改动的程序段如下：1、产生组合的子程序段:bool listmake:make() / 产生组合的优化 ： 可以实现N取M M<N if(ok=false) return false; unsigned long jiecheng=1; unsigned long change=1; for(int count=summer;count>summer-select;count-) jiecheng=jiecheng*count; for(int count=select;count>0;count-) change=change*count; jiecheng=jiecheng/change; ofile<<jiecheng<<endl; / 组合个数 int* seat = new intselect; for(int i=0;i<select;i+) seati=i+1; bool pass=true; while(pass) int j=select-1; for(;j>=0;j-) bool find=false; if(seatj+1>summer ) continue; int k=0; for(;k<select;k+) if(seatj+1)=seatk) find=true; break; if(!find) break; int m=0; for(;m<select;m+) ofile<<seatm<<" " ofile<<endl; m=1; int temp=seatj; for(;j<select;j+) seatj=temp+m; m+; m=summer-select+1; bool equal=true; for(j=0;j<select;j+) if(seatj!=m) equal=false; break; m+; if(equal) pass=false; int m=0; for(;m<select;m+) ofile<<seatm<<" " ofile<<endl; delete seat; return true; /字典排序 生成组合2、主程序改动内容：void matrix:final() /M 求 N ifstream infile("list.dat"); ofstream outfile("listcost.txt"); int* p=new intsetpoint; int* q=new intsetpoint; long mcost=0; long bestcost=9999999; int sum; infile>>sum; / 读文件 for(int count=0;count<setpoint;count+) infile>>pcount; qcount=pcount; for(int i=1;i<=sum;i+) long temp; for(int j=0;j<point;j+) temp=shortestj*point+p0; for(int count=0;count<setpoint;count+) /选出某点到各个设置点距离中最短的一个 if(temp>shortestj*point+pcount) temp=shortestj*point+pcount; mcost+=temp; for(int count=0;count<setpoint;count+) outfile<<pcount<<" " outfile<<mcost<<endl; if(mcost<bestcost) /比拟得出最优组合 bestcost=mcost; for(int count=0;count<setpoint;count+) qcount=pcount; mcost=0; for(int count=0;count<setpoint;count+) infile>>pcount; cout<<"The best : " for(int count=0;count<setpoint;count+) cout<<qcount<<" " cout<<endl; cout<<"The Sum :"<<bestcost<<endl; infile.close(); outfile.close(); delete p; delete q; 参考文献1、?运筹学? 清华大学出版社2、?数据结构根底? 清华大学出版社 Ellis Horowita , Sartaj Sahni 著3、?离散数学及其应用? 机械工业出版社 美 Kenneth H.Rosen 著 4、?组合数学? 机械工业出版社 美Richard A.Brualdi 著附 录程序代码改良前代码段#include<iostream>#include<fstream>using namespace std;class matrix public: matrix(); matrix(); public: void paths(); void load(); 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;i<18;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;i<18;i+) for(int j=0;j<18;j+) infile>>costij; infile.close(); infile.clear(); infile.open("number.txt"); infile>>point>>setpoint; infile.close(); infile.clear(); infile.open("people.txt"); for(int k=0;k<18;k+) infile>>peoplek; infile.close();int matrix:choose() / int i,min=2000,minpos=-1; for(i=0;i<point;i+) if(distancei<min && !foundi) min=distancei; minpos=i; return minpos;void matrix:paths() /最短总路程 = 该点人数* 该点到另外一点的最短距离 shorteststarttemp=distancetemp*peoplestart; int i,u,w; for(i=0;i<point;i+) foundi=false; distancei=coststarti; foundstart=true; distancestart=0; for(i=0;i<point-2;i+) u=choose(); foundu=true; for(w=0;w<point;w+) if(!foundw) if(distanceu+costuw<distancew) distancew=distanceu+costuw; for(int temp =0;temp<18;temp+) shorteststarttemp=distancetemp*peoplestart; void matrix:show() / 输出 for(int i=0;i<18;i+) for(int j=0;j<18;j+) cout<<shortestij<<" " cout<<endl; void matrix:final4() / 18选4 ifstream infile("list4.dat"); ofstream outfile("list4cost.txt"); int p1,p2,p3,p4; int q1=0,q2=0,q3=0,q4=0; long mcost=0; long bestcost=69999; int sum; infile>>sum; infile>>p1>>p2>>p3>>p4; q1=p1;q2=p2;q3=p3;q4=p4; for(int i=1;i<=sum;i+) long temp; for(int j=0;j<18;j+) temp=shortestjp1; if(shortestjp1>shortestjp2) temp=shortestjp2; if(temp>shortestjp3) temp=shortestjp3; if(temp>shortestjp4) temp=shortestjp4; mcost+=temp; outfile<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<" "<<mcost<<endl; if(mcost<bestcost) bestcost=mcost; q1=p1;q2=p2;q3=p3;q4=p4; mcost=0; infile>>p1>>p2>>p3>>p4; cout<<"The best :"<<q1<<" "<<q2<<" "<<q3<<" "<<q4<<endl; cout<<"The Sum :"<<bestcost<<endl; infile.close(); outfile.close();void matrix:final5() /18选5 ifstream infile("list5.dat"); ofstream outfile("list5cost.txt"); int p1,p2,p3,p4,p5; int q1=0,q2=0,q3=0,q4=0,q5=0; long mcost=0; long bestcost=69999; int sum; infile>>sum; infile>>p1>>p2>>p3>>p4>>p5; q1=p1;q2=p2;q3=p3;q4=p4,q5=p5; for(int i=1;i<=sum;i+) long temp; for(int j=0;j<18;j+) temp=shortestjp1; if(shortestjp1>shortestjp2) temp=shortestjp2; if(temp>shortestjp3) temp=shortestjp3; if(temp>shortestjp4) temp=shortestjp4; if(temp>shortestjp5) temp=shortestjp5; mcost+=temp; outfile<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<" "<<p5<<" "<<mcost<<endl; if(mcost<bestcost) bestcost=mcost; q1=p1;q2=p2;q3=p3;q4=p4;q5=p5; mcost=0; infile>>p1>>p2>>p3>>p4>>p5; cout<<"The best :"<<q1<<" "<<q2<<" "<<q3<<" "<<q4<<" "<<q5<<endl; cout<<"The Sum :"<<bestcost<<endl; infile.close(); outfile.close();int main() matrix a; a.load(); a.makeall(); a.final4(); return 0;程序段#include<iostream>#include<fstream>using namespace 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() ifile>>summer>>select; if(!(summer<=select)|(summer<=0)|(summer>255)|(select<=0) ok=true; else cout<<"enter error"<<endl;listmake:listmake() 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;list2<=summer-1;list2+) for(list3=list2+1;list3<=summer;list3+) ofile<<list0<<" "<<list1<<" "<<list2<<" "<<list3<<endl; shumu+; ofile<<shumu; 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;list3+) for(list4=list3+1;list4<=summer;list4+) ofile<<list0<<" "<<list1<<" "<<list2<<" "<<list3<<" "<<list4<<endl; shumu+; ofile<<shumu; else cout<<"not support"<<endl; return true;int main() listmake ls; ls.init(); ls.make(); return 0;改良后程序段如下：#include<iostream>#include<fstream>using namespace std;class matrix public: matrix(); matrix(); public: void paths(); 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;/数组 各城市人数 ;void matrix:makeall() for(int i=0;i<point;i+) start=i; paths(); matrix:matrix() ok=true; ifstream infile; infile.open("number.txt"); infile>>point>>setpoint; 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:initstart(int n)start=n-1;void matrix:load()/初始化数据 ifstream infile; infile.clear(); infile.open("matrix.txt"); for(int i=0;i<point;i+) for(int j=0;j<point;j+) infile>>costi*point+j; infile.close(); infile.clear(); infile.open("people.txt"); for(int k=0;k<point;k+) infile>>peoplek; infile.close();int matrix:choose() int i,min=2000,minpos=-1; for(i=0;i<point;i+) if(distancei<min && !foundi) min=distancei; minpos=i; return minpos;void matrix:paths() / 算法 求最短路径 int i,u,w; for(i=0;i<point;i+) found