染色装箱问题及其启发式算法

研究了装箱问题的一个新颖的衍生问题:染色装箱问题,即在装箱问题中,给每个物件指定一个颜色,要求每个箱子中所装的物件颜色各不相同,使得所需要的箱子数目尽可能少.该问题是通常装箱问题的一种推广.笔者给出了染色装箱问题的一个启发式算法,同时研究了只有两种颜色的染色装箱问题:即2-色装箱问题,并给出了一个最优算法.     

一个置换极值问题

研究一个车队探险问题的推广,证明了这个问题等价于一个置换极值问题,得到了最优解的一组必要条件.设计了一个近似算法,并提出了若干公开问题,且对一般的置换极值问题做了初步讨论.     

一个SAT问题有解的充要条件

合取范式可满足性问题(简称SAT问题)是一个NP完全问题.引入了一个饱和合取范式的概念,利用饱和合取范式的性质,对SAT问题的本质进行了研究.在此基础上,证明了一个SAT问题有解的充要条件,它为SAT问题完全算法和非完全快速算法的深入研究提供了一条新的思路.     

带准备时间和强制工期的单机排序问题

讨论了带准备时间和强制工期的单机排序问题. 在工件可中断、机器可空闲的条件下,确定一个工件排序,使得最大提前完工时间最小. 由于工件不允许延迟,首先考虑了问题的可行性. 通过将问题转化为一个带容量限制的有向图,并运用求解最大网络流的算法,提出了判定问题可行性的方法. 对于可行问题,给出了一个算法在多项式时间内获得最优排序.     

用递归算法设计程序应注意的问题

给出了一个游戏问题的解答程序.结合程序运行时出现的现象,引出一个值得注意的问题.     

带有叉熵约束的最小叉熵优化问题的求解

研究了带有叉熵约束的最小叉熵优化问题的求解问题.根据对偶理论,提出了一个简单的几何规划,该方法把一个带有叉熵约束的叉熵优化问题转化成了一个对偶规划,而对偶规划是一个只需要解决一个带有线性约束的凸规划问题,比较容易计算.     

基于非交换代数结构的公钥密码体制

提出了一个新的基于非交换代数结构的Diffie - Hellman密钥交换协议,并在此基础上建立了一个新的公钥密码体制.它的安全性取决于一个基本问题的困难性,而这个基本问题是共轭搜索问题和Diffie - Hellman问题的结合变形问题.最后将提出的体制应用到数字签名方案中,并给出一个类似于ElGamal的签名方案.     

林业砍伐问题的最优化数值解

对于育林业而言,选择在什么时候砍伐是一个至关重要的问题.时机选择得当,获得的效益就能很可观.通过运用数学方面的相关知识,建立了一个目标函数,即将砍伐林木所获得的最大利润值函数这样一个实际问题,转换为为数学上一个求极大值的问题,运用相关知识,讨论了选择什么时候砍伐才能使获得的利润取得最大值.从而为林业砍伐这一实用性问题提出了一个解决方案.     

单台机器有使用限制的排序问题

研究单台机器有使用限制的排序问题,即机器在给定的一个时间段内不可用,目标为最小化最大完工时间.每个工件都有一个到达时间,只有工件到达了才能加工,工件在加工过程中不可中断.对于该问题的离线情形,给出了一个近似比为4/3的近似算法和一个动态规划算法.对于问题的在线情形,给出了一个最优在线算法.     

解互补问题的一类广义拟牛顿算法

互补问题在实际生活中有着广泛的应用,是当前研究的一个热点问题,从而产生了很多的解决途径.本文利用互补函数将互补问题转化为一个无约束最优化问题,从而构造了一类求解互补问题的广义拟牛顿算法,并从理论上给出了无约束最优化问题的解是原互补问题解的一个充分条件.数值实验表明算法不仅可行而且效果较好.     

求解机会约束优化的Log-Sigmoid近似问题的样本均值近似方法

样本均值近似(SAA)方法在机会约束优化问题中扮演着重要的角色.基于机会约束优化问题的Log-Sigmoid近似,探讨求解Log-Sigmoid近似问题的样本均值近似方法.构造了约束函数的样本均值近似函数,建立了相应的样本均值近似问题,并且证明当样本数量足够大时,样本均值近似问题的最优值和最优解集分别以概率为1收敛于Log-Sigmoid近似问题的最优值和最优解集.     

