背包问题的性质研究

本主要研究背包问题的一般性质和解的性质。     

一种求解分组0-1背包问题的动态规划法

研究了分组0-1背包问题,提出了一种动态规划解决方法,在物品总数为n个和背包承重量为W时,递推过程的复杂度为O(nW),回溯过程的复杂度为O(n).计算实例表明利用该方法易于找到最优解.     

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

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

基于两阶段混合动态规划算法的龙门吊路径优化

产业界已出现利用多台轨道式龙门吊同时作业以提升集装箱码头装船效率的情况,由于需要确定每台龙门吊的取箱作业集合以及增加了“避免碰撞”、“顺次移动”等现实约束,故其移动路径规划问题在模型建立与求解上比单台轨道式龙门吊更为复杂。本文针对两台轨道式龙门吊同时作业的情形,建立了龙门吊移动路径网络模型,并开发了基于贪婪算法与动态规划的两阶段混合算法,并通过仿真算例,借助与基于实际调度规则所得到的调度方案的对比,验证了模型及优化算法的有效性与实用性。     

运用动态规划算法求解集值折扣{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,γ)得到问题求解的递推公式,并...     

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

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

0-1背包问题的蜂群优化算法

在项目决策与规划、资源分配、货物装载、预算控制等工作中,提出了0-1背包问题.0-1背包问题是组合优化中的典型NP难题,根据群集智能原理,给出一种基于蜂群寻优思想的新算法—蜂群算法,并针对0-1背包问题进行求解.经实验仿真并与蚁群算法计算结果作对比,验证了算法在0-1背包问题求解上的有效性和更快的收敛速度.     

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

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.     

多约束非线性整数规划的一种改进的算法

多约束非线性整数规划是一类非常重要的问题,非线性背包问题是它的一类特殊而重要的问题.定义在有限整数集上极大化一个可分离非线性函数的多约束最优化问题.这类问题常常用于资源分配、工业生产及计算机网络的最优化模型中,运用一种新的割平面法来求解对偶问题以得到上界,不仅减少了对偶间隙,而且保证了算法的收敛性.利用区域割丢掉某些整数箱子,并把剩下的区域划分为一些整数箱子的并集,以便使拉格朗日松弛问题能有效求解,且使算法在有限步内收敛到最优解.算法把改进的割平面法用于求解对偶问题并与区域分割有效结合解决了多约束非线性背包问题的求解.数值结果表明了改进的割平面方法对对偶搜索更加有效.     

一类最优指派问题的动态规划模型

考虑一类指派问题：欲指派m个人去做n项工作(m≥n)，要求每个人只做一项工作，第j项工作可以由b_j个人共同去做，其中，b_j(b_j≥1)是待求的未知数，j=1,2,…,n,满足．假定已知第i人做第j项工作的效益为c_ij≥0,i=1,2,…m;j=1,2,…,n.本文建立了求解上述问题最优指派（即使总的效益最大)的动态规划模型．     

解非凸规划问题的一种连续化方法

针对一类非线性规划问题的解存在的新等价性条件，给出了大范围收敛的连续化方法及证明了收敛性的结论．     

一个关于二次规划问题的分段线性同伦算法

本文发展了一个关于二次规划问题的分段线性同伦算法。该算法可看作是外点罚函数法的一个变体。凡是符合外点罚函数法收敛条件的二次规划问题用该算法均可经有限次轮回运算得到稳定解。大量的关于随机的凸二次规划问题的数值实验结果表明它的计算效率是高的，在某些条件下可能是多项式时间算法。     

半无限规划离散化问题一个两阶段序列二次规划算法

本文研究了求解半无限规划离散化问题(P)的一个新的算法.利用序列二次规划(SQP)两阶段方法和约束指标集的修正技术,提出了求解(P)的一个两阶段SQP算法.算法结构简单,搜索方向的计算成本较低.在适当的条件下,证明了算法具有全局收敛性.数值试验结果表明算法是有效的.推广了文献[4]中求解(P)的算法.     

求解凸二次规划问题的势下降内点算法

