Chapter Three: Linear Programming: Formulation and Applications

Confirming Pages
Chapter Three
Linear Programming:
Formulation and
Applications
Learning Objectives
After completing this chapter, you should be able to
1. Recognize various kinds of managerial problems to which linear programming can be

applied.
2. Describe the five major categories of linear programming problems, including their
identifying features.
3. Formulate a linear programming model from a description of a problem in any of
these categories.
4. Describe the difference between resource constraints and benefit constraints, includ-
ing the difference in how they arise.
5. Describe fixed-requirement constraints and where they arise.
6. Identify the kinds of Excel functions that linear programming spreadsheet models use
for the output cells, including the objective cell.
7. Identify the four components of any linear programming model and the kind of
spreadsheet cells used for each component.
8. Recognize managerial problems that can be formulated and analyzed as linear pro-
gramming problems.
9. Understand the flexibility that managers have in prescribing key considerations that
can be incorporated into a linear programming model.
Linear programming problems come in many guises. And their models take various forms.
This diversity can be confusing to both students and managers, making it difficult to recog-
nize when linear programming can be applied to address a managerial problem. Since manag-
ers instigate management science studies, the ability to recognize the applicability of linear
programming is an important managerial skill. This chapter focuses largely on developing
this skill.
The usual textbook approach to trying to teach this skill is to present a series of diverse
examples of linear programming applications. The weakness of this approach is that it empha-
sizes differences rather than the common threads between these applications. Our approach
will be to emphasize these common threads—the identifying features—that tie together
linear programming problems even when they arise in very different contexts. We will
describe some broad categories of linear programming problems and the identifying features
that characterize them. Then we will use diverse examples, but with the purpose of illustrating
and emphasizing the common threads among them.
We will focus on five key categories of linear programming problems: resource-allocation
problems, cost–benefit–trade-off problems, mixed problems, transportation problems, and
64
hil24064_ch03_064-123.indd 64 02/11/12 4:54 PM

Confirming Pages
3.1 A Case Study: The Super Grain Corp. Advertising-Mix Problem 65
assignment problems. In each case, an important identifying feature is the nature of the restric-
tions on what decisions can be made, and thus the nature of the resulting functional constraints
in the linear programming model. For each category, you will see how the basic data for a
problem lead directly to a linear programming model with a certain distinctive form. Thus,
model formulation becomes a by-product of proper problem formulation.
The chapter begins with a case study that initially involves a resource-allocation problem.
We then return to the case study in Section 3.4, where additional managerial considerations
turn the problem into a mixed problem.
Sections 3.2 to 3.6 focus on the five categories of linear programming problems in turn.
Section 3.7 then takes a broader look at the formulation of linear programming models from
a managerial perspective. That section (along with Section 3.4) highlights the importance of
having the model accurately reflect the managerial view of the problem. These (and other)
sections also describe the flexibility available to managers for having the model structured to
best fit their view of the important considerations.
3.1 A CASE STUDY: THE SUPER GRAIN CORP. ADVERTISING-MIX

PROBLEM
Claire Syverson, vice president for marketing of the Super Grain Corporation, is facing a
daunting challenge: how to break into an already overly crowded breakfast cereal market in a
big way. Fortunately, the company’s new breakfast cereal—Crunchy Start—has a lot going
for it: Great taste. Nutritious. Crunchy from start to finish. She can recite the litany in her
sleep now. It has the makings of a winning promotional campaign.
However, Claire knows that she has to avoid the mistakes she made in her last campaign
for a breakfast cereal. That had been her first big assignment since she won this promotion,
and what a disaster! She thought she had developed a really good campaign. But somehow it
had failed to connect with the most crucial segments of the market—young children and par-
ents of young children. She also has concluded that it was a mistake not to include cents-off
coupons in the magazine and newspaper advertising. Oh well. Live and learn.
But she had better get it right this time, especially after the big stumble last time. The com-
pany’s president, David Sloan, already has impressed on her how important the success of
Crunchy Start is to the future of the company. She remembers exactly how David concluded
the conversation. “The company’s shareholders are not happy. We need to get those earnings
headed in the right direction again.” Claire had heard this tune before, but she saw in David’s
eyes how deadly serious he was this time.
Claire often uses spreadsheets to help organize her planning. Her management science
course in business school impressed upon her how valuable spreadsheet modeling can be. She
regrets that she did not rely more heavily on spreadsheet modeling for the last campaign. That
was a mistake that she is determined not to repeat.
Now it is time for Claire to carefully review and formulate the problem in preparation for
formulating a spreadsheet model.
The Problem
Claire already has employed a leading advertising firm, Giacomi & Jackowitz, to help design a
nationwide promotional campaign that will achieve the largest possible exposure for Crunchy
Start. Super Grain will pay this firm a fee based on services performed (not to exceed $1 million)
and has allocated an additional $4 million for advertising expenses.
Giacomi & Jackowitz has identified the three most effective advertising media for this
product:
Medium 1: Television commercials on Saturday morning programs for children.
Medium 2: Advertisements in food and family-oriented magazines.
Medium 3: Advertisements in Sunday supplements of major newspapers.
hil24064_ch03_064-123.indd 65 02/11/12 4:54 PM

Confirming Pages
66 Chapter Three Linear Programming: Formulation and Applications
TABLE 3.1
Costs
Cost and Exposure Data
for the Super Grain Each TV
Corp. Advertising-Mix Cost Category Commercial Each Magazine Ad Each Sunday Ad
Problem Ad budget $300,000 $150,000 $100,000
Planning budget 90,000 30,000 40,000
Expected number of exposures 1,300,000 600,000 500,000
The problem now is to determine which levels should be chosen for these advertising activi-
ties to obtain the most effective advertising mix.
To determine the best mix of activity levels for this particular advertising problem, it is
necessary (as always) to identify the overall measure of performance for the problem and
then the contribution of each activity toward this measure. An ultimate goal for Super Grain
is to maximize its profits, but it is difficult to make a direct connection between advertising
exposure and profits. Therefore, as a rough surrogate for profit, Claire decides to use expected
number of exposures as the overall measure of performance, where each viewing of an adver-
tisement by some individual counts as one exposure.
Giacomi & Jackowitz has made preliminary plans for advertisements in the three media.
The firm also has estimated the expected number of exposures for each advertisement in each
medium, as given in the bottom row of Table 3.1.
The number of advertisements that can be run in the different media are restricted by both
the advertising budget (a limit of $4 million) and the planning budget (a limit of $1 million
for the fee to Giacomi & Jackowitz). Another restriction is that there are only five commercial
spots available for running different commercials (one commercial per spot) on children’s
television programs Saturday morning (medium 1) during the time of the promotional cam-
paign. (The other two media have an ample number of spots available.)
Consequently, the three resources for this problem are:
Resource 1: Advertising budget ($4 million).
Resource 2: Planning budget ($1 million).
Resource 3: TV commercial spots available (5).
Table 3.1 shows how much of the advertising budget and the planning budget would be used
by each advertisement in the respective media.
• The first row gives the cost per advertisement in each medium.
• The second row shows Giacomi & Jackowitz’s estimates of its total cost (including
overhead and profit) for designing and developing each advertisement for the respective
media.1 (This cost represents the billable fee from Super Grain.)
• The last row then gives the expected number of exposures per advertisement.
Analysis of the Problem

Claire decides to formulate and solve a linear programming model for this problem on a
spreadsheet. The formulation procedure summarized at the end of Section 2.2 guides this pro-
cess. Like any linear programming model, this model will have four components:
1. The data
2. The decisions
3. The constraints
4. The measure of performance
1
When presenting its estimates in this form, the firm is making two simplifying assumptions. One is that its
cost for designing and developing each additional advertisement in a medium is roughly the same as for the
first advertisement in that medium. The second is that its cost when working with one medium is unaffected
by how much work it is doing (if any) with the other media.
hil24064_ch03_064-123.indd 66 02/11/12 4:54 PM

Confirming Pages
The spreadsheet needs to be formatted to provide the following kinds of cells for these
components:
Four kinds of cells are Data → data cells
needed for these four com-
Decisions → changing cells
ponents of a spreadsheet
model. Constraints → output cells
Measure of performance → objective cell
Figure 3.1 shows the spreadsheet model formulated by Claire. Let us see how she did this
by considering each of the components of the model individually.
FIGURE 3.1
The spreadsheet model for the Super Grain problem (Section 3.1), including the objective cell TotalExposures (H13) and the other
output cells BudgetSpent (F8:F9), as well as the specifications needed to set up Solver. The changing cells NumberOfAds (C13:E13)
show the optimal solution obtained by Solver.
A B C D E F G H
1 Super Grain Corp. Advertising-Mix Problem
2
3 TV Spots Magazine Ads SS Ads
4 Exposures per Ad 1,300 600 500
5 (thousands)
6 Budget Budget
7 Cost per Ad ($thousands) Spent Available
8 Ad Budget 300 150 100 4,000 ≤ 4,000
9 Planning Budget 90 30 40 1,000 ≤ 1,000
10
11 Total Exposures
12 TV Spots Magazine Ads SS Ads (thousands)
13 Number of Ads 0 20 10 17,000
14 ≤
15 Max TV Spots 5
Solver Parameters F
Set Objective Cell: TotalExposures
To: Max 6 Budget
By Changing Variable Cells: 7 Spent
NumberOfAds
Subject to the Constraints: 8 =SUMPRODUCT(C8:E8,NumberOfAds)
BudgetSpent <= BudgetAvailable 9 =SUMPRODUCT(C9:E9,NumberOfAds)
TVSpots <= MaxTVSpots
H
Solver Options:
Make Variables Nonnegative 11 Total Exposures
Solving Method: Simplex LP 12 (thousands)
13 =SUMPRODUCT(ExposuresPerAd,NumberOfAds)
Range Name Cells
BudgetAvailable H8: H9
BudgetSpent F8: F9
CostPerAd C8: E9
ExposuresPerAd C4: E4
MaxTVSpots C15
NumberOfAds C13: E13
TotalExposures H13
TVSpots C13
hil24064_ch03_064-123.indd 67 02/11/12 4:54 PM

Confirming Pages
The Data
One important kind of data is the information given earlier about the amounts available of
the three resources for the problem (the advertising budget, the planning budget, and the
commercial spots available). Table 3.1 provides the other key data for the problem. Using
units of thousands of dollars, these data have been transferred directly into data cells in the
spreadsheet in Figure 3.1 and given these range names: ExposuresPerAd (C4:E4), CostPerAd
(C8:E9), BudgetAvailable (H8:H9), and MaxTVSpots (C15).
The Decisions
The problem has been defined as determining the most effective advertising mix among the
three media selected by Giacomi & Jackowitz. Therefore, there are three decisions:
Decision 1: TV 5 Number of commercials for separate spots on television.
Decision 2: M 5 Number of advertisements in magazines.
Decision 3: SS 5 Number of advertisements in Sunday supplements.
The changing cells to hold these numbers have been placed in row 13 in the columns for these
media:
TV S cell C13 M S cell D13 SS S cell E13
These changing cells are collectively referred to by the range name NumberOfAds (C13:E13).
The Constraints
These changing cells need to be nonnegative. In addition, constraints are needed for the three
resources. The first two resources are the ad budget and planning budget. The amounts avail-
able for these two budgets are shown in the range BudgetAvailable (H8:H9). As suggested by
the # signs entered into column G, the corresponding constraints are
Total spending on advertising # 4,000 (Ad budget in $1,000s)
Total cost of planning # 1,000 (Planning budget in $1,000s)
Using the data in columns C, D, and E for the resources, these totals are
Total spending on advertising 5 300TV 1 150M 1 100SS

Total cost of planning 5 90TV 1 30M 1 40SS
These sums of products on the right-hand side are entered into the output cells BudgetSpent
(F8:F9) by using the SUMPRODUCT functions shown in the lower right-hand side of
Figure 3.1. Although the # signs entered in column G are only cosmetic (trial solutions
still can be entered in the changing cells that violate these inequalities), they will serve as a
reminder later to use these same # signs when entering the constraints in Solver.
Excel Tip: Range names The third resource is TV spots for different commercials. Five such spots are available for
may overlap. For instance, purchase. The number of spots used is one of the changing cells (C13). Since this cell will be
we have used NumberOfAds
used in a constraint, we assign the cell its own range name: TVSpots (C13). The maximum
to refer to the whole range
of changing cells, C13:E13, number of TV spots available is in the data cell MaxTVSpots (C15). Thus, the required con-
and TVSpots to refer to the straint is TVSpots # MaxTVSpots.
single cell, C13.
The Measure of Performance
Claire Syverson is using expected number of exposures as the overall measure of perfor-
mance, so let
Exposure 5 Expected number of exposures (in thousands) from all the advertising
The data cells ExposuresPerAd (C4:E4) provide the expected number of exposures (in thou-
sands) per advertisement in the respective media and the changing cells NumberOfAds
(C13:E13) give the number of each type of advertisement. Therefore,
hil24064_ch03_064-123.indd 68 02/11/12 4:54 PM

Confirming Pages
Exposure 5 1,300TV 1 600M 1 500SS

5 SUMPRODUCT (ExposuresPerAd, NumberOfAds)
is the formula that needs to be entered into the objective cell, TotalExposures (H13).
Summary of the Formulation

The above analysis of the four components of the model has formulated the following linear
programming model (in algebraic form) on the spreadsheet:
Maximize Exposure 5 1,300TV 1 600M 1 500SS
subject to
Ad spending: 300TV 1 150M 1 100SS # 4,000
Planning costs: 90TV 1 30M 1 40SS # 1,000
Number of television spots: TV # 5
and
TV $ 0 M$0 SS $ 0
The difficult work of defining the problem and gathering all the relevant data in Table 3.1
leads directly to this formulation.
Solving the Model

Excel Tip: With Excel’s To solve the spreadsheet model formulated above, some key information needs to be
Solver, the Solver dialog entered into Solver. The lower left-hand side of Figure 3.1 shows the needed entries:
box is used to tell Solver
the objective cell (TotalExposures), the changing cells (NumberOfAds), the goal of
the location on the spread-
sheet of several of the maximizing the objective cell, and the constraints BudgetSpent # BudgetAvailable and
elements of the model: TVSpots # MaxTVSpots. Two options are also specified at the bottom of the Solver
the changing cells, the Parameters box on the lower left-hand side of Figure 3.1. The changing cells need non-
objective cell, and the negativity constraints because negative values of advertising are not possible. Choose the
constraints. With RSPE,
Simplex LP (Excel’s Solver) or Standard LP/Quadratic Engine (RSPE) solving method,
the Decisions, Constraints,
and Objective menu on the because this is a linear programming model. Running Solver then finds an optimal solu-
RSPE ribbon are used along tion for the model and display it in the changing cells.
with the Model pane. The optimal solution given in row 13 of the spreadsheet provides the following plan for the
promotional campaign:
Do not run any television commercials.

Run 20 advertisements in magazines.
Run 10 advertisements in Sunday supplements.
Since TotalExposures (H13) gives the expected number of exposures in thousands, this plan
would be expected to provide 17,000,000 exposures.
Evaluation of the Adequacy of the Model

When she chose to use a linear programming model to represent this advertising-mix prob-
lem, Claire recognized that this kind of model does not provide a perfect match to this prob-
lem. However, a mathematical model is intended to be only an approximate representation
of the real problem. Approximations and simplifying assumptions generally are required to
have a workable model. All that is really needed is that there be a reasonably high correlation
between the prediction of the model and what would actually happen in the real problem. The
team now needs to check whether this criterion is satisfied.
Linear programming One assumption of linear programming is that fractional solutions are allowed. For the
models allow fractional current problem, this means that a fractional number (e.g., 3½) of television commercials (or
solutions.
of ads in magazines or Sunday supplements) should be allowed. This is technically true, since
a commercial can be aired for less than a normal run, or an ad can be run in just a fraction
of the usual magazines or Sunday supplements. However, one defect of the model is that it
hil24064_ch03_064-123.indd 69 02/11/12 4:54 PM

Confirming Pages
assumes that Giacomi & Jackowitz’s cost for planning and developing a commercial or ad
that receives only a fraction of its usual run is only that fraction of its usual cost, even though
the actual cost would be the same as for a full run. Fortunately, the optimal solution obtained
was an integer solution (0 television commercials, 20 ads in magazines, and 10 ads in Sunday
supplements), so the assumption that fractional solutions are allowed was not even needed.
Although it is possible to have a fractional number of a normal run of commercials or
ads, a normal run tends to be much more effective than a fractional run. Therefore, it would
have been reasonable for Claire to drop the assumption that fractional solutions are allowed.
If Claire had done this and the optimal solution for the linear programming model had not
turned out to be integer, constraints can be added to require the changing cells to be integer.
(The TBA Airlines example in the next section provides an illustration of this type of con-
straint.) After adding such constraints, the model is called an integer programming model
instead of a linear programming model, but it still can be readily solved by Solver.
Linear programming mod- Another key assumption of linear programming is that the appropriate equation for each of
els should use SUM or the output cells, including the objective cell, is one that can be expressed as a SUMPRODUCT
SUMPRODUCT functions
of data cells and changing cells (or occasionally just a SUM of changing cells). For the objec-
for the output cells, includ-
ing the objective cell. tive cell (cell H13) in Figure 3.1, this implies that the expected number of exposures to be
obtained from each advertising medium is proportional to the number of advertisements in that
medium. This proportionality seems true, since each viewing of the advertisements by some
individual counts as another exposure. Another implication of using a SUMPRODUCT func-
tion is that the expected number of exposures to be obtained from an advertising medium is
unaffected by the number of advertisements in the other media. Again, this implication seems
valid, since viewings of advertisements in different media count as separate exposures.
Although a SUMPRODUCT function is appropriate for calculating the expected number
of exposures, the choice of this number for the overall measure of performance is somewhat
questionable. Management’s real objective is to maximize the profit generated as a result of
the advertising campaign, but this is difficult to measure so expected number of exposures
was selected to be a surrogate for profit. This would be valid if profit were proportional to
the expected number of exposures. However, proportionality is only an approximation in
this case because too many exposures for the same individual reach a saturation level where
the impact (potential profit) from one more exposure is substantially less than for the first
exposure. (When proportionality is not a reasonable approximation, Chapter 8 will describe
nonlinear models that can be used instead.)
To check how reasonable it is to use expected number of exposures as a surrogate for
profit, Claire meets with Sid Jackowitz, one of the senior partners of Giacomi & Jackowitz.
Sid indicates that the contemplated promotional campaign (20 advertisements in magazines
and 10 in Sunday supplements) is a relatively modest one well below saturation levels. Most
readers will only notice these ads once or twice, and a second notice is very helpful for rein-
forcing the first one. Furthermore, the readership of magazines and Sunday supplements is
sufficiently different that the interaction of the advertising impact in these two media should
be small. Consequently, Claire concludes that using expected number of exposures for the
objective cell in Figure 3.1 provides a reasonable approximation. (A continuation of this case
study in Case 8-1 will delve into the more complicated analysis that is required in order to
use profit directly as the measure of performance to be recorded in the objective cell instead
of making this approximation.)
Next, Claire quizzes Sid about his firm’s costs for planning and developing advertisements
in these media. Is it reasonable to assume that the cost in a given medium is proportional
to the number of advertisements in that medium? Is it reasonable to assume that the cost of
developing advertisements in one medium would not be substantially reduced if the firm had
just finished developing advertisements in another medium that might have similar themes?
Sid acknowledges that there is some carryover in ad planning from one medium to another,
especially if both are print media (e.g., magazines and Sunday supplements), but that the
carryover is quite limited because of the distinct differences in these media. Furthermore,
he feels that the proportionality assumption is quite reasonable for any given medium since
the amount of work involved in planning and developing each additional advertisement in
the medium is nearly the same as for the first one in the medium. The total fee that Super
hil24064_ch03_064-123.indd 70 02/11/12 4:54 PM

Confirming Pages
3.2 Resource-Allocation Problems 71
Grain will pay Giacomi & Jackowitz will eventually be based on a detailed accounting of the
amount of work done by the firm. Nevertheless, Sid feels that the cost estimates previously
provided by the firm (as entered in cells C9, D9, and E9 in units of thousands of dollars) give
a reasonable basis for roughly projecting what the fee will be for any given plan (the entries
in the changing cells) for the promotional campaign.
Based on this information, Claire concludes that using a SUMPRODUCT function for cell
F9 provides a reasonable approximation. Doing the same for cell F8 is clearly justified. Given
her earlier conclusions as well, Claire decides that the linear programming model incorpo-
rated into Figure 3.1 (plus any expansions of the model needed later for the detailed planning)
is a sufficiently accurate representation of the real advertising-mix problem. It will not be
necessary to refine the results from this model by turning next to a more complicated kind of
mathematical model (such as those to be described in Chapter 8).
Therefore, Claire sends a memorandum to the company’s president, David Sloan, describ-
ing a promotional campaign that corresponds to the optimal solution from the linear program-
ming model (no TV commercials, 20 ads in magazines, and 10 ads in Sunday supplements).
She also requests a meeting to evaluate this plan and discuss whether some modifications
should be made.
We will pick up this story again in Section 3.4.
Review 1. What is the problem being addressed in this case study?

Questions 2. What overall measure of performance is being used?
3. What are the assumptions of linear programming that need to be checked to evaluate the
adequacy of using a linear programming model to represent the problem under consideration?
3.2 RESOURCE-ALLOCATION PROBLEMS

In the opening paragraph of Chapter 2, we described managerial problems involving the allo-
cation of an organization’s resources to its various productive activities. Those were resource-
allocation problems.
Resource-allocation problems are linear programming problems involving the allocation of
resources to activities. The identifying feature for any such problem is that each functional con-
straint in the linear programming model is a resource constraint, which has the form
Amount of resource used # Amount of resource available
for one of the resources.
The amount of a resource used depends on which activities are undertaken, the levels of
those activities, and how heavily those activities need to use the resource. Thus, the resource
constraints place limits on the levels of the activities. The objective is to choose the levels of
the activities so as to maximize some overall measure of performance (such as total profit)
from the activities while satisfying all the resource constraints.
Beginning with the case study and then the Wyndor Glass Co. product-mix problem, we will
look at four examples that illustrate the characteristics of resource-allocation problems. These
examples also demonstrate how this type of problem can arise in a variety of contexts.
The Super Grain Corp. Advertising-Mix Problem

The linear programming model formulated in Section 3.1 for the Super Grain case study is
one example of a resource-allocation problem. The three activities under consideration are the
advertising in the three types of media chosen by Giacomi & Jackowitz.
Activity 1: TV commercials
Activity 2: Magazine ads
Activity 3: Sunday ads
The decisions being made are the levels of these activities, that is, the number of TV com-
mercials, magazine ads, and Sunday ads to run.
hil24064_ch03_064-123.indd 71 02/11/12 4:54 PM

Confirming Pages
An initial step in formulat- The resources to be allocated to these activities are

ing any resource-allocation
problem is to identify the Resource 1: Advertising budget ($4 million).
activities and the resources. Resource 2: Planning budget ($1 million).
Resource 3: TV spots available for different commercials (5).
where the amounts available of these resources are given in parentheses. Thus, this problem
has three resource constraints:
1. Advertising budget used # $4 million
2. Planning budget used # $1 million
3. TV spots used # 5
Rows 8–9 and cells C13:C15 in Figure 3.1 show these constraints in a spreadsheet. Cells C8:E9
give the amount of the advertising budget and the planning budget used by each unit of each activ-
ity, that is, the amount used by one TV spot, one magazine ad, and one Sunday ad, respectively.
Cells C4, D4, and E4 on this spreadsheet give the contribution per unit of each activity to
the overall measure of performance (expected number of exposures).
Characteristics of Resource-Allocation Problems

For each proposed activ- Other resource-allocation problems have the same kinds of characteristics as the Super Grain
ity, a decision needs to be problem. In each case, there are activities where the decisions to be made are the levels of
made as to how much of
these activities. The contribution of each activity to the overall measure of performance is
the activity to do. In other
words, what should the proportional to the level of that activity. Commonly, this measure of performance is the total
level of the activity be? profit from the activities, but occasionally it is something else (as in the Super Grain problem).
Every problem of this type has a resource constraint for each resource. The amounts of the
resources used depend on the levels of the activities. For each resource, the amount used by
each activity is proportional to the level of that activity.
These three kinds of The manager or management science team studying a resource allocation problem needs to
data are needed for any gather (with considerable help) three kinds of data:
resource-allocation
problem. 1. The amount available of each resource.
2. The amount of each resource needed by each activity. Specifically, for each combination
of resource and activity, the amount of the resource used per unit of the activity must be
estimated.
3. The contribution per unit of each activity to the overall measure of performance.
Generally there is considerable work involved in developing these data. A substantial
amount of digging and consultation is needed to obtain the best estimates available in a timely
fashion. This step is critical. Well-informed estimates are needed to obtain a valid linear pro-
gramming model for guiding managerial decisions. The dangers involved in inaccurate esti-
mates are one reason why what-if analysis (Chapter 5) is such an important part of most linear
programming studies.
The Wyndor Glass Co. Product-Mix Problem

