线性规划宽邻域预估校正算法

针对线性规划问题,提出了一种新的内点算法一宽邻域预估校正算法．该算法基于精典预估校正思想,把窄邻域拓展到一个宽邻域里使得算法更快地迭代,给出了该算法的具体步骤,讨论了其算法的计算复杂性,分析结果表明,所给方法是一多项式时间算法,通过数值实验验证该算法的有效性．     

线性规划中预测一校正内点算法的改进

研究线性规划中预测一校正内点算法的改进，获得了复杂度０（√ｎＬ）进一步地在校正部不仅把迭代点重新置于一个小邻域中，而且降低了对偶间隙。     

线性互补问题的组合同伦多项式算法

本文针对线性互补问题提出了一个新的内点方法——组合同伦内点方法,并采用预估校正算法来跟踪组合同伦路径从而得到问题的解,最后讨论了该算法的收敛性,并证明了该算法为多项式算法。     

线性规划问题的相关算法研究

本文主要是针对线性规划问题的相关算法进行了综述和原理的讲解,分别阐述了线性规划发展的历程和线性规划算法的主要数学模型,详细研究了线性规划的主要算法分为单纯形法和内点法的主要原理和算法,并为后续研究提供了一个借鉴方向.     

一般非线性规划的一个预估—校正算法的收敛性

把含等式和不等式约束的一般非线性规划问题转化为只含不等式约束的非线性规划问题,构造同伦方程。在算法中,先计算切方向来求预估点,再用牛顿法求校正点,最后证明了算法的全局线性收敛性。     

对一种线性规划新算法及其改进算法的修正与改进

通过对一种线性规划新算法具体执行过程中的一些关键环节进行分析,证明了边界面上可行方向的充分必要条件,指出了这种算法及其改进算法执行过程中可能遇到的问题,并在此基础上结合核心算法线性规划问题解的特点对算法过程进行了改进修正,使得改进后的算法更合理,更完善.     

用于线性优化的基于核函数的动态步长原-对偶内点算法

In this paper, primal-dual interior-point algorithm with dynamic step size is implemented for linear programming （LP） problems. The algorithms are based on a few kernel functions, including both serf-regular functions and non-serf-regular ones. The dynamic step size is compared with fixed step size for the algorithms in inner iteration of Newton step. Numerical tests show that the algorithms with dynaraic step size are more efficient than those with fixed step size.     

关于预估-校正方法的一点注记

求常微分方程初值问题数值解之预估—校正方法一般只对其局部截断误差的阶进行了估计，而对其具体表达式及整体截断误差没有作相应的讨论。对其具体表达式及整体截断误差作了具体地讨论并得到整体截断误差为O(h^2)。     

线性规划问题的一种新算法

单纯形法和对偶单纯形法是求解线性规划问题最基本的方法。但它们分别要求有一个可行基和对偶可行基 ,这往往不易得到。若添加人工变量 ,则不仅增加了计算量 ,而且由于变量繁多 ,给上机作业带来不便。下面我们将单纯形法和对偶单纯形法综合使用 ,不需添加人工变量 ,即可求出线性规划问题的解。基本思路是 :先用对偶单纯形法求出线性规划问题的一个基本可行解 ,然后再用单纯形法求出最优解。对问题的分析如下 :设标准线性规划问题是 :Ｍａｘｚ =Ｃｘ ,约束条件为Ａｘ =ｂ ,ｘ≥ 0 (1)其中Ａ是ｍ×ｎ阶满秩阵 ,ｍ≤ｎ令Ｂ是此问题的一个基 ,基…     

线性规划非单调一阶段算法

为了获取计算的高效率，有必要修正单纯形算法的原则．本提出了一个新的单纯形一阶段算法．与传统单纯形算法不同的是，新算法不仅不要求目标函数值单调变化，且在一阶段的迭代过程中也不必保持变量的可行性，而是采用纯组合的方法去达到可行．这样摆脱了迭代时的比值检验，减少了每次迭代的计算工组量．理论分析及数值计算结果表明新算法的前景令人鼓舞．     

线性约束非凸二次规划的有限分支定界算法

针对线性约束非凸二次规划问题,从其KKT点出发得到它的一个线性松弛规划,并递归地向该松弛规划中加入原问题的互补松弛条件的线性等式,从而得到一个有限分支定界算法,并对其收敛性进行了证明,经数值实验表明该算法是有效的.     

大规模全有界变量单关联线性规划的分解算法

本文对大规模全有界变量单关联线性规划问题(Ⅰ)提出了一种适应算法,该算法仍具有一般单纯形法的特点,即每次迭代均是在极点之间进行,而且是有限步终止的,算法还具有容量小的特点,这对大规模线性规划问题是很重要的;另外,该算法过程简洁,易于实现。     

基于对数变换的凸二次规划不可行内点算法

基于对数变换和不可行内点算法,对凸二次规划提出了一种新的迭代方向原始-对偶不可行内点算法,并证明了算法的全局收敛性和多项式复杂性,该算法可以看做近期Pan等人关于线性规划算法的推广.     

二层线性规划求顶点的算法

讨论的是上层不带约束的二层线性规划模型,给出了求其所有顶点的算法,此算法为进行二层线性规划的灵敏度分析打下了坚实的基础.     

线性规划中的整点最优解

线性规划在实际问题中有着广泛的应用．若能把实际问题转化成线性规划问题，建立正确的数学模型，通过平移找解法和调整优值法可以求出整点最优解和非整点最优解及最优值的整点最优解问题．     

整数可分离凹规划问题的一个线性规划松弛定界算法

给出了整数可分离凹规划问题的一个线性规划松弛定界算法,该算法中的分枝过程是简单的整矩形二剖分过程,定上界是简单的启发式方法,而定下界过程需要解一个线性规划松弛问题来确定的,数值实验表明所提出的算法是有效的,它可以求解中等规模的问题.     

求解整数规划的一种网格算法

借鉴求解0-1型整数规划的思路,构造以整数规划对应线性规划的最优解为中心的整数解集,并通过增加过滤条件,使得求解既简单又容易.     

整数线性规划问题解法探究

整数线性规划是线性规划问题的重要组成部分，由于整数线性规划问题还没有找到一种有效的解法，目前只能求解中小规模的整数线性规划问题，而建立在线性规划理论基础上的整数解集筛选法是求解整数线性规划问题的一种比较简洁而有效的方法。     

线性规划问题的规范型算法的一种变式

线性规划的规范性算法是从一个不可行初始基出发,通过一种简单而巧妙的初等变换,用原始单纯形算法求得可行基的方法.然而,规范型算法在初等变换过程中,需要更换系数矩阵和右手边向量,增加了计算工作量.在此提出了一种基于人工变量的单纯形变式,当确定不可行初始基之后,在每个约束方程中添加一个相同的人工变量,若右手边项为负值,其系数设置为-1,否则设置为0.这样,以人工变量作为入基变量,以最负右手边项所在行为枢轴行,进行旋转变换,就可将右手边全部化成非负项,而且与规范性算法产生的结果完全相同,但避免了初等变换产生新的系数矩阵的计算.最后,通过大规模数值试验对提出的变式与规范型算法进行了比较.结果表明,所提出的变式所用的总迭代次数要少,且在每个问题上都耗费更少的计算时间.