基本介紹
- 書名：組合最佳化導論
- 作者：越民義 李榮珩
- 出版日期：2014年5月1日
- 語種：簡體中文
- 外文名：Introduction To Combinatorial Optimization Second Edition
- 出版社：科學出版社
- 頁數：236頁
- 開本：5
內容簡介,圖書目錄,
內容簡介
《組合最佳化導論(第二版)》適合高等院校數學、管理、信息處理等有關專業的學生、教師和研究人員閱讀。
圖書目錄
第二版前言
第一版前言
第1章概述
1.1組合最佳化問題的算法
1.1.1算法
1.1.2算法的評估
1.2排序問題的記號和模型描述
1.2.1排序問題的記號
1.2.2排序問題的模型描述
第2章一台機器上的排序
2.1（）
2.1.1算法
2.1.2最優性證明
2.1.3另一個問題
2.14（）
2.2（）
2.2.1算法
2.2.2最優性證明
2.3在某些工件必須按時交貨的條件下的模型（）
2.3.1算法
2.3.2最優性證明
2.4模型（）
2.4.1算法
2.4.2最優性證明
2.5（）
2.5.1枚舉樹
2.5.2消去準則
2.5.3消去準則的套用
2.5.4下界
2.6（）
2.6.1算法
2.6.2最優性證明
2.6.3（）
2.7模型（）
2.7.1無先後關係的模型（）
2.7.2有先後關係的模型（）
2.8-個套用例子——循環矩陣
2.8.1問題的提出
2.8.2實例
2.8.3Hamilton循環
第3章兩台機器的情形
3.1問題的提出
3.1.1第一種情形
3.1.2第二種情形
3.1.3第三種情形
3.1.4若干指標和記號
3.2模型F2‖Cmax
3.2.1算法
3.2.2最優性證明
3.3模型J2|ti≤2|Cmax
3.3.1算法
3.3.2最優性證明
3.4模型J2|pij=1|maxLi
3.4.1算法
3.4.2最優性證明
3.5模型O2‖Cmax
3.5.1問題的解法
3.5.2模型的一般情況
3.6樹狀或林狀的工件加工系統：P|樹狀或林狀，pj=1|Cmax
3.6.1問題的提出
3.6.2算法
3.6.3最優性證明
3.71|prec|minmaTi（Fi）
3.7.1算法
3.7.2最優性證明
3.8P2|pi=1,prec|Cmax
3.8.1問題的提出
3.8.2Fujii等的算法
3.8.3Edmonds的算法
3.8.4M-花朵方法
3.8.5CG方法
第4章近似算法
4.1概述
4.1.1設計算法
4.1.2模擬求解
4.1.3近似算法求解
4.2近似解的定義
4.2.1一些定義
4.2.2實例
4.3一些排序問題的近似計算
4.3.1LPT算法
4.3.2完工時間的估算
4.3.3兩台機器的情形
4.4裝箱問題
4.4.1NF算法
4.4.2FF算法
4.4.3BF算法
4.5裝箱問題（續）
4.5.1記號
4.5.2引理和定理
4.5.3例子
4.6FFD算法
4.6.1FFD算法的由來
4.6.2定理和證明
4.6.3更緊界的證明
4.6.4緊界的證明
4.6.5FFD算法對小物件裝箱的漸近最壞性能比
4.6.6附錄：Csirik（1993）的有關結論及證明
4.7排序問題與裝箱問題的聯繫
4.7.1問題簡化法
4.7.2權函式法
4.7.3FFD算法在排序問題上的運用
4.7.47m上界的改進
第5章流水作業排序問題的最優算法
5.1消去準則
5.1.1排序問題的消去準則
5.1.2消去準則的選取
5.1.3任意條件下的消去準則
5.2分枝定界方法
5.2.1定義
5.2.2分枝方法
5.3上界和下界的估計
5.3.1瓶頸機器
5.3.2下界計算
5.3.3上界計算
第6章Steiner比猜想
6.1Steiner比猜想
6.1.1生成樹
6.1.2Steiner樹
6.1.3簡單回顧
6.2關於n=3，4，5的情況
6.2.1n=3
6.2.2n=4
6.2.3n=5
6.3一般情況
6.3.1問題的提出
6.3.2預備知識
6.4Steiner比猜想的證明
6.4.1情形λ≥0.5
6.4.2情形λ<0.5
6.4.3其他情形
6.5評註
第7章多重算法
參考文獻
索引
第一版前言
第1章概述
1.1組合最佳化問題的算法
1.1.1算法
1.1.2算法的評估
1.2排序問題的記號和模型描述
1.2.1排序問題的記號
1.2.2排序問題的模型描述
第2章一台機器上的排序
2.1（）
2.1.1算法
2.1.2最優性證明
2.1.3另一個問題
2.14（）
2.2（）
2.2.1算法
2.2.2最優性證明
2.3在某些工件必須按時交貨的條件下的模型（）
2.3.1算法
2.3.2最優性證明
2.4模型（）
2.4.1算法
2.4.2最優性證明
2.5（）
2.5.1枚舉樹
2.5.2消去準則
2.5.3消去準則的套用
2.5.4下界
2.6（）
2.6.1算法
2.6.2最優性證明
2.6.3（）
2.7模型（）
2.7.1無先後關係的模型（）
2.7.2有先後關係的模型（）
2.8-個套用例子——循環矩陣
2.8.1問題的提出
2.8.2實例
2.8.3Hamilton循環
第3章兩台機器的情形
3.1問題的提出
3.1.1第一種情形
3.1.2第二種情形
3.1.3第三種情形
3.1.4若干指標和記號
3.2模型F2‖Cmax
3.2.1算法
3.2.2最優性證明
3.3模型J2|ti≤2|Cmax
3.3.1算法
3.3.2最優性證明
3.4模型J2|pij=1|maxLi
3.4.1算法
3.4.2最優性證明
3.5模型O2‖Cmax
3.5.1問題的解法
3.5.2模型的一般情況
3.6樹狀或林狀的工件加工系統：P|樹狀或林狀，pj=1|Cmax
3.6.1問題的提出
3.6.2算法
3.6.3最優性證明
3.71|prec|minmaTi（Fi）
3.7.1算法
3.7.2最優性證明
3.8P2|pi=1,prec|Cmax
3.8.1問題的提出
3.8.2Fujii等的算法
3.8.3Edmonds的算法
3.8.4M-花朵方法
3.8.5CG方法
第4章近似算法
4.1概述
4.1.1設計算法
4.1.2模擬求解
4.1.3近似算法求解
4.2近似解的定義
4.2.1一些定義
4.2.2實例
4.3一些排序問題的近似計算
4.3.1LPT算法
4.3.2完工時間的估算
4.3.3兩台機器的情形
4.4裝箱問題
4.4.1NF算法
4.4.2FF算法
4.4.3BF算法
4.5裝箱問題（續）
4.5.1記號
4.5.2引理和定理
4.5.3例子
4.6FFD算法
4.6.1FFD算法的由來
4.6.2定理和證明
4.6.3更緊界的證明
4.6.4緊界的證明
4.6.5FFD算法對小物件裝箱的漸近最壞性能比
4.6.6附錄：Csirik（1993）的有關結論及證明
4.7排序問題與裝箱問題的聯繫
4.7.1問題簡化法
4.7.2權函式法
4.7.3FFD算法在排序問題上的運用
4.7.47m上界的改進
第5章流水作業排序問題的最優算法
5.1消去準則
5.1.1排序問題的消去準則
5.1.2消去準則的選取
5.1.3任意條件下的消去準則
5.2分枝定界方法
5.2.1定義
5.2.2分枝方法
5.3上界和下界的估計
5.3.1瓶頸機器
5.3.2下界計算
5.3.3上界計算
第6章Steiner比猜想
6.1Steiner比猜想
6.1.1生成樹
6.1.2Steiner樹
6.1.3簡單回顧
6.2關於n=3，4，5的情況
6.2.1n=3
6.2.2n=4
6.2.3n=5
6.3一般情況
6.3.1問題的提出
6.3.2預備知識
6.4Steiner比猜想的證明
6.4.1情形λ≥0.5
6.4.2情形λ<0.5
6.4.3其他情形
6.5評註
第7章多重算法
參考文獻
索引
