BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH
Lê Minh Tuấn
TỐI ƯU NHIỀU MỤC TIÊU VỚI HÀM MỤC TIÊU
LÀ HÀM PHÂN TUYẾN TÍNH
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thành phố Hồ Chí Minh – 2015
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH
Lê Minh Tuấn
TỐI ƯU NHIỀU MỤC TIÊU VỚI HÀM MỤC TIÊU
LÀ HÀM PHÂN TUYẾN TÍNH
Chuyên ngành:
Mã số:
Toán giải tích
60 46 01 02
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. TRỊNH CÔNG DIỆU
Thành phố Hồ Chí Minh – 2015
LỜI NÓI ĐẦU
Ngày nay, lý thuyết tối ưu là một trong các ngành Toán học phát triển
mạnh và có nhiều ứng dụng thực tế. Đây là một sự đáp ứng tích cực của Toán
học trừu tượng cho nhu cầu của cuộc sống “Suy tính về một công việc sao cho
nó được tiến hành tốt nhất”. Trong các bài toán thực tiễn, tiêu chuẩn “ tốt
nhất” thường được dựa vào nhiều tiêu chí, đó chính là vấn đề được khảo sát
trong luận văn.
Luận văn gồm các phần sau:
Lời nói đầu
Mục lục
Các ký hiệu
Chương 1
Lý thuyết tối ưu nhiều mục tiêu
Chương 2
Tối ưu vectơ dạng phân tuyến tính (MOLFP)
Kết luận
Tài liệu tham khảo
Nội dung của chương 1 gồm:quan hệ hai ngôi, quan hệ thứ tự định bởi
một nón, tập lồi, tập lồi đa diện, nửa liên tục trên, nửa liên tục dưới, sơ lược
về bài toán tối ưu nhiều mục tiêu, định nghĩa nghiệm Pareto, nghiệm Pareto
yếu, nghiệm Pareto chặt, nghiệm Pareto chính thường theo Geoffrion,
Borwein, Benson của bài toán tối ưu nhiều mục tiêu và mối quan hệ giữa các
định nghĩa Pareto chính thường.
Nội dung của chương 2 gồm: giới thiệu bài toán qui hoạch nhiều mục
tiêu phân tuyến tính theo Malivert gồm các điều kiện tối ưu, xây dựng hàm
phạt cho việc kiểm tra nghiệm Pareto và nghiệm Pareto yếu, tính nửa liên tục
trên, nửa liên tục dưới của hàm phạt.
Tôi xin kính gởi lời cám ơn sâu sắc và chân thành nhất tới TS Trịnh
Công Diệu
– Khoa Toán Tin – Trường Đại Học Sư Phạm TP.Hồ Chí Minh vì sự tận
tình giúp đỡ và chỉ bảo của thầy đối với tôi trong thời gian làm luận văn.
Tôi cũng xin gởi lời cám ơn đến Quý Thầy Cô Trường Đại Học Sư Phạm
TP.Hồ Chí Minh đã tận tình giảng dạy tôi trong suốt khóa học.
Tôi xin cám ơn Ban giám hiệu, Ban chủ nhiệm khoa Toán – Tin, Phòng
Khoa Học Công Nghệ và Phòng Sau Đại Học – Trường Đại Học Sư Phạm
TP.Hồ Chí Minh đã giúp đỡ và tạo điều kiện cho tôi trong thời gian học tại
trường.
Xin gởi lời cám ơn đến quý thầy, cô trong Hội đồng chấm luận văn đã
dành thời gian quý báu để đọc, chỉnh sửa, góp ý và phản biện cho tôi hoàn
thành luận văn này một cách hoàn chỉnh nhất.
Cuối cùng xin chân thành cảm ơn gia đình và bạn bè đã luôn quan tâm,
động viên giúp tôi hoàn thành luận văn này.
TP. Hồ Chí Minh, tháng 03 năm 2015
Học viên thực hiện
Lê Minh Tuấn
MỤC LỤC
Trang
CHƯƠNG 1: BÀI TOÁN TỐI ƯU NHIỀU MỤC TIÊU ................................. 1
1.1 Một số khái niệm cơ bản:......................................................................... 1
1.2 Bài toán tối ưu nhiều mục tiêu: ................................................................ 5
1.3 Các khái niệm tối ưu: ............................................................................... 6
1.3.1 Tối ưu Pareto: ........................................................................................... 6
1.3.2 Tối ưu Pareto yếu và chặt: ....................................................................... 7
CHƯƠNG 2: BÀI TOÁN TỐI ƯU NHIỀU MỤC TIÊU VỚI HÀM MỤC
TIÊU LÀ HÀM PHÂN TUYẾN TÍNH .......................................................... 20
2.1 Giới thiệu bài toán: ................................................................................ 20
2.2 Các điều kiện tối ưu: .............................................................................. 20
2.3 Hàm phạt: ............................................................................................... 25
2.4 Nghiệm bài toán tối ưu........................................................................... 29
KẾT LUẬN ..................................................................................................... 34
MỘT SỐ KÝ HIỆU DÙNG TRONG LUẬN VĂN
Tập số thực ( = 1 )
Tập hợp số thực mở rộng
n
Không gian Euclide n chiều trên trường số thực
=
k+
{x ∈
k
/ x i ≥ 0,i =
1,..., k} tập các vectơ không âm
M m× n ( )
Tập hợp các ma trận cấp m × n
∅
Tập hợp rỗng
E(P)
Tập hợp nghiệm Pareto của bài toán (MOLP)
Ew(P)
Tập hợp nghiệm Pareto yếu của bài toán (MOLP)
E(P 1 )
Tập hợp nghiệm Pareto của bài toán (P 1 )
Ew(P 1 )
Tập hợp nghiệm Pareto yếu của bài toán (P 1 )
E(P 2 )
Tập hợp nghiệm Pareto của bài toán (P 2 )
Ew(P 2 )
Tập hợp nghiệm Pareto yếu của bài toán (P 2 )
u.s.c
Nửa liên tục trên
l.s.c
Nửa liên tục dưới
[ x1 , x 2 ]
=
{x ∈
n
: x=
(1 − λ ) x1 + λx 2 , 0 ≤ λ ≤ 1} gọi là đoạn thẳng
đóng nối x1 và x 2
xi
Tọa độ thứ i của vectơ x
xT
Vectơ hàng ( chuyển vị của x)
x, y = x T y
( )
∇f x
int k+
Tích vô hướng của hai vectơ x và y
Gradient của f tại x
Tập hợp các điểm trong của k+
1
CHƯƠNG 1
BÀI TOÁN TỐI ƯU NHIỀU MỤC TIÊU
1.1 Một số khái niệm cơ bản:
Định nghĩa 1.1: Quan hệ hai ngôi
Cho tập hợp A ≠ ∅ , quan hệ hai ngôi trên A là tập hợp con ℜ của
A × A . Khi ( x, y ) ∈ℜ ta nói x, y có quan hệ với nhau theo quan hệ ℜ và còn
ghi: x ℜ y hoặc ℜ (x,y), nếu ( x, y ) ∉ℜ ta ghi x ℜ y
Định nghĩa 1.2
Cho ℜ là một quan hệ 2 ngôi trên tập A, ta nói ℜ có tính chất: Phản xạ
nếu ( x, x ) ∈ℜ với mọi x ∈ A . Do đó, ℜ không có tính phản xạ
⇔ ∃x ∈ A, ( x, x ) ∉ℜ .
i. Đối xứng nếu ∀x ∈ A, ∀y ∈ A ( xℜy ⇒ yℜx ) .
ii. Phản xứng nếu và chỉ nếu:
(
)
∀x, y ∈ A, x ≠ y, xℜy ⇒ yℜx .
Do đó ℜ có tính phản xứng ⇔ ( ( xℜy ∧ yℜx ) ⇒ x =y ) .
iii. Bắc cầu nếu ∀x, y, z ∈ A, xℜy ∧ yℜz ⇒ xℜz .
Do đó ℜ không có tính bắc cầu ⇔ ( ∃x, y, z ∈ A : xℜy ∧ yℜz ∧ xℜz ) .
Định nghĩa 1.3
Cho ℜ là một quan hệ 2 ngôi trên tập A khi đó:
i. ℜ được gọi là một quan hệ tương đương nếu ℜ thỏa các tính chất phản
xạ, đối xứng và bắc cầu.
ii. ℜ được gọi là tiền thứ tự nếu ℜ có tính chất phản xạ và bắc cầu.
Trong trường hợp quan hệ ℜ là tiền thứ tự thì cặp (A, ℜ ) được gọi là tập
tiền thứ tự. Để thuận tiện ta thay đổi quan hệ ℜ là . Do đó ta quy ước viết:
x y thay cho xℜy , x y thay cho x ℜy .
2
Với bất kỳ một quan hệ là tiền thứ tự nào thì cũng có hai quan hệ khác
được định nghĩa như sau:
x y ⇔ x y và y x
x ∼ y ⇔ x y và y x
Mệnh đề 1.1
Cho là một tiền thứ tự trên tập A. Khi đó:
• Quan hệ định nghĩa như trên là không phản xạ và bắc cầu.
• Quan hệ ∼ định nghĩa như trên là quan hệ tương đương.
Định nghĩa 1.4
Quan hệ hai ngôi được gọi là quan hệ thứ tự nếu có các tính chất:
phản xạ, bắc cầu và phản xứng.
Quan hệ hai ngôi được gọi là quan hệ thứ tự từng phần nếu có các
tính chất phản xạ, bắc cầu .
Trong luận văn này chúng ta sử dụng quan hệ thứ tự trên không gian
Euclide_ n . Khi đó ta có một số thứ tự trên n .
Ký hiệu≼ Định nghĩa
Tên gọi
x≤y
Nếu x i ≤ yi , ∀i =1,.., n
Thứ tự từng phần yếu
x 0 .
Ví dụ: K = 2+ ={x ∈ 2 / x i ≥ 0,i =1, 2} là nón.
3
Định nghĩa 1.6
Nón K trong n gọi là:
• Không tầm thường nếu K ≠ n và K ≠ ∅ .
• Lồi nếu tx1 + (1 − t ) x 2 ∈ K với mọi x1 , x 2 ∈ K và mọi t ∈ ( 0,1) .
• Nhọn nếu K ∩ ( −K ) ⊂ {0} .
Mệnh đề 1.2: Cho một quan hệ thứ tự trên n , ta định nghĩa tập:
K=
{y − x / x y} . Khi đó
K là nón.
Chứng minh:
Cho u ∈ K , khi đó u= y − x với x, y ∈ y n , x y .
Ta có: λx λy , với mọi λ > 0 ⇒ λu = λ ( x − y ) = λx − λy ∈ K , với mọi λ > 0 .
Vậy K là nón.
Mệnh đề 1.3`
Cho là một quan hệ hai ngôi trên n , khi đó:
i. 0 ∈ K nếu là phản xạ.
ii. K lồi nếu là bắc cầu.
iii. K nhọn nếu là phản xứng.
Chứng minh:
i.Giả sử quan hệ là phản xạ. Khi đó: x x, ∀x ∈ n ⇒ 0 = x − x ∈ K .
ii. Giả sử quan hệ là bắc cầu. Cho u, v ∈ K , nên u − 0 ∈ K và 0 − v ∈ −K ,
điều này có nghĩa là:
0 u, − v 0 kéo theo − v u ( do là bắc cầu).
Do đó u + v ∈ K tức K lồi.
iii. Lấy 0 ≠ u ∈ K thì u = y − x ∈ K và −u= x − y ∈ −K với x, y ∈ y n .
⇒ y x và x y nên x = y (mâu thuẫn u ≠ 0 ).
4
Định nghĩa 1.7
Cho K là nón, ta định nghĩa quan hệ K trên n như sau: x K y ⇔ y − x ∈ K .
Định nghĩa 1.8
Tập K ⊂ n được gọi là lồi nếu: ∀x1 , x 2 ∈ K, ∀λ ∈ : 0 ≤ λ ≤ 1 ⇒ (1 − λ ) x1 + λx 2 ∈ K
Nhận xét: Tập rỗng là tập lồi, tập một điểm cũng là tập lồi.
Định nghĩa 1.9
Cho x1 , x 2 ∈ n , đoạn thẳng nối x1 , x 2 được định nghĩa như sau:
[ x1 , x 2 ]= {x ∈ n : x= (1 − λ ) x1 + λx 2 , 0 ≤ λ ≤ 1}
Nhận xét: Tập K là lồi khi và chỉ khi ∀x1 , x 2 ∈ K ⇒ [ x1 , x 2 ] ∈ K
Mệnh đề 1.4: Cho K là nón và thứ tự theo nón K xác định như trên là
bảo toàn với phép nhân vô hướng và cộng thông thường trong n . Ta có:
1. K là phản xạ nếu 0 ∈ K .
2. K là bắc cầu nếu K lồi.
3. K là phản xứng nếu K nhọn.
Chứng minh:
Cho x, y, z ∈ y n và 0 < λ ∈ . Với x K y ⇔ y − x ∈ K . Do K là nón nên :
λ ( y − x ) ∈ K ⇒ λx K λy
y − z = ( z + y ) − ( z + x ) ⇒ z + x K z + y
1. Cho x ∈ n , khi đó x − x = 0 ∈ K ⇔ x K x.
2. Cho x K y, y K z , khi đó y − x ∈ K, z − y ∈ K . Do K lồi nên:
y − x + z − y = z − x ∈ K ⇒ x K z
3. Cho x, y ∈ y n với x K y, y K x . Khi đó ta có
y − x ∈ K, x − y ∈ K ⇒ y − x ∈ K ∩ ( −K )=
{0} ⇒ x=
y.
5
Định nghĩa 1.10
Nửa không gian đóng của n là tập hợp có dạng {x ∈ n : a, x ≥ b} hay
{x ∈
n
: a, x ≤ b} trong đó a ∈ n , b ∈ cho trước.
Định nghĩa 1.11
Tập hợp X ⊂ n được gọi là tập lồi đa diện nếu nó là giao hữu hạn của
các nửa không gian đóng.
Từ định nghĩa trên ta suy ra dạng biểu diễn chung của một tập lồi đa diện
X ⊂ n là X =
{x ∈ n : Ax ≥ b} trong đó A ∈ M m×n ( ) , b ∈ m cho trước.
Ví dụ: Tập lồi đa diện
=
X1 {( x1 , x 2 , x 3 ) ∈ 3 : x1 + x 2 + x 3 ≤ 1} là giao của 8
nửa không gian đóng trong đó mỗi nửa không gian đóng có dạng
3
3
∈
δi x i ≤ 1 trong đó δ1 , δ2 , δ3 ∈ {−1,1} .
x
,
x
,
x
:
( 1 2 3 )
∑
1
Định nghĩa 1.12
Một tập lồi đa diện không rỗng và bị chặn được gọi là đa diện lồi.
Định nghĩa 1.13
Cho hàm f : n → , x0 ∈ n , hàm f được gọi là nửa liên tục trên (u.s.c)
tại x0 nếu lim sup f ( x ) ≤ f ( x0 ) .
x→ x
0
Định nghĩa 1.14
Cho hàm f : n → , x0 ∈ n , hàm f được gọi là nửa liên tục dưới (l.s.c)
tại x0 nếu lim inf f ( x ) ≥ f ( x0 ) .
x→ x
0
Hàm f nửa liên tục trên (u.s.c) tại x0 và nửa liên tục dưới (l.s.c) tại x0
thì hàm f liên tục tại x0 .
6
1.2 Bài toán tối ưu nhiều mục tiêu:
Ta xét bài toán tối ưu nhiều mục tiêu sau:
M in f(x) = ( f1 (x),..., f k (x) )
x∈X
( MOLP )
Trong đó:
• fi : n → ( i =
1,..., k ) là các hàm tuyến tính
• X là tập lồi đa diện trong n : X =
{x ∈ n | Ax ≤ b} , A là ma trận cấp
m × n, b ∈ m .
X gọi là không gian quyết định.
Đặt Y =∈
f (x) =
( f1 (x),..., f k (x) )} gọi là không gian hàm mục tiêu
{y y k | y =
Định nghĩa 1.15: Một điểm x* ∈ X của bài toán ( MOLP ) được gọi là
nghiệm lý tưởng nếu:
f i ( x *) ≤ f i ( x ) , x ∈ X, ∀i =1,..., k
Nói một cách khác một nghiệm lý tưởng là một nghiệm mà nó phải thỏa
mãn tất cả các hàm mục tiêu cần tối ưu ứng với miền chấp nhận được là X.
Thực tế thì những nghiệm như vậy rất ít khi tồn tại nên ta đưa ra một số khái
niệm khác về tối ưu có vẻ “mềm dẻo” hơn đó là nghiệm tối ưu Pareto.
Định nghĩa 1.16
Một nghiệm x = ( x1 ,..., x n ) được gọi là trội hơn nghiệm y = ( y1 ,..., y n ) ký
hiệu x ≤ y nếu:
f i ( x ) ≤ f i ( y ) , ∀i =1,..., k
∃j ∈ {1,..., k} : f j ( x ) < f j ( y )
7
1.3 Các khái niệm tối ưu:
1.3.1 Tối ưu Pareto:
Định nghĩa 1.17: Một điểm x* ∈ X được gọi là một nghiệm tối ưu
Pareto (nghiệm hữu hiệu) của bài toán ( MOLP ) nếu không tồn tại x ∈ X, x ≠ x*
sao cho x trội hơn x* , nghĩa là: f ( x ) < f ( x* ) . Ký hiệu tập hợp nghiệm Pareto
của bài toán ( MOLP ) là E (P).
Nếu x* ∈ X là một nghiệm tối ưu Pareto thì f ( x* ) gọi là điểm hữu hiệu,
tập tất cả các điểm hữu hiệu ký hiệu là Yeff .
1.3.2 Tối ưu Pareto yếu và chặt:
Định nghĩa 1.18: Một điểm x* ∈ X được gọi là một nghiệm tối ưu Pareto
yếu (nghiệm hữu hiệu yếu) của bài toán ( MOLP ) nếu không tồn tại x ∈ X sao cho:
f ( x ) f ( x * ) . Ký hiệu tập hợp nghiệm Pareto yếu của bài toán ( MOLP ) là E w ( P ) .
Nếu x* ∈ X là một nghiệm tối ưu Pareto yếu thì f ( x* ) gọi là điểm hữu
hiệu yếu, tập tất cả các điểm hữu hiệu yếu ký hiệu là Yw −eff .
Ví dụ: Xét bài toán
− x1 + 1
Maxf1 ( x ) = − x − x + 3
1
2
Maxf ( x ) = ( − x2 − 1)
2
x1 + 2 x2 + 1
Maxf3 ( x ) = x2
=
x ∈ S {( x1 , x2 ) : x1 + x2 ≤ 2; x1 , x2 ≥ 0}
Trong đó E ( P ) là phần gạch chéo và các đường đậm nét trong hình vẽ.
Những điểm thuộc đường đứt nét và là điểm trong của S không thuộc tập
E ( P ) . Tập E w ( P ) gồm E ( P ) hợp với những điểm nằm trên đường đứt nét.
Từ hình vẽ ta nhận thấy E ( P ) có thể không đóng, còn E w ( P ) có thể đóng.
8
Định nghĩa 1.19
Một điểm x* ∈ X được gọi là một nghiệm tối ưu Pareto chặt của bài
toán ( MOLP ) nếu không tồn tại x ∈ X, x ≠ x* sao cho: f ( x ) ≤ f ( x* ) . Ký hiệu tập
hợp nghiệm Pareto chặt của bài toán ( MOLP ) là Es ( P ) .
Từ định nghĩa trên ta có nhận xét:
• Yeff ⊂ Yw −eff .
• Es ( P ) ⊂ E ( P ) ⊂ E w ( P ) .
Định nghĩa 1.20: Cho X ⊂ n , một ánh xạ f : n → và x ∈ X . Khi đó:
}
) {
ii. L ( f ( x ) ) =
f ( x )} được gọi là mặt mức của f tại x .
{x ∈ X | f ( x ) =
L ( f ( x )) \ L ( f ( x )) =
iii. L ( f ( x ) ) =
{x ∈ X | f ( x ) < f ( x )} được gọi là tập mức
(
i. L≤ f ( x ) =
x ∈ X | f ( x ) ≤ f ( x ) được gọi là tập mức của f tại x .
=
<
≤
=
chặt của f tại x .
Định lý 1.1
Cho x* ∈ X và định nghĩa
=
y q f q ( x * ) , q ∈ {1,..., k} , khi đó:
i. x* là một nghiệm tối ưu Pareto chặt nếu và chỉ nếu
L ( y ) = {x } .
k
*
≤
q
q =1
ii. x* là một nghiệm tối ưu Pareto nếu và chỉ nếu
( yq ) .
L≤ ( yq ) = L=
k
k
=
q 1=
q 1
0 sao cho
mỗi i và ∀x ∈ X thõa: fi ( x ) < fi ( x* ) và tồn tại chỉ số j sao cho: f j ( x* ) < f j ( x ) .
Hơn nữa:
f i ( x *) − f i ( x )
f j ( x ) − f j ( x* )
≤M.
Khi đó, giá trị mục tiêu đạt được tương ứng tại x* là y* = f ( x* ) gọi là
điểm hữu hiệu chính thường.
10
• x* không là nghiệm tối ưu Pareto chính thường của bài toán ( P ) nếu
mỗi M > 0 có một x ∈ X và một chỉ số i sao cho: fi ( x ) < fi ( x* ) và
fi ( x* ) − fi ( x )
f j ( x ) − fi ( x
*
)
> M, ∀j sao cho f j ( x * ) < f j ( x ) .
k
Ta xét bài toán lồi sau đây: min ∑ λi fi ( x ) ( P1 )
x∈X
i =1
Bài toán ( P1 ) gọi là bài toán tổng trọng số, trong đó λi ,i =
1,..., k là các
trọng số không âm đối với các hàm mục tiêu và
k
∑λ
i =1
i
=1 .
Định lý 1.2 (Geoffrion (1968))
Cho λi > 0,i =1,..., k với
( P1 ) thì
k
∑λ
i =1
i
=1 . nếu x * ∈ X là nghiệm tối ưu của bài toán
x * là nghiệm tối ưu Pareto chính thường của bài toán ( MOLP ) .
Chứng minh:
Cho x* ∈ X là nghiệm tối ưu của bài toán ( P1 ) . Ta muốn chứng minh:
x * ∈ X là nghiệm tối ưu Pareto, ta giả sử tồn tại x ' ∈ X sao cho f ( x ') < f ( x * ) , với
x * ) , ∀i 1,..., k ; ∃j ∈ {1,..., k} : f j ( x ' ) < f j ( x * )
λ i > 0,i =1,..., k và f i ( x ') ≤ f i (=
dẫn đến:
k
k
∑ λ f ( x ') < ∑ λ f ( x *) (mâu thuẫn)
i i
=i 1 =i 1
Cho M =
( k − 1) max
i, j
i i
λi
( k ≥ 2 ) . Giả sử x* không là nghiệm tối ưu Pareto
λj
chính thường của bài toán ( MOLP ) , tức là tồn tại một i và x ∈ X sao cho
f i ( x ) < f i ( x * ) và
f i ( x * ) − f i ( x ) > M ( f j ( x ) − f j ( x *) ) , ∀j ≠ i với f j ( x *) < f j ( x ) . Do đó
fi ( x* ) − fi ( x ) >
k −1
λ j ( f j ( x ) − f j ( x *) ) , ∀j ≠ i
λi
11
Nhân hai vế của bất đẳng thức trên với
λi
rồi sau đó lấy tổng hai vế
k −1
như sau:
λi
∑ k − 1 ( f ( x ) − f ( x ) ) > ∑ λ ( f ( x ) − f ( x *) )
*
i
i≠ j
i
)
(
j≠ i
j
j
j
⇒ λ i f i ( x * ) − f i ( x ) > ∑ λ j f j ( x ) − ∑ λ j f j ( x *)
j≠ i
j≠ i
⇒ λ i f i ( x * ) + ∑ λ jf j ( x * ) > λ i f i ( x ) + ∑ λ jf j ( x )
j≠ i
j≠ i
⇒ ∑ λi fi ( x* ) > ∑ λi fi ( x )
k
k
=i 1 =i 1
Ta gặp mâu thuẫn, điều đó nói rằng giả sử là sai, khi đó x* là nghiệm tối ưu
Pareto chính thường của bài toán ( MOLP ) .
Định lý 1.3
Cho X ⊂ n là một tập lồi và các hàm fi : n → là các hàm lồi,
i = 1,..., k . Khi đó bất đẳng thức f i < 0 với i = 1,..., k vô nghiệm trên X thì tồn tại
k
λ i ≥ 0,i =1,..., k , ∑ λ i =1 và với mọi x ∈ X thỏa mãn:
i =1
k
∑λ f (x) ≥ 0 .
i =1
i i
Định lý 1.4 (Geoffrion (1968))
Cho X ⊂ n là một tập lồi và các hàm fi : X → là các hàm lồi, i = 1,..., k .
Khi đó x* là nghiệm tối ưu Pareto chính thường của bài toán ( MOLP ) nếu và
chỉ nếu x* ∈ X là nghiệm tối ưu của bài toán ( P1 ) .
Chứng minh:
Do định lý 1.3, chúng ta chỉ cần chứng minh điều kiện cần.
Giả sử x* là nghiệm tối ưu Pareto chính thường, ta có số M > 0 sao cho mỗi
i ∈ {1,..., k}
f i ( x ) < f i ( x * )
hệ:
, ∀j ≠ i vô nghiệm. Áp dụng định
*
*
f i ( x ) + Mf j ( x ) < f i ( x ) + Mf j ( x )
12
k
lý 1.3 đối với hệ trên thì tồn tại λij ≥ 0, j =1,..., k , ∑ λij =1 và với mọi x ∈ X thỏa
j=1
mãn:
(
λ f ( x ) + ∑ λ ( f i ( x ) + Mf j ( x ) ) ≥ λ f ( x ) + ∑ λ ij f i ( x * ) + Mf j ( x * )
k
i
i i
j≠ i
k
i
j
i
i i
*
j≠ i
)
⇒ λ ii f i ( x ) + ∑ λ ijf i ( x ) +M ∑ λ ijf j ( x ) ≥ λ ii f i ( x * ) + ∑ λ ijf i ( x * ) +M ∑ λ ijf j ( x * )
k
k
k
k
j≠ i
j≠ i
j≠ i
j≠ i
⇒ ∑ λ ijf i ( x ) + M ∑ λ ijf j ( x ) ≥ ∑ λ ijf i ( x * ) + M ∑ λ ijf j ( x * )
k
=j 1
k
k
j≠ i
=j 1
k
j≠ i
⇒ f i ( x ) + M ∑ λ ijf j ( x ) ≥ f i ( x * ) + M ∑ λ ijf j ( x * )
k
k
j≠ i
j≠ i
Lấy tổng hai vế bất đẳng thức với biến chạy là i ta được:
∑ fi ( x ) + M∑∑ λijf j ( x ) ≥ ∑ fi ( x* ) + M∑∑ λijf j ( x* )
k
k
i=
1
k
k
i=
1 j≠ i
k
i=
1
k
i=
1 j≠ i
k
k
k
k
⇒ ∑ 1 + ∑ λ ij f j ( x ) ≥ ∑ 1 + ∑ λ ij f j ( x * ) .
j=
1
i≠ j
j=
1
i≠ j
k
i≠ j
Ta có thể chuẩn hóa giá trị 1 + ∑ λij để lấy tổng đến 1 chứa những số dương
λ i ,i =
1,.., k .
Vậy x* là nghiệm tối ưu của bài toán ( P1 ) .
Định nghĩa 1.22[5]
Cho Y ⊂ k và y ∈ Y
1. Nón tiếp xúc của Y tại y ∈ Y là:
{
}
k
TY ( y ) = d ∈ yy
| ∃{ t k } ⊂ , { y k } ⊂ Y saocho { y k } → y, t k ( y k − y ) → d
2. Bao nón của Y là:
cone ( Y ) =
{αy : α ≥ 0, y ∈ Y} = αY.
α
Mệnh đề 1.5[5]
1. Nón tiếp xúc TY ( y ) là một nón đóng.
13
2. Nếu Y là tập lồi thì
=
TY ( y ) cl ( cone ( Y − y ) ) , chúng là nón lồi đóng.
Chứng minh:
1. Ta có 0 ∈ TY ( y ) vì nếu y k= y, ∀k và TY ( y ) là một nón: cho
α > 0, d ∈ TY ( y ) thì αd ∈ TY ( y ) .
Lấy dãy {d l } ⊂ TY ( y ) , y ∈ Y và {d l } → d . Từ d l ∈ TY ( y ) , ∀l sẽ có những
dãy {t l,k } ⊂ y, {yl,k } ⊂ Y thõa định nghĩa 1.12. Từ sự hội tụ ta cố định l, có
những k l thỏa:
1
t l,k ( y l,k − y ) − d l ≤ , ∀k ≥ k l , chúng ta cố định k l khi đó nếu l → ∞ thì dãy
l
{t ( y
l,k l
l,k l
}
− y ) → d tức là d ∈ TY ( y ) .
2. Cho Y là tập lồi , y ∈ Y . Qua định nghĩa của bao đóng và bao nón, rõ
ràng cl ( cone ( Y − y ) ) là nón lồi đóng.
• Ta có: TY ( y ) ⊂ cl ( cone ( Y − y ) ) , thật vậy lấy d ∈ TY ( y ) , có dãy
{ t k } ⊂ y, { y k } ⊂ Y
sao cho {y k } → y, t k ( y k − y ) → d . Từ t k ( y k − y ) ∈ α ( Y − y ) , α > 0
dẫn đến d ∈ cl ( cone ( Y − y ) ) .
• Do TY ( y ) là tập đóng, ta chứng minh cone ( Y − y ) ⊂ TY ( y ) .
α ( y '− y ) với α ≥ 0, y ' ∈ Y .
Cho d ∈ cone ( Y − y ) tức là d =
1
1
Ta định nghĩa y k :=1 − y + y ' ∈ Y và t k =αk ≥ 0 .
k
k
k −1
1
y + y ' − y =
α ( ( k − 1) y + y '− ky ) =
α ( y '− y ) .
k
k
Khi đó : t k ( y k − y ) =αk
Như vậy {y k } → y, t k ( y k − y ) → d dẫn đến d ∈ TY ( y ) .
14
Định nghĩa 1.23[5]
1. (Borwein (1977)): Một nghiệm x ∈ X được gọi là nghiệm hữu hiệu
(
)
chính thường theo định nghĩa Borwein nếu TY + f ( x ) ∩ ( − k+ ) ={0} .
k
+
2. (Benson (1979)): Một nghiệm x ∈ X được gọi là nghiệm hữu hiệu
( (
))
chính thường theo định nghĩa Benson nếu cl cone Y + k+ − f ( x ) ∩ ( − k+ ) ={0} .
Định lý 1.5[5]
1. Nếu x ∈ X là nghiệm hữu hiệu chính thường theo định nghĩa Benson
thì x là nghiệm hữu hiệu chính thường theo định nghĩa Borwein.
2. Nếu X là tập lồi và f k : n → là lồi thì cả hai định nghĩa Borwein và
Benson là trùng nhau.
Mệnh đề 1.6[5]
Nếu x ∈ X là nghiệm hữu hiệu chính thường theo định nghĩa Borwein
thì x là nghiệm hữu hiệu Pareto.
Chứng minh:
Giả sử x không là nghiệm hữu hiệu Pareto nên tồn tại d ∈ k+ , d ≠ 0
sao cho:=
d f ( x ) − y với y ∈ Y .
1
k
Cho d k =
t k k,=
k 1, 2,... .
1 − d ∈ + và =
k
1
1
k
Khi đó: y + d=
f ( x ) − d + 1 − =
d f ( x ) − d → f ( x ) khi k → ∞ .
(
)
k
k
Và t k y + d k − f ( x ) = k −d + 1 − d = −d → −d, k → ∞ .
k
(
1
)
Như vậy TY + f ( x ) ∩ ( − k+ ) ≠ {0} , dẫn đến x không là nghiệm hữu hiệu
k
+
chính thường theo định nghĩa Borwein (mâu thuẫn).
- Xem thêm -