A certain community wishes to place fire stations around the community which has
ID: 3221461 • Letter: A
Question
A certain community wishes to place fire stations around the community which has been divided into five districts: A, B, C, D, and E. However, the community wishes to place the fire stations in such a way so that the response time to any one of the districts is 9 minutes or less and in such a way as to minimize the cost. Below are the response times (in minutes) and the cost (in millions of dollars) for each station. Create a spreadsheet that assigns (ire stations to districts, meets the required response time, and minimized the cost. Enter the minimum cost (in millions of dollars) below. Answer.Explanation / Answer
This example is to be solved by using Hungarian Method of Assignment
The Hungarian algorithm consists of the four steps below. The first two steps are executed once, while Steps 3 and 4 are repeated until an optimal assignment is found. The input of the algorithm is an n by n square matrix with only nonnegative elements.
Step 1: Subtract row minima
For each row, find the lowest element and subtract it from each element in that row.
Step 2: Subtract column minima
Similarly, for each column, find the lowest element and subtract it from each element in that column.
Step 3: Cover all zeros with a minimum number of lines
Cover all zeros in the resulting matrix using a minimum number of horizontal and vertical lines. If nlines are required, an optimal assignment exists among the zeros. The algorithm stops.
If less than n lines are required, continue with Step 4.
Step 4: Create additional zeros
Find the smallest element (call it k) that is not covered by a line in Step 3. Subtract k from all uncovered elements, and add k to all elements that are covered twice.
This is the original cost matrix:
1.6
11.9
14.2
6.8
7.3
11.9
2.6
15.1
14.6
14.7
14.2
15.1
2.3
8.2
9.6
6.8
14.6
8.2
2.5
6.4
7.3
14.7
9.6
6.4
2.0
We subtract the row minimum from each row:
0.0
10.3
12.6
5.2
5.7
(-1.6)
9.3
0.0
12.5
12.0
12.1
(-2.6)
11.9
12.8
0.0
5.9
7.3
(-2.3)
4.3
12.1
5.7
0.0
3.9
(-2.5)
5.3
12.7
7.6
4.4
0.0
(-2)
Cover all zeros with a minimum number of lines
There are 5 lines required to cover all zeros:
0.0
10.3
12.6
5.2
5.7
x
9.3
0.0
12.5
12.0
12.1
x
11.9
12.8
0.0
5.9
7.3
x
4.3
12.1
5.7
0.0
3.9
x
5.3
12.7
7.6
4.4
0.0
x
The optimal assignment
Because there are 5 lines required, the zeros cover an optimal assignment:
0.0
10.3
12.6
5.2
5.7
9.3
0.0
12.5
12.0
12.1
11.9
12.8
0.0
5.9
7.3
4.3
12.1
5.7
0.0
3.9
5.3
12.7
7.6
4.4
0.0
This corresponds to the following optimal assignment in the original cost matrix:
1.6
11.9
14.2
6.8
7.3
11.9
2.6
15.1
14.6
14.7
14.2
15.1
2.3
8.2
9.6
6.8
14.6
8.2
2.5
6.4
7.3
14.7
9.6
6.4
2.0
Minimum cost = 1.6*2.1 + 2.6*5.9 + 2.3*5.4 + 2.5*4.1 + 2.0*4.8 =50.97 million dollars
1.6
11.9
14.2
6.8
7.3
11.9
2.6
15.1
14.6
14.7
14.2
15.1
2.3
8.2
9.6
6.8
14.6
8.2
2.5
6.4
7.3
14.7
9.6
6.4
2.0
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.