逐次回归的单纯形算法

常出现在稳定的时间序列的线性预报中,对于P阶线性预报问题在[1]中将其归结为线性最小二乘问题:     

一个新的单纯形类算法

提出了一个求解线性规划的新单纯形类算法。它不仅无须引入人工变量，而且在第一阶段中采用无比检验。因此新算法比Arsham最近提出的push-to—pull算法效率更高。此外，本算法的数值稳定性也优于push—to—pull算法。     

方向选择约束单纯形算法

一、引言人们一直致力于求解线性规划的单纯形算法的改进工作.1976年,Powell 发表过降低基维数的改进单纯形算法,这个算法是将基矩阵的一个块用基矩阵的其它块的乘积来表示,虽然实现了降低基维数,节省了存贮空间,却增加了计算次数,减慢了计算速度.Sethi and Thompson 针对线性规划问题也提出过竞争和非竞争约束(candidate andnoncandidate constraints)的概念.他们发现,随机生成的实验问题,其总约束中大约只有15%—25%是竞争约束,并提出了一个仅对竞争约束进行旋转运算的单纯形算法.他们的算法,对某些特殊的线性规划提高了求解速度,但并不减少基的维数,并不节省内存空间,增加了程序复杂性.1984年,Sethi and Thompson 又提出 PAPA 算法,再次利用线性规划问题通常只有少量竞争约束这个事实来提高求解速度.但 PAPA 算法往往要在原问题的可行域外运行.况且,上面提到的各种算法,均不能从理论上表明,它们较标准改进单纯形算法到底节省了多少存贮单元和节省了多少计算次数.     

第一阶段原有单纯形和对偶单纯形算法的计算比较

线性最优化广泛应用于经济与管理的各个领域.在线性规划问题的求解中,如果一个初始基本可行解没有直接给出,则常采用经典的两阶段法求解.对含有"≥"不等式约束的线性规划问题,讨论了第一阶段原有单纯形法和对偶单纯形法两种算法形式,并根据第一阶段问题的特点提出了改进的对偶单纯形枢轴准则.最后,通过大规模数值试验对两种算法进行计算比较,结果表明,改进后的对偶单纯形算法在计算效率上明显优于原有单纯形算法.     

有界变量亏基单纯形算法

为克服单纯形算法中退化现象带来的困扰,本文在文[1]的基础上进一步提出亏基有界变量单纯形算法,并证明了算法的收敛性.     

单纯形算法的一种新改进

一、改进的要点考虑标准线性规划问题(Ⅰ°)其中这样,(x_1,x_2,…,x_(n m))=(0,0,…,0,b_1,…,b_m)是(Ⅰ°)之基本可行解。对标准单纯形算法改进的基本点如下: 1°由(Ⅰ°)得到初始松弛问题(I~1)(I~1) 通常选取 2°由第(I~t)得到松弛问题(I~(t 1))(I~t) 用单纯形算法求解(I~t),记每步单纯形旋转的基矩阵是B~t;基变量足标集是IB~t;基变量取值;按进基规则选取足标是j_o的非基变量x_(jo)换入基内,并且得到向量     

基于线性规划核心矩阵的单纯形算法

本文讨论了线性规划中的核心矩阵及其特性,探讨了利用核心矩阵实现单纯形算法的可能性,并进一步提出了一个基于核心矩阵的两阶段原始一对偶单纯形方法,该方法通过原始和对偶两个阶段的迭代,可以在有限次迭代中收敛到原问题的最优解或证明问题无解或无界．在试验的22个问题中,该算法的计算效率总体优于基于传统单纯形方法的MINOS软件．     

标准型在引入单纯形算法时的作用

单纯形算法是线性规划中的重点难点,教学过程不应过早困扰于繁杂的数学概念和定理证明并忽略标准型的作用,而应围绕最优化解的寻找．可行域顶点的确定,变量取值范围的确定等问题进行组织,使学生对算法先有一个比较直观的了解．然后再逐渐展开,以深化学生对算法的理解．     

