## MAS322 Operations Research

Semester 2, 2021/22 | 10 Credits | ||||

Lecturer: | Dr Yi Li | Timetable | 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.

**Prerequisites:** MAS211 (Advanced Calculus and Linear Algebra)

**Not with:** MAS423 (Advanced 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

## 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 designing solution algorithms
- be familiar with the techniques of post-optimality analysis
- be familiar with running AMPL with common solvers such as MINOS and cplex.

## Teaching methods

Lectures, problem solving, and computer lab

20 lectures, 1 tutorials

## Assessment

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

## 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; KKT conditions.
- 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 | 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.