212 CHAPTER 5 INTEGER PROGRAMMING

The following example problem demonstrates the model formulation and solution of a total integer -
Example Problem
programming problem.
Solution

The Problem Statement

A textbook publishing company has developed two new sales regions and is planning to transfer
some of its existing sales force into these two regions. The company has 10 salespeople available
for the transfer. Because of the different geographic configurations and the location of schools in
each region, the average annual expenses for a salesperson differ in the two regions; the average
is Slo,000 per salesperson in region 1 and $7,000 per salesperson in region 2. The total annual
expense budget for the new regions is $72,000. It is estimated that a salesperson in region 1 will
generate an average of $85,000 in sales each year, and a salesperson in region 2 will generate
$60,000 annually in sales. The company wants to know how many salespeople to transfer into
each region to maximize increased sales.
Formulate this problem and solve it by using QM for Windows.

Solution

Step 1: Formulate the Integer Programming Model

maximize Z = $85,00Ori + 60,00Or2

subject to
Jri + x2 = 10 salespeople

$10,000xi + 7,00Or2 s: $72,000 expense budget

Xi, X2 a 0 and integer

Step 2: Solve the Model Using QM for Windows

Problems

I. Solve problem 2 in Chapter 3 as an integer programlning model using the computer.

2. Solve problem 51 in Chapter 3 as an integer programming model using the computer.

3. Solve Problem 55 in Chapter 3 as an integer programmng model using the computer.

4. Solve Problem 59 in Chapter 3 as an integer programming model using the computer.

5. A tailor makes wool tweed sport coats and wool slacks. He is able to get a shipment of 150 square
yards of wool cloth from Scotland each month to make coats and slacks, and he has 200 hours of
 PROBLEMS 213

his own labor to make them each month. A coat requires 3 square yards of wool and 10 hours to
make, and a pair of slacks requires 5 square yards of wool and 4 hours to make. The tailor earns
$50 in profit from each coat he makes and $40 from each pair of slacks. He wants to know how
many coats and pairs of slacks to produce to maximize profit.
a. Formulate an integer linear programming model for this problem.
b. Determne the integer solution to this problem by using the computer. Compare this solution
with the solution without integer restnctions, and indicate whether the rounded-down solutictn
would have been optmal.

6. A jeweler and her apprentice make silver pins and necklaces by hand. Each week they have
80 hours of labor and 36 ounces of silver available. It requires 8 hours of labor and 2 ounces of
silver to make a pin and 10 hours of labor and 6 ounces of silver to make a necklace. Each pin
also contains a small gem of some kind. The demand for pins is no more than six per week. A pin
ears the jeweler $400 in profit, and a necklace earns S loo. The jeweler wants to know how many
of each item to make each week to maximize profit.
a. Formulate an integer programming model for this problem.
t). Solve this model by using the computer. Compare this solution with the solution with-
out integer restrictions, and indicate whether the rounded-down solution would have been
optimal.

7. A glassblower makes glass decanters and glass trays on a weekly basis. Each item requires 1 pound
of glass, and the glassblower has 15 pounds of glass available each week. A glass decanter requires
4 hours of labor, a glass tray requires only I hour of labor, and the glassblower works 25 hours
a week. The profit from a decanter is $50, and the profit from a tray is $10. The glassblower
wants to deterrmne the total number of decanters (x[) and trays ¢2) that he needs to produce to
maximize his profit.
a. Formulate an integer programming model for this prc>blem.
b. Solve this model by using the computer.

8. The Livewnght Medical Supphies Company has a total of 12 salespeople it wants to assign to
three regions~the South, the East, and the Midwest. A salesperson in the South earns $600 in
profit per month for the company, a salesperson in the East earns $540, and a salesperson in
the Midwest earns $375. The southern region can have a maximum assignment of five sales-
people. The company has a total of $750 per day available for expenses for all 12 salespeople.
A salesperson in the South has average expenses of $80 per day, a salesperson in the East has
average expenses of $70 per day, and a salesperson in the Midwest has average dally expenses
of $50. The company wants to determine the number of salespeople to assign to each region
to maximize profit.
a. Formulate an integer programming model for this problem.
b. Solve this model by using the computer.

9. Helen Holmes makes pottery by hand in her basement. She has 20 hours available each week to
make bowls and vases. A bowl requires 3 hours of labor, and a vase requires 2 hours of labor. It
requires 2 pounds of special clay to make a bowl and 5 pounds to produce a vase; she is able to
acquire 35 pounds of clay per week. Helen sells her bowls for $50 and her vases for $40. She wants
to know how many of each item to make each week to maximize her revenue.
a. Formulate an integer programming model for this problem.
b. Solve this model by using the computei.. Compare this solution with the solution without
integer restrictions, and indicate whether the rounded-down solution would have been optimal.

10. Lauren Moore has sold her business for $500,000 and wants to invest in condominium units
(which she intends to rent) and land (which she will lease to a farmer). She estimates that she
will receive an annual return of $8,000 for each condomiluum and $6,000 for each acre of land.
A condominium umt costs $70,000, and land costs $30,000 per acre. A condominium will cost
her $ 1,000 per unit, an acre of land will cost $2,000 for maintenance and upkeep, and $ 14,000
214 CHAPTER 5 INTEGER PROGRAMMING

has been budgeted for these armual expenses. Lauren wants to know how much to invest in con-
domiriums and land to maximize her annual return.
a. Formulate a mixed integer programming model for this problem.
b. Solve this model by using the computer.

11. The owner of the Consolidated Machine Shop has $10,000 available to purchase a lathe, a press,
a grinder, or some combination thereof. The following 0~1 integer linear progranming model
has been developed to determine which of the three machines (lathe, J¥i; press, x2: or grinder, j¥3)
should be purchased to maximize annual profit:

maximize Z = 1,00Ori + 70Or2 + 80Or3 (profit, S)

subject to

$5,ooor] + 6,ooor2 + 4,ooor3 = io,coo (cost, S)

Xi, X2, Jr3 = 0 or I

Solve this model by using the computer.

