Luận văn Thạc sĩ Toán học: 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

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

60 46 01 02

Chuyên ngành: Toán giải tích Mã số:

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

∈

≥

/ x

tập các vectơ không âm



+

Không gian Euclide n chiều trên trường số thực {

} 0,i 1,..., k

Tập hợp các ma trận cấp m n×

( ) m nM × 

Tập hợp rỗng

∅

Tập hợp nghiệm Pareto của bài toán (MOLP)

Tập hợp nghiệm Pareto yếu của bài toán (MOLP)

E(P) Ew(P)

Tập hợp nghiệm Pareto của bài toán (P1)

Tập hợp nghiệm Pareto yếu của bài toán (P1)

E(P1) Ew(P1)

Tập hợp nghiệm Pareto của bài toán (P2)

Tập hợp nghiệm Pareto yếu của bài toán (P2)

E(P2) Ew(P2)

Nửa liên tục trên

u.s.c

l.s.c

∈

+ λ

≤ λ ≤

: x

gọi là đoạn thẳng

( = − λ 1

)

[

] x , x



x , 0 2

Nửa liên tục dưới {

} 1

đóng nối

1x và

Tọa độ thứ i của vectơ x

Vectơ hàng ( chuyển vị của x)

x, y

T x y

Tích vô hướng của hai vectơ x và y

Gradient của f tại x

( f x∇

)

int

+ Tập hợp các điểm trong của

+

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

x, y ∈ℜ ta nói x, y có quan hệ với nhau theo quan hệ ℜ và còn

A A× . Khi (

)

x, y ∉ℜ ta ghi x ℜ y

ghi: x ℜ y hoặc ℜ (x,y), nếu (

)

Đị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

)

y x

ℜ ⇒ ℜ . x y

)

∀ ∈ ∀ ∈ ( i. Đối xứng nếu x A, y A

ii. Phản xứng nếu và chỉ nếu: ( y, x y

) ℜ ⇒ ℜ .

⇔ ℜ ∧ ℜ ⇒ =

x y y x

Do đó ℜ có tính phản xứng

)

(

)

(

∈

x z

ℜ ∧ ℜ ⇒ ℜ .

∀ ≠ ∈ x, y A, x y x

Do đó ℜ không có tính bắc cầu

iii. Bắc cầu nếu x, y, z A, x y y z ∀ ( ⇔ ∃

) ℜ ∧ ℜ ∧ ℜ .

∈ 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ℜ . y thay cho x yℜ , x

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 .

Tên gọi

Ký hiệu

Định nghĩa

Thứ tự từng phần yếu

Nếu

≼

x y≤ x i 1,.., n ≤ ∀ = y , i

Nếu

Thứ tự từng phần

y

x i 1,.., n, x ≠ y ≤ ∀ = y , i

Nếu

Thứ tự từng phần chặt

x i 1,.., n < ∀ = y , i

hoặc x

Nếu

Thứ tự tự điển

x y Lex x y<

≤

max

Nếu

{ } x

{ } y

Max_thứ tự

= i 1,..,n

x y Mo

Định nghĩa 1.5

λ ∈ với mọi x K,

Một tập con

K ⊆  được gọi là nón nếu: x K

∈ λ ∈ λ >

≥

/ x

là nón.

Ví dụ:



+= 

{ = ∈ x

} = 0,i 1, 2

Định nghĩa 1.6

Nón K trong

n gọi là:

• Không tầm thường nếu

∈ với mọi

K ≠  và K ≠ ∅ .

( ) 0,1∈

• Lồi nếu

( ) + − 1 t x K 2

∩ − ⊂ K

)

(

{ } 0

• Nhọn nếu

n , ta định nghĩa tập:

x , x K∈ và mọi

Mệnh đề 1.2: Cho một quan hệ thứ tự  trên

−

y x / x

{

} y



 . Khi đó K là nón.

Chứng minh:

y x

Cho u K∈

= − với

 , khi đó u

⇒ λ = λ u

− x y

y K

, với mọi

0λ >

= λ − λ ∈ , với mọi

0λ > .

Ta có: x λ

)

