A Generalization of the Transportation Method of Linear Programming

The transportation method of linear programming is extended to a more general class of problem, for which the "stepping-stone method" of Charnes and Cooper fails. The method is applicable to various problems in the optimum scheduling of production and transport.This paper reviews the relevant theory, and then describes an efficient computational method, applicable to computers of moderate capacity. Many features of the transportation method are retained. In particular, the amount of information which must be retained, at each stage of calculation, is much less, for a large problem, than is required for the simplex or revised simplex methods.     

A Generic Result in Linear Semi-Infinite Optimization

In this paper we consider the space of all the linear semi-infinite programming problems with the same index set, endowed with a suitable topology. We provide a constructive proof of the following generic result: if we confine ourselves to the class of problems having a bounded set of coefficient vectors (those vectors appearing in the left-hand side of the constraints), the set of those problems which have a strongly unique optimal solution contains an open and dense subset of the set of solvable problems in the same class.     

A Partitioned Inverse in Linear Programming

This note deals with linear programs in which a subset of the constraints have a special structure. This structure allows linear equations involving these constraints only to be solved particularly easily, e.g. GUB rows. A method is described for restricting the gaussian elimination in LU decomposition to the non-special rows.     

一类线性规划问题的快速解法

研究了在组合投资和多属性决策指标权重确定中有着重要应用的一类线性规划问题,得到了该类线性规划问题有可行解的充要条件,以及在有可行解的情况下寻求最优解的快速解法.     

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.     

线性规划分解筛选法的一个注记

[1][2]提出了求解线性规划问题的一种方法－分解筛选法,[3]证明了[2]的命题A是错误的,本进一步证明,用分解筛选法筛选出变量不一定是最优基变量。     

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.     

线性规划的基解算法

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

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

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

线性规划在回归分析中的应用

线性回归中,针对最小二乘法的两个替代准则一绝对离差和最小准则以及最大绝对离差最小准则,利用线性规划技术建立回归预测模型。实用分析表明,线性规划模型具有较好的预测效果,有郊地消除了统计数据中异常值对回归方程的影响。     

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.     

A Linear Programming Model of Seasonality in Milk Production

Intra-year milk supply patterns depend largely on the distribution of cow calving dates which in turn are influenced by climatic factors. The most important and least costly input to milk production is grass and the fresh growth and high digestibility of grass in spring and early summer often gives rise to a highly seasonal distribution of calvings resulting in a seasonal milk supply pattern. However, milk for liquid consumption and production of certain perishable milk products must be produced to meet a constant consumer demand throughout the year, necessitating a considerable amount of production outside the least cost period. The solution to this linear programming model gives the distribution of calving dates which will ensure the demand constraints are satisfied while minimizing production costs, and the solution to the dual gives a set of seasonal prices which should be paid to producers, equitably compensating them for the costs they incur.     

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

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

线性规划的筛选迭代算法

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

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

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

线性规划问题的一种新的摄动法

在用单纯形方法解线性规划的问题时，不可避免会出现退化情况，而某些退化情况会导致循环。目前采用的避免循环的方法一共有两类：传统的摄动法（字典序）和Bland方法。本分析了传统摄动法的一些不足，给出了一种新的摄动法。     

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

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