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.     

浅析大M法与两阶段法的一致性

分析了大M法与两阶段法在思想方法、辅助线性规划问题的构造、初始可行基、初始单纯形表、最优性检验和算法步骤等方面的一致性.     

单纯形法选择进出基变元的一个新准则

解线性规划单纯形法迭代中,G.B.Dantzig等人给出的进基原则看似简单,但其忽略了影响目标函数增加量的另外一个因素—进基变元的产出系数,而试图给出一个新的迭代进出基准则—最大增量准则,一方面可以加快迭代速度,同时也可以避免迭代中可能遇到的所谓循环.     

A computational comparison of the dinic and network simplex methods for maximum flow

We study the implementation of two fundamentally different algorithms for solving the maximum flow problem: Dinic's method and the network simplex method. For the former, we present the design of a storage-efficient implementation. For the latter, we develop a "steepest-edge" pivot selection criterion that is easy to include in an existing network simplex implementation. We compare the computational efficiency of these two methods on a personal computer with a set of generated problems of up to 4 600 nodes and 27 000 arcs.This research was supported in part by the National Science Foundation under Grant Nos. MCS-8113503 and DMS-8512277.     

A note on global stability of three-dimensional Ricker models

In the recent paper [E. C. Balreira, S. Elaydi, and R. Luís, J. Differ. Equ. Appl. 23 (2017), pp. 2037–2071], Balreira, Elaydi and Luís established a good criterion for competitive mappings to have a globally asymptotically stable interior fixed point by a geometric approach. This criterion can be applied to three dimensional Kolmogorov competitive mappings on a monotone region with a carrying simplex whose planar fixed points are saddles but globally asymptotically stable on their positive coordinate planes. For three dimensional Ricker models, they found mild conditions on parameters such that the criterion can be applied to. Observing that Balreira, Elaydi and Luís' discussion is still valid for the monotone region with piecewise smooth boundary, we prove in this note that the interior fixed point of three dimensional Kolmogorov competitive mappings is globally asymptotically stable if they admit a carrying simplex and three planar fixed points which are saddles but globally asymptotically stable on their positive coordinate planes. This result is much easier to apply in the application.     

Properties of subspaces of the space of affine functions

Conditions are presented for weak (strong) convergence, in the entire space A(x), of a sequence of positive operators to a fixed operator S on the basis of its weak (strong) convergence to S in a subspace. The criterion of Bauer's simplex is presented.Translated from Matematicheskie Zametki, Vol. 17, No. 2, pp. 307–318, February, 1975.In conclusion the author expresses his deep gratitude to Yu. A. Shashkin for his many valuable remarks.     

Rational solutions of the graphsack problem

A graphsack problem is a certain binary linear optimization problem with applications in optimal network design. From there a rational graphsack problem is derived by allowing the variables to vary continuously between 0 and 1. In this paper we deal with rational graphsack problems. First we develop the concept of compressed solutions and the concept of augmenting cuts. Making use of these concepts a very simple optimality criterion is derived. Finally an efficient algorithm solving rational graphsack problems is given which is polynomially bounded in time and which is closely related to the simplex algorithm.     

On the use of the simplex algorithm for the absolute deviation curve fitting problem

Linear curve-fitting problems are commonly solved using a criterion which minimises the sum of the squares of deviations of observations from the line. The legitimacy of this operation relies on a number of assumptions which in practice are often left untested. Alternatively the curve-fitting exercise is justified by its computational tractibility. An alternative procedure which fits lines using a criterion of minimising the sum of the absolute deviations of observations from the line is acknowledged to have attractive properties, but is often avoided because of computational difficulties in solution. In fact this problem has long been known to be amenable to solution by linear programming, and in this paper we present some results, commentary and advice based on the use of three LP codes to solve the problem. Two of these codes are conventional implementations of the simplex method while the third is a special purpose code written for just this problem. Live data from a problem of batch manufacture was used, and the influence of data is part of the investigation. At least some of the advice is contrary to that offered by earlier authors.     

An algorithm for the solution of ill-posed linear systems arising from the discretization of Fredholm integral equation of the first kind

An algorithm for obtaining approximate solutions of ill-posed systems of linear equations arising from the discretization of Fredholm integral equation of the first kind is described. The ill-posed system is first replaced by an equivalent consistent system of linear equations. The method calculates the minimum length least squares solution of the consistent system. Starting from rank = 1 of the consistent system, the rank is increased by one in succession and a new solution is calculated. This is repeated until a certain simple criterion is satisfied. Linear programming techniques are used for which successive solutions are the basic solutions in the successive simplex tableaux. The algorithm is numerically stable. Numerical results show that this method compares favorably with other direct methods.     

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

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

The range of the efficient frontier in multiple objective linear programming

Because a rational decision maker should only select an efficient alternative in multiple criterion decision problems, the efficient frontier defined as the set of all efficient alternatives has become a central solution concept in multiple objective linear programming. Normally this set reduces the set of available alternatives of the underlying problem. There are several methods, mainly based on the simplex method, for computing the efficient frontier. This paper presents a quite different approach which uses a nonlinear parametric program, solved by Wolfe's algorithm, to determine the range of the efficient frontier.     

Pivot selection methods of the Devex LP code

Pivot column and row selection methods used by the Devex code since 1965 are published here for the first time. After a fresh look at the iteration process, the author introduces dynamic column weighting factors as a means of estimating gradients for the purpose of selecting a maximum gradient column. The consequent effect of this column selection on rounding error is observed. By allowing that a constraint may not be positioned so exactly as its precise representation in the computer would imply, a wider choice of pivot row is made available, so making room for a further selection criterion based on pivot size. Three examples are given of problems having between 2500 and 5000 rows, illustrating the overall time and iteration advantages over the standard simplex methods used today. The final illustration highlights why these standard methods take so many iterations. These algorithms were originally coded for the Atlas computer and were re-coded in 1969 for the Univac 1108.     

Fuzzy facility location-allocation problem under the Hurwicz criterion

Facility location-allocation (FLA) problem has been widely studied by operational researchers due to its many practical applications. Many researchers have studied the FLA problem in a deterministic environment. However, the models they proposed cannot accommodate satisfactorily various customer demands in the real world. Thus, we consider the FLA problem with uncertainties. In this paper, a new model named α-cost model under the Hurwicz criterion is presented with fuzzy demands. In order to solve this model, the simplex algorithm, fuzzy simulations and a genetic algorithm are integrated to produce a hybrid intelligent algorithm. Finally, some numerical examples are presented to illustrate the effectiveness of the proposed algorithm.     

Global Optimization of Stochastic Black-Box Systems via Sequential Kriging Meta-Models

This paper proposes a new method that extends the efficient global optimization to address stochastic black-box systems. The method is based on a kriging meta-model that provides a global prediction of the objective values and a measure of prediction uncertainty at every point. The criterion for the infill sample selection is an augmented expected improvement function with desirable properties for stochastic responses. The method is empirically compared with the revised simplex search, the simultaneous perturbation stochastic approximation, and the DIRECT methods using six test problems from the literature. An application case study on an inventory system is also documented. The results suggest that the proposed method has excellent consistency and efficiency in finding global optimal solutions, and is particularly useful for expensive systems.     

线性规划最优解集的表现

文献［１］讨论了有无穷多最优解的线性规划问题，并利用最优单纯形表格的检验数给出线性规划有无穷多最优解的判别法，本文利用最优基可行解的凸组合及最优极向的非负线性组合给出线性规划最优解集的表现，从而把线性规划最优解集的几何特征阐释清楚．     

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.     

欧氏空间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.     

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

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

关于单形的中面

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