3 5動態規劃50年代初 由美國數學家Bellman提出 將系統運行過程分為若干相繼的階段 而在每個階段都要做出決策的過程 就叫做多段決策過程 多段決策過程的每一段的結束狀態 就是下一段的初始狀態 動態規劃是研究多段決策而提出來的一種數學方法 它的中心思想是所謂的 最優性原理 這個原理歸結為一個基本遞推關系式 從整個過程的終點出發 由后向前 使過程連續地轉移 一步一步地推到始點 找到最優解 系統動態最優化習慣稱為最優控制 它與系統靜態最優化的區別在于其自變量是時間的函數 實質上屬于泛函極值的范疇 例求從A到E的最短路徑 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f5 E 0 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D1 5 f5 E 0 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f4 D1 5 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C1 8 f4 D1 5 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C2 7 f4 D1 5 f3 C1 8 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f3 C1 8 f3 C2 7 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B1 20 f3 C2 7 f3 C1 8 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B2 14 f3 C2 7 f3 C1 8 f2 B1 21 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B3 19 f3 C2 7 f3 C1 8 f2 B1 21 f2 B2 14 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B3 19 f3 C2 7 f3 C1 8 f1 A 19 f2 B2 14 f2 B1 21 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4 D2 2 f5 E 0 f3 C3 12 f4 D1 5 f2 B3 19 f3 C2 7 f3 C1 8 f1 A 19 f2 B2 14 f2 B1 21 狀態最優