TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
*************

HOÀNG THỊ NHUNG

CẤU TRÚC CỦA TẬP NGHIỆM PARETO YẾU
CỦA BÀI TOÁN TỐI ƯU
ĐA MỤC TIÊU TUYẾN TÍNH TỪNG KHÚC
TRONG KHÔNG GIAN ĐỊNH CHUẨN

KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Toán giải tích

HÀ NỘI, 2015


LỜI CẢM ƠN
Em xin được bày tỏ lòng biết ơn chân thành tới Th.S Nguyễn Văn
Tuyên, người thầy đã truyền thụ kiến thức, tận tình giúp đỡ, hướng
dẫn em trong suốt quá trình học tập, nghiên cứu và hoàn thành khóa
luận này.
Em xin được gửi lời cảm ơn tới các thầy cô giáo trường Đại học Sư phạm
Hà Nội 2, các thầy cô giáo khoa Toán đã giúp đỡ em trong quá trình học
tập tại trường và tạo điều kiện cho em hoàn thành đề tài khóa luận tốt
nghiệp. Trong quá trình nghiên cứu, không tránh khỏi những thiếu sót
và hạn chế, em kính mong nhận được sự đóng góp ý kiến của các thầy
giáo, cô giáo và toàn thể bạn đọc để khóa luận được hoàn thiện hơn.
Hà Nội, tháng 5 năm 2015
Sinh viên


10

1.4. Sự tồn tại của điểm hữu hiệu. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

1.5. Bài toán tối ưu vector (VOP). . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

Chương 2. Cấu trúc của tập nghiệm Pareto yếu của bài toán
tối ưu đa mục tiêu tuyến tính từng khúc . . . . . . . . . . . . . . . .

17

2.1. Đặt bài toán. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.2. Cấu trúc của tập nghiệm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

2.2.1. Trường hợp nón thứ tự là đa diện. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

2.2.2. Trường hợp nón thứ tự tổng quát. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28


2

gian hữu hạn chiều sang trường hợp các không gian định chuẩn. Chúng
tôi sẽ chỉ ra rằng nếu hàm mục tiêu là tuyến tính từng khúc, lồi theo nón
giữa hai không gian định chuẩn, nón thứ tự có phần trong khác rỗng và
tập ràng buộc là đa diện thì tập các nghiệm Pareto yếu là hợp hữu hạn
các đa diện và là liên thông đường. Nếu bỏ qua giả thiết về tính lồi theo
nón của hàm mục tiêu, bằng phản ví dụ, chúng ta thấy rằng các kết quả
trên không còn đúng. Nhưng nếu nón thứ tự là đa diện và hàm mục tiêu
là tuyến tính từng khúc (không nhất thiết lồi), thì chúng tôi cũng chỉ ra
rằng tập nghiệm Pareto yếu là hợp hữu hạn các đa diện.
Khóa luận được chia thành hai chương. Chương 1 giới thiệu một số
kiến thức cơ bản về tối ưu vector.
Chương 2 trình bày cấu trúc của tập nghiệm Pareto yếu của bài toán
tối ưu đa mục tiêu tuyến tính từng khúc trong không gian định chuẩn.
Các ví dụ cũng được trình bày trong chương này để phân tích các kết
quả đạt được.


Chương 1
Bài toán tối ưu vector
1.1. Một số khái niệm cơ bản.
Giả sử E là không gian tuyến tính, R là tập các số thực.
Định nghĩa 1.1. Tập A ⊂ E được gọi là lồi, nếu:
∀x1 , x2 ∈ A; ∀λ ∈ R : 0

λ

1 ⇒ λx1 + (1 − λ)x2 ∈ A.


D

0, ∀x ∈ D} .

b khi và chỉ khi a − b ∈ D; a

m
0, i = 1, ..., m. Kí hiệu Rm
+ := {x ∈ R : x

0 khi và chỉ khi

0} và cho g : X → Rm .

Hàm g được gọi là D- giống lồi trên S ⊆ X khi và chỉ khi :
∀x1 , x2 ∈ S, ∀α ∈ [0, 1], ∃x ∈ S.
sao cho
(1 − α)g(x1 ) + αg(x2 ) − g(x) ∈ D.
Điều này được biết đến trong [13] rằng g là một hàm D- giống lồi khi
và chỉ khi tập g(S) + D là lồi.
Định nghĩa 1.4. Phần trong tương đối của tập A ⊂ Rn là phần trong
của A trong af f A (bao affine); kí hiệu là riA. Các điểm thuộc riA được
gọi là điểm trong tương đối của tập A.


