Four contractors, \(\text{P, Q, R}\) and \(\text{S}\), have been hired to complete work at one of four sites.

Each contractor will be allocated to a different site.

The cost for each contractor to complete the works, in dollars ($), is shown in the table below
 

The Hungarian algorithm is used to determine the minimum cost to complete the works.

Martha, the project manager, completes two steps of the Hungarian algorithm, as follows.

• First, she subtracts the minimum entry in each row from each element in that row to obtain a new table of values.
• Then, using this new table, she subtracts the minimum entry in each column from each element in that column.

Which one of the following tables correctly displays the results after these two steps are completed?
 

Anush, Blake, Carly and Dexter are workers on a construction site. They are each allocated one task.

The time, in hours, it takes for each worker to complete each task is shown in the table below.

\begin{array}{|c|c|c|c|c|}
\hline
\rule{0pt}{2.5ex} \rule[-1ex]{0pt}{0pt}& \textbf{Task 1} & \textbf{Task 2} & \textbf{Task 3} & \textbf{Task 4} \\
\hline
\rule{0pt}{2.5ex} \textbf{Anush} \rule[-1ex]{0pt}{0pt}& 12 & 8 & 16 & 9 \\
\hline
\rule{0pt}{2.5ex} \textbf{Blake} \rule[-1ex]{0pt}{0pt}& 10 & 7 & 15 & 10 \\
\hline
\rule{0pt}{2.5ex} \textbf{Carly} \rule[-1ex]{0pt}{0pt}& 11 & 10 & 18 & 12 \\
\hline
\rule{0pt}{2.5ex} \textbf{Dexter} \rule[-1ex]{0pt}{0pt}& 10 & 14 & 16 & 11 \\
\hline
\end{array}

The tasks must be completed sequentially and in numerical order: Task 1, Task 2, Task 3 and then Task 4.

Management makes an initial allocation of tasks to minimise the amount of time required, but then decides that it takes the workers too long.

Another worker, Edgar, is brought in to complete one of the tasks.

His completion times, in hours, are listed below.

\begin{array}{|c|c|c|c|c|}
\hline
\rule{0pt}{2.5ex} \rule[-1ex]{0pt}{0pt}& \textbf{Task 1} & \textbf{Task 2} & \textbf{Task 3} & \textbf{Task 4} \\
\hline
\rule{0pt}{2.5ex} \textbf{Edgar} \rule[-1ex]{0pt}{0pt}& 9 & 5 & 14 & 8 \\
\hline
\end{array}

When a new allocation is made and Edgar takes over one of the tasks, the minimum total completion time compared to the initial allocation will be reduced by

1. 1 hour.
2. 2 hours.
3. 3 hours.
4. 4 hours.

Four employees, Anthea, Bob, Cho and Dario, are each assigned a different duty by their manager.

The time taken for each employee to complete duties 1,2,3 and 4, in minutes, is shown in the table below

\begin{array} {|l|c|c|c|c|}
\hline \rule{0pt}{2.5ex} \text{} \rule[-1ex]{0pt}{0pt} & \text{Duty 1} & \text{Duty 2} & \text{Duty 3} & \text{Duty 4} \\
\hline \rule{0pt}{2.5ex} \text{Anthea} \rule[-1ex]{0pt}{0pt} & \text{8} & \text{7} & \text{7} & \text{8}\\
\hline \rule{0pt}{2.5ex} \text{Bob} \rule[-1ex]{0pt}{0pt} & \text{10} & \text{8} & \text{10} & \text{9}\\
\hline \rule{0pt}{2.5ex} \text{Cho} \rule[-1ex]{0pt}{0pt} & \text{8} & \text{9} & \text{7} & \text{10}\\
\hline \rule{0pt}{2.5ex} \text{Dario} \rule[-1ex]{0pt}{0pt} & \text{7} & \text{7} & \text{8} & \text{9}\\
\hline
\end{array}

The manager allocates the duties so as to minimise the total time taken to complete the four duties.

