Dynamic Programming Problem: Kevin, the head of fire department of the city Rapi
ID: 3572798 • Letter: D
Question
Dynamic Programming Problem:
Kevin, the head of fire department of the city Rapid Brook, is determining the "optimal" allocation of fire stations to three city districts. Zero stations may be located in a district. The table below shows the relationship between the number of stations and the annual expected property damage based on statistical data. Differences among districts are due to population, construction materials, and so on. A budget constraint restrict the total number of stations to five. Determine the optimal allocation by dynamic programming. Could the problem be solved by linear programming? Why or why not?Explanation / Answer
a)
From the table it is clear that the property damage will be least at 1.1 when stations are divided as 2 for District 1, 0 for District 2, 3 for District 3.
b) The problem can be solved by linear programmming. We need to loop through all the possible number of stations that can be allocated to each district.
The equation will be f(1,x) + f(2,y) + f(3,z) where f is the function to extract the value from the table. where 0<=x<=3 , 0<=y<=3 & 0<=z<=3 and x+y+z=5.
5 4 3 2 1 0 (1,3) 1.1 (2,0,3) (2,3) 0.5 (2,3) 0.6 (1,3) 0.8 (0,3) 1.2 (0,2) (3,3) 0.3 0.7 1.0 1.5Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.