求解线性规划问题的光滑型牛顿算法

对线性规划的最优性条件,给出一个扩展系统,设计一个连续化的光滑型算法求解该系统。所设计的算法的全局收敛性不需要添加任何假设条件。在每一个迭代点处,只需要解一个线性方程组和做一次线性搜索,比现有求解线性规划问题的连续化方法具有更好的收敛性质。     

线性规划算法在车辆调度中的应用

本文首先介绍了线性规划理论及其在一般运输问题中的应用;然后将其推广到车辆调度问题,提出并建立了一个动态的、开放的现代智能车辆管理调度系统模型;最后对各种模型求解算法进行了比较和分析,并给出了计算结果。     

线性规划问题规范型算法的计算机实现研究

随着科技的飞速发展,现如今世界已经步入信息时代,掌握一定的计算机技能是每一个当代人必备的一项生存手段。然而在计算机专业技术的教学和学习过程中,算法便是计算机编程技术的核心思想,如何将算法研究到位制约着计算机技术学习得好坏,因此,笔者在平时的计算机学习与教学过程中比较关注各种计算机算法的应用,本文重点阐述关于线性规划问题规范算法的计算机实现研究,希望本文的研究成果能够为从事计算机事业和教育界带来一些有意义的帮助。     

线性规划的有效算法

