背包问题的两阶段动态规划算法

本文通过理论分析给出了背包问题的两阶段动态规划算法，用例题说明了其求解过程。在计算机上运用本文所述算法和背包问题的动态规划算法求解了大量例题。解题实践说明，对于大中型背包问题，两阶段动态规划算法由于只要求对少量变量进行排序而使解题时间大为缩短，是一种值得推荐的算法。     

多目标非线性规划的可行方向交互算法

本文提出一个求解多目标非线性规划问题的交互规划算法．在每一轮迭代中,此法仅要求决策者提供目标间权衡比的局部信息．算法中的可行方向是基于求解非线性规划问题的Topkis－Veinott法构千的．我们证明,在一定条件下,此算法收敛于问题的有效解．     

运用动态规划算法求解集值折扣{0-1}背包问题

针对生产不同类商品需选择不同生产机械和模具的实际问题,提出折扣{0-1}背包问题(D{0-1}KP)的扩展模型,即集值折扣{0-1}背包问题(D{0-1}KPS).首先对该类背包问题进行理论分析,构造D{0-1}KPS的子模型D{0-1}.KPS(k,γ),然后基于D{0-1}KPS(k,γ)得到问题求解的递推公式,并...     

求解非线性规划问题的一类对偶算法

本文提出了一类求解不等式约束非线性规划问题的构造性对偶算法,我们证明在适当的条件下,势函数的罚参数存在一个阀值,当罚参数小于这个阀值时,由这一方法所产生的序列局部收敛于问题的一个Kuhn-Tucker解,我们也建立了解的依赖于罚参数的误差上界,最后,我们给出了一个特残势函数的数值结果。     

非线性互补问题的水平值估计算法

本文研究非线性互补问题（NCP）的求解算法，先将NCP转化为约束全局优化问题（CGOP），然后直接移植求解问题（CGOP）的水平值估计算法^[4,5]来求解问题（NCP）．文章证明了算法对于NCP是收敛的，数值实验说明了算法的有效性．     

混沌演化算法求解背包问题

0 引言现实世界的许多优化问题属于动态优化问题一类．我们求解此类问题的目标,是设计一种自适应算法,能够在变化的问题环境中连续追踪最优解．演化算法是基于自然界     

一类非线性规划问题的信赖域内点算法

本文对约束为线性的一类非线性优化问题提出了一种依赖域内点算法的,其中约束非负性要求一个仿射变换阵实现,其子问题变成了与个带仿射变换的线性等式约束的求解,我们证明了算法的有效性,在一定条件下证明了由算法产生的序列收敛到优化总理２的一阶稳定,点。     

非线性0-1规划问题的蜂群算法

针对非线性0-1规划,提出采用一种智能优化算法——蜂群算法进行求解.描述了蜂群算法的实现过程,并在计算机上编程予以实现.经大量实例测试,并与其它算法进行比较,获得了满意的结果.说明了蜂群算法在解决非线性0-1规划问题上的可行性与有效性,同时具有良好的优化能力..     

非线性规划问题的一种高效数值算法

提出求解一类非线性规划问题的有效数值算法,利用新引入的映射代替约束函数的梯度,在较弱的条件下,给出算法的收敛性证明.应该指出的是,结果在很大程度上改进了已有的结果,使得该算法能够处理更大一类非凸优化问题.     

非线性的规划问题

我们知道,线性规划研究的是线性约束条件下线性目标函数的最值,那么类似的会有非线性的规划问题,主要是下面三类问题:(1)非线性约束条件下求线性目标函数的最值;(2)线性约束条件下求非线性目标函数的最值;     

基于一维搜索和动态调节的非线性规划PSO算法

对非线性规划问题的处理通常采用罚函数法,使用罚函数法的困难在于参数的选取。本文提出了一种解非线性规划问题的新PSO算法(NSDPSO),该方法融入了一维搜索和动态调节技术,使NSDPSO很好地克服了标准PSO算法在前期收敛较快而在后期易陷入局部最优的缺陷。另外,文中还给出了一种新的适应度函数及选择算子,使算法在选择下一代时保持群体中不可行解的一定比例,这样不但能有效地增加群体的多样性,而且可以避免传统的过度惩罚,使群体向最优解逼近。最后的数据实验表明该算法对非线性规划问题求解是非常有效的。     

绣字问题及其动态规划算法

