LINGO在多目標(biāo)規(guī)劃和最大最小化模型中的應(yīng)用

1、LINGO在多目標(biāo)規(guī)劃和最大最小化模型中的應(yīng)用在許多實(shí)際問題中，決策者所期望的目標(biāo)往往不止一個(gè)，如電力網(wǎng)絡(luò)管理部門在制定發(fā)電計(jì)劃時(shí)即希望安全系數(shù)要大，也希望發(fā)電成本要小，這一類問題稱為多目標(biāo)最優(yōu)化問題或多目標(biāo)規(guī)劃問題。一、多目標(biāo)規(guī)劃的常用解法多目標(biāo)規(guī)劃的解法通常是根據(jù)問題的實(shí)際背景和特征，設(shè)法將多目標(biāo)規(guī)劃轉(zhuǎn)化為單目標(biāo)規(guī)劃，從而獲得滿意解，常用的解法有：1 .主要目標(biāo)法確定一個(gè)主要目標(biāo)，把次要目標(biāo)作為約束條件并設(shè)定適當(dāng)?shù)慕缦拗怠? .線性加權(quán)求和法對(duì)每個(gè)目標(biāo)按其重要程度賦適當(dāng)權(quán)重叫之0,且£%=1,然后把工叫f(x)作為新的目標(biāo)函數(shù)(其中fj(x),i=1,2,，p是原來的p個(gè)目標(biāo))。

2、3 .指數(shù)加權(quán)乘積法設(shè)fi(x),i=1,2，p是原來的p個(gè)目標(biāo),令pZ="fi(x)aii1其中ai為指數(shù)權(quán)重，把Z作為新的目標(biāo)函數(shù)。4 .理想點(diǎn)法先分別求出p個(gè)單目標(biāo)規(guī)劃的最優(yōu)解父，令h(x)=J，(fi(x)-fi*)2然后把它作為新的目標(biāo)函數(shù)。5 .分層序列法將所有p個(gè)目標(biāo)按其重要程度排序，先求出第一個(gè)最重要的目標(biāo)的最優(yōu)解，然后在保證前一個(gè)目標(biāo)最優(yōu)解的前提條件下依次求下一個(gè)目標(biāo)的最優(yōu)解，一直求到最后一個(gè)目標(biāo)為止。這些方法各有其優(yōu)點(diǎn)和適用的場(chǎng)合，但并非總是有效，有些方法存在一些不足之處。例如，線性加權(quán)求和法確定權(quán)重系數(shù)時(shí)有一定主觀性，權(quán)重系數(shù)取值不同，結(jié)果也就不一樣。線性加權(quán)求

3、和法、指數(shù)加權(quán)乘積法和理想點(diǎn)法通常只能用于兩個(gè)目標(biāo)的單位(量綱)相同的情況，如果兩個(gè)目標(biāo)是不同的物理量，它們的量綱不相同，數(shù)量級(jí)相差很大，則將它們相加或比較是不合適的。二、最大最小化模型在一些實(shí)際問題中，決策者所期望的目標(biāo)是使若干目標(biāo)函數(shù)中最大的一個(gè)達(dá)到最小(或多個(gè)目標(biāo)函數(shù)中最小的一個(gè)達(dá)到最大)。例如，城市規(guī)劃中需確定急救中心的位置，希望該中心到服務(wù)區(qū)域內(nèi)所有居民點(diǎn)的距離中的最大值達(dá)到最小，稱為最大最小化模型，這種確定目標(biāo)函數(shù)的準(zhǔn)則稱為最大最小化原則，在控制論，逼近論和決策論中也有使用。最大最小化模型的目標(biāo)函數(shù)可寫成minmaxf1(X),f2(X),fp(X)X或maxminf(X),f2(

4、X),fp(X)X式中X=(Xi,X2，Xn)T是決策變量。模型的約束條件可以包含線性、非線性的等式和不等式約束。這一模型的求解可視具體情況采用適當(dāng)?shù)姆椒āＨ?、用LINGO求解多目標(biāo)規(guī)劃和最大最小化模型1 .解多目標(biāo)規(guī)劃用LINGO求解多目標(biāo)規(guī)劃的基本方法是先確定一個(gè)目標(biāo)函數(shù)，求出它的最優(yōu)解，然后把此最優(yōu)值作為約束條件，求其他目標(biāo)函數(shù)的最優(yōu)解。如果將所有目標(biāo)函數(shù)都改成約束條件，則此時(shí)的優(yōu)化問題退化為一個(gè)含等式和不等式的方程組。LINGO能夠求解像這樣沒有目標(biāo)函數(shù)只有約束條件的混合組的可行解。有些組合優(yōu)化問題和網(wǎng)絡(luò)優(yōu)化問題，因?yàn)樽兞慷啵枰荛L運(yùn)算時(shí)間才能算出結(jié)果，如果設(shè)定一個(gè)期望的目標(biāo)值，把目

