21.0线性规划发展简史 19世纪末,康特罗维奇和F.L. Hitchcock等研究运 输问题,但其工作长期未被人们所知。由于战争的需要, TC. Koopmans重新独立研究了运输问题。 ·1947年,GB. Dantzig发表单纯形法,应用于与国 防有关的问题。该法实用而有效。单纯形法被认为是20 世纪10大算法之一(其中还有快速 Fourier变换算法等)。 ·但1972年,V.Ke和 G. Minty给出病态例子,用 单纯形法求解可能要检査遍所有的顶点才能得到最优解, 所用时间为O(2").故单纯形法为指数时间算法。 ◎2007 Fang Weiguo School of economics and management© 2007 Fang Weiguo School of Economics and Management