Một số vấn đề về quy hoạch tuyến tính và ứng dụng

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

TRƯỜNG ĐẠI HỌC QUY NHƠN

LÊ TÍNH

MỘT SỐ VẤN ĐỀ VỀ QUY HOẠCH TUYẾN

TÍNH VÀ ỨNG DỤNG

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

Bình Định - 2020

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

TRƯỜNG ĐẠI HỌC QUY NHƠN

LÊ TÍNH

MỘT SỐ VẤN ĐỀ VỀ QUY HOẠCH TUYẾN

TÍNH VÀ ỨNG DỤNG

Chuyên ngành: Toán giải tích

Mã số: 8.46.01.02

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

Người hướng dẫn: TS. NGUYỄN HỮU TRỌN

Lời cam đoan

Tôi xin cam đoan nội dung trình bày trong luận văn này là trung thực và không

trùng khớp với đề tài khác. Tôi cũng xin cam đoan rằng các kết quả trong luận văn,

tài liệu tham khảo và nội dung trích dẫn đảm bảo tính trung thực, chính xác.

Quy Nhơn, tháng 7 năm 2020

Học viên

Lê Tính

Lời cảm ơn

Luận văn này được hoàn thành dưới sự hướng dẫn tận tình của thầy Nguyễn Hữu

Trọn. Tôi xin bày tỏ lòng biết ơn sâu sắc đến thầy, người đã giúp đỡ và chỉ bảo tôi một

cách tận tình trong suốt quá trình thực hiện luận văn. Xin cảm ơn các thầy cô trong

khoa Toán và Thống kê - Đại học Quy Nhơn đã ân cần dạy tôi trong suốt quá trình

học tập tại đây.

Đặc biệt tôi xin gửi lời cảm ơn chân thành và biết ơn vô tận đối gia đình tôi, những

người đã luôn sát cánh và tạo động lực để tôi hoàn thành luận văn này.

Cuối cùng, vì kiến thức bản thân còn hạn chế nên dù rất cố gắng nhưng chắc chắn

luận văn còn nhiều thiếu sót. Kính mong quý thầy cô cùng các bạn đồng nghiệp đóng

góp ý kiến để luận văn có thể hoàn chỉnh hơn.

Quy Nhơn, tháng 7 năm 2020

Học viên

Lê Tính

Mục lục

Lời cam đoan

Lời cảm ơn

Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1 Kiến thức chuẩn bị 3

1.1 Tập lồi, hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.1 Giá trị riêng, véc tơ riêng của ma trận . . . . . . . . . . . . . . 5

1.2.2 Ma trận khả nghịch . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.3 Ma trận đường chéo . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.4 Ma trận đối xứng . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.5 Ma trận xác định dương . . . . . . . . . . . . . . . . . . . . . . 6

2 Quy hoạch phi tuyến 8

2.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2.1 Điều kiện tối ưu cấp 1 . . . . . . . . . . . . . . . . . . . . . . . 10

2.2.2 Điều kiện cấp 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.3 Điểm yên ngựa và tính chất . . . . . . . . . . . . . . . . . . . . . . . . 27

2.4 Đối ngẫu trong Quy hoạch phi tuyến . . . . . . . . . . . . . . . . . . . 32

3 Lý thuyết đối ngẫu trong quy hoạch lồi 35

3.1 Đối ngẫu mạnh trong Quy hoạch lồi . . . . . . . . . . . . . . . . . . . . 36

3.2 Một số ví dụ về các bài toán đối ngẫu . . . . . . . . . . . . . . . . . . . 41

3.2.1 Quy hoạch tuyến tính . . . . . . . . . . . . . . . . . . . . . . . 41

3.2.2 Quy hoạch toàn phương . . . . . . . . . . . . . . . . . . . . . . 42

3.2.3 Một bài toán minimax . . . . . . . . . . . . . . . . . . . . . . . 44

4 Một số ứng dụng 46

4.1 Phân tích phổ của một ma trận đối xứng . . . . . . . . . . . . . . . . . 46

4.2 Bất đẳng thức Kantorovich . . . . . . . . . . . . . . . . . . . . . . . . 48

4.3 Bất đẳng thức Hadamard . . . . . . . . . . . . . . . . . . . . . . . . . 50

4.4 Bất đẳng thức Hilbert . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.5 Các bài toán biến phân trong phương pháp tựa Newton . . . . . . . . . 56

Kết luận 59

Tài liệu tham khảo 60