Module overview
This module aims to introduce the student to some of the main deterministic techniques that are used in operational research, namely linear and integer programming. The process of modelling problems of a practical nature as a linear or integer program will be developed. Following an explanation of a standard version of the simplex method, some of its variants will be introduced. The main ideas of linear programming duality will also be explained. A computer workshop session trains students in the use of commercial linear programming software. The branch and bound approach for solving integer programming problems will also be developed.
Aims and Objectives
Learning Outcomes
Learning Outcomes
Having successfully completed this module you will be able to:
- describe 5 steps for formulating a mathematical programming problem (Section 1 (Intro to MP))
- derive the range of the RHS until the optimal basis start changing and the corresponding range of the optimal value (Section 4 (Sensitivity))
- define basic solution, basic feasible solution, optimal BSF of LP problems in standard form (Section 2 (Simplex Method))
- apply branch and bound to solve simple IP (e.g. with no more than 3 variables) (Section 5 (Integer Programming))
- describe situations when sensitivity analysis is used (Section 4 (Sensitivity))
- formulate the knapsack problem using IP (Section 5 (Integer Programming))
- write the general form of a mathematical programming problem (Section 1 (Intro to MP))
- transform LP problems from general form to standard form and vice versa (Section 2 (Simplex Method))
- apply these steps to the two examples in the handout (and similar problems) (Section 1 (Intro to MP))
- apply the dictionary and full tableau Simplex method to solve LP problems in standard form given a starting BFS (Section 2 (Simplex Method))
- describe complementary slackness conditions (Section 3 (Duality))
- solve LP problems with two variables using the graphical method (Section 1 (Intro to MP))
- derive the range of the objective coefficient until the optimal basis start changing and the corresponding range of the optimal value (Section 4 (Sensitivity))
- write down general form and standard form of LP problems (Section 2 (Simplex Method))
- distinguish between LP, IP, and NLP (Section 1 (Intro to MP))
- describe the method for finding initial BFS and to avoid cycling (Section 2 (Simplex Method))
- describe economic interpretation of shadow price and perform sensitivity analysis on LP
- formulate various problems using LP, IP and NLP
- using duality and complementary slackness to verify optimality (Section 3 (Duality))
- describe duality theorems and complementary slackness
- describe the motivation for using duality and formulate the dual problem given the primal
- describe relationships for primal-dual pair in terms of optimality, feasibility and boundedness (Section 3 (Duality))
- apply parametric programming to calculate the change of the objective value (and the optimal solutions) when more than one objective coefficient or the RHS are changed continuously (Section 4 (Sensitivity))
- derive (upper) bound on IP using LP relaxation (Section 5 (Integer Programming))
- describe graphical method, simplex methods (primal and dual) and apply them to solve relatively small LP problems
- describe general branch and bound method (Section 5 (Integer Programming))
- state LP duality theorem (Section 3 (Duality))
- describe the motivation for using duality and formulate the dual problem given the primal (Section 3 (Duality))
- model either-or, set-up costs and other condition-based constraints using binary variables and constraints in the context of integer programming (Section 5 (Integer Programming))
- describe the idea behind the Simplex method (Section 2 (Simplex Method))
- describe branch and bound methods
- describe how dual simplex can be used in the case additional constraint leads to infeasibility (Section 4 (Sensitivity))
- obtain (lower) bound on IP using rounding (Section 5 (Integer Programming))
- interpret shadow price and primal-dual pair in terms of profit maximization vs. resource scarcity (Section 3 (Duality))
- describe and prove week duality theorem (Section 3 (Duality))
- describe the dual Simplex method (using dictionary) (Section 3 (Duality))
Syllabus
Linear Programming.
- Model construction and modelling issues.
- Simplex method: two-phase algorithm, dual simplex method, network simplex method.
- Duality: motivation and definitions, duality theorem, complementary slackness, optimality
- testing.
- Sensitivity analysis: ranging for objective function coefficients and right hand-side constraints,
- economic interpretation and applications.
- Parametric programming. Integer Programming.
- Modelling techniques using zero-one variables.
- Branch and bound algorithm for integer programming.
Learning and Teaching
Teaching and learning methods
Five 2-hour lectures
Two 1-hour class sessions
Two 2-hour computer sessions
Type | Hours |
---|---|
Revision | 10 |
Wider reading or practice | 7 |
Follow-up work | 16 |
Lecture | 10 |
Preparation for scheduled sessions | 16 |
Completion of assessment task | 10 |
Practical classes and workshops | 6 |
Total study time | 75 |
Resources & Reading list
Textbooks
FS Hillier & GJ Lieberman. Introduction to Mathematical Programming. McGraw Hill.
HP Williams. Model Building in Mathematical Programming. Wiley.
HP Williams. Model Solving in Mathematical Programming. Wiley.
V Chvatal. Linear Programming. Freeman.
WL Winston. Operations Research: Applications and Algorithms. Duxbury.
Assessment
Summative
This is how we’ll formally assess what you have learned in this module.
Method | Percentage contribution |
---|---|
Coursework | 30% |
Exam | 70% |
Referral
This is how we’ll assess you if you don’t meet the criteria to pass this module.
Method | Percentage contribution |
---|---|
Written assessment | 100% |
Repeat Information
Repeat type: Internal & External