多目標規劃的LINGO求解法

吳有平，劉 杰，何 杰

（1.湖南工業大學 土木工程學院，湖南 株洲 412007；2.湖南省建筑工程集團總公司，湖南 長沙 410004）

0 引言

多目標規劃（multiple objectives programming）是數學規劃的一個分支，它研究多個目標函數在給定區域上的最優化問題，又稱多目標最優化。19世紀末法國經濟學家V.Pareto[1]最早研究了不可比較目標的優化問題，之后J.V.Neumann等人[2]做了較深入的研究。多目標規劃的研究越來越受到人們的重視，但至今有些理論問題尚在探討之中，其求解方法也在不斷改進。

求解多目標規劃問題的方法主要有2類：一是化多為少的方法，即把多目標化為較容易求解的單目標或雙目標，如主要目標法、線性加權法、平方和加權法、理想點法等。二是分層序列法，即把目標按其重要性給出一個序列，每次都在前一目標的最優解集內求下一個目標的最優解，直到求出共同的最優解。除了上述2類外，還有修正單純形法和層次分析法。層次分析法，由T.L.Saaty[3]于20世紀70年代提出，是一種定性與定量相結合的多目標決策與分析方法，對于目標結構復雜且缺乏必要數據的情況較實用。

LINGO（linear interactive and general optimizer）是美國LINDO系統公司開發的一套專門用于求解最優化問題的軟件包。LINGO也是一種最優化問題的建模語言，有許多常用的函數供使用者建模時調用，還提供了與其它數據文件的接口，易于方便地輸入、求解和分析大規模最優化問題。本文采用LINGO軟件（9.0版）求解多目標規劃轉化后的單目標規劃問題。

1 模型的一般表達式

求x=(x1,x2,…,xn)，使模型的理想目標達到極大或極小，同時滿足模型的現實目標和硬約束的要求，其數學表達式為：

理想目標

現實目標和硬約束

式（1）～（3）中：r =0,1,…，是極大化理想目標個數；

s=0,1,…，是極小化理想目標個數；

t=0,1,…，是現實目標和剛性約束個數；

*表示<，=或>。

在某些情況下，對決策變量的非負約束（4）可能不滿足，即存在決策變量取負值的情況[4]。

對每個目標函數確定一個希望達到的期望值就是理想目標，由于受各種條件的限制，這些目標值往往不能全部都達到，現實中要達到的數值b就是現實目標。約束跟現實目標的表達形式相同，但現實目標是彈性的，而約束是絕對的。因此，當一個現實目標必須滿足時，就稱它為硬約束。

2 建立LINGO模型的步驟

1）選定設計變量。多目標規劃中，要求確定的未知量可用一組基本參數來表示，這些基本參數可以是常量也可以是變量。變量的選取是在求解模型過程中不斷優化變更的，因此也稱為設計變量，可用一個向量x=(x1,x2,…,xn)表示。

2）確立目標函數。理想目標由決策變量的數學函數（目標函數）表達，目標函數表示決策者的某種愿望，如最大利潤或最小成本等，其表達式可能是線性的也可能是非線性的，用max f(x)或min f(x)表示。現實目標就是理想目標和某一指標值相配合（也就是配上右端項），構成的決策變量的數學函數，稱為現實目標，用g(x)=b，g(x)b表示。

3）建立約束條件。約束跟現實目標的表達形式相似，只是在求解模型時必須滿足其條件。LINGO優化軟件的不同版本對約束個數有不同的限定，例如：工業版本最大約束數為16 000，Demo（demonstration）版本最大約束數為150。

4）數學模型。就是對決策問題用數學表達式來描述。用LINGO軟件求解多目標規劃時，理想目標只能有1個，其他的理想目標需要根據目標滿足的優先級別轉換成現實目標或約束。形式如下：

3 應用舉例

例1 用3種不同的原液M1，M2，M3配制成3種飲料D1，D2，D3。已知每天有1 500 L的M1，每升6.00元；有2 100 L的M2，每升4.50元；有950 L的M3，每升3.00元。已知配方如下：D1由不到10%的M2和超過50%的M1配成，每升售價6.00元；D2由不到60%的M3和超過10%的M2配成，每升售價5.50元；D3由不到50%的M3和超過50%的M2配成，每升售價5.00元。首先要保證產品質量，其次是要求每天生產2 000 L的D1。怎樣安排生產才能使利潤最大[5]。

解 1）設計變量。根據已知條件，需要決策的是生產D1, D2, D3的量及其配方。令xij表示原料Mi生產產品Dj時的用量。

