Module Identifier | MA33110 | ||
Module Title | LINEAR PROGRAMMING | ||
Academic Year | 2000/2001 | ||
Co-ordinator | Mr D A Jones | ||
Semester | Semester 2 | ||
Other staff | Dr J M Pearson | ||
Mutually Exclusive | MA23110 Not available to students who have taken MA23110 | ||
Course delivery | Lecture | 19 x 1hour lectures | |
Seminars / Tutorials | 3 x 1hour example classes | ||
Assessment | Exam | 2 Hours (written examination) | 100% |
Resit assessment | 2 Hours (written examination) | 100% |
General description
The basic problem of Linear Programming is to maximise or minimise a linear function of several variables, subject to constraints expressed as linear inequalities or equations. The theory of Linear Programming is now well established to the extent that the technique often appears as an option in widely available business computer packages such as spreadsheets. This module provides a balance between the theory and applications of the subject and considers the interpretation of problem solutions.
Aims
To introduce an important application of Mathematics in the real world that is widely used.
Learning outcomes
On completion of this module, a student should be able to:
Syllabus
1. INTRODUCTION TO LINEAR PROGRAMMING: Problem formulation and the breadth of application. Basic definitions, including convexity, extreme points, feasible solutions, basic solutions, basic and non-basic variables, basic feasible solutions.
2. THE SIMPLEX METHOD: Overall idea; geometrical and algebraic characterisation. Fundamental Theorem of Linear Programming. Artificial variables; big-M method, two-phase method, Dual Simplex method. Unsigned variables. What can go wrong.
3. SENSITIVITY ANALYSIS: Interpreting the simplex tableau, including economic interpretations where relevant. Dual prices. Marginal change and return.
4. DUALITY: The dual problem and its motivation. Fundamental Theorem of Duality. Relationships between solutions to the primal and dual problems. Complementary slackness. Dual-simplex algorithm. Interpretations of the Dual problem.
5. RELATED PROBLEMS: Some standard problems, eg transportation, assignment prolems. Theory of games.
6. COMPUTER SOLUTIONS: Obtaining and interpreting output from standard spreadsheet and other computer software.
Reading Lists
Books
** Supplementary Text
H A Taha.
Operations Research, an Introduction. Maxwell-Macmillan
W L Winston.
Mathematical Programming, Applications and Algorithms. OWS-Kent
J G Ecker & M Kupferschmid.
Introduction to Operations Research. Wiley