[Lý Thuyết] Về Quy Hoạch Động

Quy hoạch động
Qui hoạch động là một trong những phương pháp tối ưu hiện đại. Đối tượng của qui hoạch động là các quá trình tối ưu nhiều bước nói chung và các quá trình phát triển theo thời gian nói riêng.
Sự xuất hiện của qui hoạch động gắn liền với tên tuổi của nhà toán học Mỹ R.Bellman mà trong những năm 50 của thế kỉ này đã áp dụng cho một loạt các bài toán thực tế, một công cụ mà sau này gọi là nguyên tắc tối ưu. Chính nhờ tính đơn giản và tính tường minh của nguyên tắc này mà phương pháp qui hoạch động tỏ ra đặc biệt hấp dẫn.
Bên cạnh nguyên tắc tối ưu, nguyên tắc quan trọng thứ hai là nguyên tắc lồng bài toán tối ưu đang xét vào một họ các bài toán tương tự. Việc áp dụng nguyên tắc tối ưu và nguyên tắc lồng dẫn đến các phương trình hàm truy toán đối với giá trị tối ưu. Những phương trình thu được cho phép lần lượt viết ra các điều khiển tối ưu cho bài toán xuất phát. Cái hay ở đây là bài toán tính toán điều khiển của cả quá trình chia ra thành một dãy các bài toán tính toán điều khiển đơn giản cho các giai đoạn của quá trình.
Lĩnh vực áp dụng của qui hoạch động rất rộng: Các quá trình kỹ thuật công nghiệp, tổ chức sản xuất, kế hoạch hóa kinh tế, trong các vấn đề khác nhau của vật lý, sinh vật, và quân sự.
$1. PHƯƠNG PHÁP PHƯƠNG TRÌNH TRUY TOÁN VÀ CÁC NGUYÊN TẮC CƠ BẢN CỦA QUI HOẠCH ĐỘNG
1.1 Bài toán phân phối một chiều và phương pháp phương trình truy toán.
1. Bài toán phân phối
Trong thực tế có nhiều tài nguyên khác nhau: Nhân công, tiền máy, nhiên liệu…Mõi tài nguyên có thể sử dụng theo nhiều cách và cho nhiều hiệu quả khác nhau. Vấn đề đặt ra là cần phân phối các tài nguyên đó như thế nào để hiệu quả sử dụng tổng cộng là lớn nhất.
Ta xét quá trình phân phối một tài nguyên với trữ lượng là a. Có n cách sử dụng. Nếu sử dụng đơn vị theo cách thứ i (i=1…N) thì sẽ đạt hiệu quả đo bằng hàm . Hãy qui định số đơn vị cần dùng theo mỗi cách i để tổng hiệu quả là lớn nhất.
Mô hình của bài toán có dạng
(1.1)
(1.1)
(1.2)
và thường được biểu thị bởi những đơn vị đo khác nhau: Chẳng hạn là nhiêu liệu thì là tốc độ, là tiền thì là máy, độ tin cậy… Độ lớn của hiệu quả phụ thuộc vào số lượng tài nguyên sử dụng (a) và vào quá trình được chọn lựa (N).
2. Phương pháp phương trình truy toán
Để nghiên cứu bài toán trên, ta lồng nó vào một họ các quá trình phân phối nào đó. Thay cho một bài toán với số lượng tài nguyên a cho trước và số các cách sử dụng N cố định, ta xét một họ các bài toán như vậy, trong đó a và N thay đổi, tức là ta chuyển quá trình tĩnh thành quá trình động.
Vì cực đại của hàm chỉ phụ thuộc vào a và N, ta gọi giá trị tối ưu là thì

