篇運籌學基礎

第1章單純形法

1.1本章內容

1.2線性規劃問題及其標準數學模型

1.2.1什麼是線性規劃問題

1.2.2線性規劃問題的標準形式

1.3用單純形法解決線性規劃問題

1.3.1線性規劃問題中的概念和原理

1.3.2單純形法的原理

1.3.3兩階段法求解一般的線性規劃問題

1.4單純形法的MATLAB實現

1.4.1MATLAB知識儲備

1.4.2S函數

1.4.3主程序

1.4.4直接用優化工具箱解線性規劃問題

1.5利用linprog命令解決投資問題

1.6單純形法的計算復雜度淺析

1.7本章小結

第2章對偶單純形法

2.1本章內容

2.2對偶問題的提出

2.2.1拉格朗日乘數法

2.2.2對偶問題的生成

2.3對偶問題的性質

2.4對偶單純形法

2.4.1單純形法的矩陣表達

2.4.2對偶單純形法的基本原理

2.4.3對偶單純形法的計算步驟

2.5對偶單純形法的MATLAB實現

2.6凡卡引理與資產定價

2.6.1凡卡引理

2.6.2資產定價

第3章靈敏度分析

3.1本章內容

3.2靈敏度分析的概念和思路

3.2.1靈敏度分析的概念

3.2.2靈敏度分析的實現思路

3.3資源向量b的變化分析與全局依賴

3.3.1資源向量b的變化分析原理

3.3.2資源向量b的全局依賴

3.3.3資源向量b靈敏度分析的MATLAB實現

3.3.4b對目標函數值和解的影響

3.4價值向量c的變化分析與全局依賴

3.4.1價值向量c的變化分析原理

3.4.2價值向量c的全局依賴

3.4.3價值向量c變化的MATLAB實現

3.4.4c對目標函數值和解的影響

3.5增加變量的分析

3.5.1增加變量的分析原理

3.5.2增加變量分析的MATLAB實現

3.6改變約束繫數矩陣的分析

3.6.1改變約束繫數矩陣的分析原理

3.6.2改變約束繫數矩陣分析的MATLAB實現

3.6.3改變A的影響

3.7增加約束條件的分析

3.7.1增加約束條件的分析原理

3.7.2增加約束條件分析的MATLAB實現

第4章內點法

4.1本章內容

4.2總述

4.3仿射尺度算法

4.3.1仿射尺度算法的原理

4.3.2仿射尺度算法的實現步驟

4.3.3仿射尺度算法的MATLAB實現

4.3.4初始值

4.3.5仿射尺度算法的計算復雜度淺析

4.4勢函數下降算法

4.4.1勢函數下降算法的原理

4.4.2勢函數下降算法的實現步驟

4.4.3勢函數下降算法的MATLAB實現

4.4.4初始值

4.4.5勢函數下降算法的計算復雜度

4.5原始路徑跟蹤算法

4.5.1原始路徑跟蹤算法的原理

4.5.2原始路徑跟蹤算法的實現步驟

4.5.3原始路徑跟蹤算法的MATLAB實現

4.5.4初始值

4.5.5原始路徑跟蹤算法的計算復雜度

4.6原始對偶路徑跟蹤算法

4.6.1用牛頓方法尋找非線性方程組的根

4.6.2用牛頓方法解決線性規劃問題的原理

4.6.3原始對偶路徑跟蹤算法的實現步驟

4.6.4原始對偶算法的MATLAB實現

4.6.5自對偶方法

4.6.6原始對偶路徑跟蹤算法計算復雜度

第5章整數規劃

5.1本章內容

5.2建模方法

5.2選擇

5.2.2強制約束

5.2.3變量之間的關繫

5.2.4析取約束

5.2.5值的約束範圍

5.2.6分段線性成本函數

5.3整數規劃的例子

5.4問題的公式化

5.5割平面法

5.6Gomory割平面法的MATLAB實現

5.7分支定界法

5.8分支定界法的MATLAB實現

5.9整數規劃的解法

5.1001整數規劃的MATLAB實現

5.11整數規劃解決旅行商問題的MATLAB實例

第6章圖與網絡流

6.1本章內容

6.2圖

6.2.1圖的概念

6.2.2有向圖

6.2.3頂點的次

6.2.4子圖

6.2.5連通圖

6.2.6樹

6.2.7生成樹

6.3網絡流問題的求解

6.3.1網絡流解的定義

6.3.2網絡流問題的變式

6.4短路徑問題

6.4.1公式化

6.4.2Bellman等式

6.4.3BellmanFord算法

6.4.4Dijkstra算法

6.4.5Dijkstra算法的MATLAB實現

6.4.6Floyd算法

6.4.7Floyd算法的MATLAB實現

6.5流問題

