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

（上册） 3

上篇 基本理论 3

第1章 基本概念与初等方法 3

1.1 几个组合最优化问题 3

1.1.1 数的优化问题 3

1.1.2 图论型优化问题 4

1.1.3 管理型优化问题 6

1.2 组合最优化的定义 6

1.2.1 定义 6

1.2.2 论域、对象与提法 7

1.2.3 问题、实例与数字例 8

1.2.4 目标函数与答案 9

1.2.5 算法与方法 10

1.3 正则实例 10

1.3.1 定义 10

1.3.2 正则实例的一般表示形式 12

1.4 特性集List PPP 13

1.4.1 特性集的标识符 13

1.4.2 关于π（1）集的特性 13

1.4.3 关于π（2）集的特性 14

1.5 目标函数与提法 14

1.5.1 目标函数 14

1.5.2 提法的分类 15

1.6 组合最优化问题的代数分类 16

1.7 两个初等方法 18

1.7.1 描述求解过程的几种方法 18

1.7.2 枚举法 19

1.7.3 隐枚举法 21

1.8 同解法 23

1.8.1 同解法概念 23

1.8.2 分支法 24

1.8.3 归结法 25

1.9 连通性的判别子程序 26

1.10 计算复杂性与多项式P问题 28

1.10.1 计算复杂性 28

1.10.2 多项式算法 30

1.11 几点注记 30

第2章 论域型与可行域型最优化原理 33

2.1.引言 33

2.2 一般最优化原理 35

2.3 序集型优化原理 36

2.3.1 定理形式的原理 36

2.3.2 公理形式的原理 37

2.4 序集及其优化原理 39

2.5.1 （论域型）最优化原理 40

2.5.1 原理的性质 40

2.5.2 公理形式 41

2.6 基本性质 42

2.7 带F与带F＊ 44

2.8 解带FF＊D 47

2.9 去劣法、扩展法与递推法 49

2.10 生成法与分治法 51

2.11 数字例及实例 53

2.12 第2（可行域型）最优化原理 55

2.12.1 第2最优化原理的公理形式 55

2.12.2 基本性质 57

2.13 建立分支定界法的思路 57

2.14 求解实例的布局与要素 58

2.14.1 求解的布局 58

2.14.2 分支与赋序 59

2.14.3 松弛实例 60

2.15 分支定界法 62

2.15.1 基本分支定界法 62

2.15.2 两个分支定界法 62

2.16 分支定界法的一般讨论 64

2.17 关于原理的注记 65

第3章 基本变换公式 67

3.1 两种描述可行集簇的方法 67

3.1.1 枚举法 67

3.1.2 线性代数法 68

3.2 对可行集簇的几点思考 71

3.2.1 可行域的几种表示方法 71

3.2.2 不同层次上的统一性 73

3.2.3 对交错路形式化的展望 75

3.3 第三种描述方法——对称差分解法 77

3.3.1 两个可行集的对称差 77

3.3.2 基本变换公式 78

3.3.3 紧邻可行集的图形表示 79

3.4 两种基本图形表示 79

3.5 可行集簇图的基本性质 81

3.5.1 简单性与连通性 81

3.5.2 均匀性 83

3.5.3 一致Hamilton性 84

3.5.4 拉格朗日有限增量公式 85

3.6 值域的代数结构 86

3.6.1 极小准域 86

3.6.2 极大准域 88

3.6.3 强优选准域 89

3.7 独立系统与拟阵 90

3.7.1 基本概念 90

3.7.2 五个典型的拟阵 91

3.7.3 K4 的支撑树簇图 92

3.8 拟阵的性质 94

3.9 几何直观的一点注记 97

第4章 邻域型与碎片型最优化原理 99

4.1 求解连续型最优化问题的微分法回顾 99

4.1.1 导数概念 99

4.1.2 几点认识 101

4.2 紧邻簇N（a）与改变度簇C（a）的分解 103

4.3.3 （邻域型）最优化原理 104

4.3.1 原理的形式 104

4.3.2 基本定理 106

4.4 一般邻点法 107

4.5 关于几个子程序的事项 108

4.6 用邻点法求解实例的基本方法 109

4.6.1 求解实例XYZ:S的方法 109

4.6.2 关于寻求初始可行解的Charnes子程序 112

4.7 求解提法1的诸实例 114

4.7.1 求解实例XYZ-1:S的方法 114

4.7.2 求解实例XYZ-1j:S的方法 115

4.8 巡回商问题 116

4.8.1 巡回商问题的提出 116

4.8.2 巡回商实例的近似算法 118

4.9.4 （碎片型）最优化原理 119

4.10 几个具体对象的碎片型最优化原理 120

4.10.1 路的优化原理 120

4.10.2 树的优化原理 121

4.10.3 匹配优化原理 121

4.10.4 策略优化原理 122

第5章 极优代数方法 124

5.1 再论强优选准域 124

5.1.1 问题的提出 124

5.1.2 碎片值域的代数结构 125

5.1.3 碎片优劣的比较 126

5.1.4 强优选性 127

5.2 强优选准域的基本性质 128

5.3 强优选准域的同构性 130

5.3.1 问题的提出 130

5.3.2 同构映射 130

5.3.3 与极小准域同构的强优选准域 131

5.4 互为同构的强优选准域 133

5.4.1 四个强优选准域 133

5.4.2 同构方法 135

5.5 极优代数 135

5.6 应用极优代数 136

5.6.1 引言 136

5.6.2 基本应用模型 137

5.6.3 例5.1 过程的代数表示 139

5.7 摹多项式及其应用 139

5.7.1 摹多项式 139

5.7.2 例5.2 匹配优化问题的数字例 140

5.7.3 例5.3 温课迎考问题的数字例 141

5.8 列车时刻表问题的数字例 143

5.9 计数强优选半环 145

5.9.1 问题的提出 145

5.9.2 计数强优选半环 146

5.10 一点注记 148

第6章 组合最优化问题的研究纲领 150

6.1 基础理论框架 150

6.1.1 基本变换公式是一个核心概念 150

6.1.2 什么是基础理论框架 152

6.2 基本变换公式与某些数学分支的关系 153

6.2.1 基本变换公式与导函数概念的同构性 153

6.2.2 离散型、连续型数学优化问题的求解过程的并行性 154

6.2.3 生物进化论与求解优化问题的同源性 155

6.3 组合最优化论的基本公理框架 157

6.4 拉卡托斯型的科学研究纲领 161

6.4.1 学科发展的过程 161

6.4.2 纲领的正文 162

6.5 研究组合最优化实例的纲领 163

6.5.1 科学研究的纲领 163

6.5.2 科学研究纲领的框图 166

6.6 对科学研究纲领的评价 166

6.7 两点历史资料 167

6.7.1 克莱因传略 167

6.7.2 拉卡托斯传略 168

参考文献 170