Algorithms for highly symmetric linear and integer programs

This paper deals with exploiting symmetry for solving linear and integer programming problems. Basic properties of linear representations of finite groups can be used to reduce symmetric linear programming to solving linear programs of lower dimension. Combining this approach with knowledge of the geometry of feasible integer solutions yields an algorithm for solving highly symmetric integer linear programs which only takes time which is linear in the number of constraints and quadratic in the dimension.     

A new class of four-point properties which characterize euclidean spaces

Characterizations of generalized euclidean spaces by means of euclidean four-point properties.state that every metric space which is complete, and which contains a metric line joining each two of its points is a generalized euclidean space if and only if each quadruple from a certain class of quadruples of the space is congruent with a quadruple of points in a euclidean space. It is known that it suffices to consider only quadruples containing a linear triple, or quadruples in which one of the linear points is a metric midpoint of the other two. Another class of four-point properties involves quadruples which contain a linear triple and a point equidistant from two of the linear points. The present paper presents three characterizations of euclidean spaces based on four-point properties in which the embedded quadruples contain a linear triple and some three of the distances determined by the four points are equal.     

二次损失下随机回归系数和参数的线性Minimax估计

对带有随机效应的一般线性模型,本文提出了随机回归系数和参数线性组合的Minimax估计问题. 在二次损失下,研究了线性估计的极小极大性.关于适当的假设,得到了可估函数的唯一线性Mjnimax 估计.     

An algorithm for computing equilibria in a linear monetary economy

An algorithm is presented for computing equilibria in a linear monetary economy, that is, an exchange economy in which all individuals have linear utility functions and in which goods are bought and sold only in exchange for money. The algorithm computes the equilibrium prices by solving a finite sequence of linear programming problems.     

医学研究中标准曲线修正的初探

目的:在医学研究和临床检验中经常使用定量检测法,在该方法中标准曲线被广泛应用,且其准确性直接影响检测结果.从统计学角度对其进行修正,使结果更为可靠.方法:应用直线回归法对直线型标准曲线进行处理,求出直线回归方程;对曲线型标准曲线,先将指数方程取对数后变成直线方程,然后求直线回归方程后再回代,求出曲线回归方程.结果:以蛋白量与其对应的OD值间关系求得直线回归方程y=0 .0 0 6x;以TNFα浓度与对应的OD值间关系求得指数回归方程y=0 .0 1 5 x0 .732 ,对两者进行F检验,回归效果均极显著.结论:应用回归法可获得定量检测法中常用的直线型及曲线型标准曲线的方程,据此可直接计算出待测样本所需数据,使其更为简便、准确、可靠.     

Generalized hamming weights and equivalences of codes

It is proved that any linear isomorphism between two linear codes which preserves a generalizedHamming weight is a monomial equivalence.which is an extension of a theorem of MacWilliams.     

双层线性分式规划求顶点的算法

基于双层线性分式规划的性质,讨论了上层不带约束的双层线性分式规划模型,给出了求其所有顶点的算法.此算法为进一步进行双层线性分式规划的灵敏度分析打下了坚实的基础,通过例子对算法进行了检验,并利用结果进行了灵敏度分析.     

Linear relations as generators of semigroups of operators

The theory of semigroups of bounded linear operators is based on the spectral theory of linear relations (multivalued linear operators), which act as generators of operator semigroups.     

On approximation of dual spaces and dual operators

We study the connection between equations which approximate an initial abstract linear equation and the adjoint one. We prove that the operator which is adjoint to the approximating one approximates the adjoint operator. As examples we consider adjoint linear integral equations and mutually dual linear programming problems.     

Linear extensions of orderings

A construction is given which makes it possible to find all linear extensions of a given ordered set and, conversely, to find all orderings on a given set with a prescribed linear extension. Further, dense subsets of ordered sets are studied and a procedure is presented which extends a linear extension constructed on a dense subset to the whole set.     

An effective method for solving linear programming problems with flexible constraints

For solving linear programming problems with flexible constraints being specific piecewise linear programs a new algorithm which is based on a systematic decomposition of the feasible set into linear constrained subsets is proposed and shown to converge.     

Monotonicity and positive invariance of linear systems over dioids

In this paper, we make connections between two apparently different concepts. The first concept is the (linear) monotonicity of a given matrix which is usually used in order to compare Markov chains. This concept is involved in the simplification of complex stochastic systems in order to control the approximation error made. The second concept is the positive invariance of sets by a (linear) map. The properties of positively invariant sets are involved in many different problems in classical control theory, such as constrained control, robustness analysis, optimisation, and also in aggregation of Markov chains (namely strong lumpability and coherency).

