This module assumes knowledge of the Simplex method for linear programming. The theory is extended to consider more complex problems, in particular instances where variables must be integer (integer programming), and analysis of the optimal solution and what-if analysis (post-optimal and parametric programming).

The second part of the module considers dynamic programming, firstly for solving shortest route problems and then, for machine replacement and production problems. The work is then extended to solve stochastic problems, where variables are not known exactly but relate to a probability.

This module includes techniques for formulating problems and recognising problems which can be solved easily. Ideas such as genetic algorithms and descent methods are introduced as means of solving problems which cannot easily be solved using linear or dynamic programming.

Emphasis is given throughout this module to practical and realistic problems.

Recommended Modules: MA0261 Operational Research

• Use the Simplex solution method to solve general linear programming problems and confidently understand its matrix interpretation.
• Resolve non-optimal and infeasible tableaux.
• use the above skills to solve problems in post-optimal, parametric and integer programming.
• construct and solve search trees, including bounds.
• recognise and formulate those problems that can be solved using dynamic programming.
• formulate and solve dynamic programming problems via networks and mathematical equations and their extension to stochastic problems.
• Formulate linear programs for a variety of problems, and recognise which are easy to solve
• Discuss the use of meta-heuristics to solve difficult problems

27 – 50 minute lectures

Some handouts will be provided in hard copy or via Learning Central, but students will be expected to take notes of lectures.

Students are also expected to undertake at least 50 hours private study including preparation of solutions to given exercises.

Skills:

Problem formulation.

Simplex method. Branch and bound search trees.

Dynamic programming formulations for practical problems.

Transferable Skills:

Clear logical thinking.

Time management.

Using mathematical ideas to solve real problems.

Formative assessment is carried out by means of regular tutorial exercises.  Feedback to students on their solutions and their progress towards learning outcomes is provided during tutorial classes.  

The summative assessment is the written examination at the end of the module.  This gives students the opportunity to demonstrate their overall achievement of learning outcomes.  It also allows them to give evidence of the higher levels of knowledge and understanding required for above average marks.

The examination paper has a choice of three from four equally weighted questions.

• Matrix formulation of linear programming problems, primal and dual problems, resolving infeasible tableaux, and added constraints, post-optimal programming, parametric programming, pure integer problems, branch and bound, cutting-plane methods, mixed integer problems.

• Network formulation of dynamic programming problems, stages and states, optimality, value iteration algorithm, tabular solution, mathematical solution, stochastic problems.

• The linear programming formulation of various problems including the transportation problem. Additional restrictions to optimal tableaux. The idea of unimodularity and how to recognise problems which are easy to solve.

Model building in Mathematical programming, Williams, H. P., Wiley

Model solving in Mathematical programming, Williams, H. P., Wiley

Not applicable.