Linear programming grew out of attempts to solve systems of linear inequalities, allowing one to optimise linear functions subject to constraints expressed as inequalities. The theory was developed independently at the time of World War II by the Soviet mathematician Kantorovich, for production planning, and by Dantzig, to solve complex military planning problems. Koopmans applied it to shipping problems and the technique enjoyed rapid development in the postwar industrial boom. The first complete algorithm to solve linear programming problems, called the simplex method, was published by Dantzig in 1947 and in the same year von Neumann established the theory of duality. In 1975, Kantorovich and Koopmans shared the Nobel Prize in Economics for their work and Dantzig’s simplex method has been voted the second most important algorithm of the 20th century after the Monte Carlo method. Linear programming is a modern and immensely powerful technique that has numerous applications, not only in business and economics, but also in engineering, transportation, telecommunications, and planning.
Learning Outcomes
By the end of the module students should be able to:
Explain the basic techniques of linear programming (graphical method and simplex method);
Construct linear programming models of a variety of managerial> problems and interpret the results obtained by applying the linear programming techniques to these problems;
Explain why and when the simplex method fails to provide a solution and how to resolve such a situation;
Present, prove and use the results of duality theory and interpret them;
Explain the computational complexity of SIMPLEX and LP.
Assessment
24561-02 : Raw Module Mark : Coursework (100%)
Assessment Methods & Exceptions
1 hours Written Unseen January Examination (80%); In-course Assessment (20%).