Javier F. Nadal

Objectives 

Make a brief report about the authors mentioned above, required for the Network Flow Programming course of the Operations Research and Industrial Engineering Department at the University of Texas at Austin

Context

The Transportation Models in the field of Network Flow Programming.

Antecedents

Probably  the first publication about the Transportation Model dates from 1781. By this time its author, Gaspard Monge (1746-1818), a well-known mathematician in the geometry descriptive field, worked under the orders of Napoleon Bonaparte in infrastructure works for his army. His work was published in the “Memoires de l'Academie des Sciences de l'Institut de France” [1] and consisted in minimizing the cost of backfilling n places with surplus brash from m other places; the brash provided by m origins a₁, a₂, …, a_m had to be moved to n destinations b₁, b₂, …, b_m with costs c_ij proportional to the distance between the origin i to the destination j. For a deeper discussion of the Monge work related with the transportation problem refer to the Buckard, Klinz and Rudolf's [2] paper.

Leonid Vitalyevich Kantorovich

In 1938, as a professor at the Leningrad University, he was giving counseling for the Laboratory of the Plywood Trust in an special kind of problems. Economically, it was a problem of delivering a raw material maximizing a linear equipment productivity under certain constraints. Mathematically, it was a problem of maximizing a linear function on a convex polygon.

He realized this mathematical problem had many economical forms such as work distribution for equipment, the best use of sowing area, rational material cutting, use of complex resources, distribution of transport flows (without knowing, this was the Monge problem, which was also stated before by A. Tolstoy in 1930 who gave an approximated solution, and later by F. Hichcock who gave origin to the name of Hichcock Transportation Problem in the modern literature). This was the reason for finding an efficient method for solving the problem.

One year later, in 1939, the Leningrad University Press printed a booklet called "The Mathematical Method of Production Planning and Organization" [3] which was dedicated to the formulation of the basic economic problems, their mathematical form, and a delineation of the solution method, and a first study of its economic implications. This contained in essence, the main ideas of the linear programming theories.

Later, in the 40’s, Tjalling C. Koopmans, George B. Dantzig, et al, found these results in their own way. But it wasn’t until the end of the 50’s, they knew each other contributions, and due to the initiative of Koopmans, his 1939's booklet was published in Management Science in 1960.

In 1975, Leonid V. Kantorovich and Tjalling C. Koopmans received the Novel Price in Economics for their contributions on the theory of the optimum allocation of resources.

According to a publication of SIAM News[4], Kantorovich, Dantzig and Von Newman are considered the founders of the linear programming.  

Frank Lauren Hitchcock

In 1941 Hitchcock published a mathematical solution for the Monge problem, for that reason in the modern books he receives the credit for this innovation. His work called "The Distribution of a Product from Several Sources to Numerous Localities" [5] gives the origin for the Hitchcock Transportation Problem analogous to the Monge formulation.

The Hitchcock Transportation Problem [6]

This problem is a special case among the linear programming problems that arises in numerous applications. It is formulated as a linear programming problem in the following way;

where U = {1,2,…, n} and V = {1,2,…,m}. Each element in V is called demand point and each element in U is called supply point. The classical example for this problem is the distribution of products from depots to customers; where the nodes in U represents the depots, the nodes in V represents the customers and an edge (i,j) Î U x V represents a distribution link from the depot i to the customer j. The model finds the minimal cost of product shipment through the complete bipartite graph in order to satisfy the demand at the nodes V and the supplies at the node U.

The graphical model would be the following;

 Note that there is an arc from every supplier to every costumer.

Tjalling Charles Koopmans

In 1942  Tjalling C. Koopmans was working as a statistician for the British Merchant Shipping Mission in Washington. His assignment was to help fit information about losses, deliveries from new construction, and employment of British-controlled and US-controlled ships into an integrated report. His problem can be described in the following way. Given a list of ports, the flows of a homogeneous ship-cargo can be described by a graph, whose vertices are the ports and whose edges represents the tonnage shipped between that pair of ports. Given also a fixed set of supplies at some ports and demands at others, an increase in the amount shipped from one particular port to another will cause compensating changes in the matrix of flows between other pairs of ports. In the paper Exchange Ratios Between Cargoes in Various Routes[7] written in 1942, Koopmans showed how to calculate these compensating changes and their consequences for the total cost expressed in ton-miles [8]. This problem is in essence, the Monge problem, one of the most elementary examples of a linear programming problem. But in 1942 the concept of linear programming had not been yet proposed in the West, and Koopmans was unable to see his work as an instance of this more general problem.

