P1_Linear programming.pdf

(291 KB) Pobierz
Chapter
9
Linear Programming
1
9.1
Introduction
A
limiting factor or principle budget factor
means you do not have enough of a resource of
some kind, in order to produce or sell all you would like, it is a scarce resource, which is in
short supply that would cause this. The analysis would maximise contribution for an
organisation, by allocating the scarce resource to producing goods, which earn the highest
amount of contribution per unit of scarce resource available. Two techniques exist for dealing
with maximising contribution given a limiting factor.
Contribution per limiting factor
– this is a technique looking to maximise the
benefit or contribution from one scarce resource. This resource has been identified as
the only resource preventing production being increased and therefore extra
contribution being earned.
Linear programming
– this is a technique used when you have identified more than
one scarce resource that you need to maximise the benefit or contribution from. It
involves plotting the resources as straight line equations on a graph and working out
the point which will maximise contribution given the combination of products that
can be sold.
9.2
Shadow (or dual) pricing
A shadow price is only relevant if you have a scarce resource, it is the extra contribution you
would earn by obtaining one more unit of the scarce resource, but this would not be the same
as the maximum price you would pay.
A shadow price is only relevant to a scarce resource and is the increase in contribution
created by having available, one more additional unit of a limiting factor at the original
cost. It is the maximum premium that an organisation should be willing to pay for one
extra unit of that constraint.
9.3
Linear programming
Linear programming is a technique using linear equations to solve complex limiting factor
which contain several constraints on production and trying to obtain an optimal solution. It
can be applied in several different situations:
Mix of materials in products
– trying to obtain the most contribution from the mix
of materials in products sold.
Capacity allocation –
maximising the capacity of storage facilities.
Distribution problems
– shipping or transportation costs minimised between
warehouses.
2
Production forecasting
– uncertain sales levels is met by having optimised
production levels.
Investment mix
– how much to invest and in which projects in a company.
Logistical problems
– location of plant or warehouse.
Approach to answering linear programming questions
Define the key variables
- this is the assigning of letters to the products and services
that are needed to be made and then using these letters to represent the amount that
should be made at the optimum point.
Construct the objective function
– this is looking at identifying the main objective
that is trying to be achieved. For example maximise contribution or minimising costs
given the combination of products and services being sold.
Set up the constraints
– these show the limits of recourses available to us to try and
meet the conditions of the objective function and they are usually described as linear
equations.
Logic or non-negativity constraints
– these are constraints which will ensure that
the answer obtained in the solution is sensible in that only zero or positive values are
in the answer.
All constraints are plotted on to a graph and then moving away from the origin a
solution is sought where all constraint conditions are met and maximises the objective
function. The solution can also be derived through simultaneous equations which is
far more accurate than using the graph or graphical method.
3
Example 9.5
‘We only do fish and chips’ face the following problems in one of their shops in Grimsby.
1. Due to EC regulations only 500 fish are available in one week
2. Cooking time is limited to 48 hours per week
3. Due to the seasonal nature of vegetable oil only 1 drum is in stock (containing 100
litres)
4. The fish and chip manager has told the staff, they must cook 2 fish every time they
cook 3 portions of chips
Details about cooking time and oil needed are as follows:
Fish (1 portion)
Chips (1 portion)
0.08 Hrs
0.04 Hrs
100 ml
50 ml
Each fish contributes £1.50 and each portion of chips £0.50
Give the number of fish and chips served in order to maximise contribution in a
single week?
1. Define variables F = Number of Fish produced
C = Number of chips produced
2. Objective function (maximise contribution) 1.5 F + 0.5 C = Contribution
3. Set up the constraints
4. Logic
Limitations with linear programming
A straight line relationship is always assumed but may not be a true representation of
the data.
If there are more than 2 variables then it will not be possible to calculate manually as
there would be more than axis to draw on a graph. We would need the use of a
computer.
Variables are completely divisible and so therefore we can produce half a unit which
may not be realistic.
These methods can be used not only to maximise contribution but also to minimise cost, the
principle is exactly the same.
4
Example 9.6
Using an output report lets relate this to ‘We only do fish and chips’ but now let’s assume
that the manager wishes to relax the constraint that 2 fish have to be produced for every 3
chips.
The report would like similar to this
Variables
F
C
500
200
Constraints
S1 (Veg oil)
40
S2 (Cooking time)
12.50
S3 (EU Regulations) 0.50
Contribution
£850
The maximum contribution is £850.
This is achieved by producing 500 fish and 200 chips.
There is no slack or surplus (spare capacity for either cooking time or EU regulations
indicating that 500 fish are used to maximum and the full cooking time of 48 hours is
being used.
Only 60 litres of vegetable oil is being used therefore a surplus of 40 litres.
Because of cooking time and fish supplies being constrained, a shadow price for one
additional hour of cooking time is £12.50 and one additional fish would be £0.50.
9.4
Simplex method
When there are more than two variables it is not possible to solve the problem using the
graphical method because it becomes very difficult to plot three dimensional graphs, instead
we need to use the simplex method. Using this method can also allow us to use a computer to
help us solve and also it lends itself to showing a shadow prices easily. The simplex method
creates an
“initial tableau”
which presents all information as a starting point. It then tests
one feasible solution point after another revising the tableau each time until it arrives at the
final solution. This is known as the
“final tableau”.
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin