topic badge

7.05 Assignment allocation

Worksheet
Adjacency matrices
1

Construct an adjacency matrix, with row and column titles in alphabetical order, for the following network problems:

a

Three people, Elise, Poppy and Richard, are each to be given 1 task (T1, T2 or T3) to complete on their own.

Each person is able to complete the 3 tasks that are available in a set time. These times, in minutes, are shown on the network diagram given:

b

A physiotherapy company receives requests for 3 home visits (V1, V2 and V3) in the same area. There are 3 workers (W1, W2 and W3) in that area who are available.

The network shows the travel cost for each worker to get to each house in dollars:

c

The coach of a swim team wants to put together a medley relay team for a competition. He needs one swimmer for each of the four kinds of stroke: Backstroke \left(BA\right), Breaststroke \left(BR\right), Butterfly \left(BF\right) and Freestyle \left(FS \right).

The swimmers in the team (S1, S2, S3 and S4) and their average times, in minutes, for each stroke are shown on the network below:

d

Four people, Christie, Hannah, Amelia and Robert, are doing a group assignment together. For this assignment, they need to take photos of 4 landmarks (L1, L2, L3 and L4).

The group decides to split up and visit 1 landmark each. The travel distance between each person’s house and each landmark is shown on the network diagram below:

Tables and bipartite graphs
2

The principal of a school wants to allocate 3 teachers to 3 classes. The following bipartite graph shows all possible allocations of the teachers.

If each teacher can only take one class, construct tables showing the two possible allocations of the teachers.

3

Construct four tables showing the possible allocations that would correspond to the following bipartite graph.

4

Construct three tables showing the possible allocations that would correspond to the following bipartite graph.

5

There are 4 elevators in an office building which has 13 levels. Bob, Avril, Elizabeth and Quentin are waiting for a lift on levels 8, 7, 1 and 6 respectively.

At the moment, Lift 1 is on level 3, Lift 2 is on level 1, Lift 3 is on level 9 and Lift 4 is on level 10. Complete the table showing the number of levels from each lift to each waiting person:

Elevator 1 (level 3)Elevator 2 (level 1)Elevator 3 (level 9)Elevator 4 (level 10)
Bob (level 8)
Avril (level 7)
Elizabeth (level 1)
Quentin (level 6)
6

For each given reduced table, construct a bipartite graph:

a
ABCD
M0403
N8910
O5037
P0400
b
A1A2A3A4A5
T11300180
T201201320
T324130010
T42901709
T516210511
c
X1X2X3X4
Y17010
Y20340
Y39004
Y40706
Hungarian algorithm (graph version)
7

Three friends, Adam, Ben and Christie, decide to have a picnic together. They each agree to buy either snacks, sandwiches or drinks from their local shopping centre and bring them to share at the picnic.

The table below shows the price of these products at each friend’s local shopping centre, in dollars:

\text{Snacks } (1)\text{Sandwiches } (2)\text{Drinks } (3)
Adam6.155.955.55
Ben7.759.258.25
Christie7.355.259.85
a

Construct a network diagram that correctly displays the data in the table.

b

They decide that Adam will purchase the sandwiches, Ben will buy the snacks and Christie will get the drinks. Construct a network diagram that correctly displays this allocation.

c

Calculate the total cost of the picnic.

8

A courier company needs to make multiple pick-ups across several stores.

The lengths of the roads (in \text{km}) linking these stores are shown in the diagram:

Adam, Ben and Caitlin are couriers who are working in the area and they have each just arrived at stores A, B, and C, respectively. They still need to make the pick-ups from stores X, Y, and Z. Each courier can only visit one more store.

Complete a table by listing the shortest distance that each courier could travel to each remaining store. Order the couriers and stores in alphabetical order.

9

Consider the following bipartite graph:

a

Find the minimum cost path(s) from each of the resources represented by vertices in the left hand side.

b

Find the minimum cost path to each of the tasks represented by vertices on the right hand side.

c

On this graph, show the optimum allocation.

d

State the optimum allocation.

10

Consider the following bipartite graph:

a

Find the minimum cost path(s) from each of the resources represented by vertices in the left hand side.

b

Update the edge weights to show the minimum cost path to each of the tasks represented by vertices on the right hand side.

c

Check for any 3 zero edges in a row to complete the next step to find the optimum allocation.

d

Select the edges on the reduced graph that make up the optimum allocation

e

State the optimum allocation.

Hungarian algorithm minimisation (matrix version)
11

The following table represents a matrix after the first row and column reduction of the Hungarian Algorithm has been performed.

