QUY HOẠCH ĐỘNG

Nguyễn Như Phong

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

Đại học Bách Khoa TPHCM

Phương pháp quy hoạch động xác định lời giải tối ưu của bài toán đa biến bằng cách phân ly bài toán này thành thành nhiều giai đoạn, mỗi giai đoạn là một bài toán con đơn biến.

Ưu điểm của việc phân ly bài toán đa biến thành các bài toán con đơn biến là ở mỗi giai đoạn chỉ tối ưu hóa một bài toán con đơn biến nên tính toán đơn giản hơn việc tối ưu hoá bài toán đa biến.

Nhằm tối ưu toàn cục cho bài toán đa biến và tránh tối ưu cục bộ ở các bài toán đơn biến, mô hình QHĐ sử dụng phương trình đệ quy để liên kết các bài toán con ở các giai đoạn.

Lời giải tối ưu của mỗi bài toán con ở mỗi giai đoạn cũng tối ưu cho bài toán tổng thể. Các bài toán con thường liên kết nhau bởi các ràng buộc chung, khi di chuyển từ bài toán con này đến bài toán con khác, phải duy trì tính khả thi của các ràng buộc chung này. 

Việc tính toán trong quy hoạch động được lặp lại nhiều lần theo từng giai đoạn, lời giải tối ưu của 1 bài toán con này được sử dụng như một ngõ vào của bài toán con tiếp theo. Khi bài toán con ở giai đoạn cuối cùng được giải, ta sẽ thu được lời giải tối ưu của bài toán tổng thể.

Phương trình đệ quy là phương tiện liên kết các giai đoạn QHĐ. Có hai phương pháp đệ quy trong bài toán QHĐ:

• Đệ quy tiến
• Đệ quy lùi

Ở phương pháp đệ quy tiến, tính toán được thực hiện từ giai đoạn đầu đến giai đoạn cuối. Ngược lại phương pháp đệ quy lùi, tính toán được thực hiện từ giai đoạn cuối đến giai đoạn đầu. Hai phương pháp này cho cùng kết quả, mặc dù phương pháp đệ quy tiến có vẻ logic hơn, tuy nhiên phương phương pháp đệ quy lùi thường hiệu quả hơn về mặt tính toán.

TLTK

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