The minimum total time taken to complete the four duties, in minutes, is

1. 29
2. 30
3. 31
4. 32

Four students, Alice, Brad, Charli and Dexter, are working together on a school project.

This project has four parts.

Each of the students will complete only one part of the project.

The table below shows the time it would take each student to complete each part of the project, in minutes.
 

  
The parts of this project must be completed one after the other.

Which allocation of student to part must occur for this project to be completed in the minimum time possible?

Annie, Buddhi, Chuck and Dorothy work in a factory.

Today each worker will complete one of four tasks, 1, 2, 3 and 4.

The usual completion times for Annie, Chuck and Dorothy are shown in the table below.
 

Buddhi takes 3 minutes for Task 3.

He takes `k` minutes for each other task.

Today the factory supervisor allocates the tasks as follows

• • Task 1 to Dorothy
  • Task 2 to Annie
  • Task 3 to Buddhi
  • Task 4 to Chuck

This allocation will achieve the minimum total completion time if the value of `k` is at least

1. 0
2. 1
3. 2
4. 3
5. 4

Bai joins his friends Agatha, Colin and Diane when he arrives for a holiday in Seatown.

Each person will plan one tour that the group will take.

Table 1 shows the time, in minutes, it would take each person to plan each of the four tours.
 

 
The aim is to minimise the total time it takes to plan the four tours.

Agatha applies the Hungarian algorithm to Table 1 to produce Table 2.

Table 2 shows the final result of all her steps of the Hungarian algorithm.
 

1. In Table 2 there is a zero in the column for Colin.
   When all values in the table are considered, what conclusion about minimum total planning time can be made from this zero?   (1 mark)
   

   --- 1 WORK AREA LINES (style=lined) ---

2. Determine the minimum total planning time, in minutes, for all four tours.   (1 mark)
   

   --- 2 WORK AREA LINES (style=lined) ---

Five children, Alan, Brianna, Chamath, Deidre and Ewen, are each to be assigned a different job by their teacher. The table below shows the time, in minutes, that each child would take to complete each of the five jobs.
 

The teacher wants to allocate the jobs so as to minimise the total time taken to complete the five jobs.

In doing so, she finds that two allocations are possible.

If each child starts their allocated job at the same time, then the first child to finish could be either

1. Alan or Brianna.
2. Brianna or Deidre.
3. Chamath or Deidre.
4. Chamath or Ewen.
5. Deidre or Ewen. 

The table below shows the time (in minutes) that each of four people, Aiden, Bing, Callum and Dee, would take to complete each of the tasks `U, V, W` and `X.`
 

If each person is allocated one task only, the minimum total time for this group of people to complete all four tasks is

A.   `22\ text(minutes)`

B.   `28\ text(minutes)`

C.   `29\ text(minutes)`

D.   `30\ text(minutes)`

E.   `32\ text(minutes)`

Four workers, Anna, Bill, Caitlin and David, are each to be assigned a different task.

The table below gives the time, in minutes, that each worker takes to complete each of the four tasks.
 

The tasks are allocated so as to minimise the total time taken to complete the four tasks.

This total time, in minutes, is

A.   `21`

B.   `28`

C.   `31`

D.   `34`

E.   `38`

Kate, Lexie, Mei and Nasim enter a competition as a team. In this competition, the team must complete four tasks, `W, X, Y\ text(and)\ Z`, as quickly as possible.

The table shows the time, in minutes, that each person would take to complete each of the four tasks.
 

If each team member is allocated one task only, the minimum time in which this team would complete the four tasks is

A.   `10\ text(minutes)`

B.   `12\ text(minutes)`

C.   `13\ text(minutes)`

D.   `14\ text(minutes)`

E.   `15\ text(minutes)`

Four people, Abe, Bailey, Chris and Donna, are each to be allocated one of four tasks. Each person can complete each of the four tasks in a set time. These times, in minutes, are shown in the table below.
 

 
If each person is allocated a different task, the minimum total time for these four people to complete these four tasks is

