0-1多项式背包问题的一种精确算法

提出了0-1多项式背包问题的一种新的精确算法. 该算法是一个基于拉格朗日松弛和对偶搜索的分枝定界方法. 用外逼近法求拉格朗日对偶问题得到上界,其中拉格朗日松弛问题通过转化为一个网络最大流问题来求解. 为了提高算法的效率,利用两种启发式方法求初始可行解,并用填充和交换的方法改进后得到初始下界; 并且在分枝定界前, 利用所得到的拉格朗日界, 先固定最优解中某些变量的值. 数值结果表明该算法是有效的.     

基于阈值深度优先策略求解非对称旅行商问题的混合分枝定界算法

针对非对称旅行商问题(ATSP)模型计算难问题,提出了一种基于深度和广度方向混合搜索的启发式策略的分枝定界算法.该算法采取有阈值的深度优先加广度加权随机搜索的策略确定分枝节点,通过求解附加弧段约束的分配问题确定下界,通过消除子环的修补算法确定上界,从而有效综合了确定性方法的准确性和启发式方法的快速性.将此算法应用于求解经典TSPLIB库中的全部ATSP问题和热轧调度的仿真研究,表现出了较高的效率和可行性.     

用混合算法求解Flow shop调度问题

研究了流程工业中的Flow shop调度问题,针对免疫算法的随机性和不确定性,结合分枝定界方法的特点,提出了一种基于免疫算法和分枝定界方法的混合调度算法,仿真结果表明该算法不仅能有效解决调度问题,而且提高了搜索效率。     

家禽智慧养殖农场自主投料机器人任务路径规划算法

为了解决家禽智能养殖场饲养环境差、喂养不及时、劳动力需求大等问题,投料机器人的开发迫在眉睫,而路径规划算法的研究是开发饲养机器人的重要环节。饲喂机器人的能耗是路径规划过程中关注的重要内容之一。投料机器人的总重量在投料过程中一直在变化,以最短路径行驶并不意味着其能耗最小,因此需要找到一条最合适的路径而不是最短的路径来使得投料机器人行驶能耗最小。针对以上问题,提出对一定数量的缺料饲料桶采用分支定界算法规划出一条能耗最小的路径;通过最短边集优先选取结合序列不等式方法计算出投料机器人行驶的能耗下界,通过基于Christofides启发式算法计算出投料机器人行驶的能耗上界,同时计算并证明能耗上界与最优能耗的最坏比界。通过在投料机器人的工控机上的运算结果表明：相较于其他求解能耗上下界的方法,所提出方法的求解结果更加精确,能够保证分支定界算法的求解速度更快,同时分支定界算法能快速地求出投料机器人的能耗最小的行驶路径,相较于其他算法而言求解能力更强。     

基于分支定界方法的双边装配线平衡

针时目前研究较少的双边装配线平衡问题，分析、研究了双边装配线的特点及其时平衡的特殊要求，建立双边装配线平衡问题的数学模型，并提出一种分支定界算法来最优化装配线的平衡。该算法采用基于任务、单步、深度优先的方法进行搜索，采用一系列启发式规则来控制分支节点搜索顺序，运用节点支配规则，下界规则，最大缓冲时问规则等时分支节点进行定界，以便迅速找到最优解，算例结果证明该算法具有较好的性能。     

带有二次约束的二次规划问题的一个收缩分枝定界算法

通过解线性规划问题，寻找包含原问题可行域的超矩形，利用剖分技术对这个超矩形进行分枝和收缩以减少算法的迭代次数，从而用线性规划松弛方法来确定原问题在每个小超矩形上的最优值的下界，提出一种新的带有二次约束的二次规划问题的收缩分枝定界算法，并证明了该算法是收敛的．     

基于截断学习效应的流水作业排序问题研究

