Question 1: A real-estate development firm, Peterson and Johnson, is considering five possible development projects. Using units of millions of dollars, the following table shows the estimated long run profit (net present value) that each project would generate, as well as the amount of investment required to undertake the project.
|
Development Project
|
|
|
11
|
2
|
3
|
4
|
5
|
|
Estimated profit (millions)
|
$1
|
$1. 8
|
$1.640.
|
8
|
$1. 4
|
|
Capital required (millions)
|
(0I
|
12
|
10
|
4
|
8
|
The owners of the firm, Dave Peterson and Ron Johnson, have raised $20 million of investment capital for these projects. Dave and Ron now want to select the combination of projects that will maximize their total estimated long-run profit (net present value) without investing more than $20 million.
a. Formulate a BIP model in algebraic form for this problem.
b. Formulate and solve this model on a spreadsheet.
Question 2: Speedy Delivery provides two-day delivery service of large parcels across the United States. Each morning at each collection center, the parcels that have arrived overnight are loaded onto several trucks for delivery throughout the area. Since the competitive battlefield in this business is speed of delivery, the parcels are divided among the trucks according to their geographical destinations to minimize the average time needed to make the deliveries.
On this particular morning, the dispatcher for the Blue River Valley Collection Center, Sharon Lofton, Is hard at work. Her three drivers will be arriving in less than an hour to make the day's deliveries. There are nine parcels to be delivered, all at locations many miles apart. As usual, Sharon has loaded these locations into her computer. She is using her company's special software package. a decision support system called Dispatcher. The first thing Dispatcher does is use these locations to generate a considerable number of attractive possible routes for the Individual delivery trucks. These routes are shown in the table below (where the numbers in each column indicate the order of the deliveries), along with the estimated time required to traverse the route.
Dispatcher is an interactive system that shows these routes to Sharon for her approval or modification. (For example. the computer may not know that flooding has made a particular route infeasible) After Sharon approves these routes as attractive possibilities with reasonable time estimates, Dispatcher next formulates and solves a BIP model for selecting three routes that minimize their total time while including each delivery location on exactly one route.
|
Delivery Location
|
Attractive Possible Route
|
|
1
|
|
3
|
|
|
|
|
8
|
9
|
10
|
|
A
|
1
|
|
|
|
1
|
|
|
|
1
|
|
|
B
|
|
2
|
|
1
|
|
2
|
|
|
2
|
2
|
|
C
|
|
|
3
|
3
|
|
|
|
|
3
|
|
|
D
|
2
|
|
|
|
|
1
|
|
1
|
|
|
|
E
|
|
|
2
|
2
|
|
|
|
|
|
|
|
F
|
|
1
|
|
|
2
|
|
|
|
|
|
|
G
|
|
|
|
|
|
|
1
|
2
|
|
|
|
H
|
|
|
1
|
|
Col
|
|
|
|
|
I
|
|
I
|
|
|
|
4
|
|
|
2
|
|
|
|
|
Time (in hours)
|
LO
|
-1.
|
7
|
5
|
|
LO
|
|
3
|
7
|
6
|
a. Using the data in the table, demonstrate how Dispatcher can formulate and solve this BIP model on a spreadsheet.
b. Describe how the problem addressed in part a is analogous to the crew scheduling problem.
Question 3: An increasing number of Americans are moving to a warmer climate when they retire. To take advantage of this trend, Sunny Skies Unlimited is undertaking a major real-estate development project. The project is to develop a completely new retirement community (to be called Pilgrim Haven) that will cover several square miles. One of the decisions to be made is where to locate the two paramedic stations that have been allocated to the community to respond to medical emergencies. For planning purposes, Pilgrim Haven has been divided into five tracts, with no more than one paramedic station to be located in any given tract. Each station is to respond to all the medical emergencies that occur in the tract in which it is located as well as in the other tracts that are assigned to this station. Thus, the decisions to be made consist of (1) the tracts to receive a paramedic station and (2) the assignment of each of the other tracts to one of the paramedic stations. The objective is to minimize the overall average of the response times to medical emergencies.
The following table gives the average response time to a medical emergency in each tract (the rows) if that tract is served by a station in a given tract (the columns). The last column gives the forecasted average number of medical emergencies that will occur in each of the tracts per day.
|
|
Fire Station in
Tract
|
Average Frequency of -
Medical
Emergencies per Day
|
|
|
1
|
IN
|
M
|
it
|
It)
|
|
Response
|
1 5
|
20
|
15
|
'C)
CN
|
10
|
2
|
|
times (min.)
|
212
|
4
|
20
|
15
|
ID
CN
|
1
|
|
to a medical
|
3 30
|
15
|
6
|
LC)
N
|
15
|
3
|
|
emergency
|
4 20
|
10
|
15
|
4
|
12
|
1
|
|
in tract
|
515
|
U)
tN
|
12
|
10
|
5
|
3
|
Formulate and solve a BIP model on a spreadsheet for this problem. Identify any constraints that correspond to mutually exclusive alternatives or contingent decisions.
Question 4: Reconsider Question 2 the management of Sunny Skies Unlimited now has decided that the decision regarding the locations of the paramedic stations should be based mainly on costs.
The cost of locating a paramedic station in a tract is $200,000 for tract 1, $250,000 for tract 2, $400,000 for tract 3, $300,000 for tract 4, and $500,000 for tract 5. Management's objective now is to determine which tracts should receive a station to minimize the total cost of stations while ensuring that each tract has at least one station close enough to respond to a medical emergency in no more than 15 minutes (on the average). In contrast to the original problem, note that the total number of paramedic stations is no longer fixed. Furthermore, if a tract without a station has more than one station within 15 minutes, it is no longer necessary to assign this tract to just one of these stations.
a. Formulate the algebraic form of a pure BIP model with five binary variables for this problem.
b. Display and solve this model on a spreadsheet
Question 5:
a. What is a Binary Integer Problem?
b. What is meant by the term "contingent decision" in the context of a Binary Integer problem?
c. What is meant by the term "mutually exclusive alternatives" in the context of a Binary Integer problem?
d. Explain using an example: What is a set covering constraint?