目錄
第1章 引論
1.1引言
1.2問題的提齣
1.3標準形式與矩陣錶示法
1.4幾何解釋
習題一
第2章 單純形法
2.1凸集
2.1.1凸集概念
2.1.2可行解域與極方嚮概念
2.2凸多麵體
2.3鬆弛變量
2.3.1鬆弛變量概念
2.3.2鬆弛變量的幾何意義
2.4單純形法的理論基礎
2.4.1極值點的特性
2.4.2矩陣求逆
2.4.3可行解域無界的情況
2.4.4退化型舉例
2.5單純形法基礎
2.5.1基本公式
2.5.2退齣基的確定與進入基的選擇
2.5.3例
2.6單純形法(續)
2.6.1基本定理
2.6.2退化型概念
2.6.3單純形法步驟
2.6.4舉例
2.7單純形錶格
習題二
第3章 改善的單純形法
3.1數學準備
3.1.1改善之一:CB(B-1a)=(CB/B-1)a
3.1.2改善之二:矩陣求逆
3.2改善的單純形法
3.2.1改善單純形法步驟
3.2.2舉例
3.3改善的單純形法錶格及其分析
3.3.1改善的單純形法錶格
3.3.2改善單純形法的復雜性分析
3.4變量有上下界約束的問題
3.4.1下界不為零的情況
3.4.2有上界的情況
3.5分解原理
3.5.1問題的提齣
3.5.2分解算法
3.5.3說明舉例
3.6無界域問題的分解算法
3.6.1分解原理
3.6.2說明舉例
習題三
第4章 單純形法的若乾補充與靈敏度分析
4.1二階段法
4.2大M法
4.3退化情形
4.3.1退化形問題
4.3.2齣現循環舉例
4.4防止循環
4.4.1退齣基不唯一時的選擇辦法
4.4.2首正嚮量概念
4.4.3不齣現循環的證明
4.5靈敏度分析
4.5.1C有變化
4.5.2右端項改變
4.5.3aij改變
4.5.4A的列嚮量改變
4.5.5A的行嚮量改變
4.5.6增加新變量
4.5.7增加新約束條件
4.5.8應用舉例
4.5.9參數規劃
習題四
第5章 對偶原理與對偶單純形法
5.1對偶問題
5.1.1對偶問題定義
5.1.2對偶問題的意義
5.1.3互為對偶
5.1.4Ax=b的情形
5.1.5其他類型
5.2對偶性質
5.2.1弱對偶性質
5.2.2強對偶定理
5.2.3min問題的對偶解法
5.3影子價格
5.4對偶單純形法
5.4.1基本公式
5.4.2對偶單純形法
5.4.3舉例
5.5主偶單純形法
5.5.1問題的引入
5.5.2主偶單純形法之一
5.5.3主偶單純形法之一
習題五
第6章 運輸問題及其他
6.1運輸問題的數學模型
6.1.1問題的提齣
6.1.2運輸問題的特殊性
6.2矩陣A的性質
6.3運輸問題的求解過程
6.3.1求初始可行解的西北角法
6.3.2最小元素法
6.3.3圖上作業法
6.4Ci-zi的計算,進入基的確定
6.5退齣基的確定
6.6舉例
6.7任務安排問題
6.7.1任務安排與運輸問題
6.7.2求解舉例
6.8任務安排的匈牙利算法
6.8.1代價矩陣
6.8.2科涅格(Konig)定理
6.8.3標誌數法
6.8.4匈牙利算法
6.8.5匹配算法
6.9任務安排的分支定界法
6.10一般的任務安排問題
6.11運輸網絡
6.11.1網絡流
6.11.2割切
6.11.3福德福剋遜(Ford-Fulkers0n)定理
6.11.4標號法
6.11.5埃德濛斯-卡普(Edm0nds-Karp)修正算法
6.11.6狄尼(Dinic)算法
習題六
第7章 哈奇揚(Xaчиян)算法與卡瑪卡(Karmarkar)算法
7.1剋裏(Klee)與明特(Minty)舉例
7.2哈奇揚算法
7.2.1問題的轉化
7.2.2哈奇揚算法步驟
7.2.3算法的正確性證明的準備
7.2.4定理的證明
7.2.5嚴格不等式組
7.2.6復雜性分析
7.3卡瑪卡算法與卡瑪卡典型問題
7.3.1卡瑪卡標準型
7.3.2化為標準型的方法之一
7.3.3化為標準型的方法之二
7.3.4T0變換
7.3.5卡瑪卡算法步驟
7.3.6卡瑪卡算法的若乾基本概念
7.3.7Tk變換的若乾性質
7.3.8勢函數及卡瑪卡算法復雜性
習題七
第8章 多目標規劃
8.1問題的提齣
8.2多目標規劃的幾何解釋
8.3多目標規劃的單純形錶格
8.4多目標規劃的目標序列化方法
8.5多目標規劃的靈敏度分析
8.6應用舉例
習題八
第9章 整數規劃問題的DFS搜索法與分支定界法
9.1問題的提齣
9.2整數規劃的幾何意義
9.3可用綫性規劃求解的整數規劃問題
9.40-1規劃和DFS搜索法
9.4.1窮舉法
9.4.2DFS搜索法
9.5整數規劃的DFS搜索法
9.5.1搜索策略
9.5.2舉例
9.6替代約束
9.6.1吉阿福裏昂(Ge0ffri0n)替代約束
9.6.2舉例
9.7分支定界法介紹
9.7.1對稱型流動推銷員問題
9.7.2非對稱型流動推銷員問題
9.7.3最佳匹配問題
9.8整數規劃問題的分支定界解法
9.9分支定界法在解混閤規劃上的應用
9.10估界方法
習題九
第10章 整數規劃的割平麵法
10.1割平麵
10.1.1郭莫萊(G0mory)割平麵方程
10.1.2例
10.2割平麵的選擇
10.3馬丁(Martin)割平麵法
10.4全整數割平麵法
10.4.1全整數單純形錶格
10.4.2舉例
10.4.3確定λ的策略
10.5混閤規劃的割平麵法
習題十
第11章 奔德斯(Benders)分解算法與群的解法
11.1混閤規劃的奔德斯分解算法
11.1.1分解算法的原理
11.1.2奔德斯分解算法
11.1.3算法舉例
11.2群的解法
11.2.1群的解法原理
11.2.2舉例
11.3群的解法和最短路徑問題
11.3.1圖的構造
11.3.2求最短路徑的戴剋斯特拉(Dijkstra)算法
11.4背包問題
11.5將整數規劃歸約為背包問題
11.6背包問題的網絡解法
11.7背包問題的分支定界解法
11.8流動推銷員問題的近似解法
11.8.1最近插入法
11.8.2最小增量法
11.8.3迴路改進法
習題十一
第12章 動態規劃算法
12.1最短路徑問題
12.1.1窮舉法
12.1.2改進的算法
12.1.3復雜性分析
12.2最佳原理
12.2.1最佳原理
12.2.2最佳原理的應用舉例
12.3流動推銷員問題
12.3.1動態規劃解法
12.3.2復雜性分析
12.4任意兩點間的最短距離
12.4.1距離矩陣算法
12.4.2動態規劃算法
12.5同順序流水作業的任務安排
12.6整數規劃的動態規劃解法
12.6.1多段判決公式
12.6.2舉例
12.7背包問題的動態規劃解法
習題十二
參考文獻
· · · · · · (
收起)