Chapter 10 & 11 Problems
10-11 A group of college students is planning a camping trip during the upcoming break. The group must hike several miles through the woods to get to the campsite, and anything that is needed on this trip must be packed in a knapsack and carried to the campsite.
One particular student, Tina Shawl, has identified eight items that she would like to take on the trip, but the combined weight is too great to take all of them.
She has decided to rate the utility of each item on a scale of 1 to 100, with 100 being the most beneficial. Each item's weight in pounds and utility value are given below.
|
ITEM
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
|
WEIGHT
|
8
|
1
|
7
|
6
|
3
|
12
|
5
|
14
|
|
UTILITY
|
80
|
20
|
50
|
55
|
50
|
75
|
30
|
70
|
Recognizing that the hike to the campsite is a long one, a limit of 35 pounds has been set as the maximum total weight of the items to be carried.
- Formulate this as a 0-1 programming problem to maximize the total utility of the items carried. Solve this knapsack problem using a computer.
- Suppose item 3 is an extra battery pack, which may be used with several of the other items. Tina has decided that she will take item 5, a CD player, only if she also takes item 3. On the other hand, if she takes item 3, she may or may not take item 5. Modify the problem to reflect this, and solve the new problem.
10-13 An airline owns an aging fleet of Boeing 737 jet airplanes. It is considering a major purchase of up to 17 new Boeing model 787 and 767 jets. The decision must take into account numerous cost and capability factors, including the following:
(1) the airline can finance up to $1.6 billion in purchases;
(2) each Boeing 787 will cost $80 million, and each Boeing 767 will cost $110 million;
(3) at least one-third of the planes purchased should be the longer-range 787;
(4) the annual maintenance budget is to be no more than $8 million;
(5) the annual maintenance cost per 787 is estimated to be $800,000, and it is $500,000 for each 767; and
(6) each 787 can carry 125,000 passengers per year, whereas each 767 can fly 81,000 passengers annually.
Formulate this as an integer programming problem to maximize the annual passenger-carrying capability. What category of integer programming problem is this? Solve this problem.
10-20 The campaign manager for a politician who is running for reelection to a political office is planning the campaign. Four ways to advertise have been selected: TV ads, radio ads, billboards, and social media advertising buys. The costs of these are $900 for each TV ad, $500 for each radio ad, $600 for a billboard for 1 month, and $180 for each buy on social media (approximately 40,000 unique impressions).
The audience reached by each type of advertising has been estimated to be 40,000 for each TV ad, 32,000 for each radio ad, 34,000 for each billboard, and 17,000 for each social media buy. The total monthly advertising budget is $16,000. The following goals have been established and ranked:
1. The number of people reached should be at least 1,500,000.
2. The total monthly advertising budget should not be exceeded.
3. Together, the number of ads on either TV or radio should be at least 6.
4. No more than 10 ads/buys of any one type should be used.
a. Formulate this as a goal programming problem.
b. Solve this using computer software.
c. Which goals are exactly met and which are not?
11-19 The Laurenster Corporation needs to set up an assembly line to produce a new product. The following table describes the relationships among the activities that need to be completed for this product to be manufactured.
|
ACTIVITY
|
DAYS
|
IMMEDIATE PREDECESSORS
|
|
a
|
m
|
b
|
|
A
|
3
|
6
|
6
|
-
|
|
B
|
5
|
8
|
11
|
A
|
|
C
|
5
|
6
|
10
|
A
|
|
D
|
1
|
2
|
6
|
B, C
|
|
E
|
7
|
11
|
15
|
D
|
|
F
|
7
|
9
|
14
|
D
|
|
G
|
6
|
8
|
10
|
D
|
|
H
|
3
|
4
|
8
|
F, G
|
|
I
|
3
|
5
|
7
|
E, F, H
|
- Develop a project network for this problem.
- Determine the expected duration and variance for each activity.
- Determine the ES, EF, LS, LF, and slack time for each activity. Also determine the total project completion time and the critical path(s).
- Determine the probability that the project will be completed in 34 days or less.
- Determine the probability that the project will take longer than 29 days.
11-23 Tom Schriber, the director of personnel of Management Resources, Inc., is in the process of designing a program that its customers can use in the job-finding process. Some of the activities include preparing resumés, writing letters, making appointments to see prospective employers, and researching companies and industries. The information on these activities is shown in the following table:
|
ACTIVITY
|
DAYS
|
IMMEDIATE PREDECESSORS
|
|
a
|
m
|
b
|
|
A
|
8
|
10
|
12
|
-
|
|
B
|
6
|
7
|
9
|
-
|
|
C
|
3
|
3
|
4
|
-
|
|
D
|
10
|
20
|
30
|
A
|
|
E
|
6
|
7
|
8
|
C
|
|
F
|
9
|
10
|
11
|
B, D, E
|
|
G
|
6
|
7
|
10
|
B, D, E
|
|
H
|
14
|
15
|
16
|
F
|
|
I
|
10
|
11
|
13
|
F
|
|
J
|
6
|
7
|
8
|
G, H
|
|
K
|
4
|
7
|
8
|
I, J
|
|
L
|
1
|
2
|
4
|
G, H
|
- Construct a network for this problem.
- Determine the expected time and variance for each activity.
- Determine ES, EF, LS, LF, and slack time for each activity.
- Determine the critical path(s) and project completion time.
- Determine the probability that the project will be finished in 70 days or less.
- Determine the probability that the project will be finished in 80 days or less.
- Determine the probability that the project will be finished in 90 days or less.