Đối ngẫu của bài toán tối ưu đa mục tiêu

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 SƯ PHẠM



NGUYỄN QUANG PHÚ

ĐỐI NGẪU CỦA BÀI TOÁN

TỐI ƯU ĐA MỤC TIÊU

Chuyên ngành: TOÁN GIẢI TÍCH

Mã số : 60.46.01.02

LUẬN VĂN THẠC SĨ TOÁN HỌC

Thái Nguyên, năm 2013

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

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC SƯ PHẠM



NGUYỄN QUANG PHÚ

ĐỐI NGẪU CỦA BÀI TOÁN

TỐI ƯU ĐA MỤC TIÊU

Chuyên ngành: TOÁN GIẢI TÍCH

Mã số : 60.46.01.02

LUẬN VĂN THẠC SĨ TOÁN HỌC

Người hướng dẫn: PGS.TS Đỗ Văn Lưu

Thái Nguyên, năm 2013

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

ii

MỤC LỤC

Trang

Trang bìa phụ ............................................................................................................... i

Mục lục...............................................................................................................ii

MỞ ĐẦU ...........................................................................................................1

Chương 1: SÁU LOẠI BÀI TOÁN ĐỐI NGẪU ĐA MỤC TIÊU VÀ CÁC

ĐỊNH LÍ ĐỐI NGẪU.......................................................................................4

1.1. Các khái niệm và định nghĩa.................................................................. 4

1.2. Bài toán tối ưu vô hướng và các đối ngẫu của nó.................................. 5

1.3. Đối ngẫu

1

( ) D

và họ các đối ngẫu

( ), D  F ....................................... 7

1.4. Các bài toán đối ngẫu đa mục tiêu (DFL),(DF),(DL) và (DP) ................ 11

1.5. Mối quan hệ giữa các đối ngẫu

1

( ),( ), vµ ( ) D D D   F FL

..................... 18

Chương 2: MỐI QUAN HỆ GIỮA SÁU LOẠI BÀI TOÁN ĐỐI NGẪU

ĐA MỤC TIÊU...............................................................................................27

2.1. Các định nghĩa và khái niệm................................................................ 27

2.2. Mối quan hệ bao hàm thức giữa DFL, DF, DL và DP............................ 29

2.3. Điều kiện bằng nhau của các tập hợp DFL, DF, DL và DP ................... 35

2.4. Đối ngẫu đa mục tiêu Nakayama ......................................................... 39

2.5. Đối ngẫu đa mục tiêu Wofle ................................................................ 44

2.6. Đối ngẫu đa mục tiêu Weir – Mond..................................................... 49

KẾT LUẬN.....................................................................................................54

TÀI LIỆU THAM KHẢO .............................................................................55

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

1

MỞ ĐẦU

1. Lí do chọn đề tài

Lý thuyết đối ngẫu là một bộ phận quan trọng của lý thuyết tối ưu. Với bài

toán cực tiểu người ta xây dựng bài toán đối ngẫu cực đại và thiết lập các định lý

đối ngẫu mạnh, yếu, ngược. Các loại bài toán đối ngẫu thường được nghiên cứu là:

đối ngẫu Lagrange, đối ngẫu Wolfe, đối ngẫu Weir – Mond, đối ngẫu Nakayama,

đối ngẫu Bot – Wanka. Các định lý đối ngẫu mạnh có nhiều ứng dụng trong việc

xây dựng các thuật toán tìm nghiệm tối ưu.

Lý thuyết đối ngẫu cho các bài toán tối ưu đa mục tiêu đã được phát triển bởi

nhiều tác giả như: J. Jahn, N. Nakayama, P. Wolfe, T. Weir, B. Mond, R.I. Bot, G.

Wanka,...(xem chẳng hạn [2], [3], [5] – [7], [9] – [11]). Với các giả thiết về tính lồi

của dữ liệu bài toán , Bot – Wanka [2,3] đã xây dựng sáu loại bài toán đối ngẫu cho

bài toán tối ưu đa mục tiêu với ràng buộc nón trong không gian hữu hạn chiều, thiết