The product-mix problem facing the management of the Wyndor Glass Co. in Section 2.1 is
to determine the most profitable mix of production rates for the two new products, consider-
ing the limited availability of spare production capacity in the company’s three plants. This is
a resource-allocation problem.
The activities under consideration are
Activity 1: Produce the special new doors.
Activity 2: Produce the special new windows.
The decisions being made are the levels of these activities, that is, the production rates for the
doors and windows. Production rate is being measured as the number of units (doors or win-
dows) produced per week. Management’s objective is to maximize the total profit generated
by the two new products, so the overall measure of performance is total profit. The contribu-
tion of each product to profit is proportional to the production rate for that product.
hil24064_ch03_064-123.indd 72 02/11/12 4:54 PM

Confirming Pages
The resources to be allocated to these activities are

Resource 1: Production capacity in Plant 1.
Each of the three functional constraints in the linear programming model formulated in
Section 2.2 (see rows 7–9 of the spreadsheet in Figure 2.3 or 2.4) is a resource constraint for
one of these three resources. Column E shows the amount of production capacity used in each
plant and column G gives the amount available.
Table 2.1 in Section 2.1 provides the data for the Wyndor problem. You already have seen
how the numbers in Table 2.1 become the parameters in the linear programming model in
either its spreadsheet formulation (Section 2.2) or its algebraic form (Section 2.3).
The TBA Airlines Problem

TBA Airlines is a small regional company that specializes in short flights in small passenger air-
planes. The company has been doing well and management has decided to expand its operations.
The Problem
The basic issue facing management now is whether to purchase more small airplanes to add
some new short flights or to start moving into the national market by purchasing some large
airplanes for new cross-country flights (or both). Many factors will go into management’s
final decision, but the most important one is which strategy is likely to be most profitable.
The first row of Table 3.2 shows the estimated net annual profit (inclusive of capital recov-
ery costs) from each type of airplane purchased. The second row gives the purchase cost per
airplane and also notes that the total amount of capital available for airplane purchases is
$250 million. The third row records the fact that management does not want to purchase more
than five small airplanes because of limited possibilities for adding lucrative short flights,
whereas they have not specified a maximum number for large airplanes (other than that
imposed by the limited capital available).
How many airplanes of each type should be purchased to maximize the total net annual profit?
Formulation
This is a resource-allocation problem. The activities under consideration are
Activity 1: Purchase small airplanes.
Activity 2: Purchase large airplanes.
The decisions to be made are the levels of these activities, that is,
S 5 Number of small airplanes to purchase
L 5 Number of large airplanes to purchase
The one resource to be allocated to these activities is
Resource: Investment capital ($250 million).
Thus, there is a single resource constraint:
Investment capital spent # $250 million
In addition, management has specified one side constraint:
Number of small airplanes purchased # 5
Figure 3.2 shows the formulation of a spreadsheet model for this problem, where the data in
Table 3.2 have been transferred into the data cells—UnitProfit (C4:D4), CapitalPerUnitPurchased
TABLE 3.2
Small Airplane Large Airplane Capital Available
Data for the TBA
Airlines Problem Net annual profit per airplane $7 million $22 million
Purchase cost per airplane $25 million $75 million $250 million
Maximum purchase quantity 5 No maximum
hil24064_ch03_064-123.indd 73 02/11/12 4:54 PM

Confirming Pages
FIGURE 3.2
A spreadsheet model for the TBA Airlines integer programming problem where the changing cells, UnitsProduced (C12:D12), show
the optimal airplane purchases obtained by Solver, and the objective cell, TotalProfit (G12), gives the resulting total profit in mil-
lions of dollars.
A B C D E F G
1 TBA Airlines Airplane Purchasing Problem
2
3 Small Airplane Large Airplane
4 Unit Profit ($millions) 7 22
5
6 Capital Capital
7 Capital per Unit Purchased Spent Available
8 Capital ($millions) 25 75 250 <= 250
9
10 Total Profit
11 Small Airplane Large Airplane ($millions)
12 Number Purchased 1 3 73
13 <=
14 Maximum Small Airplanes 5
E
6 Capital
7 Spent
8 =SUMPRODUCT(CapitalPerUnitPurchased,NumberPurchased)
Solver Parameters G
Set Objective Cell: TotalProfit 10 Total Profit
To: Max 11 ($millions)
By Changing Variable Cells: 12 =SUMPRODUCT(UnitProfit,NumberPurchased)
NumberPurchased
Subject to the Constraints: Range Name Cells
CapitalSpent <= CapitalAvailable Capital Available G8
NumberPurchased = integer CapitalPerUnitPurchased C8:D8
SmallAirplanes <= MaxSmallAirplanes CapitalSpent E8
MaxSmallAirplanes C14
Solver Options:
NumberPurchased C12:D12
Make Variables Nonnegative
SmallAirplanes C12
Solving Method: Simplex LP
TotalProfit G12
UnitProfit C4:D4
(C8:D8), CapitalAvailable (G8), and MaxSmallAirplanes (C14). The resource constraint then
appears in cells C8:G8 while C12:C14 shows the side constraint. The objective for this problem
is to maximize the total net annual profit, so the equation for the objective cell is
TotalProfit (G12) 5 SUMPRODUCT (UnitProfit, UnitsPurchased)
Since the TBA Airlines problem is a resource-allocation problem, this spreadsheet model
has essentially the same form as the Super Grain and Wyndor problems except for one small
difference. The changing cells in this case must have integer values since it is not feasible
for the company to purchase and operate a fraction of an airplane. Therefore, constraints that
the changing cells need to be integer are added. With Excel’s Solver, use the Add Constraint
dialog box to choose the range of these cells (C12:D12) as the left-hand side and then choose
int from the pop-up menu between the left-hand and right-hand side. In RSPE, choose the
changing cells (C12:D12), and then under the Constraint menu on the RSPE ribbon, choose
Integer under the Variable Type/Bound submenu.
These changing cells in Figure 3.2 show the optimal solution, (S, L) 5 (1, 3), obtained
after running Solver.
hil24064_ch03_064-123.indd 74 02/11/12 4:54 PM

Confirming Pages
Excel Tip: To constrain One of the assumptions of linear programming is that the changing cells are allowed to
a range of changing cells have any values, including fractional values, that satisfy the functional and nonnegativity
to be integer in Excel’s
constraints. Therefore, technically speaking, the TBA problem is not a linear programming
Solver, choose the range of
cells in the left-hand side of problem because of adding the constraints
the Add Constraint dialog
NumberPurchased 5 integer
box and choose int from the
pop-up menu. Clicking OK that are displayed in the Solver Parameters box in Figure 3.2. Such a problem that fits lin-
then enters the constraint
ear programming except for adding such constraints is called an integer programming
that these cells 5 integer
in the Solver dialog box. problem. The method used by Solver to solve integer programming problems is quite differ-
In RSPE, select the range ent from that for solving linear programming problems. In fact, integer programming prob-
of cells to be constrained lems tend to be much more difficult to solve than linear programming problems so there is
integer, and then under considerably more limitation on the size of the problem. However, this doesn’t matter to a
the Constraint menu on
spreadsheet modeler dealing with small problems. From his or her viewpoint, there is virtu-
the RSPE ribbon, choose
Integer under the Variable ally no distinction between linear programming and integer programming problems. They are
Type/Bound submenu. formulated in exactly the same way. Then, at the very end, a decision needs to be made as
to whether any of the changing cells need to be restricted to integer values. If so, those con-
straints are added as described above. Keep this option in mind as we continue to discuss the
formulation of various types of linear programming problems throughout the chapter.

Excel Tip: Even when a The above formulation of a model with one resource constraint and one side constraint for the
changing cell is constrained TBA Airlines problem now can be summarized (in algebraic form) as follows:
to be integer, rounding
errors occasionally will Maximize Profit 5 7S 1 22L
cause Excel to return a non-
integer value very close to subject to
an integer (e.g., 1.23E-10,
meaning 0.000000000123). 25S 1 75L # 250
To make the spreadsheet
S # 5
cleaner, you may replace
these “ugly” representations and
by their proper integer val- S$0 L$0
ues in the changing cells.
Capital Budgeting
Excel Tip: In Excel’s Financial planning is one of the most important areas of application for resource-allocation
Solver Options, the Integer problems. The resources being allocated in this area are quite different from those for applica-
Optimality (%) setting
tions in the production planning area (such as the Wyndor Glass Co. product-mix problem),
(1 percent by default)
causes Solver to stop solv- where the resources tend to be production facilities of various kinds. For financial planning,
ing an integer programming the resources tend to be financial assets such as cash, securities, accounts receivable, lines of
problem when it finds a fea- credit, and so forth. Our specific example involves capital budgeting, where the resources are
sible solution whose objec- amounts of investment capital available at different points in time.
tive function value is within
the specified percentage of The Problem
being optimal. In RSPE, the
equivalent setting is Integer The Think-Big Development Co. is a major investor in commercial real-estate development
Tolerance under the Engine projects. It currently has the opportunity to share in three large construction projects:
tab of the Solver model (see
Figure 2.19). This is useful Project 1: Construct a high-rise office building.
to speed up solving large Project 2: Construct a hotel.
problems. For smaller prob-
lems (e.g., homework prob-
Project 3: Construct a shopping center.
lems), this option should be Each project requires each partner to make investments at four different points in time: a
set to 0 to guarantee finding
an optimal solution.
down payment now, and additional capital after one, two, and three years. Table 3.3 shows
for each project the total amount of investment capital required from all the partners at these
four points in time. Thus, a partner taking a certain percentage share of a project is obligated
to invest that percentage of each of the amounts shown in the table for the project.
All three projects are expected to be very profitable in the long run. So the management of
Think-Big wants to invest as much as possible in some or all of them. Management is willing
to commit all the company’s investment capital currently available, as well as all additional
hil24064_ch03_064-123.indd 75 02/11/12 4:54 PM

Confirming Pages
An Application Vignette
A key part of a country’s financial infrastructure is its secu- Following more than 12,000 man-hours devoted to
rities markets. By allowing a variety of financial institutions this redesign, the new system was successfully launched
and their clients to trade stocks, bonds, and other finan- in November 2008. The core of the new system is a large
cial securities, they help fund both public and private ini- linear programming model that is applied many times
tiatives. Therefore, the efficient operation of its securities daily to choose which pending transactions should be set-
markets plays a crucial role in providing a platform for the tled immediately with the depositor’s available balances.
economic growth of the country. Linear programming is ideally suited for this application
Each central securities depository and its system for because it can maximize the value of the transactions
quickly settling security transactions are part of the opera- settled while taking into account the various relevant
tional backbone of securities markets and a key component constraints.
of financial system stability. In Mexico, an institution called This application of linear programming has substan-
INDEVAL provides both the central securities depository tially enhanced and strengthened the Mexican financial
and its security settlement system for the entire country. infrastructure by reducing its daily liquidity requirements
This security settlement system uses electronic book entries, by $130 billion. It also reduces the intraday financing costs
modifying cash and securities balances, for the various par- for market participants by more than $150 million annu-
ties in the transactions. ally. This application also led to INDEVAL winning the pres-
The total value of the securities transactions the INDEVAL tigious first prize in the 2010 international competition for
settles averages over $250 billion daily. This makes INDEVAL the Franz Edelman Award for Achievement in Operations
the main liquidity conduit for Mexico’s entire financial sec- Research and the Management Sciences.
tor. Therefore, it is extremely important that INDEVAL’s sys-
tem for clearing securities transactions be an exceptionally
efficient one that maximizes the amount of cash that can Source: D. Muñoz, M. de Lascurain, O. Romeo-Hernandez, F. Solis,
L. de los Santoz, A. Palacios-Brun, F. Herrería, and J. Villaseñor,
be delivered almost instantaneously after the transactions.
“INDEVAL Develops a New Operating and Settlement System
Because of past dissatisfaction with this system, INDEVAL’s Using Operations Research,” Interfaces 41, no. 1 (January–February
board of directors ordered a major study in 2005 to com- 2011), pp. 8–17. (A link to this article is provided on our website,
pletely redesign the system. www.mhhe.com/hillier5e.)
TABLE 3.3
Investment Capital Requirements
Financial Data for
the Projects Being Year Office Building Hotel Shopping Center
Considered for Partial
0 $40 million $80 million $90 million
Investment by the Think-
1 60 million 80 million 50 million
Big Development Co. 2 90 million 80 million 20 million
3 10 million 70 million 60 million
Net present value $45 million $70 million $50 million
investment capital expected to become available over the next three years. The objective is
to determine the investment mix that will be most profitable, based on current estimates of
profitability.
Since it will be several years before each project begins to generate income, which will
continue for many years thereafter, we need to take into account the time value of money
in evaluating how profitable it might be. This is done by discounting future cash outflows
(capital invested) and cash inflows (income), and then adding discounted net cash flows, to
calculate a project’s net present value.
Based on current estimates of future cash flows (not included here except for outflows),
the estimated net present value for each project is shown in the bottom row of Table 3.3. All
the investors, including Think-Big, then will split this net present value in proportion to their
share of the total investment.
For each project, participation shares are being sold to major investors, such as Think-Big,
who become the partners for the project by investing their proportional shares at the four spec-
ified points in time. For example, if Think-Big takes a 10 percent share of the office building,
it will need to provide $4 million now, and then $6 million, $9 million, and $1 million in
1 year, 2 years, and 3 years, respectively.
76
hil24064_ch03_064-123.indd 76 02/11/12 4:54 PM

Confirming Pages
The company currently has $25 million available for capital investment. Projections are
that another $20 million will become available after one year, $20 million more after two
years, and another $15 million after three years. What share should Think-Big take in the
respective projects to maximize the total net present value of these investments?
Formulation
This is a resource-allocation problem. The activities under consideration are
Activity 1: Invest in the construction of an office building.
Activity 2: Invest in the construction of a hotel.
Activity 3: Invest in the construction of a shopping center.
Thus, the decisions to be made are the levels of these activities, that is, what participation
share to take in investing in each of these projects. A participation share can be expressed as
either a fraction or a percentage of the entire project, so the entire project is considered to be
one “unit” of that activity.
The resources to be allocated to these activities are the funds available at the four invest-
ment points. Funds not used at one point are available at the next point. (For simplicity, we
will ignore any interest earned on these funds.) Therefore, the resource constraint for each
point must reflect the cumulative funds to that point.
Resource 1: Total investment capital available now.
Resource 2: Cumulative investment capital available by the end of one year.
Resource 3: Cumulative investment capital available by the end of two years.
Resource 4: Cumulative investment capital available by the end of three years.
Since the amount of investment capital available is $25 million now, another $20 million
in one year, another $20 million in two years, and another $15 million in three years, the
amounts available of the resources are the following:
Amount of resource 1 available 5 $25 million
Amount of resource 2 available 5 $(25 1 20) million 5 $45 million
Amount of resource 3 available 5 $(25 1 20 1 20) million 5 $65 million
Amount of resource 4 available 5 $(25 1 20 1 20 1 15) million 5 $80 million
Table 3.4 shows all the data involving these resources. The rightmost column gives the
amounts of resources available calculated above. The middle columns show the cumulative
amounts of the investment capital requirements listed in Table 3.3. For example, in the Office
Building column of Table 3.4, the second number ($100 million) is obtained by adding the
first two numbers ($40 million and $60 million) in the Office Building column of Table 3.3.
The Data As with any resource-allocation problem, three kinds of data need to be gathered.
One is the amounts available of the resources, as given in the rightmost column of Table 3.4.
A second is the amount of each resource needed by each project, which is given in the middle
columns of this table. A third is the contribution of each project to the overall measure of
performance (net present value), as given in the bottom row of Table 3.3.
The first step in formulating the spreadsheet model is to enter these data into data cells
in the spreadsheet. In Figure 3.3, the data cells (and their range names) are NetPresentValue
TABLE 3.4
Cumulative Investment Capital Required for an Entire Project
Resource Data for the
Think-Big Development Office Shopping Amount of
Co. Investment-Mix Resource Building Hotel Center Resource Available
Problem
1 (Now) $ 40 million $ 80 million $ 90 million $25 million
2 (End of year 1) 100 million 160 million 140 million 45 million
hil24064_ch03_064-123.indd 77 02/11/12 4:54 PM

Confirming Pages
FIGURE 3.3
The spreadsheet model for the Think-Big problem, including the formulas for the objective cell TotalNPV (H16) and the other
output cells CapitalSpent (F9:F12), as well as the specifications needed to set up Solver. The changing cells ParticipationShare
(C16:E16) show the optimal solution obtained by Solver.
A B C D E F G H
1 Think-Big Development Co. Capital Budgeting Program
2
3 Office Shopping
4 Building Hotel Center
5 Net Present Value 45 70 50
6 ($millions) Cumulative Cumulative
7 Capital Capital
8 Cumulative Capital Required ($millions) Spent Available
9 Now 40 80 90 25 ≤ 25
10 End of Year 1 100 160 140 44.76 ≤ 45
11 End of Year 2 190 240 160 60.58 ≤ 65
12 End of Year 3 200 310 220 80 ≤ 80
13
14 Office Shopping Total NPV
15 Building Hotel Center ($millions)
16 Participation Share 0.00% 16.50% 13.11% 18.11
Solver Parameters F
Set Objective Cell: TotalNPV Range Name Cells
To: Max 6 Cumulative
By Changing Variable Cells: CapitalAvailable H9:H12
ParticipationShare CapitalRequired C9:E12 7 Capital
Subject to the Constraints: CapitalSpent F9:F12 8 Spent
CapitalSpent <= CapitalAvailable ParticipationShare C16:E16
9 =SUMPRODUCT(C9:E9,ParticipationShare)
NetPresentValue C5:E5
Solver Options: 10 =SUMPRODUCT(C10:E10,ParticipationShare)
TotalNPV H16
Solving Method: Simplex LP 11 =SUMPRODUCT(C11:E11,ParticipationShare)
12 =SUMPRODUCT C12:E12,ParticipationShare)
H
14 Total NPV
15 ($millions)
16 =SUMPRODUCT(NetPresentValue,ParticipationShare)
(C5:E5), CapitalRequired (C9:E12), and CapitalAvailable (H9:H12). To save space on the

spreadsheet, these numbers are entered in units of millions of dollars.
The Decisions With three activities under consideration, there are three decisions to be made.
Decision 1: OB 5 Participation share in the office building.
Decision 2: H 5 Participation share in the hotel.
Decision 3: SC 5 Participation share in the shopping center.
For example, if Think-Big management were to decide to take a one-tenth participation share
(i.e., a 10 percent participation share) in each of these projects, then
OB 5 0.1 5 10%
H 5 0.1 5 10%
SC 5 0.1 5 10%
However, it may not be desirable to take the same participation share (expressed as either a
fraction or a percentage) in each of the projects, so the idea is to choose the best combination
hil24064_ch03_064-123.indd 78 02/11/12 4:54 PM

Confirming Pages
of values of OB, H, and SC. In Figure 3.3, the participation shares (expressed as percentages)
have been placed in changing cells under the data cells (row 16) in the columns for the three
projects, so
OB S cell C16 H S D16 SC S cell E16
where these cells are collectively referred to by the range name ParticipationShare (C16:E16).
The Constraints The numbers in these changing cells make sense only if they are nonnega-
tive, so the Make Variables Nonnegative option will need to be selected in the Excel’s Solver
dialog box (or equivalently in RSPE, set the Assume Non-Negative option to True in the
Engine tab of the Model pane). In addition, the four resources require resource constraints:
Total invested now # 25 (millions of dollars available)
Total invested within 1 year # 45 (millions of dollars available)
Total invested within 2 years # 65 (millions of dollars available)
Total invested within 3 years # 80 (millions of dollars available)
The data in columns C, D, and E indicate that (in millions of dollars)
Total invested now 5 40 OB 1 80 H 1 90 SC
Total invested within 1 year 5 100 OB 1 160 H 1 140 SC
Total invested within 2 years 5 190 OB 1 240 H 1 160 SC
Total invested within 3 years 5 200 OB 1 310 H 1 220 SC
These totals are calculated in the output cells CapitalSpent (F9:F12) using the SUMPRODUCT
function, as shown below the spreadsheet in Figure 3.3. Finally, # signs are entered into col-
umn G to indicate the resource constraints that will need to be entered in Solver.
The Measure of Performance The objective is to
Maximize NPV 5 total net present value of the investments
NetPresentValue (C5:E5) shows the net present value of each entire project, while Partici-
pationShare (C16:E16) shows the participation share for each of the projects. Therefore, the
total net present value of all the participation shares purchased in all three projects is (in mil-
lions of dollars)
NPV 5 45 OB 1 70 H 1 50 SC
5 SUMPRODUCT (NetPresentValue, ParticipationShare)
S cell H16
Summary of the Formulation This completes the formulation of the linear programming
model on the speadsheet, as summarized below (in algebraic form).
Maximize NPV 5 45 OB 1 70 H 1 50 SC
subject to
Total invested now: 40 OB 1 80 H 1 90 SC # 25
Total invested within 1 year: 100 OB 1 160 H 1 140 SC # 45
Total invested within 2 years: 190 OB 1 240 H 1 160 SC # 65
Total invested within 3 years: 200 OB 1 310 H 1 220 SC # 80
and
OB $ 0 H$0 SC $ 0
where all these numbers are in units of millions of dollars.

Note that this model possesses the key identifying feature for resource-allocation prob-
lems, namely, each functional constraint is a resource constraint that has the form
Amount of resource used # Amount of resource available
hil24064_ch03_064-123.indd 79 02/11/12 4:54 PM

Confirming Pages
Solving the Model The lower left-hand side of Figure 3.3 shows the entries needed in Solver
to specify the model, along with the selection of the usual two options. The spreadsheet shows
the resulting optimal solution in row 16, namely,
Invest nothing in the office building.
Invest in 16.50 percent of the hotel.
Invest in 13.11 percent of the shopping center.
TotalNPV (H16) indicates that this investment program would provide a total net present
value of $18.11 million.
This amount actually is only an estimate of what the total net present value would turn out
to be, depending on the accuracy of the financial data given in Table 3.3. There is some uncer-
tainty about the construction costs for the three real estate projects, so the actual investment
capital requirements for years 1, 2, and 3 may deviate somewhat from the amounts specified
in this table. Because of the risk involved in these projects, the net present value for each one
also might deviate from the amounts given at the bottom of the table. Chapter 5 describes
one approach to analyzing the effect of such deviations. Chapters 12 and 13 will present
another technique, called computer simulation, for systematically taking future uncertainties
into account. Section 13.5 will focus on further analysis of this same example.
Another Look at Resource Constraints

These examples of resource-allocation problems illustrate a variety of resources: financial
allocations for advertising and planning purposes, TV commercial spots available for pur-
chase, available production capacities of different plants, the total amount of capital avail-
able for investment, and cumulative investment capital available by certain times. However,
these illustrations only scratch the surface of the realm of possible resources that need to be
allocated to activities in resource-allocation problems. In fact, by interpreting resource suf-
ficiently broadly, any restriction on the decisions to be made that has the form
Amount used # Amount available
can be thought of as a resource constraint, where the thing whose amount is being measured
is the corresponding “resource.” Since any functional constraint with a # sign in a linear pro-
gramming model (including the side constraint in the TBA Airlines example) can be verbal-
ized in this form, any such constraint can be thought of as a resource constraint.
Hereafter, we will use resource constraint to refer to any functional constraint with a # sign in
a linear programming model. The constant on the right-hand side represents the amount avail-
able of a resource. Therefore, the left-hand side represents the amount used of this resource. In
the algebraic form of the constraint, the coefficient (positive or negative) of each decision vari-
able is the resource usage per unit of the corresponding activity.
Summary of the Formulation Procedure for Resource-Allocation

