Apuntes
Linear Programming
Contenido del apunte (1)
Página 1
Linear Programming
In this topic we look at maximising profits or minimising costs subject to constraints.
Formulating the Problem
-Decision Variables: the qualities to be decided
-Objective Function: profit/cost to be maximised/minimised
-Constraints: the limits to the problem
E.g. (1) Mrs cook is making cakes to sell for charity; fruit cake and chocolate cake. A fruit cake requires 1 egg, 250g of flour, 200g of sugar and can be sold for £3.50 . A chocolate cake requires 2 eggs, 250g of flour, 300g of sugar and can be sold for £5.00 . Mrs Cook has 36 eggs, 7kg of flour, 6kg of sugar and wishes to maximise the money she makes.
Formulate this as a linear programming problem.
Summary table:
l Eggs l Flour l Sugar l Profit l
l Fruit cake l 1 l 250 l 200 l £3.50 l
l Choc cake l 2 l 250 l 300 l £5 l
l Constraints l 36 l 7000 l 6000 l
Decision Variables: Let f be the number of fruit cakes
Let c be the number of chocolate cakes
Objective function: Maximise P=3.5f+5c
Constraints: Subject to: f+2c < 36 (eggs)
250f+250c < 7000 -> f+c < 28 (flour)
200f+300c < 6000 -> 2f+3c < 60 (sugar)
f>0 c>0 (non-negativity)
Plotting constraints and the feasible region
By plotting the restraints and shading the region than doesn't fulfil the restraints you are left with a feasible region. Within this region the values fulfil the restraints.
The ruler method.
Draw on your objective function.
To maximise the function, slide the ruler form the constraint toward the feasible region, The last point in the FR is the maximum value.
To minimise, slide the ruler from the constraint toward the FR, the first point the ruler touches the minimum value.
The vertex method.
You can instead test each vertex by solving the simultaneous equations,
Then put your values in your objective function and find out which is the maximum/minimum value.
Integer valued solutions
Sometimes there is an additional constraints in the problem that the solution has integer values. For e.g. we wouldn't be baking a fraction of a chocolate cake
Simply mark on all integer values and complete the ruler method as usual towards the first/last marked point.
Or test the marked on integers to find the largest/smallest objective function.
Información
- Descripción
- AS - Level Maths Apunte sobre Linear Programming, creado por Alice Butterworth el 13/01/2016.
- Creado por
- Alice Butterworth · ene 2016
- Actualizado
- 10 jun 2016
- Visitas
- 9
- Valoración