5、標(biāo)函數(shù)改成約束條件，則幾分鐘就能得到一個(gè)可行解，多試幾個(gè)目標(biāo)值，很快就能找到最優(yōu)解。對(duì)于多目標(biāo)規(guī)劃，同樣可以把多個(gè)目標(biāo)中的一部分乃至全部改成約束條件，取適當(dāng)?shù)南拗浦?，然后用LINGO求解，從中找出理想的最優(yōu)解，這樣處理的最大優(yōu)勢(shì)是求解速度快，節(jié)省時(shí)間。2 .解最大最小化問題第一步，先把原來較復(fù)雜的目標(biāo)函數(shù)式改寫為一個(gè)簡(jiǎn)單的目標(biāo)函數(shù)miC以及p個(gè)約束條件：fi(X)<C,f2(X)<C,fp(X)<C其他原有的約束條件不變，改寫后仍然是一個(gè)規(guī)劃，只是增加了p個(gè)約束條件，目標(biāo)函數(shù)的形式較為簡(jiǎn)單。如果能用LINGO求出它的解，則問題已經(jīng)解決，如果求解困難，可轉(zhuǎn)入下一步。第二步，取消

6、目標(biāo)函數(shù)，保留上一步由目標(biāo)函數(shù)改成的p個(gè)約束條件和所有原來的約束條件，預(yù)設(shè)C值為某個(gè)常數(shù)，此時(shí)原規(guī)劃模型不再是規(guī)劃，它僅僅包含等式和不等式，沒有目標(biāo)函數(shù)，是許多約束條件的組合，可以稱它為“混合組”。求該混合組的解，其實(shí)質(zhì)是求滿足所有約束條件并且使目標(biāo)函數(shù)等于給定值的一組決策變量的值，求出來的結(jié)果是可行解，它未必是最優(yōu)解。在存在可行解的前提下，使目標(biāo)函數(shù)值小的可行解優(yōu)于使目標(biāo)函數(shù)值大的可行解，使目標(biāo)函數(shù)值越小的可行解越接近最優(yōu)解。第三步，對(duì)具體問題作出分析，對(duì)目標(biāo)函數(shù)可能達(dá)到的最小值(即C的最小值)作適當(dāng)估計(jì)，然后在此估計(jì)值的基礎(chǔ)上由大到小改變C的值進(jìn)行試算，使可行解越來越接近最優(yōu)解。對(duì)于目標(biāo)函

7、數(shù)值離散的情況，不難找到最優(yōu)解。例：裝配線平衡模型。一條裝配線含有一系列的工作站，在最終產(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ù)間

8、的所有優(yōu)先關(guān)系。例有11件任務(wù)（Al2分配到4個(gè)工作站（14）,任務(wù)的優(yōu)先次序如下圖。每件任務(wù)所花費(fèi)的時(shí)間如下表。4=1表示分配，Xk=0表示不分配，ti表示完成各項(xiàng)任務(wù)所需時(shí)間，則目標(biāo)函數(shù)為11minmax二tixik1Mp約束條件（1）：每項(xiàng)任務(wù)只能且必須分配至一個(gè)工作站來做，可以表示為：4工Xik=1,i=1,2,11;k1約束條件（2）:各項(xiàng)任務(wù)間如果有優(yōu)先關(guān)系，則排在前面的任務(wù)i對(duì)應(yīng)的工作站（序號(hào)）應(yīng)當(dāng)小于（或等于）排在后面的任務(wù)j所對(duì)應(yīng)的工作站（序號(hào)），4即對(duì)所有有順序的任務(wù)i<j：工（kxjk-kxik）之0；k=1約束條件（3）:Xik=0或1這是一個(gè)非線性規(guī)劃（目標(biāo)函數(shù)

