Sự lựa chọn đa tiêu chuẩn

H = {a, b, c, d, e, f, {a,b), {d,el, {a,b,c), {a,b,c,d,e), E} C P(E) là một tôn ti. Tôn ti chỉ số hóa Một tôn ti H xác định trên E gọi là được chỉ số hóa nếu có một ánh xạ p : H → R(t), tức là p(H) E R(t). sao mà 1. Nếu A E H và Card A = 1 thì q(A) = 0, 2. Với mọi B, C C H và B > C, B # C thì q(B) > p(C). Ví dụ Trên tập hợp H nói trên, ta hãy thực hiện một ánh xạ, biểu diễn bằng "cây" như sau p = 4 { a,b, c, d, e,f) • = 3 { a,b, c, d,e}

4 = 2 { a,b,c} (d,e) p = 1 { a,6} 4 = 0 {a} • {b} →(c} • (d) • {e) • if)

Dễ thấy rằng tôn ti H với ánh xạ p đã trở thành một tôn ti chỉ số hóa. Có thể chứng tỏ được rằng tương ứng với một tôn ti chỉ số hóa là một khoảng cách infra, và ngược lại. Để minh họa, ta hãy trở lại khoảng cách Ý, nhưng chỉ lấy từ A đến D cho đơn giản > C A B C D

A 0,25 0,28 0,32 0,25 0,28 0,32 0,28 0,28 0,32 D 0,32 0,32 0,32 0 Các tập hợp các điểm có khoảng cách tương đối với nhau d(X, Y) = 0 tất nhiên là {A), {B), {C) và (D). Tập hợp các điểm có khoảng cách tương đối với nhau d(X, Y) ≤ 0,25 tất nhiên là {A,B}. Tập hợp các điểm có khoảng cách tương đối với nhau d(X, Y) ≤ 0,28 tất nhiên là {A, B, C}.

tất nhiên là {A, B, c, D}, Và tập hợp các tập hợp

{A, B, c, D} = 0,32

{A B, c] = 0,28

{Á, B} ^i = 0,25 = 0 {A} ế tôn ti bằng cách phân tích.

Ví dụ cho quan hệ tương sau b R a

0,4 0 a

0,4 0 b

0,4 0,3 c

0,4 0,3 d

0,4 0,1 e b R(0,2) a

0 0 a

0 0 b

0 0 c

0 0 d

1 0 e b a R(0,3)

0 1 a

0 0 b

1 0 c

1 0 d

1 0 e v.v...

\*{B}\»{CỊ \«!D}

d e c

0,4 0,4 0,1

0,3 0,4 0,3

0,2 0 04 0,4 0,2 0 0,4 0 0 4 d e c

1 0 0

0 0 ■ ũ

1 ũ 0 1 0 0

0 0 0 e d c

1 0 0

1 1 0

1 0 0

0 ! 0 1

0 0 0

Ta sẽ được tôn ti sau

II - TIÊU CHUẨN

Một trong những bài toán để lập quyết định là bài toán về tiêu chuẩn. Định nghĩa về khái niệm tiêu chuẩn là khá trừu tượng.

ĐỊNH NGHĨA

Ta gọi tiêu chuẩn xác định trên một tập E là cái đã tạo nên một cấu trúc trên tập đó.

Ví dụ

Cho tập

E = [a, b, c}

Bây giờ ta hãy đưa vào E các bất đẳng thức sau a < c < b.

Các bất đẳng thức này đã tạo trên tập E một cấu trúc thứ tự, tức là một tiêu chuẩn (tiêu chuẩn thứ tự I). ỉ

Tiêu chuẩn này được biểu diễn bằng đổ thị như sau :

Ta sang một ví dụ khác, phức tạp hơn. Giả sử cố tập

E = { a, b, c, d, e, f}.

Chúng ta hãy đưa vào tập đó một cấu trúc được biểu diễn bằng đồ thị sau

Với đổ thị này, ta đã trang bị cho tập E một cấu trúc nào đó, nghĩa là biến E thành một tiêu chuẩn nào đó. Và hãy làm rõ tiêu chuẩn này. Để đạt mục đích này, trước hết ta nhận xét rằng đồ thị này mô tả một quan hệ tiền thứ tự. Và theo lệ thường, sau khi xác định được các lớp tương đương trong quan hệ tiền thứ tự đó, chúng ta sẽ thu được một quan hệ thứ tự (mờ) có thể là toàn phần hay không toàn phần.

Theo định nghĩa, quan hệ thứ tự mờ này tạo nên một tiêu chuẩn trên tập E, được mồ tả bởi đồ thị giản đơn hóa sau

HỆ TIÊU CHUẨN

Trên một tập hợp E có thể có nhiều tiêu chuẩn khác nhau, ví dụ

E = {a, b, c}

a > c = b c > b — à

Như chúng ta thấy, các tiêu chuẩn có thể trái ngược nhau, mâu thuẫn nhau phần nào. Và bài toán hiện ra trước mắt là phải quyết định một sự dung hòa các mâu thuẫn, hay thỏa hiệp trong một chừng mực nào đó. Nhưng sự dung hòa này, thỏa hiệp này lại phụ thuộc vào chủ quan của người xem xét vấn đề, cân nhắc tính quan trọng của từng tiêu chuẩn một.

Điều này xảy ra hằng ngày trong cuộc sống. ^

Sự CÂN NHẮC, ĐÁNH GIÁ CHỦ QUAN

