The Washington State legislature is trying to decide on locations at which to base search-and-rescue teams.The teams are expensive,so the legislature would like as few as possible while still providing the desired level of service.In particular,since response time is critical,the legislature would like every county to either have a team located in that county or in an adjacent county.Formulate and solve a BIP model in a spreadsheet to determine where the teams should be located.

Question

Quizplus · Accepted Answer

The Answer is This is a set covering problem.The decisions to be made are whether to locate a team in each county.The requirement for each county is that there be a team nearby,where nearby is defined as in that county or an adjacent county.The data for this problem are the coverage data.In particular,in the row representing each county,there is a 1 in every column that would satisfy the coverage of the row's county if there were a team there.For example,Clallum county would be covered if there is a team in either Clallum or Jefferson county.

This is a set covering problem.The decisions to be made are whether to locate a team in each county.The requirement for each county is that there be a team nearby,where nearby is defined as in that county or an adjacent county.The data for this problem are the coverage data.In particular,in the row representing each county,there is a 1 in every column that would satisfy the coverage of the row's county if there were a team there.For example,Clallum county would be covered if there is a team in either Clallum or Jefferson county. The decisions to be made in this problem are whether or not to place a team in each county.Thus,a binary variable is defined for each county in the changing cells Team? (D44:AN44).The values in Team? (D44:AN44)will eventually be determined by Solver.For now,arbitrary values are entered.The goal is to minimize the total number of teams.Thus,the objective cell should calculate this total: Total Teams = SUM(Teams?).This formula is entered into TotalTeams (AQ44). The functional constraints in this problem are that each county must have at least one team nearby.Given Teams? (D44:AN44),we calculate the number of teams nearby in TeamsNearby(AO5:AO41).For Clallum county,this will be =SUMPRODUCT(D5:AN5,Team?).Using a range name or an absolute reference for Team?,this formula can be copied into cells AO6:AO41 to calculate the number of teams nearby for the other counties.The TeamsNearby (AO5:AO41)must be >= 1,as indicated by the >= in AP5:AP41. The Solver information and solved spreadsheet are shown below. Thus,they should locate a team in Jefferson,King,Lewis,Clark,Okanagan,Blanton,Spokane,and Whitman counties,for a total of 8 teams.(There are multiple optimal solutions for this problem.)

The decisions to be made in this problem are whether or not to place a team in each county.Thus,a binary variable is defined for each county in the changing cells Team? (D44:AN44).The values in Team? (D44:AN44)will eventually be determined by Solver.For now,arbitrary values are entered.The goal is to minimize the total number of teams.Thus,the objective cell should calculate this total: Total Teams = SUM(Teams?).This formula is entered into TotalTeams (AQ44).

The functional constraints in this problem are that each county must have at least one team nearby.Given Teams? (D44:AN44),we calculate the number of teams nearby in TeamsNearby(AO5:AO41).For Clallum county,this will be =SUMPRODUCT(D5:AN5,Team?).Using a range name or an absolute reference for Team?,this formula can be copied into cells AO6:AO41 to calculate the number of teams nearby for the other counties.The TeamsNearby (AO5:AO41)must be >= 1,as indicated by the >= in AP5:AP41.

The Solver information and solved spreadsheet are shown below.

Thus,they should locate a team in Jefferson,King,Lewis,Clark,Okanagan,Blanton,Spokane,and Whitman counties,for a total of 8 teams.(There are multiple optimal solutions for this problem.)

The Washington State Legislature Is Trying to Decide on Locations