# How applied maths can help money grow on trees

## Linear programming combines large numbers of simple rules to solve real-world problems

A Berkeley graduate student, George Dantzig, was late for class. He scribbled down two problems from 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 PhD.

With his doctorate in his pocket, he 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 the second World War, he was given a well-paid job at the Pentagon, with the task of mechanising the programme planning of the military. There he devised a dramatically successful technique, or algorithm, which he named linear programming (LP).

LP is a method for decision-making in a broad range of economic areas. Industrial activities are frequently limited by constraints. For example, there are normally constraints on raw materials and on the number of staff available. Dantzig assumed these constraints to be linear, with the variables, or unknown quantities, occurring in a simple form. This makes sense: if it requires four tons of raw material to make 1,000 widgets, then eight tons are needed to make 2,000 widgets. Double the output requires double the resources.

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.