模糊關系方程極小解的一種判別方法

林海濤, 楊曉鵬

(韓山師范學院 數學與統計學院, 廣東 潮州 521041)

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

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

(1)

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

系統(1)可以記為

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

或簡單記為

A·xT=bT，

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

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

(2)

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

系統(2)可以記為

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

或簡單記為

A·xT=bT.

為方便表達，在證明過程中僅以系統(1)的運算為例，即采用max-min合成算子，推導得到系統(1)的相關結論．對于系統(2)，由于利用相似的方法也可以得到相關結論，因此文中只給出相應的結果，而不再詳細證明.

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

1 預備知識

(3)

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

2 模糊關系方程極小解的判別定理

記

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

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

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

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

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

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

(4)

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

事實上對于任意i∈I，

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

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

為了尋求極小解的充分條件，引進下面記號．

事實上，對于固定的j∈J，Ji={j}意味著存在唯一的x*j使得第i個等式成立.當然，x*j可能使得多個等式成立，而且這些等式的指標構成的集合就是Ωj.可見Ωj?I.

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

另一方面，由于xα

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

例1設max-min模糊關系方程組為

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

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

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

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

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

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

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

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

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

證明略(類似定理3).

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

(6)

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

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

3 模糊關系方程極小解的判別算法

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

Step1檢驗x*是否為系統(1)(系統(2))的可行解.若不是，則x*非極小解；若是，轉向Step2.

Step2寫出x*1,x*2,…,x*n.

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

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

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

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

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

例3設max-product模糊關系方程組為

(7)

驗證下面向量是否模糊關系方程組(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) 對于x(1)，易驗證它是(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) 對于x(2)，易驗證它是(7)式的解，并且J0={3,4}，J1={1}，J2={2}，J3={2}，Ω={J1,J2,J3}.

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

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

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

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

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

4 結束語

致謝韓山師范學院博士啟動項目(QD20171001)對本文給予了資助，謹致謝意.

[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] 楊吉會，曹炳元. 取大乘積型模糊關系幾何規劃[J]. 應用數學與計算數學學報，2005，19(2):79-84.

[14] 曹炳元. 應用模糊數學與系統[M]. 北京：科學出版社，2005.

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

[16] 楊曉鵬，楊曉斌. 模糊關系方程在實驗室點對點網絡系統中的應用[J]. 遼寧工程技術大學學報，2016，35(1):79-84.

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

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

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

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