发布时间 : 星期四 文章lingo8.0完美教程更新完毕开始阅读
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
3 面试问题
有4 名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘 书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个 阶段4 名同学的顺序是一样的）。由于4 名同学的专业背景不同，所以每人在三个阶段的面
17
试时间也不同，如下表所示（单位：分钟）：
这4 名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8:00，问他们最 早何时能离开公司?（建立规划模型求解）
本问题是一个排列排序问题。对于阶段数不小于3 的问题没有有效算法，也就是说对于 学生数稍多一点儿（比如20）的情况是无法精确求解的。为此人们找到了很多近似算法。 这里我们建立的规划模型可以实现该问题的精确求解，但你会看到它的变量和约束是学生数 的平方。因此，当学生数稍多一点儿规划模型的规模经很大，求解会花费很长时间。
记ij t 为第i 名同学参加第j 阶段面试需要的时间（即表格中的数据），令ij x 表示第i 名同 学参加第j阶段面试的开始时刻（不妨将8：00 面试开始为0时刻），i ?1,2,3,4; j?1,2,3 T 为完成全部面试所花费的最少时间。 优化目标为
min3 3 {max{ }} i i
i
T ??x ??t
可以改写为：minT s.t. 13 13 T ??x ??t
23 23 33 33 43 43
T ??x ??t T ??x ??t
T ??x ??t 约束条件：
（1）时间先后次序约束（每人只有参加完前一个阶段的面试才能进入下一个阶段）；
, 1
, 1,2,3,4; 1,2 ij ij i j x t x i j ??????????
（2）每个阶段同一时间只能面试一名同学，用0-1 变量ik y 表示第k 名同学是否排 第i 名同学的前面（1 表示“是”，0 表示“否”），则 , , 1, 2,3,4; 1, 2,3; ij ij kj ik x ??t ???x ??Ty i k ??j ??i ??k (1 ), , 1,2,3,4; 1,2,3; kj kj ij ik x ??t ???x ??T ???y i k ??j ??i ??k 相应的LINGO 程序如下：
model: sets:
person/1..4/;！四名同学的集合； stage/1..3/; ！面试阶段的结合； pxs(person,stage):t,x;
！t为面试所需要的时间，x为面试开始的时间 pxp(person,person)|&1 #lt# &2:y; ！&1表示对应于第1个父集合的元素的索引值，&2表示对应于第2个父集合的元素的索引值； ！y(i,k)=1表示k排在i前; endsets data:
t=13 15 20 10 20 18
秘书初试主管复试经理面试 同学甲 13 15 20 同学乙 10 20 18 同学丙 20 16 10 同学丁 8 10 15
18
20 16 10 8 10 15; enddata min=maxt;
!maxt是面试的最后结束时间；
maxt>=@max(pxs(i,j)|j #eq# 3:x(i,j)+t(i,j)); @for(pxs(i,j)|j #lt# 3:x(i,j)+t(i,j) @for(pxp(i,k):x(i,j)+t(i,j)-x(k,j) ！同一时间只能面试一名同学； @for(pxp:@bin(y)); ！y为0-1变量； end 4 最短路问题 如图，用点表示城市，现有A,B1,B2 ,C1,C2 ,C3 ,D共7 个城市，点与点之间的连线表示 城市间有道路相连。连线旁的数字表示道路的长度。现计划从城市A 到城市D 铺设一条天然 气管道，请设计出最短的管道铺设方案。 这是一个有向图的最短路问题，当然也可利用Dijsktra 算法求解，关于算法过程实现 的MATLAB 代码，可查看参考书：《数学建模和数学实验》中的相关章节。在本问题中，因为 城市的数目并不多，故用LINGO 求解。 不失一般性，假设图中有n 个顶点，现需要求从顶点1 到顶点n 的最短路，设决策变量 为ij x ，当1 ij x ??，说明弧(i, j)位于顶点1到顶点n的路上；否则0 ij x ??，其数学规划表达式 为： min ( , ) , ij ij i j E w x E ??? ??是边集， s.t. 1 1 ( , ) ( , ) 1 1 1 0 1, n n ij ji j j i j E i j E i x x i n i n ???? ?????? ????? ?????????????????????0,1ij x ?? 相应的LINGO 代码： model: sets: ！定义七个城市的集合； cities/A,B1,B2,C1,C2,C3,D/; 19 ！定义边集，是稀疏集的显式列举方式给出的； roads(cities,cities)/A,B1 A,B2 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3 C1,D C2,D C3,D/:w,x; endsets data: ！给出每一条边的权值； w=2 4 3 3 1 2 3 1 1 3 4; enddata ！城市的数目，便于修改 n=@size(cities); ！目标函数 min=@sum(roads:w*x); ！约束条件，注意，第三个约束条件实际上可不要； @for(cities(i)|i #ne# 1 #and# i #ne# n: @sum(roads(i,j):x(i,j))=@sum(roads(j,i):x(j,i))); @sum(roads(i,j)|i #eq# 1:x(i,j))=1; End 5 最小生成树问题 我国西部的某地区共有一个城市（标记为1）和9 个乡镇（标记为2-10）组成，该地 区不久将用上天然气，其中城市1 含有井源，现要设计一个供气系统，使得从城市1 到每个 乡镇（2-10）都有一条管道相连，并且铺设管道的量尽可能的少，相关图示和数据如下： 表一：某地区城镇之间的距离单位：km 2 3 4 5 6 7 8 9 10 1 8 5 9 12 14 12 16 17 22 2 9 15 17 8 11 18 14 22 3 7 9 11 7 12 12 17 4 3 17 10 7 15 18 5 8 10 6 15 15 6 9 14 8 16 7 8 6 11 8 11 11 9 10 图一：某地区的地理位置 1 21 4 3 5 6 7 8 9