登入選單

返回Google圖書搜尋

Origins of the Simplex Method

George B. DantzigStanford University. Systems Optimization Laboratory

出版	Stanford University, Department of Operations Research, Systems Optimization Laboratory, 1987
URL	http://books.google.com.hk/books?id=59wEAAAAIAAJ&hl=&source=gbs_api

註釋

In the summer of 1947, when the author first began to work on the simplex method for solving linear programs, the first idea that occurred to him is one that would occur to any trained mathematician, namely the idea of step by step descent (with respect to the objective function) along edges of the convex polyhedral set from one vertex to an adjacent one. He rejected this algorithm outright on intuitive grounds - it had to be inefficient because it proposed to solve the problem by wandering along some path of outside edges until the optimal vertex was reached. He therefore began to look for other methods which gave more promise of being efficient, such as those that went directly through interior. Today we know that before 1947 that five isolated papers had been published on special cases of the linear programming problem by Monge (1781), Fourier (1824), de la Vallee Poussin (1911), Kantorovich (1939), and Hitchcock (1941). Fourier, Poussin, and Hitchcock proposed as a solution method descent along the outside edges of the polyhedral set which is the way we describe the simplex method today. There is no evidence that these papers had any influence on each other. Evidently they sparked zero interest on the part of other mathematicians, an exception being a paper Appell (1928) on Monge's translocation of masses problem. These references were unknown to the author when he first proposed the simplex method. As we shall see the simplex algorithm evolved from a very different geometry, one in which it appeared to be very efficient. (Author).