Throughout most of the discussion in this chapter related to the maximum covering model, we have implicitly assumed that all facilities have identical costs. In particular, it is that assumption that allowed us to limit the number of facilities that are located. In many contexts, however, construction costs differ depending on the location. In addition, there might be an explicit cost associated with not covering demands.
Let fj
be the cost of building a facility at candidate location j. Also, let B be the maximum amount that can be spent on building facilities. Finally, let
i, be a unit cost of not covering demands at demand node
(a) Formulate the problem of minimizing the combined cost of locating facilities and not covering demands. Clearly define any additional notation that you use. Also, clearly state the constraints and the objective function both mathematically and in words.
Note: You should not have a constraint like constraint (4.19) that limits the number of facilities to P. The optimal number of facilities will be determined endogenously by this model.
(b) Relax an appropriate constraint and formulate a Lagrangian problem related to the one you formulated in part (a). (You really should have only one candidate constraint to relax.)
(c) For fixed values of the Lagrange multipliers in the problem you formulated in part (b), clearly state how you would solve the Lagrangian optimization problem. In other words, how would you find the optimal values of the location variables, Xj, and the coverage variables, Zi?
(d) For fixed values of the Lagrange multipliers, how can you extract or construct a feasible solution to the problem of part (a) from the solution you obtained in part (c)? Note that there may well be more than one way to do this. Determining the “best” way is likely to require extensive computational experiments.