【目的】给出具有截断学习效应的加权总完工时间流水作业排序问题的最优解。【方法】建立具有截断学习效应的加权总完工时间流水作业排序问题的数学模型,给出优势性质、下界和上界,并采用分支定界算法求解该问题的最优解。【结果】数值模拟结果表明:启发式算法得到的解比较准确,最大误差为 0.4117 ,分支定界算法的效率比较高,处理 100 个工件所用的最大时间不超过 460s 。【结论】计算结果表明分支定界算法能够很快地给出该问题的最优排序。
     

基于截断学习效应的流水作业排序问题研究

【目的】给出具有截断学习效应的加权总完工时间流水作业排序问题的最优解。【方法】建立具有截断学习效应的加权总完工时间流水作业排序问题的数学模型,给出优势性质、下界和上界,并采用分支定界算法求解该问题的最优解。【结果】数值模拟结果表明:启发式算法得到的解比较准确,最大误差为0.411 7,分支定界算法的效率比较高,处理100个工件所用的最大时间不超过460s。【结论】计算结果表明分支定界算法能够很快地给出该问题的最优排序。     

线性两比式和的全局优化新算法

对线性两比式和这一非凸NP-困难的优化问题提出新的全局优化算法.首先把原问题等价地转化为一维参数优化问题.设计了巧妙的下界估计方法,在此基础上提出相应的分支定界算法,该算法最坏情况下可需要O(1/ε)迭代步以求得ε-近似全局最优解.数值结果表明,提出的新算法优于商业软件包BARON.此外,针对线性两比式和问题的一个具有隐凸性(等价于一个二阶锥规划)的应用特例,分支定界算法比基于CVX平台调用SDPT3求解相应的二阶锥规划等价模型效率更高.     

一类可分离的非线性0-1背包问题的分枝定界算法

构造出了一类可分离非线性0-1背包问题的分枝定界算法．分枝的过程是酱通的0-1变量分枝，用简单的取整启发式法确定更好的可行解；而在每个分枝结点处用线性松弛技术确定了它的子问题的一个线性规划松弛逼近。由此得到最优值的一个下界．数值结果表明所提出的算法是有效的．可以求解中等规模的问题．     

不完备信息系统中的确定优势粗糙决策规则提取

以不完备信息决策系统为研究对象,提出了基于确定优势关系的粗糙集模型.在确定优势关系粗糙集的基础上,提出了相对下、上近似约简的概念,给出了求得相对下、上近似约简的具体方法,并在此基础上提取不完备信息系统中的确定优势粗糙决策规则.应用实例表明了所提出的新方法的有效性.     

一类非线性比式和问题的分支定界算法

针对一类带有常系数的非线性比式和全局优化问题(P),给出求解该问题的分支定界算法.首先,将问题(P)转化为问题(Q),两者的变量个数和约束条件的个数相同.然后,利用不等式放缩的方法,建立问题(Q)的松弛线性规划,并结合分支定界算法求解.最后,在此基础上提出区域删减策略,并进行数值实验.结果表明:本算法和删减策略均是有效的.     

基于非凸上界的ranking模型构造算法

现有的ranking算法均通过最小化原目标函数的凸上界构造ranking模型,得到的模型不够精确.为此,文中提出一种基于非凸上界的ranking算法.该算法首先给出一个基于多类支持向量机(SVM)的框架,然后定义面向NDCG的目标函数,在此基础上设计一个比现有的凸上界更为紧凑的非凸上界逼近原目标函数;针对上界函数的非凸非光滑,提出使用凹-凸过程进行凸逼近,并采用割平面算法进行求解;最后,通过在基准数据集上的实验对该算法进行验证,并与现有算法进行对比.结果表明,相比现有的基于凸上界的ranking算法,文中算法得到的模型不但更为精确,而且更加稳定.     

最小阶线性函数观测器设计的最好理论结果(英文)

