Module Identifier
MA33110
Module Title
LINEAR PROGRAMMING
Academic Year
2008/2009
Co-ordinator
Mr Alan Jones
Semester
Semester 2
Pre-Requisite
MA21410
Other Staff
 

Course Delivery

Delivery Type Delivery length / details
Lecture 19 Hours. (19 x 1 hour lectures)
Seminars / Tutorials 3 Hours. (3 x 1 hour example classes)
 

Assessment

Assessment Type Assessment length / details Proportion
Semester Exam 2 Hours   (written examination)  100%
Supplementary Assessment 2 Hours   (written examination)  100%

Learning Outcomes

On completion of this module, a student should be able to:
1. describe the scope of linear programming;
2. formulate real situations as linear programming problems;
3. solve such problems by the Simplex Method;
4. apply appropriate modifications to the basic technique.
5. interpret the results of computer generated linear programming solutions.

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 and widely used application of Mathematics in the real world.

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. Interpretations of the Dual problem.
5. SPECIAL TOPICS: A selection of topics from: Zero-sum games, Integer programming, Assignment problems, Transportation problems.

Reading List

Supplementary Text
H A Taha (2003) Operations research: an introduction 7th Prentice Hall Primo search J G Ecker & M Kupferschmid (1988) Introduction to operations research Wiley Primo search W L Winston (1995) Introduction to mathematical programming: applications and algorithms 2nd OWS-Kent Primo search

Notes

This module is at CQFW Level 6