1

Trường Đại học Nông nghiệp Hà Nội
Khoa Công nghệ thông tin
PGS.TS. NGUYỄN HẢI THANH

CÁC THUẬT TOÁN GIẢI BTQHTT ĐA MỤC TIÊU
VÀ RA QUYẾT ĐỊNH NHÓM
cho hệ hỗ trợ ra quyết định quy hoạch và cân đối quỹ đất


khảo sát hoặc là các cơ hội mới cũng như các đòi hỏi cho chất lượng tổng thể và chất lượng
thông tin cần thiết nhằm xác định rõ vấn đề. Ở pha thiết kế, người ra quyết định phát triển một
bản mô tả và phác hoạ mô hình để có thể kiểm tra một cách hệ thống quá trình khám phá và giải
quyết vấn đề. Pha thiết kế bao gồm việc phát sinh các tiêu chuẩn quyết định và các phương án
quyết định, xác định các sự kiện không kiểm soát được có liên quan cũng như mô tả các quan
hệ giữa tiêu chuẩn, phương án và sự kiện. Pha thiết kế cũng sử dụng các mô hình xử lí định
lượng để đánh giá logic các phương án được mô tả và sinh ra các hành động gợi ý chuyển sang
pha chọn lựa quyết định. Trong pha chọn lựa, người ra quyết định sẽ phải cân nhắc các phân
tích và các đánh giá về các quyết định, đánh giá các kết quả hành động ra quyết định, xác định
độ tin cậy trong các quyết định, xây dựng kế hoạch triển khai, và bảo mật các nguồn lực cần
thiết trước khi thực thi kế hoạch. Sau khi lựa chọn cuối cùng (quyết định cuối cùng) được thực
hiện, người ra quyết định nên quan sát kết quả thực tế và ghi nhận khâu nào phù hợp hoặc
chưa phù hợp, theo các pha của quy trình ra quyết định là tri thức, thiết kế, chọn lựa, và triển
khai. Kết quả đầu ra sẽ có được sau khi chọn lựa cuối cùng được triển khai.
1.2. Kiến trúc của một hệ hỗ trợ quyết định
Khái niệm về kiến trúc của một hệ hỗ trợ quyết định được hiểu khá đa dạng và khác
nhau tùy theo từng tác giả. Theo Power (trích dẫn theo Mora và cộng sự, 2003), hệ hỗ trợ quyết
định bao gồm bốn thành phần chính: giao diện người sử dụng, cơ sở dữ liệu, các mô hình và công
cụ phân tích, thành phần cuối cùng là kiến trúc và mạng của hệ hỗ trợ quyết định. Còn Marakas
lại đề xuất một kiến trúc gồm năm thành phần riêng biệt: Hệ thống quản lí dữ liệu, hệ thống quản
lí mẫu, bộ máy tri thức, giao diện người sử dụng và người sử dụng (trích dẫn theo Mora và cộng
sự, 2003). Hiện nay, có nhiều hệ thống thông tin đã được phát triển để đưa ra sự hỗ trợ cho
người sử dụng trong các bước của quy trình ra quyết định (Nguyễn Khang, 2004). Dựa vào
chức năng hỗ trợ của các hệ thống đó Manuel Mora và cộng sự, 2003, đã đưa ra cách phân
loại như sau: Hệ hỗ trợ quyết định (DSS), Hệ thống xử lí thông tin (EIS), Hệ cơ sở tri thức
(KBS), Hệ máy học (MLS), Hệ tăng cường tính sáng tạo (CES). Mỗi hệ thống trên sẽ góp
phần giải quyết một số khâu nhất định trong quy trình ra quyết định. Việc tích hợp được các
hệ thống đó với nhau là giải pháp tốt nhằm tạo ra một hệ hỗ trợ ra quyết định hoàn chỉnh.

Trong một hệ hỗ trợ ra quyết định, dữ liệu bài toán có thể có từ nguồn bên ngoài hoặc

phép của thực tế. Trước đây và cũng như hiện nay, bài toán quy hoạch tuyến tính (BTQHTT)
được sử dụng rất rộng rãi để thiết kế các tiêu chuẩn ra quyết định trong nhiều lĩnh vực quản lí
và công nghệ, đặc biệt trong các vấn đề quản lí và quy hoạch đất đai. BTQHTT có dạng tổng
quát như sau:
Max (Min) z = c
1
x
1
+ c
2
x
2
+ + c
n
x
n

với các điều kiện ràng buộc
a
11
x
1
+ a
12
x
2
+ + a
1n
x
n

n
Θ b
m

x
1
Θ 0, x
2
Θ 0, , x
n
Θ 0.
Trong đó ký hiệu Θ có thể hiểu là ≤ , ≥ hoặc = đối với các ràng buộc. Đối với điều
kiện về dấu của các biến Θ 0 có thể hiểu là ≥ 0, ≤ 0 hoặc có dấu tuỳ ý. BTQHTT chỉ có đúng
một mục tiêu, các mục tiêu khác (nếu có) đều cho dưới dạng các điều kiện ràng buộc. Có rất
nhiều thuật toán giải BTQHTT, nhưng thuật toán hai pha là thuật toán điển hình và được áp
dụng rộng rãi nhất.
Trong nhiều trường hợp các mô hình toán học, trong đó có bài toán quy hoạch tuyến
tính đa mục tiêu có thể được áp dụng. Trong các bài toán công nghệ, quản lí nảy sinh từ thực
tế, chúng ta thường phải xem xét để tối ưu hoá đồng thời một lúc nhiều mục tiêu. Việc giải các
bài toán tối ưu đa mục tiêu, tức là tìm ra một phương án khả thi tốt nhất theo một nghĩa nào đó,
thực chất chính là một bài toán ra quyết định. Bài toán quy hoạch tuyến tính (BTQHTT) đa
mục tiêu với p mục tiêu có dạng sau:
Max (Min) z = c
i1
x
1
+ c
i2
x
2

2n
x
n
Θ b
2a
m1
x
1
+ a
m2
x
2
+ + a
mn
x
n
Θ b
m

x
1
Θ 0, x
2
Θ 0, , x
n
Θ 0.
4

