Based on Denardo et al. (1988). Three fires have just broken out in New York. Fires 1 and 2 each require two fire engines, and fire 3 requires three fire engines.

The “cost” of responding to each fire depends on the time at which the fire engines arrive. Let tij be the time in minutes when the engine j arrives at fire i (if it is dispatched to that location). Then the cost of responding to each fire is as follows: fire 1, 6t11 4t12; fire 2, 7t21 3t22; fire 3, 9t31 8t32 5t33. There are three fire companies that can respond to the three fires.

Company 1 has three engines available, and companies 2 and 3 each have two engines available. The time (in minutes) it takes an engine to travel from each company to each fire is shown in the file P05_85.xlsx.

a. Determine how to minimize the cost associated with assigning the fire engines. (Hint: A network with seven destination nodes is necessary.)

b. Would the formulation in part a still be valid if the cost of fire 1 were 4t11 6t12?
Modeling Problems