雙目標規(guī)劃問題的像集與求解

馬贊甫　劉妍珺

摘要經(jīng)濟管理的決策目標往往與成本、收益相關，雙目標規(guī)劃在經(jīng)濟管理中具有廣泛應用.然而，尚缺乏成熟的算法確定雙目標規(guī)劃問題的全部解.給出雙目標規(guī)劃問題像集的一般性確定法，以求其解，為研究目的所在.具體而言，構造一個帶等式約束的單目標規(guī)劃問題，以確定雙目標規(guī)劃問題像集之部分邊界，并借助拉格朗日乘子符號判斷其單調(diào)性，據(jù)此確定原問題的帕累托解與弱帕累托解.這相當于提供了一個求解雙目標規(guī)劃問題的一般性框架.

關鍵詞最優(yōu)化；雙目標規(guī)劃解法；單目標規(guī)劃；像集；弱帕累托解

中圖分類號F224-3 文獻標識碼A

AbstractThe objective of decisionmaking in economic management is often related to cost and benefit. A good case in point is that biobjective programming based on costbenefit analysis is widely used in economic management. However， so far， there is still a lack of mature algorithms to determine the full solution of the Bi objective programming problem. A general method， which was used to get the Pareto solution or weak Pareto solution for double objective optimization problems， was put forward in this research. To be specific， we constructed a single objective programming with equality constrain to determine the frontier of the image set of double objective optimization problems. Furthermore， we could determine the frontier's functional monotonicity using Lagrange multiplier and finally get the Pareto solution or weak Pareto solution. Base on above steps， A general framework was presented to solve double objective programming problem.

Key wordsOptimization， The Method of Solving DoubleObjective Programming， SingleObjective Programming， Image Set， Weak Pareto Solution

1引言

多目標規(guī)劃的解法可區(qū)分為間接算法與直接算法兩種.間接法的一般思路是將多個目標轉(zhuǎn)換為單一目標進行處理，往往只能得到問題的一個解或部分解.如楊軼華、呂顯瑞、劉慶懷等（2006）所指出的，間接法存在顧此失彼之缺點[1].直接法則以同倫法為代表，通過構造同倫映射確定多目標規(guī)劃問題的解，直指多目標規(guī)劃問題本身，可回避間接法之缺點.其中，劉慶懷、林正華（2000）考察采用該算法確定問題的最小弱有效解[2]，而楊軼華、呂顯瑞、劉慶懷等（2006）則采用該算法確定多目標規(guī)劃問題的一個有效解集[1].

考慮到萬事萬物好與壞、收益與成本等雙分類的普遍性，多目標規(guī)劃中的雙目標規(guī)劃具有極為重要的應用價值，常用于企業(yè)管理決策[3-5]、交通設置優(yōu)化[6-7]等現(xiàn)實問題.不失一般性，雙目標規(guī)劃問題的求解也可借助多目標規(guī)劃求解方法.事實上，楊軼華、呂顯瑞、劉慶懷等（2006）考慮了同倫內(nèi)點算法在雙目標規(guī)劃求解中的應用[1]，而曾玉華、彭拯（2010）同樣考慮了雙目標規(guī)劃問題的一種直接算法，即非精確交替方向法[8].下文擬提出雙目標規(guī)劃的一個更具一般性的應用分析框架，從屬于直接法，從問題的像集結構入手，試圖確定問題的全部解.

2雙目標規(guī)劃相關概念

考慮如下一般形式的雙目標規(guī)劃問題：

min x∈Xθ1x，

min x∈Xθ2x.（1）

假設目標函數(shù)θ1x，θ2x都可微.

稱xp∈X為其帕累托解，如果不存在x∈X，使得

θ1x≤θ1xp，

θ2x≤θ2xp.

且其中至少有一個為嚴格不等式.

稱xw∈X為問題（1）的弱帕累托解，如果不存在x∈X，使得下列不等式組成立：

θ1x<θ1xw，

