最最佳化計算機原理與算法程式設計

內容簡介

最最佳化方法是一門古老而又年青的學科。這門學科的源頭可以追溯到法國數學家拉

格朗日關於一個函式在一組等式約束條件下的極值問題。伴隨著工業、軍事技術和管理

決策科學的發展，這門學科也在不斷豐富發展它的內涵，衍生出組合最佳化，線性規劃，非線

性規劃，動態規劃，最優控制等分枝。拉格朗日乘子法則、庫恩塔克條件、龐特里雅金極大

值原理、貝爾曼最最佳化方程，奠定了最佳化理論研究發展的里程碑。這些經典的最佳化理論著

重描述了最優解的特徵。但是，直到有了高速計算機，人們才能夠對各類較大規模的最佳化

問題利用計算機實施求解，使最最佳化方法成為工程設計、決策管理的一種實用工具。

幾乎所有類型的最佳化問題都可概括為這樣的數學模型:給定一個集合(稱為可行集)

和該集合上定義的實值函式(稱為目標函式)，要計算函式在集合上的極值。通常，人們按

照可行集的性質對最佳化問題進行分類:如果可行集中的元素是有限的，則歸結為“組合優

化”或“網路規劃”，如圖論中最短路徑、最小費用最大流、最大權匹配等;如果可行集是有

限維空間中的一個連續子集，則歸結為線性或非線性規劃問題;如果可行集中的元素是依

賴於時間的決策序列，則歸結為“動態規劃”;如果可行集是無窮維空間中的連續子集(集

合中的元素是有限維空間中的一條曲線，由一組常微分方程描述，而目標函式為一定積

分)，則歸結為“最優控制問題”。當然，這樣的劃分不是絕對的，不論是描述問題或是計算

求解。這些分支都有一定的聯繫。網路規劃的許多問題都可表示為線性規劃;而當今流行

的“內點算法”則用非線性規劃的方法來求解線性規劃。最優控制中的許多算決都可以在

非線性規劃中找到它們的影子。

一般說來，各最佳化分支有其相應的套用領域〔但不是絕對的)。線性規劃、網路規劃、

動態規劃更多地用於管理與決策科學;非線性規劃更多地用於工程最佳化設計;最優控制常

用於控制工程。作為一本主要面向工程類研究生的教材，囿於40學時的教學時數，《最優

化計算原理與算法程式設計》主要介紹了非線性規劃的理論和算法，並扼要地介紹了動態

規劃的基本原理以及最優控制問題的數值方法。

非線性規劃是在一組等式和不等式約束條件下，求一個函式的極值問題。t}si年，

庫恩{ H . } , I}uhn)和塔克(A . W . Tt}}ker)等人提出了非線性規劃的最優性條件，為其發展奠

定了埋論基礎。隨著計算機的發展和套用，各種非線性規划算法應運而生。最著名的算

法包括)rJFP { Iaavidon-Fletcher-Powell)和BFGS { Bmgdew-Fietrher-faaldfarh-}hanno)無約束變

基本介紹