关于单形的中面

在n维欧氏空间中,作为三角形的高维推广的单形的中面是最近才引入的一个重要的几何概念．该文利用Grassmann代数的方法获得了单形的中面面积的解析表达式,证明了单形的中面类似于三角形中线的性质,例如,对于一个给定的单形,存在另一个单形使得其边长分别等于给定单形的中面面积;一个单形的所有中面有且仅有一个公共点等．同时,利用中面面积的解析表达式证明了单形中面与单形的棱长、外接圆半径、中线长、角平分面等之间的一些优美性质,建立了一些新的重要的几何不等式．     

Integration over a simplex,truncated cubes,and Eulerian numbers

Summary A method of integrating a function over a simplex is described in which (i) the simplex is first transformed into a right-angled isosceles simplex; (ii) this simplex is dissected into small cubes and truncated cubes; (iii) the integration over the truncated cubes is performed by the centroid method or by Stroud's method, and this requires the use of formulae for the moments of a truncated cube. These formulae are developed and are expressed in terms of Eulerian numbers. In the special case when the truncated cube is itself a right-angled isoceles simplex a new algorithm is given, depending on the discrete Fourier transform, for calculating the moments as polynomials inn wheren is the dimensionality.     

Simplex sliding mode control for nonlinear uncertain systems via chaos optimization

As an emerging effective approach to nonlinear robust control, simplex sliding mode control demonstrates some attractive features not possessed by the conventional sliding mode control method, from both theoretical and practical points of view. However, no systematic approach is currently available for computing the simplex control vectors in nonlinear sliding mode control. In this paper, chaos-based optimization is exploited so as to develop a systematic approach to seeking the simplex control vectors; particularly, the flexibility of simplex control is enhanced by making the simplex control vectors dependent on the Euclidean norm of the sliding vector rather than being constant, which result in both reduction of the chattering and speedup of the convergence. Computer simulation on a nonlinear uncertain system is given to illustrate the effectiveness of the proposed control method.     

单形正弦定理的再推广

本文利用Grassmann代数建立n维欧氏空间中单形的k级n-k s维顶点角的概念，在此基础上对单形的正弦定理再作推广，并获得单形新的一类体积公式和一个几何不等式．     

关于高维单形的两个性质

应用度量几何理论与解析方法,研究了n维欧氏空间En中n维单形的性质,将三角形内心与中线两个性质推广到n维单形,获得n维单形内心与中位面的两个性质.     

线性规划基线算法的基本概念

１．运算表格线性规划的基线算法是单纯形法（基点算法）的发展,因为每张运算表格对应着一条基线而得名．它象单纯形法一样好学易用,操作简便,而解题速度比单纯形法快．考虑标准型线性规划问题（ＬＰ）：：其中ｃ,ｘｅＲ"＋",Ａ是。ｘ（佩十。）矩阵,ｂｅＲ"。是（ＬＰ）的维数,。是约束个数．Ｘ＝｛ＸＥＲ""叫ＡＸ＝ｂ,Ｘ三０｝是（＊利的可行集．Ｘ是一个多面凸集．本文假定Ｃ４０．并且原点不是最优解．把Ｘ看作参数．方程组０．】Ｘ＝０,】的系数表称为母表（表１）．恒假设矩阵０－１－＼Ａｊ＼ｈｉ一"-一'-－"－"'一'-"-一"…     

欧氏空间E~n中Euler不等式的加强推广(英文)

The relation between the circum-radius and the in-radius of an n-dimensional simplex in E~n is studied.Two new generalizations of Euler inequality for the n-dimensional simplex are established.Besides,we obtain some stronger generalizations of Euler inequality for the n-dimensional simplex than previously known results.     

一种简易的单纯形表

通过对单纯形法的分析和研究,提出了一种简易的单纯形表,并利用矩形法则进行计算而得到一种改进的单纯形法.结果表明该法简单易行,并减少了计算量和存储量.     

An algorithm of simplicial Lipschitz optimization with the bi-criteria selection of simplices for the bi-section

An algorithm of simplicial optimization is proposed where a bi-criteria selection of a simplex for the bi-section is applied. The first criterion is the minimum of estimated Lipschitz lower bound over the considered simplex. The second criterion is the diameter of the simplex. The results of experimental testing are included.     

Eliminating columns in the simplex method for linear programming

