Assignment 6: Network & Integer Models
Managerial Decision Making (DS 852)
Create one Excel file for the following two problems.
• Name your file “A6-LastnameFirstname”.
• Create two different sheets for each of the following problems (problem 1 and problem 2). Solve each
problem with binary constraints on all decision variables, and set the Integer Optimality to 0 (%) in the Solver
Parameters > Options dialogue. Make sure you name the related sheets for each problem and sequence the
sheets appropriately, so it can be found easily. E.g.: Model Problem1, 1 Way Table,
Problem 1. (3.5 pts.) Deadwood City is taking bids from six bus companies on eight routes that must be driven
each day in their sprawling school district. Each company (A–F) submits its bids (in $) for how much it will
charge the city to drive the routes during the school year. However, only company F bids on all eight routes, as
seen in the table below. Blank cells indicate that a company is not bidding on a particular route.
Company Route 1 Route 2 Route 3 Route 4 Route 5 Route 6 Route 7 Route 8
A 8500 7900 5500 4000
B 8000 8400 6500 3500 5100
C 5000 4500 5750 3800
D 8000 5000 7000 6700 4350
E 7500 6500 4250 6600 3000 3000
F 7250 6000 7600 4700 5900 4400 6000 4500
Deadwood City has to decide which company should be assigned to drive each of the eight routes. The city’s
objective is to minimize the total cost of covering all eight bus routes, subject to the following conditions.
1. If a company does not bid on a route, it cannot be assigned to that route.
2. Each company can be assigned to at most two routes.
3. One company must be assigned to each route, but not every company must be assigned to a route.
Formulate this as an assignment problem in standard (tabular) form, not in the alternative (list) form of the
transportation model. One easy way to deal with the situation where a company does not bid on a route is to
replace a blank cell with a really large bid that would never be selected by the cost minimization process.
1a) Which company should be assigned to each route, and what is the total cost of their bids?
1b) Suppose that routes 6 and 7 are so far apart that it is not economically feasible for one company to drive both
routes. What constraints must be added to the model so that no company is assigned both routes 6 and 7? Find
the new optimal solution. How much does it increase Deadwood City’s total costs?
Problem 2. (3.5 pts.) Using the 1,000-mile coverage criterion, expand the Western Airlines hub location model
(discussed in the lecture) to include two new cities: Tucson, AZ and Winnipeg, Canada. You can obtain air
(flight) mileage between the new and existing cities using the website of your choice. Use only whole numbers
in your mileage data (e.g., round 234.56 up to 235 miles).. Modify the model appropriately, assuming that Tucson
and Winnipeg, like all the other cities, are candidates for being hubs and must be covered by at least one hub.
What is the URL of the website you used to gather the air mileage data? Make sure you are finding air mileage
and not road mileage. NOT Nautical Miles either.
2a) What is the new optimal solution in terms of the number of hubs? What cities are covered by each hub?
2b) What’s the smallest coverage criterion (mile limit) for which 3 hubs still cover all the cities (i.e., at what mile
limit does the minimum number of hubs needed jump from 3 to 4 hubs)? Try to get within 10 miles of the exact
answer.