基于LINGO的多目標(biāo)規(guī)劃模型求解

1、基于LINGO的多目標(biāo)規(guī)劃模型求解唐家德（楚雄師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，云南 楚雄 675000）摘要 建立實(shí)際問(wèn)題的多目標(biāo)規(guī)劃數(shù)學(xué)模型并求解是運(yùn)籌學(xué)中常遇到的問(wèn)題,應(yīng)用最優(yōu)化軟件LINGO可以快捷準(zhǔn)確地求出該類(lèi)問(wèn)題的解，本文以實(shí)例的方式介紹了多目標(biāo)規(guī)劃數(shù)學(xué)模型的建立、LINGO求解程序的編寫(xiě)，為實(shí)際工作者解決這類(lèi)優(yōu)化問(wèn)題提供了一種便捷的途徑。關(guān)鍵詞 多目標(biāo)規(guī)劃；LINGO；偏差變量；優(yōu)先級(jí).中圖分類(lèi)號(hào) O221.6 文獻(xiàn)標(biāo)識(shí)碼 AI0 引言多目標(biāo)規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要內(nèi)容,它研究在一定約束條件下多個(gè)目標(biāo)函數(shù)的極值問(wèn)題,與傳統(tǒng)的單目標(biāo)函數(shù)問(wèn)題不同,在多目標(biāo)規(guī)劃問(wèn)題中,通常不存在能使得所有目標(biāo)函

2、數(shù)同時(shí)得到優(yōu)化的最優(yōu)解,往往只需要求出滿意解.求解多目標(biāo)規(guī)劃的方法主要有兩類(lèi)：第一類(lèi)是化多為少的方法,即把多目標(biāo)化為較容易求解的單目標(biāo)問(wèn)題進(jìn)行求解,第二類(lèi)是分級(jí)序列法,即把目標(biāo)按其重要性給出一個(gè)優(yōu)先級(jí),每次在上一優(yōu)先級(jí)目標(biāo)的最優(yōu)解集內(nèi)求下一優(yōu)先目標(biāo)的最優(yōu)解,直到求出共同的最優(yōu)解，本文主要介紹第二種方法。下面我們以一個(gè)實(shí)例來(lái)說(shuō)明多目標(biāo)規(guī)劃的特點(diǎn)、采用分級(jí)序列法求解的步驟和LINGO程序的編寫(xiě)。1 一個(gè)實(shí)例（運(yùn)輸問(wèn)題模型）要把一種產(chǎn)品從產(chǎn)地運(yùn)到客戶處,發(fā)量、需求量及產(chǎn)地到客戶的運(yùn)輸費(fèi)單價(jià)如表1所示.表1 運(yùn)輸費(fèi)用單價(jià)表客戶產(chǎn)地客戶1客戶2客戶3發(fā)量產(chǎn)地1104123000產(chǎn)地281034000需求

3、量200015005000-2 線性規(guī)劃建模求解設(shè)從產(chǎn)地（）到客戶的運(yùn)送量為，單位運(yùn)輸費(fèi)用為，產(chǎn)地的發(fā)量為，客戶的需求量為，則可建立如下的線性規(guī)劃模型： min (1) s.t. (2) (3)使用LINGO軟件求解，發(fā)現(xiàn)無(wú)可行解。無(wú)可行解的原因是客戶總需求量（8500）大于產(chǎn)地的總發(fā)量（7000），客戶需求量無(wú)法滿足。 由于該問(wèn)題是一個(gè)供求不平衡問(wèn)題,總需求量缺少1500個(gè)單位,因此按下列目標(biāo)來(lái)考慮運(yùn)輸方案：第一目標(biāo),客戶1為重要部門(mén),需求量必須全部滿足;第二目標(biāo),滿足其他兩個(gè)客戶至少75%的需要量;第三目標(biāo),使運(yùn)費(fèi)盡量少;第四目標(biāo),從產(chǎn)地2到客戶1的運(yùn)量至少有個(gè)單位. 3 采用分級(jí)序列法對(duì)

