Construct an adjacency matrix, with row and column titles in alphabetical order, 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:
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.
Construct four tables showing the possible allocations that would correspond to the following bipartite graph.
Construct three tables showing the possible allocations that would correspond to the following bipartite graph.
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) |
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 |
| 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 |
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) | |
|---|---|---|---|
| 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 displays the data in the table.
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.
Calculate the total cost of the picnic.
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.
Consider the following bipartite graph:
Find the minimum cost path(s) from each of the resources represented by vertices in the left hand side.
Find the minimum cost path to each of the tasks represented by vertices on the right hand side.
On this graph, show the optimum allocation.
State the optimum allocation.
Consider the following bipartite graph:
Find the minimum cost path(s) from each of the resources represented by vertices in the left hand side.
Update the edge weights to show the minimum cost path to each of the tasks represented by vertices on the right hand side.
Check for any 3 zero edges in a row to complete the next step to find the optimum allocation.
Select the edges on the reduced graph that make up the optimum allocation
State the optimum allocation.
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:
Draw the table, after the first row and column reduction of the Hungarian Algorithm has been performed.
Draw the final reduced table.
| 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:
Use the Hungarian Algorithm to draw the final reduced table.
Determine the best allocation for A, B, and C.
Use this optimum allocation and the original cost table to determine the minimum cost.
| A | B | C | |
|---|---|---|---|
| D | 10 | 16 | 11 |
| E | 11 | 15 | 18 |
| F | 15 | 10 | 8 |
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} | 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 |
The following matrix represents a cost network:
Use the Hungarian algorithm to determine the optimum allocation for the cost network.
Calculate the minimum cost for the network.
The following matrix represents a cost network:
Use the Hungarian algorithm to determine the optimum allocation for the cost network.
Calculate the minimum cost for the network.
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:
| Bicycle | Motorbike | Car | Truck | |
|---|---|---|---|---|
| Delivery 1 | 28 | 24 | 33 | 29 |
| Delivery 2 | 18 | 19 | 26 | 28 |
| Delivery 3 | 27 | 21 | 18 | 17 |
| Delivery 4 | 21 | 24 | 25 | 22 |
Use the Hungarian algorithm to allocate a vehicle to each delivery to minimise delivery time.
Calculate the minimum total delivery time.
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.
Use the Hungarian algorithm to allocate a worker to each item.
Calculate the minimum total time to manufacture one batch of all of the items.
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)}, Breaststroke \text{(BR)}, Butterfly \text{(BU)} and Freestyle \text{(FS)}.
Their average times, in seconds, for each stroke are shown in the network below:
Represent this data in a matrix in the given form:
Use the Hungarian algorithm to allocate a stroke to each swimmer.
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.
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)} |
Represent this data in a matrix with rows and columns in the same order as the table.
Use the Hungarian algorithm to find the optimum allocation of lifts to the waiting people.
Calculate the total number of floors that the lifts have to travel to collect all the waiting people.
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:
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 heats.
| Heat D | Heat E | Heat F | |
|---|---|---|---|
| Athlete A | 4 | 8 | 7 |
| Athlete B | 1 | 4 | 3 |
| Athlete C | 9 | 2 | 6 |
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:
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.
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 |
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 a bipartite graph which represents the allocation that minimises travel costs.
Calculate the minimum travel cost.
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 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:
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?
Determine the total 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 following 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 a minimised time.
Construct a network that represents this allocation.
| 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 costs?
Calculate the minimum cost of distribution.
Construct a network that represents the allocation from the part (a).
| 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 |
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 1 | Zone 2 | Zone 3 | |
|---|---|---|---|
| Ambulance 1 | 33 | 27 | 28 |
| Ambulance 2 | 26 | 36 | 35 |
| Ambulance 3 | 30 | 38 | 23 |
| Ambulance 4 | 28 | 37 | 25 |
Create a modified table that can be used with the Hungarian algorithm to determine the optimum allocation.
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.
Determine the expected response time for each ambulance when sent to the optimum allocated zone.
A construction company has four large bulldozer located at four different garages. The bulldozers are to be moved to two different construction sites. The following table shows the distances in kilometres between the bulldozers and the construction:
Interpret the meaning of the value of 55 in the table.
Which bulldozer is furthest away from site A?
Use the Hungarian algorithm to determine which bulldozer should go to which site to minimise the total distance travelled.
| Site A | Site B | Site C | Site D | |
|---|---|---|---|---|
| Bulldozer 1 | 90 | 75 | 75 | 80 |
| Bulldozer 2 | 35 | 50 | 55 | 65 |
| Bulldozer 3 | 125 | 95 | 90 | 105 |
| Bulldozer 4 | 45 | 95 | 110 | 115 |
Find the minimum distance travelled by the bulldozers to get them to their allocated sites.
Due to roadworks the distance for Bulldozer 2 to go to Site B increases by 15\text{ km}.
Use the hungarian algorithm to find a new assignment of bulldozers to sites which would minimise the total distance travelled.
Find the new minimum distance travelled.
Explain why the new minimum distance has not increased by the 15\text{ km} extra that it now takes for Bulldozer 2 to go to site B.
A school swimming team wants to select four swimmers for a relay team. The fastest times (in seconds) for the four best swimmers are shown in the table:
| Backstroke | Breaststroke | Butterfly | Freestyle | |
|---|---|---|---|---|
| Rob | 76 | 78 | 70 | 62 |
| Joel | 74 | 80 | 66 | 62 |
| Hank | 77 | 76 | 68 | 58 |
| Sunil | 78 | 80 | 66 | 60 |
Interpret the meaning of the 77 in the table.
Which stroke is the quickest to swim? Explain your answer.
Use the Hungarian algorithm to determine which swimmer should swim which stroke to give the team the best chance of winning the relay.
Find an estimate for the race time the team would achieve.
Due to an injury, Rob estimates that he will take an extra 15 seconds to swim the breaststroke. Use the Hungarian algorithm to find two new possible minimum assignments for the swimmers.
Estimate the new minimum time for the team's race.
Explain why the new minimum time is not 15 seconds longer than the original assignment.
Four employees have three tasks to complete. This means that one employee will not be assigned a task. The time taken for each employee to complete each task is shown in the table below:
Represent the data into a square matrix by adding a dummy column with rows and columns in the same order as the table.
| Task 1 | Task 2 | Task 3 | |
|---|---|---|---|
| Angela | 36 | 23 | 48 |
| Brad | 39 | 27 | 46 |
| Cody | 46 | 25 | 39 |
| Dawn | 43 | 30 | 40 |
Use the Hungarian algorithm to determine which employee should be allocated to which task in order to minimise the time taken.
The following matrix represents a cost network:
Use the Hungarian algorithm to determine the optimum allocation for the cost network.
The following matrix represents a cost network:
Use the Hungarian algorithm to determine the optimum allocation for the cost network.
Calculate the maximum cost for the network.
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 1 | Project 2 | Project 3 | Project 4 | |
|---|---|---|---|---|
| Engineer 1 | 30 | 47 | 37 | 36 |
| Engineer 2 | 28 | 32 | 48 | 44 |
| Engineer 3 | 22 | 24 | 50 | 44 |
| Engineer 4 | 44 | 45 | 41 | 41 |
Create a new table that will allow us to perform the allocation as a minimisation problem using the Hungarian algorithm.
Apply the Hungarian algorithm to reduce this table to help find the optimum allocation.
Determine the allocation which results in a minimised cost (loss of profit).
Determine the expected profit for each project with the optimum allocation.
Calculate the total profit that can be expected.
A manufacturing company has 4 machines with different production rates. The company wishes to produce the maximum number of parts each day.
| Machine 1 | Machine 2 | Machine 3 | Machine 4 | |
|---|---|---|---|---|
| Operator 1 | 120 | 240 | 120 | 560 |
| Operator 2 | 150 | 250 | 140 | 620 |
| Operator 3 | 110 | 220 | 100 | 610 |
| Operator 4 | 160 | 210 | 90 | 540 |
Create a new table that will allow us to perform the allocation as a minimisation problem using the Hungarian algorithm.
Apply the Hungarian algorithm to reduce this table to help find the optimum allocation.
Determine the allocation which results in a minimised cost (loss of production) for the reduced table.
Determine the expected number of parts by each operator with this allocation.
Calculate the total number of parts per day that can be expected.
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.
| Ravensthorpe | Port Hedland | Darwin | Kalgoorlie | |
|---|---|---|---|---|
| Engineer 1 | 360 | 160 | 260 | 210 |
| Engineer 2 | 310 | 110 | 280 | 140 |
| Engineer 3 | 330 | 140 | 250 | 200 |
Create a new table that will allow us to perform the allocation as a minimisation problem using the Hungarian algorithm.
Apply the Hungarian algorithm to the modified table to determine the allocation which results in a minimised cost (loss of earnings).
Determine the expected day rate for each Engineer with this allocation
Calculate the total consulting fees that can be expected.
Four prefects must lead four activities at camp:
Swimming (S)
Basketball (B)
Ropes course (R)
Canoeing (C)
The prefects are asked to rank the activities out of 10, where 10 means they really want to supervise the activity, and 1 means they do not want to. The matrix shows the results:
Transform the matrix to create an equivalent minimisation problem
Use the Hungarian algorithm to determine which prefect should supervise each activity to maximise the overall ranking.