Quy hoạch động

Phương pháp quy hoạch động
Các bước thực hiện
Hạn chế của quy hoạch động
Một vài ví dụ

Một số bài toán tiêu biểu
(Phát biểu, phân tích thuật toán và tổ chức dữ liệu, chương trình)

Các bài tập luyện tập
Đề bài
Hướng dẫn

Các đề tự giải










quy họach động

Phương pháp quy hoạch động
Phương pháp quy hoạch động cùng nguyên lý tối ưu được nhà toán học Mỹ R.Bellman đề xuất vào những năm 50 của thế kỷ 20. Phương pháp này đã được áp dụng để giải hàng loạt bài toán thực tế trong các quá trình kỹ thuật công nghệ, tổ chức sản xuất, kế hoạch hoá kinh tế... Tuy nhiên cần lưu ý rằng có một số bài toán mà cách giải bằng quy hoạch động tỏ ra không thích hợp.
Trong thực tế, ta thường gặp một số bài toán tối ưu loại sau: Có một đại lượng f hình thành trong một quá trình gồm nhiều giai đoạn và ta chỉ quan tâm đến kết quả cuối cùng là trị của f phải lớn nhất hoặc nhỏ nhất, ta gọi chung là giá trị tối ưu của f. Giá trị của f phụ thuộc vào những đại lượng xuất hiện trong bài toán mà mỗi bộ giá trị của chúng được gọi là một trạng thái của hệ thống và cũng phụ thuộc vào cách thức đạt được giá trị f trong từng giai đoạn mà mỗi cách thức được gọi là một điều khiển. Đại lượng f thường được gọi là hàm mục tiêu và quá trình đạt được giá trị tối ưu của f được gọi là quá trình điều khiển tối ưu.
Bellman phát biểu nguyên lý tối ưu (cũng còn gọi là nguyên lý Bellman) như sau: " Với mỗi quá trình điều khiển tối ưu, đối với trạng thái bắt đầu A0, nếu giữa chừng ta đi đến một trạng thái A nào đó thì phần quá trình đó kể từ trạng thái A xem như trạng thái bắt đầu cũng là tối ưu."
Chú ý rằng nguyên lý này được thừa nhận và không chứng minh.
Phương pháp tìm điều khiển tối ưu theo nguyên lý Bellman thường được gọi là quy hoạch động. Thuật ngữ này nói lên được thực chất của quá trình điều khiển là động: có thể trong một số bước đầu tiên lựa chọn điều khiển tối ưu dường như không tốt nhưng tựu chung cả quá trình lại là tốt nhất.
Ta có thể giải thích ý này qua bài toán sau:
Cho một dãy N số nguyên A1, A2, ..., AN. Hãy tìm cách xoá đi một số ít nhất số hạng để dãy còn lại là đơn điệu hay tương đương hãy chọn một số nhiều nhất các số hạng sao cho dãy B gồm các số hạng đó theo trình tự xuất hiện trong dãy A là đơn điệu.
Quá trình chọn dãy B được điều khiển qua N giai đoạn để đạt được mục tiêu là số lượng số hạng của dãy B là nhiều nhất, điều khiển ở giai đoạn i thể hiện việc chọn hay không chọn Ai vào dãy B.
Giả sử dãy đã cho là 1 8 10 2 4 6 7. Nếu ta chọn lần lượt 1, 8, 10 thì chỉ chọn đư