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

所得税交纳点选址问题数学建模论文摘要本文对规划类问题中多点选址问题进行了探究。针对所得税选址问题，在已知城市间主要道路及各城市居民数的基础上，设定了一些假设，提出了三种模型，分别为穷举法，智能分区法1和智能分区法2，层次分析法。模型一：0-1规划的穷举法模型。该模型首先采用改善的Floyd-Warshall算法计算出城市间最短路径矩阵；然后，用0-1规划的穷举法获得模型目标函数的最优解。模型二：0-1规划的智能分区模型1。该模型考虑了一些普遍情况，在附加的合理的假设前提下，采用按选址数N分区解决问题的方法。该模型首先采用改善的Floyd-Warshall算法计算出城市间最短路径矩阵；然后，用启发式搜索算法将所有城市分为N个独立区域；最后，采用0-1规划求得各区域一个最优纳税点，获得最优解。模型三：最近邻法智能分区模型。该模型首先根据从各城市出发的道路数和居民数，对城市进行排序，获得N个初始纳税点，称为伪选址点；然后，利用最近邻法，根据其余城市与各个伪选址点的最短距离，对城市进行划分，得到N个分区结果（划分后各区域不需要相互独立，即可能有若干城市属于两个或两个以上区域）。最后，从三个分区结果中分别选取一个城市作为纳税点，利用两点间最短距离矩阵得到其余9点的归属，并结合人口数据得到加权总和，遍历三个分区中的所有组合，将加权和最小的选址点作为最终的选址点（真选址点）。模型四：区域层次分析模型。该模型首先根据从各城市出发的道路数的多少进行层次分析，对城市进行分层。然后，同样利用层次分析法对居民数的多少进行分层，综合层次分析求解最优解决方案。模型一，利用穷举法获取得一定是最优解，但该算法随着节点数的增加其复杂度以几何级数增长，计算量最大。但穷举法可以获取最优解，并可以最为验证智能算法有效性的依据。模型二智能分区法1，对本文针对的具体题目是可以获取最优解的，但当改变一下网络拓扑结构或者将人口数变化一下，其获取的可能仅是局部最优解。故模型二的通用性不强。模型三，最近邻法智能分区法是最优算法，该算法在复杂度比穷举法降低10倍左右的时候仍然能获取最优解。该模型受到全局最优点一定在局部最优附近可以找到启发，利用伪选址点进行分区，得到局部最优。在分区上遍历，获取全局最优解。模型四，思路清晰明了，但在面对较大数据时比较复杂，有一定的通用性以及操作局限性。关键词： 多点选址; 0-1规划; 启发式搜索; 最近邻法; 智能分区；层次分析 目 录所得税交纳点选址问题数学建模论文1摘要1目 录31 问题重述42 问题的分析53 模型假设64 模型建立74.1模型一：0-1规划的穷举法模型74.2模型二：0-1规划的分区模型94.3模型三：最近邻法分区模型125问题的求解145.1求解过程中采用的主要算法145.2问题的具体求解196结果分析与模型的评价286.1 结果分析及模型的优缺点286.2 模型的推广297 参考文献291 问题重述所得税管理部门计划对某个地区中的所得税交纳点网络进行重新设计。下图1是对此地区内的城市和主要道路的示意图。城市旁边的黑体数字表示城市的居民数目，单位为千人。在连接城市之间的弧上标出了它们之间的距离，单位为千米（斜体字）。为覆盖各个城市，所得税管理部门决定在三个城市中设置纳税点。 问题：应在哪三个城市中设置纳税点才能够使居民与最近的纳税点之间平均距离最小？图1 此区域内的城市和道路图2 问题的分析本问题的目标是从一个到多个城市组成区域内中，选出一定数目的城市设置纳税点, 建立所得税交纳点网络，实现居民与最近的纳税点之间平均距离最小。对于每个城市纳税点的建立与否只有两种可能，所以可以通过计算城市间的最短路径，然后充分利用地区的城市居民以及道路信息，采用合适的方法搜索纳税点；再确定各纳税点管辖的区域，直到求得最优解。本问题重点要解决如何选择纳税点和如何划分纳税区域，即建立合理的最优纳税点搜索和区域划分模型。由图1，得到地区内城市总数；计划设置的纳税点数目城市标号，。各城市的居民数、城市间道路信息如下表：表1 各城市的居民数城市标号123456789101112（千人）15101218524111613221920表2 道路信息城市标号123456从该城市出发的道路数324243与该城市直接相连的城市标号、及道路长度（千米，括号内内容）2（15）5（24）7（11）1（15）3（22）2（22）5（16）9（20）4（18）3（18）6（24）1（24）3（16）8（12）9（24）4（12）9（12）12(22）城市标号789101112从该城市出发的道路数346243 与该城市直接相连的城市标号、及道路长度（千米，括号内内容）1（18）8（15）10（22）5（12）7（15）9（30）11（25）3（20）5（24）6（12）8（30）11（19）12（19）7（22）11（19）8（25）9（19）10（19）12（21）6（22）9（19）11（21）3 模型假设为了便于建立模型，考虑了一些实际情况，做出了以下假设，假设系统满足如下一些条件：（1）各城市人口基本不变；（2）城市间至少有一条可到达的路径实现互连；（3）每个城市的居民只能到离该城市最近的纳税点缴税；（4）若与某些城市最近的纳税点有若干个，即其可能与若干个纳税点的距离相同且最邻近，为保证各纳税点工作负担波动不大，该城市的居民只能到最邻近的其中一个纳税点缴税；4 模型建立4.1模型一：0-1规划的穷举法模型该模型首先采用改善的Floyd-Warshall算法计算出城市间最短路径矩阵；然后，用0-1规划的穷举法获得模型目标函数的最优解。目标函数： （1）约束条件： ， （2）（3），（4） ， （5）， （6）表3 符号意义符号意义地区内城市总数计划设置的纳税点数目第个城市的标志城市的居民数城市和间可行的最短路径长度表示是否在城市设置纳税点；表示城市是否到城市纳税式（2）表示地区内有且仅有一个城市是城市的居民的缴税点；式（3）表示应开设个纳税点。式（4）表示若，则；若，则或；即表示只有在城市设置纳税点时，城市的居民才有可能去缴税。式（5）中，时，表示不在城市设置纳税点；时，表示在城市设置纳税点。式（6）中，时，表示城市不到城市纳税；时，表示城市到城市纳税。模型思路流程图为：图2 模型一的思路流程图4.2模型二：0-1规划的分区模型若已确定城市A、B为纳税点，城市C、D中居民分别属于B、A纳税点管辖范围，即。假设D中居民通过C到达A，则表示C到A的距离小于C到B的距离，这与实际情况相反。所以各纳税点管辖的区域相互独立，即D中居民到A的最短路径线路上，绝对不会包含B（）纳税点管辖的城市（如C）。如下图，粗线条表示D到A的最短路径：图3 各纳税点管辖的区域相互独立举例图根据各纳税点管辖的区域相互独立的原理，采用启发式搜索的方法分区，考虑到居民数较多且交通便利的两城市，一般不在同一纳税点缴税的实际情况，增加一些假设条件，利用这些假设条件指导搜索过程，实现合理的分区。分区后，各纳税点管辖的城市互不相关，最终获得若干分区方案；然后，分别求各个方案的最优解；最后，获得整个模型的全局最优解。其中，各方案的最优解求解方法为：先独立求各区域设置一个纳税区域时的最优解，然后各区域叠加，就可以获得该方案最优解。目标函数为：（7）约束条件：式（2）、（3）、（5）、（6）、 ， （8） ， （9） ， (10) ， (11)式中，：启发式搜索获得的方案数；：表示城市属于第个纳税区域。其余各符号意义，以及约束条件式（2）、（3）、（5）、（6）的意义均与模型一相同。式（8）表示城市属于且仅属于其中一个纳税区域。式（9）表示纳税区域有且仅有一个纳税点。式（10）表示只有城市、在同一区域，且在设置纳税点时，城市的居民才有可能去缴税。式（11）中时，表示城市不在区域纳税；时，表示城市在区域纳税。模型流程图为：图4 模型二的思路流程图4.3模型三：最近邻法分区模型该模型与模型二的目标函数相同。只是模型二是在一定的假设条件的基础上，采用启发式搜索指导分区，各区域相互独立。而本模型的初始纳税点和分区方法不需要很多额外的假设条件，充分利用了从各城市出发的道路数和居民数，而且各区域不需要相互独立，可能有若干城市属于两个或两个以上区域。模型流程图为：图5 模型三的思路流程图层次方法具体步骤如下：首先利用从各城市出发的道路数和居民数，确定初始化的N个纳税点。（1）第一步，对各城市按从城市出发的道路数由大到小进行排序；（2）第二步，剪枝，然后对于从城市出发的有效道路数相同的几个城市，按居民数由大到小排序；（3）第三步，选择排序结果的前N个城市作为初始的纳税点。其次，采用最近邻分类法，即根据其他城市与这N个纳税点的最短距离，确定其属于那个纳税区域，实现分区，获得分区结果A。然后，从分区结果A的各区域抽取一个城市作为纳税点，采用最近邻法对其他城市重新分区，直到遍历完分区结果A各区域包含的所有城市。4.4模型四层次分析法求解模型模型四利用层次分析方法，根据路径最短，附近人口最多找出所得税选址地点，最后得到最佳选址点。图6层次分析构图分区方法具体步骤如下：（1） 第一步，找到决策目标，探究在哪三个城市中设置纳税点才能够使居民与最近的纳税点之间平均距离最小。（2） 第二步，筛选分类相同或相似路线数的城市，分为三类。（3） 第三步，在各个分类城市中找到人口最多的城市，将找到的三个城市设为最佳所得税交纳点。5问题的求解5.1求解过程中采用的主要算法5.1.1 最短路径算法模型一、二、三均需要计算出两城市间距离矩阵，模型二还需要记录对应的最短路径，以便分区时作为参考条件。最短路径算法主要由改善的floyd-warshall算法实现，最后获得由任意两城市间距离矩阵和对应的最短路径。算法具体原理如下：step1：构造邻接矩阵。若城市和间无直接连通的道路，则令元素为正无穷大；否则为和直接连通的道路长度。具体步骤如下：step1_1：的值初始化为正无穷。step1_2：令 ，即的对角线元素设为0。step1_2：若城市和间有直接连通的道路，则令为该道路的长度。step2：获得两城市间距离矩阵和城市间的最短路径矩阵。、的元素分别表示为、， 对于所有的城市、和，如果，则令，（表示从城市到要经过城市，若，表示两城市可直达）。具体步骤如下：step2_1：令，为的同维零矩阵，；step2_2：若，执行下一步；否则，转向step2_8；step2_3：step2_4：若，执行下一步；否则，转向step2_1；step2_5：；step2_6：若，执行下一步；否则，转向step2_3；step2_7：若，则令，；城市通过最短路径到时，要经过城市，；转向step2_6。step2_8：得到距离矩阵和城市间最短路径矩阵，算法终止。流程图如下：图7 改善的floyd-warshall算法流程图5.1.2 启发式搜索算法启发式搜索算法将在模型二中使用，搜索的算法对该模型非常重要，搜索结果将直接指导分区过程。本模型采用的启发式搜索算法是在一些合理的假设条件下进行的，假设条件如下： （1）交通便利的城市，即从该城市出发的道路数多的城市，优先设置为分区的区域中心。（2）若干城市的交通状况相同，即从这些城市出发的道路数相同，则人数多的城市优先设置为分区的区域中心；（3）每个分区包含的城市数目相同或相差不大，即对于城市总数是要建立的纳税点数的整数倍的情况，各区包含城市数为。算法原理图如下：图8 启发式搜索流程图其中，从城市出发的有效道路数表示剪枝后的道路数（剪枝：把与区域中心相连的道路减去）。5.1.3 0-1规划算法模型一、二均需要利用0-1规划法求目标函数最优解，两模型0-1规划法原理相同，只是模型一是从个模型中求解出个最优纳税点，而模型二是从个城市中求解出一个最优纳税点。下面以模型一为例说明0-1规划法算法具体原理：step1：构造由各城市居民数构成的行向量，其元素表示为城市的居民数。step2：初始化最小距离加权和，为设置的三个交税点的加权和。step3：确定纳税点、各纳税区域，求得最小距离加权和。具体步骤如下：step3_1：；step3_2：若，执行下一步；否则，转向step3_12；step3_3：；step3_4：若，执行下一步；否则，转向step3_；step3_5：，表示选择的纳税点为城市、和；step3_6：若，执行下一步；否则，转向step3_4；step3_7：初始化各纳税区域组成的城市向量n1、n2、n3（n1、n2、n3设为长为的零向量），各区域包含的城市数c1、c2、c3（均设为0）,以及距离加权和，令；step3_8：若，执行下一步；否则，转向step3_6；step3_9：比较城市和假设的纳税点城市、和的距离，以确定的缴税点；运用matlab进行运算。 step3_10：若，则转向step3_11；否则，转向step3_8；部分Matlab程序如下：if sum0=SUMbreak;endstep3_11：若，更新纳税点、各纳税区域和最小距离加权和；否则，执行下一步；运用Matlab程序进行运算。step3_12：，转向step3_6；step3_13：得到纳税点向量node、对应的各纳税区域向量nn1、nn2、nn3，求得最小距离加权和，算法终止。原理图如下：图9 01规划算法流程图5.2问题的具体求解5.2.1 用模型一求解该模型为线性规划模型，我们采用Matlab程序求解。step1：用Matlab编程实现的2.1中介绍的最短路径算法求出城市间的最短路径距离矩阵。step1_1：利用城市间道路信息，构造邻接矩阵。表 3 邻接矩阵（行标、列标均表示城市编号）列行 step1_2：获得两城市间距离矩阵和城市间最短路径矩阵。%基于MATLAB的最短路Warshall-Floyd 算法 结果如表4、表5：表4 距离矩阵（行标、列标均表示城市编号）列行 表4 城市间最短路径矩阵（行标、列标均表示城市编号）列行 step2：用Matlab编程实现的2.2中介绍0-1规划法求得纳税点向量node、对应的各纳税区域向量nn1、nn2、nn3，求得最小距离加权和；运用Matlab程序结果如下：The weighted sum minmum is : 2438；The selected sites are : 1 6 11The selected districts are : 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缴税；求得最小距离加权和为2438（千米）。step3：求目标函数的最优解，即居民与最近的纳税点之间平均距离的最小值。运用Matlab程序结果如下：The weighted average minmum is : 13.1784即居民与最近的纳税点之间平均距离的最小值为13.1784。5.2.2 用模型二求解step1：用Matlab编程实现的floyd-warshall算法求出城市间的最短路径距离矩阵和城市间最短路径矩阵。求解过程、结果同模型一。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。图10 step2_1_1选择结果（图中用灰色标记的城市）表5 第一次搜索后从各城市出发的有效道路数结果城市标号123456789101112对应的有效道路数323232330232step2_1_2：依据城市1,3,5,7,8,11的城市居民数，从中选择新的区域中心，并更新从各城市出发的有效道路数。从表1知，其中城市11的居民数最多，为19，则设置11为区域二的中心，如下图。更新从各城市出发的有效道路数，结果如表6。从城市1,3,5,7出发的有效道路数均为3，执行step2_1_3。图11 step2_1_2后选择结果（图中用灰色标记的城市）表6 第二次搜索后从各城市出发的有效道路数结果城市标号123456789101112对应的有效道路数323232320101step2_1_3：依据城市1,3,5,7的城市居民数，从中再选择一个区域中心。从表1知，其中城市1的居民数最多，为15，则设置1为区域三的中心，如下图，3个区域的中心搜索完成。执行step2_2。图12 step2_1_3后选择结果（图中用灰色标记的城市）step2_2：根据step1获得最短路径距离矩阵和城市间最短路径，依次扩展搜索得到的区域三、二、一的中心，获得3个区域的城市集合。step2_2_1：扩展区域三的中心；图13（a）区域三step2_2_2：扩展区域二的中心；图13（b）区域二step2_2_3：扩展区域一的中心。图12（c）区域一最后获得的分区结果如下图：图14 分区结果step3：用Matlab编程实现的2.2中介绍0-1规划法获得各区域的一个纳税点，求得各区域的最小距离加权和。Matlab程序执行结果如下：SUM0=.step4：求目标函数的最优解，即居民与最近的纳税点之间平均距离的最小值。Matlab程序运行结果如下：The weighted average minmum is : 13.1784即居民与最近的纳税点之间平均距离的最小值为13.1784。5.2.3 用模型三求解step1：用Matlab编程实现的floyd-warshall算法求出城市间的最短路径距离矩阵和城市间最短路径矩阵。求解过程、结果同模型一。step2：用Matlab编程实现的冒泡排序（程序在附录。中），对各城市进行排序，确定初始化的3个纳税点。 3个初始化的纳税点为：9 11 1step3：采用最近邻分类法，获得分区结果A。分区结果A为：区域一：3 4 5 6 9 12 区域二：8 10 11区域三：1 2 5 7 step4：从分区结果A的各区域抽取一个城市作为纳税点，采用最近邻法对其他城市重新分区，直到遍历完分区结果A各区域包含的所有城市。程序在附录。 结果如下：The weighted sum minmum is : 2438；The selected sites are : 1 6 11The selected districts are : 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缴税；求得最小距离加权和为2438（千米）。step5：求目标函数的最优解，即居民与最近的纳税点之间平均距离的最小值。Matlab程序运行结果如下：The weighted average minmum is : 13.1784即居民与最近的纳税点之间平均距离的最小值为13.1784。6结果分析与模型的评价6.1 结果分析及模型的优缺点 三种模型的实验结果相同，证明了各模型的可靠性。（1）模型优点： 1. 模型原创性很强，文章中模型都是自行推导建立的； 2. 建立的规划模型能与实际紧密联系，结合实际情况对问题进行求解，使得模型具有很强的通用性和推广性； 3.模型一采用穷举法，结果可靠，但时间复杂度比较大；模型二和模型三采用分区模型，大大提高了程序的空间和时间复杂度；其中模型三中用到了简化模型，用最近邻法大致确定最优解的区域，然后再用穷举法进行求解，相比单纯的穷举法简化了问题规模，又使所做出的模型答案具有信服力。 4.通过对比单纯穷举法和最近邻法破坏性试验结果，也证明了最邻近法是可靠的。5.图文结合使思路更清晰流畅； 6. 模型的计算采用专业的数学软件，可信度较高； （2）模型缺点： 1. 模型和算法的选取比较单一，未能用到更多、更好的优化模型，缺乏与其他模型的对比性； 2. 其中的穷举法针对本题比较简单，但对