Cho một tập E, và một hệ tiêu chuẩn T|, T2,..., In trên E. Người xem xét vấn để - theo chủ quan của mình - có thể cân nhắc và cho tiêu chuẩn thứ i một giá trị nào đó Pì...

Nếu

H pì = 1 thì sự cân nhấc Pị gọi là chuẩn hóa.

Tóm lại, nói chung trong cuộc sống hàng ngày, chúng ta luôn luôn phải quyết định giữa những bài toán đa tiêu chuẩn.

Vấn đề là phải :

- Xếp các sự kiện thành những

NHÓM TƯƠNG ĐƯƠNG

với nhau, có thể dựa vào các

KHÁI NIỆM Khoảng CÁCH khác nhau,

- Xét QUAN HỆ MỜ giữa các nhóm tương đương đó, trong đó có BÀI TOÁN QUAN HỆ THỨ TỰ MỜ, BÀI TOÁN TỘN TI, BÀI TOÁN TIÊU CHUẨN, BÀI TOÁN CÂN NHẮC. - Đi xa hơn thì có BÀI TOÁN NHÂN QUẢ...

KINH DỊCH VÀ HOẠT ĐỘNG CỦA NHÂN THỂ VỚI MỌI CẤU TRÚC HỮU HÌNH, VÔ HÌNH CỦA NÓ KHÔNG THỂ NÀO TÁCH RỜI KHỎI NHỮNG LOẠI BÀI TOÁN ĐA TIÊU CHUẨN NÀY

IV - TÍCH HỢP NHIỀU TẬP MỜ THÀNH MỘT TẬP MỜ Cho n tập mờ A1, A2,..., An, trên cùng một hệ quy chiếu E = {Xi}. Kí hiệu các hàm thuộc là Ai (x;) = uj. Hãy tìm một tập mờ A, với A(xk) = ux, sao mà A làm tối thiểu lượng E = Eo, é (A, Ai).

trong đó P ; là trọng số của một sự cân nhắc chủ quan nào đó, còn 2 (A, A,) = EV4, - 14)3, là khoảng cách Euclide giữa A và A;. Bài toán quy về cách tìm cực tiểu của hàm I = Еp,M4, - Hj)”- Như đã biết, trong trường hợp này điều kiện cần để có cực tiểu là (phương pháp bình phương tối thiểu),(4 ; - 14)) = 0. ; атон, = 2 Ta suy ra ngay

i I ì

Từ đó, nếu chọn một sự cân nhắc chuẩn hóa, tức là với ^pi = 1, ta được ngay i nghiệm sau

Ví dụ

Cho

E = {a, b, c, d, e}, A a b d c e

A^ 1 0,3 0,8 0 0,1

0.2 1 0,7 1 0 A2

0,4 0,2 0,3 0,9 A3 0.1

0 0 8 0,6 0,4 1 A a và theo một loại kinh nghiệm chủ quan nào đó ta chọn sự cân nhắc sau :

Pị = 0,3, p2 = 0,1, Py = 0,5, p^ = 0,1.

Thế thì, theo công thức trên, ta được :

ụ(à) = 0,3(0,3) + 0,1(0,2) + 0,5(0,4) 4- 0,1(0) = 0,31, Tương tự như thế, ta được :

p(a) = 0,16, p{b) = 0,55, p(c) = 0,86, p(d) = 0,30, vậy

A a b d c e

0,31 0,16 0.55 0,86 0,30 ỉ<

Có thể thay khoảng cách Euclide bằng khoảng cách Hamming.

V - TÍCH HỢP NHIỀU Đồ THỊ THÀNH MỘT Đồ THỊ

Bài toán tích hợp n đồ thị thành một đổ thị được giải nếu ta đưa ra một khái niệm gọi là "khoảng cách lưỡng phần" như sau.

Cho một tập E hữu hạn và cho A, B c E. Thế thì lượng

4 card(A NB) R(A, B) = 1 - card(A U B) gọi là khoảng cách lưỡng phần giữa các tập A và B của E. Có thể chứng minh rằng khoảng cách này thỏa mãn các điều kiện của khái niệm khoảng cách k(A, A) = 0, k(A, B) = k(B, A), k(A, C) ≤ Min {k(A, B) + k(B, C)}. Ví dụ 1. Trước hết, ta chọn một ví dụ về đồ thị bình thường M, N, P, cardE = 3, hữu hạn, b Nt ! b C a. b a a 0 1 1 a 0 0 1 b 0 1 b 1 1 b 1 1 1 1 0 1 1

Hãy tìm một đồ thị R, sao mà 9(R) = p(M)k(R,M) + p(N)k(R,N) + p(P)k(R.P) • là tối thiểu, với một sự cân nhắc chuẩn hóa p(M), p(N), p(P) nào đó. Để tìm đồ thị R, số khả năng rất lớn. Tuy nhiên để giản đơn bài toán, ta hãy chọn giả thiết là đồ thị phải tìm thuộc loại thứ tự toàn phần. Thành thử, ta hãy xem đồ thị R phải tìm là thuộc loại này, từ đó, ta có thể chọn 6 đồ thị có thứ tự toàn phần sau :

a b a b

1 1

0 0 1 1 1 1 1 :

a b FT. a b a a 1 1 b 1 1 1 1 0 1 1

A : ash≤a B : h≤6≤4 C : 65"5"

Q a D : 15056 E : b515€ F : 115b50

