序贯最优化中的若干新课题

本项目的研究内容包括：以弦图扩张为中心的一组图论极值问题；网络最优嵌入问题；排序与时间表问题。作为不同于动态规划所处理的序贯最优化问题，该领域模型众多，应用广泛。本研究以探讨较统一的基本理论和方法为目标。三年内共发表学术论文15篇。其中较突出的结果如下：从稀疏矩阵计算出发，系统地论述了图扩张的基本理论，包括树宽、路宽、带宽、填充、侧廓、扩展侧廓的统一形式；建立了树宽和填充的分解定理；对排序问题的结构性质研究，解决了二机器流水作业排序的全部解问题；对单位工时排序问题建立了连续匹配的判定准则；解决了最优基图结构的刻划问题及图流形同胚分类的着色计数等。这些成果都体现出理论的创新性和方法的有效性。