Quantitative Methods for Decision Making:

SYSTEM OPTIMISATION:

LINEAR PROGRAMMING: GRAPHICAL

METHOD 2

Adrian Bown

Room: CC NT 101 / Tel. Ext. 27629

Quantitative Methods for Decision Making:

OVERVIEW OF WEEK 1

Adrian Bown

Room: CC NT 101 / Tel. Ext. 27629

Example 1 _ Maximising Profit:
• Consider a generalised production-based system in which a set of
resources are to be allocated to a number of commodities
• It is assumed that there is a high demand for both commodities and
the objective is to allocate resources such that profit is maximised
• The details of resources, commodities and profit are:

Resource 1, R 1 Resource 2, R 2 Profit

Commodity 1, C 1 3 2 2

Commodity 2, C 2 2 4 3

Maximum
7 10
Resources
 R1 R2 P

x 3 2 2

y 2 4 3

Maximum Resources 7 10

• Summary:

– Resource Equation 1: 3 x  2 y  7

– Resource Equation 2: 2 x  4 y  10

– The profit equation: P  2 x  3 y

– As there is only positive production, x  0 and y  0

 Y

6
3x  2y  7
5

3
3x  2y  7
2

0 X
3 x  2 y  70 1 2 3 4 5 6
 Y

3
Feasible domain for
2
maximisation problems

0 X
0 1 2 3 4 5 6
 Y

0 X
0 1 2 3 4 5 6
 Y

0 X
0 1 2 3 4 5 6
 Y

0 X
0 1 2 3 4 5 6
 Y

0 X
0 1 2 3 4 5 6
Example 2 _ Minimising Cost:
• A manufacturer has the choice of two products; x and y
• For the same volume, the two products provide different quantities
of the same three chemicals – see Table below
• Based on the prices given in the table, determine how much of each
product should be used to minimise manufacturing costs

Chemical A Chemical B Chemical C Cost

Product x 4 kg / m 3 8 kg / m 3 6 kg / m 3 £ 8 / m3

Product y 8 kg / m 3 6 kg / m 3 7 kg / m 3 £ 4 / m3

Minimum amount
of chemicals reqd. 32 kg / m 3 48 kg / m 3 42 kg / m 3
 Y

5
Feasible domain for
4 minimisation problems

0 X
0 1 2 3 4 5 6
 Y
First value in feasible
8
domain ( x = 0, y = 8 )

0 X
0 1 2 3 4 5 6 7 8
Quantitative Methods for Decision Making:

SYSTEM OPTIMISATION:

LINEAR PROGRAMMING: GRAPHICAL

METHOD 2

Adrian Bown

Room: CC NT 101 / Tel. Ext. 27629

Example 1;
A company produces two items; X and Y. The resources need to produce
both items are machine time for automatic processing and craftsperson
time for hand finishing. Item X requires 13 minutes of machine time and
20 minutes of craftsperson time and item Y similarly takes 19 minutes
and 29 minutes, respectively.
 
The company has 40 hours of machine time available in the next
working week but only 35 hours of craftsperson time. Machine time is
priced at £10 per hour worked and craftsperson time is priced at £8 per
hour worked; both machine and craftsperson idle times incur no costs.
The revenue received for each item produced (all production is sold) is
£30 for X and £40 for Y. The company has a specific contract to produce
10 items of X and 20 items of Y each per week for a particular customer.
 
Solve this linear program using the graphical method.
 Resource 1, R 1 Resource 2, R 2 Profit

Commodity 1, C 1

Commodity 2, C 2

Maximum
Resources
In this problem there will be two resource constraints (machine time and
craftsperson time) and two production constraints.
Resource constraints:

A company produces two items; X and Y. The resources need to produce

both items are machine time for automatic processing and craftsperson
time for hand finishing. Item X requires 13 minutes of machine time
and 20 minutes of craftsperson time and item Y similarly takes 19
minutes and 29 minutes, respectively.
 
The company has 40 hours of machine time available in the next
working week but only 35 hours of craftsperson time.

