Chapter 8 Linear Programming

1.       Objectives

1.1       Formulate and solve a multiple scarce resource problem both graphically and using simultaneous equations as appropriate.
1.2       Explain and calculate shadow prices (dual prices) and discuss their implications on decision-making and performance management.
1.3       Calculate slack and explain the implications of the existence of slack for decision-making and performance management.

2.       The Principles of Linear Programming

2.1	The Concept of Linear Programming
	Linear programming is a technique for solving problems of profit maximisation or cost minimisation and resource allocation. 'Programming' has nothing to do with computers: the word is simply used to denote a series of events. If a scenario contains two or more limiting factors, linear programming must be applied.

2.2       A typical business problem is to decide how a company should divide up its production among the various types of product it manufactures in order to obtain the maximum possible profit. A business cannot simply aim to produce as much as possible because there will be limitations or constraints within which the production must operate. Such constraints could be one or more of the following.
(a)        Limited quantities of raw materials available
(b)        A fixed number of man-hours per week for each type of worker
(c)        Limited machine hours

3.       Formulating the Problem

3.1	Steps in Linear Programming
	The steps involved are as follows. 1.        Define variables 2.        Construct objective function 3.        Establish constraints 4.        Graph constraints 5.        Establish feasible region 6.        Add iso-profit/contribution line 7.        Determine optimal solution

3.2       Maximisation problem

3.2.1

Example 1

Brunel manufactures plastic-covered steel fencing in two qualities, standard and heavy gauge. Both products pass through the same processes, involving steel-forming and plastic bonding. Standard gauge fencing sells at $18 a roll and heavy gauge fencing at $24 a roll. Variable costs per roll are $16 and $21 respectively. There is an unlimited market for the standard gauge, but demand for the heavy gauge is limited to 1,300 rolls a year. Factory operations are limited to 2,400 hours a year in each of the two production processes.   Processing hour per roll Gauge Steel-forming Plastic-bonding Standard 0.6 0.4 Heavy 0.8 1.2 What is the production mix which will maximize total contribution and what would be the total contribution? Solution: Let S be the number of standard gauge rolls per year. Let H be the number of heavy gauge rolls per year. The objective is to maximize 2S + 3H (contribution), subject to the following constraints. 0.6S + 0.8H ≦ 2,400 (Steel-forming hours) 0.4S + 1.2H ≦ 2,400 (Plastic-bonding hours) H ≦ 1,300 (Sales demand) S, H ≧ 0   Graph constraints This occurs at corner B where the following two constraint lines cross: 0.4S + 1.2H = 2,400 0.6S + 0.8H = 2,400 Solve the above equation, the contribution is maximized where: H = 1,200 and S = 2,400   Units Contribution per unit ($) Total contribution ($) Standard gauge 2,400 2 4,800 Heavy gauge 1,200 3 3,600       8,400

 

3.3       Minimisation problems

3.3.1    Although decision problems with limiting factors usually involve the maximisation of contribution, there may be a requirement to minimise costs. A graphical solution, involving two variables, is very similar to that for a maximisation problem, with the exception that instead of finding a contribution line touching the feasible area as far away from the origin as possible, we look for a total cost line touching the feasible area as close to the origin as possible.

3.3.2

Example 2

