线性规划初始对偶可行基本解的一种求法

运用对偶单纯形法求解线性规划问题时,需要先给定一个初始对偶可行的基本解.然而在线性规划问题的约束条件Ax=b中,矩阵A一般不含m阶单位矩阵,此时初始对偶可行的基本解不易求得.文中通过对线性规划问题增加人工变量和一个约束条件,给出一步便能求出其初始对偶可行基本解的简便方法,进而通过对偶单纯形法进行迭代解决线性规划问题.     

求解无功优化的线性规划最钝角松弛法

采用最钝角松弛算法求解无功优化问题的线性规划模型,为解决线性化步长调整问题在该模型中增加了信赖域约束。首先,根据最钝角原理定义主元标的概念及其计算公式,计算各个不等式约束的主元标。然后,根据不等式约束的主元标值对其进行筛选,形成一个松弛的线性规划问题,用原始单纯形法对其求解。如果松弛问题的最优解能满足原问题的不等式约束,则直接获得原问题的最优解。否则,将所有剩余的约束条件全部添加到松弛模型中,得到改变约束条件顺序后的原问题,再用对偶单纯形法进行新的求解。该算法本质上是一种2阶段单纯形法,并且第二阶段的求解可以充分利用第一阶段松弛问题的解信息,大大提高第二阶段的计算效率。以5个试验系统和1个省级538节点实际系统为测试系统,通过与单纯形法、信赖域内点法进行比较,验证其有效性。     

线性规划一种改进的对偶单纯形法

研究了线性规划对偶单纯形法的改进．根据改进原始单纯形法思想，建立了标准型线性规划对偶单纯形法的一种改进算法．与原对偶单纯形法相比，改进算法的存贮量和计算量大大减少．最后给出了方法的实算例子．     

线性规划初始基本可行解的新算法

单纯形法是求解线性规划问题的常用方法 ,但是 ,在用单纯形法前要求已知一个基本可行解 ,且线性规划需化为典式。虽然有一些方法可得到线性规划的基本可行解 ,但一般要增加人工变量 ,从而增加计算量。针对这一问题 ,文章提出了求非负变量等式约束基本可行解的一种方法。此法不须引入人工变量、不须处理约束方程 ,而直接对等式约束进行初等变换 ,得到一基本可行解 ,并在求解过程中剔除多余的约束 ,判断问题是否有解 ,同时将线性规划的约束方程化为典式。     

临界区间法求解线性规划问题

给出了求线性规划问题最优解的临界区间算法，这种算法是在已知LP(λ)的临界区间[λk，λk-1]的条件下，用单纯形法和对偶单纯形法进行旋转运算，求得[λk,λk-1]的包含临界值λ=0的紧后临界区间[λk 1，λk]，其优点是不需要基本可行解或对偶基本可行解。     

求解超大型线性规划的并行单纯形算法

提出了一种求解超大型线性规划的并行单纯形算法，将原线性规划分成若干个子线性规划，每台计算机用单纯形法计算一个子线性规划，各机间象高斯消去法一样分块消去、分块回代，当满足一定条件时得到原线性规划的最优解．     

关于“单纯形法选择进出基变元的一个新准则”的计算效率

线性规划广泛应用于经济与管理的各个领域,单纯形法是求解线性规划实际问题非常有效的算法．对“单纯形法选择进出基变元的一个新准则”进行了分析,给出了详细的算法步骤,通过大规模的数值试验进一步揭示了该算法的计算效率．结果表明,这种改进的单纯形算法虽然在大部分问题上的迭代次数比经典的单纯形算法有所减少,但所耗费的计算时间却普遍增加,其计算效率随着问题规模的增大而不断下降．     

二层线性规划问题的全局收敛算法

基于单纯形法提出了一种具有全局收敛性质的算法来求解该问题.在该方法中,用下层的Kuhn-Tucker条件代替下层问题,将原二层线性规划转化为传统的单层规划问题.之后利用下层规划对偶问题可行域的顶点将该单层规划转化为一系列线性规划问题,从而用单纯形法来求解这些线性规划来得到原二层线性规划问题的解.最后,用实例验证了该方法的可行性.     

L.P.问题单纯形法一种改进的迭代判别方法