Using last week’s terminology, the commodities are the two items X and Y
 Resource 1, R 1 Resource 2, R 2 Profit, P

Maximum Resources
In this problem there will be two resource constraints (machine time and
craftsperson time) and two production constraints.
Resource constraints:

A company produces two items; X and Y. The resources need to produce

both items are machine time for automatic processing and craftsperson
time for hand finishing. Item X requires 13 minutes of machine time
and 20 minutes of craftsperson time and item Y similarly takes 19
minutes and 29 minutes, respectively.
 
The company has 40 hours of machine time available in the next
working week but only 35 hours of craftsperson time.

Using last week’s terminology, the resources are machine and craftsperson
times
 Machine Time, Craftperson’s
R1 Time, R 2 P

x 13 20

y 19 29

Maximum 40 * 60 = 2400 35 * 60 = 2100

Resources

Machine time (mins) 13X + 19Y ≤ (40 * 60)  13X + 19Y ≤ 2400

[ Limits; X = 0, Y = 126.3 and X = 184.6, Y = 0 ]

Craftsperson time (mins) 20X + 29Y ≤ (35 * 60)  20X + 29Y ≤ 2100

[ Limits; X = 0, Y = 72.4 and X = 105, Y = 0 ]

In this problem there will be two resource constraints (machine time and
craftsperson time) and two production constraints.
Resource constraints:

Machine time (mins) 13X + 19Y ≤ (40 * 60)  13X + 19Y ≤ 2400
[ Limits; X = 0, Y = 126.3 and X = 184.6, Y = 0 ]
Craftsperson time (mins) 20X + 29Y ≤ (35 * 60)  20X + 29Y ≤ 2100
[ Limits; X = 0, Y = 72.4 and X = 105, Y = 0 ]
 
Production constraints:

The company has a specific contract to produce 10 items of X and 20

items of Y each per week for a particular customer.
 R1 R2 P

x 3 2 2

y 2 4 3

Maximum Resources 7 10

• Summary:

– Resource Equation 1: 3 x  2 y  7

– Resource Equation 2: 2 x  4 y  10

– The profit equation: P  2 x  3 y

– As there is only positive production, x  0 and y  0

 Y

0 X
0 1 2 3 4 5 6
In this problem there will be two resource constraints (machine time and
craftsperson time) and two production constraints.
Resource constraints:

Machine time (mins) 13X + 19Y ≤ (40 * 60)  13X + 19Y ≤ 2400
[ Limits; X = 0, Y = 126.3 and X = 184.6, Y = 0 ]
Craftsperson time (mins) 20X + 29Y ≤ (35 * 60)  20X + 29Y ≤ 2100
[ Limits; X = 0, Y = 72.4 and X = 105, Y = 0 ]
 
Production constraints:

The company has a specific contract to produce 10 items of X and 20

items of Y each per week for a particular customer.

X ≥ 10 and Y ≥ 20
X = 10

13X + 19Y = 2400

20X + 29Y = 2100

Feasible region
Y = 20
Finally, a profit equation is required.

Machine time is priced at £10 per hour worked and craftsperson time is
priced at £8 per hour worked; both machine and craftsperson idle times
incur no costs. The revenue received for each item produced (all
production is sold) is £30 for X and £40 for Y.

Profit: P = 30X + 40Y – 10 machine time (hrs) – 8 craftsperson time (hrs)

From the previous slide; Machine time (mins) = 13X + 19Y

and, Craftsperson time (mins) = 20X + 29Y

P = 30X + 40Y – 10[(13X + 19Y)/60] - 8[(20X + 29Y)/60]

P = 30X + 40Y – 2.17X – 3.17Y – 2.67X – 3.87Y
P = 25.16X + 32.96Y
 
X = 10

13X + 19Y = 2400

20X + 29Y = 2100

Feasible region
Y = 20
 X = 10
13X + 19Y = 2400
20X + 29Y = 2100

Feasible region
Y = 20