Claire Speke has undertaken a contract to supply a customer with at least 260 units in total of two products, X and Y, during the next month. At least 50% of the total output must be units of X. The products are each made by two grades of labour, as follows.   X Y   Hours Hours Grade A labour 4 6 Grade B labour 4 2 Total 8 8 Although additional labour can be made available at short notice, the company wishes to make use of 1,200 hours of Grade A labour and 800 hours of Grade B labour which has already been assigned to working on the contract next month. The total variable cost per unit is $120 for X and $100 for Y. Claire Speke wishes to minimise expenditure on the contract next month. How much of X and Y should be supplied in order to meet the terms of the contract? Solution: Let X be the number of units of X Let Y be the number of units of Y The objective is to minimise 120X + 100Y (cost), subject to the following constraints.   X + Y ≧ 260 (Supply total) X ≧ 0.5 (X + Y) (Proportion of X in total) 4X + 6Y ≧ 1,200 (Grade A labour) 4X + 2Y ≧ 800 (Grade B labour) X, Y ≧ 0   The constraint X ≧ 0.5 (X + Y) needs simplifying further. X ≧ 0.5 (X + Y) 2X ≧ X + Y X ≧ Y In a graphical solution, the line will be X = Y. Graph constraints The cost line 120x + 100y = 12,000 has been drawn to show the slope of every cost line 120x + 100y. Costs are minimised where a cost line touches the feasible area as close as possible to the origin of the graph. This occurs where the constraint line 4x + 2y = 800 crosses the constraint line x + y = 260. This point is found as follows. x + y = 260              (1) 4x + 2y = 800          (2) 2x + y = 400            (3) ((2) ÷ 2) x = 140                    (4) ((3) – (1)) y = 120                    (5)   Cost will be minimized by supplying the following   Unit cost ($) Total cost ($) 140 units of X 120 16,800 120 units of Y 100 12,000     28,800 The proportion of units of X in the total would exceed 50%, and demand for Grade A labour would exceed the 1,200 hours minimum.

4.      Slack (寬鬆) and Surplus (剩餘)

4.1	Slack and Surplus
	Slack occurs when maximum availability of a resource is not used. Surplus occurs when more than a minimum requirement is used.

4.2       If, at the optimal solution, the resource used equals the resource available there is no spare capacity of a resource and so there is no slack.
4.3       If a resource which has a maximum availability is not binding at the optimal solution, there will be slack.

4.4

Example 3

A machine shop makes boxes (B) and tins (T). Contribution per box is $5 and per tin is $7. A box requires 3 hours of machine processing time, 16kg of raw materials and 6 labour hours. A tin requires 10 hours of machine processing time, 4kg of raw materials and 6 labour hours. In a given month, 330 hours of machine processing time are available, 400kg of raw material and 240 labour hours. The manufacturing technology used means that at least 12 tins must be made every month. The constraints are: 3B + 10T ≤ 330 16B + 4T ≤ 400 6B + 6T ≤ 240 T ≥ 12 The optimal solution is found to be to manufacture 10 boxes and 30 tins. If we substitute these values into the inequalities representing the constraints, we can determine whether the constraints are binding or whether there is slack. Machine time: (3 × 10) + (10 × 30) = 330 = availability Constraint is binding Raw materials: (16 × 10) + (4 × 30) = 280 < 400 There is slack of 120kg of raw materials. Labour: (6 × 10) + (6 × 30) = 240 = availability Constraint is binding. If a minimum quantity of a resource must be used and, at the optimal solution, more than that quantity is used, there is a surplus on the minimum requirement. This is shown here in the production of tins where the optimal production is 30 tins but T ≥ 12. There is therefore a surplus of 18 tins over the minimum production requirement. You can see from this that slack is associated with ≤ constraints and surplus with ≥ constraints. Machine time and labour are binding constraints so they have been used to their full capacity. It can be argued that if more machine time and labour could be obtained, more boxes and tins could be produced and contribution increased.

5.      Shadow Prices

5.1	Shadow Prices
	The shadow price or dual price of a limiting factor is the increase in value which would be created by having one additional unit of the limiting factor at the original cost. The shadow price is the increase in contribution created by the availability of an extra unit of a limited resource at its original cost.

5.2

Example 4