4、多目標(biāo)規(guī)劃求解31 確定目標(biāo)的優(yōu)先級(jí)與權(quán)系數(shù) 首先確定目標(biāo)的優(yōu)先級(jí)與權(quán)系數(shù)，目標(biāo)的優(yōu)先分為兩個(gè)層次,第一個(gè)層次是目標(biāo)分成不同的優(yōu)先級(jí),在計(jì)算多目標(biāo)規(guī)劃時(shí),必須先優(yōu)化高優(yōu)先級(jí)的目標(biāo),然后再優(yōu)化低優(yōu)先級(jí)的目標(biāo),通常以表示不同的優(yōu)先級(jí),并規(guī)定,在上述實(shí)例中，有四個(gè)目標(biāo)，按重要性分為第一至第四目標(biāo)，我們分別記這四個(gè)目標(biāo)的優(yōu)先級(jí)為。第二個(gè)層次是目標(biāo)處于同一優(yōu)先級(jí),但兩個(gè)目標(biāo)的權(quán)重不一樣,因此兩目標(biāo)同時(shí)優(yōu)化,用權(quán)系數(shù)的大小來(lái)表示目標(biāo)重要性的差別.32 統(tǒng)一處理目標(biāo)與約束其次將原線性規(guī)劃的目標(biāo)函數(shù)和約束條件都統(tǒng)一視為約束條件，然后將約束分成兩類(lèi)，一類(lèi)是嚴(yán)格要求滿足的，用嚴(yán)格的等式或不等式約束來(lái)處理，例如，上

5、述例子中，對(duì)各產(chǎn)地發(fā)量的約束是要求嚴(yán)格滿足的，這類(lèi)約束稱為剛性約束：(剛性約束)另一類(lèi)約束是可以不嚴(yán)格要求滿足的,稱為柔性約束,對(duì)于柔性約束,我們通過(guò)設(shè)置偏差變量的方法將其轉(zhuǎn)化為等式約束.3.3偏差變量的設(shè)置方法用偏差變量來(lái)表示計(jì)算值與目標(biāo)值之間的差異,若,則令,即為超過(guò)部分的數(shù)量,故稱為正偏差變量;若時(shí),令,即為沒(méi)有達(dá)到部分的數(shù)量,故稱為負(fù)偏差變量.若, 則 在實(shí)際問(wèn)題中,對(duì)于計(jì)算值來(lái)說(shuō),如果希望盡量超過(guò)目標(biāo)值,則極小化負(fù)偏差變量,即;希望盡量不超過(guò),則極小化正偏差變量, 即;希望盡可能地接近,則同時(shí)極小化正、負(fù)偏差變量，即; 在上述實(shí)例中，四個(gè)目標(biāo)可視為四個(gè)柔性約束，分別寫(xiě)為：（1） 客戶

6、1為重要部門(mén)需求量必須全部滿足,即：;（2） 滿足客戶2和客戶3至少75%的需要量,即：;（3） 使運(yùn)費(fèi)盡量少,即：（4）從產(chǎn)地到客戶的運(yùn)輸量至少有個(gè)單位,即：;根據(jù)上面的陳述,可以寫(xiě)出相應(yīng)的目標(biāo)函數(shù)為：,其中均為優(yōu)先級(jí).4 LINGO軟件求解將上述內(nèi)容編寫(xiě)為以下LINGO程序：sets: Level/1.4/: P, z, Goal;!定義優(yōu)先級(jí)集合及其屬性; S_Con_Num/1.5/: dplus, dminus; !定義柔性約束集合及正負(fù)偏差變量; Plant /1,2/: e; !定義產(chǎn)地集合及發(fā)量; Customer /1.3/: d; !定義客戶集合及需求量; Routes(P

7、lant, Customer): c, x; !生成產(chǎn)地與客戶的派生集及單位運(yùn)價(jià)和運(yùn)輸量;endsetsdata: P= ? ? ? ? ; !分級(jí)運(yùn)算，等待用戶輸入; Goal= ? ? ? 0; !分級(jí)運(yùn)算，用戶根據(jù)上一級(jí)運(yùn)算結(jié)果輸入; e= 3000 4000; !產(chǎn)地發(fā)量數(shù)據(jù); d= 2000 1500 5000; !客戶需求量數(shù)據(jù); c = 10 4 12 8 10 3; !各產(chǎn)地到各客戶單位運(yùn)價(jià)數(shù)據(jù);enddatamin=sum(Level: P * z); !目標(biāo)函數(shù);z(1) = dminus(1);z(2) = dminus(2)+dminus(3);z(3) = dplus

