1、所得稅交納點選址問題數學建模論文摘要本文對規劃類問題中多點選址問題進行了探究。針對所得稅選址問題，在已知城市間主要道路及各城市居民數的基礎上，設定了一些假設，提出了三種模型，分別為窮舉法，智能分區法1和智能分區法2。模型一：0-1規劃的窮舉法模型。該模型首先采用改善的Floyd-Warshall算法計算出城市間最短路徑矩陣；然后，用0-1規劃的窮舉法獲得模型目標函數的最優解。模型二：0-1規劃的智能分區模型1。該模型考慮了一些普遍情況，在附加的合理的假設前提下，采用按選址數N分區解決問題的方法。該模型首先采用改善的Floyd-Warshall算法計算出城市間最短路徑矩陣；然后，用啟發式搜索算法

2、將所有城市分為N個獨立區域；最后，采用0-1規劃求得各區域一個最優納稅點，獲得最優解。模型三：最近鄰法智能分區模型。該模型首先根據從各城市出發的道路數和居民數，對城市進行排序，獲得N個初始納稅點，稱為偽選址點；然后，利用最近鄰法，根據其余城市與各個偽選址點的最短距離，對城市進行劃分，得到N個分區結果（劃分后各區域不需要相互獨立，即可能有若干城市屬于兩個或兩個以上區域）。最后，從三個分區結果中分別選取一個城市作為納稅點，利用兩點間最短距離矩陣得到其余9點的歸屬，并結合人口數據得到加權總和，遍歷三個分區中的所有組合，將加權和最小的選址點作為最終的選址點（真選址點）。模型一，利用窮舉法獲取得一定是最

3、優解，但該算法隨著節點數的增加其復雜度以幾何級數增長，計算量最大。但窮舉法可以獲取最優解，并可以最為驗證智能算法有效性的依據。模型二智能分區法1，對本文針對的具體題目是可以獲取最優解的，但當改變一下網絡拓撲結構或者將人口數變化一下，其獲取的可能僅是局部最優解。故模型二的通用性不強。模型三，最近鄰法智能分區法是最優算法，該算法在復雜度比窮舉法降低10倍左右的時候仍然能獲取最優解。該模型受到全局最優點一定在局部最優附近可以找到啟發，利用偽選址點進行分區，得到局部最優。在分區上遍歷，獲取全局最優解。關鍵詞： 多點選址; 0-1規劃; 啟發式搜索; 最近鄰法; 智能分區 目 錄摘要1目 錄21 問題重

4、述22 問題的分析33 模型假設54 模型建立64.1模型一：0-1規劃的窮舉法模型64.2模型二：0-1規劃的分區模型84.3模型三：最近鄰法分區模型115問題的求解135.1求解過程中采用的主要算法135.2問題的具體求解186結果分析與模型的評價271.優缺點277 參考文獻271 問題重述所得稅管理部門計劃對某個地區中的所得稅交納點網絡進行重新設計。下圖1是對此地區內的城市和主要道路的示意圖。城市旁邊的黑體數字表示城市的居民數目，單位為千人。在連接城市之間的弧上標出了它們之間的距離，單位為千米（斜體字）。為覆蓋各個城市，所得稅管理部門決定在三個城市中設置納稅點。 問題：應在哪三個城市中

5、設置納稅點才能夠使居民與最近的納稅點之間平均距離最小？圖1 此區域內的城市和道路圖2 問題的分析本問題的目標是從一個由多個城市組成區域內中，選出一定數目的城市設置納稅點, 建立所得稅交納點網絡，實現居民與最近的納稅點之間平均距離最小。對于每個城市納稅點的建立與否只有兩種可能，所以可以通過計算城市間的最短路徑，然后充分利用地區的城市居民以及道路信息，采用合適的方法搜索納稅點；再確定各納稅點管轄的區域，直到求得最優解。本問題重點要解決如何選擇納稅點和如何劃分納稅區域，即建立合理的最優納稅點搜索和區域劃分模型。由圖1，得到地區內城市總數；計劃設置的納稅點數目城市標號，。各城市的居民數、城市間道路信息

6、如下表：表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（

