离散动态规划与Bellman代数PDF电子书下载

第一部分 基础理论 3

第1章 离散动态规划的基本公理系统与Bellman代数 3

1.1 策略优化问题及最优化原理 3

1.1.1 两个例题 3

1.1.2 最优化原理 5

1.2 对最优化原理的讨论 5

1.2.1 策略的代数结构 5

1.2.2 策略优劣的比较 8

1.2.3 Bellman公理 9

1.3 动态规划的基本公理系统与求解公式 9

1.3.1 Bellman半环 9

1.3.2 基本公理系统 10

1.3.3 求解公式 11

1.4 几个重要的代数系统 12

1.4.1 Bellman半环的基本性质 12

1.4.2 强优选准域 13

1.4.3 Bellman代数 15

1.5 实数集上一些代数系统举例 17

1.5.1 实数集上的Bellman半环的例 17

1.5.2 实数集上的强优选准域与Bellman代数的例 18

1.5.3 几个非强优选准域的例子 19

1.6 四类最优策略 19

1.7 图论模型及三个基本问题 21

1.7.1 决策与策略的图形表示 21

1.7.2 动态规划问题的分类三个基本问题 23

1.8 关于Bellman代数的注记 26

参考文献 27

第2章 决策数确定型问题 28

2.1 基本概念 28

2.2 递推公式Ⅰ 29

2.3 问题Ⅰ的（摹）矩阵模型 31

2.4 问题Ⅰ的图论模型 34

2.4.1 图论模型 34

2.4.2 数字例 36

2.5 赋值多阶段有向图中求解所有最优路及其长度的程序 38

2.6 资源分配问题 41

2.6.1 问题的一般讨论 41

2.6.2 数字例摹矩阵法 42

2.6.3 摹多项式法 45

2.7 计数Bellman半环 47

参考文献 51

第3章 决策数简单不确定型问题 52

3.1 引言 52

3.2 最优化原理和递推公式Ⅱ 53

3.3 问题Ⅱ的两种模型 54

3.3.1 矩阵模型 54

3.3.2 图论模型 55

3.4 两种计算公式 57

3.4.1 逆序递推公式与计算表 57

3.4.2 顺序递推公式与计算表 60

3.4.3 数字例 62

3.5 基本库存问题 63

3.5.1 一般问题的讨论 63

3.5.2 数字例 66

3.6 基本设备更新问题数字例 68

3.7 矩阵连乘式最优结合方式的算法 71

3.8 赋值上三角有向图中求解所有最短路及其长度的程序 73

3.9 工程计划的统筹问题 75

参考文献 77

第4章 决策数不确定型问题 78

4.1 图论模型 78

4.2 网络的基本代数性质 79

4.2.1 基本性质 79

4.2.2 基本公式 82

4.2.3 基本公式的图论意义三元运算 82

4.2.4 寻求有效算法的必要性 84

4.3 同解方法 85

4.3.1 同解网络 85

4.3.2 两种同解方法 86

4.3.3 非劣关系?的基本性质 88

4.3.4 改进子的结构 89

4.4 问题Ⅲ-1的一般算法 93

4.4.1 第一代数结构定理 93

4.4.2 问题Ⅲ-1的一般算法 95

4.4.3 Ford算法与Yen算法数字例 98

4.5 行型算法 99

4.5.1 一般网络中的行型算法 99

4.5.2 无回路网络中的问题Ⅲ-1行型算法 101

4.6 阳网络中问题Ⅲ-1的Dijkstra算法 101

4.6.1 Dijkstra算法 101

4.6.2 数字例 107

4.7 问题Ⅲ-2及其一般算法 108

4.7.1 第二代数结构定理 108

4.7.2 问题Ⅲ-2的一般算法 110

4.8 问题Ⅲ-2的Floyd算法 112

4.8.1 Floyd算法 112

4.8.2 数字例 114

4.9 分块覆盖组 118

4.10 问题Ⅲ-2的Dantzig算法 121

4.10.1 Dantzig算法 121

4.10.2 数字例 123

4.11 第一正则网络的Hu算法 125

4.11.1 第一正则网络Hu算法 125

4.11.2 Hu算法推广 130

4.12 第二正则网络 130

4.13 数值算法设计与最优路算法 132

4.13.1 迭代法与最优路算法 132

