所得税交纳点选址问题数学建模论文

所得税交纳点选址问题数学建模论文

摘要

本文对规划类问题中多点选址问题进行了探究。针对所得税选址问题，在已知城市间主要道路及各城市居民数的基础上，设定了一些假设，提出了三种模型，分别为穷举法，智能分区法1和智能分区法2，层次分析法。

模型一：0-1规划的穷举法模型。该模型首先采用改善的Floyd-Warshall算法计算出城市间最短路径矩阵；然后，用0-1规划的穷举法获得模型目标函数的最优解。

模型二：0-1规划的智能分区模型1。该模型考虑了一些普遍情况，在附加的合理的假设前提下，采用按选址数N分区解决问题的方法。该模型首先采用改善的Floyd-Warshall算法计算出城市间最短路径矩阵；然后，用启发式搜索算法将所有城市分为N个独立区域；最后，采用0-1规划求得各区域一个最优纳税点，获得最优解。

模型三：最近邻法智能分区模型。该模型首先根据从各城市出发的道路数和居民数，对城市进行排序，获得N个初始纳税点，称为伪选址点；然后，利用最近邻法，根据其余城市与各个伪选址点的最短距离，对城市进行划分，得到N个分区结果（划分后各区域不需要相互独立，即可能有若干城市属于两个或两个以上区域）。最后，从三个分区结果中分别选取一个城市作为纳税点，利用两点间最短距离矩阵得到其余9点的归属，并结合人口数据得到加权总和，遍历三个分区中的所有组合，将加权和最小的选址点作为最终的选址点（真选址点）。

模型四：区域层次分析模型。该模型首先根据从各城市出发的道路数的多少进行层次分析，对城市进行分层。然后，同样利用层次分析法对居民数的多少进行分层，综合层次分析求解最优解决方案。

模型一，利用穷举法获取得一定是最优解，但该算法随着节点数的增加其复杂度以几何级数增长，计算量最大。但穷举法可以获取最优解，并可以最为验证智能算法有效性的依据。模型二智能分区法1，对本文针对的具体

1

题目是可以获取最优解的，但当改变一下网络拓扑结构或者将人口数变化一下，其获取的可能仅是局部最优解。故模型二的通用性不强。模型三，最近邻法智能分区法是最优算法，该算法在复杂度比穷举法降低10倍左右的时候仍然能获取最优解。该模型受到全局最优点一定在局部最优附近可以找到启发，利用伪选址点进行分区，得到局部最优。在分区上遍历，获取全局最优解。模型四，思路清晰明了，但在面对较大数据时比较复杂，有一定的通用性以及操作局限性。

关键词：多点选址; 0-1规划; 启发式搜索; 最近邻法; 智能分区；层次分析

2

目录

所得税交纳点选址问题数学建模论文 .................................................................................... 1 摘要........................................................................................................................................... 1 目录........................................................................................................................................... 3 1 问题重述 ............................................................................................................................... 4 2 问题的分析 ........................................................................................................................... 5 3 模型假设 ............................................................................................................................... 6 4 模型建立 ............................................................................................................................... 7

4.1模型一：0-1规划的穷举法模型............................................................................... 7 4.2模型二：0-1规划的分区模型 .................................................................................. 9 4.3模型三：最近邻法分区模型 ................................................................................... 12 5问题的求解 ......................................................................................................................... 14

5.1求解过程中采用的主要算法 ................................................................................... 14 5.2问题的具体求解 ....................................................................................................... 19 6结果分析与模型的评价 ...................................................................................................... 26

6.1 结果分析及模型的优缺点 ...................................................................................... 26 6.2 模型的推广 .............................................................................................................. 27 7 参考文献 ............................................................................................................................. 27

3

1 问题重述

所得税管理部门计划对某个地区中的所得税交纳点网络进行重新设计。下图1是对此地区内的城市和主要道路的示意图。城市旁边的黑体数字表示城市的居民数目，单位为千人。在连接城市之间的弧上标出了它们之间的距离，单位为千米（斜体字）。为覆盖各个城市，所得税管理部门决定在三个城市中设置纳税点。

问题：应在哪三个城市中设置纳税点才能够使居民与最近的纳税点之间平均距离最小？

图1 此区域内的城市和道路图

4

2问题的分析

