Mathematical Sciences

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

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

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.