线性规划的多项式算法

《线性规划的多项式算法》，线性规划内点法开创性著作。Л.Г.哈奇安著。发表于苏联科学院报告1979年244。中译文载于《应用数学与计算数学》1980年第2期。

内容简介

本文被认为是线性规划算法研究上的一个重大的理论突破，开创了线性规划内点算法的研究领域。本文以70年代由蓄尔创造的椭球方法的思想为基础，构造了一系列椭球以搜索一线性不等式组的解。这一算法的运算次数为O(n3(n2+m)L)，所需精度为O(nL)，所需内存为O(nm+n2)个数的数组，而数组内的数的长度为O(nL)。这里L是整个问题m输入长度，又因一个线性规划问题利用对偶理论很容易将多项式等价地化为一个线性不等式组的相容性问题，从而该算法提供了一个解线性规划的多项式算法。算法的理论价值是重大的，但由于其要求精度过高而不太实用。针对这一问题刺激起了对线性规划内点法的研究，具有重大实用价值的卡麦卡算法即为其中的重要成果。哈奇安由于本文的成果曾获国际运筹学奖。

作者简介

Л.Г.哈奇安(Л.Г.Хациян)，苏联数学家。

工具书指南

工具书品种和数量的日益增多，使人们面临着一个如何选择的问题，首先要知道有哪些关于解决该问题的工具书可利用，这些工具书以哪本为善，这就需要有工具书的工具书（也称工具书指南）^[1]——工具书指南大体分为三类：

1.以教学为目的：以培养学生的情报意识，提高他们在学习和科学研究活动中利用工具书解答疑难和独立检索文献的能力为主要目标。结合教学要点介绍常用的、重要的和最新出版的工具书，如：《中文工具书使用法》等。

2.以普及工具书知识为目的：既给读者提供有关文献和工具书的基础知识，同时，或以工具书类型为纲重点介绍重要的工具书，或以问题为线索，重点介绍常用的工具书^[2]，如：《参考工作与参考工具书》等。

3.工具书的工具书：读者按它的指引，知道解决某一门有什么工具书可供查考，从而开拓视野，提高学习与科研的效率，如《中国工具书大辞典》等。

视频