ra quyết định. Hai thành phần rất quan trọng chính là:
− Thuật toán giải BTQHTT một mục tiêu và đa mục tiêu.
− Thuật toán ra quyết định nhóm hay còn gọi là ra quyết định tập thể.
Trong các hệ hỗ trợ ra quyết định quy hoạch và cân đối quỹ đất, các thuật toán trên
giúp tìm ra các phương án hợp lí và ra quyết định đúng đắn để chọn lựa ra một (hoặc) một số
phương án tốt nhất.
5

II. THUẬT TOÁN GIẢI BTQHTT MỘT MỤC TIÊU VÀ ĐA MỤC TIÊU
2.1. Thuật toán đơn hình hai pha giải BTQHTT một mục tiêu
Xét bài toán gốc: z =
n
j 1
=
∑
c
j
x
j
→ Min/ Max
với các ràng buộc (giả sử các biến đều không âm)

n
ij j i
j 1
n
ij j i
j 1
n
ij j i




=


≥



Bước 1:
- Nhập dạng bài toán Min / Max và đưa các biến về dạng không âm.
- Nhập tổng số ràng buộc m bao gồm các ràng buộc mang dấu:
≤ (m
1
ràng buộc) , ≥ (m
2
ràng buộc) và = (m
3
ràng buộc).
- Nhập số biến: n biến.
- Nhập véc tơ hệ số hàm mục tiêu: C = [ c
1
, c
2
, . . ., c
n
].
- Nhập véc tơ hệ số vế phải: b = [ b
1,

,

Biến giả: m
2
+ m
3
biến x
n+m1+m2+q
,
2 3
q 1,m m
= +
.
Nếu m
2
+ m
3
= 0, chuyển sang bước 4.
Nếu m
2
+ m
3
≠ 0, giải bài toán theo hai pha bằng cách chuyển sang bước 3.
Bước 3: Pha thứ nhất.
Xây dựng và giải bài toán phụ:
ω =
m2 m3
q
+
∑
Giải pha I

Tính
∆
k

Giải pha II

bị chặn, BT vô nghiệm

Tìm phần tử
xoay

Chuyển đổi

cơ sở
N
Y
Tìm hàng xoay

Tính
f(X
)

BT có nghiệm

Tính
∆
k

Y
N
Có biến giả
?

∃
k,
∆

pha
II

Hình II.1. Sơ đồ thuật giải đơn hình hai pha
7

Kết thúc pha 1 có thể xảy ra ba trường hợp sau đây:
− Phương án tối ưu không có biến giả, lấy đó làm phương án xuất phát, thay lại hệ số
hàm mục tiêu, loại trừ các cột biến giả và sang bước 4.
− Phương án tối ưu có biến giả khác 0 thì bài toán tối ưu không có phương án. Dừng.
− Phương án tối ưu có chứa biến giả nhưng biến giả bằng 0, xoá các dòng chứa các
biến giả này, thay lại hệ số hàm mục tiêu, loại trừ các cột biến giả và sang bước 4.
Bước 4: Pha thứ 2.
Giải bài toán gốc với phương án xuất phát tìm được bằng phương pháp đơn hình.
Bước 5: In kết quả .
Sơ đồ thuật giải cho BTQHTT gốc là bài toán Max được cho trên hình II.1.

2.2. Thuật giải đơn hình giải BTQHTT dạng chính tắc
Thuật toán hai pha trên đây đã sử dụng một thủ tục để giải BTQHTT dạng chính tắc.
Sau đây là phát biếu về BTQHTT dạng chính tắc và thuật giải đơn hình:
Max z = c
1
x
1
+ c
2
x
2
+ + c
n

x
1
+ a
22
x
2
+ + a
2n
x
n
+ x
n+2
= b
2 a
m1
x
1
+ a
m2
x
2
+ + a
mn
x
n
+ x
n+m

)
T
.
– Đặt chỉ số biến cơ sở: r(1) = n + 1, , r(m) = n + m.
– Gán x
r(i)
= b
i
, i =
1,m
.
– Đặt flag = 2.
Các bước lặp
Bước 1:
– Tính c
T
x = z = d
1
x
r(1)
+ + d
m
x
r(m)
.
– Tính z
j
=
m
pj p

B
–1
B], trong đó ∆
B
= 0. Như vậy ∆
j
= c
j
– z
j
,
với z
j
=
m
pj p
p 1
a d
=
∑
, ∀j ∈ N và ∆
j
= c
j
– z
j
= 0, ∀j ∈ B, (tức là z
N
=
T

= ∀ >
 
 
.
Trong tr
ường hợp không tồn tại a
is
> 0, đặt flag = 0 và chuyển sang bước kết thúc.
8

– Xác định phần tử xoay a
qs
.
– Tính lại (để chuyển sang bảng đơn hình mới): b
q
:= b
q
/a
qs
, a
qj
:= a
qj
/a
qs
, ∀j . ∀ i ≠ q
tính lại b
i
:= b
i

i
i
)
)=
=b
b
i
i,
,i
i=
=1,m
.

một mục tiêu nào đó bài toán không cho phương án tối ưu thì cần xem xét để chỉnh sửa lại
các điều kiện ràng buộc ban đầu).
ii) Tính giá trị các hàm mục tiêu tại p phương án x
1
, x
2
, , x
p
và lập bảng pay−off.
Xác định giá trị cận trên
B
i
z
và giá trị cận dưới
w
i
z
của mục tiêu z
i
(i =1, 2, , p), với
B
i
z
=
z
i
(x
i
) và
w

µ = =
−

iv) Đặt: S
P
= {x
1
, x
2
, , x
p
}, k :=1 và
(k)
i
a
=
B
i
z
với i = 1, 2, , p.
Các bước lặp (xét bước lặp thứ k)
Bước 1:
i) Xây dựng hàm thoả dụng tổ hợp từ các hàm thoả dụng trên:
u = w
1
µ
1
(z
1
) + w

, , w
p
≤ 1.
ii) Giải BTQHTT với hàm thoả dụng tổ hợp với m ràng buộc ban đầu và p ràng buộc
bổ sung z
i
(x) ≤
(k)
i
a
, i = 1, 2, , p, để tìm được phương án tối ưu của bước lặp thứ k là x
(k)

