华东交通大学数学建模2012年第一次模拟训练题所属学校：华东交通大学（ECJTU ） 参赛队员：胡志远、周少华、蔡汉林、段亚光、李斌、邱小秧、周邓副、孙燕青指导老师：朱旭生（博士）摘要：本文的运输问题是一个比较复杂的问题，大多数问题都集中在最短路径的求解问题上，问题特点是随机性比较强。

根据不同建模类型 针对问题一 ，我们直接采用Dijkstra 算法（包括lingo 程序和手算验证），将问题转化为线性规划模型求解得出当运送员在给第二个客户卸货完成的时，若要他先给客户10送货，此时尽可能短的行使路线为：109832V V V V V →→→→，总行程85公里。

针对问题二，我们首先利用prim 算法求解得到一棵最小生成树：121098436751V V V V V V V V V V V →→→→→→→→→→再采用Dijkstra 算法求得客户2返回提货点的最短线路为12V V →故可得到一条理想的回路是：121098436751V V V V V V V V V V V →→→→→→→→→→ 后来考虑到模型的推广性，将问题看作是哈密顿回路的问题，建立相应的线性规划模型求解，最终找到一条满足条件的较理想的的货车送货的行车路线：121098436751V V V V V V V V V V V →→→→→→→→→→。

针对问题三，我们首先直接利用问题二得一辆车的最优回路，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，最终可为公司确定合理的一号运输方案:两辆车全程总和为295公里（见正文）；然后建立线性规划模型得出二号运输方案：两辆车全程总和为290公里（见正文）； 针对问题四，一、问题分析对问题（一）的分析就是求指定两点间的最短路径问题，对此我们可以采用dijkstra算法可以很简单的算出答案，由此延伸一下我们可以推广到可找出第二个客户到任何一个客户的的最短路径，为此我们也将找出此类题目的一般lingo算法。

对问题（二）的分析,由提货点出发再返回到提货点，而且这条路径必须是相对而言最短的，显然这个问题是在模型中找出一条最短的哈密尔顿回路的问题，建立相应的线性规划模型就能最终找到一条满足条件的较理想的的结果对问题（三）的分析，这个问题主要是要把9个客户（1好客户为提货点）分成两个集合，然后依次构建出两个完整的最短的汉密尔顿回路。

对问题（四）的分析关键字：Dijkstra算法, prim算法, 哈密顿回路二、模型假设1、任何两个客户之间的路径长度都是固定的，不存在临时出发状况例如绕道，改道的情况。

2、不考虑任何现实状况中的实际情况，一切按照题目的数据进行求解。

