動態規劃中最優化原理的思考

王偉業 路宇

摘 要：最優化原理也稱最優性原理。指解決多階段決策問題的理論。這個理論是美國的貝爾曼在1956年提出的。它原來的表述是：一個過程的最優策略具有這樣的性質，即無論其初始狀態及初始決策如何，其以后諸決策對以第一個決策所形成的狀態作為初始狀態的過程而言，必須構成最優策略。這個原理的實質是多階段決策過程具有這樣的性質，即不管過去的過程如何，只從當前的狀態和系統的最優化要求出發，作出下一步的最優決策。

關鍵詞：最優化原理 動態規劃

動態規劃一般可分為線性動規，區域動規，樹形動規，背包動規四類。動態規劃問世以來，在經濟管理、生產調度、工程技術和最優控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題，用動態規劃方法比用其它方法求解更為方便。

雖然動態規劃主要用于求解以時間劃分階段的動態過程的優化問題，但是一些與時間無關的靜態規劃（如線性規劃、非線性規劃），只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態規劃方法方便地求解。

動態規劃程序設計是對解最優化問題的一種途徑、一種方法，而不是一種特殊算法。不像搜索或數值計算那樣，具有一個標準的數學表達式和明確清晰的解題方法。動態規劃程序設計往往是針對一種最優化問題，由于各種問題的性質不同，確定最優解的條件也互不相同，因而動態規劃的設計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動態規劃算法，可以解決各類最優化問題。因此讀者在學習時，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創造性的技巧去求解。我們也可以通過對若干有代表性的問題的動態規劃算法進行分析、討論，逐漸學會并掌握這一設計方法。

動態規劃的主要難點在于理論上的設計，也就是上面4個步驟的確定，一旦設計完成，實現部分就會非常簡單。使用動態規劃求解問題，最重要的就是確定動態規劃三要素：問題的階段，每個階段的狀態以及從前一個階段轉化到后一個階段之間的遞推關系。遞推關系必須是從次小的問題開始到較大的問題之間的轉化，從這個角度來說，動態規劃往往可以用遞歸程序來實現，不過因為遞推可以充分利用前面保存的子問題的解來減少重復計算，所以對于大規模問題來說，有遞歸不可比擬的優勢，這也是動態規劃算法的核心之處。確定了動態規劃的這三要素，整個求解過程就可以用一個最優決策表來描述，最優決策表示一個二維表，其中行表示決策的階段，列表示問題狀態，表格需要填寫的數據一般對應此問題的在某個階段某個狀態下的最優值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據遞推關系，從1行1列開始，以行或者列優先的順序，依次填寫表格，最后根據整個表格的數據通過簡單的取舍或者運算求得問題的最優解。

最優化理論與算法在信息論中應用，使用最優化課程中解決非線性目標函數、線性約束函數極值問題的可行方向法中的Zoutendijk方法，結合Matlab軟件中的數值，計算工具箱對信息論中的問題進行編程分析和求解。最優化原理方法的引入，能夠從數值計算的角度給出相關定理的解釋，有助于加深對信息論中香濃定理的理解。

最優化原理的方法主要研究對象是各種有組織系統的管理問題及其生產經營活動。最優化原理的目的在于針對所研究的系統，求得一個合理運用人力、物力和財力的最佳方案，發揮和提高系統的效能及效益，最終達到系統的最優目標

無論采取哪種理論和方法，都應遵循下列基本原則：（一）局部效應服從整體效應的原則。系統局部效應與整體效應相聯系，但并不一致。有的局部優，整體也優，有的局部優，整體不優，有的局部不優而整體優。在處理局部與整體關系時，必須把整個優化作為主要目標。（二）堅持系統多級優化原則。從目標、方案、模型、評價到決策，每個因素都存在優化問題。特別是對系統運行過程的多階段的逐級優化，是系統整體優化的保證。（三）堅持優化的絕對性與相對性結合的原則。系統“達優”本身是絕對的，但優化的程度又是相對的。在進行可行性分析時，能實現理想的優化最好；但考慮各種條件，盡管不理想，但能實現“滿意性”優化也可。滿意性原則是可行、靈活、省力的方法。新聞傳播系統的整體優化是從報道方針、計劃、采編、發行、群眾工作、經營管理、隊伍素質、技術設備等各層次、各階段的優化而實現的。其中某一層次、階段的優化，如采編優化，不等于新聞系統整體優化。如何建立新聞傳播系統的整體優化模型，特別是數學模型，是一項有待開發，具有重大價值的科研項目。1B431A6E-3239-4E5A-9FC0-70D2AC306C67