Linear Programming - Max Cover
DixieNet is an Internet service provider for residential customers in a southern state. The company is small now but plans to expand. Its first major goal is to establish a set of hubs throughout the state so that all residents of the state can access a hub via a local phone call. Local phone service is available between all pairs of adjacent counties in the state. Thus, if there is a hub in a given county, or in one of the adjacent counties, then residents of that county have the desired access.
County adjacencies are shown below. Values of 1 indicate counties that are adjacent to each other and values of 0 show counties that are not adjacent to each other. Each county is considered to be adjacent to itself.
|
County Adjacencies
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
|
1
|
1
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
2
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
3
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
4
|
0
|
0
|
1
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
|
5
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
|
6
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
|
7
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
|
8
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
|
9
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
0
|
|
10
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
|
11
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
|
12
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
|
13
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
|
14
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Popn
|
36,369
|
39,987
|
21,302
|
30,458
|
38,334
|
55,096
|
38,223
|
258,787
|
873,224
|
128,483
|
99,276
|
571,697
|
90,381
|
43,089
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Questions: Please use excel solver and also provide a "concise" algebraic formulation / narration)
a) Solve the Max Cover model for DixieNet with 1, 2 and 3 hubs.
b) DixieNet has decided to use sales representatives to generate sales at the grass roots level. Each sales rep will be assigned a primary county and a secondary county. The sales rep then travels within these 2 counties only. That way, once a sales rep is assigned a particular primary and secondary country, those populations are covered.
b) i) Assuming that you initially had 1 sales rep, which county would you assign him to (primary and secondary) in order to maximize population coverage? Develop a Greedy Heuristic for solving this.
b) ii) Suppose you had 2, 3, 4, or 5 sales reps. How would you assign them? Develop a Greedy Heuristic for solving this and also, the most concise Integer programming model to solve the problem optimally. Show the algebraic formulation and implement and solve it in excel.