8、(4);z(4) = dminus(5); !各優(yōu)先級(jí)優(yōu)化的目標(biāo);for(Plant(i): sum(Customer(j): x(i,j) = e(i); !產(chǎn)量約束為剛性約束; x(1,1)+x(2,1)+dminus(1)-dplus(1)=2000; !第一目標(biāo)約束為柔性約束; for(Customer(j)|j#gt#1: sum(Plant(i): x(i,j)+dminus(j)-dplus(j)=0.75*d(j);); !第二目標(biāo)約束;sum(Routes: c*x)+dminus(4)-dplus(4)=33000; !第三目標(biāo)約束; x(2,1)+dminus(5)-dp

9、lus(5)=1000; !第四目標(biāo)約束; for(Level(i)|i #lt# size(Level): bnd(0,z(i),Goal(i);); !人為增加上下界約束;現(xiàn)將上述程序分別執(zhí)行四次,在做第一級(jí)目標(biāo)計(jì)算時(shí),分別輸入;分別輸入,執(zhí)行得到.在做第二級(jí)目標(biāo)運(yùn)算時(shí),分別輸入;分別輸入,執(zhí)行得到.在做第三級(jí)目標(biāo)運(yùn)算時(shí),分別輸入, 分別輸入,執(zhí)行得到.在做第四級(jí)目標(biāo)運(yùn)算時(shí),分別輸入;分別輸入,執(zhí)行得到.通過(guò)四次運(yùn)算我們得到上述問(wèn)題的部分輸出結(jié)果：X( 1, 1) 1750.000 0.000000 X( 1, 2) 1125.000 0.000000 X( 1, 3) 0.000000

10、0.000000 X( 2, 1) 250.0000 0.000000 X( 2, 2) 0.000000 2.142857 X( 2, 3) 3750.000 0.000000根據(jù)結(jié)果我們可以知道從產(chǎn)地運(yùn)往個(gè)客戶的運(yùn)輸量分別為：,從產(chǎn)地運(yùn)往個(gè)客戶的運(yùn)輸量分別為：.此結(jié)果滿足四個(gè)目標(biāo)約束,則此運(yùn)輸方案為滿意解,故最小運(yùn)輸費(fèi)用為: 5 小結(jié) 采用分級(jí)序列法，多目標(biāo)規(guī)劃的一般數(shù)學(xué)表達(dá)式也可以記為： （4）將所有柔性約束（等式或不等式）加上負(fù)偏差變量與正偏差變量的差后變?yōu)榈仁郊s束，如果希望約束保持小于，則極小化正偏差變量，如果希望約束保持大于，則極小化負(fù)偏差變量，如果希望約束保持等于，則極小化正、負(fù)

11、偏差變量之和。采用分級(jí)序列法再結(jié)合LINGO軟件，可以高效準(zhǔn)確地求出多目標(biāo)規(guī)劃問(wèn)題，這種求解方法具有普遍的實(shí)踐意義,適合解決常規(guī)的多目標(biāo)規(guī)劃的數(shù)學(xué)模型.由于多目標(biāo)規(guī)劃還有很多方面的應(yīng)用,如林產(chǎn)品的加工中各種原材料的最佳配比、木材最優(yōu)運(yùn)輸路線的選擇、造林的最佳投資方案選擇、水資源的最優(yōu)配置、撫育采伐的最優(yōu)控制、產(chǎn)品生產(chǎn)的安排、投資方案選擇等,都可以用多目標(biāo)數(shù)學(xué)規(guī)劃的方法加以解決.目前,多目標(biāo)數(shù)學(xué)規(guī)劃的理論,求解方法都處于迅速發(fā)展階段,并且在生產(chǎn)、經(jīng)濟(jì)、科學(xué)、工程等諸多領(lǐng)域中都處于重要的地位,例如設(shè)計(jì)一個(gè)導(dǎo)彈,既要其射程遠(yuǎn),又要耗料少,還要命中率高等,只有對(duì)各因素的指標(biāo)進(jìn)行綜合衡量后,才能做出合理

12、的決策.相信,在不久的將來(lái)多多目標(biāo)規(guī)劃問(wèn)題將會(huì)在實(shí)踐中得到廣泛地應(yīng)用,理論也會(huì)隨之不斷地完善,計(jì)算技術(shù)也會(huì)更為簡(jiǎn)便,在理論與實(shí)踐的結(jié)合上將會(huì)有廣闊的發(fā)展前景.參考文獻(xiàn)：1謝金星,薛毅.優(yōu)化建模與LINGO軟件M.北京：清華大學(xué)出版社,2005.2徐玖平,李軍.多目標(biāo)決策的理論與方法M.北京：清華大學(xué)出版社,2005.3.3徐玖平,胡智能,李軍.運(yùn)籌學(xué)（類(lèi)）M.北京：科學(xué)出版社,2004.4李華.預(yù)測(cè)與決策M(jìn).西安：電子科技大學(xué)出版社,2005.3.1.5王麗穎,趙連麗,趙連忠.多目標(biāo)規(guī)劃模型的應(yīng)用研究J.白城師范學(xué)院學(xué)報(bào),2010,24（6）：7-15. 6劉淋. 多目標(biāo)線性規(guī)劃的若干解法及L

13、ingo實(shí)現(xiàn)J.襄樊職業(yè)技術(shù)學(xué)院報(bào),2011,10（6）：20-22.7 鄭漳華，艾芊，顧承紅，蔣傳文. 考慮環(huán)境因素的分布式發(fā)電多目標(biāo)優(yōu)化配置J. 中國(guó)電機(jī)工程學(xué)報(bào),2009,29（13）：23-29.8 喬辰； 張國(guó)立. 幾何加權(quán)法求解多目標(biāo)規(guī)劃問(wèn)題J. 華北電力大學(xué)學(xué)報(bào)(自然科學(xué)版), 2011,38（6）：107-110.10 劉楊，云美萍，彭國(guó)雄. 應(yīng)急車(chē)輛出行前救援路徑選擇的多目標(biāo)規(guī)劃模型J. 公路交通科技,2009,26（8）：135-139.11 何其超，胡列格，錢(qián)紅波. 基于多目標(biāo)規(guī)劃的低碳銷(xiāo)售物流網(wǎng)絡(luò)規(guī)劃方法J. 系統(tǒng)工程,2013,31（7）：20-22.12劉淋. 多目

14、標(biāo)線性規(guī)劃的若干解法及Lingo實(shí)現(xiàn)J.襄樊職業(yè)技術(shù)學(xué)院報(bào),2011,10（6）：20-22.The Solving of The Multiobjective Programming Based on LINGOTang Jia-de(Department of Mathematics, Chuxiong Normal University, Chuxiong Yunnan 675000 China)Abstract: It is often encountered problems to establish multiobjective programming model and solv

15、ing the in the application of operations research, we can use optimization software LINGO to find out the solution of the problem. In the paper we introduce the methods of establishment the multiobjective programming model and solving by LINGO , it provides a convenient for the actual worker to solve this kind of optim