The city of Spring View is taking bids from six bus companies on the eight routes that must be driven in the surrounding school district. Each company enters a bid of how much it will charge to drive...

The city of Spring View is taking bids from six bus companies on the eight routes that must be driven in the surrounding school district. Each company enters a bid of how much it will charge to drive selected routes, although not all companies bid on all routes. The data are listed in Table 5.5. (If a company does not bid on a route, the corresponding entry is blank.) The city must decide which companies to assign to which routes with the specifications that (1) if a company does not bid on a route, it cannot be assigned to that route; (2) exactly one company must be assigned to each route; and (3) a company can be assigned to at most two routes. The objective is to minimize the total cost of covering all routes.

Objective To use a network model to assign companies to bus routes so that each route is covered at minimum cost to the city and no company is assigned to more than two routes.