MATH3017 Mathematical Programming
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
• 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.
Having successfully completed this module you will be able to:
- Build a mathematical programming model of a real-life situation
- 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
- Use a computer package to solve the type of linear programming problems that arise in practice
- Apply a suitable variant of the simplex method to solve a linear programming problem
- Understand the basic theory in linear programming
• 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.
|Total study time||150|
Resources & Reading list
HILLIER F S & LIEBERMAN G J, (2010). Introduction to Operations Research.
R. Vandrbei (2014). Linear Programming: Foundation and Extension.
|Exam (2 hours)||80%|
Repeat type: Internal & External
To study this module, you will need to have studied the following module(s):
|MATH2013||Introduction to Operational Research|
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.