Phương pháp hàm phạt cho bài toán tối ưu

BỘ GIÁO DỤC VÀ ĐÀO TẠO

TRƯỜNG ĐẠI HỌC KHOA HỌC

NGUYỄN THỊ LÊ

PHƯƠNG PHÁP HÀM PHẠT

CHO BÀI TOÁN TỐI ƯU

LUẬN VĂN THẠC SỸ

Chuyên ngành : TOÁN ỨNG DỤNG

Mã số : 60 46 36

Người hướng dẫn khoa học:

GS- TSKH LÊ DŨNG MƯU

THÁI NGUYÊN, 2012

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

Lời cảm ơn 4

Mở đầu 5

1 Các kiến thức cơ bản về tập lồi và hàm lồi 7

1.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2.1 Định nghĩa và tính chất . . . . . . . . . . . . . . . . 11

1.2.2 Tính liên tục . . . . . . . . . . . . . . . . . . . . . . 13

1.2.3 Dưới vi phân . . . . . . . . . . . . . . . . . . . . . . 14

1.2.4 Tính chất cực trị . . . . . . . . . . . . . . . . . . . 15

2 Phương pháp hàm phạt 17

2.1 Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . 17

2.1.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . 17

2.1.2 Các điều kiện tối ưu . . . . . . . . . . . . . . . . . . 19

2.2 Phương pháp hàm phạt . . . . . . . . . . . . . . . . . . . . 23

2.2.1 Hàm phạt điểm ngoài . . . . . . . . . . . . . . . . . 24

2.2.2 Hàm phạt điểm trong . . . . . . . . . . . . . . . . . 26

2.2.3 Hàm phạt kiểu Lagrange . . . . . . . . . . . . . . . 31

3 Hàm phạt chính xác và áp dụng 42

3.1 Hàm phạt chính xác cho bài toán tối ưu lồi. . . . . . . . . . 42

3.2 Hàm phạt chính xác cho bài toán tối ưu trên tập Pareto . . 49

3.2.1 Bài toán tối ưu vecto tuyến tính . . . . . . . . . . . 49

3.2.2 Hàm phạt chính xác cho bài toán tối ưu trên tập

Pareto . . . . . . . . . . . . . . . . . . . . . . . . . 53

2

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

Tài liệu tham khảo 58

3

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

Trước khi trình bày nội dung chính của luận văn, em xin bày tỏ lòng

biết ơn sâu sắc tới GS.TSKH Lê Dũng Mưu người đã tận tình hướng dẫn

và giúp đỡ em trong suốt quá trình học tập và nghiên cứu để em có thể

hoàn thành khóa luận này.

Em cũng xin bày tỏ lòng biết ơn chân thành tới quý thầy, cô giáo trường

Đại học Khoa học- Đại học Thái Nguyên và Viện Toán học - Viện Khoa

học và Công nghệ Việt Nam đã giảng dạy và giúp đỡ em hoàn thành khóa

học.

Nhân dịp này em cũng xin chân thành cảm ơn Ban Giám hiệu, các bạn

đồng nghiệp Trường Cao đẳng Công nghệ và Kinh tế công nghiệp, gia đình

và bạn bè đã luôn động viên, giúp đỡ và tạo điều kiện cho em về mọi mặt

trong suốt quá trình học tập và thực hiện khóa luận tốt nghiệp.

Mặc dù đã có nhiều cố gắng nhưng Luận văn khó tránh khỏi những

thiếu sót. Tác giả rất mong nhận được ý kiến đóng góp của quý thầy, cô

và bạn đọc để luận văn được hoàn thiện hơn.

Xin trân trọng cảm ơn!

Thái Nguyên, ngày 20 tháng 07 năm 2012

Tác giả

Nguyễn Thị Lê

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

Mở đầu

Bài toán tối ưu là bài toán tìm một phương án chấp nhận được để

làm cực trị một hàm số hoặc một hàm vecto. Đây là bài toán có nhiều ứng

dụng trong thực tế. Khó khăn chính trong việc nghiên cứu và giải quyết

bài toán này là phải tìm được một phương án tối ưu trong miền chấp nhận

được. Để giải quyết khó khăn này, phương pháp hàm phạt là một cách

tiếp cận cơ bản để giải quyết bài toán tối ưu có ràng buộc. Ý tưởng chính

của phương pháp này là chuyển bài toán có ràng buộc về một dãy các bài

toán không ràng buộc hoặc có ràng buộc đơn giản hơn. Các loại hàm phạt

thường được dùng là hàm phạt điểm ngoài, hàm phạt điểm trong và hàm

phạt kiểu Lagrange (thưởng- phạt). Đối với phương pháp hàm phạt điểm

ngoài, hàm phạt được xác định cả bên ngoài miền chấp nhận được và có

tính chất là lượng phạt p(x) > 0 nếu x không thuộc miền chấp nhận được

D, trái lại, nếu x ∈ D thì p(x) = 0. Một hàm phạt khác là hàm phạt kiểu

Lagrange, hàm này cũng xác định cả bên ngoài miền ràng buộc như hàm

phạt điểm ngoài, nhưng bên trong miền chấp nhận được, lượng phạt có

thể nhận giá trị âm, tức là được thưởng tùy theo mức độ thỏa mãn miền

ràng buộc. Phương pháp có hiệu quả hơn cả là phương pháp hàm phạt

điểm trong, khác với hàm phạt điểm ngoài và hàm phạt kiểu Lagrange,

hàm phạt này chỉ xác định tại miền trong của tập chấp nhận được, còn

tại các điểm gần biên của miền chấp nhận được thì p(x) = +∞.

Thông thường, người ta chỉ có thể chuyển việc một bài toán có ràng

buộc về việc giải một dãy vô hạn các bài toán không có ràng buộc hoặc có

ràng buộc đơn giản hơn. Tuy nhiên trong một số trường hợp cụ thể, với

những điều kiện nhất định thì ta có thể chuyển về việc giải chỉ duy nhất

một bài toán không ràng buộc. Hàm phạt cho tính chất này được gọi là

hàm phạt chính xác.

Bản luận văn này nhằm mục đích chủ yếu là hệ thống các kiến thức cơ

bản về các loại phương pháp hàm phạt đã kể trên. Cụ thể, luận văn đã đề

5

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