求解整数规划问题的微粒群算法

针对整数规划问题的特点,提出了一种在整数空间中进行进化计算的PSO算法,使微粒群的进化限于整数空间.仿真实验结果验证了方法的正确性与有效性.     

基于种族优生的进化规划用于混合非线性整数规划

混合非线性整数规划是在许多工程应用中经常遇到的重要问题。本文提出一种基于种族优生的进化规划算法用于求解混合非线性整数规划。一方面，该算法基于多种群并且每一代都选择各种群的最优秀个体作为下一代的种群祖先。另一方面，该算法的进化步长、种群规模和处理约束条件时所取的参数在进化过程中是动态变化的。实验表明该方法求解混合非线性整数规划问题的仿真结果优于现有的研究成果(GA，ES，SA)。     

赋权有向图中最小生成树问题的显式整数规划模型

就具有不对称权重的有向图中的最小生成树问题,本文首次建立了相应的显式整数规划模型,这一模型可以成功地运用整数规划软件包如Ｌｉｎｄｏ等求解。并进一步将这一模型推广到随机最小生成树问题,也即具有随机变量权重的有向图中的最小生成树问题,并设计了相应的求解算法,给出了数值例示。     

整数规划的一种线性规划解法

根据凸分析理论和单纯形法原理，提出了整数规划的一个线性规划解法。该方法主旨是将整数规划问题的离散的可行集填充成一个连续的单纯形，这样原整数规划问题就化为该单纯形上的一个新的线性规划问题。利用单纯形法求解该线性规划问题，便可得到整数规划的最优解。且进一步提出并证明了指派问题的线性规划解法。     

求解整数规划的一种仿生类全局优化算法——模拟植物生长算法

针对整数规划全局优化问题所首次提出的模拟植物生长算法,是一种源于大自然的仿生类随机算法.该算法从植物的向光性特点出发,将整数规划的可行域作为植物的生长环境,根据各可行解目标函数的变化情况确定植物的生长信息(形态素浓度),进而模拟出向光源(全局最优解)迅速生长的植物生长动力学模型.经过对无约束和有约束两类具有多个全局最优解的非线性整数规划问题的具体求解,取得了满意的效果.     

中国邮递员问题的整数规划模型

基于无向图的传统中国邮递员问题,给出了相应的显式整数规划模型,应用整数规划软件包求解可以方便地确定相应问题的最优投递路线,进一步地,讨论了一类基于有向图的广义中国邮递员问题,给出了相应的显式整数规划模型;并研究了随机中国邮递员问题,建立了相应的确定型等价模型.举例说明了各种模型的有效性.最后,讨论了中国邮递员问题的可能推广及其建模问题.     

双旋转货架拣货路径优化策略

讨论了由一个拣货员负责的双旋转货架系统,考虑拣货员每次拣取货物所需时间不同,目标是寻找一种最优拣货顺序使得总拣货时间最小。该问题被证明为强NP-难问题,提出了几种启发式算法寻找最优拣货顺序,并对相关模型及算法进行模拟测试以证明其有效性,为方法选择与应用提供了依据。     

混流生产线平衡的动态规划及启发式方法

本文利用多级存贮和多级持有成本概念以及连贯排序特性，将混流装配系统转化为一个序列系统，并提出了可以使包括劳动力成本、存贮成本以及装卸成本在内的总成本极小化的计算方法。最后，通过运算结果证明了所提算法应用于混流线设计的有效性。     

项目附加资源优化的整数规划算法

根据网络计划技术中的关键线路法ＣＰＭ的时间参数分析,提出了一个工程项目建设过程中附加资源的混合整数规划模型,使建设项目在充分利用自身已有资源的前提下得到附加租赁机械设备和附加资源的使用安排计划,并使所支付的费用最低     

静态武器目标分配问题的攻击界整数规划求解方法

静态武器目标分配(weapon-target assignment, WTA)问题的直接表现形态是非线性.在不丧失模型最优解的前提下,本文把WTA问题建模为整数线性规划(ILP)模型,并提出在最优武器分配方案中攻击特定目标的武器数量存在上界(攻击界).在采用启发式方法限定攻击界后,WTA问题的ILP模型的维数被大规模降低,使得求解能够在短时间内完成.与近年来发表于国内外期刊上的算例进行试算比较,结果显示本文提出的方法在求解速度和求解优化程度方面具有明显的优势.     

Optimal set integer programming algorithm for multiple maneuvering targets tracking in clutter

The aim of this paper is to solve the problems of multitarget tracking in clutter. Firstly, the data association of measurement-to-target is formulated as an integer programming problem. Through using the linear programming (LP) based branchand-bound method and adjusting the constraint conditions, an optimal set integer programming (OSIP) algorithm is then proposed for tracking multiple non-maneuvering targets in clutter. For the case of maneuvering targets, this paper introduces the OSIP algorithm into the filtering step of the interacting multiple model (IMM) algorithm resulting in the IMM based on OSIP algorithm. Extensive Monte Carlo simulations show that the presented algorithms can obtain superior estimations even in the case of high density noises.     

A novel mixed integer programming formulation and progressively stochastic search for capacitated lot sizing