关于满Steiner树问题的一个近似算法

满Steiner树问题(TST)是求解一个正则点都是叶子的最小Steiner树问题.Fabio Viduani Martinez等人给出了此问题的近似算法,它的性能比为2ρ-ρ/(3ρ-2)≈2.52,而目前求解Steiner树问题的近似算法的性能比,最小值约为1.550.对满Steiner树问题给出了一个近似算法,并将它的性能比改进为2ρ-3ρ/(6ρ-2)≈2.463.     

样条子空间逼近周期可微函数的最佳逼近度

样条函数类与周期函数类的逼近问题是函数逼近论的重要内容。为了在较大范围内研究最佳逼近问题,在Lp空间内研究最佳逼近方法的基础上,利用最佳逼近的对偶原理、Holder不等式等工具,借助抽象逼近的方法和技巧,研究了样条子空间在Orlicz空间内的最佳逼近问题,给出了最佳逼近度的估计式。研究结果对误差估计、精度分析可提供必要的理论分析依据和参考数据。     

概率约束规划问题的一个光滑近似

许多有重要价值的实际问题均属于概率约束问题,该类问题通常是非凸的且非光滑的,有效的求解方法多集中于凸近似方法.基于Sigmoid函数,将概率约束函数光滑化并建立相应的光滑近似问题,通过收敛性分析,证明了在适当的条件下,当参数充分大时,光滑近似问题与原问题等价,且光滑近似问题的最优值和最优解集分别收敛到原问题的最优值和最优解集.     

一种有理曲线多项式逼近的方法

文章讨论了有理曲线的多项式逼近问题,采用L2准则作为度量的标准,考虑将有理曲线表达式中的分母部分‘去掉’,将逼近的式子做变形。这种方法避免了有理函数的积分问题,降低了运算的难度。通过相应的数值实例可以知道：在无端点限制时具有良好的逼近效果;插值端点时,可以通过提高逼近多项式曲线的次数达到较好的逼近效果;在端点处保持几何连续性时,通过非线性规划问题的解决,得到不错的逼近曲线。     

具有两条边界影响的非凸单个守恒律的整体弱熵解

使用折线逼近法,对具有两条边界影响的非凸单个守恒律初边值问题构造了整体近似解,并证明其收敛到初边值问题的整体弱熵解.     

近似边界元方法及其收敛性分析

以Ｌａｐｌａｃｅ方程Ｄｉｒｉｃｈｌｅｔ问题为例,为椭圆边值问题近似边界元法的建立及其收敛性分析提供了一种框架性的工作。文中给出了近似基本解的确定方法,具近似基本解的离散边界变分方程解的存在惟一性定理以及近似解的误差估计,特别给出了近似基本解中截断数和离散网格宽度应保持的匹配关系,文末给出了数值算例。     

利用H-J-B方程的粘性逼近求解非线性最优控制

利用李级数离散控制系统，逼近最优轨道，并利用H-J-B方程的粘性逼近估计值函数．进而借助动态规划原理，把非线性最优控制的数值求解转化为一组正定二次规划的求解．对一个非线性的动态规划过程进行线性化的逼近，这在理论上简化了非线性最优控制问题求解的困难，从实际计算数学的角度看，这也将加快非线性最优控制数值解的计算速度。     

矩阵最小剩余问题及其最优近似问题的对称解

主要给出了矩阵的最小剩余问题及其最优近似问题的对称解.首先,分别给出了与矩阵最小剩余问题及其最优近似问题等价的线性方程;其次,用广义奇异值分解得到了与最小剩余问题等价的线性方程的对称解,即最小剩余问题的对称解;最后,通过寻求与最优近似问题等价的线性方程的对称解,从而得到了矩阵的最优近似问题的最优近似解.     

多维空间不均匀网格差分格式的稳定性判别法

讨论了多维空间中关于一个坐标面的正负两边具有不均匀网格的差分格式的稳定性,依据Michelson理论,应用付氏分析法把其它坐标的对偶变数作为参数,因此,问题化为单个变量情形的不均匀网格差分格式的稳定性问题,因此可以应用Kreiss稳定性判别法来处理这个问题。