His work was well received by Combined Shipping Adjustment Board as an explanation of the "paradoxes of shipping" which were always difficult to explain to higher authorities.

In 1944, Koopmans joined the Cowles Commission for Research in Economics at the University of Chicago and he continued his study of the transportation problem initiated in 1942. By the end of 1946 he realized that his earlier problem of transporting a homogeneous commodity from a set of origins to a set of destinations so as to minimize the total cost of transportation could be formulated as a problem of minimizing a linear function of a number of variables, subject to a set of linear inequalities constraining the values assumed by these variables. He also proposed a method of solution based on an economic idea that was to become of central importance in his subsequent research.

Dr George B. Dantzig had initiated his work on linear programming while employed by the U.S. Department of the Air Force, and in the summer of 1947 he developed the details of the simplex method, an algorithm for their solution [8]. Several months earlier Koopmans had had a consequential meeting with Dantzig in which he realized the relationship between the linear programming problem of Dantzig with his transportation problem. Koopmans presented these ideas at a meeting of the International Statistical Conference in Washington in September 1947 which was published in 1949 as a paper called Optimum Utilization of the Transportation System [9]. 

Koopmans demonstrated that an efficient plan --a plan for which no alternative existed using less inputs and providing no less of any output-- would be associated with a vector of prices with a special property. The prices, intimately related to Dantzig's dual variables, would yield a zero profit for the activities used in that plan and a profit less than or equal to zero for all the remaining activities [8]. 

His strong convictions led him to make trips to the Soviet Union in the 60's, where he met Leonid V. Kantorovich. Time ago, he had developed a test for optimality and an outline of an algorithm for linear programming that was similar to but more cumbersome than the simplex method. In Kantorovich's work the problem of the optimal allocation of resources was approached not only from the point of view of a pure mathematician, but also with an economist's appreciation of the fundamental role played by prices in reaching an optimal decision [8]. Kantorovich's work helped to outline the final form of his model.

As it was said before, T. Koopmans and L. Kantorovich were honored with the Novel Prize in 1975 for their independent works in these fields. 

Conclusion

L. Kantorovich, F. Hitchcock and T. Koopmans have been central figures in the development of the modern economic science and played seminal roles in the modern theory of the allocation of scarce resources. They have independently developed a rational method for allocating resources so as to attain a given economic objective at the lowest cost. This is called the Transportation Problem, a special case of what subsequently became known as Linear Programming. 

They were a remarkable inspiring leaders of research who combined their mathematical power with a deep concern for the ultimate practical applications of their works.

All these reasons make them the main references in solving the Transportation Problem.

References

[1] Yacuzzi, E. & Rodríguez, V. (2002). Diseño e Implantación de un Sistema de Apoyo a las Decisiones basado en el Modelo de Transporte. Work paper.  

[2] Burkard, R., Klinz, B. & Rudolf, R. (1996). Perspectives of Monge Properties in Optimization. Discrete Applied Mathematics, 70, 95-161.

[3] Kantorovich, L. (1939). Mathematical Methods of Organising and Planning Production. Reprinted in Management Science, 1960.

[4] SIAM News. (1994). Professor George Dantzig: Linear Programming Founder Turns 80 [Online]. Available: http://www.stanford.edu/group/SOL/dantzig.html [Accessed 2002, July 5].

[5] Hitchcock, F. (1941). The Distribution of a Product from Several Sources to Numerous Localities. Journal of Mathematics and Physics, 20, pp. 224-230.

[6] Matsui, T. (1993). A Linear Time Algorithm for the Hitchcock Transportation Problem with Fixed Number of Supply Points. Unpublished.

[7] Koopmans, T. (1942). Exchange Ratios between Cargoes on Various Routes (Non-Refrigerated Dry Cargoes). Memorandum for the Combined Shipping Adjustment Board. Reprinted in Scientific Papers of Tjalling C. Koopmans, Springer Verlag, pp. 77-86, 1970.

[8] Scarf, H. National Academy Press. Biographical Memoirs: Tjalling Charles Koopmans [Online], Available: http://www.nap.edu/html/biomems/tkoopmans.html [Accessed 2002, July 5].

[9] Koopmans, T. (1947). Optimum Utilization of the Transportation System. Proceedings of the International Statistical Conference (Washington D.C.), 5. Reprinted as supplement to Econometrica, 17, 3-4,1949.