一、记号与假设 设讨论的线性规划为(LP)minf~是cTx{x〔R。自S。门E“卜其中,R。~弋:Ia了x镇b‘,i一1,2,…,m},s。~奄x!x1Q矛‘x毛l},Q,一diag(2‘,2气…,2“),L为给定的正整牧. 假设A~[a,,a:,…,。副’,M一毛l,2,…,m},N~几l,2,…,。},rank(A)一。,{】a、!,,~1,i~1,2,…,、. 如ScM,则记A的第户列中行标在S中的元素按S中的顺序沟成的列向量为击,. 如Z〔N,则记A的第‘行中列标在:中的元素按:中的顺序构成的行向量为A‘:. 如“为一个向量,则记“中正分量的个数为P+(的.记集合s的元素个数为!51. 对任一个x〔R。,记J(,)一{ilajx~b‘,…     

线性规划算法并行特征剖析

由于并行计算机的出现,并行算法的研究已事在必行。该领域的工作,目前大体上可归为4类:从事算法思想的研究,如同步并行、异步并行等;构造并行算法,在各个科技计算分支上都或有所见,其中基本代数运算更有基础意义;改造已有算法,使之具有更高的     

解线性规划加阶算法

51．引言文献门提出了如下一类数学规划问题：有九十l个集会见人，几，··、·，几．求。使满足于约束条件因为通常的数学规划问题仅为其特例，而且它有广泛而深刻的实用价值，引起了我们的研究兴趣二当f（x）与所有i（刘均为线性函数时，就要求一种与之适应的解线性规划的算法．为此，我们研究出了一种解线性规划问题的加阶算法．事实上，在解决实际问题时常常出现下述情形：如研究一个经济行为得出了一个线性规划问题，用单纯形法求得了它的最优解，后发现必须再增加约束条件才能与实际情形相吻合．此情形加阶算法更显示出它的优越性．在…     

线性规划计算机算法的新进展

线性规划（LineaProgammins，简称LP），是运筹学的一个较新分支，是处理线性目标函数和线性约束的最优化方法，有广泛的应用。但是近来，实践中出现的线性规划模型，往往具有几千个变量，500－1500个或更多的约束，手算已无能为力，一般必须用计算机求解。计算机所能理解和接受的，只是按照实际问题所编制的程序。这一系列的计算步骤，即解题步骤，通常即称之为算法。任何一般性的计算方法、计算程序，均可称之为算法。算法有好有坏，我们可以从不同的角度，用不同的标准来衡量和评价一个算法的好坏。但人们关心的主要是随着问题的规模越…     

多项式族稳定性判定问题的多项式算法

利用除零原则,多项式族稳定性的判定问题(系数仿射依赖于参数的情形)可以化为单参数秩2简单二次规划问题.本文用二次规划的理论、Kuhn-Tucker条件,提出了此问题的一个多项式时间算法.可以看到许多重要的结果,如棱边定理和强Kharitonov定理仅是此算法的一个特例.作为简单应用,介绍了区间多项式族Schur问题的一个具体算例.     

快速的多项式平滑型支持向量顺序回归算法

支持向量顺序回归是一种重要的有监督排序学习算法.尽管其优化问题规模与样本数呈线性关系,但在学习大容量数据集时,训练速度仍过慢.为此,提出一种支持二次误差的多项式平滑型支持向量顺序回归(psSVOR)算法,其优化方法包括3个步骤:用两个分段多项式函数分别近似(1+x)+和(1-x)+,优化目标转变为二次可微的无约束问题,从而由Newton-YUAN方法直接求平行的多个决策超平面.给出了分段多项式平滑函数的3个性质及psSVOR的收敛定理.另外引入简约核提高非线性psSVOR的优化速度.多个公开数据集及LETOR OSHUMED的实验表明,与传统方法相比,psSVOR的顺序回归性能并不逊色,而训练速度显著快.     

块角型约束线性规划问题的内点分解算法

块角型约束线性规划问题的内点分解算法吴力（中国科学院计算数学与科学工程计算研究所）ＡＤＥＣＯＭＰＯＳＩＴＩＯＮＡＬＧＯＲＩＴＨＭＦＯＲＬＩＮＥＡＲＰＲＯＧＲＡＭＭＩＮＧＰＲＯＢＬＥＭＳＷＩＴＨＢＬＯＣＫＡＮＧＵＬＡＲＣＯＮＳＴＲＡＩＮＴＳ￥ＷｕＬｉ（...     

基于密切多项式近似的多项式插值算法框架

多项式插值技术是近似理论中一种常见的近似方法,被广泛用于数值分析、信号处理等领域。但传统的多项式插值技术大多是基于数值分析与实验结果相结合得到的,没有统一的理论描述和规律性的解决方案。为此,根据密切多项式近似理论为图像的多项式插值算法提出一个统一的理论框架。密切多项式近似的理论框架包括采样点数目、密切阶数和导数近似规则三个部分,它既可以用于分析现有的多项式插值算法,也可以用于开发新的多项式插值算法。分析了主流多项式插值技术在密切多项式近似理论框架下的表现形式,并以四点二阶密切多项式插值算法为例详细描述了利用密切多项式插值的理论框架开发新的多项式插值算法的一般流程。理论分析和数值实验表明大多数主流插值算法都属于密切多项式插值算法,它们的处理效果与采样点数目、密切阶数和导数近似规则有紧密的关系。     

带多项式量级约束条件的多商品流BWTSP线性规划

黑白旅行商问题(BWTSP)是近年来出现的新NP-难解问题,根据图中边是否对称可以分为无向BWTSP和有向BWTSP两种.现有无向BWTSP的Ghiani线性规划中约束条件数目为指数多个.权值阈值等于+∞的有向BWTSP通过转换为RATSP问题而存在多项式个约束条件的线性规划.针对一般的有向BWTSP,提出了一种仅包含多项式个约束条件的新线性规划.其基本思想是首先将有向BWTSP问题归约为ATSP问题,然后利用ATSP包含n(n+4)个约束条件的Finke-Claus-Gunn线性规划,通过定义剩余和消耗基数商品流,分析了环路上的弧应满足的约束条件,并证明这些n\\+2+2|W|的约束条件即是基数约束条件;类似地通过定义剩余和消耗权值商品流,得到n\\+2+n+2|B|个权值约束条件. 最终得到原始问题仅包含3n\\+2+7n个约束条件的线性规划.由于无向BWTSP问题和权值阈值等于+∞的有向BWTSP均是一般有向BWTSP的特例,故此结果对于它们同样有效.     

基于线性规划的碰撞检测算法研究

介绍了虚拟环境中一种基于凸多面体面信息对偶线性规划模型(DualModel)的快速旋转和移动物体之间干涉碰撞实时检测方法。该文详细介绍了建模过程和求解步骤,物体由构成凸多面体的三角形面信息表示,而物体的运动由一组虚拟现实环境中的全局移动和旋转矩阵表示。这种数学编程方法具有数据结构简单、算法可靠和速度快等优点,同时能够很好地解决高速(运动帧)碰撞的问题。这一方法通过使用主-对偶(primal-dual)内点方法来解线性规划方程,具有很好的效果,能够检测多物体对之间的碰撞。实验结果表明,基于数学编程的方法相对两种著名的工具包I-COLLIDE和SOLID,具有速度快和稳定可靠的优点,而I-COLLIDE和SOLID工具包基于两种著名的算法:LinCanny(LC)最近特征算法和GJK算法(EnhancedGilbertJohnsonandKeethialgorithm)。     

一个分区线性规划问题及其算法

在生产实际中广泛存在着一类分区线性规划问题:规划Ⅰ.求一X=(x_1,x_2,…,x_n)适合下列约束条件:     

AES算法中的多项式模运算及其性能分析

随着计算机和通信技术的发展,用户对信息的安全存储与保密的需求越来越迫切。高级加密标准（AES）具有简洁、实现速度快、安全性高等优点,在计算机通信和信息系统安全领域有着最广泛的应用,AES算法的分析与研究也越来越受到人们的重视。AES算法中字节替代正逆变换、列混淆正逆变换和轮密钥扩展等多处使用有限域GF（28）上多项式模运算,多项式模运算是AES算法的重要数学基础。文中以列混淆正逆变换为例分析多项式模运算的理论问题及实现思路,对AES的理解和高效实现具有一定的借鉴意义。     

一个新的多项式实根分离算法

本文提出了分离多项式方程P(x)=0的实根的一个新的计算机代数算法,它解决了王湘浩教授在[1]中提出的用连分数变换分离有重根多项式的实根的问题.对于有重根的n次多项式P(x),该算法具有时间复杂性上界O(n~6L~3(|P|_0)),远远优于现有的解决同样问题的计算机代数算法的时间上界O(n~(10)+n~7L~3(|P|_0)).该算法已在计算机代数系统SAC-2上实现.上机实验的结果也初步证实了新算法的优越性.     

整数线性规划的改进分支定界算法

分支定界(B&B)算法是求解整数线性规划(ILP)问题的一种最常用的方法,如何划分问题(分支)和按何种策略选择子问题进行扩展是影响算法效率的两个重要因素.提出了一种改进的分支定界算法,采用伪费用分支策略划分问题,采用深度优先搜索(DFS)策略选择子问题进行扩展,并在Matlab中编程实现.数值实验表明,改进的算法能够有效提高求解效率,当问题规模较大时,改进效果尤其明显.     

不等式约束的非线性规划混合遗传算法

针对带不等式约束的非线性规划问题,提出了一个混合遗传算法。该算法分为全局探测和局部开采两个阶段,全局探测阶段是通过在有潜力的小生境内嵌入单纯形搜索,快速确定有前景的区域;而局部开采阶段则是在最有前景的区域进行单纯形搜索。该算法增强了局部搜索能力并同时保持种群的多样性,有效地解决了遗传算法的过早收敛和局部搜索能力弱的问题。典型非线性规划算例验证了混合算法的效率、精度和可靠性。     

正交多项式拟合在EMD算法端点问题中的应用

经验模态分解(EMD)是由Huang等人提出的一种全新的针对非线性非平稳信号处理的算法.通过EMD,可以把一个信号分解为若干个固有模态函数(IMF),再将这些IMF进行希尔波特变换,从而得到具有真正意义的瞬时频率,因此解决了传统信号处理方法的不足之处。与此同时,EMD算法是一个全新的算法,本身也存在不足,如端点问题。文章在现有的解决方法的基础上,提出了用正交多项式拟合的方法来解决EMD的端点问题,并通过和已有算法的比较来证明这种方法的有效性。     

求解本原多项式的快速算法

本原元和本原多项式是有限域理论中的2个重要的概念.本原元的求解问题是解决实际密码序列问题的前提条件,而本原元的求解问题又可以归结为本原多项式的求解问题.该文结合求解最小多项式的方法给出一个在二元有限域上本原多项式的求解算法,在求解过程中同时给出了相应的最小多项式,并给出了算法相应的效能分析.