5

Nhận xét 1.2.
intA := {x ∈ Rn : ∃ε > 0, x + εB ⊂ A} ,

0, ∀n}, thì C là nón nhọn, lồi. Tuy nhiên, ta chưa

biết nón C là nón đúng hoặc nón sắc vì ta chưa biết tôpô xác định trên
không gian này.
3. Nón thứ tự từ điển: Cho
lp = x ∈ Ω : x = (

1

|xn |p ) p , 1

p < ∞.

Kí hiệu C là hợp của 0 và các dãy mà số hạng đầu tiên khác không của
dãy là dương. Đây là một nón lồi, còn gọi là nón thứ tự từ điển. Nó là
nón nhọn nhưng không là nón đúng và cũng không phải là nón có giá
chặt.
Mệnh đề 1.1. Nón C là đúng khi và chỉ khi một trong các điều kiện
sau thoả mãn:
(a) C là đóng;
(b) C\l(C) là mở, khác rỗng;
(c) C là hợp của 0 và giao của các nửa không gian mở và nửa không
gian đóng trong E.
Chứng minh. (a) Hiển nhiên
(b) Nếu C\l(C) mở thì intC = ∅ và intC = C\l(C). Do đó, ta có
clC + C\l(C) = (clC) + intC ⊆ C,


7


nên lưới {bα = cα /tα } hội tụ tới 0. Hơn thế nữa B là đóng, dẫn tới mâu
thuẫn: 0 = lim bα ∈ B. Bằng cách này, ta có thể giả sử {tα } hội tụ tới
điểm to

0. Nếu to = 0 thì từ tính bị chặn của B, lim tα bα = 0. Do đó

c = 0 và hiển nhiên c ∈ C. Nếu to > 0, ta có thể giả sử tα > , ∀α, > 0.
Từ bα = cα /tα hội tụ tới c/to và hơn nữa, B đóng nên vector c/to ∈ B.
Do đó c ∈ C và C đóng nên C nhọn là hiển nhiên.

1.2. Quan hệ hai ngôi và quan hệ thứ tự.
Cho một tập hợp E tuỳ ý, một quan hệ hai ngôi trong E được định
nghĩa bởi một tập con B của tập hợp tích E × E. Điều này có nghĩa là,
một phần tử x ∈ E có quan hệ với y ∈ E nếu (x, y) ∈ B.
Định nghĩa 1.7. Cho B là một quan hệ hai ngôi trong E. Ta nói quan
hệ này là:
(a) Phản xạ nếu (x, x) ∈ B với mọi x ∈ E;
(b) Đối xứng nếu(x, y) ∈ B suy ra (y, x) ∈ B với mỗi x, y ∈ E;
(c) Bắc cầu nếu (x, y) ∈ B, (y, z) ∈ B suy ra (x, z) ∈ B với x, y, z ∈ B;
(d) Đầy đủ hoặc liên thông nếu (x, y) ∈ B hoặc (y, x) ∈ B với mỗi
x, y ∈ E, x = y;
(e) Tuyến tính trong trường hợp E là không gian vector thực nếu:
(x, y) ∈ B suy ra (tx + z, ty + z) ∈ B với mọi x, y, z ∈ E, t > 0;
(f) Đóng trong trường hợp E là không gian vector tôpô, nếu nó là đóng
như một tập con của không gian tích E × E.


9

Để làm rõ định nghĩa này, chúng ta xem xét một số ví dụ cổ điển sau.

C

y và không phải là y
C

C

x, hay là x ∈ y + C\l(C).

y nghĩa là x >K y với K = {0} ∪ intC.


10

Ví dụ 1.4. 1. Cho Rn và tập C = Rn+ . Thì BC là phản xạ, bắc cầu,
tuyến tính, đóng, không đối xứng nhưng không đầy đủ.
Cho x = (x1 , ..., xn ) , y = (y1 , ..., yn ) ∈ Rn :
x

C

y khi và chỉ khi xi

x >C y khi và chỉ khi xi

yi với i = 1,..., n;
yi với i = 1,..., n và ít nhất một bất đẳng

