关于一般线性规划逆问题的一种简化

本将一般线性规划的逆问题转化为对应于已知解x^oj=0的价值系数cj不允许调整的限制逆问题，得到了逆问题的简化模型，然后给出了其在τ∞，τ1，τ2模意义下的具体形式，分别为线性规划和二次规划问题。     

一般线性规划问题的限制逆问题

本文提出了一般线性规划问题的限制逆问题,利用线性规划的最优性条件,分别给出了其在l∞,l1,l2模意义下的数学模型,它们分别为线性规划和二次规划问题。     

分块态射的广义逆

ClineRE给出了分块矩阵的Moore-Penrose逆的表达式,PetrPeska引进了分块态射的记号且导出了分块态射的Moore-Penrose逆的表达式.本文中,我们推广了Cline型分块态射的记号并得到了Cline型分块态射的Moore-Penrose逆和Drazin逆以及群逆的表达式.     

Constructive Solution of Inverse Parametric Linear/Quadratic Programming Problems

Parametric convex programming has received a lot of attention, since it has many applications in chemical engineering, control engineering, signal processing, etc. Further, inverse optimality plays an important role in many contexts, e.g., image processing, motion planning. This paper introduces a constructive solution of the inverse optimality problem for the class of continuous piecewise affine functions. The main idea is based on the convex lifting concept. Accordingly, an algorithm to construct convex liftings of a given convexly liftable partition will be put forward. Following this idea, an important result will be presented in this article: Any continuous piecewise affine function defined over a polytopic partition is the solution of a parametric linear/quadratic programming problem. Regarding linear optimal control, it will be shown that any continuous piecewise affine control law can be obtained via a linear optimal control problem with the control horizon at most equal to 2 prediction steps.     

判断并解决线性规划“多反而少”悖论的逆最优值解法

现有研究通过调整线性规划模型的右端项来消除“多反而少”悖论,而该文提出并验证了悖论是由技术系数矩阵、目标函数系数以及右端项三者的不合理搭配造成的。首先,通过建立原-对偶模型来判断悖论现象存在与否;然后,将悖论问题转换成逆最优值问题进行解决,构建了通过调整目标函数系数以及技术系数矩阵来消除悖论的模型;最后,提出了判断并解决悖论的逆最优值解法,阐述了其优势与经济意义,并通过数值算例验证其有效性。     

A Semidefinite Programming approach for solving Multiobjective Linear Programming

Several algorithms are available in the literature for finding the entire set of Pareto-optimal solutions of Multiobjective Linear Programmes (MOLPs). However, all of them are based on active-set methods (simplex-like approaches). We present a different method, based on a transformation of any MOLP into a unique lifted Semidefinite Program (SDP), the solutions of which encode the entire set of Pareto-optimal extreme point solutions of any MOLP. This SDP problem can be solved, among other algorithms, by interior point methods; thus unlike an active set-method, our method provides a new approach to find the set of Pareto-optimal solutions of MOLP.     

A Newton Method for Linear Programming

A fast Newton method is proposed for solving linear programs with a very large (10⁶) number of constraints and a moderate (10²) number of variables. Such linear programs occur in data mining and machine learning. The proposed method is based on the apparently overlooked fact that the dual of an asymptotic exterior penalty formulation of a linear program provides an exact least 2-norm solution to the dual of the linear program for finite values of the penalty parameter but not for the primal linear program. Solving the dual problem for a finite value of the penalty parameter yields an exact least 2-norm solution to the dual, but not a primal solution unless the parameter approaches zero. However, the exact least 2-norm solution to the dual problem can be used to generate an accurate primal solution if mn and the primal solution is unique. Utilizing these facts, a fast globally convergent finitely terminating Newton method is proposed. A simple prototype of the method is given in eleven lines of MATLAB code. Encouraging computational results are presented such as the solution of a linear program with two million constraints that could not be solved by CPLEX 6.5 on the same machine.     

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

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

A Linear Approximation for Chance-Constrained Programming

Decision environments involve the need to solve problems with varying degrees of uncertainty as well as multiple, potentially conflicting objectives. Chance constraints consider the uncertainty encountered. Codes incorporating chance constraints into a mathematical programming model are not available on a widespread basis owing to the non-linear form of the chance constraints. Therefore, accurate linear approximations would be useful to analyse this class of problems with efficient linear codes. This paper presents an approximation formula for chance constraints which can be used in either the single- or multiple-objective case. The approximation presented will place a bound on the chance constraint at least as tight as the true non-linear form, thus overachieving the chance constraint at the expense of other constraints or objectives.     

半定规划的限制逆问题与广义逆问题

本文提出了半定规划的限制逆问题与广义逆问题，利用半定规划的最优性条件，分别给出了其在l∞，l1,l2模意义下的数学模型，它们仍为半定规划问题。     

A Generalization of a Result in Linear Programming

The simplex method of linear programming depends upon a theoremconcerning the maximization of a linear function subject tolinear constraints. In the present paper this theorem is generalizedto one concerning the maximization subject to linear constraintsof a function which is an increasing function in each of a numberof linear functions. A method for deriving further extensionsof the theorem is suggested and a particular example workedout. It is shown also how the theorem leads to a simple algorithmin a particular case and it is suggested that other similarapplications may be found.     

线性规划对偶问题的一个注记

指出了线性规划对偶问题定义中的一个小漏洞,并作了改正     

Representations for the Weighted Moore-Penrose Inverse of a Partitioned Matrix

The weighted moore-Penrose inverse of a partitioned matrix A=(U V) is discussed. Representations for the weighted Moore-Penrose inverse of the matrix A are derived, which extend some early results.     

A Note on Shadow Prices in Linear Programming

Using convex analysis and a characterization of the entire family of optimal solutions to an L.P., we show that in order to obtain shadow prices, one has to solve a much smaller L.P. derived from any optimal tableau. We then show that positive as well as negative shadow prices for any constraint or for any combination of constraints can easily be computed by parametric linear programming. Some examples exhibiting the method are also included.     

线性规划的筛选迭代算法

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

一个新的解线性规划的神经网络

本文提出一个新的解线性规划的Hopfields-型网络。该网络基于线性规划的对偶理论,并使用了Sigmoid函数,但不需要预先给定的罚参数和乘法模拟器,我们证明该网络不仅全局收敛到线性规划的精确解,而且能同时解原规划和对偶规划。由于在该网络中没有使用乘法模拟器而利用了Sigmoid函数,因此该模型是很容易用硬件实现的。     

线性规划的基解算法

提出了求解线性规划问题的一种新方法-基解算法,它是一个不需引入人工变量,不必预先求出一个可行基的直接求解算法。     

求标准线性规划问题的一种截解法

本提出了求解线性规划问题的一种新思路，就是通过平行移动目标函数等值面，即改变目标函数作为参数的取值来截取基本可行解，甚至最优解。值得注意的是，本算法可能会克服由退化引起的迭代循环。     

Inverse Linear Difference Operators

For matrices whose elements are scalar linear difference operators, algorithms for checking invertibility (unimodularity) and constructing an inverse matrix (if it exists) are proposed. Their complexity is lower than that of other available algorithms. The differences of these algorithms from their differential analogues are discussed.