初等组合最优化论 下PDF电子书下载

中篇 代数对象型的优化问题 3

第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.2Bellman最优化原理 11

7.3.3Bellman基本递推公式 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.11N阶优化原理 34

7.11.1一般N阶优化原理 34

7.11.2碎片型N阶优化原理 35

7.12N阶策略优化原理 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.7BLB算法 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

下篇 网络对象型的优化问题 127

第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.4Prim算法、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.2Glover-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.6Floyd定理 171

11.7Floyd算法 172

11.8 1×n型路优化问题的几个算法 176

11.9阳网络的1×n型路优化实例 177

11.9.1Dijkstra算法的讨论 177

11.9.2Dijkstra算法 180

11.9.3Dijkstra算法表上作业 182

11.10块状正则划分规则 183

11.11赋嘉量凝结图 185

11.12凝结路与凝结网络 187

11.12.1凝结路 187

11.12.2块状邻接矩阵与凝结网络 188

11.13Dantzig算法 190

11.13.1Dantzig定理 190

11.13.2数字例 192

11.14第一种可分解网络 194

11.14.1统筹方法 194

11.14.2数字例 195

11.15强连通图 198

11.16第二种可分解网络 199

11.16.1Hu定理 199

11.16.2Hu算法 202

11.16.3Hu算法推广 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.10Q类图的图元及基本公式 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.3GM图 250

12.12.4Korte图 251

12.13中国邮路优化问题 255

12.14网络流优化问题 257

12.15续论基本变换公式的核心作用 260

全书结束语 262

参考文献 266

附录 274

附录A特性集 274

附录B方法与子程序集 276

附录C实例按提法分类 277

附录D组合最优化问题的代数分类 278

附录E全书例题汇编 278

名词索引 281