【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《二次分配问题(QuadraticAssignmentProblem)》，欢迎阅读！
例 7.8 二次分配问题（Quadratic Assignment Problem ）
这个问题是指派问题的一种推广。可以把指派问题看作线性规划问题，故较易求解，而二次分配 问题是纯整数规划问题，往往很难求解。
与分配问题一样，二次分配问题也与两个目标集合 便达到某一目标。这里两种必须满足的条件：必须把
S、T有关。S和T含有相同数目的元素，以 S的每个元素确切地分配给
T的一个元素；T的
Xj
每个元素只能接受 S的一个元素。可引入 0-1变量：
1,把i （S的一个元素）分配给j（ T的一个元素） 0,
用和分配问题相同的约束条件给出以上两个条件：
n
Xij 1, i 1,2, ,n
j 1 n
Xij 1, j 1, 2,
i 1
, n
Cjkl
但是本问题的目标比分配问题的更加复杂。
j
我们得到的价格系数
，其解释是：在i （S的一个元素） 分配给
（ T的一个元素）的同时把 k（ S的一个元素）分配给I （T的一个元素）所应承担的费用。
Xij
1
显然，只有当
变量的二次表达式:
且
Xkl 1
，即其乘积
XijXkl 1
时，才承担这种费用。于是本目标变成一个
c
X
X
0-1
ijkl ij ki
i 1 j 1 k 1 l 1
o
最常见的是系数
Cijkl
从其它系数
tik
和
djl
的乘积推出来的情况：
Cijkl tikdjl
o为了弄清这个相当复杂
的模型，研究下面两个应用是有好处的。
首先认为S是一个n个工厂的集合，T是一个n个城市的集合。本问题就是要在每一城市中设置
一个工厂，并要使工厂之间总的通讯费用最小。通讯费用取决于（ 每对工厂所在两个城市之间的距离。
显然，有些工厂很少与别的工厂通讯，虽相距甚远而费用却不大。另一方面，有些工厂可能需要 大量通讯。通讯费取决于距离的远近。 当的单位计量）；
djl
1）每对工厂之间通讯的次数； （2）
在这个应用中，
tik
表示工厂i和工厂k之间的通讯次数（以适
j和I之间的距离有关）。如 来确定。因而总费用可用上
为城市j和城市|之间每单位的通讯费用（显然这与
Cijkl tikdjl
果工厂i和k分别设在城市j和l，显然这两家间的通讯费由 述目标函数来表示。
例7.9有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书 初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段
学的顺序是一样的）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下 表所示（单位：分钟）：
秘书初试 主管复试 经理面试
4名同
同学甲 同学乙 同学丙
13 10 20 8
15 20 16 10
20 18 10 15
8:00 ,问他们最早何时能
同学丁
这4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨 离开公司？（建立规划模型求解）
本问题是一个排列排序问题。
对于阶段数不小于 3的问题没有有效算法， 也就是说对于学生数稍
多一点儿（比如 20）的情况是无法精确求解的。为此人们找到了很多近似算法。这里我们建立的规 划模型可以实现该问题的精确求解，但你会看到它的变量和约束是学生数的平方。因此，当学生数稍 多一点儿规划模型的规模经很大，求解会花费很长时间。 !三阶段面试模型；
model: sets : students; phases;
!学生集三阶段面试模型 !阶段集；
；
sp(stude nts,phases):t,x;
ss(students,students) | &1 #LT# &2:y; en dsets data :
stude nts = s1..s4; phases = p1..p3; t= 13 15 20 10 20 18 20 16 10 8 10 15; en ddata
ns= @size(students); !学生数; np= @size(phases); !阶段数; !单个学生面试时间先后次序的约束 @for(sp(l,J) | J #LT# np: x(l,J)+t(l,J)v=x(l,J+1) );
!学生间的面试先后次序保持不变的约束 @for(ss(I,K):
@for(phases(J): x(l,J)+t(l,J)-x(K,J)v=200*y(l,K); x(K,J)+t(K,J)-x(l,J)v=200*(1-y(l,K)); ) );
!目标函数； mi n= TMAX; @for(stude nts(l): x(l,3)+t(l,3)v=TMAX );
!把丫定义0-1变量； @for(ss: @bin (y)); end
；
；
计算的部分结果为：
Global optimal solution found at iteration: Objective value:
84.00000 Variable
NS NP TMAX X( S1, P1) X( S1, P2)
Value 4.000000 3.000000 84.00000 8.000000 21.00000
Reduced Cost
0.000000 0.000000
0.000000 0.000000 0.000000
898
本文来源：https://www.wddqxz.cn/eccd79f0c2c708a1284ac850ad02de80d4d80683.html
2022-04-04
