Optimization with Spreadsheets

Problem set - 4
Integer Linear Programming

Problem 1
The Ice-Cold Refrigerator Company is considering investing in several projects that have
varying capital requirements over the next four years. Faced with limited capital each year,
management would like to select the most profitable projects. The estimated net present value
for each project, the capital requirements, and the available capital over the four-year period
are shown in Table 7.1.

Problem 2
RMC, Inc., is a small firm that produces a variety of chemical products. Three raw materials
are used to produce three products – a fuel additive, solvent base, and a carpet cleaning fluid.
The profit contributions are $40 per ton for fuel additive, $30 per ton for solvent base, and
$50 per ton for the carpet cleaning fluid. Each ton of fuel additive is a blend of 0.4 tons of
material 1 and 0.6 tons of material 3. Each ton of solvent base requires 0.5 tons of material 1,
0.2 tons of material 2, and 0.3 tons of material 3. Each ton of carpet cleaning fluid is a blend
of 0.6 tons of material 1, 0.1 tons of material 2, and 0.3 tons of material 3. RMC has 20 tons
of material 1, 5 tons of material 2, and 21 tons of material 3 and is interested in determining
the optimal production quantities for the upcoming planning period.

Suppose the following are available concerning the setup cost and the maximum production
quantity for each of the three products. Determine the optimal product mix.
Problem 3
The MB company operates a plant in St. Louis with an annual capacity of 30,000 units.
Product is shipped to regional distribution centres located in Boston, Atlanta, and Houston.
Because of an anticipated increase in demand, MB plans to increase capacity by constructing
a new plant in one or more of the following cities: Detroit, Toledo, Denver or Kansas city.
The estimated annual fixed cost and the annual capacity for the four proposed plants are as
follows:

Proposed plant Annual fixed cost ($) Annual capacity

Detroit 1, 75, 000 10, 000
Toledo 3, 00, 000 20, 000
Denver 3, 75, 000 30, 000
Kansas city 5, 00, 000 40, 000

The company’s long range planning group developed forecasts of the anticipated annual
demand at the distribution centres as follows:

Distribution center Annual demand

Boston 30, 000
Atlanta 20, 000
Houston 20, 000

The shipping cost per unit from each plant to distribution center is shown in the table
provided below. Develop a model for choosing the best plant location and for determining
how much to ship from each plant to each distribution center.

Plant site Boston Atlanta Houston

Detroit 5 2 3
Toledo 4 3 4
Denver 9 7 5
Kansas city 10 4 2
St. Louis 8 4 3

Problem 4
SOUTHWESTERN AIRWAYS needs to assign its crews to cover all its upcoming flights. We
will focus on the problem of assigning three crews based in San Francisco to the flights listed
in the first column of Table 12.4. The other 12 columns show the 12 feasible sequences of
flights for a crew. (The numbers in each column indicate the order of the flights.) Exactly
three of the sequences need to be chosen (one per crew) in such a way that every flight is
covered. (It is permissible to have more than one crew on a flight, where the extra crews
would fly as passengers, but union contracts require that the extra crews would still need to
be paid for their time as if they were working.) The cost of assigning a crew to a particular
sequence of flights is given (in thousands of dollars) in the bottom row of the table. The
objective is to minimize the total cost of the three crew assignments that cover all the flights.
Problem 5
The long-range planning department for the Ohio Trust Company is considering expanding
its operation into a 20-county region in northeastern Ohio (see Figure 7.9). Currently, Ohio
Trust does not have a principal place of business in any of the 20 counties. According to the
banking laws in Ohio, if a bank establishes a principal place of business (PPB) in any county,
branch banks can be established in that county and in any adjacent county. However, to
establish a new principal place of business, Ohio Trust must either obtain approval for a new
bank from the state’s superintendent of banks or purchase an existing bank. Ohio Trust would
like to determine the minimum number of PPBs necessary to do business throughout the 20-
county region.

FIGURE 7.9 THE 20-OUNTY REGION IN NORTHEASTERN OHIO

TABLE 7.3 COUNTIES IN THE OHIO TRUST EXPANSION REGION

Problem 6
Salem Foods is planning to enter the frozen pizza market. Currently, two existing brands,
Antonio’s and King’s, have the major share of the market. In trying to develop a sausage
pizza that will capture a significant share of the market, Salem determined that the four most
important attributes when consumers purchase a frozen sausage pizza are crust, cheese,
sauce, and sausage flavor. The crust attribute has two levels (thin and thick); the cheese
attribute has two levels (mozzarella and blend); the sauce attribute has two levels (smooth
and chunky); and the sausage flavor attribute has three levels (mild, medium, and hot).

Table 7.4 shows the part-worths for each level of each attribute provided by a sample of eight
potential Salem customers who are currently buying either King’s or Antonio’s pizza. For
consumer 1, the part-worths for the crust attribute are 11 for thin crust and 2 for thick crust,
indicating a preference for thin crust. For the cheese attribute, the part-worths are 6 for the
mozzarella cheese and 7 for the cheese blend; thus, consumer 1 has a slight preference for the
cheese blend. From the other part-worths, we see that consumer 1 shows a strong preference
for the chunky sauce over the smooth sauce (17 to 3) and has a slight preference for the
medium-flavored sausage. Note that consumer 2 shows a preference for the thin crust, the
cheese blend, the chunky sauce, and mild-flavored sausage. The part-worths for the other
consumers are interpreted in a similar manner.

The part-worths can be used to determine the overall value (utility) each consumer attaches to
a particular type of pizza. For instance, consumer 1’s current favorite pizza is the Antonio’s
brand, which has a thick crust, mozzarella cheese, chunky sauce, and medium-flavored
sausage. We can determine consumer 1’s utility for this particular type of pizza using the
part-worths in Table 7.4. For consumer 1, the part-worths are 2 for thick crust, 6 for
mozzarella cheese, 17 for chunky sauce, and 27 for medium-flavored sausage. Thus,
consumer 1’s utility for the Antonio’s brand pizza is 2 + 6 + 17 + 27 = 52. We can compute
consumer 1’s utility for a King’s brand pizza in a similar manner. The King’s brand pizza has
a thin crust, a cheese blend, smooth sauce, and mild-flavored sausage. Because the part-
worths for consumer 1 are 11 for thin crust, 7 for cheese blend, 3 for smooth sauce, and 26
for mild-flavored sausage, consumer 1’s utility for the King’s brand pizza is 11 + 7 + 3 + 26 =
47. In general, each consumer’s utility for a particular type of pizza is just the sum of the
appropriate part-worths.

In order to be successful with its brand, Salem Foods realizes that it must entice consumers in
the marketplace to switch from their current favorite brand of pizza to the Salem product.
That is, Salem must design a pizza (choose the type of crust, cheese, sauce, and sausage
flavor) that will have the highest utility for enough people to ensure sufficient sales to justify
making the product. Assuming the sample of eight consumers in the current study is
representative of the marketplace for frozen sausage pizza, we can formulate and solve an
integer programming model that can help Salem come up with such a design. In marketing
literature, the problem being solved is called the share of choices problem.

Note: Antonio’s brand is the current favourite for pizza for customers 1,4,6,7, and 8 King’s
brand is the current favourite pizza for consumers 2,3 and 5.