模糊關(guān)系方程極小解的一種判別方法

林海濤, 楊曉鵬

(韓山師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 廣東 潮州 521041)

Sanchez[1-2]第一次提出了含max-min合成算子的模糊關(guān)系方程并進(jìn)行開(kāi)創(chuàng)性的探究之后，模糊關(guān)系方程開(kāi)始被應(yīng)用于多個(gè)領(lǐng)域[3-6]，諸如模糊邏輯推理、人工智能、模糊決策和圖像處理.后來(lái)，學(xué)者又致力于含max-product合成算子的模糊關(guān)系方程[7-9]的研究，并在諸多領(lǐng)域得到廣泛的應(yīng)用[10-13].max-min和max-product是最基本的2個(gè)模糊關(guān)系運(yùn)算.經(jīng)典的Max-T(T表示連續(xù)三角模，包含min和product等)模糊關(guān)系方程或不等式的解集由其唯一的最大解和有限個(gè)極小解所完全確定[14-15]．一般情況下，最大解是容易得到的，因此獲得解集的關(guān)鍵就是求出全部的極小解．對(duì)于解集或極小解集的求解方法，可以參閱文獻(xiàn)[17-20]．然而，求出模糊關(guān)系方程的極小解是一個(gè)NP困難問(wèn)題，一般都不容易．對(duì)于一些具體的問(wèn)題，并不需要求出全部的極小解，而只需判斷一個(gè)解是否模糊關(guān)系方程的極小解．正是基于這樣的考慮，本文將研究含max-min算子和max-product算子的模糊關(guān)系方程的極小解判別方法，并給出具體的判別步驟.

含max-min合成算子的模糊關(guān)系方程，其型如：

(1)

在系統(tǒng)(1)中，aij,bi,xj∈[0,1]，i∈I={1,2,…,m}，j∈J={1,2,…,n},而且a∧b表示求a、b的最小值，a∨b表示求a、b的最大值.

系統(tǒng)(1)可以記為

(ai1∧x1)∨(ai2∧x2)∨…∨(ain∧xn)=bi，i∈I，

或簡(jiǎn)單記為

A·xT=bT，

其中，A=(aij)m×n，b=(bi)1×m，x=(xj)1×n.

含max-product合成算子的模糊關(guān)系方程，其型如：

(2)

其中,A=(aij)m×n，b=(bi)1×m，x=(xj)1×n，aijxj表示普通的乘積.

系統(tǒng)(2)可以記為

ai1x1∨ai2x2∨…∨ainxn=bi，i∈I，

或簡(jiǎn)單記為

A·xT=bT.

為方便表達(dá)，在證明過(guò)程中僅以系統(tǒng)(1)的運(yùn)算為例，即采用max-min合成算子，推導(dǎo)得到系統(tǒng)(1)的相關(guān)結(jié)論．對(duì)于系統(tǒng)(2)，由于利用相似的方法也可以得到相關(guān)結(jié)論，因此文中只給出相應(yīng)的結(jié)果，而不再詳細(xì)證明.

如果系統(tǒng)(1)存在可行解，即存在x∈[0,1]n，使得A·xT=bT成立，那么稱系統(tǒng)(1)為相容的；否則，稱系統(tǒng)(1)為不相容的.系統(tǒng)(1)的所有可行解構(gòu)成的集合記為X(A,b).

1 預(yù)備知識(shí)

(3)

定理2[14]若系統(tǒng)(1)是相容的,記X=[0,1]n，則(1)的所有解集為：

2 模糊關(guān)系方程極小解的判別定理

記

Ji={j|Ai·(x*j)T=bi,j∈J}，

即J0表示x*的分量為0的指標(biāo)集.顯然Ji、J0都是J的子集.

定理3若x*為系統(tǒng)(1)解，則對(duì)任意i∈I，Ji≠?.

即Ai·(x*j0)T=bi.因而j0∈Ji.從而Ji≠?.證畢.

可知，對(duì)于任意i∈I，Ji≠?.因而Ji至少含有一個(gè)元素，至多含有n個(gè)元素.記Ω={Ji|Ji為單元素集,i∈I}.

定理4(必要條件1) 若x*為系統(tǒng)(1)的解，則x*為極小解的必要條件是

(4)

其中，Ω為如上定義，即所有為單元素集的Ji的集合.

事實(shí)上對(duì)于任意i∈I，

注1定理4給出的是極小解的必要條件，但不是充分條件.例如,對(duì)于

(0.4∧x1)∨(0.5∧x2)=0.4，