The capacitated multi-level lot sizing problem is to schedule a number of different items with a bill-of-materials structure over a horizon of finite periods.To advance techniques of solving this class of problems,this paper proposes a new mixed integer programming formulation.Theoretical proofs and computational tests are provided to show that this formulation is able to provide better linear programming relaxation lower bounds than a previously-proposed strong mixed integer programming formulation.Based on the new strong formulation,a progressively stochastic search approach is proposed for solving the problem.Computational results showed that the approach generates high quality solutions,especially for problems of large sizes.     

ALLOCATING REPAIRABLE SYSTEM＇S RELIABILITY SUBJECT TO MINIMAL TOTAL COST - AN INTEGER PROGRAMMING APPROACH

Reliability allocation problem is commonly treated using a closed-form expression relating the cost to reliability. A recent approach has introduced the use of discrete integer technique for un-repairable systems. This research addresses the allocation problem for repairable systems. It presents an integer formulation for finding the optimum selection of components based on the integer values of their Mean Time to Failure （MTTF） and Mean Time to Repair （MTTR）. The objective is to minimize the total cost under a system reliability constraint, in addition to other physical constraints. Although, a closed-form expression relating the cost to reliability may not be a linear; however, in this research, the objective function will always be linear regardless of the shape of the equivalent continuous closed-form function. An example is solved using the proposed method and compared with the solution of the continuous closed-form version. The formulation for all possible system configurations, components and subsystems are also considered.     

求QoS路由的整数线性规划方法

QoS路由的任务是在网络中寻找一条满足多个约束条件的路径使网络资源的利用达到最优. 该问题是一个NP-完全问题. 提出了一种新的基于整数线性规划模型选择路由的方法. 思路是将复杂约束引入到目标函数作为罚项, 得到一个松弛整数线性规划问题. 因为约束系数矩阵是全幺模矩阵, 松弛问题可以通过线性规划很快地求解. 拉格朗日乘子的调整用罚函数的方法很容易计算. 数值实验表明提出的方法是有效的.     

基于双层规划模型的制造业选址布局优化方法研究

经济全球化趋势和全球多式联运网络的形成推动了资源的自由流通和优化配置,改变了制造产业的空间分布形态.本文针对经济全球化背景下制造产业的选址优化问题,提出选址优化与分布-分配相结合的双层规划模型.在模型中运输网络被拆分成原材料运输网络和产品运输网络,上层模型用于确定产业的选址方案和原材料及产品流量的OD矩阵,下层模型用于计算OD流量在运输网络中的交通流特征.为求解模型,设计遗传算法和Frank-Wolfe算法相结合的启发式求解算法,并以中国钢铁制造产业的选址为例验证模型的可行性.结果表明该方法具有实用性,可以有效帮助决策者实施制造产业的选址决策.     

非线性约束最短路问题的启发式算法

多约束QoS路由优化是当前网络研究中的一个重要课题,而受限最短路问题(RSP)是QoS路由的一个基本问题。它是NP-完全的,并有许多具有多项式时间和伪多项式时间的启发式求解算法。然而这些方法只能求解一些带有线性约束的RSP。对一些非线性的约束(比如丢失率约束)大都用数学方法转化成线性约束来求解,这增加了问题的复杂性。本文提出了一种新的具有伪多项式时间的启发式算法来求解这类带非线性约束的RSP。主要思想是将非线性约束作为检验条件来使用。当每得到一个解时,检查解是否满足非线性约束。如满足,则得到最终解;否则在原问题中添加一个线性约束。该新约束将去除已经找到的解,从而使原问题的解空间进一步缩小,直到得到最终解。仿真算例说明了算法的有效性。     

洪水灾情评价的遗传程序设计方法

洪水灾情评价在洪水灾害分类管理决策中具有重要的指导意义,其关键问题就是在评价模型的结构未确知时,如何建立合适的模型来描述以灾情评价指标值为系统输入与以灾情评价等级值为系统输出之间所隐含的复杂关系。为此,提出了用FORTRAN语言实现洪水灾情评价的遗传程序设计新方法(GP-EFDL)。研究结果说明,GP-EFDL可在较大的程序搜索空间中获取一个最佳函数表达式,来反映洪水灾情评价系统的输入与输出样本数据系列所隐含的关系,在自然灾害系统建模、预测和控制等计算机程序自动设计中具有应用价值。表4,参13。     

基于时间约束的多源多品种配送系统模型及一种启发式算法

配送系统设计时,除了使系统的总费用最小外,还要满足各需求点对配送时间的要求。在说明了建模的假设条件后,建立了考虑时间约束的多源多品种配送系统模型,并根据模型的特殊结构开发了相应的启发式算法,最后用实际调研的数据作为算例对模型进行了数值演算。     

热轧钢管主生产计划模型与算法研究

建立了热轧无缝钢管主生产计划问题的混合整数线性规划模型．该模型可归结为多阶段多产品带有能力约束的批量问题，但与传统批量问题存在以下不同：①充分反映了钢管企业与其它行业的不同工艺特点；②目标函数追求最大化现金流而不是最小化成本；③允许订单积压；④考虑库存能力约束；⑤忽略设置时间及成本。但引入了最小生产批量约束．鉴于该问题的NP难性，使用两种基于优化的启发式算法进行求解，并提出两条策略加以改进．