θ2x<θ2xw.

多目標規(guī)劃問題的帕累托解或弱帕累托解其定義依據(jù)是目標函數(shù)值，因此，研究多目標規(guī)劃問題的像集是求解多目標規(guī)劃問題確定其帕累托解與弱帕累托解的最直接手段.特別是，雙目標規(guī)劃問題的像集不僅易于確定，且具有幾何直觀性，是求取雙目標規(guī)劃問題的便利工具.問題（1）的像集定義為

F=θ1x，θ2x|x∈X.（2）

與多目標規(guī)劃問題的帕累托解與弱帕累托解相對應，可分別定義其像集中的帕累托點與弱帕累托點.

稱θp1，θp2∈F為F中的帕累托點，如果不存在θ1，θ2∈F使得

θ1≤θp1，

θ2≤θp2.

其中至少存在一個嚴格不等式.

稱θw1，θw2∈F為F中的弱帕累托點，如果不存在θ1，θ2∈F使得

θ1<θw1，

θ2<θw2.

顯然，如果xp∈X為多目標規(guī)劃問題的帕累托解，則其像θ1xp，θ2xp必為F中的帕累托點，反之亦然.類似地，如果xw∈X為問題的弱帕累托解，則其像θ1xw，θ2xw必為F中的弱帕累托點，反之亦然.基于此，可構造單目標規(guī)劃問題確定雙目標規(guī)劃問題像集的基本特征，以達到確定其帕累托解及與弱帕累托解之目的.

2雙目標規(guī)劃像集的確定

確定像集的方法較多，不過，一般具有問題針對性.比如，單一決策變量事實上可定義雙目標函數(shù)之間的一個參數(shù)方程，可采用消除變量方式確定目標函數(shù)之間的函數(shù)關系.又如，若問題為多目標線性規(guī)劃形式，可采用凸組合方式確定像集[9].針對雙目標規(guī)劃問題，本項研究考察其像集的一般性確定方法.

不論變量x維度如何，雙目標規(guī)劃問題的像集總是二維空間中的點集.因此，可通過探究像集的結構特別是下邊界形式確定雙目標規(guī)劃問題的弱帕累托解.為此，考察如下單目標規(guī)劃問題：

min θ2x，

s.t.θ1x=θ1，x∈X.（3）

其中θ1∈θ1x|x∈X.問題（3）旨在界定多目標規(guī)劃問題像集的下方邊界.該問題為等式約束問題，按照通常的做法，就x∈X，構造拉格朗日函數(shù)

Lx，λ=θ2x+λθ1-θ1x.

問題的一階條件等價于如下方程組：

θ1x=θ1，θ2xx=λθ1xx.

這里θixx為函數(shù)θix的梯度向量，i=1，2.針對給定的參數(shù)θ1，假設存在滿足拉格朗日條件的xθ1與λθ1，其中xθ1∈X為問題（3）的最優(yōu)解，記相應的目標函數(shù)最小值為θ2θ1.

現(xiàn)需要判斷單目標規(guī)劃問題的最優(yōu)解是否為多目標規(guī)劃問題的帕累托解.

若θ2θ1在θ1處可導，且λθ1>0，則根據(jù)包絡定理（Envelope Theorem）有[10]

dθ2θ1dθ1=λθ1>0，

或者說函數(shù)θ2θ1在θ1處單調(diào)遞增，這表明xθ1并非多目標規(guī)劃問題的弱帕累托解.

反之，若λθ1<0，此時

dθ2θ1dθ1=λθ1<0.

表明在xθ1的某領域范圍內(nèi)，兩目標函數(shù)之間存在此消彼長關系，xθ1為多目標規(guī)劃問題的局部帕累托解.除此之外，若λθ1=0，暫不能確定xθ1是否為雙目標規(guī)劃問題的弱帕累托解.

