MAS423 Advanced Operations Research

Semester 2, 2017/18 10 Credits
Lecturer: Dr Yi Li uses MOLE Reading List
Aims Outcomes Teaching Methods Assessment Full Syllabus

Mathematical Programming is the title given to a collection of optimisation algorithms that deal with constrained optimisation problems. Here the problems considered will all involve constraints which are linear, and for which the objective function to be maximised or minimised is also linear. Some of these problems are not continuously differentiable; special algorithms have to be developed. The module considers first how these problems arise from practical applications, then introduces the solution of such problems, and finally explain the important area of post-optimality analysis where we answer questions about the effects of changes in the parameters of the problem on the optimal solution. Additional topics include integer programming problems and network models.

Prerequisites: MAS211 (Advanced Calculus and Linear Algebra)
Not with: MAS322 (Operations Research)
No other modules have this module as a prerequisite.


Outline syllabus

  • Building linear programming, integer programming and piecewise linear programming models
  • Graphical techniques
  • The Simplex Method and variants
  • Matrix representation of the simplex algorithm
  • Elementary post-optimality analysis
  • Duality and applications in post-optimality analysis



Aims

  • To develop the mathematical skills that will provide you with the appropriate foundations for further mathematical studies.
  • To enable you to analyse OR problems that may arise in your future employment.

Learning outcomes

  • be able to build linear programming models, logical integer programming models, and piece-wise linear programming models
  • be able to use the Simplex Method and its variants, to solve Linear Programming Problems
  • have an understanding of duality and its relevance in sensitivity analysis
  • be familiar with the techniques of sensitivity analysis
  • be familiar with running AMPL with common solvers such as MINOS and cplex.

Teaching methods

Lectures, tutorials, problem solving


20 lectures, 1 tutorials

Assessment

One formal 2 hour written examination with 4 compulsory questions [65%]. Mini-project [35%].

Full syllabus

  • Modelling with linear programming, integer programming and piece-wise linear programming problems.
  • Graphical solutions for two-dimensional problems.
  • The Simplex Method: the basic simplex algorithm, artificial variables and the two-phase method, and the dual simplex algorithm.
  • Elementary post-optimality analysis: changing model parameters; adding and removing variables and constraints; changing cost coefficients and resources.
  • Duality: the definition and properties of the dual problem of a general optimization problem; derivation of the dual problems of linear programming problems; properties of the primal-dual pair; applications in post-optimality analysis
  • Guided self-study: elementary usage of the AMPL software and writing simple codes with AMPL.

Reading list

Type Author(s) Title Library Blackwells Amazon
B Paul R. Thie and Gerard E. Keough An Introduction to Linear Programming and Game Theory 518.7 (T) Blackwells Amazon
B Taha Operations Research: An Introduction 519.38 (T) Blackwells Amazon
C Bertsimas and Tsitsiklis Introduction to Linear Optimization. 519.72 (B) Blackwells Amazon
C Winston Introduction to Mathematical Programming 519.7 (W) Blackwells Amazon

(A = essential, B = recommended, C = background.)

Most books on reading lists should also be available from the Blackwells shop at Jessop West.