单纯形法是求解线性规划问题的有效方法．本文给出了求解一般线性规划问题的单纯形算法中一种改进的迭代判别方法，该方法与传统的判别方法相比，是一种利用较少次迭代求解线性规划问题最优解的方法．     

一类多维线性规划的图解法

利用对偶线性规划和对偶线性规划最优解互补松弛条件解决了含有多个变量和两个约束的线性规划的图解法求解问题．突破了线性规划的图解法只能用于二维线性规划求解的框框．     

一种改进的单调增强单纯形算法

考察单调增强单纯形算法的实际计算性能,并解析其计算效率较低的原因．该文提出一种改进方法,即从第一阶段算法开始,每旋出一个人工变量,就使非负缩减费用系数的个数得到单调增加;在第二阶段算法中,放松对枢轴行的选择要求,从而可使驱动变量尽快旋入基中,产生一个对偶可行解,然后再应用对偶单纯形算法获得问题的最优解或无可行解的结论．大规模数值试验对改进算法进行检验的结果表明,这种改进算法的计算效率优于经典单纯形算法,单调增强单纯形算法理论具有实用价值．     

线性互补约束问题的一个SQP算法

针对非线性规划一些经典的算法一般不能直接应用到均衡问题上来的缺点,通过一个处处连续可微的互补函数以及光滑近似法的思想,把互补约束均衡问题转化为一光滑非线性规划问题,提出一个SQP算法求解该光滑非线性规划问题,并给出了算法的数值解,数值实验结果表明算法具有很好的收敛速度和寻优结果.     

Curet原始-对偶单纯形算法的推广

Curet原始-对偶单纯形算法的实质是在保持对偶可行性的前提下求解一系列原始松驰子问题,因此它必须有一个初始对偶可行解来启动。对于原问题目标函数存在负的价值系数的情形,提出引入人工约束通过简单的初等行变换产生新的目标函数,获得相应的对偶可行解,然后应用Curet原始‐对偶单纯形算法获得问题的一个原始可行解。为了使这个原始可行解更接近最优解,在每次迭代中都对新的目标函数进行修正以逐步逼近原目标函数。在该基础上,通过实现互补松弛条件来取得问题的最优解。大规模数值试验结果表明,与经典两阶段单纯形算法相比,提出的算法在大部分问题上使用更少的迭代次数和执行时间,因而这种推广是有价值的。     

求解背包约束下下模集函数近似算法及性能保证

为有效求得背包约束条件下不同问题的解,我们往往采取不同的方式,以获得其最优解。但更多情况下,我们无法找出其精确最优解,这时我们将选取不同的变量,通过有效的算法,以获得该问题的近似解。我们利用线性规划的知识,分析最大化非减下模集函数在背包约束下近似算法,得出该算法计算复杂性为O(n5),性能保证为1-e-1。     

单纯形—模拟退火算法

在简要介绍单纯形法基础上,针对模拟退火算法存在收敛慢、费机时较多的缺陷,将单纯形法与模拟退火算法有机地结合起来,形成一种新的改进造型的优化算法－单纯形－模拟退火算法,以加快速敛速度,提高解的质量,是单纯形法与模拟退火算法各自特点的综合,并通过算例进行了验证。     

一种不用人工变量单纯形法—SM—WUAV法初探

本文提出一种不用人工变量,适用于求解一般线性规划问题的单纯形法.与传统单纯形法相比,本文提出的算法,除更具通用性外,迭代次数相对减少,有时甚至明显减少.事实证明,该算法是有效的.     

国际数学规划领域的热点问题：线性规划内点法

论述20世纪80年代至今的国际数学规划领域的热点问题——线性规划内点法的出现和它的理论体系、研究现状及其发展，同时也讨论了传统的单纯形法的最新进展以及内点法与单纯形法的对比测试，展现了该领域当前的研究现状与发展趋势。     

求解单背包约束下下模函数半定松驰算法

为有效求得背包约束条件下下模函数的解,往往采取不同的方式,以获得最优解,但更多情况下无法找出其精确最优解。针对这个问题,选取两种不同的方法,先对所求解通过添加变量进行约束,再应用贪婪算法,以获得该问题的最优近似解;利用线性规划的知识,分析最大化非减下模集函数在单背包约束下的近似算法,得出当σ>0.19时,算法(III)的性能保证大于0.732,并且随着σ的增大而接近最优解,算法(III)中的参数θ对某种大规模情形将不起作用。