You are here: Mathematics > undergraduate > undergraduate studies > course units > level 3 units > MATH39011
School of Mathematics

# MATH39011 - 2009/2010

General Information
• 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: Mr. M. Tso
Page Contents
Other Resources
• Materials will be available in lectures.

## 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

1. Convex function. Convex set. Fundamental theorem of linear programming.
2. Examples: L1-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. Further examples and applications.

### 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. In addition, students should expect to spend at least four hours each week on private study for this course unit.

### Assessment

End of semester examination (2 hours ) 100%

## Arrangements

Materials will be available in lectures. .