7、30）11（25）3（20）5（24）6（12）8（30）11（19）12（19）77（22）11（19）8（25）9（19）10（19）12（21）6（22）9（19）11（21）城市標號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、）8（15）10（22）5（12）7（15）9（30）11（25）3（20）5（24）6（12）8（30）11（19）12（19）77（22）11（19）8（25）9（19）10（19）12（21）6（22）9（19）11（21）3 模型假設為了便于建立模型，考慮了一些實際情況，做出了以下假設，假設系統滿足如下一些條件：（1）各城市人口基本保持不變；（2）城市間至少有一條可到達的路徑實現互連；（3）每個城市的居民只能到離該城市最近的納稅點繳稅；（4）若與某些城市最近的納稅點有若干個，即其可能與若干個納稅點的距離相同且最鄰近，為保證各納稅點工作負擔波動不大，該城市的居民只能到最鄰近的其中一個納稅

9、點繳稅；4 模型建立4.1模型一：0-1規劃的窮舉法模型該模型首先采用改善的Floyd-Warshall算法計算出城市間最短路徑矩陣；然后，用0-1規劃的窮舉法獲得模型目標函數的最優解。目標函數： （1）約束條件： ， （2）（3），（4） ， （5）， （6）表3 符號意義符號意義地區內城市總數計劃設置的納稅點數目第個城市的標志城市的居民數城市和間可行的最短路徑長度表示是否在城市設置納稅點；表示城市是否到城市納稅式（2）表示地區內有且僅有一個城市是城市的居民的繳稅點；式（3）表示應開設個納稅點。式（4）表示若，則；若，則或；即表示只有在城市設置納稅點時，城市的居民才有可能去繳稅。式（5）中，

10、時，表示不在城市設置納稅點；時，表示在城市設置納稅點。式（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 各納稅點管轄的區域相互獨立舉例圖根據各納稅點管轄的區域相互獨立的原理，采用啟發式搜索的方法分區，考慮

11、到居民數較多且交通便利的兩城市，一般不在同一納稅點繳稅的實際情況，增加一些假設條件，本模型將利用這些假設條件指導搜索過程，實現合理的分區。分區后，各納稅點管轄的城市互不相關，最終獲得若干分區方案；然后，分別求各個方案的最優解；最后，獲得整個模型的全局最優解。其中，各方案的最優解求解方法為：先獨立求各區域設置一個納稅區域時的最優解，然后各區域疊加，就可以獲得該方案最優解。目標函數為：（7）約束條件：式（2）、（3）、（5）、（6）、 ， （8） ， （9） ， (10) ， (11)式中，：啟發式搜索獲得的方案數；：表示城市屬于第個納稅區域。其余各符號意義，以及約束條件式（2）、（3）、（5）、

12、（6）的意義均與模型一相同。式（8）表示城市屬于且僅屬于其中一個納稅區域。式（9）表示納稅區域有且僅有一個納稅點。式（10）表示只有城市、在同一區域，且在設置納稅點時，城市的居民才有可能去繳稅。式（11）中時，表示城市不在區域納稅；時，表示城市在區域納稅。模型流程圖為：圖4 模型二的思路流程圖4.3模型三：最近鄰法分區模型本模型與模型二的目標函數相同。只是模型二是在一定的假設條件的基礎上，采用啟發式搜索指導分區，各區域相互獨立。而本模型的初始納稅點和分區方法不需要很多額外的假設條件，充分利用了從各城市出發的道路數和居民數，而且各區域不需要相互獨立，可能有若干城市屬于兩個或兩個以上區域。模型流程

13、圖為：圖5 模型三的思路流程圖分區方法具體步驟如下：首先利用從各城市出發的道路數和居民數，確定初始化的N個納稅點。（1）第一步，對各城市按從城市出發的道路數由大到小進行排序；（2）第二步，剪枝，然后對于從城市出發的有效道路數相同的幾個城市，按居民數由大到小排序；（3）第三步，選擇排序結果的前N個城市作為初始的納稅點。其次，采用最近鄰分類法，即根據其他城市與這N個納稅點的最短距離，確定其屬于那個納稅區域，實現分區，獲得分區結果A。然后，從分區結果A的各區域抽取一個城市作為納稅點，采用最近鄰法對其他城市重新分區，直到遍歷完分區結果A各區域包含的所有城市。5問題的求解5.1求解過程中采用的主要算法

