二次分配問題

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

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

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

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

5、經(jīng)很大，求解會花費(fèi)很長時(shí)間。 記  !三階段面試模型;model:sets: students; !學(xué)生集三階段面試模型; 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); !學(xué)生數(shù); np=size(phases); !階段數(shù);

6、60; !單個學(xué)生面試時(shí)間先后次序的約束; for(sp(I,J) | J #LT# np: x(I,J)+t(I,J)<=x(I,J+1) ); !學(xué)生間的面試先后次序保持不變的約束; 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); ) ); !目標(biāo)函數(shù); min=TMAX; for(students(I): x(I,3)+t(I,3)<=TMAX ); !把Y定義0-1變量; for(ss: bin(y);end計(jì)算的

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