Course finder

Semester 2

Linear Programming, Modelling and Solution (MATH10073)

Subject

Mathematics

College

SCE

Credits

10

Normal Year Taken

3

Delivery Session Year

2023/2024

Pre-requisites

Previous study of linear algebra: matrix (non-)singularity, linear systems of equations, matrix-matrix multiplication. Visiting students are advised to check that they have studied the material covered in the syllabus of each prerequisite course before enrolling.

Course Summary

Linear programming (LP) is the fundamental modelling technique in optimal decision-making. This course will introduce the concepts of LP modelling, explore the mathematical properties of general LP problems and study the theory of the simplex algorithm as a solution technique. Students will use the Xpress mathematical programming system to create, solve and analyse case studies and then present their work in oral and written form. As a consequence, in addition to the assessment of theoretical understanding and hand calculation via a written examination, the course is also assessed via a short individual Xpress assignment and a substantial group-based case study.

Course Description

Linear programming (LP) offers the natural entry to the study of operational research, not only because LP is the fundamental modelling technique in optimal decision-making, but also because the mathematical nature of LP problems [everything is linear!] means that they can be analysed with tools from linear algebra introduced at level 8. This course introduces the concepts of LP modelling, explores the mathematical properties of general LP problems and studies the theory of the simplex algorithm as a solution technique. The novel feature of this course is that it introduces the Xpress mathematical programming system to create, solve and analyse case studies. The course ends with a group-based case study in which, much like an OR consultant might do, you will model, solve and analyse a meaningful example, presenting your work in oral and written form.Syllabus1. Linear programming: Decision variables, objective function, bounds and constraints. The feasible region; geometric and algebraic characterisation of an optimal solution. The dual of an LP problem and duality theory. Theory underlying sensitivity and fair prices.2. Modelling: Introduction to the Xpress mathematical programming system as a means of modelling, solving and analysing LP case studies. Exploration of the modelling language Mosel to define index sets, data arrays, decision variables, constraints, solve LP problems, analyse problem sensitivity and report the results in a suitable format for further processing using Excel.3. Solution: Study of the simplex algorithm for LP problems. Geometric and algebraic concepts underlying the algorithm and consequences for solution methods. Proof of termination for non-degenerate LPs. Linear algebra underlying its implementation via the revised simplex method.

Assessment Information

Written Exam 50%, Coursework 50%, Practical Exam 0%

Additional Assessment Information

Coursework 50%, Examination 50%

view the timetable and further details for this course