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)重，且，然后把作為新的目標(biāo)函數(shù)（其中是原來(lái)的個(gè)目標(biāo)）。3指數(shù)加權(quán)乘積法設(shè)是原來(lái)的個(gè)目標(biāo)，令其中為指數(shù)權(quán)重，把作為新的目標(biāo)函數(shù)。4

2、理想點(diǎn)法先分別求出個(gè)單目標(biāo)規(guī)劃的最優(yōu)解，令然后把它作為新的目標(biāo)函數(shù)。5分層序列法將所有個(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)求和法、指數(shù)加權(quán)乘積法和理想點(diǎn)法通常只能用于兩個(gè)目標(biāo)的單位（量綱）相同的情況，如果兩個(gè)目標(biāo)是不同的物理量，它們的量綱不相同，數(shù)量級(jí)相差很大，則將它們相加或比較是不合適的。二、最大最小化模型在一些實(shí)際問題

3、中，決策者所期望的目標(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ù)可寫成或 式中是決策變量。模型的約束條件可以包含線性、非線性的等式和不等式約束。這一模型的求解可視具體情況采用適當(dāng)?shù)姆椒āＨ?、用LINGO求解多目標(biāo)規(guī)劃和最大最小化模型1解多目標(biāo)規(guī)劃用LINGO求解多目標(biāo)規(guī)劃的基本方法是先確定一個(gè)目標(biāo)函數(shù)，求出它的最優(yōu)解，然后把此最優(yōu)值作為約束條件，

4、求其他目標(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)樽兞慷?，需要很長(zhǎng)運(yùn)算時(shí)間才能算出結(jié)果，如果設(shè)定一個(gè)期望的目標(biāo)值，把目標(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解最大最小化問題第一步，先把原來(lái)較復(fù)雜的目標(biāo)函數(shù)式改寫為一個(gè)簡(jiǎn)單的目

5、標(biāo)函數(shù) 以及個(gè)約束條件： 其他原有的約束條件不變，改寫后仍然是一個(gè)規(guī)劃，只是增加了個(gè)約束條件，目標(biāo)函數(shù)的形式較為簡(jiǎn)單。如果能用LINGO求出它的解，則問題已經(jīng)解決，如果求解困難，可轉(zhuǎn)入下一步。第二步，取消目標(biāo)函數(shù)，保留上一步由目標(biāo)函數(shù)改成的個(gè)約束條件和所有原來(lái)的約束條件，預(yù)設(shè)值為某個(gè)常數(shù)，此時(shí)原規(guī)劃模型不再是規(guī)劃，它僅僅包含等式和不等式，沒有目標(biāo)函數(shù)，是許多約束條件的組合，可以稱它為“混合組”。求該混合組的解，其實(shí)質(zhì)是求滿足所有約束條件并且使目標(biāo)函數(shù)等于給定值的一組決策變量的值，求出來(lái)的結(jié)果是可行解，它未必是最優(yōu)解。在存在可行解的前提下，使目標(biāo)函數(shù)值小的可行解優(yōu)于使目標(biāo)函數(shù)值大的可行解，使目標(biāo)

6、函數(shù)值越小的可行解越接近最優(yōu)解。第三步，對(duì)具體問題作出分析，對(duì)目標(biāo)函數(shù)可能達(dá)到的最小值（即C的最小值）作適當(dāng)估計(jì)，然后在此估計(jì)值的基礎(chǔ)上由大到小改變C的值進(jìn)行試算，使可行解越來(lái)越接近最優(yōu)解。對(duì)于目標(biāo)函數(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ù)的

7、工作站。問題會(huì)因?yàn)楸姸嗳蝿?wù)間存在優(yōu)先關(guān)系而變得更復(fù)雜，任務(wù)的分配必須服從這種優(yōu)先關(guān)系。這個(gè)模型的目標(biāo)是最小化裝配線周期。有2類約束： 要保證每件任務(wù)只能也必須分配至一個(gè)工作站來(lái)加工； 要保證滿足任務(wù)間的所有優(yōu)先關(guān)系。例 有11件任務(wù)（AK）分配到4個(gè)工作站（14），任務(wù)的優(yōu)先次序如下圖。每件任務(wù)所花費(fèi)的時(shí)間如下表。(A)(B)(C)(F)(G)(K)(J)(I)(H)(E)(D)任務(wù)ABCDEFGHIJK時(shí)間4511950151212121289解：用變量表示任務(wù)分配給工作站的情況，表示分配，表示不分配，表示完成各項(xiàng)任務(wù)所需時(shí)間，則目標(biāo)函數(shù)為約束條件（1）：每項(xiàng)任務(wù)只能且必須分配至一個(gè)工作站來(lái)