Craftsperson time (mins) 20 X + 29 Y = 2100

When X = 10; 29Y = 2100 - 20X = 2100 – 20( 10 )  Y = 1900/29 = 65.52

When Y = 20; 20X = 2100 - 29Y = 2100 – 29( 20 )  X = 1520/20 = 76

P = 25.16X + 32.96Y

X = 10, Y = 65.52  P = 2411.14 and X = 76, Y = 20 P = 2571.36

Production Constraints: The constraints on product (i.e. x and/or y > 0) can
also be applied to minimisation problems

7
Feasible domain
6

0 X
0 1 2 3 4 5 6 7 8
Production Constraints: For instance, if y > 0 but ‘ 2 < x < 7 ’:

7
Feasible domain
6

0 X
0 1 2 3 4 5 6 7 8
Example 2;
A company manufactures two products, A and B, and the profit per unit
sold is £3 and £5, respectively. Each product has to be assembled on a
particular machine with each unit of A taking 12 minutes of assembly
time and each unit of B takes 25 minutes of assembly time. The company
estimates that the machine has an effective working week of 30 hours.
Customer demand dictates that for every five units of product A produced
at least two units of product B must be produced.
 i. If the objective of this exercise is to maximise profit, solve this linear
program using the graphical method.
ii. The company has been offered the chance to hire an extra machine,
thereby doubling the effective assembly time available. In order for it
be worthwhile to them, the company requires a minimum 25 % profit
on top of the cost of hiring the machine. What is the maximum
amount that the company should pay (per week) for the hire of this
machine?
Example 2;
A company manufactures two products, A and B, and the profit per unit
sold is £3 and £5, respectively. Each product has to be assembled on a
particular machine with each unit of A taking 12 minutes of assembly
time and each unit of B takes 25 minutes of assembly time. The company
estimates that the machine has an effective working week of 30 hours.
Customer demand dictates that for every five units of product A produced
at least two units of product B must be produced.
 i. If the objective of this exercise is to maximise profit, solve this linear
program using the graphical method.
ii. The company has been offered the chance to hire an extra machine,
thereby doubling the effective assembly time available. In order for it
be worthwhile to them, the company requires a minimum 25 % profit
on top of the cost of hiring the machine. What is the maximum
amount that the company should pay (per week) for the hire of this
machine?
Part i.

Objective: maximise profit, where P = 3A + 5B

Constraints:

• Technological:

Technological constraints mean that for every five units of product A

produced at least two units of product B must be produced
 Technological constraints mean that for
every five units of product A produced at
least two units of product B must be
produced – i.e. for 10 A’s there must be,
B at least, 4 B’s

A
Part i.

Objective: maximise profit, where P = 3A + 5B

Constraints:

• Technological:

Technological constraints mean that for every five units of product A

produced at least two units of product B must be produced

