1 of 8 0-day streak

Find an optimum assignment with the Hungarian algorithm

Question 1 of 8

Calculator allowed

A laboratory assigns instruments to tests. The rows represent the instruments and the columns represent the tests. Each entry is an integer setup time in minutes

The aim is to minimise the total setup time. Use the reductions and independent zeros to find the required assignment

Original setup time table (minutes)
Row	Test 3	Test 1	Test 2
Instrument 3	36	48	27
Instrument 1	51	27	42
Instrument 2	30	51	63

(a)3 marks

Complete the row minima needed for the Hungarian reduction

Instrument 3 minimum Instrument 1 minimum Instrument 2 minimum

(b)1 mark

Select the complete allocation with the optimum original total

Instrument 1 → Test 1; Instrument 2 → Test 3; Instrument 3 → Test 2

Instrument 1 → Test 1; Instrument 2 → Test 2; Instrument 3 → Test 3

Instrument 1 → Test 2; Instrument 2 → Test 3; Instrument 3 → Test 1

Instrument 1 → Test 1; Instrument 2 → Test 1; Instrument 3 → Test 2

Enter the optimum original total setup time

Optimum total setup time (minutes)