Tiếp theo, theo phương pháp bình phương tối thiểu, ta được (9(А), q(B), 9(C), g(D), q(E), 9(F)) = k(A, M) k(B, M) k (C, M) K(D, M) k(E, M) k(F, M) = (P(M), P(N), P(P)) X< k(A, N) K(B, N) K(C, N) K(D, N) KE, N) k(F, N) (K(A, P) K(B, P) K(C, P) K(D, P) K(E, P) K(E, P)I

Tính các k (A, M), k (A, N)... ở vế phải Ta có card (A N M) = 3, card (A U M) = 8, card (A N N) = 3, card (A U N) = 9, card (A N P) = 2, card (A U P) = 8, từ đó : K(A, M) = 1 - 3/8 = 5/8, k(A, N) = 1 - 319 = 213, K(A, P) = 1,- 218 = 3/4. Tương tự như thế, ta được

và sự cân nhắc píM) = 0,7, pỉN) = 0,3. Bài tính đặt ra là tìm một đồ thị thông thường R, mang tính thứ tự toàn phần (để được đơn giản), tích hợp được tốt nhất các đồ thị M và N. Ta chọn đồ thị R đó trong số các đồ thị A, B, C, D, E, F ở ví dụ 1 trên. Ta tính

AN M a b A UM a b a 0,3 0 a 1 0 0,8 b 1 0,2 b 1 1 0,4 0,9 1 1 1 1

AN n M, Ø) = (0,3)2 + 0 + 0 + 1 + (0,2)2 + 0 + (0,92 + 1 + 0 = 2,94, (A UM, Ø) = 1 + 0 + (0,8)2 + 1 + 1 + (0,4) +1+1+1 = 6,80, tức là k (A, M) = 1 - (2,94/6,80) = 0,56 Tiếp theo, tương tự như thế, ta tính được é (A n N, Ø) = 2,74, é° (A UN, Ø) = 7,45, tức là k (A, N) = 0,63. từ đó q(A) = p(M) k (A, M) + p(N) k(A, N) = 0,7(0,56) + 0,3(0,63) = 0,58. Tương tự như thế, ta có k(C, M) = 0,75, K(C, N) = 0,65, q(B) = 0,72, k(D, M) = 0,77, K(D, N) = 0,70, q(B) = 0,75, K(E, M) = 0,75, k(E, N) = 0,60, q(B) = 0,73, K(F, M) = 0,89, K(F, N) = 0,70, q'B) = 0,83. Thành thử Min {q(A), q'B), q(C), q'D), q(E), q(F)) = 0,58. Nhưng số này lại tương ứng với đồ thị A. Cuối cùng như thế là R = A, và quan hệ thứ tự tương ứng là a > 6 ≥ c.

Ta nói rằng đồ thị A đã tích hợp tốt nhất các đồ thị mờ M và N theo sự cân nhắc trên. Còn có một số loại bài toán khác trong phạm vi tích hợp đồ thị, chẳng hạn là bài toán tích hợp nhiều đồ thị M, N,.., P thông thường bằng một đồ thị mờ R. Công thức vẫn tương tự như trên, tức là R(x, Y) = p(M) Míx, y) + p(N) N(x, y) + p(P) P(x, 1), p(M) + p(N) +... + p(P) = 1.

VI - TÍCH HỢP NHIỀU QUAN HỆ THÀNH MỘT QUAN HỆ. PHƯƠNG PHÁP JACQUET LAGRÈGE Cho một hệ quy chiếu E = {a, b, c, d} và 7 tiêu chuẩn sau C, : a > 6 = c > d, Cz : a > c>d >b, C3:6>6> a =d, C4 : 6 > a =0= d, C5 : d =6>a>e, Co:c >6= a = d, Cy : a >0=d > b. Kí hiệu hệ tiêu chuẩn này là C = 1C1, Cz, Cz, C4, O5, Cụm, Cnt. Tiếp theo, ta định nghĩa Cab là tập con của C chỉ chứa các phần tử nào của C trong đó a ≥ b, và tương tự như thế cho các tập con khác. Thành thử, theo định nghĩa đó, ta được Cau = Cbb =Ccc =Cdd =C, Cy = 191. Cz, 96971, Các = 1Cp, Cz, C4, Cu, Gat, Cba = 1C3, Cự, Cs, Cf), Ob0 = 101, 03, 94. 955 Cbd = 101, 03, 04, 05, 967, Cca = 1C3, C4. C,l. ; Từ đó các tập con 91. 02, 03. C7. C5, 96,97

ta được Bảng c2 c3 C4 C1

0,2 0,8 0,3 0,6 Caa

0,2 0,8 0 0 Cab

0,2 0,8 0 0,6 Các

0,2 0,8 0,6 0 0,3 Cad

0.3 0 0 0,6 Cba

0,2 0,8 0,3 0,6 Cbb

0,2 0 0,3 0,6 Cbc

0,2 ũ 0,3 0 0 Cbd

0 0 0 0 0,3 Cca

0,2 0,8 0 0 0 Ccb

0,2 0,8 0,6 0,3 Ccc

0,2 0,8 0,6 0 0,3 Ccd

0 0,3 0 0 Cda

0 0,8 ũ 0 Cáp

0 0 0 0,6 Cdc

0,2 0,6 0,8 0,3 Cdd

Trong Bảng trên, ờ cột cuối lượng Smn bằng