Assuming we cross out zeros using three lines as shown, draw the final reduced table.

12

Consider the following cost table:

a

Draw the table, after the first row and column reduction of the Hungarian Algorithm has been performed.

b

Draw the final reduced table.

A_{1}A_{2}A_{3}A_{4}
B_{1}28343329
B_{2}26363831
B_{3}21262834
B_{4}40283329
13

Consider the following cost table:

a

Use the Hungarian Algorithm to draw the final reduced table.

b

Determine the best allocation for A, B, and C.

c

Use this optimum allocation and the original cost table to determine the minimum cost.

ABC
D101611
E111518
F15108
14

Find the reduced form of the matrix using the Hungarian Algorithm for the following cost table:

X_{1}X_{2}X_{3}X_{4}X_{5}
Y_{1}122160180110191
Y_{2}155157170170150
Y_{3}133145162151170
Y_{4}139171150143200
Y_{5}150154170160198
15

The following matrix represents a cost network:

\begin{matrix} & \begin{matrix} P&Q&R&S\end{matrix}\\ \begin{matrix} T\\ U\\ V\\ W \end{matrix} & \begin{bmatrix}7.5&8.5&7.5&11.5\\9.0&9.5&7.0&11.0\\8.5&9.0&8.0&11.0\\8.0&9.0&6.0&10.5 \end{bmatrix} \end{matrix}
a

Use the Hungarian algorithm to determine the optimum allocation for the cost network.

b

Calculate the minimum cost for the network.

16

The following matrix represents a cost network:

\begin{matrix} & \begin{matrix} A&B&C\end{matrix}\\ \begin{matrix} W\\ X\\ Y\\ Z \end{matrix} & \begin{bmatrix}6&6&53\\89&2&59\\96&95&95\\34&12&38 \end{bmatrix} \end{matrix}
a

Use the Hungarian algorithm to determine the optimum allocation for the cost network.

b

Calculate the minimum cost for the network.

17

A courier company has four different delivery vehicles: one bicycle, one motorbike, one small car and one light truck. This morning there are four deliveries to be made. Each of the four vehicles is available to do one of the deliveries

The table below shows the time, in minutes, that each vehicle would take to complete each of the four deliveries:

BicycleMotorbikeCarTruck
Delivery 128243329
Delivery 218192628
Delivery 327211817
Delivery 421242522
a

Use the Hungarian algorithm to allocate a vehicle to each delivery to minimise delivery time.

b

Calculate the minimum total delivery time.

18

A factory produces four different items of gardening equipment: shovels, forks, picks and axes. There are four workers in the factory: Alex, Lucy, Ray and Kerry, who can work on one product at a time. The time, in hours, that it takes each worked to produce a batch of each product is given in the diagram below:

The manager wants to allocate the deliveries so that the total production time is at a minimum.

a

Use the Hungarian algorithm to allocate a worker to each item.

b

Calculate the minimum total time to manufacture one batch of all of the items.

19

The swim coach wants to choose the best medley relay team for a competition from the top four swimmers: Elka, Linda, Petria and Giaan. She needs one swimmer for each of the 4 kinds of stroke: Backstroke \text{(BS)}, Breastroke \text{(BR)}, Butterfly \text{(BU)} and Freestyle \text{(FS)}.

Their average times, in seconds, for each stroke are shown in the network below:

a

Represent this data in a matrix in the given form:

b

Use the Hungarian algorithm to allocate a stroke to each swimmer.

\begin{matrix} & \begin{matrix} & \text{BA} \enspace & \text{BR} \enspace & \text{BU} \enspace & \text{FS} \quad \end{matrix} \\ \begin{matrix} \text{Eika} \\ \text{Linda} \\ \text{Petria} \\ \text{Giaan} \end{matrix} & \begin{bmatrix} ⬚ \quad & ⬚ \quad & ⬚ \quad & ⬚ \\ ⬚ \quad & ⬚ \quad & ⬚ \quad & ⬚ \\ ⬚ \quad & ⬚ \quad & ⬚ \quad & ⬚ \\ ⬚ \quad & ⬚ \quad & ⬚ \quad & ⬚ \end{bmatrix} \end{matrix}
20

A car manufacturing company needs to sign contracts with 5 raw material suppliers for their 5 factories. The cost (thousand \$s) of supplying each factory with raw materials is shown in the following table:

a

If the company can only sign one contract with each supplier, construct a network diagram showing how the company should allocate the suppliers to minimise cost.

b

Calculate the total minimum cost of all the contracts.

