Phương pháp chiếu giải bài toán tối ưu

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

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

BÙI THỊ NGHĨA

PHƯƠNG PHÁP CHIẾU GIẢI BÀI

TOÁN TỐI ƯU

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

THÁI NGUYÊN – 2015

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

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

BÙI THỊ NGHĨA

PHƯƠNG PHÁP CHIẾU GIẢI BÀI

TOÁN TỐI ƯU

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

Mã số: 60 46 01 12

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

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

GS. TSKH. LÊ DŨNG MƯU

THÁI NGUYÊN – 2015

i

Mục lục

Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

Chương 1. Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1. Kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2. Phát biểu bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3. Một số ví dụ điển hình về bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3.1. Bài toán thể tích lớn nhất. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3.2. Bài toán lập kế hoạch sản xuất. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3.3. Bài toán định vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3.4. Bài toán phân việc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4. Sự tồn tại nghiệm tối ưu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.5. Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.5.1. Tối ưu không ràng buộc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.5.2. Tối ưu có ràng buộc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.5.3. Điều kiện tối ưu Kuhn - Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

Chương 2. Phương pháp chiếu giải bài toán tối ưu . . . . . . . . . . 23

2.1. Toán tử chiếu lên tập lồi đóng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.2. Một thuật toán chiếu giải bài toán tối ưu lồi. . . . . . . . . . . . . . . . . . . . 27

2.2.1. Thuật toán chiếu dưới đạo hàm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.2.2. Thuật toán hàm phạt điểm trong . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

1

Mở đầu

Toán học nảy sinh từ thực tiễn và đã được ứng dụng rộng rãi trong thực

tế. Lí thuyết tối ưu là một ngành toán học được ứng dụng trong rất nhiều

lĩnh vực của khoa học tự nhiên, xã hội, công nghệ, kinh tế...

Bài toán tối ưu đóng vai trò quan trọng trong lý thuyết tối ưu, có hai yếu

tố quan trọng trong bài toán tối ưu là tập chấp nhận được (tập ràng buộc)

và hàm mục tiêu xác định trên tập đó. Để chứng minh sự tồn tại nghiệm và

xây dựng phương pháp giải, người ta thường phân loại các bài toán theo cấu

trúc của tập chấp nhận được và tính chất hàm mục tiêu.

Mục đích của luận văn này là tổng hợp lại kiến thức cơ bản của bài toán

tối ưu. Đặc biệt luận văn đi sâu trình bày thuật toán chiếu giải bài toán tối

ưu không đòi hỏi tính khả vi của hàm mục tiêu.

Luận văn được chia làm 2 chương

Chương 1: Bài toán tối ưu

Chương này trình bày một số kiến thức cơ bản về giải tích lồi, phát biểu bài

toán tối ưu, một số ví dụ điển hình về bài toán tối ưu, sự tồn tại nghiệm và

điều kiên tối ưu.

Chương 2: Phương pháp chiếu giải bài toán tối ưu.

Chương này trình bày chi tiết về toán tử chiếu lên tập lồi đóng và tính chất

của toán tử chiếu. Thuật toán chiếu để giải bài toán tối ưu lồi đợc giới thiệu

ở đây là thuật toán chiếu dưới đạo hàm. Cuối chương là thuật toán hàm phạt

điểm trong là một kỹ thuật cho phép đưa việc giải bài toán tối ưu có ràng

buộc về việc giải các bài toán không có ràng buộc qua đó cho phép tránh

phải tính hình chiếu vì rất nhiều trường hợp tính hình chiếu rất khó, thậm

trí không thực hiện được.

Nhân dịp này, tôi xin bày tỏ lòng biết ơn sâu sắc tới GS. TSKH. Lê Dũng

Mưu, người thầy đã tận tâm, nhiệt tình hướng dẫn, cung cấp tài liệu, truyền

đạt cho tôi kiến thức trong quá trình học tập và luôn giúp đỡ, động viên tôi