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_66.xlsx.

a. Determine how to minimize the cost associated with assigning the fire engines. (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₁₂?