线性不等式组的一种新算法

New Algorithm for System of Linear Inequalities

介绍线性不等式组的一种以旋转运算为基础的直接解法。由于这种方法无须添加任何变量,计算用表非常紧凑。不仅使每次迭代的计算量较小,而且可以方便地从理论上分析问题,证明了此算法在每次迭代中按最小下标规则选择入出向量可以避免循环。计算机实验表明,该算法可以非常有效地求解马科维兹的资产组合选择模型。

A pivoting-based algorithm for the system of linear inequalities is proposed. Since it solves the system directly without adding any variables, a compact form is used for operations. It not only requires less computation for each iteration but also makes easy the theoretical analysis for the characteristics of the solved problem. It is proved that this method terminates as long as the entering and leaving variables are selected by the smallest-subscript rule in each iteration. This proof is essentially that proposed by G.B. Bland, but varies greatly in the form. The experiment shows that this method is very efficient for solving Markowitz抯 portfolio selection model (convex quadratic programming).