We propose a column-eliminating technique for the simplex method of linear programming. A pricing criterion is developed for checking whether a dual hyperplane corresponding to a column intersects a simplex containing all of the optimal dual feasible solutions. If the dual hyperplane has no intersection with this simplex, we can eliminate the corresponding column from further computation during the course of the simplex method.The author is grateful for many discussions with Professor G. B. Dantzig, Stanford University, and for his valuable suggestions about this work. The author also gratefully acknowledges the editor and two referees for their very helpful comments, corrections, and remarks.     

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

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

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

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

Towards a practical parallelisation of the simplex method

The simplex method is frequently the most efficient method of solving linear programming (LP) problems. This paper reviews previous attempts to parallelise the simplex method in relation to efficient serial simplex techniques and the nature of practical LP problems. For the major challenge of solving general large sparse LP problems, there has been no parallelisation of the simplex method that offers significantly improved performance over a good serial implementation. However, there has been some success in developing parallel solvers for LPs that are dense or have particular structural properties. As an outcome of the review, this paper identifies scope for future work towards the goal of developing parallel implementations of the simplex method that are of practical value.     

Steepest-edge simplex algorithms for linear programming

We present several new steepest-edge simplex algorithms for solving linear programming problems, including variants of both the primal and the dual simplex method. These algorithms differ depending upon the space in which the problem is viewed as residing, and include variants in which this space varies dynamically. We present computational results comparing steepest-edge simplex algorithms and approximate versions of them against simplex algorithms that use standard pivoting rules on truly large-scale realworld linear programs with as many as tens of thousands of rows and columns. These results demonstrate unambiguously the superiority of steepest-edge pivot selection criteria to other pivot selection criteria in the simplex method.The research of this author was supported in part by NSF Grants DMS 85-12277, DMS 91-0619 and CDR 84-21402.     

线性规划流动等值面算法

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

A conjugate Rosen’s gradient projection method with global line search for piecewise linear concave optimization

The Kelley cutting plane method is one of the methods commonly used to optimize the dual function in the Lagrangian relaxation scheme. Usually the Kelley cutting plane method uses the simplex method as the optimization engine. It is well known that the simplex method leaves the current vertex, follows an ascending edge and stops at the nearest vertex. What would happen if one would continue the line search up to the best point instead? As a possible answer, we propose the face simplex method, which freely explores the polyhedral surface by following the Rosen’s gradient projection combined with a global line search on the whole surface. Furthermore, to avoid the zig-zagging of the gradient projection, we propose a conjugate gradient version of the face simplex method. For our preliminary numerical tests we have implemented this method in Matlab. This implementation clearly outperforms basic Matlab implementations of the simplex method. In the case of state-of-the-art simplex implementations in C or similar, our Matlab implementation is only competitive for the case of many cutting planes.     

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

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

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

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

含自由变量LP问题的改进单纯形法

对于含自由变量的LP问题,为了得到比单纯形法[1]更有效的算法,通过研究在单纯形法迭代过程中,将自由变量化为非负变量再实施运算的规律,提出一种能节省存贮空间和提高运算速度的改进单纯形法。数值实验表明新算法是有效的。     

Parallel distributed-memory simplex for large-scale stochastic LP problems

We present a parallelization of the revised simplex method for large extensive forms of two-stage stochastic linear programming (LP) problems. These problems have been considered too large to solve with the simplex method; instead, decomposition approaches based on Benders decomposition or, more recently, interior-point methods are generally used. However, these approaches do not provide optimal basic solutions, which allow for efficient hot-starts (e.g., in a branch-and-bound context) and can provide important sensitivity information. Our approach exploits the dual block-angular structure of these problems inside the linear algebra of the revised simplex method in a manner suitable for high-performance distributed-memory clusters or supercomputers. While this paper focuses on stochastic LPs, the work is applicable to all problems with a dual block-angular structure. Our implementation is competitive in serial with highly efficient sparsity-exploiting simplex codes and achieves significant relative speed-ups when run in parallel. Additionally, very large problems with hundreds of millions of variables have been successfully solved to optimality. This is the largest-scale parallel sparsity-exploiting revised simplex implementation that has been developed to date and the first truly distributed solver. It is built on novel analysis of the linear algebra for dual block-angular LP problems when solved by using the revised simplex method and a novel parallel scheme for applying product-form updates.