12. Northwoods Backpackers is a retail catalog store in Vermont that specializes in outdoor clothing and
camping equipment. Phone orders are taken each day by a large pool of computer operators, some
of whom are permanent and some temporary. A permanent operator can process an average of 76
orders per day, whereas a temporary operator can process an average of 53 orders per day. The com-
pany averages at least 6cO orders per day. The store has 10 computer workstations. A permanent
operator processes about 1.3 orders with errors each day, whereas a temporary operator averages
4. I orders with errors dally. The store wants to limit errors to 24 per day. A permanent operator is
paid $81 per day, including benefits, and a temporary operator is paid $50 per day. The company
wants to know the number of permanent and temporary operators to hire to lmmmize costs.

Formulate an integer programming model for this problem and solve it by using the computer.

13. In the example problem solution for this chapter on page 212, a textbook company was attempting
to deterlnine how many sales representatives to assign to each of two new regions. The company
has now decided that if any sales representatives are assigned to region I, a sales office must be
established there, at an annual cost of Sl 8,OcO. This altered problem is an example of a type of
integer programming problem known as a "fixed charge" problem.
a. Reformulate the integer prog[amming model to reflect this new cctndition.
b. Solve this new problem by using the computer.

14. The Texas Consolidated Electronics Company is contemplating a research and development pro-
gram encompassing eight research projects. The company is constrained from embarking on all
projects by the number c)f available management scientists (40) and the budget available for R&D
projects ($300,coo). Further, if project 2 is selected, project 5 must also be selected (but not vice
versa). Following are the resource requirements and the estimated profit for each project:

Expense Management Estimated profit

Project ($1,000s) Scientists Required ($1,OOO,000s)

1$60

2110

353

447 4 0.16

592 7 0.56
685 6 0.61

773

865
 PROBLEMS 215

Fomulate the integer programming model for this problem and solve it by using the computer.

15. Mazy's Department Store has decided to stay open for business on a 24-hour basis. The store
manger has divided the 24-hour day into six 4-hour periods and has determined the following
minimum personnel requirements for each period:

Personnel
"me Needed
Midnight4: 00 A.M. 90
4:Oong:oo A.M. 215
8:00 A.M.-Noon 250
NoonJ:00 p.M. 65
4:00-8:00 p.M. 3cO
8 : 00 p.M.-Midnight 125

Store personnel must report to work at the beginning of one of these time periods and
must work for 8 consecutive hours. The store manager wants to know the minimum number
of employees to assign to each 4-hour segment to minimize the total number of employees.
Formulate and solve this problem.

16. The athletic boosters club for Beaconville has planned a 2-day fund-raising drive to purchase
uniforms for all the local high schools and to improve facilities. Donations will be solicited during
the day and night by telephone and personal contact. The boosters club has arranged for local
college students to donate their time to solicit donations. The average donation from each type of
contact and the time for a volunteer to solicit each type of donation are as follows:

Average Interview Time

Average Donation (S) (min.)

Phone Personal Phone Personal

Day S16 $33 6 13

Night 17 37 7 19

The boosters club has gotten several businesses and car dealers to donate gasofine and cars
for the college students to use to make a maximum of 575 personal contacts dally during the fund-
raising drive. The college students will donate a total of 22 hours during the day and 43 hours at
night during the dnve.
The president of the boosters club wants to know how many diffelent types of donor contacts
to schedule dunng the dnve to maximize total donations. Fomulate and solve an integer program-
ming model for this problem. What is the difference in the total maximum value of donations
between the integer and noninteger rounded-down solutions to this problem?

17. The Metropofitan Alts Council (MAC) wants to advertise its upcoming season of plays, concerts,
and bullets. A television commercial that costs $25,000 will supposedly reach 53,000 potential
arts customers. The breakdown of the audience is as follows:

Age Mal e Female

= 35 12,OcO 20,000

< 35 7,000 14,OcO

216 CHAPTER 5 INTEGER PROGRAMMING

A newspaper ad costs $7,000, and the newspaper claims that its ads will reach an audience
of 30,000 potential arts customers, broken down as follows:

Ago Hal. Female

= 35 12,000 8,000
< 35 6,000 4,000

A radio ad costs $9,000, and it is estinated to reach an audienee of 41,000 arts customers,
with the following audience breakdown:

Age Mole Female

a 35 7,000 11,coo
< 35 10,000 13,000

The [Link] council has establ]shed several marketing guidelines. It wants to reach at least
200,000 potential arts customers. It believes older people are more likely to buy tickets than
younger people, so it wants to reach at least 1.5 times as many people over 35 as people under
35. The council also believes women are more likely to instigate ticket purchases to the arts than
men, so it wants its advertising audience to be at least 60 percent female.
a. Formulate and solve an integer progranming model for MAC to determine the number of ads
of each type it should use at the minimum cost.
b. Solve this model without integer restrictions, and compare the results.

18. Juan Hemandez, a Cuban athlete who visits the United States and Europe frequently, is allowed to
return with a limited number of consumer items not generally available in C`uba. The items, which
are camed in a duffel bag, cannot exceed a weight of 5 pounds. Once Juan is in Cuba, he sells the
items at highly inflated prices. The three most popular items in Cuba are denim jeans, CD players,
and CDs of U.S. rock groups. The weight and profit (in U.S. dollars) of each item are as follows:

ltom Weight (I b.) Profit

Denimjeans 2 $ 90
CD players 3 150

Compact discs I 30

Juan wants to deterlmne the combination of items he should pack in his duffel bag to maxi-
m]ze his profit. This problem is an example of a type of integer programming problem known as
a "knapsack" problem. Formulate and solve this problem.

19. The Avalon Floor Cleaner Company is trying to determine the number of salespeople it should
auocate to its three regions-the East, the Midwest, and the West. The company has 100 sales-
people that it wants to assign to the three regions. The annual average unit sales volume achieved
by a salesperson in each region is as follows:

unlts per
R®glon Salesperson
East 25 ,000
Midwest 18 ,000

West 31,000
 PROBLEMS 217

Because travel distances, costs of living, and other factors vary among the three regions, the
annual cost of having a salesperson is $5,000 in the East, Sl i,000 in the Midwest, and $7,000
in the West. The company has $700,000 budgeted for expenses. To ensure nationwide exposure
for its product, the company has decided that each region must have at least 10 salespeople. The
company wants to know how many salespeople to allocate to each region to maximize total aver-
age units sold. Formulate an integer progranming model for this problem, and solve it by using
the computer.

20. The Terraco Motor Company has produced a llghtweight, all-terrain vehicle code-named .`J99
Terra" for the military. The company is now planning to sell the Terra to the public. It has five
plants that manufacture the vehicle and four regional distnbution centers. The company is unsure
of public demand for the Terra, so it is considering reducing its fixed operating costs by closing
one or more plants, even though it would incur an increase in transportation costs. The relevant
costs for the problem are provided in the following table. The transportation costs are per thousand
vehicles shipped; for example, the cost of shipping 1,000 vehicles from plant I to warehouse C
is $32,000.

