## MATH3017 Mathematical Programming

### Module Overview

This module is compulsory for the following programmes:

Mathematics with Management Sciences

Mathematics with Operational Research

### Module Details

**Title: **Mathematical Programming**Code: **MATH3017**Year: **3**Semester: **2

**CATS points: **15** ECTS points: **7.5**Level: **Undergraduate**Co-ordinator(s): **Dr Hou-Duo Qi

### Pre-requisites and / or co-requisites

Module | Code | Year |
---|---|---|

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.

### Syllabus

- 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)

### Assessment

### Assessment methods

- 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.