What is OR

Linear Programming


The first modules we developed in this series focused on linear programming. The father of linear programming is George Dantzig, who developed between 1947 and 1949 the foundation concepts for framing and solving linear programming problems. During WWII, he worked on developing various plans or proposed schedules of training, logistics supply and deployment which the military calls "programs." After the war he was challenged to find an efficient way to develop these programs. He came to recognize that the planning problem could be formulated as a system of linear inequalities. His next challenge involved the concept of a goal. At that time, when managers thought of goals, they generally meant rules of thumb for carrying out a goal. A navy man might have said our goal is to win the war and we can do that by building more battleships. Dantzig was the first to express the criterion for selecting a good or best plan as an explicit mathematical function that we now call the objective function. All of this work would have been of limited practical value without an efficient method, or algorithm, for finding the optimal solution to a set of linear inequalities that maximizes (profit) or minimizes (cost) of an objective function. He therefore proceeded to develop the simplex algorithm which efficiently solves this problem.

Economists were excited by these developments. Several attendees at a first conference entitled Activity Analysis of Production and Allocation went on to win Nobel prizes in economics with their work drawing on linear programming to model fundamental economic principles.

The first problem Dantzig solved, much to the chagrin of his wife, was a minimum cost diet problem that involved the solution of nine equations (nutrition requirements) with seventy-seven decision variables. The National Bureau of Standards supervised the solution which took 120 man days using hand-operated desk calculators. (His wife rejected the minimum cost diet as boring.) Nowadays, a standard personal computer could handle this problem in under a second. EXCEL spreadsheet software includes as a standard addition a module called "solver," which includes a linear programming solver.

As mainframe computers became available in the 50's and grew more and more powerful, the first major users of the simplex algorithm to solve practical problems were the petroleum and chemical industries. One use was to minimize the cost of blending gasoline to meet certain performance and content criterion. The field of linear programming grew exponentially and led to the development of non-linear programming in which inequalities and/or the objective function are non-linear functions. Another extension is called integer programming (combinatorics) in which the variables must take on only integer values. These disciplines are collectively called mathematical programming.

Back to What is OR?



Website by:
QuIC Solutions, Inc