6.5.1標號法

6.5.2流小割定理

6.5.3FordFulkerson算法的MATLAB實現

6.6小費用流問題

6.7小生成樹問題

6.7.1算法1（Kruskal算法）

6.7.2Kruskal算法的MATLAB實現

6.7.3算法2（破圈法）

6.7.4根樹及其應用

第7章線性規劃的復雜度和橢球法

7.1本章內容

7.2有效算法及其復雜度

7.3橢球法背後的關鍵幾何結果

7.4線性規劃的多項式時間算法

7.4.1橢球法

7.4.2算法分析

第二篇全局優化算法

第8章遺傳算法

8.1本章內容

8.2遺傳算法的原理

8.3遺傳算法的步驟

8.3.1初始參數

8.3.2染色體編碼

8.3.3適應度函數

8.3.4約束函數的處理

8.3.5遺傳算法算子

8.3.6搜索終止條件

8.4遺傳算法實例

8.5全局和局部極小值

8.6遺傳算法的特點

第9章模擬退火算法

9.1本章內容

9.2退火過程的物理原理

9.2.1固定溫度下粒子的轉移原則

9.2.2溫度對粒子能量分布的影響

9.2.3能量與粒子分布的關繫

9.3模擬退火的模型和步驟

9.3.1參數的設定

9.3.2操作要求

9.3.3模擬退火的步驟

9.4模擬退火的MATLAB實現

9.4.1MATLAB實現模擬退火算法的代碼

9.4.2一個簡單的應用

9.5用模擬退火算法解決TSP問題

9.5.1TSP問題概述與分析

9.5.2能量函數與狀態轉移函數

9.5.3sa函數的使用

9.5.4設定上的一些問題

9.6模擬退火函數simulannealbnd

9.6.1基本用法

9.6.2options選項

9.6.3problem結構

9.6.4應用實例

第10章粒子群優化算法

10.1本章內容

10.2粒子群優化算法的原理

10.2.1種群的信息共享

10.2.2粒子群優化算法的數學表達

10.3粒子群優化算法的MATLAB實現

10.3.1初始參數

10.3.2MATLAB實現

10.3.3一個簡單的例子

10.4粒子群優化算法的進一步說明

10.4.1為什麼要重復多次執行算法

10.4.2初始參數如何設定

10.5粒子群優化算法函數particleswarm

10.5.1基本用法

10.5.2應用實例

10.5.3options的使用

10.6粒子群優化算法的收斂機制及優點和缺點討論

第11章多目標優化算法

11.1本章內容

11.2多目標優化算法概況

11.3Pareto解

11.4Gamultiobj算法

11.4.1算法迭代步驟

11.4.2迭代停止條件

11.5Gamultiobj算法的MATLAB實現

11.6多目標優化算法的例子

11.6.1簡單的多目標問題

11.6.2具有線性限制條件的多目標問題

11.6.3具有上下界限制的多目標問題

11.7Paretosearch算法

11.8Paretosearch和Gamultiobj算法的比較

第三篇運籌學應用案例

第12章債券優化問題

12.1問題的描述

12.2從Excel中提取數據

12.2.1導入債券價格

12.2.2導入現金流

12.3化問題的求解

12.3.1允許債券單個購買時的求解

12.3.2以千支為單位進行購買時的求解

第13章水電站大壩優化

13.1載入數據並定義常值

13.2定義目標函數

13.2.1計算總收益及其Hessian矩陣

13.2.2創建目標函數

13.3限制條件

13.4小化目標函數並輸出結果

參考文獻