Problems
The four examples illustrate that the following steps are used for any resource-allocation
problem to define the specific problem, gather the relevant data, and then formulate the linear
programming model.
1. Since any linear programming problem involves finding the best mix of levels of various
activities, identify these activities for the problem at hand. The decisions to be made are
the levels of these activities.
2. From the viewpoint of management, identify an appropriate overall measure of perfor-
mance (commonly profit, or a surrogate for profit) for solutions of the problem.
3. For each activity, estimate the contribution per unit of the activity to this overall measure
of performance.
4. Identify the resources that must be allocated to the activities.
5. For each resource, identify the amount available and then the amount used per unit of each
activity.
hil24064_ch03_064-123.indd 80 02/11/12 4:54 PM

Confirming Pages
3.3 Cost–Benefit–Trade-Off Problems 81
FIGURE 3.4
A template of a spreadsheet model for pure resource-allocation problems.
Activities
Unit Profit Profit per unit of activity

Resources Resources
Used Available
Constraints
SUMPRODUCT
Resource used per unit of activity (resource used per unit,
changing cells)
≤
Total Profit
Level of Activity Changing cells SUMPRODUCT(profit per unit, changing cells)
6. Enter the data gathered in steps 3 and 5 into data cells in a spreadsheet. A convenient for-
mat is to have the data associated with each activity in a separate column, the data for the
unit profit and each constraint in a separate row, and to leave two blank columns between
the activity columns and the amount of resource available column. Figure 3.4 shows a
template of the overall format of a spreadsheet model for resource-allocation problems.
7. Designate changing cells for displaying the decisions on activity levels.
8. For the two blank columns created in step 6, use the left one as a Totals column for output
cells and enter # signs into the right one for all the resources. In the row for each resource,
use the SUMPRODUCT function to enter the total amount used in the Totals column.
9. Designate an objective cell for displaying the overall measure of performance. Use a
SUMPRODUCT function to enter this measure of performance.
All the functional constraints in this linear programming model in a spreadsheet are
resource constraints, that is, constraints with a # sign. This is the identifying feature that
classifies the problem as being a resource-allocation problem.
Review 1. What is the identifying feature for a resource-allocation problem?

Questions 2. What is the form of a resource constraint?
3. What are the three kinds of data that need to be gathered for a resource-allocation problem?
4. Compare the types of activities for the four examples of resource-allocation problems.
5. Compare the types of resources for the four examples of resource-allocation problems.
3.3 COST–BENEFIT–TRADE-OFF PROBLEMS

Cost–benefit–trade-off problems have a form that is very different from resource-allocation
problems. The difference arises from managerial objectives that are very different for the two
kinds of problems.
For resource-allocation problems, limits are set on the use of various resources (including
financial resources), and then the objective is to make the most effective use (according to
some overall measure of performance) of these given resources.
For cost–benefit–trade-off problems, management takes a more aggressive stance, pre-
scribing what benefits must be achieved by the activities under consideration (regardless of
the resulting resource usage), and then the objective is to achieve all these benefits with mini-
A cost–benefit–trade-off mum cost. By prescribing a minimum acceptable level for each kind of benefit, and then mini-
formulation enables man-
agement to specify mini-
mizing the cost needed to achieve these levels, management hopes to obtain an appropriate
mum goals for the benefits trade-off between cost and benefits. (You will see in Chapter 5 that what-if analysis plays a
that need to be achieved by key role in providing the additional information needed for management to choose the best
the activities. trade-off between cost and benefits.)
hil24064_ch03_064-123.indd 81 02/11/12 4:54 PM

Confirming Pages
Cost–benefit–trade-off problems are linear programming problems where the mix of levels
of various activities is chosen to achieve minimum acceptable levels for various benefits at
a minimum cost. The identifying feature is that each functional constraint is a benefit
constraint, which has the form
Level achieved $ Minimum acceptable level
for one of the benefits.
Interpreting benefit broadly, we can think of any functional constraint with a $ sign as a
benefit constraint. In most cases, the minimum acceptable level will be prescribed by manage-
ment as a policy decision, but occasionally this number will be dictated by other circumstances.
For any cost–benefit–trade-off problem, a major part of the study involves identifying all
the activities and benefits that should be considered and then gathering the data relevant to
these activities and benefits.
These three kinds of data Three kinds of data are needed:
are needed for any cost–
benefit–trade-off problem. 1. The minimum acceptable level for each benefit (a managerial policy decision).
2. For each benefit, the contribution of each activity to that benefit (per unit of the activity).
3. The cost per unit of each activity.
Let’s examine two examples of cost–benefit–trade-off problems.
The Profit & Gambit Co. Advertising-Mix Problem

As described in Section 2.7, the Profit & Gambit Co. will be undertaking a major new adver-
tising campaign focusing on three cleaning products. The two kinds of advertising to be used
are television and the print media. Management has established minimum goals—the mini-
mum acceptable increase in sales for each product—to be gained by the campaign.
The problem is to determine how much to advertise in each medium to meet all the sales
goals at a minimum total cost.
An initial step in formulat- The activities in this cost–benefit–trade-off problem are
ing any cost–benefit–trade-
off problem is to identify Activity 1: Advertise on television.
the activities and the Activity 2: Advertise in the print media.
benefits.
The benefits being sought from these activities are
Benefit 1: Increased sales for a spray prewash stain remover.
Benefit 2: Increased sales for a liquid laundry detergent.
Benefit 3: Increased sales for a powder laundry detergent.
Management wants these increased sales to be at least 3 percent, 18 percent, and 4 percent,
respectively. As shown in Section 2.7, each benefit leads to a benefit constraint that incor-
porates the managerial goal for the minimum acceptable level of increase in the sales for the
corresponding product, namely,
Level of benefit 1 achieved $ 3%
The data for this problem are given in Table 2.2 (Section 2.7). Section 2.7 describes how
the linear programming model is formulated directly from the numbers in this table.
This example provides an interesting contrast with the Super Grain Corp. case study in
Section 3.1, which led to a formulation as a resource-allocation problem. Both are advertis-
ing-mix problems, yet they lead to entirely different linear programming models. They differ
because of the differences in the managerial view of the key issues in each case:
• As the vice president for marketing of Super Grain, Claire Syverson focused first on how
much to spend on the advertising campaign and then set limits (an advertising budget of
$4 million and a planning budget of $1 million) that led to resource constraints.
hil24064_ch03_064-123.indd 82 02/11/12 4:54 PM

Confirming Pages
Cost control is essential for survival in the airline industry. over a 24-hour day (this minimum changes from day to
Therefore, upper management of United Airlines initiated day over a seven-day week), how many employees of each
a management science study to improve the utilization shift length should begin work at what start time over each
of personnel at the airline’s reservations offices and air- 24-hour day of a seven-day week? Fortunately, linear pro-
ports by matching work schedules to customer needs more gramming thrives on such combinatorial nightmares. The
closely. The number of employees needed at each location linear programming model for some of the locations sched-
to provide the required level of service varies greatly dur- uled involves over 20,000 decisions!
ing the 24-hour day and might fluctuate considerably from This application of linear programming was credited
one half hour to the next. with saving United Airlines more than $6 million annually in
Trying to design the work schedules for all the employ- just direct salary and benefit costs. Other benefits included
ees at a given location to meet these service requirements improved customer service and reduced workloads for sup-
most efficiently is a nightmare of combinatorial consider- port staff.
ations. Once an employee arrives, he or she will be there
continuously for the entire shift (2 to 10 hours, depending
Source: T. J. Holloran and J. E. Bryne, “United Airlines Station
on the employee), except for either a meal break or short Manpower Planning System,” Interfaces 16, no. 1 (January–February
rest breaks every two hours. Given the minimum number 1986), pp. 39–50. (A link to this article is provided on our website,
of employees needed on duty for each half-hour interval www.mhhe.com/hillier5e.)
• The management of Profit & Gambit instead focused on what it wanted the advertising
campaign to accomplish and then set goals (minimum required increases in sales) that led
to benefit constraints.
From this comparison, we see that it is not the nature of the application that determines the
classification of the resulting linear programming formulation. Rather, it is the nature of the
restrictions imposed on the decisions regarding the mix of activity levels. If the restrictions
involve limits on the usage of resources, that identifies a resource-allocation problem. If the
restrictions involve goals on the levels of benefits, that characterizes a cost–benefit–trade-off
problem. Frequently, the nature of the restrictions arise from the way management frames the
problem.
However, we don’t want you to get the idea that every linear programming problem falls
entirely and neatly into either one type or the other. In the preceding section and this one, we
are looking at pure resource-allocation problems and pure cost–benefit–trade-off problems.
Although many real problems tend to be either one type or the other, it is fairly common to
have both resource constraints and benefit constraints, even though one may predominate.
(In the next section, you will see an example of how both types of constraints can arise in
the same problem when the management of the Super Grain Corp. introduces additional con-
siderations into the analysis of their advertising-mix problem.) Furthermore, we still need to
consider additional categories of linear programming problems in the remaining sections of
this chapter.
Now, another example of a pure cost–benefit–trade-off problem.
Personnel Scheduling
One of the common applications of cost–benefit–trade-off analysis involves personnel sched-
uling for a company that provides some kind of service, where the objective is to schedule
the work times of the company’s employees so as to minimize the cost of providing the level
of service specified by management. The following example illustrates how this can be done.
The Problem
Union Airways is adding more flights to and from its hub airport and so needs to hire addi-
tional customer service agents. However, it is not clear just how many more should be hired.
Management recognizes the need for cost control while also consistently providing a satisfac-
tory level of service to the company’s customers, so a desirable trade-off between these two
factors is being sought. Therefore, a management science team is studying how to schedule
the agents to provide satisfactory service with the smallest personnel cost.
83
hil24064_ch03_064-123.indd 83 02/11/12 4:54 PM

Confirming Pages
TABLE 3.5
Time Periods Covered by Shift
Data for the Union
Airways Personnel Minimum Number
Scheduling Problem Time Period 1 2 3 4 5 of Agents Needed
6:00 AM to 8:00 AM ✔ 48
8:00 AM to 10:00 AM ✔ ✔ 79
10:00 AM to noon ✔ ✔ 65
Noon to 2:00 PM ✔ ✔ ✔ 87
2:00 PM to 4:00 PM ✔ ✔ 64
4:00 PM to 6:00 PM ✔ ✔ 73
6:00 PM to 8:00 PM ✔ ✔ 82
8:00 PM to 10:00 PM ✔ 43
10:00 PM to midnight ✔ ✔ 52
Midnight to 6:00 AM ✔ 15
Daily cost per agent $170 $160 $175 $180 $195
Based on the new schedule of flights, an analysis has been made of the minimum number
of customer service agents that need to be on duty at different times of the day to provide a
satisfactory level of service. (The queueing models presented in Chapter 11 can be used to
determine the minimum numbers of agents needed to keep customer waiting times reason-
able.) These numbers are shown in the last column of Table 3.5 for the time periods given in
the first column. The other entries in this table reflect one of the provisions in the company’s
current contract with the union that represents the customer service agents. The provision is
that each agent works an eight-hour shift. The authorized shifts are
Shift 1: 6:00 am to 2:00 pm.
Shift 2: 8:00 am to 4:00 pm.
Shift 3: Noon to 8:00 pm.
Shift 4: 4:00 pm to midnight.
Shift 5: 10:00 pm to 6:00 am.
Check marks in the main body of Table 3.5 show the time periods covered by the respective
shifts. Because some shifts are less desirable than others, the wages specified in the contract
differ by shift. For each shift, the daily compensation (including benefits) for each agent is
shown in the bottom row. The problem is to determine how many agents should be assigned
to the respective shifts each day to minimize the total personnel cost for agents, based on this
bottom row, while meeting (or surpassing) the service requirements given in the last column.
Formulation
This problem is, in fact, a pure cost–benefit–trade-off problem. To formulate the problem, we
need to identify the activities and benefits involved.
Activities correspond to shifts.
The level of each activity is the number of agents assigned to that shift.
A unit of each activity is one agent assigned to that shift.
Thus, the general description of a linear programming problem as finding the best mix of activ-
ity levels can be expressed for this specific application as finding the best mix of shift sizes.
Benefits correspond to time periods.
For each time period, the benefit provided by the activities is the service that agents pro-
vide customers during that period.
The level of a benefit is measured by the number of agents on duty during that time period.
Once again, a careful formulation of the problem, including gathering all the relevant data,
leads rather directly to a spreadsheet model. This model is shown in Figure 3.5, and we out-
line its formulation below.
hil24064_ch03_064-123.indd 84 02/11/12 4:54 PM

Confirming Pages
FIGURE 3.5
The spreadsheet model for the Union Airways problem, including the formulas for the objective cell TotalCost (J21) and the other
output cells TotalWorking (H8:H17), as well as the specifications needed to set up Solver. The changing cells NumberWorking
(C21:G21) show the optimal solution obtained by Solver.
A B C D E F G H I J
1 Union Airways Personnel Scheduling Problem
2
3 6AM–2PM 8AM–4PM Noon–8PM 4PM–Midnight 10PM–6AM
4 Shift Shift Shift Shift Shift
5 Cost per Shift $170 $160 $175 $180 $195
6 Total Minimum
7 Time Period Shift Works Time Period? (1=yes, 0=no) Working Needed
8 6AM–8AM 1 0 0 0 0 48 ≥ 48
9 8AM–10AM 1 1 0 0 0 79 ≥ 79
10 10AM–12PM 1 1 0 0 0 79 ≥ 65
11 12PM–2PM 1 1 1 0 0 118 ≥ 87
12 2PM–4PM 0 1 1 0 0 70 ≥ 64
13 4PM–6PM 0 0 1 1 0 82 ≥ 73
14 6PM–8PM 0 0 1 1 0 82 ≥ 82
15 8PM–10PM 0 0 0 1 0 43 ≥ 43
16 10PM–12AM 0 0 0 1 1 58 ≥ 52
17 12AM–6AM 0 0 0 0 1 15 ≥ 15
18
19 6AM–2PM 8AM–4PM Noon–8PM 4PM–Midnight 10PM–6AM
20 Shift Shift Shift Shift Shift Total Cost
21 Number Working 48 31 39 43 15 $30,610
Solver Parameters H
Set Objective Cell: TotalCost Range Name Cells
To: Min 6 Total
CostPerShift C5:G5
By Changing Variable Cells:
MinimumNeeded J8:J17 7 Working
NumberWorking
Subject to the Constraints: NumberWorking C21:G21 8 =SUMPRODUCT(C8:G8,NumberWorking)
NumberWorking = integer ShiftWorksTimePeriod C8:G17
9 =SUMPRODUCT(C9:G9,NumberWorking)
TotalWorking >= MinimumNeeded TotalCost J21
TotalWorking H8:H17 10 =SUMPRODUCT(C10:G10,NumberWorking)
Solver Options: 11 =SUMPRODUCT(C11:G11,NumberWorking)
Solving Method: Simplex LP 12 =SUMPRODUCT(C12:G12,NumberWorking)
J
20 Total Cost
21 =SUMPRODUCT(CostPerShift,NumberWorking)
The Data As indicated in this figure, all the data in Table 3.5 have been entered directly into
the data cells CostPerShift (C5:G5), ShiftWorksTimePeriod (C8:G17), and MinimumNeeded
(J8:J17). For the ShiftWorksTimePeriod (C8:G17) data, an entry of 1 indicates that the corre-
sponding shift includes that time period whereas 0 indicates not. Like any cost–benefit–trade-
off problem, these numbers indicate the contribution of each activity to each benefit. Each
agent working a shift contributes either 0 or 1 toward the minimum number of agents needed
in a time period.
hil24064_ch03_064-123.indd 85 02/11/12 4:54 PM

Confirming Pages
The Decisions Since the activities in this case correspond to the five shifts, the decisions to
be made are
S1 5 Number of agents to assign to Shift 1 (starts at 6 am)
S2 5 Number of agents to assign to Shift 2 (starts at 8 am)
S3 5 Number of agents to assign to Shift 3 (starts at noon)
S4 5 Number of agents to assign to Shift 4 (starts at 4 pm)
S5 5 Number of agents to assign to Shift 5 (starts at 10 pm)
The changing cells to hold these numbers have been placed in the activity columns in row 21, so
S1 S cell C21 S2 S cell D21 c S5 S cell G21
where these cells are collectively referred to by the range name NumberWorking (C21:G21).
The Constraints These changing cells need to be nonnegative. In addition, we need 10
benefit constraints, where each one specifies that the total number of agents serving in the
corresponding time period listed in column B must be no less than the minimum acceptable
number given in column J. Thus, these constraints are
Total number of agents serving 628 am $ 48 (min. acceptable)
Total number of agents serving 8210 am $ 79 (min. acceptable)
#
#
#
Total number of agents serving midnight26 am $ 15 (min. acceptable)
Since columns C to G indicate which of the shifts serve each of the time periods, these totals
are
Total number of agents serving 628 am 5 S1
Total number of agents serving 8210 am 5 S1 1 S2
#
#
#
Total number of agents serving midnight26 am 5 S5
These totals are calculated in the output cells TotalWorking (H8:H17) using the SUMPROD-
UCT functions shown below the spreadsheet in Figure 3.5.
One other type of constraint is that the number of agents assigned to each shift must have an
integer value. These constraints for the five shifts should be added in the same way as described
for the TBA Airlines problem in Section 3.2. In particular, with Excel’s Solver they are added
in the Add Constraint dialog box by entering NumberWorking on the left-hand side and then
choosing int from the pop-up menu between the left-hand side and the right-hand side. The set
of constraints, NumberWorking 5 integer, then appears in the Solver Parameters, as shown
in Figure 3.5. In RSPE, select the range of cells to be constrained integer, and then under the
Constraint menu on the RSPE ribbon, choose Integer under the Variable Type/Bound submenu.
The Measure of Performance The objective is to
Minimize Cost 5 Total daily personnel cost for all agents
Since CostPerShift (C5:G5) gives the daily cost per agent on each shift and NumberWorking
(C21:G21) gives the number of agents working each shift,
Cost 5 170S1 1 160S2 1 175S3 1 180S4 1 195S5 (in dollars)
5 SUMPRODUCT (CostPerShift, NumberWorking)
S cell J21
Summary of the Formulation The above steps provide the complete formulation of the
linear programming model on a spreadsheet, as summarized below (in algebraic form).
hil24064_ch03_064-123.indd 86 02/11/12 4:54 PM

Confirming Pages
Minimize Cost 5 170S1 1 160S2 1 175S3 1 180S4 1 195S5 (in dollars)

subject to
Total agents 628 am: S1 $ 48
Total agents 8210 am: S1 1 S2 $ 79
#
#
#
Total agents midnight26 am: S5 $ 15
and
S1 $ 0 S2 $ 0 S3 $ 0 S4 $ 0 S5 $ 0
Solving the Model The lower left-hand corner of Figure 3.5 shows the entries needed in
Solver, along with the selection of the usual two options. After solving, NumberWorking
(C21:G21) in the spreadsheet shows the resulting optimal solution for the number of agents
that should be assigned to each shift. TotalCost (J21) indicates that this plan would cost
$30,610 per day.
Summary of the Formulation Procedure for Cost–Benefit–Trade-

Off Problems
The nine steps in formulating any cost–benefit–trade-off problem follow the same pattern as
presented at the end of the preceding section for resource-allocation problems, so we will not
repeat them here. The main differences are that the overall measure of performance now is
the total cost of the activities (or some surrogate of total cost chosen by management) in steps
2 and 3, benefits now replace resources in steps 4 and 5, and $ signs now are entered to the
right of the output cells for benefits in step 8. Figure 3.6 shows a template of the format of a
spreadsheet model for cost–benefit–trade-off problems.
All the functional constraints in the resulting model are benefit constraints, that is, con-
straints with a $ sign. This is the identifying feature of a pure cost–benefit–trade-off problem.
Review 1. What is the difference in managerial objectives between resource-allocation problems and
Questions cost–benefit–trade-off problems?
2. What is the identifying feature of a cost–benefit–trade-off problem?
3. What is the form of a benefit constraint?
4. What are the three kinds of data that need to be gathered for a cost–benefit–trade-off problem?
5. Compare the types of activities for the two examples of cost–benefit–trade-off problems.
6. Compare the types of benefits for the two examples of cost–benefit–trade-off problems.
FIGURE 3.6
A template of a spreadsheet model for pure cost–benefit–trade-off problems.
Activities
Unit Cost Cost per unit of activity

Benefit Benefit
Achieved Needed
Constraints
SUMPRODUCT
Benefit achieved per unit of activity (benefit per unit,
changing cells)
≥
Total Cost
Level of Activity Changing cells SUMPRODUCT(cost per unit, changing cells)
hil24064_ch03_064-123.indd 87 02/11/12 4:54 PM

Confirming Pages
3.4 MIXED PROBLEMS

Sections 3.2 and 3.3 each described a broad category of linear programming problems—
resource-allocation and cost–benefit–trade-off problems. As summarized in Table 3.6, each
features one of the first two types of functional constraints shown there. In fact, the identi-
fying feature of a pure resource-allocation problem is that all its functional constraints are
resource constraints. The identifying feature of a pure cost–benefit–trade-off problem is that
all its functional constraints are benefit constraints. (Keep in mind that the functional con-
straints include all the constraints of a problem except its nonnegativity constraints.)
The bottom row of Table 3.6 shows the last of the three types of functional constraints,
namely, fixed-requirement constraints, which require that the left-hand side of each
such constraint must exactly equal some fixed amount. Thus, since the left-hand side rep-
resents the amount provided of some quantity, the form of a fixed-requirement constraint is
Amount provided 5 Required amount
The identifying feature of a pure fixed-requirements problem is that it is a linear pro-
gramming problem where all its functional constraints are fixed-requirement constraints. The
next two sections will describe two particularly prominent types of fixed-requirement prob-
lems called transportation problems and assignment problems.
However, before turning to these types of problems, we first will use a continuation of the
Super Grain case study from Section 3.1 to illustrate how many linear programming problems
fall into another broad category called mixed problems.
Many linear programming problems do not fit completely into any of the previously discussed
categories (pure resource-allocation problems, cost–benefit–trade-off problems, and fixed-
requirement problems) because the problem’s functional constraints include more than one of
the types shown in Table 3.6. Such problems are called mixed problems.
Now let us see how a more careful analysis of the Super Grain case study turns this resource-
allocation problem into a mixed problem that includes all three types of functional constraints
shown in Table 3.6.
Super Grain Management Discusses Its Advertising-Mix Problem

The description of the Super Grain case study in Section 3.1 ends with Clair Syverson (Super
Grain’s vice president for marketing) sending a memorandum to the company’s president,
David Sloan, requesting a meeting to evaluate her proposed promotional campaign for the
company’s new breakfast cereal.
Soon thereafter, Claire Syverson and David Sloan meet to discuss plans for the campaign.
David Sloan (president): Thanks for your memo, Claire. The plan you outline for the
promotional campaign looks like a reasonable one. However, I am surprised that it does not
make any use of TV commercials. Why is that?
Claire Syverson (vice president for marketing): Well, as I described in my memo,
I used a spreadsheet model to see how to maximize the number of exposures from the
TABLE 3.6
Types of Functional Constraints
Type Form* Typical Interpretation Main Usage

Resource constraint LHS # RHS For some resource, Resource-allocation problems
Amount used # Amount available and mixed problems
Benefit constraint LHS $ RHS For some benefit, Cost–benefit–trade-off problems
Level achieved $ Minimum and mixed problems
acceptable level
Fixed-requirement constraint LHS 5 RHS For some quantity, Fixed-requirements problems
Amount provided 5 Required amount and mixed problems
*LHS 5 Left-hand side (a SUMPRODUCT function).

RHS 5 Right-hand side (a constant).
hil24064_ch03_064-123.indd 88 02/11/12 4:54 PM

