ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN KIM THANH
MỘT PHƯƠNG PHÁP VÔ HƯỚNG HÓA
GIẢI BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN KIM THANH
MỘT PHƯƠNG PHÁP VÔ HƯỚNG HÓA
GIẢI BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU
Chuyên ngành: Toán ứng dụng
Mã số: 60.46.36
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học:
PGS.TS. TẠ DUY PHƯỢNG
THÁI NGUYÊN - 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
LỜI CẢM ƠN
Luận văn này được viết dưới sự hướng dẫn tận tình của PGS.TS. Tạ
Duy Phượng. Tôi xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới Thầy
và gia đình.
Tôi xin chân thành cảm ơn Ban giám hiệu trường Đại học Khoa học,
Phòng đào tạo và nghiên cứu khoa học đã quan tâm giúp đỡ, tạo mọi điều
kiện thuận lợi cho tôi được học tập tốt.
Tôi xin chân thành cảm ơn Ban giám hiệu và các bạn đồng nghiệp
trường TH PT Lưu Nhân Chú - Thái Nguyên đã tạo điều kiện cho tôi hoàn
thành luận văn này.
Tôi xin chân thành cảm ơn bạn bè và gia đình đã hết lòng động viên

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Mục đích của luận văn là trình bày một phương pháp tì m tập hữu hiệu
nhờ phương phá p số dựa theo tài liệu [3]. Trong [3] , Gabriele Eichfelder
đã sử dụng phương pháp ti ếp cận vô hướng hóa phụ thuộc tham số của
Pasco letti và Serafini .
Nhiệm vụ của luận văn là trình bày một cách chi tiết, có chứng mi nh
một số định lí, nhận xét, trình bày lại thuậ t toán giải bài toán tối ưu hai
mục tiêu.
Luận văn của gồm 3 chương:
Chương 1 là những kiến thức chuẩn bị của luận văn. Trong phần đầu
của chương này, chúng tôi nhắc lại những khái niệm và kết quả cơ bản của
tối ưu đa mục tiêu, chẳng hạn như các khái niệm cực tiểu và các tính chất
của nón sắ p thứ tự, đặc biệt là nón đa diện.
Chương 2 dành riêng tìm hiểu kĩ về phương pháp vô hướng hóa giải
bài toán tối ưu.
Vô hướng hóa được đưa ra dựa trên vô hướng hóa Pascoletti-Serafini. Đây
là một trong hai chương chính của luận văn.
Chương 3 Trong chương này chủ yếu sử dụng kết quả trước để phát
triển thuật toá n điều khi ển việc lựa chọn tham số trong tiếp cận vô hướng
hóa Pascoletti-Serafini.
Và cuối cùng là kết luận và tài liệu tham k hảo.
Thái Nguyên, năm 2011
Học viên
Nguyễn Kim Thanh
iii
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Mục lục
1 Kiến thức chuẩn bị 1
1.1 Kiến thức cơ sở . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Quan hệ sắp thứ tự . . . . . . . . . . . . . . . . . . 2

→ R
q
(p, q ∈ N) là các hà m liên tục.
Ta đặt f(x) = (f
1
(x), ., f
m
(x)) với
f
i
: R
m
→ R
, i = 1, , m.
Cho S ⊂ R
n
là một tập lồi đó ng và C ⊂ R
p
là một nón lồi đóng. Nhắc
lại rằng một tập C ⊂ R
p
là một nón lồi đóng nếu λ(x + y) ∈ C với mọi
λ ≥ 0, x, y ∈ C.
Xét bài t oán tối ưu đa mục tiêu ( MOP ):
min f(x)
với các hạn chế
g(x) ∈ C,
h(x) = 0
q
,