trong đó thỏa mãn (1.2) và (1.3). Khi N thay đổi, ta hãy tìm mối liên hệ giữa các hàm …., Vì ở đây ta biết ngay …. nên có thể nói rõ hơn là : Biết …. với a thay đổi, hãy tìm mối liên hệ giữa …. … ?
Giả sử …… là lượng tài nguyên quyết định đối với quá trình thứ N. Khi đó bất kì … như thế nào, số lượng còn lại … sẽ được sử dụng sao để cho nhận được thu nhập cực đại của N-1 quá trình còn lại. Vì thu nhập tối ưu của N -1 quá trình theo định nghĩa là …. nên sự quyết định … cho quá trình thứ N đi đến thu nhập tổng cộng đối với N quá trình : …..
Phương trình truy toán là
…….
Như vậy ta đã đưa bài toán cực trị của N biến về N bài toán cực trị một biến và phương tình (1.4) gọi là phương trình truy toán của qui hoạch động. Đó là ý cơ bản của phương pháp qui hoạch động giải bài toán cực trị bằng phương pháp phương trình truy toán.
Biết ….. dựa vào phương trình truy toán (1.4) ta tìm được …., sau đó lại thay …. vào (1.4) ta tìm được …..v.v…. Cứ như vậy cho tới khi tìm được ….
Cơ sở của việc làm này là nguyên lý tối ưu tổng quát mà ta sé xét trong mục dưới đây
1.2 Các nguyên tắc cơ bản của qui hoạch động
Qui hoạch động là việc qui hoạch từng giai đoạn của quá trình nhiều giai đoạn mà trong đó mỗi giai đoạn ta chỉ tối ưu hóa một bước. Tuy nhiên khi qui hoạch một quá trình nhiều giai đoạn, ở mỗi bước ta phải lựa chọn điều khiển trên cơ sở không phải xuất phát từ lợi ích nhỏ hẹp của chính bước đó mà từ lợi ích chung của toàn bộ quá trình.
1. Nguyên tắc đánh số các giai đoạn từ dưới lên.
Đối với giai đoạn cuối có thể làm cho nó tốt nhất và không lo hậu quả. Khi đó giai đoạn này trở nên ổn định và ta có thể xét giai đoạn ở trước đó và cứ tiếp tục cho tới lúc ta đi được tới giai đoạn đầu của quá trình.
2. Nguyên tắc thông số hóa bài toán
Ở giai đoạn sát giai đoạn cuối cùng, ta chưa biết kết quả nên ta phải đặt giả thiêt cho giai đoạn này rồi ứng với giả thiết đó ta tìm điều khiển tối ưu cho giai đoạn cuối cùng. Ở các bước khác tình hình cũng xảy ra như vậy. Do đó quá trình điều khiển tối ưu sẽ phụ thuộc vào các thông số đặc trưng cho kết quả ở bước trước.
3. Nguyên tắc lồng
Lồng bài toán ban đầu vào một bài toán rộng hơn hay một họ các bài toán và do đó bài toán ban đầu là một trường hợp riêng của họ bài toán này.
Họ bài toán này nhờ có các thông số nên ta giải được. Ta sẽ thử kết quả của bài toán với các thông số khác nhau cho tới một lúc được thông số của bài toán ban đầu thì dừng lại.
4. Nguyên tắc tối ưu (Bellman)
Dáng điệu tối ưu có tính chất là: dù trạng thái ban đầu và điều khiển ban đầu có dạng như thế nào thì điều khiển tiếp theo cũng là tối ưu đối với trạng thái thu được trong kết quả tác động những điều khiển ban đầu.

Bài toán ứng dụng cho quy hoạch động - bài toán knapsack 0-1 hay bài toán cái túi xách:
Cho m là kích thước cái túi, n là số lượng đồ vật, w[i] là kích thước của đồ vật thứ i (i = 1..n), ứng với mỗi w[i] ta có v[i] là giá trị của đồ vật đó. c[i,m] sẽ là giá trị mà cái túi đạt được lớn nhất ứng với i.
c[i,m] = 0 nếu i == 0 hoặc m == 0
c[i,m] = c[i-1,m] nếu w[i] > m
c[i,w] = max(c[i-1,m] , k*v[i]+c[i-1,m-k*w[i]) với k*w[i] <= m, k >= 1