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 all possible allocations.
Construct tables showing all possible allocations that would correspond to the following bipartite graphs:
For each given reduced table, construct a bipartite graph:
| A | B | C | D | |
|---|---|---|---|---|
| M | 0 | 4 | 0 | 3 |
| N | 8 | 9 | 1 | 0 |
| O | 5 | 0 | 3 | 7 |
| P | 0 | 4 | 0 | 0 |
| 1 | 2 | 3 | |
|---|---|---|---|
| A | 17 | 0 | 0 |
| B | 0 | 0 | 27 |
| C | 0 | 13 | 0 |
| A1 | A2 | A3 | A4 | A5 | |
|---|---|---|---|---|---|
| T1 | 13 | 0 | 0 | 18 | 0 |
| T2 | 0 | 12 | 0 | 13 | 20 |
| T3 | 24 | 13 | 0 | 0 | 10 |
| T4 | 29 | 0 | 17 | 0 | 9 |
| T5 | 16 | 21 | 0 | 5 | 11 |
| X1 | X2 | X3 | X4 | |
|---|---|---|---|---|
| Y1 | 7 | 0 | 1 | 0 |
| Y2 | 0 | 3 | 4 | 0 |
| Y3 | 9 | 0 | 0 | 4 |
| Y4 | 0 | 7 | 0 | 6 |
A car manufacturing company wishes to sign contracts with 5 raw material suppliers for their 5 factories. The cost (thousand \$\text{'s}) of supplying each factory with raw materials is shown in the table:
If the company can only sign one contract with each supplier, construct a bipartite graph to show how they should allocate the suppliers in order to minimise the cost.
Calculate the total minimum cost of all the contracts.
| S_{1} | S_{2} | S_{3} | S_{4} | S_{5} | |
|---|---|---|---|---|---|
| F_{1} | 250 | 342 | 264 | 321 | 234 |
| F_{2} | 271 | 323 | 244 | 311 | 251 |
| F_{3} | 251 | 333 | 255 | 300 | 237 |
| F_{4} | 261 | 310 | 260 | 341 | 222 |
| F_{5} | 280 | 251 | 260 | 300 | 250 |
Construct an adjacency matrix for the following network problems:
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:
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:
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:
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:
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:
| Snacks (1) | Sandwiches (2) | Drinks (3) | |
|---|---|---|---|
| Adam | 6.15 | 5.95 | 5.55 |
| Ben | 7.75 | 9.25 | 8.25 |
| Christie | 7.35 | 5.25 | 9.85 |
Construct a network diagram that correctly represents this data.
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.
Using this allocation, calculate the total cost of the picnic.
Four students, Aaron, Briana, Chris and David, have finished a group assignment and their teacher gives them 4 movie tickets as a reward. However, each ticket is for a different cinema.
The table below shows the distances between the student’s houses and the cinemas in kilometres:
| Cinema 1 | Cinema 2 | Cinema 3 | Cinema 4 | |
|---|---|---|---|---|
| Aaron | 19.8 | 11.4 | 2.2 | 11.7 |
| Briana | 7.4 | 3.1 | 19.6 | 12.5 |
| Chris | 23.8 | 9.7 | 15.7 | 25.7 |
| David | 3.2 | 6.1 | 5.5 | 15.3 |
Construct a network diagram that correctly displays this data.
They decide that Briana will go to Cinema 1, David will go to Cinema 2, Aaron will go to Cinema 3 and Chris will go to Cinema 4. Construct a network diagram that correctly displays this allocation.
Using this allocation, calculate the total distance that the students need to travel to use their cinema tickets.
A taxi service receives 4 requests for pick up at different locations in the city. There are 4 taxis available in the area which the operator can assign to pick up each of the passengers.
The table below shows how long it will take in minutes for the taxis to get to each of the passengers:
| Passenger 1 | Passenger 2 | Passenger 3 | Passenger 4 | |
|---|---|---|---|---|
| Taxi A | 38 | 16 | 19 | 12 |
| Taxi B | 17 | 24 | 27 | 30 |
| Taxi C | 31 | 16 | 38 | 33 |
| Taxi D | 49 | 11 | 12 | 30 |
Construct a network diagram that correctly displays this data.
The operator assigns Taxi A to pick up Passenger 4, Taxi B to pick up Passenger 1, Taxi C to pick up Passenger 3, and Taxi D to pick up Passenger 2. Construct a network diagram that correctly displays this allocation.
Using this allocation, calculate the total amount of time (in minutes) spent travelling to each of the passengers.
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) |
There are 5 tasks that urgently need to be completed by an IT department. The IT manager wants to assign these tasks to 5 of their employees so that they are finished as soon as possible.
The table below shows the amount of time each employee is expected to take to complete each task, in hours:
| Task 1 | Task 2 | Task 3 | Task 4 | Task 5 | |
|---|---|---|---|---|---|
| Person A | 9.5 | 1 | 9 | 4 | 5.5 |
| Person B | 8.5 | 3.5 | 3 | 2.5 | 5.5 |
| Person C | 2 | 7 | 7.5 | 8.5 | 3 |
| Person D | 4 | 7 | 8.5 | 3 | 4.5 |
| Person E | 8 | 7 | 6.5 | 5 | 9.5 |
Construct a network diagram that correctly displays this data.
The manager decides to assign Person A to Task 4, Person B to Task 3, Person C to Task 1, Person D to Task 5, and Person E to Task 2. Construct a network diagram that correctly displays this allocation.
Using this allocation, calculate the total amount of time spent on these tasks.
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.
Construct a table to display the shortest distance from each courier to each remaining store.
For each of the following cost tables:
Perform the first row and column reduction of the Hungarian algorithm to the table.
Give the final reduced table.
| A | B | C | |
|---|---|---|---|
| D | 10 | 16 | 11 |
| E | 11 | 15 | 18 |
| F | 15 | 10 | 8 |
| A_1 | A_2 | A_3 | A_4 | |
|---|---|---|---|---|
| B_1 | 28 | 34 | 33 | 29 |
| B_2 | 26 | 36 | 38 | 31 |
| B_3 | 21 | 26 | 28 | 34 |
| B_4 | 40 | 28 | 33 | 29 |
Consider the following cost table:
Draw the table, after the first row and column reduction of the Hungarian Algorithm has been performed.
| A | B | C | D | |
|---|---|---|---|---|
| E | 23 | 19 | 24 | 20 |
| F | 36 | 24 | 29 | 19 |
| G | 25 | 24 | 27 | 18 |
| H | 33 | 24 | 36 | 24 |
Assuming we cross out zeros using three lines in the following way, draw the final reduced table.
Consider the following cost table:
Find the reduced form of the corresponding matrix using the Hungarian algorithm.
| X_1 | X_2 | X_3 | X_4 | X_5 | |
|---|---|---|---|---|---|
| Y_1 | 122 | 160 | 180 | 110 | 191 |
| Y_2 | 155 | 157 | 170 | 170 | 150 |
| Y_3 | 133 | 145 | 162 | 151 | 170 |
| Y_4 | 139 | 171 | 150 | 143 | 200 |
| Y_5 | 150 | 154 | 170 | 160 | 198 |
In a sports tournament, a team of 3 athletes, A, B, C, need to complete 3 different types of heats, D, E, F, in the shortest time possible. The following table represents the average time (in minutes) of each athlete in each type of heat:
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.
Calculate the minimum total time of the competitions.
| Heat D | Heat E | Heat F | |
|---|---|---|---|
| Athlete A | 4 | 8 | 7 |
| Athlete B | 1 | 4 | 3 |
| Athlete C | 9 | 2 | 6 |
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:
| Perth | Adelaide | Darwin | Cairns | |
|---|---|---|---|---|
| Sydney | 370 | 170 | 270 | 220 |
| Melbourne | 320 | 120 | 290 | 250 |
| Canberra | 340 | 150 | 260 | 210 |
| Brisbane | 310 | 200 | 220 | 190 |
Using the Hungarian algorithm, construct an allocation that minimises travel costs.
Calculate the minimum travel cost possible.
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):
Using the Hungarian algorithm, construct bipartite graphs, which represents the allocations that results in the minimum cost.
Calculate the minimum cost of distribution.
| Store W | Store X | Store Y | Store Z | |
|---|---|---|---|---|
| Centre A | 5 | 1 | 2 | 4 |
| Centre B | 4 | 3 | 9 | 6 |
| Centre C | 6 | 4 | 5 | 7 |
| Centre D | 2 | 7 | 3 | 1 |
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:
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.
Calculate the minimum total distance traveled.
| Site 1 | Site 2 | Site 3 | Site 4 | Site 5 | |
|---|---|---|---|---|---|
| Crane 1 | 25 | 17 | 19 | 28 | 32 |
| Crane 2 | 16 | 22 | 19 | 34 | 28 |
| Crane 3 | 22 | 27 | 14 | 11 | 29 |
| Crane 4 | 20 | 26 | 11 | 18 | 25 |
| Crane 5 | 38 | 29 | 34 | 15 | 25 |
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:
Use the Hungarian algorithm to find the allocation which costs the least.
Calculate the minimum cost of travel.
| Car 1 | Car 2 | Car 3 | |
|---|---|---|---|
| Location 1 | 29 | 37 | 22 |
| Location 2 | 32 | 27 | 26 |
| Location 3 | 33 | 34 | 25 |
The council needs to assign 4 engineers to 4 projects. Each engineer supplied the council with their minimum cost for each project. The costs (in thousand dollars) are listed in the table:
If each engineer can only handle one project, and Project 4 has specifically requested Engineer 1, how should the council allocate the other engineers in order to get the minimum cost? Use the Hungarian algorithm to complete the allocation.
Calculate the minimum cost of all the projects.
| P_{1} | P_{2} | P_{3} | P_{4} | |
|---|---|---|---|---|
| E_{1} | 84 | 69 | 69 | 74 |
| E_{2} | 29 | 79 | 49 | 59 |
| E_{3} | 119 | 89 | 84 | 99 |
| E_{4} | 39 | 104 | 89 | 109 |
The fire department needs to dispatch 5 trucks from different buildings to 5 fire locations. The table shows the time (in minutes) for each fire truck to arrive at each fire location:
Use the Hungarian algorithm to determine the allocation which results in the fastest time.
Construct a network that represents the assignment for the minimised time.
| F_{1} | F_{2} | F_{3} | F_{4} | F_{5} | |
|---|---|---|---|---|---|
| T_{1} | 23 | 32 | 24 | 25 | 17 |
| T_{2} | 32 | 24 | 27 | 16 | 21 |
| T_{3} | 22 | 21 | 19 | 23 | 25 |
| T_{4} | 27 | 26 | 24 | 28 | 16 |
| T_{5} | 24 | 22 | 21 | 23 | 19 |
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:
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 cost?
Calculate the minimum cost of distribution.
Construct a network that represents the optimum assignment.
| J_{1} | J_{2} | J_{3} | J_{4} | |
|---|---|---|---|---|
| C_{1} | 23 | 28 | 25 | 31 |
| C_{2} | 18 | 21 | 26 | 20 |
| C_{3} | 22 | 20 | 24 | 27 |
| C_{4} | 28 | 26 | 27 | 27 |