In the context of linear dynamical systems over semirings which play an important role in the study of discrete event systems, we establish links between monotone (or isotone) linear maps and linear maps which admit some special families of positively invariant sets.     

n阶常系数非齐次线性微分方程的降阶解法

给出一阶线性非齐次微分方程的积分因子解法,避免了常数变易法带来的不便和不自然;给出,n阶常系数非齐次线性微分方程的降阶解法,可以看出,高阶常系数线性非齐次微分方程最终都可以归结为求解一阶线性微分方程,从而避免了待定系数法求非齐次方程特解的繁琐,并最终说明了一般微积分教材中只给出两种类型常系数非齐次线性微分方程的待定系数解法的原因．     

Formulation of linear problems and solution by a universal machine

Using the predicate language for ordered fields a class of problems referred to aslinear problems is defined. This class contains, for example, all systems of linear equations and inequalities, all linear programming problems, all integer programming problems with bounded variables, all linear complementarity problems, the testing of whether sets that are defined by linear inequalities are semilattices, all satisfiability problems in sentenial logic, the rank-computation of matrices, the computation of row-reduced echelon forms of matrices, and all quadratic programming problems with bounded variables. A single, one, algorithm, to which we refer as theUniversal Linear Machine, is described. It solves any instance of any linear problem. The Universal Linear Machine runs in two phases. Given a linear problem, in the first phase a Compiler running on a Turing Machine generates alinear algorithm for the problem. Then, given an instance of the linear problem, in the second phase the linear algorithm solves the particular instance of the linear problem. The linear algorithm is finite, deterministic, loopless and executes only the five ordered field operations — additions, multiplications, subtractions, divisions and comparisons. Conversely, we show that for each linear algorithm there is a linear problem which the linear algorithm solves uniquely. Finally, it is shown that with a linear algorithm for a linear problem, one can solve certain parametric instances of the linear problem.Research was supported in part by the National Science Foundation Grant DMS 92-07409, by the Department of Energy Grant DE-FG03-87-ER-25028, by the United States—Israel Binational Science Foundation Grant 90-00434 and by ONR Grant N00014-92-J1142.Corresponding author.     

Boundedness and closedness of linear relations

This paper focuses on boundedness and closedness of linear relations, which include both single-valued and multi-valued linear operators. A new (single-valued) linear operator induced by a linear relation is introduced, and its relationships with other two important induced linear operators are established. Several characterizations for closedness, closability, bundedness, relative boundedness and boundedness from below (above) of linear relations are given in terms of their induced linear operators. In particular, the closed graph theorem for linear relations in Banach spaces is completed, and stability of closedness of linear relations under bounded and relatively bounded perturbations is studied. The results obtained in the present paper generalize the corresponding results for single-valued linear operators to multi-valued linear operators, and some improve or relax certain assumptions of the related existing results.     

离散系统Lyapunov第二方法的一些问题

本文讨论线性时不变离散系统Lyapunov方程解集的几何性质以及分段线性离散系统的稳定性,得出每个子系统都是稳定的分段线性离散系统渐近稳定的一些充分条件,并把这些结果应用于二阶分段线性系统.     

Normal extensions of subnormal linear relations via quaternionic Cayley transforms

A quaternionic Cayley transform for linear relations is introduced and some of its properties are exhibited. We emphasize the role played by the linear relations whose quaternionic Cayley transforms are unitary operators, which happen to be normal relations, and investigate the class of those linear relations which extend to such normal relations.     

Duality for Algebraic Linear Programming

A duality theory for algebraic linear (integer) programming (ALP) is developed which is of the same importance for linear (integer) programming with linear algebraic objectives as linear programming duality is for classical LP. In particular, optimality criteria for primal, primal-dual, and dual methods are given which generalize feasibility and complementarity criteria of classical LP. Strong duality results are given for special combinatorial problems. Further, the validity and finiteness of a primal simplex method based on a feasibility criterion are proved in the case of nondiscrete variables. In this case a strong duality result is shown.     

The <Emphasis Type="Italic">K</Emphasis>th-Best Approach for Linear Bilevel Multi-follower Programming

The majority of research on bilevel programming has centered on the linear version of the problem in which only one leader and one follower are involved. This paper addresses linear bilevel multi-follower programming (BLMFP) problems in which there is no sharing information among followers. It explores the theoretical properties of linear BLMFP, extends the Kth-best approach for solving linear BLMFP problems and gives a computational test for this approach.     

线性空间C[a,b]上的线性相关性研究

研究了线性空间C[a,b]上的线性相关性,给出了衡量C[a,b]上n个函数线性相关性程度的量以及线性相关的充分必要条件.