Undergraduate Course: Linear Programming, Modelling and Solution (MATH10073)
Course Outline
School  School of Mathematics 
College  College of Science and Engineering 
Credit level (Normal year taken)  SCQF Level 10 (Year 3 Undergraduate) 
Availability  Available to all students 
SCQF Credits  10 
ECTS Credits  5 
Summary  Linear programming (LP) is the fundamental modelling technique in optimal decisionmaking. This course will introduce the concepts of LP modelling, explore the mathematical properties of general LP problems and study the theory of the simplex algorithm as a solution technique. Students will use the Xpress mathematical programming system to create, solve and analyse case studies and then present their work in oral and written form. As a consequence, in addition to the assessment of theoretical understanding and hand calculation via a written examination, the course is also assessed via a short individual Xpress assignment and a substantial groupbased case study. 
Course description 
Linear programming (LP) offers the natural entry to the study of operational research, not only because LP is the fundamental modelling technique in optimal decisionmaking, but also because the mathematical nature of LP problems [everything is linear!] means that they can be analysed with tools from linear algebra introduced at level 8. This course introduces the concepts of LP modelling, explores the mathematical properties of general LP problems and studies the theory of the simplex algorithm as a solution technique. The novel feature of this course is that it introduces the Xpress mathematical programming system to create, solve and analyse case studies. The course ends with a groupbased case study in which, much like an OR consultant might do, you will model, solve and analyse a meaningful example, presenting your work in oral and written form.
Syllabus
1. Linear programming: Decision variables, objective function, bounds and constraints. The feasible region; geometric and algebraic characterisation of an optimal solution. The dual of an LP problem and duality theory. Theory underlying sensitivity and fair prices.
2. Modelling: Introduction to the Xpress mathematical programming system as a means of modelling, solving and analysing LP case studies. Exploration of the modelling language Mosel to define index sets, data arrays, decision variables, constraints, solve LP problems, analyse problem sensitivity and report the results in a suitable format for further processing using Excel.
3. Solution: Study of the simplex algorithm for LP problems. Geometric and algebraic concepts underlying the algorithm and consequences for solution methods. Proof of termination for nondegenerate LPs. Linear algebra underlying its implementation via the revised simplex method.

Information for Visiting Students
Prerequisites  Previous study of linear algebra: matrix (non)singularity, linear systems of equations, matrixmatrix multiplication. Visiting students are advised to check that they have studied the material covered in the syllabus of each prerequisite course before enrolling. 
High Demand Course? 
Yes 
Course Delivery Information

Academic year 2020/21, Available to all students (SV1)

Quota: 110 
Course Start 
Semester 2 
Timetable 
Timetable 
Learning and Teaching activities (Further Info) 
Total Hours:
100
(
Lecture Hours 15,
Seminar/Tutorial Hours 5,
Supervised Practical/Workshop/Studio Hours 10,
Summative Assessment Hours 2,
Programme Level Learning and Teaching Hours 2,
Directed Learning and Independent Learning Hours
66 )

Assessment (Further Info) 
Written Exam
50 %,
Coursework
50 %,
Practical Exam
0 %

Additional Information (Assessment) 
Coursework 50%, Examination 50% 
Feedback 
Not entered 
Exam Information 
Exam Diet 
Paper Name 
Hours & Minutes 

Main Exam Diet S2 (April/May)  MATH10073 Linear Programming, Modelling and Solution  1:30  
Learning Outcomes
On completion of this course, the student will be able to:
 Model, solve and analyse a simple case study using Xpress and present an investigation of that case study in oral and written form.
 Use the simplex algorithm by hand to solve a small linear programming problem
 Use the optimality conditions for a linear programming problem to deduce properties of its optimal solution
 Form the dual of a (primal) linear programming problem and exploit the relations between the two problems
 Formulate and analyse linear programming models for solving specific classes of problem.

Reading List
Introduction to Operations Research, F. S. Hillier and G. Lieberman, McGrawHill Higher Education, 9th edition. ISBN10: 0071267670 
Additional Information
Graduate Attributes and Skills 
Experience of modelling realistic case studies. Further development of programming skills (using Mosel), groupwork, verbal and oral presentation skills. 
Additional Class Delivery Information 
16 onehour lectures
5 onehour workshops
4 twohour labs 
Keywords  LPMS,linear programming,modelling language,case study 
Contacts
Course organiser  Dr Julian Hall
Tel: (0131 6)50 5075
Email: J.A.J.Hall@ed.ac.uk 
Course secretary  Mr Christopher Palmer
Tel: (0131 6)50 5060
Email: chris.palmer@ed.ac.uk 

