Linear Programming

For Linear Programming there are some excellent ways of using technology to help your learning. This post will look at online utilities from zweigmedia and the use of the Excel Solver.

This example from MEI (MEI Decision 1 Legacy Specimen Paper) will be used to illustrate the use of these tools.

A vet is treating a farm animal. He must provide minimum daily requirements of an antibiotic, a vitamin and a nutrient. He has two types of medicine available, tablets and liquid. The table summarises what the medicines contain and the requirements.
Vet Problem - table
The tablets cost £0.38 each and liquid medicine costs £1 per dose.
The vet wants to find the cheapest way to treat the animal.
We have x as the number of tablets which the vet prescribes per day, and y is the number of doses of liquid medicine, giving us the linear programming problem:
Minimise    0.38x + y
Subject to
3x +   2y   ≥ 18
2x +   4y   ≥ 16
10x + 50y ≥ 100

Firstly we will look at zweigmedia’s Linear Programming Grapher. This is intuitive to use. Note the option to see examples. Fraction mode is selected here.
Selecting Solve gives a clear solution illustrated graphically.

LP vet problem

Linear Programming Grapher – zweigmedia

We see that the optimal solution, if x and y can take any values, is a cost of £3.20,
with x = 20/3 and y = 2/3.

LP Vet Graphical Solution

We could also solve the problem using the Simplex Tool. As well as a solution it is possible to see the simplex tableaus. The Simplex Tool is needed for any problems with more than two variables.
Simplex Tool zweigmedia

If we wish to restrict x and y to integers, we can turn to Excel and use Solver. This allows a choice of making x and y integer or not.

Using the same example, we can set up the problem in Excel.
Vet Problem with Excel Solver is the Excel spreadsheet with annotation to explain the answer report and for full instructions on setting up the spreadsheet, use this file:
Solver Excel to solve LP problems – Colleen Young

Excel Solver

Set up the problem in Excel

and use Solver..

Excel Solver Answer Report

Excel Solver – Answer Report

We could choose to restrict x and y to integers with Solver.
Excel Solver specify integer solution
giving us the solution:
Excel Solver Answer Report Integer

For a further example, this time a maximisation problem from Edexcel have a look at this Excel file, Badges LP Edexcel. Each sheet in the workbook is fully annotated to explain the method.
Edexcel LP Problem Excel Solver
Edexcel LP Problem Excel Solver Graphical Solution

 

 

 

 

 

One comment on “Linear Programming

  1. Reblogged this on Mathematics, Learning and Technology and commented:

    For any teachers teaching Discrete Mathematics, solving Linear Programming problems with technology as well as by hand allows answers to be checked and more problems to be explored. The new UK Advanced Level specifications quite rightly emphasise the use of technology to enhance learning. Teachers who are using the OCR (MEI) Further Mathematics specification, note that specific mention is made in that specification of technology such as Excel Solver. With my own students, we will be exploring the tools described here. Using an old MEI example, full instructions are given for setting up problems using Excel Solver.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s