AS October 2020 Q2

EdexcelCurrent spec9 marksAllocation

2. Four workers, A, B, C and D, are each to be assigned to one of four tasks, P, Q, R and S.

Each worker must be assigned to one task, and each task must be done by exactly one worker.

Worker C cannot be assigned to task Q.

The amount, in pounds, that each worker would earn when assigned to each task is shown in the table below.

	P	Q	R	S
A	72	98	59	84
B	67	87	68	86
C	70	–	62	79
D	78	93	64	81

The Hungarian algorithm is to be used to find the maximum total amount that can be earned by the four workers.

(a) Explain how the table should be modified so that the Hungarian algorithm may be applied. (2)

(b) Modify the table so that the Hungarian algorithm may be applied. (1)

(c) Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total earnings. You should explain how any initial row and column reductions were made and also how you determined if the table was optimal at each stage. (6)

Mark scheme (a)

Scheme	Marks	AO
Subtract each entry from a constant (e.g. 98) to convert from maximisation problem to minimisation	B1	1.1a
Add an appropriate large value to cell CQ (e.g. twice the largest value) to make CQ unattractive	B1	3.5c
	(2)

Notes

B1: Valid statement regarding converting a maximisation problem to a minimisation problem

B1: Explain the need to add an unattractive value to cell CQ

(note that candidates may first assign a negative value to the CQ entry and then subtract)

Mark scheme (c)

Scheme

Marks

No reduction for row A, reduce row B by 11, reduce row C by 19 and row D by 5 (or equivalent). Reduce column P by 9 and column R by 17, no reduction in columns Q and S.

2.4

Reducing rows and columns gives

	P	Q	R	S
A	26	0	39	14
B	20	0	19	1
C	9	59	17	0
D	15	0	29	12

followed by

	P	Q	R	S
A	17	0	22	14
B	11	0	2	1
C	0	59	0	0
D	6	0	12	12

1.1b

Two lines required to cover the zeros hence solution is not optimal (augment by 1)

	P	Q	R	S
A	16	0	21	13
B	10	0	1	0
C	0	60	0	0
D	5	0	11	11

1.1b

Three lines required to cover the zeros hence solution is not optimal (augment by 5)

e.g.

	P	Q	R	S
A	11	0	16	8
B	10	5	1	0
C	0	65	0	0
D	0	0	6	6

1.1b

Four lines required to cover the zeros hence solution is optimal

2.4

A – Q, B – S, C – R, D – P

2.2a

(6)

(9 marks)

Notes

B1: Correct statements regarding row and column reduction

M1: Simplifying the initial matrix by reducing rows and then columns

M1: Develop an improved solution – need to see one double covered +e; one uncovered –e; and one single covered unchanged. 2 lines needed to 3 lines needed

M1: Develop an improved solution – need to see one double covered +e; one uncovered –e; and one single covered unchanged. 3 lines needed to 4 lines needed (so getting to the optimal table)

B1: Correct statements regarding the minimum number of lines to cover zeros

A1: CSO on final table (so must have scored all previous M (but not necessarily the B) marks in this part) + deduction of the correct allocation