带不可用时间段和恶化加工时间的几个多项式可解问题

文章研究了机器带有一个不可用时间段并且加工时间恶化的单机调度问题,考虑了2种不同加工时间函数下的2种目标函数;首先讨论了机器一直可用的情况,证明了2个带恶化加工时间的问题是多项式可解的,在此基础上对机器带一个不可用时间段时的情况进行了讨论,证明了这2种约束下的几个问题的多项式可解性.     

一个矩阵多项式求逆问题的推广

矩阵求逆是高等代数研究的重要问题,建立在此基础上的矩阵多项式求逆问题,因其复杂灵活的形式而成为一个研究难点.从一个二次矩阵多项式的求逆问题出发,运用逆矩阵定义、多项式互素、线性方程组理论给出了该问题的三种解法,并通过第三种方法进一步推得了此类矩阵多项式的求逆公式.     

工件有到达时间最小化最大完工时间的平行机分批排序问题

研究工件有到达时间的最小化最大完工时间的平行机分批排序问题.对于不同的工件到达时间的个数和机器台数都是常数的情形提出了一个伪多项式时间的动态规划算法和一个完全多项式时间框架.     

高等代数中关于多项式内容的两处微观处理

不同于大部分教材中用较为具体的辗转相除法,本文应用第二数学归纳法更为简洁地证明了两个多项式的最大公因式的存在性定理.提取了一个简单的引理:若一个整系数多项式可以写成一个本原多项式和一个有理数的乘积,则该有理数必为整数;在此基础上更为简洁地将整系数多项式在有理数域上的可约问题归结为它在整数环上的可约问题,更简洁地证明了整系数多项式有理根存在的必要性定理.总之,用较为概括简明的方法处理了两个多项式的最大公因式的存在性问题和涉及本原多项式的相关内容.     

基于范数下的反瓶颈Steiner树问题

讨论了在l1范数下的反瓶颈Steiner树问题.对于给定的一个可行解,修改带限制的边权使其成为瓶颈Steiner树问题的最优解,并且在l1范数下边权的修改费用最小.讨论了最优目标值的范围,在此基础上给出了一个求解反瓶颈Steiner问题的多项式时间算法.     

工件可拒绝平行机排序

考虑工件有到达时间并且可拒绝的m台无界平行批处理机最小化最大完工时间的排序问题.如果拒绝一个工件,要花费一定的惩罚费用;如果接受这个工件,在m台机器中的一台上分批加工,定义一批的加工时间为这批中所包含的最长工件的加工时间.目标函数是最小化接受工件的最大完工时间与拒绝工件的费用之和.当m是一个给定的数时,给出了这个问题的一个拟多项式时间算法和一个完全多项式时间近似方案.     

最大延迟限制下两个代理的重新排序

两个代理的重新排序问题是指,每一个代理有一个非中断加工的工件集,两个代理共用一个机器进行加工,每一个代理分别考察依赖于各自工件完工时间的目标函数.针对单机上有限错位和原始工件集最大延迟限制下,使得新工件集的最大延迟或总加工时间和最小的多代理重新排序问题,设计出几个这类问题的多项式或拟多项式时间的算法.     

树网络上的最优有向连接问题

有向网络上的最优有向连接问题是寻求从若干起点到若干终点的连接方式,使连接费用为最小。已知此问题是NP一困难问题。目前的一个研究方向是探讨存在多项式时间算法的特殊情形。本文研究了这样的特殊情形：树网络上所有起点处于同一条路上,建立了多项式时间算法。     

乘积匹配多项式的存在性

假若一个以点积为自变量的多项式不是再生核,则它无法在机器学习的核方法中使用.解决此问题的办法之一是匹配另外一个点积的多项式,使两者乘积成为再生核.在一定条件下,通过解一系列的不等式,得到匹配多项式存在的充分必要条件,并探讨与此条件相关的数列和生成函数列的性质.     

多元多项式的计算时间复杂性

多项式的计算是数值分析领域中一个基本的计算工具。目前,有关一元多项式计算问题的时间复杂性已有很多研究[1]～[3]。本文就多元多项式中的几个主要计算问题进行了讨论,给出了多元多项式乘法、多元多项式的求值、多元多项式的插值、求多元多项式的各阶偏导数值等计算问题的计算时间复杂性上界。与传统算法比较,其工作量的界有了明显的改进,拓广了文[1]、[3]中已有的相应结果。1.多元多项式乘法的时间复杂性上界     

