線性相依條件下未確知機會約束規劃的解法

李小青,周長銀,王延朝

(山東科技大學信息科學與工程學院,山東青島 266510)

線性相依條件下未確知機會約束規劃的解法

李小青,周長銀,王延朝

(山東科技大學信息科學與工程學院,山東青島 266510)

在未確知數為線性相依條件下,研究了一般線性約束形式的未確知機會約束規劃問題的解法,并給出具體算例說明了該方法的可行性。同時,這種處理問題的思想對建立未確知支持向量機也有很大的現實意義。

未確知有理數;線性相依;可信度;機會約束規劃

0 引言

目前對確定性信息的研究已形成了一套比較完整的理論體系。然而,在實際工作和生活中卻存在著大量的不確定性信息,大體上可以分為隨機信息、模糊信息、灰信息和未確知信息[1]。未確知信息是一種不同于以上三種信息的另一種信息,它最早由中國工程院院士王光遠教授提出[2]。這種信息的不確定性是由于決策者不能完全把握事物的真實狀態和數量關系而造成的純主觀認識上的不確定性。隨著人們對未確知信息的不斷深入研究,目前已初步形成了一套未確知信息理論,并在未確知有理數理論的基礎上構造了未確知機會約束規劃問題。但目前只解決了未確知機會約束規劃中當約束條件為g(x,B)=B-h(x),g(x,B)=h(x)-B這兩種形式的規劃問題的算法[3],筆者要討論的約束條件為更一般的線性形式:g(x,B)=h(x)A-B的未確知機會約束規劃模型。利用線性相依未確知有理數的相關理論,在未確知數A, B滿足線性相依條件下,給出了未確知機會約束規劃的一個解法。

1 未確知數理論

定義1[4]對任意閉區間[a,b],a=x1<…

定義2[5]設 A=[[x1,xn],f(x)]和 B=[[y1,yn], g(y)]為同階未確知有理數,其中

若當確信A取xi時,B取yi,且當B取yi時,A取xi,則稱A和B是相依未確知有理數。

定義3[5]設A與B為相依未確知有理數,當且僅當αi=βi,(i=1,2,…,n)時,則稱 A與B是線性相依的。

定義4[5]設A與B是相依的未確知有理數,稱同階未確知有理數C=[[x1+y1,xn+yn],h(z)]為相依未確知有理數A與B的和,記作C=A?B,其中

由以上定義知,任意的未確知有理數A與它自身是線性相依的,同時,若把實數a定義為未確知有理數的形式,則未確知有理數與實數也是線性相依的。

定理1[5]設G為所有與某一n階未確知有理數線性相依的n階未確知有理數的非空集合,則按上述的加法和數乘運算,G是實數域R上的線性空間。

定理2設k∈R為任意常數,A為實數,未確知有理數B具有定義2中的形式,則未確知事件的可信度Cr{k(A-B)≤0}等價于下面兩種形式:當k>0時,Cr{k(A-B)≤0}=Cr{AB≤0};當k<0時,Cr{k(A-B)≤0}=Cr{A-B≥0}。

證明由未確知有理數 B的形式可知:kB=[ky1, kyn],g′(y)],其中

2 線性相依條件下未確知機會約束規劃問題的解法

考慮如下的未確知機會約束規劃問題:

其中x∈Rn為決策向量,Bi(i=1,2,…,p)為未確知參數向量。f(x)為不含未確知參數的目標函數,g(x,Bi),i=1,2,…,p為約束函數,α∈[σ,1]為事先給定的置信水平,Cr{.}為未確知事件的可信度。

對于未確知機會約束規劃,當約束函數為特殊情形,即g(x,B)=B-h(x),g(x,B)=h(x)-B時,利用文獻[3]中的算法,將未確知約束條件轉化為相應的確知等價類,從而可將整個未確知規劃問題轉化為一個確知問題,再利用確知規劃的方法解之。下面我們考慮當約束條件為一般形式時,即 g(x,Bi)=h(x)A-Bi(其中h(x)為決策變量 x的函數, A,Bi(i=1,2,…,p)為未確知有理數),當A與Bi(i=1,2,…,p)為線性相依未確知有理數時,未確知機會約束規劃問題的解法。

設A=[[x1,xn],f(x)]與Bi(i=1,2,…,p)為線性相依未確知有理數,其中

設Bi=A+ai,Bi=[[x1+ai,xn+ai],wi(y)],其中

