by Robert Litan
Today, this problem is readily solved by typing in the required amounts in an application program available on the Internet.2 But before the age of the computer and, later, the Internet, someone had to come up with the mathematical technique for solving it, by hand (as is the case for virtually every other formula now easily solved by computers and often available on the Internet). The great Russian mathematician Leonid Kantorovich and American professor George Dantzig (see the following boxes) independently came up with the simplex method for doing this. Nobel Prize–winning economist George Stigler of the University of Chicago also outlined his own linear programming-based solution to the diet problem.3
The simplex solution method, which can be found in any textbook on operations research, or on the Internet,4 entails a process of trial and error: successive calculations are made, with improving results, until an optimum is reached. This is much like everyday life, the way humans learn from their mistakes, constantly becoming better—though unlikely perfect—in any endeavor they undertake. We will encounter the trial and error process in Chapter 6, when we discuss the use of experiments in both economics and the business world.
Linear programming was used for far more than solving diet problems. During World War II, the U.S. military secretly used the technique that Dantzig had largely developed as a way of reducing costs. After the war, the technique was described in the academic literature, and thereafter used widely in industry, for scheduling airline and shipping routes, planning the outputs of oil refineries, and minimizing costs for firms in the electricity and telecommunications industries.7
George Dantzig
George Bernard Dantzig—yes, his parents gave him his first two names in honor of George Bernard Shaw—was a long-time professor of operations research at the University of California at Berkeley and later Stanford University.5
Dantzig inherited his aptitude for mathematics from his father, who also was a mathematician. Born in Germany, his family emigrated to the United States early in the twentieth century, initially moving to Portland, Oregon, and later to Baltimore and then to Washington, D.C. During the family’s time in the nation’s capital, Dantzig’s mother worked as a linguist at the Library of Congress while his father tutored math at the University of Maryland, from which Dantzig earned his undergraduate degree in mathematics and physics. He obtained his doctorate in statistics at the University of California at Berkeley, after serving in the U.S. Air Force Office of Statistical Control during World War II. During his time in the Air Force, he developed techniques for allocating airplane production in an efficient manner.
One event during Dantzig’s graduate studies has become legend. During one of his statistics courses, the teacher and Dantzig’s eventual thesis adviser wrote two famous unresolved problems in statistics on the blackboard. As he was late to class, Dantzig thought they were homework problems, and a few days later handed in the solutions. Several weeks later, the adviser told Dantzig that he had just solved two of the most difficult, unresolved problems in statistics, and on that basis alone the statistics department awarded Dantzig his PhD.6
After the War, Dantzig first worked at the Rand Corporation, then moved to the University of California at Berkeley and later to Stanford. During the course of his career he won many professional prizes for his work, which found its way into practical uses in a wide range of industries described in the text.
In academia, linear programming became the foundation of the field of operations research, a cross between economics and math, to which a number of other prominent economists, such as Kenneth Arrow, Tjalling Koopmans, and Robert Dorfman, made important contributions (some won Nobel Prizes for their other work).8 William Baumol, who is profiled later, wrote a classic textbook explaining various operations research techniques.9
The Transportation Problem
As indicated earlier, linear programming has been applied in many industries, primarily with the objective of minimizing costs. The founders, executives, employees, and consumers in these industries have many unseen and mostly unknown (outside of the economics profession itself) economists and mathematicians to thank.
One of the more widely known applications of linear programming is known as the transportation problem, outlined by a French mathematician, Gaspard Monge. Simply stated, this problem involves figuring out the least costly way of sending outputs of some items—say raw materials—from where they are sourced (for example, in mines or in forests) to destinations for further processing into finished goods. The sources may not be equally productive, the costs for sending the materials or supplies may differ from one route to another, and the distances between the various sources and destinations also vary. Figuring out how much to send from each source to each destination via a route that minimizes overall costs is the essence of the transportation problem.
Instead of sending materials to different locations, imagine you are running an airline that is sending people from and to different places. Suppose further there are multiple routes the planes can fly (in the old days, as we will see in Chapter 9, one had to get government approval before flying any route, which was essentially impossible for new entrants); your airline has a limited number of planes, each with a fixed number of seats; the market conditions dictating the prices you can charge for seats are constantly changing; some costs rise in a linear fashion as the numbers of flights increase (salaries for pilots, flight attendants, and maintenance personnel, whether they are employees or contractors); and other costs are linearly related to the route distance (principally fuel). Assuming you can get landing rights and gate slots at the takeoff and landing airports, the transportation problem for airlines becomes: What combination of routes will maximize your profits? Or, if you don’t know the prices the market will let you charge, at the very least, what combination of routes will minimize your costs given the size of your workforce, salary structure, the number of your planes, and total miles they can fly?
It doesn’t take much thought to realize that this is a really complicated problem, one that grows exponentially more difficult the larger the airline, and thus the more planes and routes the airline can fly. As William Baumol noted in his textbook on the subject of operations research, there are literally billions of different combinations of inputs and outputs that are theoretically possible even for a firm with fewer numbers of products and constraints than are involved in setting the traffic patterns for today’s airlines.10 Picking out the one or the few items that minimize costs or maximize profits is thus akin to finding the proverbial needle in the haystack. But with a powerful detection device such as linear programming, aided by modern computers, one can yield the result in seconds or less. Now you can understand why transportation companies, like airlines, trucks, and railroads, can and do use programming techniques to solve these problems and to update the solutions on a regular basis.
It took more than century before a method for solving the transportation problem, as Monge identified it, was invented. Leonid Kantorovich first devised a solution to the problem during World War II. Refinements since then have enabled transportation problems to be solved through techniques simpler than the simplex method developed initially to cope with standard linear programming problems. In addition, the structure of the transportation problem has been used to develop ways of optimally assigning jobs where employees can make the most valuable contributions, in what economists have called the assignment or matching problem, a subject I take up in Chapter 7.
Critical Path Method
A variation of linear programming, widely used in large organizations to manage large projects with multiple interdependent tasks, is critical path analysis. CPM involves listing all of the activities or tasks that are required to complete a project, such as constructing a building or an airplane, or undertaking a research and development project; the estimated time to complete each task; and the extent to which the various activities are dependent on one another (you can’t build the first, second, and third floors, and so on
, until the foundation and each of the preceding floors is completed).
Leonid Kantorovich
The original giant in operations research, the one who first discovered the simplex method for solving linear programming programs (Dantzig later replicated and refined it), was the great Russian mathematician and economist Leonid Kantorovich. He was born in 1912 in Russia.
Kantorovich was a mathematical prodigy, beginning his college education at Leningrad University at the age of 14, where he eventually earned his PhD and became a full professor in the faculty of mathematics at the age of 22.
Kantorovich eventually worked for the Soviet government, developing linear programming after being assigned the problem of optimizing production in the plywood industry. During World War II, he was put in charge of safety. In the depth of the famous winter of 1941 to 1942, during the siege of Leningrad, he walked between cars on the ice of Lake Ladoga so he could better calculate the optimal distance between cars on the ice to ensure the cars did not sink. After the war, given its command-and-control economy, the Soviet government adopted linear programming to plan its economy.
In 1949, Kantorovich was awarded the Stalin Prize, and for his courage during the war he was given the Order of the Patriotic War, both remarkable given his Jewish background and the infamous anti-Semitism in Russia and later in the Soviet Union. He won the coveted Lenin Prize in 1965 for his work.
In 1975, Kantorovich shared the Nobel Prize with Tjalling Koopmans (one of my mentors in graduate school who kindly took me under his wing). Kantorovich was not aware until the 1950s that linear programming techniques had been independently developed in America after he developed them. He died in 1986.
Using just these values, mathematical techniques—similar to those involved in linear programming—have been developed for determining the quickest path to completing the entire project.11 Since time is money, the quickest path is generally the one with the least cost, though sometimes, there are risks associated with the fastest path. In these situations, there are tradeoffs between getting it right and getting it done at least expense.
Today, many companies follow the logic of CPM but use diagrams to analyze it. One of the most commonly used diagrams is the Program Evaluation and Review Technique, or PERT chart. CPM, PERT, or some variation is commonly used by major weapons contractors, by the military itself, and by software companies—or firms that require multiple tasks, pursued in parallel and interdependently. CPM software is also widely available to assist companies in organizing complex projects at minimum cost.
The Role of Government and Other Thoughts on Programming Problems
Up to this point, I have mentioned government only in passing, largely in connection with satisfaction of the needs of the military in both the United States and Russia during World War II. But the U.S. government, the Office of Naval Research in particular, played an important role in funding basic research in linear programming in the United States after the end of the war. Along with the role the government played in launching the Internet (also initially for military purposes), and later in supporting research on Internet search algorithms, the government did what most economists routinely have called on the government to do: to support basic research with broad public benefits that would not otherwise be funded by individual companies at the socially optimal level because the gains from the research would be too widely diffused.
There are two other aspects of linear programming that deserve mention before moving to our next topic. First, for each application of linear programming to minimizing costs there is a dual that calculates the way to maximize profits. Essentially, all the signs in the original problem are reversed (instead of the constraints being expressed as amounts greater than a given sum, they are stated as being less than a particular amount). In addition, the objective is changed from minimization to maximization. The reference above to maximizing profits in the airline example, or extending it to maximizing profits in any plant with multiple outputs and inputs, are examples of duals of a cost minimization problem.
Because the values of the inputs into a production process represent the amount by which an additional input, say of labor or a certain material, contributes to the profits of the firm, economists call these values “shadow prices.” For example, suppose your firm had a linear programming dual in which the objective was to maximize profits and one of the constraints is that each employee works no more than 40 hours per week. The dual calculates, among other things, the additional gain in profits from having employees work a marginal unit, say an average of one more hour per week. The result, or the shadow price of labor, would be marginal value of an additional hour of work—a number you might like to have in comparing that figure to the overtime hourly pay the law may require you to pay those employees.
Second, linear programming derives its name from the fact that all the key relationships, say between costs and output, are linear—that is, they are multiplied by the same constant factor. Not all relationships in the world work that way, however. Typically, output per unit of output falls as more is produced—this is the notion of diminishing returns. The opposite of diminishing returns is economies of scale, which arise when the average cost of something falls the more of it is produced.
In either situation of diminishing or increasing returns, some or possibly all of the relationships between costs and output can be nonlinear—that is, the graph of such a relationship is not a straight line. Not surprisingly, techniques for solving nonlinear programming problems have surfaced, and represent an advance over the initial linear programming solutions. As a general rule, where one has diminishing returns, the linear programming solution will recommend too few activities, products, or routes (in the case of transportation networks discussed next). Conversely, in the presence of increasing returns or economies of scale, the linear solution will recommend too many activities, products, or routes. Since the real world is often not linear (though it may be close enough), nonlinear programming solutions are often more realistic.
William Baumol
I could have profiled William Baumol in almost any of the chapters in this book, that’s how versatile and prolific he has been throughout his distinguished career, which marks him as one of the greatest American economists of the last half century. I chose to do it here, however, because he published extensively on linear programming and operations research techniques in the early stages of his career, and as the endnotes indicate, I draw extensively in this chapter from the latest edition of one of his textbooks on these subjects.12
Baumol spent most of his academic career as a professor of economics at Princeton University and then after his “retirement” (which never happened), as professor of economics and director of the entrepreneurship center at New York University’s Stern School of Business. He is one of the rare breed of economists who is both mathematically gifted and who writes clearly and engagingly.
During his long career—he was still working on a number of book-length projects past the age of 90—he developed novel insights, tested important hypotheses, and wrote about an astonishingly wide range of microeconomic and macroeconomic subjects: the theory of contestable markets, growth theory, monetary economics, macroeconomic fluctuations and dynamics (the subject that introduced me to Baumol as a junior in college when I used his textbook on this subject), and the economics of the performing arts (live theater, orchestras, dance performances, and so on, which is not an accident, since he is an accomplished artist as well). He is the coauthor, with Alan Blinder (another of America’s great economists, and one of its best writers, profiled in Chapter 12), of multiple editions of an introductory economics textbook.
Baumol may be best known for the disease named after him. Baumol’s disease asserts that the costs of some economic activities are condemned to rise at a rate significantly greater than the economy’s rate of inflation because the quantity of labor required to produce these services is difficult to reduce. Since the Industrial Revolution, labor-
saving productivity improvements have been occurring at an unprecedented pace in most manufacturing activities, reducing the cost of making these products even as workers’ wages have risen. However, in some service industries (such as health care, education, and the live performing arts, among others) automation is not always possible. As a result, labor-saving productivity improvements in these activities occur at a rate well below average for the economy. Therefore, the costs in these service industries increase at a much faster rate than that of inflation. Yet even Baumol recognizes that technology—sound recordings in the case of music and the various Internet-based methods of education that continue to proliferate—may help to alleviate his productivity disease.
During 2005 to 2007, I was privileged to coauthor (with Carl Schramm) a book and a number of articles on entrepreneurship and capitalism with Will Baumol. I consider the book, Good Capitalism: Bad Capitalism, my best to date (outside of this book), and collaborating with Baumol was the reason why.
Learning by Doing
Toward the beginning of the last chapter, I recounted the standard textbook approach to pricing—set your price at marginal cost, or a truly competitive market will force you to do it. In addition, economists typically assume diminishing returns set in at some point in business. It is progressively harder and more costly, for example, to squeeze out cost savings as one produces more of an item. Or if you’ve heard the phrase “Let’s first pick the low-hanging fruit,” you’re hearing an application of diminishing returns. The phrase implies that once the easily picked fruit—likely the fruit on a tree that is most visible—is picked, it is more time-consuming, and thus more costly, to fumble through the tree looking for the hidden pieces.