最小阶线性函数观测器直接估测Kx(t)信号,其中K是任意给定的.这个观测器的极点在设计时也是任意给定的.1986年发表的一个设计程序所要解的公式是将这一设计问题简化成的一组线性方程组,保证设计出来的观测器阶数的上下限也是至今为止最低的.自1986年以来,上述的这一线性方程组已被宣称定性为这一设计问题的最可能简单的公式,上述的观测器阶数的上下限也已被宣称定性为最可能低的上下限.本文进一步证明和宣称定性这一1986年的结果是这一设计问题的最可能好的理论结果.这一宣称定性的重大意义可由以下两个事实来说明.首先这一明确而决定性的宣称定性是该结果发表26年后才作出的.其次相比最近发表的一篇相关论文,该文只是将整个设计问题推导成复杂得多的公式,没能提出真正系统地计算该复杂公式的解的计算程序,却宣称只有该文才得到了整个设计问题的解!     

一种基于事件触发的分布式卡尔曼一致性滤波算法设计

针对无线传感器网络中存在的通信带宽受限等问题,设计了基于事件触发的分布式卡尔曼一致性滤波算法.采用增量发送的传输机制,每个传感器仅在当前时刻观测值与最新触发时刻观测值之间的差值平方超出阈值时,才将观测值发送到相应的估值器.而每个估值器都可以通过时间触发的规则从其邻居节点接收到估计值.为了避免估值之间互协方差矩阵的计算,通过局部最小化方差的上界提出了事件触发的分布式卡尔曼滤波器.基于李雅普诺夫方法证明了算法在均方意义下的指数有界性.数值仿真验证了事件触发的阈值越小,通信率越高且滤波器的估计精度越高;否则,通信率越低且估计精度越低.     

优势变精度粗糙集在UCAV威胁估计中的应用

针对对象属性包含偏好信息及对象属性数据可能存在噪声或者一定程度的不完整的问题,在对经典粗糙集理论分析的基础上,引入优势变精度粗糙集方法,给出了优势变精度粗糙集算法的具体步骤,并结合UCAV作战特点,将其运用到UCAV威胁估计过程中.建立了基于优势变精度粗糙集方法的UCAV威胁估计决策信息系统,给出了决策系统所包含的条件属性和决策属性,并通过实例进行了分析.由结果可知,该决策方法实现简单,能正确对目标的威胁等级进行估计,且得出的规则以一定置信度给出,保证了规则的一致性,对于包含偏好属性的决策信息系统,该方法可以辨识出规则之间的不相容性.     

改进的PPM数据压缩算法及性能分析和比较

PPM算法在文本无损压缩方面具有比LZ算法更高的压缩率。PPM算法分建模和编码两步，在建模时有两种方法选择上下文模型，一种是固定最大长度上下文，即PPM；另一种是不固定最大长度上下文，即PPM^*．在VC 环境下利用PPM^* D算法编制的压缩软件，通过对文本、图像、声音文件以及可执行文件进行实验，效果令人满意，其压缩率都比Winzip要高．     

带有二次约束的一般二次规划问题的松弛分枝定界方法

考虑带有二次约束的一般二次规划问题的求解，当约束条件为非凸二次函数时，对原问题中的某个二次约束进行凸二次松驰，或在原问题的约束条件中增加一个球约束，使得原问题的可行域包含在松驰二次规划问题的可行域内。采用椭球剖分策略剖分可行域为小 椭球，用投影次梯度算法解松驰二次规划问题的拉格朗日对偶问题，从而获得原问题的一个下界。原问题最优值的一个上界可从迭代过程中的可行点得到，并在迭代过程中得到调整。该算法或在原问题最优值的一个上下界相同时终止，得到原问题的整体最优解；或产生一无限序列，其任一聚点都是原问题的整体最优解。     

A Branch and Bound-Based Algorithm for the Weak Linear Bilevel Programming Problems

Most real-world optimization problems are hierarchical involving non-cooperative objectives. Many of these problems can be formulated in terms of the first (upper level) objective function being minimized over the solution set mapping of the second (lower level) optimization problem. Often the upper level decision maker is risk-averse. The resulting class of problem is named weak bilevel programming problem. This paper presents a new algorithm which embeds a penalty function method into a branch and bound algorithm to deal with a weak linear bilevel programming problem. An example illustrates the feasibility of the proposed algorithm.