例 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时,才承担这种费用。于是本目标变成一个 cXX0-1 ijkl ij ki i 1 j 1 k 1 l 1 o 最常见的是系数Cijkl从其它系数tik和djl的乘积推出来的情况:Cijkl tikdjl o为了弄清这个相当复杂 的模型,研究下面两个应用是有好处的。 首先认为S是一个n个工厂的集合,T是一个n个城市的集合。本问题就是要在每一城市中设置 一个工厂,并要使工厂之间总的通讯费用最小。通讯费用取决于( 每对工厂所在两个城市之间的距离。 显然,有些工厂很少与别的工厂通讯,虽相距甚远而费用却不大。另一方面,有些工厂可能需要 大量通讯。通讯费取决于距离的远近。 当的单位计量);djl1)每对工厂之间通讯的次数; (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.wddqw.com/doc/eccd79f0c2c708a1284ac850ad02de80d4d80683.html