带最小批量约束的计划问题及其拉格朗日松弛算法

针对一类带最小批量约束的计划问题, 提出了基于拉格朗日松弛策略求解算法. 通过拉格朗日松弛策略, 将原问题转为一系列带最小批量约束的动态经济批量W-W(Wagner-Whitin)子问题. 提出了解决子问题且其时间复杂度O(T³)的最优前向递推算法. 对于拉格朗日对偶问题, 用次梯度算法求解, 获得原问题的下界. 若对偶问题的解是不可行的, 通过固定装设变量, 求解一个剩余的线性规划问题来进行可行化处理. 最后, 数据仿真验证了算法的有效性.     

解非线性规划的多目标遗传算法及其收敛性

给出非线性约束规划问题的一种新解法。它既不需用传统的惩罚函数,又不需区分可行解和不可行解,新方法把带约束的非线性规划问题转化成为两个目标函数优化问题,其中一个是原约束问题的目标函数,另一个是违反约束的度函数,并利用多目标优化中的Pareto优劣关系设计了一种新的选择算子,通过对搜索操作和参数的合理设计给出了一种新型遗传算法,且给出了算法的收敛性证明,最后数据实验表明该算法对带约束的非线性规划问题求解是非常有效的。     

解非线性约束规划问题的新型多目标遗传算法

给出非线性约束规划问题的一种新解法。把带约束的非线性规划问题转化成为两个目标的多目标优化问题，并为转化后的多目标优化模型设计了一种新型多目标遗传算法，数据实验表明该算法对带约束的非线性规划问题求解是非常有效的。     

基于混合搜索的含逻辑“与”“或”的RM优化算法

相对于标准约束优化问题,广义约束优化问题（或称析取优化问题）的等式或不等式约束条件中不仅包含逻辑“与”关系,还含有逻辑“或”关系.单调速率（RM）优化问题是广义约束优化问题的一个重要应用.目前RM优化问题已有的解法包括函数变换、混合整数规划、线性规划搜索等算法.随着任务数的增多,这些算法的求解时间较长.提出一种基于线性规划的深度广度混合搜索算法（LPHS）,将广义约束优化问题拆分成若干子问题,建立线性规划搜索树,合理选择搜索顺序,利用动态剪枝算法减小子问题的规模,最终求得最优解.实验结果表明,LPHS算法比其他方法有明显的效率提升.研究成果与计算机基础理论中的可满足性模理论的研究相结合,有助于提高可满足性模理论问题的求解效率,促进该理论在程序验证、符号执行等领域的进一步应用.     

简化线性规划模型的方法研究及实现

一般的线性规划模型都存在大量的冗余约束,这些冗余约束势必会干扰线性规划问题的求解,降低解题速度,影响解题效率。如果在求解线性规划问题之前,能够对这些冗余约束进行化简并消去,就能够提高模型中约束矩阵的稀疏度,缩小线性规划问题的规模,且在求解时能节省大量的计算机存储空间和运算时间。提出了一种新的简化线性规划模型的方法,程序实现后试验表明,该简化方法达到了预期的效果。     

分布式约束网络系统的设计与实现

针对工程设计中的一类约束问题,文章结合约束传播算法和区间求解算法,在一定的条件下,给出了多值约束下连续变量的可行值域求解算法。同时基于上速算法设计了一套分布式的计算环境,并给出该系统求解的一个实例。     

非线性循环不变式的自动生成

提出了一个自动生成非线性循环不变式的算法。循环不变式可以表示成一个带参数的多项式的形式,根据断言的归纳特性,将循环不变式的生成问题转变成一个约束求解问题,这个约束求解问题的每个解对应于一个循环不变式,如果约束求解问题仅有零解,则说明不存在该参数多项式形式的循环不变式。该算法在Maple中得到了实现,并通过一些实例说明了该算法的有效性。     

基于雁群启示的粒子群优化算法的几何约束求解

几何约束是约束求解技术中最关键的问题之一.求解一个几何约束问题的最终目的是确定几何图形中每一个几何体的具体坐标位置.几何约束问题可以等价为求解非线性方程组问题.约束问题转化为一个优化问题.本文采用基于雁群启示的粒子群优化算法来求解该问题.该算法受雁群飞行特征启发,一方面将粒子排序,每个粒子跟随其前面那个较优粒子飞行,保持了多样性;另一方面使每个粒子利用更多其他粒子的有用信息,粒子之间的竞争被增强.两个方面的结合将平衡速度和精度之间的矛盾.实验表明,该方法可以提高几何约束求解的效率和收敛性.     

基于约束的调度研究和实现

运用约束程序设计(CP)思想和技术来调度正成为一个新兴的研究领域。文章首先对CP和调度的相关领域知识进行了简要介绍;然后按照CP所倡导的问题建模和问题求解相分离的思想,建立起一般理论调度问题的约束模型,并设计实现了一个基于约束的调度求解算法CBS-1;并对一些典型问题进行了实验,实验结果表明算法提高了约束调度求解的效率和通用性。     

具有未知参数的非线性系统动态优化

针对具有未知参数和不等式路径约束的非线性系统动态优化问题,提出一种新颖有效的数值求解方法.首先,将未知参数视为一个动态优化问题的决策变量;其次,利用多重打靶法将无限维的含未知参数动态优化问题转化为有限维的非线性规划问题,进而在不等式路径约束违反的时间段内,用有限多个内点约束替代原不等式路径约束;然后,用内点法求解转化后的非线性规划问题,在路径约束违反的一定容许度下,经过有限多次步数迭代后得到未知参数值的同时得到控制策略,并在理论上对所提出算法的收敛性进行相应证明;最后,对两个经典的含未知参数非线性系统的动态优化问题进行数值仿真以验证所提出算法的有效性.     

