Simplex algorithm

This article is about the linear programming algorithm. For the non-linear optimization heuristic, see Nelder–Mead method.

In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming.[1]

The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin.[2] Simplices are not actually used in the method, but one interpretation of it is that it operates on simplicial cones, and these become proper simplices with an additional constraint.[3][4][5][6] The simplicial cones in question are the corners (i.e., the neighborhoods of the vertices) of a geometric object called a polytope. The shape of this polytope is defined by the constraints applied to the objective function.

  1. ^ Murty, Katta G. (2000). Linear programming. John Wiley & Sons.
  2. ^ Murty (1983, Comment 2.2)
  3. ^ Murty (1983, Note 3.9)
  4. ^ Stone, Richard E.; Tovey, Craig A. (1991). "The simplex and projective scaling algorithms as iteratively reweighted least squares methods". SIAM Review. 33 (2): 220–237. doi:10.1137/1033049. JSTOR 2031142. MR 1124362.
  5. ^ Stone, Richard E.; Tovey, Craig A. (1991). "Erratum: The simplex and projective scaling algorithms as iteratively reweighted least squares methods". SIAM Review. 33 (3): 461. doi:10.1137/1033100. JSTOR 2031443. MR 1124362.
  6. ^ Strang, Gilbert (1 June 1987). "Karmarkar's algorithm and its place in applied mathematics". The Mathematical Intelligencer. 9 (2): 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR 0883185. S2CID 123541868.