供应网络的建立及道路破坏问题

供给网络的建立与道路破坏问题摘要本文针对供给链网络的建立与道路破坏问题，运用Floyd算法、0-1整数规划、遍历法等多种方法，借助Lingo、Matlab等软件，综合分析了49个城市的供给链网络的相关数据，建立了线性规划模型、影响度模型以及优先选择模型，得到了城市运输供给链中最优供给点及破坏道路时破坏程度不同情况下的最优破坏方案。针对问题一，由于49个城市中*些城市的建站费用过高，不适合建立供给点。将这些城市剔除后共有28个城市可以作为供给点。通过题中所给的数据运用floyd算法，借助MATLAB软件求出每个城市到其他城市的最短距离，然后写出目标函数及相应的约束条件,采用0-1整数规划法建立现行规划模型,使用Lingo软件得到建立8个供给点费用最少，供给点城市编号分别为4、7、11、20、23、26、28、45。针对问题二，研究破坏道路的方案，使对方平均总费用增加25%,将被破坏的道路间的距离改成一个很大的值，近似看作这条路是不通的。运用floyd算法，借助MATLAB软件求出道路破坏后供给点城市与各城市之间的最短距离，再建立目标函数及约束条件，建立影响度模型，运用Lingo软件得出道路破坏后的最短运输路线，进一步得到破坏后的运输费用，与破坏前费用相减可以得到道路破坏后增加的费用，当使总费用增加25%时最少破坏道路的序列号为1、2、4、5、7、9，总费用增加11577797元。针对问题三，主要研究的是破坏尽可能少的道路来使对方平均总费用至少增加100%，供给点的基建费用是固定不变的，决定平均总费用的只是运输的平均总费。所以求运输的平均费用其实就是根据相应的概率分布求运输费用的期望值。由于有8条道路可以被破坏，所以可以给出255种道路破坏方案。由于破坏方选取一些道路进展破坏时，这些道路不一定被破坏，而是服从一定的概率分布，可以根据上面的分析建立优先选择模型，运用MATLAB编写相应的求平均总费用的程序来求出各种方案的平均总费用，得出破坏道路的序列号为1、2、4、5、7、9，平均总费用为1.059×107元。最后，对本文解决问题的方法和模型进展推广，分析了在其他领域的应用，并且综合评价了模型的优缺点。关键词：供给链网络；道路破坏；0-1整数规划；Floyd算法；LINGO§1问题的重述1.1背景知识全球化竞争的加剧促使越来越多的企业开场采用供给链管理策略，以实现企业的一体化管理。供给链是一个复杂的网状构造系统，每一局部都面临着各种潜在的风险，任何一局部出现问题都可能给整个供给链带来严重的影响，因此如何分析、评价和提高供给链系统的可靠性变得日益迫切。设施系统是供给链的核心，在供给链研究中有着极其重要的地位。在一个设施系统中，*些个设施由于自然灾害或者其他因素的影响可能失效，例如911恐惧袭击事件、2004年的印度洋海啸、2008年的汶川地震等都对诸多行业的设施系统造成了严重的破坏。现有*物流公司要在全国各城市之间建立供给链网络。需要选定局部城市作为供给点，将货物运输到各城市。通常每个供给点的货物是充足的，可以充分满足相应城市的需求。设该公司考虑共考虑49个城市的网络，并假定作为供给点的城市其供给量可以满足有需要的城市的需求。现将要建立一个供给网络，为各城市提供货物供给。货物运输利用汽车进展公路运输，设每吨每公里运输费用为0.5元。1.2相关数据1.49个城市的网络坐标〔详见表1〕；2.城市之间的道路连接关系〔详见表2〕；3.每个城市建立配送中心的固定费用和需求量〔详见表3〕；4.可破坏的道路〔详见表4〕。1.3具体问题1.现在要从49个城市中选取局部城市做为供给点供给本城市及其它城市。建立供给点会花费固定费用，从供给点运输到需求点会产生运输费用，要使总费用最小，问建立多少个供给点最好。给出选中作为供给点的城市，并给出每个供给点供给的城市。同时根据坐标作出每一个供给点到需求点的连接图。2.假定有*组织对该供给网络的道路进展破坏。并非所有的道路都可以被破坏，可破坏的道路见表4。当*条道路被破坏后，该条道路就不能再被使用，以前运输经过该道路的只有改道，但总是沿最短路运输。如果破坏方选取的策略是使对方总费用增加25%，而每破坏一条道路都需要本钱和代价，因此需要破坏最少的道路。问破坏方选取哪几条线路进展破坏。给出具体的破坏道路和总费用。3.假定各道路能否被破坏具有随机性，当*条道路被破坏后，该条道路就不能再被使用，以前运输经过该道路的只有改道，但总是沿最短路运输。由于破坏方选取一些边进展破坏时，这些边不一定被破坏，而是服从一定的概率分布。设可破坏的边及各边破坏的概率见表4。运输时产生的费用可按照各种情况下的平均费用来考虑。如果破坏方选取的策略是使对方平均总费用至少增加100%，同样需要破坏最少的道路。问破坏方将选取哪几条线路进展破坏。给出具体的破坏道路和平均总费用。§2问题的分析2.1对问题的总体分析通过对题目所提供的49个城市的运输供给链数据进展分析，运用Floyd算法求出每个城市到其他城市的最短距离，再根据题意列出目标函数及相关的约束条件，利用Lingo程序求解出最优解。对于对供给网络的道路进展破坏问题中，由于破坏程度不同，即破坏的成功率并不一定是百分之百，当破坏是百分之百时，把该条路的距离改成一个很大的值，将得到的新数据运用Floyd算法求出每个城市到其他城市的最短距离，然后给出相应的约束条件建立模型求满足条件的最优解。假设破坏不是百分之百时，即破坏服从一定的概率时，根据相应的概率分布求运输费用即为运输的平均费用，利用Matlab程序得到满足条件的最优解。2.2具体问题的分析⑴对问题1的分析问题一研究的主要是从49个城市中找到适当数量的供给点来使运输费用和基建费用的总费用到达最低。我们可以先通过题中所给的数据运用floyd算法求出每个城市到其他城市的最短距离，然后给出相应的约束条件,运用Lingo软件进展求解,即可得出确定的供给点,使总费用到达最低。最后根据选中作为供给点的城市的坐标作出每一个供给点到需求点的连接图。⑵对问题2的分析问题二主要研究的是破坏尽可能少的道路来使总费用增加25%,于是可以假设当*条道路被破坏时，把该条道路的距离改成一个很大的值，这样就可以近似的看成这个道路是不通的。当*条道路被破坏时，根据新得到的数据用floyd算法重新求出各城市到其他城市的最短距离，然后求出其他没有供给点的城[2]市距离最近的供给点及其之间的距离，最后就可以求出当该道路被破坏时的总费用。然后给出相应的约束条件，建立模型求当总费用增加25%时破坏的道路数量最少的情况，这样就求出了最少的道路数和具体的道路及总费用。⑶对问题3的分析问题三主要研究的是给出适当的破坏道路的方案，对方平均总费用至少增加100%，平均总费用由建造供给点的基建费用和各种情况下运输的平均费用组成，当给出道路破坏的方案后，由于8个供给点是固定的，所以建造供给点的基建费用是不变的，变化的是运输的平均费用。由于破坏方选取一些道路进展破坏时，这些边不一定被破坏，而是服从一定的概率分布。所以求运输的平均费用其实就是根据相应的概率分布求运输费用的期望值。由于有6条道路可以被破坏，所以可以给出64种道路破坏方案。由于破坏方选取一些道路进展破坏时，这些道路不一定被破坏，而是服从一定的概率分布，所以有种情况，在种的情况下运输费用的期望值就是运输的平均总费用。根据上面的分析建立模型，求出各种方案的平均总费用，最后就可以得到相应的方案使得在破坏道路最少的情况下平均总费用到达最大。§3模型的假设〔1〕假设各道路能否被破坏具有随机性；〔2〕假定所有城市之间均可以通过公路运输进展物资运输；〔3〕假设问题二中对任意道路破坏的成功率为百分之百；〔4〕假设各城市的需求量固定不变；〔5〕假设在运输网络简单设期间和*组织破坏期间不会遭遇地震，海啸等自然灾害的影响；〔6〕所有数据来源真实可靠。§4名词解释与符号说明4.1名词解释1.供给链网络：供给链网络是由与核心企业相连的成员组织构成的，这些组织直接或间接与他们的供给商或客户相连，从起始端到消费端。必须分类并确定哪些成员对公司以及供给链的成功起着决定作用，以便对它们给予关注和合理分配资源。2.配送中心[1]：是一种物流结点，它不以贮藏仓库的这种单一的形式出现，而是发挥配送职能的流通仓库。也称做基地、据点或流通中心。配送中心的目的是降低运输本钱、减少销售时机的损失，为此建立设施、设备并开展经营、管理工作[1]。3.floyd算法：floyd算法又称为弗洛伊德算法、插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。通过一个图的权值矩阵求出它的每两点间的最短路径矩阵，从图的带权邻接矩阵开场，递归地进展n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；以此类推，最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。4.2符号说明符号符号说明0-1变量，判断第i个城市是否建立供给点0-1变量，判断从第i个城市是否给第j个城市配送货物在第i个城市建立供给点的固定费用第j个城市的货物需求量第i个城市到第j个城市的最短路径代表i条可以破坏的路0-1变量，判断是否破坏第i条路道路破坏前的总费用道路破坏后的总费用道路破坏前后的增加的总费用平均总费用运输的平均费用8个供给点基建费用§5模型的建立与求解5.1线性规划模型1.模型的分析对于问题一，研究的主要是从49个城市中找到适当数量的供给点及其位置来使运输费用和基建费用的总费用到达最低。总费用由运输费用和基建费用组成,随着选取供给点的数量的增多,运输费用减小,但基建费用会随之增加,很明显,这是一个0-1规划问题。我们先通过题中所给的数据运用floyd算法求出每个城市到其他城市的最短距离，然后给出相应的约束条件,运用Lingo软件进展求解,即可得出确定的供给点,使总费用到达最低。最后根据选中作为供给点的城市的坐标作出每一个供给点到需求点的连接图。2.模型的准备从49个城市中选取n个作为供给点，一共是有种方案，但由于*些城市的建站费用过高，不适合建立供给点，我们将这些城市剔除后共有28个城市可以作为供给点，再运用MATLAB软件编程〔见程序1〕，画出各城市之间道路关系图如图1所示〔图中1-49为各城市编号〕。图1各城市之间道路关系图3.模型的建立通过对问题的分析与数据的整理可以根据Floyd算法[2-3]求出任意两个城市之间的最短公路长度，得到一个49×49的矩阵C[i][j]，根据表2中的数据对C[i][j]进展初始化，假设从i市到j市有直达路径，则将表格中的数据赋给C[i][j],否则将付给C[i][j]，然后用Floyed算法求出从i市到j市的最短路径。Floyed算法思想如下：〔1〕i=1;j=1;k=1;〔2〕u=C[i][k]+C[k][j],假设u<C[i][j],则令C[i][j]=u，否则直接转到3。〔3〕假设j<49,则令j=j+1，转到2；否则转到4。〔4〕假设i<49，则令i=i=1，转到2；否则转到5。〔5〕假设k<49，则令k=k+1，j=1，i=1，转到2；否则输出。通过这种算法运用MATLAB软件编程〔见程序2〕，最后得到的矩阵C[i][j]就是任意两个城市i和j之间的最短路径，得到一个的数据阵，我们截取局部〔10×10〕的数据如表1所示。表1各城市之间最短距离城市编号1234567891010120270480540799112913591260109421200370580660919124914791200103432702700210740106913991629115198544805802100530127916091839136111955540660740530013391669189918001634679991910691279133903305602059189371129124913991609166933002302389222381359147916291839189956023002619245391260120011511361180020592389261902801010941034985119516341893222324532800运用Floyd算法求出每个城市到其他城市的最短距离后，然后给出相应的约束条件如下：1.第j个城市只能承受一个供给点给它提供货物，即：其中l(i,j)判断第i个城市是否给第j个城市提供货物供给。2.对于任意一个城市i，假设不在该城市建配送点，则*(i)=0且l(i,j)0，因此可得约束条件：l(i,j)*(i)；假设在该城市建配送点，则*(i)=1且l(i,j)0或1，因此也可得约束条件：l(i,j)*(i)。综上，我们有约束条件：其中*(i)表示是否在第i个城市建立供给点。而总费等于建立供给点的花费固定费用与从供给点运输到需求点产生运输费用之和，现在我们要求建立供给点的数量使使总费用最小。即：其中D(i,j)表示第i个城市到底j个城市的最短路径，h(i)表示在第i个城市建立供给点的固定费用。于是我们可以建立0-1整数规划模型[4]，综合上述约束条件有：用Lingo软件编写程序〔见程序3〕求解得出结果，如表2所示：表2建立供给点城市及其相应需求点建供给点城市为提供货物城市41,2,3,4,5,15,16,27,46,4776,7,8,39,40,41,42119,10,11,12,13,32,36,37,38,432019,20,21,24,25,33,34,35,48,492322,2326262828,29,30,314514,17,18,44,45由lingo软件得出的结果可知，可以作为供给点的城市编号为4、7、11、20、23、26、28、45，运用matlab软件编写相应的程序〔见程序4〕，画出了49个城市中可以作为供给点以及不可以作为供给点城市〔实心点代表可以作为供给点的城市，空心点代表不可以作为供给点的城市〕，如图2所示。图2供给点城市以及不作为供给点城市再根据lingo软件[5]得出的各供给点所对应的供给的城市，可以利用matlab软件结合几何画板画出每个供给点城市到需要该供给点提供货物的城市线路图如图3所示。图3供给点到需求点路线图其中实心点即为可以建供给点的城市，箭头指向的点为承受货物供给的城市。有的城市和供给点并不直接相连，可以按照箭头所指的中转城市进展货物供给。4.模型的求解运用Floyed算法算出任意两个城市之间的最短公路长度，再用lingo软件求解得出建立8个供给点费用最少，这8个供给点城市编号分别为4、7、11、20、23、26、28、45。5.2影响度模型1.模型的分析问题二主要研究的是破坏尽可能少的道路来使总费用增加25%,于是可以假设当*条道路被破坏时，把该条道路的距离改成一个很大的值，这样就可以近似的看成这个道路是不通的。当*条道路被破坏时，根据新得到的数据用floyd算法重新求出各城市到其他城市的最短距离，求出其他没有供给点的城市距离最近的供给点及其之间的距离，最后就可以求出当该道路被破坏时的总费用。然后给出相应的约束条件，建立模型求当总费用增加25%时破坏的道路数量最少的情况，这样就求出了最少的道路数和具体的道路及总费用，程序流程图如图4所示。图4程序流程图2.模型的准备道路被破坏后，我们把相应的道路距离改为一个很大的值〔例如1000000000〕，这样当我们在用floyd算法求最短路时就可以把这条道路绕过去，就可以近似把道路看成是被破坏的。从建立的道路关系图4中可以直观的看出到达城市49的路只有一条，从城市21出发，因此如果这条路被破坏的话，城市49将得不到供给，因此这条道路不能被破坏，这样可以被破坏的路就只有8条，如表3所示。表3能够破坏的道路道路序号城市1城市21452343740410115192071745920213.模型的建立当*条道路被破坏后，该条道路就不能再被使用，以前运输经过该道路的只有改道，但总是沿最短路运输，因此需要破坏最少的道路，即：其中r(i)代表8条可以被破坏的路，y(i)为0-1变量，当y(i)为1时，代表破坏这条路；y(i)为0时，不破坏这条路。minR为可破坏道路数的最小数量。由于破坏方选择的策略是使对方总费用增加25%，即：其中S1为道路破坏前的总费用，S2为道路破坏后的总费用，被破坏的道路数小于8，即：，建立线性规划模型有：由Lingo软件求解可以得出被破坏的道路序列号以及被破坏的道路如表4所示，表4被破坏的道路序号被破坏的道路序号城市1城市2被破坏的道路1454→52344→34101111→105192020→197174545→179202120→21当被破坏的道路只有一条时一共有8种情况，当破坏的道路有两条时，一共有种情况，依次类推，由于情况比拟少，可以用遍历法把所有的情况及其总费用求出来，再对数据进展分析比照，找到当总费用比破坏前费用增加25%时破坏的道路数最少的情况。首先采用Floyd算法，运用MATLAB软件针对被破坏的道路中供给点城市的货物运输路线进展处理，其中破坏的道路影响的供给点城市有4〔〕、11〔〕、20〔〕、45〔〕。分别对各受影响的供给点进展分析，当受影响的供给点为4〔〕时，道路1、2被破坏后，供给点4〔〕向各城市供给的路线将发生变化，运用Floyd算法算出当道路1、2被破坏后供给点4到其提供货物的城市的最短距离，得出道路被破坏后的运输路线如表5所示。表5道路1、2破坏前后的运输道路受影响的供给点道路破坏前的运输道路道路破坏后的货物运输道路44→3→14→16→3→14→3→24→16→15→24→54→30→54→3→154→16→154→5→474→30→47当道路4被破坏时，供给点城市11〔〕的供货道路受到影响，采用Floyd算法求出当道路11→10被破坏时供给点城市11〔〕到各需求城市的最短路径，得出道路4被破坏后供给点城市11〔〕的运输路线如表6所示。表6道路4破坏后的运输道路受影响的供给点道路破坏前的运输道路道路破坏后的货物运输道路1111→1011→9→1011→10→1211→9→10→1211→10→3811→9→10→3811→10→4311→9→10→43当道路5、9被破坏时供给点城市20〔〕的供货道路受到影响，采用Floyd算法求出当道路5、9被破坏时供给点城市20〔〕到各需求城市的最短路径，得出道路5、9被破坏后供给点城市20〔〕的运输路线如表7所示。表7道路5、9破坏后的运输道路受影响的供给点道路破坏前的运输道路道路破坏后的货物运输道路2020→19→3320→48→18→19→3320→19→3420→48→18→19→3420→19→3520→48→18→19→3520→1920→48→18→1920→2120→48→18→19→2120→21→4920→48→18→19→21→49当道路7被破坏时供给点城市45〔〕的供货道路受到影响，采用Floyd算法求出当道路7被破坏时供给点城市45〔〕到各需求城市的最短路径，得出道路7被破坏后供给点城市45〔〕的运输路线如表8所示。表8道路7破坏后的运输道路受影响的供给点道路破坏前的运输道路道路破坏后的货物运输道路4545→1745→18→1745→17→1445→18→14运用MATLAB软件结合几何画板将改道后的运输道路图画出如图5所示，其中较细的实线表示不需要改道的运输路线，较粗的虚线表示改道后的运输路线；虚线连接的点表示需要作为中转点的城市，虚线的起点表示供给点，箭头指向的点表示被供给点。图5改道后的运输道路图破坏方选取的策略是使对方总费用增加25%且要求破坏的道路最少，将各受影响的供给点道路破坏前的运输费用和道路破坏后的运输费用整合如表9所示。表9道路破坏本钱增加情况道路序号增加本钱原本钱百分比19130891971181%21081168.5919711812%426931091971183%538162591971184%734705291971184%9186629.591971182%4.模型的求解观察表10道路破坏的线路，因为破坏方的策略是使对方总费用增加25%，所以可利用表10中的百分比〔道路破坏后，运输增加的本钱与原本钱的百分比〕进展线性规划，从而得到最优的结果。利用Lingo程序求解，得到破坏方的最正确破坏方案，即破坏路线的序列号为1、2、4、5、7、9，破坏的道路如图5中虚线所示：图5道路破坏路线图道路被破坏后，造成费用增加，参照表9可得最终费用为9197118+2716340.5=11577797元。5.3优先选择模型1.模型的分析针对该问题可以先计算出道路破坏之前的运输费用，道路受到破坏的平均运输费用，道路破坏之前的运输总费用，道路破坏后的运输总费用。列出破坏前后的运输费用应该满足的数学关系式，分别对64种情况进展讨论，得到在破坏最少的道路前提下，使得对方平均总费用最大。程序流程图为：2.模型的准备①运输时产生的费用可按照各种情况下的平均费用来考虑。如果破坏方选取的策略是使对方平均总费增加最大，同时需要破坏最少的道路。道路受破坏的平均费用为：，其中表示道路破坏之前的运输总费用，表示道路破坏后的运输总费用。道路破坏之前的运输费用：，道路受到破坏的平均运输费用应满足：其中是对方平均总费用的增加率，在〔〕越小的前提下越大越好②24、25两城市道路破坏，供给点城市对其供给并未受到影响；21、49两城市的道路破坏后49将得不到供给，对这两条道路选择破坏不会对对方平均总费用产生影响，因而这两条道路在道路破坏方案选择中不予考虑。对除24、25，21、49两条道路之外的其余7条道路的破坏前后的平均总费用例表如下，见表10。表10道路破坏前后平均总费用受破坏的道路破坏前的运输费用道路破坏改道破坏后的平均费用4→52427064→30→53075894→30→474→3735221.54→16→3→115556704→16→15→24→16→157→401359937→41→40103183.511→1081645011→9→10108324911→9→10→1211→9→10→3811→9→10→4320→19648495.520→48→18→19→33157060820→48→18→19→3420→48→18→19→3520→48→18→1945→1730737445→18→1765442645→18→1420→216650520→48→18→19→21186629.520→48→18→19→21→49从表1可以看出7、40两城市的道路破坏前的运输费用为135993，破坏后的运输费用为103183.5，破坏前后的运输费用反而减少，不能到达道路破坏的效果。③根据对六条道路破坏前后的平均总费用进展计算列表如下，见表11。表11破坏道路后增加的费用受破坏的道路破坏前运输费用道路破坏的平均费用增加的费用4→5242706281635.838929.84→3735221.51309535.45574313.9511→10816450949849.5133399.520→19648495.51155657.38507161.8845→1730737448090017352620→2166505138579.772074.73.模型的建立根据模型的分析及准备可以得出，可以破坏的道路有六条，再对六条道路分别进展考虑共有64种情况，建立模型[8]，即：如果同时破坏了条道路〔〕，则破坏之前的平均总费用等于：破坏条道路之后的平均增加的总费用为:等于每条到道路的增加的平均费用之和。对64种情况进展讨论，找出满足在最小且越大的情况下，选择破坏哪几条道路。不同破坏的道路个数对应的六组平均总费用中，取每组平均总费用中的最大值，如表12所示。表12平均总费用最大值破坏边的个数平均总费用中的最大值10.953935621.0163829231.02878682541.03975458251.05048708261.0590422371.06062564581.060625645根据表3用MATLAB作出破坏道路的个数与平均总费用最大值的走势图〔MATLAB作图程序见程序5〕如下：图6平均总费用走势图4.模型的求解根据图1分析，随着破坏的道路的数量的增加，平均总费用的最大值大体上呈现出一个上升的趋势，但当破坏的道路数为6时，平均总费用到达最大值为：元。因而选择破坏的道路序号为：1、2、4、5、7、9。§6误差分析优先选择模型中[6]，根据计算的道路受破坏的平均费用存有一定的误差。根据表11中的数据结合表13，道路破坏后的运输费用表表13道路破坏后的运输费用表受破坏的道路破坏后的费用4→53075894→3155567011→10108324920→19157060845→1765442620→21186629.5利用E*CEL对道路破坏前后及增加的运输费用作图。图7道路破坏前后及增加的运输费用图利用MATLAB对道路破坏前后及道路破坏的平均费用作图〔MATLAB作图[7]程序见程序6〕图8道路破坏前后及道路破坏的平均费用图图8中的蓝色折线条表示道路破坏的平均运输总费用，高于图7中黄色折线条表示的道路破坏前后的增加费用，低于道路破坏前的费用，因而不可防止的存有一定误差。§7模型的评价与推广6.1模型的评价1.优点(1)在解决最优问题时，分别运用MATLB和Lingo两个语言来实现模型的运算，两种语言很好的结合解决了问题；(2)在解决任意两城市之间最短距离时采用Floyd算法，准确度很高；(3)论文中对数据进展处理做了很多图表，使结果简单直观；(4)运用多种数学软件〔如MATLAB、Lingo〕，取长补短，使计算结果更加准确、明晰。(5)从破坏者角度出发，考虑炸路的价值问题，优先炸价值比拟高的路，模型具有完备性和通用性，实用价值高。2.缺点(1)在解决问题的过程，编程的比重相对于建立模型的比重偏大；(2)对一些数据进展了必要的近似处理，会带来一定的误差。6.2模型的推广在解决第一问时，我们尝试了穷举法，编写了matlab程序，但计算量太大，等待结果的时间很长。后来我们结合约束条件，运用lingo软件，把它转化为0-1规划问题，使模型大大简化，大大缩短了运行的时间。解决此问题的模型可以推广到交巡警效劳平台设置与调度优化问题中，交巡警效劳平台的管辖围分配及警力调度问题是一个具有实际背景的新课题，其本质是优化问题。涉及的主要知识背景为图论、整数规划等，可利用最短路径、最优指派等方法来求解。主要思想为根据实际背景设置约束条件，求解最优目标值，进而给出满足多个目标的最正确方案。与该论文所用方法不谋而合。参考文献[1]百度百科.配送中心，baike.baidu./link[2]华友．运筹学[M].中国科技大学.2008.8.[3]中庚．实用运筹学[M].清华大学.2007.12.[4]桂元，黄己立．数学建模[M]．中国科技大学.2008.8.[5]金星，薛毅．优化模型与LINDO/LINGO软件[M].清华大学.2005.7.[6]冬梅；大学生数学建模竞赛与教学策略研究；师大学2008。[7]胡守信,柏年,基于MATLAB的数学实验,:科学,2004.6第一版。[8]启源等.数学模型〔第三版〕[M].高等教育.2003.8。附表1:表1各城市坐标编号城市坐标*(公里)坐标Y(公里)编号城市坐标*(公里)坐标Y(公里)13639268526130416882**371226012730072030334882465282562224443326244429238123245呼市32382771302788250964196295631乌市1332330574312321032台北4263106984386343033353870294177175634澳门3470696103918182135352673711406116303639289711237801788374201160313402911623840162285143676142239408926131537152322404296292016342920924140953374173507162442海拉尔451227101833941357433751205519343979944333418932029357604532291633213140450463054229022276915084730892749232545164348304491924277811744930532612523701025附表2:表2各公路段及里程表序号城市1城市2距离〔公里〕序号城市1城市2距离〔公里〕1121205215433492132705316175403155405416275504167995516434735115420561644285614084457171838072337058174440682153605917453629342106018197801031531161182410101131644062184550812455306318486641341643064192071014427630651921580154307606619341301653072067193512717540152168193668818547186692021560196733070202465020639387712025820216407277220483052278230732149270237404297422233402474134775222449025842819762225109026910280772227910279111907822457952891584079232599029101127980232621703010121608123279203110146608224256503210156808324485603310385988425262320341043325852629194035111388086263126723611146408727287003711371538827306403812146108927446373912166509027463044012175409128292304112434359228305004213146809328311980431319102094304755444133249095333536451336266963536591461337592973843368471417270984041304481418640994042929491419860100414266950151643010144454665115383611024647541附表3:表3各城市作配送中心的固定费用城市费用(元)需求量(吨)城市费用(元)需求量(吨)11123584123226310085121000000000974279411847743733400965281963843234272080358291000000000194516948022330114760151610000000007153110000000002347457824753321000000000246810000000009893310000000007019100000000013913410000000005510663936624351000000000233114116166773610000000001741237012048737100000000056813580032636381000000000761145266804953910000000005831573324860340289104317168767367214110000000002041776060883442100000000027218585504642437204809481995577678644699200115020526680693452438084012110000000001564610000000002242224753203257471000000000217236846081126481000000000366242766403644910000000005525403560531〔注：1000000000表示该点不用，费用太高〕附表4:表4破坏道路及概率道路序号城市1城市2破坏概率1450.62340.737400.45410110.5519200.55624250.4717450.5821490.6920210.6程序1:A=[3639371234883326323841964312438641773918406137804029367637153429350733943439293531402769254527782370130430072562238127881332426335383470352639284201401640894296409545123751333432293054308930443053;2685260124652444277129563210343017561821163017881162142223222092162413577997604501508164311741025168820302244232425093305106970269673797116032285261329203374271020551893163322902749919261];*=A(1,:);y=A(2,:);plot(*,y,'*')te*t(3639,2685,'1');te*t(3712,2601,'2');te*t(3488,2465,'3');te*t(3326,2444,'4');te*t(3238,2771,'5');te*t(4196,2956,'6');te*t(4312,3210,'7');te*t(4386,3430,'8');te*t(4177,1756,'9');te*t(3918,1821,'10');te*t(4061,1630,'11');te*t(3780,1788,'12');te*t(4029,1162,'13');te*t(3676,1422,'14');te*t(3715,2322,'15');te*t(3429,2092,'16');te*t(3507,1624,'17');te*t(3394,1357,'18');te*t(3439,799,'19');te*t(2935,760,'20');te*t(3140,450,'21')te*t(2769,1508,'22');te*t(2545,1643,'23');te*t(2778,1174,'24');te*t(2370,1025,'25');te*t(1304,1688,'26');te*t(3007,2030,'27');te*t(2562,2244,'28');te*t(2381,2324,'29');te*t(2788,2509,'30');te*t(1332,3305,'31');te*t(4263,1069,'32');te*t(3538,702,'33');te*t(3470,696,'34');te*t(3526,737,'35');te*t(3928,971,'36');te*t(4201,1603,'37');te*t(4016,2285,'38');te*t(4089,2613,'39');te*t(4296,2920,'40');te*t(4095,3374,'41');te*t(4512,2710,'42');te*t(3751,2055,'43');te*t(3334,1893,'44');te*t(3229,1633,'45');te*t(3054,2290,'46');te*t(3089,2749,'47');te*t(3044,919,'48');te*t(3053,261,'49');B=[11111122333444455566677789991010101010101111111212121213131313131414141515151616161617171718181818191919191920202020212222222222232323242425262627272727282828303335384040414446;235615403154151651627303040477394084041421011151112141538431314371416174314193236371718191638431727434418444519244548202134353621242548492324252745252627254826293128304446293031473536434142424547];[pq]=size(B);form=1:q;line([A(1,B(1,m))A(1,B(2,m))],[A(2,B(1,m))A(2,B(2,m))],'Marker','.','LineStyle','-')end程序2:n=49;a=zeros(n);a(1,2)=120;a(1,3)=270;a(1,5)=540;a(1,6)=799;a(1,15)=420;a(2,3)=370;a(2,15)=360;a(3,4)=210;a(3,15)=311;a(3,16)=440;a(4,5)=530;a(4,16)=430;a(4,27)=630;a(4,30)=760;a(5,30)=720;a(5,40)=1521;a(5,47)=186;a(6,7)=330;a(6,39)=387;a(6,40)=727;a(7,8)=230;a(7,40)=429;a(7,41)=347;a(8,42)=819;a(9,10)=280;a(9,11)=190;a(9,15)=840;a(10,11)=279;a(10,12)=160;a(10,14)=660;a(10,15)=680;a(10,38)=598;a(10,43)=325;a(11,13)=880;a(11,14)=640;a(11,37)=153;a(12,14)=610;a(12,16)=650;a(12,17)=540;a(12,43)=435;a(13,14)=680;a(13,19)=1020;a(13,32)=490;a(13,36)=266;a(13,37)=592;a(14,17)=270;a(14,18)=640;a(14,19)=860;a(15,16)=430;a(15,38)=361;a(15,43)=349;a(16,17)=540;a(16,27)=550;a(16,43)=473;a(16,44)=285;a(17,18)=380;a(17,44)=406;a(17,45)=362;a(18,19)=780;a(18,24)=1010;a(18,45)=508;a(18,48)=664;a(19,20)=710;a(19,21)=580;a(19,34)=130;a(19,35)=127;a(19,36)=688;a(20,21)=560;a(20,24)=650;a(20,25)=820;a(20,48)=305;a(21,49)=270;a(22,23)=340;a(22,24)=490;a(22,25)=1090;a(22,27)=910;a(22,45)=795;a(23,25)=990;a(23,26)=2170;a(23,27)=920;a(24,25)=650;a(24,48)=560;a(25,26)=2320;a(26,29)=1940;a(26,31)=2672;a(27,28)=700;a(27,30)=640;a(27,44)=637;a(27,46)=304;a(28,29)=230;a(28,30)=500;a(28,31)=1980;a(30,47)=554;a(33,35)=36;a(35,36)=591;a(38,43)=368;a(40,41)=304;a(40,42)=929;a(41,42)=669;a(44,45)=466;a(46,47)=541;a=a+a';M=ma*(ma*(a))*n^2;%M为充分大的正实数a=a+((a==0)-eye(n))*M;path=zeros(n);fork=1:nfori=1:nforj=1:nifa(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=k;endendendenda,path程序3:sets:weizhi/1..49/:*,jijian,*uqiu;

