线性规划新算法的改进

本文基于算法要简单实用的思想,对一种线性规划新算法中的核心算法进行改进,使其计算方法更简单计算量更小,使整个算法更为可行有效。     

一个改进的线性规划预校正算法

本文我们提出了一个改进型线性规划预校正算法，我们的预步和校正步方向与Mizuno－Todd-Ye[4]的方向是不同的．我们的算法的迭代复杂度为，然而在校正步，我们降低对偶间隙一个常数因子．     

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

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

线性规划Karmarkar算法的一种改进算法及其数值检验

本文给出求解线性规划问题的一种改进的Karmarkar算法IKA.本算法通过施行仿射变换,将已给定的一个可行内点,变成另一空间可行域中所有分量为1的点e,然后从e出发,沿梯度方向进行一维搜索,使问题的目标函数单调下降,并收敛于最优值,因而不需假定目标函数最优值为已知.几个有数百个约束方程和变量的实际算例表明本算法比Karmarkar算法有效.     

基于改进基线算法的线性规划灵敏度问题研究

针对基线算法由于计算方面的无记忆性而在线性规划灵敏度方面的难实现问题,提出了改进的基线算法,并分别讨论了在价值系数C、技术系数矩阵A及资源向量b等各种情况发生变化的条件下,如何采用改进的基线算法进行灵敏度分析,从而能够简便、快捷的获得新的最优解.最后通过实例进行了说明.     

一个新的线性规划Criss-cross算法

本文利用重新排列下标的技巧,提出了一个新的criss-cross算法.并证明了其有限性,理论分析及初步的计算实验表明,新算法比最小下标criss-cross算法效率更高.     

一种新的线性规划多项式时间算法

本文给出了一种新的线性规划多项式时间算法。在此算法中，每步可沿一族方向中的一个进行线性搜索，同时，还使用了开关策略，从而大大减少了求逆矩阵的次数，最后，证明了算法经Ｏ（ｎＬ）次迭代结束。     

多目标线性规划模糊算法与折衷算法分析

本分析了多目标线性规划中“min”算子的非补偿性和“算术平均”算子的不平衡性,并在此基础上论述了两阶段模糊算法与经典折衷算法之间的内在联系。     

二次规划的内椭球算法

对于标准型的凸二次规划问题本文给出了一个新算法，算法的一每步迭代，利用内椭球的思想来近似求解一个线性质规划子问题而得到迭代方向，再适当选取步长而使之成为多项式算法，其迭代步数为Ｏ（ｎＬ＾２），每一步迭代所需计算量为Ｏ（ｎ＾３）。其中ｎ为变量个数，Ｌ为问题的输入长度。     

一种改进的双层规划内点算法(英文)

本文针对线性双层规划问题提出一个由KMY算法演变而来的原对偶内点算法.与现在很多线性双层规划单纯型算法不同,作者提出的算法从一可行初始点穿过约束多面体内部直接得到近似最优解,当约束条件和变量数目增加时,本算法的迭代次数和计算时间变化很小.所以大大提高实际可操作性能和运算效率.     

线性规划基线算法群部分算法计算实验

本文简要介绍了基线算法的构思原理 ,对其中部分算法的具体实现形式进行了测试 ,并与单纯形法进行了比较 .理论和数值结果表明基线算法是一种可靠、有效的算法 .作者还给出了一些对其它算法在计算实践中的看法     

Duality in Fuzzy Linear Programming: Some New Concepts and Results

A class of fuzzy linear programming (FLP) problems based on fuzzy relations is introduced, the concepts of feasible and -efficient solutions are defined. The class of crisp (classical) LP problems and interval LP problems can be embedded into the class of FLP ones. Moreover, for FLP problems a new concept of duality is introduced and the weak and strong duality theorems are derived. The previous results are applied to the special case of interval LP and compared to the existing literature.     

Geometric Algorithm for Multiparametric Linear Programming

We propose a novel algorithm for solving multiparametric linear programming problems. Rather than visiting different bases of the associated LP tableau, we follow a geometric approach based on the direct exploration of the parameter space. The resulting algorithm has computational advantages, namely the simplicity of its implementation in a recursive form and an efficient handling of primal and dual degeneracy. Illustrative examples describe the approach throughout the paper. The algorithm is used to solve finite-time constrained optimal control problems for discrete-time linear dynamical systems.     

线性规划的筛选迭代算法

提出了求解线性规划(LP)问题的一种新方法———筛选迭代算法。它通过筛选n维LP问题的n个控制约束方程(不添加松驰变量)的方法求得LP问题的最优解     

An Algorithm for Approximate Multiparametric Linear Programming

Multiparametric programming considers optimization problems where the data are functions of a parameter vector and describes the optimal value and an optimizer as explicit functions of the parameters. In this paper, we consider a linear program where the right-hand side is an affine function of a parameter vector; we propose an algorithm for approximating its solution. Given a full-dimensional simplex in the parameter space and an optimizer for each simplex vertex, the algorithm formulates the linear interpolation of the given solutions as an explicit function of the parameters, giving a primal feasible approximation of an optimizer inside the simplex. If the resulting absolute error in the objective exceeds a prescribed tolerance, then the algorithm subdivides the simplex into smaller simplices where it applies recursively. We propose both a basic version and a refined version of the algorithm. The basic version is polynomial in the output size, provided a polynomial LP solver is used; the refined version may give a smaller output. A global error bound for the optimizer is derived and some computational tests are discussed.     

Outcome-Space Cutting-Plane Algorithm for Linear Multiplicative Programming

This article presents an outcome-space pure cutting-plane algorithm for globally solving the linear multiplicative programming problem. The framework of the algorithm is taken from a pure cutting-plane decision set-based method developed by Horst and Tuy for solving concave minimization problems. By adapting this method to an outcome-space reformulation of the linear multiplicative programming problem, rather than applying directly the method to the original decision-set formulation, it is expected that considerable computational savings can be obtained. Also, we show how additional computational benefits might be obtained by implementing the new algorithm appropriately. To illustrate the new algorithm, we apply it to the solution of a sample problem.     

线性规划的最钝角松弛算法

本文提出一个基于最钝角原理的松弛算法求解线性规划问题。该算法依据最钝角原理略去部分约束得到一个规模较小的子问题,用原始单纯形算法解之;再添加所略去的约束恢复原问题,若此时全部约束条件均满足则已获得一个基本最优解,否则用对偶单纯形算法继续求解。初步的数值试验表明,新算法比传统两阶段单纯形算法快得多。     

New Branch-and-Cut Algorithm for Bilevel Linear Programming

Linear mixed 0–1 integer programming problems may be reformulated as equivalent continuous bilevel linear programming (BLP) problems. We exploit these equivalences to transpose the concept of mixed 0–1 Gomory cuts to BLP. The first phase of our new algorithm generates Gomory-like cuts. The second phase consists of a branch-and-bound procedure to ensure finite termination with a global optimal solution. Different features of the algorithm, in particular, the cut selection and branching criteria are studied in details. We propose also a set of algorithmic tests and procedures to improve the method. Finally, we illustrate the performance through numerical experiments. Our algorithm outperforms pure branch-and-bound when tested on a series of randomly generated problems. Work of the authors was partially supported by FCAR, MITACS and NSERC grants.