裝配線平衡模型

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