最佳选址问题(所得税交纳点选址问题).doc

所得税交纳点选址一、问题叙述所得税管理部门计划对某个地区中的所得税交纳点网络进行重新设计。图B.1是对此地区内的城市和主要道路的示意图。城市旁边的黑体数字表示城市的居民数目，单位为千人。在连接城市之间的弧上标出了它们之间的距离，单位为千米（斜体字）。为覆盖各个城市，所得税管理部门决定在三个城市中设置纳税点。应在哪三个城市中设置纳税点才能够使居民与最近的纳税点之间平均距离最小？图B.1：此区域内的城市和道路图二、问题分析设所求的平均距离为，则=* / P（i=1、2、311、12），其中12个城市到各自最近的纳税点到最短距离（单位千米），其中被选为纳税点的城市的距离为零，故可看为其它九个城市到各自最近纳税点距离的和；为每个城市的人数（单位千人）;P为所有城市的总人数。人数都已知，而问题在于找出三个纳税点使其它九个城市到各自最近纳税点的距离之和除以总人数最短，故问题首先要知道城市与城市之间的最短距离。已知每个城市间的最短距离之后，再按照排列组合，将12个城市中所有的3个城市作为纳税点的情况（有C=220种情况）下每种情况的=/P算出来进行对比，最小的那个就是我们所要求的情况，这个过程我们需要计算机程序的帮助来完成。三、模型建立按照问题分析结果，首先我们要列出每个城市之间的最短距离，由图B.1可得出下表：城市123456789101112101537552460183348405867215022403852334842556161337220181630432820583939455401803412614624624334524381634036271224493743660523012360574212503122718334361275701545224061833482846124215030372546948422024241245300381919104055586249502237380194011586139433731402519190211267613934432261461940210表一完成每个城市之间的最短距离之后，接下来需要编写程序，使之能算出220种情况并进行比较，同时得出最优解。四、模型的求解 我们小组借助Microsoft Visual Studio 10.0程序,利用C+语言编程,使用简洁的数组循环语句来实现所有的功能。具体的算法如下：（程序代码见附录一）算法的主要思路就是:从预定的站点中顺序选出3个站点,分别计算其他每一个站点到这3个站点中的最优路径min，用每一个站点的人数乘它到最近站点的距离（代权和），得到总距离的加权和mindistance，与所选定的站点序号一起输出。同时将所有的总距离加权和mindistance储存在一维数组中，通过比较输出最小值。将表一矩阵中的244个数据以12*12矩阵的形式输入到文本文档“xuanzhi.txt”中，并将其保存在D盘根目录下。用于程序的函数调用。运行Microsoft Visual Studio 10.0程序，建立名为“最佳选址问题”的项目，在源文件中输入源代码（见附录一），执行程序，通过调用二维数组的数据（矩阵），在一系列循环下，程序输出结果：分别显示任意三个站点为所得税缴纳点时整个区域的路径距离代权和与最佳选址结果。通过运行的程序结果可以直接看出：当选择1,6,11这三个城市为纳税点时，居民与最近的纳税点之间平均距离最小，其对应的加权距离和为2438。由于此区域内的总居民数为185,000 人，因此每个居民到最近纳税点的平均距离为2438/185 = 13.178千米。将在结点1，6，和11 设置纳税点。城市1，2，5，7 的居民将去结点1 的纳税点缴税，城市3，4，6，9 的居民将去结点6 的纳税点缴税，城市8，10，11，12将去结点11 的纳税点缴税。五、模型检验我们通过随机抽样的方法进行检验。随机抽取三个城市作为纳税点，算出这种情况下的平均距离，重复5次，与所得结果进行比较，所得结果均为最小。以下是检验过程：(1) 选取2，3，4作为纳税点时，从程序结果看： 居民到纳税点平均最小距离：4295/185=23.216千米。(2) 选取3，6，10作为纳税点时，从程序结果看：居民到纳税点平均最小距离：2718/185=14.692千米。(3) 选取6，8，12作为纳税点时，从程序结果看：居民到纳税点平均最小距离：3105/185=16.784千米。(4) 选取5，8，11作为纳税点时，从程序结果看：居民到纳税点平均最小距离：3538/185=19.124千米。(5) 选取7，9，11作为纳税点时，从程序结果看：居民到纳税点平均最小距离：2718/185=14.692千米。而选取1,6,11作为纳税点时，居民到纳税点的平均距离是13.178千米，通过比较可知选取1,6,11时居民到交纳点平均距离最小。六、模型评价本模型由于大部分过程由计算机编程完成，运用数组和多重循环的算法，此算法简单有效，代码编写容易。操作过程简单快捷，效率较高，容易理解，可以算出任意两个站点之间的最短距离并从中输出最优值。本模型没有利用数学公理或定理，或数学软件实现，仅仅利用计算机编程软件实现，但是具有伸缩性，实用性很强。遇到类似选址问题只需要改变无向图的临界矩阵数据即可得到一系列最优选址问题，可以运用到解决类似的问题中，所以推广型比较强。本模型没有数学公式的引用，而是利用纯计算机算法，所以缺乏文本的表述性。附表一：计算220种可能情况程序源代码：#include#includeusing namespace std;void main()int a220;int n=0;int value;int i,j,k;int min;int s=0;int m;int mindistance;int mindl;int arr1212;ifstream fin (d:xuanzhi.txt);if(!fin.is_open()cout打开文件失败value;int i=0,j=0;while(!fin.eof()if(j!=12)arrij=value;j+;elsej=0;i+;arrij=value;j+;finvalue;fin.close();int b12=15,10,12,18,5,24,11,16,13,22,19,20;for(i=0;i=11;i+)for(j=i+1;j=11;j+)for(k=j+1;k=11;k+)for(m=0;m=11;m+)min=arrmi;if(arrmj=min)min=arrmj;if(arrmk=min)min=arrmk;s=s+min*bm;mindistance=s;an=s;n+;s=0;couti+1 j+1 k+1 mindistanceendl;mindl=a0;for(int p=1;p=219;p+)if(ap=mindl)mindl=ap;coutendl;cout最短路径是：mindl千米endl;coutendl