%0 Journal Article
%T 线性规划计算的复杂性
%A 黄光明
%A 格雷汉
%J 科技导报
%P 65-67
%D 1980
%X 1979年11月7日,《纽约时报》第一版上刊出了一篇文章,开头就说“苏联无名数学家的新发现震动了数学和数值分析的世界”,还说这一发现可能应用到气象予报、工业规划、原油提炼、大工厂作业表设计、巡回路线问题和密码设计等方面。这样一个耸人听闻的新发现到底是怎么一回事呢?为什么它会有这样大的威力呢?这个新发现就是1979年1月《苏联科学院院刊》发表的一位年青学者哈强(Khachian)关于线性规划的椭球算法的研究报告。这个报告宣布了整系数线性规划不是一个NP完全问题。到目前为止,这个新发现还只是计算理论上的一个重要发现,还要做很多工作才能真正用于计算。
%U http://www.kjdb.org/CN/abstract/abstract7468.shtml