《初等組合最最佳化論（下冊）》是2018年08月01日科學出版社出版的圖書，作者是秦裕瑗、鄧旭東。
基本介紹
- 書名：初等組合最最佳化論（下冊）
- 作者：秦裕瑗、鄧旭東
- ISBN：9787030528308
- 頁數：289
- 定價：118.00元
- 出版社：科學出版社
- 出版時間：2018年08月01日
- 裝幀：平裝
- 開本：B5
內容簡介,圖書目錄,
內容簡介
本書以生物進化為自然原型，模仿導數概念與牛頓切線法，通過建立基本變換公式與一般鄰點法，形成了研究組合最最佳化論的核心思想和方法。本書分上、下兩冊共三篇（12章）展開學術探討，上冊（上篇）建立了本學科的公理系統和科學研究綱領——發現算法的方法，指出組合型與連續型最最佳化理論的並行關係。在此基礎上，下冊（中、下兩篇）對多個經典問題的各自實例進行了探討，整理出它們的常用求解算法，並探討了它們之間的相互關係。
圖書目錄
目錄
(下冊)
前言
摘要
中篇 代數對象型的最佳化問題
第7章 集合型三個最佳化問題 3
7.1 初等子集最佳化問題 PP11 3
7.1.1 問題的提出 3
7.1.2 強優選準域上的初等子集最佳化實例 4
7.1.3 實數域中初等子集最佳化實例 6
7.2 和值最小型擬陣的基集最佳化問題 PP12 6
7.2.1 問題的提出 6
7.2.2 貪婪法 8
7.3 策略最佳化問題 PP13 9
7.3.1 問題的提出 9
7.3.2 Bellman 最最佳化原理 11
7.3.3 Bellman 基本遞推公式 13
7.4 狀態-決策兩種直觀表示 14
7.4.1 狀態-決策圖 14
7.4.2 狀態空間-決策簇的代數表示 14
7.5 多階段賦值有向圖模型 16
7.6 研究組合最最佳化實例的一種途徑 20
7.7 峰 (谷) 值型提法實例 22
7.7.1 實例的提出 22
7.7.2 基本性質 23
7.7.3 數字例 25
7.8 峰谷差提法實例 27
7.8.1 求解算法 27
7.8.2 數字例 28
7.9 一般最最佳化原理的推廣 29
7.10 廣義優選半環 31
7.10.1 基本概念與性質 31
7.10.2 一般方法 33
7.11 N 階最佳化原理 34
7.11.1 一般 N 階最佳化原理 34
7.11.2 碎片型 N 階最佳化原理 35
7.12 N 階策略最佳化原理 36
7.13 廣義優選半環 SEQUENCE 與 (N-TH) 37
7.14 數字例 39
7.15 廣義優選半環和 PARETO 40
7.15.1 代數系統和 PARETO 40
7.15.2 廣義強優選準域 42
7.15.3 有效化原理 43
7.16 廣義優選半環 ESSENCE 43
7.16.1 實質摹多項式 43
7.16.2 旅行費用-時間實例 45
7.17 研究組合最最佳化問題的一種思路 46
7.17.1 問題的提法 46
7.17.2 問題諸實例的相關性 47
第8章 向量集型最佳化問題 50
8.1 非負組合子 (向量) 集最佳化問題 50
8.1.1 引言 50
8.1.2 定義 51
8.2 基本變換公式 53
8.3 相鄰可行解的關係 54
8.4 改變度簇 C(a) 的分類 56
8.5 鄰點法 57
8.5.1 改進單純形法 57
8.5.2 疊代過程避免循環現象的充分條件 59
8.5.3 表算格式 59
8.6 線性規劃 60
8.6.1 非負組合基集最佳化問題與線性規劃問題 60
8.6.2 線性規劃的幾種型式 60
8.7 對偶線性規劃 62
8.7.1 對偶性 62
8.7.2 線性規劃的對偶問題 63
8.8 基本性質 65
8.9 帶參數的線性規劃問題 68
8.9.1 原設-對偶方法 68
8.9.2 數字例 68
8.10 整數型組合向量子集最佳化問題 70
8.11 兩個求解整數線性規劃的方法 72
8.11.1 分支定界法 72
8.11.2 割平面法 72
8.12 普通線性規劃的各種衍生問題 74
8.13 策略最佳化問題的普通線性規劃求解方法 75
8.14 一點註記 77
第9章 方陣集型全排列最佳化問題 79
9.1 基本概念 79
9.1.1 引言 79
9.1.2 排序論定義 81
9.1.3 幾個基本的目標函式 83
9.2 研究排序實例的綱領 84
9.2.1 排序實例的特性與方法 84
9.2.2 第3最最佳化原理 85
9.2.3 可行解 a 的改變度簇 C(a) 86
9.2.4 第4最最佳化原理 87
9.3 排序型的鄰點法 87
9.4 基本排序實例 89
9.4.1 總等待時間最小實例 89
9.4.2 總等待費用最佳化實例 91
9.5 兩個單機排序誤時實例 92
9.5.1 誤時峰值實例 92
9.5.2 峰值費用最小實例 94
9.5.3 誤工工件數最佳化實例 95
9.5.4 線性排序模型 99
9.6 流水作業最佳化問題 100
9.6.1 1×n流水作業最佳化問題 100
9.6.2 2×n流水作業最佳化問題 100
9.7 BLB算法 103
9.8 同順序2×n流水作業最佳化問題 106
9.8.1 三個有效的算法 106
9.8.2 數字例 108
9.8.3 對三個算法的一點評註 110
9.9 一般Johnson算法的幾個套用 111
9.9.1 幾個一台機器排序最佳化實例 111
9.9.2 固態流水作業實例 113
9.10 同順序3×n流水作業最佳化問題 114
9.11 同順序3×n流水作業最佳化實例 115
9.12 分支定界法及啟發式算法 118
9.12.1 分支定界法 118
9.12.2 啟發式算法的下界 119
9.12.3 啟發式算法的上界 122
9.13 計算機上的實驗方法 123
下篇 網路對象型的最佳化問題
第10章 樹的最佳化問題 127
10.1 樹、森林及其基本性質 127
10.1.1 兩個預備子程式 127
10.1.2 樹的基本概念 127
10.2 樹的最佳化實例與同解算法 128
10.2.1 支撐樹與余樹 128
10.2.2 樹的最佳化實例的提出 129
10.2.3 破圈算法 130
10.3 第1最最佳化原理與最小支撐樹實例 131
10.3.1 第1最最佳化原理 131
10.3.2 去劣算法、生成算法和貪婪算法 132
10.4 第3最最佳化原理與鄰點法 134
10.4.1 第3最最佳化原理 134
10.4.2 可行解的改變度 135
10.4.3 調優算法與M算法 135
10.5 第4最最佳化原理與最優擴充法 137
10.5.1 原理的論述 137
10.5.2 最優擴充定理與最小樹實例 138
10.5.3 一般最優擴充算法 140
10.5.4 Prim算法、Berg算法與宋昭潤優選邊算法 142
10.6 數字例 145
10.7 強優選準域上樹的最佳化實例 149
10.7.1 極大準域上樹的最佳化實例 149
10.7.2 峰值型最小樹實例 150
10.8 度限制樹的最佳化問題 151
10.8.1 實例的提出與求解思路 151
10.8.2 Glover-Klingman 定理 152
10.8.3 求解方法 153
10.9 首N階和值最小型支撐樹實例 154
第11章 路的最佳化問題 158
11.1 路的最佳化問題 158
11.2 基本概念 159
11.3 基本公式與三元運算 161
11.3.1 基本公式 161
11.3.2 三元運算 162
11.4 同解方法 164
11.4.1 同解網路 164
11.4.2 非劣關係的基本性質 165
11.5 改進子程式 166
11.5.1 改進子 (矩陣) 166
11.5.2 改進的子程式 167
11.5.3 諸種改進子程式 169
11.6 Floyd 定理 171
11.7 Floyd 算法 172
11.8 1×n 型路最佳化問題的幾個算法 176
11.9 陽網路的 1×n 型路最佳化實例 177
11.9.1 Dijkstra 算法的討論 177
11.9.2 Dijkstra 算法 180
11.9.3 Dijkstra 算法表上作業 182
11.10 塊狀正則劃分規則 183
11.11 賦嘉量凝結圖 185
11.12 凝結路與凝結網路 187
11.12.1 凝結路 187
11.12.2 塊狀鄰接矩陣與凝結網路 188
11.13 Dantzig 算法 190
11.13.1 Dantzig 定理 190
11.13.2 數字例 192
11.14 第一種可分解網路 194
11.14.1 統籌方法 194
11.14.2 數字例 195
11.15 強連通圖 198
11.16 第二種可分解網路 199
11.16.1 Hu 定理 199
11.16.2 Hu 算法 202
11.16.3 Hu 算法推廣 203
11.17 結束語 204
11.17.1 幾點註記 204
11.17.2 歷史回顧 204
第12章 匹配最佳化問題 207
12.1 匹配及其基本性質 207
12.1.1 匹配概念 207
12.1.2 匹配最佳化問題的算法 208
12.2 基本性質與方法 209
12.2.1 基本性質與三個初等方法 209
12.2.2 四個數字例 210
12.3 第1, 2最最佳化原理與匹配最佳化問題 216
12.4 第3最最佳化原理 217
12.4.1 交錯路概念 217
12.4.2 二分圖的基本性質 218
12.5 二分圖的基數最大型匹配實例 219
12.5.1 匈牙利算法 219
12.5.2 數字例 220
12.6 賦值路的匹配最佳化定理 222
12.6.1 賦態匹配 223
12.6.2 賦值路上的最優匹配定理 224
12.7 賦值路的和值最大型匹配 224
12.7.1 (子) 路的值矩陣和匹配矩陣 224
12.7.2 最優匹配的計算公式 226
12.7.3 數字例 229
12.8 匹配最佳化原理 231
12.8.1 原理的提出 231
12.8.2 串聯公式 231
12.8.3 基本計算公式 234
12.9 並聯問題 235
12.9.1 並聯的公式 235
12.9.2 數字例 236
12.10 Q類圖的圖元及基本公式 237
12.10.1 圖元及其匹配矩陣表 238
12.10.2 幾個變形規則 241
12.11 極優代數方法 243
12.12 四個數字例 243
12.12.1 賦值正四面體圖 244
12.12.2 賦值正六面體圖 246
12.12.3 GM 圖 250
12.12.4 Korte 圖 251
12.13 中國郵路最佳化問題 255
12.14 網路流最佳化問題 257
12.15 續論基本變換公式的核心作用 260
全書結束語 262
參考文獻 266
附錄 274
附錄A 特性集 274
附錄B 方法與子程式集 276
附錄C 實例按提法分類 277
附錄D 組合最最佳化問題的代數分類 278
附錄E 全書例題彙編 278
名詞索引 281
(下冊)
前言
摘要
中篇 代數對象型的最佳化問題
第7章 集合型三個最佳化問題 3
7.1 初等子集最佳化問題 PP11 3
7.1.1 問題的提出 3
7.1.2 強優選準域上的初等子集最佳化實例 4
7.1.3 實數域中初等子集最佳化實例 6
7.2 和值最小型擬陣的基集最佳化問題 PP12 6
7.2.1 問題的提出 6
7.2.2 貪婪法 8
7.3 策略最佳化問題 PP13 9
7.3.1 問題的提出 9
7.3.2 Bellman 最最佳化原理 11
7.3.3 Bellman 基本遞推公式 13
7.4 狀態-決策兩種直觀表示 14
7.4.1 狀態-決策圖 14
7.4.2 狀態空間-決策簇的代數表示 14
7.5 多階段賦值有向圖模型 16
7.6 研究組合最最佳化實例的一種途徑 20
7.7 峰 (谷) 值型提法實例 22
7.7.1 實例的提出 22
7.7.2 基本性質 23
7.7.3 數字例 25
7.8 峰谷差提法實例 27
7.8.1 求解算法 27
7.8.2 數字例 28
7.9 一般最最佳化原理的推廣 29
7.10 廣義優選半環 31
7.10.1 基本概念與性質 31
7.10.2 一般方法 33
7.11 N 階最佳化原理 34
7.11.1 一般 N 階最佳化原理 34
7.11.2 碎片型 N 階最佳化原理 35
7.12 N 階策略最佳化原理 36
7.13 廣義優選半環 SEQUENCE 與 (N-TH) 37
7.14 數字例 39
7.15 廣義優選半環和 PARETO 40
7.15.1 代數系統和 PARETO 40
7.15.2 廣義強優選準域 42
7.15.3 有效化原理 43
7.16 廣義優選半環 ESSENCE 43
7.16.1 實質摹多項式 43
7.16.2 旅行費用-時間實例 45
7.17 研究組合最最佳化問題的一種思路 46
7.17.1 問題的提法 46
7.17.2 問題諸實例的相關性 47
第8章 向量集型最佳化問題 50
8.1 非負組合子 (向量) 集最佳化問題 50
8.1.1 引言 50
8.1.2 定義 51
8.2 基本變換公式 53
8.3 相鄰可行解的關係 54
8.4 改變度簇 C(a) 的分類 56
8.5 鄰點法 57
8.5.1 改進單純形法 57
8.5.2 疊代過程避免循環現象的充分條件 59
8.5.3 表算格式 59
8.6 線性規劃 60
8.6.1 非負組合基集最佳化問題與線性規劃問題 60
8.6.2 線性規劃的幾種型式 60
8.7 對偶線性規劃 62
8.7.1 對偶性 62
8.7.2 線性規劃的對偶問題 63
8.8 基本性質 65
8.9 帶參數的線性規劃問題 68
8.9.1 原設-對偶方法 68
8.9.2 數字例 68
8.10 整數型組合向量子集最佳化問題 70
8.11 兩個求解整數線性規劃的方法 72
8.11.1 分支定界法 72
8.11.2 割平面法 72
8.12 普通線性規劃的各種衍生問題 74
8.13 策略最佳化問題的普通線性規劃求解方法 75
8.14 一點註記 77
第9章 方陣集型全排列最佳化問題 79
9.1 基本概念 79
9.1.1 引言 79
9.1.2 排序論定義 81
9.1.3 幾個基本的目標函式 83
9.2 研究排序實例的綱領 84
9.2.1 排序實例的特性與方法 84
9.2.2 第3最最佳化原理 85
9.2.3 可行解 a 的改變度簇 C(a) 86
9.2.4 第4最最佳化原理 87
9.3 排序型的鄰點法 87
9.4 基本排序實例 89
9.4.1 總等待時間最小實例 89
9.4.2 總等待費用最佳化實例 91
9.5 兩個單機排序誤時實例 92
9.5.1 誤時峰值實例 92
9.5.2 峰值費用最小實例 94
9.5.3 誤工工件數最佳化實例 95
9.5.4 線性排序模型 99
9.6 流水作業最佳化問題 100
9.6.1 1×n流水作業最佳化問題 100
9.6.2 2×n流水作業最佳化問題 100
9.7 BLB算法 103
9.8 同順序2×n流水作業最佳化問題 106
9.8.1 三個有效的算法 106
9.8.2 數字例 108
9.8.3 對三個算法的一點評註 110
9.9 一般Johnson算法的幾個套用 111
9.9.1 幾個一台機器排序最佳化實例 111
9.9.2 固態流水作業實例 113
9.10 同順序3×n流水作業最佳化問題 114
9.11 同順序3×n流水作業最佳化實例 115
9.12 分支定界法及啟發式算法 118
9.12.1 分支定界法 118
9.12.2 啟發式算法的下界 119
9.12.3 啟發式算法的上界 122
9.13 計算機上的實驗方法 123
下篇 網路對象型的最佳化問題
第10章 樹的最佳化問題 127
10.1 樹、森林及其基本性質 127
10.1.1 兩個預備子程式 127
10.1.2 樹的基本概念 127
10.2 樹的最佳化實例與同解算法 128
10.2.1 支撐樹與余樹 128
10.2.2 樹的最佳化實例的提出 129
10.2.3 破圈算法 130
10.3 第1最最佳化原理與最小支撐樹實例 131
10.3.1 第1最最佳化原理 131
10.3.2 去劣算法、生成算法和貪婪算法 132
10.4 第3最最佳化原理與鄰點法 134
10.4.1 第3最最佳化原理 134
10.4.2 可行解的改變度 135
10.4.3 調優算法與M算法 135
10.5 第4最最佳化原理與最優擴充法 137
10.5.1 原理的論述 137
10.5.2 最優擴充定理與最小樹實例 138
10.5.3 一般最優擴充算法 140
10.5.4 Prim算法、Berg算法與宋昭潤優選邊算法 142
10.6 數字例 145
10.7 強優選準域上樹的最佳化實例 149
10.7.1 極大準域上樹的最佳化實例 149
10.7.2 峰值型最小樹實例 150
10.8 度限制樹的最佳化問題 151
10.8.1 實例的提出與求解思路 151
10.8.2 Glover-Klingman 定理 152
10.8.3 求解方法 153
10.9 首N階和值最小型支撐樹實例 154
第11章 路的最佳化問題 158
11.1 路的最佳化問題 158
11.2 基本概念 159
11.3 基本公式與三元運算 161
11.3.1 基本公式 161
11.3.2 三元運算 162
11.4 同解方法 164
11.4.1 同解網路 164
11.4.2 非劣關係的基本性質 165
11.5 改進子程式 166
11.5.1 改進子 (矩陣) 166
11.5.2 改進的子程式 167
11.5.3 諸種改進子程式 169
11.6 Floyd 定理 171
11.7 Floyd 算法 172
11.8 1×n 型路最佳化問題的幾個算法 176
11.9 陽網路的 1×n 型路最佳化實例 177
11.9.1 Dijkstra 算法的討論 177
11.9.2 Dijkstra 算法 180
11.9.3 Dijkstra 算法表上作業 182
11.10 塊狀正則劃分規則 183
11.11 賦嘉量凝結圖 185
11.12 凝結路與凝結網路 187
11.12.1 凝結路 187
11.12.2 塊狀鄰接矩陣與凝結網路 188
11.13 Dantzig 算法 190
11.13.1 Dantzig 定理 190
11.13.2 數字例 192
11.14 第一種可分解網路 194
11.14.1 統籌方法 194
11.14.2 數字例 195
11.15 強連通圖 198
11.16 第二種可分解網路 199
11.16.1 Hu 定理 199
11.16.2 Hu 算法 202
11.16.3 Hu 算法推廣 203
11.17 結束語 204
11.17.1 幾點註記 204
11.17.2 歷史回顧 204
第12章 匹配最佳化問題 207
12.1 匹配及其基本性質 207
12.1.1 匹配概念 207
12.1.2 匹配最佳化問題的算法 208
12.2 基本性質與方法 209
12.2.1 基本性質與三個初等方法 209
12.2.2 四個數字例 210
12.3 第1, 2最最佳化原理與匹配最佳化問題 216
12.4 第3最最佳化原理 217
12.4.1 交錯路概念 217
12.4.2 二分圖的基本性質 218
12.5 二分圖的基數最大型匹配實例 219
12.5.1 匈牙利算法 219
12.5.2 數字例 220
12.6 賦值路的匹配最佳化定理 222
12.6.1 賦態匹配 223
12.6.2 賦值路上的最優匹配定理 224
12.7 賦值路的和值最大型匹配 224
12.7.1 (子) 路的值矩陣和匹配矩陣 224
12.7.2 最優匹配的計算公式 226
12.7.3 數字例 229
12.8 匹配最佳化原理 231
12.8.1 原理的提出 231
12.8.2 串聯公式 231
12.8.3 基本計算公式 234
12.9 並聯問題 235
12.9.1 並聯的公式 235
12.9.2 數字例 236
12.10 Q類圖的圖元及基本公式 237
12.10.1 圖元及其匹配矩陣表 238
12.10.2 幾個變形規則 241
12.11 極優代數方法 243
12.12 四個數字例 243
12.12.1 賦值正四面體圖 244
12.12.2 賦值正六面體圖 246
12.12.3 GM 圖 250
12.12.4 Korte 圖 251
12.13 中國郵路最佳化問題 255
12.14 網路流最佳化問題 257
12.15 續論基本變換公式的核心作用 260
全書結束語 262
參考文獻 266
附錄 274
附錄A 特性集 274
附錄B 方法與子程式集 276
附錄C 實例按提法分類 277
附錄D 組合最最佳化問題的代數分類 278
附錄E 全書例題彙編 278
名詞索引 281
