MATH3017 Mathematical Programming
This module is compulsory for the following programmes:
Mathematics with Management Sciences
Mathematics with Operational Research
Title: Mathematical Programming
CATS points: 15 ECTS points: 7.5
Co-ordinator(s): Dr Hou-Duo Qi
Pre-requisites and / or co-requisites
|Introduction to Operational Research||MATH2013||2|
Aims and objectives
- build a mathematical programming model of a real-life situation;
- apply a suitable variant of the simplex method to solve a linear programming problem;
- use a computer package to solve the type of linear programming problems that arise in practice;
- write a report that describes the formulation of a linear programming problem, and presents and interprets the solution;
- apply a branch and bound algorithm to solve integer programming problems.
- Building linear programming models. Hard and soft constraints. Multi-objective problems: goal programming. Multi-period model. Multi-plant problem. Trim loss problem.
- The simplex method and its underlying principles. Review of the simplex method. Basic feasible solutions: why the simplex method generates an optimal solution. Degeneracy and anti-cycling pivoting rules: perturbation and Bland's smallest subscript rule. Performance of simplex method in practice.
- Duality. Motivation: generating upper bounds and economic considerations. Duality theorems: strong and weak duality, complementary slackness. Testing optimality.
- Sensitivity analysis. Ranging analysis: objective function coefficients and right hand sides. Economic considerations.
- Variants of the simplex method. Dual simplex method. Revised simplex method.
- Minimum cost network flow problem. Formulation of the minimum cost network flow problem and its dual. Network simplex method. Decomposition theorem and degeneracy. Applications: production planning problem.
- Integer programming. Building integer programming models: examples with zero-one variables. General purpose branch and bound algorithm. Balas' additive algorithm for zero-one problems. Special purpose branch and bound algorithms: knapsack problem
Learning and teaching
Study time allocation
Contact hours: 4
Private study hours: 4
Total study time: 8 hours
Teaching and learning methods
Lectures, computer workshops, problem sheets, private study.
Resources and reading list
CHVATAL V Linear Programming. (Freeman)
WILLIAMS H P Model Building in Mathematical Programming. (3rd Edition, Wiley)
WILLIAMS H P Model Solving in Mathematical Programming. (Wiley)
HILLIER F S & LIEBERMAN G J Introduction to Mathematical Programming. (McGraw Hill)
- Written Examination 80%;
- PURPOSE OF THE ASSESSMENT: To demonstrate understanding of the simplex method and its variants for solving linear programming problems, and how branch and bound can be used to solve integer programming problems.
- FEEDBACK: Examination feedback will be sent to students via Blackboard after the marking has been completed (normally two weeks after the exam)
- Coursework 20%;
- PURPOSE OF THE ASSESSMENT: To demonstrate mathematical programming modelling skills, the ability to use computer software to solve a mathematical programming problem, and write a report of the type that would be suitable for an Operational Research Manager on analysis of a problem.
- FEEDBACK: Coursework feedback will be sent to students via Blackboard after the marking has been completed (normally two weeks after the coursework has been submitted
- Referral Assessment: Written Examination.