1tansportatlon Costs ($ 1,0006) to

Warehouse Annual
hoduction Annual Flxed
From plant A 8 C D Capac]ty operating costs
1 $56 $21 $32 $65 12.000 $2,100,000

18 46 7 35 18,000 850,000

12 71 41 52 14,000 1,800,000

30 24 61 28 10,000 1,loo,000

45 50 26 31 16,000 900,000

6,000 14,000 8 ,000 10,OcO

Formulate and solve an integer programming model for this problem to assist the company
in determining which plants should remain open and which should be closed and the number of
vehicles that should be shipped from each plant to each warehouse to miml"ze total cost.

21. The Otter Creek Winery produces three kinds of table wine-a blush, a white, and a red. The
winery has 30,000 pounds of grapes available to produce wine this season. A cask of blush
requires 360 pounds of grapes, a cask of white requires 375 pounds, and a cask of red requires
410 pounds. The winery has enough storage space in its aging room to store 67 casks of wine.
The winery has 2,200 hours c>f production capacity, and it requires 14 hours to produce a cask of
blush, 10 hours to produce a cask of white, and 18 hours to produce a cask of red. From records
of previous years. sales, the winery knows it will sell at least twice as much blush as red and at
least I.5 times as much white as blush. The profit for a cask c)f blush is $12,100, the proflt for
a cask of white is $8,700, and the profit for a cask of red is $10,500. The winery wants to know
the number of casks of each table wine to produce. Formulate and solve an integer programming
model for this problem.

22. Brenda Last, an undergraduate business major at State University, is attempting to determine her
course schedule for the fall semester. She is considering seven 3-credit-hour courses, which are
shown in the following table. Also included are the average number of hours she expects to have
to devote to each course each week ¢ased on information frc)in other students) and her m!.#[Link]
expected grade in each course, based on an analysis of the grading records of the teachers in each
course:
218 CHAPTER 5 INTEGER PROGF(AMMING

Course Average Hours per week Minimum Grade

Management I
Pnnciples of Accounting
Corporate Finance

Quantitative Methods 12D

Marketing Management
Java Programming
English Literature

An A in a course earns 4 quality credits per hour, a a earns 3 quality credits, a C earns 2
quality credits, a D earns I quality credit. and an F earns no quality credits per hour. Brenda wants
to select a schedule that will provide at least a 2.0 grade point average. To remaln a full-time stu-
dent, which she must do to continue receiving financial aid, she must take at least 12 credit hours.
Principles of Accounting, Corporate Finance, Quantitative Methods, and Java Programming all
require a lot of computing and mathematics, and Brenda would like to take no more than two of
these courses. To remaln on schedule and meet prerequisites, she needs to take at least three of
the following courses: Management I, Principles of Accounting, Java Programming, and English
Literature. Brenda wants to develop a course schedule that will minimize the number of hours
she has to work each week.
a. Fomulate a 0-1 integer programmng model for this problem.
b. Solve this model by using the computer. Indicate how many total hours Brenda should expect
to work on these courses each week and her mininum grade point average.

23. The artisans at Jewelry Junction in Phoemx are preparing to make goldjewelry during a 2-month
period for the Christmas season. They can make bracelets, necklaces, and pins. Each bracelet
requires 6.3 ounces of gold and 17 hours of labor, each necklace requires 3.9 ounces of gold and
10 hours of labor, and each pin requires 3 .1 ounces of gold and 7 hours of labor. Jewelry Junction
has avallable 125 ounces of gold and 320 hours of labor. A bracelet sells for Sl,650, a necklace
for $850, and a pin for $790. The store wants to know how many of each item to prc)duce to
maxii"ze revenue.
a. Formulate an integer programming model for this problem.
b. Solve this model by using the computer. Compare this solution with the solution with the
integer restnctions relaxed, and indicate whether the rounded-down solution would have been
Optimal.

24. Harry and Melissa Jacobson produce handcrafted furniture in a workshop on their farm. They
have obtained a load of 600 board feet of birch from a neighbor and are planning to produce round
kitchen tables and ladder-back chairs during the next 3 months. Each table will require 30 hours
of labor, each chair will require 18 hours, and between them they have a total of 480 hours of
labor available. A table requires 40 board feet of wood to make, and a chair requires 15 board
feet. A table earns the couple $575 in profit, and a chair earns $120 in profit. Most people who
buy a table also want four chairs to go with it, so for every table that is produced, at least four
chairs must also be made, although additional chalrs can also be sold separately. Formulate and
solve an integer programming model to determine the number of tables and chairs the Jacobsons
should make to maximize profit.

25. The Jacobsons in Problem 24 have been approached by a home fumishings company that needs
a wooden stool for its catalog. The company has asked the Jacobsons to produce a batch of 20
wooden stools, and the Jacobsons would realize a profit of $65 for each stool. A stool will require
4 board feet of wood and 5 hours to produce. Fomulate and solve an integer programning model
to help the Jacobsons determine whether they should also produce the stools.
 PROBLEMS 219

26. The Suntrek Company is a global apparel retailer with stores around the world. It manufactures
many of its clothing items in China and transports them by rail and truck to four ports on the
coast-Hong Kong, Shenzhen, Yangshen, and Qingdao-where they are loaded into shipping
containers for monthly shipment overseas to U.S. distributors. The company requires 25 total
containers and the available containers at each port, the monthly leasing cost per container, the
shipping time from each port to the United States, and the average percent damage historically
incurred at each port are shown in the following table.