Confirming Pages
3.4 Mixed Problems 89
campaign and this turned out to be the plan that does this. I also was surprised that it did not
include TV commercials, but the model indicated that introducing commercials would pro-
vide less exposures on a dollar-for-dollar basis than magazine ads and Sunday supplement
ads. Don’t you think it makes sense to use the plan that maximizes the number of exposures?
David: Not necessarily. Some exposures are a lot less important than others. For example,
we know that middle-aged adults are not big consumers of our cereals, so we don’t care very
much how many of those people see our ads. On the other hand, young children are big con-
sumers. Having TV commercials on the Saturday morning programs for children is our pri-
mary method of reaching young children. You know how important it will be to get young
children to ask their parents for Crunchy Start. That is our best way of generating first-time
sales. Those commercials also get seen by a lot of parents who are watching the programs
with their kids. What we need is a commercial that is appealing to both parents and kids, and
that gets the kids immediately bugging their parents to go buy Crunchy Start. I think that is a
real key to a successful campaign.
Claire: Yes, that makes a lot of sense. In fact, I already have set some goals regarding
the number of young children and the number of parents of young children that need to be
reached by this promotional campaign.
David: Good. Did you include those goals in your spreadsheet model?
Claire: No, I didn’t.
David: Well, I suggest that you incorporate them directly into your model. I suspect that
maximizing exposures while also meeting your goals will give us a high impact plan that
includes some TV commercials.
Claire: Good idea. I’ll try it.
David: Are there any other factors that the plan in your memo doesn’t take into account as
well as you would like?
Claire: Well, yes, one. The plan doesn’t take into account my budget for cents-off cou-
pons in magazines and newspapers.
David: You should be able to add that to your model as well. Why don’t you go back and
see what happens when you incorporate these additional considerations?
Claire: OK, will do. You seem to have had a lot of experience with spreadsheet modeling.
David: Yes. It is a great tool as long as you maintain some healthy skepticism about what
comes out of the model. No model can fully take into account everything that we must con-
sider when dealing with managerial problems. This is especially true the first time or two
you run the model. You need to keep asking, what are the missing quantitative consider-
ations that I still should add to the model? Then, after you have made the model as complete
as possible and obtained a solution, you still need to use your best managerial judgment to
weigh intangible considerations that cannot be incorporated into the model.
Incorporating Additional Managerial Considerations into the

Super Grain Model
Therefore, David and Claire conclude that the spreadsheet model needs to be expanded to
incorporate some additional considerations. In particular, since the promotional campaign
is for a breakfast cereal that should have special appeal to young children, they feel that two
audiences should be targeted—young children and parents of young children. (This is why
one of the three advertising media recommended by Giacomi & Jackowitz is commercials on
children’s television programs Saturday morning.) Consequently, Claire now has set two new
goals for the campaign.
Goal 1: The advertising should be seen by at least five million young children.
Goal 2: The advertising should be seen by at least five million parents of young children.
In effect, these two goals are minimum acceptable levels for two special benefits to be
achieved by the advertising activities.
Benefit 1: Promoting the new breakfast cereal to young children.
Benefit 2: Promoting the new breakfast cereal to parents of young children.
hil24064_ch03_064-123.indd 89 02/11/12 4:54 PM

Confirming Pages
TABLE 3.7
Benefit Data for the Revised Super Grain Corp. Advertising-Mix Problem
Number Reached in Target Category (in millions)

Each TV Each Each Minimum
Target Category Commercial Magazine Ad Sunday Ad Acceptable Level
Young children 1.2 0.1 0 5
Parents of young children 0.5 0.2 0.2 5
Because of the way the goals have been articulated, the level of each of these benefits
is measured by the number of people in the specified category that are reached by the
advertising.
To enable constructing the corresponding benefit constraints (as described in Section 3.3),
Claire asks Giacomi & Jackowitz to estimate how much each advertisement in each of the
media will contribute to each benefit, as measured by the number of people reached in the
specified category. These estimates are given in Table 3.7.
It is interesting to observe that management wants special consideration given to these two
kinds of benefits even though the original spreadsheet model (Figure 3.1) already takes them
into account to some extent. As described in Section 3.1, the expected number of exposures
is the overall measure of performance to be maximized. This measure counts up all the times
that an advertisement is seen by any individual, including all those individuals in the target
Benefit constraints are use- audiences. However, maximizing this general measure of performance does not ensure that
ful for incorporating mana- the two specific goals prescribed by management (Claire Syverson) will be achieved. Claire
gerial goals into the model.
feels that achieving these goals is essential to a successful promotional campaign. Therefore,
she complements the general objective with specific benefit constraints that do ensure that the
goals will be achieved. Having benefit constraints added to incorporate managerial goals into
the model is a prerogative of management.
Claire has one more consideration she wants to incorporate into the model. She is a strong
believer in the promotional value of cents-off coupons (coupons that shoppers can clip from
printed advertisements to obtain a refund of a designated amount when purchasing the adver-
tised item). Consequently, she always earmarks a major portion of her annual marketing bud-
get for the redemption of these coupons. She still has $1,490,000 left from this year’s allotment
for coupon redemptions. Because of the importance of Crunchy Start to the company, she has
decided to use this entire remaining allotment in the campaign promoting this cereal.
This fixed amount for coupon redemptions is a fixed requirement that needs to be expressed
as a fixed-requirement constraint. As described at the beginning of this section, the form of a
fixed-requirement constraint is that, for some type of quantity,
In this case, the quantity involved is the amount of money provided for the redemption of
cents-off coupons. To specify this constraint in the spreadsheet, we need to estimate how
much each advertisement in each of the media will contribute toward fulfilling the required
amount for the quantity. Both medium 2 (advertisements in food and family-oriented maga-
zines) and medium 3 (advertisements in Sunday supplements of major newspapers) will fea-
ture cents-off coupons. The estimates of the amount of coupon redemption per advertisement
in each of these media is given in Table 3.8.
TABLE 3.8
Data for the Fixed-Requirement Constraint for the Revised Super Grain Corp. Advertising-Mix Problem
Contribution toward Required Amount

Each Each Each Required
Requirement TV Spot Magazine Ad Sunday Ad Amount
Coupon redemption 0 $40,000 $120,000 $1,490,000
hil24064_ch03_064-123.indd 90 02/11/12 4:54 PM

Confirming Pages
Formulation of the Revised Spreadsheet Model

Figure 3.7 shows one way of formatting the spreadsheet to expand the original spreadsheet
model in Figure 3.1 to incorporate the additional managerial considerations. We then outline
the four components of the revised model next.
FIGURE 3.7
The spreadsheet model for the revised Super Grain problem, including the formulas for the objective cell TotalExposures (H19)
and the other output cells in column F, as well as the specifications needed to set up Solver. The changing cells NumberOfAds
(C19:E19) show the optimal solution obtained by Solver.
A B C D E F G H
1 Super Grain Corp. Advertising-Mix Problem
2
3 TV Spots Magazine Ads SS Ads
4 Exposures per Ad 1,300 600 500
5 (thousands)
6 Cost per Ad ($thousands) Budget Spent Budget Available
7 Ad Budget 300 150 100 3,775 ≤ 4,000
8 Planning Budget 90 30 40 1,000 ≤ 1,000
9
10 Number Reached per Ad (millions) Total Reached Minimum Acceptable
11 Young Children 1.2 0.1 0 5 ≥ 5
TotalExposures
12 Parents of Young Children 0.5 0.2 0.2 5.85 ≥ 5
($thousands)
13
14 TV Spots Magazine Ads SS Ads Total Redeemed Required Amount
15 Coupon Redemption 0 40 120 1,490 = 1,490
16 per Ad ($thousands)
17 Total Exposures
18 TV Spots Magazine Ads SS Ads (thousands)
19 Number of Ads 3 14 7.75 16,175
20 ≤
21 Maximum TV Spots 5
Solver Parameters F
Set Objective Cell: TotalExposures Range Name Cells
To: Max 6 Budget Spent
By Changing Variable Cells: BudgetAvailable H7:H8
NumberOfAds BudgetSpent F7:F8 7 =SUMPRODUCT(C7:E7,NumberOfAds)
Subject to the Constraints: CostPerAd C7:E8
BudgetSpent <= Budget Available 8 =SUMPRODUCT(C8:E8,NumberOfAds)
TVSpots <= MaxTVSpots CouponRedemptionPerAd C15:E15
9
TotalReached >= MinimumAcceptable ExposuresPerAd C4:E4
TotalRedeemed = RequiredAmount MaxTVSpots C21 10 Total Reached
MinimumAcceptable H11:H12 11 =SUMPRODUCT(C11:E11,NumberOfAds)
Solver Options:
Make Variables Nonnegative NumberOfAds C19:E19
12 =SUMPRODUCT(C12:E12,NumberOfAds)
Solving Method: Simplex LP NumberReachedPerAd C11:E12
RequiredAmount H15 13
TotalExposures H19 14 Total Redeemed
TotalReached F11:F12 15 =SUMPRODUCT(CouponRedemptionPerAd,
TotalRedeemed F15
NumberOfAds)
TVSpots C19
H
17 Total Exposures
18 (thousands)
19 =SUMPRODUCT(ExposuresPerAd,NumberOfAds)
hil24064_ch03_064-123.indd 91 02/11/12 4:54 PM

Confirming Pages
The Data
Additional data cells in NumberReachedPerAd (C11:E12), MinimumAcceptable (H11:H12),
CouponRedemptionPerAd (C15:E15), and RequiredAmount (H15) give the data in
Tables 3.7 and 3.8.
The Decisions
Recall that, as before, the decisions to be made are
TV 5 Number of commercials on television
M 5 Number of advertisements in magazines
SS 5 Number of advertisements in Sunday supplements
The changing cells to hold these numbers continue to be in NumberOfAds (C19:E19).
The Constraints
In addition to the original constraints, we now have two benefit constraints and one fixed-
requirement constraint. As specified in rows 11 and 12, columns F to H, the benefit con-
straints are
Total number of young children reached $ 5 (goal 1 in millions)
Total number of parents reached $ 5 (goal 2 in millions)
Using the data in columns C to E of these rows,
Total number of young children reached 5 1.2TV 1 0.1M 1 0SS

5 SUMPRODUCT (C11:E11, NumberOfAds)
S cell F11
Total number of parents reached 5 0.5TV 1 0.2M 1 0.2SS
5 SUMPRODUCT (C12:E12, NumberOfAds)
S cell F12
These output cells are given the range name TotalReached (F11:F12).
The fixed-requirement constraint indicated in row 15 is that
Total coupon redemption 5 1,490 (allotment in $1,000s)
CouponRedemptionPerAd (C15:E15) gives the number of coupons redeemed per ad, so
Total coupon redemption 5 0TV 1 40M 1 120SS
5 SUMPRODUCT (CouponRedemptionPerAd, NumberOfAds)
S cell F15
These same constraints are specified in Solver, along with the original constraints, in
Figure 3.7.
The Measure of Performance

The measure of performance continues to be
Exposure 5 1,300TV 1 600M 1 500SS
5 SUMPRODUCT (ExposuresPerAd, NumberOfAds)
S cell H19
so the objective cell is again TotalExposures (H19).

The above steps have resulted in formulating the following linear programming model (in
algebraic form) on a spreadsheet.
Maximize Exposure 5 1,300TV 1 600M 1 500SS
hil24064_ch03_064-123.indd 92 02/11/12 4:54 PM

Confirming Pages
subject to the following constraints:

1. Resource constraints:
300TV 1 150M 1 100SS # 4,000 (ad budget in $1,000s)
90TV 1 30M 1 40SS # 1,000 (planning budget in $1,000s)
TV # 5 (television spots available)
2. Benefit constraints:
1.2TV 1 0.1M $5 (millions of young children)
0.5TV 1 0.2M 1 0.2SS $ 5 (millions of parents)
3. Fixed-requirement constraint:
40M 1 120SS 5 1,490 (coupon budget in $1,000s)
4. Nonnegativity constraints:
TV $ 0 M$0 SS $ 0
Solving the Model

The lower left-hand corner of Figure 3.7 shows the entries needed in Solver, along with the
selection of the usual two options. Solver then finds the optimal solution given in row 19.
This optimal solution provides the following plan for the promotional campaign:
Run 3 television commercials.
Run 14 advertisements in magazines.
Run 7.75 advertisements in Sunday supplements (so the eighth advertisement would
appear in only 75 percent of the newspapers).
Although the expected number of exposures with this plan is only 16,175,000, versus the
17,000,000 with the first plan shown in Figure 3.1, both Claire Syverson and David Sloan
feel that the new plan does a much better job of meeting all of management’s goals for this
campaign. They decide to adopt the new plan.
A model may need to be This case study illustrates a common theme in real applications of linear programming—
modified a number of times the continuing evolution of the linear programming model. It is common to make later adjust-
before it adequately incor-
ments in the initial version of the model, perhaps even many times, as experience is gained
porates all the important
considerations. in using the model. Frequently, these adjustments are made to more adequately reflect some
important managerial considerations. This may result in a mixed problem because the new
functional constraints needed to incorporate the managerial considerations may be of a differ-
ent type from those in the original model.
Other Examples
This case study provides a relatively simple example of a small mixed problem. Most of
the mixed problems that arise in practice are much larger, sometimes involving hundreds or
thousands of activities and hundreds or thousands of constraints. At first glance, these larger
problems may seem considerably more complicated than the case study. However, the impor-
tant thing to remember is that any linear programming problem can have only three types
of functional constraints—resource constraints, benefit constraints, and fixed-requirement
constraints—where each type is formulated just as illustrated above for the case study.
There are numerous kinds of managerial problems to which linear programming can be
applied. We don’t have nearly enough space available to give examples of all the most impor-
tant kinds of applications. However, if you would like to explore this further, we suggest that
you go through the five solved problems that are summarized in front of the Problems sec-
tion for this chapter. Reading the seven cases that follow the Problems section, as well as the
application vignettes in both this chapter and the preceding chapter, also will further illustrate
the unusually wide applicability of linear programming.
Meanwhile, we soon will turn to two more categories of linear programming problems in
the next two sections.
hil24064_ch03_064-123.indd 93 02/11/12 4:54 PM

Confirming Pages
Summary of the Formulation Procedure for Mixed Linear

Programming Problems
The procedure for formulating mixed problems is similar to the one outlined at the end of
Section 3.2 for resource-allocation problems. However, pure resource-allocation prob-
lems only have resource constraints whereas mixed problems can include all three types
of functional constraints (resource constraints, benefit constraints, and fixed-requirement
constraints). Therefore, the following summary for formulating mixed problems includes
separate steps for dealing with these different types of constraints. Also see Figure 3.8 for a
template of the format for a spreadsheet model of mixed problems. (This format works well
for most mixed problems, including those encountered in this chapter, but more flexibility is
occasionally needed, as will be illustrated in the next chapter.)
1. Since any linear programming problem involves finding the best mix of levels of various
activities, identify these activities for the problem at hand. The decisions to be made are
the levels of these activities.
2. From the viewpoint of management, identify an appropriate overall measure of perfor-
mance for solutions of the problem.
3. For each activity, estimate the contribution per unit of the activity to this overall measure
of performance.
4. Identify any resources that must be allocated to the activities (as described in Section 3.2).
For each one, identify the amount available and then the amount used per unit of each
activity.
5. Identify any benefits to be obtained from the activities (as described in Section 3.3). For
each one, identify the minimum acceptable level prescribed by management and then the
benefit contribution per unit of each activity.
6. Identify any fixed requirements that, for some type of quantity, the amount provided must
equal a required amount (as described in Section 3.4). For each fixed requirement, identify
the required amount and then the contribution toward this required amount per unit of
each activity.
FIGURE 3.8
A template of a spreadsheet model for mixed problems.
Activities
Unit Profit or Cost Profit/cost per unit of activity

Resources Resources
Used Available
≤
SUMPRODUCT
Resource used per unit of activity (resource used per unit,
changing cells)
Constraints
Benefit Benefit
Achieved Needed
Benefit achieved per unit of activity

SUMPRODUCT
(benefit per unit,
≥
changing cells)
=
Total Profit or Cost
Level of Activity Changing cells SUMPRODUCT(profit/cost per unit, changing cells)
hil24064_ch03_064-123.indd 94 02/11/12 4:54 PM

Confirming Pages
3.5 Transportation Problems 95
7. Enter the data gathered in steps 3–6 into data cells in a spreadsheet.
8. Designate changing cells for displaying the decisions on activity levels.
9. Use output cells to specify the constraints on resources, benefits, and fixed requirements.
10. Designate an objective cell for displaying the overall measure of performance.
Review 1. What types of functional constraints can appear in a mixed linear programming problem?
Questions 2. What managerial goals needed to be incorporated into the expanded linear programming
model for the Super Grain Corp. problem?
3. Which categories of functional constraints are included in the new linear programming model?
4. Why did management adopt the new plan even though it provides a smaller expected number
of exposures than the original plan recommended by the original linear programming model?
3.5 TRANSPORTATION PROBLEMS

One of the most common applications of linear programming involves optimizing a shipping
plan for transporting goods. In a typical application, a company has several plants producing
a certain product that needs to be shipped to the company’s customers (or perhaps to distribu-
tion centers). How much should each plant ship to each customer in order to minimize the
total cost? Linear programming can provide the answer. This type of linear programming
problem is called a transportation problem.
This kind of application normally needs two kinds of functional constraints. One kind
specifies that the amount of the product produced at each plant must equal the total amount
shipped to customers. The other kind specifies that the total amount received from the plants
by each customer must equal the amount ordered. These are fixed-requirement constraints,
which makes the problem a fixed-requirements problem. However, there also are variations
of this problem where resource constraints or benefit constraints are needed.
Transportation problems and assignment problems (described in the next section) are such
important types of linear programming problems that the entire Chapter 15 on the CD-ROM
is devoted to further describing these two related types of problems and providing examples
of a wide variety of applications.
We provide below an example of a typical transportation problem.
The Big M Company Transportation Problem

The Big M Company produces a variety of heavy duty machines at two factories. One of
its products is a large turret lathe. Orders have been received from three customers to pur-
chase some of these turret lathes next month. These lathes will be shipped individually, and
Table 3.9 shows what the cost will be for shipping each lathe from each factory to each cus-
tomer. This table also shows how many lathes have been ordered by each customer and how
many will be produced by each factory. The company’s distribution manager now wants to
determine how many machines to ship from each factory to each customer to minimize the
total shipping cost.
Figure 3.9 depicts the distribution network for this problem. This network ignores the geo-
graphical layout of the factories and customers and instead lines up the two factories in one
column on the left and the three customers in one column on the right. Each arrow shows one
of the shipping lanes through this distribution network.
TABLE 3.9
Shipping Cost for Each Lathe
Some Data for the Big M
Company Distribution- To Customer 1 Customer 2 Customer 3 Output
Network Problem From
Factory 1 $700 $900 $800 12 lathes
Factory 2 800 900 700 15 lathes
Order size 10 lathes 8 lathes 9 lathes
hil24064_ch03_064-123.indd 95 02/11/12 4:54 PM

Confirming Pages
FIGURE 3.9 10 lathes

The distribution network C1
needed
for the Big M Company
problem. the
0/la
$70
12 lathes $900/la
F1 the
produced $8
00
/la
the 8 lathes
C2
needed
e
th
/la
00
e
/lath
$8
15 lathes $900
F2
produced
$70
0/la
the
9 lathes
C3
needed
Formulation of the Problem in Linear Programming Terms

We need to identify the activities and requirements of this transportation problem to for-
mulate it as a linear programming problem. In this case, two kinds of activities have been
mentioned—the production of the turret lathes at the two factories and the shipping of these
lathes along the various shipping lanes. However, we know the specific amounts to be pro-
duced at each factory, so no decisions need to be made about the production activities. The
decisions to be made concern the levels of the shipping activities—how many lathes to ship
through each shipping lane. Therefore, we need to focus on the shipping activities for the
linear programming formulation.
The activities correspond to shipping lanes, depicted by arrows in Figure 3.9.
The level of each activity is the number of lathes shipped through the corresponding ship-
ping lane.
Just as any linear programming problem can be described as finding the best mix of activ-
ity levels, this one involves finding the best mix of shipping amounts for the various shipping
lanes. The decisions to be made are
SF1-C1 5 Number of lathes shipped from Factory 1 to Customer 1
so six changing cells will be needed in the spreadsheet.
The objective is to
Minimize Cost 5 Total cost for shipping the lathes
Using the shipping costs given in Table 3.9,
Cost 5 700SF1-C1 1 900SF1-C2 1 800SF1-C3 1 800SF1-C1 1 900SF2-C2 1 700SF2-C3
is the quantity in dollars to be entered into the objective cell. (We will use a SUMPRODUCT
function to do this a little later.)
hil24064_ch03_064-123.indd 96 02/11/12 4:54 PM

Confirming Pages
Procter & Gamble (P & G) makes and markets over 300 the number of North American plants by almost 20 percent,
brands of consumer goods worldwide. The company has saving over $200 million in pretax costs per year.
grown continuously over its long history tracing back to A major part of the study revolved around formulating
the 1830s. To maintain and accelerate that growth, a major and solving transportation problems for individual prod-
management science study was undertaken to strengthen uct categories. For each option regarding keeping certain
P & G’s global effectiveness. Prior to the study, the com- plants open, and so forth, solving the corresponding trans-
pany’s supply chain consisted of hundreds of suppliers, over portation problem for a product category showed what
50 product categories, over 60 plants, 15 distribution cen- the distribution cost would be for shipping the product
ters, and over 1,000 customer zones. However, as the com- category from those plants to the distribution centers and
pany moved toward global brands, management realized customer zones.
that it needed to consolidate plants to reduce manufactur-
ing expenses, improve speed to market, and reduce capital Source: J. D. Camm, T. E. Chorman, F. A. Dill, J. R. Evans,
D. J. Sweeney, and G. W. Wegryn, “Blending OR/MS, Judgment,
investment. Therefore, the study focused on redesigning and GIS: Restructuring P & G’s Supply Chain,” Interfaces 27, no. 1
the company’s production and distribution system for its (January–February 1997), pp. 128–142. (A link to this article is pro-
North American operations. The result was a reduction in vided on our website, www.mhhe.com/hillier5e.)
The spreadsheet model also will need five constraints involving fixed requirements. Both
Table 3.9 and Figure 3.9 show these requirements.
Requirement 1: Factory 1 must ship 12 lathes.
Requirement 2: Factory 2 must ship 15 lathes.
Requirement 3: Customer 1 must receive 10 lathes.
Thus, there is a specific requirement associated with each of the five locations in the distribu-
tion network shown in Figure 3.9.
All five of these requirements can be expressed in constraint form as
For example, Requirement 1 can be expressed algebraically as
SF1-C1 1 SF1-C2 1 SF1-C3 5 12
where the left-hand side gives the total number of lathes shipped from Factory 1, and 12 is the
required amount to be shipped from Factory 1. Therefore, this constraint restricts SF1-C1, SF1-C2,
and SF1-C3 to values that sum to the required amount of 12. In contrast to the # form for
resource constraints and the $ form for benefit constraints, the constraints express fixed
requirements that must hold with equality, so this transportation problem falls into the category
of fixed-requirements problems introduced in the preceding section. However, Chapter 15 (on
the CD-ROM) gives several examples that illustrate how variants of transportation problems
can have resource constraints or benefit constraints as well. For example, if 12 lathes represent
the manufacturing capacity of Factory 1 (the maximum number that can be shipped) rather
than a requirement for how many must be shipped, the constraint just given for Requirement
1 would become a # resource constraint instead. Such variations can be incorporated readily
into the spreadsheet model.
Formulation of the Spreadsheet Model

Careful problem formula- In preparation for formulating the model, the problem has been formulated above by iden-
tion needs to precede model tifying the decisions to be made, the constraints on these decisions, and the overall mea-
formulation.
sure of performance, as well as gathering all the important data displayed in Table 3.9. All
this information leads to the spreadsheet model shown in Figure 3.10. The data cells include
ShippingCost (C5:E6), Output (H11:H12), and OrderSize (C15:E15), incorporating all the
data from Table 3.9. The changing cells are UnitsShipped (C11:E12), which give the deci-
sions on the amounts to be shipped through the respective shipping lanes. The output cells
are TotalShippedOut (F11:F12) and TotalToCustomer (C13:E13), where the SUM functions
97
hil24064_ch03_064-123.indd 97 02/11/12 4:54 PM

