有关流水作业问题的若干结果

我们给出有关流水作业问题的若干结果，并讨论有待研究的一些问题．     

Powell映射及其应用

本文引入了Powell映射的概念,并将向量组的共轭性度量的概念扩充到非二次函数情形,用以讨论非线性最优化中Powell算法的性质,并得到了该算法在凸性假设下的二个收敛定理。     

离散型数学模型问题的计算复杂性简介

<正> 为什么有必要在讲述数学模型时介绍计算复杂性理论呢?一方面,在建立数学模型的过程中,必须同时考虑如何求解的问题,因此就要设计一个算法或近似算法,它有时可以利用表达式,有时只能利用解的结构性质,在离散型的数学问题中,穷举法往往是不可行的,即使在计算机上计算,对规模稍大的问题也不能在短时间内完成。因此,有必要知道,一个算法的计算工作量究竟有多大?与问题规模的关系如何?进一步,一个问题究竟有没有多项式算法(亦称好算法,后面将详述)?这就要求对算法复杂性理论有所了解。另一方面,计算机能做多种多样的运算,还能“转移”,“停机”等,因此,计算机科学中的计算复杂性理论本身就要求对计算对象及一般运算建立一个统一的数学模型,不过由于这个模型相当抽象与深入,对此我们在这里不进行介绍。我们的重点是:如何理解与判断算法的计算复杂性?如何理解与判断问题的计算复杂性?需要进一步钻研与查阅的读者可参考[1]和[2]     

拟线性双曲抛物耦合方程组的第二边值问题

§1.引言 在[1]中,我们讨论了拟线性双曲抛物耦合方程组的柯西问题。在本文中,进一步讨论它的第二边值问题。我们仍用[1]中的记号,凡类似的推导不再赘述。     

关于切块法的收敛性

我们知道,在多维最优化中,切块法(Region Elimination Technique,参见[1])。得出一个逐渐缩小的区域序列,在目标函数为凸的情形下,对应于有界闭凸集上的极小值点,将始终保留在序列的每个区域中。同时还已证明,切块法所得区域的体积趋于零的速度可用几何数列类比(参见[2])。但是,关于切块法的收敛特性,还存在以下两     

变步长轴向搜索法在非凸情形的性质

§1.引言变步长轴向搜索法亦称变步长坐标方向法,它作为一个最优化方法,其特点是:不采用一维搜索,且各方向的步长按照搜索的成功或失败而独立地增加或缩减.它可以作为缓慢而可靠的方法来使用,也可作为Rosenbrock方法的基本组成部分.由于它的上述特点,特别是各个方向的步长独立变化的特点,它不能被纳入[3]中定步长下山法的框架,因而给它的理论分析带来了困难.文[4]对变步长轴向搜索法在目标函数为凸性的情形下的收敛性给出了证明,其中对目标函数的下降量采用了特殊的估计手段.本文在[4]的基础上,在     

总延误问题的优先条件的可递性

关于一台机器的总延误问题,Emmons所建立的优先条件及相应的优先准则长期被认为是最重要的研究成果之一。本文证明,在适当的假设下,优先条件具有可递性,本文还讨论了优先条件与相应偏序的关系,以及它与工件集合的关系。作者将在另文研究优先条件用于偏序扩张的问题,要利用本文的结果。     

变步长轴向搜索法的分析

变步长轴向搜索法是指在搜索过程中各个方向之步长可随时变化的轴向搜索法,长期以来它只是一种经验方法。本文在这一方法中引入下山门槛,给出目标函数下降量的细致的估计,证明了这一方法对可微的目标函数具有收敛性。     

链式先后关系下的单机分批排序问题

在本文,我们证明链式先后关系下的单机分批排序问题是强NP困难的,解决了Albers和Brucker（1993）提出的待解决问题．关于此问题,Albers和Brucker（1993）也曾试图给出NP困难性证明,我们阐明了其证明中存在的缺陷．     

五台机器自由作业的稠密时间表

对于五台机器自由作业的稠密时间表，我们证明了一个比值不等式．