Avai lable Contai ner Sh ippi ng Percent

Ports Contai hers Cost (S) Time (Days) Damage (%)

Hong Kong 9 270 25 2

Shenzhen 14 210 23 1.5

Yangshen 10 230 32 3

Qingdao 6 190 22 2

The company wants the average shipping tine per container to be 24 days or less and the average
percent damaged per container to be 2.5 percent or less. Formulate and solve an integer program-
ming model to determine the number of containers Suntrek should lease at each port to minimize
shipping costs.

27. Six Sigma is a well-recognized quality management system that employs inprovement projects
to improve business processes to reduce product and service defects, reduce costs, and increase
profits. Each project has a "champion" from upper management who is responsible for the proj-
ect's success. The project leader is known as a "black belt," and project team members are called
"green belts." Sinsun. a manufacturer of cell phone parts and components, has eight improvement

projects under consideration, and six champions, 10 black belts, and 25 green belts available to be
assigned to the projects. The following table shows for each of the projects the number of green
belts required, the percent reduction in defects expected, the cost savings (in S millions), and the
profit improvement (in S millions).

Green Dofect Cost Prof]t

Project Belts Reduction (%) Savings (S M) Improvements (S M)

1 3 0.97 I.32 1.9

2 4 i.35 I.16 2.3

3 7 I.16 0.95 3.6

4 2 0.82 0.88 2.7

5 6 1.02 1.05 4.I

6 5 0.86 1.26 3.8

7 4 1.15 1.13 5.3

8 6 0.96 0.85 4.8

The company wants to select the projects that will result in the greatest profit improvement while
achieving a defect reduction of at least 5 percent and cost savings of at least $6.3 million. Fomu-
late and solve an integer programming model for this problem.

28. The Skimmer Boat Company manufactures three kinds of molded fiberglass recreational boats-
a bass fishing boat, a ski boat, and a speedboat. The profit for a bass boat is $20,500, the profit
for a ski boat is $12,000, and the profit for a speedboat is $22,300. The company believes it will
220 CHAPTER 5 INTEGER PROGRAMMING

sell more bass boats than the other two boats combined but no more than twice as many. The ski
boat is its standard production model, and bass boats and speedboats are modifications. The com-
pany has production capacity to manufacture 210 standard (ski-type) boats; however, a bass boat
requires 1.3 times the standard prnduction capacity, and a speedboat requires 1.5 times the normal
production capacity. In addition, a bass boat uses one high-powered engine and a speedboat uses
two, and only 160 high-powered enSnes are available. The company wants to know how many
boats of each type to produce to maximize profit. Fomulate and solve an integer programming
model for this problem.

29. The Reliance Manufacturing Company produces an aircraft part. The company can produee the
part endrely at a flexible work center with multiple computerized machines. The company has four
work centers, all of which are different because they were purchased at different times. Each work
center has a single operator; however, the company' s operators have different skill levels, resulting
in different levels of daily output and product quafity. The following tables show the average daily
output and average number of defects per day for each of the company.s five operators who are
capable of producing the aircraft part:

Average Dally Output per Machine

Operator A a C D

1 18 20 21 17

2 19 15 22 18

3 20 20 17 19

4 24 21 16 23

5 22 19 21 21

Average Number of Defects Daily

per Machine
[Link] A 8 C D
1 0. 3 0.9 0.6 0.4

2 0.8 0.5 I.1 0.7

3 1.1 1.3 0.6 0.8

4 1.2 0.8 0.6 0.9

5 1.0 0.9 I.0 I.0

The company wants to determine which operator to assign to each machine to maximize daily
output and keep the percentage of defects to less than 4 percent.
a. a Fomulate a 0-I integer programming model for this problem.
b. b Solve this model by using the computer.

30. Corsouth Mortgage Associates is a large home mortgage fin in the Southeast. It has a pool
of permanent and temporary computer operators who process mortgage accounts, including
posting payments and updating escrow accounts for insurance and taxes. A permanent opera-
tor can process 220 accounts per day, and a temporary operator can process 140 accounts per
day. On average, the firm must process and update at least 6,300 accounts daily. The company
has 32 computer workstations available. Permanent and temporary operators work 8 hours
per day. A permanent operator averages about 0.4 error per day, whereas a temporary opera-
tor averages 0.9 error per day. The company wants to nmit errors to 15 per day. A permanent
operator is paid S120 per day, whereas a temporary operator is paid $75 per day. Corsouth
 PROBLEMS 221

wants to determine the number of permanent and temporary operators it needs to minimize
cost. Formulate and solve an integer programming model for this problem and compare this
solution to the noninteger solution.

31. In Problem 30, Corsouth Mortgage Associates is considering hiring some hourly, part-time com-
puter operators in addition to its permanent and temporary operators. A part-time operator can pro-
cess 12 accounts per hour, averages 0.16 error per hour, and is paid $4.50 per hour. Corsouth wants
to know the number of permanent and temporary employees it should use, plus the number Of
part-time hours it should arrange for. Fomulate and solve a mixed integer model for this problem.
32. Texmart is a locally owned "big-box" retail store chain in Texas with 75 stores, primarily located
in the Dallas-Fort Worth area. To compete with national big-box store chains, Texmart is plan-
ming to undertake several "sustainability" (i.e„ "green.') projects at its stores. The national chains
have been heavily publicizing their §ustamabifity efforts, including the reduction Of greenhouse
gas (GHG) emissions, which has had a positive effect on their sales. They have also demonstrated
that sustainability projects can have a positive impact on cost (especially energy) savings. The
projects Texmart is considering include installing solar panels at some or all of its stores; install-
ing small wind turbines; replacing some or all of its 165 tmcks with more fuel-efficient hybrid
tnicks; reducing waste, including recycling; and reducing plastic bags in their stores. The costs
for these projects, the resulting reduction in GHG emissions, the energy savings, and the annual
costs savings are shown in the following table:

Sustainable Projects

Solar Wind Shipping/ Waste/ Plastic

Power Power Vehicles Recycling Bags

Media/public relations score 3 2 I I 2

Cost 2,600,000 950,000 38,000 365,000 175,000
GHG reductions (metric
tons per year) 17,500 8,600 25 I,700 900
Cost savings (S) 220,000 125,000 26,OCH) 75,000 45,000