và giá trị của các hàm mục tiêu z
i
cũng như của các hàm thoả dụng µ
i
(z
i
) (với i =1, 2, , p).
Bước 2:
i) Nếu µ
min
= Min {µ
i
(z
i
): i = 1, 2, , p} bé hơn một ngưỡng t nào đó (t được lựa
ch
ọn trong đoạn [0, 1] và có thể được sửa chỉnh lại trong quá trình giải bài toán) thì phương

a
=
B
i
z
với i = 1, 2, , p và chọn ngẫu nhiên
một chỉ số h ∈ {1, 2, , p} để đặt lại giá trị cắt
(k)
h
a
∈ (
w
h
z
,
B
h
z
].
Quay về bước 1.
iii) Nếu người giải bài toán không muốn mở rộng tập S
P
thì chuyển sang bước 3.
Bước 3:
i) Loại khỏi tập S
P
các phương án bị trội.
ii) Kết thúc.

2.4. Trường hợp khảo sát 1

X_1_2_5*1 + X_1_2_6*1 = 4680.41
X_2_1_3*1 = 2135.53
X_3_1_1*1 + X_3_1_2*1 + X_3_2_3*1 + X_3_2_4*1 + X_3_2_5*1 + X_3_2_6*1 = 319.36
X_4_1_1*1 + X_4_2_2*1 + X_4_2_3*1 + X_4_2_4*1 +X_4_2_5*1 + X_4_2_6*1 = 640.3
X_5_2_1*1 + X_5_1_2*1 + X_5_2_3*1 + X_5_2_4*1 + X_5_2_5*1 + X_5_2_6*1 = 188.67
X_6_2_1*1 + X_6_2_2*1 + X_6_2_4*1 = 3.08
X_7_2_1*1 + X_7_2_2*1 + X_7_2_4*1 + X_7_2_5*1 + X_7_2_6*1 = 575.61
10
X_8_2_1*1 + X_8_2_2*1 + X_8_2_3*1 + X_8_2_4*1 = 11.93
X_9_2_1*1 + X_9_2_2*1 + X_9_2_3*1 + X_9_2_4*1 + X_9_2_6*1 = 597.64
X_10_2_1*1 + X_10_2_2*1 + X_10_2_3*1 + X_10_2_4*1 + X_10_2_5*1 + X_10_2_6*1 =
1163.15
Các ràng buộc tương quan tỷ lệ
X_3_1_1*1 + X_4_1_1*1 + X_5_2_1*1 + X_6_2_1*1 + X_7_2_1*1 + X_8_2_1*1 +
X_9_2_1*1 + X_10_2_1*1 ≤ 3499.74
X_3_1_2*1 + X_4_2_2*1 + X_5_1_2*1 + X_6_2_2*1 + X_7_2_2*1 + X_8_2_2*1 +
X_9_2_2*1 + X_10_2_2*1 ≤ 3499.74
X_2_1_3*1 + X_3_2_3*1 + X_4_2_3*1 + X_5_2_3*1 + X_8_2_3*1 + X_9_2_3*1 +
X_10_2_3*1 ≤ 5056.58
X_3_2_4*1 + X_4_2_4*1 + X_5_2_4*1 + X_6_2_4*1 + X_7_2_4*1 + X_8_2_4*1 +
X_9_2_4*1 + X_10_2_4*1 ≤ 3499.74
X_1_2_5*1 + X_3_2_5*1 + X_4_2_5*1 + X_5_2_5*1 + X_7_2_5*1 + X_10_2_5*1 ≤ 7567.5
X_1_2_6*1 + X_3_2_6*1 + X_4_2_6*1 + X_5_2_6*1 + X_7_2_6*1 + X_9_2_6*1 +
X_10_2_6*1 ≤ 8165.14
Ràng buộc về mức độ sử dụng lao động
X_1_2_5*401 + X_1_2_6*371 + X_2_1_3*860 + X_3_1_1*892 + X_3_1_2*858 +
X_3_2_3*860 + X_3_2_4*893 + X_3_2_5*401 + X_3_2_6*371 + X_4_1_1*892 +
X_4_2_2*858 + X_4_2_3*860 + X_4_2_4*893 + X_4_2_5*401 + X_4_2_6*371 +
X_5_2_1*892 + X_5_1_2*858 + X_5_2_3*860 + X_5_2_4*893 + X_5_2_5*401 +
X_5_2_6*371 + X_6_2_1*892 + X_6_2_2*858 + X_6_2_4*893 + X_7_2_1*892 +

B w
i i
z z
(z ) , i 1, 2, 3.
z z
−
µ = =
−

Các bước lặp
Hàm thoả dụng tổ hợp được xây dựng từ các hàm thoả dụng trên:
u = w
1
µ
1
(z
1
) + w
2
µ
2
(z
2
) + w
3
µ
3
(z
3
) → Max.

tiêu: Z1 = 157005887.4, Z2 = 3283.86, Z3 = 20370.8957.
Nếu W1 = 0.6, W2= 0.2, W3 = 0.2. Kết quả thu được cho biết giá trị các hàm mục
tiêu: Z1 = 181719693.44, Z2 = 3283.8, Z3 = 17007.0429.
Người sử dụng muốn giá trị hàm mục tiêu Z1 nhỏ hơn một ngưỡng nào đó, giá trị này
phải nằm trong khoảng Z1
Max
, Z1
Min
. Người sử dụng phải nhập giá trị cắt cho hàm mục tiêu
Z1 nằm trong khoảng (110565323.94, 199639407.68), chẳng hạn là 180000000. Chọn W1 =
0.4, W2 = 0.3, W3 = 0.3. Kết quả giải bài toán: X_1_2_6 = 4680.41 | X_2_1_3 = 2135.53 |
X_3_1_1 = 319.36 | X_4_1_1 = 640.3 | X_5_1_2 = 188.67 | X_6_2_1 = 3.08 | X_7_2_6 =
575.61 | X_8_2_3 = 11.93 | X_9_2_3 = 597.64 | X_10_2_3 = 1163.15 | s[53] = 2537 | s[54] =
3311.07 | s[55] = 1148.33 | s[56] = 3499.74 | s[57] = 7567.5 | s[58] = 2909.12 | s[59] =
22994112.6 | s[60] = 1163.15 | s[61] = 3831721.36 | s[62] = 2135.53 | s[63] = 319.36 | s[64] =
640.3 | s[65] = 188.67 | s[66] = 3.08 | s[67] = 4680.41 | s[68] = 11.93 | s[69] = 597.64 | s[70] =
575.61, các biến khác có giá trị bằng 0. Giá trị các hàm mục tiêu: Z1 = 157005887.4, Z2 =
3283.86, Z3 = 20370.8957.

