李小青,周长银,王延朝

(山东科技大学信息科学与工程学院,山东青岛 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-),女,硕士研究生,主要从事随机优化及未确知支持向量机研究。