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.
AMBIENT/
Chủ đề:
Nội dung Text: 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ương 5
Kỹ thuật tối ưu trong TNN
Quy hoạch động trong TNN
- 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
- 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
- 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)
- 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)
- Giới thiệu
v
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ê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.
- 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
- 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
- Hình thành DP và pp giải
Phương trình đệ quy lùi
f n* ( S n ) = Opt .{ Rn ( S n , X n ) + f n*+1 ( S n +1 )}
Xn
= Opt .{ Rn ( S n , X n ) + f n*+1 [ Tn ( S n , X n ) ] }
Xn
Hoặc:
Opt.{ R (S , X )}
n n n for n = N
Xn
f (Sn ) =
*
{ }
n
Opt n n n n+1 (Sn+1 )
. R ( S , X ) + f *
for n = 1 to N − 1
Xn
- Ứ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ổ)
- Ứng dụng của DP trong TNN
I. Bài toán phân bổ nước
R3(x3)
S1
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
x
1
- Ứ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)
- Ứng dụng DP trong TNN
I. Bài toán phân bổ nước
--
Tại giai đoạn 1
f1 * ( S1 ) = Max [ R 3 (x 3 ) ]
0 x3 S1
0 S1 Q
--
Tại giai đoạn 2
f 2 * ( S 2 ) = Max [ R 2 (x 2 ) + f1 * ( S 2 − x2 ) ]
0 x2 S2
0 S2 Q
--
Tại giai đoạn 3
f 3 * ( S3 ) = Max [ R 1 (x1 ) + f 2 * ( S3 − x1 ) ]
0 x1 S3
S3 = Q
- Ứ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
- Ứng dụng DP trong TNN
II. Bài toán vận hành hồ chứa (Reservoir Operation Problem)
St
T
Max Bt ( St , Rt ) Qt
Rt
t =1
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=1 t=2 t = T-1 t = T
n = T n = T-1 n=2 n=1
S1 ST-1 ST ST+1
- Ứ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 1
fT ( ST ) = Max [ BT (ST ,R T ) ]
0 RT ST + QT
ST + QT − RT K
-
Tại giai đoạn 2: n= 2, t = T-1
fT2−1 ( ST −1 ) = Max �
B
� T1 (ST1 ,R T1 )+f T
1
( ST −1 + QT −1 − RT −1 ) �
�
0 RT −1 ST −1 + QT −1
ST −1 + QT −1 − RT −1 K
-
Một cách tươngn tự, cho bất kỳ thời kỳ t
� BT (ST ,R T )+fTn+−11 ( ST + QT − RT ) �
f t ( ST ) = Max � �
0 RT ST + QT
ST + QT − RT K
-
Tại giai đoạn cuối
f1T cùng,
( S1 = St = 1,M
') = nax
= T�
B (S',R )+ f t −1
( S '+ Q1 − R1 ) �
� 1 1 2 �
0 R1 S '+ Q1
S '+ Q1 − R1 K
- Ứ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 Q2 QT
S’ S2’=S’+Q-R1* S3’=S2’+Q2-R2*
R1* R2* RT*
- Ứ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
- Thank You !
www.themegallery.com
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
