BÀI TOÁN TỐI ƯU RÀNG BUỘC BẤT PHƯƠNG TRÌNH

Nguyễn Như Phong

Kỹ thuật Hệ thống Công nghiệp

Đại học Bách Khoa TPHCM

Bài toán tối ưu có ràng buộc dạng bất phương trình:

Max     z = f(X)

            St.        g_i(X) £ 0, i = 0,  1,...m

Các ràng buộc không âm X  ³  0 nếu có sẽ được bao gồm trong m ràng buộc nêu trên.

Để giải bài toán tối ưu có ràng buộc dạng bất phương trình, ta thường dùng các phương pháp  Lagrange mở rộng. Phương pháp Lagrange mở rộng có giới hạn về mặt tính toán ứng dụng cho các trường hợp thực tế.

Điều kiện Kuhn – Tucker được xây dựng dựa trên phương pháp Lagrange và cung cấp nền tảng cho giải thuật quy hoạch phi tuyến.

Các giải thuật quy hoạch phi tuyến có thể chia thành hai loại là trực tiếp và gián tiếp. Giải thuật trực tiếp như giải thuật độ dốc là giải thuật xác định điểm tối ưu theo độ cốc cực đại là hướng gia tăng hay suy giảm nhanh nhất của hàm mục tiêu tương ứng với bài toán cực đại hay cực tiểu. Giải thuật gián tiếp bao gồm các giải thuật như quy hoạch toàn phương, quy hoạch phân chia hay quy hoạch ngẫu nhiên.

TLTK

Nguyễn Như Phong. Vận trù xác định. NXBĐHQG. 2010