其中ai∈R為任意的實數。

根據第二部分的線性相依理論,我們考慮線性相依條件下未確知機會約束規劃中當約束條件為一般形式時的解法。

g(x,Bi)=h(x)A-Bi=h(x)A-(A+ai)=h(x)AA-ai=[h(x)-1]A-ai。

利用曲線 h(x)-1可以把整個空間劃分為3部分,即h(x)-1>0,h(x)-1<0,h(x)-1=0。

對于 h(x)-1≠0,則有

相應的未確知機會約束規劃中的條件 Cr{g(x,Bi)≤0}≥α,即可寫成如下形式

利用上面的定理2可知(1)式等價于以下兩種形式: ,則上面兩個式子可表示成如下形式:

于是,對于一般形式的約束條件g(x,Bi)=h(x)A-Bi就轉化為目前已解決的g(x,B)=B-h(x),g(x,B)=h(x)-B的形式,接著利用文獻[3]中的算法,可將約束條件為一般形式的未確知機會約束規劃轉化為與其等價的確知規劃。

特別的,對于h(x)-1=0的情形,未確知約束條件就簡化為Cr{-ai≤0}≥α的形式,因此,若 ai<0,則無解;若ai≥0,則未確知約束條件就等價為 h(x)-1=0。

3 算例

對于上述線性相依條件下的未確知機會約束規劃問題的解法,我們給出一個具體算例。

解如下的未確知機會約束規劃:

設未確知有理數A=[[1,4],f(x)],B=A+2=[[3,6], w(x)],其中

記h(x)=3x1+x2,而A與B為線性相依未確知有理數,顯然該規劃的約束條件具有g(x,B)=h(x)A-B的一般形式。利用第三部分所給的方法解此規劃問題,步驟如下:當h(x)-1≠0時,可將規劃(2)中的未確知約束條件Cr{(3x1+x2)A-B≤0}≥0.8轉化為下面的等價問題:

這樣就把約束條件為一般形式的未確知問題轉化為目前已解決的約束條件為特殊形式的問題,接著再利用文獻[3]中的算法就可求得整個問題的解。步驟如下。

首先,將未確知有理數A表示成其分布型:

再根據文獻[3]中的算法,將式(3),式(4)中的兩個式子轉化為其相應的確知等價類:

于是,當 h(x)-1≠0時,原未確知機會約束規劃(2)的確知規劃為:

特殊情形時,即當3x1+x2-1=0時,并且這里的a= 2>0,則原問題(2)等價于下面的規劃

4 結束語

筆者研究了在兩未確知有理數為線性相依條件下未確知機會約束規劃問題的解法,對于建立未確知支持向量機的設想具有一定的現實意義,但對于一般情況下的解法還需進一步研究。

[1] Yang Zhimin.Review of the monograph mathematical treatment and application of uncertain information[J]. Chinese Science Bulletion,2001(7):615-616.

[2] 王光遠.未確知信息及其數學處理[J].哈爾濱建筑工程學院學報,1999(4):1-4.

[3] 楊志民,鄧乃揚.未確知機會約束規劃[J].系統工程, 2004:11-14.

[4] 楊志民,劉廣利.不確定性支持向量機原理及應用[M].北京:科學出版社,2007:38-202.

[5] 高志強,王義鬧.相依未確知信息的數學表達及其運算[J].華中科技大學學報,2003(4):36-38.

[6] Charens A,Cooper W.Chance constrained programming [J].Management Science,1959(1).

[7] András Prékopa.On probabilistic constrained programming [M].Princeton:Princeton university press,1970:113 138.

(責任編校:夏玉玲)

The Method of Unascertained Chance Constrained Programming under the Conditions of Linear Interdependence

LI Xiao-qing,ZHOU Chang-yin,WANG Yan-zhao
(College of Information Science and Engineering,SUST,Qingdao 266510,China)

Under the linear interdependence condition,the solution is studied about unascertained chance constrained programming with general linear constrain and method for solving the problem is proposed with numerical examples to demonstrate the method’s feasibility.Such a way to deal with problems has great practical significance for the establishment of unascertained support vector machines.

unascertained rational number;linear interdependence;credible degree;chance con-strained programming

O211.5

A

1672-349X(2010)06-0010-03

2010-06-02

國家自然科學基金項目(10971122);山東省自然科學基金項目(Y2008A 01)

李小青(1983-),女,碩士研究生,主要從事隨機優化及未確知支持向量機研究。