線性規(guī)劃

第一部分 單純形法
第1章 數(shù)學(xué)模型
1.1 引言
1.2 問題的提出
1.3 標(biāo)準(zhǔn)形式與矩陣表示
1.4 幾何解釋
習(xí)題一
第2章 單純形法
2.1 凸集
2.1.1 凸集概念
2.1.2 可行解域與極方向概念
2.2 凸多面體
2.3 松弛變量
2.3.1 松弛變量概念
2.3.2 松弛變量的幾何意義
2.4 單純形法的理論基礎(chǔ)
2.4.1 極值點(diǎn)的特性
2.4.2 矩陣求逆
2.4.3 可行解域無界的情況
2.4.4 退化型舉例
2.5 單純形法基礎(chǔ)
2.5.1 基本公式
2.5.2 退出基的確定與進(jìn)入基的選擇
2.5.3 舉例
2.6 單純形法(續(xù))
2.6.1 基本定理
2.6.2 退化型概念
2.6.3 單純形法步驟
2.6.4 舉例
2.7 單純形表格
習(xí)題二
第3章 改善的單純形法
3.1 數(shù)學(xué)準(zhǔn)備
3.2 改善的單純形法
3.2.1 改善的單純形法的步驟
3.2.2 舉例
3.3 改善的單純形法表格
3.3.1 表格的介紹
3.3.2 復(fù)雜性分析
習(xí)題三
第4章 單純形法的補(bǔ)充
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準(zhǔn)則
4.5 靈敏度分析
4.5.1 C有變化
4.5.2 右端項(xiàng)改變
4.5.3 aij改變
4.5.4 A的列向量改變
4.5.5 A的行向量改變
4.5.6 增加新變量
4.5.7 增加新約束條件
4.5.8 應(yīng)用舉例
4.5.9 參數(shù)規(guī)劃
4.6 分解原理
4.6.1 分解算法
4.6.2 說明舉例
4.7 無界域問題的分解算法
4.7.1 分解原理
4.7.2 說明舉例
習(xí)題四
第5章 對(duì)偶原理與對(duì)偶單純形法
5.1 對(duì)偶問題
5.1.1 對(duì)偶問題定義
5.1.2 對(duì)偶問題的意義
5.1.3 互為對(duì)偶
5.1.4 Ax=b的情形
5.1.5 其他類型
5.2 對(duì)偶性質(zhì)
5.2.1 弱對(duì)偶性質(zhì)
5.2.2 強(qiáng)對(duì)偶性質(zhì)
5.2.3 min問題的對(duì)偶解法
5.3 影子價(jià)格
5.4 對(duì)偶單純形法
5.4.1 基本公式
5.4.2 對(duì)偶單純形法
5.4.3 舉例
5.5 原偶單純形法
5.5.1 問題的引入
5.5.2 原偶單純形法之一
5.5.3 原偶單純形法之二
習(xí)題五
第二部分 幾個(gè)專題
*第6章 運(yùn)輸問題及其他
6.1 運(yùn)輸問題的數(shù)學(xué)模型
6.1.1 問題的提出
6.1.2 運(yùn)輸問題的特殊性
6.2 矩陣A的性質(zhì)
6.3 運(yùn)輸問題的求解過程
6.3.1 求初始可行解的西北角法
6.3.2 最小元素法
6.3.3 圖上作業(yè)法
6.4 ci-zi的計(jì)算，進(jìn)入基的確定
6.5 退出基的確定
6.6 舉例
6.7 任務(wù)安排問題
6.7.1 任務(wù)安排與運(yùn)輸問題
6.7.2 求解舉例
6.8 任務(wù)安排的匈牙利算法
6.8.1 代價(jià)矩陣
6.8.2 Knig定理
6.8.3 標(biāo)志數(shù)法
6.8.4 匈牙利算法
6.8.5 匹配算法
6.9 任務(wù)安排的分支定界法
6.10 一般的任務(wù)安排問題
6.11 運(yùn)輸網(wǎng)絡(luò)
6.11.1 網(wǎng)絡(luò)流
6.11.2 割切
6.11.3 Ford-Fulkerson定理
6.11.4 標(biāo)號(hào)法
6.11.5 Edmonds-Karp修正算法
6.11.6 Dinic算法
習(xí)題六
第7章 內(nèi)點(diǎn)法簡介
7.1 Klee與Minty舉例
7.2 數(shù)學(xué)準(zhǔn)備
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 原偶對(duì)稱型
7.3.2 KKT方程組及牛頓法
7.3.3 μ的確定,步長的確定
7.3.4 初始值和結(jié)束準(zhǔn)則
7.3.5 算法步驟
7.3.6 收斂性的討論
7.3.7 KKT方程組的重要?dú)w約
7.4 梯度法與仿射變換
第8章 目標(biāo)規(guī)劃
8.1 問題的提出
8.2 目標(biāo)規(guī)劃的幾何解釋
8.3 目標(biāo)規(guī)劃的單純形表格
8.4 目標(biāo)序列化方法
8.5 目標(biāo)規(guī)劃的靈敏度分析
8.6 應(yīng)用舉例
習(xí)題八
第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 對(duì)稱型流動(dòng)推銷員問題
9.6.2 非對(duì)稱型流動(dòng)推銷員問題
9.7 整數(shù)規(guī)劃的分支定界解法
9.8 分支定界法在解混合規(guī)劃上的應(yīng)用
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ī)劃的割平面法
習(xí)題九