Assuming that machine minutes is the constraint, which product should be produced first and why?

OR-Notes

J E Beasley

OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research [OR]. They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

A full list of the topics available in OR-Notes can be found here.

Linear programming solution examples

Linear programming example 1997 UG exam

A company makes two products [X and Y] using two machines [A and B]. Each unit of X that is produced requires 50 minutes processing time on machine A and 30 minutes processing time on machine B. Each unit of Y that is produced requires 24 minutes processing time on machine A and 33 minutes processing time on machine B.

At the start of the current week there are 30 units of X and 90 units of Y in stock. Available processing time on machine A is forecast to be 40 hours and on machine B is forecast to be 35 hours.

The demand for X in the current week is forecast to be 75 units and for Y is forecast to be 95 units. Company policy is to maximise the combined sum of the units of X and the units of Y in stock at the end of the week.

• Formulate the problem of deciding how much of each product to make in the current week as a linear program.
• Solve this linear program graphically.

Solution

Let

• x be the number of units of X produced in the current week
• y be the number of units of Y produced in the current week

then the constraints are:

50x + 24y = 45 so production of X >= demand [75] - initial stock [30], which ensures we meet demand

y >= 95 - 90

i.e. y >= 5 so production of Y >= demand [95] - initial stock [90], which ensures we meet demand

The objective is: maximise [x+30-75] + [y+90-95] = [x+y-50]
i.e. to maximise the number of units left in stock at the end of the week

It is plain from the diagram below that the maximum occurs at the intersection of x=45 and 50x + 24y = 2400

Solving simultaneously, rather than by reading values off the graph, we have that x=45 and y=6.25 with the value of the objective function being 1.25

Linear programming example 1995 UG exam

The demand for two products in each of the last four weeks is shown below.

Week 1 2 3 4 Demand - product 1 23 27 34 40 Demand - product 2 11 13 15 14

Apply exponential smoothing with a smoothing constant of 0.7 to generate a forecast for the demand for these products in week 5.

These products are produced using two machines, X and Y. Each unit of product 1 that is produced requires 15 minutes processing on machine X and 25 minutes processing on machine Y. Each unit of product 2 that is produced requires 7 minutes processing on machine X and 45 minutes processing on machine Y. The available time on machine X in week 5 is forecast to be 20 hours and on machine Y in week 5 is forecast to be 15 hours. Each unit of product 1 sold in week 5 gives a contribution to profit of £10 and each unit of product 2 sold in week 5 gives a contribution to profit of £4.

It may not be possible to produce enough to meet your forecast demand for these products in week 5 and each unit of unsatisfied demand for product 1 costs £3, each unit of unsatisfied demand for product 2 costs £1.

• Formulate the problem of deciding how much of each product to make in week 5 as a linear program.
• Solve this linear program graphically.

Solution

Note that the first part of the question is a forecasting question so it is solved below.

For product 1 applying exponential smoothing with a smoothing constant of 0.7 we get:

M1 = Y1 = 23
M2 = 0.7Y2 + 0.3M1 = 0.7[27] + 0.3[23] = 25.80
M3 = 0.7Y3 + 0.3M2 = 0.7[34] + 0.3[25.80] = 31.54
M4 = 0.7Y4 + 0.3M3 = 0.7[40] + 0.3[31.54] = 37.46

The forecast for week five is just the average for week 4 = M4 = 37.46 = 31 [as we cannot have fractional demand].

For product 2 applying exponential smoothing with a smoothing constant of 0.7 we get:

M1 = Y1 = 11
M2 = 0.7Y2 + 0.3M1 = 0.7[13] + 0.3[11] = 12.40
M3 = 0.7Y3 + 0.3M2 = 0.7[15] + 0.3[12.40] = 14.22
M4 = 0.7Y4 + 0.3M3 = 0.7[14] + 0.3[14.22] = 14.07

The forecast for week five is just the average for week 4 = M4 = 14.07 = 14 [as we cannot have fractional demand].

We can now formulate the LP for week 5 using the two demand figures [37 for product 1 and 14 for product 2] derived above.

Let

x1 be the number of units of product 1 produced

x2 be the number of units of product 2 produced

where x1, x2>=0

The constraints are:

15x1 + 7x2 = 0

Solution

To solve this LP we use the equation c-a-b=0 to put c=a+b [>= 0 as a >= 0 and b >= 0] and so the LP is reduced to

minimise

4a + 5b + 6[a + b] = 10a + 11b

subject to

a + b >= 11

a - b = 35

a >= 0 b >= 0

From the diagram below the minimum occurs at the intersection of a - b = 5 and a + b = 11

i.e. a = 8 and b = 3 with c [= a + b] = 11 and the value of the objective function 10a + 11b = 80 + 33 = 113.

Linear programming example 1987 UG exam

Solve the following linear program:

maximise 5x1 + 6x2

subject to

x1 + x2 = 3

5x1 + 4x2 = 0

x2 >= 0

Solution

It is plain from the diagram below that the maximum occurs at the intersection of

5x1 + 4x2 = 35 and

x1 - x2 = 3

Solving simultaneously, rather than by reading values off the graph, we have that

5[3 + x2] + 4x2 = 35

i.e. 15 + 9x2 = 35

i.e. x2 = [20/9] = 2.222 and

x1 = 3 + x2 = [47/9] = 5.222

The maximum value is 5[47/9] + 6[20/9] = [355/9] = 39.444

Linear programming example 1986 UG exam

A carpenter makes tables and chairs. Each table can be sold for a profit of £30 and each chair for a profit of £10. The carpenter can afford to spend up to 40 hours per week working and takes six hours to make a table and three hours to make a chair. Customer demand requires that he makes at least three times as many chairs as tables. Tables take up four times as much storage space as chairs and there is room for at most four tables each week.

Formulate this problem as a linear programming problem and solve it graphically.

Solution

Variables

Let

xT = number of tables made per week

xC = number of chairs made per week

Constraints

• total work time

6xT + 3xC = 3xT

• storage space

[xC/4] + xT = 0

Objective

maximise 30xT + 10xC

The graphical representation of the problem is given below and from that we have that the solution lies at the intersection of

[xC/4] + xT = 4 and 6xT + 3xC = 40

Solving these two equations simultaneously we get xC = 10.667, xT = 1.333 and the corresponding profit = £146.667