nếu với x, y, z, w ∈ R
m
tùy ý ta có:
(i) x ≤ x (tính phản xạ),
(ii) x ≤ y, y ≤ z ⇒ x ≤ z (tính bắc cầu),
(iii) x ≤ y, w ≤ z ⇒ x + w ≤ y + z (tính tương thích với phép cộng),
(iv) x ≤ y, α ∈ R
+
⇒ αx ≤ αy (tính tương thích vớ i phép nhâ n vô hướng).
Định ngh ĩa 1.1.3. Một quan hệ sắp thứ tự bộ phận ≤ trên R
m
được gọi
là phản xứng nếu với x, y ∈ R
m
bất kì x ≤ y, y ≤ x ⇒ x = y.
Định nghĩa 1.1.4. Một không gian tuyến tính R
m
được trang bị một
quan hệ sắp thứ tự được gọi là không gian tuyến tính sắp thứ tự.
Ví dụ 1.1.5. Quan hệ sắp thứ tự trên R
m
được định nghĩa bởi:
≤
m
:= {(x, y) ∈ R
m
× R
m
| x
i

m
| y − x ∈ K}
(iii) Một quan hệ sắp thứ tự K là phản xứng nếu và chỉ nếu K là nón nhọn.
Nhắc lại rằng, nón K ⊂ R
m
được gọi là nón nhọ n nếu K ∩(−K) = {0
m
}
Giả sử K l à một nón nhọn nào đó . Khi đó quan hệ sắp thứ tự trên R
m
≤
K
:= {(x, y) ∈ R
m
× R
m
| y − x ∈ K}
Nếu x ≤
K
y với x, y ∈ R
m
thì y −x ∈ K. Vì K là nón nhọn x −y ∈ K chỉ
khi x − y = 0
m
hay y ≤
K
x khi x = y. Do đó quan hệ sắp thứ tự ≤
K
là
phản xứng.

+
, điểm K-cực tiểu cũng được gọi là Ed g eword-Pareto-cực tiểu
(EP-cực tiểu).
Trong hình 1.2 là v í dụ về bài toán tối ưu hai mục tiêu. Tập Ω và f(Ω)
là những nón nhọn sắp thứ tự. Tập hữu hiệu là phần đường tô đậm.
Trong không gia n tuyến tính sắp thứ tự, tồn tại những điểm không thể
so sá nh được với nhau như các điểm (1; 2) và (2; 1) trong R
2
tương ứng với
4
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
nón sắp thứ tự tự nhiên. Đó là lí do tại sao bài toán tối ưu tổng quát dễ
có vô số nghiệm. Bởi vì việc tính toán trực tiếp t ất cả các nghiệm trong
trường hợp tổng quát là không thể nên t a cố gắng đưa r a xấ p x ỉ tiệm cận
theo điểm của tập hữu hiệu với độ xấp xỉ cao nhất.
Trong trường hợ p quan hệ sắp thứ tự toàn phầ n và nếu bài toán đa mục
tiêu là giải được thì chỉ có duy nhất một nghiệm cực tiểu trong không gian
ảnh.
Một quan hệ sắp thứ tự được gọi là sắp thứ tự toàn phần nếu với mọi
x, y ∈ R
m
hoặc x ≤ y hoặc y ≤ x là đúng. Nếu một q uan hệ sắp thứ tự
được đặc trưng bởi một nón lồi K ⊂ R
m
thì nó là sắp thứ tự toàn phần
nếu và chỉ nếu K ∪(−K) = R
m
.
Ví dụ quan hệ sắp thứ tự tự đi ển x ác định bởi nón
K =

