MATH311 - Linear Programming and Applications

Year

Credit points

Campus offering

Prerequisites

MATH104 Differential and Integral Calculus and MATH107 Introduction to Logic and Algebra

Teaching organisation

Unit rationale, description and aim

This unit combines the ideas developed in the calculus and algebra strands of the mathematics sequences and provides an introduction to linear programming, a major mathematical process in operational research. Models and applications are considered both graphically and algorithmically and particularly with reference to transportation and assignment problems with their special algorithms and the connection to simple matrix games. Appropriate technology will be used including the computer package Microsoft Excel.

Learning outcomes

To successfully complete this unit you will be able to demonstrate you have achieved the learning outcomes (LO) detailed in the below table.

Each outcome is informed by a number of graduate capabilities (GC) to ensure your work in this, and every unit, is part of a larger goal of graduating from ACU with the attributes of insight, empathy, imagination and impact.

Explore the graduate capabilities.

On successful completion of this unit, students should be able to:

LO1 - Model a small linear program (GA3, GA4, GA5, GA8, GA9, GA10) 

LO2 - Represent and analyse a simple linear program in two dimensions (GA4, GA5, GA8) 

LO3 - Perform iterations of the basic simplex method (GA4, GA5, GA8) 

LO4 - Use technology efficiently to solve a linear program. (GA4, GA5, GA8, GA10) 

LO5 - Understand duality and obtain a linear program dual. (GA4, GA5, GA8) 

LO6 - Model transportation and assignment problems using linear program (GA4, GA5, GA8, GA9) 

LO7 - Use special algorithms for transportation and assignment problems (GA4, GA5, GA8) 

LO8 - Solve a simple matrix game (GA4, GA5, GA8) 

LO9 - Solve some simple network problems including shortest path and maximum flow problems (GA4, GA5, GA8). 

Graduate attributes

GA3 - apply ethical perspectives in informed decision making

GA4 - think critically and reflectively 

GA5 - demonstrate values, knowledge, skills and attitudes appropriate to the discipline and/or profession 

GA8 - locate, organise, analyse, synthesise and evaluate information 

GA9 - demonstrate effective communication in oral and written English language and visual media 

GA10 - utilise information and communication and other relevant technologies effectively.

Content

Topics may include: 

1. Review of linear graphs in two dimensions. Feasible sets. 
2. Introduction to graphical linear programs. 
3. The simplex method 
4. Find solutions to Linear Programming problems by computer using Microsoft Excel. 
5. Sensitivity analysis 
6. Duality 
7. The Dual simplex method and Integer programs. Branch and bound. 
8. Transport problems 
9. Assignment problems 
10. Simple two person zero sum games. 
11. Optimisation of some network problems. 

Learning and teaching strategy and rationale

This unit includes 4 contact hours per week over 12 weeks, comprising 2 hours of lectures and 2 of tutorials. 

Assessment strategy and rationale

A range of assessment procedures will be used to meet the unit learning outcomes and develop graduate attributes consistent with University assessment requirements. Such procedures may include assignments, reports, multiple choice tests and supply answer examinations, student presentations or case studies. 

Overview of assessments

Representative texts and references

Dantzig, G. (1998). Linear programming and extensions. Princeton: Princeton University Press 

Ragsdale, C. (2011). Spreadsheet modelling and decision analysis. (6th ed.). Mason, Ohio: South-Western Cengage Learning. 

Winston, W., & Golberg, J. (2003). Operations research: Applications and algorithms. Melbourne: Cengage Learning Business Press