9、非線性），但可以化為線性規(guī)劃，增加一個(gè)11變量，再增加四個(gè)約束條件:LINGOS序?yàn)椋?#163;toWZ,k=1,2,3,4,目標(biāo)函數(shù)變?yōu)閙inZi1model:!裝配線平衡模型;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/;tsx(task,station):x;!x是派生集合txs的一個(gè)屬性。如果x(i,k)=1,則表示第i個(gè)任務(wù)指派給第k個(gè)工作站完

10、成；endsetsdata:!任務(wù)ABCDEFGHIJK的完成時(shí)間估計(jì)如下；T=4511950151212121289;enddata!當(dāng)任務(wù)超過15個(gè)時(shí)，模型的求解將變得很慢；!每一個(gè)作業(yè)必須指派到一個(gè)工作站，即滿足約束；for(task(i):su(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):sui(station(k):k*x(j,k)-k*x(i,k)>=0);!對(duì)于每一個(gè)工作站來說，其花費(fèi)時(shí)間必須不大于裝配線周期；for(station(k):su(txs(

11、i,k):t(i)*x(i,k)<=cyctime);!目標(biāo)函數(shù)是最小化轉(zhuǎn)配線周期；iin=cyctiie;!指定x(i,j)為0/1變量；for(txs:bin(x);end計(jì)算的部分結(jié)果為Globaloptimalsolutionfoundatiteration:1255Objectivevalue:50.00000VariableValueReducedCostCYCTIME50.000000.000000X(A,1)1.0000000.000000X(A,2)0.0000000.000000X(A,3)0.00000045.00000X(A,4)0.0000000.000000X

12、(B,1)0.0000000.000000X(B,2)0.0000000.000000X(B,3)1.00000011.00000X(B,4)0.0000000.000000X(C,1)0.0000000.000000X(C,2)0.0000000.000000X(C,3)0.0000009.000000X(C,4)1.0000000.000000X(D,1)0.0000000.000000X(D,2)1.0000000.000000X(D,3)0.00000050.00000X(D,4)0.0000000.000000X(E,1)0.0000000.000000X(E,2)0.0000000

13、.000000X(E,3)1.00000015.00000X(E,4)0.0000000.000000X(F,1)0.0000000.000000X(F,2)0.0000000.000000X(F,3)0.00000012.00000X(F,4)1.0000000.000000X(G,1)0.0000000.000000X(G,2)0.0000000.000000X(G,3)0.00000012.00000X(G,4)1.0000000.000000X(H,1)0.0000000.000000X(H,2)0.0000000.000000X(H,3)1.00000012.00000X(H,4)0

14、.0000000.000000X(I,1)0.0000000.000000X(I,2)0.0000000.000000X(I,3)1.00000012.00000X(I,4)0.0000000.000000X(J,1)0.0000000.000000X(J,2)0.0000000.000000X(J,3)0.0000008.000000X(J,4)1.0000000.000000X(K,1)0.0000000.000000X(K,2)0.0000000.000000X(K,3)0.0000009.000000X(K,4)1.0000000.000000例：工件的安裝與排序問題。某設(shè)備由24個(gè)工

15、件組成，安裝時(shí)需要按工藝要求重新排序。I .設(shè)備的24個(gè)工件均勻分布在等分成六個(gè)扇形區(qū)域的一圓盤的邊緣上，放在每個(gè)扇形區(qū)域的4個(gè)工件總重量與相鄰區(qū)域的4個(gè)工件總重量之差不允許超過一定值。II .工件的排序不僅要對(duì)重量差有一定的要求，還要滿足體積的要求，即兩相鄰工件的體積差應(yīng)盡量大，使得相鄰工件體積差不小于一定值。問題1:按重量排序算法；問題2:按重量和體積排序算法；請(qǐng)按下表中的工件數(shù)據(jù)（重量單位：g,體積單位：cm3）進(jìn)行實(shí)時(shí)計(jì)算表工件的重量和體積數(shù)據(jù)序號(hào)12345678910重量348352347349347.5347330329329327.5體積101.5102105105.510610

16、49498100.598.5序號(hào)11121314151617181920重量329331.5348.5347346.5348347.5348333330體積9899104.5105107.5104.5104104.59797序號(hào)21222324重量332.5331.5331.5332體積999896.594.5解：對(duì)問題1和2分別求解。(1)對(duì)問題1,僅考慮重量進(jìn)行排序。用i=1,2,，24表示24個(gè)工件，W表示各工件的重量，j=1,2,，6表示圓盤上的6個(gè)扇區(qū)，Dj表示各扇區(qū)上4個(gè)工件的總重量，Xj是0-1型決策變量，表示工件i是否放在扇區(qū)j上，Xj=1表示放，Xj=0表示不放。每個(gè)工件必須

17、且只能放到一個(gè)位置上，每個(gè)位置放一個(gè)且僅放一個(gè)工件，每個(gè)扇區(qū)放4個(gè)工件，重量之和為Dj。目標(biāo)函數(shù)是：相鄰扇區(qū)上的Dj之差的(絕對(duì)值)最大值達(dá)到最小，建立0-1規(guī)劃模型如下：minmax|Dkd-Dk|)1 .勺2 24XXij=4,j=1,2,，6i46XXij=1,i=1,2,，24jg24DjWiXj,ji1Xj=0或1=1,2,6D7=D1模型中的D7是虛擬的,D7=Di使得1-6-1扇區(qū)構(gòu)成圓盤，引入D7的目的只是使目標(biāo)函數(shù)的表達(dá)式簡(jiǎn)潔該0-1規(guī)劃模型的目標(biāo)函數(shù)是相鄰扇區(qū)上的Dj之差（絕對(duì)值）的最大值達(dá)到最小，屬于最大最小化模型。按照前面所述把規(guī)劃模型轉(zhuǎn)化為混合組的步驟，去掉目標(biāo)函數(shù)，

18、增加約束條件:|Dj.i-Dj|MC,j=1,2,6保留原來的約束條件，并令C為某個(gè)常數(shù)，原規(guī)劃就轉(zhuǎn)化成了一個(gè)包含150個(gè)變量，36個(gè)等式約束，6個(gè)不等式約束的非線性混合組。由于24個(gè)工件的重量數(shù)據(jù)多數(shù)為整數(shù)，部分有小數(shù)，小數(shù)的最小計(jì)數(shù)單位為0.5,所以相鄰扇區(qū)重量之差的基本計(jì)數(shù)單位是0.5,即|Dj41-Dj|的可能取值是離散的。令®0,0.5,1,1.5,2,中的具體值（C值越小越好）。用LING魏程求解，不難求得當(dāng)C=0.5時(shí)有可行解，因C=0寸無可行解，故C=0.5時(shí)的可行解就是最優(yōu)解。用第一組工件的重量數(shù)據(jù)，編寫LINGO程序如下：model:sets:gj/1.24/:w

19、;shq/1.6/:d;bl（gj,shq）:x;endsetsdata:w=348352347349347.5347330329329327.5329331.5348.5347346.5348347.5348333330332.5331.5331.5332;enddatafor(bl:bin(x);c=0.5;!常數(shù)C可以設(shè)定不同的值試一試for(gj(i):sum(shq(j):x(i,j)=1);for(shq(j):sum(gj(i):x(i,j)=4);for(shq(j):d(j)=sum(gj(i):w(i)*x(i,j);for(shq(j)|j#lt#6:d(j+1)-d(j

20、)<=c);for(shq(j)|j#lt#6:d(j+1)-d(j)>=-c);d(1)-d(6)<=c;d(1)-d(6)>=-c;end運(yùn)行結(jié)果如下：Feasiblesolutionfoundatiteration:15994VariableValueC0.5000000W(1)348.0000W(2)352.0000W(3)347.0000W(4)349.0000W(5)347.5000W(6)347.0000W(7)330.0000W(8)329.0000W(9)329.0000W(10)327.5000W(11)329.0000W(12)331.5000W(

21、13)348.5000W(14)347.0000W(15)346.5000W(16)348.0000W(17)347.5000W(18)348.0000W(19)333.0000W(20)330.0000W(21)332.5000W(22)331.5000W(23)331.5000W(24)332.0000D(1)1357.000D(2)1356.500D(3)1357.000D(4)1357.500D(5)1357.000D(6)1357.500X(1,1)0.000000X(1,2)1.000000X(1,3)0.000000X(1,4)0.000000X(1,5)0.000000X(1,

22、6)0.000000X(2,1)0.000000X(2,2)0.000000X(2,3)0.000000X(2,4)1.000000X(2,5)0.000000X(2,6)0.000000X(3,1)0.000000X(3,2)0.000000X(3,3)0.000000X(3,4)0.000000X(3,5)1.000000X(3,6)0.000000X(4,1)0.000000X(4,2)0.000000X(4,3)1.000000X(4,4)0.000000X(4,5)0.000000X(4,6)0.000000X(5,1)0.000000X(5,2)0.000000X(5,3)1.00

23、0000X(5,4)0.000000X(5,5)0.000000X(5,6)0.000000X(6,1)0.000000X(6,2)1.000000X(6,3)0.000000X(6,4)0.000000X(6,5)0.000000X(6,6)0.000000X(7,1)0.000000X(7,2)1.000000X(7,3)0.000000X(7,4)0.000000X(7,5)0.000000X(7,6)X(8,1)X(8,2)X(8,3)X(8,4)X(8,5)X(8,6)X(9,1)X(9,2)X(9,3)X(9,4)X(9,5)X(9,6)X(10,1)X(10,2)X(10,3)X

24、(10,4)X(10,5)X(10,6)X(11,1)X(11,2)X(11,3)X(11,4)X(11,5)X(11,6)X(12,1)X(12,2)X(12,3)X(12,4)X(12,5)X(12,6)X(13,1)X(13,2)X(13,3)X(13,4)X(13,5)X(13,6)X(14,1)X(14,2)X(14,3)X(14,4)X(14,5)X(14,6)0.0000000.0000000.0000001.0000000.0000000.0000000.0000001.0000000.0000000.0000000.0000000.0000000.0000000.000000

25、0.0000000.0000001.0000000.0000000.0000000.0000000.0000000.0000000.0000001.0000000.0000000.0000001.0000000.0000000.0000000.0000000.0000001.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000000.0000001.000000X(15,2)0.000000X(15,3)0.000000X(15,4)0.000000X(15,5)0.000000X(15,6)1

26、.000000X(16,1)0.000000X(16,2)0.000000X(16,3)0.000000X(16,4)0.000000X(16,5)1.000000X(16,6)0.000000X(17,1)1.000000X(17,2)0.000000X(17,3)0.000000X(17,4)0.000000X(17,5)0.000000X(17,6)0.000000X(18,1)0.000000X(18,2)0.000000X(18,3)0.000000X(18,4)1.000000X(18,5)0.000000X(18,6)0.000000X(19,1)0.000000X(19,2)0

27、.000000X(19,3)0.000000X(19,4)0.000000X(19,5)1.000000X(19,6)0.000000X(20,1)0.000000X(20,2)0.000000X(20,3)0.000000X(20,4)1.000000X(20,5)0.000000X(20,6)0.000000X(21,1)0.000000X(21,2)0.000000X(21,3)0.000000X(21,4)0.000000X(21,5)0.000000X(21,6)1.000000X(22,1)0.000000X(22,2)0.000000X(22,3)0.000000X(22,4)0.000000X(22,5)0.000000X(22,6)1.000000X(23,1)0.000000X(23,2)0.000000X(23,3)1.000000X(23,4)0.000000X(23,5)0.000000X(23,6)0