撰写本书的中心意图是为数学分支——组合最优化建立基础理论系统。本书首先给出了组合最优化问题的定义和一般最优化原理,这是建设基础理论工作的第一层。
一个数学对象的优化问题由诸多实例组成,每个实例涉及四个集合:论域、可行解(最优解)、可行域以及所赋实数值(权)所在集合。在论述实例时,总会涉及集合与其子集合之间,或集合与元素之间的关系。本书把一般原理应用于论域和可行域,建立了论域型和可行域型的最优化原理。对于最基本的实例,例如,规定可行解的值是诸元素的值之和,所求最小值就是一种优化的提法,记作 实例。在以后的计算过程中,这样的实数集必须构成一个半群。遵从一些前辈学者的见解,本书在两个可行解 之间建立了基本变换公式: 其中 符号 表示集合间的对称差运算,变换规则是 在演算基本变换公式的过程中, 型实例所赋的实数之间是一个加法交换群。在此基础上,本书引入了邻域概念,建立了拓扑结构。像布尔巴基学派那样,我们识别出组合最优化的三个基本结构,即序结构、代数结构和拓扑结构方面应有的条件,这是建设基础理论工作的第二层。
而采取什么技术,添加什么辅助公理,让所得结构成为人们较为熟悉或者有望开展研究工作的数学结构,并有效地表现出来,为以后所用,不同学者所得的结果无须一致。
本书以基本变换公式为核心,直接把所得的序结构与交换群合并,在实数集上建立了互相同构的四个具体的 准域,建立了强优选准域,提出了极优代数方法,加上从邻域概念所得的拓扑结构,成为建设组合最优化论基础理论的最终表现形式。
本书还用基本变换公式建立了邻点型和碎片型的最优化原理,把一般原理和所建立的这四个原理依次称为第 最优化原理,这是建设基础理论工作的第三层。
最后,基于上述数学结构系统,建立了拉卡托斯型的研究组合最优化问题实例的纲领,成为发现精确方法的方法。还论述了它们不仅是组合最优化论的基础理论系统,也能为组合数学、普通大学教育的运筹学课程所用。
上述所论组成本书上篇,共六章。由于没有涉及计算复杂性问题,称之为初等组合最优化论的基础理论。
按数学对象的代数结构,把问题分类为集合型、向量集型和方阵集型等。中篇有三章,第7章主要用极优代数方法讨论策略优化问题(动态规划)实例的求解方法,并研究诸实例之间的元型–衍生关系和方法,我们还重建了吴学谋的首N阶优化原理和吴沧浦的多目标优化原理;第8章用基本变换公式直接得到线性规划的改进单纯形算法;第9章用极优代数方法主要讨论同顺序流水作业排序问题。
下篇分三章。第10章按科学研究纲领整理树的优化实例的诸种算法;第11章以极优代数的摹矩阵为工具,系统地讨论路的优化问题;第12章建立了匹配优化原理,像求解不定积分的方法那样,在 类图形上求解诸多匹配优化数字例。
论述过程中,本书:
直接从问题的定义与一般原理得到了五种八个求解实例的初等方法(合称为第0类方法),再在上述四个新建的最优化原理上代数地导出各自4类求解实例的方法;
提出了一般优化扩充方法,统一地求解了数列(首N阶)型、向量集(多目标)型与多项式型提法的广义策略优化实例;
证明了策略优化问题与网络中两点间路的优化实例的同构性;
用极优代数方法求解了策略优化问题的诸实例。
在高等数学中,求解连续型最优化问题的基本方法是导数概念与牛顿切线法的组合,记作 【(导数) + (牛顿切线法)】。在组合最优化论中,我们用基本变换公式把可行解 的改变度簇 理解为导函数,则求解诸多实例的迭代法是【 (基本变换公式) + (一般邻点法)】。这不仅是对前者的一种摹写,而且当人们把生物两性交配而得到的种子(胎儿)作为生物繁衍后代的基本手段时,它们都是对达尔文的生物进化过程 【(种子(胎儿)) + (世代传承) 】 的摹写。这样,我们在连续型与离散型最优化两套理论之间尝试实现数学形式上的统一性方面做出了进一步的工作。
第一作者从20世纪70年代中期开始接触动态规划至今,40年来学术方向一直没有改变,1994年70岁退休,以此把学术工作分为前、后两期。原本有从1993年开始花五年时间写成组合最优化基础理论的计划,出乎意料地工作至今才告一段落。期间有三年时间因病接受治疗,感谢武汉同济医院章咏裳、周四维、庄乾元三位教授精心反复的治疗。在审读清样阶段,又因肺癌放疗术后体力下降,终于用20天时间完成了审读,使得本书的撰写和出版在艰难曲折的过程中完成。庆幸本书最终出版面世。
在构思、撰写本书的过程中,第二作者邓旭东同本人讨论了大量的相关学术问题,并且对书中实例进行了演算,共同完成了本书的撰写和编审工作。
在本书即将脱稿之际,眼前不时地浮现出一位位学者慈祥友善的容貌,亲切的叮嘱、讨论和询问的情景。四十年来,许多同行学者们关注我们在学术上的摸索与进展,在此深深地感谢他们。
我要特别感谢林诒勋教授,自我们从1978年在烟台学术会议上结识起,他一直是我工作的见证人。他先后五六次评审我的(包括本书)专著和教材,我们经常书信来往,在参加的多个学术会议上,我们当面交谈,他给了我很多的支持、指点和鼓励,几乎在本书各章中都有他的见解,本书所采用的基本术语“基本变换公式”也是遵从他的建议。
学术交流非常重要,几乎每次参加会议,我总是先准备好将要请教的问题,这样得益会更多。我深切感谢湖北省数学学会和运筹学会的同仁们,还要感谢唐国春教授,自1990年成立中国运筹学会排序专业委员会至今,他每次为我安排学术交流等事项。
40年来武汉科技大学的领导,几任党委书记和校长尤泽贵、丁永昌、任德麟、孔建益教授,管理学院两任院长潘开灵与邓旭东教授给予了我很多的帮助和支持,在此表示衷心的感谢。
为了一件跨时几年甚至几十年才能完成的学术研究工作,没有和睦的家庭是不可想象的。一个学者能够得到家庭成员如此的理解和支持是幸福的,我真诚地感谢妻子傅赛珍老师在生活上的关心和学术上对我的全面支持。感谢长女明建、次女明复和女婿杨磊。
再次感谢所有关心本书出版的学者们,也欢迎大家对本书提出指正意见和建议。
秦裕瑗
2016年11月于武汉科技大学