旅行商问题数学建模
- 格式:doc
- 大小:112.00 KB
- 文档页数:11
数学建模遗传算法例题数学建模中,遗传算法是一种基于进化思想的优化算法,可以应用于复杂的优化问题中。
本文将介绍一些遗传算法的例题,帮助读者更好地理解遗传算法的应用。
例题一:背包问题有一个体积为V的背包和n个物品,第i个物品的体积为vi,价值为wi。
求这个背包最多能装多少价值的物品。
遗传算法的解决步骤:1. 初始化种群:随机生成一定数量的个体作为初始种群。
2. 适应度函数:将每个个体代入适应度函数,计算其适应度值。
3. 选择:根据每个个体的适应度值,选择一定数量的个体进入下一代。
4. 交叉:对被选中的个体进行交叉操作,生成新的个体。
5. 变异:对新的个体进行变异操作,引入新的基因。
6. 重复以上步骤,直到符合终止条件。
在背包问题中,适应度函数可以定义为:背包中物品的总价值。
交叉操作可以选择单点交叉或多点交叉,变异操作可以选择随机变异或非随机变异。
例题二:旅行商问题有n个城市,旅行商需要依次经过这些城市,每个城市之间的距离已知。
求旅行商经过所有城市的最短路径。
遗传算法的解决步骤:1. 初始化种群:随机生成一定数量的个体作为初始种群,每个个体代表一种旅行路线。
2. 适应度函数:将每个个体代入适应度函数,计算其适应度值。
3. 选择:根据每个个体的适应度值,选择一定数量的个体进入下一代。
4. 交叉:对被选中的个体进行交叉操作,生成新的个体。
5. 变异:对新的个体进行变异操作,引入新的基因。
6. 重复以上步骤,直到符合终止条件。
在旅行商问题中,适应度函数可以定义为:旅行商经过所有城市的总距离。
交叉操作可以选择顺序交叉或部分映射交叉,变异操作可以选择交换或反转基因序列。
总结:遗传算法是一种强大的优化算法,可以应用于多种复杂的优化问题中。
在数学建模中,遗传算法的应用也越来越广泛。
本文介绍了背包问题和旅行商问题的遗传算法解决步骤,希望对读者有所帮助。
旅行售货员(TSP),Hamilton回路的lingo程序方法一model:sets:city / 1..6/: u;! 定义6个城市;link( city, city):dist, ! 距离矩阵;x; !决策变量;endsetsn = @size( city);data: !距离矩阵;dist =0 2 100 4 100 22 0 8 100 4 100100 8 0 5 8 74 1005 06 100100 4 8 6 0 42 100 7 100 4 0 ;!这里可改为你要解决的问题的数据;enddata!目标函数;min = @sum( link: dist * x);@FOR( city( K):!进入城市K;@sum( city( I)| I #ne# K: x( I, K)) = 1;!离开城市K;@sum( city( J)| J #ne# K: x( K, J)) = 1;);!保证不出现子圈;@for(city(I)|I #gt# 1:@for( city( J)| J#gt#1 #and# I #ne# J:u(I)-u(J)+n*x(I,J)<=n-1););!限制u的范围以加速模型的求解,保证所加限制并不排除掉TSP问题的最优解;@for(city(I) : u(I)<=n-1 );@for( link: @bin( x));!定义X为0\1变量;end部分结果有:Global optimal solution found.Objective value: 26.00000Objective bound: 26.00000Infeasibilities: 0.000000Extended solver steps: 0Total solver iterations: 179V ariable V alue Reduced CostN 6.000000 0.000000U( 1) 5.000000 0.000000U( 2) 0.000000 0.000000U( 3) 3.000000 0.000000U( 4) 5.000000 0.000000U( 5) 1.000000 0.000000U( 6) 2.000000 0.000000注意,这里有两个u(1)=U(4)=5说明:(1)红色部分语句1)保证不会有某一边来回的情况假如有某(i,j)来回,则x(i,j)=x(j,i)=1,对这两个x(i,j)=x(j,i)=1分别用一次上述for语句,得到:u(i)-u(j)+n*x(i,j)<=n-1u(j)-u(i)+n*x(j,i)<=n-1将这两个不等式两边相加,则得到矛盾2n<=2(n-1)2)保证不出现子圈假如有某个子圈i->j->k->i产生,那么一定同时会有一个不包含起点1的子圈产生,所以不妨设子圈i->j->k->i不包含起点1,则有x(i,j)=x(j,k)=x(k,i)=1,但x(j,i)=x(k,j)=x(i,k)=0,对上述3个x(i,j)=x(j,k)=x(k,i)=1分别用三次上面的for语句得到:u(i)-u(j)+n*x(i,j)<=n-1u(j)-u(k)+n*x(j,k)<=n-1u(k)-u(i)+n*x(k,i)<=n-1将三个不等式相加,得到矛盾3n<=3(n-1),所以可不能产生子圈。
资料范本本资料为word版本,可以直接编辑和打印,感谢您的下载旅行商问题数学建模地点:__________________时间:__________________说明:本资料适用于约定双方经过谈判,协商而共同承认,共同遵守的责任与义务,仅供参考,文档可直接下载或修改,不需要的部分可直接删除,使用时请详细阅读内容黄石理工学院数学建模大型作业2011—2012 学年第1学期目录一.摘要二.旅行问题问题描述符号说明模型设计建模求解模型分析三.建模过程及心得体会四.参考文件一.摘要本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。
问题一,是一个依赖与每个城市去一次且仅去一次的路线确定问题,问题二类似于问题一。
问题三是一个依赖于可背重量限制的背包问题。
关键词:HAMILTON回路 LINGO 最优旅行路线 0-1模型二.旅行问题问题描述某人要在假期内从城市A出发,乘火车或飞机到城市B,C,D,E,F旅游购物。
他计划走遍这些城市各一次且仅一次,最后返回城市A。
已知城市间的路费数据见附表1,请你设计一条旅行路线使得他的总路费最少。
如果临行他因故只能去4个城市,该怎样修订旅行路线?在城市间旅游时他计划购买照相机,衣服,书籍,摄像机,渔具,白酒,食品,而受航空行李重量的限制以及个人体力所限,所买物品的总重量不能超过15kg,各种物品的价格见附表2.请你为他决策买哪些物品,使所买物品价值最大。
附表1:附表2模型设计首先给出一个定义:设v1,v2,......,vn是图G中的n个顶点,若有一条从某一顶点v1出发,经过各节点一次且仅一次,最后返回出发点v1的回路,则称此回路为HAMILTON回路。
问题1.分析:这个优化问题的目标是使旅行的总费用最少,要做的决策是如何设定旅行路线,决策受的约束条件:每个城市都必须去,但仅能去一次。
按题目所给,将决定变量,目标函数和约束条件用数学符号及式子表示出来,就可得一下模型。
走遍全中国方案的研究摘要本文通过对走遍中国各省会城市、直辖市和港澳台的最优路径选择问题进行分析,发现这是一个十分典型的旅行商问题(Traveling Salseman Problem ),即寻找一条遍历n 个城市(在本文中为34个城市)的最短路径。
我们搜索了这34个城市的经纬度和部分列车、航班时刻表等各方面信息,综合省钱、省时、方便等因素,进一步深入并细化,从而得到判断各订票方案的准则。
针对问题一,我们利用欧几里得平面知识,由公式0002901800290A B x R A y R ππ+⎧=⋅⎪⎪⎨-⎪=⎪⎩将该34个城市的经纬度转化为平面直角坐标,从而将其简化成二维平面问题。
目前,解旅行商问题(tsp 问题)的方法有许多种,本文采用了较为先进的遗传算法。
遗传算法是目前解决组合优化问题最有效的工具之一,本文介绍了遗传算法的基本原理,讨论了遗传算法中的有关遗传算子设计等方面的技术。
由于该算法在搜索空间中同时考虑了许多点,这样就减少了收敛于局部极小的可能,也增加了处理的并行性。
同时,我们利用MATLAB 软件编辑了相关程序,计算出了遍历该34个城市的最短路径,其路径长度为14661km 。
对于问题二,在只考虑旅行路线最经济的前提下,结合第一问得出的最优路径,我们收集了这34个城市的列车和航班时刻表等信息,从而找出最经济的订票方案,并得其花费为11426元。
针对问题三,在综合考虑省时、省钱、方便等诸多因素的前提下制定订票方案的评价准则,我们运用了层次分析法对其进行研究。
根据对旅行过程中省时,省钱及方便的偏重程度,我们相应地给出了判断矩阵111571513731⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦A ,然后对其进行一致性检验,发现其不一致程度在容许范围内。
因此我们利用其最大特征根max λ对应的特征向量w 作为比较因素的权向量,并得到以下评价表达式:12120.0740.2830.643*(0.8330.167)C x x x x =+++。
3 旅行商问题3.1 旅行商问题概述3.1.1 旅行商问题的定义和数学模型① 定义旅行商问题(Traveling Salesman Problem ,简记TSP)是组合数学中一个古老而又困难的问题,它易于描述但至今尚未彻底解决,现己归入所谓的NP 完全问题类,经典提法为:有一货物推销员要去若干个城市推销货物,从城市1出发,经其余各城市一次,然后回到城市1,问选择怎样的行走路线,才能使总行程最短(各城市间距离为己知)。
该问题在图论的意义下就是所谓的最小Hamilton 圈问题,由于在许多领域中都有着广泛的应用,因而寻找其实际而有效的算法就显得颇为重要了。
遗憾的是,计算复杂性理论给予我们的结论却是,这种可能性尚属未知。
若设城市数目为n 时,那么组合路径数则为(n-1)!。
很显然,当城市数目不多时要找到最短距离的路线并不难,但随着城市数目的不断增大,组合路线数将呈指数级数规律急剧增长,以至达到无法计算的地步,这就是所谓的“组合爆炸问题”。
假设现在城市的数目增为20个,组合路径数则为(20-1)! ,如此庞大的组合数目,若计算机以每秒检索1000万条路线的速度计算,也需要花上386年的时间。
尽管现在计算机的计算速度大大提高,而且已有一些指数级的算法可精确地求解旅行商问题,但随着它们在大规模问题上的组合爆炸,人们退而求其次,转向寻找近似算法或启发式算法,经过几十年的努力,取得了一定的进展。
② 数学模型设(,)G V E =为赋权图,{1,2,}V n ="为顶点集,E 为边集,各顶点间距离为ij c ,已知(0,,,)ij ij c c i j V >=+∞∈,并设则旅行商问题的数学模型可写成如下的线性规划形式:ij ij i jMinZ c x ≠=∑1,(,)0,ij i j x ⎧=⎨⎩边在最优路线上其它,1,1,.1,{0,1},ij j i ij i jij i j S ij x i V x j V s t x K K V x i j V ≠≠∈⎧=∈⎪⎪=∈⎪⎨⎪≤−⊂⎪⎪∈∈⎩∑∑∑这里,K 为V 的所有非空子集,K 为集合K 中所含图G 的顶点个数。
黄石理工学院数学建模大型作业2011—2012 学年第1学期目录一.摘要二.旅行问题1.问题描述2.符号说明3.模型设计4.建模求解5.模型分析6.三.建模过程及心得体会四.参考文件一.摘要本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。
问题一,是一个依赖与每个城市去一次且仅去一次的路线确定问题,问题二类似于问题一。
问题三是一个依赖于可背重量限制的背包问题。
关键词:HAMILTON回路LINGO 最优旅行路线0-1模型二.旅行问题问题描述某人要在假期内从城市A出发,乘火车或飞机到城市B,C,D,E,F 旅游购物。
他计划走遍这些城市各一次且仅一次,最后返回城市A。
已知城市间的路费数据见附表1,请你设计一条旅行路线使得他的总路费最少。
如果临行他因故只能去4个城市,该怎样修订旅行路线?在城市间旅游时他计划购买照相机,衣服,书籍,摄像机,渔具,白酒,食品,而受航空行李重量的限制以及个人体力所限,所买物品的总重量不能超过15kg,各种物品的价格见附表2.请你为他决策买哪些物品,使所买物品价值最大。
模型设计首先给出一个定义:设v1,v2,......,vn 是图G 中的n 个顶点,若有一条从某一顶点v1出发,经过各节点一次且仅一次,最后返回出发点v1的回路,则称此回路为HAMILTON 回路。
问题1.分析:这个优化问题的目标是使旅行的总费用最少,要做的决策是如何设定旅行路线,决策受的约束条件:每个城市都必须去,但仅能去一次。
按题目所给,将决定变量,目标函数和约束条件用数学符号及式子表示出来,就可得一下模型。
模型建立:对于6个城市的旅行问题设A,B,C,D,E,F 六个城市分别对应v1,v2,v3,v4,v5,v6。
假设ij d 表示从城市i 到城市j 的费用。
定义0-1整数型变量ij x =1表示从城市i 旅行到城市j ,否则ij x =0。
则旅行问题的数学模型可表示为一个整数规划问题。
min z=661ij iji jdx =∑∑ (i ≠j)s.t.61iji x=∑=1 (i ≠j ;j=1,2, (6)61ijj x=∑=1 (i ≠j ;i=1,2, (6)1i j ij u u nx n -+≤- (i ≠j;i=2,3,……,6;j=2,3,……6)其中辅助变量i u (i=2,3,……,6)可以是连续变化的,虽然这些变量在最优解中取普通的整数值(从而在约束条件中,可以限定这些变量为整数)。
事实上,在最优解中,i u =访问城市的顺序数。
模型求解运用LINGO ,输入程序:MODEL :!Traveling Sales Problem for the cities of six city; SETS :CITY / 1..6/: U; ! U( I) = sequence no. of city;LINK( CITY, CITY): COST, ! The cost matrix;X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not be symmetric;COST= 0 120 250 330 210 150120 0 98 350 225 300250 98 0 520 430 280330 350 520 0 270 185210 225 430 270 0 420150 300 280 185 420 0 ;ENDDATAN= @SIZE( CITY);MIN= @SUM( LINK: COST * X);@FOR( CITY( K): !It must be entered;@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;! It must be departed;@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems;@FOR( CITY( 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)); !Make the X's 0/1;! For the first and last stop we know...;@FOR( CITY( K)| K #GT# 1:U( K) <= N - 1 - (N - 2) * X( 1, K);U( K) >= 1 + ( N - 2) * X( K, 1));END得到结果:总费用为1163路线:A-B-C-F-D-E-A问题2.临时因故只能去4个城市,那么应该怎样安排旅行路线。
分析:在B,C,D,E,F五个城市中选4个城市,显然有5种可能,按照问题一中的模型,将费用矩阵稍作修改,运用LINGO分别解除5种可能的费用,进行比较,即得结果。
(1)选取B,D,E,F,计算旅行费用:MODEL:!Traveling Sales Problem for the cities of six city;SETS:CITY / 1..5/: U; ! U( I) = sequence no. of city;LINK( CITY, CITY): COST, ! The cost matrix;X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not be symmetric;COST= 0 120 330 210 150120 0 350 225 300330 350 0 270 185210 225 270 0 420150 300 185 420 0 ;ENDDATAN= @SIZE( CITY);MIN= @SUM( LINK: COST * X);@FOR( CITY( K): !It must be entered;@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;! It must be departed;@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems;@FOR( CITY( 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)); !Make the X's 0/1;! For the first and last stop we know...;@FOR( CITY( K)| K #GT# 1:U( K) <= N - 1 - (N - 2) * X( 1, K);U( K) >= 1 + ( N - 2) * X( K, 1));END得到结果:总费用:950路线:A-B-E-D-F-A(2)选取B,C,E,F,计算旅行费用:MODEL:!Traveling Sales Problem for the cities of six city; SETS:CITY / 1..5/: U; ! U( I) = sequence no. of city;LINK( CITY, CITY): COST, ! The cost matrix;X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not be symmetric;COST= 0 120 250 210 150120 0 98 225 300250 98 0 430 280210 225 430 0 420150 300 280 420 0 ;ENDDATAN= @SIZE( CITY);MIN= @SUM( LINK: COST * X);@FOR( CITY( K): !It must be entered;@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;! It must be departed;@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems;@FOR( CITY( 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)); !Make the X's 0/1;! For the first and last stop we know...;@FOR( CITY( K)| K #GT# 1:U( K) <= N - 1 - (N - 2) * X( 1, K);U( K) >= 1 + ( N - 2) * X( K, 1));END得到结果:总费用:963路线:A-E-B-C-F-A(3)选取B,C,D,F,计算旅行费用:MODEL:!Traveling Sales Problem for the cities of six city; SETS:CITY / 1..5/: U; ! U( I) = sequence no. of city;LINK( CITY, CITY): COST, ! The cost matrix;X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not be symmetric;COST= 0 120 250 330 150120 0 98 350 300250 98 0 520 280330 350 520 0 185150 300 280 185 0 ;ENDDATAN= @SIZE( CITY);MIN= @SUM( LINK: COST * X);@FOR( CITY( K): !It must be entered;@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;! It must be departed;@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems;@FOR( CITY( 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)); !Make the X's 0/1;! For the first and last stop we know...;@FOR( CITY( K)| K #GT# 1:U( K) <= N - 1 - (N - 2) * X( 1, K);U( K) >= 1 + ( N - 2) * X( K, 1));END得到结果:总费用:1013路线:A-B-C-F-D-A(4)选取路线:B,C,D,E,计算旅行费用:MODEL:!Traveling Sales Problem for the cities of six city; SETS:CITY / 1..5/: U; ! U( I) = sequence no. of city;LINK( CITY, CITY): COST, ! The cost matrix;X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not be symmetric;COST= 0 120 250 330 210120 0 98 350 225250 98 0 520 430330 350 520 0 270210 225 430 270 0 ;ENDDATAN= @SIZE( CITY);MIN= @SUM( LINK: COST * X);@FOR( CITY( K): !It must be entered;@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;! It must be departed;@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems;@FOR( CITY( 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)); !Make the X's 0/1;! For the first and last stop we know...;@FOR( CITY( K)| K #GT# 1:U( K) <= N - 1 - (N - 2) * X( 1, K);U( K) >= 1 + ( N - 2) * X( K, 1));END得到结果:总费用:1173路线:A-C-B-E-D-A(5)选取C,D,E,F,计算旅行费用:MODEL:!Traveling Sales Problem for the cities of six city;SETS:CITY / 1..5/: U; ! U( I) = sequence no. of city;LINK( CITY, CITY): COST, ! The cost matrix;X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not be symmetric;COST= 0 250 330 210 150250 0 520 430 280330 520 0 270 185210 430 270 0 420150 280 185 420 0 ;ENDDATAN= @SIZE( CITY);MIN= @SUM( LINK: COST * X);@FOR( CITY( K): !It must be entered;@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;! It must be departed;@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems;@FOR( CITY( 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)); !Make the X's 0/1;! For the first and last stop we know...;@FOR( CITY( K)| K #GT# 1:U( K) <= N - 1 - (N - 2) * X( 1, K);U( K) >= 1 + ( N - 2) * X( K, 1));END得到结果:总费用:1195路线:A-C-F-D-E-A因此,总结以上(1),(2),(3),(4),(5)五种情况可得:应该选用路线:A-B-E-D-F-A。