Nghiệm tối ưu (tối ưu hóa)

Nghiệm tối ưu — trong nghiên cứu vận trù, tối ưu hóa và lý thuyết ra quyết định, đây là nghiệm chấp nhận được (tức là thỏa mãn tất cả các ràng buộc của bài toán) đảm bảo giá trị cực trị (cực đại hoặc cực tiểu, tùy theo cách đặt bài toán) của hàm mục tiêu.

Việc tìm nghiệm tối ưu là mục tiêu chính của hầu hết các bài toán tối ưu hóa.

Bản chất và đặc trưng

Nghiệm tối ưu có hai đặc trưng then chốt:

1. Tính chấp nhận được: Nó phải thỏa mãn tất cả các ràng buộc được áp đặt lên các biến của mô hình. Nói cách khác, nghiệm tối ưu luôn thuộc miền nghiệm chấp nhận được (MNC). 2. Tính cực trị theo hàm mục tiêu: Trong số tất cả các nghiệm chấp nhận được, nó đảm bảo giá trị tốt nhất (cực đại hoặc cực tiểu) của hàm mục tiêu, hàm này hình thức hóa tiêu chí tối ưu.

Không phải mọi nghiệm chấp nhận được đều là nghiệm tối ưu, nhưng bất kỳ nghiệm tối ưu nào cũng nhất thiết phải là nghiệm chấp nhận được.

Mối liên hệ với miền nghiệm chấp nhận được

Miền nghiệm chấp nhận được (MNC) là tập hợp tất cả các phương án (bộ giá trị của các biến) thỏa mãn các ràng buộc của bài toán. Nghiệm tối ưu là điểm (hoặc các điểm) trong miền này mà tại đó hàm mục tiêu đạt cực trị. Nếu MNC rỗng thì bài toán không có nghiệm chấp nhận được và do đó cũng không có nghiệm tối ưu.

Vai trò của hàm mục tiêu và các ràng buộc

• Các ràng buộc xác định tập hợp các nghiệm khả thi (MNC).
• Hàm mục tiêu xác định nghiệm nào trong số các nghiệm khả thi đó là tốt nhất (tối ưu).

Không có hàm mục tiêu thì không thể xác định nghiệm chấp nhận được nào là tối ưu. Không có các ràng buộc thì bài toán có thể là tầm thường hoặc không có nghiệm tối ưu hữu hạn (ví dụ, cực đại hóa hàm tuyến tính không có ràng buộc).

Tính duy nhất của nghiệm tối ưu

Nghiệm tối ưu không phải lúc nào cũng duy nhất. Trong một số bài toán (ví dụ, trong quy hoạch tuyến tính, nếu hàm mục tiêu song song với một trong các ràng buộc tích cực) có thể tồn tại vô số nghiệm tối ưu có cùng giá trị hàm mục tiêu. Tuy nhiên, giá trị của hàm mục tiêu tại điểm (các điểm) tối ưu luôn là duy nhất (nếu tối ưu tồn tại).

Các phương pháp tìm nghiệm

Để tìm nghiệm tối ưu trong nghiên cứu vận trù, người ta sử dụng nhiều phương pháp toán học khác nhau tùy theo loại mô hình:

• Phương pháp đơn hình (cho quy hoạch tuyến tính)
• Các phương pháp giảm gradient và các phương pháp số khác (cho quy hoạch phi tuyến)
• Phương pháp nhánh và cận, các phương pháp cắt (cho quy hoạch nguyên)
• Các phương pháp quy hoạch động

Sự phụ thuộc vào mô hình

Điều quan trọng cần hiểu là nghiệm chỉ là tối ưu trong khuôn khổ mô hình toán học được chấp nhận. Nếu mô hình phản ánh không đầy đủ tình huống thực tế (hàm mục tiêu được chọn không đúng, không tính đến các ràng buộc hoặc phụ thuộc quan trọng), thì nghiệm tối ưu được tìm thấy về mặt hình thức có thể trở nên không hiệu quả hoặc thậm chí sai lầm trong thực tiễn.

Tính tối ưu trong các bài toán đa tiêu chí

Trong các bài toán có nhiều hàm mục tiêu (tối ưu hóa đa tiêu chí), khái niệm nghiệm tối ưu duy nhất thường được thay thế bằng khái niệm tối ưu Pareto. Nghiệm tối ưu Pareto là nghiệm chấp nhận được mà không thể cải thiện giá trị của một hàm mục tiêu mà không làm xấu đi giá trị của ít nhất một hàm mục tiêu khác.

Tài liệu tham khảo

• Ventzel E. S. Nghiên cứu vận trù: bài toán, nguyên tắc, phương pháp luận. — M.: Nauka, 1988.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

Xem thêm

• Nghiên cứu vận trù
• Tối ưu hóa
• Mô hình toán học
• Hàm mục tiêu
• Các ràng buộc
• Miền nghiệm chấp nhận được
• Nghiệm chấp nhận được
• Tiêu chí
• Lý thuyết ra quyết định
• Tối ưu hóa đa tiêu chí
• Tối ưu Pareto
• Cực trị