2.4. Nhận xét về phương pháp thoả dụng mờ tương tác
Đây là phương pháp dễ lập trình, có tác dụng giúp người ra quyết định đưa được các
mục tiêu khác nhau về cùng một thang bậc thoả dụng (từ 0% tới 100%). Do đó phương pháp
có ưu điểm nổi bật là giúp giải quyết được các BTQHTT với các mục tiêu khác nhau về đơn
vị đo. Ngoài ra, phương pháp cho phép tìm kiếm các phương án tối ưu một cách linh hoạt
bằng cách sử dụng các lát cắt bổ sung.
Như vậy phương pháp giúp đưa ra được nhiều phương án hợp lí để tăng thêm thông
tin cho bộ máy ra quyết định. Chẳng hạn, trong trường hợp khảo sát trên đây, phương pháp đã
tạo ra được năm phương án tối ưu (hai phương án đã bị loại do có các phương án khác “trội”
hơn) để đưa vào chọn lựa.
12

p
∈ [0,1] ∀ p.
Tính r
ij
theo một trong hai công thức r
ij
=
[
]
)x(U)x(U1
2
1
ji
−+
hoặc tính theo công thức r
ij

= U(x
i
)/ [U(x
i
)+U(x
j
)] , ∀i, j để xác định độ trội hơn /hay kém hơn của phương án (tập hợp
các giá trị r
ij
cũng đồng thời xác định một quan hệ ưu tiên mờ). Dễ thấy r
ij
∈ [0,1] ∀ i, j.
Bước 2. Tính

13
− Tận dụng được tri thức của các chuyên gia trong nhiều lĩnh vực khác nhau, với các
nhận biết, cảm nhận khác nhau về cùng một vấn đề.
− Giúp các chuyên gia cân nhắc và xem xét sửa chỉnh lại các đánh giá mang tính chủ
quan của mình.
− Đưa ra một quy trình giả khách quan nhằm phân cụm các ý kiến trong từng bước, và
làm cho các ý kiến hội tụ về một cách đánh giá thống nhất.
So với thuật toán Delphi gốc của Kaufmann A. và Gupta, 1991, thuật toán Delphi cải
biên khác ở hai điểm:
− Các chuyên gia sắp hạng các phương án bởi số mờ chứ không phải số rõ. Điều này
làm cho sự đánh giá được “mềm” hơn, thực tế hơn.
− Bằng cách áp dụng phương pháp phân cụm dữ liệu, thông tin sau mỗi bước lặp cung
cấp cho các chuyên gia không chỉ bao gồm thông tin về điểm trung bình cộng toán nhóm của
từng phương án, mà còn bao gồm cả điểm trung bình (là số mờ) trong các lớp cụm có chứa
nhiều ý kiến. Điều này giúp cho việc sửa chỉnh lại các đánh giá của từng chuyên gia trong
bước lặp tiếp theo được thuận lợi hơn.
Phân cụm các dữ liệu số thông thường như đã quen biết trong đa số các chuyên ngành
nghiên cứu hiện nay được gọi là phân cụm dữ liệu rõ (crisp data). Khi thu thập dữ liệu, ta
thường tiến hành phương pháp chọn mẫu A gồm n cá thể. Bằng cách định lượng hoá các đặc
tính của các cá thể đó, mỗi cá thể sẽ ứng với một bộ m số tương ứng với m đặc tính được xem
xét. Bài toán phân cụm đặt ra ở đây là đưa vào một khái niệm hàm khoảng cách d thích hợp
nhằm đánh giá "độ gần gũi" giữa các cá thể đó, từ đó có thể xem xét và đề xuất các phương
pháp phân cụm / phân loại phù hợp. Giả sử ta đã quyết định phân cụm mẫu A ra l lớp. Dựa
trên hàm khoảng cách đã đề ra, cần tìm được phân cụm tối ưu của tập mẫu A theo một nghĩa
nào đó. Sau đây là hai tiêu chuẩn quan trọng, tiêu chuẩn khoảng cách (trọng tâm) cực tiểu và
tiêu chuẩn bình phương bé nhất thường được dùng trong thực tế.
Cho A = { a
1
, a
2

1,n
} trong phân hoạch C.
i
n
i i j
j 1
1
a a
n
=
=
∑
là trọng tâm của lớp C
i
. Đặt l(C
i
) =
i
n
2
ij i
j 1
d (a , a )
=
∑
thì D (C)
=
∑∑∑
=
===

thông thường) từ mỗi phần tử của A tới trọng tâm của lớp (mà nó thuộc vào) đạt giá trị bé
nhất (tức là nếu xét một phân hoạch bất kỳ C có cùng số lớp l , ta luôn có D(C
*
) ≤ D(C)).
Định nghĩa: Phân hoạch C
*
= {C
1
*
, C
2
*
, , C
l
*
} được gọi là phân hoạch với khoảng
cách cực tiểu nếu ∀a
ij
(*)
∈ C
i
*
thì
(*) (*)
ij i ij r
d(a ,a ) d(a ,a )
≤
∀ r ≠ i. Như vậy nếu C
*
là phân hoạch

l
i
i 1
n
=
∑
= n.
− Chọn sai số ε dương đủ bé.
− Tính D(C
0
). Chọn biến đếm k, bắt đầu từ 0 và chọn hằng k
max
> 0.
Các bước lặp (bước lặp thứ k)
Bước 1: Với C
i
(k)
={a
i1
(k)
,…, a
i,ni
(k)
}, tính
i
n
(k) (k)
i ij
(k)
j 1

các trọng tâm
(k)
i
a
với i =
1,l
của các lớp trong phân hoạch C
k
, cần tạo nên lớp C
i
(k+1)

