Baker K.R. Optimization Modeling with Spreadsheets
Подождите немного. Документ загружается.
San
Antonio Phoenix
Los
Angeles Seattle Detroit Atlanta New York Boston Philadelphia
San Antonio 0 602 1376 1780 1262 935 1848 2000 1668
Phoenix 602 0 851 1193 1321 1290 2065 2201 1891
Los Angeles 1376 851 0 971 2088 2140 2870 2995 2702
Seattle 1780 1193 971 0 1834 2178 2620 2707 2486
Detroit 1262 1321 2088 1834 0 655 801 912 654
Atlanta 935 1290 2140 2178 655 0 940 1096 765
New York 1848 2065 2870 2620 801 940 0 156 180
Boston 2000 2201 2995 2707 912 1096 156 0 333
Philadelphia 1668 1891 2702 2486 654 765 180 333 0
(a) What is the minimum value of the trip’s longest leg?
(b) What is the optimal tour?
9.8. Optimizing Capacity Pelham Power Company (PPC) uses a system of boilers and tur-
bines to produce power. PPC owns five boilers. If a given boiler is operated, it can produce
steam within an output range given in the following table. Quantities are shown in tons.
The cost per ton of producing steam is also shown in the table.
Boiler 1 2 3 4 5
Min. 300 325 350 355 375 tons of steam
Max. 800 820 840 920 960 tons of steam
Cost 2.20 2.35 2.50 2.65 2.80 dollars per ton
of steam
Steam from the boilers is used by the turbines to produce power. PPC owns four tur-
bines. If a given turbine is operated, it can produce power from steam at the rate given in
the following table. The amount of steam each turbine can accommodate is also shown in
the table, along with the maximum and minimum of its input range (in tons of steam). The
cost of producing power is also shown in the table.
Turbine 1 2 3 4
Rate 4.00 4.50 5.00 5.50 kwh per ton of steam
Min. 420 450 480 510 tons of steam
Max. 825 875 925 975 tons of steam
Cost 2.15 2.50 2.75 2.95 dollars per ton of steam
What is the minimum cost of deploying boilers and turbines to produce 10,000 kwh
of power at PPC?
9.9. Balancing Workloads Over the next six weeks, an insurance company needs to send
more than 1.75 million pieces of marketing literature to customers in 16 states. In order to
coordinate with other marketing efforts, all the mailings for a given state must go out the
same week (i.e., if mailings for Georgia are sent in week 2, then all 136,562 pieces of mail
for Georgia must be sent that week). The operations manager would like to minimize the
largest amount of mail processed in any given week during the four-week campaign. The
required volumes are shown below.
366 Chapter 9 Heuristic Solutions with the Evolutionary Solver
State Volume
AZ 82,380
CA 212,954
CT 63,796
GA 136,562
IL 296,479
MA 99,070
ME 38,848
MN 86,207
MT 33,309
NC 170,997
NJ 104,974
NV 29,608
OH 260,858
OR 63,605
TX 214,076
VA 134,692
(a) Determine which states should be assigned for processing each week in order to
achieve the desired objective.
(b) What is the largest amount of mail processed in any given week?
9.10. Scheduling Power Plants During the next 8 months, Metropolis Power Company fore-
casts the demands shown below (measured in thousands of kwh).
Month 1 2 3 4 5 6 7 8
Demand 96 154 148 77 84 92 119 126
The power will be supplied from the four generating facilities, GF1 –GF4. The facilities
are each characterized by a generating capacity, a monthly operating cost, a startup cost,
and a shutdown cost. These are each shown in thousands of dollars in the table below.
When a generator is in operation, it provides service at its full capacity, even if that
exceeds demand. No operating cost is saved by partial (rather than full) use of a genera-
tor’s capacity. At the beginning of each month, it is possible to shut down any of the facili-
ties that have been operating or to start up any of the facilities that have been idle, with the
cost implications indicated in the table.
Facility Capacity Cost Startup Shutdown
GF1 70 8 4 3
GF2 60 7 3 2
GF3 50 6 3 2
GF4 40 5 2 3
At the start of month 1, facilities GF1 and GF2 are in operation.
What is the minimum total cost of providing the power demanded?
Exercises
367
9.11. Team Assignment A new class of 15 students has been admitted to the graduate Film
Studies program at the State University. During much of the first year, these students will
be working on teams, producing short films. The program director wants to assign stu-
dents to teams so that the teams are as diverse as possible. There will be three teams of
five students each.
Diversity is measured based on four characteristics or factors: undergraduate film
major (1 if yes, 0 if no), previous employment in the film industry (1 if yes, 0 if no), inter-
est in documentaries (1 if so, 0 otherwise), and gender (1 if female, 0 if male). Thus, each
student is represented by four factor ratings.
Student UG Emp Int Feml
10000
20110
31011
41000
50110
60011
71000
80010
90011
10 0 1 0 0
11 1 1 1 0
12 0 0 1 0
13 1 0 0 1
14 1 0 1 0
15 0 1 0 0
Total 6 5 9 4
Average 2.00 1.67 3.00 1.33
For a given factor j, team i has a factor rating (c
i,j
for factor j) equal to the total
number of 1s among its team members. The challenge is to convert a profile of factor
ratings into a quantitative measure of diversity. A specific diversity measure has been
adopted, based on the principle that if the teams “resemble” each other, then the
makeup of the teams must be diverse. The calculation is made as follows. Find the average
factor rating per team. (This figure can be computed from the raw data, as shown in the
table.) For each group, calculate the absolute deviation between its rating and the average
factor rating on the same factor. Sum the four deviations to get the group value. Sum the
three group values to get a total. Minimize the total. This measure would have a value of
zero if the teams resembled each other perfectly. In symbols, the diversity measure is
z ¼
X
3
i¼1
X
4
j¼1
jc
i, j
c
j
j
Find the assignment of students to teams that minimizes the diversity measure z.
368 Chapter 9 Heuristic Solutions with the Evolutionary Solver
9.12. Making Car Assignments You are organizing rides for a group of campers going on an
all-day, off-site trip. You have lined up some drivers, and your problem, essentially, is to
assign campers to drivers. The drivers, and the capacities of their cars, are provided in the
following table.
Driver Capacity
Saul 5
Chris 4
Rob 3
Erick 5
Anna 6
Jim 5
The campers represent different age groups. Each age group is to be delivered to a
different location. Thus, if a car holds campers of different ages, then the driver will
have to drive to different destinations. An ideal solution would require each driver to
go to just one location. However, such a solution is unattainable. The campers and
their age groups are listed in the table below.
Group Camper Group Camper
Age 7 George Age 9 Eric
Marcia Scott
Steve Sarah
Andrew Gretchen
Brian Jamie
Suzanne Liz
Age 8 Lisa Age 10 Patty
Ben Francesca
Tommy Adrian
Vanessa Ali
Alberto Cliff
Jason Mickey
Sean Matt
Although we know what an “ideal” solution would look like, we need a metric for
evaluating less-than-ideal solutions. One suitable metric is the total number of delivery
stops. Find the minimal number of stops and the assignment of campers to cars that
achieves it.
Exercises
369
Case: Colgate Wave (Abridged)
Introduction
In 1996, Colgate-Palmolive was trying to maintain its market presence in the tooth-
brush category, with three strong brands spanning the price spectrum. Colgate
Classic was the company’s low-priced brand, Colgate Plus was a mid-priced, pre-
mium brand, and Colgate Total represented the company’s most recent entry (three
years earlier) into the super-premium segment. There were several competitors in
each of these three market segments, but Colgate had been the market leader, with
a total share of about 24 percent in 1995, followed by Gillette (Oral B) and Procter
& Gamble (Crest) with 18 percent and 16 percent, respectively. By 1996, however,
Colgate’s market share was slipping in the face of dual pressures: low prices from
private-label brands and new entries from competitors in the premium/super-premium
sector.
The company was closely monitoring its market share in the super-premium
and premium segments. These segments not only provided higher dollar margins
than the lower segment, but they were also expected to expand as consumers
became more conscious of oral hygiene. Therefore, Colgate had been planning to
introduce a new super-premium toothbrush named Wave. Exhibit 9.1 provides a
concept description of the Wave toothbrush. Colgate had conducted a concept test
for the product, and the results had been quite promising.
The company also felt it was important to preserve its product portfolio share in
the premium and super-premium segments. Informally, Colgate’s rule of thumb was
that the market share of each brand in these two segments had to exceed 4 percent
because experience showed that distribution drops off exponentially at lower market
shares.
At the same time, Colgate was concerned about an anticipated 18 percent price
rollback on Procter & Gamble’s Crest Complete. Colgate wanted to assess the
impact of the possible price cut on existing market shares and to decide on a suitable
response, in terms of both its pricing of existing products and its introduction of the
new product.
The Study
The company had designed and conducted a conjoint study to assist in its product line
pricing decision. Data for the national study were gathered through personal inter-
views with 510 adults who were the primary shoppers for their households and who
had purchased a non-electric toothbrush in the previous six months. Complete,
usable responses were obtained from 484 of these respondents in a three-part question-
naire. The first part asked people about their preferred toothbrushes and obtained infor-
mation about their shopping behavior. The second part was a conjoint exercise that
This is an abridged version of an original case written by Professor Kusum Ailawadi of Dartmouth College
and is used with permission.
370 Chapter 9 Heuristic Solutions with the Evolutionary Solver
formed the core of the study. The final section contained some basic demographic
questions.
In the conjoint exercise, consumers were shown a simulated display containing 11
existing toothbrush brands that accounted for approximately 70 percent of the market,
EXHIBIT 9.1 Wave Concept Statement
Case: Colgate Wave (Abridged) 371
along with the new Colgate Wave. The display was configured to resemble shelf dis-
plays in actual stores and the toothbrushes were shown in their normal packaging, with
prices clearly marked. (At the beginning of the interview, respondents were asked
what kind of store they usually purchased toothbrushes at—such as discount stores/
mass merchandisers, drug/grocery stores, etc. The prices they were subsequently
shown were consistent with the outlets they shopped at—lower prices for those shop-
ping at discount and mass merchandisers and higher prices for those shopping at drug/
grocery stores.) Respondents were free to pick up and examine each product if they
wished. Respondents were initially shown this display with prices for each toothbrush
set at 24 percent below market level and were asked to select the brand that they would
buy. Once the respondent made a choice, the price of the chosen item was raised by
6 percent while prices of all others remained constant. Then, the respondent was
asked to make a choice again. Prices for each brand were varied from 24 percent
below market level to 24 percent above market level, in 6 percent increments. The
choice process was repeated until the respondent had gone through all brands at all
the price levels, or would not buy any brand at the prices shown, or refused to continue
with the exercise. The result was a matrix of choices made for brands at up to nine
different price levels. Not all respondents had the same number of choices because
they could opt out earlier saying, “All prices are too high.”
These choices were used as inputs to a proprietary model that estimated each
respondent’s part-worth utilities (on a scale of 1000) for each brand and price level.
These utilities, along with demographic information for each respondent, made up
the input data for the model. Given a price scenario, the model calculated market
shares from the data on utilities. The case appendix provides a description of the
Excel workbook containing the model.
The actual market prices and market shares of the 11 existing brands in the study,
along with the market price being planned for Colgate Wave, are listed in the table
below. In this table, market shares have been re-scaled from their original values for
the entire US market so that they add up to 100 percent for the 11 brands included
in the study. These 11 brands accounted for anticipated sales of roughly 300 million
toothbrushes in 1996.
Brand Price Share: %
Colgate Wave 2.99
Colgate Plus 2.14 18.10
Colgate Classic 0.99 2.90
Colgate Total 2.69 6.79
Crest Complete 2.54 12.70
Oral-B Advantage 2.99 10.81
Oral-B Indicator 2.39 12.09
Store brands (Rite Aid) 1.09 17.31
Mentadent 2.99 7.40
Aquafresh Flex Direct 2.59 2.90
Reach Plaque Sweeper 2.89 0.70
Reach Regular 2.14 8.30
372 Chapter 9 Heuristic Solutions with the Evolutionary Solver
At these prices, the contribution and net profit margins for the four Colgate brands
were as follows.
Classic Plus Total Wave
Unit price 0.99 2.14 2.69 2.99
Variable cost 0.59 1.18 1.34 1.35
Contribution
margin
0.40 0.96 1.35 1.64
Case Appendix: Market Share Simulation Model (Colgate.xls)
The workbook consists of three sheets: (1) data, (2) calculations, and (3) simulation.
As the names of the sheets imply, the data sheet contains raw input data for the model,
the calculations sheet performs all the necessary calculations, and the simulation sheet
determines the final market shares for each simulation. The contents of the three sheets
are described below. A copy of the model can be downloaded from the book’s website:
http://mba.tuck.dartmouth.edu/opt/
Data
Column A contains the respondent ID for each of the 484 respondents. Columns B
through M contain the estimated utilities for each of the 12 brands in the study.
Columns O through W contain the utilities for each of the nine price levels in the
study. Column Y contains Kendall’s Tau (a measure of model fit) for each respondent.
Columns AA through AE contain some basic demographic data for the respondents.
Finally, column AF contains data on the number of toothbrushes purchased per year
by each respondent. The information on toothbrushes purchased is ultimately used to
compute the “share of toothbrushes” in the other sheets.
Calculations
Columns A through H convert actual dollar prices entered in the simulation sheet into
price levels (e.g., 24 percent below or 12 percent above market price) for which utili-
ties are available. Columns F, G, and H assign an integer to each of the nine price levels
(e.g., 24 percent below equals 14 and 24 percent above equals 22). Column E lists the
current market prices of each brand. (The market price for Wave is the super-premium
price of $2.99 used in its concept test.) Column B converts the price entered in the
simulation sheet to the closest (lower) integer between 14 and 22, corresponding to
the scale in column G. It also truncates prices at both ends. Thus, if a price is more
than 24 percent below (or above) market price in the Simulation sheet, it will be trun-
cated to 24 percent below (or above). Column C calculates the price difference as a
percentage. This information is used to interpolate price utilities between the nine dis-
crete levels used in the study.
Column J lists the respondent IDs. Columns K through V compute the total uti-
lities of each brand in the simulation, given the prices entered in the simulation sheet.
These columns pick the utilities of the appropriate brand and the appropriate integer
price level from the data sheet, and include any necessary interpolation of price utility.
Case: Colgate Wave (Abridged) 373
Column X lists the maximum utility across the 12 brands. If a price of 100 is entered
for Wave in the simulation sheet, Wave is left out of the calculation in Column Y.
Columns Z through AK compute 0/1 variables indexing the brand with the maximum
utility (i.e., the brand that will be chosen). These columns are summed in row 487 to
provide the total number of times that each brand is chosen in the sample of 484
respondents. The choices are weighted by each respondent’s number of toothbrushes
purchased per year (from the data sheet) to get the total number of toothbrushes of each
brand in row 488.
Simulation
Current (“Original”) market prices of each brand are listed in C9:C20. New prices for
each simulation should be entered in the yellow area (B9:B20). The resultant percen-
tage change in price is computed in D9:D20. Prices must not fall beyond the permiss-
ible range (24 percent below market price to 24 percent above market price). The limits
of the permissible ranges are shown in cells F9:G20. Although the worksheet allows
prices beyond this range in the simulation sheet, the actual prices used to calculate
utilities will be appropriately truncated in the calculation sheet. To run a simulation
without Wave in the market, enter a price of 100 for Wave. This value will cause it
to be disregarded in the prediction of choice and share.
Each brand’s predicted share of choices by the 484 respondents is computed in
B24:B35. The corresponding share of toothbrushes (choices weighted by number of
toothbrushes purchased per year) is computed in C24:C35. Cells D24:D35 contain
adjustment factors for these results. Finally, predicted shares of toothbrushes, adjusted
by these factors, appear in cells E24:E35.
The adjustment factors in cells D24:D35 bring predicted share of toothbrushes
in the base case (current prices in current market) in line with actual market shares.
That is, when current prices are placed in cells B10:B20, the adjustment factors
produce the market shares listed in the case. In order to make this calculation, the
model is run once for the base case and its predictions are saved. Then the base
case shares listed in the case are entered. The adjustment factors are calculated directly
from these figures.
374
Chapter 9 Heuristic Solutions with the Evolutionary Solver
Appendix 1
Optimization Software and
Supplemental Files
A1.1. RISK SOLVER PLATFORM
Purchasers of this book may download a powerful software package called Risk Solver
Platform (RSP) that was developed by the same team that created Excel’s Solver, and
that accommodates all Excel Solver models. This book uses Risk Solver Platform for
Education (RSPE), which has all the functionality of the commercial product RSP but
with lower limits on the size of optimization problems and “educational use” water-
marks on charts. All the examples and exercises in this book can be solved within
the limits of RSPE.
If you’ve purchased this book and you are a student enrolled in a university
course, you can download and install the software and use RSPE for a full semester
(140 days) at no charge. To do this, visit www.solver.com/student, fill out the form
on this page, and click the button to register and download. To complete the form,
you’ll need two pieces of information: a Textbook Code, which is BOMS2, and a
Course Code, which your instructor can obtain from Frontline Systems, the software
developers, and give to you.
1
If you’ve purchased this book for self-study but you’re not enrolled in a university
course, you have two options: (1) Visit www.solver.com and register on the forms
presented there, download and install the software, and use RSP (the full commercial
product with much higher size limits) on a free trial, which is currently limited to
15 days; or (2) Contact Frontline Systems at 775-831-0300 or info@solver.com and
request a Course Code that will allow you to use RSPE for 140 days. As long as
you’re using the software for learning rather than production use, the company’s cur-
rent policy is to routinely grant these licenses.
The software works with Excel 2003, Excel 2007 and Excel 2010, but if you are
using the 64-bit version of Excel 2010, be sure to download and run the Setup program
Optimization Modeling with Spreadsheets, Second Edition. Kenneth R. Baker
# 2011 John Wiley & Sons, Inc. Published 2011 by John Wiley & Sons, Inc.
1
For longer-term licenses, course instructors should contact Frontline Systems at 775-831-0300 or
info@solver.com
375