MATH30005 - 2006/2007

 

Specification

Aims

To introduce students to the mathematical foundations and algorithmic basis of linear programming and related techniques. To give practice in modelling and to provide stimulus and motivation for the further study of advanced mathematical programming techniques.

Brief Description of the unit

Mathematical programming techniques seek to optimize a function in Rⁿ subject to given constraints. Such techniques have found widespread application in operational research, science, engineering, economics and business. Whilst the origins of the subject are often traced to Dantzig's discovery of the simplex algorithm for linear programming in 1947, the conceptual framework is far wider.

Learning Outcomes

At the end of the course students will:

• understand the fundamental properties of linear programming (LP) solutions;
• be able to solve a small-scale LP by use of a (reduced) simplex tableau;
• be able to formulate LP's and integer problems (ILP) in the context of an application;
• be able to solve small-scale ILP's and apply methods based on duality theory.

Syllabus

1. Convex function. Convex set. Fundamental theorem of linear programming.
2. Examples: L₁-regression. Diet problem. Cutting stock problem.
3. Solution of LP problems by the simplex algorithm.
4. Theorem of duality. Complementary slackness. Sensitivity analysis.
5. Integer and mixed integer LP. Cutting planes. Branch and bound method.
6. Knapsack problem. Transportation problem.

Textbooks

D. G. Luenberger, Linear and Non-Linear Programming, Addison-Wesley, 1984;

V. Chvatal, Linear Programming, Freeman, 1983.

Teaching and learning methods

Two lectures per week plus one weekly examples class.

Assessment

 

End of semester examination (2 hours ) 100% .

to the top

Arrangements