綜上，利用單目標規(guī)劃問題確定多目標規(guī)劃問題的解，主要關注如下兩點：其一，給定參數(shù)θ1一個可能的取值，函數(shù)θ2x能否在方程θ1x=θ1的解集中取到最小值.如果單目標規(guī)劃問題最優(yōu)值負無窮，則滿足θ1x=θ1的可行解滿足帕累托解的定義，是多目標規(guī)劃問題的帕累托解.換言之，即便2θ1在θ1處無定義，也不影響求取雙目標規(guī)劃問題的帕累托解.

其二，該最小值點是否滿足局部弱帕累托性，即相應的拉格朗日乘子符號如何.若乘子為負，則單目標規(guī)劃問題的解是多目標規(guī)劃問題的局部弱帕累托解，否則該解并非弱帕累托解.當然，如果目標函數(shù)滿足凸性，局部弱帕累托解必然是整體弱帕累托解.

進一步地，若就每一個可能的θ1∈θ1x|x∈X都確定了問題（3）的值，則可據(jù)此繪取最小值函數(shù)2θ1的圖像，從而不難確定像集中的帕累托點與弱帕累托點，同時也得到了雙目標規(guī)劃問題的帕累托解與弱帕累托解.

出于求解需要，問題（3）并未完全確定雙目標規(guī)劃問題的像集，僅僅得到其下邊界.我們還可以求解如下最大化問題以確定像集之上邊界：

max θ2xs.t.θ1x=θ1，x∈X.（4）

設問題存在最優(yōu)值，并記為2θ1.于是，在給定目標函數(shù)1取值θ1的情況下，我們確定了目標函數(shù)2的變動范圍，有θ2∈2θ1，2θ1，從而得到雙目標規(guī)劃問題像集的一個大致認識.

3步驟與示例

綜上，為確定雙目標規(guī)劃問題（1）的像集及弱帕累托解集，其基本步驟可細分為如下三步：首先，確定目標函數(shù)θ1x在可行解集X上的值域；其次，針對目標函數(shù)θ1x在其值域中的所有取值θ1，求單目標規(guī)劃問題（3）與（4）的最優(yōu)解，以確定雙目標規(guī)劃問題像集的下邊界與上邊界；最后，根據(jù)問題（3）的拉格朗日乘子符號，判斷可行解是否為雙目標規(guī)劃問題的局部弱帕累托解.當然，視問題不同可將兩個目標函數(shù)的主次關系進行相應調(diào)整，即，也可在給定目標函數(shù)θ2x取值基礎上探討目標函數(shù)θ1x的取值范圍.

第二步要求針對某一目標函數(shù)的所有可能取值去確定另一個目標函數(shù)的最大值與最小值，事實上已將雙目標規(guī)劃問題轉(zhuǎn)化為單目標規(guī)劃問題.在數(shù)值解法之余，有時亦可確定一個目標函數(shù)的最大、最小值相應于另一個目標函數(shù)具體取值的函數(shù)關系式.

4 經(jīng)濟學應用

經(jīng)濟學往往面臨價值取向的二維性.經(jīng)濟人總是權衡成本與收益，就生產(chǎn)者而言，產(chǎn)出最大而投入最小；就消費者而言，效用最大而支付最??；就投資者而言，收益最大而風險最小，等等，都是經(jīng)濟人理所當然的考慮.事實上，經(jīng)濟學研究源于資源的稀缺性，經(jīng)濟決策的核心是優(yōu)化稀缺資源的配置與利用，其中不乏經(jīng)典的雙目標規(guī)劃問題，也采用了類似的處理方式.

比如，微觀經(jīng)濟學中生產(chǎn)函數(shù)與成本函數(shù)的定義.任何生產(chǎn)總是涉及到投入與產(chǎn)出兩類目標，問題的像集表現(xiàn)為生產(chǎn)可能集.具有帕累托特征或弱帕累托特征的生產(chǎn)方式需具備如下條件：給定投入的情況下，獲得最大的產(chǎn)出；或者，在給定產(chǎn)出的情況下，投入成本最小.這兩個條件分別定義了生產(chǎn)函數(shù)與成本函數(shù)，事實上確定了生產(chǎn)可能集的部分邊界.顯然，這一機理與確定像集邊界一致.