Confirming Pages
Here is an example where entered into these cells are shown below the spreadsheet in Figure 3.10. The constraints are
SUM functions are used that TotalShippedOut is required to equal Output and TotalToCustomer is required to equal
for output cells instead of
SUMPRODUCT functions.
OrderSize. These constraints have been specified on the spreadsheet and entered into Solver.
The objective cell is TotalCost (H15), where its SUMPRODUCT function gives the total
shipping cost. The lower left-hand corner of Figure 3.10 shows the entries needed in Solver,
along with the selection of the usual two options.
The layout of the spreadsheet is different than for all the prior linear programming exam-
ples in the book. Rather than a separate column for each activity and a separate row for each
constraint, the cost data and changing cells are laid out in a table format. This format provides
a more natural and compact way of displaying the constraints and results.
UnitsShipped (C11:E12) in the spreadsheet in Figure 3.10 shows the result of applying
Solver to obtain an optimal solution for the number of lathes to ship through each shipping
lane. TotalCost (H15) indicates that the total shipping cost for this shipping plan is $20,500.
Since any transportation problem is a special type of linear programming problem, it
makes the standard assumption that fractional solutions are allowed. However, we actually
don’t want this assumption for this particular application since only integer numbers of lathes
FIGURE 3.10
The spreadsheet model for the Big M Company problem, including the formulas for the objective cell TotalCost (H15) and the other
output cells TotalShippedOut (F11:F12) and TotalToCustomer (C13:E13), as well as the specifications needed to set up Solver. The
changing cells UnitsShipped (C11:E12) show the optimal solution obtained by Solver.
A B C D E F G H
1 Big M Company Distribution Problem
2
3 Shipping Cost
4 (per Lathe) Customer 1 Customer 2 Customer 3
5 Factory 1 $700 $900 $800
6 Factory 2 $800 $900 $700
7
8 Total
9 Shipped
10 Units Shipped Customer 1 Customer 2 Customer 3 Out Output
11 Factory 1 10 2 0 12 = 12
12 Factory 2 0 6 9 15 = 15
13 Total to Customer 10 8 9
14 = = = Total Cost
15 Order Size 10 8 9 $20,500
Solver Parameters F
Range Name Cells
Set Objective Cell: TotalCost
To: Min 8 Total
OrderSize C15:E15
By Changing Variable Cells: 9
Output H11:H12 Shipped
UnitsShipped
Subject to the Constraints: ShippingCost C5:E6 10 Out
TotalShippedOut = Output TotalCost H15
11 =SUM(C11:E11)
TotalToCustomer = OrderSize TotalShippedOut F11:F12
TotalToCustomer C13:E13 12 =SUM(C12:E12)
Solver Options: UnitsShipped C11:E12
Solving Method: Simplex LP B C D E
13 Total to Customer =SUM(C11:C12) =SUM(D11:D12) =SUM(E11:E12)
H
14 Total Cost
15 =SUMPRODUCT(ShippingCost,UnitsShipped)
hil24064_ch03_064-123.indd 98 02/11/12 4:54 PM

Confirming Pages
3.6 Assignment Problems 99
can be shipped from a factory to a customer. Fortunately, even while making the standard
assumption, the numbers in the optimal solution shown in UnitsShipped (C11:E12) only have
integer values. This is no coincidence. Because of the form of its model, almost any trans-
portation problem (including this one) is guaranteed in advance to have an optimal solution
that has only integer values despite the fact that fractional solutions also are allowed. In par-
ticular, as long as the data for the problem includes only integer values for all the supplies
and demands (which are the outputs and order sizes in the Big M Company problem), any
transportation problem with feasible solutions is guaranteed to have an optimal solution with
integer values for all its decision variables. Therefore, it is not necessary to add constraints to
the model that require these variables to have only integer values.
To summarize, here is the algebraic form of the linear programming model that has been
formulated in the spreadsheet:
Minimize Cost 5 700SF1-C1 1 900SF1-C2 1 800SF1-C3 1 800SF2-C1
1 900SF2-C2 1 700SF2-C3
subject to the following constraints:
1. Fixed-requirement constraints:
SF1-C1 1 SF1-C2 1 SF1-C3 5 12 (Factory 1)
SF2-C1 1 SF2-C2 1 SF2-C3 5 15 (Factory 2)
SF1-C1 1 SF2-C1 5 10 (Customer 1)
2. Nonnegativity constraints:
SF1-C1 $ 0 SF1-C2 $ 0 SF1-C3 $ 0 SF2-C1 $ 0 SF2-C2 $ 0 SF2-C3 $ 0
Review 1. Why are transportation problems given this name?

Questions 2. What is an identifying feature of transportation problems?
3. How does the form of a fixed-requirement constraint differ from that of a resource constraint?
A benefit constraint?
4. What are the quantities with fixed requirements in the Big M Company problem?
3.6 ASSIGNMENT PROBLEMS

We now turn to another special type of linear programming problem called assignment
problems. As the name suggests, this kind of problem involves making assignments.
Frequently, these are assignments of people to jobs. Thus, many applications of the assignment
problem involve aiding managers in matching up their personnel with tasks to be performed.
Other applications might instead involve assigning machines, vehicles, or plants to tasks.
Here is a typical example.
An Example: The Sellmore Company Problem

The marketing manager of the Sellmore Company will be holding the company’s annual
sales conference soon for sales regional managers and personnel. To assist in the administra-
tion of the conference, he is hiring four temporary employees (Ann, Ian, Joan, and Sean),
where each will handle one of the following four tasks:
1. Word processing of written presentations.
2. Computer graphics for both oral and written presentations.
3. Preparation of conference packets, including copying and organizing written materials.
4. Handling of advance and on-site registrations for the conference.
He now needs to decide which person to assign to each task.
hil24064_ch03_064-123.indd 99 02/11/12 4:54 PM

Confirming Pages
TABLE 3.10 Required Time per Task (Hours)

Data for the Sellmore
Co. Problem Temporary Word Hourly
Employee Processing Graphics Packets Registrations Wage
Ann 35 41 27 40 $14
Ian 47 45 32 51 12
Joan 39 56 36 43 13
Sean 32 51 25 46 15
Decisions need to be made Although each temporary employee has at least the minimal background necessary to per-
regarding which person to form any of the four tasks, they differ considerably in how efficiently they can handle the dif-
assign to each task.
ferent types of work. Table 3.10 shows how many hours each would need for each task. The
rightmost column gives the hourly wage based on the background of each employee.
Formulation of a Spreadsheet Model

Using Cost (D15:G18), Figure 3.11 shows a spreadsheet model for this problem. Table 3.10 is entered at the top. Com-
the objective is to mini- bining these required times and wages gives the cost (cells D15:G18) for each possible assign-
mize the total cost of the
ment of a temporary employee to a task, using equations shown at the bottom of Figure 3.11.
assignments.
This cost table is just the way that any assignment problem is displayed. The objective is to
determine which assignments should be made to minimize the sum of the associated costs.
A value of 1 in a chang- The values of 1 in Supply (J24:J27) indicate that each person (assignee) listed in column
ing cell indicates that the C must perform exactly one task. The values of 1 in Demand (D30:G30) indicate that each
corresponding assignment
task must be performed by exactly one person. These requirements then are specified in the
is being made, whereas 0
means that the assignment constraints given in Solver.
is not being made. Each of the changing cells Assignment (D24:G27) is given a value of 1 when the corre-
sponding assignment is being made, and a value of 0 otherwise. Therefore, the Excel equation
for the objective cell, TotalCost 5 SUMPRODUCT(Cost, Assignment), gives the total cost
Excel Tip: When solving for the assignments being made. The Solver Parameters box specifies that the goal is to mini-
an assignment problem, mize this objective cell.
rounding errors occasion-
The changing cells in Figure 3.11 show the optimal solution obtained after running Solver.
ally will cause Excel
to return a noninteger This solution is
value very close to 0
Assign Ann to prepare conference packets.
(e.g., 1.23 E-10, meaning
0.000000000123) or very Assign Ian to do the computer graphics.
close to 1 (e.g., 0.9999912). Assign Joan to handle registrations.
To make the spreadsheet
cleaner, you may replace Assign Sean to do the word processing.
these “ugly” representations
The total cost given in cell J30 is $1,957.
by their proper value of 0 or
1 in the changing cells.
Characteristics of Assignment Problems
Note that all the functional constraints of the Sellmore Co. problem (as shown in cells H24:J27
and D28:G30 of Figure 3.11) are fixed-requirement constraints which require each person to
perform exactly one task and require each task to be performed by exactly one person. Thus,
like the Big M Company transportation problem, the Sellmore Co. is a fixed-requirements
problem. This is a characteristic of all pure assignment problems. However, Chapter 15 (on the
CD-ROM) gives some examples of variants of assignment problems where this is not the case.
Like the changing cells Assignment (D24:G27) in Figure 3.11, the changing cells in
the spreadsheet model for any pure assignment problem gives a value of 1 when the corre-
sponding assignment is being made, and a value of 0 otherwise. Since the fixed-requirement
constraints require only each row or column of changing cells to add up to 1 (which could
happen, e.g., if two of the changing cells in the same row or column had a value of 0.5 and the
rest 0), this would seem to necessitate adding the constraints that each of the changing cells
must be integer. After choosing the Solver option to make the changing cells nonnegative,
this then would force each of the changing cells to be 0 or 1. However, it turned out to be
unnecessary to add the constraints that require the changing cells to have values of 0 or 1 in
hil24064_ch03_064-123.indd 100 02/11/12 4:54 PM

Confirming Pages
3.6 Assignment Problems 101
FIGURE 3.11
A spreadsheet formulation of the Sellmore Co. problem as an assignment problem, including the objective cell TotalCost (J30) and
the other output cells Cost (D15:G18), TotalAssignments (H24:H27), and TotalAssigned (D28:G28), as well as the specifications
needed to set up the model. The values of 1 in the changing cells Assignment (D24:G27) show the optimal plan obtained by Solver
for assigning the people to the tasks.
A B C D E F G H I J
1 Sellmore Co. Assignment Problem
2
3 Task
4 Required Time Word Hourly
5 (Hours) Processing Graphics Packets Registrations Wage
6 Ann 35 41 27 40 $14
7 Assignee Ian 47 45 32 51 $12
8 Joan 39 56 36 43 $13
9 Sean 32 51 25 46 $15
10
11
12 Task
13 Word
14 Cost Processing Graphics Packets Registrations
15 Ann $490 $574 $378 $560
16 Assignee Ian $564 $540 $384 $612
17 Joan $507 $728 $468 $559
18 Sean $480 $765 $375 $690
19
20
21 Task
22 Assignment Word Total
23 Processing Graphics Packets Registrations Assignments Supply
24 Ann 0 0 1 0 1 = 1
25 Assignee Ian 0 1 0 0 1 = 1
26 Joan 0 0 0 1 1 = 1
27 Sean 1 0 0 0 1 = 1
28 Total Assigned 1 1 1 1
29 = = = = Total Cost
30 Demand 1 1 1 1 $1,957
B C D E F G H
13 Word 22 Total
14 Cost Processing Graphics Packets Registrations 23 Assignments
15 Ann =D6*I6 =E6*I6 =F6*I6 =G6*I6 24 =SUM(D24:G24)
16 Assignee Ian =D7*I7 =E7*I7 =F7*I7 =G7*I7 25 =SUM(D25:G25)
17 Joan =D8*I8 =E8*I8 =F8*I8 =G8*I8 26 =SUM(D26:G26)
18 Sean =D9*I9 =E9*I9 =F9*I9 =G9*I9 27 =SUM(D27:G27)
Solver Parameters
Range Name Cells
Set Objective Cell: TotalCost
To: Min Assignment D24:G27
By Changing Variable Cells: Cost D15:G18
Assignment J Demand D30:G30
Subject to the Constraints: 29 Total Cost HourlyWage I6:I9
TotalAssigned = Demand RequiredTime D6:G9
TotalAssignments = Supply 30 =SUMPRODUCT(Cost,Assignment) Supply J24:J27
TotalAssigned D28:G28
Solver Options: TotalAssignments H24:H27
Make Variables Nonnegative TotalCost J30
Solving Method: Simplex LP
C D E F G
28 Total Assigned =SUM(D24:D27) =SUM(E24:E27) =SUM(F24:F27) =SUM(G24:G27)
hil24064_ch03_064-123.indd 101 02/11/12 4:54 PM

Confirming Pages
Figure 3.11 because Solver gave an optimal solution that had only values of 0 or 1 anyway. In
fact, a general characteristic of pure assignment problems is that Solver always provides such
an optimal solution without needing to add these additional constraints.
As described further in Chapter 15, another interesting characteristic of any pure assign-
ment problem is that it can be viewed as a special type of pure transportation problem. In
particular, every fixed-requirement constraint in the corresponding transportation problem
would require that either a row or column of changing cells add up to 1. This would result in
Solver giving an optimal solution where every changing cell has a value of either 0 or 1, just
as for the original assignment problem.
Review 1. Why are assignment problems given this name?

Questions 2. Pure assignment problems have what type of functional constraints?
3. What is the interpretation of the changing cells in the spreadsheet model of a pure assignment
problem?
3.7 MODEL FORMULATION FROM A BROADER PERSPECTIVE

Formulating and analyzing a linear programming model provides information to help manag-
ers make their decisions. That means the model must accurately reflect the managerial view
of the problem:
Both the measure of perfor- • The overall measure of performance must capture what management wants accomplished.
mance and the constraints
• When management limits the amounts of resources that will be made available to the activ-
in a model need to reflect
the managerial view of the ities under consideration, these limitations should be expressed as resource constraints.
problem. • When management establishes minimum acceptable levels for benefits to be gained from
the activities, these managerial goals should be incorporated into the model as benefit
constraints.
• If management has fixed requirements for certain quantities, then fixed-requirement con-
straints are needed.
With the help of spreadsheets, some managers now are able to formulate and solve small
linear programming models themselves. However, larger linear programming models may be
formulated by management science teams, not managers. When this is done, the management
science team must thoroughly understand the managerial view of the problem. This requires
clear communication with management from the very beginning of the study and maintaining
effective communication as new issues requiring managerial guidance are identified. Man-
agement needs to clearly convey its view of the problem and the important issues involved.
A manager cannot expect to obtain a helpful linear programming study without making clear
just what help is wanted.
Linear programming stud- As is necessary in any textbook, the examples in this chapter are far smaller, simpler, and
ies need strong managerial more clearly spelled out than is typical of real applications. Many real studies require formu-
input and support.
lating complicated linear programming models involving hundreds or thousands of decisions
and constraints. In these cases, there usually are many ambiguities about just what should be
incorporated into the model. Strong managerial input and support are vital to the success of a
linear programming study for such complex problems.
When dealing with huge real problems, there is no such thing as “the” correct linear pro-
gramming model for the problem. The model continually evolves throughout the course of the
study. Early in the study, various techniques are used to test initial versions of the model to
identify the errors and omissions that inevitably occur when constructing such a large model.
This testing process is referred to as model validation.
Once the basic formulation has been validated, there are many reasonable variations of the
model that might be used. Which variation to use depends on such factors as the assumptions
about the problem that seem most reasonable, the estimates of the parameters of the model
that seem most reliable, and the degree of detail desired in the model.
In large linear programming studies, a good approach is to begin with a relatively simple
version of the model and then use the experience gained with this model to evolve toward
hil24064_ch03_064-123.indd 102 02/11/12 4:54 PM

Confirming Pages
3.8 Summary 103
more elaborate models that more nearly reflect the complexity of the real problem. This pro-
cess of model enrichment continues only as long as the model remains reasonably easy
to solve. It must be curtailed when the study’s results are needed by management. Managers
often need to curb the natural instinct of management science teams to continue adding “bells
and whistles” to the model rather than winding up the study in a timely fashion with a less
elegant but adequate model.
When managers study the output of the current model, they often detect some undesirable
characteristics that point toward needed model enrichments. These enrichments frequently
take the form of new benefit constraints to satisfy some managerial goals not previously
articulated. (Recall that this is what happened in the Super Grain case study.)
What-if analysis addresses Even though many reasonable variations of the model could be used, an optimal solution can
some key questions that be solved for only with respect to one specific version of the model at a time. This is why what-
remain after formulating
if analysis is such an important part of a linear programming study. After obtaining an optimal
and solving a model.
solution with respect to one specific model, management will have many what-if questions:
• What if the estimates of the parameters in the model are incorrect?
• How do the conclusions change if different plausible assumptions are made about the
problem?
• What happens when certain managerial options are pursued that are not incorporated into
the current model?
Chapter 5 is devoted primarily to describing how what-if analysis addresses these and related
issues, as well as how managers use this information.
Because managers instigate management science studies, they need to know enough about
linear programming models and their formulation to be able to recognize managerial prob-
lems to which linear programming can be applied. Furthermore, since managerial input is so
important for linear programming studies, managers need to understand the kinds of manage-
rial concerns that can be incorporated into the model. Developing these two skills have been
the most important goals of this chapter.
Review 1. A linear programming model needs to reflect accurately whose view of the problem?
Questions 2. What is meant by model validation?
3. What is meant by the process of model enrichment?
4. Why is what-if analysis an important part of a linear programming study?
3.8 Summary Functional constraints with a # sign are called resource constraints, because they require that the
amount used of some resource must be less than or equal to the amount available of that resource. The
identifying feature of resource-allocation problems is that all their functional constraints are resource
constraints.
Functional constraints with a $ sign are called benefit constraints, since their form is that the level
achieved for some benefit must be greater than or equal to the minimum acceptable level for that
benefit. Frequently, benefit constraints express goals prescribed by management. If every functional
constraint is a benefit constraint, then the problem is a cost–benefit–trade-off problem.
Functional constraints with an 5 sign are called fixed-requirement constraints, because they express
the fixed requirement that, for some quantity, the amount provided must be equal to the required amount.
The identifying feature of fixed-requirements problems is that their functional constraints are fixed-
requirement constraints. One prominent type of fixed-requirements problem is transportation problems,
which typically involve finding a shipping plan that minimizes the total cost of transporting a product from
a number of plants to a number of customers. Another prominent type is assignment problems, which typi-
cally involves assigning people to tasks so as to minimize the total cost of performing these tasks.
Linear programming problems that do not fit into any of these three categories are called mixed
problems.
In many real applications, management science teams formulate and analyze large linear program-
ming models to help guide managerial decision making. Such teams need strong managerial input and
support to help ensure that their work really meets management’s needs.
hil24064_ch03_064-123.indd 103 02/11/12 4:54 PM

Confirming Pages
Glossary assignment problem A type of linear program- integer programming problem A variation of a
ming problem that typically involves assigning linear programming problem that has the additional
people to tasks so as to minimize the total cost of restriction that some or all of the decision variables
performing these tasks. (Section 3.6), 99 must have integer values. (Section 3.2), 75
benefit constraint A functional constraint with mixed problem Any linear programming prob-
a $ sign. The left-hand side is interpreted as lem that includes at least two of the three types
the level of some benefit that is achieved by the of functional constraints (resource constraints,
activities under consideration, and the right-hand benefit constraints, and fixed-requirement con-
side is the minimum acceptable level for that ben- straints). (Section 3.4), 88
efit. (Section 3.3), 82 model enrichment The process of using expe-
cost–benefit–trade-off problem A type of rience with a model to identify and add important
linear programming problem involving the details that will provide a better representation of
trade-off between the total cost of the activi- the real problem. (Section 3.7), 103
ties under consideration and the benefits to be model validation The process of checking and
achieved by these activities. Its identifying fea- testing a model to develop a valid model.
ture is that each functional constraint in the lin- (Section 3.7), 102
ear programming model is a benefit constraint. resource-allocation problem A type of linear
(Section 3.3), 82 programming problem concerned with allocating
fixed-requirement constraint A functional resources to activities. Its identifying feature is
constraint with an 5 sign. The left-hand side rep- that each functional constraint in its model is a
resents the amount provided of some type of quan- resource constraint. (Section 3.2), 71
tity, and the right-hand side represents the required resource constraint A functional constraint
amount for that quantity. (Section 3.4), 88 with a # sign. The left-hand side represents the
fixed-requirements problem A type of linear amount of some resource that is used by the
programming problem concerned with optimiz- activities under consideration, and the right-
ing how to meet a number of fixed requirements. hand side represents the amount available of that
Its identifying feature is that each functional resource. (Section 3.2), 71
constraint in its model is a fixed-requirement transportation problem A type of linear pro-
constraint. (Section 3.4), 88 gramming problem that typically involves finding
identifying feature A feature of a model that a shipping plan that minimizes the total cost of
identifies the category of linear programming transporting a product from a number of plants to
problem it represents. (Chapter introduction), 64 a number of customers. (Section 3.5), 95
Learning Aids for This Chapter in Your MS Courseware

Chapter 3 Excel Files: Big M Example
Super Grain Example Revised Super Grain Example
TBA Airlines Example Sellmore Example
Think-Big Example Excel Add-in:
Union Airways Example Risk Solver Platform for Education (RSPE)
Solved Problems (See the CD-ROM or Website for the Solutions)

3.S1. Farm Management
Labor Fertilizer
Dwight and Hattie have run the family farm for over 30 years. Required Required Expected
They are currently planning the mix of crops to plant on their (hours per (tons per Profit (per
120-acre farm for the upcoming season. The table gives the
Crop acre) acre) acre)
labor-hours and fertilizer required per acre, as well as the total
expected profit per acre for each of the potential crops under Oats 50 1.5 $500
consideration. Dwight, Hattie, and their children can work at Wheat 60 2 $600
most 6,500 total hours during the upcoming season. They have Corn 105 4 $950
200 tons of fertilizer available. What mix of crops should be
planted to maximize the family’s total profit? 3.S2. Diet Problem
a. Formulate and solve a linear programming model for this The kitchen manager for Sing Sing prison is trying to decide
problem in a spreadsheet. what to feed its prisoners. She would like to offer some com-
b. Formulate this same model algebraically. bination of milk, beans, and oranges. The goal is to minimize
hil24064_ch03_064-123.indd 104 02/11/12 4:54 PM

Confirming Pages
Chapter 3 Problems 105
cost, subject to meeting the minimum nutritional requirements through three wholesalers. The shipping cost from each plant
imposed by law. The cost and nutritional content of each food, to the warehouse of each wholesaler along with the monthly
along with the minimum nutritional requirements, are shown demand from each wholesaler are also indicated in the table.
below. What diet should be fed to each prisoner? The management of Heart Start now has asked their top man-
agement scientist (you) to address the following two questions.
a. Formulate and solve a linear programming model for this How many automated external defibrillators should be produced
problem in a spreadsheet. in each plant, and how should they be distributed to each of the
b. Formulate this same model algebraically. three wholesaler warehouses so as to minimize the combined
cost of production and shipping? Formulate and solve a linear
Oranges
programming model in a spreadsheet.
Navy (large Minimum
Milk Beans Calif. Daily 3.S5. Bidding for Classes
(gallons) (cups) Valencia) Requirement In the MBA program at a prestigious university in the Pacific
Niacin (mg) 3.2 4.9 0.8 13.0 Northwest, students bid for electives in the second year of their
Thiamin (mg) 1.12 1.3 0.19 1.5 program. Each student has 100 points to bid (total) and must
Vitamin C take two electives. There are four electives available: Manage-
(mg) 32.0 0.0 93.0 45.0 ment Science (MS), Finance (Fin), Operations Management
Cost ($) 2.00 0.20 0.25 (OM), and Marketing (Mkt). Each class is limited to 5 students.
The bids submitted for each of the 10 students are shown in the
table below.
3.S3. Cutting Stock Problem
Decora Accessories manufactures a variety of bathroom acces-
sories, including decorative towel rods and shower curtain rods. Student Bids for Classes
Each of the accessories includes a rod made out of stainless Student MS Fin OM Mkt
steel. However, many different lengths are needed: 12, 18, 24,
40, and 60 inches. Decora purchases 60-inch rods from an out- George 60 10 10 20
side supplier and then cuts the rods as needed for their products. Fred 20 20 40 20
Each 60-inch rod can be used to make a number of smaller rods. Ann 45 45 5 5
For example, a 60-inch rod could be used to make a 40-inch Eric 50 20 5 25
Susan 30 30 30 10
and an 18-inch rod (with 2 inches of waste), or five 12-inch
Liz 50 50 0 0
rods (with no waste). For the next production period, Decora Ed 70 20 10 0
needs twenty-five 12-inch rods, fifty-two 18-inch rods, forty- David 25 25 35 15
five 24-inch rods, thirty 40-inch rods, and twelve 60-inch rods. Tony 35 15 35 15
What is the fewest number of 60-inch rods that can be purchased Jennifer 60 10 10 20
to meet their production needs? Formulate and solve an integer
programming model in a spreadsheet.
3.S4. Producing and Distributing AEDs a. Formulate and solve a spreadsheet model to determine an as-
signment of students to classes so as to maximize the total bid
at Heart Start
points of the assignments.
Heart Start produces automated external defibrillators in each
of two different plants (A and B). The unit production costs and b. Does the resulting solution seem like a fair assignment?
monthly production capacity of the two plants are indicated in c. Which alternative objectives might lead to a fairer
the table below. The automated external defibrillators are sold assignment?
Unit Shipping Cost

Unit Monthly
Warehouse Warehouse Warehouse Production Production
1 2 3 Cost Capacity
Plant A $22 $14 $30 $600 100

