二次分配問題

1、例7.8 二次分配問題（Quadratic Assignment Problem）這個問題是指派問題的一種推廣。可以把指派問題看作線性規(guī)劃問題，故較易求解，而二次分配問題是純整數(shù)規(guī)劃問題，往往很難求解。與分配問題一樣，二次分配問題也與兩個目標集合S、T有關。S和T含有相同數(shù)目的元素，以便達到某一目標。這里兩種必須滿足的條件：必須把S的每個元素確切地分配給T的一個元素；T的每個元素只能接受S的一個元素?？梢?-1變量：。用和分配問題相同的約束條件給出以上兩個條件：，但是本問題的目標比分配問題的更加復雜。我們得到的價格系數(shù)，其解釋是：在（S的一個元素）分配給（T的一個元素）的同時把（S的一個元素

2、）分配給（T的一個元素）所應承擔的費用。顯然，只有當且，即其乘積時，才承擔這種費用。于是本目標變成一個0-1變量的二次表達式：。最常見的是系數(shù)從其它系數(shù)和的乘積推出來的情況：。為了弄清這個相當復雜的模型，研究下面兩個應用是有好處的。首先認為S是一個n個工廠的集合，T是一個n個城市的集合。本問題就是要在每一城市中設置一個工廠，并要使工廠之間總的通訊費用最小。通訊費用取決于（1）每對工廠之間通訊的次數(shù)；（2）每對工廠所在兩個城市之間的距離。顯然，有些工廠很少與別的工廠通訊，雖相距甚遠而費用卻不大。另一方面，有些工廠可能需要大量通訊。通訊費取決于距離的遠近。在這個應用中，表示工廠i和工廠k之間的通訊

3、次數(shù)（以適當?shù)膯挝挥嬃浚?；為城市j和城市之間每單位的通訊費用（顯然這與j和之間的距離有關）。如果工廠i和k分別設在城市j和，顯然這兩家間的通訊費由來確定。因而總費用可用上述目標函數(shù)來表示。             例7.9 有4名同學到一家公司參加三個階段的面試：公司要求每個同學都必須首先找公司秘書初試，然后到部門主管處復試，最后到經(jīng)理處參加面試，并且不允許插隊（即在任何一個階段4名同學的順序是一樣的）。由于4名同學的專業(yè)背景不同，所以每人在三個階段的面試時間也不同，如下表所

4、示（單位：分鐘）： 秘書初試主管復試經(jīng)理面試同學甲131520同學乙102018同學丙201610同學丁81015      這4名同學約定他們?nèi)棵嬖囃暌院笠黄痣x開公司。假定現(xiàn)在時間是早晨8:00，問他們最早何時能離開公司?（建立規(guī)劃模型求解） 本問題是一個排列排序問題。對于階段數(shù)不小于3的問題沒有有效算法，也就是說對于學生數(shù)稍多一點兒（比如20）的情況是無法精確求解的。為此人們找到了很多近似算法。這里我們建立的規(guī)劃模型可以實現(xiàn)該問題的精確求解，但你會看到它的變量和約束是學生數(shù)的平方。因此，當學生數(shù)稍多一點兒規(guī)劃模型的規(guī)模

5、經(jīng)很大，求解會花費很長時間。 記  !三階段面試模型;model:sets: students; !學生集三階段面試模型; phases; !階段集; sp(students,phases):t,x; ss(students,students) | &1 #LT# &2:y;endsetsdata: students = s1.s4; phases = p1.p3; t= 13 15 20 10 20 18 20 16 10 8 10 15; enddata ns=size(students); !學生數(shù); np=size(phases); !階段數(shù);

6、60; !單個學生面試時間先后次序的約束; 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); ) ); !目標函數(shù); min=TMAX; for(students(I): x(I,3)+t(I,3)<=TMAX ); !把Y定義0-1變量; for(ss: bin(y);end計算的

7、部分結(jié)果為： 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