2）確立目標函數。由條件可知，理想目標是在現有原料的情況下安排3種飲料的生產，使其獲得最大利潤，即理想目標。由M1生產D1其獲利為0（6-6）元，生產D2獲利為-0.5（5.5-6.0）元，生產D3獲利為-1（5.0-6.0）元，M2和M3為原料生產的各種飲料獲利分別為1.5, 1, 0.5元和3, 2.5, 2元。即

其他目標根據實際情況擬定，如要保證品質，則要求嚴格按配方生產，即：

3）建立約束條件。滿足每天生產2 000 L的D1飲料，這是必須滿足的條件。原料的總量是有限的，即：

x11+x21+x31=2 000 ；

4）數學模型。將上述目標函數和約束條件綜合起來，即

5）LINGO程序。LINGO源程序如下：

在LINGO軟件中，系統默認變量大于等于零，編程時可以省略。

程序運行結果：

從運行結果可知，1 000 L的M1, 200 L的M2和800 L的M3用于生產D1飲料；1 900 L的M2和150 L的M3用于生產D2飲料；D3不安排生產；最大獲利為4 975元。而文獻[6]的結果為4708.3元，且D1飲料未達到2 000 L的目標。結果較文獻[6]采用優先乘子模型LINDO解法滿意。

例2 一作坊生產2種產品，產品A每單位產品凈獲利潤10元，產品B每單位產品凈獲利潤8元；A產品每單位產品需占用機器3 h，B產品為2 h，公司每周共有機器時數120 h，允許適當加班，但加班生產的各單位產品利潤均降低1元。根據合同，每周2種產品各需提供30單位，怎樣安排生產才能使利潤最大[5]。

解 1）設計變量。根據已知條件，需要決策的是生產A, B產品的設計安排。令：

x1為產品A在正常上班時間內每周的產量；

x2為產品A在加班時間內每周的產量；

x3為產品B在正常上班時間內每周的產量；

x4為產品B在加班時間內每周的產量。

2）確立目標函數。由條件可知，理想目標是在現有的機器時間或適當的加班情況下，獲得最大利潤，即

其他目標根據實際情況擬定，如在有效機器時間120 h內首先滿足合同提供A, B各30個單位；其次加班時數應盡量減少，假定每周加班不超過20 h；最后利潤要求每周至少為800元，等。用數學函數表示為：

3）建立約束條件。根據合同，每周2種產品各需提供30單位，這是必須滿足的條件，即：

4）數學模型。將上述目標函數和約束條件綜合起來，即

5）LINGO程序。LINGO源程序如下：

運行時提示數據溢出，把現實目標減少2個，即把加班不超過20 h和理想利潤大于800元去掉，得到如下LINGO源程序：

LINGO運行結果：

從上述計算結果可知，在正常生產時間內生產20單位A和30單位B，再安排加班時間生產10單位A，能獲得530元最大利潤。生產10單位A需要30小時，故最初的假設不滿足，而且利潤也不是最初的要求的800元，故現實目標不一定能滿足，是彈性約束。結果與文獻[7]中應用LINDO軟件根據傳統模型計算結果相同，但此方法及程序簡單。

4 結語

本文應用LINGO軟件，采用減少現實目標的方法求解多目標規劃問題。由2個實例的求解過程可知，其過程簡單，結果也優于用傳統方法所得結果[6-7]。另外，在有多個理想目標時，也可將其中的n-1個轉換成現實目標或約束，再用LINGO求解。該方法對其他規劃問題的求解有一定的參考價值。

[1]Pareto V.Manual of Political Economy[M].New Jersey：Scholars Book Shelf，1971：92-98.

[2]Neumann J V，Morgenstern O.Theory of Games and Economic Behavior[M].London：Princeton University Press，1953：271-272.

[3]Saaty T L.The Analytic Hierarchy Process[M].New York：McGraw-Hill International，1980：241-243.

[4]Ignizio J P.Linear Programming in Single-Multiple-Objective Systems[M].New Jersey：Prentice-Hall，1982：37.

[5]盧開澄.單目標、多目標與整數規劃[M].北京：清華大學出版社，1999：242-244.Lu Kaicheng.Single & Multiple Objectives and Integer Programming[M].Beijing：Tsinghua University Press，1999：242-244.

[6]洪 文.利用LINDO求解目標規劃[J].安徽大學學報：自然科學版，2001，25(2) ：1-5.Hong Wen.Solve Object Programming with LINDO[J].Journal of Anhui University：Natural Science Edition，2001，25(2) ：1-5.

[7]羅罡輝，葉艷妹.多目標規劃的LINDO求解方法[J].計算機運用與軟件，2004，21(2) ：108-110.Luo Ganghui，Ye Yanmei.Solve Multi-Objective Goal Programming With LINDO[M].Computer Applications and Software，2004，21(2) ：108-110.