14、最短路徑算法模型一、二、三均需要計算出兩城市間距離矩陣，模型二還需要記錄對應的最短路徑，以便分區時作為參考條件。最短路徑算法主要由改善的floyd-warshall算法實現，最后獲得由任意兩城市間距離矩陣和對應的最短路徑。算法具體原理如下：step1：構造鄰接矩陣。若城市和間無直接連通的道路，則令元素為正無窮大；否則為和直接連通的道路長度。具體步驟如下：step1_1：的值初始化為正無窮。step1_2：令 ，即的對角線元素設為0。step1_2：若城市和間有直接連通的道路，則令為該道路的長度。step2：獲得兩城市間距離矩陣和城市間的最短路徑矩陣。、的元素分別表示為、， 對于所有的城市、和，

15、如果，則令，（表示從城市到要經過城市，若，表示兩城市可直達）。具體步驟如下：step2_1：令，為的同維零矩陣，；step2_2：若，執行下一步；否則，轉向step2_8；step2_3：step2_4：若，執行下一步；否則，轉向step2_1；step2_5：；step2_6：若，執行下一步；否則，轉向step2_3；step2_7：若，則令，；城市通過最短路徑到時，要經過城市，；轉向step2_6。step2_8：得到距離矩陣和城市間最短路徑矩陣，算法終止。流程圖如下：圖6 改善的floyd-warshall算法流程圖5.1.2 啟發式搜索算法啟發式搜索算法將在模型二中使用，搜索的算法對該

16、模型非常重要，搜索結果將直接指導分區過程。本模型采用的啟發式搜索算法是在一些合理的假設條件下進行的，假設條件如下： （1）交通便利的城市，即從該城市出發的道路數多的城市，優先設置為分區的區域中心。（2）若干城市的交通狀況相同，即從這些城市出發的道路數相同，則人數多的城市優先設置為分區的區域中心；（3）每個分區包含的城市數目相同或相差不大，即對于城市總數是要建立的納稅點數的整數倍的情況，各區包含城市數為。算法原理圖如下：圖8 啟發式搜索流程圖其中，從城市出發的有效道路數表示剪枝后的道路數（剪枝：把與區域中心相連的道路減去）。5.1.3 0-1規劃算法模型一、二均需要利用0-1規劃法求目標函數最優

17、解，兩模型0-1規劃法原理相同，只是模型一是從個模型中求解出個最優納稅點，而模型二是從個城市中求解出一個最優納稅點。下面以模型一為例說明0-1規劃法算法具體原理：step1：構造由各城市居民數構成的行向量，其元素表示為城市的居民數。step2：初始化最小距離加權和，為設置的三個交稅點的加權和。step3：確定納稅點、各納稅區域，求得最小距離加權和。具體步驟如下：step3_1：；step3_2：若，執行下一步；否則，轉向step3_12；step3_3：；step3_4：若，執行下一步；否則，轉向step3_；step3_5：，表示選擇的納稅點為城市、和；step3_6：若，執行下一步；否則，

