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 (Tiếp theo)

Nội dung text: 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 (Tiếp theo)

1. Chương 5 Kỹ thuật tối ưu trong TNN Quy hoạch động trong TNN
2. Nội dung 1 Giới thiệu 2 Nguyên lý tối ưu Bellman 3 Thiết lập DP và phương pháp giải 4 Ứng dụng DP trong TNN
3. Giới thiệu v 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 đầu v 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ứa v DP không tuân theo bất cứ một công thức toán học chuẩn nào v 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 nhau v DP có thể áp dụng cho bài toán tuyến tính hoặc phi tuyến
4. Giới thiệu v 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 X v 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à X v 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)
5. Giới thiệu v Vấn đề quyết định đa giai đoạn: được tạo thành bởi n giai đoạn Rn Rn-1 R2 R1 Sn 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 1 v 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ạn v 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 n v 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)
6. Giới thiệu vQuy 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
7. Nguyên lý tối ưu Bellman v 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.
8. Hình thành DP và pp giả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 D3 Giai đ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
9. Hình thành DP và pp giả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ế tiếp thông qua hàm chuyển chuyển đổi trạng thái (5) Lời giải sẽ bắt đầu bằng việc tìm quyết định tối ưu cho mỗi trạng thái có thể trong giai đoạn cuối cùng – đệ quy lùi (backward recursive) (6) Mối quan hệ đệ quy nhằm nhận dạng chính sách tối ưu cho mỗi trạng thái tại giai đoạn n có thể được viết như sau, biết chính sách tối ưu cho mỗi trạng thái tại giai đoạn kế tiếp (n+1) Phương trình đệ quy lùi
10. Hình thành DP và pp giải Phương trình đệ quy lùi Hoặc:
11. Ứng dụng của DP trong TNN I. Bài toán phân bổ nước Hàm mục tiêu: Tối đa lợi nhuận thực thu được từ phân bổ nước Max z = R1(x1) + R2(x2) + R3(x3) Ràng buộc x1 + x2 + x3 ≤ Q (Nguồn nước có sẵn cho phân bổ)
12. Ứng dụng của DP trong TNN I. Bài toán phân bổ nước R3(x3) S 1 User 3 Giai đoạn 1 x3 R2(x2) S2 User 2 User 3 Giai đoạn 2 x2 R1(x1) S3 User 1 User 2 User 3 Giai đoạn 3 x1
13. Ứng dụng DP trong TNN I. Bài toán phân bổ nước S1: Số lượng nước có sẵn cho phân bổ tại giai đoạn 1 (cho người sử dụng 3 S2: Số lượng nước có sẵn cho phân bổ tại giai đoạn 2 (cùng cho người sử dụng 2 và 3) S3: Số lượng nước có sẵn cho phân bổ tại giai đoạn 3 (cùng cho người sử dụng 1, 2 và 3) * f1 (S1); Lơi nhuận tối đa thu được nhờ phân bổ S1 * f2 (S2); Lơi nhuận tối đa thu được nhờ phân bổ S2 * f3 (S3); Lơi nhuận tối đa thu được nhờ phân bổ S3 X1, X2, X3: Số lượng nước có thể phân bổ tới người sử dụng 1, 2, 3 * * * x1 , x2 , x3 : Số lượng nước được phân bổ tới người sử * * * dụng 1,2 3 tương ứng với f1 (S1); f2 (S2); f3 (S3)
14. Ứng dụng DP trong TNN I. Bài toán phân bổ nước - Tại giai đoạn 1 - Tại giai đoạn 2 - Tại giai đoạn 3
15. Ứng dụng DP trong TNN I. Bài toán phân bổ nước Ví dụ 1: ü Cho Q = 4 đơn vị (Lượng nước có sẵn cho phân bổ tới 3 người sử dụng ü Giả sử phân bổ nước được tiến hành theo số nguyên rời rạc từng đơn vị một, thay đổi từ 0 tới 4 (ví dụ: 0, 1,2,3,4) ü Với 3 người sử dụng được ký hiệu là User 1, User 2 và User 3, Lợi nhuận thực thu được từ sự phân bổ cho 3 người sử dụng nước như sau Số lượng Lợi nhuận thực từ nước được User 1 User 2 User 3 phân bổ (x) R1(x1) R2(x2) R3(x3) 0 0 0 0 1 5 5 7 2 8 6 12 3 9 3 15 4 8 -4 16 ü Tìm phương án phân bổ nước tối ưu tới 3 người sử dụng sao cho lợi nhuận thực thu được là lớn nhất .
16. Ứng dụng DP trong TNN II. Bài toán vận hành hồ chứa (Reservoir Operation Problem) St Qt Rt K ü Bt (St, Rt): Lợi nhuận trong suốt thời kỳ t tương ứng với St và Rt ü T: Số thời kỳ trong năm ü t: Thời kỳ trong năm ü n: giai đoạn t = T t = 1 t = 2 t = T-1 n = T n = T-1 n = 2 n = 1 S S1 ST-1 ST T+1
17. Ứng dụng DP trong TNN II. Bài toán vận hành hồ chứa (Reservoir Operation Problem) - Tại giai đoạn 1: n = 1, t = T - Tại giai đoạn 2: n= 2, t = T-1 - Một cách tương tự, cho bất kỳ thời kỳ t - Tại giai đoạn cuối cùng, t = 1, n = T
18. Ứng dụng DP trong TNN II. Bài toán vận hành hồ chứa (Reservoir Operation Problem) Quá trình truy ngược nghiệm tối ưu Q1 QT Q2 S’ S2’=S’+Q-R1* S3’=S2’+Q2-R2* RT* R1* R2*
19. Ứng dụng DP trong TNN II. Bài toán vận hành hồ chứa (Reservoir Operation Problem) Ví dụ 2: ü Cho K = 4 ü Dòng chảy vào hồ trong 4 mùa: Q1 = 2, Q2 = 1, Q3 = 3, Q4 = 2 ü Lượng dòng chảy trữ và xả chỉ mang những giá trị nguyên dương rời rạc 0, 1, 2, , (Dòng chảy tràn đã bao gồm trong lượng xả) ü Lương trữ của hồ tại bắt đầu của năm là: 0 đơn vị ü Lợi nhuận thực thu được từ việc xả nước được liệt kê trong bảng (lợi nhuận được lấy tương tự cho cả 4 mùa) Lượng xả từ hồ Lợi nhuận thực : NB(R) 0 -100 1 250 2 320 3 480 4 520 5 520 6 410 7 120 ü Tìm chính sách vận hành hồ tối ưu về mặt lợi nhuận
20. www.themegallery.com