assign(weizhi,weizhi):D,l;

endsets

data:

jijian=ole('C:\Users\Administrator\Desktop\数据源','cost');

*uqiu=ole('C:\Users\Administrator\Desktop\数据源','need');

D=ole('C:\Users\Administrator\Desktop\数据源','shortestpath');

enddata

min=sum(weizhi(k):*(k)*jijian(k))+sum(weizhi(j):sum(weizhi(i):*uqiu(j)*D(i,j)*l(i,j)))*0.5;

for(weizhi(i):bin(*(i)));

for(assign(i,j):bin(l(i,j)));

for(weizhi(j):sum(weizhi(i):l(i,j))=1);

for(weizhi(i):for(weizhi(j):l(i,j)<=*(i)));

End

程序4:A=[3639371234883326323841964312438641773918406137804029367637153429350733943439293531402769254527782370130430072562238127881332426335383470352639284201401640894296409545123751333432293054308930443053;2685260124652444277129563210343017561821163017881162142223222092162413577997604501508164311741025168820302244232425093305106970269673797116032285261329203374271020551893163322902749919261];a=[26,28,23,20,4,45,7,11];*1=A(1,a);y1=A(2,a);b=[1,2,3,5,6,8,9,10,12,13,14,15,16,17,18,19,21,22,24,25,27,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,46,47,48,49];*2=A(1,b);y2=A(2,b);plot