三、符号说明c表示从第i个客户到第j个客户的路线距离ij表示第i个客户到第j个客户的0-1变量(注：其他变量在模型中定义)四、模型的建立与求解问题一、模型一：直接求解：为了简化问题我们用dijistra算法直接求解，然后用表格法简化其操作步骤：1 2 3 4 5 6 7 8 9 102→3→8→9→10(且最短路径为85)同样从上表格中我们不但可以找出客户2到客户10的最短路径同样可以找出客户到其他任何客户位置的最短路径列表如下：2→1(最短路径为50) 2→3(最短路径为30) 2→3→4(最短路径为45) 2→5(最短路径为35) 2→6(最短路径为50) 2→5→7(最短路径为45) 2→3→8(最短路径为552→3→8→9(最短路径为65)模型二：编写出lingo 的算法求解：定义)(i f 是由i p 点出发至终点N p 的最短路程，由最优化原理可得⎪⎩⎪⎨⎧=-=+=0)(1,,2,1)},({min )(N f N i j f c i f ij j这是一个函数方程，用LINGO 可以很方便的解决。

model: data: n=10; enddata sets:points/1..n/: F; !10个客户点; roads(points,points)/ 1,22,3 2,5 2,6 2,83,4 3,6 3,7 3,8 3,104,5 4,6 4,7 4,8 4,9 4,105,6 5,7 5,8 5,106,7 6,8 6,97,8 7,9 7,108,99,10/: D, P;endsetsdata:D=5030 35 50 6015 30 50 25 6045 30 55 20 40 6560 10 30 5525 55 3530 45 601020;enddataF(n)=0;@for(points(i) | i #lt# n:F(i)=@min(roads(i,j): D(i,j)+F(j)););!显然，如果P(i,j)=1,则点i到点n的最短路径的第一步是i --> j，否则就不是。

由此，我们就可方便的确定出最短路径;@for(roads(i,j):P(i,j)=@if(F(i) #eq# D(i,j)+F(j),1,0));End摘入Lingo的部分显示结果：P( 1, 2) 1.000000 P( 2, 3) 1.000000 P( 2, 5) 0.000000 P( 2, 6) 0.000000 P( 2, 8) 0.000000 P( 3, 4) 0.000000 P( 3, 6) 0.000000 P( 3, 7) 0.000000 P( 3, 8) 1.000000 P( 3, 10) 0.000000 P( 4, 5) 0.000000P( 4, 6) 0.000000 P( 4, 7) 0.000000 P( 4, 8) 1.000000 P( 4, 9) 0.000000 P( 4, 10) 0.000000 P( 5, 6) 0.000000 P( 5, 7) 0.000000 P( 5, 8) 0.000000 P( 5, 10) 1.000000 P( 6, 7) 0.000000 P( 6, 8) 0.000000 P( 6, 9) 1.000000 P( 7, 8) 1.000000 P( 7, 9) 0.000000 P( 7, 10) 1.000000 P( 8, 9) 1.000000由p(i,j)是否等于1来确定路径，可得路径为2->3,3->8,8->9,9->10.为85模型结果对比：由第一个结果对比第二个模型的算法结果相同，可知这个lingo 算法模型是正确的，以后若遇到类似求某点到其他各点的最短路径问题都可选用lingo 的算法求解问题二很明显运输公司分别要对10个客户供货，必须访问每个客户，但问题要求我们建立相应模型寻找一条尽可能短的行车路线，首先不考虑送货员把10个客户所需的货送完货后不返回提货点的情形，利用求最小生成树的prim 算法结合题中所给的邻接矩阵，很快可以得到以下一棵最小生成树：V1→V5→V7→V6→V3→V4→V8→V9→V10→V2以上路线的总行程为175公里，充分利用问题一所建的模型(1),很快就可以求得2V （客户2）返回1V （提货点）的最线路是12V V 行程50公里(，我们有理由相信这样构成的回路实际上也是最短回路：V1→V5→V7→V6→V3→V4→V8→V9→V10→V2→V1总行程为225公里。

这种寻路方法并不比其他方法差而且它的速度也很快，只是它局限于顶点数较少的情形，一旦顶点数扩大实现起来难度就会大大提高，而且它的不易推广，因此我们有必要对此问题深入研究，进而建立起一个数学模型以适应顶点数变化，使它能够具有较好的推广性，应用到现实生活中去来实现以不变应万变的现象。

模型的推广变量说明ij c 表示从第i 个客户到第j 个客户的路线距离表示第i 个客户到第j 个客户的0-1变量根据对问题的分析，我们首先引入一些0-1整数变量：ij x ⎩⎨⎧≠=其它情况，且到巡回路线是从，0,1j i j i其题目目标就是使 ∑=nj i ijijx c1,为最小。

这里有两个明显的必须满足的条件：访问客户i 后必须要有一个即将访问的确切客户；访问客户j 前必须要有一个刚刚访问过的确切客户。

用下面的两组约束分别实现上面的两个条件。

ni xnj ij,,2,1,11==∑=nj xni ij,,2,1,11==∑=这里，我们将添加一种在原模型上附加充分的约束条件以避免产生子巡回的方法。

把额外变量),,3,2(n i u i =附加到问题中。

可把这些变量看作是连续的（虽然这些变量在最优解中取普通的整数值）。

现在附加下面形式的约束条件nj i n x n u u ij j i ≤≠≤-≤+-2,1。

为了证明该约束条件有预期的效果，必须证明：（1）任何含子巡回的路线都不满足该约束条件；（2）全部巡回都满足该约束条件。

首先证明（1），用反证法。

假设还存在子巡回，也就是说至少有两个子巡回。

那么至少存在一个子巡回中不含客户1。

把该子巡回记为121i i i i k ，则必有111132121-≤+--≤+--≤+-n n u u n n u u n n u u i i i i i i k把这k 个式子相加，有1-≤n n ，矛盾！故假设不正确，结论（1）得证。

下面证明（2），采用构造法。

对于任意的总巡回1111-n i i ，可取=i u 访问客户i 的顺序数，取值范围为}2,,1,0{-n 。

因此，nj i n u u j i ≤≠≤-≤-2,2。

下面来证明总巡回满足该约束条件。

(ⅰ)总巡回上的边⎪⎪⎩⎪⎪⎨⎧-≤-=+--≤-=+--≤-=+---111111123221n n n u u n n n u u n n n u u n n i i i i i i（ⅱ）非总巡回上的边⎪⎩⎪⎨⎧-∈-≤-≤--∈-=-≤-≤--+}{},,3,2{,12},{},,3,2{,2,,2,1,1211r j i r r j i i n j n n u u i i n j n r n n u u n r 从而结论（2）得证。

这样我们把TSP 转化成了一个混合整数线性规划问题。

⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎨⎧=≥==≤≠≤-≤+-=====∑∑∑==≠=n i u n j i x n j i n x n u u n i x n j x t s x c z i ij ij j i n j ij ni ij nj i j i ijij ,,3,2,0,,2,1,,1,02,1,,2,1,1,,2,1,1..min 111,显然，当客户个数较大（大于30）时，该混合整数线性规划问题的规模会很大，从而给求解带来很大问题。

TSP 已被证明是NP 难问题，目前还没有发现多项式时间的算法。