{^(cp + Cnin(C2) s™

Bây giờ, ta hãy viết ma trận Smn c a b Smn t

1 a 0,72 1 0,55 b c 0,36 0,72 d 0 38 0,69 là ma trận c5 c6 Smn C7

1 0,6 1 0,1

1 0,6 0,72 0

0 0,6 0,63 0,1

1 0,97 0 0,6

1 0,55 0,1 0

1 0,6 1 0,1

1 0 0,33 0,1

0 1 0 0,61

1 0 0 0,36

1 0,72 0 0,6

1 0,6 1 0,1

0 1 0,6 0,92

1 0,1 0 0,38

1 0,6 0,69 0,1 ũ 0,1 0,6 0,36

1 0,6 1 0,1

C(C7).

c d

0,97 0,63 0,33 0 61

1 0,97 1 0,36 s khác nhau, chẳng hạn

S'mn 1l a b d a 1 0,72 0,97 0,63 b 0,55 1 0,61 0,33 0,38 0,69 0,36 0,36 0,72 0,97 1 Hai ma trận trên là tương ứng với hai thứ tự khác nhau : Smn tương ứng với thứ tự a > b > c > d. S'mn tương ứng với thứ tự a > 6 > d > c. Các phần tử ma trận nằm bên trên đường chéo chính của mỗi ma trận đó gọi là các "hệ số dính từng phần tương ứng với thứ tự đang xét", còn các phần tử nằm bên dưới gọi là các "hệ số thải từng phần" Thế thì lượng K(a, b, c, d) = E(Smn - SJ, tổng lấy theo các hệ số dính và hệ số thải, các hệ số thứ nhất không đổi dấu, các hệ số thứ hai đổi dấu, gọi là "hệ số dính toàn bộ" tương ứng với thứ tự đang xét của a, b, c, d. Như thế là ta có tất cả 24 hệ số dính tương ứng với 24 thứ tự khác nhau của a, b, c, d. Nói riêng, với thứ tự a > b > c > d, theo định nghĩa, ta được Kía, b, c, d) = (0,72 - 0,55) + (0,63 - 0,36) + (0,97 - 0,38) + (0,33 - 0,72) + + (0,61 - 0,69) + (0,97 - 0,38) = 1,17, Kía, b, d, c) = (0,72 - 0,55) + (0,97 - 0,38) + (0,63 - 0,36) + (0,61 - 0,69) + + (0,33 - 0,72) + (0,36 - 0,97) = -0,05. Kết quả chung được ghi thành Bảng sau

Thứ tự K Thứ tự K a> b›c> d 1,17 b>c>a>d 0,29 a>d>b> c -0,05 b›asa>d -0,89 a›c>b>d 1,95 b>d> a > C -1,57 a> c>d>b 2,11 b>d> c >a -2,11 ay d > b > c 0,11 C » a > b, > d 1,41 a z d > c > b 0,89 C > > d > b 1,57 b > > c > d 0,73 C > b > a z d 1,07 b > a d > c -0,39 C > d > a - 0,11 c ›d> a > b 0,39 c> d> b> a 0,05 d > a > c -1,07 d > a c > b -0,29 1. d > b > a > c -1,41 d > b > > …a -1,95 d > c> a> b -0,73 d > b y a -1,17

Thứ tự toàn phần tốt nhất (tất nhiên theo sự cân nhắc được lựa chọn) là tương ứng với giá trị cao nhất của K. Đó là giá trị Max K = 2,11. Thứ tự tương ứng là a > c > d > b. Đó chính là kết quả tích hợp 7 tiêu chuẩn trên. Cũng có trường hợp xuất hiện nhiều nghiệm.

VII - TÍCH HỢP NHIỀU QUAN HỆ THÀNH MỘT QUAN HỆ. PHƯƠNG PHÁP ELECTRE Ta chuyển sang một phương pháp tích hợp nhiều quan hệ khác, gọi là phương pháp Electre. Cũng như trước, cho n tiêu chuẩn C,, Cz..... Cn • được xác định bởi n quan hệ tiền thứ tự (với các tính chất phản xạ và bắc cầu) Ry, Rez,.... Tụ, Bây giờ chúng ta hãy giả sử có một sự cân nhác pi và từ đó xây dựng được một quan hệ mờ R với hàm thành phần dạng R(x, J) = Ep,R,(, v). Ip = 1. • Do các quan hệ Rị có tính phản xạ, quan hệ R cũng có tính chất đó. Ví dụ Cho ba tiêu chuẩn A, B, C tương ứng với ba quan hệ tiền thứ tự M, N, P sau

M1 a e Nf a d e

1 1 o 1 + = O Q 0. 1 • 1 0 1 e 1 = 1

C

1 Q -- ; 1 e 1

Tiếp theo, ta chọn sự cân nhắc p(M) = 0,3, p(N) = 0,6, p(P) = 0,1.

Từ đó, ta dựng được quan hệ mờ sau b a d e c

0,4 1 0,4 0,4 0,4 a

1 1 0,9 1 0,9 b

1 0 0 1 ũ c

0 0,9 1 0 0 d

0,7 0,7 0,7 0,7 1 e

Đến đây có hai thao tác khác nhau, có liên quan đến các quan hệ đã cho M, N, p và quan hệ mờ R, kết quả của sự cân nhắc chủ quan trên.

THAO TÁC 1

Thành lập mối quan hệ thứ tự cho các lớp thuộc mối quan hệ M, N, p đã cho.

- Với quan hệ M, chúng ta có ba lớp tương đương là

{a, ố}, {c, d}, {e}, trong đó xuất phát là lớp {a, b} (lớp xuất phát gọi là lớp không có tổ tiên) được xác định theo chiều mũi tên. Từ đó, ta có thể lập sơ đổ sau :

Np số thứ tự 1 M :

No> số thứ tự 0

Với các quan hệ khác, ta cũng tiến hành tương tự như thế

Np số thứ tự 1

No, số thứ tự 0 n 31 SỐ thứ tự 3 Nỉ P :

Nọ, số thứ tự 2 w

N„ số thứ tự 1 {*}

No. số thứ tự 0 {“.e)

Theo các kết quả thu được, các lớp tương đương chia thành từng mức có các số thứ tự tương ứng.

Các số thứ tự theo các quan hệ khác nhau M, N, p của lớp các phần tử a, b..., cho phép định nghĩa lượng sau :

r(x, y) = Max (mức của X - mức của y),x, y = a, b, c...

M.N.P

Từ đó lập Bảng r(x, y).

Đến đây, chúng ta cho một định mức z = 0, 1, 2, 3... và định nghĩa tập

D(l) = {{x, ỵ} sao mà r(x, yj ^ l}, Dự) = E X E[ D(l), chẳng hạn, theo Bảng trên, ta được

D(2) = Hc, a}, {c, e], {c, a], [d, a}, {d, e} }, f từ đó P(2) gồm tất cả các cặp có mặt trong Bảng mà không có dấu *