lập các định lý đối ngẫu yếu, mạnh và các kết quả về quan hệ bao hàm thức của các

tập ảnh các bài toán đối ngẫu đa mục tiêu.

Lý thuyết đối ngẫu của Bot – Wanka cho các bài toán tối ưu đa mục tiêu

được nhiều tác giả quan tâm nghiên cứu. Chính vì vậy tôi chọn đề tài “Đối ngẫu của

bài toán tối ưu đa mục tiêu”. Đây là đề tài có tính thời sự và đang được nhiều nhà

toán học quan tâm nghiên cứu.

2. Mục đích và nhiệm vụ nghiên cứu

2.1. Mục đích nghiên cứu

Mục đích nghiên cứu của luận văn này là trình bày các định lý đối ngẫu yếu

và mạnh của Bot – Wanka [2], [3] cho bài toán tối ưu đa mục tiêu với ràng buộc

nón và các kết quả về quan hệ bao hàm thức của các tập ảnh của sáu loại bài toán

đối ngẫu đó cùng với các kết quả so sánh với các bài toán đối ngẫu Nakayama,

Wolfe, Weir – Mond.

2.2. Nhiệm vụ nghiên cứu

- Luận văn tập trung vào các nhiệm vụ chính sau đây:

- Đọc, dịch tài liệu từ hai bài báo tiếng Anh của R.I. Bot và G.Wanka (2004)

đăng trên tạp chí Optimization.

- Sử dụng các kết quả của hai bài báo đó để viết luận vă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

2

3. Phương pháp nghiên cứu

- Sử dụng công cụ giải tích hàm, giải tích lồi và các kiến thức của lí thuyết tối ưu.

4. Bố cục của luận văn

- Luận văn bao gồm phần mở đầu, hai chương, kết luận và danh mục các tài

liệu tham khảo.

Chương 1. Sáu loại bài toán đối ngẫu đa mục tiêu và các định lí đối ngẫu

Trình bày các định lí đối ngẫu yếu và mạnh cho bài toán tối ưu đa mục tiêu

(P) với ràng buộc nón trong không gian hữu hạn chiều. Với các giả thiết về tính lồi

của các hàm mục tiêu và ràng buộc, các định lí đối ngẫu mạnh cho bài toán vô

hướng (

P

) được trình bày. Từ bài toán vô hướng (

P

) sáu bài toán đối ngẫu cho (P)

được trình bày cùng với các định lí đối ngẫu yếu và mạnh. Một số kết quả về quan

hệ bao hàm thức của các tập ảnh của các bài toán đối ngẫu (D1),

(D ) 

, và (DFL)

được trình bày cùng với các kết quả so sánh tập nghiệm hữu hiệu của các bài toán

đối ngẫu đó. Các kết quả trình bày trong chương 1 là của R.I. Bot và G. Wanka [2].

Chương 2. Mối quan hệ giữa sáu loại bài toán đối ngẫu đa mục tiêu

Trình bày các kết quả về quan hệ bao hàm thức giữa sáu loại bài toán đối

ngẫu của bài toán tối ưu đa mục tiêu (P) đã trình bày trong chương 1 là (D1),

(D ) 

,

(DFL), (DF), ( DL) và (DP). Kết quả chỉ ra rằng khi các giả thiết (Af),(Ag) và (ACQ)

đúng thì với

  F

, ta có quan hệ bao hàm thức giữa các tập ảnh của các bài toán

đối ngẫu:

1         m m D D D D D D Ö Ö FL L F P

và các đẳng thức giữa các tập

các phần tử cực đại của các bài toán đối ngẫu:

max max max max max max 1

    

 FL F L P v D v D v D v D v D v D

Các quan hệ bao hàm thức giữa sáu loại bài toán đối ngẫu đó cũng được so

sánh với các bài toán đối ngẫu Nakayama, Wolfe và Weir – Mond. Các kết quả

được trình bày trong chương 2 la của R.I. Bot và G. Wanka [3].

Nhân dịp này em xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới PGS￾TS Đỗ Văn Lưu, người thầy đã tận tình hướng dẫn, giúp đỡ em hoàn thành bản

luận văn này.