Điều kiện cần và đủ tối ưu cho bài toán quy hoạch phi tuyến

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

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

TRẦN PHƯƠNG HOA

ĐIỀU KIỆN CẦN VÀ ĐỦ TỐI ƯU

CHO BÀI TOÁN QUY HOẠCH PHI TUYẾN

CHUYÊN NGÀNH: TOÁN ỨNG DỤNG

MÃ SỐ: 60.46.01

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

Người hướng dẫn khoa học: PGS. TS. ĐỖ VĂN LƯU

THÁI NGUYÊN - 2010

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

Mục lục

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

Mở đầu 1

Chương 1. MỘT SỐ ĐỊNH LÝ LUÂN PHIÊN 4

1.1. CÁC ĐỊNH LÝ FARKAS THUẦN NHẤT VÀ KHÔNG THUẦN

NHẤT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2. MỘT SỐ ĐỊNH LÝ LUÂN PHIÊN KHÁC . . . . . . . . . 6

Chương 2. ĐIỀU KIỆN TỐI ƯU KHI KHÔNG GIẢ THIẾT

ĐIỀU KIỆN CHÍNH QUY 9

2.1. CÁC KHÁI NIỆM VÀ KẾT QUẢ BỔ TRỢ . . . . . . . . 9

2.2. CÁC ĐIỀU KIỆN CẦN VÀ ĐỦ TỐI ƯU KHI KHÔNG

GIẢ THIẾT ĐIỀU KIỆN CHÍNH QUY . . . . . . . . . . 19

Chương 3. ĐIỀU KIỆN TỐI ƯU KHI GIẢ THIẾT ĐIỀU

KIỆN CHÍNH QUY 30

3.1. CÁC ĐIỀU KIỆN CHÍNH QUY MANGASARIAN - FRO￾MOVITZ CẤP MỘT VÀ CẤP HAI . . . . . . . . . . . . . 30

3.2. CÁC ĐIỀU KIỆN TỐI ƯU CẤP MỘT VÀ CẤP HAI . . . 34

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

Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

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

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

Lý thuyết các điều kiện tối ưu cho các bài toán quy hoạch toán học

được phát triển từ những giai đoạn sớm nhất của toán học và có nhiều ứng

dụng trong kinh tế, kỹ thuật.

Để dẫn các điều kiện cần tối ưu người ta thường sử dụng một công cụ

hữu hiệu là các định lý tách các tập lồi không tương giao hoặc các định

lý luân phiên (Theorems of the alternative) về sự tương thích của một hệ

tuyến tính thuần nhất hoặc không thuần nhất. Các định lý luân phiên nổi

tiếng là các định lý của J.Farkas, P. Gordan, T. S. Motzkin,...(xem [5]).

Trong bài tổng quan [6], G. Still và M. Streng đã trình bày các điều kiện

cần và đủ tối ưu cho các điểm cực tiểu địa phương chặt cấp một, cấp hai

và cực tiểu cô lập của các bài toán quy hoạch phi tuyến trơn với các ràng

buộc đẳng thức và bất đẳng thức trong không gian hữu hạn chiều. Giữa

các điều kiện cần và các điều kiện đủ tối ưu thường có một sự sai khác (a

gap), trong đó các điều kiện đủ mạnh hơn các điều kiện cần. Khi giả thiết

các điều kiện chính quy Mangasarian - Fromovitz cấp một và cấp hai thì

sẽ không có sự sai khác giữa các điều kiện cần và các điều kiện đủ nữa.

Luận văn tập trung trình bày các điều kiện cần và đủ cho các điểm cực

tiểu địa phương chặt cấp một và cấp hai ở các dạng gốc và đối ngẫu cho

bài toán quy hoạch phi tuyến trơn có hữu hạn ràng buộc đẳng thức và bất

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