Nguyên lý quy hoạch động Bellman 1. Nguyên lý chung của quy hoạch động Bellman Bên cạnh nguyên lý cực đại Pontryagin ,nguyên lý quy hoạch động Bellman là trụ cột thứ hai của lý thuyết điều khiển tối ưu. Triết lý của quy hoạch động là “biến tĩnh thành động”,biến 1 bài toán n ẩn số giải bằng 1 bước về bài toán 1 ẩn số giải bằng n bước,trong đó các bài toán con có liên hệ với nhau qua 1 công thức truy toán. Khi giải bài toán bằng nguyên lý quy hoạch động Bellman,ta thường xét bài toán ngược từ đích vì khi xét bài toán ngược từ cuối,ta có thể xét tính tối ưu của nó mà không cần quan tâm đến hậu quả.Tất nhiên khi xét từng bài toán con,điều cần quan tâm là tối ưu tổng thể của bài toán lớn chứ không phải là trên từng đoạn đường nhỏ. Chính vì giải bài toán ngược từ cuối nên ta chưa biết được kết cục của nó vì trạng thái của hệ thống lúc đó chưa xác định.Bài toán tối ưu của ta được đặc trưng bởi các tham số,còn gọi là điều kiện đầu.Chỉ tiêu tối ưu J xk và tín hiệu điều khiển tối ưu u xk là hàm của sự kiện xk của bài toán con đó. Sau khi truy ngược từ cuối,dựa vào các điều kiện biên ta “giải xuôi” bài toán để tìm kết cục của bài toán. Nguyên lý tối ưu Bellman: Bất cứ đoạn cuối của 1 quỹ đạo tối ưu nào cũng phải là 1 quỹ đạo tối ưu.
2.Một ví dụ áp dụng nguyên lý Bellman: Ta lấy bài tóan tìm đường đi để đạt chỉ tiêu chất lượng tối ưu. 2 4
4
4
4 8
3
11
7
6
5
6 12
6 4
8
0
3
9
1
1
5
3
7
5
8
3 9
Ta tìm đường đi từ thành phố 1 đến thành phố 10 phải đi qua các thành phố 2,3,4 ...
Lưu Như Hòa-ĐKTĐ-KSTN-K50
Tìm đường đi sao cho tổng chi phí là thấp nhất.(chi phí là trọng số của 1 cạnh) Gọi Qn ( s ) là chi phí nhỏ nhất vận chuyển từ thành phố s đến thành phố 10 (khi còn n giai đoạn). I n ( s ) là thành phố mà từ thành phố s phải đi qua để có chi phí nhỏ nhất (khi còn n giai đoạn) Ta có Qk ( s ) min Qk 1 ( s ) g k ( s ) n=1 s j 10 8 9 n=2 s
5+0 3+0 j 8
5 6 7 n=3 s 2 3 4 n=4 s 1
Q1 ( s ) 5 3 9
9+5 7+5 j 5
j
I1 ( s ) 10 10 Q2 ( s ) 11 12 8
8+3 12+3 5+3 6
7
3+11 4+11 4+11
8+12
4+8 6+8 6+8
2
3
4
4+12
3+14
11+14
I 2 ( s) 9 8 9 Q3 ( s) 12 14 14
I 3 ( s) 7 7 7
Q4 ( s ) 16
I 4 ( s) 2
Vậy quãng đường tối ưu phải là: 1 – 2 – 7 – 9 – 10.Chi phí lúc đó là Q4 16 là nhỏ nhất. Bây giờ ta xét bài toán này với kích thước lớn hơn. Khởi tạo dữ liệu: function data=gendata(m,n) data=round(100*(rand(m,n,n)+0.1)); data(1,:,:)=repmat(data(1,1,:),1,n); for j=1:n data(m,j,:)=repmat(data(m,j,1),1 ,n); end
Lưu Như Hòa-ĐKTĐ-KSTN-K50
m=1000; % so hang n=100; % so cot data = gendata(m,n); index = zeros(m,n); cost = zeros(m+1,n);
Tìm đường đi tối ưu
for i=m:-1:1 for j=1:n [cost(i,j),index(i,j)]=min(reshape(data(i,j,:),1,n)+cost(i+1,:)); end end
Vẽ đoạn đường tối ưu: y(1)=1; for k=2:m+1 y(k)=index(k-1,y(k-1)); end plot(y,'r') axis([1 m+1 1 n]);grid
Ta có kết quả đoạn đường tối ưu theo Bellman như sau:
Quy dao toi uu bellman
100 90 80 70 60 50 40 30 20 10 100
200
300
400
500
600
700
800
900
1000
Tương tự như thế ta cho m và n nhỏ hơn để so sánh 2 phương pháp dùng nguyên lý QHĐ Bellman và phương pháp duyệt thông thường.
Lưu Như Hòa-ĐKTĐ-KSTN-K50
Để đo thời gian thực hiện lệnh ta dùng cặp lệnh: tic-toc: tic for i=m:-1:1 for j=1:n [cost(i,j),index(i,j)]=min(reshape(data(i,j,:),1,n)+cost(i+1,:)); end end y(1)=1; for k=2:m+1 y(k)=index(k-1,y(k-1)); end h=line([1:m+1],y); set(h,'LineWidth',4,'Color','r'); axis([1 m+1 1 n]);grid toc time1 = toc pause
Phuong phap Bellman
100 90 80 70 60 50 40 30 20 10 1
1.5
2
2.5
Kết quả là: Elapsed time is 0.126656 seconds. time1 = 0.1267 Lưu Như Hòa-ĐKTĐ-KSTN-K50
3
3.5
4
4.5
5
5.5
6
Lưu Như Hòa-ĐKTĐ-KSTN-K50
tic T=ones(1,6); Cmin=inf; for p=1:n for q=1:n for r=1:n for s=1:n C=data(1,1,p)+data(2,p,q)+data(3,q,r)+data(4,r,s)+data(5,s,1); if C
Phuong phap duyet thong thuong
100 90 80 70 60 50 40 30 20 10 1
1.5
2
2.5
Lưu Như Hòa-ĐKTĐ-KSTN-K50
3
3.5
4
4.5
5
5.5
6
Kết quả là: Elapsed time is 21.480805 seconds. time2 = 21.4809
Hai phương pháp cho cùng kết quả nhưng rõ ràng phương pháp duyệt chậm hơn rất nhiều so với phương pháp bellman (gấp 169.5 lần trong trường hợp >> Cmin này) >> time2/time1 ans = 169.5532
Cmin = 55 >> cost(1,1) ans = 55
Lưu Như Hòa-ĐKTĐ-KSTN-K50