This week’s That’s Maths in The Irish Times ( TM030 ) is about Linear Programming (LP) and about how it saves millions of Euros every day through optimising efficiency.
A Berkeley graduate student, George Dantzig, was late for class. He scribbled down two problems written on the blackboard and handed in solutions a few days later. But the problems on the board were not homework assignments; they were two famous unsolved problems in statistics. The solutions earned Dantzig his Ph.D.
With his doctorate in his pocket, Dantzig went to work with the US Air Force designing schedules for training, stock distribution and troop deployment, activities known as programming. He was so efficient that, after World War II, he was given a well-paid job at the Pentagon with the task of mechanising the program planning of the military. There he devised a dramatically successful technique, or algorithm, which he named linear programming (LP).
Left: George Dantzig (1914-2005), the American mathematical scientist who devised linear programming and the simplex algorithm. Right: The simplex algorithm moves along the edges of the polytope until it reaches the optimum solution [Image Wikimedia Commons].
LP finds the maximum value of a quantity such as output volume or total profit, subject to the constraints. This quantity, called the objective, is also linear in the variables. A real-life problem may have hundreds of thousands of variables and constraints, so a systematic method is needed to find an optimal solution. Dantzig devised a method ideally suited to LP, called the simplex method.
At a conference in Wisconsin in 1948, when Dantzig presented his algorithm, a senior academic objected: “But we all know the world is nonlinear.” Dantzig was nonplussed by this put-down, but an audience member rose to his defence: “The speaker titled his talk ‘Linear Programming’ and carefully stated his axioms. If you have an application that satisfies the axioms, then use it. If it does not, then don’t.” This respondent was none other than John von Neumann, the leading applied mathematician of the twentieth century.
LP is used in a number of Irish industries. One interesting application by the Forestry Board, Coillte, is harvest scheduling. This enables decisions on when and where to cut trees so that, over the long term, financial benefits are optimised. A more advanced system, which incorporates environmental and social constraints in addition to economic factors, is under development by Coillte and UCD Forestry.
The acid test of an algorithm is its capacity to solve the problems for which it was devised. LP is an amazing way of combining a large number of simple rules and obtaining an optimal result. It is used in manufacturing, mining, airline scheduling, power generation and food production, maximizing efficiency and saving enormous amounts of natural resources every day. It is one of the great success stories of applied mathematics.
ThatsMaths 