Mức của x - Mức của y

x, У Trong M Trong N Trong P r(x, y) D(2)

a, a 0 - 0 = 0 1 - 1 = 0 0 - 0 = 0 0 a, b 0 = 0 = 0 1-0= 1 0 - 1 = -1 1 а, с 0 - 1 = -1 1 - 1= 0 0 - 2 = -2 0 a, d 0 - 1 = -1 1 - 1 = 0 0 - 3 = -3 0

a, e 0 - 1 =-1 1-0= 0 0- 0= 0 1

b, a 0 - 0 = 0 0 - 1 = -1 1- 0 = 1 1 b, b 0 - 0 = 0 0 - 0 = 0 1 - 1= 0 0 b, с 0 - 1= -1 0 - 1 = -1 1 - 2 = -1 -1 b, d 0 - 1 = -1 0 - 1 = -1 1 - 3 = -2 -1 b, e 0 - 1=-1 0 - 0 = 0 1 - 0 = 1 1.

с, а 1 - 0 = 1 1- 1 = 0 2 - 0 = 2 2 * с, b 1 - 0 = 1 1 - 0 = 1 2 - 1 = 1 1 с, с 1 - 1 = 0 1- 1 = 0 2 - 2 = 0 0 c, d 1 - 1 = 0 1 - 1 = 0 2 - 3. = -1 с, е 1 - 1 = 0 1 - 0 = 1 2 - 0 = 2 2 * d, a 1 - 0 = 1 1 - 1 = 0 3 - 0 = 3 3 * d, b 1- 0 = 1 1- 0 =1 3 - 1 = 2 2 * d, c 1 - 1 = 0 1 - 1 = 0 3 - 2 = 1 1 d, d 1 - 1 = 0 1 - 1 = 0 3 - 3 = 0 0 d, e 1 - 1 = 0 1 - 1 = 0 3 - 0 = 3 3 * е, а 1 - 0 = 1 0 - 1 = -1 0 - 0 = 0 1.

e, b 1- 0 = 1 0 - 0 = 0 0 - 1= -1 е, с 1 - 1= 0 0 - 1 = -1 0 - 3 = -3 e, d 1 - 1 = 0 0 - 1 = -1 0 - 2 = -2 е, е 1 - 1 = 0 0 - 0 = 0 0 - 0 = 0

THAO TÁC II Thao tác này có liên quan đến quan hệ mờ R. Cụ thể là : Ta hãy phân tích quan hệ mờ này thành nhiều quan hệ thông thường như đã nói trong định lý phân tích

R(1) 1 1 b d e A(0,9)1 a b d e a 1 0 0 a 1 0 0 0 b 1 0 e 1 1 0 0 1 1 d 0 0 0 d 1 1 e 0 0 0 1 e 0

R (0,7) 1 a b d e R (0,4) 11 a b d e a 1 0 0 0 a 1 0 0 0 b 1 1 1 1 b 1 1 0 1 0 0 d 1 0 d 0 1 e 1 1 1 e 1 1 1 1 1