(¯y −int( K)) ∩ f(Ω) = ∅
Tập tất cả các nghiệm cực ti ểu yếu tương ứng với nón K được kí hiệu là
M
w
(f(Ω), K). Tập ảnh của tập tất cả các điểm cực tiểu yếu
E
w
(f(Ω), K) := { f (x) | x ∈ M
w
(f(Ω), K)}
được gọi là tập các đ i ểm hữu hiệu yếu tương ứn g với nón K.
Ta cũng xét tập các điểm hữu hiệu yếu đối với K = R
m
+
.
Các điểm K-cực tiểu là các điểm cực tiểu tương ứng với nón int(K)∪{0
m
}.
Vì vậy xét các mệnh đề dưới đây ta xét trong trường hợp int(K) khác rỗng
đó là
M(f(Ω), K) ⊂ M
w
(f(Ω), K).
E(f(Ω), K) ⊂ E
w
(f(Ω), K).
Bổ đề 1.1.10. ([5]) Cho K
1
và K
2

).
Chứng minh. Vì K
1
⊂ K
2
nên int(K
1
) ⊂ in t(K
2
) và vì vậy
M
w
(f(Ω), K
2
) = M(f(Ω), int(K
2
)) ∪{0
m
}
6
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
⊂ M(f (Ω), int(K
1
)) ∪{0
m
}
= M
w
(f(Ω), K
1

+ λx ∈ K và x
2
+ λx ∈ K, ∀λ ∈ [0,
¯
λ]
Vì K lồi nên ta có :
tx
1
+ (1 − t)x
2
+ λx = t(x
1
+ λx) + (1 −t)(x
2
+ λx) ∈ K, ∀λ ∈ [0,
¯
λ]
7
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Vậy tx
1
+ (1 − t)x
2
∈ cor(K) hay cor(K) lồi.
(ii) Lấy ¯x bất kì thuộc cor(K) và µ > 0. Với mỗi x ∈ X có
¯
λ > 0 sao cho
¯x +
λ
µ

| y
1
≥ 0, y
3
= 0

⊂ R
3
Nếu K = R
2
+
×0 thì in t(K) = ∅ và ta không thể xác định nghiệm cực tiểu
yếu. Tuy nhiên
icr(K) =

y ∈ R
3
| y
1
> 0 , y
2
> 0, y
3
= 0

và ta có thể xác định một nghiệm yếu tương ứng với icr(K) ∪{0
3
}.
Định nghĩa 1.1.16. Cho K = R
m

m
đã biết. Khi đó:
(i) E(αf(Ω), K) = αE(f(Ω), K),
(ii) E(f(Ω) +
˜
f(
˜
Ω), K) ⊂ E(f(Ω), K) + E(
˜
f(
˜
Ω), K),
(iii) E(f(Ω), K) ⊃ E(f(Ω) + K, K),
(iv) Nếu K là một nón lồi nhọn thì
E(f(Ω), K) = E(f (Ω + K), K).
Chứng minh. (i) Ta có
E(f(Ω), K) := {f(x) | x ∈ M(f(Ω), K)}
⇒ αE(f(Ω ), K) = {αf(x) | x ∈ M(f(Ω), K)}
= E(f(Ω), K)
(ii) Lấy
¯y ∈ E(f(Ω) +
˜
f(
˜
Ω), K).
Khi đó ¯y = y
1
+ y
2
với y

˜
f(
˜
Ω), K).
Bằng cách chứng minh tương tự ta cũng có y
2
∈ E(
˜
f(
˜
Ω), K). Từ đó có
¯y ∈ E(f(Ω), K) + E(
˜
f(
˜
Ω), K)
9
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
hay
E(f(Ω) +
˜
f(
˜
Ω), K) ⊂ E(f(Ω), K) + E(
˜
f(
˜
Ω), K).
(iii) Vi ệc chứng minh trở nên tầm thường nếu f(Ω) = ∅.
Xét trường hợp f(Ω) = ∅. Giả sử y ∈ E(f(Ω+K), K) nhưng y ∈ E(f( Ω), K).


và d

+ d

∈ K ,vì K là nón
lồi. Do K nhọn, d

+ d