又比如，金融經(jīng)濟學中資產(chǎn)組合前沿邊界的確定事實上即等價于雙目標規(guī)劃問題像集的確定，其決策變量為資產(chǎn)組合權重向量，兩個目標函數(shù)分別是資產(chǎn)組合權重的方差函數(shù)與期望收益函數(shù).問題的經(jīng)典處理方式即Harry Markowitz （1952）提出的均值-方差模型[11]采用了雙目標規(guī)劃像集求解方法，即，在給定期望收益的前提下考察方差的最小值，或者，在給定方差的前提下謀求期望收益的最大值.處理結果的表現(xiàn)方式亦然，得到了雙目標規(guī)劃問題像集的上下邊界，也就是資產(chǎn)組合前沿邊界.

5 結論

利用像集探究多目標規(guī)劃問題的帕累托解與弱帕累托解是一種傳統(tǒng)思路，當問題為雙目標規(guī)劃類型時，尤具可行性.從確定雙目標規(guī)劃問題的像集邊界入手，以拉格朗日乘子符號或像集邊界函數(shù)單調(diào)性求取問題的局部弱帕累托解，這提供了雙目標規(guī)劃問題的一個分析框架.必須承認，囿于作者學識，此處僅提出一個分析框架，相關結論并未給出嚴格的數(shù)學證明，不過，該分析框架確實具有較好的應用前景.

參考文獻

[1]楊軼華， 呂顯瑞， 劉慶懷等. 求雙目標凸規(guī)劃問題有效解集的內(nèi)點同倫算法[J]. 吉林大學學報， 2006， 44 （1）： 39-43.

[2]劉慶懷， 林正華. 求解多目標規(guī)劃最小弱有效解的同倫內(nèi)點方法[J]. 應用數(shù)學學報， 2000， 23 （2）： 188-195.

[3]于麗英， 楊雷. 生產(chǎn)計劃的雙目標混合整數(shù)規(guī)劃模型及其求解[J]. 上海交通大學學報， 2001， 35 （7）： 1100-1102.

[4]王兆杰， 高峰， 翟橋柱等. 高耗能企業(yè)關口平衡問題的雙目標規(guī)劃模型[J]. 西安交通大學學報， 2013， 47 （8）： 26-32.

[5]張人千， 張?zhí)m慷. 基于收益-風險雙目標規(guī)劃的隨機能力擴張模型[J]. 系統(tǒng)工程理論與實踐， 2015， 35 （7）： 1678-1688.

[6]杜進有， 謝汶莉. 城市群環(huán)路的雙目標規(guī)劃模型[J]. 西南交通大學學報， 2006， 41 （1）： 102-106.

[7]雋海民， 裴玉龍， 申翔浩. 城市客運交通結構生態(tài)效用雙目標優(yōu)化模型[J]. 公路交通科技， 2012， 29 （7）： 139-143.

[8]曾玉華， 彭拯. 一種求解雙目標規(guī)劃的非精確交替方向法[J]. 運籌學學報， 2010， 14 （4）： 121-128.

[9]魏權齡. 經(jīng)濟與管理中的數(shù)學規(guī)劃[M]. 北京： 中國人民大學出版社， 2011.

[10]Paul Milgrom， Ilya Segal. Envelope Theorem for Arbitrary Choice Sets [J]. Econometrica， 2002， 70 （2）： 583-601.

[11]Harry Markowitz. Portfolio Selection [J]. Journal of Finance， 1952， 7 （1）： 77-91.

[12]林銼云， 董加禮. 多目標優(yōu)化的方法與理論[M]. 長春： 吉林教育出版社， 1992.

[13]胡毓達. 多目標規(guī)劃有效性理論[M]. 上海： 上?？茖W技術出版社， 1994.