Distance MSc in Operational Research - Optimisation

Credit Value: 6
Tutors: Tim Bedford

Class description/introduction

The class introduces students to the modelling approaches and solution methods used in optimisation. Unstructured problem descriptions are formulated using mathematical notation. These problems are classified and appropriate solution methods are selected where they exist. The solution methods are covered in detail for certain classes of problem.

Class aims

To give an understanding of the methods and techniques used in optimisation.

Learning outcomes

Subject specific knowledge and skills

• Be able to transform a verbal description of an optimisation problem into a mathematical model.
• Be able to classify problems as LP, MIP, QP, CP, NLP programmes, and thus identify an appropriate technique for analysis
• Be able to analyse simple problems using a graphical approach
• Solve linear programmes using the simplex algorithm, be able to interpret the solutions derived from the approaches and on the basis of these be able to make practical recommendations
• Understand how to extend the linear programming technique to a wider class of problems using integers
• Understand the use of stochastic optimisation techniques such as simulated annealing and genetic algorithms
• Be able to use appropriate computer software for the solution of optimization problems
• Demonstrate understanding of the package's internal logic by being able to specify the nature of the modifications required to it in different circumstances;
• Conduct sensitivity analysis of solutions, and report on this in a matter understandable and useful to a client.

Cognitive abilities and non-subject specific skills

• Improved problem structuring skills
• Ability to communicate using mathematical equations

Content/Structure of class

The class starts with a survey of the types of business problems that can be structured into optimisation problems. By looking at the generic structure of optimisation problems we shall see how a verbal description of an optimisation problem can be transformed into a mathematical model. As different types of problem require different solution methods, the classification of the problem type is considered.

The most simple type of optimisation problem, which also permits exact solution in a finite number of steps, is that of linear programming. For low dimensional problems these are solved using a graphical method. The simplex algorithm is used to solve higher dimensional problems. When there are integer restrictions on some or all of the variables the simplex algorithm as such is no longer appropriate on its own, and is extended by the branch and bound method to give an exact solution.

For non linear problems we are mostly unable to find exact solutions. Deterministic local search algorithms are mentioned, and the modern stochastic-based heuristics such as genetic algorithms are discussed.

We use state-of-the-art software to build and solve various kinds of optimisation problems.

Reading List

The following may be of use but are not required:

• M Wisniewski and T Dacre (1990), Mathematical Programming: Optimization Models for Business and Management Decision Making
• H.P.Williams (1985);"Model Building in Mathematical Programming", Wiley.

Assessment

Exam.

Matrix of learning outcomes/assessment

• Learning Outcomes
• Be able to transform a verbal description of an optimisation problem into a mathematical model.
• Be able to classify problems as LP, MIP, QP, CP, NLP programmes, and thus identify an appropriate technique for analysis
• Be able to analyse simple problems using a graphical approach
• Solve linear programmes using the simplex algorithm, be able to interpret the solutions derived from the approaches and on the basis of these be able to make practical recommendations
• Understand how to extend the linear programming technique to a wider class of problems using integers
• Understand the use of stochastic optimisation techniques such as simulated annealing and genetic algorithms
• Be able to use appropriate computer software for the solution of optimization problems
• Demonstrate understanding of the package's internal logic by being able to specify the nature of the modifications required to it in different circumstances;
• Conduct sensitivity analysis of solutions, and report on this in a matter understandable and useful to a client;

management science DEPARTMENT OF MANAGEMENT SCIENCE
UNIVERSITY OF STRATHCLYDE Graham Hills BUILDING 40 GEORGE STREET G1 1QE
t:0141 548 3613/3141 f:0141 552 6686
contact-mansci@strath.ac.uk