Linear programming – the basic ideas

Introduction

Please note: a Statement of Participation is not issued on this course.

This free OpenLearn course, Linear programming – the basic ideas, is an extract from the Open University course M373 Optimization [Tip: hold Ctrl and click a link to open it in a new tab. (Hide tip)] , a third level applied mathematics course that will interest you if you need to create mathematical models or if you use numerical software in industry, science, commerce or research. It’s concerned with the skills needed to represent real optimization problems as mathematical models, and with techniques used in numerical analysis and operational research for solving these models by computer. Explaining how and when modelling and numerical techniques can be applied, the course covers solutions of non-linear equations; systems of linear and non-linear equations and mathematical modelling; linear and integer programming; and non-linear optimization for unconstrained and constrained minimisation problems.

Linear programming – the basic ideas consists of material from M373 Unit II.1, Linear programming – the basic ideas, and has four sections in total. You should set aside about three to four hours to study each of the sections; the whole extract should take about 16 hours to study. The extract is a small part (around 7%) of a large course that is studied over eight months, and so can give only an approximate indication of the level and content of the full course.

An optimization problem, when modelled mathematically, usually results in a real function whose optimum value, i.e. whose maximum or minimum value is sought. This extract focuses on constrained optimization problems where the function to be optimized and the constraints can all be expressed as linear combinations of the variables. In particular, the extract concentrates on the formulation and solution of small linear programming problems. It is relatively self-contained and should be reasonably easy to understand for someone with a sound knowledge of relevant mathematics,such as could be gained from Open University level 2 study of linear algebra, calculus and matrices.

Mathematical/statistical content at the Open University is usually provided to students in printed books, with PDFs of the same online. This format ensures that mathematical notation is presented accurately and clearly. The PDF of this extract thus shows the content exactly as it would be seen by an Open University student. However, the extract isn't entirely representative of the module materials, because there are no explicit references to use of the M373 software or to video material (although please note that the PDF may contain references to other parts of M373). In this extract, some illustrations have also been removed due to copyright restrictions.

Regrettably, mathematical and statistical content in PDF form is not accessible using a screenreader, and you may need additional help to read these documents.

Section 1 deals with the formulation of linear programming models, describing how mathematical models of suitable real-world problems can be constructed.

Section 2 looks at graphical representations of two-dimensional models, considers some theoretical implications and examines the graphical solution of such models.

Section 3 introduces the simplex method for solving linear programming models.

Section 4 uses matrix notation to formalize the simplex method.