初等组合最优化论 下册
作者：秦裕瑗，邓旭东
出版时间： 2018年版
内容简介
本书以生物进化为自然原型，模仿导数概念与牛顿切线法，通过建立基本变换公式与一般邻点法，形成了研究组合最优化论的核心思想和方法。本书分上、下两册共三篇（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
