Microsoft Word - Bellman

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 1

3

5

3

9 4

3

4 8

11

7

6

5 10

6 12

6 4

8

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

I3 (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

Tìm ñường ñi tối ưu

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);

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

Lưu Như Hòa-ðKTð-KSTN-K50

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

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
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