判断具有多线性约束条件的凸空间是否为空的交边算法

本文研究被若干线性约束条件界定的凸空间是否为空的判断问题，此问题在线性规划中有广泛的实际背景。本文提出了一个求解此问题的交边算法，该算法已被编程实现了，实际试算表明，其平均计算时间复杂度不高，是目前求解同类问题的算法中的较优者。     

Step response of a class of second-order non-minimum phase transfer functions†

This paper investigates the problem of controlling a discrete-time linear system with jump parameters. A review of the literature is presented as well as a development of the application of dynamic programming to this class of control problems. Dynamic programming has been applied by many researchers and it was observed that no closed-form analytical solution could be constructed because of the ‘dual’ aspects of the controller. The main contribution of the present work is an algorithm, suitable for computer implementation, for the optimal dual control. The construction of the algorithm is based on transforming the dynamic programming relations into a space of sufficient statistics and using a finite-dimensional optimization procedure to obtain the optimal control as a function of the statistics. This is achieved by first developing a suitable recursive realization of a ‘filter’ which generates the sufficient statistics for the problem and then embedding this filter into the dynamic programming equations. Several examples are presented to illustrate the use of the algorithm for constructing optimal and suboptimal controllers.     

一个线性递归查询算法的设计与实现

旨在解决在演绎数据库中，如何利用递归规则进行递归查询的问题。介绍了一个线性递归查询算法的基本思想，阐述了该算法的设计与具体实现，包括算法采用的数据结构、程序中各功能模块的功能，对算法进行了分析。     

光网络中波长通道优化路由算法研究

通过对波长通道路由问题具体特点的数学分析,将问题分解为多个小规模的线性数学规划模型,设计了一个基于当前解邻域变换的快速搜索算法。模拟试验表明,同启发式算法相比,该算法能在较短的时间内取得更好的优化效果。     

An optimal volume ellipsoid algorithm for parameter set estimation

A recursive ellipsoid algorithm is derived for estimating the parameter set of a single-input single-output linear time-invariant system with bounded noise. The algorithm's objective is to seek the minimal volume ellipsoid bounding the feasible parameter set. Cast in a recursive framework, where a minimal volume ellipsoid results at each recursion, the algorithm extends a result due to Khachian (see Aspvall and Stone, 1980) in which a technique was developed to solve a class of linear programming problems. This extension and application to the parameter set estimation problem have intuitive geometric appeal and are easy to implement. Comparisons are made to the optimal bounding ellipsoid algorithm of Fogel and Huang (1982), and the results are demonstrated through computer simulations     

一类递归查询问题的快速求解算法

提出一个求解一类扩充递归Ｄａｔａｌｏｇ逻辑程序的算法,论证其正确性,并讨论了算法的复杂性。该算法结合了自底向上和自顶向下的逻辑程序求解算法的优点,但比魔集算法简单,易于实现。利用宁可以解决工程数据管理中常遇到的产品零部件装配关系的递归查询问题。     

基于梯形和平行四边形的圆片剪冲下料算法设计与实现

提出一种在矩形板材上引入梯形条带来进行排样的方法,首先用两条平行的分界 线将板材分为两个大小一致的直角梯形段和一个平行四边形段,分别采用递归算法和动态规划 算法确定梯形段和平行四边形段中条带的最优组合,从而确定最优排样方式;再结合线性规划 算法解决圆片下料问题,使得整个下料方案的材料利用率最大化。最后采用大量随机生成的例 题进行实验,实验结果表明该算法能有效提高材料利用率。     

线性递归Da taL og 程序优化算法

提出了线性齐次ＤａｔａＬｏｇ逻辑程序的概念,并为该类程序设计了一个优化的求解算法。在此基础上提出了求解一般线性ＤａｔａＬｏｇ程序的优化算法,该算法利用带有的约束条件的递归调用方法,将线性ＤａｔａＬｏｇ程序求解问题变换成齐次程序的求解问题。算法简单,易于实现,可应用于任何线性ＤａｔａＬｏｇ程序的求解。     

广义Hanoi塔问题的动态规划算法

基于动态规划算法思想，深入分析了广义Hanoi塔问题动态规划分割点的特征，给出动态规划分割点的简单计算公式，使得动态规划算法转化为一个非常简单的递归算法，由此可以迅速产生广义Hanoi塔问题的最优移动序列，从而彻底解决了广义Hanoi塔问题的最优移动序列问题．     

具有模型和实际差异的非线性离散动态系统最优控制

针对模型与实际存在一定差异的情况,提出了一种求解非 线性离散系统最段控制的动态系统优化和参数估计集成（Ｄｙｎａｍｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｓｙｓｔｅｍ Ｏｐｔｉｍｉｚａｔｉｏｎ Ｐａｒａｍｅｔｅｒ Ｅｓｔｉｍａｔｉｏｎ,简称ＤＩＳＯＰＥ）的研究法。推导出一组求解一类有终端等式约束的非齐次的线性两点边值问题的递推公式,对于有终端等式约束的非线线性最优控制问题得到了在计算上易于实现的一种ＤＩＳＯＰＥ