trong
phân hoạch mới C
k+1
.
Bước 3: Tính D(C
k+1
). Nếu D (C
k+1
) < D(C
k
) - ε và k < k
max
thì thay k bởi k+1 rồi
quay về bước 1. Nếu trái lại (các trường hợp khác), dừng và in ra phân hoạch xấp xỉ tối ưu.
Phân loại dữ liệu mờ
Ngày nay, trong nhiều tình huống thu thập, xử lí, quản lí dữ liệu và ra quyết định, các
phương pháp phân loại đối với các dữ liệu số thông thường (dữ liệu rõ) như đã biết cũng đã tỏ
ra thiếu phù hợp. Đó là vì, các dữ liệu thu thập được trên thực tế thường chứa đựng các độ bất


C
2

x

µ
·

A
1
A
2
Hình III.1. Tính khoảng cách giữa hai số mờ

15
Định nghĩa: Xét hai số mờ dạng tam giác ã
1
= (x
B1
,x
A1
,x
C1
), ã
2
=(x
B2
,x
A2

D
1
và A
2
B
2
C
2
D
2
, với D
1
rất sát gần A
1
và D
2
rất sát gần A
2
. Tuy
nhiên, có thể xây dựng được các tứ giác A
1
B
1
C
1
D
1
và A
2
B

Tính chất 1. d(ã
1
, ã
2
) = d(ã
2
, ã
1
) (≥ 0)
Tính chất 2. d(ã
1
, ã
3
) ≤ d(ã
1
, ã
2
) + d(ã
2
, ã
3
) ∀ ã
1
, ã
2
, ã
3
.
Trong một số trường hợp, có thể dùng khoảng cách quy chuẩn giữa hai số mờ: d*(ã
1

không nên triển khai. Điều này cho phép các chuyên gia đưa ra ý kiến một cách tương đối dễ
dàng. Giả sử các mức đó có thể minh hoạ bằng các số mờ một chiều là: (0.9, 0.95, 1.0), (0.7,
0.8, 0.9), (0.5, 0.6, 0.7), (0.3, 0.4, 0.5), (0.1, 0.2, 0.3) và (0, 0.05, 0.1). Chẳng hạn, (0.9, 0.95,
1.0) có nghĩa là phương án được đánh giá rất tốt, thỏa mãn được từ 90% tới 100% mong
muốn của chuyên gia, mà trong giải này thì 95% mức mong muốn là đạt được với khả năng
nhiều nhất.
Thuật giải Delphi cải biên xử lí và tổng hợp ý kiến chuyên gia
Bước khởi tạo
− Xin ý kiến n chuyên gia đánh giá một phương án ở các mức: rất tốt, tốt, khá phù
hợp, không phù hợp, kém hiệu quả, không nên triển khai.
− Chọn l là số lớp để phân hoạch ý kiến các chuyên gia, thông thường chọn l = 3 hoặc l = 4.
− Chọn k
max
là số bước lặp tối đa cần thực hiện (thông thường chọn k
max
= 10 đến 15.
Đặt k = 1.
Các bước lặp
Bước 1: Sử dụng phương pháp phân loại dữ liệu căn cứ vào thuật giải xấp xỉ dựa trên
các tiêu chuẩn khoảng cách cực tiểu và bình phương bé nhất đã biết (dùng công thức tính
khoảng cách θ(ã
1
,ã
2
) giữa hai số mờ ã
1
,ã
2
là các giá trị lượng hoá hai ý kiên khác nhau)
Bước 2:

), cần tính chỉ số C
f
=
0.5(x
1
– x
2
+ z
1
– z
2
) + (y
1
– y
2
). Nếu C
f
> 0 thì phương án A được coi là tốt hơn phương án
B, nếu C
f
< 0 thì A xấu hơn B, còn nếu C
f
= 0 thì A và B ngang nhau.

3.3. Trường hợp khảo sát 2
Ra quyết định nhóm lựa chọn phương án tốt nhất phục vụ quy hoạch sử dụng đất sản
xuất nông nghiệp trên địa bàn Tam Nông, Phú Thọ bằng thuật giải Delphi cải biên
Theo mục 2.3 và 2.4. sau khi giải BTQHTT với ba mục tiêu, thuật giải thoả dụng mờ
tương tác đưa ra năm phương án tối ưu Pareto như được tổng hợp trên bảng III.1 (hai phương
án đã bị loại do có các phương án khác “trội” hơn). Đó là các phương án thu được khi giải

3283.86

17007.04

Các chuyên gia nhập ý kiến đánh giá 05 phương án này một cách đồng thời. Giả sử
bài toán 5 chuyên gia đánh giá và số bước lặp tối đa cho phép là 5 bước, số lớp trong một
phân hoạch là 3.
Bước lặp thứ 1: Ý kiến chuyên gia được tổng hợp trong bảng III.2. Chẳng hạn đối với
phương án 1, ý kiến đánh giá của các chuyên gia 1, 2, 3, 4 và 5 lần lượt là: tốt, rất tốt, khá phù
hợp, tốt và tốt. Chú ý rằng các mức đánh giá rất tốt, tốt, khá phù hợp, không phù hợp, kém
hiệu quả, không nên triển khai được định lượng bằng các số mờ một chiều là: (0.9, 0.95, 1.0),
(0.7, 0.8, 0.9), (0.5, 0.6, 0.7), (0.3, 0.4, 0.5), (0.1, 0.2, 0.3) và (0, 0.05, 0.1).
Bảng III.2. Ý kiến các chuyên gia bước lặp 1
Chuyen
Gia
PhuongAn1 PhuongAn2 PhuongAn3 PhuongAn4 PhuongAn5
cg1 Tốt Không phù
hợp
Kém hiệu quả Khá phù hợp Rất tốt
cg2 Rất tốt Không phù
hợp
Không phù
hợp
Tốt Tốt
cg3 Khá phù
hợp
Không phù
hợp
Không phù
hợp

Không phù
hợp
Tốt Tốt
cg3 Tốt Không phù
hợp
Không phù
hợp
Khá phù hợp Tốt
cg4 Tốt Kém hiệu quả Kém hiệu quả Khá phù hợp Tốt
cg5 Tốt Không phù
hợp
Không phù
hợp
Khá phù hợp Rất tốt
Kết quả sau bước lặp thứ hai :
0.7 , 0.8 , 0.9 0.3 , 0.4 , 0.5 0.3 , 0.4 , 0.5 0.5 , 0.6 , 0.7 0.7 , 0.8 , 0.9
0.74 , 0.83 , 0.92 0.26 , 0.36 , 0.46 0.22 , 0.32 , 0.42 0.54 , 0.64 , 0.74 0.78 , 0.86 , 0.94
0.74 , 0.83 , 0.92 0.26 , 0.36 , 0.46 0.22 , 0.32 , 0.42 0.54 , 0.64 , 0.74 0.78 , 0.86 , 0.94
Phương án 1, 2 và 4 đã được các chuyên gia thống nhất đánh giá. Phương án 3 và 5
chưa thống nhất được ý kiến chuyên gia, cần phải tiến hành bước lặp tiếp theo.
Bước lặp thứ 3: Ý kiến chuyên gia cho trong bảng III.4.
Bảng III.4. Ý kiến các chuyên gia bước lặp 3
Chuyen
Gia
PhuongAn1 PhuongAn2 PhuongAn3 PhuongAn4 PhuongAn5
cg1 Tốt Không phù
hợp
Không phù
hợp
Khá phù hợp Rất tốt

Phương án : 4 >Khá phù hợp
Trung bình = (0.5,0.6,0.7)
Xấp xỉ = (0.5,0.6,0.7)
Căn cứ vào kết quả giải ta thấy phương án 5 được chuyên gia đánh giá là tốt nhất có ý
kiến trung bình của các chuyên gia là (0.9, 0.95, 1.0). Tiếp theo là phương án 1 có ý kiến
trung bình các chuyên gia là (0.7, 0.8, 0.9). Phương án 4 có ý kiến trung bình (0.5, 0.6, 0.7)
xếp thứ ba. Các phương án trên được lưu trữ và báo cáo lại cho bộ máy quản lý. Sau khi cân
nhắc, phương án 5 được đưa ra triển khai.
3.4. Mô hình ra quyết định tập thể dựa trên toán tử DELOWA
Xét bài toán ra quyết định nhóm khi cần lựa chọn từ tập hợp n phương án quyết định
ra một phương án hợp lí nhất dựa trên ý kiến của m chuyên gia. Kí hiệu:
i) X = {x
1
, , x
n
} là tập các phương án hành động cần lựa chọn.
ii) N = {e
1
, , e
m
} là tập các chuyên gia.
iii) w: N→ [0, 1] là hàm trọng số, đánh giá tầm quan trọng của mỗi chuyên gia, được định
nghĩa bới: e
k
→ w
k
= w(k). Ký hiệu véc tơ các trọng số là w = (w
1
, ,w
m

S
j
.
ii) Tồn tại các toán tử phủ định: Neg(S
i
) = S
j
, j = T +1 – i .
iii) Tồn tại toán tử Max thay cho toán tử hợp: Max {S
i
, S
j
} = S
i
(với S
i
~
f
S).
(Đây là một tính chất còn tranh cãi do chưa tính tới sự bù trừ - compensation)
Như vậy, tập nhãn S xác định một quan hệ mờ ngôn ngữ. Chẳng hạn, nếu S là biến
ngôn ng
ữ Ưu tiên hơn, thì M
R
(x
1
, x
2
) = S
1

