《單目標、多目標與整數規劃》是1999年清華大學出版社出版的圖書，作者是盧開澄。本書對單目標線性規劃、多目標線性規劃和整數規劃等問題的提出、各種解算方法及其靈敏度的分析進行了比較全面的介紹和深入的討論，並有眾多的例題，是本書的特點。
基本介紹
- 作者：盧開澄
- ISBN：9787302033301
- 頁數：413
- 定價：29.80元
- 出版社：清華大學出版社
- 出版時間：1999-07
- 裝幀：平裝
- 叢書： 計算機科學組合學叢書
內容介紹,作品目錄,
內容介紹
內容簡介
本書共12章，前7章討論單目標線性規劃；第8章討論多目標線性規劃；後面4章討論與整數規劃
相關的問題。
本書可作為數學與經濟管理專業運籌學的教材，並可作為這一領域的工作人員的參考書。
作品目錄
目錄
第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背包問題的動態規劃解法
習題十二
參考文獻
第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背包問題的動態規劃解法
習題十二
參考文獻