Let us suppose that WX manufactures two products, A and B. Both products pass through two production departments, mixing and shaping. The organisation's objective is to maximise contribution to fixed costs. Product A is sold for $1.50 whereas product B is priced at $2.00. There is unlimited demand for product A but demand for B is limited to 13,000 units per annum. The machine hours available in each department are restricted to 2,400 per annum. Other relevant data are as follows. Machine hours required Mixing Shaping   Hrs Hrs Product A 0.06 0.04 Product B 0.08 0.12       Variable cost per unit   $ Product A   1.30 Product B   1.70 The objective function is: Contribution (C) = 0.2x + 0.3y The constraints are: 0.06x + 0.08y ≤ 2,400 0.04x + 0.12y ≤ 2,400 0 ≤ y ≤ 13,000 0 ≤ x The availability of time in both departments are limiting factors because both are used up fully in the optimal product mix. Let us therefore calculate the effect if one extra hour of shaping department machine time was made available so that 2,401 hours were available. The new optimal product mix would be at the intersection of the two constraint lines 0.06x + 0.08y = 2,400 and 0.04x + 0.12y = 2,401. Solution by simultaneous equations gives x = 23,980 and y = 12,015.       Product Units Contribution per unit ($) Total contribution ($) A 23,980 0.20 4,796.0 B 12,015 0.30 3,604.5       8,400.5 Original contribution [(24,000 x $0.20 + (12,000 x $0.30)) 8,400.0 Increase in contribution form one extra hour of shaping time 0.5 The shadow price of an hour of machining time in the shaping department is therefore the standard machine cost plus $0.50. This means that extra machine capacity could be rented, for example, provided the cost is less than $0.50 per hour. This value of machine time only applies as long as shaping machine time is a limiting factor. If more and more machine hours become available, there will eventually be so much machine time that it is no longer a limiting factor.

Examination Style Questions

Question 1 – Limiting Factors and Linear Programming (Maximize Contribution)
A company manufactures and sells two types of product to a number of customers. The company is currently preparing its budget for the year ending 31 December 2010 which it divides into 12 equal periods.

The cost and resource details for each of the company’s product types are as follows:

	Product type M	Product type F
	$	$
Selling price per unit	200	210
Variable costs per unit
Direct material P ($2.50 per litre)	20	25
Direct material Q ($4.00 per litre)	40	20
Direct labour ($7.00 per hour)	28	35
Overhead ($4.00 per hour)	16	20
Fixed production cost per unit	40	50
	Units	Units
Maximum sales demand in period 1	1,000	3,000

The fixed production cost per unit is based upon an absorption rate of $10 per direct labour hour and a total annual production activity of 180,000 direct labour hours. One-twelfth of the annual fixed production cost will be incurred in period 1.

In addition to the above costs, non-production overhead costs are expected to be $57,750 in period 1.

During period 1, the availability of material P is expected to be limited to 31,250 litres. Other materials and sufficient direct labour are expected to be available to meet demand.

It is the company’s policy not to hold inventories of finished goods.

Required:

(a)        Calculate the number of units of product types M and F that should be produced and sold in period 1 in order to maximize profit.                                                                                    (3 marks)
(b)        Using your answer to (a) above, prepare a columnar budgeted profit statement for period 1 in a marginal cost format.                                                                                                         (4 marks)

After presenting your statement to the budget management meeting, the production manager has advised you that in period 1 the other resources will also be limited. The maximum resources available will be:

It has been agreed that these factors should be incorporated into a revised plan and that the objective should be to make as much profit as possible from the available resources.

(c)        Using graphical linear programming to determine the revised production plan for period 1. State clearly the number of units of product types M and F that are to be produced.             (7 marks)
(d)        Using your answer to part (c) above, calculate the profit that will be earned from the revised plan.                                                                                                                            (2 marks)
(e)        Calculate and explaining the meaning of the shadow price for material Q.
(4 marks)
(Total 20 marks)

Question 2 – Linear Programming (Maximise Contribution)
The instruments department of Max Ltd makes two products: the XL and the YM. Standard revenues and costs per unit for these products are show below:

	XL		TM
	$	$	$	$
Selling price		200		180
Variable costs:
Material A ($10 per kg)	(40)		(40)
Direct labour ($8 per hour)	(32)		(16)
Plating ($12 per hour)	(12)		(24)
Other variable costs	(76)		(70)
		(160)		(150)
Fixed overheads (allocated at $7 per direct labour hour)		(28)		(14)
Standard profit per unit		12		16

Plating is a separate automated operation and the costs of $12 per hour are for plating materials and electricity.

In any week the maximum availability of inputs is limited to the following:

A management meeting recently considered ways of increasing the profit of the instrument department. It was decided that each of the following possible changes to the existing situation should be examined independently of each other.

