初等组合最优化论（上册）

(上册)

前言摘要

上篇 基本理论

第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 带*与带* 44

2.8 解带*** 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 

(下册)

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

第7章 集合型三个优化问题

第8章 向量集型优化问题

第9章 方阵集型全排列优化问题

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

第10章 树的优化问题

第11章 路的优化问题

第12章 匹配优化问题

全书结束语

参考文献

名词索引

附录

附录A 特性集

附录B 方法与子程序集

附录C 实例按提法分类

附录D 问题按代数结构分类1.6

附录E 全书例题汇编