8、做，可以表示為：；約束條件（2）：各項(xiàng)任務(wù)間如果有優(yōu)先關(guān)系，則排在前面的任務(wù)對(duì)應(yīng)的工作站（序號(hào)）應(yīng)當(dāng)小于（或等于）排在后面的任務(wù)所對(duì)應(yīng)的工作站（序號(hào)），即對(duì)所有有順序的任務(wù)：；約束條件（3）：。這是一個(gè)非線性規(guī)劃（目標(biāo)函數(shù)非線性），但可以化為線性規(guī)劃，增加一個(gè)變量，再增加四個(gè)約束條件：，目標(biāo)函數(shù)變?yōu)椤INGO程序?yàn)椋簃odel: !裝配線平衡模型;sets: !任務(wù)集合，有一個(gè)完成時(shí)間屬性t; task/ A B C D E F G H I J K/:t; !任務(wù)之間的優(yōu)先關(guān)系集合（A 必須完成才能開始B，等等）; pred(task,task)/ A,B B,C C,F C,G F,J G

9、,J J,K D,E E,H E,I H,J I,J /; ! 工作站集合; station/1.4/; tsx(task, station):x; ! x是派生集合txs的一個(gè)屬性。如果x(i，k）1，則表示第i個(gè)任務(wù) 指派給第k個(gè)工作站完成;endsetsdata: !任務(wù)A B C D E F G H I J K的完成時(shí)間估計(jì)如下; T = 45 11 9 50 15 12 12 12 12 8 9;enddata ! 當(dāng)任務(wù)超過15個(gè)時(shí)，模型的求解將變得很慢; !每一個(gè)作業(yè)必須指派到一個(gè)工作站，即滿足約束; for(task(i): sum(station(k):x(i,k) = 1)

10、; !對(duì)于每一個(gè)存在優(yōu)先關(guān)系的作業(yè)對(duì)來(lái)說(shuō)，前者對(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è)工作站來(lái)說(shuō)，其花費(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é)果為 Global optimal solution found at iterati

11、on: 1255 Objective value: 50.00000 Variable Value Reduced Cost CYCTIME 50.00000 0.000000 X( A, 1) 1.000000 0.000000 X( A, 2) 0.000000 0.000000 X( A, 3) 0.000000 45.00000 X( A, 4) 0.000000 0.000000 X( B, 1) 0.000000 0.000000 X( B, 2) 0.000000 0.000000 X( B, 3) 1.000000 11.00000 X( B, 4) 0.000000 0.00

12、0000 X( C, 1) 0.000000 0.000000 X( C, 2) 0.000000 0.000000 X( C, 3) 0.000000 9.000000 X( C, 4) 1.000000 0.000000 X( D, 1) 0.000000 0.000000 X( D, 2) 1.000000 0.000000 X( D, 3) 0.000000 50.00000 X( D, 4) 0.000000 0.000000 X( E, 1) 0.000000 0.000000 X( E, 2) 0.000000 0.000000 X( E, 3) 1.000000 15.0000

13、0 X( E, 4) 0.000000 0.000000 X( F, 1) 0.000000 0.000000 X( F, 2) 0.000000 0.000000 X( F, 3) 0.000000 12.00000 X( F, 4) 1.000000 0.000000 X( G, 1) 0.000000 0.000000 X( G, 2) 0.000000 0.000000 X( G, 3) 0.000000 12.00000 X( G, 4) 1.000000 0.000000 X( H, 1) 0.000000 0.000000 X( H, 2) 0.000000 0.000000 X

14、( H, 3) 1.000000 12.00000 X( H, 4) 0.000000 0.000000 X( I, 1) 0.000000 0.000000 X( I, 2) 0.000000 0.000000 X( I, 3) 1.000000 12.00000 X( I, 4) 0.000000 0.000000 X( J, 1) 0.000000 0.000000 X( J, 2) 0.000000 0.000000 X( J, 3) 0.000000 8.000000 X( J, 4) 1.000000 0.000000 X( K, 1) 0.000000 0.000000 X( K

15、, 2) 0.000000 0.000000 X( K, 3) 0.000000 9.000000 X( K, 4) 1.000000 0.000000例：工件的安裝與排序問題。某設(shè)備由24個(gè)工件組成，安裝時(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，體積單位：

16、cm3）進(jìn)行實(shí)時(shí)計(jì)算。表 工件的重量和體積數(shù)據(jù)序號(hào)12345678910重量348352347349347.5347330329329327.5體積101.5102105105.51061049498100.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)行排序。用表示24個(gè)工件，表示各工件的重量

17、，表示圓盤上的6個(gè)扇區(qū)，表示各扇區(qū)上4個(gè)工件的總重量，是0-1型決策變量，表示工件是否放在扇區(qū)上，表示放，表示不放。每個(gè)工件必須且只能放到一個(gè)位置上，每個(gè)位置放一個(gè)且僅放一個(gè)工件，每個(gè)扇區(qū)放4個(gè)工件，重量之和為。目標(biāo)函數(shù)是：相鄰扇區(qū)上的之差的（絕對(duì)值）最大值達(dá)到最小，建立0-1規(guī)劃模型如下：模型中的是虛擬的，使得1-6-1扇區(qū)構(gòu)成圓盤，引入的目的只是使目標(biāo)函數(shù)的表達(dá)式簡(jiǎn)潔。該0-1規(guī)劃模型的目標(biāo)函數(shù)是相鄰扇區(qū)上的之差（絕對(duì)值）的最大值達(dá)到最小，屬于最大最小化模型。按照前面所述把規(guī)劃模型轉(zhuǎn)化為混合組的步驟，去掉目標(biāo)函數(shù)，增加約束條件：保留原來(lái)的約束條件，并令C為某個(gè)常數(shù)，原規(guī)劃就轉(zhuǎn)化成了一個(gè)包含

18、150個(gè)變量，36個(gè)等式約束，6個(gè)不等式約束的非線性混合組。由于24個(gè)工件的重量數(shù)據(jù)多數(shù)為整數(shù)，部分有小數(shù)，小數(shù)的最小計(jì)數(shù)單位為0.5，所以相鄰扇區(qū)重量之差的基本計(jì)數(shù)單位是0.5，即的可能取值是離散的。令C取0，0.5，1，1.5，2，中的具體值（C值越小越好）。用LINGO編程求解，不難求得當(dāng)C=0.5時(shí)有可行解，因C=0時(shí)無(wú)可行解，故C=0.5時(shí)的可行解就是最優(yōu)解。用第一組工件的重量數(shù)據(jù)，編寫LINGO程序如下：model: sets: gj/1.24/:w; shq/1.6/:d; bl(gj,shq):x; endsets data: w=348 352 347 349 347.5 3

19、47 330 329 329 327.5 329 331.5 348.5 347 346.5 348 347.5 348 333 330 332.5 331.5 331.5 332; enddata for(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)=-c); d(1)-d(6)=-c;end運(yùn)行結(jié)果如下：

20、Feasible solution found at iteration: 15994 Variable Value C 0.5000000 W( 1) 348.0000 W( 2) 352.0000 W( 3) 347.0000 W( 4) 349.0000 W( 5) 347.5000 W( 6) 347.0000 W( 7) 330.0000 W( 8) 329.0000 W( 9) 329.0000 W( 10) 327.5000 W( 11) 329.0000 W( 12) 331.5000 W( 13) 348.5000 W( 14) 347.0000 W( 15) 346.500

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

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

23、, 3) 1.000000 X( 4, 4) 0.000000 X( 4, 5) 0.000000 X( 4, 6) 0.000000 X( 5, 1) 0.000000 X( 5, 2) 0.000000 X( 5, 3) 1.000000 X( 5, 4) 0.000000 X( 5, 5) 0.000000 X( 5, 6) 0.000000 X( 6, 1) 0.000000 X( 6, 2) 1.000000 X( 6, 3) 0.000000 X( 6, 4) 0.000000 X( 6, 5) 0.000000 X( 6, 6) 0.000000 X( 7, 1) 0.00000