Energy savings (kwh) 400,000 150,000 34.000 l,2cO 55,000

Units 75 75 165 75 75

The media/public relations score in this table designates the importance of a particular project
relative to the other projects in generating public awareness and pubficity. For example, a score
of 3 indicates that the solar power project will have the greatest public impact. However, Tex-
marl believes if it undertakes a project, it will require a threshold number of projects to make an
impact~specifically, a solar power installation at 1 store or more, wind power projects in at least
3 stores, at least 10 new trucks, at least 2 waste/recycling store projects, and at least 6 stores with
plastic bag reduction projects. Texmart has budgeted $30 million for sustainable projects, and it
wants to achieve GHG emission reductions of at least 250,000 metnc tons per year; it wants to
achieve annual cost savings of at least $4 million; and it wants to achieve annual energy savings
of at least 5 miluon kilowatt hours 0(Wh), while maximizing the public relations impact of its
sustainability program. Develop and solve a unear programming model to help Texmart determine
how many projects of each type it should undertake.

33. In Problem 32, reformulate and solve the model so that Texmart maximizes its cost savings and
does not consider the media/public relations impact at all.

34. The Office of Homeland Security and the Centers for Disease Control and Prevention have
jointly mandated that cities and localities develop plans for establishing emergency command
222 CHAPTER 5 INTEGER PROGRAMMING

centers in multiple locations to dispense vaccines and antibiotics and provide security and
police coordination in the event of major emergency events, such as terrorist attacks, bio-
terrorism, and natural pandemics. These command centers must be located such that one is
within 15 minutes of every person in the general population. For cities with large popula-
tions and geographic areas, this could result in a large number of centers and create logistical
problems in setting them up quickly and staffing them. As such, cities would like to create
the minimum number of command centers possible. To determine where it should locate
its command centers, a city has divided its geographic area into four quadrants-northeast,
northwest, southeast, and southwest. Within each quadrant, it has established four sectors
with potential sites for command centers~A, 8, C, and D-usually where there is a suffi-
cient facility capable of housing a center and not necessarily centrally located. The potential
command center site in a sector is always within 15 minutes of the population in the other
three sectors in the quadrant and also within 15 minutes of the population in some sectors in
adjacent quadrants, as shown in the following table:

Sector Adjacent Quadrant sectors within 15 Mlnutes

1 . NE-A NW-A, SE-A

2. NE-B NW-A, NW-B
3. NE-C SE-A, SE-C
4. NE-D NW-A. NW-C, SE-B, SW-A
5. NW-A NE-A, NE-B, NE-D
6. NW-B
7. NW-C RE-D, SE-B
8. NW-D SW-B, SW-D
9. SE-A

10. SE-B NE-D, NW-C, SW-A, SW-C

11. SE-C NE-C, SW-C
12. SE-D SW-C, SW-D
13. SW-A NE-D, SE-B
14. SW-B

15. SW-C SE-B, SE-C, SE-D

16. SW-D NW-D, SE-D

Determine the locatlon of the minimum number of command centers for the city.

35. Tech offers a number of off-campus courses in its professional and executive masters of infer-
nation technology (MIT) programs at various locations around the state. The courses are
taught by a group of regular Tech information technology faculty and adjuncts they hire from
around the state. There are two main considerations in assigning individual faculty to courses:
the travel distance and the average course teaching evaluation scores from past years. The
college would like to minimize the mleage for teaching the courses not only for each faculty
member's benefit but also to reduce program expenses. It would also like to have the faculty
member who does the best job with a particular course teach that course. The following table
shows the mileage for each faculty member to each course location and his or her average
teaching evaluation scores (c)n a 5.00 scale, where "5" is outstanding and "1" is poor) for the
fall semester:
 PROD LE MS 223

Teacher
Course
(mileage/score) Abrahams Bray Clayton Dennis Evans Farah Gonzalez Hampton

MIT 125 35/4.10 35/4.63 71/4.55 35/4.43 119/3.78 215/4.21 35/4.93 94/4.06

MIT 225 74/4.05 74/3.7 8 95/4.61 74/4. 26 147/3.69 13 5/2.78 74/4.12 112/4.02

MIT 250 74/3.97 74/4.17 95/4.12 74/3.45 147/3.91 135/3.94 74/4.33 112/4.11

MIT 3cO 35/2.95 35/3.67 71/4.14 35/3.95 119/3.25 215/4.33 35/4.71 94/3.99

MIT 325 210/4.63 210/4.12 105/3.95 210/4.55 55/3.45 45/3.52 210/4.85 110/4.06

MIT 375 175/4.15 175/3.95 115/4.06 175/3.92 67/3.88 65/4.11 175/4.13 134/4.07

MIT 400 210/4.22 210/4.55 105/3.52 210/4.34 55/3.66 45/4.16 210/4.66 110/3.95

MIT 425 175/4.36 175/4.44 115/3.95 175/3.88 67/4.01 65/3.77 175/4.15 134/4.23

MIT 450 74/3.78 74/4.03 95/4.11 74/3.94 147/3.54 135/2.95 74/4.24 112/3.96

MIT 500 175/3.87 175/3.45 115/3.86 175/3.84 67/3.92 65/3.45 175/3.81 134/3.76

Formulate and solve a linear programming model that will assign all the faculty members such
that all courses are covered and each faculty member teaches at least one, but no more than two
courses. Explain your solution approach.

