IMAT1703
DATA ANALYTICS
AND STATISTICS
LECTURE 14
LINEAR PROGRAMMING
OVERVIEW
The concept of linear programming.
How to express linear programming
problems.
The objective function and constraints.
To formulate and solve maximising
problems.
For simple (2 variable) maximisation
problems be able to describe the LP
problem graphically. 2
Linear Programming
Linear programming has nothing to
do with computer programming.
The use of the word “programming”
here means “choosing a course of
action.”
Linear programming involves
choosing a course of action when the
mathematical model of the problem
contains only linear functions. 3
DEFINITION OF LINEAR PROGRAMMING (LP)
Linear programming is a problem solving
technique that has been developed to help
managers decide on the allocation of limited
resources.
Decisions will usually be based on some sort
of optimisation (such as maximising profit or
minimising risk) subject to a number of
constraints (such as machine hours, machine
spare hours, manpower hours etc.)
4
TYPICAL LP APPLICATIONS
A manufacturer wants to develop a production
schedule that will maximise their potential profit but
satisfies forecast sales demand and keeps within the
resources available to them.
A financial analyst must select a suitable portfolio of
investments for a client that maximises the
anticipated return, but keeps within their budget and
an allowable level of risk.
A marketing manager needs to decide how to allocate a
marketing budget to various media such as TV, radio,
newspapers, etc. to maximise audience exposure. 5
LIMITATIONS OF LINEAR PROGRAMMING
For Linear Programming the following limitations apply:
1. The variables must be continuous, i.e.) not discrete.
2. Only one objective can be solved at any one time,
i.e.) it is not possible to optimise on two or more
things at once! For example, we cannot maximise
profit and minimise cost at the same time – they
are 2 different things!
3. The relationships of the variables for the objectives
and constraints must be linear.
6
GUIDELINES FOR MODEL FORMULATION
Understand the problem thoroughly.
Describe the objective.
Describe each constraint.
Define the decision variables.
Write the objective in terms of the
decision variables.
Write the constraints in terms of the
decision variables.
7
Example 1
o A toy company makes a soft teddy bears that earn them a
unit profit of £10 each.
o Each bear requires 5 hours of production time
o There are a total of 40 hours of production time available
each week.
o How many bears can the company make each week if
they want to maximise total weekly profit?
o What is the total profit?
• 5 hours per bear required
• 40 hours available in total
• So, 8 bears can be made
8
• Profit = 8 x £10 = £80
Example 1 Continued
We can formulate a mathematical model for this decision
making problem as follows:
Let x = number of bears made
Since the profit per bear is £10, the total profit is, which we
want to maximise.
Each bear requires 5 hours to make, so x bears requires 5x
hours to make.
But we only have 40 hours available and so we are
constrained by the fact that whatever value x takes, the hours
used, 5x, must be ≤ 40.
We can write this model mathematically as:
10x 9
5x ≤ 40.
Example 1 Continued
The solution of the problem represented by this
model is still quite simple.
The reason for representing the problem in this way
is that more complicated problems can be
represented using mathematical models in this way.
Doing this allows us to solve them using computer
software, The Management Scientist.
This problem that has three components:
Decision variable: x
Objective function: 10x
Constraints: 5x ≤ 40
All Linear Programming problems have these three 10
components.
Example 2
• Suppose the same toy company also makes soft rabbits
that earn them a unit profit of £5 each and that each rabbit
requires 2 hours of production time.
• Assume there are 40 hours of production time to be
shared between the production of bears and rabbits.
• How many bears and how many rabbits should they make
to maximise profit?
• This is still a simple problem, but the solution may not be
immediately obvious to all straight away.
• We can develop a mathematical model as follows:
Decision variable: x and y
Objective function: 10x + 5y
11
Constraints: 5x + 2y ≤ 40
Example 1 Continued
Having formulated the problem like this, we can solve
it using software such as Excel and The Management
Scientist.
The Management Scientist Output
Max 10x + 5y
Subject to 5x + 2y ≤ 40 x=0 and
y = 20
OPTIMAL SOLUTION
Objective Function Value = 100.000
Variable Value Reduced Costs 10x0 + 5x20
--------- ------- ------------- = 100 Profit
x 0.000 2.500
12
y 20.000 0.000
Example 3
o Consider a company that uses a single commodity A to
produce products X and Y.
o Each unit of product X requires 200g of commodity A and
produces a profit of £5 per unit.
o Each unit of product Y requires 100g of commodity A and
produces a profit of £4 per unit.
o If 1 kg (1000g) of commodity A is available, how many
units of products X and Y should be produced?
o The company would like to maximise profit.
o Although product X has a higher unit profit, £5 compared
to £4 for Y, it uses twice the resources.
o We could therefore produce 2 units of Y, at a profit of £8,
for every 1 unit of X, at a profit of £5.
o Company should therefore produces 10 units of Y (uses
all commodity A) and none of product X. 13
o Total profit is 10x £4 = £40.
EXAMPLE 4 A SIMPLE MAXIMISATION PROBLEM:
PAR INC.
Par Inc. is a small manufacturer of golf equipment and
supplies whose management has decided to move into the
market for Standard and Deluxe golf bags.
After thorough investigation of the steps involved in
manufacturing a golf bag, management has determined that
each golf bag produced will require the following operations:
Cutting and dyeing the material
Sewing
Finishing (inserting umbrella holder, club separators, etc.)
Inspection and packaging.
14
EXAMPLE 4 PAR INC. CONTINUED
What quantity of each type of bag should be made, using
available resources, to maximise the profit?
Profits are £10 per Standard bag and £9 per Deluxe bag.
Resource requirements (hours per bag) and available
resources are shown on next slide.
Note In practice, LP solves problems of many variables
(sometimes thousands) and equations, however if we use 2
variables we can demonstrate all of the main features of LP in
order to introduce the terminology.
15
EXAMPLE 1 PAR INC: RESOURCE REQUIREMENTS
(HOURS PER BAG) AND TOTAL HOURS AVAILABLE IN EACH OF 4
DEPARTMENTS INVOLVED IN MANUFACTURING PROCESS ARE:
Cutting Inspection
Product & &
Dyeing Sewing Finishing Packaging
Standard
Bag 7/10 1/2 1 1/10
Deluxe
Bag 1 5/6 2/3 1/4
Hours
Available 630 600 708 135
16
THE OBJECTIVE FUNCTION AND DECISION VARIABLES
To formulate any LP problem we need to state:
The objective function (which is the maximisation or
minimisation objective of the problem).
For the Par Inc. problem, the objective is to maximise
the total profit contribution. We can write this objective in
mathematical form using simple notation.
The decision variables. In the LP problem, let
S represent the number of Standard bags made and
D represent the number of Deluxe bags made,
17
THE OBJECTIVE FUNCTION AND DECISION VARIABLES
Profits £10 per Standard and £9 per Deluxe
bag
Ifmake S Standard and D Deluxe bags total
profit is:
10S + 9D
Want to maximise total profit
So Objective Function is:
Max 10S + 9D 18
CUTTING AND DYEING CONSTRAINT
Amount of cutting and dyeing time
required to produce S Standard bags
and D Deluxe bags is:
7
S + 1D
10
• But we only have 630 hrs of cutting and
dyeing time available, giving us the
constraint
7
S + D ≤ 630
10
19
SEWING TIME CONSTRAINT
Sewingtime required to produce S
Standard bags and D Deluxe bags is:
1 5
S+ D
2 6
• There are 600 hrs of sewing time
available, giving us the constraint:
1 5
S + D ≤ 600
2 6 20
FINISHING TIME CONSTRAINT AND INSPECTION
AND PACKAGING CONSTRAINT
Finishing time constraint is:
2
S + D ≤ 708
3
o Inspection and packaging constraint is:
1 1
S + D ≤ 135
10 4
21
PROBLEM FORMULATED AS AN LP PROBLEM:
22
PROBLEM FORMULATED AS AN LP PROBLEM TO BE
SOLVED IN THE MANAGEMENT SCIENTIST:
Max 10X1 + 9X2 Max 10S + 9D
such that: such that:
0.7X1 + X2 < 630 0.7S + D < 630
0.5X1 + 0.8333X2 < 600 0.5S + 0.8333D < 600
X1 + 0.6667X2 < 708 S + 0.6667D < 708
0.1X1 + 0.25X2 < 135 0.1S + 0.25D < 135
Note The Management Scientist uses variables X1, X2 and
doesn’t support fractions so the LP problem is entered into
the software as indicated above and the non-negativity of
23
X1 and X2 is assumed.
OPTIMAL SOLUTION USING THE
MANAGEMENT SCIENTIST Profit
Objective Function Value = 7667.9417
Variable Value Reduced Costs
-------------- --------------- --------------------
Number of
S 539.9842 0.0000
Standard
D 252.0110 0.0000 bags and
Deluxe bags
Constraint Slack/Surplus Dual Prices
---------------- ------------------- -----------------
1 0.0000 4.3746
2 120.0071 0.0000
3 0.0000 6.9378 24
4 17.9988 0.0000
SOLUTION CONTINUED
OBJECTIVE COEFFICIENT RANGES
Variable Lower Limit Current Value Upper Limit
S 6.3000 10.0000 13.4993
D 6.6670 9.0000 14.2857
RIGHT HAND SIDE RANGES
Constraint Lower Limit Current Value Upper Limit
1 495.6000 630.0000 682.3589
2 479.9929 600.0000 No Upper Limit
3 580.0140 708.0000 900.0000
4 117.0012 135.0000 No Upper Limit
25
SUMMARY OF SOLUTION
The correct interpretation of the solution to the
golf bag problem is therefore:
make 540 Standard golf bags
make 252 Deluxe golf bags
total profit = £7668
Solution on output on previous slide is slightly
different since we used decimals to just 4 d.p. in
problem formulation entered in the software.
The rest of the output will be considered in a later
lecture.
26
GRAPHICAL SOLUTION OF EXAMPLE 1: THE
PAR INC. PROBLEM
27
S = 0, D = 630
1200
D = 0, S = 6300/7 = 900
(S=0, D=630) (0, 630) (900, 0)
No. of Deluxe Bags
1000
800
600
(S=900, D=0)
400
200
0
0 200 400 600 800 1000 1200 1400
No. of Standard Bags
28
1200
7
S + D = 630
No. of Deluxe Bags
1000 10
800
All points in shaded
600
area satisfy constraint
400 7
S + D ≤ 630
200 10
0
0 200 400 600 800 1000 1200 1400
No. of Standard Bags
29
1200 S = 0, D = 3600/5 = 720
1 5
S + D = 600 D = 0, S = 1200
No. of Deluxe Bags
1000 2 6 (0, 720) (1200, 0)
800
600 All points in shaded
area satisfy constraint
400 1 5
S + D ≤ 600
200 2 6
0
0 200 400 600 800 1000 1200 1400
No. of Standard Bags
30
2
1200 S + D = 708 S = 0, D = 2124/2 = 1062
3 D = 0, S = 708
(0, 1062) (708, 0)
No. of Deluxe Bags
1000
800
600
All points in shaded
400 area satisfy constraint
2
200 S + D ≤ 708
3
0
0 200 400 600 800 1000 1200 1400
No. of Standard Bags
31
1200 S = 0, D = 540
1 1 D = 0, S = 1350
S + D = 135
No. of Deluxe Bags
1000 (0, 540) (1350, 0)
10 4
800
All points in shaded
600
area satisfy constraint
400 1 1
S + D ≤ 135
200 10 4
0
0 200 400 600 800 1000 1200 1400
No. of Standard Bags
32
GRAPHICAL VIEW OF ALL 4 CONSTRAINTS
All points in shaded area satisfy
all constraints
1200 All points in the shaded area are
therefore feasible solutions to the
No. of Deluxe Bags
1000
LP problem. The shaded area is
800
called the feasible region to the
600 problem.
400
200
0
0 200 400 600 800 1000 1200 1400
No. of Standard Bags
33
HOW DO WE FIND THE OPTIMAL SOLUTION
ON THE GRAPH?
We require the optimal point to:
maximise 10S + 9D, but
also satisfy ALL of the constraints.
Therefore on the graph, we need to plot the line with
equation:
10S + 9D = constant
Note This equation represents a series of parallel lines
depending on what value the constant takes. These lines
are called iso-profit lines.
34
EXAMPLE
Consider a profit of $1800
$1,800 chosen because 10 and 9 divide into it
Could consider instead say $3,600 or$7,200 etc.
So we need to plot the line 10S + 9D = 1800
This line cuts axes at following points:
If S = 0 then 10*0 + 9D = 1800
Hence D = 1800/9 = 200
If D = 0 then 10S + 9*0 = 1800
Hence S = 1800/10 = 180
3
5
ISO-PROFIT LINE FOR £1800
As an example consider a profit of £1800
1200 So plotting the line 10S + 9D = 1800
this line cuts the axes at the following
No. of Deluxe Bags
1000
points:
800
600
(S=0, D=200)
400
200 (S=180, D=0)
0
0 200 400 600 800 1000 1200 1400
No. of Standard Bags
36
BUT THERE ARE MANY OTHER PARALLEL
ISO-PROFIT LINES
S = 0, D = 400
D = 0, S = 360
1200 (0, 400) (360, 0)
S = 0, D = 800
Profit of £1800
No. of Deluxe Bags
1000 D = 0, S = 720
(0, 800) (720, 0)
800
Profit of £3600
600 Profit of £7200
400
200
0
0 200 400 600 800 1000 1200 1400
No. of Standard Bags
37
SO WHICH PROFIT LINE?
We are interested in the iso-profit line which MAXIMISES the
profit!
How is this achieved graphically?
By moving the iso-profit lines (parallel) in a direction which
increases profit (when maximising move the line ‘out’ away
from the origin.)
We do this until we get to the outermost edge of the feasible
region and the profit line is just about to move outside of the
feasible region. (We stop as beyond this no points satisfy all
the constraints!)
The optimal solution to a LP problem is found at an 38
extreme point of the feasible region for the problem.
FINDING THE OPTIMAL POINT ON THE GRAPH
1200
Optimal Point where Cut &
No. of Deluxe Bags
1000
Dye and Finishing constraint
800 lines intersect
600
400
200
0
0 200 400 600 800 1000 1200 1400
No. of Standard Bags
39
DETERMINING CO-ORDINATES OF OPTIMAL POINT
Max profit is at point where the cutting and
dyeing constraint and the finishing constraints
meet
i.e. where
7/10S + D = 630 ----- (1) and
S + 2/3D = 708 ------(2) intersect.
7/10S + 14/30D = 495.6 (multiply (2) by 7/10)
0.5333 D = 134.4
D = 134.4/0.5333 = 252
7/10 S + 252 = 630 (substitute in (1))
7/10 S = 378
S = 3780/7 = 540
Solving simultaneously gives:
S = 540, D = 252 40
DETERMINING CO-ORDINATES OF OPTIMAL POINT
Max profit is at point where the cutting and dyeing
constraint and the finishing constraints meet
i.e. where
7/10S + D = 630
and S + 2/3D = 708 intersect.
Solving simultaneously gives:
S = 540, D = 252
Profit = 10S+9D = 10*540 + 9*252
= £7668
These two constraints are binding constraints.
(Cutting and Dyeing and Finishing)
Other two constraints are non-binding constraints.
(Sewing and Inspection and Packaging) 41
SUMMARY OF SOLUTION
The correct interpretation of the
solution to the golf bag problem
as we saw last week is therefore:
make 540 standard bags
and 252 deluxe bags
at a profit of £7668
42
SUMMARY OF GRAPHICAL METHOD
Plotthe constraints on the same graph
Identify the feasible region
Draw an iso-profit line that gives a specific
value for the profit (objective function)
If
maximising move the iso-profit line ‘out’
away from origin and parallel
Do this until profit line is just about to move
outside feasible region 43