一、问题的提出如何用最短的线在织物上不间断地绣一个汉字是一个有趣的图论问题。一个由n条直线段组成的汉字可以看成是一个有2n个节点的图G。每条线段连接一对顶点,n条线段构成G的一个完美对集M。如图1中的“六”字,4条直线段连接了8个顶点。将顶点间的距离作为顶点间连线的权,则问题变为如何寻找一条经过所有M中元素的路P,使P中边的权和为最小。由于顶点间的连线是任意的,P交替地通过M中元素和非M中元素,所以问题的实质是在一个2n阶的完全图中找一条M交错路,     

一类最优指派问题的动态规划算法

考虑一类指派问题：欲把m项工作指派n个人去完成（m≥n）。要求每项工作只能由一个人来做,第i个人可以同时做bi项工作,其中bi(bi≥1）是待求的未知数;i=1,2,…,n,满足∑^ni=1bi=m,假定已知第i人做第j项工作所用的时间cij≥0,i=1,2,…,m。中给出了求解上述问题最优指派（即使总耗用时间最小）的动态规划解法。     

约束非线性规划的神经网络算法

神经网络具有内在大规模并行运算和快速收敛特性,它在最优化技术上的运用近年来受到广泛的重视。本提出一个新的求解一般约束非线性规划的神经网络模型,它具有全局收敛性和广泛的适用性,是求解一般非线性规划问题的新工具。理论分析和模拟计算均表明了模型的有效性。     

改进的非线性整数规划算法

通过对LUUS随机搜索算法的分析，本文首次提出了一种改进的随机定向搜索法（MRDISA）通过实例计算，说明该算法的优点是最优解的可靠性不受初始值X^(0)和初始搜索范围R^(0)的影响，并可用于求解高维约束非线性整数规划问题。     

用非线性方程组求解等式约束非线性规划问题的降维算法

本文研究线性和非线性等式约束非线性规划问题的降维算法.首先,利用一般等式约束问题的降维方法,将线性等式约束非线性规划问题转换成一个非线性方程组,解非线性方程组即得其解;然后,对线性和非线性等式约束非线性规划问题用Lagrange乘子法,将非线性约束部分和目标函数构成增广的Lagrange函数,并保留线性等式约束,这样便得到一个线性等式约束非线性规划序列,从而,又将问题转化为求解只含线性等式约束的非线性规划问题.     

单背包问题的半定松弛算法

首先给出了单背包问题的秩1半定松驰规划，然后在此基础上提出了求解该问题的半定松驰随机算法KSSD。分析结果表明：（1）当σ＞0.19时，算法KSSD的近似比就会超过0.27。（2）算法KSSD中的参数θ对某种大规模情形将不起作用。     

多背包问题的半定松驰算法

The multiple knapsack problem denoted by MKP (B,S,rn,n) can be defined as follows. A set B of n items and a set S of rn knapsacks are given such that each item j has a profit pi and weight wj,and each knapsack i has a capacity Ci. The goal is to find a subset of items of maximum profit such that they have a feasible packing in the knapsacks. MKP (B,S,m,n) is strongly NP-Complete and no polynomial time approximation algorithm can have an approximation ratio better than 0.5. In the last ten years,semi-definite programming has been empolyed to solve some combinatorial problems successfully. This paper firstly presents a semi-definite relaxation algorithm (MKPS) for MKP (B,S,rn,n). It is proved that MKPS have a approximation ratio better than 0. 5 for a subclass of MKP (B,S,m,n) with n≤100, m≤5 and max^nj=1{wj}/min^mi=1={Ci}≤2/3.     

非线性互补约束规划问题的一个新的QP-free算法

本文研究了非线性互补约束均衡问题.利用互补函数以及光滑近似法,把非线性互补约束均衡问题转化为一个光滑非线性规划问题,得到了超线性收敛速度,数值实验结果表明本文提出的算法是可行的.     

基于粒子群算法的非线性二层规划问题的求解算法

粒子群算法（Particle Swarm Optimization，PSO）是一种新兴的优化技术，其思想来源于人工生命和演化计算理论。PSO通过粒子追随自己找到的最好解和整个群的最好解来完成优化。该算法简单易实现，可调参数少，已得到了广泛研究和应用。本文根据该算法能够有效的求出非凸数学规划全局最优解的特点，对非线性二层规划的上下层问题求解，并根据二层规划的特点，给出了求解非线性二层规划问题全局最优解的有效算法。数值计算结果表明该算法有效。