線性規(guī)劃

第一部分 單純形法
第1章 數(shù)學模型
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 單純形法(續(xù))
2.6.1 基本定理
2.6.2 退化型概念
2.6.3 單純形法步驟
2.6.4 舉例
2.7 單純形表格
習題二
第3章 改善的單純形法
3.1 數(shù)學準備
3.2 改善的單純形法
3.2.1 改善的單純形法的步驟
3.2.2 舉例
3.3 改善的單純形法表格
3.3.1 表格的介紹
3.3.2 復雜性分析
習題三
第4章 單純形法的補充
4.1 二階段法
4.2 大M法
4.3 變量有上下界約束問題
4.3.1 下界不為零的情況
4.3.2 有上界的約束
4.4 退化情形
4.4.1 退化形問題
4.4.2 出現(xiàn)循環(huán)舉例與防止循環(huán)的Bland準則
4.5 靈敏度分析
4.5.1 C有變化
4.5.2 右端項改變
4.5.3 aij改變
4.5.4 A的列向量改變
4.5.5 A的行向量改變
4.5.6 增加新變量
4.5.7 增加新約束條件
4.5.8 應用舉例
4.5.9 參數(shù)規(guī)劃
4.6 分解原理
4.6.1 分解算法
4.6.2 說明舉例
4.7 無界域問題的分解算法
4.7.1 分解原理
4.7.2 說明舉例
習題四
第5章 對偶原理與對偶單純形法
5.1 對偶問題
5.1.1 對偶問題定義
5.1.2 對偶問題的意義
5.1.3 互為對偶
5.1.4 Ax=b的情形
5.1.5 其他類型
5.2 對偶性質
5.2.1 弱對偶性質
5.2.2 強對偶性質
5.2.3 min問題的對偶解法
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 運輸問題的數(shù)學模型
6.1.1 問題的提出
6.1.2 運輸問題的特殊性
6.2 矩陣A的性質
6.3 運輸問題的求解過程
6.3.1 求初始可行解的西北角法
6.3.2 最小元素法
6.3.3 圖上作業(yè)法
6.4 ci-zi的計算，進入基的確定
6.5 退出基的確定
6.6 舉例
6.7 任務安排問題
6.7.1 任務安排與運輸問題
6.7.2 求解舉例
6.8 任務安排的匈牙利算法
6.8.1 代價矩陣
6.8.2 Knig定理
6.8.3 標志數(shù)法
6.8.4 匈牙利算法
6.8.5 匹配算法
6.9 任務安排的分支定界法
6.10 一般的任務安排問題
6.11 運輸網(wǎng)絡
6.11.1 網(wǎng)絡流
6.11.2 割切
6.11.3 Ford-Fulkerson定理
6.11.4 標號法
6.11.5 Edmonds-Karp修正算法
6.11.6 Dinic算法
習題六
第7章 內點法簡介
7.1 Klee與Minty舉例
7.2 數(shù)學準備
7.2.1 Lagrange乘數(shù)法
7.2.2 Kuhn-Tucker條件
7.2.3 垂直投影矩陣
7.2.4 最速下降法
7.2.5 牛頓法介紹
7.2.6 罰函數(shù)概念
7.2.7 中心路徑
7.3 路徑跟蹤法
7.3.1 原偶對稱型
7.3.2 KKT方程組及牛頓法
7.3.3 μ的確定,步長的確定
7.3.4 初始值和結束準則
7.3.5 算法步驟
7.3.6 收斂性的討論
7.3.7 KKT方程組的重要歸約
7.4 梯度法與仿射變換
第8章 目標規(guī)劃
8.1 問題的提出
8.2 目標規(guī)劃的幾何解釋
8.3 目標規(guī)劃的單純形表格
8.4 目標序列化方法
8.5 目標規(guī)劃的靈敏度分析
8.6 應用舉例
習題八
第9章 整數(shù)規(guī)劃
9.1 問題的提出
9.2 整數(shù)規(guī)劃的幾何意義
9.3 0-1規(guī)劃和DFS搜索法
9.3.1 窮舉法
9.3.2 DFS搜索法
9.4 0-1規(guī)劃的DFS搜索法
9.4.1 搜索策略
9.4.2 舉例
*9.5 替代約束
9.5.1 Geoffrion替代約束
9.5.2 舉例
9.6 分支定界法
9.6.1 對稱型流動推銷員問題
9.6.2 非對稱型流動推銷員問題
9.7 整數(shù)規(guī)劃的分支定界解法
9.8 分支定界法在解混合規(guī)劃上的應用
9.9 背包問題的分支定界解法
9.10 整數(shù)規(guī)劃的割平面法
9.10.1 Gomory割平面方程
9.10.2 舉例
9.11 割平面的選擇
9.12 Martin割平面法
9.13 全整數(shù)割平面法
9.13.1 全整數(shù)單純形表格
9.13.2 舉例
9.14 混合規(guī)劃的割平面法
習題九