5B ≥ 2A ( i.e., if A = 10, B ≥ 4 → (5 [ min. 4 ] ≥ 2 [ 10 ])

 5B – 2A ≥ 0 or B – 0.4A ≥ 0
 Feasible domain

A
Part i.

Objective: maximise profit, where P = 3A + 5B

Constraints:

• Technological:

Technological constraints mean that for every five units of product A

produced at least two units of product B must be produced

5B ≥ 2A ( i.e., if A = 10, B ≥ 4 → (5 [ min. 4 ] ≥ 2 [ 10 ])

 5B – 2A ≥ 0 or B – 0.4A ≥ 0

•  Resource: Assembly time 12A + 25B ≤ 30(60)  12A + 25B ≤ 1800

[ Limits; A = 0, B = 72 and A = 150, B = 0 ]

• Production:X ≥ 0 and Y ≥ 0
B
12A + 25B = 1800
B – 0.4A = 0

Feasible region

Solution: A = 81.8, B = 32.7, revenue = £ 408.90

Part ii.
• Doubling the assembly time available means that the resource
constraint becomes 12A + 25B ≤ 2(1800), i.e. 12A + 25B ≤ 3600.
• This new constraint will be parallel to the existing assembly time
constraint.
• The original technological and production constraint statements remain
valid
Solution: A = 163.6, B = 65.4, revenue = £ 817.80
• The additional profit is £ 817.80 - £408.90 (revenue from Part i.) =
£ 408.90
• In order to make a 25 % profit (on top of the cost), the maximum
amount that should be paid for the machine is £ 408.90 = £ 327.12
1.25
Example 3 – Applying the process to non-linear situations;

R1 R2 Profit

x 3 ‘ x £2

y 2 y £3

Maximum Resources 7 9

• R 1: 3x  2y  7

• R 2: x2  y2  9
• As there is only positive production, x  0 and y  0
• Profit equation: P  2 x  3 y
– From last week, the limits of Resource Equation 1 ( 3 x  2 y  7 )

are: x = 0, y = 3.5 and, if y = 0, x = 2.33

Y

3
3x  2y  7
2

0 X
0 1 2 3 4 5 6
The limits of Resource Equation 2 ( x 2
 y 2
 9 ) are:

When x  0   0   y  9  y  9  y  3
2 2 2

Plotting the curve:

Method 1: If you have a pair of compasses, you can draw a circle

with a radius of 3

x  1   1   y  9  y  8  y  2.83
2 2 2
Method 2:

x  2   2   y  9  y  5  y  2.24
2 2 2

2 2 2
 Y

3
x2  y2  9

0 X
0 1 2 3 4 5 6
 Y

0 X
0 1 2 3 4 5 6
 Corners of shaded region
x y
0 3

2.33 0

• Resource Equation 1:

7  3x
3x  2y  7  y   3.5  1.5 x Eqn. 3
2

• Resource Equation 2: x 2
 y 2
 9
• Resource Equation 1: 3 x  2 y  7  y  3.5  1.5 x Eqn. 3

• Resource Equation 2: x 2
 y 2
 9

• Sub. Eqn. 3 into R. Eqn. 2:

 
2
x  y  9
2 2
 x 
2
3.5  1.5 x  9

 x2    3.5  1.5 x    3.5  1.5 x    9

 x2   12.25  10.5 x  2.25 x 2   9

 3.25x 2  10.5 x  12.25  9

 3.25x 2  10.5 x  3.25  0

• Resource Equation 1: 3 x  2 y  7  y  3.5  1.5 x Eqn. 3

• Resource Equation 2: x 2
 y 2
 9

• Sub. Eqn. 3 into R. Eqn. 2:

3.25x 2  10.5 x  3.25  0

b b2  4ac
x 
2a

a  3.25 b   10.5 c  3.25

   10.5     10.5   4  3.25  3.25 

2

x 
 2  3.25 
x  0.347 or 2.884
 Y

0 X
0 1 2 3 4 5 6
• Resource Equation 1: 3 x  2 y  7  y  3.5  1.5 x Eqn. 3

• Resource Equation 2: x 2
 y 2
 9

• Sub. Eqn. 3 into R. Eqn. 2:

3.25x 2  10.5 x  3.25  0

b b2  4ac
x 
2a

a  3.25 b   10.5 c  3.25

   10.5     10.5   4  3.25  3.25 

2

x 
 2  3.25 
x  0.347 or 2.884
 Corners of shaded region
x y
0 3
0.347 2.980
2.33 0

• Resource Equation 1: 3 x  2 y  7

• Resource Equation 2: x  y  9
2 2

• Now know x = 0.347 therefore back-substitute to find ‘ y ‘:

3  0.347   2 y  7  y  2.980

 0.347 
2
• Check:  y2  9  y  2.980
 Corners of shaded region
Profit ( £ )
x y

0 3 9

0.347 2.980 9.63

2.33 0 4.66

• Resource Equation 1: 3 x  2 y  7

• Resource Equation 2: x 2
 y 2
 9

• Profit Equation: P  2 x  3 y
COMPLETE THE
TUTORIAL
QUESTIONS