4.13.2 问题Ⅲ-2的加速算法及其推广 133

4.13.3 问题Ⅲ-1的加速算法 135

4.14 线性方程组初等变换与最优路问题 136

4.15 历史回顾 139

参考文献 141

第二部分 理论推广 145

第5章 基本公理系统的第一类推广 145

5.1 嘉量原理 145

5.1.1 嘉量 145

5.1.2 路的嘉量原理 146

5.2 网络的赋嘉量凝结图 148

5.2.1 凝结图及其嘉量 148

5.2.2 凝结路 150

5.2.3 凝结网络及其路改进法 151

5.3 路改进算法的应用 153

5.4 网络摄动优化问题 155

5.5 峰（谷）值优化问题 156

5.5.1 第一类推广基本公理系统的第二个途径 156

5.5.2 求解劣值最优问题的算法数字例 158

5.6 峰谷值差均衡型问题 160

5.6.1 问题Ⅳ-2的算法 160

5.6.2 数字例 162

5.7 强优选准域的扩充及其性质 164

5.8 扩充上的线性代数 169

5.8.1 行列式 169

5.8.2 dom与det 170

5.8.3 Cramer法则 170

5.8.4 特征多项式 171

参考文献 172

第6章 基本公理系统的第二类推广 173

6.1 三种推广题目的提出 173

6.2 广义Bellman半环 175

6.3 动态规划的一般公理系统 179

6.4 首N阶优化解问题问题Ⅴ 180

6.4.1 首N阶优化解题目的提出 180

6.4.2 N阶优化原理 181

6.5 广义Bellman半环SEQUENCE与（N-TH，?，?） 183

6.6 问题Ⅴ 186

6.6.1 计算公式 186

6.6.2 数字例 186

6.7 广义Bellman半环Ω和PARETO 188

6.7.1 代数系统Ω和PARETO 189

6.7.2 广义强优选准域 191

6.8 问题Ⅵ 192

6.8.1 有效化原理 192

6.8.2 数字例 192

6.9 广义Bellman半环：ESSENCE 194

6.9.1 实质摹多项式 194

6.9.2 旅行费用-时间问题数字例 195

参考文献 198

第三部分 应用问题 201

第7章 匹配优化问题 201

7.1 匹配及其基本性质 201

7.1.1 匹配概念 201

7.1.2 路上最优匹配的两个事实 202

7.2 赋值路上最优匹配的基本计算公式 204

7.2.1 子路的赋型最优匹配 204

7.2.2 （子）路的值矩阵和匹配矩阵 205

7.2.3 最优匹配的计算公式 207

7.3 郁金花图数字例 210

7.4 匹配优化原理及其基本计算公式 213

7.4.1 匹配优化原理 213

7.4.2 串联公式 214

7.4.3 基本公式 216

7.5 数字例 217

7.6 赋值二分图的最优匹配数字例 220

7.7 并联公式数字例 224

7.8 首N阶优化匹配问题 227

7.8.1 极大匹配 227

7.8.2 首N阶优化匹配问题数字例 228

7.9 所有极大匹配的计数问题数字例 233

7.10 可化为最优匹配的排序问题数字例 239

7.11 两点注记 243

参考文献 244

第8章 数学物理方法中的应用 245

8.1 构造多阶段有向图的五点近似法 245

8.1.1 五点近似法的提出 245

8.1.2 五点近似法 246

8.1.3 五点近似法的推广 248

8.2 变分法 249

8.2.1 问题的提出 249

8.2.2 变分法的一般论述 250

8.2.3 变分法与其他方程的关系 253

8.3 多阶段自动控制系统 253

8.3.1 问题的提出 253

8.3.2 数字例 254

8.4 金属压力加工能耗优化问题 257

8.4.1 问题的提出 257

8.4.2 最优压下规程与最优化原理 258

8.5 最优压下规程的图论模型 259

8.6 技术转移问题 261

参考文献 265

附录 组合图论与抽象代数的基本知识 266

A.1 无向图的基本概念 266

A.1.1 无向图 266

A.1.2 路与连通性 267

A.2 有向图 269

A.3 抽象代数的基本概念 272

A.3.1 集合的结构数学系统 272

A.3.2 半群、带与群 274

A.3.3 半环、环与域 275

A.3.4 线性空间与代数 275

A.4 关于科学计算软件Mathematica 276

参考文献 277