Plant B $16 $20 $24 $625 120
Monthly Demand 80 60 70
Problems
We have inserted the symbol E* to the left of each problem (or 3.1. Reconsider the Super Grain Corp. case study as presented
its parts) where Excel should be used (unless your instructor in Section 3.1. The advertising firm, Giacomi & Jackowitz, now
gives you contrary instructions). Either the Excel’s Solver or has suggested a fourth promising advertising medium—radio
RSPE may be used to solve such problems. An asterisk on the commercials—to promote the company’s new breakfast cereal,
problem number indicates that at least a partial answer is given Crunchy Start. Young children are potentially major consumers
in the back of the book. of this cereal, but parents of young children (the major potential
hil24064_ch03_064-123.indd 105 02/11/12 4:55 PM

Confirming Pages
purchasers) often are too busy to do much reading (so may miss
Resource Usage
the company’s advertisements in magazines and Sunday supple-
per Unit of Each
ments) or even to watch the Saturday morning programs for
Activity
children where the company’s television commercials are aired.
However, these parents do tend to listen to the radio during the Amount of
commute to and from work. Therefore, to better reach these Resource
parents, Giacomi & Jackowitz suggests giving consideration to Resource 1 2 3 Available
running commercials for Crunchy Start on nationally syndicated A 30 20 0 500
radio programs that appeal to young adults during typical com- B 0 10 40 600
muting hours. C 20 20 30 1,000
Giacomi & Jackowitz estimates that the cost of develop- Contribution per unit $50 $40 $70
ing each new radio commercial would be $50,000, and that
Contribution per unit 5 profit per unit of the activity.
the expected number of exposures per commercial would be
900,000. The firm has determined that 10 spots are available for
different radio commercials, and each one would cost $200,000 E* a. Formulate and solve a linear programming model
for a normal run. for this problem on a spreadsheet.
E* a. Formulate and solve a spreadsheet model for the b. Express this model in algebraic form.
revised advertising-mix problem that includes this E*3.5. Consider a resource-allocation problem having the fol-
fourth advertising medium. Identify the data cells, lowing data.
the changing cells, and the objective cell. Also show
the Excel equation for each output cell expressed as Resource Usage per
a SUMPRODUCT function. Unit of Each Activity
b. Indicate why this spreadsheet model is a linear pro-
Amount of
gramming model.
Resource
c. Express this model in algebraic form. Resource 1 2 3 4 Available
3.2 Read the referenced article that fully describes the man- P 3 5 22 4 400
agement science study summarized in the application vignette Q 4 21 3 2 300
presented in Section 3.2. Briefly describe how linear program- R 6 3 2 21 400
ming was applied in this study. Then list the various benefits that S 22 2 5 3 300
resulted from this study. Contribution $11 $9 $8 $9
3.3.* Consider a resource-allocation problem having the fol- per unit
lowing data. Contribution per unit 5 profit per unit of the activity.
Resource Usage a. Formulate a linear programming model for this

per Unit of Each problem on a spreadsheet.
Activity b. Make five guesses of your own choosing for the
Amount of optimal solution. Use the spreadsheet to check each
Resource 1 2 Resource Available one for feasibility and, if feasible, for the value of
the objective function. Which feasible guess has the
1 2 1 10 best objective function value?
2 3 3 20
3 2 4 20 c. Use Solver to find an optimal solution.
Contribution $20 $30 3.6.* The Omega Manufacturing Company has discontinued
per unit
the production of a certain unprofitable product line. This act
Contribution per unit 5 profit per unit of the activity. created considerable excess production capacity. Management
is considering devoting this excess capacity to one or more of
E* a. Formulate a linear programming model for this three products, Products 1, 2, and 3. The available capacity of
problem on a spreadsheet. the machines that might limit output is summarized in the fol-
E* b. Use the spreadsheet to check the following solu- lowing table.
tions: (x1, x2) 5 (2, 2), (3, 3), (2, 4), (4, 2), (3, 4),
(4, 3). Which of these solutions are feasible? Which Available Time
of these feasible solutions has the best value of the Machine Type (in Machine-Hours per Week)
objective function?
E* c. Use Solver to find an optimal solution. Milling machine 500
Lathe 350
d. Express this model in algebraic form. Grinder 150
e. Use the graphical method to solve this model.
3.4. Consider a resource-allocation problem having the fol- The number of machine-hours required for each unit of the
lowing data. respective products are shown in the next table.
hil24064_ch03_064-123.indd 106 02/11/12 4:55 PM

Confirming Pages
Productivity Coefficient (in Machine-Hours per Unit) E* d. Use Solver to find an optimal solution.
e. Express the model in algebraic form.
Machine Type Product 1 Product 2 Product 3
E*3.8. Consider the following algebraic formulation of a
Milling machine 9 3 5 resource-allocation problem with three resources, where the
Lathe 5 4 0 decisions to be made are the levels of three activities (A1, A2,
Grinder 3 0 2 and A3).
Maximize Profit 5 20A1 1 40A2 1 30A3
The Sales Department indicates that the sales potential for
Products 1 and 2 exceeds the maximum production rate and that subject to
the sales potential for product 3 is 20 units per week. The unit Resource 1: 3A1 1 5A2 1 4A3 # 400 (amount available)
profit would be $50, $20, and $25, respectively, for Products 1, Resource 2: A1 1 A2 1 A3 # 100 (amount available)
2, and 3. The objective is to determine how much of each prod-
Resource 3: A1 1 3A2 1 2A3 # 200 (amount available)
uct Omega should produce to maximize profit.
and
a. Indicate why this is a resource-allocation problem
by identifying both the activities and the limited A1 $ 0 A2 $ 0 A3 $ 0
resources to be allocated to these activities.
Formulate and solve the spreadsheet model for this problem.
b. Identify verbally the decisions to be made, the con-
3.9. Read the referenced article that fully describes the man-
straints on these decisions, and the overall measure
agement science study summarized in the application vignette
of performance for the decisions.
presented in Section 3.3. Briefly describe how linear program-
c. Convert these verbal descriptions of the constraints ming was applied in this study. Then list the various financial
and the measure of performance into quantitative and nonfinancial benefits that resulted from this study.
expressions in terms of the data and decisions.
3.10. Consider a cost–benefit–trade-off problem having the
E* d. Formulate a spreadsheet model for this problem. Iden- following data.
tify the data cells, the changing cells, the objective cell,
and the other output cells. Also show the Excel equa- Benefit Contribution
tion for each output cell expressed as a SUMPROD- per Unit of Each
UCT function. Then use Solver to solve the model. Activity
e. Summarize the model in algebraic form.
Minimum
3.7. Ed Butler is the production manager for the Bilco Cor-
Acceptable
poration, which produces three types of spare parts for automo-
Benefit 1 2 Level
biles. The manufacture of each part requires processing on each
of two machines, with the following processing times (in hours). 1 5 3 60
2 2 2 30
3 7 9 126
Part
Unit cost $60 $50
Machine A B C
E* a. Formulate a linear programming model for this
1 0.02 0.03 0.05
2 0.05 0.02 0.04 problem on a spreadsheet.
E* b. Use the spreadsheet to check the following solu-
Each machine is available 40 hours per month. Each part tions: (x1, x2) 5 (7, 7), (7, 8), (8, 7), (8, 8), (8, 9),
manufactured will yield a unit profit as follows: (9, 8). Which of these solutions are feasible? Which
of these feasible solutions has the best value of the
objective function?
Part
E* c. Use Solver to find an optimal solution.
A B C d. Express the model in algebraic form.
Profit $50 $40 $30 e. Use the graphical method to solve this model.
E*3.11. Consider a cost–benefit–trade-off problem having the
Ed wants to determine the mix of spare parts to produce to following data.
maximize total profit.
Benefit Contribution
a. Identify both the activities and the resources for this
per Unit of Each Activity
resource-allocation problem.
E* b. Formulate a linear programming model for this Minimum
problem on a spreadsheet. Acceptable
Benefit 1 2 3 4 Level
E* c. Make three guesses of your own choosing for the
optimal solution. Use the spreadsheet to check each P 2 21 4 3 80
one for feasibility and, if feasible, for the value of Q 1 4 21 2 60
the objective function. Which feasible guess has the R 3 5 4 21 110
best objective function value? Unit cost $400 $600 $500 $300
hil24064_ch03_064-123.indd 107 02/11/12 4:55 PM

Confirming Pages
a. Formulate a linear programming model for this Maureen wishes to determine the mix of investments in these
problem on a spreadsheet. assets that will cover the cash flow requirements while minimiz-
b. Make five guesses of your own choosing for the ing the total amount invested.
optimal solution. Use the spreadsheet to check each E* a. Formulate a linear programming model for this
one for feasibility and, if feasible, for the value of problem on a spreadsheet.
the objective function. Which feasible guess has the E* b. Use the spreadsheet to check the possibility of
best objective function value? purchasing 100 units of asset 1, 100 units of asset
c. Use Solver to find an optimal solution. 2, and 200 units of asset 3. How much cash flow
3.12.* Fred Jonasson manages a family-owned farm. To sup- would this mix of investments generate 5, 10,
plement several food products grown on the farm, Fred also and 20 years from now? What would be the total
raises pigs for market. He now wishes to determine the quantities amount invested?
of the available types of feed (corn, tankage, and alfalfa) that E* c. Take a few minutes to use a trial-and-error approach
should be given to each pig. Since pigs will eat any mix of these with the spreadsheet to develop your best guess
feed types, the objective is to determine which mix will meet cer- for the optimal solution. What is the total amount
tain nutritional requirements at a minimum cost. The number of invested for your solution?
units of each type of basic nutritional ingredient contained within E* d. Use Solver to find an optimal solution.
a kilogram of each feed type is given in the following table, e. Summarize the model in algebraic form.
along with the daily nutritional requirements and feed costs.
Minimum
Nutritional Kilogram Kilogram Kilogram Daily
Ingredient of Corn of Tankage of Alfalfa Requirement
Carbohydrates 90 20 40 200
Protein 30 80 60 180
Vitamins 10 20 60 150
Cost (¢) 84 72 60
E* a. Formulate a linear programming model for this 3.14. Web Mercantile sells many household products through
problem on a spreadsheet. an online catalog. The company needs substantial warehouse
E* b. Use the spreadsheet to check if (x1, x2, x3) 5 (1, 2, 2) space for storing its goods. Plans now are being made for leas-
is a feasible solution and, if so, what the daily cost ing warehouse storage space over the next five months. Just how
would be for this diet. How many units of each much space will be required in each of these months is known.
nutritional ingredient would this diet provide daily? However, since these space requirements are quite different, it
E* c. Take a few minutes to use a trial-and-error approach may be most economical to lease only the amount needed each
with the spreadsheet to develop your best guess for month on a month-by-month basis. On the other hand, the addi-
the optimal solution. What is the daily cost for your tional cost for leasing space for additional months is much less
solution? than for the first month, so it may be less expensive to lease the
maximum amount needed for the entire five months. Another
E* d. Use Solver to find an optimal solution.
option is the intermediate approach of changing the total amount
e. Express the model in algebraic form. of space leased (by adding a new lease and/or having an old
3.13. Maureen Laird is the chief financial officer for the Alva lease expire) at least once but not every month.
Electric Co., a major public utility in the Midwest. The com- The space requirement and the leasing costs for the various
pany has scheduled the construction of new hydroelectric plants leasing periods are as follows.
5, 10, and 20 years from now to meet the needs of the growing
population in the region served by the company. To cover the Required Space
construction costs, Maureen needs to invest some of the compa- Month (Square Feet)
ny’s money now to meet these future cash flow needs. Maureen
may purchase only three kinds of financial assets, each of which 1 30,000
costs $1 million per unit. Fractional units may be purchased. The 2 20,000
assets produce income 5, 10, and 20 years from now, and that 3 40,000
4 10,000
income is needed to cover minimum cash flow requirements in
5 50,000
those years, as shown in the following table.
Income per Unit of Asset Leasing Period Cost per

Minimum (Months) Sq. Ft. Leased
Cash Flow
1 $ 65
Year Asset 1 Asset 2 Asset 3 Required 2 100
5 $2 million $1 million $0.5 million $400 million 3 135
10 0.5 million 0.5 million 1 million 100 million 4 160
20 0 1.5 million 2 million 300 million 5 190
hil24064_ch03_064-123.indd 108 02/11/12 4:55 PM

Confirming Pages
The objective is to minimize the total leasing cost for meet-

Minimum Number of
ing the space requirements.
Consultants Required
a. Indicate why this is a cost–benefit–trade-off prob- Time of Day to Be on Duty
lem by identifying both the activities and the ben-
efits being sought from these activities. 8 AM–noon 6
Noon–4 PM 8
b. Identify verbally the decisions to be made, the con-
4 PM–8 PM 12
straints on these decisions, and the overall measure 8 PM–midnight 6
of performance for the decisions.
c. Convert these verbal descriptions of the con- Two types of computer consultants can be hired: full-time
straints and the measure of performance into and part-time. The full-time consultants work for eight consecu-
quantitative expressions in terms of the data and tive hours in any of the following shifts: morning (8 am–4 pm),
decisions. afternoon (noon–8 pm), and evening (4 pm–midnight). Full-time
E* d. Formulate a spreadsheet model for this problem. consultants are paid $14 per hour.
Identify the data cells, the changing cells, the objec- Part-time consultants can be hired to work any of the four shifts
tive cell, and the other output cells. Also show the listed in the table. Part-time consultants are paid $12 per hour.
Excel equation for each output cell expressed as a An additional requirement is that during every time period,
SUMPRODUCT function. Then use Solver to solve there must be at least two full-time consultants on duty for every
the model. part-time consultant on duty.
e. Summarize the model in algebraic form. Larry would like to determine how many full-time and
part-time consultants should work each shift to meet the above
E*3.15. Consider the following algebraic formulation of a cost– requirements at the minimum possible cost.
benefit–trade-off problem involving three benefits, where the
a. Which category of linear programming problem
decisions to be made are the levels of four activities (A1, A2, A3,
does this problem fit? Why?
and A4):
E* b. Formulate and solve a linear programming model
Minimize Cost 5 2 A1 1 A2 2 A3 1 3 A4 for this problem on a spreadsheet.
c. Summarize the model in algebraic form.
subject to
3.17.* The Medequip Company produces precision medical
Benefit 1: 3 A1 1 2 A2 2 2 A3 1 5 A4 $ 80 (minimum
diagnostic equipment at two factories. Three medical centers
acceptable
have placed orders for this month’s production output. The fol-
level)
lowing table shows what the cost would be for shipping each
Benefit 2: A1 2 A2 1 A4 $ 10 (minimum unit from each factory to each of these customers. Also shown
acceptable are the number of units that will be produced at each factory and
level) the number of units ordered by each customer.
Benefit 3: A1 1 A2 2 A3 1 2A4 $ 30 (minimum A decision now needs to be made about the shipping
acceptable plan for how many units to ship from each factory to each
level) customer.
a. Which category of linear programming problem
and does this problem fit? Why?
A1 $ 0 A2 $ 0 A3 $ 0 A4 $ 0 E* b. Formulate and solve a linear programming model
for this problem on a spreadsheet.
Formulate and solve the spreadsheet model for this problem. c. Summarize this formulation in algebraic form.
Unit Shipping Cost

To
From Customer 1 Customer 2 Customer 3 Output
Factory 1 $600 $800 $700 400 units

Factory 2 400 900 600 500 units
Order size 300 units 200 units 400 units
3.16. Larry Edison is the director of the Computer Center for 3.18. The Fagersta Steelworks currently is working two
Buckly College. He now needs to schedule the staffing of the mines to obtain its iron ore. This iron ore is shipped to either
center. It is open from 8 am until midnight. Larry has monitored of two storage facilities. When needed, it then is shipped on to
the usage of the center at various times of the day and deter- the company’s steel plant. The diagram below depicts this dis-
mined that the following number of computer consultants are tribution network, where M1 and M2 are the two mines, S1 and
required. S2 are the two storage facilities, and P is the steel plant. The
hil24064_ch03_064-123.indd 109 02/11/12 4:55 PM

Confirming Pages
diagram also shows the monthly amounts produced at the mines 3.20. The Metalco Company desires to blend a new alloy of
and needed at the plant, as well as the shipping cost and the 40 percent tin, 35 percent zinc, and 25 percent lead from several
maximum amount that can be shipped per month through each available alloys having the following properties.
shipping lane.
40 tons
Alloy
$2,000/ton
produced M1 S1
30 tons max. $4 Property 1 2 3 4 5
70 00
ton /ton
$1 ons
30
,7
sm 100 tons Percentage of tin 60 25 45 20 50

00 ma
t
ax
/to x.
. needed Percentage of zinc 10 15 45 50 40

n
Percentage of lead 30 60 10 30 10
P
m n
Cost ($/lb) 22 20 25 24 27
o
.
to 0/t
ax
n
/to x.
50 1,60
00
$8 s ma
ns
$
ton The objective is to determine the proportions of these alloys

70
60 tons $1,100/ton
S2 that should be blended to produce the new alloy at a minimum cost.
produced M2
50 tons max. a. Identify all the requirements that will need to be
expressed in fixed-requirement constraints.
Management now wants to determine the most economical
plan for shipping the iron ore from the mines through the distri- E* b. Formulate and solve a linear programming model
bution network to the steel plant. for this problem on a spreadsheet.
c. Express this model in algebraic form.
a. Identify all the requirements that will need to be
expressed in fixed-requirement constraints. 3.21. The Weigelt Corporation has three branch plants with
excess production capacity. Fortunately, the corporation has a
E* b. Formulate and solve a linear programming model
new product ready to begin production, and all three plants have
for this problem on a spreadsheet.
this capability, so some of the excess capacity can be used in this
c. Express this model in algebraic form. way. This product can be made in three sizes—large, medium,
3.19.* Al Ferris has $60,000 that he wishes to invest now in and small—that yield a net unit profit of $420, $360, and $300,
order to use the accumulation for purchasing a retirement annu- respectively. Plants 1, 2, and 3 have the excess capacity to pro-
ity in five years. After consulting with his financial advisor, he duce 750, 900, and 450 units per day of this product, respec-
has been offered four types of fixed-income investments, which tively, regardless of the size or combination of sizes involved.
we will label as investments A, B, C, and D. The amount of available in-process storage space also
Investments A and B are available at the beginning of each of imposes a limitation on the production rates of the new product.
the next five years (call them years 1 to 5). Each dollar invested Plants 1, 2, and 3 have 13,000, 12,000, and 5,000 square feet,
in A at the beginning of a year returns $1.40 (a profit of $0.40) respectively, of in-process storage space available for a day’s
two years later (in time for immediate reinvestment). Each dol- production of this product. Each unit of the large, medium, and
lar invested in B at the beginning of a year returns $1.70 three small sizes produced per day requires 20, 15, and 12 square feet,
years later. respectively.
Investments C and D will each be available at one time in Sales forecasts indicate that if available, 900, 1,200, and 750
the future. Each dollar invested in C at the beginning of year 2 units of the large, medium, and small sizes, respectively, would
returns $1.90 at the end of year 5. Each dollar invested in D at be sold per day.
the beginning of year 5 returns $1.30 at the end of year 5. At each plant, some employees will need to be laid off unless
Al wishes to know which investment plan maximizes the most of the plant’s excess production capacity can be used to
amount of money that can be accumulated by the beginning of produce the new product. To avoid layoffs if possible, manage-
year 6. ment has decided that the plants should use the same percentage
a. For this problem, all its functional constraints can of their excess capacity to produce the new product.
be expressed as fixed-requirement constraints. To Management wishes to know how much of each of the sizes
do this, let At, Bt, Ct, and Dt be the amounts invested should be produced by each of the plants to maximize profit.
in investments A, B, C, and D, respectively, at the E* a. Formulate and solve a linear programming model
beginning of year t for each t where the investment for this mixed problem on a spreadsheet.
is available and will mature by the end of year 5. b. Express the model in algebraic form.
Also let Rt be the number of available dollars not 3.22.* A cargo plane has three compartments for storing
invested at the beginning of year t (and so available cargo: front, center, and back. These compartments have capac-
for investment in a later year). Thus, the amount ity limits on both weight and space, as summarized below.
invested at the beginning of year t plus Rt must
equal the number of dollars available for invest-
ment at that time. Write such an equation in terms Weight Space
of the relevant variables above for the beginning Capacity Capacity
of each of the five years to obtain the five fixed- Compartment (Tons) (Cubic Feet)
requirement constraints for this problem.
Front 12 7,000
b. Formulate a complete linear programming model Center 18 9,000
for this problem in algebraic form. Back 10 5,000
E* c. Formulate and solve this model on a spreadsheet.
hil24064_ch03_064-123.indd 110 02/11/12 4:55 PM

Confirming Pages
Furthermore, the weight of the cargo in the respective com- to employ. They would like to maximize their net profit—their
partments must be the same proportion of that compartment’s gross profit from sales minus their labor costs.
weight capacity to maintain the balance of the airplane. E* a. Formulate and solve a linear programming model
The following four cargoes have been offered for shipment for this problem on a spreadsheet.
on an upcoming flight as space is available. b. Summarize this formulation in algebraic form.
Weight Volume Profit E*3.24. Oxbridge University maintains a powerful mainframe
Cargo (Tons) (Cubic Feet/Ton) ($/Ton) computer for research use by its faculty, Ph.D. students, and
research associates. During all working hours, an operator must
1 20 500 320 be available to operate and maintain the computer, as well as to
2 16 700 400 perform some programming services. Beryl Ingram, the director
3 25 600 360 of the computer facility, oversees the operation.
4 13 400 290 It is now the beginning of the fall semester and Beryl is con-
fronted with the problem of assigning different working hours to
Any portion of these cargoes can be accepted. The objec- her operators. Because all the operators are currently enrolled in
tive is to determine how much (if any) of each cargo should be the university, they are available to work only a limited number
accepted and how to distribute each among the compartments to of hours each day.
maximize the total profit for the flight. There are six operators (four undergraduate students and two
E* a. Formulate and solve a linear programming model graduate students). They all have different wage rates because of
for this mixed problem on a spreadsheet. differences in their experience with computers and in their pro-
b. Express the model in algebraic form. gramming ability. The following table shows their wage rates,
along with the maximum number of hours that each can work
3.23. Comfortable Hands is a company that features a prod-
each day.
uct line of winter gloves for the entire family—men, women,
and children. They are trying to decide what mix of these three
Maximum Hours of Availability
types of gloves to produce.
Comfortable Hands’s manufacturing labor force is union- Operators Wage Rate Mon. Tue. Wed. Thurs. Fri.
ized. Each full-time employee works a 40-hour week. In addi-
tion, by union contract, the number of full-time employees can K. C. $10.00/hour 6 0 6 0 6
never drop below 20. Nonunion, part-time workers also can be D. H. $10.10/hour 0 6 0 6 0
hired with the following union-imposed restrictions: (1) each H. B. $9.90/hour 4 8 4 0 4
part-time worker works 20 hours per week and (2) there must S. C. $9.80/hour 5 5 5 0 5
be at least two full-time employees for each part-time employee. K. S. $10.80/hour 3 0 3 8 0
N. K. $11.30/hour 0 0 0 6 2
All three types of gloves are made out of the same 100 per-
cent genuine cowhide leather. Comfortable Hands has a long-
term contract with a supplier of the leather and receives a Each operator is guaranteed a certain minimum number of
5,000-square-foot shipment of the material each week. The mate- hours per week that will maintain an adequate knowledge of the
rial requirements and labor requirements, along with the gross operation. This level is set arbitrarily at 8 hours per week for
profit per glove sold (not considering labor costs), are given in the undergraduate students (K. C., D. H., H. B., and S. C.) and
the following table. 7 hours per week for the graduate students (K. S. and N. K.).
The computer facility is to be open for operation from 8 am
Material Labor Gross to 10 pm Monday through Friday with exactly one operator on
Required Required Profit duty during these hours. On Saturdays and Sundays, the com-
Glove (Square Feet) (Minutes) (per Pair) puter is to be operated by other staff.
Because of a tight budget, Beryl has to minimize cost. She
Men’s 2 30 $8 wishes to determine the number of hours she should assign to
Women’s 1.5 45 10 each operator on each day. Formulate and solve a spreadsheet
Children’s 1 40 6 model for this problem.
3.25. Slim-Down Manufacturing makes a line of nutritionally
Each full-time employee earns $13 per hour, while each complete, weight-reduction beverages. One of its products is a
part-time employee earns $10 per hour. Management wishes to strawberry shake that is designed to be a complete meal. The
know what mix of each of the three types of gloves to produce strawberry shake consists of several ingredients. Some informa-
per week, as well as how many full-time and part-time workers tion about each of these ingredients is given next.
Calories Total Vitamin

