裝配線平衡模型

§7綜合舉例例求解非線性方程組其LINGO代碼如下：model:x^2+y^2=2;2*x^2+x+y^2+y=4;end計(jì)算的部分結(jié)果為Feasiblesolutionfoundatiteration:0VariableValueXY例裝配線平衡模型一條裝配線含有一系列的工作站，在最終產(chǎn)品的加工過程中每個(gè)工作站執(zhí)行一種或幾種特定的任務(wù)。裝配線周期是指所有工作站完成分配給它們各自的任務(wù)所化費(fèi)時(shí)間中的最大值。平衡裝配線的目標(biāo)是為每個(gè)工作站分配加工任務(wù)，盡可能使每個(gè)工作站執(zhí)行相同數(shù)量的任務(wù)，其最終標(biāo)準(zhǔn)是裝配線周期最短。不適當(dāng)?shù)钠胶庋b配線將會(huì)產(chǎn)生瓶頸——有較少任務(wù)的工作站將被迫等待其前面分配了較多任務(wù)的工作站。問題會(huì)因?yàn)楸姸嗳蝿?wù)間存在優(yōu)先關(guān)系而變得更復(fù)雜，任務(wù)的分配必須服從這種優(yōu)先關(guān)系。這個(gè)模型的目標(biāo)是最小化裝配線周期。有2類約束：①要保證每件任務(wù)只能也必須分配至一個(gè)工作站來加工；②要保證滿足任務(wù)間的所有優(yōu)先關(guān)系。例有11件任務(wù)（A—K）分配到4個(gè)工作站（1—4），任務(wù)的優(yōu)先次序如下圖。每件任務(wù)所花費(fèi)的時(shí)間如下表。(A)(A)(B)(C)(F)(G)(K)(J)(I)(H)(E)(D)任務(wù)ABCDEFGHIJK時(shí)間4511950151212121289MODEL:!裝配線平衡模型;SETS:!任務(wù)集合，有一個(gè)完成時(shí)間屬性T;TASK/ABCDEFGHIJK/:T;!任務(wù)之間的優(yōu)先關(guān)系集合（A必須完成才能開始B，等等）;PRED(TASK,TASK)/A,BB,CC,FC,GF,JG,JJ,KD,EE,HE,IH,JI,J/;!工作站集合;STATION/1..4/;TXS(TASK,STATION):X;!X是派生集合TXS的一個(gè)屬性。如果X（I，K）＝1，則表示第I個(gè)任務(wù)指派給第K個(gè)工作站完成;ENDSETSDATA:!任務(wù)ABCDEFGHIJK的完成時(shí)間估計(jì)如下;T=4511950151212121289;ENDDATA!當(dāng)任務(wù)超過15個(gè)時(shí)，模型的求解將變得很慢;!每一個(gè)作業(yè)必須指派到一個(gè)工作站，即滿足約束①;@FOR(TASK(I):@SUM(STATION(K):X(I,K))=1);!對(duì)于每一個(gè)存在優(yōu)先關(guān)系的作業(yè)對(duì)來說，前者對(duì)應(yīng)的工作站I必須小于后者對(duì)應(yīng)的工作站J，即滿足約束②;@FOR(PRED(I,J):@SUM(STATION(K):K*X(J,K)-K*X(I,K))>=0);!對(duì)于每一個(gè)工作站來說，其花費(fèi)時(shí)間必須不大于裝配線周期;@FOR(STATION(K):@SUM(TXS(I,K):T(I)*X(I,K))<=CYCTIME);!目標(biāo)函數(shù)是最小化轉(zhuǎn)配線周期;MIN=CYCTIME;!指定X(I,J)為0/1變量;@FOR(TXS:@BIN(X));END計(jì)算的部分結(jié)果為Globaloptimalsolutionfoundatiteration:1255Objectivevalue:VariableValueReducedCostCYCTIMEX(A,1)X(A,2)X(A,3)X(A,4)X(B,1)X(B,2)X(B,3)X(B,4)X(C,1)X(C,2)X(C,3)X(C,4)X(D,1)X(D,2)X(D,3)X(D,4)X(E,1)X(E,2)X(E,3)X(E,4)X(F,1)X(F,2)X(F,3)X(F,4)X(G,1)X(G,2)X(G,3)X(G,4)X(H,1)X(H,2)X(H,3)X(H,4)X(I,1)X(I,2)X(I,3)X(I,4)X(J,1)X(J,2)X(J,3)X(J,4)X(K,1)X(K,2)X(K,3)X(K,4)例旅行售貨員問題（又稱貨郎擔(dān)問題，TravelingSalesmanProblem）有一個(gè)推銷員，從城市1出發(fā)，要遍訪城市2，3，…，n各一次，最后返回城市1。已知從城市i到j(luò)的旅費(fèi)為，問他應(yīng)按怎樣的次序訪問這些城市，使得總旅費(fèi)最少可以用多種方法把TSP表示成整數(shù)規(guī)劃模型。這里介紹的一種建立模型的方法，是把該問題的每個(gè)解（不一定是最優(yōu)的）看作是一次“巡回”。在下述意義下，引入一些0-1整數(shù)變量：其目標(biāo)只是使為最小。這里有兩個(gè)明顯的必須滿足的條件：訪問城市i后必須要有一個(gè)即將訪問的確切城市；訪問城市j前必須要有一個(gè)剛剛訪問過的確切城市。用下面的兩組約束分別實(shí)現(xiàn)上面的兩個(gè)條件。123123456以上兩個(gè)條件都滿足，但它顯然不是TSP的解，它存在兩個(gè)子巡回。這里，我們將敘述一種在原模型上附加充分的約束條件以避免產(chǎn)生子巡回的方法。把額外變量附加到問題中?？砂堰@些變量看作是連續(xù)的（最然這些變量在最優(yōu)解中取普通的整數(shù)值）?，F(xiàn)在附加下面形式的約束條件。為了證明該約束條件有預(yù)期的效果，必須證明：（1）任何含子巡回的路線都不滿足該約束條件；（2）全部巡回都滿足該約束條件。首先證明（1），用反證法。假設(shè)還存在子巡回，也就是說至少有兩個(gè)子巡回。那么至少存在一個(gè)子巡回中不含城市1。把該子巡回記為，則必有把這k個(gè)式子相加，有，矛盾！故假設(shè)不正確，結(jié)論（1）得證。下面證明（2），采用構(gòu)造法。對(duì)于任意的總巡回，可取訪問城市i的順序數(shù)，取值范圍為。因此，。下面來證明總巡回滿足該約束條件。(ⅰ)總巡回上的邊（ⅱ）非總巡回上的邊從而結(jié)論（2）得證。這樣我們把TSP轉(zhuǎn)化成了一個(gè)混合整數(shù)線性規(guī)劃問題。顯然，當(dāng)城市個(gè)數(shù)較大（大于30）時(shí)，該混合整數(shù)線性規(guī)劃問題的規(guī)模會(huì)很大，從而給求解帶來很大問題。TSP已被證明是NP難問題，目前還沒有發(fā)現(xiàn)多項(xiàng)式時(shí)間的算法。對(duì)于小規(guī)模問題，我們求解這個(gè)混合整數(shù)線性規(guī)劃問題的方式還是有效的。TSP是一個(gè)重要的組合優(yōu)化問題，除了有直觀的應(yīng)用外，許多其它看似無聯(lián)系的優(yōu)化問題也可轉(zhuǎn)化為TSP。例如：問題1現(xiàn)需在一臺(tái)機(jī)器上加工n個(gè)零件（如燒瓷器），這些零件可按任意先后順序在機(jī)器上加工。我們希望加工完成所有零件的總時(shí)間盡可能少。由于加工工藝的要求，加工零件時(shí)機(jī)器必須處于相應(yīng)狀態(tài)（如爐溫）。設(shè)起始未加工任何零件時(shí)機(jī)器處于狀態(tài)，且當(dāng)所有零件加工完成后需恢復(fù)到狀態(tài)。已知從狀態(tài)調(diào)整到狀態(tài)需要時(shí)間。零件本身加工時(shí)間為。為方便起見，引入一個(gè)虛零件0，其加工時(shí)間為0，要求狀態(tài)為，則{0，1，2，…，n}的一個(gè)圈置換π就表示對(duì)所有零件的一個(gè)加工順序，在此置換下，完成所有加工所需要的總時(shí)間為由于是一個(gè)常數(shù)，故該零件的加工順序問題變成TSP。!旅行售貨員問題;model:sets:city/1..5/:u;link(city,city):dist,!距離矩陣;x;endsetsn=@size(city);data:!距離矩陣，它并不需要是對(duì)稱的;dist=@qrand(1);!隨機(jī)產(chǎn)生，這里可改為你要解決的問題的數(shù)據(jù);enddata!目標(biāo)函數(shù);min=@sum(link:dist*x);@FOR(city(K):!進(jìn)入城市K;@sum(city(I)|I#ne#K:x(I,K))=1;!離開城市K;@sum(city(J)|J#ne#K:x(K,J))=1;);!保證不出現(xiàn)子圈;@for(city(I)|I#gt#1:@for(city(J)|J#gt#1#and#I#ne#J:u(I)-u(J)+n*x(I,J)<=n-1););!限制u的范圍以加速模型的求解，保證所加限制并不排除掉TSP問題的最優(yōu)解;@for(city(I)|I#gt#1:u(I)<=n-2);!定義X為0\1變量;@for(link:@bin(x));end計(jì)算的部分結(jié)果為：Globaloptimalsolutionfoundatiteration:77Objectivevalue:VariableValueReducedCostNU(1)U(2)U(3)U(4)U(5)DIST(1,1)DIST(1,2)DIST(1,3)DIST(1,4)DIST(1,5)DIST(2,1)DIST(2,2)DIST(2,3)DIST(2,4)DIST(2,5)DIST(3,1)DIST(3,2)DIST(3,3)DIST(3,4)DIST(3,5)DIST(4,1)DIST(4,2)DIST(4,3)DIST(4,4)DIST(4,5)DIST(5,1)DIST(5,2)DIST(5,3)DIST(5,4)DIST(5,5)X(1,1)X(1,2)X(1,3)X(1,4)X(1,5)X(2,1)X(2,2)X(2,3)X(2,4)X(2,5)X(3,1)X(3,2)X(3,3)X(3,4)X(3,5)X(4,1)X(4,2)X(4,3)X(4,4)X(4,5)X(5,1)X(5,2)X(5,3)X(5,4)X(5,5)例最短路問題給定N個(gè)點(diǎn)組成集合，由集合中任一點(diǎn)到另一點(diǎn)的距離用表示，如果到?jīng)]有弧聯(lián)結(jié)，則規(guī)定，又規(guī)定，指定一個(gè)終點(diǎn)，要求從點(diǎn)出發(fā)到的最短路線。這里我們用動(dòng)態(tài)規(guī)劃方法來做。用所在的點(diǎn)表示狀態(tài)，決策集合就是除以外的點(diǎn)，選定一個(gè)點(diǎn)以后，得到效益并轉(zhuǎn)入新狀態(tài)，當(dāng)狀態(tài)是時(shí)，過程停止。顯然這是一個(gè)不定期多階段決策過程。定義是由點(diǎn)出發(fā)至終點(diǎn)的最短路程，由最優(yōu)化原理可得這是一個(gè)函數(shù)方程，用LINGO可以方便的解決。!最短路問題;model:data:n=10;enddatasets:cities/1..n/:F;!10個(gè)城市;roads(cities,cities)/1,21,32,42,52,63,43,53,64,74,85,75,85,96,86,97,108,109,10/:D,P;endsetsdata:D=65369751191875410579;enddataF(n)=0;@for(cities(i)|i#lt#n:F(i)=@min(roads(i,j):D(i,j)+F(j)););!顯然，如果P(i,j)=1,則點(diǎn)i到點(diǎn)n的最短路徑的第一步是i-->j，否則就不是。由此，我們就可方便的確定出最短路徑;@for(roads(i,j):P(i,j)=@if(F(i)#eq#D(i,j)+F(j),1,0));end計(jì)算的部分結(jié)果為：Feasiblesolutionfoundatiteration:0VariableValueNF(1)F(2)F(3)F(4)F(5)F(6)F(7)F(8)F(9)F(10)P(1,2)P(1,3)P(2,4)P(2,5)P(2,6)P(3,4)P(3,5)P(3,6)P(4,7)P(4,8)P(5,7)P(5,8)P(5,9)P(6,8)P(6,9)P(7,10)P(8,10)P(9,10)例露天礦生產(chǎn)的車輛安排（CMCM2003B）鋼鐵工業(yè)是國家工業(yè)的基礎(chǔ)之一，鐵礦是鋼鐵工業(yè)的主要原料基地。許多現(xiàn)代化鐵礦是露天開采的，它的生產(chǎn)主要是由電動(dòng)鏟車（以下簡稱電鏟）裝車、電動(dòng)輪自卸卡車（以下簡稱卡車）運(yùn)輸來完成。提高這些大型設(shè)備的利用率是增加露天礦經(jīng)濟(jì)效益的首要任務(wù)。露天礦里有若干個(gè)爆破生成的石料堆，每堆稱為一個(gè)鏟位，每個(gè)鏟位已預(yù)先根據(jù)鐵含量將石料分成礦石和巖石。一般來說，平均鐵含量不低于25%的為礦石，否則為巖石。每個(gè)鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個(gè)鏟位至多能安置一臺(tái)電鏟，電鏟的平均裝車時(shí)間為5分鐘。卸貨地點(diǎn)（以下簡稱卸點(diǎn)）有卸礦石的礦石漏、2個(gè)鐵路倒裝場（以下簡稱倒裝場）和卸巖石的巖石漏、巖場等，每個(gè)卸點(diǎn)都有各自的產(chǎn)量要求。從保護(hù)國家資源的角度及礦山的經(jīng)濟(jì)效益考慮，應(yīng)該盡量把礦石按礦石卸點(diǎn)需要的鐵含量（假設(shè)要求都為%1%，稱為品位限制）搭配起來送到卸點(diǎn)，搭配的量在一個(gè)班次（8小時(shí)）內(nèi)滿足品位限制即可。從長遠(yuǎn)看，卸點(diǎn)可以移動(dòng)，但一個(gè)班次內(nèi)不變?？ㄜ嚨钠骄盾嚂r(shí)間為3分鐘。所用卡車載重量為154噸，平均時(shí)速28。卡車的耗油量很大，每個(gè)班次每臺(tái)車消耗近1噸柴油。發(fā)動(dòng)機(jī)點(diǎn)火時(shí)需要消耗相當(dāng)多的電瓶能量，故一個(gè)班次中只在開始工作時(shí)點(diǎn)火一次。卡車在等待時(shí)所耗費(fèi)的能量也是相當(dāng)可觀的，原則上在安排時(shí)不應(yīng)發(fā)生卡車等待的情況。電鏟和卸點(diǎn)都不能同時(shí)為兩輛及兩輛以上卡車服務(wù)?？ㄜ嚸看味际菨M載運(yùn)輸。每個(gè)鏟位到每個(gè)卸點(diǎn)的道路都是專用的寬60的雙向車道，不會(huì)出現(xiàn)堵車現(xiàn)象，每段道路的里程都是已知的。一個(gè)班次的生產(chǎn)計(jì)劃應(yīng)該包含以下內(nèi)容：出動(dòng)幾臺(tái)電鏟，分別在哪些鏟位上；出動(dòng)幾輛卡車，分別在哪些路線上各運(yùn)輸多少次（因?yàn)殡S機(jī)因素影響，裝卸時(shí)間與運(yùn)輸時(shí)間都不精確，所以排時(shí)計(jì)劃無效，只求出各條路線上的卡車數(shù)及安排即可）。一個(gè)合格的計(jì)劃要在卡車不等待條件下滿足產(chǎn)量和質(zhì)量（品位）要求，而一個(gè)好的計(jì)劃還應(yīng)該考慮下面兩條原則之一：1.總運(yùn)量（噸公里）最小，同時(shí)出動(dòng)最少的卡車，從而運(yùn)輸成本最??；2.利用現(xiàn)有車輛運(yùn)輸，獲得最大的產(chǎn)量（巖石產(chǎn)量優(yōu)先；在產(chǎn)量相同的情況下，取總運(yùn)量最小的解）。請(qǐng)你就兩條原則分別建立數(shù)學(xué)模型，并給出一個(gè)班次生產(chǎn)計(jì)劃的快速算法。針對(duì)下面的實(shí)例，給出具體的生產(chǎn)計(jì)劃、相應(yīng)的總運(yùn)量及巖石和礦石產(chǎn)量。某露天礦有鏟位10個(gè)，卸點(diǎn)5個(gè)，現(xiàn)有鏟車7臺(tái)，卡車20輛。各卸點(diǎn)一個(gè)班次的產(chǎn)量要求：礦石漏萬噸、倒裝場Ⅰ萬噸、倒裝場Ⅱ萬噸、巖石漏萬噸、巖場萬噸。鏟位和卸點(diǎn)位置二維示意圖如下，各鏟位和各卸點(diǎn)之間的距離（公里）如下表：鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏倒裝場Ⅰ巖場巖石漏倒裝場Ⅱ各鏟位礦石、巖石數(shù)量(萬噸)和礦石的平均鐵含量如下表：鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石量0．951．051．001．051．101．251．051．301．351．25巖石量1．251．101．351．051．151．351．051．151．351．25鐵含量30%28%29%32%31%33%32%31%33%31%model:titleCUMCM-2003B-01;sets:cai/1..10/:crate,cnum,cy,ck,flag;xie/1..5/:xsubject,xnum;link(xie,cai):distance,lsubject,number,che,b;endsetsdata:crate=30282932313332313331;xsubject=;distance=;cy=;ck=;enddata!目標(biāo)函數(shù);min=@sum(cai(i):@sum(xie(j):number(j,i)*154*distance(j,i)));!max=@sum(link(i,j):number(i,j));!max=xnum(3)+xnum(4)+xnum(1)+xnum(2)+xnum(5);!min=@sum(cai(i):!@sum(xie(j):!number(j,i)*154*distance(j,i)));!xnum(1)+xnum(2)+xnum(5)=340;!xnum(1)+xnum(2)+xnum(5)=341;!xnum(3)=160;!xnum(4)=160;!卡車每一條路線上最多可以運(yùn)行的次數(shù);@for(link(i,j):b(i,j)=@floor((8*60-(@floor((distance(i,j)/28*60*2+3+5)/5)-1)*5)/(distance(i,j)/28*60*2+3+5)));!b(i,j)=@floor(8*60/(distance(i,j)/28*60*2+3+5)));!t(i,j)=@floor((distance(i,j)/28*60*2+3+5)/5);!b(i,j)=@floor((8*60-(@floor((distance(i,j)/28*60*2+3+5)/5))*5)/(distance(i,j)/28*60*2+3+5)));!每一條路線上的最大總車次的計(jì)算;@for(link(i,j):lsubject(i,j)=(@floor((distance(i,j)/28*60*2+3+5)/5))*b(i,j));!計(jì)算各個(gè)鏟位的總產(chǎn)量;@for(cai(j):cnum(j)=@sum(xie(i):number(i,j)));!計(jì)算各個(gè)卸點(diǎn)的總產(chǎn)量;@for(xie(i):xnum(i)=@sum(cai(j):number(i,j)));!道路能力約束;@for(link(i,j):number(i,j)<=lsubject(i,j));!電鏟能力約束;@for(cai(j):cnum(j)<=flag(j)*8*60/5);!電鏟數(shù)量約束----addedbyXieJinxing,2003-09-07;@sum(cai(j):flag(j))<=7;!卸點(diǎn)能力約束;@for(xie(i):xnum(i)<=8*20);!鏟位產(chǎn)量約束;@for(cai(i):number(1,i)+number(2,i)+number(5,i)<=ck(i)*10000/154);@for(cai(i):number(3,i)+number(4,i)<=cy(i)*10000/154);!產(chǎn)量任務(wù)約束;@for(xie(i):xnum(i)>=xsubject(i)*10000/154);!鐵含量約束;@sum(cai(j):number(1,j)*(crate(j))<=0;@sum(cai(j):number(2,j)*(crate(j))<=0;@sum(cai(j):number(5,j)*(crate(j))<=0;@sum(cai(j):number(1,j)*(crate(j))>=0;@sum(cai(j):number(2,j)*(crate(j))>=0;@sum(cai(j):number(5,j)*(crate(j))>=0;!關(guān)于車輛的具體分配;@for(link(i,j):che(i,j)=number(i,j)/b(i,j));!各個(gè)路線所需卡車數(shù)簡單加和;hehe=@sum(link(i,j):che(i,j));!整數(shù)約束;@for(link(i,j):@gin(number(i,j)));@for(cai(j):@bin(flag(j)));!車輛能力約束;hehe<=20;ccnum=@sum(cai(j):cnum(j));end例最小生成樹（MinimalSpanningTree，MST）問題求解最小生成樹的方法雖然很多，但是利用LINGO建立相應(yīng)的整數(shù)規(guī)劃模型是一種新的嘗試。這對(duì)于處理非標(biāo)準(zhǔn)的MST問題非常方便。我們主要參考了文[7]。在圖論中，稱無圈的連通圖為樹。在一個(gè)連通圖G中，稱包含圖G全部頂點(diǎn)的樹為圖G的生成樹。生成樹上各邊的權(quán)之和稱為該生成樹的權(quán)。連通圖G的權(quán)最小的生成樹稱為圖G的最小生成樹。許多實(shí)際問題都可以歸結(jié)為最小生成樹。例如,如何修筑一些公路把若干個(gè)城鎮(zhèn)連接起來；如何架設(shè)通訊網(wǎng)絡(luò)將若干個(gè)地區(qū)連接起來；如何修筑水渠將水源和若干塊待灌溉的土地連接起來等等。為了說明問題,以下面的問題作為范例。范例：假設(shè)某電話公司計(jì)劃在六個(gè)村莊架設(shè)電話線，各村莊之間的距離如圖所示。試求出使電話線總長度最小的架線方案。V1V2V3V1V2V3V4V5V61122233345MST的整數(shù)規(guī)劃模型如下：例分配問題（指派問題，AssignmentProblem）這是個(gè)給n個(gè)人分配n項(xiàng)工作以獲得某個(gè)最高總效果的問題。第i個(gè)人完成第j項(xiàng)工作需要平均時(shí)間。要求給每個(gè)人分配一項(xiàng)工作，并要求分配完這些工作，以使完成全部任務(wù)的總時(shí)間為最小。該問題可表示如下：顯然，此問題可看作是運(yùn)輸問題的特殊情況。可將此問題看作具有n個(gè)源和n個(gè)匯的問題，每個(gè)源有1單位的可獲量，而每個(gè)匯有1單位的需要量。從表面看，這問題要求用整數(shù)規(guī)劃以保證能取0或1。然而，幸運(yùn)的是，此問題是運(yùn)輸問題的特例，因此即使不限制取0或1，最優(yōu)解也將取0或1。如果把婚姻看作分配問題，丹茨證明，整數(shù)性質(zhì)證明一夫一妻會(huì)帶來最美滿幸福的生活！顯然，分配問題可以作為線性規(guī)劃問題來求解，盡管模型可能很大。例如，給100人分配100項(xiàng)工作將使所得的模型具有10000個(gè)變量。這時(shí)，如采用專門算法效果會(huì)更好。時(shí)間復(fù)雜度為的匈牙利算法便是好選擇，這是由Kuhu（1955）提出的。model:!7個(gè)工人，7個(gè)工作的分配問題;sets:workers/w1..w7/;jobs/j1..j7/;links(workers,jobs):cost,volume;endsets!目標(biāo)函數(shù);min=@sum(links:cost*volume);!每個(gè)工人只能有一份工作;@for(workers(I):@sum(jobs(J):volume(I,J))=1;);!每份工作只能有一個(gè)工人;@for(jobs(J):@sum(workers(I):volume(I,J))=1;);data:cost=6267425495385852197437673927239572655228114923124510;enddataend計(jì)算的部分結(jié)果為：Globaloptimalsolutionfoundatiteration:14Objectivevalue:VariableValueReducedCostVOLUME(W1,J1)VOLUME(W1,J2)VOLUME(W1,J3)VOLUME(W1,J4)VOLUME(W1,J5)VOLUME(W1,J6)VOLUME(W1,J7)VOLUME(W2,J1)VOLUME(W2,J2)VOLUME(W2,J3)VOLUME(W2,J4)VOLUME(W2,J5)VOLUME(W2,J6)VOLUME(W2,J7)VOLUME(W3,J1)VOLUME(W3,J2)VOLUME(W3,J3)VOLUME(W3,J4)VOLUME(W3,J5)VOLUME(W3,J6)VOLUME(W3,J7)VOLUME(W4,J1)VOLUME(W4,J2)VOLUME(W4,J3)VOLUME(W4,J4)VOLUME(W4,J5)VOLUME(W4,J6)VOLUME(W4,J7)VOLUME(W5,J1)VOLUME(W5,J2)VOLUME(W5,J3)VOLUME(W5,J4)VOLUME(W5,J5)VOLUME(W5,J6)VOLUME(W5,J7)VOLUME(W6,J1)VOLUME(W6,J2)VOLUME(W6,J3)VOLUME(W6,J4)VOLUME(W6,J5)VOLUME(W6,J6)VOLUME(W6,J7)VOLUME(W7,J1)VOLUME(W7,J2)VOLUME(W7,J3)VOLUME(W7,J4)VOLUME(W7,J5)VOLUME(W7,J6)VOLUME(W7,J7)例二次分配問題（QuadraticAssignmentProblem）這個(gè)問題是指派問題的一種推廣?？梢园阎概蓡栴}看作線性規(guī)劃問題，故較易求解，而二次分配問題是純整數(shù)規(guī)劃問題，往往很難求解。與分配問題一樣，二次分配問題也與兩個(gè)目標(biāo)集合S、T有關(guān)。S和T含有相同數(shù)目的元素，以便達(dá)到某一目標(biāo)。這里兩種必須滿足的條件：必須把S的每個(gè)元素確切地分配給T的一個(gè)元素；T的每個(gè)元素只能接受S的一個(gè)元素。可引入0-1變量：。用和分配問題相同的約束條件給出以上兩個(gè)條件：，但是本問題的目標(biāo)比分配問題的更加復(fù)雜。我們得到的價(jià)格系數(shù)，其解釋是：在（S的一個(gè)元素）分配給（T的一個(gè)元素）的同時(shí)把（S的一個(gè)元素）分配給（T的一個(gè)元素）所應(yīng)承擔(dān)的費(fèi)用。顯然，只有當(dāng)且，即其乘積時(shí)，才承擔(dān)這種費(fèi)用。于是本目標(biāo)變成一個(gè)0-1變量的二次表達(dá)式：。最常見的是系數(shù)從其它系數(shù)和的乘積推出來的情況：。為了弄清這個(gè)相當(dāng)復(fù)雜的模型，研究下面兩個(gè)應(yīng)用是有好處的。首先認(rèn)為S是一個(gè)n個(gè)工廠的集合，T是一個(gè)n個(gè)城市的集合。本問題就是要在每一城市中設(shè)置一個(gè)工廠，并要使工廠之間總的通訊費(fèi)用最小。通訊費(fèi)用取決于（1）每對(duì)工廠之間通訊的次數(shù)；（2）每對(duì)工廠所在兩個(gè)城市之間的距離。顯然，有些工廠很少與別的工廠通訊，雖相距甚遠(yuǎn)而費(fèi)用卻不大。另一方面，有些工廠可能需要大量通訊。通訊費(fèi)取決于距離的遠(yuǎn)近。在這個(gè)應(yīng)用中，表示工廠i和工廠k之間的通訊次數(shù)（以適當(dāng)?shù)膯挝挥?jì)量）；為城市j和城市之間每單位的通訊費(fèi)用（顯然這與j和之間的距離有關(guān)）。如果工廠i和k分別設(shè)在城市j和，顯然這兩家間的通訊費(fèi)由來確定。因而總費(fèi)用可用上述目標(biāo)函數(shù)來表示。例有4名同學(xué)到一家公司參加三個(gè)階段的面試：公司要求每個(gè)同學(xué)都必須首先找公司秘書初試，然后到部門主管處復(fù)試，最后到經(jīng)理處參加面試，并且不允許插隊(duì)（即在任何一個(gè)階段4名同學(xué)的順序是一樣的）。由于4名同學(xué)的專業(yè)背景不同，所以