I was reading about the "Fundamental Theorem of Linear Programming" Wikipedia - this theorem states that the maximum or the minimum of a linear program occurs at the corner regions.
I tried to do some research about this theorem but could not find out who originally proved it and in which year this theorem was proven.
For instance, was the "Fundamental Theorem of Linear Programming" known to Dantzig or Kantorovich when they developed the Simplex Algorithm?
Or did the Simplex Algorithm come before the actual formal proof of the "Fundamental Theorem of Linear Programming" - and the Simplex Algorithm originally was more of a "heuristic" instead of theoretically rigorous method? I.e. Did Dantzig and Kantorovich simply observe the Simplex Method to perform surprisingly well in many circumstances and had no idea that the maximum and the minimum of these linear programs were at the corners?
Thank you!
The fundamental theorem of linear programming (LP) states that every feasible linear program that is bounded below has an optimal solution in a zero-dimensional face (a vertex) of the feasible polyhedron.
This theorem has been extended by Tardella (2011) and I give a Reference below:
F. Tardella (2011) The fundamental theorem of linear programming: extensions and applications, Optimization, 60:1-2, 283-301, DOI: 10.1080/02331934.2010.506535
Abstract of Tardella's paper:
"The fundamental theorem of linear programming (LP) states that every feasible linear program that is bounded below has an optimal solution in a zero-dimensional face (a vertex) of the feasible polyhedron. We extend this result in two directions. We find a larger class of objective functions for which vertex optimality holds, and we give conditions guaranteeing the existence of an optimal solution in a larger family of faces of the feasible polyhedron. Our results also extend, with a very simple proof, the Frank–Wolfe theorem on the existence of an optimal solution to a Quadratic Program that is bounded below. We then apply our results to build up a general framework for obtaining upper and lower bounds and constant factor approximation algorithms for optimization problems. Furthermore, we show that several known results providing continuous formulations for discrete optimization problems can be easily derived and generalized with our extension of the fundamental theorem of Linear Programming. Finally, by exploiting the equivalence between continuous and discrete formulations of the problem of minimizing a function on a polyhedron, we prove polynomial-time solvability and present efficient algorithms for several new classes of continuous optimization problems."
F. Tardella's paper on Optimization (2011)