A.   260 minutes

B.   355 minutes

C.   360 minutes

D.   365 minutes

E.   375 minutes

Each of four children is to be driven by his or her parents to one of four different concerts. The following table shows the distance that each car would have to travel, in kilometres, to each of the four concerts. 

The concerts will be allocated so as to minimise the total distance that must be travelled to take the children to the concerts. The hungarian algorithm is to be used to find this minimum value.

1. Step 1 of the hungarian algorithm is to subtract the minimum entry in each row from each element in the row. Complete step 1 for Tahlia by writing the missing values in the table below.   (1 mark)
   

   --- 0 WORK AREA LINES (style=lined) ---

    

After further steps of the hungarian algorithm have been applied, the table is as follows.
 
 

It is now possible to allocate each child to a concert.

2. Explain why this table shows that Tahlia should attend Concert 2.   (1 mark)
   

   --- 2 WORK AREA LINES (style=lined) ---

3. Determine the concerts that could be attended by James, Dante and Chanel to minimise the total distance travelled. Write your answers in the table below.   (1 mark)
   

   --- 0 WORK AREA LINES (style=lined) ---

    

   
   

4. Determine the minimum total distance, in kilometres, travelled by the four cars.   (1 mark)
   

   --- 3 WORK AREA LINES (style=lined) ---

Planning a train club open day involves four tasks.

Table 1 shows the number of hours that each club member would take to complete these tasks.
 

The Hungarian algorithm will be used to allocate the tasks to club members so that the total time taken to complete the tasks is minimised.

The first step of the Hungarian algorithm is to subtract the smallest element in each row of Table 1 from each of the elements in that row.

The result of this step is shown in Table 2 below.

1. Complete Table 2 by filling in the missing numbers for Andrew.   (1 mark)
   

   --- 0 WORK AREA LINES (style=lined) ---

    
   

    

   
    

After completing Table 2, Andrew decided that an allocation of tasks to minimise the total time taken was not yet possible using the Hungarian algorithm.

2. Explain why Andrew made this decision.   (1 mark)
   

   --- 2 WORK AREA LINES (style=lined) ---

Table 3 shows the final result of all steps of the Hungarian algorithm.
 

3.  i. Which task should be allocated to Andrew?   (1 mark)
   

   --- 1 WORK AREA LINES (style=lined) ---

4. ii. How many hours in total are used to plan for the open day?   (1 mark)
   

   --- 2 WORK AREA LINES (style=lined) ---

Four tasks, `W`, `X`, `Y` and `Z`, must be completed. 

Four workers, Julia, Ken, Lana and Max, will each do one task. 

Table 1 shows the time, in minutes, that each person would take to complete each of the four tasks.
 

The tasks will be allocated so that the total time of completing the four tasks is a minimum. 

The Hungarian method will be used to find the optimal allocation of tasks. Step 1 of the Hungarian method is to subtract the minimum entry in each row from each element in the row.
 

1. Complete step 1 for task `X` by writing down the number missing from the shaded cell in Table 2.   (1 mark)
   

   --- 0 WORK AREA LINES (style=lined) ---

The second step of the Hungarian method ensures that all columns have at least one zero.

The numbers that result from this step are shown in Table 3 below.
 

2. Following the Hungarian method, the smallest number of lines that can be drawn to cover the zeros is shown dashed in Table 3.
   

    

   These dashed lines indicate that an optimal allocation cannot be made yet.
   

    

   Give a reason why.   (1 mark)
   

   --- 2 WORK AREA LINES (style=lined) ---

3. Complete the steps of the Hungarian method to produce a table tasks can be made.
   

    

   Two blank tables have been provided for working if needed.   (1 mark)
   

   --- 0 WORK AREA LINES (style=lined) ---

    

    
       
   
         
    

4. Write the name of the task that each person should do for the optimal allocation of tasks.   (2 marks)
   

   --- 0 WORK AREA LINES (style=lined) ---