單目標(biāo)、多目標(biāo)與整數(shù)規(guī)劃

第1章  引論                  
 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  單純形法                  
 2.6.1  基本定理                  
 2.6.2  退化型概念                  
 2.6.3  單純形法步驟                  
 2.6.4  舉例                  
 2.7  單純形表格                  
 習(xí)題二                  
 第3章  改善的單純形法                  
 3.1  數(shù)學(xué)準(zhǔn)備                  
 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  改善單純形法的復(fù)雜性分析                  
 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  說明舉例                  
 習(xí)題三                  
 第4章  單純形法的若干補(bǔ)充靈敏度分析                  
 4.1  二階段法                  
 4.2  大M法                  
 4.3  退化情形                  
 4.3.1  退化形問題                  
 4.3.2  出現(xiàn)循環(huán)舉例                  
 4.4  防止循環(huán)                  
 4.4.1  退出基不唯一時(shí)的選擇辦法                  
 4.4.2  首正向量概念                  
 4.4.3  不出現(xiàn)循環(huá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ī)劃                  
 習(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ì)偶定理                  
 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í)題五                  
 第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  科涅格定理                  
 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  福德-?？诉d定理                  
 6.11.4  標(biāo)號(hào)法                  
 6.11.5  埃德蒙期-卡普修正算法                  
 6.11.6  狄尼算法                  
 習(xí)題六                  
 第7章  哈奇揚(yáng)算法與卡瑪卡算法                  
 7.1 克里與明特舉例                  
 7.2  哈奇揚(yáng)算法                  
 7.2.1  問題的轉(zhuǎn)化                  
 7.2.2  哈奇揚(yáng)算法步驟                  
 7.2.3  算法的正確性證明的準(zhǔn)備                  
 7.2.4  定理的證明                  
 7.2.5  嚴(yán)格不等式組                  
 7.2.6  復(fù)雜性分析                  
 7.3  卡瑪卡算法與卡碼卡典型問題                  
 7.3.1  卡瑪卡標(biāo)準(zhǔn)型                  
 7.3.2  化為標(biāo)準(zhǔn)型的方法之一                  
 7.3.3  化為標(biāo)準(zhǔn)型的方法之二                  
 7.3.4  T0變換                  
 7.3.5  卡瑪卡算法步驟                  
 7.3.6  卡瑪卡算法的若干基本概念                  
 7.3.7   TK變換的若干性質(zhì)                  
 7.3.8  勢(shì)函數(shù)及卡瑪止的復(fù)雜性                  
 練習(xí)七                  
 第8章  多目標(biāo)規(guī)劃                  
 8.1  問題的提出                  
 8.2  多目標(biāo)規(guī)劃的幾何解釋                  
 8.3  多目標(biāo)規(guī)劃的單純形表格                  
 8.4  多目標(biāo)規(guī)劃的目標(biāo)序列化方法                  
 8.5  多目標(biāo)規(guī)劃的靈敏度分析                  
 8.6  應(yīng)用舉例                  
 習(xí)題八                  
 第9章  整數(shù)規(guī)劃問題的DFS搜索法與分支定界法                  
 9.1  問題的提出                  
 9.2  整數(shù)規(guī)劃的幾何意義                  
 9.3  可用線性規(guī)劃求解的整數(shù)規(guī)劃問題                  
 9.4  0-1規(guī)劃和DFS搜索法                  
 9.4.1  窮舉法                  
 9.4.2  DFS搜索法                  
 9.5  整數(shù)規(guī)劃的DFS搜索法                  
 9.5.1  搜索策略                  
 9.5.2  舉例                  
 9.6  替代約束                  
 9.6.1  吉阿福里昂替代約束                  
 9.6.2  舉例                  
 9.7  分支定界法介紹                  
 9.7.1  對(duì)稱型流動(dòng)推銷員問題                  
 9.7.2  非對(duì)稱型流動(dòng)推銷員問題                  
 6.7.3  最佳匹配問題                  
 6.10  分支定界法在解混合規(guī)劃上的應(yīng)用                  
 6.11  估階方法                  
 習(xí)題九                  
 第10章  整數(shù)規(guī)劃的割平面法                  
 10.1  割平面                  
 10.1.1  郭莫萊割平面方程                  
 10.1.2  例                  
 10.2  割平面的選擇                  
 10.3  馬丁割平面方程                  
 10.4  全整數(shù)割平面法                  
 10.4.1  全整數(shù)單純形表格                  
 10.4.2  舉例                  
 10.4.3  確定λ的策略                  
 10.5  混合規(guī)劃的割平面法                  
 習(xí)題十                  
 第十一章  奔德斯分析算法與招的解決                  
 11.1  混合規(guī)劃的奔德斯分解算法                  
 11.1.1  分解算法的原理                  
 11.1.2  奔德斯分解算法                  
 11.1.3  算法舉例                  
 11.2  群的解法                  
 11.2.1  群的解法原理                  
 11.2.2  舉例                  
 11.3  群的解法和最短路徑問題                  
 11.3.1  圖的構(gòu)造                  
 11.33.2  求最短路徑的戴克斯特拉算法                  
 11.4  背包問題                  
 11.5  將整數(shù)規(guī)劃歸約為背包問題                  
 11.6  背包問題的網(wǎng)絡(luò)解法                  
 11.7  背包問題的分支定界解法                  
 11.8  流動(dòng)推銷員問題的近似解法                  
 11.8.1  最近插入法                  
 11.8.2  最小增量法                  
 11.8.3  回路改進(jìn)法                  
 習(xí)題十一                  
 第12章  動(dòng)態(tài)規(guī)劃算法                  
 12.1  最短路徑問題                  
 12.1.1  窮舉法                  
 12.1.2  改進(jìn)的算法                  
 12.1.3  復(fù)雜性分析                  
 12.2  最佳原理                  
 12.2.1  最佳原理                  
 12.2.2  最佳原理的應(yīng)用舉例                  
 12.3  流動(dòng)推銷員問題                  
 12.3.1  動(dòng)態(tài)規(guī)劃解法                  
 12.3.2  復(fù)雜性分析                  
 12.4  任意兩點(diǎn)間的最短距離                  
 12.4.1  距離矩陣算法                  
 12.4.2  動(dòng)態(tài)規(guī)劃算法                  
 12.5  同順序流水作業(yè)的任務(wù)安排                  
 12.6  整數(shù)規(guī)劃的動(dòng)態(tài)規(guī)劃解法                  
 12.6.1  多段判決公式                  
 12.6.2  舉例                  
 12.7  背包問題的動(dòng)態(tài)規(guī)劃解法                  
 習(xí)題十二                  
 參考文獻(xiàn)