24、0 X( 7, 2) 1.000000 X( 7, 3) 0.000000 X( 7, 4) 0.000000 X( 7, 5) 0.000000 X( 7, 6) 0.000000 X( 8, 1) 0.000000 X( 8, 2) 0.000000 X( 8, 3) 1.000000 X( 8, 4) 0.000000 X( 8, 5) 0.000000 X( 8, 6) 0.000000 X( 9, 1) 1.000000 X( 9, 2) 0.000000 X( 9, 3) 0.000000 X( 9, 4) 0.000000 X( 9, 5) 0.000000 X( 9, 6) 0

25、.000000 X( 10, 1) 0.000000 X( 10, 2) 0.000000 X( 10, 3) 0.000000 X( 10, 4) 1.000000 X( 10, 5) 0.000000 X( 10, 6) 0.000000 X( 11, 1) 0.000000 X( 11, 2) 0.000000 X( 11, 3) 0.000000 X( 11, 4) 0.000000 X( 11, 5) 1.000000 X( 11, 6) 0.000000 X( 12, 1) 0.000000 X( 12, 2) 1.000000 X( 12, 3) 0.000000 X( 12,

26、4) 0.000000 X( 12, 5) 0.000000 X( 12, 6) 0.000000 X( 13, 1) 1.000000 X( 13, 2) 0.000000 X( 13, 3) 0.000000 X( 13, 4) 0.000000 X( 13, 5) 0.000000 X( 13, 6) 0.000000 X( 14, 1) 0.000000 X( 14, 2) 0.000000 X( 14, 3) 0.000000 X( 14, 4) 0.000000 X( 14, 5) 0.000000 X( 14, 6) 1.000000 X( 15, 1) 0.000000 X( 15, 2) 0.000000 X( 15, 3) 0.000000 X( 15, 4) 0.000000 X