单纯形算法的两种部分定价策略

根据Hu和Johnson的原始一对偶单纯形算法原理,提出了两种部分定价策略.给定一组原始一对偶可行解,首先,选择与原始问题简约价值系数为负且对偶松弛变量取零值相应的非基变量作为部分定价变量,再用Dantzig准则的单纯形算法求解该原始子问题.其次,针对原始退化问题,选择相应于原始问题简约价值系数小于某个适当小正数的非基变量进行部分定价,然后应用Bland准则的单纯形算法求解原始子问题,以克服退化可能引起的循环现象.最后,对来自NETLIB和MIPLIB的一些典型算例执行初步数值试验,结果表明,与经典单纯形算法相比,提出的算法具有更好的计算表现.     

对单纯形算法的两点改进意见

本文指出两点:1.按照最速下降规则确定进基和离基变量,既能避免迭代循环,又常减少迭代次数;2.可不直接引入人工变量求初始基可行解,并从一开始就考虑按一定意义下使原目标函数下降最多的原则选择基变量,使得到的初始基可行解尽可能的好。 1.关于最速下降规则设所论线性规划问题由表1给出: 最速下降规则可叙述如下: (A)设R={j|λ_j>0},对每一j∈R,计算     

关于使用最大改进规则的单纯形算法

[5]建立了定理5—3、5—4、5—5，并据此证明了采用该的最大改进规则的单纯形算法是多项式算法。本举例证明了[5]中的定理5—3、5—4、5—5是错误的。     

基于混合单纯形算法的模糊均值图像分割

针对模糊C均值算法用于图像分割时对初始值敏感、容易陷入局部极值的问题,提出基于混合单纯形算法的模糊均值图像分割算法.算法利用Nelder-Mead单纯形算法计算量小、搜索速度快和粒子群算法自适应能力强、具有较好的全局搜索能力的特点,将混合单纯形算法的结果作为模糊C均值算法的输入,并将其用于图像分割.实验结果表明:基于混合单纯形算法的模糊均值图像分割算法在改善图像分割质量的同时,提高了算法的运行速度.     

一个求解线性规划的单纯形-内点算法

根据单纯形方法和大步长路径跟踪算法（Ｈｅｒｔｏｇ，Ｒｏｏｓ和Ｔｅｒｌａｋｙ１９９１），对于具有不等式约束的线性规划问题，引进了一个具有组合特性的内点算法．该方法保留了单纯形方法和内点算法的优点，克服了它们的不足，在任何情况下，这个方法都能快速收敛．数值结果也很好地验证了这个结论．     

关于使用最大改进规则的对偶单纯形算法

本举例证明了[3]的定理10-1是错误的。     

多目标线性规划的一种交互式单纯形算法

本文基于分析有效极点解的有效变量的特点以及在有效点处各个目标函数的数值来得到改进的搜索方向的研究思想,提出了求解目标函数和约束均为线性的多目标线性规划问题的一种交互式算法。该方法可以保证每一步得到的解均为有效极点解,且根据决策者的偏好不断得到改进,直至最终得到满意的最终解。     

模糊线性规划问题的一种新的单纯形算法

提出求解模糊线性规划问题的一种新的思路 ,就是应用单纯形法先求解与 (FLP)相应的普通线性规划问题 ,通过模糊约束集与模糊目标集的隶属度的比较 ,获得两个集合交集的最优隶属度 ,将此最优隶属度代入最优单纯形表中 ,即可求得 (FLP)的解。本算法只需在一张适当的迭代表台上执行单纯形迭代过程 ,简捷方便适用     

二分单纯形算法中子规划问题的进一步研究

本对二分单纯形算法的子规划问题作进一步研究,提出一个新的子规划问题来改善问题的不可行性,并确定了相应的主元旋转规则,并编制了相应于新子规划的新二分算法,并对94个线性规划问题进行了数值实验,实验结果表明,新二分算法是一种改进的二分算法。