1　引　言二次规划问题的求解是数学规划和工业应用等领域的一个重要课题 ,同时也是解一般非线性规划问题的序列二次规划算法的关键 .求解二次规划问题的早期技术是利用线性规划问题的单纯形方法求解二次规划问题的 KKT最优性必要条件[1 ] .这类算法比较直观 ,但在处理不等式约束时 ,松弛变量的引进很容易导致求解过程的明显减慢 .有效集策略是求解二次规划问题的另一类主要技术 .这类方法一般都是稳定的 ,但随着问题中大量不等式约束的出现 ,其收敛速度将越来越低[2 ] .简约空间技术将所求问题的 Hessian阵投影到自由变量所在的子空间中 …     

A o(n logn) algorithm for LP knapsacks with GUB constraints

A specialization of the dual simplex method is developed for solving the linear programming (LP) knapsack problem subject to generalized upper bound (GUB) constraints. The LP/GUB knapsack problem is of interest both for solving more general LP problems by the dual simplex method, and for applying surrogate constraint strategies to the solution of 0–1 Multiple Choice integer programming problems. We provide computational bounds for our method of o(n logn), wheren is the total number of problem variables. These bounds reduce the previous best estimate of the order of complexity of the LP/GUB knapsack problem (due to Witzgall) and provide connections to computational bounds for the ordinary knapsack problem.We further provide a variant of our method which has only slightly inferior worst case bounds, yet which is ideally suited to solving integer multiple choice problems due to its ability to post-optimize while retaining variables otherwise weeded out by convex dominance criteria.     

A INTERIOR POINT ALGORITHM FOR CONVEX NONLINEAR PROGRAMMING PROBLEMS

This paper describes a primal-dual interior paint algorithm for convex nonlinear programming problems subject to linear constraints. The algorithm is based on the path following idea. Each iteration updates a penalty parameter and finds a Newton step associated with the simplified Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem for that parameter. It is shown that the duality gap if reduced at each iteration by a factor of (1 - δ / n~(1/n) ), where S is positive and depends on some parameters associated with the objective function.     

关于二次规划问题分段线性同伦算法的改进

本文利用Ｃｈｏｌｅｓｋｙ分解，Ｇａｕｓｓ消去等技术和定义适当的同伦映射，将关于二次规划问题的分段线性同伦算法加以改进，改进后的算法，对于严格凸二次规划来说，计算效率与Ｇｏｌｄｆａｒｂ－Ｉｄｎａｎｉ的对偶法相当。     

求线性规划问题相容方程组非负解的算法

本文提出一个解线性规划问题的新算法.其最优解是通过求一个相容方程组的非负解而得到.这算法的计算量在最坏情况下是O(mnτ),其中τ是相应方程的m×n矩阵非零元素的个数.     

AN EFFECTIVE SEQUENTIAL QUADRATIC PROGRAMMING ALGORITHM FOR NONLINEAR OPTIMIZATION PROBLEMS

In this paper,a new globally convergent algorithm for nonlinear optimization prablems with equality and inequality constraints is presented. The new algorithm is of SQP type which determines a search direction by solving a quadratic programming subproblem per itera-tion. Some revisions on the quadratic programming subproblem have been made in such a way that the associated constraint region is nonempty for each point x generated by the algorithm, i. e. , the subproblems always have optimal solutions. The new algorithm has two important properties. The computation of revision parameter for guaranteeing the consistency of quadratic sub-problem and the computation of the second order correction step for superlinear convergence use the same inverse of a matrix per iteration, so the computation amount of the new algorithm will not be increased much more than other SQP type algorithms; Another is that the new algorithm can give automatically a feasible point as a starting point for the quadratic subproblems pe     

一类线性规划逆问题及解法

本文讨论了逆ＬＰ问题的更一般的情况,这里称它为广义逆ＬＰ问题,即在知道了一部分变量和价值系数的条件下,求余下的未知的变量和价值系数,将它们合起来组成给定的ＬＰ问题的最优解。显然若知道全部价值系数就成为ＬＰ问题;若知道全部变量就成为逆ＬＰ问题,它是在根据研制应用软件时提出的。文中给出了解广义逆ＬＰ问题的算法,并成功地用于“宏观经济调控系统”等应用软件的研制中,对要解决的实际问题,给出了强多项式算法。