thức là ngặt;
x


x;

Tập các điểm hữu hiệu của A kí hiệu là E(A, C);


11

(c) x ∈ A là điểm hữu hiệu thực sự (toàn cục) của A tương ứng với C
nếu tồn tại một nón lồi K = E với intK ⊇ C\l(C) sao cho x ∈ E(A, K);
Tập các điểm hữu hiệu toàn cục của A được kí hiệu là P rE(A, C);
(d) Giả sử intC = ∅, x ∈ A là một điểm hữu hiệu yếu của A tương ứng
với C nếu x ∈ E(A, {0} ∪ intC);
Tập các điểm hữu hiệu yếu của A kí hiệu là W E(A, C).
Ví dụ 1.5. Cho
A = (x, y) ∈ R2 : x2 + y 2

1, y

0 ∪ {(x, y) : x

0, 0

B = A ∪ {(−2, −2)}.
Nếu cho C = R2+ , ta có:
IE(B) = P rE(B) = E(B) = W E(B) = {(−2, −2)};
IE(A) = ∅,
P rE(A) = (x, y) ∈ R2 : x2 + y 2 = 1, 0 > x, 0 > y ,
E(A) = P rE(A) ∪ {(0, −1)} ∪ {(−1, 0)},
W E(A) = E(A) ∪ {(x, y) : y = −1, x

khi C là nhọn.
Chứng minh. Lấy x ∈ P rE(A). Nếu x ∈ E(A) có y ∈ A và x − y ∈
C\l(C). Lấy nón lồi K, K = E với intK ⊆ C\l(C) và x ∈ E(A, K). Thì
x − y ∈ intK ⊆ K\l(K). Điều này mâu thuẫn với x ∈ E(A, K) suy ra
P rE(A) ⊆ E(A).
Lấy x ∈ E(A). Nếu x ∈ W E(A) theo Mệnh đề 1.3 tồn tại y ∈ A sao
cho x − y ∈ intC. Do C = E, intC ⊆ C\l(C) nên ta có x − y ∈ C\l(C).
Điều này mâu thuẫn với x ∈ E(A). Vậy E(A) ⊆ W E(A).
Rõ ràng, IE(A) ⊆ E(A). Nếu IE(A) = ∅, cho x ∈ IE(A) thì x ∈
E(A). Cho y ∈ E(A) thì y ≥ x vì vậy x

y. Lấy một điểm bất kì

z ∈ A có z

x vì x ∈ IE(A) suy ra z

y là y ∈ IE(A). Do đó,

IE(A) = E(A). Ngoài ra, nếu C là nhọn x

y và y ≥ x chỉ có thể xảy

ra trường hợp x = y. Vậy IE(A) là tập một điểm.
Định nghĩa 1.10. Cho x ∈ E. Tập A ∩ (x − C) được gọi là một nhát
cắt A tại x và kí hiệu Ax .


13


cần chứng minh E(Ax , C) = ∅. Xét tập P bao gồm tất cả các lưới giảm
trong A. Vì A = ∅ suy ra P = ∅. Với a, b ∈ P ta viết a

b nếu b ⊆ a.

Rõ ràng ( ) là quan hệ thứ tự trong P , và một xích bất kì trong P đều
có cận trên. Thật vậy, giả sử {aλ ; λ ∈ Λ} là một xích trong P . Gọi B là
tập tất cả các tập con hữu hạn B của Λ được sắp thứ tự bởi bao hàm,
đặt
aB = ∪ {aα ; α ∈ B} .
Và
ao = ∪ {aB : B ∈ B} .
Thì ao là một phần tử của P và ao

aα với mọi α ∈ Λ nghĩa là ao là

một cận trên của xích này. Áp dụng bổ đề Zorn, tồn tại phần tử lớn
nhất của P , kí hiệu là a∗ = {xα : α ∈ I} ∈ P . Bây giờ, giả sử ngược lại
E(Ax , C) = ∅. Chúng ta sẽ chứng minh {(xα − clC)c : α ∈ I} phủ Ax .
Ta chỉ ra với mỗi y ∈ Ax có α ∈ I mà (xα − clC)c chứa y. Giả sử phản
chứng y ∈ xα − clC, ∀α ∈ I. Vì E(Ax , C) = ∅ có z ∈ Ax với y >C z. Do
tính đúng của C nên x − α >C z, (α ∈ I). Thêm z vào lưới a∗ ta thấy
rằng lưới này không thể lớn nhất, dẫn tới mâu thuẫn. Vậy định lí được
chứng minh.


15

1.5. Bài toán tối ưu vector (VOP).
Cho X là một tập con khác rỗng của một không gian tôpô và F là một

aα ∈ V + C, ∀α

β.

Do {aα } là dãy giảm, nên
aα ∈ aδ + C, ∀δ

α.

Từ đây suy ra:
aα ∈ cl(F (x) + C) = F (x) + C, ∀α.
Dẫn tới mâu thuẫn: F (x) + C không thể là C- đầy đủ.


Chương 2
Cấu trúc của tập nghiệm Pareto
yếu của bài toán tối ưu đa mục tiêu
tuyến tính từng khúc
2.1. Đặt bài toán.
Trong phần này, cho X, Y là các không gian định chuẩn và cho C ⊂ Y
là nón lồi với int (C) = ∅, khi đó xác định một quan hệ thứ tứ ≤C
trong Y : với y1 , y2 ∈ Y, y1 ≤C y2 ⇔ y2 − y1 ∈ C. y1

C − min f (x)
a∗j , x ≤ cj , j = 1, ..., n.
Để thuận tiện, gọi Γ là tập chấp nhận được của (2.2), tức là:
Γ := x ∈ X : a∗j , x ≤ cj , j = 1, ..., n .
Một vector x¯ ∈ Γ được gọi là nghiệm Pareto yếu của (2.2) nếu
f (¯
x) ∈ W E (f (Γ) , C) ;

(2.2)


19

trong trường hợp này, f (¯
x) được gọi là giá trị Pareto yếu của (2.2). Kí
hiệu Sw và Vw theo thứ tự là tập nghiệm Pareto yếu của (2.2) và tập giá
trị Pareto yếu của (2.2).
Rõ ràng là Sw = Γ ∩ f −1 (Vw ) và Vw = W E (f (Γ) , C) .
Trong phần tiếp theo, chúng ta giả sử rằng f : X → Y là ánh xạ tuyến
tính từng khúc được định nghĩa trong (2.1). Chúng ta cũng giả thiết
rằng Sw là khác rỗng.
Tiếp theo, ta trình bày một số tính chất cơ bản được sử dụng trong phần
sau:
Bổ đề 2.1. Cho I = {1, ..., m} và Io := {i ∈ I : int (Pi ) = ∅} , trong đó,
m như trong (2.1). Khi đó X =

i∈Io

Pi .


i∈I\Io

Pi = ∅. Do đó,

= ∅. Mâu thuẫn với giả thiết của (2.1). Bổ đề được

chứng minh.
Bổ đề 2.2. f là C lồi nếu và chỉ nếu
Ti (x) + bi ≤C f (x) , ∀x ∈ X, 1 ≤ i ≤ m.

(2.3)


20

Chứng minh. • Điều kiện đủ:
Đặt Ωi := {(x, y) ∈ X × Y : Ti (x) + bi ≤C y} . Khi đó, (2.1)và (2.3) có
nghĩa là epiC (f ) =

m
i=1 Ωi .

Do đó, epiC (f ) là lồi và như vậy f là C lồi.

• Điều kiện cần:
Cho Io giống như trong Bổ đề 2.1. Khi đó, X =

i∈Io



2.2. Cấu trúc của tập nghiệm.
Trong phần tiếp theo, chúng ta nghiên cứu cấu trúc của Sw và Vw . Trước
hết ta nhắc lại một kết quả cơ bản của Arrow, Barankin và Brackwell
[3]:
Định lý ABB. Cho X, Y là không gian hữu hạn chiều và nón sinh thứ
tự C là đa diện. Gọi T : X → Y là toán tử tuyến tính bị chặn và b ∈ Y.
Giả sử rằng, ánh xạ mục tiêu f (x) = T (x) + b với mọi x ∈ X và Sw là
khác rỗng. Khi đó, Sw là hợp của hữu hạn các đa diện và là liên thông
đường.
Chúng ta sẽ trình bày các mở rộng của Định lí ABB tới các không gian
vô hạn chiều và trường hợp tuyến tính từng khúc trong hai trường hợp
sau:

Trích đoạn Trường hợp nón thứ tự tổng quát

---