18、轉向step3_4；step3_7：初始化各納稅區域組成的城市向量n1、n2、n3（n1、n2、n3設為長為的零向量），各區域包含的城市數c1、c2、c3（均設為0）,以及距離加權和，令；step3_8：若，執行下一步；否則，轉向step3_6；step3_9：比較城市和假設的納稅點城市、和的距離，以確定的繳稅點；Matlab程序如下： if (D(n,i)<=D(n,j)&&(D(n,i)<=D(n,k) sum0=sum0+D(n,i)*P(1,n); c1=c1+1; n1(1,c1)=n; elseif (D(n,j)<=D(n,i)&&

19、;(D(n,j)<=D(n,k) sum0=sum0+D(n,j)*P(1,n); c2=c2+1; n2(1,c2)=n; elseif(D(n,k)<=D(n,i)&&(D(n,k)<=D(n,j) sum0=sum0+D(n,k)*P(1,n); c3=c3+1; n3(1,c3)=n; end step3_10：若，則轉向step3_11；否則，轉向step3_8；部分Matlab程序如下：if sum0>=SUMbreak;endstep3_11：若，更新納稅點、各納稅區域和最小距離加權和；否則，執行下一步；部分Matlab程序如下：if su

20、m0<SUMSUM=sum0;%更新最小加權和node(1,1)=i;%更新選址點node(1,2)=j;node(1,3)=k;nn1=zeros(1,c1);nn1=n1(1,1:c1); %更新各納稅區域nn2=zeros(1,c2);nn2=n2(1,1:c2);nn3=zeros(1,c3);nn3=n3(1,1:c3);endstep3_12：，轉向step3_6；step3_13：得到納稅點向量node、對應的各納稅區域向量nn1、nn2、nn3，求得最小距離加權和，算法終止。原理圖如下：圖8 01規劃算法流程圖5.2問題的具體求解 用模型一求解該模型為線性規劃模型，我們采

21、用Matlab程序求解。step1：用Matlab編程實現的2.1中介紹的最短路徑算法求出城市間的最短路徑距離矩陣。step1_1：利用城市間道路信息，構造鄰接矩陣。表 3 鄰接矩陣（行標、列標均表示城市編號）列行 step1_2：獲得兩城市間距離矩陣和城市間最短路徑矩陣。部分Matlab程序如下：%基于MATLAB的最短路Warshall-Floyd 算法 % Initializen=length(A); % Vertex numberD=A; % Distance matrixW=zeros(n); % Route matrix% Update distance matrix D and

22、route matrix Rfor k=1:n % Iteration steps for i=1:n for j=i+1:n if D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j); D(j,i)=D(i,j); W(i,j)=k; W(j,i)= W(i,j); end end end end 結果如表4、表5：表4 距離矩陣（行標、列標均表示城市編號）列行 表4 城市間最短路徑矩陣（行標、列標均表示城市編號）列行 step2：用Matlab編程實現的2.2中介紹0-1規劃法求得納稅點向量node、對應的各納稅區域向量nn1、nn2、nn3，求得最小

23、距離加權和；部分Matlab程序如下：node=zeros(1,3);%選取的三個交稅點，初始化for i=1:1:10 for j=i+1:1:11 for k=j+1:1:12 sum0=0; %初始化距離加權和 n1=zeros(1,10);n2=n1;n3=n1;%初始化的各納稅區域 c1=0;c2=0;c3=0;%初始化的各納稅區域城市數 for n=1:1:12 if (D(n,i)<=D(n,j)&&(D(n,i)<=D(n,k) sum0=sum0+D(n,i)*P(1,n); c1=c1+1; n1(1,c1)=n; elseif (D(n,j)&

24、lt;=D(n,i)&&(D(n,j)<=D(n,k) sum0=sum0+D(n,j)*P(1,n); c2=c2+1; n2(1,c2)=n; elseif(D(n,k)<=D(n,i)&&(D(n,k)<=D(n,j) sum0=sum0+D(n,k)*P(1,n); c3=c3+1; n3(1,c3)=n; end if sum0>=SUM break; end end if sum0<SUM SUM=sum0;%更新最小加權和 node(1,1)=i;%更新選址點 node(1,2)=j; node(1,3)=k; nn1

25、=zeros(1,c1);nn1=n1(1,1:c1);%更新各納稅區域nn2=zeros(1,c2);nn2=n2(1,1:c2);nn3=zeros(1,c3);nn3=n3(1,1:c3); end end endend結果如下：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繳稅；求得最小距離加權

26、和為2438（千米）。step3：求目標函數的最優解，即居民與最近的納稅點之間平均距離的最小值。Matlab程序如下： average=SUM/sum(P);fprintf('The weighted average minmum is :nn')disp(average)結果如下：The weighted average minmum is : 13.1784即居民與最近的納稅點之間平均距離的最小值為13.1784。5.2.2 用模型二求解step1：用Matlab編程實現的floyd-warshall算法求出城市間的最短路徑距離矩陣和城市間最短路徑矩陣。求解過程、結果同模型

27、一。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。圖9 step2_1_1選擇結果（圖中用灰色標記的城市）表5 第一次搜索后從各城市出發的有效道路數結果城市標號123456789101112

28、對應的有效道路數323232330232step2_1_2：依據城市1,3,5,7,8,11的城市居民數，從中選擇新的區域中心，并更新從各城市出發的有效道路數。從表1知，其中城市11的居民數最多，為19，則設置11為區域二的中心，如下圖。更新從各城市出發的有效道路數，結果如表6。從城市1,3,5,7出發的有效道路數均為3，執行step2_1_3。圖10 step2_1_2后選擇結果（圖中用灰色標記的城市）表6 第二次搜索后從各城市出發的有效道路數結果城市標號123456789101112對應的有效道路數323232320101step2_1_3：依據城市1,3,5,7的城市居民數，從中再選擇一

29、個區域中心。從表1知，其中城市1的居民數最多，為15，則設置1為區域三的中心，如下圖，3個區域的中心搜索完成。執行step2_2。圖11 step2_1_3后選擇結果（圖中用灰色標記的城市）step2_2：根據step1獲得最短路徑距離矩陣和城市間最短路徑，依次擴展搜索得到的區域三、二、一的中心，獲得3個區域的城市集合。step2_2_1：擴展區域三的中心；圖12（a）區域三step2_2_2：擴展區域二的中心；圖12（b）區域二step2_2_3：擴展區域一的中心。圖12（c）區域一最后獲得的分區結果如下圖：圖13 分區結果step3：用Matlab編程實現的2.2中介紹0-1規劃法獲得各區

30、域的一個納稅點，求得各區域的最小距離加權和。Matlab程序執行結果如下：SUM0=.step4：求目標函數的最優解，即居民與最近的納稅點之間平均距離的最小值。Matlab程序如下： average=sum(SUM0)/sum(P);fprintf('The weighted average minmum is :nn')disp(average)結果如下：The weighted average minmum is : 13.1784即居民與最近的納稅點之間平均距離的最小值為13.1784。5.2.3 用模型三求解step1：用Matlab編程實現的floyd-warshal

31、l算法求出城市間的最短路徑距離矩陣和城市間最短路徑矩陣。求解過程、結果同模型一。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 sele

32、cted 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程序如下： average=SUM/sum(P);fprintf('The weighted average minmum is :nn')disp(average)結果如下：The weight

33、ed average minmum is : 13.1784即居民與最近的納稅點之間平均距離的最小值為13.1784。6結果分析與模型的評價6.1 結果分析及模型的優缺點 三種模型的實驗結果相同，證明了各模型的可靠性。（1）模型優點： 1. 模型原創性很強，文章中模型都是自行推導建立的； 2. 建立的規劃模型能與實際緊密聯系，結合實際情況對問題進行求解，使得模型具有很強的通用性和推廣性； 3.模型一采用窮舉法，結果可靠，但時間復雜度比較大；模型二和模型三采用分區模型，大大提高了程序的空間和時間復雜度；其中模型三中用到了簡化模型，用最近鄰法大致確定最優解的區域，然后再用窮舉法進行求解，相比單純的

34、窮舉法簡化了問題規模，又使所做出的模型答案具有信服力。 4.通過對比單純窮舉法和最近鄰法破壞性試驗結果，也證明了最鄰近法是可靠的。5.圖文結合使思路更清晰流暢； 6. 模型的計算采用專業的數學軟件，可信度較高； （2）模型缺點： 1. 模型和算法的選取比較單一，未能用到更多、更好的優化模型，缺乏與其他模型的對比性； 2. 其中的窮舉法針對本題比較簡單，但對實際其他較復雜問題不具有通用性。3. 模型二必須滿足一定的假設條件，推廣型不強。 4.最鄰近法只是在一定程度上降低了算法的復雜度，并不一定達到了最優的計算量，對于實際問題也不一定有實用性。6.2 模型的推廣 通過對題目的解讀我們發現這是一類規劃問題。我們建立了最近鄰法分區模型。仔細分析我們建立的模型不難發現：這個模型不僅僅適用于納稅點的最佳選址問題，它對規劃問題的求解都可以起到指導作用。 本題的求解是一個典型的規劃問題，我們的模型的使用范圍非常廣泛，這一解決問題的模型可以推廣到其他服務性行業的選址中的方案的確定。比如說，物流中心的選址就可以