36. Rowntown Cab Company has 70 dnvers that it must schedule in three 8-hour shifts. However,
the demand for cabs in the metropolitan area varies dramatically according to the time of day.
The slowest period is between midnight and 4:00 A.M. The dispatcher receives few calls, and
the calls that are received have the smallest fares of the day. Very few people are going to the
airport at that time of night or taking other long-distance trips. It is estimated that a driver will
average $80 in fares during that period. The largest fares result from the airport runs in the
moming. Thus, the drivers who start their shift during the period from 4:00 A.M. to 8:00 A.M.
average $500 in total fares, and drivers who start at 8:00 A.M. average $420. Drivers who
start at noon average $300, and drivers who start at 4:00 p.M. average $270. Drivers who start
at the beginning of the 8:00 p.M. to midnight period earn an average of $210 in fares during
their 8-hour shift.

To retain customers and acquire new ones, Rowntown must maintain a high customer
service level. To do so, it has determined the minimum number of drivers it needs working
during every 4-hour time segment-10 from midnight to 4:00 A.M.,12 from 4:00 to 8:00 A.M.,
20 from 8:00 A.M. to noon, 25 from noon to 4:00 p.M., 32 from 4:00 to 8:00 p.M., and 18 from
8:00 p.M. to midmght.
a. Formulate and solve an integer programning model to help Rowntown Cab schedule its
dnvers.
b. If Rowntown has a maxinum of only 15 drivers who will work the late shift from midnight to
8:00 A.M., refomulate the model to reflect thLs complication, and solve it.
c. All the drivers like to work the day shift from 8:00 A.M. to 4:00 P.M., so the company has
decided to limit the number of drivers who work this 8-hour shift to 20. Reformulate the model
in (b) to reflect this restriction and solve it.

37. The bus company in Draper operates a "Weekend Rider" bus service from the Tech campus to
Washington, DC. The bus seats 55 passengers and selects the shortest route to DC that will also
result in at least 30 passengers. The bus can travel through 11 different cities and towns depend-
ing on the number of passengers it expects to attract. The following network shows the different
cormecting pickup points and the distance between them in miles:
224 CHAPTERS lNTEGERPROGRAMMING

The bus service expects to pick up the following passengers at each possible stop: 20 at stop I Crech),
4 at stop 2, 3 at stop 3, 5 at stop 4, 5 at stop 5, 7 at stop 6, 6 at stop 7, 4 at stop 8, 8 at stop 9, 6 at stop
10. 6 at stop 11, and 5 at stop 12. Determine the shortest route between Tech (at 1) to DC (at 13) that
will result in at least 30 passengers. Compare this route to the shortest route without the required
number of passengers, and indicate how many passengers the bus would have with this route.

38. "Wins above replacement," or WAR, is a complex statistical measure of a major league baseball
player's performance that sums up a player's total contribution to a team using various offensive
and defensive statistics. It reflects the number of additional wins a team has gained with a player
relative to the number of expected wins with a replacement-level player at a minirml cost. The
highest WAR measure for a player last season was 10.0. The Sox's general manager is evaluat-
ing 10 free agent players to possibly sign to contracts for next season. Following are the WAR
measures (from last season), contract demands, and ages of these players.

Contract s Contract
Pl ayer WAR (millions) Years Age

Mike Bass 4.6 2.I 1 25

Josh Donald, p 3.7 10.0 1 28

Miguel Gomez 5.9 17.4 2 31

Carlos cabrera 9.1 24.0 5 32

Matt carper, p 7.2 18.0 3 34
Evan Longier 4. 3 4.3 1 27

Paul Goldsulth 2.7 3.I 1 36

Jcey veto 5.2 16.5 3 29
Robinson canoe 8.1 24.0 6 28
Matt Fists, p 7.5 9.3 2 31

For those players bargailrmg for multiyear contracts, the dollar values are spread equally over the
years of the contract. The general manager has some specific guidelines for signing new players.
Donald, Carper, and Fists are pitchers, and the general manager wants to sign at least one pitcher.
He wants to limit the contracts' dollars for next season to $34 million, and the overall value of
the contracts to not exceed $55 million to remain under the league salary cap (and not be taxed
for exceeding the cap). He does not want the average contract length to exceed 2.5 years, and he
wants the average age of the players he signs to be 31 years or less.
Formulate and solve an integer programming model to determine which players the general
manager should sign to contracts to maximize the overall WAR of the players.
 PROBLEMS 2Z5

39. Globex Investment Capital Corporation owns six companies that have the following estimated
returns (in miluons of dollars) if sold in one of the next 3 years:

Year Sold
(estimated retu rn, $1,000,0005)

Company 1 2 3

1 S14 $18 $23

2 9 11 15

3 18 23 27

4 16 21 25

5 12 16 22

6 21 23 28

To operating funds, the company must sell at least $20 inillion worth of assets in year 1, $25
million in year 2. and $35 milhon in year 3. Globex wants to develop a plan for selling these
companies during the next 3 years to maximize return.
Fomulate an integer progranming model for this problem. and solve it by using the computer.

40. The Heartland Distribution Company is a food warehouse and distributor that has a contract with
a grocery store chain in several Midwest and Southeast cities. The company wants to construct
new warehouses/distribution centers in some of the cities it services to serve the stores in those
cities plus all the other stores in the other cities that don.t have distribution centers. A distribution
center can effectively service all stores within a 300-mile radius. The company also wants to limit
its fixed armual costs to under $900,000. The company wants to build the minimum number of
distribution centers possible.
The following table shows the cities within 300 miles of every city and the projected fixed
annual charge for a distnbution center in each city:

Annual Fixed Charge

City ($1,OO0s) Cities within 300 Miles

I. Atlanta $276 Atlanta, Chndotte, Nashville