< S
T
thì x
i
được ưu tiên rõ ràng hơn x
j
.
− r
ij
= S
(t+1)/2
có

nghĩa là mức ưu tiên giữa x
i
và x
j
là mức bàng quan (ưu tiên như
nhau / không hơn mấy).
Như vậy ứng với mỗi chuyên gia e
k
, có một quan hệ ưu tiên mờ ngôn ngữ P
k
: X×X →
S với tính chất: nếu P
k
(x
i
, x
j

= 1, ∀i≠j
r
ii
= 0 ,
như trong quan hệ ưu tiên mờ.
Các lượng từ mờ không giảm
Trong ngôn ngữ thông thường chúng ta thường gặp các lượng từ ngôn ngữ như: phần
nhiều, ít nhất là 50%, … Cần mô hình hoá các lượng từ này như thế nào?
Định nghĩa: Hàm Q: [0, 1] → [0, 1], được gọi là lượng từ quan hệ nếu Q(0) = 0 và
tồn tại z ∈ [0,1] sao cho: Q(z) =1. Lượng từ quan hệ Q được gọi là lượng từ không giảm nếu
Q(z
1
) ≤ Q(z
2
) một khi z
1
< z
2
.
Ta xét lượng từ không giảm Q
1
[a, b] với a, b ∈ [0, 1] là lượng từ có dạng sau:
Q
1
(z) =
0
(z a) /(b a)
1



tương ứng với Q
1
[a, b] và biến ngôn ngữ S được
xác
định như một hàm nhận giá trị là các nhãn của biến ngôn ngữ S,tức là Q
2
: [0,1] → S với
quy tắc sau:
1

0

0,5
1 z
Hình III.2. Lượng từ quan hệ “ít nhất 50%”
20
S
1
nếu z <a
Q
2
(z) = S
i
nếu a ≤ z ≤ b
S
T
nếu z > b.
Trong đó S
i
= max {S

ó
µ
t
(.) là hàm liên thu
ộ
c xác
đị
nh t
ậ
p m
ờ
S
t
.
Ví dụ:
Xét s
ố
m
ờ
d
ạ
ng t
ứ
giác: S
t
= (a
t
, b
t
, c

 
µ
 
−
 
= µ
t
(0,8) , v
ớ
i a = 0, b = 0,5 và z
= 0,4.
Ứ
ng v
ớ
i l
ượ
ng t
ừ
Q
1
[a, b]
đ
ã bi
ế
t, µ
t
(.)
đ
ánh giá xem v
ớ

đị
nh
trên
đ
ây (S
i
là nhãn mà (z-a)/(b-a) thu
ộ
c vào S
i
v
ớ
i
độ
thu
ộ
c l
ớ
n nh
ấ
t).
Ch
ẳ
ng h
ạ
n v
ớ
i z = 0,4, n
ế
u xét các l

) = (0,93; 0,98; 0,99; 1)
− C (
certain
−
tất nhiên hơn hẳn
) = (1; 1; 1; 1)
thì M = {MC, ML} và do
đ
ó Q
2
(0,4) = ML.
Mô tả tập S
1
, …, S
T

S
t
= (a
t
, b
t
, c
t
, d
t
), v
ớ
i a
1

t
< b
t+1
, c
t
< c
t+1
, d
t
< d
t+1
∀ t .
1
t
µ

a
t
b
t
c
t
u
t
Hình III.3. Số mờ dạng tứ giác: S
t
= (a
t
, b
t

V
ậ
y Q
2
là toán t
ử

đơ
n
đ
i
ệ
u không gi
ả
m.
Các độ đo liên ứng ngôn ngữ
Xét các kí hi
ệ
u:
− T
ậ
p V
ij
[S
t
] = {k: P
k
(i, j) = S
t
, k ∈{1, …, m}} là t

ng c
ủ
a t
ậ
p V
ij
[S
t
]
đượ
c ký hi
ệ
u là N
ij
[S
t
] = V
ij
[S
t
].
−V
ij
là phân ho
ạ
ch c
ủ
a t
ậ
p các chuyên gia khi

] = ∑ w
1
(k)
đượ
c g
ọ
i là t
ổ
ng các tr
ọ
ng s
ố
quy chu
ẩ
n c
ủ
a các
chuyên gia
đồ
ng ý
đ
ánh giá m
ứ
c
ư
u tiên c
ủ
a ph
ươ
ng án x

ố
quy chu
ẩ
n c
ủ
a w. W
ij
(S
t
)
đượ
c g
ọ
i là
tr
ọ
ng l
ự
c c
ủ
a S
t
trong m
ố
i quan h
ệ

ư
u tiên x
i

ứ
c
ư
u tiên gi
ữ
a x
i
và x
j
theo ki
ể
u 2
ứ
ng v
ớ
i m
ỗ
i nhãn S
t
.
Định nghĩa:
IC
2
(i,j) = Max IC
2
(i,j) [S
t
]
đượ
c g

a thu
ậ
n
ư
u tiên ngôn ng
ữ
gi
ữ
a x
i
và x
j

đượ
c xác
đị
nh b
ở
i
PC
2
(i,j)=Q
2
(
)
2
IC (i, j)
.
Độ
liên

2










−
∑
≠
1n
)j,i(IC
ji
2
.
S
ố

đ
o quan h
ệ
th
ỏ
a thu
ậ
n liên

ji
2
i
.
Toán tử tích hợp ngôn ngữ LOWA
LOWA
đượ
c phát tri
ể
n d
ự
a trên toán t
ử
OWA c
ủ
a Yager (1988) và toán t
ử
t
ổ
h
ợ
p l
ồ
i
c
ủ
a Delgalo et al.(1993). Chúng ta trình bày nhanh v
ề
LOWA thông qua ví d
ụ

b
≡ W = (0,5; 0,3; 0,2). Lúc
đ
ó ta có: LOWA(a, W
a
) = Wb
T
=
22
C
3
(W, b) v
ớ
i C
3
= w
1
⊗ b
1
⊕
(1-w
1
)⊗C
2
(W’, b’), trong
đ
ó W
’
thu
đượ

, S
1
)]
= 0,5 ⊗ S
3

