线性规划的符号跟踪算法

分析了只含一个约束条件的线性规划最优基变量的特征，将其运用到搜寻含m个约束条件的线性规划的最优基变量，从而提出了线性规划的符号跟踪算法，为线性规划求解提供了新途径。     

方向选择约束单纯形算法

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

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

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

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

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

线性规划的目标函数最速递减算法

在对偶单纯形方法的基础上，提出了线性规划的目标函数最速递减算法。它避开求初始可行基或初始基，以目标函数全局快速递减作为选基准则，将选基过程与换基迭代合二为一，从而大大减少了迭代次数。数值算例显示了该算法的有效性和优越性。     

线性规划流动等值面算法

对于线性规划问题，本文给出了基于流动等值面的等价模型，提出了一种不可行流动等值面算法．新算法保留了传统单纯形算法的优点并克服了它的不足。初步数值结果表明新算法比传统方法更为有效．     

一个新的单纯形类算法

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

求线性规划初始可行基的新方法

本文提出一个求线性规划初始可行基的新算法，该算法不仅避免了人工变量，而且理论分析及初步的数值实验结果表明其效率更高。     

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

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

多层线性规划问题的整体优化算法

本文研究了求解多层线性规划问题的整体优化算法,利用流动等值面技术,证明了算法的有限终止性,并给出实际例子验证了算法的有效性.     

一个含有多余约束的线性规划问题改进算例

为了在不改变原有约束条件的情况下,充分利用现有条件,使规划的目标达到更优解。给出了两种含有多余约束的线性规划问题的改进方法:增加资源量或者减少资源量,并给出了一个具体的算例。     

“准最优基”程序实现与应用探讨

在利用"准最优基"简化单纯形法的求解过程的基础上,采用matlab将"准最优基"方法程序化,并采用程序进行了模型.求解原采用两阶段法求解的线性规划问题,用"准最优基"方法,不必加入人工变量,改两阶段为一阶段,简化了求解过程,并针对只能将其目标函数系数为正的变量进基、约束条件都为正的局限性进行了探讨."准最优基"方法对目标函数的系数有正有负的情况,约束条件的系数有正有负的情况都适用.借助"bland法则"的思想,按下标顺序进基取代变量强度系数进基,得出了同样的结果,并对E.Beale的循环例子进行计算,一步得出最优解."准最优基"方法既可以提高运算速度,同时具有很好的适用性.     

线性比式和规划问题的输出空间分支定界算法

本文旨在针对线性比式和规划这一NP-Hard非线性规划问题提出新的全局优化算法.首先,通过引入p个辅助变量把原问题等价的转化为一个非线性规划问题,这个非线性规划问题的目标函数是乘积和的形式并给原问题增加了p个新的非线性约束,再通过构造凸凹包络的技巧对等价问题的目标函数和约束条件进行相应的线性放缩,构成等价问题的一个下界线性松弛规划问题,从而提出了一个求解原问题的分支定界算法,并证明了算法的收敛性.最后,通过数值结果比较表明所提出的算法是可行有效的.     

线性规划问题的规范型算法

提出了线性规划问题的两种规范标准形式；证明了任意一个线性规划问题都可化为这两种形式之一；给出了不需引入人工变量的线性规划问题的求解算法。     

Convergence property of the Iri-Imai algorithm for some smooth convex programming problems

In this paper, the Iri-Imai algorithm for solving linear and convex quadratic programming is extended to solve some other smooth convex programming problems. The globally linear convergence rate of this extended algorithm is proved, under the condition that the objective and constraint functions satisfy a certain type of convexity, called the harmonic convexity in this paper. A characterization of this convexity condition is given. The same convexity condition was used by Mehrotra and Sun to prove the convergence of a path-following algorithm.The Iri-Imai algorithm is a natural generalization of the original Newton algorithm to constrained convex programming. Other known convergent interior-point algorithms for smooth convex programming are mainly based on the path-following approach.     

计算机指令优化控制模型

为了对计算机指令进行最优控制设计 ,我们建立了解决最优控制的整数线性规划模型 .由于变量较多 ,约束条件全都是线性的 ,目标函数为一次 ,我们采用单纯形法对问题求解 ,整个算法都用 c语言实现 ,并对实例进行了求解 .本模型很好的解决了计算机指令优化控制的问题 ,也适用于其他类似问题 .     

Parametric simplex algorithms for solving a special class of nonconvex minimization problems

It is shown that parametric linear programming algorithms work efficiently for a class of nonconvex quadratic programming problems called generalized linear multiplicative programming problems, whose objective function is the sum of a linear function and a product of two linear functions. Also, it is shown that the global minimum of the sum of the two linear fractional functions over a polytope can be obtained by a similar algorithm. Our numerical experiments reveal that these problems can be solved in much the same computational time as that of solving associated linear programs. Furthermore, we will show that the same approach can be extended to a more general class of nonconvex quadratic programming problems.     

如何利用单纯形表上的信息

本文分析了求解线性规划的基本方法－－单纯形法所使用的单纯形表，将表中所提供的信息分为直接信息和间接信息两类，论述了如何充分利用这些信息的方法。例如如何由最终表求原问题、如何利用表中的数据互相推演和校正等。这是一篇教学经验的总结，对初学者可能有一定的帮助。     

An extended branch and bound algorithm for linear bilevel programming

For linear bilevel programming, the branch and bound algorithm is the most successful algorithm to deal with the complementary constraints arising from Kuhn–Tucker conditions. However, one principle challenge is that it could not well handle a linear bilevel programming problem when the constraint functions at the upper-level are of arbitrary linear form. This paper proposes an extended branch and bound algorithm to solve this problem. The results have demonstrated that the extended branch and bound algorithm can solve a wider class of linear bilevel problems can than current capabilities permit.