Mở đầu Quy hoạch động là một phương pháp quy hoạch toán học nhằm tìm lời giải tối ưu của quá trình nhiều bước (hoặc nhiều giai đoạn). Tính từ "động" ở đây nhằm nhấn mạnh vai trò thời gian và sự xuất hiện các dãy quyết định trong quá trình giải bài toán, cũng như thứ tự các phép toán có ý nghĩa quan trọng. Quá trình khảo sát được chia thành nhiều bước, ở mỗi bước ta sử dụng một quyết định. Quyết định ở bước trước có thể điều khiển quá trình ở bước sau.
Như vậy, quy hoạch động tạo nên một dãy quyết định. Dãy quyết định đó gọi là sách lược (hoặc có khi là chiến lược). Sách lược thỏa mãn mục tiêu quy định gọi là sách lược tối ưu. Chỉ tiêu tối ưu phải thể hiện đối với toàn bộ quá trình nhiều bước.
Sau đây để chuẩn bị tìm hiểu nội dung cơ bản của phương pháp quy hoạch động ta khảo sát một ví dụ về quá trình điều khiển nhiều bước. Giả thiết cần tìm một sách lược tối ưu để phân phối nguồn vốn ban đầu X cho một hệ thống k xí nghiệp hoạt động trong n năm sao cho lợi nhuận thu được từ k xí nghiệp đó sau n năm là cực đại. Ở đây, nguồn vốn X có thể là nguồn vật tư, sức lao động, công suất đặt của máy móc. Ngoài ra, bài toán có thể xây dựng theo những mục tiêu khác như chi phí về nhiên liệu cực tiểu, hiệu quả tổng về lao động là cực đại.
Sách lược tối ưu ở đây là bộ giá trị nguồn vốn đầu tư cho từng nhà máy ở mỗi năm sao cho lợi nhuận tổng sau n năm là cực đại. Giả thiết gọi Xj(i) là giá trị nguồn vốn đầu tư cho xí nghiệp i ở đầu năm j, trong đó: i = 1, 2,. , n, ngoài ra thỏa mãn điều kiện về cân bằng nguồn vốn ở mỗi năm., n ; (7-1) Trong đó: Xj - Là nguồn vốn tổng còn lại, đặt vào năm j cho k xí nghiệp. Lợi nhuận tổng của k xí nghiệp sau n năm ký hiệu là W, giá trị của W phụ thuộc vào nguồn vốn ban đầu X và số năm hoạt động n.
Có thể biểu diễn W là hàm của các giá trị Xj(i)., n ; (7-4) 99 X (j i ) 0 ; (7-5) Trong đó: biểu thức (7-3) có thể biểu diễn bằng tổng lợi nhuận của n năm, nghĩa là: k W ( X , n) Wj ( X j ) ; (7-6) t 1 Trong đó: Wj - Là lợi nhuận của k xí nghiệp năm thứ j. Như vậy, hàm mục tiêu W(X,n) có dạng một tổng, đây là một dạng thuận lợi khi sử dụng phương pháp quy hoạch động. Ở đây, giả thiết rằng nguồn vốn X đưa vào năm đầu tiên cho k xí nghiệp và hàng năm không được bổ sung. Không những thế lượng nguồn vốn của mỗi xí nghiệp qua từng năm đều bị hao hụt do sử dụng để sản xuất sinh lợi nhuận, nghĩa là đối với xí nghiệp i có: X1(i) > X2(i) >.
Ngoài ra, cần đặc biệt lưu ý là lợi nhuận của k xí nghiệp phải đạt giá trị cực đại sau n năm, mà không phải chỉ xét từng năm riêng rẽ. Bài toán xác định sách lược tối ưu phân phối nguồn vốn X cho k xí nghiệp sản xuất trong n năm trên đây có thể giải quyết theo 2 hướng: + Hướng thứ nhất: Xác định đồng thời bộ giá trị {Xj(i)} để hàm lợi nhuận W(W1, W2, ., Wn) đạt giá trị cực đại trong không gian n chiều. Trong trường hợp n nhỏ, các hàm Wj là giải tích, khả vi. Bài toán có thể giải được nhờ những phép tính vi, tích phân.
Khi n lớn (chẳng hạn n = 10) bài toán đã trở nên rất phức tạp. + Hướng thứ hai: Giải quyết bài toán trên đây theo từng bước. Hướng này cho thuật toán đơn giản hơn, đặc biệt trong trường hợp số bước n (số giai đoạn, số năm) là lớn. Hướng này thể hiện nội dung tinh thần phương pháp quy hoạch động: Việc tối ưu hóa được thực hiện dần từng bước, nhưng phải đảm bảo nhận được lời giải tối ưu cho cả n bước.
Đó là một đặc điểm quan trọng về nguyên lý tối ưu của quy hoạch động, nghĩa là trong quá trình tìm lời giải không được phép nhìn cục bộ, tìm tối ưu riêng rẽ cho từng bước mà phải nhìn rộng ra những bước sau, vì trong nhiều trường hợp một quyết định đem lại lợi nhuận cực đại riêng rẽ cho bước này có thể dẫn đến hậu quả tai hại cho bước sau. Chẳng hạn trong sách lược quản lý các xí nghiệp nêu trên nếu chỉ nhìn cục bộ trong một năm thì để đạt được lợi nhuận tối đa, ta đầu tư toàn bộ nguồn vốn X cho xí nghiệp nào mà sản xuất có nhiều lợi nhuận nhất mặc dù sau năm đó thiết bị hư hỏng nhiều gây thiệt hại sản xuất cho những năm sau. Theo tinh thần của phương pháp quy hoạch động nêu trên, ta thấy ở mỗi bước đều phải chọn quyết định sao cho dãy quyết định còn lại phải tạo thành một sách lược tối ưu. Đó chính là nguyên lý tối ưu của quy hoạch động, nguyên lý đó còn có thể phát 100 biểu như sau: "Một bộ phận của sách lược tối ưu cũng là một sách lược tối ưu".
Điều đó phản ánh quan điểm hệ thống khi xét tối ưu theo từng bước như đã trình bày. Tuy nhiên, có một bước mà khi làm tối ưu ta không cần quan tâm đến tương lai, đó là bước cuối cùng (bước thứ n). Vì vậy, quá trình quy hoạch động được tiến hành theo trình tự ngược: Từ bước cuối cùng lên bước đầu tiên. Trước hết, ta quy hoạch cho bước cuối cùng.
Nhưng khi đó chưa biết kết cục của bước trước đó, nghĩa là chưa biết bước (n - 1) kết thúc ra sao, chẳng hạn trong ví dụ về quản lý xí nghiệp, ta chưa biết năm thứ (n - 1) nguồn vốn còn lại bao nhiêu, lợi nhuận đã đạt được là bao nhiêu. Vì vậy, cách làm của quy hoạch động là tìm lời giải tối ưu ở bước n ứng với những phương án kết thúc khác nhau ở bước (n - 1). Lời giải đó được gọi là lời giải tối ưu có điều kiện ở bước n nhằm đạt cực trị hàm mục tiêu ở bước n (và không quan tâm đến trạng thái của hệ sau bước n). Tiếp tục phần xác định lời giải tối ưu có điều kiện ở bước (n - 1) ứng với mọi phương án kết thúc có thể của bước (n - 2) sao cho hàm mục tiêu đạt cực trị trong cả 2 bước cuối (bước n - 1 và n).
Tiếp theo khảo sát như vậy đến bước đầu tiên. Ở mỗi bước ta tìm được lời giải tối ưu có điều kiện đảm bảo cho cả dãy quyết định tiếp theo đến bước n là tối ưu. Thủ tục đó phản ánh nguyên lý tối ưu đã trình bày. Sau khi thực hiện xong trình tự ngược xác định được lời giải (quyết định) tối ưu có điều kiện ở mỗi bước, căn cứ vào mỗi trạng thái ban đầu cho của bài toán, ta tiến hành trình tự từ bước 1 đến bước n và xác định dãy quyết định tối ưu.
Về mặt toán học, nhờ việc chuyển nghiên cứu quá trình n về từng bước, phương pháp quy hoạch động đã làm giảm thứ nguyên của bài toán, tạo thuận lợi để giải. Ngoài ra, nhờ những thủ tục truy chứng mang tính chất chương trình hóa nên phương pháp quy hoạch động dễ dàng thực hiện trên máy vi tính điện tử số. Ở đây cần chú ý rằng, việc mô tả n giai đoạn (trong thời gian) của quá trình chỉ là quy ước, cũng có thể quan niệm gồm n đối tượng khảo sát trong một giai đoạn thời gian hoặc tổng quát là hệ gồm k đối tượng hoạt động trong n giai đoạn thời gian. Thành lập phương trình phiếm hàm BELLMAN Xét bài toán phân phối nguồn vốn như sau: Giả thiết ta cần đầu tư nguồn vốn ban đầu X1 vào một xí nghiệp để sản xuất 2 mặt hàng A, B.
Quá trình khảo sát là n năm. Vào đầu năm thứ nhất nguồn vốn tổng X1 được phân làm 2 phần: x1 để sản xuất mặt hàng A và (X1-x1) để sản xuất mặt hàng B. Sau năm đầu mặt hàng A mang lại cho xí nghiệp một lợi nhuận theo quan hệ g(x1), mặt hàng B mang lợi nhuận h(X1-x1). Để sản xuất mặt hàng, nguồn vốn đều bị hao hụt.
Giả thiết sau năm đầu sản xuất mặt hàng A, nguồn vốn x1 còn: x2 = a. x1, trong đó: 0 < a < 1; Đối với mặt hàng B nguồn vốn còn: (X2-x2) = b(X1-x1), trong đó 0 < b < 1; 101 Nguồn vốn x2 và (X2-x2) tiếp tục đầu tư vào năm thứ 2 để sản xuất mặt hàng A và B. Quá trình tiếp diễn trong n năm. Giá trị ban đầu X1 cũng như số năm n đã biết.
Do sự khác nhau đã biết giữa các giá trị đã biết g(x1), h(X1-x1), a, b nên xuất hiện yêu cầu tìm sự phân phối tối ưu nguồn vốn X1 trong từng năm sao cho tổng lợi nhuận của xí nghiệp sau n năm là cực đại. Cách đặt bài toán theo phương pháp cổ điển Bài toán phân phối nguồn vốn trên đây có thể phát biểu một cách cổ điển như sau: Cần xác định các giá trị x1, x2,. , xn là lượng nguồn vốn đầu tư để sản xuất mặt hàng A ở năm thứ nhất, thứ hai. thứ n, sao cho tổng lợi nhuận của xí nghiệp sau khi sản xuất 2 mặt hàng A và B sau n năm là cực đại.
(7-10) X n ax n b( X n1 x n1 ) Bài toán chuyển thành yêu cầu xác định điểm cực đại của hàm W(x1, x2,. , xn) trong không gian n chiều với ràng buộc dạng (7-9) và (7-10). Trong trường hợp n nhỏ hơn lời giải có thể nhận được bằng phép tính vi phân. Tuy nhiên, cần thận trọng về một số trường hợp cực đại nằm ở biên của ràng buộc, ngoài ra n lớn, chẳng hạn n 10, bài toán trở nên rất phức tạp.
Không những thế, cách giải bài toán như vậy cho quá nhiều thông tin không cần thiết, vì đã biết X1 và n chỉ cần xác định x1 như là hàm của X1 và n, như vậy bài toán được giải hoàn toàn, và suy ra x2,. Theo ý đó, ta có thể đặt bài toán một cách mới, theo tinh thần quy hoạch động.