!旅行售货员问题; model sets city 5/ link( city, city) dist,!距离矩阵; endsets size( city) data:!距离矩阵,它并不需要是对称的; dist=@ grand(1);!随机产生,这里可改为你要解决的问题的数据 enddata !目标函数; min @sum( link: dist * x)i GFOR( city( K) !进入城市K; esum(City(工)|工#ne#K:x(工,K))=1 !离开城市K; Gsum( city( J)I J #ne# K: x( K, J))=li !保证不出现子圈; for(city(工)|工#gt#1 @for( city( j)I j#gt#1 and I #ne# J: u(I)-u(J)+n*x(I,J)<=n-1); !限制u的范围以加速模型的求解,保证所加限制并不排除掉Ts问题的最优解; for(city(工)|工#gt#1:u(工)<=n-2); !定义x为01变量 @for( link: bin( x)) end
!旅行售货员问题; model: sets: city / 1.. 5/: u; link( city, city): dist, ! 距离矩阵; x; endsets n = @size( city); data: !距离矩阵，它并不需要是对称的; dist = @qrand(1); !随机产生，这里可改为你要解决的问题的数据; 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) | I #gt# 1: u(I)<=n-2 ); !定义X为0\1变量; @for( link: @bin( x)); end
例7.4最短路问题 给定M个点p(i=1,2,,M组成集合{p}。 c;表示任一点D到另一点p的距离,并作如下规定:若D;到p没 有弧联结,C1=+,c1=0(=1,2…,M 现指定一个终点p,求从p点出发到的最短路线 用动态规划方法做:点p表示状态,决策集合是除p以外点, 选定一个点D以后,得到c;并转入新状态效益p;,当状态是p时, 过程停止 这是一个不定期多阶段决策过程。 定义f():由点出发至终点p最短路程,由最优化原理得: ()=m(+(),1 1.2.….N-1 (x)=0 函数方程,用 LINGO可以方便的解决
给定N个点pi(i=1,2,…,N)组成集合{pi}。 cij表示任一点pi到另一点pj的距离，并作如下规定：若pi到pj没 有弧联结，cij=+∞，cii =0 (i=1,2,…,N)。 现指定一个终点pN，求从pi点出发到pN的最短路线。 用动态规划方法做：点pi表示状态，决策集合是除pi以外点， 选定一个点pj以后，得到cij并转入新状态效益pj ，当状态是pN时， 过程停止。 这是一个不定期多阶段决策过程。 定义f(i)：由点pi出发至终点pN最短路程，由最优化原理得： ( ) ( ( )) ( ) min , 1, 2, , 1 0 = + = − = ij j f i c f j i N f N 函数方程，用LINGO可以方便的解决。 例7.4 最短路问题