運籌學作為一門現代科學，是在第二次世界大戰期間首先在英國和美國發展起來的，但運籌學的思想在中國早已應用於實際，“運籌帷幄之中，決勝千裡之外”就體現了運籌學的思想與作用。運籌學以應用數學為基礎，利用數學模型和算法尋找復雜問題中的或近似的解答，對學習、工作、生活都很有幫助。隨著科學技術和生產的發展，運籌學已被廣泛應用於多個領域，發揮著越來越重要的作用。
關於運籌學的教材已經有一些，國內的教材更容易理解，國外的教材理論體繫更強。所以本書綜合國內教材邏輯清晰、更容易理解的優點，同時吸納國外教材中的部分理論，使運籌學的理論體繫更加完善。運籌學涉及大量的算法推演和計算，部分讀者可能會感覺枯燥，喪失學習的興趣。其實，隨著計算機軟件的發展，很多計算工作可以交由軟件代勞，這樣讀者隻需輕松理解概念，理解運籌學算法的邏輯，然後直接通過軟件得到計算結果即可。在常用的處理運籌學問題的軟件中，MATLAB包含的內容全，代碼容易理解，且拓展性強，比較有利於學習和後期的應用，所以本書的案例采用MATLAB實現。讀者可以通過代碼快速實現運籌學的應用，同時可以通過分析代碼理解運籌學實現的邏輯，也更有利於理論的學習和理解。
全書內容分三篇，篇為運籌學基礎，包括第1~7章； 第二篇為全局優化算法，包括第8~11章； 第三篇為運籌學應用案例，包括第12章和第13章。
第1章介紹線性規劃基本的解法——單純形法。在原理的敘述上，盡量避免冗長的算式，采用線性代數的方式揭示該算法工作的本質。在本章的後給出了單純形法的實現代碼，可以幫助讀者深入理解單純形法，以及單純形法的數學語言與計算機語言的轉換方式。
第2章介紹對偶單純形法。在對偶單純形法的學習中，容易遇到的問題是知其然而不知其所以然，為此本章從讀者熟悉的拉格朗日乘數法開始講解，解釋為什麼需要對偶單純形法，並對原問題和對偶問題的有關性質用代數證明。值得一提的是，我們介紹如何利用對偶單純形法證明凡卡引理，由此引出資產定價中重要的無套利原理。
第3章首先介紹何為靈敏度分析，接下來將其具體應用到線性規劃問題中。靈敏度分析是衡量一個模型的重要準則，求解小體量的線性規劃問題可能不足以看到它的優越性，但這種思路是應該掌握的。
第4章內點法的內容在當前國內運籌學教材中比較少見。作為計算數學常用的方法，掌握內點法對於有志於進行算法學習的讀者是必要的。在可行域內尋找勢函數、障礙函數的設置，內點法都是十分有代表性、值得深入理解的方法。本章涉及豐富的代數證明，需要讀者有一定的線性代數基礎。

第5章介紹整數規劃方法，包括割平面法、分支定界法和01整數規劃，並針對每種算法，利用相關例子和具體代碼演示。對於實際案例，很多優化問題的變量往往存在整數限制，所以整數規劃的各種方法都具有實際意義。基於整數規劃算法的應用意義，本章在模型建立階段具體介紹模型的選擇、限制條件的轉換、整數規劃模型的變式，將各種情況的一般問題歸結為容易解決的數學形式。本章的後介紹利用整數規劃解決問題的MATLAB實例，幫助讀者理解整數規劃的應用場景和具體應用過程。
第6章介紹圖與網絡流問題，包括幾種經典的網絡流問題，即短路徑問題、流問題、小費用流問題和小生成樹問題的解決方法。標記法等人工計算方法和較為復雜的借助程序的算法並重，針對不同問題都給出了較為簡便的優化算法。另外，引入了一些網絡流問題變式的形成過程和BellmanFord算法，豐富網絡流問題的公式化和短路徑問題的解決方案。
第7章介紹線性規劃的復雜度和橢球法。本章著眼於線性規劃的新方向，這一方向強調幾何方法，並引進非線性規劃的技巧，介紹研究橢球法的目的，即增強算法有效性及幾何基礎知識。解釋橢球法的思想旨在為讀者解決線性規劃問題提供新的思路，為算法有效性的改進提供可能性，同時提示讀者在學習、研究規劃算法時需注意對算法的計算復雜度有所考查。
第8章介紹遺傳算法。遺傳算法是啟發式算法中為經典的一種算法，是根據遺傳進化過程而設計的算法，也是全局優化算法中適應非常廣的著名的方法之一。本章詳細介紹遺傳算法的原理、步驟和MATLAB實現過程。
第9章介紹模擬退火算法，也是全局優化算法中比較經典的算法，其有趣的過程是基於固體退火的原理而設計。本章介紹模擬退火算法的原理、參數設置的方法、旅行商問題的求解實例以及MATLAB求解器的使用方法。
第10章介紹粒子群優化算法。其算法原理是鳥群采用信息共享的機制進行覓食，也是比較有趣的全局優化算法。本章除了介紹算法的原理、實現過程外，還介紹相關的使用經驗，以及與其他全局優化算法在收斂性方面的比較。
第11章介紹多目標優化算法。重點介紹多目標優化的機理、算法步驟和應用實例，豐富了運籌學的內容。
第12章介紹經典運籌學在金融行業的綜合應用案例，使用的是線性規劃方法，並分別介紹是否有整數約束的兩種情況下的求解過程。
第13章介紹工程上的水電站大壩優化的綜合應用案例，使用非線性規劃和二次規劃，給出詳細的工程背景介紹及實現過程。
後，感謝清華大學出版社盛東亮和鐘志芳老師一直以來的支持和鼓勵，幫助我們順利完成書稿！
由於作者水平有限，書中疏漏之處在所難免，在此，誠懇地期待廣大讀者批評指正，我將在科學與技術的路上與大家互勉共進！

卓金武2022年10月