⊕
0,5 ⊗(0,6⊗S
2
+ 0,4⊗S
1
) = 0,5 ⊗ S
3

⊕
0,5 ⊗S
k
,
v
ớ
i k = min {T, 1 + round (0,6 ×(2-1))} v
ớ
i 0,6 = w’
2
(tr
ọ
ng s
ố

đ

ủ
a nhãn
cao nh
ấ
t trong các nhãn c
ủ
a bi
ế
n ngôn ng
ữ
S. Cu
ố
i cùng ta có:
LOWA(a,W
a
) = 0,5 ⊗ S
3

⊕
0,5 ⊗S
k
= S
3
.
Chú ý.
N
ế
u w
j
= 1 và w

∈ X’.
Để

đ
o
độ
tr
ộ
i
đị
a ph
ươ
ng c
ủ
a x
i
so v
ớ
i x
j
nói riêng c
ũ
ng nh
ư
so v
ớ
i
t
ấ
t c

ổ
ng tr
ọ
ng s
ố
các chuyên gia
đ
ánh
giá x
i
ít nh
ấ
t
ư
u tiên nh
ư
ho
ặ
c
ư
u tiên h
ơ
n nh
ư
x
j
và
D
2
(x

ứ
ng v
ớ
i S’
đượ
c
đị
nh ngh
ĩ
a
b
ở
i: x
i

~
f
x
j
⇔ D
2
(x
i
, X’, S’) ≥ D
2
(x
j
, X’, S’), ∀ x
i
, x

i
, X’, S’) = max {D
2
(x
k
, X’, S’)} ∀x
k
∈X’},
Quy trình ra quyết định tập thể dựa trên LOWA
B
ướ
c 1: Xác
đị
nh các tr
ọ
ng s
ố
c
ủ
a các chuyên gia và quy chu
ẩ
n w
1
(k) và tìm W
ij
[S
t
].
B
ướ

i
đ
i
ể
m sao cho: PC
2
(x*) = Max PC
2
(x
j
).
Bước 4:
Áp d
ụ
ng toán t
ử
LOWA
để
tìm
độ
tr
ộ
i t
ươ
ng
đố
i ki
ể
u 2:E
2

ậ
p con X = {Y
1
, ,Y
T
}, v
ớ
i
Y
t
= {x
i
/ E
2
(x
i
, x*) = S
t
} ∀S
t
∈ S và v
ớ
i x* ∈ Y
(T+1)/2
.
S
ắ
p th
ứ
t

đạ
i: Y
t*
v
ớ
i t* = max {t: Y
t
≠ ∅; S
t
∈ S}
23
B
ướ
c 6:

Ch
ọ
n t
ậ
p S’ là các nhãn m
ạ
nh n
ử
a sau và tính
độ
tr
ộ
i
đị
a ph

