Reference no: EM131656276

The Asheville School District is taking bids from six bus companies on eight routes that must be driven in the surrounding school district. Each company enters a bid on how much it will charge to drive the selected routes, although not all companies bid on all routes. The table below show the bids ($) by the companies on the routes (a blank cell indicates they did not bid on a route). The school district must decide which companies to assign to which routes with the understanding that a company cannot be assigned to a route it did not bid on and only one company can be assigned to a route. In this situation, since there are more routes than companies bidding on routes, the school district will all a company to be assigned to at most two routes. Company Route 1 Route 3 Route 3 Route 4 Route 5 Route 6 Route 7 Route 8 Alpha 4100 3500 2700 3250 2000 Bravo 3900 4100 3200 1700 2500 Charlie 2400 3000 2200 2800 1800 Delta 4000 2500 3400 3400 2100 Echo 3600 3200 2000 3200 1400 1500 Foxtrot 3500 2900 3700 2300 2800 3000 2100 Formulate this problem in Excel and solve to determine the minimum total costs required to cover all routes. (Hint: the “supply” of the companies can be at most 2; to prevent assigning bids to companies that didn’t provide bids you can always use artificially high bid amounts to prevent the assignment or not select those cells when selecting decision variables in Solver) a) Not counting the non-negativity constraint - how many constraints does this problem have? b) What is the minimum cost required to have all routes assigned and no company assigned to more than two routes?