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

馬贊甫　劉妍珺

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

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

中圖分類號(hào)F224-3 文獻(xiàn)標(biāo)識(shí)碼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引言

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

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

2雙目標(biāo)規(guī)劃相關(guān)概念

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

min x∈Xθ1x，

min x∈Xθ2x.（1）

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

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

θ1x≤θ1xp，

θ2x≤θ2xp.

且其中至少有一個(gè)為嚴(yán)格不等式.

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

θ1x<θ1xw，

θ2x<θ2xw.

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

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

與多目標(biāo)規(guī)劃問題的帕累托解與弱帕累托解相對(duì)應(yīng)，可分別定義其像集中的帕累托點(diǎn)與弱帕累托點(diǎn).

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

θ1≤θp1，

θ2≤θp2.

其中至少存在一個(gè)嚴(yán)格不等式.

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

θ1<θw1，

θ2<θw2.

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

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

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

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

min θ2x，

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

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

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

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

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

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

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

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

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

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

反之，若λθ1<0，此時(shí)

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

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

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

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

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

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

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

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

3步驟與示例

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

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

4 經(jīng)濟(jì)學(xué)應(yīng)用

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

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

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

5 結(jié)論

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

[9]魏權(quán)齡. 經(jīng)濟(jì)與管理中的數(shù)學(xué)規(guī)劃[M]. 北京： 中國人民大學(xué)出版社， 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]林銼云， 董加禮. 多目標(biāo)優(yōu)化的方法與理論[M]. 長春： 吉林教育出版社， 1992.

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