可分离的二次背包问题的一种直接算法

二次背包问题是一个NP hard问题.给出一般的可分离二次背包问题的一种快速求解的直接算法,分析可分离连续二次背包问题的结构特性,并研究此问题最优解与拉格朗日系数λ的关系.在此基础上,提出通过调节λ来找到可分离二次背包问题的局部最优解的算法,此算法的计算复杂度为O(n).     

二次背包问题的秩二松驰

把对最大割问题进行秩二松驰的思想应用到二次背包问题上,得到二次背包问题的秩二松驰模型.应用罚函数法求得该模型的最优解,再利用扰动算法将该最优解转化成二次背包问题的解.     

线性分式函数的迭代公式与还原周期

文[1]得出了线性分式函数的迭代公式[1],文[2]、文[3]探讨了几次迭代还原函数的构造定理[2][3],而定理不具有普遍性。利用高等代数知识推导出线性分式函数的另一迭代公式,用特征根之比得出还原周期,由此构造了任意次迭代还原函数。     

二元Thiele型向量插值连分式的系数算法

本文给出了文[1]中二元向量插值连分式的系数算法,给出的数值例子说明了这种算法的有效性。     

解无约束最优化问题的一个非单调BFGS信赖域算法

在文[19]的基础上,给出了一个解无约束最优化问题的非单调BFGS校正的信赖域算法.此算法具有较好的性质,所给的BFGS校正的具有二次约束的信赖域子问题总保证是严格凸二次规划.在适当的条件下此算法具有全局收敛性和Q 二次收敛性.     

无参数变异的二进制差分进化算法

鉴于差分进化算法在解决复杂连续问题上的优良性能,针对0-1变量的特点,提出了一种用于求解0-1规划问题的二进制差分进化算法(BDEPM).与采用离散变换和逻辑运算的改进算法相比,BDEPM算法中的变量采用二进制编码方式,在进化过程中无需变异率,即可根据个体间的差异直接在离散域内进行变异,算法的思路清晰、结构简单、控制参数少、易于理解和实现.将BDEPM用于求解0-1背包问题,针对其约束提出了一种二次贪婪变换的修复策略,两个背包实例的仿真对比实验验证了BDEPM算法的优越性.     

0-1背包问题的非线性降维近似算法

求解0-1背包问题的精确算法不能在较短时间内求解大规模0-1背包问题,使其实用性受到限制.针对该问题,给出求解0-1背包问题的非线性降维算法,并进行了数值实验,验证了算法的有效性.该算法属于近似算法,相对其他一些近似算法,计算结果更为精确.     

求解0-1背包问题的混合遗传算法

对于0-1背包问题设计一种价值密度,并在此基础上提出求解0-1背包问题的混合遗传算法.经大量数值实验比较该方法与传统方法及简单遗传算法,结果表明算法能有效求解0-1背包问题.     

Overton算法收敛性的一个结论

Overton 在[1]中对一般最优场址模型给出了一个具二次终端敛速的算法.但未能证明该算法的收敛性.本文在一定条件下证明了 Overton 算法具有全局收敛性.     

带满意条件不可微的分式极小—极大化问题的最优性条件

本文指出了[1]中的错误,把[1]中讨论的问题扩充成了带满意条件不可微的分式极小—极大化问题。在较弱的假设条件下,利用不同于[1]中的方法讨论了扩充问题的最优性条件。     

求解带非凸二次约束的广义二次分式规划最小值的全局算法(英文)

基于最近发展的单调优化理论,提出了求解带非凸二次约束的广义二次分式规划最小值的全局算法,给出了算法的收敛性证明. 数值实验表明了该算法的可行性和有效性.     

一类二次二层规划的平衡点算法

Manoel Campelo[1]借助线性规划的单纯形算法,给出了求解线性二层规划的平衡点算法.本文借助线性规划的单纯形法和二次规划的Lemke算法,给出求解一类非线性二层规划的平衡点算法,并给出算例说明算法可行性.     

基于遗传算法求解0—1背包问题的算法探讨

0-1背包问题是一类典型的组合优化问题,并且是NP完全问题,具有重要的研究意义.介绍了贪婪算法和基本遗传算法求解背包问题的设计思想,提出了基于贪婪算法的混合遗传算法求解0-1背包问题.实验结果表明改进的遗传算法有更好的近似解.     

有序组合树法求解0-1背包问题初探

以0-1背包问题为研究对象,建立数学模型,采用有序组合树法对中小规模的背包问题进行求解.与传统的贪婪算法相比,该算法更容易找到最优解.并通过实例说明该算法对解决中小规模的0-1背包问题是行之有效的.     

一种改进的模拟退火算法求解0-1背包问题

从增强算法收敛性和减少参数依赖性的角度出发,提出应用改进的模拟退火算法求解0-1背包问题.对模拟退火算法有所改进,并有效地克服它的弱点,使其在优化性能,优化效率和可靠性方面有明显的优越性.阐明了用该算法求解0-1背包问题的具体实现过程,并通过实际数值计算和结果比较表明,该算法在求解0-1背包问题优于传统的模拟退火算法,并且得到更有效的近似解.     

求解全局优化问题的一种新方法

局部最优性必要条件是用来设计局部优化算法的一个主要工具。本文将介绍求解全局优化问题的一种新的方法：利用全局景优性器件（最优性必要备件[NC]和最优性充分备件[SC]）来研究一类{0,1}双值混合二次规划问题的一些最优化算法。首先利用其全局最优性必要条件[NC]来研究这类双值混合二次规划问题的局部最优化算法,然后针对于这类{0,1}双值混合二次规划问题,研究一类特殊的辅助函数Fr,x（x）来克服现有的局部极小点,最后利用所碍到的辅助函数Fr,x（x）和局部优化算法LOMMQP以及全局最冼性充分条件[SC]来得到具有一定终止准则的全局最优化算法（GOM）。     

多背包问题的计算

本文讨论二个附加限制的多背包问题:限定总件数的多背包问题和0、1多背包问题,给出了它们的动态规划算法。限定总件数的多背包问题的算法所需的空间为O(BM),时间为O(nBM+kB~2),0、1多背包问题的算法所需的空间为O(min{2~(kn/2),nM~k}),时间为O(min{k·n~(kn/2),knM~k}),其中n为物品的种类数或件数,k为背包数,M=max{M_i:1≤i≤k},M_i(1≤i≤k)是第i个背包允许的最大重量,B是允许装入的最大总件数。     

基于混合蛙跳算法的背包问题求解

混合蛙跳算法(SFLA)是一种全新的后启发式群体进化算法,具有高效的计算性能和优良的全局搜索能力.背包问题是一个典型的 NP完全问题.首先建立了背包问题基于 0/1规划的数学模型,阐述了混合蛙跳算法的基本理论.针对离散搜索空间,提出了SFLA的改进算法,应用该算法解决了背包问题.在实例上的运行结果表明本文方法的可行性和有效性.     

关于同余式2n≡4(mod n)

用模幂算法计算出同余式2n≡4(mod n)在3≤n≤1011范围内的所有奇数解.利用由二次剩余推出的一个结论,提高了算法效率,解决了[2]、[3]中提出的一个问题并提出了与此奇数解相关的新问题与猜想.     

一种广义互补问题的磨光方法

文章基于文献[1]中一种广义互补问题的转化模型，建立了一种磨光牛顿算法，并在适当的条件下，证明了这种算法的超线性收敛性和Q-二次收敛性．