• Các mức k = 1, 0,9, 0,7, 0,4 gọi là ngưỡng. Ta thấy ngay rằng tại ngưỡng k = 1 thì, với ma trận thứ nhất, các cặp sau là có liên quan với nhau (thường gọi là tương thích với nhau) Q(1) = {ía, as, {b,b}, {b, c), (b, d), (c. c), íc, di, (d, d), {d, el). Tại ngưỡng k = 0,9 ta có các cặp sau : Q(0,9) = Q(1) U {ib aj, {b, e) ; {d, b)). Và tại các ngưỡng khác, ta có Q(0,7) = Q(0,9) U {{e, al, {e, b), (e, c), {e, d)), Q(0,4) = Q(0,7) U {ía, b}, {a, cl, {a, d), {a, el). Dễ thấy rằng khi k càng tăng thì tập trên càng nghèo Q(1) C Q(0,9) C Q(0,7) C Q(0,4). Trong lúc các tập Q gọi là tập tương thích, thì các tập D gọi là tập không tương thích. Vì lí do này, để ước lượng sự tương thích giữa các cặp, ta cần lấy cái giao I(k, 1) = Q(k) n D(L) C E X E.

Tập ỉ(k, l) sẽ gồm những cặp tạo nên một quan hệ thông thường. Cái đóng bắc cầu của nó sẽ cho một quan hệ bắc cầu Max Min, nghĩa là một quan hệ tiền thứ tự thông thường, quan hệ này sẽ đóng vai trò tổng hợp các quan hệ M, N, p lại với nhau, với các đặc trưng sau :

- Trọng số cân nhắc p, - Ngưỡng k, - Mức l.

Ví dụ, ta chọn ngưỡng 0,7 và mức 2. Ta thu được trong trường hợp này ỉ(k, ỉ) = 1(0,7 ; 2) = Q(0,7) n 5(2) = {{a, a}, {b, a}, {b, b}, {b, c}, {b, d}, {c, c}, {c, d}, {d, c}, {d, d}, {e, a}, {e, b}, {e, c}, {e, d}, {e, e}}}.

Một điều may mắn là quan hệ với /(0,7 ; 2) chính là cái dóng bắc cầu Max Min của nó. Kết quả này của bài toán tích hợp nhiều quan hệ M,' N, p chính lại là 7 ? — M. Và điều này không lấy làm ngạc nhiên lắm, do chúng ta đã chọn sự cân nhắc p(M) = 0,6 khá cao.

Chú ý

Trong ví dụ trên, khi thành lập số thứ tự các lớp của một quan hệ tiền thứ tự, chúng ta đã xuất phát từ các lớp không có tổ tiên, nghĩa là tại đó chỉ có các mũi tên xuất phát, mà không có mũi tên tới.

Tất nhiên, cũng có thể dựng thứ tự các lớp xuất phát từ tình huống ngược lại, tức là các lớp tại đó chỉ có mũi tên tới mà không có mũi tên đi. Những lớp như thế gọi là những lớp không có thừa tự.

VIII - TÍCH HỢP NHIỀU PHÂN HOẠCH THÀNH MỘT PHÂN HOẠCH

Chúng ta hãy chuyển sang một loại bài toán khác là bài toán tích hợp nhiều phân hoạch thành một phân hoạch. Cách giải bài toán này dựa vào hai điểm sau :

- Công thức Stirling về số lượng phân hoạch, - Khái niệm chỉ số bất đồng tính giữa hai tập con của cùng một tập.

CÔNG THỨC STIRLING

Cho một tập E gồm m phần tử, card E = ni, và E có r lớp tương đương. Thế thì số phân hoạch sím, r) đối với tập E sẽ cho bởi công thức truy toán sau (công thức Stirling) :

s(m + 1, r) = s(m, r - 1) + r.s(m, r), * m = 1, 2, 3... r = 1, 2, 3,...

Từ đó có thể lập Bảng sau

s(m, r) r = 1 r = 1 r = 1 r =1 r= 1 r = 1 r =1 Es(m, r) s(1, r) s(2, r) 2 s(3, r) 3 1 5 s(4, r) 1 7 6 1 15 s(5, г) 1 15 25 10 1 52 s(6, r) 1 31 90 65 15 1 203 s(7, r) 1 63 301 350 140 21 1 877 s(8, r) 1 127 966 1701 1050 266 28 1 4140

Ví dụ Cho E = la, b, c, dl, m = 4. Nếu r = 2, thì ta có các phân loại sau Lớp (3, 1) ; [(a, b, c), (d}], lía, b, d), (c}l, [ía, c, d). {b}], [íb, c, d}, {a)], 4 phân hoạch, Lớp (2, 2) ; [la, b), íc, d)l, lía, c), íb, dil, Lía, di, Ib, cłl, 3 phân hoạch. • Nếu r = 3, thì ta có 6 phân hoạch sau Lớp (2, 1, 1) : ({a, b), {c), {d)l, ({a, c), {b), {d)l. (a, d}, {b}, {c)l, ({b, c}, {a}, {d} ], ((o, d), {a}, {c}l, ({e, di, {aj, {6]].

CHỈ SỐ BẤT ĐỒNG TÍNH Cho một tập E và tập các tập con của E là P(E). Gọi T và S là hai tập con của P(E), S C P(E), S C P(E). Thế thì, theo định nghĩa, chỉ số bất đồng tính q (T, S) giữa hai tập T và S là (T, S) = 1-=2 Max CardAn B) # ZETBES Card(A U B)' p(I, S) = 1 - ŽÍ4(I,S) + Y(S, I)}. Rõ ràng là : p(T, T) = 0, p(S, S) = 0, p (T, S) # D = T = S, p(T, S) = p(S, T), p(T, S) E 10, 1l.

Ví dụ

Cho

E = { a, b, c, d, e, f}, T = [A, B, c, D, E}, s = {F, G},.

với

A = {a}, B = {a. b}, c = {a, e, f}, D = {b, d, e}, E = {c, f}, F = [b, c], G = [a, b, c, f}.

Câu hỏi : Hai tập T và s đồng tính với nhau đến mức nào, nghĩa là hai phần hoạch T và s khác nhau đến mức nào ?

Ta tính như sau :

Card (A n F) = Card 0 = 0, Card CA u F) = Card {a, b, c} = 3, từ đó

Card (A n F) / Card (A u F) = 0.

CA ÍT G) = {a}, Card CA (An G) = 1, (A u G) = {ữ, b, d, /}, Card (A u G) = 4 =>

Card (A n G) / Card (A u G) = 1/4. - •

Max{[Card (A n F)/ Card (A u F)] ; [Card (A n Gì/ Card (A u G]} =

= Max {0,1/4} = 1/4.

(B n F) = {b}, Card (B n F) = 1, (B u F) = {a, b, c}, Card (A u G) = 3

Card (B n GỊ / Card (B u F) = ỉ/3.

(B n G) ={a, ờ}, Card n G) = 2, (B u G) =(ữ, b, d, f}, CardíB u G) = 4 =>

Card (B n G) ỉ Card (B u G) = 1/2.

Max { [Card (B n F) / Card (B u F)], [Card (B n GỴ. / Card (B u G]} =

=Max {1/3,1/4} = 1/3.

(C n F) = 0, Card (C n F) = 0, (C n F) = {a, b, d, e, f}, (C u F) = 5 =>

Card (C n F) / Card {C u F) = 0.

(C n G) = {af}, Card(C n G) = 2, (C u G) = {a,b,d,e,f}t Card(C n G) = 5 =>

Card (C n G) / Car (C u G) = 2/5.

Max {[Card (C n F) / Card ÍC u F)], [Card (C n G) / Card (C u G]} =

= Max {0,2/5} = 2/5.

Max {[Card (D n F) / Card co u F)]s [Card (B n G) / Card (D u G]} = 2/5.

Max {[Card (B n F) / Card (E u F)], [Card (E n G) / Card (E u G]} = 1/3.

Các kết quả thu được ở trên có thể viết dưới dạng ma trận sau

F G Max A 0 1/4 1/4 1/3 1/2 1/2 2/5 2/5 D

Như thế ta được hàm V'(I, S) = (1/4 + 1/2 + 2/5 + 2/5 + 1/3)/5 = 113/300, do Card T = 5. Đối với 4(S, T) ta lấy Max theo cột, ta được V(S, T) = (1/3 + 1/2)/3 = 5/12, do Card S = 2. Từ đó, chỉ số bất đồng tính giữa T và S là p(S, T) = 1 - (113/300 + 5/12)/2 = 1 - 119/300 = 181/300 = 0,603. Bây giờ chúng ta hãy chuyển sang một loại khác về quan hệ bất đồng, tính. Cho một tập E, và P(E) là tập các tập con của nó. Lại cho hai tập T và S, T C P(E), S C P(E), trong đó I = 1A;), S = (Bị, i = 1,2,... n, j = 1, 2.., n2, Ai, B ; đều là những tập mờ. Cũng như trước, ta định nghĩa u(T,S) = Card F T E Max (e ? (A n B, Ø)le° (A U B, Ø)). AET BES từ đó, chỉ số bất đồng tính định nghĩa như sau p(T, S) = 1 - 14(T, S) + Y(S, T)H/2. Cũng có thể dùng định nghĩa khác, thay khoảng cách Euclide bằng khoảng cách Hamming. Ví dụ Cho E = {a, b, c, d, el, T = ÍM, N, P}, S = {U, V),

M a b

0.3 0

N a b

0.5 0.1

p a b

1 0,2 u b a

0.3 0.4

V a b

0 0

Ta được ngay các tập mờ sau

Mn u b a

0,3 0

MU u b a

0,3 0,4

từ đó ta được

e2 (M

Tương tự như thế ta tính được

b d e c

1 0 0.4 0,2 b đ c e

0.1 0 0,8 1 d b c e

0 0 0,4 b d c e

1 0.8 0 b d c e

0,4 0.8 0 0 d b c e

0,4 0,8 0 0 b d c e

1 1 0,2

G = la,6}, 1c1. hay là {dì, khi xét tập M. Các công thức cho các tập N và Q cũng tương tự như với M. Với N và Q ta có tương ứng G(N) = la, c, d) hay là 10), khi xét tập N, G'Q ! = la) hay là lb. c. dì, khi xét tập Q. Những điều nói trên có nghĩa là tìm một phân hoạch cụ thể W trong số 15 phân hoạch A1... Als của E sao mà chỉ số bất đồng tính (°) là bé nhất. 1. Với phân hoạch A = A, = la, b. c. d), và M = la, bi, icl, {đì, ta có J(A,) = la, b, c, d), Card A, = 1, và G(M) = {a, bì, lc), hay là Id), Card M = 3. Ta tính riêng từng trường hợp trên. Ta có ") A = A, = J = la. b, c ; d), G, (M) = la, b), Card (d N G,) / Card (d U G,) = Card la, b) / Card la, b, c, dy = 2/4 = 1/2, B, A = A, = e = la, o, c, di, Gz (Il) = 1ct, Card (d N Gz) / Card (J U Gz) = Card (c) / Card (a, b, c, d) = 1/4, ") A = A, = la, b, c, d) = J, Gz (M) = (d), Card (J N G3) / Card (J U G3) = Card (d) / Card la, b, c, d) = 1/4. Từ đó ta được Max (Card (J N G) / Card (d/ U G) } = Max (1/2, 1/4, 1/4} = 1/2, GEM ¿ Max {Card (J ^ G) / Card (J U G)) = JEACEM = Max (Card (J n G) / Card (J U G)) = 1/2, GEM do J= A = Ay, từ đó y(A, M) = (CardA) ' 2 Max | {Card (J n G) / Card (J U G)| = JEAGEM = (1/1). (1/2) = 1/2. Tương tự như thế, ta được

y(M, A) = (CardM) ' ¿ Max {Card (J n G) / Card (J U G)} = GEMJEA

= (1/3) (1/2 + 1/2 + 1/4), từ đó ta được chỉ số bất đồng tính giữa M và A, p(M, A,) = 1 - (1/2) {(1/3) (1/2 + 1/4 + 1/4) + (1/1) (1/2)} = 1 - 5/12 = 7/12. Các kết quả trên có thể viết lại dưới dạng Bảng sau

J(AI) 1 G(M) → ab d Max abcd 1/2 1/4 1/4 1/2 фр (М, А1) = = 1 - (1/2) {(1/3) (1/2 + 1/4 + 1/4) + + (1/1) (1/2)}_ = = 1 - 5/12 = 7/12 Max 1/2 1/4 1/4

J(A1) 1 G(N) → acd b Max • abcd 3/4 1/4 3/4 4р (N, A1, A) = = 1 - (1/2) {(3/4) (3/4 + 1/4) + + (1/1) (3/4)} = = 1 - 5/8 = 3/8

Max 3/4 1/4

J(A1) 1 G(Q) → a bcd Max abcd 1/4 3/4 3/4 4 (Q, A1) = = 1 - (1/2) {(1/2) (1/4 + 3/4) + + (1/1) (3/4)} = = 1 - 5/8 = 3/8

Max 1/4 3/4

Từ đó đẳng thức (*) cụ thể sẽ là + (318) (3/8) + (4/8) (3/8) = 0,40. W(A,) = (1/8) (7/12)

J(Az) V G(M) → ab d Max abc 2/3 1/3 2/3 Ф (N, A2) = d 0 1 = 1 - (1/2) {(1/3) (2/3 + 1/3 + 1) + + (1/2) (2/3 + 1)} = = 1 - 3/4 = 1/4

Max 2/3 1/3 1

J(A2) d G(N) → acd b Max abc 1/2 2/3 2/3 •(N. A2) 1 - (1/2) {(1/2) (1/2 + 1/3) d 1/3 1/3 + (1/2) (12 + 1/3) = = 1 - 5/12 = 7/12 Max 1/2 1/3

J(A2)1 G(Q) → b i bcd Max abc 1/3 1/2 1/2 p (Q. A2) = d 0 1/3 1/3 = 1 - (1/2) {(1/2) (1/3 + 1/2) + + (1/2) (1/2 + 1/3)} = = 1 - 5/12 = 7/12. Max 1/3 1/2

Đẳng thức (*) trong trường hợp này sẽ là WIA.) = (1/8) (1/4) + (3/8) (7/12) + (4/8) (7/12) = 13/24 = 0,54. Tiếp tục tính như thế, cuối cùng ta được

4 (М, Аз) = 1/4 y (N, A3) = 7/12 4 (Q, А3) = 7/12

W(A3) = (1/8) (1/4) + (3/8) (7/12) + (4/8) (7/12) = 13/24 = 0,54.

r (M, A4) = 43/72 Ф (N, A4) = 0 p (Q, A4) = 7/12 W(A4) = (1/8) (43/72) + (3/8) (0) + (4/8) (7/12) = 0,36.

4 (M, A5) = 43/72 Ф (N, A5) = 7/12 4 (Q, A5) = 0

W(A5) = (1/8) (43/72) + (3/8) (7/12) + (4/8) (0) = 13/24 = 0,29.

p(M, A6) = 7/24 Ф (N, AG) = 5/12 ф(Q, А6) = 5/12 W(AG) = (1/8) (7/12) + (3/8) (5/12) + (4/8) (5/12) = 0,40.

p (M, A7) = 19/36 4 (N, A7) = 5/12 Ф(Q, Аз) = 5/12 W(A7) = (1/8) (19/36) + (3/8) (5/12) + (4/8) (5/12) = 13/24 = 0,43.

Ф (М, Aa) = 19/36 4 (N, A3) = 5/12 p(Q, A3) = 5/12

W(A8) = (1/8) (19/36) + (3/8) (5/12) + (4/8) (5/12) = 13/24 = 0,43.

ф (M, Ag) = 0 p (N, Ag) = 43/72 4(Q, A9) = 43/72

W (Ag) = (1/8) (0) + (3/8) (43/72) + (4/8) (43/72) = 0,52.

4 (M, A10) = 1/3 4 (N, A10) = 1/4 Ф(Q, A10) = 43/72

W(A10) = (1/8) (1/3) + (3/8) (1/4) + (4/8) (43/72) = 0,43.

4 (M, А11) = 1/3 ф (N, A11) = 1/4 4 (Q, A11) = 43/72

W(A11) = (1/8) (1/3) + (3/8) (1/4) + (4/8) (43/72) = 0,43.

ф (M, A12) = 1/3 p (N, A12) = 43/12 p(Q, A12) = 1/4

W(A3) = (1/8) (1/3) + (3/8) (43/72) + (4/8) (1/4) = 0,39.

p(M, A13) = 1/3 fp(Q, A13) = 1/4 I p(Q, A13) = 1/4

^13) = (1/8) (1/3) + (3/8) (43/72) + (4/8) (1/4) = 0,39.

p(M, A-u) = 1/2 p(N, A14) = 1/4 p(Q, A14) =1/4 w(Ai4) = (1/8) (1/2) + (3/8) (1/4) + (4/8) (1/4) = 0,28.

p(M, A15) = 5/24 p(N, A15) = 5/12 p{Q, A15) = 5/12

MA15) = (1/8) (5/24) + (3/8) (5/12) + (4/8) (5/12) = 0,39.

Ta thấy rằng lượng W(Ai) = 0,28 là bé nhất với AI.

KẾT LUẬN

Sự tích hợp ba quan hệ đã cho M> N, Q - với sự cân nhắc p(M), p(N), p(Q) cụ thể trên và với khái niệm khoảng cách trên - thành quan hệ ÀI4 = {{c, d}, fal, (ô}};sẽ là tốt nhất.

TÍCH HỢP

{M, N, Q} & A14 = {{c, d}, {a}, {b}}

{p(M), p(N), P(Q)