2. Charlotte 25 3 Atlanta, Charlotte, Richmond
3. Cincinnati 394 Cincimati, Cleveland, IndianapoEs. Louisville,
Nashville, Pittsburgh
4. Cleveland 408 Cincirmati, Cleveland, Indianapous` Pittsburgh
5. Indianapofis 282 Cincirmati. Cleveland, IndianapoHs, Loui sville,
Nashville, St. Louis

6. Louisville 365 Cincinmti, Indianapolis, Louisville, Nashville,

St. Louis

7. Nashville 268 Atlanta, Cincinnati, Indianapoli s, Louisville,

Nashville, St. Louis

8. Pittsburgh 323 Cincinnati, Cleveland, Pittsburgh, RIchmond

9. Richmond 3 85 Charlotte, Pittsburgh, Richmond
10. St. Louis 298 Indianapolis, Louisville, Nashville, St. Louis

a. Formulate an integer programming model for this problem, and solve it by using the computer.
b. What is the solution if the cost constraint is removed from the original model fomulation?
What is the difference in cost?
226 CHAPTER 5 INTEGER PROGRAMMING

41 . The Kreeger Grocery Store chain has bought out a competing grocery store chain. However, it now
has too many stores in close proximty to each other in certain cities. In Roanoke the chain has 10
stores, and it does not want any stores closer than 2 miles to each other. Following are the monthly
revenues (S I,000s) from each store and a map showing the general proximity of the stores . Stores
within 2 miles of each other are circled.

Monthly
Store Reven ue ($1,000s)

1094

Develop and solve an integer programming

model to determine which stores the Kreeger
chain should keep open in Roanoke.

42. A youth soccer club has contracted with Holi-

day Helpers, a local travel agency, to broker hotel rooms for out-of-town teams that have entered
the club's Labor Day weekend soccer tournament. The agency has 12 teams, it needs to arrange
for rooms at 8 possible hotels. The following tables show the number of rooms each team needs,
the number of rooms available at each hotel, the room rate at each hotel, and the maximum room
rate each team wants to pay:

Max Rooms Room Rooms

Team Rate Needed Hotel Rate Availabl®
I. Arsenal A. Holiday $90
2. United 75 18 B. Roadside 75
3. Wildcats 60 20 C. Bates 55
4. Rage 80 12 D. Hampson 95
5. Rapids 110 17 E. Tilton 100
6. Storm 90 10 F. Marks 80
7. Tigers 70 18 G. Bayside 70
8. Stars H. Harnott 80
9. Comets 80 20
10. Hurncanes 65 16
11. Strikers 90 20
12. Bees 100 14

a. All of a tean's rooms must be at the same hotel. Formulate a model and develop a solution for
the agency to reserve rooms for as many teams as possible, according to their needs.
b. The travel agency has requested that each team Indicate three hotels it would prefer to stay at,
in order of priority, based on price, location, and facilities. The teams. preferences are shown
in the following table:
 PROBLEMS 227

Hotel
Priority 1 2 3 4 5 6 7 8 9 10 11 12

1CBCFDFCFHCAE
2GG-HEAGHF-HA
3-C-BAH-BB-FD

Determine a revised hotel room allocation to assign rooms to all teams while reflecting their
preferences to the greatest possible extent.

43. The Tech Software School contracts to train employees of companies in the use of various soft-
ware products and packages. The training programs are all delivered on three consecutive days
but require different daily durations, depending on the software product. For a specific 7-day
week (including weekends), the school has contrasted with eight different companies for training
sessions for different software products. The companies can send their employees to the Tech
training facihity only on certain days, as shown in the following table, with the hourly training
requirements per day:

Ea rl lest Latest
Company First Day Second Day Third Day Start Day Start Day

A46314
832513

C71125

D13625

E85235

F55515

G63335

H46634

The school has 20 staff-hours per day available for these training sessions.
a. Develop a/c¢s!.b/c traln]ng schedule for the eight companies.
b. Develop a/ec§I.b/a training schedule for the companies that will minimize the weekend training
hours (where the weekend includes days 6 and 7).

44. Each day Seacoast Food Services makes deliveries to four restaurants it supplies in the metro
Atlanta area. The service uses one truck that starts at its warehouse, makes a delivery to each
restaurant, and then ret`ms to the warehouse. The mileage between the warehouse, I, and each
of the restaurants, 2, 3, 4, and 5, i§ shown in the following table:

Location

Location 1 2 3 4 5

I - 10 15 20 40
2 10 - 12 16 24
3 15 12 - 10 20
4 20 16 10 - 16
5 40 24 20 16 -
228 CHAPTER 5 INTEGER PROGRAMMING

Fomulate and solve an integer programming model to determine the route (or tour) the truck -
should take to stan at the warehouse, visit each restaurant once, and return to the warehouse with
the minimum total distance traveled.

45. HTM Realty has a store front rental property in downtown Draperton, a small college town
next to the Tech campus. The property encompasses four business spaces that open onto Col-
lege Avenue. HTM has a long-ten tenant in each space, and their leases are all running out at
approximately the same time. HTM wants to significantly increase the rent for each space, and
the current tenants have all indicated that they win stay on at a slightly increased rent but not at
the rental price that HTM wants. HTM has shopped the spaces around and has gotten commit-
ments from four new tenants at the higher rent. However, HTM realizes that there is a very high
likelihood that the current tenants will remain in business and pay their rent for a new 3-year
lease, whereas there is a much smaller likelihood that the new tenants will be able to stay in
business and fulfill their lease payments. The following table shows the current and prospective
new tenants for each space, their monthly payments for a 3-year lease, and the probability that
each will remain in business:

Lease Lease
Space CurrentTenant Payment Probability NewTenant Payment Probability
A Doughnut shop $1,2cO .90 Sub shop $2,400 .50
a Jewelry store 800 .90 Dress shop 1,200 .70
C Music store I,000 .95 Restaurant 2,000 .40
D Gift & Card shop I,100 .95 TechLogo store 1,800 .60

HTM wants to lease each space to businesses that will rmximize their expected lease payments.
It also wants a ukehhood that at least three of the businesses will stay in business. Formulate and
solve an integer programming model for this problem.

46. The va//ey 7jmcs and War/d Iven/s pubush and deliver a moming newspaper 7 days a week. The
bundled papers are delivered by trucks to a number of area communities where they are picked
up by carriers at a central location in the community, who then deliver the individual newspapers
to customers along various predetermmed routes. The papers arrive at the central distnbution
location aLround 6 A.M., and they must be delivered by 8 A.M. The routes include homes, stores,
restaurants, and newspaper machines. Ooe community, Hanich Creek, has 10 routes, and six avail-
able paper camers, who have requested a delivery contract. The following table shows the time
(in minutes) required to deliver the newspapers along each route, the number of papers delivered
on each route, and the vehicle capacity (in number of papers) of each carrier:

Carrier A 8 C D E F

Vehicle capacity 600 720 450 510 660 550

Route 1 2 3 4 5 6 7 8 9 10

Time (mm.) 29 35 15 35 20 23 35 40 45 50
Papers delivered 200 240 Ilo 90 65 135 80 170 150 270

Fomulate and solve a linear integer programming model that will minimize the total number of
carriers needed to make the deliveries and that will determine which camer will be assigned each
route and the total number of papers delivered by each of the selected carriers.
 PROBLEMS 229

47. The BigRig Trucking Company participates in an Internet transportation exchange where
customers advertise their shipments including load weight and volume, and trip origin and
destination. BigRig then computes the cost and trme of the tnp and determines the bid it should
make for the shipment to achieve a certain profit level. Twelve customers have posted shipments
on the exchange, and BigRig has three trucks available for shipments. Each truck has a load
capacity of 80,000 pounds and 5,500 cubic feet and available driving tine of 90 hours. The fol-
lc)wing table shows the load parameters (i.e., weight in pounds and volume in cubic feet) for each
customer shipment and the profit BigRIg would realize from each shipment:

Customer Profit(S) Loudob.) Load(fl3) Time(hours)

20,000 44,000 I, 600 51
17,OcO 39,000 2,100 22
15 ,OcO 24,000 3,200 45
4 7,000 3 3 ,coo 3,700
5 18,000 18,000 4,400 110
6 12,000 21,000 2,900 105
7 5,000 15,000 1,loo 44
8 4,6cO 19,000 1, 600 56
9 1 I,OcO 23,000 800 60
10 6,200 [Link] I,800 25
11 14,OcO 55,000 3,700 37
12 9,000 45 ,000 2,900 41

Formulate and solve a l]near progranming model to detemine which customer shipments BigRIg
should bid on to maximize profit.

48. Twobucks Coffee Company currently operates 12 coffee shops in downtown Nashville. The com-
pany has been losing money and wants to downsize by closing some stores. Its policy has been to
saturate the downtown area with stores so that one is virtually always in the sight of a potential
or current customer. However, the company's new policy is to have enough stores so that each is
within 5 minutes' walking distance of another store. The company would also like to have annual
operating costs of no more than $900,000.
The following table shows the coffee shops within 5 minutes' walking distance of another
shop and the average annual cost of the existing stores:

Annual Average
Store Lacatlon Operatlng cost (i) Stores wlthEn 5 Mlnutos' Walking Distance
I. 3rd street 456 3rd street, Rose street
[Link] street 207 loth street, South street, Broad street
3. South [Link] 139 South street, Hill street,loth street
4. Mulberry Avenue 246 Mu lberry Avenue, Beamer Boulevard
5. Rose street 177 Rose street, 3rd street, Church street
6. Wisham Avenue 212 Wisham Avenue, Broad street, 23rd Avenue
7. Richmond Road 195 RIchmond Road, Broad street
8. Hill Street 170 Hill street, South street
9. 23rd Avenue 184 23rd Avenue, Wisham Avenue
10. Broad Street Broad Street, Wisham Avenue, R]chmond Road,
loth Street
1 I. Church Street Church Street, Rose Street, Beamer Boulevard
12. Beamer Boulevard Beamer Boulevard, MulbeiTy Avenue, Church
Street
230 CHAPTER5 lNTEGERPROGRAMMING

Formulate and solve a linear programming model that win select the minimum nuinber of stores -
the company will need to achieve its new poficy objechve.

49. The town of Hillsboro recently purchased a 55-acre tract of farm land, and it has $550,000 bud-
geted to develop recreational facilities. The impetus for the purchase was the need for more soccer
fields to meet the increasing demand of youth soccer in the area. However, once the land was
purchased,anumberofotherinterestgroupsbegantolobbythetowncounciltodevelopotherrec-
reational facifities including rugby, fcotball, softball, and baseball fields, plus walking and running
trails, a children`s playground, and a dog park. The following table shows the amount of acreage
required by each project, the annual expected usage for each facility, and the cost to construct
each facility. Also included is a priority desigmtion detemined by the town's recreation com-
mittee based on several public heanngs and their perceptions of the critical need of each facifity.

I:acility Annual usage (people) Acres Cost (S) Priority

Rugby fields 4,700 7 75 ,000 3

Football fields 12,500 12 180,000 2

Soccer fields 32,000 20 350,000 I

Dog park 7,500 6 45,000 3
Playground 41,000 3 120,000 2
Walking/rurming trails 47,000 25 80,000 1
Softball fields 2 3.000 5 115,000 2

Baseball fields 16,000 8 210,000 3

a. Formulate and solve a l]near prograniming model that will maximize annual usage and achieve
an average priority level of no more than I.75.
b. Refomulate the model such that the objective is to achieve the minimum average priority level
while achieving an annual usage of at least 120,000.
c. What combination of faciuties will use the maxinum acreage available without exceeding
the budget and achieving an average priority level of no more than 1.75? What is the annual
usage with these facilities?

PM COMPUTER SERVICES the operations, Paulette and Maureen help with all other
tasks, including sales and accounting.
They pay the students who work for them $8 per hour
P ulette Smith and Maureen Becker are seniors in engi- for a 40-hour week, or $1,280 per month. They hire stu-
neering and business, respectively, at State University. dents on a monthly basis, and their delivery schedule is
They have set up a company. PM Computer Services, to also on a monthly (i.e., end-of-the-month) basis. PM cur-
assemble and sell their own brand of personal computers. rently has flve employees. PM Computers has determined
They buy component parts on the open market from a vari- that each of its employees is able to produce 12.7 comput-
ety of sources in the United States and overseas, and they ers, on average, per month. When the monthly demand for
assemble their computers, mostly at night, in their three- its computers exceeds its regular production capacity, PM
bedroom apartment. They sell their computers primarily to employs limited overtime. Each computer produced on an
departments at State University and to other students. They overtime basis adds $12 to the labor cost of a computer.
hire other students to perform the assembly operations and A PM employee can produce 0.6 computer per month on
to test and package the computers. In addition to managing an overtime basis.