(1)        The selling price of product YM could be increased.
(2)        Plating time could be sold as a separate service at $16 per hour.
(3)        A new product, ZN, could be sold at $240 per unit. Each unit would require the following:

 

 

(4)        Overtime could be introduced and would be paid at a premium of 50% above normal rates.

Required:

(a)        Formulate a linear programme to determine the production policy which maximizes the profits of Max Ltd in the present situation (i.e. ignoring the alternative assumptions in 1 to 4 above), solve, and specify the optimal product mix and weekly profit.                                                      (10 marks)
(b)        Determine the maximum selling price of YM at which the product mix calculated for requirement (a) would still remain optimal.                                                                                 (4 marks)
(c)        Show how the linear programme might be modified to accommodate the sale of plating time at $16 per hour (i.e. formulate but do not solve).
(3 marks)
(d)        Using shadow prices (dual values), calculate whether product ZN would be a profitable addition to the product range.                                                                                                     (5 marks)
(e)        Ignoring the possibility of extending the product range, determine whether overtime working would be worthwhile, and if so state how many overtime hours should be worked.         (3 marks)
(Total 25 marks)

Question 3 – Linear Programming (Minimise costs)
HK Ltd is a light engineering company which produces a range of components, machine tools and electronic devices for the motor and aircraft industry.

HK Ltd produces two types of alarm system, one for offices and homes (X) and the other for motor vehicles (Y), on the same equipment. For financial reasons, it is important to minimize the costs of production. To match the current stock and demand position at least 100 alarm systems in total are required each week, but the quantity of one type must not exceed twice that of the other. The inputs necessary for the manufacture of one alarm system are given below, together with the availability of resources each week.

Type	Plating	Circuitry	Assembly
X	3 feet	4 units	20 minutes
Y	2 feet	8 units	8 minutes
Totals available each week	420 feet	800 units	34 hours

The management accountant estimates that the unit costs of production are $100 for X and $80 for Y. Past experience suggests that all alarms can be sold. At present, 75 of each alarm system are produced each week.

Required:

State the objective function and the constraints for the production of alarm systems and use a graphical method of linear programming to find the optimal product mix.
(10 marks)

Question 4 – Linear Programming (Maximise Contribution)
Higgins Co (HC) manufactures and sells pool cues and snooker cues. The cues both use the same type of good quality wood (ash) which can be difficult to source in sufficient quantity. The supply of ash is restricted to 5,400 kg per period. Ash costs $40 per kg.

The cues are made by skilled craftsmen (highly skilled labour) who are well known for their workmanship. The skilled craftsmen take years to train and are difficult to recruit. HC’s craftsmen are generally only able to work for 12,000 hours in a period. The craftsmen are paid $18 per hour.

HC sells the cues to a large market. Demand for the cues is strong, and in any period, up to 15,000 pool cues and 12,000 snooker cues could be sold. The selling price for pool cues is $41 and the selling price for snooker cues is $69.

Manufacturing details for the two products are as follows:

	Pool cues	Snooker cues
Craftsmen time per cue	0.5 hours	0.75 hours
Ash per cue	270 g	270 g
Other variable costs per cue	$1.20	$4.70

HC does not keep inventory.

Required:

(a)        Calculate the contribution earned from each cue.                                              (2 marks)
(b)        Determine the optimal production plan for a typical period assuming that HC is seeking to maximise the contribution earned. You should use a linear programming graph (using the graph paper provided), identify the feasible region and the optimal point and accurately calculate the maximum contribution that could be earned using whichever equations you need.                              (12 marks)

Some of the craftsmen have offered to work overtime, provided that they are paid double time for the extra hours over the contracted 12,000 hours. HC has estimated that up to 1,200 hours per period could be gained in this way.

Required:

(c)        Explain the meaning of a shadow price (dual price) and calculate the shadow price of both the labour (craftsmen) and the materials (ash).                                                                    (5 marks)
(d)        Advise HC whether to accept the craftsmens’ initial offer of working overtime, discussing the rate of pay requested, the quantity of hours and one other factor that HC should consider. (6 marks)
(25 marks)
(ACCA F5 Performance Management June 2008 Q2)