二次分配问题
例7.8 二次分配问题（Quadratic Assignment Problem）
这个问题是指派问题的一种推广。可以把指派问题看作线性规划问题，故较易求解，而二次分配问题是纯整数规划问题，往往很难求解。
与分配问题一样，二次分配问题也与两个目标集合S 、T 有关。S 和T 含有相同数目的元素，以便达到某一目标。这里两种必须满足的条件：必须把S 的每个元素确切地分配给T
的一个元素；T 的每个元素只能接受S 的一个元素。可引入0-1变量：
⎧1, x ij =⎨
⎩0,
把（i S 的一个元素）分配给其它
（j T 的一个元素）
。
n
用和分配问题相同的约束条件给出以上两个条件：
∑
j =1n
x ij =1, x ij =1,
i =1, 2, , n
∑
i =1
j =1, 2, , n
，
c
但是本问题的目标比分配问题的更加复杂。我们得到的价格系数ijkl ，其解释是：在i （S
的一个元素）分配给j （T 的一个元素）的同时把k （S 的一个元素）分配给l （T 的一个元素）所应承担的费用。显然，只有当
x ij =1
且
x kl =1
，即其乘积
x ij x kl =1
时，才承担这种
费用。于是本目标变成一个0-1变量的二次表达式： n n n n
∑∑∑∑c
i =1
j =1k =1l =1
ijkl
x ij x kl
。
c ijkl =t ik d
jl
最常见的是系数
c ijkl
从其它系数
t ik
和
d
jl
的乘积推出来的情况：。为了弄清这个
相当复杂的模型，研究下面两个应用是有好处的。
首先认为S 是一个n 个工厂的集合，T 是一个n 个城市的集合。本问题就是要在每一城市中设置一个工厂，并要使工厂之间总的通讯费用最小。通讯费用取决于（1）每对工厂之间通讯的次数；（2）每对工厂所在两个城市之间的距离。
显然，有些工厂很少与别的工厂通讯，虽相距甚远而费用却不大。另一方面，有些工厂可能需要大量通讯。通讯费取决于距离的远近。在这个应用中，ik 表示工厂i 和工厂k
d
之间的通讯次数（以适当的单位计量）；jl 为城市j 和城市l 之间每单位的通讯费用（显然这与j 和l 之间的距离有关）。如果工厂i 和k 分别设在城市j 和l ，显然这两家间的通讯费由
c ijkl =t ik d
jl
t
来确定。因而总费用可用上述目标函数来表示。
例7.9 有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任
何一个阶段4名同学的顺序是一样的）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示（单位：分钟）：
这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)
! 学生间的面试先后次序保持不变的约束; @for(ss(I,K):
@for(phases(J):
x(I,J)+t(I,J)-x(K,J)
x(K,J)+t(K,J)-x(I,J)
! 目标函数; min =TMAX;
@for(students(I):
x(I,3)+t(I,3)
! 把Y 定义0-1变量; @for(ss: @bin(y)); end
计算的部分结果为：
Global optimal solution found at iteration: 898 Objective value: 84.00000
Variable Value Reduced Cost NS 4.000000 0.000000 NP 3.000000 0.000000 TMAX 84.00000 0.000000 X( S1, P1) 8.000000 0.000000 X( S1, P2) 21.00000 0.000000 X( S1, P3) 36.00000 0.000000 X( S2, P1) 21.00000 0.000000 X( S2, P2) 36.00000 0.000000 X( S2, P3) 56.00000 0.000000 X( S3, P1) 31.00000 0.000000 X( S3, P2) 56.00000 0.000000 X( S3, P3) 74.00000 0.000000 X( S4, P1) 0.000000 1.000000 X( S4, P2) 8.000000 0.000000 X( S4, P3) 18.00000 0.000000 Y( S1, S2) 0.000000 -200.0000 Y( S1, S3) 0.000000 0.000000 Y( S1, S4) 1.000000 200.0000 Y( S2, S3) 0.000000 -200.0000 Y( S2, S4) 1.000000 0.000000 Y( S3, S4) 1.000000 0.000000