MATH39011 - 2007/2008
- Title: Mathematical Programming
- Unit code: MATH39011 (semester 1)
- Credits: 10
- Prerequisites: Basic linear algebra
- Co-requisite units: None
- School responsible: Mathematics
- Member of staff responsible: Dr. Mike Tso
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 Rn 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
- Convex function. Convex set. Fundamental theorem of linear programming.
- Examples: L1-regression. Diet problem. Cutting stock problem.
- Solution of LP problems by the simplex algorithm.
- Theorem of duality. Complementary slackness. Sensitivity analysis.
- Integer and mixed integer LP. Cutting planes. Branch and bound method.
- Knapsack problem. Transportation problem.
Textbooks
Teaching and learning methods
Two lectures per week plus one weekly examples class. In additiona students should expect to spend at least four hours each week on private study for this course unit.