Answered step by step
Verified Expert Solution
Question
1 Approved Answer
5. Suppose that you are asked to locate police stations in Richardson. There are five possible locations {A, B, C, D, E} for stations
5. Suppose that you are asked to locate police stations in Richardson. There are five possible locations {A, B, C, D, E} for stations and six districts {1,2,3,4,5,6} to serve. A station in a given location can only serve districts in its vicinity. A station can serve several districts, but every district must be served by at least one station. The table below shows which station can serve which districts: Possible locations A B B C D E Districts served 1,3,5 2,5 3,4 1,3,4 2,6 Parts a,b and c are independent. a) Provide a formulation to minimize the number of police stations required to serve Richardson dis- tricts. b) Suppose that districts 1 and 4 are high crime areas; police can be called for a crime while inves- tigating another crime. Thus, we want to build redundancy by making sure that these districts are served by at least two stations. Modify the formulation of (a) accordingly. c) Suppose that none of the districts has to be served anymore. Further suppose that district i has 10,000i population, e.g. district 1 has 10,000, district 2 has 20,000, district 6 has 60,000 people. A for- mulation to open up exactly three police stations to serve the most of the population is needed. Your 12 co-worker has come up with the following formulation: Let y be 1 if there is a station at location 1, otherwise 0. Similarly define YB, YC, YD, YE. If YA = 1, districts 1, 3 and 5 will be served, or a population of 10,000+30,000+50,000=90,000 will be served. Similarly the number of people served with yB = 1, yc = 1, yD = 1 and y = 1 are 70,000, YD YE 70,000, 80,000 and 80,000. Thus, your co-worker suggests: - max 90,000yA +70,000 +70,000yc + 80,000yD+ 80,000YE Such that: YA+YB+yc+yD+YE = 3; YA, YB, YC, YD, YE = {0,1}. - Use your common sense to solve this simple formulation to find that in the optimal solution y = YD = YE = 1 and the objective indicates serving 250,000 people. But note that there are only 210,000 (=10,000+20,000+30,000+40,000+50,000+60,000) people in all the districts. Explain to your co-worker where the mistake is in the above formulation. d) Provide a correct formulation for the problem in c).
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started