例 7.1 求解非线性方程组代码：
model:
x^2+y^2=2;
2*x^2+x+y^2+y=4;
end
结果：
Feasible solution found at iteration,0
Variable Value
X 0.454336
Y 1.339247
§ 7 综合举例
22
22
2
24
xy
x x y y
一条装配线含有一系列的工作站，在最终产品的加工过程中每个工作站执行一种或几种特定的任务。装配线周期是指所有工作站完成分配给它们各自的任务所化费时间中的最大值。平衡装配线的目标是为每个工作站分配加工任务，尽可能使每个工作站执行相同数量的任务，其最终标准是装配线周期最短。不适当的平衡装配线将会产生瓶颈 —— 有较少任务的工作站将被迫等待其前面分配了较多任务的工作站。
问题会因为众多任务间存在优先关系而变得更复杂，任务的分配必须服从这种优先关系。
这个模型的目标是最小化装配线周期。有 2类约束：
① 要保证每件任务只能也必须分配至一个工作站来加工；
② 要保证满足任务间的所有优先关系。
例 有 11件任务（ A— K）分配到 4个工作站（ 1— 4），任务的优先次序如下图
。每件任务所花费的时间如下表。
例 7.2 装配线平衡模型
（ I）
（ H）
（ G） （ J）
（ K）
（ F）
（ B）（ A） （ C）
（ E）（ D）
MODEL:
!装配线平衡模型 ;
SETS:
!任务集合，有一个完成时间属性 T;
TASK/ A B C D E F G H I J K/,T;
!任务之间的优先关系集合（ A 必须完成才能开始 B，等等） ;
PRED( TASK,TASK)/ A,B B,C C,F C,G F,J G,J J,K D,E E,H E,I H,J I,J /;
! 工作站集合 ;
STATION/1..4/;
TXS( TASK,STATION),X;
! X是派生集合 TXS的一个属性。如果 X（ I,K）＝ 1，则表示第 I个任务指派给第 K个工作站完成 ;
ENDSETS
DATA:
!任务 A B C D E F G H I J K的完成时间估计如下 ;
T = 45 11 9 50 15 12 12 12 12 8 9;
ENDDATA
! 当任务超过 15个时，模型的求解将变得很慢 ;
!每一个作业必须指派到一个工作站，即满足约束① ;
@FOR( TASK( I),@SUM( STATION( K),X( I,K)) = 1);
!对于每一个存在优先关系的作业对来说，前者对应的工作站 I必须小于后者对应的工作站 J，即满足约束② ;
@FOR( PRED( I,J),@SUM( STATION( K),K * X( J,K) - K * X( I,K)) >= 0);
!对于每一个工作站来说，其花费时间必须不大于装配线周期 ;
@FOR( STATION( K):
@SUM( TXS( I,K),T( I) * X( I,K)) <= CYCTIME);
!目标函数是最小化转配线周期 ;
MIN = CYCTIME;
!指定 X(I,J) 为 0/1变量 ;
@FOR( TXS,@BIN( X));
END
任务 A B C D E F G H I J K
时间 45 11 9 50 15 12 12 12 12 8 9
有一个推销员，从城市 1出发，要遍访城市 2,3,…,n各一次，最后返回城市 1。已知从城市 i到 j的旅费为 Cij，问他应按怎样的次序访问这些城市，使得总旅费最少？
可以用多种方法把 TSP表示成整数规划模型。这里介绍的一种建立模型的方法，是把该问题的每个解（不一定是最优的）看作是一次
,巡回,。
在下述意义下，引入一些 0-1整数变量：
例 7.3 旅行售货员问题（又称货郎担问题,Traveling Salesman Problem）
1
0ij
i j i j
x
,巡 回 路 线 是 从 到,且
,其 它 情 况其目标只是使 为最小。
,1?
ij ij
ij
Cx
这里有两个明显的必须满足的条件：
访问城市 i后必须要有一个即将访问的确切城市；
访问城市 j前必须要有一个刚刚访问过的确切城市。
用下面的两组约束分别实现上面的两个条件。
1
1
n
ij
j
x
1,2,,in?
1
1
n
ij
i
x
1,2,,jn?
1 2
3
4
5
6
到此得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于 TSP来说并不充分，仅仅是必要条件。
例如：
以上两个条件都满足，但它显然不是 TSP的解，它存在两个子巡回。
这里，将叙述一种在原模型上附加充分的约束条件以避免产生子巡回的方法。把额外变量附加到问题中。可把这些变量看作是连续的（最然这些变量在最优解中取普通的整数值）。现在附加下面形式的约束条件
12i j i ju u n x n i j n，
为证明该约束条件有预期的效果，必须证明：
（ 1）任何含子巡回的路线都不满足该约束条件；
（ 2）全部巡回都满足该约束条件。
首先证明（ 1），用反证法。假设还存在子巡回，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含城市 1。把该子巡回记为
2,3,,?iu i n
1 2 1ki i i i
，则必有 12
23
1
1
1
1
k
ii
ii
ii
u u n n
u u n n
u u n n
这 k个式子相加，有,,矛盾！
=访问城市 i的顺序数，取值范围为 。因此，
。下面来证明总巡回满足该约束条件。
，可取
1nn
故假设不正确，结论（ 1）得证。
下面证明（ 2），采用构造法。对于任意的总巡回
2 -111nii
iu2,3,,?in
2iju u n 2i j n
(ⅰ) 总巡回上的边 12
23
21
11
11
11
nn
ii
ii
ii
u u n n n
u u n n n
u u n n n
（ ⅱ ）非总巡回上的边从而结论（ 2）得证。
这样我们把 TSP转化成了一个混合整数线性规划问题。
1
2 - 1
2 - 1
r
n
ij
ij
u u n n
u u n n
12,3,,, rrj i n i i
1,2,,2rn
2,3,, rj i n i
,1
1
1
m i n
.,1 1,2,,
1 1,2,,
12
0,1,1,2,,
0,2,3,,
ij ij
ij
ij
n
ij
j
n
ij
i
i j ij
ij
i
z C x
s t x j n
x i n
u u n x n i j n
x i j n
u i n
，
显然，当城市个数较大（大于 30）时，该混合整数线性规划问题的规模会很大，从而给求解带来很大问题。 TSP已被证明是 NP难问题，
目前还没有发现多项式时间的算法。对小规模问题，求解这个混合整数线性规划问题的方式还是有效的。
TSP是一个重要的组合优化问题，除了有直观的应用外，许多其它看似无联系的优化问题也可转化为 TSP。例如：
问题 1 现需在一台机器上加工 n个零件（如烧瓷器），这些零件可按任意先后顺序在机器上加工。我们希望加工完成所有零件的总时间尽可能少。由于加工工艺的要求，加工零件 j时机器必须处于相应状态 Sj（如炉温）。设起始未加工任何零件时机器处于状态 S0，
，且当所有零件加工完成后需恢复到 S0状态。已知从状态 Si调整到状态 Sj(i≠j) 需要时间 Cij 。零件 j本身加工时间为 pj。为方便起见
，引入一个虚零件 0，其加工时间为 0，要求状态为 S0，,则 {0,1
,2,…,n}的一个圈置换 π 就表示对所有零件的一个加工顺序，
在此置换下，完成所有加工所需要的总时间为由于 是一个常数，故该零件的加工顺序问题变成 TSP。
0 0 0
n n n
ji i i i i
i i j
C p C p
0?
n
j
j
p
!旅行售货员问题 ;
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 最短路问题 给定 N个点 pi组 (i=1,2,…,N)成集合 {pi}，由集合中任一点 pi到另一点 pj的距离用 cij表示，如果 pi到 pj到 没有弧联结，则规定 cij=+∞，又规定 cii=0 (i=1,2,…,N),指定一个终点 pN，
要求从 pi点出发到 pN的最短路线。这里用动态规划方法来做。用所在的点 pi表示状态，决策集合就是除 pi以外的点，选定一个点 pj以后，得到 cij并转入新状态效益 pj,当状态是 pN时，过程停止。显然这是一个不定期多阶段决策过程。
定义 f(i)是由点 pj出发至终点 pN的最短路程，由最优化原理可得
m in,1,2,,1
0
ij
j
f i c f j i N
fN
函数方程，用 LINGO可以方便的解决。
!最短路问题 ;model:
data:n=10;
enddatasets:
cities/1..n/,F; !10个城市 ;roads(cities,cities)/
1,2 1,32,4 2,5 2,6
3,4 3,5 3,64,7 4,8
5,7 5,8 5,96,8 6,9
7,108,10
9,10/,D,P;
endsetsdata:
D=6 5
3 6 97 5 11
9 18 7 5
4 105
79;
enddataF(n)=0;
@for(cities(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
hkm
m
例 7.5 露天矿生产的车辆安排（ CMCM2003B）
钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。
露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于 25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多能安置一台电铲，电铲的平均装车时间为 5分钟。
卸货地点（以下简称卸点）有卸矿石的矿石漏,2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为 29.5% 1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（ 8小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为 3分钟。
所用卡车载重量为 154吨，平均时速 28。卡车的耗油量很大，每个班次每台车消耗近 1吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。
卡车每次都是满载运输。
每个铲位到每个卸点的道路都是专用的宽 60的双向车道，不会出现堵车现象，
每段道路的里程都是已知的。
一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；出铲位 1 铲位 2 铲位 3 铲位 4 铲位 5 铲位 6 铲位 7 铲位 8 铲位 9 铲位 10
矿石漏 5.26 5.19 4.21 4.00 2.95 2.74 2.46 1.90 0.64 1.27
倒装场 Ⅰ 1.90 0.99 1.90 1.13 1.27 2.25 1.48 2.04 3.09 3.51
岩场 5.89 5.61 5.61 4.56 3.51 3.65 2.46 2.46 1.06 0.57
岩石漏 0.64 1.76 1.27 1.83 2.74 2.60 4.21 3.72 5.05 6.10
倒装场 Ⅱ 4.42 3.86 3.72 3.16 2.25 2.81 0.78 1.62 1.27 0.50
各铲位矿石、岩石数量 (万吨 )和矿石的平均铁含量如下表：
铲位 1 铲位 2 铲位 3 铲位 4 铲位 5 铲位 6 铲位 7 铲位 8 铲位 9 铲位 10
矿石量 0.95 1.05 1.00 1.05 1.10 1.25 1.05 1.30 1.35 1.25
岩石量 1.25 1.10 1.35 1.05 1.15 1.35 1.05 1.15 1.35 1.25
铁含量 30% 28% 29% 32% 31% 33% 32% 31% 33% 31%
各铲位矿石、岩石数量 (万吨 )和矿石的平均铁含量如下表：
model:
title CUMCM-2003B-01;
sets:
cai / 1..10 /:crate,cnum,cy,ck,flag;
xie / 1,,5 /:xsubject,xnum;
link( xie,cai ):distance,lsubject,number,che,b;
endsets
data:
crate=30 28 29 32 31 33 32 31 33 31;
xsubject= 1.2 1.3 1.3 1.9 1.3 ;
distance= 5.26 5.19 4.21 4.00 2.95 2.74 2.46 1.90 0.64
1.27
1.90 0.99 1.90 1.13 1.27 2.25 1.48 2.04 3.09
3.51
5.89 5.61 5.61 4.56 3.51 3.65 2.46 2.46 1.06
0.57
0.64 1.76 1.27 1.83 2.74 2.60 4.21 3.72 5.05
6.10
4.42 3.86 3.72 3.16 2.25 2.81 0.78 1.62 1.27
0.50;
cy = 1.25 1.10 1.35 1.05 1.15 1.35 1.05 1.15 1.35 1.25;
ck = 0.95 1.05 1.00 1.05 1.10 1.25 1.05 1.30 1.35 1.25;
enddata
!目标函数 ;
min=@sum( cai (i):
@sum ( xie (j):
number (j,i)*154*distance (j,i)));
!max =@sum(link(i,j):number(i,j));
!max=xnum (3)+xnum (4)+xnum (1)+xnum (2)+xnum(5);
!min=@sum( cai (i):
! @sum ( xie (j):
! number (j,i)*154*distance (j,i)));
!xnum (1)+xnum (2)+xnum(5)=340;
!xnum (1)+xnum (2)+xnum(5)=341;
!xnum (3)=160;
!xnum (4)=160;
!卡车每一条路线上最多可以运行的次数 ;
@for (link (i,j):
b(i,j)=@floor((8*60-
(@floor((distance(i,j)/28*60*2+3+5)/5)-
1)*5)/(distance(i,j)/28*60*2+3+5)));
!b(i,j)=@floor(8*60/(distance(i,j)/28*60*2+3+5)));
!t(i,j)=@floor((distance(i,j)/28*60*2+3+5)/5);
!b(i,j)=@floor((8*60-
(@floor((distance(i,j)/28*60*2+3+5)/5))*5)/(distance(i,j)/
28*60*2+3+5)));
!每一条路线上的最大总车次的计算 ;
@for( link (i,j):
lsubject(i,j)=(@floor((distance(i,j)/28*60*2+3+5)/5))*b(i,
j));
!计算各个铲位的总产量 ;
@for (cai(j):cnum(j)=@sum(xie(i):number(i,j)));
!计算各个卸点的总产量 ;
@for (xie(i):xnum(i)=@sum(cai(j):number(i,j)));
!道路能力约束 ;
@for (link (i,j):number(i,j)<=lsubject(i,j));
!电铲能力约束 ;
@for (cai (j),cnum(j) <= flag(j)*8*60/5 );
!电铲数量约束 ---- added by Xie Jinxing,2003-09-07;
@sum(cai(j),flag(j) ) <=7;
!卸点能力约束 ;
@for (xie (i):xnum (i)<=8*20);
!铲位产量约束 ;
@for (cai (i),
number(1,i)+number(2,i)+number(5,i)<=ck(i)*10000/154);
@for (cai (i):number(3,i)+number(4,i)<=cy(i)*10000/154);
!产量任务约束 ;
@for (xie (i):xnum (i)>= xsubject (i)*10000/154);
!铁含量约束 ;
@sum(cai (j):number(1,j)*(crate(j)-30.5) )<=0;
@sum(cai (j):number(2,j)*(crate(j)-30.5) )<=0;
@sum(cai (j):number(5,j)*(crate(j)-30.5) )<=0;
@sum(cai (j):number(1,j)*(crate(j)-28.5) )>=0;
@sum(cai (j):number(2,j)*(crate(j)-28.5) )>=0;
@sum(cai (j):number(5,j)*(crate(j)-28.5) )>=0;
!关于车辆的具体分配 ;
@for (link (i,j):che (i,j)=number (i,j)/b(i,j));
!各个路线所需卡车数简单加和 ;
hehe=@sum (link (i,j),che (i,j));
!整数约束 ;
@for (link (i,j),@gin(number (i,j)));
@for (cai (j),@bin(flag (j)));
!车辆能力约束 ;
hehe<=20;
ccnum=@sum(cai (j),cnum(j) );
end
求解最小生成树的方法虽然很多，但是利用 LINGO建立相应的整数规划模型是一种新的尝试。这对于处理非标准的 MST问题非常方便。我们主要参考了文 [7]。
在图论中，称无圈的连通图为树。在一个连通图 G中，称包含图 G全部顶点的树为图 G的生成树。生成树上各边的权之和称为该生成树的权。连通图 G
的权最小的生成树称为图 G的最小生成树。
许多实际问题都可以归结为最小生成树。如,如何修筑一些公路把若干个城镇连接起来；如何架设通讯网络将若干个地区连接起来；如何修筑水渠将水源和若干块待灌溉的土地连接起来等等。为说明问题,以下面的问题作为范例。
范例：假设某电话公司计划在六个村庄架设电话线，各村庄之间的距离如图所示。试求出使电话线总长度最小的架线方案。
为了便于计算机求解，特作如下规定：
（ 1）节点 V1表示树根；
（ 2）两个节点之间没有线路时，
规定两节点之间距离为 M（较大的值）
MST的整数规划模型如下：
例 7.6 最小生成树（ Minimal Spanning Tree,MST）问题
V1
V2
V3
V4
V5
V6
1
1
2
2
2
3
3
3
45
ijc
这是个给 n个人分配 n项工作以获得某个最高总效果的问题。第 i个人完成第 j项工作需要平均时间 cij。要求给每个人分配一项工作，并要求分配完这些工作，以使完成全部任务的总时间为最小。该问题可表示如下：
例 7.7 分配问题（指派问题,Assignment Problem）
11
1
1
m in
.,1 1,2,,
1 1,2,,
0,1
nn
ij ij
ij
n
ij
j
n
ij
j
ij
z c x
s t x j n
x i n
x
显然，此问题可看作是运输问题的特殊情况。可将此问题看作具有 n个源和 n个汇的问题，每个源有 1单位的可获量，而每个汇有 1
单位的需要量。从表面看，这问题要求用整数规划以保证 xij能取 0
或 1。然而，幸运的是，此问题是运输问题的特例，因此即使不限制 xij取 0或 1，最优解也将取 0或 1。如果把婚姻看作分配问题，丹茨证明，整数性质证明一夫一妻会带来最美满幸福的生活！显然，分配问题可以作为线性规划问题来求解，尽管模型可能很大。例如，
给 100人分配 100项工作将使所得的模型具有 10000个变量。这时，
如采用专门算法效果会更好。
时间复杂度为 O(n2)的匈牙利算法便是好选择，这是由 Kuhu
（ 1955）提出的。
model:
!7个工人,7个工作的分配问题 ;
sets:
workers/w1..w7/;
jobs/j1..j7/;
links(workers,jobs),cost,volume;
endsets
!目标函数 ;
min=@sum(links,cost*volume);
!每个工人只能有一份工作 ;
@for(workers(I):
@sum(jobs(J),volume(I,J))=1;
);
!每份工作只能有一个工人 ;
@for(jobs(J):
@sum(workers(I),volume(I,J))=1;
);
data:
cost= 6 2 6 7 4 2 5
4 9 5 3 8 5 8
5 2 1 9 7 4 3
7 6 7 3 9 2 7
2 3 9 5 7 2 6
5 5 2 2 8 11 4
9 2 3 12 4 5 10;
enddata
end
指派问题的一种推广。可以把指派问题看作线性规划问题，故较易求解，而二次分配问题是纯整数规划问题，往往很难求解。
与分配问题一样，二次分配问题也与两个目标集合 S,T有关。 S和 T
含有相同数目的元素，以便达到某一目标。这里两种必须满足的条件：必须把 S的每个元素确切地分配给 T的一个元素； T的每个元素只能接受 S的一个元素。可引入 0-1变量：
用和分配问题相同的约束条件给出以上两个条件：
例 7.8 二次分配问题（ Quadratic Assignment Problem）
1 i S j T
0
,
,ij
x
把 的 一 元 素 分 配 的 一 元 素其 它
1
1
n
ij
j
x
1,2,,in?
1
1
n
ij
i
x
1,2,,jn?
但是本问题的目标比分配问题的更加复杂。我们得到的价格系数 cijkl，
其解释是：在 i（ S的一个元素）分配给 j（ T的一个元素）的同时把 k
（ S的一个元素）分配给 l（ T的一个元素）所应承担的费用。显然，
只有当 xij=1且 xkl=1,即其乘积 xijkl=1时，才承担这种费用。于是本目标变成一个 0-1变量的二次表达式：
最常见是系数 cijkl从其它系数 tik和 djl的乘积推出来的情况,Cijkl=tikdjl
为弄清这个相当复杂的模型，研究下面两个应用有好处。
1 1 1 1
i j i j k l
i j k l
cxx
首先认为 S是一个 n个工厂的集合,T是一个 n个城市的集合。本问题就是要在每一城市中设置一个工厂，并要使工厂之间总的通讯费用最小。通讯费用取决于
（ 1）每对工厂之间通讯的次数；
（ 2）每对工厂所在两个城市之间的距离。
显然，有些工厂很少与别的工厂通讯，虽相距甚远而费用却不大。
另一方面，有些工厂可能需要大量通讯。通讯费取决于距离的远近
。在此应用中，表示 tik工厂 i和工厂 k之间的通讯次数（以适当的单位计量）； djl为城市 j和城市 j之间每单位的通讯费用（显然这与 j和之间的距离有关）。若工厂 i和 k分别设在城市 j和 l，显然这两家间的例 7.9 有 4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段 4名同学的顺序是一样的）。由于 4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示（单位：分钟）：
秘书初试 主管复试 经理面试同学甲 13 15 20
同学乙 10 20 18
同学丙 20 16 10
同学丁 8 10 15
4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨 8:00，问他们最早何时能离开公司?（建立规划模型求解）
本问题是一个排列排序问题。对于阶段数不小于 3的问题没有有效算法，也就是说对于学生数稍多一点儿（比如 20）的情况是无法精确求解的。为此人们找到了很多近似算法。这里我们建立的规划模型可以实现该问题的精确求解，但你会看到它的变量和约束是学生数的平方。因此，当学生数稍多一点儿规划模型的规模经很大
，求解会花费很长时间。记
!三阶段面试模型 ;
model:
sets:
students; !学生集三阶段面试模型 ;
phases; !阶段集 ;
sp(students,phases):t,x;
ss(students,students) | &1 #LT# &2:y;
endsets
data:
students = s1..s4;
phases = p1..p3;
t=
13 15 20
10 20 18
20 16 10
8 10 15;
enddata
ns=@size(students); !学生数 ;
np=@size(phases); !阶段数 ;
!单个学生面试时间先后次序的约束 ;
@for(sp(I,J) | J #LT# np:x(I,J)+t(I,J)<=x(I,J+1));
!学生间的面试先后次序保持不变的约束 ;
@for(ss(I,K):
@for(phases(J):
x(I,J)+t(I,J)-x(K,J)<=200*y(I,K);
x(K,J)+t(K,J)-x(I,J)<=200*(1-y(I,K));
)
);
!目标函数 ;
min=TMAX;
@for(students(I):x(I,3)+t(I,3)<=TMAX);
!把 Y定义 0-1变量 ;
@for(ss,@bin(y));
end
model:
x^2+y^2=2;
2*x^2+x+y^2+y=4;
end
结果：
Feasible solution found at iteration,0
Variable Value
X 0.454336
Y 1.339247
§ 7 综合举例
22
22
2
24
xy
x x y y
一条装配线含有一系列的工作站，在最终产品的加工过程中每个工作站执行一种或几种特定的任务。装配线周期是指所有工作站完成分配给它们各自的任务所化费时间中的最大值。平衡装配线的目标是为每个工作站分配加工任务，尽可能使每个工作站执行相同数量的任务，其最终标准是装配线周期最短。不适当的平衡装配线将会产生瓶颈 —— 有较少任务的工作站将被迫等待其前面分配了较多任务的工作站。
问题会因为众多任务间存在优先关系而变得更复杂，任务的分配必须服从这种优先关系。
这个模型的目标是最小化装配线周期。有 2类约束：
① 要保证每件任务只能也必须分配至一个工作站来加工；
② 要保证满足任务间的所有优先关系。
例 有 11件任务（ A— K）分配到 4个工作站（ 1— 4），任务的优先次序如下图
。每件任务所花费的时间如下表。
例 7.2 装配线平衡模型
（ I）
（ H）
（ G） （ J）
（ K）
（ F）
（ B）（ A） （ C）
（ E）（ D）
MODEL:
!装配线平衡模型 ;
SETS:
!任务集合，有一个完成时间属性 T;
TASK/ A B C D E F G H I J K/,T;
!任务之间的优先关系集合（ A 必须完成才能开始 B，等等） ;
PRED( TASK,TASK)/ A,B B,C C,F C,G F,J G,J J,K D,E E,H E,I H,J I,J /;
! 工作站集合 ;
STATION/1..4/;
TXS( TASK,STATION),X;
! X是派生集合 TXS的一个属性。如果 X（ I,K）＝ 1，则表示第 I个任务指派给第 K个工作站完成 ;
ENDSETS
DATA:
!任务 A B C D E F G H I J K的完成时间估计如下 ;
T = 45 11 9 50 15 12 12 12 12 8 9;
ENDDATA
! 当任务超过 15个时，模型的求解将变得很慢 ;
!每一个作业必须指派到一个工作站，即满足约束① ;
@FOR( TASK( I),@SUM( STATION( K),X( I,K)) = 1);
!对于每一个存在优先关系的作业对来说，前者对应的工作站 I必须小于后者对应的工作站 J，即满足约束② ;
@FOR( PRED( I,J),@SUM( STATION( K),K * X( J,K) - K * X( I,K)) >= 0);
!对于每一个工作站来说，其花费时间必须不大于装配线周期 ;
@FOR( STATION( K):
@SUM( TXS( I,K),T( I) * X( I,K)) <= CYCTIME);
!目标函数是最小化转配线周期 ;
MIN = CYCTIME;
!指定 X(I,J) 为 0/1变量 ;
@FOR( TXS,@BIN( X));
END
任务 A B C D E F G H I J K
时间 45 11 9 50 15 12 12 12 12 8 9
有一个推销员，从城市 1出发，要遍访城市 2,3,…,n各一次，最后返回城市 1。已知从城市 i到 j的旅费为 Cij，问他应按怎样的次序访问这些城市，使得总旅费最少？
可以用多种方法把 TSP表示成整数规划模型。这里介绍的一种建立模型的方法，是把该问题的每个解（不一定是最优的）看作是一次
,巡回,。
在下述意义下，引入一些 0-1整数变量：
例 7.3 旅行售货员问题（又称货郎担问题,Traveling Salesman Problem）
1
0ij
i j i j
x
,巡 回 路 线 是 从 到,且
,其 它 情 况其目标只是使 为最小。
,1?
ij ij
ij
Cx
这里有两个明显的必须满足的条件：
访问城市 i后必须要有一个即将访问的确切城市；
访问城市 j前必须要有一个刚刚访问过的确切城市。
用下面的两组约束分别实现上面的两个条件。
1
1
n
ij
j
x
1,2,,in?
1
1
n
ij
i
x
1,2,,jn?
1 2
3
4
5
6
到此得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于 TSP来说并不充分，仅仅是必要条件。
例如：
以上两个条件都满足，但它显然不是 TSP的解，它存在两个子巡回。
这里，将叙述一种在原模型上附加充分的约束条件以避免产生子巡回的方法。把额外变量附加到问题中。可把这些变量看作是连续的（最然这些变量在最优解中取普通的整数值）。现在附加下面形式的约束条件
12i j i ju u n x n i j n，
为证明该约束条件有预期的效果，必须证明：
（ 1）任何含子巡回的路线都不满足该约束条件；
（ 2）全部巡回都满足该约束条件。
首先证明（ 1），用反证法。假设还存在子巡回，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含城市 1。把该子巡回记为
2,3,,?iu i n
1 2 1ki i i i
，则必有 12
23
1
1
1
1
k
ii
ii
ii
u u n n
u u n n
u u n n
这 k个式子相加，有,,矛盾！
=访问城市 i的顺序数，取值范围为 。因此，
。下面来证明总巡回满足该约束条件。
，可取
1nn
故假设不正确，结论（ 1）得证。
下面证明（ 2），采用构造法。对于任意的总巡回
2 -111nii
iu2,3,,?in
2iju u n 2i j n
(ⅰ) 总巡回上的边 12
23
21
11
11
11
nn
ii
ii
ii
u u n n n
u u n n n
u u n n n
（ ⅱ ）非总巡回上的边从而结论（ 2）得证。
这样我们把 TSP转化成了一个混合整数线性规划问题。
1
2 - 1
2 - 1
r
n
ij
ij
u u n n
u u n n
12,3,,, rrj i n i i
1,2,,2rn
2,3,, rj i n i
,1
1
1
m i n
.,1 1,2,,
1 1,2,,
12
0,1,1,2,,
0,2,3,,
ij ij
ij
ij
n
ij
j
n
ij
i
i j ij
ij
i
z C x
s t x j n
x i n
u u n x n i j n
x i j n
u i n
，
显然，当城市个数较大（大于 30）时，该混合整数线性规划问题的规模会很大，从而给求解带来很大问题。 TSP已被证明是 NP难问题，
目前还没有发现多项式时间的算法。对小规模问题，求解这个混合整数线性规划问题的方式还是有效的。
TSP是一个重要的组合优化问题，除了有直观的应用外，许多其它看似无联系的优化问题也可转化为 TSP。例如：
问题 1 现需在一台机器上加工 n个零件（如烧瓷器），这些零件可按任意先后顺序在机器上加工。我们希望加工完成所有零件的总时间尽可能少。由于加工工艺的要求，加工零件 j时机器必须处于相应状态 Sj（如炉温）。设起始未加工任何零件时机器处于状态 S0，
，且当所有零件加工完成后需恢复到 S0状态。已知从状态 Si调整到状态 Sj(i≠j) 需要时间 Cij 。零件 j本身加工时间为 pj。为方便起见
，引入一个虚零件 0，其加工时间为 0，要求状态为 S0，,则 {0,1
,2,…,n}的一个圈置换 π 就表示对所有零件的一个加工顺序，
在此置换下，完成所有加工所需要的总时间为由于 是一个常数，故该零件的加工顺序问题变成 TSP。
0 0 0
n n n
ji i i i i
i i j
C p C p
0?
n
j
j
p
!旅行售货员问题 ;
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 最短路问题 给定 N个点 pi组 (i=1,2,…,N)成集合 {pi}，由集合中任一点 pi到另一点 pj的距离用 cij表示，如果 pi到 pj到 没有弧联结，则规定 cij=+∞，又规定 cii=0 (i=1,2,…,N),指定一个终点 pN，
要求从 pi点出发到 pN的最短路线。这里用动态规划方法来做。用所在的点 pi表示状态，决策集合就是除 pi以外的点，选定一个点 pj以后，得到 cij并转入新状态效益 pj,当状态是 pN时，过程停止。显然这是一个不定期多阶段决策过程。
定义 f(i)是由点 pj出发至终点 pN的最短路程，由最优化原理可得
m in,1,2,,1
0
ij
j
f i c f j i N
fN
函数方程，用 LINGO可以方便的解决。
!最短路问题 ;model:
data:n=10;
enddatasets:
cities/1..n/,F; !10个城市 ;roads(cities,cities)/
1,2 1,32,4 2,5 2,6
3,4 3,5 3,64,7 4,8
5,7 5,8 5,96,8 6,9
7,108,10
9,10/,D,P;
endsetsdata:
D=6 5
3 6 97 5 11
9 18 7 5
4 105
79;
enddataF(n)=0;
@for(cities(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
hkm
m
例 7.5 露天矿生产的车辆安排（ CMCM2003B）
钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。
露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于 25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多能安置一台电铲，电铲的平均装车时间为 5分钟。
卸货地点（以下简称卸点）有卸矿石的矿石漏,2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为 29.5% 1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（ 8小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为 3分钟。
所用卡车载重量为 154吨，平均时速 28。卡车的耗油量很大，每个班次每台车消耗近 1吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。
卡车每次都是满载运输。
每个铲位到每个卸点的道路都是专用的宽 60的双向车道，不会出现堵车现象，
每段道路的里程都是已知的。
一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；出铲位 1 铲位 2 铲位 3 铲位 4 铲位 5 铲位 6 铲位 7 铲位 8 铲位 9 铲位 10
矿石漏 5.26 5.19 4.21 4.00 2.95 2.74 2.46 1.90 0.64 1.27
倒装场 Ⅰ 1.90 0.99 1.90 1.13 1.27 2.25 1.48 2.04 3.09 3.51
岩场 5.89 5.61 5.61 4.56 3.51 3.65 2.46 2.46 1.06 0.57
岩石漏 0.64 1.76 1.27 1.83 2.74 2.60 4.21 3.72 5.05 6.10
倒装场 Ⅱ 4.42 3.86 3.72 3.16 2.25 2.81 0.78 1.62 1.27 0.50
各铲位矿石、岩石数量 (万吨 )和矿石的平均铁含量如下表：
铲位 1 铲位 2 铲位 3 铲位 4 铲位 5 铲位 6 铲位 7 铲位 8 铲位 9 铲位 10
矿石量 0.95 1.05 1.00 1.05 1.10 1.25 1.05 1.30 1.35 1.25
岩石量 1.25 1.10 1.35 1.05 1.15 1.35 1.05 1.15 1.35 1.25
铁含量 30% 28% 29% 32% 31% 33% 32% 31% 33% 31%
各铲位矿石、岩石数量 (万吨 )和矿石的平均铁含量如下表：
model:
title CUMCM-2003B-01;
sets:
cai / 1..10 /:crate,cnum,cy,ck,flag;
xie / 1,,5 /:xsubject,xnum;
link( xie,cai ):distance,lsubject,number,che,b;
endsets
data:
crate=30 28 29 32 31 33 32 31 33 31;
xsubject= 1.2 1.3 1.3 1.9 1.3 ;
distance= 5.26 5.19 4.21 4.00 2.95 2.74 2.46 1.90 0.64
1.27
1.90 0.99 1.90 1.13 1.27 2.25 1.48 2.04 3.09
3.51
5.89 5.61 5.61 4.56 3.51 3.65 2.46 2.46 1.06
0.57
0.64 1.76 1.27 1.83 2.74 2.60 4.21 3.72 5.05
6.10
4.42 3.86 3.72 3.16 2.25 2.81 0.78 1.62 1.27
0.50;
cy = 1.25 1.10 1.35 1.05 1.15 1.35 1.05 1.15 1.35 1.25;
ck = 0.95 1.05 1.00 1.05 1.10 1.25 1.05 1.30 1.35 1.25;
enddata
!目标函数 ;
min=@sum( cai (i):
@sum ( xie (j):
number (j,i)*154*distance (j,i)));
!max =@sum(link(i,j):number(i,j));
!max=xnum (3)+xnum (4)+xnum (1)+xnum (2)+xnum(5);
!min=@sum( cai (i):
! @sum ( xie (j):
! number (j,i)*154*distance (j,i)));
!xnum (1)+xnum (2)+xnum(5)=340;
!xnum (1)+xnum (2)+xnum(5)=341;
!xnum (3)=160;
!xnum (4)=160;
!卡车每一条路线上最多可以运行的次数 ;
@for (link (i,j):
b(i,j)=@floor((8*60-
(@floor((distance(i,j)/28*60*2+3+5)/5)-
1)*5)/(distance(i,j)/28*60*2+3+5)));
!b(i,j)=@floor(8*60/(distance(i,j)/28*60*2+3+5)));
!t(i,j)=@floor((distance(i,j)/28*60*2+3+5)/5);
!b(i,j)=@floor((8*60-
(@floor((distance(i,j)/28*60*2+3+5)/5))*5)/(distance(i,j)/
28*60*2+3+5)));
!每一条路线上的最大总车次的计算 ;
@for( link (i,j):
lsubject(i,j)=(@floor((distance(i,j)/28*60*2+3+5)/5))*b(i,
j));
!计算各个铲位的总产量 ;
@for (cai(j):cnum(j)=@sum(xie(i):number(i,j)));
!计算各个卸点的总产量 ;
@for (xie(i):xnum(i)=@sum(cai(j):number(i,j)));
!道路能力约束 ;
@for (link (i,j):number(i,j)<=lsubject(i,j));
!电铲能力约束 ;
@for (cai (j),cnum(j) <= flag(j)*8*60/5 );
!电铲数量约束 ---- added by Xie Jinxing,2003-09-07;
@sum(cai(j),flag(j) ) <=7;
!卸点能力约束 ;
@for (xie (i):xnum (i)<=8*20);
!铲位产量约束 ;
@for (cai (i),
number(1,i)+number(2,i)+number(5,i)<=ck(i)*10000/154);
@for (cai (i):number(3,i)+number(4,i)<=cy(i)*10000/154);
!产量任务约束 ;
@for (xie (i):xnum (i)>= xsubject (i)*10000/154);
!铁含量约束 ;
@sum(cai (j):number(1,j)*(crate(j)-30.5) )<=0;
@sum(cai (j):number(2,j)*(crate(j)-30.5) )<=0;
@sum(cai (j):number(5,j)*(crate(j)-30.5) )<=0;
@sum(cai (j):number(1,j)*(crate(j)-28.5) )>=0;
@sum(cai (j):number(2,j)*(crate(j)-28.5) )>=0;
@sum(cai (j):number(5,j)*(crate(j)-28.5) )>=0;
!关于车辆的具体分配 ;
@for (link (i,j):che (i,j)=number (i,j)/b(i,j));
!各个路线所需卡车数简单加和 ;
hehe=@sum (link (i,j),che (i,j));
!整数约束 ;
@for (link (i,j),@gin(number (i,j)));
@for (cai (j),@bin(flag (j)));
!车辆能力约束 ;
hehe<=20;
ccnum=@sum(cai (j),cnum(j) );
end
求解最小生成树的方法虽然很多，但是利用 LINGO建立相应的整数规划模型是一种新的尝试。这对于处理非标准的 MST问题非常方便。我们主要参考了文 [7]。
在图论中，称无圈的连通图为树。在一个连通图 G中，称包含图 G全部顶点的树为图 G的生成树。生成树上各边的权之和称为该生成树的权。连通图 G
的权最小的生成树称为图 G的最小生成树。
许多实际问题都可以归结为最小生成树。如,如何修筑一些公路把若干个城镇连接起来；如何架设通讯网络将若干个地区连接起来；如何修筑水渠将水源和若干块待灌溉的土地连接起来等等。为说明问题,以下面的问题作为范例。
范例：假设某电话公司计划在六个村庄架设电话线，各村庄之间的距离如图所示。试求出使电话线总长度最小的架线方案。
为了便于计算机求解，特作如下规定：
（ 1）节点 V1表示树根；
（ 2）两个节点之间没有线路时，
规定两节点之间距离为 M（较大的值）
MST的整数规划模型如下：
例 7.6 最小生成树（ Minimal Spanning Tree,MST）问题
V1
V2
V3
V4
V5
V6
1
1
2
2
2
3
3
3
45
ijc
这是个给 n个人分配 n项工作以获得某个最高总效果的问题。第 i个人完成第 j项工作需要平均时间 cij。要求给每个人分配一项工作，并要求分配完这些工作，以使完成全部任务的总时间为最小。该问题可表示如下：
例 7.7 分配问题（指派问题,Assignment Problem）
11
1
1
m in
.,1 1,2,,
1 1,2,,
0,1
nn
ij ij
ij
n
ij
j
n
ij
j
ij
z c x
s t x j n
x i n
x
显然，此问题可看作是运输问题的特殊情况。可将此问题看作具有 n个源和 n个汇的问题，每个源有 1单位的可获量，而每个汇有 1
单位的需要量。从表面看，这问题要求用整数规划以保证 xij能取 0
或 1。然而，幸运的是，此问题是运输问题的特例，因此即使不限制 xij取 0或 1，最优解也将取 0或 1。如果把婚姻看作分配问题，丹茨证明，整数性质证明一夫一妻会带来最美满幸福的生活！显然，分配问题可以作为线性规划问题来求解，尽管模型可能很大。例如，
给 100人分配 100项工作将使所得的模型具有 10000个变量。这时，
如采用专门算法效果会更好。
时间复杂度为 O(n2)的匈牙利算法便是好选择，这是由 Kuhu
（ 1955）提出的。
model:
!7个工人,7个工作的分配问题 ;
sets:
workers/w1..w7/;
jobs/j1..j7/;
links(workers,jobs),cost,volume;
endsets
!目标函数 ;
min=@sum(links,cost*volume);
!每个工人只能有一份工作 ;
@for(workers(I):
@sum(jobs(J),volume(I,J))=1;
);
!每份工作只能有一个工人 ;
@for(jobs(J):
@sum(workers(I),volume(I,J))=1;
);
data:
cost= 6 2 6 7 4 2 5
4 9 5 3 8 5 8
5 2 1 9 7 4 3
7 6 7 3 9 2 7
2 3 9 5 7 2 6
5 5 2 2 8 11 4
9 2 3 12 4 5 10;
enddata
end
指派问题的一种推广。可以把指派问题看作线性规划问题，故较易求解，而二次分配问题是纯整数规划问题，往往很难求解。
与分配问题一样，二次分配问题也与两个目标集合 S,T有关。 S和 T
含有相同数目的元素，以便达到某一目标。这里两种必须满足的条件：必须把 S的每个元素确切地分配给 T的一个元素； T的每个元素只能接受 S的一个元素。可引入 0-1变量：
用和分配问题相同的约束条件给出以上两个条件：
例 7.8 二次分配问题（ Quadratic Assignment Problem）
1 i S j T
0
,
,ij
x
把 的 一 元 素 分 配 的 一 元 素其 它
1
1
n
ij
j
x
1,2,,in?
1
1
n
ij
i
x
1,2,,jn?
但是本问题的目标比分配问题的更加复杂。我们得到的价格系数 cijkl，
其解释是：在 i（ S的一个元素）分配给 j（ T的一个元素）的同时把 k
（ S的一个元素）分配给 l（ T的一个元素）所应承担的费用。显然，
只有当 xij=1且 xkl=1,即其乘积 xijkl=1时，才承担这种费用。于是本目标变成一个 0-1变量的二次表达式：
最常见是系数 cijkl从其它系数 tik和 djl的乘积推出来的情况,Cijkl=tikdjl
为弄清这个相当复杂的模型，研究下面两个应用有好处。
1 1 1 1
i j i j k l
i j k l
cxx
首先认为 S是一个 n个工厂的集合,T是一个 n个城市的集合。本问题就是要在每一城市中设置一个工厂，并要使工厂之间总的通讯费用最小。通讯费用取决于
（ 1）每对工厂之间通讯的次数；
（ 2）每对工厂所在两个城市之间的距离。
显然，有些工厂很少与别的工厂通讯，虽相距甚远而费用却不大。
另一方面，有些工厂可能需要大量通讯。通讯费取决于距离的远近
。在此应用中，表示 tik工厂 i和工厂 k之间的通讯次数（以适当的单位计量）； djl为城市 j和城市 j之间每单位的通讯费用（显然这与 j和之间的距离有关）。若工厂 i和 k分别设在城市 j和 l，显然这两家间的例 7.9 有 4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段 4名同学的顺序是一样的）。由于 4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示（单位：分钟）：
秘书初试 主管复试 经理面试同学甲 13 15 20
同学乙 10 20 18
同学丙 20 16 10
同学丁 8 10 15
4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨 8:00，问他们最早何时能离开公司?（建立规划模型求解）
本问题是一个排列排序问题。对于阶段数不小于 3的问题没有有效算法，也就是说对于学生数稍多一点儿（比如 20）的情况是无法精确求解的。为此人们找到了很多近似算法。这里我们建立的规划模型可以实现该问题的精确求解，但你会看到它的变量和约束是学生数的平方。因此，当学生数稍多一点儿规划模型的规模经很大
，求解会花费很长时间。记
!三阶段面试模型 ;
model:
sets:
students; !学生集三阶段面试模型 ;
phases; !阶段集 ;
sp(students,phases):t,x;
ss(students,students) | &1 #LT# &2:y;
endsets
data:
students = s1..s4;
phases = p1..p3;
t=
13 15 20
10 20 18
20 16 10
8 10 15;
enddata
ns=@size(students); !学生数 ;
np=@size(phases); !阶段数 ;
!单个学生面试时间先后次序的约束 ;
@for(sp(I,J) | J #LT# np:x(I,J)+t(I,J)<=x(I,J+1));
!学生间的面试先后次序保持不变的约束 ;
@for(ss(I,K):
@for(phases(J):
x(I,J)+t(I,J)-x(K,J)<=200*y(I,K);
x(K,J)+t(K,J)-x(I,J)<=200*(1-y(I,K));
)
);
!目标函数 ;
min=TMAX;
@for(students(I):x(I,3)+t(I,3)<=TMAX);
!把 Y定义 0-1变量 ;
@for(ss,@bin(y));
end
