## MATH3017Mathematical 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
Co-ordinator(s): Dr Hou-Duo Qi

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

ModuleCodeYear
Introduction to Operational ResearchMATH20132

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

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

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