(

λ

Vậy K là nón. 

x, y , x ∈   . y

Mệnh đề 1.3`

n , khi đó:

Cho  là một quan hệ hai ngôi trên

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:

x, x

∀ ∈ ⇒ = − ∈ 0

x x K



i. Giả sử quan hệ  là phản xạ. Khi đó:



ii. Giả sử quan hệ  là bắc cầu. Cho u, v K∈

 , nên u 0 K và 0 v − ∈



 ,

điều này có nghĩa là:

−  ( do  là bắc cầu).

− u, v

 kéo theo v

+ ∈

Do đó u v K

 tức K lồi.

− ∈ − K

iii. Lấy 0

 và u

 thì u

 với

= − ∈ ≠ ∈ y x K − = − ∈ − x y K u K x, y ∈  .

y= (mâu thuẫn u 0≠ ). 

x và x y ⇒  y  nên x

Định nghĩa 1.7

Cho K là nón, ta định nghĩa quan hệ

n như sau:

Kx 

K trên

⇔ − ∈ y y x K

Định nghĩa 1.8

∀

∈ ∀λ ∈

≤ λ ≤ ⇒ − λ

: 0

x K

( 1

)

Tập



x , x K, 1 2

+ λ ∈ 2

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.

K ⊂  được gọi là lồi nếu:

Định nghĩa 1.9

Cho

x , x ∈  , đoạn thẳng nối

+ λ

≤ λ ≤

: x

( = − λ 1

)



[

]

x , x 1

x , 0 2

{ = ∈ x

} 1

∀

∈ ⇒

∈ K

Nhận xét: Tập K là lồi khi và chỉ khi

[

]

x , x K 2

x , x 1

x , x được định nghĩa như sau:

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ó:

K là phản xạ nếu 0 K∈

 .

K là bắc cầu nếu K lồi.

K là phản xứng nếu K nhọn.

Chứng minh:

Cho

. Do K là nón nên :

Kx 

⇔ − ∈ y y x K x, y, z ∈  và 0 < λ ∈  . Với

λ λ x y

( − = y z

) y x K ( + z y

)

x x

− = ∈ ⇔ 0 K

1. Cho

− z x + z y − ∈ ⇒ λ (  K ) + ⇒ + z x  K   

 K



− ∈

x ∈  , khi đó

− ∈ . Do K lồi nên:

2. Cho

x y, y z  K  , khi đó y x K, z y K

x − + − = − ∈ ⇒  y x z y z z x K

3. Cho

− ∈

y x K, x y K

y x K

( − ∈ ⇒ − ∈ ∩ −

) { } = ⇒ = 0

x y, y x x, y ∈  với  K  . Khi đó ta có



Định nghĩa 1.10

Nửa không gian đóng của

hay

n là tập hợp có dạng {

} b

∈

≤

: a, x

trong đó

a ∈  , b ∈  cho trước.



{

} b

∈ ≥ x : a, x 

Định nghĩa 1.11

Tập hợp

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 ⊂  được gọi là tập lồi đa diện nếu nó là giao hữu hạn của

≥

: Ax

trong đó

(

)



× m n

{ = ∈ X x

} b

∈

≤

: x

là giao của 8

∈ ∈ A M , b   cho trước. X ⊂  là

Ví dụ: Tập lồi đa diện

)



X 1

x , x , x 2

{ (

} 1

nửa không gian đóng trong đó mỗi nửa không gian đóng có dạng

trong đó

} 1,1

)

{ δ δ δ ∈ − , 1 3

∑ :

∈ δ ≤ x x , x , x 2  (    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

x ∈  , hàm f được gọi là nửa liên tục trên (u.s.c)

n →

 ,

tại

( f x

)

0x nếu

( f x 0

≤ lim sup → x x 0

Định nghĩa 1.14

Cho hàm

x ∈  , hàm f được gọi là nửa liên tục dưới (l.s.c)

n →

 ,

tại

( f x

)

( f x 0

0x nếu

Hàm f nửa liên tục trên (u.s.c) tại

0x và nửa liên tục dưới (l.s.c) tại

thì hàm f liên tục tại

0x .

≥ lim inf → x x 0

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:

(

) MOLP

(

)

f (x),..., f (x) 1

M in f(x) ∈ x X

Trong đó:

i 1,..., k

là các hàm tuyến tính

)



( → = 

•

if :

≤

| Ax

, A là ma trận cấp

• X là tập lồi đa diện trong

n :



{ = ∈ X x

} b

X gọi là không gian quyết định.

| y

gọi là không gian hàm mục tiêu

Đặt

( f x

)

(



f (x),..., f (x) 1

{ = ∈ y

} )

MOLP được gọi là

m n, b× ∈  .

Định nghĩa 1.15: Một điểm

*x X∈ của bài toán (

)

nghiệm lý tưởng nếu:

≤

∈ ∀ =

i 1,..., k

)

(

( f x * i

) f x , x X, i

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

x ,..., x

Một nghiệm

được gọi là trội hơn nghiệm

ký

(

)

(

)

y ,..., y 1

hiệu x

y≤ nếu:

≤

)

( ) ) ( ∀ = i 1,..., k f y , f x i i ( { ( ) } ∃ ∈ f y 1,..., k : f x j j

<   

1.3 Các khái niệm tối ưu:

1.3.1 Tối ưu Pareto:

*x X∈ được gọi là một nghiệm tối ưu

Định nghĩa 1.17: Một điểm

Pareto (nghiệm hữu hiệu) của bài toán (

)

*x , nghĩa là:

. Ký hiệu tập hợp nghiệm Pareto

sao cho x trội hơn

( f x

)

( f x

MOLP là E (P).

của bài toán (

)

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à effY .

∈ ≠ x X, x x MOLP nếu không tồn tại

1.3.2 Tối ưu Pareto yếu và chặt:

*x X∈ được gọi là một nghiệm tối ưu Pareto

Định nghĩa 1.18: Một điểm

MOLP nếu không tồn tại x X∈ sao cho:

yếu (nghiệm hữu hiệu yếu) của bài toán (

)

MOLP là

. Ký hiệu tập hợp nghiệm Pareto yếu của bài toán (

)

( wE P .

)

( f x

)

( f x

*x X∈ là một nghiệm tối ưu Pareto yếu thì

Nếu

( 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à w effY −

Ví dụ: Xét bài toán

(

)

Maxf 1

Maxf

(

)

1 + ) 1 +

− + x 1 − − x x 1 2 ( − − x 2 + 2 x 1

x 2

Maxf

x 2

( ∈ =

≤

≥

x S

)

, x x 1 2

x 1

x 2

, x x 1 2

) x { (

} 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

) wE P gồm

(

)E P . Tập

(

)E P hợp với những điểm nằm trên đường đứt nét.

(

wE P có thể đóng.

Từ hình vẽ ta nhận thấy

(

)

)E P có thể không đóng, còn

(

Định nghĩa 1.19

*x X∈ được gọi là một nghiệm tối ưu Pareto chặt của bài

Một điểm

≤

sao cho:

. Ký hiệu tập

toán (

)

( f x

)

( f x

hợp nghiệm Pareto chặt của bài toán (

) MOLP là

( sE P .

)

∈ ≠ x X, x x MOLP nếu không tồn tại

Từ định nghĩa trên ta có nhận xét:

• eff Y

w eff

⊂

( s E P

)

( E P

)

( w E P

)

•

f : →

 và x X∈ . Khi đó:

Y −⊂

≤

được gọi là tập mức của f tại x .

( x X | f x

)

≤

)

( f x

X ⊂  , một ánh xạ

Định nghĩa 1.20: Cho { = ∈

} )

( ( L f x

)

ii.

được gọi là mặt mức của f tại x .

( x X | f x

)

( f x

( ( L f x

)

{ = ∈

iii.

được gọi là tập mức

( x X | f x

)

≤

( f x

)

(

)

{ = ∈

} )

} ) )

(

) ( ) L f x \ L f x

(

( ( L f x

)

chặt của f tại x .

Định lý 1.1

*x X∈ và định nghĩa

, khi đó:

Cho

{ } 1,..., k

) ( * f x , q q

*x là một nghiệm tối ưu Pareto chặt nếu và chỉ nếu

( L y ≤

) { } = x



= q 1

= ∈ y

*x là một nghiệm tối ưu Pareto nếu và chỉ nếu

ii.

( L y ≤

)

( L y =

)



= q 1

*x là một nghiệm tối Pareto yếu nếu và chỉ nếu

iii.

( L y<

)



= q 1

= ∅

Chứng minh:

i. *x là một nghiệm tối ưu Pareto chặt

≤

sao cho:

( f x

)

( f x

∈ ≠ x X, x x ⇔ không tồn tại

≤

∀ ∈

sao cho:

)

{ } 1,..., k

( f x q

) * f x , q q

(

∈ ≠ x X, x x ⇔ không tồn tại

sao cho:

( L y ≤

)

( L y ≤

) { } = x



= q 1

ii.

*x là một nghiệm tối ưu Pareto

≤

≠

∈ ⇔ ∈ ≠ x x X, x x ⇔ không tồn tại

và

( f x

)

( f x

)

( f x

≤

∀ ∈

⇔ không tồn tại x X∈ sao cho:

và :

{ } 1,..., k

)

( f x q

) * f x , q q

(

∃ ∈ j

{ ( } 1,..., k : f x

)

( f x j

⇔ không tồn tại x X∈ sao cho:

và

( L y≤

)

( x L y<∈

= q 1

x ⇔ không tồn tại x X∈ sao cho: ∈

( L y ≤

)

( L y =

)



= q 1

*x là một nghiệm tối Pareto yếu

ii.

⇔ =

( f x

)

( f x

∀ ∈

⇔ không tồn tại x X∈ sao cho:

)

{ } 1,..., k

( f x q

) * f x , q q

(

⇔ không tồn tại x X∈ sao cho:

( L y<

)

= q 1

⇔

= ∅

( L y<

)



= q 1

x ⇔ không tồn tại x X∈ sao cho: ∈

Định nghĩa 1.21[5](Geoffrion (1968))

*x X∈ được gọi là một nghiệm tối ưu Pareto chính thường theo

Geoffrion nếu

*x là nghiệm tối ưu Pareto và nếu tồn tại một số M 0> sao cho

mỗi i và x X

và tồn tại chỉ số j sao cho:

)

( f x j

( f x i

( f x j

)

( f x i

< < ∀ ∈ thõa:

Hơn nữa:

) −

( f x * i ( ) f x j

( f x i ( * f x j

) )

− ≤ M

Khi đó, giá trị mục tiêu đạt được tương ứng tại

*x là

gọi là

( f x

)

điểm hữu hiệu chính thường.

= y

)P nếu

• *x không là nghiệm tối ưu Pareto chính thường của bài toán (

mỗi M 0> có một x X∈ và một chỉ số i sao cho:

và

)

( f x i

sao cho

)

( f x j

)

) −

)

( f x i ( f x j

( f x i ( f x i

) )

Ta xét bài toán lồi sau đây:

(

)

)1P

( f x i

λ∑

min ∈ x X

= i 1

− > < M, ∀ j

là các

Bài toán (

)1P gọi là bài toán tổng trọng số, trong đó

i ,i 1,..., k

trọng số không âm đối với các hàm mục tiêu và

λ =∑

= i 1

λ =

Định lý 1.2 (Geoffrion (1968))

Cho

với

. nếu

*x X∈ là nghiệm tối ưu của bài toán

= i 1

MOLP .

*x là nghiệm tối ưu Pareto chính thường của bài toán (

)

(

)1P thì

= 0,i 1,..., k 1 λ > i λ =∑

Chứng minh:

Cho

*x X∈ là nghiệm tối ưu của bài toán (

)1P . Ta muốn chứng minh:

f x '

, với

*x X∈ là nghiệm tối ưu Pareto, ta giả sử tồn tại x ' X∈ sao cho (

)

( f x

≤

∀ =

i 1,..., k ;

∃ ∈ j

và

(

)

} { 1,..., k : f x '

( f x ' i

( f x j

)

) ( * f x , i

(mâu thuẫn)

dẫn đến:

)

( f x ' i

( f x * i

∑

= i 1

≥

− M k 1 max

Cho

. Giả sử

*x không là nghiệm tối ưu Pareto

(

)

(

)

i, j

λ λ

MOLP , tức là tồn tại một i và x X∈ sao cho

chính thường của bài toán (

)

và

)

( f x i

= 0,i 1,..., k λ > i

. Do đó

)

(

)

(

)

( f x * j

( f x j

( f x M f x i

(

) f x * , j

( f x i

)

−

∀ ≠ j

)

(

)

( f x i

( f x j

(

) f x * , j

( f x i

)

− k 1 λ

− > − j ∀ ≠ với i

Nhân hai vế của bất đẳng thức trên với

rồi sau đó lấy tổng hai vế

λ i − k 1

như sau:

)

( f x i

( f x j

( f x * j

)

(

( f x i

)

∑

(

)

≠

− > λ −

)

( f x i

( f x j

( f x * j

)

( f x i

∑

≠

⇒ λ − λ − λ > λ i − k 1 (

)

( f x i

( f x j

) ( f x j

)

( f x i

∑

≠

> λ + λ ⇒ λ + λ

)

( f x i

)

∑

k ∑ ⇒ λ = i 1

= i 1

*x là nghiệm tối ưu

Ta gặp mâu thuẫn, điều đó nói rằng giả sử là sai, khi đó

Pareto chính thường của bài toán (

)

MOLP . 

> λ

Định lý 1.3

Cho

 là các hàm lồi,

if : →

X ⊂  là một tập lồi và các hàm

vô nghiệm trên X thì tồn tại

. Khi đó bất đẳng thức if

= = i 1,..., k 0< với i 1,..., k

≥

và với mọi x X∈ thỏa mãn:

)

( f x i

λ =∑

∑

= i 1

= 0,i 1,..., k λ ≥ i

Định lý 1.4 (Geoffrion (1968))

Cho

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 (

)1P .

X ⊂  là một tập lồi và các hàm if : X →  là các hàm lồi, i 1,..., k

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

( f x i

∈

hệ:

vô nghiệm. Áp dụng định

{ } 1,..., k

( f x i (

) )

)

) ( + f x Mf x i

( ) ( + f x Mf x i

)

< , ∀ ≠ j i <    

0, j 1,..., k

lý 1.3 đối với hệ trên thì tồn tại

và với mọi x X∈ thỏa

i λ ≥ j

i j

= j 1

mãn:

1 λ =∑

)

(

( f x i

i i

i j

( + f x Mf x i

i i

i j

(

)

( ) ( + f x Mf x i

( f x i

)

∑

(

)

≠

λ + λ ≥ λ + λ

)

(

( f x i

i i

) f x M i

i j

( f x j

i j

i i

i j

)

( f x j

) ( * f x M i

( f x i

)

∑

≠

⇒ λ + λ + λ ≥ λ + λ + λ

)

(

) f x M i

i j

( f x j

i j

) ( * f x M i

( f x j

)

∑

≠

k ∑ ⇒ λ = j 1

= j 1

+ λ ≥ λ + λ

)

(

) f x M i

( f x j

i j

( f x j

)

) ( * f x M i

∑

≠

i≠

Lấy tổng hai vế bất đẳng thức với biến chạy là i ta được:

≥

(

)

) f x M i

( f x j

i j

) ( * f x M i

( f x j

)

∑

∑∑

∑

∑∑

≠

= i 1

= i 1 j

= i 1

= i 1 j

⇒

≥

)

i j

≠

= j 1

 ∑ ∑ + 1  

 ( f x  j 

 ∑ ∑ + 1  

 ) ( * f x .  j 

Ta có thể chuẩn hóa giá trị

i j

∑ để lấy tổng đến 1 chứa những số dương

≠

  

  

⇒ + λ ≥ + λ

Vậy

*x là nghiệm tối ưu của bài toán (

)1P . 

λ = i ,i 1,.., k

Định nghĩa 1.22[5]

Cho

1. Nón tiếp xúc của Y tại y Y∈ là:

⊂

→

= ∈ d

y, t

)

{ } ∃ t



( T y Y

{ , y

}

{ Y saocho y

}

(

) − → y

Y ⊂  và y Y∈

{

}

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

(

)

YT y là một nón đóng.

−

2. Nếu Y là tập lồi thì

, chúng là nón lồi đóng.

)

( cl cone Y y

)

(

)

( YT y

Chứng minh:

∈

vì nếu

)

(

)

1. Ta có

( 0 T y Y

YT y là một nón: cho

α >

α ∈

thì

( ∈ 0, d T y

)

( d T y Y

∈

⊂

d→ . Từ

∀ sẽ có những

( ) T y ,

) T y , y Y

(

Lấy dãy { } d

∈ và { }ld

⊂

thõa định nghĩa 1.12. Từ sự hội tụ ta cố định l, có



l,kt

dãy {

}

}l,k

{ , y

những

lk thỏa:

l,k

y, k = ∀ và

, chúng ta cố định

lk khi đó nếu l → ∞ thì dãy

l,k

(

)

l,k

∈

− − ≤ ∀ ≥ , k k t y y d 1 l

)

. 

( d T y Y

l,kt

(

{

} )

2. Cho Y là tập lồi , y Y∈ . Qua định nghĩa của bao đóng và bao nón, rõ

là nón lồi đóng.

ràng

( cl cone Y y−

)

(

)

⊂

−

∈

thật vậy

lấy

, có dãy

)

( cl cone Y y

)

• Ta có:

(

)

( YT y

( d T y Y

⊂



{ } kt

{ }k , y

→

y, t

− → . Từ d

α > 0

(

) − Y y ,

sao cho { }

(

)

(

) − ∈ α

y y − → tức là d

dẫn đến

(

)

(

)

(

)

( cone Y y

) − ⊂

)

• Do

( T y Y

YT y là tập đóng, ta chứng minh

∈

−

= α

α ≥

− y ' y

0, y ' Y

tức là

với

∈ .

Cho

(

)

( d cone Y y

−

∈ − d cl cone Y y

k y :

∈ y ' Y

Ta định nghĩa

và kt

1 k

  

  

0 = α ≥ . k

Khi đó :

(

)

(

)

(

)

(

)

∈

→

y, t

− → dẫn đến

)

. 

( d T y Y

Như vậy { }

(

)

− = α + − = α + − − = α t y y k y y ' y k 1 y y ' ky − y ' y − k 1 k 1 k            

Đị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

{ } 0

k +

( ∩ −

)

( f x

)



(

)

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

{ } 0



k +

)

( ∩ −

)

( f x

( cl cone Y

)

= 

)

(

Đị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à

 là lồi thì cả hai định nghĩa Borwein và

kf : →

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:

≠

, d

Giả sử x không là nghiệm hữu hiệu Pareto nên tồn tại

+∈ 

sao cho:

( f x

)

= d y − với y Y∈ .

Cho

k +

= = − ∈ = k, k 1, 2,... d 1 d  và kt 1 k      

Khi đó:

khi k → ∞ .

( f x

)

( f x

)

( f x

)

= − = + y d − + d 1 d − → d 1 k 1 k      

Và

( f x

)

(

)

≠

, dẫn đến x không là nghiệm hữu hiệu

Như vậy

{ } 0



k +

( ∩ −

)

( f x

)



(

)

k +

chính thường theo định nghĩa Borwein (mâu thuẫn).

− = − = − → − → ∞ t + y d k − + d 1 d d, k d 1 k            

Định lý 1.6[5] (Benson (1979))

Một nghiệm x X∈ là nghiệm Pareto chính thường theo định nghĩa của

Geoffrion khi và chỉ khi x là nghiệm Pareto chính thường theo định nghĩa

của Benson.

Chứng minh:

(

)⇒

MOLP , giả sử x không là

Cho x là nghiệm Pareto của bài toán (

)

∈

−

≠

d cl cone f X

, d

Khi đó, tồn tại

. Không mất

)

(

{ } 0



k +

( ∩ −

)

( f x

)

(

)

nghiệm Pareto chính thường theo định nghĩa của Benson. (

, do đó mọi dãy

tính

tổng quát

ta giả sử

⊂

X, r

+

k +

⊂  và { }st

{ } x

{ }

s + − r

sao cho

→ . Chọn dãy con nếu cần thiết, ta giả sử

( f x

)

( f x

)

(

là dãy trong )

là giống nhau đối với tất cả s và khác rỗng

( { } 1,..., k : f x

)

( f x i

} )

{ ℑ = ∈ i

(vì x là nghiệm Pareto).

< − ≤ ∀ = 1, d 0 i 2,..., k d 1

Cho M 0> , từ tính hội tụ tồn tại 0s sao cho với mọi

−

< −

(

) 6.1

( f x 1

)

( f x 1

)

1 2.t

−

≤

2,..., k

6.2

Và

(

)

( f x i

)

( f x i

)

1 2.Mt

Bởi vì st → ∞ , trường hợp riêng với i ∈ ℑ thì ta được:

−

≤

∀ ≥ s

6.3

(

)

( 0 f x i

)

( f x i

)

1 2.Mt

)

s s≥ ta có:

Do đó từ (

)6.1 và (

)6.3 :

(

)

( f x 1 ( f x i

) )

= > M 6.4 − − ) 1 2.t 1 2.Mt

Vì M được chọn tuỳ ý nên x không là nghiệm Pareto chính thường theo

định nghĩa của Geoffrion. )⇐ (

MOLP , giả sử x không là

Cho x là nghiệm Pareto của bài toán (

)

nghiệm Pareto chính thường theo định nghĩa của Geoffrion, lấy {

}sM là dãy

sx X∈ sao cho

những số thực dương không bị chặn. Với mỗi

sM tồn tại một

)

∀ ∈ j

và

với

sao cho

{

} 2,..., k

(

)

( f x j

( f x 1

)

( f x j

)

( f x 1

)

( f x 1 ( f x j

( f x 1 ( f x i

) )

Chọn một dãy con nếu cần thiết, chúng ta có thể giả sử rằng:

< < > M 6.5 − − )

là như nhau với mọi s và khác rỗng, chúng

( } { 1,..., k : f x

)

( f x i

} )

{ ℑ = ∈ i

ta xây dựng thích hợp những dãy { }st

, { }sr

→ ∈

−

s + − r

d cl cone f X

(

)



 như sau:

k +

( f x

)

( ∩ −

)

( f x

)

( f x

)

(

)

(

)

sao cho giới hạn )

(

−

Định nghĩa

t : s

dẫn đến st

( f x 1

)

( f x 1

)

(

) 1

Định nghĩa s r

+∈  thông qua:

> ∀ 0, s

(6.6)

s r : i

= ∈ ℑ 0

)

( f x i

Với những dãy trên chúng ta có:

− ≠ ∉ ℑ i 1,i i 1,i ) ( f x i   =  

= i 1

s + − r

(6.7)

( f x i

)

( f x i

)

(

)

= t

− 1 s

s + − r

Vì {

∈ ℑ i 0, M 0 ( ≠ ∉ ℑ i 1,i ) = − 1     ∈  

}sM → ∞ nên dãy này hội tụ về

( f x

)

( f x

)

(

)

lim t →∞ s

với i 1,..., k =

d ∈  ở đó

Do đó, từ (6.7) thì

= − = ≠ ∉ ℑ = 1, d 0,i 1,i , d 0,i ∈ ℑ . d 1

∈

−

1, 0,..., 0

Bởi vì

)

(

( = −



 nên x không là

k +

)

( ∩ −

( f x

)

( cl cone f X

)

(

nghiệm Pareto chính thường theo định nghĩa của Benson.

, ta giả sử rằng các hàm mục tiêu

(

)

 Khi

( ) | g x ,..., g

)

{ = ∈ X x

} 0

cũng như các hàm ràng buộc

là khả vi liên tục. Ta xét bài

= jg , j 1,..., m

≤ x 

= if ,i 1,..., k

toán tối ưu đa mục tiêu sau:

(

)

( min f x với

)

( ) | g x ,..., g

)

{ ∈ = ∈ x X x

} 0

≤ x 

Định nghĩa 1.24[5] (Kuhn và Tucker (1951))

MOLP nếu x là

Một điểm x gọi là nghiệm Pareto chính thường của (

)

MOLP và nếu không có

một nghiệm Pareto của (

)

∇

≤ ∀ =

i 1,..., k

) ( if x , d

∇

∈

< xảy ra tại một vài

{ } 1,..., k

) ( pf x , d

d ∈  thỏa mãn:

) ( g x , d

∧ ( J x

)

( = j 1,..., m : g x

)

{

} 0

∇ ≤ = = 0, ∀ ∈ j

Định nghĩa 1.25[5]

Bài toán tối ưu đa mục tiêu khả vi thỏa điều kiện ràng buộc KT tại

∇

≤

∀ ∈ j

x X∈ nếu bất kỳ

có

d ∈  với

) ( g x , d

∧ ( J x

)

( = j 1,..., m : g x

)

{

} 0

0> , một hàm

0α >

một số thực t

θ  và   → : 0, t 

sao cho

= α . d

( ) ' 0

( ) 0

( ) t

(

)

θ = θ x, g 0, 0, t  ≥ ∀ ∈  t   và

Định lý 1.7[5] (Geoffrion (1968))

Cho bài toán tối ưu đa mục tiêu khả vi thỏa điều kiện ràng buộc KT tại

x X∈ và x là nghiệm Pareto chính thường theo định nghĩa Geoffrion. Khi đó

x là nghiệm Pareto chính thường theo định nghĩa Kuhn và Tucker.

Chứng minh:

Giả sử x là một nghiệm Pareto nhưng không là nghiệm hữu hiệu chính

thường theo định nghĩa Kuhn và Tucker, khi đó tồn tại

d ∈  thỏa mãn:

≤ ∀ =

∇

i 1,..., k

) ( if x , d

{ } 1,..., k

) ( pf x , d

∇

≤

∀ ∈ j

) ( g x , d

∧ ( J x

)

( = j 1,..., m : g x

)

{

} 0

∇ ∈ 0 p < xảy ra tại một vài

Sử dụng hàm θ từ điều kiện ràng buộc KT, ta chọn được dãy kt

ℑ =

cần thiết dãy đó thỏa mãn

, tập ℑ là như nhau với mọi

(

)

(

)

( f x i

{ i : f

} )

)ktθ (

k. Với i ∈ ℑ, bằng khai triển Taylor của hàm if tại

−

∇

α + ο

> . 0

(

)

(

)

(

)

( f x i

)

) ( f x , d i

0→ , nếu

) ( if x , d

∇

Nhưng từ

< chỉ ra:

) ( 1f x , d

)

− ∇

α +

) ( f x , d 1

−

)

(

→ ∞ ∀ ∈ ℑ ,

( t t

)

( −

) (

f 1 )

( f x 1 (

)

t ( f x i

) )

∇

α +

( ) f x , d i

( t

Do đó x không là nghiệm Pareto chính thường theo định nghĩa của

Geoffrion ( mâu thuẫn giả thiết). 

∇ ∇ 0 i ≤ dẫn đến α = ∀ ∈ ℑ 0, .

Định lý 1.8[5]

Cho

f , g : →

 là các hàm lồi, khả vi liên tục và x là nghiệm Pareto

chính thường theo định nghĩa Kuhn và Tucker. Khi đó x là nghiệm Pareto

chính thường theo định nghĩa Geoffrion.

Hình 1.3.2.1 Sơ đồ mối quan hệ giữa các định nghĩa nghiệm Pareto chính

thường trong các trường hợp:

Borwein

K là nón lồi đóng, x X∈

Định lý 1.5

Benson

Định lý 1.6

+=  , x X∈

Geoffrion

Định lý 1.7

Định lý 1.8

≤

( | g x

)

+=  ,



} 0

{ ∈ = ∈ x X x

Kuhn - Tucker

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

2.1 Giới thiệu bài toán:

là k hàm phân tuyến tính, cụ thể:

Với

)

 (

if : →

( f x i

+ A x s + B x t

trong đó

= i 1, 2,..., k

n vào  ,

iA , B là các ánh xạ tuyến tính từ

f(x)

(

)

f (x),..., f (x) 1

m n

s , t ∈  . Đặt

≤

| Ax

Cho X là tập lồi đa diện trong

, A

n :



} b

{ = ∈ X x

B x t

+ > ∀ ∈ 0,

. Khi đó ta xét bài toán tối ưu

Chúng ta giả sử rằng:

} { 1, 2,..., k

nhiều mục tiêu với hàm thành phần phân tuyến tính có dạng:

( 2P )

∈ , b×∈   .

Các hàm thành phần không lồi, dạng đặc biệt của chúng cùng với việc sử

dụng vô hướng ta có tính chất đặc trưng cho bài toán tối ưu thể hiện qua bổ đề

1 sau đây (trong phần 2.2).

Min f(x) ∈ x X

2.2 Các điều kiện tối ưu:

Bổ đề 1: (Xem Malivert (1995))

∈

với mọi

là k hàm phân tuyến tính, giả sử

Cho

{ } 1, 2,..., k

)

( f x i

+ A x s + B x t

−

∇

∀ ∈

−

, ở đó

Lấy bất kỳ x X∈ thì :

)

( f x i

)

( ) f x , x x , x X i

) (

+ B x t + B x t

là gradient của if tại x .

( if x∇

)

B x t 0, x X + ≠ ∀ ∈ .

Chứng minh:

Theo định nghĩa của gradient ta có:

∇ −

)

( f x i

)

) (

+ − = −     1 t

) ) )

( + A x t x x ( + B x t x x

) )

) ( ( f x , x x i ( lim f x t x x → t ( (

)

−

lim → t 0

1 t

   

   

−

)

( tA x i

( t A x i

)

( ( ( ) + − 1 t A x tA x i ) ( ( ( ) − 1 t B x tB x i ( ( ) + − 1 t A x

 

 

   

 

lim → t 0

1 t

  )

( tB x i

−

(

)

( ) tA x B x

)

) ) ( s A x i ) ( ) B x i ) ) (   s B x   i ( ) ( ) ( + − 1 t B x ( ) + s B x i i

)

) ( ( A x B x

( t A x i i

( )*

lim → t 0

1 t

( tt A x i (

) ( ( ( ) tB x 1 t B x i ) ( ) ) ( t B x i i ( ) ( ) ) ( ( ) ) − − 1 t B x s t 1 t A x i i ( ) ) ( ) ( ( ( ) ) − 1 t B x t B x tB x i i i

( ts B x i )

−

)( B x x A x s

(

)

Mặt khác: ) ( + A x x . B x t +

−

( − A xB x t A x A xB x t A x B xA x s B x A xB x s B x

i +

−

i − A xB x t A x t A x B xA x s B x s B x

− + = − lim → t 0 1 t − +       s A x s +  + B x t t  

(

)( B x x A x s

)

Suy ra ( ) *

) + B x t

)( + A x x B x t (

( )

− − − + =

)

∇ −

) ( ( f x , x x i )( + A x x B x t

)

(

− − + + B x t + B x t ( = +

)

(

)( + A x s B x t i

)( B x x A x s ) )( + A x s B x t i )

+ + = +

)

( f x i

) − )( + B x t B x t ( ) − )( ( + B x t B x t )

( f x i

= −

Nhận xét:

Cho x, y bất kỳ thuộc X với x

y≠ , ta lấy hai điểm thuộc vể đoạn thẳng [

]x, y :

. Từ bổ đề 1,

)

( ) x t y x ,

( x t ' y x

)

[

] 0,1 , t '

[

t '

(

)

−

t '

−

)

(

)

) ( f x i

( f z i

t '

∇

−

∇

−

)

(

)

(

) ( f x , z i

t '

( ( ) f z f z i i ( ( ) − f z i t + B x t i i + t B z i

t '

= ∇

−

(

) t ' .

)

(

) ( f x , y x i

)

(

B z i

) ( ) f x i + B x t i i + t B z i 2 ) ( + B x t i )( + t B z i

t '

Từ đó, ta có ngay những điều sau:

= + − = + − ∈ ∈ z z t 0, t

t '

với mỗi

)

(

i) Nếu

[ 0, t∈

( f z i

t '

( f z i

) if x , y x

∇ − 0 > thì

t '

với mỗi

)

(

[ 0, t∈

ii) Nếu

( f z i

t '

( f z i

) if x , y x

∇ − 0 < thì

∇

−

= thì

với mỗi

)

(

[ 0, t∈

iii) Nếu

( f z i

t '

( f z i

) if x , y x

Như vậy hàm if đơn điệu trên mỗi đoạn thẳng hoặc tia được chứa trong X.

= t '

Định lý 2.1[3]

khi và chỉ khi tồn tại những số thực

Cho x X∈ , khi đó

( x E P∈

thoả y X

∀ ∈ :

= 0,i 1,..., k λ > i

(

) A x s B y x

(

)

(

) + B x t A

∑

= i 1

λ − + − ≥ 0    

Chứng minh:

Ta có:

∈

⇔

−

∀ =

i 1,..., k

{ } \ 0 ,

(

) 9.1

)



k −

( x E P 2

(

) + B x t A

(

) A x s B x x

) − ∉

(

 

 

−

(

) + B x t A 1

(

) + A x s B 1

Đặt



xQ =

−

(

) + B x t A

(

) + A x s B

     

     

( Q X x

)

(

{

} ) Q y x : y X

− = ∈ −

Chứng minh(

)9.1 :

≤

i 1,..., k

)

( f y i

Thật vậy giả sử

( x E P

(

)

) ( ∀ = f x , i ) ( x

   

∉ y X ⇔ ∃ ∈ và 0i thỏa:

Từ bổ đề 1, hệ bất phương trình trên

≤ ∀ = − i 1,..., k 0,

) ( f x , y x i ) ( x , y x

∇ − < f 0  ∇  ⇔   

)( B y x A x s

)

(

Từ

)

) ( ( f x , y x i

) + B x t

)( + A y x B x t (

( )

− − + − ∇ − =

(

)

Ta có:

(

)

( (

) + B x t A ) + B x t A

) A x s B y x ( (

− − + i 1,..., k 9.2 − < 0 − y x   ) + A x s B i ≤ ∀ = 0, )         

Vậy

{ } \ 0 ,

)

k −

( x E P 2

(

) + B x t A

(

) A x s B x x

) − ∉

(

∈ ⇔ − + ∀ = i 1,..., k   

, khi đó D là tập đa diện lồi. Theo hệ quả 19.7.1 từ

Đặt

( D : Q X x x

là một nón đa diện lồi, đặc biệt K là nón

Rockaller (1970), với K : coneD

lồi đóng.

= −   )

(

)

k −

( Q y x

( xQ y x

)

− ⇔ 9.2 ≠ . 0 − ∈  và

{ } 0

(

) 9.1

{ } 0

k −

( Q y x

) − ∩

⇔ = ⇔ ∩ = K  

≥ ∀ ∈

: z, v

Đặt



, khi đó (

++ )K

{ + = ∈ z

} 0, v K

= K

. Thật vậy: giả sử

theo định lý tách

Khi đó:

k +

ta có:

≤ ≤ ξ

ξ , u

∀ ∈ , z , u int

, z K + ∀ ∈

sao cho

{ } k \ 0

∃ξ ∈ 



k +

∩ ∩ K int K int ≠ ∅ = ∅

Suy ra

(mâu thuẫn).

{ } 0

ξ ∈ − và

k +

k −

(

++ )

ξ ∈ = ⇒ ξ ∈ ∩ K K K =

 λ

 λ ∈ ∩ K

int

λ = :

Lấy

ta được

λ ∈ ∩ Λ ,

 , đặt

k +

  λ + + λ ...

  

  

, v

0, v K

. Từ

≥ ∀ ∈ ta có:

với

k +

∑ :

= i 1

= λ

−

λ − Q , y x

≥ . 0

( , Q y x

)

khi và chỉ khi tồn tại những số thực

Điều đó có nghĩa là:

( x E P∈

ri 1, λ = λ > ∀ 0 i i     Λ = λ ∈  

−

≥

∀ ∈ :

thoả y X

) − B x t A

(

) A x s B y x

(

)

(

∑

 

 

= i 1

Nếu

x X∈ ,

là hàng

thứ

j của ma

trận A,

tập hợp

= 0,i 1,..., k λ > i

{ } 1,..., m : A x

( I x

)

{ = ∈ j

}

∈

≤

0, j



. 

: A d j

( I x

Nhắc lại rằng nón tiếp xúc của X tại x được xác định bởi: { = ∈ xT X d

= b

} )

Hệ quả 2.1[3]

khi và chỉ khi tồn tại những số thực

Cho x X∈ , thì

( x E P∈

và

sao

cho

( I x

)

∈ = 0,i 1,..., k 0, j λ > i µ ≥ j

(

) + B x t A

(

) + A x s B i

∑

= i 1

∑ ( ∈ j I x

)

λ − + µ = A 0 j    

Định lý 2.2[3]

Cho x X∈ , khi đó

khi và chỉ khi tồn tại những số thực

)

( w x E P 2

∈

không đồng thời bằng 0 thoả y X

∀ ∈ :

−

≥

) A x s B y x

(

)

(

) + B x t A

(

∑

 

 

= i 1

= 0,i 1,..., k λ > i

Chứng minh:

Với cách đặt

xQ và K như trong định lý 2.1, ta dễ dàng chứng minh được:

)

k +

k −

( w x E P 2

)

(

)

) ( − ∩ −

( Q X x

= ∅

Thật vậy, nếu

, khi đó tồn tại

{ } \ 0

{ } k \ 0

∃ξ ∈ 

+∩ 

≤ ≤ ξ

∀ ∈

ξ , u

, z , u

, z K + ∀ ∈

sao cho



k +

∈ ⇔ = ∅ ⇔ ∩ = ∅ int K int  

ξ ∈ 

k −

(

++ )K



k ⇒ ξ ∈ ∩ ⇒ ξ ∈ ∩  −

k −

) { } \ 0

(

 λ

⇒ ξ ∈ = và K

 λ ∈ ∩ K

λ = :

Lấy

, đặt

ta được

λ ∈ ∩ Λ :

{ } \ 0

k +

  λ + + λ ...

  

  

⇒ λ

≥ ∀ ∈

, v

0, v K

⇒

= λ

−

≥

λ − Q , y x



( , Q y x

)

≠ 0 

Hệ quả 2.2[3]

Cho x X∈ , thì

khi và chỉ khi tồn tại những số thực

)

( w x E P 2

∈

không đồng thời bằng 0 và

sao

( I x

)

−

cho

= A 0 j

) + A x s B i

(

) + B x t A

(

∑

 

 

= i 1

)

∑ ( ∈ j I x

= ∈ 0,i 1,..., k 0, j λ ≥ i µ ≥ j

2.3 Hàm phạt:

Giả sử X là tập compact.

Chúng ta định nghĩa Pe và Pw, cho x X∈ :

(

) = P x max e

= i 1

1 k     ∑ τ  

) A x s B d i

Sao cho

( 0

) (     ∈ − τ≥ d X x;  i

(

) = wP x max

− + ≤ −τ = + B x t A ;i 1,..., k  

−

≤ −τ =

+ B x t A

;i 1,..., k

)

(

) A x s B d i

 

Sao cho

(    i  ∈ −  d X x

Khi X compact, tồn tại cực đại và theo sau nó từ 0 X x

∈ − thì Pe và Pw

nhận những giá trị trong

+ .

Hơn nữa, ta dễ dàng thấy rằng

)

(

)

( P x w

tính chất:

} 0 ) =

) ( x X : P x

)

} 0

{ ( = ∈ x X : P x { = ∈

≤ ∀ ∈ và sau đó ta có các P x , x X e

Mệnh đề 2.1[3] ) ( ( ) i E P 2 ( ) ( w ii E P 2

Chứng minh:

)

( x X : P x

)

{ = ∈

} 0

( ( ) i E P 2

Lấy

( x E P∈

≥ ∀ ∈ −

⇒

−

0, d X x,i 1,..., k

+ B x t A

(

) A x s B d i

 

 

i ⇒ −τ ≥ ∀ =

) i 1,..., k

Mà

Vậy

0= .

)

( eP x

∈

i 1,..., k

Lấy

( x X : P x

)

= ⇒ τ = ∀ = i

⇒

−

≤ ∀ =

+ B x t A

i 1,..., k

(

)

(

) A x s B X x

(

)

 

 

Giả sử tồn tại y X∈ sao cho:

⇒ τ = ∀ = i 1,..., k i 1,..., k 0, τ ≥ ∀ = 0, i

(

)

(

)

− + − ≤ ∀ = i 1,..., k 0,

(

)

( (

) A x s B y x (

⇒ τ > ⇒

> (mâu thuẫn)

)

( P x e

⇒ ∈

( x E P

− < + B x t A − y x 0 + B x t A )   ) + A x s B i          

)

(

)

( x X : P x

{ = ∈

} 0

( ) w ii E P 2

∈

⇒

−

≥ ∀ ∈ −

+ B x t A

0, d X x,i 1,..., k

Lấy

(

)

(

( w x E P 2

) A x s B d i

 

 

⇒ −τ ≥ ⇒ τ ≤ . Vậy max

0τ =

∈

−

≤ ∀ ∈ −

= ⇒ 0

+ B x t A

0, d X x,i 1,..., k

Lấy

)

(

)

(

( x X : P x

) A x s B d i

 

 

−

< ∀ =

+ B x t A

i 1,..., k

)

(

) A x s B y x

(

)

Giả sử tồn tại y X∈ sao cho: (  

 

⇒ −τ < ∀ =

⇒ τ > ⇒

i 1,..., k

0 max

τ > (mâu thuẫn)

) ( w x E P .

⇒ ∈

Chú thích 1:

(

)

) eP x và

wP x là lời giải của bài toán tuyến tính và theo

mệnh đề 7 cho ta cách kiểm tra một điểm x X∈ là hữu hiệu, hữu hiệu yếu.

Chú thích 2: Trong N.Popovici, chúng ta có thể nói x là ε − hữu hiệu

nếu

(

)

(

)

eP x ≤ε . Trong định nghĩa trên nếu điều kiện

eP x ≤ε được thay bởi

(

)

wP x ≤ ε ta gọi x là ε − hữu hiệu yếu.

Mệnh đề 2.2[3]

0x X∈ .

eP và wP là nửa liên tục trên tại tất cả những điểm

Chứng minh:

Ta chứng minh cho eP , chứng minh tương tự cho wP .

Giả sử rằng

0x X∈ , khi đó tồn tại

eP không liên tục trên tại

≥

0 ε > và một

sao cho mọi n,

+ε . Điều này

dãy

)

( P x e

lim x →∞ n

X∈ sao cho

và

sao cho:

nghĩa là với mọi n, tồn tại

{ } 1,..., k

∈ ∈ − d X x

(

)

+ + − 0, i 1,..., k B x i  

)

( P x e

( (

) t A i ) t A i

Tập chỉ số {

}

1, 2,..., k là xác định, chúng ta có thể giả sử rằng ni không

phụ thuộc vào n, với

{ } 1,..., k

= ∈ i 0

+ − ≤ − + +ε ≤ ∀ = ( B x i A x i  s B d  i i ) s B d i i A x i (        

Khi X là tập compact và

chỉ ra rằng

nd hội tụ về

lim x →∞ n

∈ − d X x

(

)

cùng với

+ + − 0, i 1,..., k B x i  

)

( P x e

( (

) t A i ) t A i

+ − ≤ − + +ε ≤ ∀ = ( B x i A x i A x i (  s B d  i i ) s B d i i        

(

)

ta có ngay

+ + − 0, i 1,..., k B x i

)

( P x e

( (

) t A i ) t A i

điều này trái với định nghĩa của

(

)

P x . Vậy eP liên tục trên tại

0x X∈ . 

+ − ≤ − + +ε ≤ ∀ = ( B x i A x i  s B d  i i ) s B d i i A x i (          

Mệnh đề 2.3[3]

(

)

) ( E P \ E P 2 2

eP là nửa liên tục dưới tại tất cả những điểm

∈

Nó có thể xảy ra vấn đề

(

)

) ( E P \ E P 2 2

eP không nửa liên tục dưới tại

∉ x

Ví dụ:

≤

− + x 1

−

≤

min

, x

sao cho

− +

− + x 1 + − x

4 x 1 , 3 x

4 1

  

    

≥

1 2 0, x

     

Kiểm

tra được

và với mọi

(

)

(

)

n ∈ 

) ( E P \ E P 2 2

−

∈

, 0.5

Ta có

, trong khi đó

0= và

0> .

)

( P x e

) ( E P . 2

lim x →∞ n

1 n

  

  

Mệnh đề 2.4[3]

0x X∈ .

wP là nửa liên tục dưới tại tất cả những điểm

= ∈ x 4, 0.5

Chứng minh:

∈

Nếu

ta có

)

+ , hiển nhiên

( P x w

( w E P 2

0= và wP nhận giá trị trong

∈

)

( w E P 2

wP là nửa liên tục dưới tại

∉

Bây giờ giả sử rằng

hoặc

0> và cho

0ε > .

)

( w E P 2

( P x w

0d sao cho

Từ định nghĩa của wP chỉ ra rằng tồn tại

x + ∈ d X

(

)

{ } 1,..., k

) t A i

( P x ,i w 0

và (  

+ − + ≤ − ∈ B x i A x i s B d i i  

Xét lân cận V của

0x chứa tất cả những x X∈ sao cho

(

)

{ } 1,..., k

(

) − ε ∈ ,i

) t A i

( P x w

∈

≥

Chúng ta có được với mọi

( x V, P x

)

( P x w

− ε và wP là nửa liên tục

dưới tại điểm

0x . 

Từ mệnh đề 2.2 và mệnh đề 2.4, wP là liên tục trên X.

+ − + ≤ − B x i A x i s B d i i    

2.4 Nghiệm bài toán tối ưu

Tập nghiệm hữu hiệu hoặc hữu hiệu yếu thường rộng và không lồi ngay

cả khi trong trường hợp tuyến tính. Ta cần tìm giữa các điểm tối ưu là nghiệm

của bài toán tối ưu. Cụ thể là việc cực tiểu hoá một hàm mới trên cả

)2E P (

E P . Chúng ta nghiên cứu việc cực tiểu hoá của một hàm khả vi trên

hoặc

(

)

(

( E P .

)2E P hoặc

Ta xét hai bài toán:

inf

(

)

( min f x

)

(

)

( f x 0

và

∈

)

( x E P∈ 2

( w x E P 2

Với

 là hàm khả vi.

0f : →

(

)2E P không cần thiết đóng, ta có ngay inf thay cho min trong (

)eQ và ta

biểu thị giá trị tối ưu bởi kí hiệu f .

Mặt khác nữa

E P là com pact, giá trị tối ưu của (

(

)

)wQ được viết

∈

)

( w E P 2

là (

) * f x , x 0

Từ mệnh đề 2.1 ta viết lại các bài toán như sau:

inf

(

)

(

)

( min f x

)

( f x 0

≤

và

)

( P x e

( P x w

∈ x X

Chú ý rằng

eP và wP nói chung cả hai không lồi hoặc khả vi, tương ứng

với hàm Lagrangian là:

+ λ

và

) λ =

)

) λ =

)

( L x, e

( f x 0

( P x e

( L x, w

( f x 0

( P x w

Cho

0λ ≥ , ta định nghĩa hàm đối ngẫu:

(

) λ =

(

) λ =

(

) λ

(

) λ và

min L x, w ∈ x X

inf L x, e ∈ x X

Chú ý với X là compact và

(

)

eD λ ∈  . Hơn nữa

eP dương chúng ta có

E P \ E P , ta không thể thay inf

(

)

(

eP không hoàn toàn nửa liên tục dưới trên

bởi min.

∀λ ≥ , tồn tại

với

) ( x λ thỏa

(

) λ =

(

Từ định nghĩa của wD , mệnh đề 2.4 cho phép ta viết min thay cho inf và ( L x w

) ) λ λ ∈  .

≤

D ,

ta nhận thấy

∀λ ≥ ,

Với x X

)

(

) Dλ ≤

(

) λ .

( P x w

( P x e

Ta có các kết quả sau:

∀ ∈ ,

Mệnh đề 2.5[3]

+ .

eD và

wD là những hàm tăng trên

Mệnh đề 2.6[3]

Với mọi

(

) λ ≤ và f

(

) λ ≤

( f x

với

λ ∈  , ta có

Xét dãy tăng (

)kλ → +∞ và một dãy con (

)kε

+ λ

≤

ε → ε > 0.

)

(

) λ +ε

)

Cho k ∈  ta lấy

( f x 0

( P x k e

+ λ

≤

(tương tự

λ + ε ).

)

(

)

( f x 0

( P x k w

là không đổi.

Khi X là compact tập điểm tụ của (

)kx

X∈ sao cho:

Mệnh đề 2.7[3]

. Ta có:

Kí hiệu x là một điểm tụ của (

)kx

0= (tương tự

( ) i

)

( lim P x e

( wP x

)

0= ),

(

)

( f x

( 0f x

)

( f x 0

)

≤ ii f≤ + ε (tương tự + ε ).

Chứng minh:

( )i Xét một dãy (

hội tụ về x . Từ mệnh đề 2.6 ta có với mọi k ∈  thì:

)kx

+ λ

≤

+ ε ).

)

( f x 0

( P x k e

( f x 0

( P x k w

( f x 0

+ λ f ≤ +ε (tương tự

kết hợp bất đẳng thức trên đòi hỏi

)

Vì f0 là liên tục nên

( lim f x 0

( f x 0

)

rằng dãy

(tương tự

)

) bị chặn trên. Khi (

( P x k e

( P x k w

)kλ → +∞ ta nhận

0= (tương tự

được

)

( lim P x e

( wP x

)

0= ).

(tương

tự

)

cùng

với

(

)ii Vì

)

( P x k e

( P x k w

λ λ ≥ 0 ≥ 0

)

( f x 0

( P x k e

+ λ f ≤ +ε

(tương tự

)

( f x 0

( P x k w

( f x 0

≤

+ λ ≤ + ε ) ta suy ra:

+ ε ) dẫn đến

)

( f x 0

( 0f x

)

f≤ + ε (tương tự f≤ + ε

(tương tự

( f x

( 0f x

)

≤ + ε ).

Chú thích 3

ν ε> 0,

> mệnh đề 2.7 chỉ rõ khi k đủ lớn,

Cho hai số thực

kx là ν− hữu

≤

+ ε ).

)

( f x 0

hiệu (tương tự ν− hữu hiệu yếu) được nhắc đến trong chú thích 2 và thỏa: ( f x

Để tìm

kx ta phải giải quyết bài toán dạng:

+ λ

và

)

(

) λ =

(

) λ =

)

( P x e

( P x w

( ( inf f x 0 ∈ x X

( ( min f x ∈ x X

Ta muốn đưa ra dạng khác của bài toán này và sau đó dùng phương pháp

số tối ưu của tối ưu khả vi.

Ta gọi lại:

(

) = P x max e

f≤ + ε (tương tự

= i 1

1 k     ∑ τ  

−

0;i 1,..., k

+ B x t A

(

) A x s B d i

+ τ ≤ i

 

i ≤ −

) b Ax;

Sao cho

(     Ad  τ≥

(

) = wP x max

−

+ τ ≤

0;i 1,..., k

+ B x t A

(

) A x s B d i

 

Sao cho

i ≤ −

) b Ax;

(      Ad

Viết lại đối ngẫu cho mỗi bài toán tuyến tính ta có được:

−

(

)

(

)

eP x min b Ax

−

+ B x t A

γ = A 0

(

)

(

)

+ A x s B i

∑

 

 

= i 1

i 1,..., k;

Sao cho

δ ≤ i

γ ≥

δ ≥

1 k 0

        

Và

−

(

)

(

)

wP x min b Ax

−

+ B x t A

γ = A 0

(

)

(

)

+ A x s B i

∑

 

 

= i 1

Sao cho

δ = i

δ ≥

    ∑   = i 1 γ ≥  

Dùng những công thức tương ứng ta có như sau:

+ λ

− b Ax

(

) λ =

)

(

)

) γ

( ( inf f x 0

(

)

(

)

∑

= i 1

Sao cho

≤ b Ax k δ − + + B x t A γ = A 0 + A x s B i    

= i 1,..., k;

Và

+ λ

− b Ax

(

) λ =

)

(

)

) γ

( ( min f x

≤

Ax k

−

+ B x t A

γ = A 0

(

)

(

)

+ A x s B i

∑

 

 

= i 1

Sao cho

δ = i

= i 1

δ ≥

     ∑   γ ≥ 

Đối với mỗi bài toán, hàm đa mục tiêu và các ràng buộc thì khả vi phụ

thuộc vào các biến x, γ và δ . Những giải pháp cho các bài toán đó là cho một

dãy (

(

)kλ → +∞ , nhận được từ mệnh đề 2.7 một dãy

) eP x hoặc

( ) wP x

kx mà

dần đến 0.

δ ≥ 1 k 0 0      δ ≤  γ ≥ 

KẾT LUẬN

Sau quá trình tìm hiểu, luận văn đã đạt được một số kết quả như sau:

Trong chương 1 giới thiệu 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à chứng minh mối quan hệ giữa các định nghĩa Pareto chính

Trong chương 2 giới thiệu bài toán qui hoạch nhiều mục tiêu phân

thường, minh họa bằng sơ đồ.tuyến tính trong đó chứng minh lại các điều

kiện tối ưu với bổ đề 1, từ đó rút ra nhận xét tính đơn điệu của các hàm thành

phần. Luận văn trình bày chứng minh định lý 9 và định lý 10 cho ta tính chất

cụ thể nghiệm Pareto và nghiệm Pareto yếu, xây dựng hàm phạt cho việc

kiểm tra nghiệm Pareto và nghiệm Pareto yếu, thấy được tính nửa liên tục

trên, nửa liên tục dưới của hàm phạt qua mệnh đề 8, mệnh đề 9, mệnh đề 10.

Tìm hiểu vấn đề cực tiểu hóa một hàm khả vi trên cả tập nghiệm Pareto và tập

nghiệm Pareto yếu.

Các kết quả đã được trình bày trong các sách [1], [3], [4],[5] (phần tài

liệu tham khảo).

Hơn nữa, các kết quả trên trong bài toán qui hoạch nhiều mục tiêu phân

tuyến tính ở chương 2 đúng cho bài toán qui hoạch nhiều mục tiêu chương 1.

Vì sự hiểu biết của bản thân còn hạn chế nên luận văn không tránh khỏi

sự thiếu sót. Em rất mong sự góp ý và chỉ bảo của Quý Thầy Cô trong hội

đồng để luận văn được hoàn thiện hơn.

TÀI LIỆU THAM KHẢO

Tài liệu tiếng Việt

[1] Bùi Thế Tâm – Trần Vũ Thiệu, Các phương pháp tối ưu hóa, Nxb.

Giao thông vận tải ,1998.

[2] Bùi Minh Trí, Tối ưu hóa. Tập 1,2. NXB Khoa học kỹ thuật, 2005.

Tài liệu tiếng Anh

[3] Christian Malivert, Multicriteria Fractional Optimization, Université

de Limoges, France, 1995.

[4] Rockafellar R.T., Convex Analysis, Princeton University Press, 1970.

[5] Matthias Ehrgott., Multicriteria Optimization, Second edition,

Auckland, 2005.

linear

fractional

[6] Kornbluth J., Steuer R., Multiple objective

programming, Management Science 27, (1981) 9, 1024-1039.