所得税交纳点选址探究

所得税交纳点选址探究作者：任蕊（0932037）缪崯森（0932102）孙倩倩（0932015）数学建模——所得税交纳点选址探究-1-目录摘要.............................................................................................................................................-2-一、问题的重述..........................................................................................................................-2-二、模型假设与符号约定..........................................................................................................-3-2.1模型的假设与说明...............................................................................................................-3-2.2符号约定与说明..............................................................................................................-3-三、模型的分析..........................................................................................................................-3-四、模型的建立与求解..............................................................................................................-4-4.1模型I:Dijkstra..................................................................................................................-4-4.2模型II:Floyd...................................................................................................................-6-五、模型评价..............................................................................................................................-7-参考文献......................................................................................................................................-8-附录一Dijkstra的MatLab程序............................................................................................-9-附录二Floyd的MatLab程序...............................................................................................-10-附录三任意一节点到其他节点最短的走法..........................................................................-11-数学建模——所得税交纳点选址探究-2-摘要本文运用了图论的思想理论，在仔细分析问题的条件和要求的基础上，把城市交通网络等效为有向赋权图，将各个纳税点等效为有向图上的各个顶点，采用求解最短路程问题的迪克斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法对本问题进行求解，并分别通过MatLab、Lingo加以实现，体验在不同环境下两种算法的优劣，继而得出纳税点安排的最佳方案。我们的模型合理、实用、简单易懂，可以通用于以图为基础的最优节点的选择问题中，以指导城市规划部门作出相对正确的选择.关键字纳税点规划；选址；Dijkstra算法；Floyd算法；最佳路线一、问题的重述所得税管理部门计划对某个城市的所得税交纳点网络进行重新设计.下图是该城市主要区和主要道路的示意图.区旁边的黑体数字表示该区居民数目，单位为千人.在连区之间的弧上标出了它们之间的距离，单位为千米（斜体字）.为覆盖整个城市，所得税管理部门决定在三个区设置纳税点.请建立数学模型给出三个纳税点安排的最佳方案.数学建模——所得税交纳点选址探究-3-二、模型假设与符号约定2.1模型的假设与说明1.题目中所有居民都要交纳所得税，且每个居民都是独立完成所得税的交纳.2.三个纳税点均可独立完成纳税工作，且所接待的纳税人无上限.3.每条道路在任何时段均畅通.2.2符号约定与说明1.设题目所给的图为G，V为G的顶点集，{|112}iVvi，E为G的边集，{|0,12}ijEvvij.那么该图可以被定义为(,)GVE.2.令图G的每一条边e都对应一个实数()Fe，则称G为赋权图(,,)GVEF,并设(,)Puv为节点u到节点v的路径，用()EP表示(,)Puv全部边的集合，记()()()eEPFPFe，称F(P)为路径P(u,v)的权或长度.3.()Pi表示每一个交纳点的居民数，(1,212)i.4.()Vj表示最优缴纳点交纳点,(1,2,3)j.三、模型的分析1.该问题的目的是对某个城市的所得税交纳点网络进行重新设计，以找出最合理的选址方案，以方便居民生活，有效提高纳税的效率.2.可把该问题抽象为从拓扑图G中寻找最优节点问题，这样可以采用最短路径算法，Dijkstra和Flody算法加以实现.3.该模型在不考虑纳税点接待量的限制，交通拥堵等条件下可抽象为求所有居民到达纳税点的总路程最短的问题，以期达到方便纳税人就近纳税，减少不必要的路上时间花费，节约能源，实现建设资源环保型社会的目标.数学建模——所得税交纳点选址探究-4-四、模型的建立与求解4.1模型I:Dijkstra若0(,)Puv是G中连接u,v的路径，且对任意在G中连接u,v的路径(,)Puv都有0()()FPFP，则称0(,)Puv是G中连接u,v的最短路径.那么显然，若12mvvv为从1v到mv的最短距离，则1km，12kvvv必为从1v到kv的最短距离.更具上述原理求G中某一点到其他各点的距离的算法叫Dijkstra算法.可用两种标号T（TemporaryLabel）标号与P（PermanentLabel）.给iv节点一个P标号指从1v到iv的最短路权，iv点的标号不再改变.给jv一个T标号时，()jTv表示从1v到iv的最短路权的上界，是临时标号，凡没有得到P标号的点都有T标号，到所有的T标号全部得到P标号时，程序结束.Dijkstra标号算法计算步骤a)赋初值.给1v以P标号，记录1()0Pv，其余各点,212ivi给T标号，1()(,)iiTvavv并将iv的父节点设为1v.记录1vu，Su，转向b).b)更新所有的T标号和其父节点./vVS，如果()()(,)TvPuauv，则令()()(,)TvPuauv，并重新记录v的父节点为u，转向c).c)给出下一个P标号并更新记录u和S.*()min(),/TvTvvVS给*v以标号P，**()()PvTv，重新记录*,||uvSSu，转向d).d)终止判断.若/VS非空，转向b),否则终止.由于每个节点人口不同，则我们把节点上的人口视为边的权的一部分，因而可有()||()()||()ijijjiijFvvPiFvvPj这时可把G视为有向图，我们可得出权矩阵为：数学建模——所得税交纳点选址探究-5-015241815022220181620180122416012241201222180152212150302520241230019192201925191902122192101212根据权矩阵，由Dijkstra算法可以求出iv到其余各结点的最短距离节点1234567891011121015044499012014401985286248801102134022250264720190124836376854612101159122035552200324807204734482601276741780482540021601702886717363121364817680536038019261208642971923121078703860690052036021618006276721561100589440727033051610981351368024058548476012208495480336828601008165039081447592097204202404321202884954800836361380106005506961116245120024259249403618001187061046877418574444040024741804201210056104686122155286717362478803990表格1各节点相互最小距离在MatLab中，用枚举法求123,,VVV，对上述矩阵任选三行，记为kjiXX,,X（i,j,k=1,2,…,12且i≠j≠k），则这样的组合有123C种。a列的最小值记为),,(minkajaiaXXX(a=1,2,…,12)。再对上述最小值求和，记为S=121a),,(minkajaiaXXX，这样的S有123C个，再用find函数找出S的最小值对应在矩阵中的位置.容易得到123,,1,6,11VVV，最优解对应的矩阵为0150444990120144019852862488011021340900520360216180062767215611005894408706104687741857444404002474180420ANS数学建模——所得税交纳点选址探究-6-也可以用lingo枚举得出最优解.model:sets:point/1..12/:p,x;way(point,point):d,c;endsetsdata:d=015374524601833484058671502240385233484255616137220181630432820583939454018034126146246243342438163403627122449434360523012360574212503122183343612757015452240613348284612421503037