选址问题数学模型

建立合理的派出所；市领导人巡究对象时，为了突出与求解目标进行抽象、化简，并用图来描了简化问题，突出要点，以便更，再经过计算可得到本问的派出所管辖围m济社，各个社区对应人口(单位：千人)如表1-1：ABCDEFGHIJKL6487MNPQRSTUVWXY8987VVD7T6U98L9CXFGN69M8KHP9SAQ7RWBI(注：横线上的数据表示相邻社区之间的距离，单位：百米)号意义第j个社区的居民人口数度社区j是否到社区i缴费是否在社区i设置缴费站衡度kRjDijija0Lkiilkck边e的边权i点v的点权ikj=1,2,...24；k=1,2,3；围覆盖所有的区域,在考虑具体目标时,一是从快速反应或者公平性考虑,要求要求分三组(路)巡视，得到总路程最短且各组尽可能均衡的巡视路线，可，点W出发，行遍所有顶点至少一次，使得总权(路程)最小.解决此类问题的一方法是不现实的，本题可使用近似算法来求得近似最优解.社区社区编号从该社区出发的道路数与该社区直接相连的社区编号及道路长度(百米)A3CS，X(16)B3XC5A(24)，D(11)，E(9)，T(10)，W(15)D3CQ)，S(8)E4CFT6)，U(9)F6E(8)，L(10)，U(14)，W(11)，G(11)，Y(11)G3FI0)，W(15)H4M(15)，P(19)，K(11)，Y(8)I4B)，P(19)，G(10)，Y(25)J3LNU8)K3M(12)，H(11)，P(23)L4FJ)，Y(10)，M(9)M4N(6)，L(9)，H(15)，K(12)N2M(6)，J(6)P3H)，I(19)，K(23)Q3RDV10)R2S3A(20)，D(8)，R(12)T3CEV(7)U4EF)，J(8)，V(15)V3QTU(15)W5B22)，C(15)，F(11)，G(15)，X(8)X3A6)，B(18)，W(8)Y4F(11)，H(8)，I(25)，L(10)050人千/口15人各社区人口统计图ABCDEFGHIJKLMNPQRSTUVWXY社区1)利用社区间道路信息，构造邻接矩阵L。若城市i和j间无直接连通的道路，则令(i,j)元素a为正无穷大；否则L=|21222n|Laaa」n1n2nn构构造2)获得两社区间距离矩阵D。D、R的(i,j)元素分别表示为D、R(i=1,2,,24;j=1,2,,24)，对于ijij所有的城市i、j和k，如果D>D+D，则令D=D+D，R=k(表ijikkjijikkjij示从城市i到j要经过城市k，若Rij=0，表示两城市可直达)。经过matlab和两社区邻接接矩LL阵jijijjj=1根据模型假设(4)可知，每个社区的居民只能到附近最近的一个缴费站缴费，缴费站，根据模型假设(3)可知，只能在社区设置3个煤气缴费站，所以有约束条件为：P=313)模型流程图如下：社区间主要道路Floyd算法各社区居民数社区间的最短路径和最短路径距离矩阵选择其中三个社社区间的最短路径和最短路径距离矩阵确定各社区所属缴费站0-1规划穷举法计算平均距离获得最优解进一步讨论模型的有效性和推广性jj=1QWMDQ，R，S，T，VA，B，C，E，F，G，I，W，XH，J，K，L，M，N，P，V，Y根据上面求最短路径求出的任意两点的最短距离矩阵D,可以看出K到S的最短距离最长，D=66百米，要使能在3分钟有警察(警车的时速为50km/h)DLN要求的情况下覆盖整N>3minN4增加了一个约束条件：Dijij25，即保证警察在3分钟到达事发地。j=1目标函数：minN用MATLAB软件编程计算(见附录三，模拟程序二)应设派出所三个，有(千人)总路程(单DD，Q，R，V，T，C,S,E(千人)总路程(单位：RRRVVT，SWGG132368KMMNN管辖人口数(千总路程(单QD，Q，R，S，T，V，C，UWA，B，E，F，G，I，X，WKH，J，K，L，M，N，P，Y(1)方案一和方案二其管辖围的人口分布量不均匀；(3)方案一，二，三其人口均衡度分别是36.52%、45.45%、19.23%，故第三7DX98614LFW815GIBN69MY8KH派出所三P97派出所一RSA派出所二UVT实际路程均衡度:a=mi,ajx|o(li)-o(lj)|0mxo(li)00kkkkk|min[ax(l)-min(l)]kkkiminl=nw(e)(i=1,2,,n)kii=1minamaxlkminlkk3)(n|minlkw(ei)(i=1,2,,n)〈|mina=max(lk)-min(lk)|max(lk)VV739CU96E8F8J8LYN56MKGH6IBP94SA7RXD(2)分解所得的三个子图包含的顶点数尽可能接近8个；(3)尽量使分解所得的子图为连通图；(4)尽量使子图与W的最短路上的点在该子圈，尽量使各子图部形成环路。VV739CU96E8F8J8LYN56MKGH6IBP94SAQ7RXD佳巡WFG,I,B,X,A,X,WWCT,V,U,Q,R,Q,S,D,C,WWFL,J,N,M,K,P,H,Y,F,W1)模型的优点2)模型的缺点时间复杂度；也可以用J7ABCDEFGHIJKLA0B0C09D0E908F80G0H0I0J08K0L80M9N6PQ9RS8T6U98VWXY8MNPQRSTUVWXYAInfInf20InfBInfInfInfInfCInfInfInf10DInf9Inf8InfEInfInfInf69FInfInfInfInfGInfInfInfInfH15InfInfInf8IInfInfInfInfJInf6InfInfInf8K12InfInfInfL9InfInfInfM06InfInfInfN60InfInfInfPInf0InfInfInfQInf07InfInfRInf7012InfSInf120InfTInfInfInf07UInfInfInfInf0VInfInfInf70WInfInfInfInf08XInfInfInfInf80YInfInfInfInf0ABCDEFGHIJKLA0333539B340413337C09D0E908F80G0H0I0J08K0L80M9N6PQ9RS8T6U98VWXY8MNPQRSTUVWXYABCD98E69FGH8IJ68KL9M06N60P0Q07R70S0T07U0V70W08X80Y0clearR=[1012186101548711131111892214871015281813];n=24;a=zeros(n);a(1,3)=24;a(1,18)=20;a(1,23)=16;a(2,23)=18;a(2,22)=22;a(2,9)=28;a(3,5)=9;a(3,19)=10;a(3,4)=11;a(3,22)=15;a(4,16)=9;a(4,18)=8;a(5,19)=6;a(5,6)=8;a(5,20)=9;a(6,7)=11;a(6,24)=11;a(6,12)=10;a(6,20)=14;a(6,22)=11;a(7,9)=10;a(7,22)=15;a(8,15)=19;a(8,11)=11;a(8,13)=15;a(8,24)=8;a(9,15)=19;a(9,24)=25;a(10,12)=8;a(10,14)=6;a(10,20)=8;a(11,13)=12;a(11,15)=23;a(12,24)=10;a(12,13)=9;a(13,14)=6;a(16,17)=7;a(16,21)=10;a(17,18)=12;a(19,21)=7;a(20,21)=15;a(22,23)=8;a=a+a';%Floyd算法求每对顶点之间的最短距离M=max(max(a))*n^2;%M为充分大的正实数d=a+((a==0)-eye(n))*M;path=zeros(n);fork=1:nfori=1:nforj=1:nifd(i,j)>d(i,k)+d(k,j)d(i,j)=d(i,k)+d(k,j);path(i,j)=k;%确定缴费站的位置L=[];L1=[];L2=[];S=[];S(1)=0;k=2;forx=1:24fory=1:24forz=1:24forn=1:24L(1)=d(n,x);L(2)=d(n,y);L(3)=d(n,z);L1(n)=p(n)*min(L);S(k)=sum(L1)/sum(R);b=1:k-2;if(S(k)<S(k-b))L2(1)=x;L2(2)=y;L2(3)=z;k=k+1;fori=1:k-2S(i)=S(i+1);Smin=min(S);%最小平均距离wz=L2;%缴费站的位置fprintf('最小平均距离:')disp(Smin)fprintf('缴费站的位置:')clearn=24;a=zeros(n);a(1,3)=24;a(1,18)=20;a(1,23)=16;a(2,23)=18;a(2,22)=22;a(2,9)=28;a(3,5)=9;a(3,19)=10;a(3,4)=11;a(3,22)=15;a(4,16)=9;a(4,18)=8;a(5,19)=6;a(5,6)=8;a(5,20)=9;a(6,7)=11;a(6,24)=11;a(6,12)=10;a(6,20)=14;a(6,22)=11;a(7,9)=10;a(7,22)=15;a(8,15)=19;a(8,11)=11;a(8,13)=15;a(8,24)=8;a(9,15)=19;a(9,24)=25;a(10,12)=8;a(10,14)=6;a(10,20)=8;a(11,13)=12;a(11,15)=23;a(12,24)=10;a(12,13)=9;a(13,14)=6;a(16,17)=7;a(16,21)=10;a(17,18)=12;a(19,21)=7;a(20,21)=15;a(22,23)=8;a=a+a';%Floyd算法求每对顶点之间的最短距离M=max(max(a))*n^2;%M为充分大的正实数d=a+((a==0)-eye(n))*M;path=zeros(n);fork=1:nfori=