from Fat Calories Content Thickeners Cost
Ingredient (per tbsp.) (per tbsp.) (mg/tbsp.) (mg/tbsp.) (¢/tbsp.)
Strawberry flavoring 1 50 20 3 10
Cream 75 100 0 8 8
Vitamin supplement 0 0 50 1 25
Artificial sweetener 0 120 0 2 15
Thickening agent 30 80 2 25 6
hil24064_ch03_064-123.indd 111 02/11/12 4:55 PM

Confirming Pages
The nutritional requirements are as follows. The beverage E*3.28. The Cost-Less Corp. supplies its four retail outlets from
must total between 380 and 420 calories (inclusive). No more its four plants. The shipping cost per shipment from each plant
than 20 percent of the total calories should come from fat. to each retail outlet is given below.
There must be at least 50 milligrams (mg) of vitamin content.
For taste reasons, there must be at least two tablespoons (tbsp.)
Unit Shipping Cost
of strawberry flavoring for each tbsp. of artificial sweetener.
Finally, to maintain proper thickness, there must be exactly 15 Retail Outlet: 1 2 3 4
mg of thickeners in the beverage.
Management would like to select the quantity of each ingre- Plant
dient for the beverage that would minimize cost while meeting 1 $500 $600 $400 $200
the above requirements. 2 200 900 100 300
3 300 400 200 100
a. Identify the requirements that lead to resource con- 4 200 100 300 200
straints, to benefit constraints, and to fixed-require-
ment constraints.
E* b. Formulate and solve a linear programming model Plants 1, 2, 3, and 4 make 10, 20, 20, and 10 shipments per
for this problem on a spreadsheet. month, respectively. Retail outlets 1, 2, 3, and 4 need to receive
c. Summarize this formulation in algebraic form. 20, 10, 10, and 20 shipments per month, respectively.
3.26. Joyce and Marvin run a day care for preschoolers. They The distribution manager, Randy Smith, now wants to deter-
are trying to decide what to feed the children for lunches. They mine the best plan for how many shipments to send from each
would like to keep their costs down, but they also need to meet plant to the respective retail outlets each month. Randy’s objec-
the nutritional requirements of the children. They have already tive is to minimize the total shipping cost.
decided to go with peanut butter and jelly sandwiches, and some Formulate this problem as a transportation problem on a
combination of graham crackers, milk, and orange juice. The spreadsheet and then use Solver to obtain an optimal solution.
nutritional content of each food choice and its cost are given in E*3.29. The Childfair Company has three plants producing
the table below. child push chairs that are to be shipped to four distribution
Calories Total Vitamin C Protein Cost

Food Item from Fat Calories (mg) (g) (¢)
Bread (1 slice) 10 70 0 3 5
Peanut butter (1 tbsp.) 75 100 0 4 4
Strawberry jelly (1 tbsp.) 0 50 3 0 7
Graham cracker (1 cracker) 20 60 0 1 8
Milk (1 cup) 70 150 2 8 15
Juice (1 cup) 0 100 120 1 35
The nutritional requirements are as follows. Each child centers. Plants 1, 2, and 3 produce 12, 17, and 11 shipments per
should receive between 400 and 600 calories. No more than month, respectively. Each distribution center needs to receive
30 percent of the total calories should come from fat. Each child 10 shipments per month. The distance from each plant to the
should consume at least 60 milligrams (mg) of vitamin C and respective distribution centers is given below.
12 grams (g) of protein. Furthermore, for practical reasons, each
child needs exactly 2 slices of bread (to make the sandwich), at
least twice as much peanut butter as jelly, and at least 1 cup of Distance to Distribution Center (Miles)
liquid (milk and/or juice).
Joyce and Marvin would like to select the food choices 1 2 3 4
for each child that minimize cost while meeting the above
Plant
requirements. 1 800 1,300 400 700
a. Identify the requirements that lead to resource con- 2 1,100 1,400 600 1,000
straints, to benefit constraints, and to fixed-require- 3 600 1,200 800 900
ment constraints.
E* b. Formulate and solve a linear programming model The freight cost for each shipment is $100 plus 50 cents/mile.
for this problem on a spreadsheet. How much should be shipped from each plant to each of the
c. Express the model in algebraic form. distribution centers to minimize the total shipping cost?
3.27. Read the referenced article that fully describes the man- Formulate this problem as a transportation problem on a
agement science study summarized in the application vignette spreadsheet and then use Solver to obtain an optimal solution.
presented in Section 3.5. Briefly describe how the model for the E*3.30. The Onenote Co. produces a single product at three
transportation problem was applied in this study. Then list the vari- plants for four customers. The three plants will produce 60, 80,
ous financial and nonfinancial benefits that resulted from this study. and 40 units, respectively, during the next week. The firm has
hil24064_ch03_064-123.indd 112 02/11/12 4:55 PM

Confirming Pages
made a commitment to sell 40 units to customer 1, 60 units to Formulate this problem on a spreadsheet and then use Solver
customer 2, and at least 20 units to customer 3. Both customers to obtain the optimal solution identified above.
3 and 4 also want to buy as many of the remaining units as pos- 3.34. Four cargo ships will be used for shipping goods from
sible. The net profit associated with shipping a unit from plant i one port to four other ports (labeled 1, 2, 3, 4). Any ship can be
for sale to customer j is given by the following table. used for making any one of these four trips. However, because
of differences in the ships and cargoes, the total cost of loading,
transporting, and unloading the goods for the different ship–port
Customer
combinations varies considerably, as shown in the following
1 2 3 4 table.
Plant
1 $800 $700 $500 $200 Port
2 500 200 100 300
3 600 400 300 500 1 2 3 4
Ship
Management wishes to know how many units to sell to cus-
1 $500 $400 $600 $700
tomers 3 and 4 and how many units to ship from each of the 2 600 600 700 500
plants to each of the customers to maximize profit. Formulate 3 700 500 700 600
and solve a spreadsheet model for this problem. 4 500 400 600 600
E*3.31. The Move-It Company has two plants building forklift
trucks that then are shipped to three distribution centers. The
production costs are the same at the two plants, and the cost of The objective is to assign the four ships to four different ports
shipping each truck is shown below for each combination of in such a way as to minimize the total cost for all four shipments.
plant and distribution center. a. Describe how this problem fits into the format for
an assignment problem.
E* b. Formulate and solve this problem on a spreadsheet.
Distribution Center
E*3.35. Reconsider Problem 3.10. Now distribution centers 1,
1 2 3 2, and 3 must receive exactly 10, 20, and 30 units per week,
respectively. For administrative convenience, management has
Plant
decided that each distribution center will be supplied totally
A $800 $700 $400
by a single plant, so that one plant will supply one distribution
B 600 800 500
center and the other plant will supply the other two distribution
centers. The choice of these assignments of plants to distribu-
A total of 60 forklift trucks are produced and shipped per
tion centers is to be made solely on the basis of minimizing total
week. Each plant can produce and ship any amount up to a maxi-
shipping cost.
mum of 50 trucks per week, so there is considerable flexibility
Formulate and solve a spreadsheet model for this problem.
on how to divide the total production between the two plants so
as to reduce shipping costs. However, each distribution center 3.36. Vincent Cardoza is the owner and manager of a
must receive exactly 20 trucks per week. machine shop that does custom order work. This Wednesday
Management’s objective is to determine how many forklift afternoon, he has received calls from two customers who
trucks should be produced at each plant, and then what the over- would like to place rush orders. One is a trailer hitch com-
all shipping pattern should be to minimize total shipping cost. pany that would like some custom-made heavy-duty tow bars.
Formulate and solve a spreadsheet model for this problem. The other is a mini-car-carrier company that needs some cus-
tomized stabilizer bars. Both customers would like as many
E*3.32. Redo Problem 3.31 when any distribution center may
as possible by the end of the week (two working days). Since
receive any quantity between 10 and 30 forklift trucks per week
both products would require the use of the same two machines,
in order to further reduce total shipping cost, provided only that
Vincent needs to decide and inform the customers this after-
the total shipped to all three distribution centers must still equal
noon about how many of each product he will agree to make
60 trucks per week.
over the next two days.
E*3.33. Consider the assignment problem having the following Each tow bar requires 3.2 hours on machine 1 and 2 hours
cost table. on machine 2. Each stabilizer bar requires 2.4 hours on machine
1 and 3 hours on machine 2. Machine 1 will be available for
Job 16 hours over the next two days and machine 2 will be avail-
able for 15 hours. The profit for each tow bar produced would
1 2 3 be $130 and the profit for each stabilizer bar produced would
be $150.
Person
Vincent now wants to determine the mix of these production
A $5 $7 $4
quantities that will maximize the total profit.
B 3 6 5
C 2 3 4 a. Formulate an integer programming model in alge-
braic form for this problem.
The optimal solution is A-3, B-1, C-2, with a total cost of $10. E* b. Formulate and solve the model on a spreadsheet.
hil24064_ch03_064-123.indd 113 02/11/12 4:55 PM

Confirming Pages
3.37. Pawtucket University is planning to buy new copier purchases. Regardless of which airplanes are purchased, air
machines for its library. Three members of its Management travel of all distances is expected to be sufficiently large that
Science Department are analyzing what to buy. They are con- these planes would be utilized at essentially maximum capac-
sidering two different models: Model A, a high-speed copier, ity. It is estimated that the net annual profit (after capital recov-
and Model B, a lower speed but less expensive copier. Model A ery costs are subtracted) would be $4.2 million per long-range
can handle 20,000 copies a day and costs $6,000. Model B can plane, $3 million per medium-range plane, and $2.3 million per
handle 10,000 copies a day but only costs $4,000. They would short-range plane.
like to have at least six copiers so that they can spread them It is predicted that enough trained pilots will be available to
throughout the library. They also would like to have at least one the company to crew 30 new airplanes. If only short-range planes
high-speed copier. Finally, the copiers need to be able to handle were purchased, the maintenance facilities would be able to handle
a capacity of at least 75,000 copies per day. The objective is to 40 new planes. However, each medium-range plane is equivalent
determine the mix of these two copiers that will handle all these to 11/3 short-range planes, and each long-range plane is equivalent
requirements at minimum cost. to 12/3 short-range planes in terms of their use of the maintenance
E* a. Formulate and solve a spreadsheet model for this facilities.
problem. The information given here was obtained by a preliminary
b. Formulate this same model in algebraic form. analysis of the problem. A more detailed analysis will be con-
ducted subsequently. However, using the preceding data as a
3.38. Northeastern Airlines is considering the purchase of
first approximation, management wishes to know how many
new long-, medium-, and short-range jet passenger airplanes.
planes of each type should be purchased to maximize profit.
The purchase price would be $67 million for each long-range
plane, $50 million for each medium-range plane, and $35 million E* a. Formulate and solve a spreadsheet model for this
for each short-range plane. The board of directors has autho- problem.
rized a maximum commitment of $1.5 billion for these b. Formulate this model in algebraic form.
Case 3-1
Shipping Wood to Market
Alabama Atlantic is a lumber company that has three sources
Unit Investment for Ships ($1,000s) to
of wood and five markets to be supplied. The annual availability
Market
of wood at sources 1, 2, and 3 is 15, 20, and 15 million board
feet, respectively. The amount that can be sold annually at mar- Source 1 2 3 4 5
kets 1, 2, 3, 4, and 5 is 11, 12, 9, 10, and 8 million board feet,
respectively. 1 275 303 238 — 285
In the past, the company has shipped the wood by train. 2 293 318 270 250 265
However, because shipping costs have been increasing, the 3 — 283 275 268 240
alternative of using ships to make some of the deliveries is being
investigated. This alternative would require the company to Considering the expected useful life of the ships and the time
invest in some ships. Except for these investment costs, the ship- value of money, the equivalent uniform annual cost of these
ping costs in thousands of dollars per million board feet by rail investments is one-tenth the amount given in the table. The objec-
and by water (when feasible) would be the following for each tive is to determine the overall shipping plan that minimizes the
route. total equivalent uniform annual cost (including shipping costs).
Unit Cost by Rail ($1,000s) to Market Unit Cost by Ship ($1,000s) to Market
Source 1 2 3 4 5 1 2 3 4 5
1 61 72 45 55 66 31 38 24 — 35
2 69 78 60 49 56 36 43 28 24 31
3 59 66 63 61 47 — 33 36 32 26
The capital investment (in thousands of dollars) in ships You are the head of the management science team that has
required for each million board feet to be transported annually been assigned the task of determining this shipping plan for each
by ship along each route is given next. of the three options listed next.
hil24064_ch03_064-123.indd 114 02/11/12 4:55 PM

Confirming Pages
Case 3-2 Capacity Concerns 115
Option 1: Continue shipping exclusively by rail. Finally, consider the fact that these results are based on cur-
Option 2: Switch to shipping exclusively by water (except rent shipping and investment costs, so that the decision on the
where only rail is feasible). option to adopt now should take into account management’s
Option 3: Ship by either rail or water, depending on which projection of how these costs are likely to change in the future.
is less expensive for the particular route. For each option, describe a scenario of future cost changes that
would justify adopting that option now.
Present your results for each option. Compare.
Case 3-2
Capacity Concerns
Bentley Hamilton throws the business section of The New York you can see from the graph, our missed or late orders have
Times onto the conference room table and watches as his associ- increased steadily and significantly over the past 12 months. I
ates jolt upright in their overstuffed chairs. think this trend explains why we have been losing market share,
Mr. Hamilton wants to make a point. causing our stock to drop to its lowest level in 52 weeks. We
He throws the front page of the The Wall Street Journal on have angered and lost the business of retailers, our customers
top of The New York Times and watches as his associates widen who depend upon on-time deliveries to meet the demand of
their eyes once heavy with boredom. consumers.”
Mr. Hamilton wants to make a big point. “Why have we missed our delivery dates when our produc-
He then throws the front page of the Financial Times on top tivity level should have allowed us to fill all orders?” Mr. Ham-
of the newspaper pile and watches as his associates dab the fine ilton asks. “I called several departments to ask this question.”
beads of sweat off their brows. “It turns out that we have been producing pagers for the
Mr. Hamilton wants his point indelibly etched into his asso- hell of it!” Mr. Hamilton says in disbelief. “The marketing and
ciates’ minds. sales departments do not communicate with the manufacturing
“I have just presented you with three leading financial news- department, so manufacturing executives do not know what pag-
papers carrying today’s top business story,” Mr. Hamilton ers to produce to fill orders. The manufacturing executives want
declares in a tight, angry voice. “My dear associates, our com- to keep the plant running, so they produce pagers regardless of
pany is going to hell in a hand basket! Shall I read you the head- whether the pagers have been ordered. Finished pagers are sent
lines? From The New York Times, ‘CommuniCorp stock drops to the warehouse, but marketing and sales executives do not
to lowest in 52 weeks.’ From The Wall Street Journal, ‘Commu- know the number and styles of pagers in the warehouse. They
niCorp loses 25 percent of the pager market in only one year.’ try to communicate with warehouse executives to determine if
Oh, and my favorite, from the Financial Times, ‘CommuniCorp the pagers in inventory can fill the orders, but they rarely receive
cannot CommuniCate: CommuniCorp stock drops because of answers to their questions.”
internal communications disarray.’ How did our company fall Mr. Hamilton pauses and looks directly at his associates.
into such dire straits?” “Ladies and gentlemen, it seems to me that we have a serious
Mr. Hamilton throws a transparency showing a line sloping internal communications problem. I intend to correct this prob-
slightly upward onto the overhead projector. “This is a graph lem immediately. I want to begin by installing a companywide
of our productivity over the last 12 months. As you can see computer network to ensure that all departments have access to
from the graph, productivity in our pager production facility has critical documents and are able to easily communicate with each
increased steadily over the last year. Clearly, productivity is not other through e-mail. Because this intranet will represent a large
the cause of our problem.” change from the current communications infrastructure, I expect
Mr. Hamilton throws a second transparency showing a line some bugs in the system and some resistance from employees.
sloping steeply upward onto the overhead projector. “This is I therefore want to phase in the installation of the intranet.”
a graph of our missed or late orders over the last 12 months.” Mr. Hamilton passes the following time line and require-
Mr. Hamilton hears an audible gasp from his associates. “As ments chart to his associates (IN 5 intranet).
Month 1 Month 2 Month 3 Month 4 Month 5
IN education
Install IN in sales
Install IN in
manufacturing
Install IN in
warehouse
Install IN in
marketing
hil24064_ch03_064-123.indd 115 02/11/12 4:55 PM

Confirming Pages
“There are several factors that complicate your decision,”

Department Number of Employees
Mr. Hamilton continues. “Two server manufacturers are willing
Sales 60
to offer discounts to CommuniCorp. SGI is willing to give you
Manufacturing 200 a discount of 10 percent off each server purchased, but only if
Warehouse 30 you purchase servers in the first or second month. Sun is will-
Marketing 75 ing to give you a 25 percent discount off all servers purchased
in the first two months. You are also limited in the amount of
money you can spend during the first month. CommuniCorp has
Mr. Hamilton proceeds to explain the time line and require- already allocated much of the budget for the next two months, so
ments chart. “In the first month, I do not want to bring any you only have a total of $9,500 available to purchase servers in
department onto the intranet; I simply want to disseminate infor- months 1 and 2. Finally, the manufacturing department requires
mation about it and get buy-in from employees. In the second at least one of the three more powerful servers. Have your deci-
month, I want to bring the sales department onto the intranet sion on my desk at the end of the week.”
since the sales department receives all critical information from
customers. In the third month, I want to bring the manufacturing a. Emily first decides to evaluate the number and type of serv-
department onto the intranet. In the fourth month, I want to install ers to purchase on a month-to-month basis. For each month,
the intranet at the warehouse, and in the fifth and final month, I formulate a spreadsheet model to determine which servers
want to bring the marketing department onto the intranet. The Emily should purchase in that month to minimize costs in
requirements chart above lists the number of employees requir- that month and support the new users given your results for
ing access to the intranet in each department.” the preceding months. How many and which types of servers
Mr. Hamilton turns to Emily Jones, the head of Corporate should she purchase in each month? How much is the total
Information Management. “I need your help in planning for the cost of the plan?
installation of the intranet. Specifically, the company needs to b. Emily realizes that she could perhaps achieve savings if she
purchase servers for the internal network. Employees will con- bought a larger server in the initial months to support users in
nect to company servers and download information to their own the final months. She therefore decides to evaluate the num-
desktop computers.” ber and type of servers to purchase over the entire planning
Mr. Hamilton passes Emily the following chart detailing the period. Formulate a spreadsheet model to determine which
types of servers available, the number of employees each server servers Emily should purchase in which months to minimize
supports, and the cost of each server. total cost and support all new users. How many and which
Number of Employees
Type of Server Server Supports Cost of Server
Standard Intel Pentium PC Up to 30 employees $ 2,500

Enhanced Intel Pentium PC Up to 80 employees 5,000
SGI Workstation Up to 200 employees 10,000
Sun Workstation Up to 2,000 employees 25,000
“Emily, I need you to decide what servers to purchase and types of servers should she purchase in each month? How
when to purchase them to minimize cost and to ensure that the much is the total cost of the plan?
company possesses enough server capacity to follow the intranet c. Why is the answer using the first method different from that
implementation timeline,” Mr. Hamilton says. “For example, using the second method?
you may decide to buy one large server during the first month d. Are there other costs for which Emily is not accounting in her
to support all employees, or buy several small servers during problem formulation? If so, what are they?
the first month to support all employees, or buy one small server
e. What further concerns might the various departments of
each month to support each new group of employees gaining
CommuniCorp have regarding the intranet?
access to the intranet.”
Case 3-3
Fabrics and Fall Fashions
From the 10th floor of her office building, Katherine Rally Today is an especially important day because she must meet
watches the swarms of New Yorkers fight their way through the with Ted Lawson, the production manager, to decide upon next
streets infested with yellow cabs and the sidewalks littered with month’s production plan for the fall line. Specifically, she must
hot dog stands. On this sweltering July day, she pays particular determine the quantity of each clothing item she should produce
attention to the fashions worn by the various women and won- given the plant’s production capacity, limited resources, and
ders what they will choose to wear in the fall. Her thoughts are demand forecasts. Accurate planning for next month’s production
not simply random musings; they are critical to her work since is critical to fall sales since the items produced next month will
she owns and manages TrendLines, an elite women’s clothing appear in stores during September and women generally buy the
company. majority of the fall fashions when they first appear in September.
hil24064_ch03_064-123.indd 116 02/11/12 4:55 PM

Confirming Pages
Case 3-3 Fabrics and Fall Fashions 117
She turns back to her sprawling glass desk and looks at the Any material that is not used in production can be sent back to
numerous papers covering it. Her eyes roam across the clothing the textile wholesaler for a full refund, although scrap material
patterns designed almost six months ago, the lists of material cannot be sent back to the wholesaler.
requirements for each pattern, and the lists of demand forecasts She knows that the production of both the silk blouse and cot-
for each pattern determined by customer surveys at fashion ton sweater leaves leftover scraps of material. Specifically, for
shows. She remembers the hectic and sometimes nightmarish the production of one silk blouse or one cotton sweater, 2 yards
days of designing the fall line and presenting it at fashion shows of silk and cotton, respectively, are needed. From these 2 yards,
in New York, Milan, and Paris. Ultimately, she paid her team 1.5 yards are used for the silk blouse or the cotton sweater and
of six designers a total of $860,000 for their work on her fall 0.5 yard is left as scrap material. She does not want to waste the
line. With the cost of hiring runway models, hair stylists, and material, so she plans to use the rectangular scrap of silk or cot-
make-up artists; sewing and fitting clothes; building the set; ton to produce a silk camisole or cotton miniskirt, respectively.
choreographing and rehearsing the show; and renting the confer- Therefore, whenever a silk blouse is produced, a silk camisole
ence hall, each of the three fashion shows cost her an additional is also produced. Likewise, whenever a cotton sweater is pro-
$2,700,000. duced, a cotton miniskirt is also produced. Note that it is pos-
She studies the clothing patterns and material requirements. sible to produce a silk camisole without producing a silk blouse
Her fall line consists of both professional and casual fashions. and a cotton miniskirt without producing a cotton sweater.
She determined the price for each clothing item by taking into The demand forecasts indicate that some items have lim-
account the quality and cost of material, the cost of labor and ited demand. Specifically, because the velvet pants and velvet
machining, the demand for the item, and the prestige of the shirts are fashion fads, TrendLines has forecasted that it can
TrendLines brand name. sell only 5,500 pairs of velvet pants and 6,000 velvet shirts.
The fall professional fashions include. TrendLines does not want to produce more than the forecasted
Clothing Item Material Requirements Price Labor and Machine Cost
Tailored wool slacks 3 yards of wool $300 $160

2 yards of acetate for lining
Cashmere sweater 1.5 yards of cashmere 450 150
Silk blouse 1.5 yards of silk 180 100
Silk camisole 0.5 yard of silk 120 60
Tailored skirt 2 yards of rayon 270 120
1.5 yards of acetate for lining
Wool blazer 2.5 yards of wool 320 140
1.5 yards of acetate for lining
The fall casual fashions include.
Clothing Item Material Requirements Price Labor and Machine Cost
Velvet pants 3 yards of velvet $350 $175

2 yards of acetate for lining
Cotton sweater 1.5 yards of cotton 130 60
Cotton miniskirt 0.5 yard of cotton 75 40
Velvet shirt 1.5 yards of velvet 200 160
Button-down blouse 1.5 yards of rayon 120 90
She knows that for the next month, she has ordered 45,000 demand because once the pants and shirts go out of style, the
yards of wool, 28,000 yards of acetate, 9,000 yards of cashmere, company cannot sell them. TrendLines can produce less than the
18,000 yards of silk, 30,000 yards of rayon, 20,000 yards of vel- forecasted demand, however, since the company is not required
vet, and 30,000 yards of cotton for production. The prices of the to meet the demand. The cashmere sweater also has limited
materials are listed below. demand because it is quite expensive, and TrendLines knows it
can sell at most 4,000 cashmere sweaters. The silk blouses and
Material Price per Yard camisoles have limited demand because many women think silk
is too hard to care for, and TrendLines projects that it can sell at
Wool $ 9.00 most 12,000 silk blouses and 15,000 silk camisoles.
Acetate 1.50 The demand forecasts also indicate that the wool slacks,
Cashmere 60.00
tailored skirts, and wool blazers have a great demand because
Silk 13.00
Rayon 2.25
they are basic items needed in every professional wardrobe.
Velvet 12.00 Specifically, the demand is 7,000 pairs of wool slacks and 5,000
Cotton 2.50 wool blazers. Katherine wants to meet at least 60 percent of the
demand for these two items to maintain her loyal customer base
hil24064_ch03_064-123.indd 117 02/11/12 4:55 PM

