离散动态规划与Bellman代数

第一部分 基础理论

第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 基本性质

……

第二部分　理论推广

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

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

第三部分　应用问题

第7章　匹配优化问题

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

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

参考文献

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

本书建立了一个与最优化原理足够贴近的代数系统。叫做Bellman半环，从而建立了离散动态规划的基本公理系统，证明了Bellman代数（包括极大代数和极小代数）是最优化原理成立的一个充分条件。

全书分三个部分共8章，以原理为基础，以Bellman代数为工具，讨论离散动态规划的基础理论、算法和应用。基本公理系统能够推广为一般公理系统，用以讨论k阶优化解问题、多目标非劣解问题，并建立匹配优化原理，得到了关于路和匹配的多种优化问题的求解公式。本书表明，离散动态规划是一门既具有公理化基础又具有代数工具的、专门讨论决策优化学问的应用数学分支。

本书可作为应用数学、管理科学等专业研究生学习教材和专业人员的参考书籍。

本项目以串并混合型离散制造系统为研究对象，主要开展了变动作业计划约束下系统整体预防性维护活动的动态调度研究。首先，通过分析离散制造系统系统层维护调度的参数构成、基本输入和状态转移等需求，研究建立了基于役龄递减和故障率递增的设备层混合式修复非新规则，实现了设备层的维护调度建模。然后，基于组成本理论和动态规划方法，分析了变动作业计划对组成本及动态调度过程的约束机制，建立了机会维护下离散制造系统整体的动态维护调度策略。之后，结合设备层的维护调度模型，研究了不同配置型式下设备提前或延期维护的节余成本的计算方法，完成了系统层维护调度目标函数的构建，实现了系统层维护调度策略的分阶段的动态优化。最后，分别以八设备串行离散制造系统和三阶段四设备串并混合型离散制造系统为仿真测试平台，通过仿真分析展示了本研究维护调度策略的具体决策过程，同时通过与其他两种维护调度策略，即所有作业区间设备都提前维护的策略和所有作业区间设备都延期维护的策略进行对比分析，进一步验证了本研究维护调度策略和优化模型的有效性。 本研究的动态维护调度理论融入了变动作业计划约束，不仅对提高离散制造系统的维护调度水平具有现实意义，而且促进了维护调度和作业调度两个研究领域的交叉与耦合。在本项目预定研究计划的基础上，项目组还进行了拓展研究，开展了多种维护技术下的多设备离散制造系统的维护调度研究以及考虑产线缓冲区条件下的多设备系统的维护调度研究，并取得了一系列的研究成果。 通过项目组研究成员3年来的共同努力，项目组最终完成了项目研究报告一份，发表和录用期刊论文16篇，其中SCI/EI论文12篇，包括《Reliability Engineering and System Saftety》、《European Journal of Operational Research》、《Computers and Industry Engineering》等国际知名SCI期刊论文3篇。此外，执行期间项目组还组织或参与了制造系统维护相关的学术会议2次，培养博硕士生6名。 2100433B

以串并混合型离散制造系统为研究对象，开展变动作业计划约束下系统整体预防性维护活动的动态调度研究。首先，通过分析系统层维护调度的参数构成、基本输入和状态转移等需求，研究建立基于役龄递减和故障率递增的混合式修复非新规则，实现设备层的维护调度建模。然后，基于组成本理论和动态规划方法，分析变动作业计划对组成本及动态调度过程的约束机制，建立机会维护下系统整体的动态维护调度策略。之后，结合设备层的维护调度模型，研究不同配置下设备提前或延期维护的节余成本的计算方法，完成系统层维护调度目标函数的构建，实现系统层维护调度策略的分阶段的动态优化。最后，以三阶段四设备组成的离散机械制造系统为测试床，通过仿真运行和对比分析，验证本研究维护调度策略和优化模型的有效性。本研究的动态维护调度理论融入变动作业计划约束，不仅对提高离散制造系统的维护调度水平具有现实意义，而且将促进维护调度和作业调度两个研究领域的交叉与耦合。

动态规划就是解决多阶段决策最优化问题的一种思想方法。

树形动态规划阶段

将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。

树形动态规划状态

各阶段开始时的客观条件叫做状态。

树形动态规划决策

当各段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。

树形动态规划策略

由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略。

树形动态规划状态转移方程

前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由k阶段到k 1阶段状态的演变规律，称为状态转移方程。