Mathematical Programming III

Go to this course in the University Course Planner.

Description

Objective

To introduce the students to algorithms for solving network optimisation problems and other discrete optimisation problems. At the end of this subject, students should be able to analyse certain network optimisation problems and provide the features of a mathematical model. be able to solve certain network optimisation problem and to interpret the result; write computer code for algorithms as studied in class; understand how such algorithms are constructed and hence be able to adapt the methods to related problems; be aware of complexity issues for optimisation algorithms. present a mathematical argument to peers (via a tutorial presentation).

Content

maximum flow problems in networks, including Ford-Fulkerson theorem, and a polynomial algorithm for solving such problems; an application of the first section: an example of how a simple algorithm can be used to construct more complex algorithms; in this case the Hungarian method for solving the Transportation problem; the Out-of-Kilter algorithm for solving the minimum cost circulation problem: another example of an Primal-dual algorithm; a selection of other network optimisation topics; advanced linear programming including an introduction to integer programming; if time permits, an introduction to interior point methods for LP's.

Liz Cousins Lecturer for this course

Delivery

5 one-hour lectures and 1 one-hour tutorial every two weeks.

Assessment

90% examination, 10% assignment (including computing assignments). As well, students are expected to participate in tutorial presentations.

Graduate attributes

• Applying mathematical knowledge (1)
• Interpreting data and drawing conclusions (2)
• Formulating mathematical problems (3)
• Problem solving skills (4)
• Flexibility in working environment (5)
• ( )
• Communication skills (6)
• Team participation and leadership (7)

Linkage past

Prerequisite is MATHS 1007A/B Mathematics 1 or equivalent. Students are assumed to be familiar with the concepts of Linear Programming.

Linkage present

This subject forms part of an Operations Research stream, which could also include subjects such as APP MTH 3014 Optimisation III, APP MTH 3001 Applied Probability III and APP MTH 3016 Telecommunications Systems Modelling III. Such a stream would be suitable for a student contemplating a career in telecommunications, business, or any other area demanding decision-making.

Linkage future

This course is not recorded as prequisite for other courses.

Restrictions

None.

Recommended text

None.