MA30087/50087: Optimisation methods of operational research

MA30087/50087: Optimisation methods of operational research

	Lecturer:	Simon Shaw; 4W 4.10, s.shaw at bath.ac.uk
Timetable:	Lectures:	Monday 11:15 (3WN 2.1) and Monday 15:15 (CB 1.11).
	Problems classes:	Thursday 12:15 (3WN 2.1).

The full unit timetable is available here. A schedule for the course is available here.

Credits:	6
MA30087 Level:	Honours
MA50087 Level:	Masters UG & PG
Period:	Semester 1
MA30087 Assessment:	EX 100%
MA50087 Assessment:	CW 25%, EX 75% The coursework is likely to take the form of directed reading enabling you to submit answers to set questions on that reading. It will most likely be set in Week 10 (30 Nov 15) with a submission date in Week 15 (04 Jan 16).
Other work:	There will be weekly question sheets. These will be set and handed in during problems classes. Any work submitted by the hand-in deadline will be marked and returned to you. Full solutions to all exercises will be made available.
MA30087 Requisites:	Before taking this unit you must take MA10207 and take MA10210.
MA50087 Requisites:
Description:	Aims & Learning Objectives: Aims: To present methods of optimisation commonly used in OR, to explain their theoretical basis and give an appreciation of the variety of areas in which they are applicable. (MA50087 only: To facilitate an in-depth understanding of the topic.) Objectives: On completing the course, students should be able to Recognise practical problems where optimisation methods can be used effectively Implement appropriate algorithms, and understand their procedures Understand the underlying theory of linear programming problems, especially duality. (MA50087 only: Demonstrate an in-depth understanding of the topic.) Content: The Nature of OR: Brief introduction. Linear Programming: Basic solutions and the fundamental theorem. The simplex algorithm, two phase method for an initial solution. Interpretation of the optimal tableau. Applications of LP. Duality. Topics selected from: Sensitivity analysis and the dual simplex algorithm. Brief discussion of Karmarkar's method. The transportation problem and its applications, solution by Dantzig's method. Network flow problems, the Ford-Fulkerson theorem. Non-linear Programming: Revision of classical Lagrangian methods. Kuhn-Tucker conditions, necessity and sufficiency. Illustration by application to quadratic programming.

Some useful books

We won't follow a book as such but useful references include:

Bernard Kolman and Robert E. Beck, Elementary linear programming with applications, Second Edition, 1995. 519.72 KOL
David G. Luenberger and Yinyu Ye, Linear and Nonlinear Programming, Third Edition, 2008.
This edition is not in the library but the full text is available as an e-book here. The Second Edition is available in the library.
Jiří Matoušek and Bernd Gärtner, Understanding and Using Linear Programming, 2007.
This edition is not in the library but the full text is available as an e-book here.
Robert J.Vanderbei, Linear Programming: Foundations and Extensions, Third Edition, 2008.
This edition is not in the library but the full text is available as an e-book here.
Mokhtar S. Bazaraa, John J. Jarvis and Hanif D. Sherali, Linear programming and network flows, Third Edition, 2005. 514.025 BAZ
Frederick S. Hillier and Gerald J. Lieberman, Introduction to operations research, Eighth Edition, 2005. 512.747.9 HIL

2015/16 Course summary and material

Material covered:

Lecture 1 (28 Sep 15):	§1 Introduction: what is operational research? Motivating example of linear programming. Handout: pdf.
	Handwritten notes: pdf. Online notes: p4-7 (end of Chapter).
