Từ khóa: Quy hoạch động; Tối ưu; Ràng buộc; Hàm mục tiêu.
Abstract: This article presents methodological basis of dynamic programming method, a popular and modern optimization seeking method based on analysis of multi-steps decision model. Based on an example, the article also presents application of the method in solving problem on seeking the optimal longitudinal section of urban railway, one of the important requirements of designing work in the field of transport construction.
Keywords: Dynamic Programming; Optimization; Constraints; Object Function.
1. ĐẶT VẤN ĐỀ
Trong cuộc sống người ta thường phải tiến hành một chuỗi các quyết định tại nhiều thời điểm khác nhau. Vì các quyết định được thực hiện ở nhiều giai đoạn khác nhau nên vấn đề trên được gọi là quyết định nhiều bước.
Quy hoạch động là phương pháp toán học dùng để tối ưu hoá quá trình quyết định nhiều bước. Khái niệm quy hoạch động được Richard Bellman đưa ra vào đầu những năm 1950.
Tư tưởng chính của quy hoạch động là tách quá trình quyết định nhiều bước thành những quá trình quyết định đơn bước. Bài toán tối ưu n biến được tách thành n bài toán tối ưu theo một biến được giải liên tiếp nhau. Việc tách bài toán ban đầu thành n bài toán con được thực hiện sao cho lời giải tối ưu của bài toán n biến ban đầu sẽ thu được từ lời giải tối ưu của n bài toán con một biến.
NGUỒN:
TS. Nguyễn Hữu Thiện - Trường Đại học Giao thông Vận tải
Mời xem chi tiết trên Tạp chí Cầu đường Việt Nam số tháng 4 Năm 2017