現代優化計算方法

《現代優化計算方法》全書共6章，第1章介紹算法複雜性的基本概念和啓發式算法的評價方法，後5章分別介紹各個現代優化計算方法。

本書可作為數學、管理科學、計算機科學、工業工程等學科中相關優化專業的研究生教材，也可供相關專業研究人員參考。 ^[1] 

基於這種想法，本書由6章組成。第1章介紹了現代優化算法要解決的問題及它們中的共同點，並將本書各章銜接在一起。第2章、第3章、第4章和第5章分別介紹禁忌搜索算法、模擬退火算法、遺傳算法和人工神經網絡算法，這些是現代優化算法的組成。第6章提供評價算法的一種工具：拉格朗日鬆弛算法。

第1章為概論。首先介紹現代優化算法所要解決的組合優化問題。通過複雜性概念的引入，使得我們知道為什麼和在什麼情況下將現代優化算法應用到優化問題。通過鄰域和算法評價方法的介紹，使我們找出現代優化算法的一些共同點。由於有關複雜性概念的內容不易理解，因此，作者在處理這部分內容時，以多個典型組合優化問題為背景，通過對它們的一步步分析來介紹複雜性的一個個概念。為了適應不同層次的讀者，本章將複雜性概念的內容分為1．2節和1.5節兩部分。1．2節介紹了多項式時間可求得最優解的多項式問題。1.5節更進一步介紹了NP、NP-complete和NP-hard概念。對學時要求較少或非運籌學專業學生的教學，可以略去1．5節。

將第2，3，4，5這四章的內容作為一個整體，從最容易理解的局部搜索算法開始，逐步深入地介紹全局搜索的禁忌搜索算法，帶有隨機搜索的模擬退火和遺傳算法，最後，給出人工神經網絡算法。對學時要求較少或非運籌學專業學生的教學，可以略去3．2節、3．3節和4．3節中的證明。

第6章拉格朗日鬆弛算法使得本書成為一個整體。不僅要學會應用現代優化算法，還應該學會評價這些算法。對於極小化目標函數的優化問題，現代優化算法能給出一個目標值不低於最優目標值的可行解，當評價一個算法的計算效率時，可行解目標值同最優目標值一個下界的差是評價的標準之一。拉格朗日鬆弛算法則是提供最優目標值下界的工具之一。

最優化是人們在工程技術、科學研究和經濟管理的諸多領域中經常遇到的問題。結構設計要在滿足強度要求等條件下使所用材料的總重量最輕；資源分配要使各用户利用有限資源產生的總效益最大；安排運輸方案要在滿足物資需求和裝載條件下使運輸總費用最低；編制生產計劃要按照產品工藝流程和顧客需求，儘量降低人力、設備、原材料等成本使總利潤最高。可以預料，隨着科學技術尤其是計算機技術的不斷髮展，以及數學理論與方法向各門學科和各個應用領域的更廣泛、更深入的滲透，在即將到來的21世紀信息時代，最優化理論和技術必將在社會的諸多方面起着越來越大的作用。

解決實際生活中優化問題的手段大致有以下幾種：一是靠經驗的積累，憑主觀作判斷；二是做試驗選方案，比優劣定決策；三是建立數學模型，求解最優策略。雖然由於建模時要作適當簡化，可能使結果不一定非常完善，但是它基於客觀數據，求解問題簡便、靈活、經濟，而且規模可以很大(將來會越來越大)。人們還可以吸收從經驗得到的規則，用實驗來不斷校正建立的模型。隨着數學方法和計算機技術的進步，用建模和數值模擬解決優化問題這一手段，將會越來越顯示出它的效能和威力。顯然，在決策定量化、科學化的呼聲日益高漲的今天，數學建模方法的推廣應用是符合時代潮流和形勢發展需要的。

最優化理論、模型與方法所包含的內容很多，國內已出版了不少教材和專著介紹其各個分支。但是一方面，近年來發展起來的、有着廣泛應用背景的規劃模型(如隨機規劃、模糊規劃等)，以及一些已經為許多人採用、受到廣泛關注的優化算法(如模擬退火、遺傳算法等)，還缺乏詳細和系統的介紹；另一方面，一些偏重優化理論和方法的教材，其要求難以與工科學生的數學知識銜接，也缺少對於應用來説十分重要的建模過程和軟件介紹，而一些比較通俗的運籌學教材，則在加強理論基礎，適應學生將來從事科研工作需要上考慮較少。我們這套教材試圖彌補以上兩方面的缺陷，力求體現下述特點：

1．內容既包含傳統的線性規劃與非線性規劃等部分，又納入有廣泛應用前景的隨機規劃和模糊規劃；在傳統內容中，既注重典型的數學思想和方法的系統敍述，又引入豐富的建模實例。

2．數學基礎既與工科學生所學知識銜接，又考慮到研究生閲讀文獻、從事科研工作的需要，適當提高理論基礎的起點。

3．對一般教材介紹的諸多算法進行精選，配合介紹一些應用軟件，並引入近年來迅速發展的若干新算法。

本系列教材將陸續出版，首批四冊為：《線性與非線性規劃》、《網絡優化》、《現代優化計算方法》、《隨機規劃與模糊規劃》。

1．1組合最優化問題

1．2計算複雜性的概念

1．3鄰域概念

1．4啓發式算法

1．5np，np-c和np-hard概念

1．6小結

練習題

參考文獻

2．1局部搜索

2．2禁忌搜索

2．3技術問題

2．4應用實例

練習題

參考文獻

3．1模擬退火算法及模型

3．2馬爾可夫鏈

3．3時齊算法的收斂性

3．4非時齊算法收斂性簡介

3．5實現的技術問題

3．6應用案例--下料問題

練習題

參考文獻

4．1遺傳算法

4．2模板理論

4．3馬爾可夫鏈收斂分析

4．4實現的技術問題

4．5遺傳模擬退火算法

4．6應用案例--生產批量問題

練習題

參考文獻

5．1人工神經網絡的基本概念

5．2單層前向神經網絡

5．3多層前向神經網絡

5．4競爭學習神經網絡

5．5反饋型神經網絡

練習題

參考文獻

6．1基於規劃論的鬆弛方法

6．2拉格朗日鬆弛方法的理論

6．3拉格朗日鬆弛的進一步討論

6．4拉格朗日鬆弛算法

6．5拉格朗日鬆弛在能力約束單機排序問題中