Hamming距离下的最短路逆问题

针对Hamming距离下的最短路逆问题,分析了最优解的性质,给出并证明了问题存在可行解的充分必要条件;利用把背包问题的实例多项式归约到该问题的实例,证明了该问题为NP困难的,为设计该类问题的近似算法提供了理论依据.     

最大独立集问题的表面计算模型

DNA计算是解决一类难于计算问题的一种新方法,最大独立集问题是一个著名的NP完全问题,最大团问题及最小覆盖问题等价于最大独立集问题。本文中,我们尝试将最大独立集转化为0-1规化问题,利用0-1规化问题的表面计算模型求解最大独立集。本文充分说明了NP-完全问题可以相互转化的性质。     

一类自由边界问题的正则性研究

研究一类自由边界问题的正则性,通过函数变换,把原来的自由边界问题转化成新的自由边界问题,通过求解新的自由边界问题,相应的自由边界的光滑性得到提高．     

证券组合模型系数的凸二次规划求解方法

证券组合问题是二次规划问题,在证券组合模型中的协方差矩阵为正定的条件下,利用矩阵理论将其转化为等价的无约束优化问题.并且建立了原问题的K-T点与等价无约束问题的稳定点之间的关系.为证券组合投资的最优化提供科学依据和有效的计算方法.     

M-O模型的拟合优度检验

针对在软件可靠性中广泛使用的M-O模型,考虑了如何判定其是否适合特定的软件系统的问题.首先将该问题转化成了统计中的拟合优度检验问题,然后为该检验问题提出了一个合理的检验统计量,证明了统计量的渐近正态性,并给出了检验的拒绝域.     

CVRP中二维装载问题的研究

二维载重量限制的VRP（2L-CVRP）问题是一种新的组合优化问题,是VRP问题的一个现实延伸。2L-CVRP问题中包含了物流配送中的两个子问题：装载问题和路由选择问题。很多VRP的研究,往往只致力于在路由选择方面进行优化,而忽略装载问题。针对这个问题,本文阐述了三种常用的装载算法,通过提高车辆装载率,减少车辆数目,从而降低成本。最后给出了三种算法的实验对比。     

干的无粘大气环流方程组混合问题的适定性

该文针对干的无粘大气环流方程组的混合问题,讨论其底部边界的混合问题.所采用的分析方法是将该混合问题分解成两部分:一个纯Cauchy问题和一组积分表达式.首先证明了这样的分解与原问题同解,然后用分层方法讨论相应Cauchy问题的适定性,从而得到了原混合问题的适定的充要条件.最后给出了构造适定混合问题解析解的计算方法.     

一类热传导反问题中边界温度场的重建算法

给出了一类二维热传导方程反问题中边界温度场的重建算法。首先将反问题归结为一泛函极小化问题;然后通过对未知边界的有限维逼近,将反问题分解成一系适定的热传导方程正问题;最后根据偏微分方程线性问题的叠加原理,将泛函极小化问题离散为线性代数方程组,再应用Tikhonov正则化方法求解线性代数方程组,从而获得边界温度场的数值解。数值算例表明了本文的算法是有效的,且具有较强的稳定性。     

求解带均衡约束多目标规划问题的一种方法

讨论约束是非线性不等式和变分不等式的多目标规划问 题（简记为VPEC问题）, 即目标为多个均衡约束的数学规划. 给出了多目标VPEC问题的最优 性必要和充分条件, 利用充分性条件将多目标VPEC问题转化为一个与之等价的一般形式的约 束优化问题, 并建立了求解此问题的l₁罚函数方法.     

L_1正则化问题的对偶性理论

L1正则化问题是一个非光滑的无约束最优化问题,在变量选择,数据压缩和图像处理等领域有广泛的应用。给出了L1问题最优解存在的新的必要条件和充分条件,利用这些条件构造出L1正则化问题的一个MondWeir型对偶问题,最后给出了相应的弱对偶定理和强对偶定理。