中南大学 数学建模 lingo matlab 优化建模论文 运输问题的图论优化模型

运输问题的图论优化模型摘要本文根据题设城市的道路情况和客户需求情况，以客户所在位置为节点，以客户间所可以直接连通的道路为边建立有向图。建立了任意两点间最短路径长度和路径的计算模型，建立了遍历所有节点的最短路径模型并做了模型分析和拓展讨论。利用0-1规划模型和上述两个模型探索了分2辆有限容量汽车运输的总路径最短最优解。利用动态规划模型和逼近算法及前述模型探讨并实现了有限容量车的规划问题，并对问题作了拓展性分析和模型评价。第一问我们考虑用最短路径模型，首先用Matlab实现了Floyd算法，计算出了任意两点的最短路线长度，并利用Floyd的原理通过正向追踪法找出任意两点的最短线路径。用Pascal进一步编写程序实现Floyd路径，并汇总了中转次数，发现全图上有两个路径需要经过两点中转才能获得最短路径，有一个路径需要经过三点中转才能获得最短路径，其余各路径至多只须经过一点中转即可获得最短路径。借鉴前面的Floyd最短路模型作为基础，我们研究了最短运输路径问题，发现这是一个遍历所有点的最短路径问题，在经典模型中没有相关类似的描述。我们根据数据量作了评估，发现遍历枚举模型的时间复杂度为O(n3+n!)，对于只有10个节点的问题，这个时间复杂度可以在计算机1秒的运算内解决，故采用Pascal编写了一个枚举程序，得到了最优解。同时我们也探索了另外两个模型，分别是“遍历贪心次优模型”和“插入逼近&遗传算法近似最优模型”（简称遍历遗传模型）。发现前者在无向图中有较高概率得到最优解，但随着图的复杂性和有向图的引入，正确率降低，该模型计算的时间复杂度为O(n3+n2)。后者利用遗传算法在比对足够多次后我们用SPSS统计得到最优解的概率趋于100%，针对本题我们设置的比对次数是1000,无法得到最优解的概率小于10-30（参见4.3）,该模型计算的时间复杂度是O(n3+1000·n·n2)。我们可以发现对于10个节点以下问题用枚举算法更优，10个节点以上的问题需要考虑用近似算法去寻求最优解更好。关于本文探讨的图，得到的最优结果为最短路程225，且仅有一种方案。参考前述观点，我们采取0-1规划模型配合枚举找到最优解，若只考虑每个客户都一次就拿到货物，则0-1规划的时间复杂度是O(2n)；若考虑同一个地点两辆车可能各送一部分，0-1规划的时间复杂度是O(22n)。经过分析我们发现n<10的情况下，计算机可以在较短时间内算得O(22n)，故我们用此方法得到了全局最优解，总共有4种方案，2种方案每个客户只需要收货一次，两车行驶的最短路程之和为280。关于出车问题安排，我们分了两个步骤来建立模型，首先，我们证明发现派出的车尽量少，产生的费用才可能最优（详见7.2）。因此我们用动态规划模型生成任意一种可行的使用最少车辆的方法（如7.3,7.4所述），然后再保证不超过总容量的条件下通过任意两车转移或者交换货物，检查对应两车所需要走的总路程是否有缩短，若缩短则保留，若无缩短则放弃修改，直到一次完整比较后未发生任何改变则说明已经找到了最优解，我们找到的最少总费用为655元。为了验证算法，我们也尝试构造了一个枚举模型，通过Pascal筛选可以装下的方案发现，从10个货物中选3个货物总共有35种可行方案，从10个货物中选2个货物总共有43种可行方案。在用组合算法把方案汇总并作合理性判断，然后比对得出最优解。关键字：Floyd改进模型遍历贪心模型遍历遗传模型遍历枚举模型0-1规划模型

问题重述快递公司要为10个客户配送货物，10个客户间的道路关系如附件一的邻接矩阵所描述，现分别需要解决如下问题：1）接到临时派遣通知时，迅速找到从当前点到达目标客户的最短线路方案。（拟给出2号客户到10号客户间的最短路径方法。）2）出发给所有客户送货物，并回到出发地的所走的最短线路方案。3）用两辆容积是50的货车送货，十个地点所需要的货量分别为8，13，6，9，7，15，10，5，12，9。给出方案确定两辆货车应分别给哪几个客户配送货物，按照什么样的路线送，使路线合最短。送货后货车需要回到出发点。4）若用容积25的货车运货，每出一辆车的出车费为100元，运货的价格为1元每公里（不考虑空车返回的费用），如何安排车辆才能使得运输公司运货的总费用最省。问题分析问题背景分析现代生活对于效率的要求越来越高，近几年又提倡构建节约型社会，因此如何高效、节约的选择路线不仅仅是快递公司所面临的问题，同样也是百姓出门所面临的实际问题，本论文以快递公司的运输问题为例来描述算法，但算法同样可以引申到社会实际生活中来，该问题具有很强的实际意义和价值。问题要求分析据题意，解决该问题关键在以下几个方面：找到任意两点间的最短路线长度及路径。找到经过一系列点的最短路径长度及路径。在运输有限制的条件下，如何分配，使得车行总路程最短。在换算为费用问题的情况下，如何评估和分配，使得运输总成本最低。基本假设附件一的邻接矩阵的道路均可通行，不存在堵车、施工等问题。每次提货地点都在客户1所在的位置，但是给客户1送货仍需要占用货车的空间。假设货物可以分割。在用容量为50的货车运输时，客户愿意分多次接受货物。在用容量为25的货车运输是，客户只愿意一次将货物接受完全。符号说明n ：表示有个客户；v ：每辆车的总承载量；i ：表示第个客户； ：表示第个客户所需的货物量； ：表示个客户分配车辆后的剩余车载量； ：表示将第个客户的货物分配给了车辆； ：表示每辆车装完货物后的剩余载重； ：表示第i辆车装载的第j种货物； ：表示第i个客户。图中表示节点。 ：表示第i个客户到第j个客户的路。图中表示边(弧)。 ：表示第i个客户到第j个客户的路程。图中表示边权 ：表示0-1变量