為了尋求極小解的充分條件，引進(jìn)下面記號(hào)．

事實(shí)上，對(duì)于固定的j∈J，Ji={j}意味著存在唯一的x*j使得第i個(gè)等式成立.當(dāng)然，x*j可能使得多個(gè)等式成立，而且這些等式的指標(biāo)構(gòu)成的集合就是Ωj.可見(jiàn)Ωj?I.

事實(shí)上，xα與x*僅在第j0分量不同，其它相同.因而，只需要考慮指標(biāo)屬于Ωj0的那些方程.由Ωj0定義，對(duì)任意i∈Ωj0，有

另一方面，由于xα

這說(shuō)明找到比x*還小的解xα，此與x*為極小解矛盾.證畢.

例1設(shè)max-min模糊關(guān)系方程組為

驗(yàn)證下面的向量是否模糊關(guān)系方程組(5)的極小解:

解(i) 對(duì)于x(1)，易驗(yàn)證它不是(5)式的解，因而不是極小解.

定理6(充分條件) 設(shè)x*為系統(tǒng)(1)的解，則x*為極小解的充分條件是:

對(duì)任意ε=(ε1,ε2,…,εn)>0，令

由于Ji0={j0}為單元素集，因而對(duì)任意j≠j0，總成立

即bi0>Ai0·(x′)T，從而x′?X(A,b).由命題1，x*為極小解.證畢.

綜合定理4～6可以得到:

定理7(充要條件) 設(shè)x*為系統(tǒng)(1)的解，則x*為極小解的充要條件是:

定理8若x*為系統(tǒng)(2)的解，則對(duì)任意i∈I，Ji≠?.

證明略(類似定理3).

定理9設(shè)x*為系統(tǒng)(1)的解，則x*為極小解的充要條件是

(6)

證明略(類似定理4及6).

注3定理7用來(lái)檢驗(yàn)max-min模糊關(guān)系方程的解是否是極小解，定理9則是max-product模糊關(guān)系方程的解是否是極小解的充要條件.雖然均是以指標(biāo)的形式表達(dá)，但記號(hào)(4)與(6)所表達(dá)的運(yùn)算基礎(chǔ)不同.另外，對(duì)于前者，其充分條件比較“嚴(yán)格”，原因是需要考慮到min運(yùn)算的性質(zhì).而對(duì)于后者，只需要考慮指標(biāo)集是否滿足(6)的關(guān)系.

3 模糊關(guān)系方程極小解的判別算法

基于定理4～7(定理9)，給出max-min(max-product)模糊關(guān)系方程的極小解的判別算法．

Step1檢驗(yàn)x*是否為系統(tǒng)(1)(系統(tǒng)(2))的可行解.若不是，則x*非極小解；若是，轉(zhuǎn)向Step2.

Step2寫(xiě)出x*1,x*2,…,x*n.

Step3計(jì)算出J0、Ji及Ω，i=1,2,…,m.

例2設(shè)max-min模糊關(guān)系方程組與例1相同，驗(yàn)證下面的向量是否模糊關(guān)系方程組(5)的極小解：

(iv)x(4)=(0,0.3,0.7,0.4);

(v)x(5)=(0.3,0,0.7,0.4).

解(iv)對(duì)于x(4)，易驗(yàn)證它是(5)式的解，并且J0={1}，J1={3}，J2={3}，J3={3}，J4={2}，J5={4}，Ω={J1,J2,J3,J4}，故

例3設(shè)max-product模糊關(guān)系方程組為

(7)

驗(yàn)證下面向量是否模糊關(guān)系方程組(7)的極小解:

(i)x(1)=(0.8,0.75,0,1);

(ii)x(2)=(0.8,0.75,0,0);

(iii)x(3)=(0.8,0,0,1);

解(i) 對(duì)于x(1)，易驗(yàn)證它是(7)式的解，并由x*1=(0.8,0,0,0)，x*2=(0,0.75,0,0)，x*3=(0,0,0,0)，x*4=(0,0,0,1)，得J0={3}，J1={1}，J2={2,4}，J3={2,4}，Ω={J1}.由于

因而x(1)不是極小解.

(ii) 對(duì)于x(2)，易驗(yàn)證它是(7)式的解，并且J0={3,4}，J1={1}，J2={2}，J3={2}，Ω={J1,J2,J3}.

(iii) 對(duì)于x(3)，易驗(yàn)證它是(7)式的解，并且J0={2,3}，J1={1}，J2={4}，J3={4}，Ω={J1,J2,J3}.