ầ
n t
ử
c
ủ
a t
ậ
p Y
t
b
ấ
t kì. Nghi
ệ
m
t
ậ
p th
ể
là t
ậ
p Ef
2
(Y
t*
).
Sắp thứ tự tập phương án
Xét t
ậ
p ph
ươ

ự
a ch
ọ
n h
ơ
n ho
ặ
c nh
ư
x
j
, x
i
R x
j
= o n
ế
u x
j

ư
u tiên
h
ơ
n x
i
.
Hàm giá tr
ị
th

= 0 n
ế
u x
i
Rx
j
= o.
S
ắ
p x
ế
p các ph
ươ
ng án thu
ộ
c X theo th
ứ
t
ự
t
ă
ng d
ầ
n c
ủ
a hàm giá tr
ị
th
ứ
t

x
1
x
2
x
3
x
4
x
5
x
6

x
1
x x x x x x
x
2
o x x x x o
x
3
o o x x o o
x
4
o o o x o o
x
5
o x x x x o
x
6

ư
v
ậ
y ta có th
ể
phân l
ớ
p t
ậ
p X thành các l
ớ
p Y
1
, Y
2
, Y
3
, Y
4
, trong
đ
ó Y
1
= {x
4
}, Y
2
= {x
3
}, Y

ớ
i j
> i thì d
ễ
th
ấ
y x
j
Rx
i
= x.
Độ lệch giữa các cách sắp xếp thứ tự ưu tiên trên tập các phương án
Xét t
ậ
p ph
ươ
ng án X và các l
ớ
p Y
1
, Y
2
, … Y
k
mà các ph
ầ
n t
ử
c
ủ

t s
ắ
p x
ế
p th
ứ
t
ự

ư
u tiên nào
đ
ó. Xét các ký hi
ệ
u: X’ = {Y
1
’, Y
2
’, …,
Y
k
’} và X” = {Y
1
”, Y
2
”, …, Y
k
”}, v
ớ
i Y

a các cách s
ắ
p x
ế
p th
ứ
t
ự

ư
u tiên X’ và X’’ trên t
ậ
p ph
ươ
ng
án X
sẽ được xác định bởi
: D(X’, X”) = ∑y
ij
(t
ổ
ng l
ấ
y theo j), trong
đ
ó y
ij
= 0 n
ế
u xj thu

c t
ậ
p Y
(i+h)
’’
ho
ặ
c Y
(i-h)
”.
Ví dụ:
Cho X’= {Y
1
’, Y
2
’, Y
3
’, Y
4
’} v
ớ
i Y
1
’ = {x
4
}, Y
2
’ = {x
3
}, Y

}, Y
3
’’ = {x
4
, x
5
} và
Y
4
’’ = {x
1
, x
6
}. Khi
đ
ó D(X’, X’’) = 2.
24
Định nghĩa: Độ
l
ệ
ch quy chu
ẩ
n gi
ữ
a các cách s
ắ
p x
ế
p th
ứ

a ra
đị
nh lí sau
đ
ây:
Định lí:
Các hàm D(X’, X”) và D’(X’, X”) trên
đ
ây tho
ả
mãn các tính ch
ấ
t c
ầ
n có c
ủ
a
m
ộ
t hàm kho
ả
ng cách.
Sau
đ
ây là thu
ậ
t gi
ả
i ra quy
ế

theo ph
ươ
ng pháp dùng toán t
ử
LOWA.
B
ướ
c 2: Tính
độ
l
ệ
ch quy chu
ẩ
n c
ủ
a ý ki
ế
n c
ủ
a t
ừ
ng chuyên gia so v
ớ
i ý ki
ế
n t
ậ
p th
ể
.

ổ
ng này không nh
ỏ
h
ơ
n 75% ho
ặ
c s
ố
l
ầ
n l
ặ
p v
ượ
t quá ng
ưỡ
ng quy
đị
nh M (là m
ộ
t s
ố
t
ự
nhiên ch
ọ
n tr
ướ
c) thì d

ế
n c
ủ
a mình.
B
ướ
c 4: T
ă
ng s
ố
l
ầ
n l
ặ
p lên 1 và tr
ở
v
ề
b
ướ
c 1.
3.5. Trường hợp khảo sát 3
Ra quyết định tập thể về 06 phương án quy hoạch đất Nhân Chính, Lý Nhân, Hà Nam
bằng thuật toán DELOWA
Để
th
ự
c hi
ệ
n b

Xuân Quân, 2006):
i) Xác
đị
nh các tham s
ố
cho bài toán: Ch
ọ
n và
đặ
t tên các ph
ươ
ng án t
ừ
X1 t
ớ
i X6.
Ch
ọ
n t
ậ
p các nhãn / l
ượ
ng t
ừ
ngôn ng
ữ
so sánh th
ứ
t
ự

để
so sánh và
đ
ánh giá các
ph
ươ
ng án. Trên hình III.5 là ý ki
ế
n
đ
ánh giá c
ủ
a m
ộ
t trong 10 chuyên gia khi so sánh gi
ữ
a 06
ph
ươ
ng án v
ớ
i nhau, ch
ẳ
ng h
ạ
n X1 so v
ớ
i X4 theo nhãn C, có ngh
ĩ
a là X1 t

ể

đượ
c minh ho
ạ
trên hình III.6.

Hình III.6. Tổng hợp ý kiến đánh giá của các chuyên gia và đưa ra thứ tự ưu tiên
Nh
ư
v
ậ
y ph
ươ
ng án X6 là ph
ươ
ng án t
ố
t nh
ấ
t
ở
b
ướ
c 1, ti
ế
p theo là các ph
ươ
ng án X1,
X5, X2, X3 và kém nh

tin c
ậ
y cao) b
ằ
ng các nhãn /
l
ượ
ng t
ừ
ngôn ng
ữ
. Tuy nhiên, c
ũ
ng nh
ư
trong ph
ươ
ng pháp Delphi, thu
ậ
t toán DELOWA
đượ
c
ti
ế
p t
ụ
c b
ở
i các b
ướ

ạ
ch
đấ
t. Quá trình s
ử
a
ch
ỉ
nh nh
ư
v
ậ
y nh
ằ
m làm cho quy
ế
t
đị
nh t
ậ
p th
ế

đạ
t
đượ
c cu
ố
i cùng là t
ố