模型的建立及求解建图重述矩阵矩阵分析有向图无向图的判定首先我们发现图并非关于i=j这条对角线对称，故说明存在有e(i,j)e(j,i)，即两点间的边权值根据其方向不同可能不同。因此无向图无法描述，只能用有向图描述。出度入度不等V1的出度等于E[1,j]0且E[1,j](j[1,n])的点的个数。V1的入度等于E[1,j]0且E[i,1](i[1,n])的点的个数。显然可发现有部分节点的出度与入度不相等，可以说明该有向图的部分边为单边，可以理解为道路中的单行线。边点分析矩阵中的每一个数值代表一条边，故可知图总共有64条边，有10个顶点，故假若有算法可以使其进行边点转换。则所生成的图的点将达到64个，计算规模可能更大，复杂度可能更高。有向图概览根据邻接矩阵我们制作出了该邻接矩阵所描述的有向图可以看出题目所述的图相当的复杂，因此我们采用（i,j,k）的方式描述边权，即（i,j,k）的含义为Vi到Vj有一条边，边权为k。根据此图我们可以进一步验证1.2的分析结果，此图也为手工验算程序的结果提供了方便。

Floyd模型解题思路及结果解题思路根据问题的描述该问要解决临时接到通知时选择一条道路到达目的地的方法，简化来看这就是一个寻找从当前点到目标点的最短路问题。按照问题要求，我们需要给出有向图中找到从V2到V10的最短路线的路径。根据经典问题求最短路径的解法[1]，我们可以用dijkstra算法或者Floyd算法，dijkstra算法可以算出从某一点出发到其他所有点的最短路径。Floyd算法可以一次性计算出任意两点的最短路径。通过综合分析这道题目，为了进一步扩展得到任意两点的最短路径为后续问题做好基础，我们选择了用Floyd算法，直接算出任意两点间的最短路长度和对应路径。结果经过本模型可以算得最优解：V2到V10的最短路径是：2-->3-->8-->9-->10其总长度为：85Floyd算法描述Floyd算法计算最短路线的长度Floyd算法的优势是，它可以直接求出含负权的网络中任意两点之间的最短路，只是相对Dijkstra算法要稍微复杂些。Floyd计算的时间复杂度是O(n3)，空间复杂度是O(n2)令网络N=（V，E，W）的权矩阵为其中权矩阵中的用N（i,j,m）表示顶点集合，导出的N的子网络。特别的，N（i,j,0）表示由顶点集导出的N的子网络。把网络N（i,j,m）中最短路的长记为，则显然有如下结论：（1）；（2）N（i,j,n）=N，因此为N中最短路的长；（3）N（i,j,m-1）是N（i,j,m）的子网络，故；（4）N（i,m,n）=N（i,m,m-1）,N（m,j,m）=N（m,j,m-1）,所以，。Floyd算法计算最短路线的路径为了求网络N（i,j,m）中最短路的长同时求出N（i,j,m）中最短路路，引“进后点标号”。令表示路的第一条弧的箭头的下标，显然，。若已经知道，当时，则；否则，。若，=k，则是D中最短路，从而的第一条弧即为的第二条弧，依次类推，可以得到上的所有弧。这种方法称为正想追踪法。Floyd的使用条件根据Floyd算法使用的条件发现：1）本题中网络N=(V,E,W)不含负回路，则对一切i,j=1,2,…,n，满足2）对于任意的i,j,m,不超过网络N（i,j,m）中任何一条路的长。因此题目的所生成的有向图可以使用Floyd算法。程序的Matlab实现及相关中间状态W=程序步骤及说明输入W矩阵(W同附件一)，存入a，当两点不能直接到达时及两点之间的距离为时，这两个点之间的距离描述为M，程序中赋值为10000。为记录走过的路径，建立一个初始为全零的与a矩阵同大小的path矩阵。开始floyd算法比较a(i,j)>a(i,k)+a(k,j)是否成立，若成立则将a(i,j)替换成a(i,k)+a(k,j)，与此同时路径中代表从i出发到j的最短路径需要经过k来中介，因此path(i,j)=path(i,k);当场经过k,i,j[1,n]的所有情况后，原a被修正成了SSSP路径即任意两点间的最短路径。而path(i,j)中的值则表达从i到j的最短路径中，下一步该到那个点。程序核心代码（MatLab）%floyd算法fork=1:10fori=1:10forj=1:10ifa(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=path(i,k);endendendend%输出路线结果的过程i1=input('请输入起点');i2=input('请输入终点');disp(i1);whilei1~=i2%i1==i2说明已到达终点，停止探索，结束程序。i1=path(i1,i2);disp(i1);end;%完全代码请参看附录程序结果分析根据W矩阵，我们算得：最短路径矩阵其中可看到a(2,10)=85,即2到10的最短路径长度为85。路径记录矩阵我们在此演算从V2到V10路径的计算过程：由path(2,3)=3可知从V2到V10得先经过V3；由path(3,10)=8可知从V3到V10得先经过V8;由path(8,10)=9说明V8到V10需要经过V9,由path(9,10)=10，说明V9到V10可直接到达。故送货员要在下完客户2的货然后要送货给客户10，所走的路径是：V2V3V8V9V10（总长度为85）模型评价该问题直接采用了经典算法Floyd算法，故算法可靠稳定准确，可以得到最优解。利用该模型可以容易的计算出任意两点间的最短路线长度及最短路线路径。模型补充由于后面要解决的问题复杂性增高，因此我们用Pascal语言编写了一个更便于人机交互和模型补充的程序。算法与前述类似，但稍有改进。详细代码见附录六：问题1的pascal程序（模型2）。遍历贪心模型解题思路及结果解题思路分析这一问题，我们可以发现，这算个问题简化描述，就是找一条最短路径经过所有的节点并返回，这一问题没有经典算法可以直接使用，因此只能够造算法。假若要构造时间复杂度尽可能低的算法，我们当然首先想到了容易构造出O(n2)为时间复杂度的贪心算法，此算法最终会遍历所有的点，因此我们命名叫做便利贪心模型。贪心算法是不断寻找局部最优解进而产生全局最优解的算法，因此它需要各个局部都相对独立，这样才能得到全局最优解，但是题述问题并不是一个局部独立问题，因此使用便利贪心算法只能得到近似解。结果经过后面多种算法运算比较，发现此算法在本题数据下得到的不是最优解，只是近似解，路程总长度为240，而最优解总长度为225，算法请参考4遍历遗传算法和5遍历枚举算法。次优解得路径是V1V5V7V5V2V3V4V8V9V6V9V10V1贪心算法所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。[2]遍历贪心算法假设现有一最短距离矩阵X=，按贪心算法，从第一个节点出发找到矩阵第一行不为零的最小数，然后转入第i行找不为零的最小的数且j在前面不曾取入,重复这样找下去，遍历所有行。算法样例1下面为说明贪心算法有一定的可行性我们以一个简单的例子说明：图3.1如图3.1所示的网络图为一个负权的无向网络图，根据floyd算法可以得出该网络图任意两点之间的最短距离构成的矩阵为运用贪心算法算出的路径及两点间的最短距离如下所示最短路程为22；贪心过程如下：第一行找到非0，最小，且未到过的点为：2第一行找到非0，最小，且未到过的点为：3第一行找到非0，最小，且未到过的点为：4第一行找到非0，最小，且未到过的点为：5因此得到的路径如图3.2。112341513387图3.2图3.2并不是最终结果，只是遍历时到达关键点的顺序，关键点之间用最小路径相连就得到了真正的遍历路径。如图3.3：112351433113123552图3.3算法样例2但是贪心算法得出的是局部最优解，整体最优解不一定就会等于局部最优解，如图3.4所示的网络图为一个负权的无向网络图，根据floyd算法可以得出该网络图任意两之间的最短距离矩阵为（图3.4）运用贪心算法算出的路径及两点间的最短距离关键点如图3.5所示总路线长：26112341515389图3.5其路径如图3.6：112351433113143554图3.6但上述结果事实证明不是最优解，最优解如图3.7。11254331137545图3.7根据图3.7计算，总路线长：25故比贪心算法更优，说明贪心算法有其局限性。程序的Pascal实现程序步骤及说明程序较为简单，就是利用一个集合保存已经走过的点，每次找到符合约束条件的点加进集合，直到全部加进。加入的顺序就是关键序列的顺序。在通过两点最短路径扩充，就得到了所需路径。程序核心代码（Pascal）c[1]:=1;ci:=1;s:=0;whileci<ndobegink:=32760;fori:=1tondobeginm:=1;forj:=1tocidoifc[j]=ithenm:=0;if(b[c[ci],i]<>0)and(m=1)and(b[c[ci],i]<k)thenbegink:=b[c[ci],i];c[ci+1]:=i;end;end;inc(ci);s:=s+kend;s:=s+b[c[ci],1];模型评价此算法是非完美的，但时间复杂度较低，因此在数据量上千的情况时，不需要得到精确解，只需要有近似值时，可以用这种模型。遍历遗传模型解题思路及结果解题思路由于贪心算法的局限性，前文通过遍历贪心模型得到的解并不一定是最优解，接下来我们通过遍历遗传模型来求这个最短路程，并证明这样得出的解一定是最优解。结果结合遍历遗传算法与插入法得到从提货点出发给10个客户配送完货物后再回到提货点所行驶的最优解路径为V1V5V7V6V3V4V8V9V10V1最短行驶路程为225。插入法的描述插入法的核心思想就是，根据元素（送货点）插入顺序的不同，得到不同的排列，通过计算相邻两点间的最短距离并且累加求和，选择路程最短的排列，然后不断的把剩下的点按照之前的方法进行插入，最终得到最优的路径。插入法的步骤对于第二个问题，我们已经知道货车的提货点和客户1(点)是在同一个地方，意思是货车从1出发。 插入法的算法： 对于给定的插入排列（），开始路径为road=-，。、开始插入，；比较每一种插入方式下的相邻两点最短路径的总和，取其中的最小值，并且把原先的优化路径更改为road=-…--…-。、如果，那么停止，否则就继续插入下一个点。插入法的范例说明对于一个这样的两点距离用邻接矩阵的图表示，求从开始出发，通过所有点且返回的最短路径的问题，网络图如图4.1所示：（其中表示两个客户之间无直接的路线到达）图4.1利用Floyd算法，得到任意两点之间的最短距离，如表4.1所示12345105638250739337045453406589560表4.1插入法的图形表达如图4.2：插入序列13245插入序列13245路径131Stage2插入2插入21231路程151321路程18最优路径1231Stage3 插入4路径1231插入414231路程1612431路程1512341路程21最优路径12431路径11Stage1插入3插入3131显然最优路径131Stage4插入5插入5152431路程27125431路程27124531路程22124351路程25最优路径124531路径12431Stage5路径124531由此我们我们对于13245这样的插入顺序列得到的最短路径是22，其中最短的经过实际路径为1-3-4-2-4-5。4．3遗传算法的描述遗传算法的核心思想是模拟自然界生物进化过程，采用人工进化的方式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。4．3.1遗传算法操作步骤1）编码我们将每一个插入序列作为一个生命体，那么给其赋予一定的基因，这个过程叫做编码初始群体的生成由于遗传的需要，我们必须设定一些初始的生物群体，让其作为生物繁殖的第一代，需要说明的是，初始群体的每个个体都是通过随机方法产生的，这样便可以保证生物的多样性和竞争的公平性。适应度评估检测生物的进化服从适者生存，优胜劣汰的进化规则，因此，我们必须规定什么样的基因是“优”的，什么样的基因是“劣”的，在这里，我们认为那些使得路程短的基因是优的，而使路程长的基因是劣的。选择接下来，我们便可以进行优胜劣汰的过程，这个过程在遗传算法里叫做选择。注意，选择应该是一个随机的过程，基因差的生物体不一定会被淘汰，只是其被淘汰概率比较大罢了，这与自然界中的规律是相同的。因此，我们可以采取赌论的方式来进行选择。交叉操作接下来进行交叉繁殖，随机选出两个生物体，让其交换一部分基因，这样便形成了两个新的生物体，为第二代。变异生物界中不但存在着遗传，同时还存在着变异，在这里我们也引入变异，使生物体的基因中的某一位以一定的概率发生变化，这样引入适当的扰动，能避免局部极值的问题。以上的算法便是最简单的遗传算法，通过以上步骤不断地进化，生物体的基因便逐渐地趋向最优，最后便能得到我们想要的结果。流程图如图4.3所示编码和初始群体形成编码和初始群体形成适应度的检测评估选择交叉变异图4.34.3.2模型改进根据插入法改进模型，我们就可以对于这样一个从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线的问题给出最优解的答案。其中，最短行驶的距离是225。走过的实际路线为 1576348910214．4程序的Pascal实现及相关中间状态4．4．1程序核心代码（Pascal）forl:=1to1000dobegin//变异1000次s:=32760;randomize;fori:=1to100dobegin//突变频率j:=round(random*(n-2))+2;k:=round(random*(n-2))+2;if(j>n)or(j<1)thenj:=n;if(k>n)or(k<1)thenk:=1;i1:=c[k];c[k]:=c[j];c[j]:=i1;end;d[1]:=1;f[1]:=1;f[2]:=1;fori:=ndownto2dobegin//开始尝试插入法s:=32760;forj:=2ton-i+2dobegind:=f;m:=0;fork:=n-i+2downtojdobegind[k+1]:=d[k];end;d[j]:=c[i];fork:=1ton-i+2dobeginm:=m+b[d[k],d[k+1]];end;ifm<sthenbegins:=m;e:=d;end;end;f:=e;end;//比较插入法值的大小ifs<ssthenbeginss:=s;g:=f;end;end;模型评价与分析尽管插入遗传的寻优方式带有一定的随机性。但是当我们对于所有插入顺序序列得到的解用SPSS13进行频数统计，得到结果如下表4.2所示：FrequencyPercentValidPercentCumulativePercentValid225.002483230.0012234333.733.740.6235.008220822.722.763.2240.00260697.27.270.4245.00279077.77.778.1250.00283177.87.885.9255.003297260.00123313.43.498.4265.0036771.01.099.4270.001973.5.599.9275.00144.0.0100.0280.00101.0.0100.0Total362880100.0100.0表4.2发现最优解出现的概率为6.8%。当变异的次数达到43时，得不到最优解的概率为0.048。根据概率论中小概率事件的定义，如果一个事件发生的概率小于0.05时，可以认为这个事件不会发生。我们可以认为，这个遍历遗传算法，有及其顽强的鲁棒性，可以求到问题的最优解。遍历枚举模型解题思路及结果解题思路同前两模型要解决的问题一样，这是一个找一条最短路径经过所有的节点并返回的模型。前两个模型中一个是近似算法，一个是逼近最优解算法，但都不能说100%得到最优解。因此我们构造出了这个遍历枚举模型。所谓枚举，就是把所有的可能性都列出来，在做比较。若关键点包含有所有点，我们发现遍历路径的总长度只取决于关键点的顺序。因此我们利用排列的模型不断生成新的序列，并把产生序列作为关键序列，比对并计算，从而得到最优解。n的排列数为n!,故用遍历枚举模型只能解出较少点数的图。10个点正好为临界值范围内，故本题可以利用此算法得到最优解。结果最优解总长度为225，与遍历遗传算法所得相同。最优解得路径是：V1V5V7V6V3V4V8V9V10V1枚举算法描述枚举算法是先设置一组初初状态，通过特定的运算使其状态发生改变，经过有序的有限次数的改变，到达末状态，此时经过了所有状态的算法。这种算法的优越性在于可以根据程序需要做必要的剪枝操作以便简化程序。遍历枚举算法如解题思路所述，利用排列的经典算法产生序列，在利用程序将关键点扩充成运输路径。比对路径长度就可以的到最优解。程序的Pascal实现及相关中间状态程序核心代码（Pascal）proceduresol;//计算最短路，比较是不是比前面的方案更优，更优的话则记录下来。vari,j,k:integer;begink:=0;fori:=1ton-1dok:=k+b[plan[i],plan[i+1]];k:=k+b[plan[n],1];ifk<sthenbegins:=k;c:=plan;end;//main主程序部分的调用s:=32760;fori:=1tondoplan[i]:=i;sol;repeat//排列序列的生成经典算法findi;ifi>1thenbeginfindj;change;ifplan[1]<>1thenbreak;sol;end;untili<=1;模型评价毫无疑问这个模型是既具有价值的，因为它是唯一个可以拿到最优解的模型，因为它尝试了所有的可行方案，但是由于时间复杂度很高，因此在点数很多的时候该算法无法算出结果。但该算法为近似解得算法改进奠定了基础。因此该算法的价值不容忽略。模型拓展该模型可以拓展加入比判断，输出最优解的所有情况。因此经过本模型计算后，我们可以放心大胆的说，最有序列有且只有一个，路程为225的这个解法是该图遍历点的路径的最优解。0-1规划模型6．1解题思路及结果6．1．1解题思路0-1目标规划法是用来处理选型问题的多维性，其中自变量取值只能取0和1两个值。我们可以通过0-1规划模型为十个客户的货物分车装载运输。6．1．2结果两辆小车分配所需运送的货物后行驶的最短路线按卸货顺序有4种分配方式：方案1.卸货位置:car1:17691car2:152348101实际路径car1:V1→V7→V6→V9→V1car2:V1→V5→V2→V3→V4→V8→V9→V10→V1方案2.卸货位置car1:17691car2:1523489101实际路径car1:V1→V7→V6→V9→V1car2:V1→V5→V2→V3→V4→V8→V9→V10→V1方案3.卸货位置car1:1769101car2:1523481实际路径car1:V1→V7→V6→V9→V10→V1car2:V1→V5→V2→V3→V4→V8→V9→V1方案4.卸货位置car1:1769101car2:15234891实际路径car1:V1→V7→V6→V9→V10→V1car2:V1→V5→V2→V3→V4→V8→V9→V16．2建立模型6．2．1模型建立c假设第一辆车用十个0-1变量（j=1~10）来控制，第二辆车也用十个0-1变量（j=1~10）来控制。，其中i=1~2,j=1~10；因表示第j个客户所需的货物量，设函数dd(n,c1,c2,…,cn)为遍历中不为0的结点的最短路径长度。实现方法为前述3个模型。由此我们可以建立模型：minZ=dd(n,1x11,2x12,3x13,…,10x110)+dd(n,1x21,2x22,3x23,…,10x210)s.t.

s.t.6．2．3模型说明由条件可知不会同时为0，故只能两个中一个为0，一个为1，或两个都为1。1）当=0，=1时，说明第j个客户的货物由第二辆车来运送；2）=1，=0时，说明第j个客户的货物由第一辆车来运送；3）=1，=1时，说明第j个客户的货物拆分为两份，分别由第一辆车和第二辆车运送。重量判断假若没有货物拆成两份的情况，重量很好判断，两辆车分别小于等于25就是可以满足的重量。在有货物拆分的情况下，经过分析发现，除了需要拆分的货物外，其余货物总合要小于25即重量会有合格的方案。程序实现proceduremake_xl;//序列生成模块vari,j,k:integer;begin//repeati:=n*2;whilexl[i]<>0dodec(i);ifi<1thenover:=true;xl[i]:=1;forj:=i+1ton*2doxl[j]:=0;forj:=1tondoifxl[j]=0thenxl[j+n]:=1;xl[1]:=1;xl[1+n]:=1;{k:=1;forj:=1tondoifxl[j]+xl[n+j]=0thenbegink:=0;break;end;}//if(xl[1]<>1)or(xl[1+n]<>1)thenk:=0;//until{(k=1)or}(over);end;functionkeyun:boolean;//超重判断模块vari,j,k,w1,w2:integer;pd:boolean;beginw1:=0;w2:=0;k:=0;pd:=true;fori:=1tondobeginif(c1[i]=1)and(c2[i]=0)thenw1:=w1+zl[i];if(c1[i]=0)and(c2[i]=1)thenw2:=w2+zl[i];if(c1[i]=1)and(c2[i]=1)thenk:=1;if(c1[i]=0)and(c2[i]=0)thenpd:=false;end;if(w1>50)or(w2>50)thenpd:=false;ifk=1thenif(w1=50)or(w2=50)thenpd:=false;keyun:=pd;end模型评价该模型巧妙利用0-1规划的思想，具体问题具体分析，进而将问题各种因素全部都考虑囊括在内，是一个标准的完全算法。假若用户不允许货物拆分的话，那么可以把规划的位数从20位缩小到10位，即两辆车总有一辆送。动态规划交换逼近模型解题思路及结果解题思路本文在前一问的基础上，增加了出车的数量，故首先我们要判断到底需要多少辆车，通过动态规划的思想，我们发现最少要用4辆车。但究竟4辆车更优还是5辆车更优，我们给出了相关证明。证明发现4辆车的结果比5辆车的更优，然后，我们在保证不超重地情况下，采取交换两车物品判断两车所走的路径是否更优的逼近的方法，不断逼近最优值。当一次完整的比对所有车后没有发生变化，说明找到了最优解。结果有两组等价结果所需要价格为655元，方案分别为：方案1.卸货位置car1:12car2:76car3:1034car4:589实际路径car1:V1→V1→V5→V2car2:V1→V7→V6car3:V1→V9→V10→V3→V4car4:V1→V5→V8→V9方案2.卸货位置car1:52car2:76car3:189ca4:1034实际路径car1:V1→V5→V2car2:V1→V7→V6car3:V1→V1→V5→V8→V9\car4:V1→V9→V10→V3→V4相关证明反证法：假设开出5辆车，每辆车的载重均不超过25个单位，五辆车的总费用少于开出四辆车的总费用。由已知条件可知（i=1~10），四辆车中有两辆装有2个客户的货物，两辆车装有3个客户的货物。1） 因为从任意的客户i到客户j的运费均小于100，故增开第五辆车从提货点直接为客户j运送货物能使前四辆车减少的费用小于100，而第五辆车的费用为100+显然比100大，故增开第五辆车来运送一个客户所需货物会使总费用增大；2） 若5辆车每两车个跑两个客户的方案比较复杂，因此用程序模拟发现，题设数据这样能够得到的最优解是275的路程，在加上500的出车费用，最后等于775的价格。找出任意一种装车送货方案的动态规划算法分配第一辆车时的表格如下：i12345678910Ai81369715105129Bi17411242165201133133131）、找到一个i，令Bi=min{Bj}，将i客户货物装车；

2）、找寻k，令，若则将客户k的货物装车，并令i=k并重复步骤2；若k=0，则该车货物装完。分配第二辆车时，将第一辆车已分配了的客户的货物去掉，将剩余的客户的货物按原来客户序列重新排列，按第一辆车分配的方法重复。分配第三、第四辆车用类似方法，最终得出一种装车送货方案：第一辆车所需到达的点为1、3、6、7，货物总量为24；第二辆车所需到达的点为2、5、8，货物总量为25；第三辆车所需到达的点为4、6，货物总量为24；第四辆车所需到达的点为9、10，货物总量为21。简化为表格表述如下：所需到达的点1、3、6、72、5、84、69、10客户货物组合86101375915129货物总量24252421剩余载重1013调整装车送货方案，以得到更优的装车送货方案1）、由上表可知，四辆车的剩余载重均不会超过客户的最小货物需求量，故本例中只能通过车辆之间货物的交换才可能出现更多的装车送货方案。2）、寻找任意两辆车中能够交换的客户的货物并且仍然满足4辆车不超过其载重的条件为表示第m辆车中的第n种货物可以与第i辆车的第j种货物交换。通过前面的模型计算出交换前后辆车路程的距离和，作比较，若交换后会导致路程减小，则保留交换后的状态，完成交换，否则的话复原成交换前。最优解的判断条件7．4所述的调换方案在任意两车间进行，故第1辆车要尝试与2、3、4辆车各物品交换，第2辆车要与3、4两车各物品交换，第3辆车要与第4辆车各物品尝试交换。我们管这样经过一次完整的交换过程叫做一个“完全交换尝试”。假若经过一个“完全交换尝试”后，没有发生一次交换，则说明当前状态已经是最优解。若发生过至少一次交换则需要重复做一次“完全交换尝试”进行判断。程序的Pascal实现程序核心代码（Pascal）//ii<-->jjforii:=1to3doforjj:=ii+1to4dofork:=1tocar[ii,0]doforl:=1tocar[jj,0]dobeginif(car[ii,-1]+zl[car[ii,k]]-zl[car[jj,l]]>=0)and(car[jj,-1]+zl[car[jj,l]]-zl[car[ii,k]]>=0)thenbegincar[ii,-1]:=car[ii,-1]+zl[car[ii,k]]-zl[car[jj,l]];car[jj,-1]:=car[jj,-1]+zl[car[jj,l]]-zl[car[ii,k]];m:=car[ii,k];car[ii,k]:=car[jj,l];car[jj,l]:=m;fillchar(dot,sizeof(dot),0);dot[1]:=1;fori1:=1tocar[ii,0]dodot[i1+1]:=car[ii,i1];car[ii,-2]:=qiongjubuhui(car[ii,0]+1);fillchar(dot,sizeof(dot),0);dot[1]:=1;fori1:=1tocar[jj,0]dodot[i1+1]:=car[jj,i1];car[jj,-2]:=qiongjubuhui(car[jj,0]+1);if(car[ii,-2]+car[jj,-2]<car2[ii,-2]+car2[jj,-2])thenbegincar2:=car;ok:=false;end;end;car:=car2;end;模型验证通过编写了一个组合序列生成器生成所有可能的10选3情况，和10选2情况，通过质量要小于等于25的条件作为筛选，共筛选出78条。进行78选4的方式的组合，并判断是否能走遍所有的点，筛选出116条可行方案，对116条可行方案求值，发现结果与上述算法所得结果一致。（相关数据见附录）。模型评价该模型相比校验用的完全算法模型时间复杂度不高，但取得的值确实最优的，具有较好的推广价值。模型拓展特别注意到原文体中描述出车费用的计量方式是每辆车100元出车费，若深究此话含义，所得结果应该是255+100=355为最优解。因为空车返回不计价格，一辆车反复跑节省了出车费用，固使之最小。小结模型的分析已在各个部分作了说明，这里不再重述，由于比赛时间短暂，做了的很多工作未能详述，再次简要概括，相关数据附在附录中。针对遗传算法当中的插入算法模型，为了校验他的可靠性，专门编写了全排列进入黑箱，对黑箱的数据进行SPSS的统计分析，得到最优解的概率，从而确定了遗传算法索要比对的次数级别。针对各个算法都有一些小的优化和剪枝，比较琐碎再此也不再详述，详细请参考附录中的程序原文。

参考文献[1]徐玖平等，运筹学，科学出版社，2006[2]网友资源，百度百科，/view/298415.htm[3]黄良文主编，统计学原理，北京：中国统计出版社，2000.6[4]杨位钦顾岚著，时间序列分析与动态数据建模（修订本），北京：北京理工大学出版社，1988[5]范金城，梅长林著，数据分析，科学出版社，2002[6]曹利国，吴耀斌，向期中等，信息学奥林匹克奥赛经，2002[7]姜启源谢金星叶俊等编，数学建模，北京：高等教育出版社，2003[8]孙祥等编，MATLAB7.0基础教程，北京：清华大学出版社2005.5[9]刘汝佳等，算法艺术与信息学竞赛，清华大学出版社，2004.1

附录附录一路径的邻接矩阵附录二各客户所需要的货物量8，13，6，9，7，15，10，5，12，9附录三题目的Floyd任意两点之间的矩阵d（i，j）0405540255530555070500304535504555658555300155530502535554045150453050203050251545450351030405555503030350255035553025505010250304060304525203025300103020403040351525450203520102520403035300附录四两点i，j之间最短距离所经过的路径path（i，j）其中path（i，j）=j，表示i，j是直接到达。1544577599123356538942348678891334568889122457788107234767499153856788109534597899410104767891012335353910附录五（i，j）表示从i出发到j停止一共要走几个点1332232323212322334532123222342321223234223213223232223123232323221232332223212323323222122223233321附录六相关程序问题1用Floyd算法的matlab实现程序clear;clc;M=10000;%不能直接到达是将距离赋值给Ma(1,:)=[0,50,M,40,25,M,30,M,50,M];a(2,:)=[50,0,30,M,35,50,M,60,M,M];a(3,:)=[M,30,0,15,M,30,50,25,M,60];a(4,:)=[40,M,15,0,45,30,55,20,40,65];a(5,:)=[25,15,M,45,0,60,10,30,M,55];a(6,:)=[M,50,30,30,60,0,25,55,35,M];a(7,:)=[30,M,50,M,10,25,0,30,45,60];a(8,:)=[M,60,25,20,30,55,30,0,10,M];a(9,:)=[20,M,M,40,M,15,25,45,0,20];a(10,:)=[35,20,10,45,20,M,60,M,30,0];%建立a矩阵path=zeros(length(a));%建立一个与矩阵a同大小的全零矩阵fori=1:10forj=1:10path(i,j)=j;%用path矩阵记录走过的点endendfork=1:10fori=1:10forj=1:10ifa(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=path(i,k);%floyd算法endendendenda,pathi1=input('请输入起点');i2=input('请输入终点');disp(i1);whilei1~=i2i1=path(i1,i2);disp(i1);end;问题1的pascal程序（模型2）programfloyd;constmaxn=15;vari1,i2,i3,ss,i,j,k,l,s,m,n,ci:integer;a,b:array[1..maxn,1..maxn]ofinteger;path:array[1..maxn,1..maxn,0..maxn]ofinteger;plan,zl,c:array[1..maxn]ofinteger;f:text;r,total:integer;beginassign(f,'in.txt');reset(f);//assign(output,'out.txt');rewrite(output);readln(f,n,i1,k);fori:=1tondoread(f,zl[i]);readln(f);fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);fillchar(path,sizeof(path),0);//read//ifi1=1thenbeginfori:=1tondobeginforj:=1tondobeginread(f,a[i,j]);ifa[i,j]=0thenbeginpath[i,j,0]:=1;path[i,j,1]:=i;end;ifa[i,j]<>0thenbeginpath[i,j,0]:=2;path[i,j,1]:=i;path[i,j,2]:=j;end;end;readln(f);end;//end;b:=a;//runfork:=1tondofori:=1tondoforj:=1tondoif(b[i,k]<>-1)and(b[k,j]<>-1)and((b[i,k]+b[k,j]<b[i,j])or(b[i,j]=-1))thenbeginb[i,j]:=b[i,k]+b[k,j];path[i,j,0]:=path[i,k,0]+path[k,j,0]-1;form:=1topath[i,k,0]dopath[i,j,m]:=path[i,k,m];form:=1topath[k,j,0]dopath[i,j,m+path[i,k,0]-1]:=path[k,j,m];end;//printwriteln;writeln('---YuanShi---');fori:=1tondobeginforj:=1tondowrite(a[i,j]:5);writeln;end;writeln;writeln('----SSSP----');fori:=1tondobeginforj:=1tondowrite(b[i,j]:5);writeln;end;writeln;writeln('----PathN----');fori:=1tondobeginforj:=1tondowrite(path[i,j,0]:5);writeln;end;close(f);reset(input);//displaypathwhile(i1<>-1)dobeginreadln(i1,i2);fori:=1topath[i1,i2,0]-1dowrite(path[i1,i2,i],'-->');writeln(path[i1,i2,path[i1,i2,0]]);writeln(b[i1,i2]);end;end.问题二的pascal程序（模型3、4、5）programforyd;constmaxn=15;vari1,i2,i3,ss,i,j,k,l,s,m,n,ci:integer;a,b:array[1..maxn,1..maxn]ofinteger;zl,c,d,e,f,g,plan:array[1..maxn]ofinteger;ff:text;total:integer;over,show,stop:boolean;c1,c2:array[1..maxn]ofbyte;xl:array[0..2*maxn]ofbyte;procedurefindi;begini:=n;while(i>1)and(plan[i]<plan[i-1])dodec(i)end;procedurefindj;beginj:=n;while(plan[j]<=plan[i-1])dodec(j)end;procedurechange;vark,h:integer;begink:=plan[i-1];plan[i-1]:=plan[j];plan[j]:=k;fork:=ito(n+i)div2dobeginh:=plan[k];plan[k]:=plan[n+i-k];plan[n+i-k]:=h;end;end;proceduresol;vari,j,k:integer;begink:=0;fori:=1ton-1dok:=k+b[plan[i],plan[i+1]];k:=k+b[plan[n],1];ifk<sthenbegins:=k;c:=plan;end;{ifk=sthenbeginwriteln;writeln('---QiongJu---');writeln;write('1');fori:=2tondowrite('-->',plan[i]);writeln('-->1');writeln('Total:',k);end;}end;beginassign(input,'in.txt');reset(input);assign(output,'out.txt');rewrite(output);readln(n,i1,k);fori:=1tondoread(zl[i]);readln;fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);fillchar(c,sizeof(c),0);//readifi1=1thenbeginfori:=1tondobeginforj:=1tondoread(a[i,j]);readln;end;end;ifi1=2thenbeginfori:=1tondoforj:=1tondoifi<>jthena[i,j]:=-1elsea[i,j]:=0;i1:=0;whilei1<>-1dobeginreadln(i1,i2,i3);ifi1<>-1thenbegina[i1,i2]:=i3;ifk=1thena[i2,i1]:=i3;end;end;end;b:=a;//runfork:=1tondofori:=1tondoforj:=1tondoif(b[i,k]<>-1)and(b[k,j]<>-1)and((b[i,k]+b[k,j]<b[i,j])or(b[i,j]=-1))thenb[i,j]:=b[i,k]+b[k,j];//printwriteln;writeln('---YuanShi---');fori:=1tondobeginforj:=1tondowrite(a[i,j]:5);writeln;end;writeln;writeln('----SSSP----');fori:=1tondobeginforj:=1tondowrite(b[i,j]:5);writeln;end;//SSSP+Searchc[1]:=1;ci:=1;s:=0;whileci<ndobegink:=32760;fori:=1tondobeginm:=1;forj:=1tocidoifc[j]=ithenm:=0;if(b[c[ci],i]<>0)and(m=1)and(b[c[ci],i]<k)thenbegink:=b[c[ci],i];c[ci+1]:=i;end;end;inc(ci);s:=s+kend;s:=s+b[c[ci],1];writeln;writeln('---JinSiSuanFa---');writeln;write('1');fori:=2tondowrite('-->',c[i]);writeln('-->1');writeln('Total:',s);//xiuzhengYICHuanss:=32760;forl:=1to2000dobegins:=32760;randomize;fori:=1to100dobeginj:=round(random*(n-2))+2;k:=round(random*(n-2))+2;if(j>n)or(j<1)thenj:=n;if(k>n)or(k<1)thenk:=1;i1:=c[k];c[k]:=c[j];c[j]:=i1;end;d[1]:=1;f[1]:=1;f[2]:=1;fori:=ndownto2dobegins:=32760;forj:=2ton-i+2dobegind:=f;m:=0;fork:=n-i+2downtojdobegind[k+1]:=d[k];end;d[j]:=c[i];fork:=1ton-i+2dobeginm:=m+b[d[k],d[k+1]];end;ifm<sthenbegins:=m;e:=d;end;end;f:=e;end;ifs<ssthenbeginss:=s;g:=f;end;end;//s:=s+b[f[n],1];writeln;writeln('---YiChuanJinSiSuanFa---');writeln;write('1');fori:=2tondowrite('-->',g[i]);writeln('-->1');writeln('Total:',ss);//QiongJus:=32760;fori:=1tondoplan[i]:=i;sol;repeatfindi;ifi>1thenbeginfindj;change;ifplan[1]<>1thenbreak;sol;end;untili<=1;writeln;writeln('---QiongJu---');writeln;write('1');fori:=2tondowrite('-->',c[i]);writeln('-->1');writeln('Total:',s);close(input);close(output);end.问题三的pascal程序（模型6）programforyd;constmaxn=15;varcari1,cari2,i1,i2,i3,ss,i,j,k,l,s,m,n,ci:integer;a,b:array[1..maxn,1..maxn]ofinteger;dot,zl,c,d,e,f,g,plan:array[1..maxn]ofinteger;ff:text;total:integer;over,show,stop:boolean;c1,c2,car1,car2:array[1..maxn]ofinteger;xl:array[0..2*maxn]ofbyte;procedurefindi(n:integer);begini:=n;while(i>1)and(plan[i]<plan[i-1])dodec(i)end;procedurefindj(n:integer);beginj:=n;while(plan[j]<=plan[i-1])dodec(j)end;procedurechange(n:integer);vark,h:integer;begink:=plan[i-1];plan[i-1]:=plan[j];plan[j]:=k;fork:=ito(n+i)div2dobeginh:=plan[k];plan[k]:=plan[n+i-k];plan[n+i-k]:=h;end;end;proceduresol(n:integer);vari,j,k:integer;begink:=0;fori:=1ton-1dok:=k+b[dot[plan[i]],dot[plan[i+1]]];k:=k+b[dot[plan[n]],1];ifk<sthenbegins:=k;c:=plan;end;end;procedureqiongju(n:integer);begin//QiongJus:=32760;fori:=1tondoplan[i]:=i;sol(n);repeatfindi(n);ifi>1thenbeginfindj(n);change(n);ifplan[1]<>1thenbreak;sol(n);end;untili<=1;writeln;writeln('---QiongJu---');writeln;write('1');fori:=2tondowrite('-->',dot[c[i]]);writeln('-->1');writeln('Total:',s);end;proceduresolbuhui(n:integer);vari,j,k:integer;begink:=0;fori:=1ton-1dok:=k+b[dot[plan[i]],dot[plan[i+1]]];//k:=k+b[dot[plan[n]],1];ifk<sthenbegins:=k;c:=plan;end;end;procedureqiongjubuhui(n:integer);begin//QiongJus:=32760;fori:=1tondoplan[i]:=i;solbuhui(n);repeatfindi(n);ifi>1thenbeginfindj(n);change(n);ifplan[1]<>1thenbreak;solbuhui(n);end;untili<=1;ss:=s;//writeln;//writeln('---QiongJu---');//writeln;//write('1');//fori:=2tondowrite('-->',dot[c[i]]);//writeln('-->1');//writeln('Total:',s);end;procedureSSSPSearch(n:integer);begin//SSSP+Searchc[1]:=1;ci:=1;s:=0;whileci<ndobegink:=32760;fori:=1tondobeginm:=1;forj:=1tocidoifc[j]=ithenm:=0;if(b[c[ci],i]<>0)and(m=1)and(b[c[ci],i]<k)thenbegink:=b[c[ci],i];c[ci+1]:=i;end;end;inc(ci);s:=s+kend;s:=s+b[c[ci],1];writeln;writeln('---JinSiSuanFa---');writeln;write('1');fori:=2tondowrite('-->',c[i]);writeln('-->1');writeln('Total:',s);end;procedureyichuan(n:integer);//xiuzhengYICHuanbeginss:=32760;fori:=1tondoc[i]:=i;forl:=1to2000dobegins:=32760;randomize;fori:=1to100dobeginj:=round(random*(n-2))+2;k:=round(random*(n-2))+2;if(j>n)or(j<1)thenj:=n;if(k>n)or(k<1)thenk:=1;i1:=c[k];c[k]:=c[j];c[j]:=i1;end;d[1]:=1;f[1]:=1;f[2]:=1;fori:=ndownto2dobegins:=32760;forj:=2ton-i+2dobegind:=f;m:=0;fork:=n-i+2downtojdobegind[k+1]:=d[k];end;d[j]:=c[i];fork:=1ton-i+2dobeginm:=m+b[dot[d[k]],dot[d[k+1]]];end;ifm<sthenbegins:=m;e:=d;end;end;f:=e;end;ifs<ssthenbeginss:=s;g:=f;end;end;//s:=s+b[f[n],1];writeln;writeln('---YiChuanJinSiSuanFa---');writeln;write('1');fori:=2tondowrite('-->',dot[g[i]]);writeln('-->1');writeln('Total:',ss);end;procedureyichuanbuhui(n:integer);//xiuzhengYICHuanbeginss:=32760;fori:=1tondoc[i]:=i;forl:=1to1000dobegins:=32760;randomize;fori:=1to100dobeginj:=round(random*(n-2))+2;k:=round(random*(n-2))+2;if(j>n)or(j<1)thenj:=n;if(k>n)or(k<1)thenk:=1;i1:=c[k];c[k]:=c[j];c[j]:=i1;end;d[1]:=1;f[1]:=1;f[2]:=1;fori:=ndownto2dobegins:=32760;forj:=2ton-i+2dobegind:=f;m:=0;fork:=n-i+2downtojdobegind[k+1]:=d[k];end;d[j]:=c[i];fork:=1ton-i+1dobeginm:=m+b[dot[d[k]],dot[d[k+1]]];end;ifm<sthenbegins:=m;e:=d;end;end;f:=e;end;ifs<ssthenbeginss:=s;g:=f;end;end;//s:=s+b[f[n],1];//writeln;//writeln('---YiChuanBuHuiSuanFa---');//writeln;{write('1');fori:=2tondowrite('-->',dot[g[i]]);//writeln('-->1');writeln;writeln('Total:',ss);}end;functionkeyun:boolean;vari,j,k,w1,w2:integer;beginw1:=0;w2:=0;fori:=1tondobeginif(c1[i]=1)and(c2[i]=0)thenw1:=w1+zl[i];if(c1[i]=0)and(c2[i]=1)thenw2:=w2+zl[i];end;if(w1<=50)and(w2<=50)thenkeyun:=trueelsekeyun:=false;end;proceduremake_xl;vari,j,k:integer;begin//repeati:=n*2;whilexl[i]<>0dodec(i);ifi<1thenover:=true;xl[i]:=1;forj:=i+1ton*2doxl[j]:=0;forj:=1tondoifxl[j]=0thenxl[j+n]:=1;xl[1]:=1;xl[1+n]:=1;{k:=1;forj:=1tondoifxl[j]+xl[n+j]=0thenbegink:=0;break;end;}//if(xl[1]<>1)or(xl[1+n]<>1)thenk:=0;//until{(k=1)or}(over);end;proceduresol3;vari,j,k:integer;min,tmpmin:longint;beginfori:=1to2*ndoxl[ci]:=0;over:=false;xl[1]:=1;xl[1+n]:=1;min:=32760;whilenot(over)dobeginmake_xl;fori:=1tondobeginc1[i]:=xl[i];c2[i]:=xl[i+n];end;ifk