缴费点选取两种算法.doc

目录一 摘要二 问题的重述2.1基本情况及相关信息2.2需要解决的问题三 模型假设四 基本符号说明五 问题的分析5.1缴费点选址的步骤5.2问题一的分析5.3问题二的分析5.4问题三的分析5.5问题四的分析六模型的建立和求解6.1模型的建立6.2模型的求解七问题的求解.问题一.问题二.问题三.问题四八模型评价及改进.1模型的优点.2模型的缺点.3模型的改进九参考文献附件所得税缴费点选址问题一. 摘要选址是工程建设与日常生活中经常遇到的问题，在何处选址是各个领域的决策者都要面临的一个极为重要的决定。对于服务业而言，其选址是否合理决定着其能否实现利益的最大化，例如餐饮店，超市在选址时就会主要考虑其所选的地址是否满足人流量大，靠近人口居住的稠密区，交通便利以及有利于其自身的长远发展等等因素。而对于像医院，缴费点，消防站等以服务群众为宗旨的公共服务设施，在选址时，需要考虑所选择的地址能够给予群众最大的方便，以医院的选址为例，其所选地址应考虑靠近人口分布较稠密的地区，并且所在地区的交通也应便利。由此我们可以看出，只有合理的选址才能最大化的方便于民。现要对某个区域中的缴费点进行重新设计，为了便于处理此规划模型中的数据，利用图论相关知识，将题目给出的简化图看做一个带权无向简单图，求出其带权邻接矩阵，然后以Matlab为平台利用Floyd算法求出最短距离矩阵。得到最短距离矩阵后，带入规划模型中，结合lingo和matlab软件进行求解，从而给出题目的解答。关键字：运筹学与控制论；选址；图论；Floyd算法； 二.问题的重述2.1基本情况及相关信息 所得税管理部门计划对某个区域中的缴费点进行重新设计。该区域原来有4各缴费点，分别位于图1的2,6,13,15位置。图1是该区域的一个实际简化，其中连接线表示有道路相通，连接线上数字表示两地距离（单位百米），圆圈内数字是位置序号。各点代表的居民数见表1。 表1各点居民数（单位千人）位置123456789人数504545484040363232位置101112131415161718人数3030362520152010102.2需要解决的问题(1) 给出合理选址的标准(2) 根据合理选址的标准,分析原来的地址是否合理(3) 若要考虑迁移一个缴费点,应该迁移哪个缴费点,迁到哪里(4) 如果在原方案中增加一个新的缴费点,最好应该设在哪里三.模型假设1.假设每个居民区都是理性化的质点。2.假设从居民区到各个缴费点之间的道路保持畅通, 距离不会发生改变，即不考虑其他突发事件的影响，居民区的居民可以直达缴费点。3.假设每个居民区的人数保持不变。4.假设每个居民区的人会选择距离最近的缴税点缴税。5.假设同一个居民区的居民只能到一个缴费点进行缴费。四.基本符号说明符号含义区域区域的人数和的距离区域特征值区域关系矢量G带权无向简单图A(G)带权邻接矩阵X图G的顶点集（区域集合）W图G的权（距离集合）E图G的边集，道路集合D图G的最短距离矩阵五.问题的分析5.1缴费点选址的步骤选址问题的步骤如下图所示：分析题意收集整理资料确定选址标准建立并求解数学模型确定选址方案复查结果是否通过？确定最终结果是是5.2问题一的分析由于各个居民区人数不等,为了体现公平性和效率性,在考虑到缴费点到各个居民点距离长度的基础上,还要将居民点的人数作为该区域的权重,计算每一个居民点至其它各个居民点的路径长度的加权和,使其最短,从而使选址合理化。5.3问题二的分析若要根据指定的标准，分析选址的合理性，首先要将居民区的分布图用图论的相关知识进行转化,在此基础上建立基于点搜索的多目标优化模型,运用数学软件求解模型。将求解出的最优点与原来的选址进行分析，得出其是否合理。5.4问题三的分析 若要考虑迁移一个缴费点，将四个缴费点视作变量，利用穷举法对四个变量中的任意三个变量赋予特定值，分别求出在合理性条件的约束下第四个变量的最优值，将各种情况下居民到缴费点的距离之和进行比较，总距离最小的情况即四种选择中的最优解，即可得出应当迁移哪个缴费点。5.5问题四的分析若要增加一个新的缴费点，则该问题基于问题一的标准，即增加一个点后，使得居民到达五个缴税点的距离之和最短。仍采用已建立的模型，只需修改模型中的约束条件，进行求解，即可得出相应的答案。六模型的建立和求解6.1模型的建立 设X=,为n个区域，区域有居民人，相邻区域和的距离为,现在选择m个区域建立所得税缴费点，使得居民到最近的所得税缴费点的平均距离最小。这里的平均距离指的是每个区域中的居民人与他们到最近的缴费点之间的距离的乘积之和除以所有小区居民的总人数，即 由于人口总数为一个定值，因此只需考虑。 考虑在n个区域中建立m个所得税缴费点来满足目标函数，设 为区域的特征值 1，在区域建立所得税缴费点 0，不在区域建立所得税缴费点并且设区域关系变量 1，区域的居民到区域缴费 0，区域的居民不到区域缴费此时目标函数就即为min()。由于所得税缴费点只能选取m个，故 同时，同一个小区的居民只能到一个缴费点缴费，故 当缴费点设在区域，即= 1时，其他区域(ij)的居民可以到区域缴费，也可以不到区域缴费，此时 = 0或1；但当缴费点没有设在区域，即= 0时，其他区域(ij)的居民一定不能到区域缴费，此时所有 = 0。由此可知，综上所述，建立如下数学模型：6.2模型的求解对于题目给出的所得税缴费点选址简化图，可将该简化图视作一个带权无向简单图G( X,E,W )，其中X = ,为G的顶点集,即所有区域的集合； E = , ,为G的边集，即相邻区域和间道路的集合；W = ,为G的权，表示相邻区域和间距离的集合。图中各区域相应的居民数分别为r= 50 45 45 48 40 40 36 32 32 30 30 36 25 20 15 20 10 10直接求出该带权无向简单图的带权邻接矩阵A(G)，A(G)中元素表示相邻区域和之间的距离，用表示两区域间不连通。0,20,18,18,15,20,0,26,28,30,28,30,30,18,26,0,20,20,26,18,20,0,18,18,50,18,15,28,18,0,38,32,18,0,36,50,38,0,34,32,0,36,30,36,0, ,28,0,30,30,30,0,26,32,30,20,26,0,28,32,28,0,32,26,32,0,34,34,0,24,36,18,24,0,30,36,30,0,32,36,34,32,06求得A(G)后，在matlab中编程利用Floyd算法求出任意两区域点之间的最短距离矩阵，将其记为D。(程序代码见附件)目标函数： minf()约束条件： ， ， ， 0,1 。 数学模型如下：minf() ，s.t. = ， ， 0,1 。按以上模型，在软件lingo中编程，利用计算机辅助软件求出合理选址的最优解，可到如下结果：其中C表示是否选择某个区域作为所得税缴纳点，1表示选择，0表示不选择。从结果可看出，要使得居民到最近的所得税缴费点的平均距离最小，则最合理的选址方案为（2,4,7,12），即选择区域2，区域4，区域7和区域12为所得税缴费点。七问题的求解问题一 为了使选址合理化，给出如下选址标准：通过对各居民区的载荷（人口数）加权，求出每一个居民点至其它各个居民点的最短路径长度的加权和，使得加权求和达到最小。并采用多目标方法，充分体现公共服务设施的公平性和效率性，要求缴费点覆盖需求点的总权重最大，同时从缴费点的使用效率出发，要求居民区到缴费点的总加权距离最小。问题二题目中的选址方案为(2,6,13,15)，根据上述模型的求解结果，在问题一中给定的选址标准下的，最佳的选址方案为(2,4,7,12), 显然题目中给定的方案不是最合理的。为了求出在具体每种选址方案下所有居民到最近缴费点缴费所需行走的最短总路程(这与居民到最近的所得税缴费点的最小平均距离等价)，我们在Matlab中编程解决这一问题，部分结果如下：选址方案最短总路程(m)最小平均距离(m/千人)(2,6,13,15)1399824.8191(2,4,7,12)(最优解)1085019.2376从以上计算结果进一步看出，当选址方案为题目中给出的(2,6,13,15)时，居民到最近的所得税缴费点的最小平均距离为24.8191（m/千人），而当选择最优选址方案(2,4,7,12)时，居民到最近的所得税缴费点的最小平均距离将缩短到19.2376(m/千人)，这在实际生活中将大大方便居民的生活。问题三由于共给定了四个缴费点，故共有四种迁移方案，每种方案下迁移一个缴费点而其余三个缴费点是即定不变的，可以利用穷举法分别计算每种迁移方案下可迁移到的最优点及此时所有居民到最近缴费点缴费所需行走的最短总路程，通过比较得出最优方案。数学模型已在上文中给出，根据数学模型在matlab中的编程，事实上只需在问题二中程序的基础上稍加修改即可，因为现在有三个点是固定不变的，故程序代码中将这三个点分别赋予相应值即可。运行程序，结果如下：迁移点迁移到迁移后的选址方案最短总路程21（1,6,13,15）1343464（2,4,13,15）12248135（2,5,6,15）12286154（2,4,6,13）12098由以上结果可知，若只考虑迁移1个缴费点，则最合理的选择为将区域15的缴费点迁移到区域4，因为在四种方案中，此方案下所有居民到最近缴费点缴费所需行走的总路程最短，进而使得在其余三个缴费点不变的情况下，居民到最近缴费点缴费所需行走的平均路程尽可能地最短。问题四由于选址个数增加为五个，故将数学模型修改如下：minf()，s.t. = ， ， 0,1 在matlab中编写程序，选址个数为五，且使得所有居民到最近缴费点缴费所需行走的总路程最短，这五个点中四个点是给定的，即题目给出的(2,6,13,15)。编程运行后结果为5，即在(2,6,13,15)四个点不变的情况下，增加一个缴费点区域5，能使得居民到最近缴费点缴费所需行走的平均路程最短，此时选址最合理。八模型的评价及改进.1模型的优点（1）模型从居民的利益出发，并以方便居民为目标，通过对各个居民点的人口数加权，从而使得每个居民到达缴费点的平均距离最短。求解时通过matlab环境建立二维矩阵，然后根据优化模型，利用LINGO把数学模型转译成计算机语言，借助于计算机来求出最优解，从而把人从复杂的运算中解放出来。 （2）模型适用范围广，该模型适用于诸如医院急救站、巡逻警点、物流配送等的类似的规划建设，只需将参数或约束条件做相应的修改即可。（3）算法简单易懂，通用性强，得到的结果可靠性高。.2模型的缺点本文中给出的评价标准总体比较合理，但判定指标有限，且各个居民区人数情况会有变动，数据具有一定的局限性，同时由于道路状态会发生变动，某些道路可能由于施工或其他非可抗拒因素而阻塞，此时居民不能选择最近的点缴费，此模型考虑的情况比较简单。.3模型的改进 由于居民区的人数是变动的，是一个动态系统，每个时刻不停的有居民的流入、流出，因为该问题没有时间的后效性，因此可以用马尔科夫链来描述这种动态的转移过程。首先需要确定系统中的居民的状态集，在计算出各个状态之间的转移概率，这样能得到每种状态下，处在这个居民点的人数和要移入这个居民点的人数。 同时由于居民点的人数没有确切的来源，所以可能导致建立模型出来的结果与事实不相符。鉴于现状以此为切入点，将路径规划和缴费点选址相结合，研究居民点分布和缴费点选址的综合问题。另外，在建立次模型时采用的是定量分析，将定量分析和定性分析相结合并在定性分析中引入增加不确定因素的分析，是进一步优化的方向。参考文献耿素云 屈婉玲 张立昂，离散数学（第四版），北京：清华大学出版社，2008年姜启源 谢金星 叶俊，数学模型（第三版），北京：高等教育出版社，2003年梅索，毛洪振，赵东方, 中国科技论文:基于Floyd算法的社区服务中心的选址问题, 2009年1月第1期王瑞，孙圆圆，胡梦宁，水厂选址的最优化问题，年月附件（） matlab 用Floyd算法求最短距离矩阵function D,R=Floyd(a) % 输出矩阵D为各点间最短距离，矩阵R为最短路径。 % Floyd算法求最短路径，输入矩阵%为各点的带权邻接矩阵，Inf表示两点不通。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;double D,R=floyd(a);n=size(a,1); D=a; for i=1:n for j=1:n Ri,j=num2str(i), num2str(j); 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,j)=D(i,k)+D(k,j); l=length(Ri,k)-length(num2str(k);Ri,j=Ri,k(1:l),Rk,j; end end end end（） 利用lingo求解模型model:sets:p/1.18/:w,c; !w为各区域居民数，c为最终的选址情况;m(p,p):v,x; !v为距离矩阵，x为对应关系;endsetsdata:v=0201818153653475048503866446036667220026382856666030283030585280568692182602033387065565446204826603868741838200181850506866664068464218485415283318036383258565853815960366672365638183606868868484588664603666365366705038680709694969011896926866344760655032687003688908511391926898104503056685886963605860608882110861161224828546656849488580305662801088411412050304666588496906030026326498841141203830204053589085605626028468058889466584868818611811388623228032668610212244522646596496918280644632034587010060806042606092921101089880663402436683656381836366868868484588658240306266866848666666981161141148810270363003272927454723634104122120120941221006862320;w=50 45 45 48 40 40 36 32 32 30 30 36 25 20 15 20 10 10 ;enddatamin=sum(m(i,j):w(i)*v(i,j)*x(i,j); !取所有居民到最近缴费点的距离之和的最小值;for(p(i):sum(p(j):x(i,j)=1); !另矩阵x的每一行的和为1，即同一个区域的居民只能到一个缴费点缴费;sum(p:c)=4; !缴费点只能选取4个;for(m(i,j):x(i,j)=c(j); !当c(j)选为缴费点时，区域i可选择它也可不选它，但当c(j)未选为缴费点时，区域i一定不能选其为缴费点;for(m:bin(x); !限制x中的元素为0或1，x(i,j)=1表示区域i居民以区域j为缴费点，x(i,j)=0表示区域i居民不以区域j为缴费点;for(p:bin(c); !限制c中为元素为0或1，c(i)=1表示选择区域i作为缴费点，c(i)=0表示不选择区域作为缴费点;end（） 问题二function E=count(A) %定义count函数，输出矩阵E即为所有情况下所有居民到最近缴费点的最小总距离A=combntns(1:18,4); %列出12个居民点选3个缴费点的所有情况。double E=count(a);for i=1:nchoosek(18,4) %用forend循环计算以上列出所有情况下所有居民需要行走的总路程！A2=A(i,:);A3=A2(1,1); %选取4个区域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=02018181536534750485038664460366672;20026382856666030283030585280568692;18260203338706556544620482660386874;18382001818505068666640684642184854;15283318036383258565853815960366672;36563818360686886848458866460366636;536670503868070969496901189692686634;4760655032687003688908511391926898104;50305668588696360586060888211086116122;48285466568494885803056628010884114120;5030466658849690603002632649884114120;38302040535890856056260284680588894;665848688186118113886232280326686102122;445226465964969182806446320345870100;6080604260609292110108988066340243668;36563818363668688684845886582403062;668668486666669811611411488102703630032;72927454723634104122120120941221006862320; ; %距离矩阵，即居民到其他区域所有最短的距离。B1=B(:,A3); %居民到所选的缴费点的理论最短距离。B2=B(:,A4);B3=B(:,A5);B4=B(:,A6) C=B1 B2 B3 B4; D=sort(C,2); %将C矩阵中的行元素从小到大排列,使即第一列的数据是最小值，即其余14个居民点选择4个缴费点中最佳的一个点。Shortjourney=D(:,1); %每位居民选择缴费点后需要行走的最短路程。 Sum(i)=People*Shortjourney; %所有居民所要行走的路程总和。end E=reshape(Sum,nchoosek(18,4),1); %将以上得到的数组转为矩阵。 minposition=find(E=min(E); %找出最小值在矩阵的位置。A=combntns(1:18,4); position=A(minposition,:) %最佳的缴费点的选择。（） 问题三double E=count(A);for i=1:nchoosek(18,1) if i=2&i=6&i=13 %2,6,13为选定的固定点，此处将其从18个区域中排除（可改变这三个点以计算其他三种情况）A2=A(:,i); %选取1个区域，并读取已固定的3个缴费点A3=A2(1,1); A4=A(:,2)A5=A(:,6);A6=A(:,13);People=50 45 45 48 40 40 36 32 32 30 30 36 25 20 15 20 10 10; %每个居民点的人数的矩阵。 B=02018181536534750485038664460366672;20026382856666030283030585280568692;18260203338706556544620482660386874;18382001818505068666640684642184854;15283318036383258565853815960366672;36563818360686886848458866460366636;536670503868070969496901189692686634;4760655032687003688908511391926898104;50305668588696360586060888211086116122;48285466568494885803056628010884114120;5030466658849690603002632649884114120;38302040535890856056260284680588894;665848688186118113886232280326686102122;445226465964969182806446320345870100;6080604260609292110108988066340243668;36563818363668688684845886582403062;668668486666669811611411488102703630032;72927454723634104122120120941221006862320; %距离矩阵，即居民到其他区域所有最短的距离。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; %所有居民所要行走的路程总和。else Sum(i)=30000 %将Sum(2),Sum(3),Sum(6)赋一个较大值，使其不影响最优点的选取endend E=reshape(Sum,1,nchoosek(18,1); %将以上得到的数组转为矩阵。 minposition=find(E=min(E); %找出最小值在矩阵的位置。value=min(E);A=1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18; position=A(:,minposition) %最佳的缴费点的选择。（） 问题四clear all;A=1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18; %列出18个区域选1个缴费点的所有情况。for i=1:nchoosek(18,1) if i=2&i=6&i=13&i=15 %将已选定的四个点排除A2=A(:,i);A3=A2(1,1); %选取1个区域，并读取已选择的4个缴费点A4=A(:,2)A5=A(:,6);A6=A(:,13);A7=A(:,15)People=50 45 45 48 40 40