Bài giảng Phân tích hệ thống tài nguyên nước: Chương 5 - Ngô Lê An (tt)

Bài giảng "Phân tích hệ thống tài nguyên nước - Chương 5: Kỹ thuật tối ưu trong TNN (Quy hoạch động trong TNN) giới thiệu khái niệm quy hoạch động trong TNN, nguyên lý tối ưu Bellman, thiết lập DP và phương pháp giải, ứng dụng DP trong TNN. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích hệ thống tài nguyên nước: Chương 5 - Ngô Lê An (tt) Chương5KỹthuậttốiưutrongTNNQuyhoạchđộngtrongTNN Nộidung1 Giới thiệu2 Nguyên lý tối ưu Bellman3 Thiết lập DP và phương pháp giải4 Ứng dụng DP trong TNN Giớithiệuv Quy hoạch động (Dynamic Programming - DP): Chia bài toán tối ưu ban đầu với tất cả biến của nó, thành một tập hợp những vấn đề tối ưu nhỏ hơn, mỗi vấn đề tối ưu nhỏ đó cần được giải quyết trước khi Xác định được nghiệm tối ưu tổng thể của vấn đề ban đầuv DP phù hợp cho những vấn đề quyết định theo chuỗiØ Vấn đề quyết định theo chuỗi (hoặc đa giai đoạn): Những quyết định được làm một cách trình tự theo chuỗi, dựa vào trạng thái của hệ thốngØ Ví dụ của vấn đề quyết định theo chuỗi trong TNN: Vận hành hồ chứav DP không tuân theo bất cứ một công thức toán học chuẩn nàov Tùy vào đặc trưng của vấn đề xem xét, sẽ hình thành những vấn đề quyết định theo chuỗi khác nhauv DP có thể áp dụng cho bài toán tuyến tính hoặc phi tuyến Giớithiệuv Một vấn đề quyết định đơn giai đoạn Phản hồi, R Đầu vào S Chuyển đổi Đầu ra T trạng thái, T (S, X) Quyết định Xv S: đầu vào (input)v X: Biến quyết định (decision variable)v T: đầu ra (output)v Bởi vì biến quyết định cho đầu vào S, sẽ có một tin phản hồi R (return) là hàm của cả S và Xv Quá trình chuyển đổi từ đầu vào S tới đầu ra T gọi là sự chuyển đổi trạng thái (state transformation) Giớithiệuv Vấn đề quyết định đa giai đoạn: được tạo thành bởi n giai đoạn Rn Rn-1 R2 R1Sn Sn-1 Sn-1 S1 S0 Xn Xn-1 X2 X1 Giai đoạn n Giai đoạn (n-1) Giai đoạn 2 Giai đoạn 1v Giai đoạn n (stages): Điểm mốc của bài toán, quyết định được thực hiện tại đóv Biến quyết định Xn (decision variables): chuỗi của những hành động ứng cho mỗi giai đoạnv Biến trạng thái Sn (state variables): Miêu tả trạng thái của hệ thống tại giai đoạn nv Thông tin phản hồi từ giai đoạn n (Rn): Hiệu quả của những quyết định tại mỗi giai đoạn, Rn = R(Sn, Sn+1, xn)v Chuyển đổi giai đoạn Tn (stage transformation): mối quan hệ giữa trạng thái đầu vào, đầu ra tại bất cứ giai đoạn n: Sn+1 = Tn(Sn, Xn) Giớithiệuv Quy hoạch động rời rạc, tất định (Discrete Deterministic DP)- Biến trạng thái và biến quyết định chỉ lấy những giá trị rời rạc- Biến trạng thái tại giai đoạn kế tiếp được xác định hoàn toàn bởi trạng thái và chính sách quyết định tại giai đoạn hiện hành – hàm chuyển đổi trạng thái là tất định NguyênlýtốiưuBellmanv Nguyên lý tối ưu Bellman Một chính sách tối ưu (một tập hợp của những quyết định) có đặc tính là Bất luận trạng thái ban đầu và quyết định ban đầu như thế nào, những quyết định tiếp theo phải tạo thành một chính sách tối ưu đối với trạng thái sinh ra từ quyết định ban đầu. HìnhthànhDPvàppgiải v Bài toán tìm đường vận chuyển ngắn nhất B1 C1 D1 B2 C2 D2 E Nguồn Điểm đến B3 C3 D3Giai đoạn 4 Giai đoạn 3 Giai đoạn 2 Giai đoạn 1 v Trạng thái của hệ thống Sn: nút v Giai đoạn của hệ thống là những cột chia rẽ của những nút kết nối v Biến quyết định: Đoạn đường kết nối (links) hay nút tại đó (xn) đến được điểm mục tiêu (Sn+1) v Mối quan hệ đầu vào, đầu ra: Sn+1 = xn v Mục tiêu: Tìm con đường vận chuyển ngắn nhất từ A tới E HìnhthànhDPvàppgiải(1) Vấn đề được chia ra thành các giai đoạn với những biến quyết định tại mỗi giai đoạn(2) Mỗi giai đoạn đều có những trạng thái tương ứng với nó(3) Kết quả quyết định tại mỗi giai đoạn sẽ cho(ü- Những thông tin phản hồi, dựa vào hàm phản hồi, và(ü- Chuyển đổi biến trạng thái hiện hành đi vào biến trạng thái cho giai đoạn kế t ...