(iv) 對(duì)于x(4)，易驗(yàn)證它是(7)式的解，并且J0={1,2}，J1={3}，J2={4}，J3={4}，Ω={J1,J2,J3}.

(iv) 對(duì)于x(5)，易驗(yàn)證它是(7)式的解，并且J0={1,4}，J1={3}，J2={2}，J3={3}，Ω={J1,J2,J3}.

由于(ii)、(iii)、(iv)、(v)滿足

根據(jù)定理9，x(2)、x(3)、x(4)和x(5)是系統(tǒng)(7)極小解.

4 結(jié)束語(yǔ)

致謝韓山師范學(xué)院博士啟動(dòng)項(xiàng)目(QD20171001)對(duì)本文給予了資助，謹(jǐn)致謝意.

[1] SANCHEZ E. Equations de Relations Floues[M]. Marseille:These Biologie Humaine，1972.

[2] SANCHEZ E. Resolution of composite fuzzy relation equations[J]. Information and Control,1976,30(1):38-48.

[3] SANCHEZ E. Solutions in composite fuzzy relationequations:application to medical diagnosis in Brouwerian logic[C]. Gupta M M, Saridis G N, Gaines B R. Fuzzy Automata and Decision Processes. Amsterdam:North-Holland,1977.

[4] NOBUHARA H, BEDE B, HIROTA K. On variouseigen fuzzy sets and their application to image reconstruction[J]. Information Sciences,2006,176(20):2988-3010.

[5] NOBUHARA H， PEDRYCZ W， SESSA S， et al. A motion compression/reconstruction method based on maxt-norm composite fuzzy relational Equations[J]. Information Sciences，2006，176(17):2526-2552.

[6] DI NOLA A， RUSSO C. Lukasiewicz transform and its application to compression and reconstruction of digital images[J]. Information Sciences，2007，177(6):1481-1498.

[7] LOETAMONPHONG J， FANG S C. An efficient solution procedure for fuzzy relation equations with max-product composition[J]. IEEE Trans Fuzz Syst,1999,7(4):441-445.

[8] PEEVA K， KYOSEV Y. Algorithm for solving max-product fuzzy relational equations[J]. Soft Computing,2007,11(7):593-605.

[9] SHIEH B S. Deriving minimal solutions for fuzzy relation equations with max-product composition[J]. Information Sciences,2008,178(19):3766-3774.

[10] YANG X P, ZHOU X G, CAO B Y. Single-variable term semi-latticized fuzzy relation geo-metric programming with max-product operator[J]. Information Sciences,2015,325(24):271-287.

[11] YANG X P, ZHOU X G, CAO B Y. Latticized linear programming subject to max-product fuzzy relation inequalities with application in wireless communication[J]. Information Sciences,2016,358(17):44-55.

[12] YANG X P, ZHOU X G, CAO B Y. Min-max programming problem subject to addition-min fuzzy relation inequalities[J]. IEEE Transactions on Fuzzy Systems,2016,24(1):111-119.

[13] 楊吉會(huì)，曹炳元. 取大乘積型模糊關(guān)系幾何規(guī)劃[J]. 應(yīng)用數(shù)學(xué)與計(jì)算數(shù)學(xué)學(xué)報(bào)，2005，19(2):79-84.

[14] 曹炳元. 應(yīng)用模糊數(shù)學(xué)與系統(tǒng)[M]. 北京：科學(xué)出版社，2005.

[15] 胡寶清. 模糊理論基礎(chǔ)[M]. 武漢：武漢大學(xué)出版社，2004.

[16] 楊曉鵬，楊曉斌. 模糊關(guān)系方程在實(shí)驗(yàn)室點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用[J]. 遼寧工程技術(shù)大學(xué)學(xué)報(bào)，2016，35(1):79-84.

[17] 曾中海，吳莉，王學(xué)平. BL-代數(shù)上sup-*合成模糊關(guān)系方程的極小解與算法[J]. 四川師范大學(xué)(自然科學(xué)版)，2013，36(2):185-89.

[18] 王學(xué)平. 完備格上模糊關(guān)系方程的研究進(jìn)展[J]. 四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2009，32(3):365-376.

[19] 屈小兵，雷滿華. 完備Brouwerian格上模糊關(guān)系方程解集的一種分類[J]. 四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2013，36(2):185-89.

[20] 何鵬，王學(xué)平. 覆蓋矩陣和max-min合成模糊關(guān)系方程的極小解[J]. 模糊系統(tǒng)與數(shù)學(xué)，2015，29(2):109-117.