Shadow Prices in Multiple Objective Linear Programming

In two recent papers, the problems of the two-sided nature of shadow prices in degenerate L.P.s have been reviewed. Aukamp and Steinberg demonstrate that shadow prices and the optimal dual variables computed by L.P. packages do not necessarily correspond. Their analysis is completed by Mustafa Akgul, who shows that positive and negative prices can be easily computed by simple auxiliary programmes as well as by parametric programming methods. The original work on this subject by Strum discusses the pricing and accounting aspects of two-sided shadow prices. The purpose of this note is to extend the analysis of Akgul to multiple-objective linear programming (MOLP) models.     

The Computation of Shadow Prices in Linear Programming

The purpose of this paper is to demonstrate that when degeneracy is present in an optimal basic solution to a linear programming problem, the optimal values of the dual variables do not necessarily correspond to shadow prices. In such instances, major commercial L.P. packages (such as IBM's MPS and MPSX) may provide misleading information about the shadow prices. It will be shown how the actual values of the shadow prices may be determined, and the nature of the relationship between shadow prices and dual variables will be discussed.     

基于投入产出线性规划模型的燃料乙醇影子价格研究

影子价格能够反映资源的稀缺性及对国民经济的贡献程度.应用投入产出与线性规划相结合的分析方法,构建了投入产出线性规划模型,并基于笔者编制的2005年燃料乙醇投入产出表,针对燃料乙醇制造业部门的不同发展速度,运用投入产出线性规划模型对燃料乙醇的影子价格进行了具体测算.     

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

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

A Note on Degeneracy in Integer Linear Programming Problem

A set of three batches of 1000 randomly produced integer linear programming problems of different sizes was solved using a partial enumeration algorithm. That particular algorithm involves the initial ordering of the variables according to their attractiveness when considered individually. The results reveal that, as might have been expected, the most attractive variables appear very much more frequently than do the less attractive. Perhaps less expected is the fact that the average number of variables appearing in the optimum solution is considerably less than might have been anticipated. Thus, for example, the average number of variables which appear in a set of problems featuring 20 variables and 10 constraints is only 4.14, as against the 10 one would have been expecting in continuous LP problems of that size. It is argued that it is this inherent characteristic which results in truncation solution procedures being as effective as they are.     

关于线性规划基本定理的一点注记

本就线性规划基本定理的证明方法及过程提出一点修改意见。     

A Note on Redundancy and Linear Parametric Programming

A simple redundancy criterion for a system of linear inequalities is given. Considering a linear programming problem with linear inequality constraints the sensitivity analysis of the optimal solution of the right-hand side in combination with the redundancy criterion can help to identify redundant inequalities (constraints). The redundancy criterion is applied to a linear parametric problem which is enlarged by an auxiliary condition such as "stop the parametric procedure when a chosen constraint becomes redundant".     

关于线性规划问题熵障碍对偶法的注记

线性规划是目标优化问题中最常用的模型。关于大规模线性规划问题的有效求解问题一直受到人们的关注。熵障碍对偶法是继内点法之后,又一解线性规划问题的新的算法。本文讨论了熵障碍对偶法的推广形式及其梯度类算法的收敛性。     

关于线性规划单纯形法的注记

本文讨论了单纯形法中最优解和检验数之间的关系,以及确定主元列标号的不同原则。     

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

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

线性规划影子价格的求解判断方法探讨

针对线性规划对偶问题最优解不唯一时,在已有文献提出的对偶最优解不唯一的充要条件定理基础上,结合线性规划灵敏度分析,提出影子价格的求解判断的简单准则及其命题,并进行证明.最后,用算例加以分析,指出该判断方法简单易行,也可作为通过计算软件求解影子价格的准确判断方法.     

A Note on Diet Planning in the Third World by Linear and Goal Programming

This note sets out to counter the view that goal programming applied to diet planning offers little improvement over conventional linear programming techniques.     

A Note on Chance-Constrained Programming

A stochastic linear programme with chance constraints is considered. By allowing for the possibility of sampling, a so-called dynamic statistical decision model is developed, and the existence of an optimal decision rule is shown under appropriate continuity and compactness assumptions.     

关于直线拟合的注记

讨论了使残差的最大绝对值为最小准则和使残差的绝对值之和为最小的准则的直线拟合问题 ,采用线性规划可解决此问题 .最后讨论了多项式拟合的情况 .     

关于精确罚函数和线性规划的一个注记

本文给出了线性规划（LP）的解和其相应的精确罚函数解的等价性,证明是初等的,简明的。     

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.