建模 旅行售货员问题.docx

旅行售货员(TSP)，Hamilton 回路的 lingo 程序 方法一 model: sets: city / 1..6/: u;! 定义 6 个城市; link( city, city): dist, ! 距离矩阵; x; !决策变量; endsets n = @size( city); data: !距离矩阵; dist =0 2 100 4 100 2 2 0 8 100 4 100 100 8 0 5 8 7 4 100 5 0 6 100 100 4 8 6 0 4 2 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.00000 Objective bound: 26.00000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 179 Variable Value Reduced Cost N 6.000000 0.000000 U( 1) 5.000000 0.000000 U( 2) 0.000000 0.000000 U( 3) 3.000000 0.000000 U( 4) 5.000000 0.000000 U( 5) 1.000000 0.000000 U( 6) 2.000000 0.000000 注意，这里有两个 u(1)=U(4)=5 说明： 红色部分语句 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-1 u(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-1 u(j)-u(k)+n*x(j,k)=n-1 u(k)-u(i)+n*x(k,i)=n-1 将三个不等式相加，得到矛盾 3n=3(n-1)，所以可不能产生子圈。 整个程序可以改为下面两种情况： 如果把红色部分中过滤条件 |I #gt# 1 去掉，那么可以改为 model: sets: city / 1..6/: u;! 定义 6 个城市; link( city, city): dist, ! 距离矩阵; x; !决策变量; endsets n = @size( city); data: !距离矩阵; dist =0 2 100 4 100 2 2 0 8 100 4 100 100 8 0 5 8 7 4 100 5 0 6 100 100 4 8 6 0 4 2 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): @for( city( J)| J#gt#1 #and# I #ne# J