Based on Denardo et al XXXXXXXXXXThree 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...

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 t_ij
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, 6t₁₁
+ 4t₁₂; fire 2, 7t₂₁
+ 3t₂₂; fire 3, 9t₃₁
+ 8t₃₂
+ 5t₃₃. 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 4t₁₁
+ 6t₁₂?