离散动态规划与Bellman代数

　　本书建立了一个与最优化原理足够贴近的代数系统。叫做Bellman半环，从而建立了离散动态规划的基本公理系统，证明了Bellman代数（包括极大代数和极小代数）是最优化原理成立的一个充分条件。全书分三个部分共8章，以原理为基础，以Bellman代数为工具，讨论离散动态规划的基础理论、算法和应用。基本公理系统能够推广为一般公理系统，用以讨论k阶优化解问题、多目标非劣解问题，并建立匹配优化原理，得到了关于路和匹配的多种优化问题的求解公式。本书表明，离散动态规划是一门既具有公理化基础又具有代数工具的、专门讨论决策优化学问的应用数学分支。本书可作为应用数学、管理科学等专业研究生学习教材和专业人员的参考书籍。

　　秦裕瑗，1924年生于扬州。1950年毕业于上海大同大学数学系。先后任教子同济大学、武汉测绘学院和武汉科技大学。主要讲授高等数学、泛函分析、动态规划。组合最优化和运筹学等十多门课程。1882年被评为教授。1992年起享受国务院政府特殊津贴。曾任华中工学院等三所大学的兼职教授。先后应邀在美国、加拿大、联邦德国、民主德国、波兰、捷克斯洛伐克和奥地利等7个国家的14所大学进行学术演讲或学术交流。1989年9月-1990年2月。经奥地利国家科学部批准。任Graz技术大学客座教授，授课一学期，讲授自己的英文专著。1989年获湖北省人事厅与省教育委员会授予的湖北省优秀教师奖，1990年列入世界数学家名册，1992年获国务院颁发的“作出突出贡献”政府特殊津贴证书，1993年获国家教委科技进步三等奖，1995年获国家测绘局授予的科技贡献二等奖（第二作者）。发表学术论文40余篇。出版的著作有《嘉量原理——有限型多阶段决策问题的一个新处理》、OptimunPath Problems in Networks、《运筹学简明教程》（与秦明复合编、第二版为普通高等教育“十一五”国家级规划教材）、《一元代数方程纵横谈》；译著有[德]Roth·高等数学。第二卷（与邓立生合作）、第三卷、第四卷三个分册，[德]W·戴根·K·包美尔·微积分题解。上、下卷；另有一本《最优路问题——极优代数方法》已送审。

第一部分 基础理论
第1章 离散动态规划的基本公理系统与Bellman代数
1.1 策略优化问题及最优化原理
1.1.1 两个例题
1.1.2 最优化原理
1.2 对最优化原理的讨论
1.2.1 策略的代数结构
1.2.2 策略优劣的比较
1.2.3 Bellman公理
1.3 动态规划的基本公理系统与求解公式
1.3.1 Bellman半环
1.3.2 基本公理系统
1.3.3 求解公式
1.4 几个重要的代数系统
1.4.1 Bellman半环的基本性质
1.4.2 强优选准域
1.4.3 Bellman代数
1.5 实数集上一些代数系统举例
1.5.1 实数集上的Bellman半环的例
1.5.2 实数集上的强优选准域与Bellman代数的例
1.5.3 几个非强优选准域的例子
1.6 四类最优策略
1.7 图论模型及三个基本问题
1.7.1 决策与策略的图形表示
1.7.2 动态规划问题的分类三个基本问题
1.8 关于Bellman代数的注记
参考文献
第2章 决策数确定型问题
2.1 基本概念
2.2 递推公式Ⅰ
2.3 问题Ⅰ的（摹）矩阵模型
2.4 问题Ⅰ的图论模型
2.4.1 图论模型
2.4.2 数字例
2.5 赋值多阶段有向图中求解所有最优路及其长度的程序
2.6 资源分配问题
2.6.1 问题的一般讨论
2.6.2 数字例摹矩阵法
2.6.3 摹多项式法
2.7 计数Bellman半环
参考文献
第3章 决策数简单不确定型问题
3.1 引言
3.2 最优化原理和递推公式Ⅱ
3.3 问题Ⅱ的两种模型
3.3.1 矩阵模型
3.3.2 图论模型
3.4 两种计算公式
3.4.1 逆序递推公式与计算表
3.4.2 顺序递推公式与计算表
3.4.3 数字例
3.5 基本库存问题
3.5.1 一般问题的讨论
3.5.2 数字例
3.6 基本设备更新问题数字例
3.7 矩阵连乘式最优结合方式的算法
3.8 赋值上三角有向图中求解所有最短路及其长度的程序
3.9 工程计划的统筹问题
参考文献
第4章 决策数不确定型问题
4.1 图论模型
4.2 网络的基本代数性质
4.2.1 基本性质
4.2.2 基本公式
4.2.3 基本公式的图论意义三元运算
4.2.4.寻求有效算法的必要性
4.3 同解方法
4.3.1 同解网络
4.3.2 两种同解方法
4.3.3 非劣关系≤的基本性质
4.3.4.改进子的结构
4.4 问题III-1 的一般算法
4.4.1 第一代数结构定理
4.4.2 问题III-1的一般算法
4.4.3 Ford算法与Yen算法数字例
4.5 行型算法
4.5.1 一般网络中的行型算法
4.5.2 无回路网络中的问题III-1行型算法
4.6 阳网络中问题III-1的Diikstra算法
4.6.1 Dijkstra算法
4.6.2 数字例
4.7 问题III.2 及其一般算法
4.7.1 第二代数结构定理
4.7.2 问题III-2的一般算法
4.8 问题III-2的Floyd算法
4.8.1 Floyd算法
4.8.2 数字例
4.9 分块覆盖组
4.10 问题III-2的Dantzig算法
4.10.1 Dantzig算法
4.10.2 数字例
4.11 第一正则网络的Hu算法
4.11.1 第一正则网络Hu算法
4.11.2 Hu算法推广
4.12 第二正则网络
4.13 数值算法设计与最优路算法
4.13.1 迭代法与最优路算法
4.13.2 问题III-2的加速算法及其推广
4.13.3 问题III-1的加速算法
4.14 线性方程组初等变换与最优路问题
4.15 历史回顾
参考文献
第二部分 理论推广
第5章 基本公理系统的第一类推广
第6章 基本公理系统的第二类推广
第三部分 应用问题
第7章 匹配优化问题
第8章 数学物理方法中的应用
附录 组合图论与抽象代数的基本知识
参考文献