本问题的目标是从一个到多个城市组成区域内中，选出一定数目的城市设置纳税点, 建立所得税交纳点网络，实现居民与最近的纳税点之间平均距离最小。

对于每个城市纳税点的建立与否只有两种可能，所以可以通过计算城市间的最短路径，然后充分利用地区的城市居民以及道路信息，采用合适的方法搜索纳税点；再确定各纳税点管辖的区域，直到求得最优解。本问题重点要解决如何选择纳税点和如何划分纳税区域，即建立合理的最优纳税点搜索和区域划分模型。

由图1，得到地区内城市总数M?12；计划设置的纳税点数目N?3 城市标号Ci?i，i?1,2?,M。

各城市的居民数Rci、城市间道路信息如下表：

表1 各城市的居民数Rci

城市标号 1 2 3 4 5 6 7 8 9 10 11 12 Rci（千人）

15 10 12 18 5 24 11 16 13 22 19 20 表2 道路信息

城市标号 从该城市出发的道路数 1 3 2 2 3 4 4 2 5 4 6 3 5

2（22） 3（18） 1（24） 4（12） 与该城市直接相连2（15） 1（15）的城市标号、及道路5（24） 长度（千米，括号内7（11） 内容） 城市标号 从该城市出发的道路数 3（20） 7（22） 8（25） 6（22） 1（18） 5（12）与该城市直接相连的城市标号、及道路长8（15） 7（15） 5（24） 11（19） 9（19） 9（19） 9（30） 6（12） 10（19） 11（21） 12（21） 7 3 8 4 9 6 10 2 11 4 12 3 3（22） 5（16） 6（24） 3（16） 9（12） 9（20） 4（18） 8（12） 12(22） 9（24） （22） 11（25） 8（30） 度（千米，括号内内10容） 11（19） 12（19）

3 模型假设

为了便于建立模型，考虑了一些实际情况，做出了以下假设，假设系统满足如下一些条件：

（1）各城市人口基本不变；

（2）城市间至少有一条可到达的路径实现互连； （3）每个城市的居民只能到离该城市最近的纳税点缴税；

（4）若与某些城市最近的纳税点有若干个，即其可能与若干个纳税点的距离相同且最邻近，为保证各纳税点工作负担波动不大，该城市的居民只能到最邻近的其中一个纳税点缴税；

6

4 模型建立

4.1模型一：0-1规划的穷举法模型

该模型首先采用改善的Floyd-Warshall算法计算出城市间最短路径矩阵；然后，用0-1规划的穷举法获得模型目标函数的最优解。

目标函数：

MM

??Rmini?1j?1cjM?Dcicj?Vcicj

（1）

?Rj?1cj

约束条件：

?Vi?1Mcicj?1，j?1,2?,M

（2）

?Bi?1Mci?N

（3）

Vcicj?Bci，i?1,2?,M，j?1,2?,M

（4）

?0Bci??

?1

，i?1,2?,M（5）

Vcicj?0?? ?1，i?1,2?,M，j?1,2?,M（6）

表3 符号意义 符号 M N 意义 地区内城市总数 计划设置的纳税点数目 第i个城市的标志 Ci 7

RciDcicj 城市的Ci居民数 城市和Cj间可行的最短路径长度 表示是否在城市Ci设置纳税点； 表示城市Cj是否到城市Ci纳税 Bci Vcicj

式（2）表示地区内有且仅有一个城市是城市Cj的居民的缴税点；式（3）表示应开设N个纳税点。

式（4）表示若Bci?0，则Vcicj?0；若Bci?1，则Vcicj?1或Vcicj?0；即表示只有在城市Ci设置纳税点时，城市Cj的居民才有可能去Ci缴税。

式（5）中，Bci?0时，表示不在城市Ci设置纳税点；Bci?1时，表示在城市Ci设置纳税点。

式（6）中，Vcicj?0时，表示城市Cj不到城市Ci纳税；Vcicj?1时，表示城市Cj到城市Ci纳税。

模型思路流程图为：

8

图2 模型一的思路流程图

4.2模型二：0-1规划的分区模型

若已确定城市A、B为纳税点，城市C、D中居民分别属于B、A纳税点管辖范围，即DISTBC?DISTAC?DISTAD?DISTBD。假设D中居民通过C到达A，则表示C到A的距离小于C到B的距离，这与实际情况相反。

所以各纳税点管辖的区域相互独立，即D中居民到A的最短路径线路上，绝对不会包含B（A?B）纳税点管辖的城市（如C）。如下图，粗线条表示D到A的最短路径：

9

图3 各纳税点管辖的区域相互独立举例图

根据各纳税点管辖的区域相互独立的原理，采用启发式搜索的方法分区，考虑到居民数较多且交通便利的两城市，一般不在同一纳税点缴税的实际情况，增加一些假设条件，利用这些假设条件指导搜索过程，实现合理的分区。

分区后，各纳税点管辖的城市互不相关，最终获得若干分区方案；然后，分别求各个方案的最优解；最后，获得整个模型的全局最优解。其中，各方案的最优解求解方法为：先独立求各区域设置一个纳税区域时的最优解，然后各区域叠加，就可以获得该方案最优解。

目标函数为：

minp?1PL???Rk?1i?1j?1NMMcj?Dcicj?Vcicj?Belongcik?Belongcjk?Ri?1n（7）

ci约束条件：式（2）、（3）、（5）、（6）、

?Belongk?1Ncik?1，i?1,2?,M（8）

?Bi?1Mci?Belongcik?1，k?1,2?,N（9）

i?1,2?,M，j?1,2?,M，

Vcicj?Bci?Belongcik?Belongcjk10

k?1,2?,N(10)

?0Belongcik??，i?1,2?,M，k?1,2?,N(11)

?1

式中，PL：启发式搜索获得的方案数；

Belongcik：表示城市Ci属于第k个纳税区域。

其余各符号意义，以及约束条件式（2）、（3）、（5）、（6）的意义均与模型一相同。式（8）表示城市Ci属于且仅属于其中一个纳税区域。式（9）表示纳税区域k有且仅有一个纳税点。式（10）表示只有城市Ci、Cj在同一区域，且在Ci设置纳税点时，城市Cj的居民才有可能去Ci缴税。

式（11）中Belongcik?0时，表示城市Ci不在区域纳税；Belongcik?1时，表示城市Ci在区域纳税。

模型流程图为：

11

城市间主要道路最短路径算法各城市居民数启发式搜索算法城市间最短路径和距离矩阵N个区域中心（共PL种方案）启发式搜索算法分为N个独立区域0-1规划各区域分别选择一个最优纳税点进一步讨论模型的推广性

图4 模型二的思路流程图

4.3模型三：最近邻法分区模型

该模型与模型二的目标函数相同。只是模型二是在一定的假设条件的基础上，采用启发式搜索指导分区，各区域相互独立。而本模型的初始纳税点和分区方法不需要很多额外的假设条件，充分利用了从各城市出发的道路数和居民数，而且各区域不需要相互独立，可能有若干城市属于两个或两个以上区域。

模型流程图为：

12

城市间主要道路最短路径算法各城市居民数城市排序城市间最短路径和距离矩阵N个区域中心最近邻分类法分为N个区域各区域分别选择一个城市，用最近邻法分区，直到获得最优解进一步讨论模型的推广性

图5 模型三的思路流程图

层次方法具体步骤如下：

首先利用从各城市出发的道路数和居民数，确定初始化的N个纳税点。 （1）第一步，对各城市按从城市出发的道路数由大到小进行排序； （2）第二步，剪枝，然后对于从城市出发的有效道路数相同的几个城市，按居民数由大到小排序；

（3）第三步，选择排序结果的前N个城市作为初始的纳税点。

其次，采用最近邻分类法，即根据其他城市与这N个纳税点的最短距离，确定其属于那个纳税区域，实现分区，获得分区结果A。

然后，从分区结果A的各区域抽取一个城市作为纳税点，采用最近邻法对其他城市重新分区，直到遍历完分区结果A各区域包含的所有城市。

13

4.4模型四层次分析法求解模型

模型四利用层次分析方法，根据路径最短，附近人口最多找出所得税选址地点，最后得到最佳选址点。

图6层次分析构图

分区方法具体步骤如下：

（1） 第一步，找到决策目标，探究在哪三个城市中设置纳税点才能够使居

民与最近的纳税点之间平均距离最小。

（2） 第二步，筛选分类相同或相似路线数的城市，分为三类。

（3） 第三步，在各个分类城市中找到人口最多的城市，将找到的三个城市

设为最佳所得税交纳点。

5问题的求解

5.1求解过程中采用的主要算法

5.1.1最短路径算法

模型一、二、三均需要计算出两城市间距离矩阵D，模型二还需要记录对应的最短路径，以便分区时作为参考条件。最短路径算法主要由改善的floyd-warshall算法实现，最后获得由任意两城市间距离矩阵D和对应的最短路径。算法具体原理如下：

step1：构造邻接矩阵A。

若城市Ci和Cj间无直接连通的道路，则令?i,j?元素Aij为正无穷大；否则Aij?i?1,2,?,M;j?1,2,?,M?为Ci和Cj直接连通的道路长度。具体步骤如

14

下：

step1_1：A的值初始化为正无穷。

step1_2：令Aii?0?i?1,2,?,M?，即A的对角线元素设为0。

step1_2：若城市Ci和Cj间有直接连通的道路，则令Aii?0?i?1,2,?,M?为该道路的长度。

step2：获得两城市间距离矩阵D和城市间的最短路径矩阵W。

D、W的?i,j?元素分别表示为Dcicj、Wcicj?i?1,2,?,M;j?1,2,?,M?，对

于所有的城市Ci、Cj和Ck，如果

Dcicj?Dcick?Dckcj，则令

Dcicj?Dcick?Dckcj，Wcc?Ck（表示从城市Ci到Cj要经过城市Ck，若ij。具体步骤如下： Wcicj?0，表示两城市可直达）

step2_1：令D?A，W为A的同维零矩阵，k?1； step2_2：若k?M，执行下一步；否则，转向step2_8； step2_3：i?1

step2_4：若i?M?1，执行下一步；否则，转向step2_1； step2_5：j?i?1；

step2_6：若j?M，执行下一步；否则，i?i?1转向step2_3；

step2_7：若Dcc?Dcc?Dckcj，则令Dcicj?Dcick?Dckcj，Dcjci?Dcicj；城市Ciijik通过最短路径到Cj时，要经过城市Ck，Wcc?Ck，Wcc?Wcc；转向step2_6。 ijjiijstep2_8：得到距离矩阵D和城市间最短路径矩阵W，算法终止。

流程图如下：

15

开始构造邻接矩阵A两城市间距离矩阵D城市间的最短路径矩阵W结束

图7改善的floyd-warshall算法流程图

5.1.2启发式搜索算法

启发式搜索算法将在模型二中使用，搜索的算法对该模型非常重要，搜索结果将直接指导分区过程。本模型采用的启发式搜索算法是在一些合理的假设条件下进行的，假设条件如下：

（1）交通便利的城市，即从该城市出发的道路数多的城市，优先设置为分区的区域中心。

（2）若干城市的交通状况相同，即从这些城市出发的道路数相同，则人数多的城市优先设置为分区的区域中心；

（3）每个分区包含的城市数目相同或相差不大，即对于城市总数M是要建立的纳税点数N的整数倍的情况，各区包含城市数为M/N。

算法原理图如下：

16

开始NN=0搜索从各城市出发的有效道路数的最大值MAX有效道路数=MAX的城市组成城市集合JJ包含的城市个数Num==1N搜索J中各城市的居民数的最大值MRYJ中居民数=MR的城市组成城市集合JRYJR包含的城市个数NumR==1Y区域NN的中心,与中心相连道路剪枝，NN=NN+1NN==NPL种N区域中心方案扩展第PL个方案NN区域的中心，搜索离该中心距离最近的M/N个城市，NN区域扩展完成NNN=NN-1NN==NYPL=PL-1NPL==0Y结束

图8 启发式搜索流程图

其中，从城市出发的有效道路数表示剪枝后的道路数（剪枝：把与区域中心相连的道路减去）。

5.1.3 0-1规划算法

模型一、二均需要利用0-1规划法求目标函数最优解，两模型0-1规划

法原理相同，只是模型一是从M个模型中求解出N个最优纳税点，而模型二是

17

从M/N个城市中求解出一个最优纳税点。

下面以模型一为例说明0-1规划法算法具体原理：

step1：构造由各城市居民数构成的行向量R，其?1,i?元素Rci?i?1,2,?,M?表

示为城市Ci的居民数。

step2：初始化最小距离加权和SUM?Inf(无穷大)，SUM为设置的三个交税点的加权和。

step3：确定纳税点、各纳税区域，求得最小距离加权和。具体步骤如下： step3_1：i?1；

step3_2：若i?M?2，执行下一步；否则，转向step3_12； step3_3：j?i?1；

step3_4：若j?M?1，执行下一步；否则，i?i?1，转向step3_； step3_5：k?j?1，表示选择的纳税点为城市Ci、

Cj和Ck；

step3_6：若k?M，执行下一步；否则，j?j?1，转向step3_4； step3_7：初始化各纳税区域组成的城市向量n1、n2、n3（n1、n2、n3设为长为的M?2零向量），各区域包含的城市数c1、c2、c3（均设为0）,以及距离加权和SUM0?0，令n?1；

step3_8：若n?M，执行下一步；否则，k?k?1，转向step3_6； step3_9：比较城市Cn和假设的纳税点城市Ci、以确定CnCj和Ck的距离，的缴税点；运用matlab进行运算。

step3_10：若SUM0?SUM，则转向step3_11；否则n?n?1，转向step3_8；部分Matlab程序如下：

if sum0>=SUM

break; end

step3_11：若SUM0?SUM，更新纳税点、各纳税区域和最小距离加权和；否则，执行下一步；运用Matlab程序进行运算。

18

step3_12：k?k?1，转向step3_6；

step3_13：得到纳税点向量node、对应的各纳税区域向量nn1、nn2、nn3，求得最小距离加权和SUM0，算法终止。

原理图如下：

开始构造居民数向量R最小距离加权和SUM?Inf(无穷大)0-1规划算法(step3）N个纳税点各纳税区域最小距离加权和SUM0结束 图90—1规划算法流程图

5.2问题的具体求解

5.2.1用模型一求解

该模型为线性规划模型，我们采用Matlab程序求解。

step1：用Matlab编程实现的2.1中介绍的最短路径算法求出城市间的最短路径距离矩阵D。

step1_1：利用城市间道路信息，构造邻接矩阵A。

表 3邻接矩阵A（行标、列标均表示城市编号）

列 行 1 2 3 4 5 6 7 8 9 10 11 12 19

123456789101112 ?0?15??Inf??Inf?24??Inf?18??Inf?Inf??Inf??Inf??Inf 15022InfInfInfInfInfInfInfInfInfInf2201816InfInfInf20InfInfInfInfInf180Inf12InfInfInfInfInfInf24Inf16Inf0InfInf1224InfInfInfInfInfInf12Inf0InfInf12InfInf2218InfInfInfInfInf015Inf22InfInfInfInfInfInf12Inf15030Inf25InfInfInf20Inf2412Inf300Inf1919InfInfInfInfInfInf22InfInf019InfInfInfInfInfInfInfInf251919021Inf?Inf??Inf??Inf?Inf??22?Inf??Inf?19??Inf??21??0?step1_2：获得两城市间距离矩阵D和城市间最短路径矩阵W。 %基于MATLAB的最短路Warshall-Floyd 算法 结果如表4、表5：

表4距离矩阵D（行标、列标均表示城市编号）

列 行 1 2 3 4 5 6 7 8 9 10 11 12 123456789101112 ?0 15 37 55 24 60 18 33 48 40 58 67??15 0 22 40 38 52 33 48 42 55 61 61????37 22 0 18 16 30 43 28 20 58 39 39???55 40 18 0 34 12 61 46 24 62 43 34???24 38 16 34 0 36 27 12 24 49 37 43????60 52 30 12 36 0 57 42 12 50 31 22? ?18 33 43 61 27 57 0 15 45 22 40 61????33 48 28 46 12 42 15 0 30 37 25 46??48 42 20 24 24 12 45 30 0 38 19 19????40 55 58 62 49 50 22 37 38 0 19 40???58 61 39 43 37 31 40 25 19 19 0 21????67 61 39 34 43 22 61 46 19 40 21 0??表4 城市间最短路径矩阵W（行标、列标均表示城市编号）

列 行 1 2 3 4 5 6 7 8 9 10 11 12 20

123456789101112 ?0?0??2??3?0??9?0??7?5??7??8??9000334173799200004850119933003085611960303098008899440909901190018889008081177550900070115306008001100771111811071100118999898000009?9??9??6?9??0? 11??11?0??11??0?0??

step2：用Matlab编程实现的2.2中介绍0-1规划法求得纳税点向量node、对应的各纳税区域向量nn1、nn2、nn3，求得最小距离加权和SUM0；

运用Matlab程序

结果如下：The weighted sum minmum is : 2438；

The selected sites are : 1 6 11

The selected districtsare : 1 2 5 7

3 4 6 9

8 10 11 12

即纳税点为城市1、6,、11；城市1、5、7到1缴税，城市3、4、9到6缴税，城市8、10、12到11缴税；求得最小距离加权和SUM0为2438（千米）。

step3：求目标函数的最优解，即居民与最近的纳税点之间平均距离的最小值。运用Matlab程序

结果如下：

The weighted average minmumis : 13.1784

即居民与最近的纳税点之间平均距离的最小值为13.1784。

5.2.2用模型二求解

step1：用Matlab编程实现的floyd-warshall算法求出城市间的最短路径距离

矩阵D和城市间最短路径矩阵W。

21

求解过程、结果同模型一。

step2：用Matlab编程实现2.3中的启发式搜索算法，进行分区，获得各个区

域城市集合；

step2_1：用Matlab编程实现的冒泡排序法（程序在。。），选择3个区域中心。 step2_1_1：依据从各城市出发的道路数选择区域中心，更新从各城市出发

的有效道路数。

从表2知，从城市9出发的道路数最多，为6，则设置9为区域一的中心，如下图。更新从各城市出发的有效道路数，结果如表5。从城市1,3,5,7,8,11出发的有效道路数均为3，执行step2_1_2。

123457896101112

图10step2_1_1选择结果（图中用灰色标记的城市）

表5 第一次搜索后从各城市出发的有效道路数结果

城市标号 对应的有效道1 2 3 4 5 6 7 8 9 10 11 12 3 2 3 2 3 2 3 3 0 2 3 2 22

路数

step2_1_2：依据城市1,3,5,7,8,11的城市居民数，从中选择新的区域中心，并

更新从各城市出发的有效道路数。

从表1知，其中城市11的居民数最多，为19，则设置11为区域二的中心，如下图。更新从各城市出发的有效道路数，结果如表6。从城市1,3,5,7出发的有效道路数均为3，执行step2_1_3。

15123124117855691610111219

表6 第二次搜索后从各城市出发的有效道路数结果

图11step2_1_2后选择结果（图中用灰色标记的城市）

城市标号 对应的有效1 2 3 4 5 6 7 8 9 10 11 12 3 2 3 2 3 2 3 2 0 1 0 1 23

道路数

step2_1_3：依据城市1,3,5,7的城市居民数，从中再选择一个区域中心。从表

1知，其中城市1的居民数最多，为15，则设置1为区域三的中心，如下图，3个区域的中心搜索完成。执行step2_2。

151231241178556916101112

图12step2_1_3后选择结果（图中用灰色标记的城市）

step2_2：根据step1获得最短路径距离矩阵D和城市间最短路径，依次扩展搜索得到的区域三、二、一的中心，获得3个区域的城市集合。 step2_2_1：扩展区域三的中心；

1257 图13（a）区域三

step2_2_2：扩展区域二的中心；

8101112 图13（b）区域二

24

step2_2_3：扩展区域一的中心。

3469

图12（c）区域一

最后获得的分区结果如下图：

123457896101112

图14分区结果

step3：用Matlab编程实现的2.2中介绍0-1规划法获得各区域的一个纳税点，

求得各区域的最小距离加权和SUM0i?i?1,2,3?。

Matlab程序执行结果如下：SUM0=…….

step4：求目标函数的最优解，即居民与最近的纳税点之间平均距离的最小值。

Matlab程序运行结果如下：

The weighted average minmumis : 13.1784

即居民与最近的纳税点之间平均距离的最小值为13.1784。

5.2.3

用模型三求解

step1：用Matlab编程实现的floyd-warshall算法求出城市间的最短路径距离

矩阵D和城市间最短路径矩阵W。

25

求解过程、结果同模型一。

step2：用Matlab编程实现的冒泡排序（程序在附录。。。。中），对各城市

进行排序，确定初始化的3个纳税点。

3个初始化的纳税点为：9 11 1

step3：采用最近邻分类法，获得分区结果A。

分区结果A为：区域一：3 4 区域二：8 10 11

区域三：12

5 6 9 12

5 7

step4：从分区结果A的各区域抽取一个城市作为纳税点，采用最近邻法对其

他城市重新分区，直到遍历完分区结果A各区域包含的所有城市。程序在附录。

结果如下：The weighted sum minmum is : 2438；

The selected sites are : 1 6 11

The selected districtsare : 1 2 5 7

3 4 6 9

8 10 11 12

即纳税点为城市1、6,、11；城市1、5、7到1缴税，城市3、4、9到6缴税，城市8、10、12到11缴税；求得最小距离加权和SUM0为2438（千米）。

step5：求目标函数的最优解，即居民与最近的纳税点之间平均距离的最小值。

Matlab程序运行结果如下：

The weighted average minmumis : 13.1784

即居民与最近的纳税点之间平均距离的最小值为13.1784。

6结果分析与模型的评价

6.1 结果分析及模型的优缺点

三种模型的实验结果相同，证明了各模型的可靠性。 （1）模型优点：

1. 模型原创性很强，文章中模型都是自行推导建立的；

2. 建立的规划模型能与实际紧密联系，结合实际情况对问题进行求解，

26

使得模型具有很强的通用性和推广性；

3. 模型一采用穷举法，结果可靠，但时间复杂度比较大；模型二和模型三采用分区模型，大大提高了程序的空间和时间复杂度；其中模型三中用到了简化模型，用最近邻法大致确定最优解的区域，然后再用穷举法进行求解，相比单纯的穷举法简化了问题规模，又使所做出的模型答案具有信服力。

4. 通过对比单纯穷举法和最近邻法破坏性试验结果，也证明了最邻近法是可靠的。

5. 图文结合使思路更清晰流畅；

6. 模型的计算采用专业的数学软件，可信度较高； （2）模型缺点：

1. 模型和算法的选取比较单一，未能用到更多、更好的优化模型，缺乏与其他模型的对比性；

2. 其中的穷举法针对本题比较简单，但对实际其他较复杂问题不具有通用性。

3.模型二必须满足一定的假设条件，推广型不强。

4. 最邻近法只是在一定程度上降低了算法的复杂度，并不一定达到了最优的计算量，对于实际问题也不一定有实用性。 6.2 模型的推广

通过对题目的解读我们发现这是一类规划问题。我们建立了最近邻法分区模型。仔细分析我们建立的模型不难发现：这个模型不仅仅适用于纳税点的最佳选址问题，它对规划问题的求解都可以起到指导作用。

本题的求解是一个典型的规划问题，我们的模型的使用范围非常广泛，这一解决问题的模型可以推广到其他服务性行业的选址中的方案的确定。比如说，物流中心的选址就可以用最近邻法分区模型解决。只不过需要考虑的约束条件和追求的目标有所不同。

7参考文献

【1】 赵希男. 主成分分析法评价功能浅析[ J] . 系统工程, 1995, 13( 2) :24~ 27. 【2】 肯德尔. 多元分析[M] . 北京:科学出版社, 1983. 19

【3】 阎慈琳. 关于主成分分析做综合评价的若干问题[ J ] . 数理统计与管理,

1998, 17( 2) : 22~ 25.

【4】 金若南, 张文杰等编译.现代综合物流管理[M].中国铁道出版社, 1994 【5】 许哲荣, 胡黄德.多产品配送中心场址规划与选择[C].见: 1999 年国际 【6】 物流研讨会论文集, 1999

【7】 祝延军, 胡纯德, 高随祥.单亲进化遗传算法在配送中心选址中的应用[J].

计算机工程与设计, 2005; 26( 3) : 580～582

27

【8】 马欣, 朱双东, 杨斐.旅行商问题的一种改进遗传算法[J].计算机仿真,2003;

20( 4)

【9】 潘正君, 康立山, 陈毓屏.演化计算[M].北京: 清华大学出版社, 1998 【10】王战权,杨东援,汪超.配送中心选址的遗传算法研究[J].物流技术,2001; ( 3) :

11～14

【11】贺国先, 刘凯.优化物流中心配送方案的遗传算法[J].系统工程理论与实践,

2003; 4( 4) : 76～81

【12】肖鹏, 李茂军, 张军平等.单亲遗传算法在物流配送系统中的应用[J].系统

工程, 2000; ( 18) : 64～59

【13】王连芬.层次分析法引论.北京：中国人民大学出版社，1990

28

本文来源：https://www.bwwdw.com/article/reqr.html