S_{1}S_{2}S_{3}S_{4}S_{5}
F_{1}250342264321234
F_{2}271323244311251
F_{3}251333255300237
F_{4}261310260341222
F_{5}280251260300250
21

There are 4 elevators in an office building which has 12 levels. Neil, Michael, Graeme and Brooke are waiting for a lift on levels 10, 3, 4 and 6 respectively. Vacant lifts are currently on levels 10, 7, 4 and 1.

a

Complete the following table to show the number of levels from each lift to each person:

\text{Neil} \\ \text{ (level 10)}\text{Michael} \\ \text{ (level 3)}\text{Graeme} \\ \text{ (level 4)}\text{Brooke} \\ \text{ (level 6)}
\text{Lift 1} \\ \text{(level 10)}
\text{Lift 2} \\ \text{ (level 7)}
\text{Lift 3} \\ \text{ (level 4)}
\text{Lift 4} \\ \text{ (level 1)}
b

Represent this data in a matrix with rows and columns in the same order as the table.

c

Use the Hungarian algorithm to find the optimum allocation of lifts to the waiting people.

d

Calculate the total number of floors that the lifts have to travel to collect all the waiting people.

22

In a sports tournament, a team of 3 athletes need to complete 3 different types of heats in the shortest time possible. The following table represents the average time (in minutes) of each athlete in each type of heat:

a

If every athlete can only compete in one heat each, use the Hungarian algorithm to construct a bipartite graph which represents the optimum allocation for the team of athletes.

b

Calculate the minimum total time of the heats.

Heat DHeat EHeat F
Athlete A487
Athlete B143
Athlete C926
23

A consultancy firm has four consultants, one in Sydney, one in Melbourne, one in Canberra and one in Brisbane. They need to send one consultant to jobs in each of Perth, Adelaide, Darwin and Cairns.

The following table shows the cost of the airplane ticket to send each consultant to each area:

PerthAdelaideDarwinCairns
Sydney370170270220
Melbourne320120290250
Canberra340150260210
Brisbane310200220190
a

Using the Hungarian algorithm, construct a bipartite graph which represents the allocation that minimises travel costs.

b

Calculate the minimum travel cost.

24

A fashion company owns 4 distribution centres in a certain area. 4 retail stores want to start obtaining merchandise from the company. The following table shows the cost of distribution from each centre to each store (in hundreds of dollars):

a

Using the Hungarian algorithm, construct bipartite graphs, which represents the allocations that results in the minimum cost.

b

Calculate the minimum cost of distribution.

Store WStore XStore YStore Z
Centre A5124
Centre B4396
Centre C6457
Centre D2731
25

A construction company has five cranes that need to be sent to five construction sites. The following table displays the distance (kilometres) between each crane and each construction site:

a

In order to save time and money, the construction company wants to allocate the cranes such that the total distance travelled is minimal.

Use the Hungarian Algorithm to construct an allocation that achieves their goal.

b

Calculate the minimum total distance traveled.

Site 1Site 2Site 3Site 4Site 5
Crane 12517192832
Crane 21622193428
Crane 32227141129
Crane 42026111825
Crane 53829341525
26

A limousine company has to dispatch 3 cars to 3 different locations. The table displays the traveling cost (in dollars) of each car to each area:

a

Use the Hungarian algorithm to find the allocation which costs the least.

b

Calculate the minimum cost of travel.

Car 1Car 2Car 3
Location 1293722
Location 2322726
Location 3333425
27

The municipality needs to assign 4 engineers to 4 projects. Each engineer supplied the municipality with the minimum cost for each project. The costs (in thousand dollars) are listed in the following table:

a

If each engineer can only handle one project, and Project 4 has specifically requested Engineer 1, how should the municipality allocate the other engineers in order to get the minimum cost?

b

Determine the total minimum cost of all the projects.

P_{1}P_{2}P_{3}P_{4}
E_{1}84696974
E_{2}29794959
E_{3}119898499
E_{4}3910489109
28

The fire department needs to dispatch 5 trucks from different buildings to 5 fire locations. The following table shows the time (in minutes) for each fire truck to arrive at each fire location:

a

Use the Hungarian algorithm to determine the allocation which results in a minimised time.

b

Construct a network that represents this allocation.

F_{1}F_{2}F_{3}F_{4}F_{5}
T_{1}2332242517
T_{2}3224271621
T_{3}2221192325
T_{4}2726242816
T_{5}2422212319
29

A phone company has 4 job vacancies. After performing all the interviews, they have 4 top candidates. Each candidate proposed their expected wages (\$ \text{/hr}) for each job. The following table shows the wage of each candidate for each job:

a

If each candidate can only do one job, and the second candidate will only do the first job, how should the phone company allocate the other candidates in order to minimise costs?

b

Calculate the minimum cost of distribution.

c

Construct a network that represents the allocation from the part (a).

J_{1}J_{2}J_{3}J_{4}
C_{1}23282531
C_{2}18212620
C_{3}22202427
C_{4}28262727
30

The ambulance service in a major city has 4 ambulances available at 4 bases. To minimise the time to attend any incident, the operators divides the city into 3 zones, with travelling time (in minutes) shown in the table below:

Zone 1Zone 2Zone 3
Ambulance 1332728
Ambulance 2263635
Ambulance 3303823
Ambulance 4283725
a

Create a modified table that can be used with the Hungarian algorithm to determine the optimum allocation.

b

Apply the Hungarian algorithm to determine the allocation which results in a minimised cost (response time) for the modified table. Leave a position blank if an ambulance is not allocated to the zone.

c

Determine the expected response time for each ambulance when sent to the optimum allocated zone.

Hungarian algorithm maximisation (matrix version)
31

The following matrix represents a cost network:

a

Use the Hungarian algorithm to determine the optimum allocation for the cost network.

b
Calculate the maximum cost.
\begin{matrix} & \begin{matrix} N&P&Q&R\end{matrix}\\ \begin{matrix} J\\ K\\ L\\ M \end{matrix} & \begin{bmatrix}15&17&15&23\\18&19&14&17\\17&18&16&22\\16&18&12&21 \end{bmatrix} \end{matrix}
32

The following matrix represents a cost network:

a

Use the Hungarian algorithm to determine the optimum allocation for the cost network.

b

Calculate the maximum cost for the network.

\begin{matrix} & \begin{matrix} A&B&C&D&E\end{matrix}\\ \begin{matrix} V\\ W\\ X\\ Y \end{matrix} & \begin{bmatrix}25&83&29&11&59\\32&12&46&33&29\\61&17&12&13&11\\15&73&37&67&43 \end{bmatrix} \end{matrix}
33

An engineering company employs 4 engineers to work on contract projects. The engineers have different skills so the profit earned for a contract depends on the allocation of the engineers for the current projects.

The profitability (in \$1000\text{s}) is specified in the table below for each engineer on each project to help determine how the company can maximise profits:

Project 1Project 2Project 3Project 4
Engineer 130473736
Engineer 228324844
Engineer 322245044
Engineer 444454141
a

Create a new table that will allow us to perform the allocation as a minimisation problem using the Hungarian algorithm.

b

Apply the Hungarian algorithm to reduce this table to help find the optimum allocation.

c

Determine the allocation which results in a minimised cost (loss of profit).

d

Determine the expected profit for each project with the optimum allocation.

e

Calculate the total profit that can be expected.

34

A manufacturing company has 4 machines with different production rates. The company wishes to produce the maximum number of parts each day.

Machine 1Machine 2Machine 3Machine 4
Operator 1120240120560
Operator 2150250140620
Operator 3110220100610
Operator 416021090540
a

Create a new table that will allow us to perform the allocation as a minimisation problem using the Hungarian algorithm.

b

Apply the Hungarian algorithm to reduce this table to help find the optimum allocation.

c

Determine the allocation which results in a minimised cost (loss of production) for the reduced table.

d

Determine the expected number of parts by each operator with this allocation.

e

Calculate the total number of parts per day that can be expected.

35

An oil and gas engineering firm has four consultants based in the head office. They would like to send one consultant to projects in each of Ravensthorpe, Port Hedland, Darwin and Kalgoorlie.

The following table shows the consulting day rates that can be earned by each engineer in each of the projects. The company wishes to maximise the total consulting fees.

RavensthorpePort HedlandDarwinKalgoorlie
Engineer 1360160260210
Engineer 2310110280140
Engineer 3330140250200
a

Create a new table that will allow us to perform the allocation as a minimisation problem using the Hungarian algorithm.

b

Apply the Hungarian algorithm to the modified table to determine the allocation which results in a minimised cost (loss of earnings).

c

Determine the expected day rate for each Engineer with this allocation

d

Calculate the total consulting fees that can be expected.

Sign up to access Worksheet
Get full access to our content with a Mathspace account

Outcomes

4.3.10

use a bipartite graph and/or its tabular or matrix form to represent an assignment/ allocation problem

4.3.11

determine the optimum assignment(s), by inspection for small-scale problems, or by use of the Hungarian algorithm for larger problems

What is Mathspace

About Mathspace