= 0 và vì vậy y ∈ E(f(Ω), K), dẫn tới mâu thuẫn.
Bổ đề được chứng mi nh.
Định lí dưới đây chỉ ra rằ ng chỉ xét cần biên ∂f(Ω) của tập f(Ω) là đủ
để xác đị nh tất cả các nghiệm cực ti ểu.
Định lý 1.1.18. Cho K là một nón khác rỗng sắp thứ tự với K = {0
m
} .
Khi đó:
E(f(Ω), K) ⊂ ∂f(Ω).
Điều này cũng đúng c ho các điểm h ữu hiệu yếu.
Định lý 1.1.19. Cho K là một nón nhọn với i n t(K) = ∅. Khi đó
E
w
(f(Ω), K) ⊂ ∂f(Ω).
Chứng minh. C ho ¯y ∈ E(f(Ω), K). Ta giả sử ¯y ∈ f( Ω)\∂f(Ω ) = int(f(Ω)).
Khi đó tồn tại δ > 0 và một hình cầu mở B = {y ∈ R
m
| y < δ} với
¯y + B ⊂ f(Ω). Cho k ∈ int(K). Khi đó có một λ < 0 sao cho λk ∈ B và
¯y + λk ∈ f(Ω). Vì K là một nón nên λk ∈ −i n t(K) và vì vậy ta có

(¯x).
1.2 Nón đa diện sắp thứ tự
Nón lồi đa diện là một loại nón lồ i đặc biệt. Các tính chất của nó có thể
được sử dụng để đơn giản hóa lời giải bài toán tối ưu đa mục tiêu.
Định nghĩa 1.2.1. Một tập K ∈ R
m
là một nón lồi đa d i ện nếu K có
thể được biểu diễn bởi:
K =

x ∈ R
m
| (
¯
k
i
)

x ≥ 0, i = 1, , s

với s ∈ N và các vector (
¯
k
i
)

∈ R
m
, i = 1, , s.
Định nghĩa 1.2.2. Một tập K ⊂ R

sinh.
Nếu nón K có thể được biểu diễn dạng
K =

x ∈ R
m
| (
¯
k
i
)

x ≥ 0, i = 1, , s

thì ta có thể nói rằng K được si nh hay được tạo bởi ma trận
¯
K :=











