The University of Southampton
Courses

MATH3017 Mathematical Programming

Module Overview

The topics to be covered include: • Solving LP Models: The simplex algorithm and its extensions. The use of computers. • Duality: The relationship between an LP model and dual including theorems on duality, complementarity, and the alternative; Shadow prices; Sensitivity analysis. • Flows in Networks: The network form of the simplex algorithm. Minimum Cost. • Integer Programming: Branch and bound algorithms. The knapsack problem.

Aims and Objectives

Module Aims

• develop the ideas underlying the simplex method for linear programming; • describe and motivate the main variants of the simplex method; • introduce more practical aspect of linear programming; • develop the basic concepts in integer programming. • This module covers linear and integer programming. Such problems arise in areas such as manufacturing, distribution, finance, agriculture, health, energy and resources planning. • The introductory material on linear programming (LP) presented in MATH2013 will be reviewed and developed. The course work involves formulating an LP model and solving it using a computer package.

Learning Outcomes

Learning Outcomes

Having successfully completed this module you will be able to:

  • Apply a branch and bound algorithm to solve integer programming problems
  • Write a report that describes the formulation of a linear programming problem, and presents and interprets the solution
  • Build a mathematical programming model of a real-life situation
  • Use a computer package to solve the type of linear programming problems that arise in practice
  • Understand the basic theory in linear programming
  • Apply a suitable variant of the simplex method to solve a linear programming problem

Syllabus

• Building linear programming models including integer programming models. • 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. Theorem of Alternative. Testing optimality. • Sensitivity analysis. Ranging analysis: objective function coefficients and right hand sides. Economic considerations. • Variants of the simplex method. Dual 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

Teaching and learning methods

Lectures, computer workshops, problem sheets, private study.

TypeHours
Independent Study98
Teaching52
Total study time150

Resources & Reading list

R. Vandrbei (2014). Linear Programming: Foundation and Extension. 

HILLIER F S & LIEBERMAN G J, (2010). Introduction to Operations Research. 

Assessment

Summative

MethodPercentage contribution
Coursework 20%
Exam  (2 hours) 80%

Referral

MethodPercentage contribution
Exam 100%

Repeat Information

Repeat type: Internal & External

Linked modules

Pre-requisite: MATH2013 Introduction To Operational Research 2016-17

Costs

Costs associated with this module

Students are responsible for meeting the cost of essential textbooks, and of producing such essays, assignments, laboratory reports and dissertations as are required to fulfil the academic requirements for each programme of study.

In addition to this, students registered for this module typically also have to pay for:

Books and Stationery equipment

Course texts are provided by the library and there are no additional compulsory costs associated with the module.

Please also ensure you read the section on additional costs in the University’s Fees, Charges and Expenses Regulations in the University Calendar available at www.calendar.soton.ac.uk.

Share this module Facebook Google+ Twitter Weibo

We use cookies to ensure that we give you the best experience on our website. If you continue without changing your settings, we will assume that you are happy to receive cookies on the University of Southampton website.

×