We are presenting a theory whose official birth was at the heart of the twentieth century and in fact in the years right after the Second World War. However, all the readers are familiar with the method of Lagrange multipliers from Calculus, named after Joseph Louis Lagrange (1736-1813) who considered equality constrained minimization and maximization problems in 1788, in the course of the study of a stable equilibrium for a mechanical system.
The famous French mathematician Joseph B. Fourier (1768-1830) considered mechanical systems subject to inequality constraints, in 1798, though Fourier died before he could raise any real interest of his new findings to the mathematical community. Two students of Fourier|the famous mathematician, Navier, in 1825, and the equally famous mathematical economist, Cournot, in 1827, without mentioning the work of Fourier|rediscovered the principle of
Fourier, giving the necessary conditions for equilibrium with ad hoc argument which make specifi c reference to the mechanical interpretation.
In 1838, the Russian mathematician Mikhail Ostrogradsky (1801-1862) gave the same treatment in the more general terms. He asserted without referring to Joseph B. Fourier, that at the minimizer the gradient of the objective function can be represented as a linear combination, with nonnegative multipliers of the gradients of the constraints.
It is worth noticing that Ostrogradsky was a student in Paris before he went to St. Petersburg, and he attended the mathematical courses of Fourier, Poisson, Chauchy and other famous French mathematicians.
The Hungarian theoretical physicist Julius Farkas (1847-1930) focused on the mathematical foundation and developed a theory of homogeneous linear inequalities which was published in 1901. However, the first effective acknowledgment of the importance of the work of Farkas was given in the Masters thesis of Motzkin in 1933. But, the Farkas Lemma has to wait almost half a century to be applied. American mathematicians also started developing a theory for systems of linear inequalities followed by a paper on “preferential voting” published in The American Mathematical Monthly in 1916.
Note that the theory of linear programming did not just appear overnight. Linear programming depends on development of other mathematical theories and mathematical tools, one of these is of course Convex Analysis, which was not known well before.
The birth of the linear programming theory took place in two different, equally developed countries: the USSR and USA, but the motivating forces were also entirely different.
In the USSR, the father of linear programming is Leonid Vitalievich Kantorovich (1912{1996) and he is well known in the mathematical community for his achievements in linear programming, mathematical economics and functional analysis. He was awarded the Nobel Prize in 1975 together with T. C. Koopmans (1910-1985).
In the year 1939, Kantorovich was a young professor at the Leningrad University. A state fi rm that produced plywood and wished to make more efficient use of its machines contacted Kantorovich for a scientific c advice. The aim was to increase the production level of five different types of plywood, carried out by eight factories, each with different production capacity. Kantorovich soon realized that this problem has a mathematical structure.
In 1939, Kantorovich discussed and numerically solved the optimization problem under inequality constraints, in his small book, which was translated to English in 1960. In this book, Kantorovich presented several microeconomic problems from the production planning of certain industries. But, till 1958, economists in the USSR were not in favour to use the theory given by Kantorovich.
In 1960, at the Moscow Conference, economists discussed for the first time the use of mathematical methods in economics and planning, and later in 1971 for optimal planning procedures.
The work of Kantorovich was available to the rest of the world in 1960, when Tjalling Carles Koopmans (1910-1985) published an English translation of Kantorovich’s work in 1939.
Meanwhile, a similar line of research on inequality constrained optimization took place in the USA independent of the work of the Russians. During the Second World War from 1942 to 1944, Koopmans worked as a statistician
at the “Allied Shipping Adjustment Board” and was concerned with some transportation models.
In the same period, George B. Dantzig (1914-2005), who is recognized as the Western Father of Linear Programming, collaborated with the Pentagon as an expert of programming methods, developed with the help of desk calculators. Dantzig finished his studies and became a PhD in mathematics soon after the war ended.
Job opportunities came from the University of California at Berkeley and from the Pentagon. The simplex method discovered by Dantzig to solve a linear programming problem was presented for the first time in the summer of 1947. In June 1947, Dantzig introduced the simplex algorithm to Koopmans who took it to the community of economists
namely, K. J. Arrow, P. A. Samuelson, H. Simon, R. Dorfman, L. Hurwiez and others, and the Simplex method became quite a potential method. The Simplex algorithm has been declared as one of the best 10 algorithms with the greatest influence on the development and practice of science and engineering in the twentieth century.
Cleve Barry Moler, the chairman of the Computer Science department at the University of New Mexico, started developing MATLAB in the late 1970s. He designed it to give his undergraduate students for accessing LINPACK (Linear Algebra Subroutines for Vector-Matrix operations) and EISPACK (To compute eigenvalues and eigen vectors)
general purpose libraries of algoritms. It soon became popular to other universities also and found a strong interest among the students of applied mathematics. Jack Little and Steve Bangert attracted with this new programming environment and rewrote several developed MATLAB functions in C. Moler, Little and Bangert founded the Mathworks, Inc., in 1984.
MATLAB was first adopted by researchers and practitioners in control engineering, Little’s specialty, but quickly spread to many other domains. It is now also used in education for learning and teaching.