(
¯

s
0
s

.
Nếu nón K là nón sinh bởi ma trận
¯
K và nếu ker(
¯
K) = {0
m
} thì K là
nhọn và quan hệ sắp thứ tự là phản xứng . Ví dụ nón nhọ n xác định bởi
sắp thứ t ự tự nhiên là đa diện sinh bởi ma trận đơn vị m chiều E
m
.
Công việc tìm điểm K-cực tiểu của bài toán tới ưu đa mục tiêu tương
ứng với nón nhọn sắp thứ tự sinh bởi ma trận
¯
K ∈ R
s×m
, có thể quy về
việc xác định điểm EP -cực tiểu của bài toán tối ưu đa mục tiêu
min
¯
Kf (x)
thỏa mãn điều kiện ràng buộc
x ∈ Ω
với s hàm mục tiêu (
¯

12
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
với
¯
(K) ∈ R
s×m
và ker(
¯
K) = {0
m
}. Khi đó
E(f(Ω), K) =

y ∈ f(Ω) |
¯
Ky ∈ E(
¯
Kf(Ω), R
s
+
)

và
M(f(Ω), K) = M(
¯
Kf(Ω), R
s
+
)
thỏa mãn

3
(x)





(1.2)
với nón sắp thứ tự
K =















y ∈ R
3
|










ở đây
K =

y ∈ R
3
| −y
3
≤ y
1
≤ y
3
, −y
3
≤ y
2
≤ y
3
, y
3
≥ 0

là một hình chóp với đỉnh chóp là gốc tọa độ.
Theo bổ đề 1.2.4, điểm ¯x ∈ Ω là một nghiệm K-cực tiểu của (1.2) khi

(x) + f
3
(x)








.
Trong trường hợ p hai mục tiêu, mọi nón sắ p thứ tự là hữu hạn sinh.
Ta có:
Bổ đề 1.2.6. Cho K ⊂ R
2
là một nón nhọn đóng sắp thứ tự với K = {0
2
}.
Khi đó K là một đa diện và hoặc có một k ∈ R
2
\ {0
2
} sao cho
K = {λk | λ ≥ 0}
hoặc t ồn t ại l
1
, l
2
∈ R

l
2
, λ
1
, λ
2
≥ 0

.
Chứng minh. C húng ta đưa ra cách chứng minh kiến thiết sao cho ta có
thể x ác định K và l
1
, l
2
và
˜
l
1
,
˜
l
2
tương ứng bởi việc giải bài toán tối ưu đơn
giản.
Ta bắt đầu bằng vi ệc giải bài toán:
min ϕ
các điều k iện ràng buộc


cosϕ

, ϕ
1
+ π].
Nếu ϕ
1
= ϕ
2
thì
K =

λk | k = (cosϕ
1
, sinϕ
1
)

, λ > 0

.
Nếu ϕ
1
= ϕ
2
thì do tính lồi của K
K =

y ∈ R
2
| y = λ(cosϕ, sinϕ)


≥ 0

Tương tự ta có thể giải cho trường hợp ϕ
1
= 0 và giải bài toán (1) và
(2) tương ứng với ϕ ∈ [π, 3π ] thay v ì ϕ ∈ [ 0, 2π].
Ta có
˜
l
1
:= (cosϕ
1
, sinϕ
1
)

và
˜
l
2
:= (cosϕ
2
, sinϕ
2
)

với
˜
l
1

Để xác định nghiệm của bài toán tối ưu đa mục tiêu (MOP)
min f(x)
các điều k iện ràng buộc
g(x) ∈ C
h(x) = 0
q
x ∈ S
với tậ p ràng buộc Ω = {x ∈ S | g(x) ∈ C, h(x) = 0
q
}.
Một tro ng các phương pháp hay dùng để giải bài toán (MOP) là phương
pháp vô hướng hóa. Điều này được thực hiện, chẳng hạn bằng phương
pháp tổng t rọng số. Xét bài to án vô hướng:
min
m

i=1
w
i
f
i
(x)
trong đó w ∈ K
∗
\ {0
m
} với K
∗
là nón đối ngẫu của nón K, tức là
K

Ngoài ra cò n rất nhiều các phương pháp vô hướng hóa khác có t hể được
tìm thấy. Tuy nhiên trong luận văn này, chúng tôi quan tâm tới phương
pháp vô hướng hóa Pascoletti-Serafini.
2.1 Tối ưu hóa Pascoletti-Serafini
Pasco letti và Serafini đã đưa bài toán tối ưu đa mục tiêu trên về bài toán
vô hướ ng hóa chứa tham số a ∈ R
m
và r ∈ R
m
.
Xét bài t oán (SP(a, r)) :
min t
các điều k iện ràng buộc
a + tr −f(x) ∈ K
g(x) ∈ C
h(x) ∈ 0
q
t ∈ R, x ∈ S
Bài toán này có tham số phụ thuộc vào tập ràng buộc :
(a, r) :=

(t, x) ∈ R
n+1
| a + tr − f(x) ∈ K, x ∈ Ω

17
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Ta giả sử nón K là nó n khác rỗng, lồi, đóng, nhọn. Phát biểu của bài toán
tối ưu vô hướng dưới dạng này tương ứng với định ng hĩa của K-cực tiểu.
Một điểm ¯x ∈ Ω sao cho ¯y = f(¯x) là K-cực tiểu nếu

yếu của bài to án tối ưu đa mục tiêu (MOP) và bằng phương pháp thay đổi
tham số (a, r) ∈ R
m
× R
m
, tất cả các điểm K-cực tiểu của (MOP) có thể
tìm thấy được nghiệm của (SP(a,r)).
2.2 Tính chất của vô hướng hóa Pascoletti-
Serafini
Ta giả sử K là nón khá c rỗng, nhọn, đóng, sắp thứ tự trong R
m
.
Định lý 2.2.1. Xét bài toán tối ưu vô hướng (SP(a,r)) với int(K) = ∅.
(i) Nếu ¯x là K c ực tiểu yếu của bài toán tối ưu đa mục tiêu (M OP), thì
(0, ¯x) là một nghiệm cực tiểu của bài toán (SP(a,r)) với tham số a := f (¯x)
19
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn