数学建模运输问题.doc

华东交通大学数学建模2012年第一次模拟训练题所属学校：华东交通大学（ECJTU）参赛队员：胡志远、周少华、蔡汉林、段亚光、李斌、邱小秧、周邓副、孙燕青 指导老师：朱旭生（博士）摘要： 本文的运输问题是一个比较复杂的问题，大多数问题都集中在最短路径的求解问题上，问题特点是随机性比较强。根据不同建模类型 针对问题一 ，我们直接采用Dijkstra算法（包括lingo程序和手算验证），将问题转化为线性规划模型求解得出当运送员在给第二个客户卸货完成的时，若要他先给客户10送货，此时尽可能短的行使路线为：，总行程85公里。针对问题二，我们首先利用prim算法求解得到一棵最小生成树：再采用Dijkstra算法求得客户2返回提货点的最短线路为故可得到一条理想的回路是：后来考虑到模型的推广性，将问题看作是哈密顿回路的问题，建立相应的线性规划模型求解，最终找到一条满足条件的较理想的的货车送货的行车路线：。针对问题三，我们首先直接利用问题二得一辆车的最优回路，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，最终可为公司确定合理的一号运输方案:两辆车全程总和为295公里（见正文）；然后建立线性规划模型得出二号运输方案：两辆车全程总和为290公里（见正文）；针对问题四， 一、问题分析对问题（一）的分析就是求指定两点间的最短路径问题，对此我们可以采用dijkstra算法可以很简单的算出答案，由此延伸一下我们可以推广到可找出第二个客户到任何一个客户的的最短路径，为此我们也将找出此类题目的一般lingo算法。对问题（二）的分析,由提货点出发再返回到提货点，而且这条路径必须是相对而言最短的，显然这个问题是在模型中找出一条最短的哈密尔顿回路的问题，建立相应的线性规划模型就能最终找到一条满足条件的较理想的的结果对问题（三）的分析，这个问题主要是要把9个客户（1好客户为提货点）分成两个集合，然后依次构建出两个完整的最短的汉密尔顿回路。对问题（四）的分析关键字：Dijkstra算法, prim算法, 哈密顿回路 二、 模型假设1、任何两个客户之间的路径长度都是固定的，不存在临时出发状况例如绕道，改道的情况。2、不考虑任何现实状况中的实际情况，一切按照题目的数据进行求解。三、符号说明表示从第i个客户到第j个客户的路线距离表示第i个客户到第j个客户的0-1变量(注：其他变量在模型中定义)四、模型的建立与求解问题一、 模型一： 直接求解：为了简化问题我们用dijistra算法直接求解，然后用表格法简化其操作步骤： 12345678910A5030*infi3550infi60infiInfiB504535*508055infi90C5045*50455590D505045*558590F50*50558590G50*558590H55*8590I65*90J85*由上表我们显然可以得到一条最短路径：238910(且最短路径为85)同样从上表格中我们不但可以找出客户2到客户10的最短路径同样可以找出客户到其他任何客户位置的最短路径列表如下：21(最短路径为50)23(最短路径为30)234(最短路径为45)25(最短路径为35)26(最短路径为50)257(最短路径为45) 238(最短路径为552389(最短路径为65)模型二：编写出lingo的算法求解：定义是由点出发至终点的最短路程，由最优化原理可得这是一个函数方程，用LINGO可以很方便的解决。model:data: n=10;enddatasets: points/1.n/: F; !10个客户点; roads(points,points)/ 1,2 2,3 2,5 2,6 2,8 3,4 3,6 3,7 3,8 3,10 4,5 4,6 4,7 4,8 4,9 4,10 5,6 5,7 5,8 5,10 6,7 6,8 6,9 7,8 7,9 7,10 8,9 9,10/: D, P;endsetsdata:D= 50 30 35 50 60 15 30 50 25 60 45 30 55 20 40 65 60 10 30 55 25 55 35 30 45 60 10 20;enddata F(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.000000 P( 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( 9, 10) 1.000000由p(i,j)是否等于1来确定路径，可得路径为2-3,3-8,8-9,9-10.为85模型结果对比：由第一个结果对比第二个模型的算法结果相同，可知这个lingo算法模型是正确的，以后若遇到类似求某点到其他各点的最短路径问题都可选用lingo的算法求解问题二很明显运输公司分别要对10个客户供货，必须访问每个客户，但问题要求我们建立相应模型寻找一条尽可能短的行车路线，首先不考虑送货员把10个客户所需的货送完货后不返回提货点的情形，利用求最小生成树的prim算法结合题中所给的邻接矩阵，很快可以得到以下一棵最小生成树：V1V5V7V6V3V4V8V9V10V2以上路线的总行程为175公里，充分利用问题一所建的模型(1),很快就可以求得（客户2）返回（提货点）的最线路是行程50公里(，我们有理由相信这样构成的回路实际上也是最短回路：V1V5V7V6V3V4V8V9V10V2V1总行程为225公里。这种寻路方法并不比其他方法差而且它的速度也很快，只是它局限于顶点数较少的情形，一旦顶点数扩大实现起来难度就会大大提高，而且它的不易推广，因此我们有必要对此问题深入研究，进而建立起一个数学模型以适应顶点数变化，使它能够具有较好的推广性，应用到现实生活中去来实现以不变应万变的现象。模型的推广变量说明表示从第i个客户到第j个客户的路线距离表示第i个客户到第j个客户的0-1变量 根据对问题的分析，我们首先引入一些0-1整数变量：其题目目标就是使 为最小。这里有两个明显的必须满足的条件：访问客户i后必须要有一个即将访问的确切客户；访问客户j前必须要有一个刚刚访问过的确切客户。用下面的两组约束分别实现上面的两个条件。这里，我们将添加一种在原模型上附加充分的约束条件以避免产生子巡回的方法。把额外变量附加到问题中。可把这些变量看作是连续的（虽然这些变量在最优解中取普通的整数值）。现在附加下面形式的约束条件。 为了证明该约束条件有预期的效果，必须证明：（1）任何含子巡回的路线都不满足该约束条件；（2）全部巡回都满足该约束条件。首先证明（1），用反证法。假设还存在子巡回，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含客户1。把该子巡回记为，则必有把这k个式子相加，有，矛盾！故假设不正确，结论（1）得证。下面证明（2），采用构造法。对于任意的总巡回，可取访问客户i的顺序数，取值范围为。因此，。下面来证明总巡回满足该约束条件。()总巡回上的边（）非总巡回上的边从而结论（2）得证。这样我们把TSP转化成了一个混合整数线性规划问题。显然，当客户个数较大（大于30）时，该混合整数线性规划问题的规模会很大，从而给求解带来很大问题。TSP已被证明是NP难问题，目前还没有发现多项式时间的算法。对于小规模问题，我们求解这个混合整数线性规划问题的方式还是有效的。以下是linggo算法：MODEL: SETS: CUSTOMERS / 1. 10/: U; LINK( CUSTOMERS, CUSTOMERS): DIST,X; ENDSETS DATA: DIST = 0 50 100000 40 25 100000 30 100000 50 100000 50 0 30 100000 35 50 100000 60 10000 100000 100000 30 0 15 100000 30 50 25 100000 60 40 10000 15 0 45 30 55 20 40 65 25 15 100000 45 0 60 10 30 100000 55 100000 50 30 30 60 0 25 55 35 1000000 30 100000 50 100000 10 25 0 30 45 60 100000 60 25 20 30 55 30 0 10 100000 20 100000 100000 40 100000 15 25 45 0 20 35 20 10 45 20 100000 60 100000 30 0;ENDDATA N = SIZE( CUSTOMERS); MIN = SUM( LINK: DIST * X); FOR( CUSTOMERS( K): SUM( CUSTOMERS( I)| I #NE# K: X( I, K) = 1; SUM( CUSTOMERS( J)| J #NE# K: X( K, J) = 1; FOR( CUSTOMERS( J)| J #GT# 1 #AND# J #NE# K: U( J) = U( K) + X ( K, J) - ( N - 2) * ( 1 - X( K, J) + ( N - 3) * X( J, K) ); ); FOR( LINK: BIN( X); FOR( CUSTOMERS( K)| K #GT# 1: U( K) = 1 + ( N - 2) * X( K, 1) );END可得结果：从中可以找出一条较为理想的回路是：可见按此模型求解的结果与采用prim算法求解的结果是一样的。问题三、用两辆容量为50单位的小货车运货，在每个客户所需固定货物量的情况下，要使得行程之和最短，我们假设每个客户的货物都由同一辆货车提供，这样只要找出两条尽可能短的回路（无子圈），并保证每条线路客户总需求量在50个单位以内。这样问题就解决了！事实上这样的两条回路是存在的：由题二得到了一条哈密顿回路可根据货物需求量的大小将其分为前后两部分（随便从中截断），然后都回到V1客户点构成回路。（注：由于提货点在客户1所在的位置，故不必考虑为客户1送货的情况。）变量说明：定义一个有序集合：例如：N=代表由模型(2)求解得出的哈密顿回路的路径全集（集合中的元素是不可调换的，故称它为顺序集合）；1、为集合N中第i个元素终点所对应的下标。（即若i=3，则，）2、为集合N中第i个元素终点所对客户的货物需求量（即若i=3则）其中=的第i个分量的值（value）。接下来我们设计一个简单的思路来寻找较好的路径：Step1：根据以下模型获得一个值k，依k的取值把问题二中的最短回路分两条路径（然后分别补充为两条回路，无子圈）：Step3：利用模型(1)分别求得到的最短路径： 以及到的最短路径：Step4：从而获取两辆货车的路线如下表：车号路线一号车 二号车据上描述可建立模型：依据模型很容易求得：k=5所以根据我们所设计的算法很快找到一组合理的运输路线是：车号行车路线一号车 二号车（因为根据模型(1)很容易可以确定至的最短路径是，至的最短路径是，但在代用模型(1)的时候须注意的是相应的客户位置的变换，可参照问题一的求解决方法。）由此可得两车所行驶的距离之和（单位：公里）：结果优化从以上得到的两条行车路线来看，两车都经过了客户5，根据算法二号车必客户5才能保证行程较短，而根据模型(1)易知路径优于，因此可优化一号车路线为：，经检验优化后的两条行车路线上客户货物需求量总和分别是40与46均不超过货车的容量50，故认为此方案更优，这样我们可以给运输公司提供的一号运输方案是：车号行车路线线路的长度该车负责的客户一号车140公里3,4,6,7二号车155公里2,5,8,9,10两辆车全程总和为295公里。模型结果分析：很明显，以上猜想得到的模型来求解这一问题，存在着很大的缺陷，那就是没有更好说服力，因为我们有理由相信这个模型分成的两个集合（即两个小回路）并不一定是最有效的，虽然结果不是很让人感到很满意，但这个结果也是很有一定客观性，因为我们这个结果是基于问题二中最短路径引申得到的，故结果应该不会很差。因此我们还想通建立另一个模型来弥补这一缺陷。 模型二针对上面的两个集合分配不合理的问题，我们可以建立相应的线性规划模型对以上的运输方案进一步优化,考虑到本问题与问题二有相似之处即要考虑回到提货点的情形,因此我们可以在模型(2)上进行改进, 在保证二号不超载(不超出容量)的前提下,先确定第一辆车的最优路径,首先对模型中将会用的变量作一些简单的定义或说明:1为每个客户的需货量,它是在向量的每j个分量,据上分析知:(不考虑客户1的需求量,因为它在提货点)。2由于这里是分两条路线分别给10个客户送货,就没有必要设计每条路线都能够访问每个客户点,但要保证送货员能回提货点,且均从提货点出发回到提货点，则送货员进入一个客户同时也必须出来。故我们用以下条件来分别保证我们的假设： 到此我们得到了一个模型，它是一个指派问题的整数规划模型。其目标又是一个是在约束条件下取得最小值。其余变量的假设与问题二的假设一致。故可建立模型（3）如下：在约束下，参加附录3的代码，在lingo中求解可得以下结果：K的值满足条件的较短路径（1-1）路径长度（单位：公里）=7不存在符合条件的路径以上可视为确定首先确定的第一辆车的行车方案；则这两条路线所对的第二辆车最优路线的选择，（以长度为95公里的路线为例）只需将模型（3）中的条件：与改为条件即要保证第二辆访问到所有第一辆车未访问过的客户，允许其访问第一辆车访问过的客户，故模型基本上不用改动。同样参照参加附录的代码，可求得上述路线对应的另一条路线为：K的值满足条件的较短路径（2-1）路径长度（单位：公里）=7不存在符合条件的路径此时我们可以为公司提供一种更好的二号运输方案：车号行车路线线路的长度该车负责的客户一号车135公里4，5，8，9，10二号车155公里2，3，6，7两辆车全程总和为290公里。结果分析与评价虽然我们猜想模型很简单，但它是解决本问题的关键，也是我们建模思路的切入点，通过这个模型的建立与求解我们逐渐发现问题的所在，故而引导我们对自己所建的模型一步一步地优化，最终得到一个非常理想的运输方案，当然我们模型也存在不少问题，例如我们没有用一个统一的模型来同时得出两辆车的最优路线，而是要我们自己通过对数据进行一步步计算在分析，这是我们觉得比较郁闷的地方，我们将慢慢地对其不断改进与完善。问题四： 五、模型优缺点 （略）六、参考文献 （略）附件：1、第一题linggo算法model:data: n=10;enddatasets: points/1.n/: F; !10个客户点; roads(points,points)/ 1,2 2,3 2,5 2,6 2,8 3,4 3,6 3,7 3,8 3,10 4,5 4,6 4,7 4,8 4,9 4,10 5,6 5,7 5,8 5,10 6,7 6,8 6,9 7,8 7,9 7,10 8,9 9,10/: D, P;endsetsdata:D= 50 30 35 50 60 15 30 50 25 60 45 30 55 20 40 65 60 10 30 55 25 55 35 30 45 60 10 20;enddata F(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程序代码：MODEL: SETS: CUSTOMERS / 1. 10/: U; LINK( CUSTOMERS, CUSTOMERS): DIST,X; ENDSETS DATA: DIST = 0 50 100000 40 25 100000 30 100000 50 100000 50 0 30 100000 35 50 100000 60 10000 100000 100000 30 0 15 100000 30 50 25 100000 60 40 10000 15 0 45 30 55 20 40 65 25 15 100000 45 0 60 10 30 100000 55 100000 50 30 30 60 0 25 55 35 1000000 30 100000 50 100000 10 25 0 30 45 60 100000 60 25 20 30 55 30 0 10 100000 20 100000 100000 40 100000 15 25 45 0 20 35 20 10 45 20 100000 60 100000 30 0;ENDDATA N = SIZE( CUSTOMERS); MIN = SUM( LINK: DIST * X); FOR( CUSTOMERS( K): SUM( CUSTOMERS( I)| I #NE# K: X( I, K) = 1; SUM( CUSTOMERS( J)| J #NE# K: X( K, J) = 1; FOR( CUSTOMERS( J)| J #GT# 1 #AND# J #NE# K: U( J) = U( K) + X ( K, J) - ( N - 2) * ( 1 - X( K, J) + ( N - 3) * X( J, K) ); ); FOR( LINK: BIN( X); FOR( CUSTOMERS( K)| K #GT# 1: U( K) = 1 + ( N - 2) * X( K, 1) );END第三题lingo程序代码：model:sets: CUSTOMERS/ 1.10/: u,D; link( CUSTOMERS, CUSTOMERS):C, x; endsets min = sum( link: C*x)