Lecture 2 (28 Sep 15):	§2 The Linear Programming Problem: standard framework, standard maximisation and minimisation problem.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p8 (start of Chapter)-10 (end of Definition 2).
Lecture 3 (05 Oct 15):	Canonical framework, slack variables, expressing the standard problem in canonical form.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p10 (end of Definition 2)-12 (end of page).
Lecture 4 (05 Oct 15):	Graphical method, geometry of linear programming, convex sets, hyperplane is convex.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p12 (end of page)-15 (prior to Definition7).
Lecture 5 (12 Oct 15):	Half-spaces, the feasible set of solutions to a linear programming problem form a closed convex polyhedron.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p15 (prior to Definition7)-17 (end of Chapter).
Lecture 6 (12 Oct 15):	§3 The Fundamental Theorem of Linear Programming: basic variables and basic feasible solutions.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p17 (end of Chapter)-19 (end of the page).
Lecture 7 (19 Oct 15):	Equivalence of basic feasible solutions and extreme points.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p19 (end of the page)-21 (line after equation (3.8)).
Lecture 8 (19 Oct 15):	Fundamental theorem of LP: if there is an optimal feasible solution then there is optimal basic feasible solution.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p21 (line after equation (3.8))-23 (equation (3.16)).
Lecture 9 (26 Oct 15):	§4 The Simplex Method: preliminary theory, reduced costs.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p23 (equation (3.16))-25 (prior to Example 15).
Lecture 10 (26 Oct 15):	Example of the simplex algorithm. Handout: pdf.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p25 (prior to Example 15)-27 (prior to T2).
Lecture 11 (02 Nov 15):	Determining how to change the basis, r_jθ_j method.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p27 (prior to T2)-30 (after equation (4.11)).
Lecture 12 (02 Nov 15):	Example identifying when there is no finite optimal solution, finding an initial BFS.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p30 (after equation (4.11))-32 (prior to Section 4.3).
Lecture 13 (09 Nov 15):	The two-phase method, artificial variables, auxiliary LP problem.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p32 (prior to Section 4.3)-33 (after second bullet point).
Lecture 14 (09 Nov 15):	Example of the two-phase method. Handout: pdf.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p33 (after second bullet point)-36 (end of Phase I).
Lecture 15 (16 Nov 15):	Summary of the primal simplex algorithm. §5 Duality: motivating example.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p36 (end of Phase I)-38 (end of equation (5.1)).
Lecture 16 (16 Nov 15):	Symmetric and asymmetric dual, dual of the dual is the primal, weak duality.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p38 (end of equation (5.1))-41 (statement of Theorem 5).
Lecture 17 (23 Nov 15):	Duality theorem, symmetric complementary slackness theorem.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p41 (statement of Theorem 5)-43 (statement of Theorem 7).
Lecture 18 (23 Nov 15):	Using complementary slackness to find optimal solutions, asymmetric complementary slackness.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p43 (statement of Theorem 7)-45 (statement of Theorem 8).
Lecture 19 (30 Nov 15):	§6 Transportation problem: introduction, matrix-vector representation of the balanced transportation problem and its dual.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p45 (statement of Theorem 8)-47 (after equation (6.2)).
Lecture 20 (30 Nov 15):	Key properties: existence of finite optimal solution, m+n-1 independent constraints, using asymmetric complementary slackness to solve the transportation problem.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p47 (after equation (6.2))-50 (asymmetric CS statement)).
Lecture 21 (03 Dec 15):	Example of transportation algorithm, north-west corner method. Handout: pdf.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p50 (asymmetric CS statement)-52 (after equation (6.6)).
Lecture 22 (07 Dec 15):	Matrix method, a note on degeneracy.
	Lecture overview: pdf. Handwritten notes: pdf. Online notes: p52 (after equation (6.6))-56 (end of course).
Revision (10 Dec 15):	Handwritten notes: pdf.

Forthcoming material:
This course is now completed.

Lecture notes: pdf.

Homework:
I have removed the Solution Sheets but if you took the unit in 2015-2016 and need any of the sheets then please email me.

Problems 0 (01 Oct 15):	Question Sheet Zero: pdf.
	Handout: pdf. Handwritten notes: pdf.
Problems 1 (08 Oct 15):	Question Sheet One: pdf.
	Handwritten notes: pdf.
Problems 2 (15 Oct 15):	Question Sheet Two: pdf.
	Handwritten notes: pdf.
Problems 3 (22 Oct 15):	Question Sheet Three: pdf.
	Handwritten notes: pdf.
Problems 4 (29 Oct 15):	Question Sheet Four: pdf.
	Handwritten notes: pdf.
Problems 5 (05 Nov 15):	Question Sheet Five: pdf.
	Handwritten notes: pdf.
Problems 6 (12 Nov 15):	Question Sheet Six: pdf.
	Handout: pdf. Handwritten notes: pdf.
Problems 7 (19 Nov 15):	Question Sheet Seven: pdf.
	Handwritten notes: pdf.
Problems 8 (26 Nov 15):	Question Sheet Eight: pdf.
	Handwritten notes: pdf.
Problems 9 (07 Dec 15):	Question Sheet Nine: pdf.
	Handwritten notes: pdf.

Exam papers:

	2014/15	2013/14	2012/13	2011/12	2010/11
Paper:	pdf	pdf	pdf	pdf	pdf
Solutions:	pdf	pdf	pdf	pdf	pdf

Last revision:
10/12/15