Confirming Pages
and not lose business in the future. Although the demand for tai- therefore get no refund for the velvet. How does this fact
lored skirts could not be estimated, Katherine feels she should change the production plan?
make at least 2,800 of them. d. What is an intuitive economic explanation for the difference
between the solutions found in parts b and c?
a. Ted is trying to convince Katherine not to produce any velvet
shirts since the demand for this fashion fad is quite low. He e. The sewing staff encounters difficulties sewing the arms and
argues that this fashion fad alone accounts for $500,000 of lining into the wool blazer since the blazer pattern has an
the fixed design and other costs. The net contribution (price awkward shape and the heavy wool material is difficult to
of clothing item – materials cost – labor cost) from selling cut and sew. The increased labor time to sew a wool blazer
the fashion fad should cover these fixed costs. Each velvet increases the labor and machine cost for each blazer by $80.
shirt generates a net contribution of $22. He argues that given Given this new cost, how many of each clothing item should
the net contribution, even satisfying the maximum demand TrendLines produce to maximize profit?
will not yield a profit. What do you think of Ted’s argument? f. The textile wholesaler informs Katherine that since another
b. Formulate and solve a linear programming problem to maxi- textile customer canceled his order, she can obtain an extra
mize profit given the production, resource, and demand 10,000 yards of acetate. How many of each clothing item
constraints. should TrendLines now produce to maximize profit?
Before she makes her final decision, Katherine plans to explore g. TrendLines assumes that it can sell every item that was not
the following questions independently, except where otherwise sold during September and October in a big sale in Novem-
indicated. ber at 60 percent of the original price. Therefore, it can sell
all items in unlimited quantity during the November sale.
c. The textile wholesaler informs Katherine that the velvet can- (The previously mentioned upper limits on demand only con-
not be sent back because the demand forecasts show that the cern the sales during September and October.) What should
demand for velvet will decrease in the future. Katherine can the new production plan be to maximize profit?
Case 3-4
New Frontiers
Rob Richman, president of AmeriBank, takes off his glasses, Internet allows this convenient transaction method. Over the
rubs his eyes in exhaustion, and squints at the clock in his study. Internet, customers are able to perform transactions on their
It reads 3 am. For the last several hours, Rob has been por- desktop computers either at home or work. The explosion of the
ing over AmeriBank’s financial statements from the last three Internet means that many potential customers understand and
quarters of operation. AmeriBank, a medium-sized bank with use the World Wide Web. He therefore feels that if AmeriBank
branches throughout the United States, is headed for dire eco- offers Web banking (as the practice of Internet banking is com-
nomic straits. The bank, which provides transaction, savings, monly called), the bank will attract many new customers.
investment, and loan services, has been experiencing a steady Before Rob undertakes the project to make Web banking
decline in its net income over the past year, and trends show that possible, however, he needs to understand the market for Web
the decline will continue. The bank is simply losing customers to banking and the services AmeriBank should provide over the
nonbank and foreign bank competitors. Internet. For example, should the bank only allow customers to
AmeriBank is not alone in its struggle to stay out of the red. access account balances and historical transaction information
From his daily industry readings, Rob knows that many American over the Internet, or should the bank develop a strategy to allow
banks have been suffering significant losses because of increasing customers to make deposits and withdrawals over the Internet?
competition from nonbank and foreign bank competitors offering Should the bank try to recapture a portion of the investment mar-
services typically in the domain of American banks. Because the ket by continuously running stock prices and allowing customers
nonbank and foreign bank competitors specialize in particular ser- to make stock transactions over the Internet for a minimal fee?
vices, they are able to better capture the market for those services Because AmeriBank is not in the business of performing
by offering less expensive, more efficient, more convenient ser- surveys, Rob has decided to outsource the survey project to a
vices. For example, large corporations now turn to foreign banks professional survey company. He has opened the project up for
and commercial paper offerings for loans, and affluent Americans bidding by several survey companies and will award the proj-
now turn to money-market funds for investment. Banks face the ect to the company that is willing to perform the survey for the
daunting challenge of distinguishing themselves from nonbank least cost. Rob provided each survey company with a list of sur-
and foreign bank competitors. vey requirements to ensure that AmeriBank receives the needed
Rob has concluded that one strategy for distinguishing information for planning the Web banking project.
AmeriBank from its competitors is to improve services that Because different age groups require different services,
nonbank and foreign bank competitors do not readily pro- AmeriBank is interested in surveying four different age groups.
vide: transaction services. He has decided that a more conve- The first group encompasses customers who are 18 to 25 years
nient transaction method must logically succeed the automatic old. The bank assumes that this age group has limited yearly
teller machine, and he believes that electronic banking over the income and performs minimal transactions. The second group
hil24064_ch03_064-123.indd 118 02/11/12 4:55 PM

Confirming Pages
Case 3-5 Assigning Students to Schools 119
encompasses customers who are 26 to 40 years old. This age c. After submitting its bid, Sophisticated Surveys is informed
group has significant sources of income, performs many trans- that it has the lowest cost but that AmeriBank does not like
actions, requires numerous loans for new houses and cars, and the solution. Specifically, Rob feels that the selected survey
invests in various securities. The third group encompasses cus- population is not representative enough of the banking cus-
tomers who are 41 to 50 years old. These customers typically tomer population. Rob wants at least 50 people of each age
have the same level of income and perform the same number group surveyed in each region. What is the new bid made by
of transactions as the second age group, but the bank assumes Sophisticated Surveys?
that these customers are less likely to use Web banking since d. Rob feels that Sophisticated Surveys oversampled the 18-to-
they have not become as comfortable with the explosion of com- 25-year-old population and the Silicon Valley population. He
puters or the Internet. Finally, the fourth group encompasses imposes a new constraint that no more than 600 individuals
customers who are 51 years of age and over. These customers can be surveyed from the 18-to-25-year-old population and
commonly crave security and require continuous information no more than 650 individuals can be surveyed from the Sili-
on retirement funds. The bank believes that it is highly unlikely con Valley population. What is the new bid?
that customers in this age group will use Web banking, but the e. When Sophisticated Surveys calculated the cost of reaching
bank desires to learn the needs of this age group for the future. and surveying particular individuals, the company thought
AmeriBank wants to interview 2,000 customers with at least 20 that reaching individuals in young populations would be
percent from the first age group, at least 27.5 percent from the easiest. In a recently completed survey, however, Sophisti-
second age group, at least 15 percent from the third age group, cated Surveys learned that this assumption was wrong. The
and at least 15 percent from the fourth age group. new costs for surveying the 18-to-25-year-old population are
Rob understands that some customers are uncomfortable listed below.
with using the Internet. He therefore wants to ensure that the
survey includes a mix of customers who know the Internet well
and those that have less exposure to the Internet. To ensure Region Cost per Person
that AmeriBank obtains the correct mix, he wants to interview
at least 15 percent of customers from the Silicon Valley where Silicon Valley $6.50
Internet use is high, at least 35 percent of customers from big Big cities 6.75
Small towns 7.00
cities where Internet use is medium, and at least 20 percent of
customers from small towns where Internet use is low.
Sophisticated Surveys is one of three survey companies Given the new costs, what is the new bid?
competing for the project. It has performed an initial analysis f. To ensure the desired sampling of individuals, Rob imposes
of these survey requirements to determine the cost of surveying even stricter requirements. He fixes the exact percentage of
different populations. The costs per person surveyed are listed in people that should be surveyed from each population. The
the following table. requirements are listed next.
Age Group
Population Percentage of People Surveyed
Region 18 to 25 26 to 40 41 to 50 51 and over
18 to 25 25%
Silicon Valley $4.75 $6.50 $6.50 $5.00 26 to 40 35
Big cities 5.25 5.75 6.25 6.25 41 to 50 20
Small towns 6.50 7.50 7.50 7.25 51 and over 20
Silicon Valley 20
Sophisticated Surveys explores the following options Big cities 50
cumulatively. Small towns 30
a. Formulate a linear programming model to minimize costs

while meeting all survey constraints imposed by AmeriBank. By how much would these new requirements increase the cost
b. If the profit margin for Sophisticated Surveys is 15 percent of of surveying for Sophisticated Surveys? Given the 15 percent
cost, what bid will it submit? profit margin, what would Sophisticated Surveys bid?
Case 3-5
Assigning Students to Schools
The Springfield School Board has made the decision to close school students to the three remaining middle schools. The
one of its middle schools (sixth, seventh, and eighth grades) at school district provides busing for all middle school students
the end of this school year and reassign all of next year’s middle who must travel more than approximately a mile, so the school
hil24064_ch03_064-123.indd 119 02/11/12 4:55 PM

Confirming Pages
board wants a plan for reassigning the students that will mini- How much does this increase the total busing cost? (This line
mize the total busing cost. The annual cost per student for busing of analysis will be pursued more rigorously in Case 7-3.)
from each of the six residential areas of the city to each of the
schools is shown in the following table (along with other basic The school board is considering eliminating some busing to
data for next year), where 0 indicates that busing is not needed reduce costs. Option 1 is to only eliminate busing for students trav-
and a dash indicates an infeasible assignment. eling 1 to 1.5 miles, where the cost per student is given in the table
Busing Cost per Student
Number of Percentage Percentage Percentage

Area Students in 6th Grade in 7th Grade in 8th Grade School 1 School 2 School 3
1 450 32 38 30 $300 $ 0 $700

2 600 37 28 35 — 400 500
3 550 30 32 38 600 300 200
4 350 28 40 32 200 500 —
5 500 39 34 27 0 — 400
6 450 34 28 38 500 300 0
School capacity: 900 1,100 1,000
The school board also has imposed the restriction that each as $200. Option 2 is to also eliminate busing for students traveling
grade must constitute between 30 and 36 percent of each school’s 1.5 to 2 miles, where the estimated cost per student is $300.
population. The above table shows the percentage of each area’s
d. Revise the model from part a to fit Option 1, and solve. Com-
middle school population for next year that falls into each of
pare these results with those from part b, including the reduc-
the three grades. The school attendance zone boundaries can be
tion in total busing cost.
drawn so as to split any given area among more than one school,
but assume that the percentages shown in the table will continue e. Repeat part d for Option 2.
to hold for any partial assignment of an area to a school. The school board now needs to choose among the three alter-
You have been hired as a management science consultant native busing plans (the current one or Option 1 or Option 2).
to assist the school board in determining how many students in One important factor is busing costs. However, the school board
each area should be assigned to each school. also wants to place equal weight on a second factor: the inconve-
nience and safety problems caused by forcing students to travel
a. Formulate and solve a linear programming model for this
by foot or bicycle a substantial distance (more than a mile, and
problem.
especially more than 1.5 miles). Therefore, they want to choose
b. What is your resulting recommendation to the school board? a plan that provides the best trade-off between these two factors.
After seeing your recommendation, the school board f. Use your results from parts b, d, and e to summarize the key
expresses concern about all the splitting of residential areas information related to these two factors that the school board
among multiple schools. They indicate that they “would like to needs to make this decision.
keep each neighborhood together.” g. Which decision do you think should be made? Why?
c. Adjust your recommendation as well as you can to enable Note: This case will be continued in later chapters (Cases 5-4
each area to be assigned to just one school. (Adding this and 7-3), so we suggest that you save your analysis, including
restriction may force you to fudge on some other constraints.) your basic spreadsheet model.
Case 3-6
Reclaiming Solid Wastes
The Save-It Company operates a reclamation center that collects as a percentage of the total weight for that product grade.) For each
four types of solid waste materials and then treats them so that they of the two higher grades, a fixed percentage is specified for one of
can be amalgamated (treating and amalgamating are separate pro- the materials. These specifications are given in the first table along
cesses) into a salable product. Three different grades of this prod- with the cost of amalgamation and the selling price for each grade.
uct can be made, depending on the mix of the materials used. (See The reclamation center collects its solid waste materials
the first table.) Although there is some flexibility in the mix for from some regular sources and so is normally able to maintain a
each grade, quality standards specify the minimum or maximum steady rate for treating them. The second table gives the quanti-
amount of the materials allowed in that product grade. (This mini- ties available for collection and treatment each week, as well as
mum or maximum amount is the weight of the material expressed the cost of treatment, for each type of material.
hil24064_ch03_064-123.indd 120 02/11/12 4:55 PM

Confirming Pages
Case 3-7 Project Pickings 121
Amalgamation Selling Price

Grade Specification Cost per Pound per Pound
Material 1: Not more than 30% of the total

A Material 2: Not less than 40% of the total $3.00 $8.50
Material 4: Exactly 20% of the total
B Material 2: Not less than 10% of the total 2.50 7.00
Material 4: Exactly 10% of the total
C Material 1: Not more than 70% of the total 2.00 5.50
Available Treatment Cost

Material Pounds/Week per Pound Additional Restrictions
1 3,000 $3.00 1. For each material, at least half

2 2,000 6.00 of the pounds/week available
3 4,000 4.00 should be collected and treated.
4 1,000 5.00 2. $30,000 per week should be
used to treat these materials.
The Save-It Company is solely owned by Green Earth, maximize the total weekly profit (total sales income minus total
an organization that is devoted to dealing with environmen- amalgamation cost).
tal issues; Save-It’s profits are all used to help support Green
Earth’s activities. Green Earth has raised contributions and a. Formulate this problem in linear programming terms by
grants, amounting to $30,000 per week, to be used exclusively to identifying all the activities, resources, benefits, and fixed
cover the entire treatment cost for the solid waste materials. The requirements that lurk within it.
board of directors of Green Earth has instructed the management b. Formulate and solve a spreadsheet model for this linear pro-
of Save-It to divide this money among the materials in such a gramming problem.
way that at least half of the amount available of each material is c. Express this linear programming model in the spreadsheet in
actually collected and treated. These additional restrictions are algebraic form.
listed in the second table.
Within the restrictions specified in the two tables, manage-
ment wants to allocate the materials to product grades so as to
Case 3-7
Project Pickings
Tazer, a pharmaceutical manufacturing company, entered the Now Tazer is beginning to fear the pressure of competition.
pharmaceutical market 15 years ago with the introduction of six Tazer knows that once the patent expires in five years, generic
new drugs. Five of the six drugs were simply permutations of drug manufacturing companies will swarm into the market like
existing drugs and therefore did not sell very heavily. The sixth vultures. Historical trends show that generic drugs decrease
drug, however, addressed hypertension and was a huge success. sales of branded drugs by 75 percent.
Since Tazer had a patent on the hypertension drug, it experienced Tazer is therefore looking to invest significant amounts of
no competition, and profits from the hypertension drug alone money in research and development this year to begin the search
kept Tazer in business. Pharmaceutical patents remain in force for a new breakthrough drug that will offer the company the
for 20 years, so this one has five more years before it expires. same success as the hypertension drug. Tazer believes that if
During the past 15 years, Tazer continued a moderate amount the company begins extensive research and development now,
of research and development, but it never stumbled upon a drug the probability of finding a successful drug shortly after the
as successful as the hypertension drug. One reason is that the expiration of the hypertension patent will be high.
company never had the motivation to invest heavily in innova- As head of research and development at Tazer, you are
tive research and development. The company was riding the profit responsible for choosing potential projects and assigning project
wave generated by its hypertension drug and did not feel the need directors to lead each of the projects. After researching the needs
to commit significant resources to finding new drug breakthroughs. of the market, analyzing the shortcomings of current drugs,
hil24064_ch03_064-123.indd 121 02/11/12 4:55 PM

Confirming Pages
and interviewing numerous scientists concerning the promising Project Up: 20

areas of medical research, you have decided that your depart- Project Stable: 450
ment will pursue five separate projects, which are listed below: Project Choice: 451
Project Up: Develop a more effective antidepressant that Project Hope: 39
does not cause serious mood swings. Project Release: 40
Project Stable: Develop a drug that addresses
manic-depression. Under these new conditions with just four senior scien-
tists, which scientists will lead which projects to maximize
Project Choice: Develop a less intrusive birth control
preferences?
method for women.
e. Do you support the assignments found in part d? Why or
Project Hope: Develop a vaccine to prevent HIV infection.
why not?
Project Release: Develop a more effective drug to lower
f. Now you again consider all five scientists. You decide, how-
blood pressure.
ever, that several scientists cannot lead certain projects. In par-
For each of the five projects, you are only able to specify the ticular, Dr. Mickey does not have experience with research on
medical ailment the research should address since you do not the immune system, so he cannot lead Project Hope. His fam-
know what compounds will exist and be effective without ily also has a history of manic-depression, and you feel that he
research. would be too personally involved in Project Stable to serve as
You also have five senior scientists to lead the five projects. an effective project leader. Dr. Mickey therefore cannot lead
You know that scientists are very temperamental people and will Project Stable. Dr. Kvaal also does not have experience with
only work well if they are challenged and motivated by the proj- research on the immune system and cannot lead Project Hope.
ect. To ensure that the senior scientists are assigned to projects In addition, Dr. Kvaal cannot lead Project Release because he
they find motivating, you have established a bidding system for does not have experience with research on the cardiovascular
the projects. You have given each of the five scientists 1,000 bid system. Finally, Dr. Rollins cannot lead Project Up because
points. They assign bids to each project, giving a higher number her family has a history of depression and you feel she would
of bid points to projects they most prefer to lead. be too personally involved in the project to serve as an effec-
The following table provides the bids from the five senior tive leader. Because Dr. Mickey and Dr. Kvaal cannot lead
scientists for the five individual projects. two of the five projects, they each have only 600 bid points.
Project Dr. Kvaal Dr. Zuner Dr. Tsai Dr. Mickey Dr. Rollins
Project Up 100 0 100 267 100

Project Stable 400 200 100 153 33
Project Choice 200 800 100 99 33
Project Hope 200 0 100 451 34
Project Release 100 0 600 30 800
You decide to evaluate a variety of scenarios you think are Dr. Rollins has only 800 bid points because she cannot lead
likely. one of the five projects. The following table provides the new
a. Given the bids, you need to assign one senior scientist to bids of Dr. Mickey, Dr. Kvaal, and Dr. Rollins.
each of the five projects to maximize the preferences of the
scientists. What are the assignments? Project Dr. Mickey Dr. Kvaal Dr. Rollins
b. Dr. Rollins is being courted by Harvard Medical School to Project Up 300 86 Can’t lead
accept a teaching position. You are fighting desperately to Project Stable Can’t lead 343 50
keep her at Tazer, but the prestige of Harvard may lure her Project Choice 125 171 50
away. If this were to happen, the company would give up the Project Hope Can’t lead Can’t lead 100
project with the least enthusiasm. Which project would not Project Release 175 Can’t lead 600
be done?
c. You do not want to sacrifice any project since researching Which scientists should lead which projects to maximize
only four projects decreases the probability of finding a preferences?
breakthrough new drug. You decide that either Dr. Zuner or g. You decide that Project Hope and Project Release are too
Dr. Mickey could lead two projects. Under these new con- complex to be led by only one scientist. Therefore, each of
ditions with just four senior scientists, which scientists will these projects will be assigned two scientists as project lead-
lead which projects to maximize preferences? ers. You decide to hire two more scientists in order to staff
d. After Dr. Zuner was informed that she and Dr. Mickey are all projects: Dr. Arriaga and Dr. Santos. Because of religious
being considered for two projects, she decided to change her reasons, neither of them want to lead Project Choice and so
bids. Dr. Zuner’s new bids for each of the projects are they assign 0 bid points to this project. The next table lists all
shown next. projects, scientists, and their bids.
hil24064_ch03_064-123.indd 122 02/11/12 4:55 PM

Confirming Pages
Additional Cases 123
Project Dr. Kvaal Dr. Zuner Dr. Tsai Dr. Mickey Dr. Rollins Dr. Arriaga Dr. Santos
Project Up 86 0 100 300 Can’t lead 250 111

Project Stable 343 200 100 Can’t lead 50 250 1
Project Choice 171 800 100 125 50 0 0
Project Hope Can’t lead 0 100 Can’t lead 100 250 333
Project Release Can’t lead 0 600 175 600 250 555
Which scientists should lead which projects to maximize

preferences?
Additional Cases
h. Do you think it is wise to base your decision in part g Additional cases for this chapter are also available at the
only on an optimal solution for a variant of an assignment University of Western Ontario Ivey School of Business website,
problem? cases.ivey.uwo.ca/cases, in the segment of the CaseMate area
designated for this book.
hil24064_ch03_064-123.indd 123 09/11/12 4:53 PM

Chapter Three: Linear Programming: Formulation and Applications

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

Chapter Three: Linear Programming: Formulation and Applications

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chapter Three: Linear Programming: Formulation and Applications

Uploaded by

Copyright:

Available Formats

Confirming Pages

1. Recognize various kinds of managerial problems to which linear programming can be

hil24064_ch03_064-123.indd 64 02/11/12 4:54 PM

3.1 A Case Study: The Super Grain Corp. Advertising-Mix Problem 65

3.1 A CASE STUDY: THE SUPER GRAIN CORP. ADVERTISING-MIX

hil24064_ch03_064-123.indd 65 02/11/12 4:54 PM

66 Chapter Three Linear Programming: Formulation and Applications

Analysis of the Problem

hil24064_ch03_064-123.indd 66 02/11/12 4:54 PM

3.1 A Case Study: The Super Grain Corp. Advertising-Mix Problem 67

Range Name Cells

hil24064_ch03_064-123.indd 67 02/11/12 4:54 PM

68 Chapter Three Linear Programming: Formulation and Applications

Total spending on advertising 5 300TV 1 150M 1 100SS

hil24064_ch03_064-123.indd 68 02/11/12 4:54 PM

3.1 A Case Study: The Super Grain Corp. Advertising-Mix Problem 69

Exposure 5 1,300TV 1 600M 1 500SS

Summary of the Formulation

Solving the Model

Do not run any television commercials.

Evaluation of the Adequacy of the Model

hil24064_ch03_064-123.indd 69 02/11/12 4:54 PM

70 Chapter Three Linear Programming: Formulation and Applications

hil24064_ch03_064-123.indd 70 02/11/12 4:54 PM

3.2 Resource-Allocation Problems 71

Review 1. What is the problem being addressed in this case study?

3.2 RESOURCE-ALLOCATION PROBLEMS

Amount of resource used # Amount of resource available

for one of the resources.

The Super Grain Corp. Advertising-Mix Problem

hil24064_ch03_064-123.indd 71 02/11/12 4:54 PM

72 Chapter Three Linear Programming: Formulation and Applications

An initial step in formulat- The resources to be allocated to these activities are

Characteristics of Resource-Allocation Problems

The Wyndor Glass Co. Product-Mix Problem

hil24064_ch03_064-123.indd 72 02/11/12 4:54 PM

3.2 Resource-Allocation Problems 73

The resources to be allocated to these activities are

The TBA Airlines Problem

hil24064_ch03_064-123.indd 73 02/11/12 4:54 PM

74 Chapter Three Linear Programming: Formulation and Applications

hil24064_ch03_064-123.indd 74 02/11/12 4:54 PM

3.2 Resource-Allocation Problems 75

Summary of the Formulation

hil24064_ch03_064-123.indd 75 02/11/12 4:54 PM

hil24064_ch03_064-123.indd 76 02/11/12 4:54 PM

3.2 Resource-Allocation Problems 77

hil24064_ch03_064-123.indd 77 02/11/12 4:54 PM

78 Chapter Three Linear Programming: Formulation and Applications

(C5:E5), CapitalRequired (C9:E12), and CapitalAvailable (H9:H12). To save space on the

hil24064_ch03_064-123.indd 78 02/11/12 4:54 PM

3.2 Resource-Allocation Problems 79

where all these numbers are in units of millions of dollars.

hil24064_ch03_064-123.indd 79 02/11/12 4:54 PM

80 Chapter Three Linear Programming: Formulation and Applications

Another Look at Resource Constraints

Summary of the Formulation Procedure for Resource-Allocation

hil24064_ch03_064-123.indd 80 02/11/12 4:54 PM