论文部分内容阅读
§1 引言 1984年美国印度裔青年数学家Karmarkar提出了一种新的具有多项式时间复杂性的求解线性规划的方法,其迭代次数是O（nL）阶,运算次数是O(n<sup>7/2</sup>L)阶（L为计算机表示数据的字长）,低于哈奇扬的椭球方法,而且Karmarkar还声称该方法计算速度比经典的单纯形方法快五十倍。一时间这一研究成果成为轰动运筹学界与数学界的重要新闻。然而许多专家对这一宣布持怀疑态度。特别是由于在此前不久当第一个多项式时间的LP方法——椭球方法问世后,也曾有