数学建模所得税交纳点选址.doc

b题：所得税交纳点选址所得税管理部门计划对某个地区中的所得税交纳点网络进行重新设计。图b.1是对此地区内的城市和主要道路的示意图。城市旁边的黑体数字表示城市的居民数目，单位为千人。在连接城市之间的弧上标出了它们之间的距离，单位为千米（斜体字）。为覆盖各个城市，所得税管理部门决定在三个城市中设置纳税点。应在哪三个城市中设置纳税点才能够使居民与最近的纳税点之间平均距离最小？图b.1：此区域内的城市和道路图 所得税交纳点选址摘要随着我国各地居民区的增加，及经济发展带来的高收入，纳税成为了国家财政收入的一大部分，税收作为国家经济杠杆之一，具有调节收入分配、促进资源配置、促进经济增长的作用。 纳税是国家财政收入的主要来源，国家用收来的税款发展经济、科技、教育、文化和国防等事业。纳税点选址问题属于最佳选址问题，选址应用非常广泛，所得税缴纳点选址只是一个应用领域。选址问题是一种长期决策，它的好坏直接影响到服务方式，质量，效率，成本。能影响到利益与市场竞争力。所以选址问题有着重大的经济社会意义。选址问题研究的典型例如weber问题，中值问题，覆盖问题，中心问题，多目标选址，竞争选址，不受欢迎的选址，选址-分配，选址-路线等。随着选址理论的发展，很多种中心选址的方法被开发出来，归结起来主要可分为五种方法：解析方法，最优化线性方法，启发方法，仿真方法以及综合因素评价法，遗传算法，随即分析，模糊数学分析等等。关键词：所得税缴纳点 选址 最短路径 c+ 模型模型的符号说明 符号符号说明g赋权图g=（v，e）v顶点集e链接g各顶点的边集hi顶点vi的权重dxy链接顶点x和y的最短路径模型分析建立及求解1. 模型预处理将各城市看成是图的结点，他们人口数量作为顶点的权重，链接它们的道路看成是图中的弧，则整个地区就可以抽象成一个无向的带权图g。对给定一个无向带权图g=（v，e），其中v=v1,v2，.vn是非空顶点集，e=e1，e2，.en是连接g各顶点的边集，hi为顶点vi的权重， g中的任何顶点a，b，dab为代表连接a点和b点最短路径。 2. 算法描述首先，题目要求的是纳税点间平均距离最短，可以利用floyd算法实现2点间距离最短。对于所有两点之间无直接连线的，距离dab均算作正无穷（表中以代替）。对任意节点a，daa为0。对于所有弧c=（a,b），dab为弧长。对于任意b,c,d三个结点，若有dcddbc+dcd；则将dbc+dcd的值赋给dcd， 具体列出v1与其他各点的邻接矩阵，求出v1到各点的最短路径：v1015241815022220181620180122416012241201222180152212150302520241230019192201925191902219210推广至所有节点，可算出对于任意x,y，dxy的最小值，也就是最短路径。如下表所示：1234567891011121015375524691833484958672150224038523348425561613372201816304328205839394554018034126146246243345243816340362712244937436605230123605742125031327183343612757015452240618334828461242150303725469484220242412453003819401040555862495022373801940115861394337314025191902112676139344322614619402103. 建立模型1纳税点在城市a建立与否只有两种可能，故使用0-1规划模型xa=0表示不在城市a建立纳税点；xa=1表示在城市a建立纳税点。2城市a的居民是否会到纳税点b纳税设置变量yabyab=0表示不会到此地纳税；yab=1表示会到此地纳税。3. 变量yab计算每个居民到最近纳税点的平均距离，并找出城市与纳税点之间的依赖关系。4应开设n个纳税点使5每个城市的居民只能到一个纳税点交税6最小化每个城市居民人数加权距离的总和，除以居民总人数，得到每个居民到最近纳税点的平均距离/1857考虑到会有城市没有分配纳税点，增加约束条件xa=0 = yab=0，即yabxa。以上为数学模型。具体的编程思路为： 此处运用c+枚举法，以此计算c312种情况，把每次情况选出的三个点和其他它点最短路与每点的人数相乘，然后叠加，最后除以总人数得出平均距离，取平均距离中最小的即为结果输出。最短路径运用floyd算法上面算法部分已阐述。赋权图用邻接表存储，避免了邻接矩阵存储大量0及正无穷消耗大量的空间。4. 程序实现#include using namespace std;const int infinite=10000;class edgepublic:int from,to,weight;edge()from=-1;to=-1;weight=0;edge(int f,int t,int w)from=f;to=t;weight=w;bool isedge(edge oneedge)if(oneedge.weight0&oneedge.to=0)return true;else return false;class graphpublic:int numvertex;int numedge;int *mark;int *indegree;graph(int numvert)numvertex=numvert;numedge=0;indegree=new intnumvertex;mark=new intnumvertex;for(int i=0;i0&oneedge.to=0)return true;else return false;/用邻接表存储图struct listunitint vertex;int weight;template class linkpublic:t data;link *next;link(t ele,link *nextvalue=null)data=ele;next=nextvalue;link(link *nextvalue=null)next=nextvalue;template class llistpublic:link *head;llist()head=new link();class graphl:public graphprivate:llist *gralist;public:graphl(int numvert);graphl()delete gralist;edge firstedge(int onevertex);edge nextedge(edge preedge);bool setedge(int from,int to,int weight);graphl:graphl(int numvert):graph(numvert)gralist=new llistnumvertex;edge graphl:firstedge(int onevertex)edge myedge;myedge.from=onevertex;link *temp=gralistonevertex.head;if(temp-next!=null)myedge.to=temp-next-data.vertex;myedge.weight=temp-next-data.weight;return myedge;edge graphl:nextedge(edge preedge)edge myedge;myedge.from=preedge.from;link *temp=gralistpreedge.from.head;while(temp-next!=null&temp-next-data.vertexnext;if(temp-data.vertex=preedge.to&temp-next!=null)myedge.to=temp-next-data.vertex;myedge.weight=temp-next-data.weight;return myedge;bool graphl:setedge(int from,int to,int weight)link *temp=gralistfrom.head;while(temp-next!=null&temp-next-data.vertexnext;if(temp-next=null)temp-next=new link;temp-next-data.vertex=to;temp-next-data.weight=weight;numedge+;indegreeto+;return true; if(temp-next-data.vertex=to)temp-next-data.weight=weight;return false;if(temp-next-data.vertexto)link *other=temp-next;temp-next=new link;temp-next-data.vertex=to;temp-next-data.weight=weight;temp-next-next=other;numedge+;indegreeto+;return true;void creategraph(graphl *g,int nv)int i;int ne;int tail,head,weight;docoutne;if(ne=0)break;else cout输入错误 弧的数目应在0-nv*(nv-1)/2之间(nv*(nv-1)/2);cout请分别输入每条弧的弧尾 弧头 权值endl;for(i=0;ine;i+)cout第i+1tail;cinhead;cinweight;if(tailnv|headnv|head=tail)cout输入无效 请重新输入setedge(tail-1,head-1,weight)=false|g-setedge(head-1,tail-1,weight)=false)cout改变了已有弧的权值endl;i-;continue;cout创建成功numvertex;for(i=0;inumvertex;i+)di=new distg-numvertex;for(i=0;inumvertex;i+)for(j=0;jnumvertex;j+)if(i=j) dij.length=0;dij.pre=i;elsedij.length=infinite;dij.pre=-1;for(v=0;vnumvertex;v+)for(edge e=g-firstedge(v);g-isedge(e);e=g-nextedge(e)dve.to.length=e.weight;dve.to.pre=v;for(v=0;vnumvertex;v+)for(i=0;inumvertex;i+)for(j=0;jnumvertex;j+)if(dij.length(div.length+dvj.length)dij.length=div.length+dvj.length;dij.pre=dvj.pre;coutendl每对顶点之间的最短路径矩阵：endl;for(i=0;inumvertex;i+)for(j=0;jnumvertex;j+)if(dij.length10) coutdij.length ;else coutdij.length ;coutendl;coutendl交税点分配示意：numvertex;dist *allc=new distg-numvertex;int pop=0;for(i=0;inumvertex;i+)pop=pop+populationi;for(i=0;inumvertex;i+)alli.index=i;alli.length=infinite;alli.pre=0;allci.index=i;allci.length=infinite;allci.pre=0;for(v=0;vnumvertex;v+)for(i=v+1;inumvertex;i+)for(j=i+1;jnumvertex;j+)temp=0;for(k=0;knumvertex;k+)if(dkv.length=dki.length)allk.length=dkv.length;allk.pre=v;elseallk.length=dki.length;allk.pre=i;if(dkj.lengthallk.length)allk.length=dkj.length;allk.pre=j;for(k=0;knumvertex;k+)temp=temp+allk.length*populationk;if(sumtemp) sum=temp;for(k=0;knumvertex;k+)allck.length=allk.length;allck.pre=allk.pre;for(k=0;knumvertex;k+)coutk+1 ;coutendl;for(k=0;knumve