Baker K.R. Optimization Modeling with Spreadsheets
Подождите немного. Документ загружается.
asymmetric set of precedence arrows might suggest where a logical error can be
found.
†
Invoke the Cell Edit function. Selecting a formula cell and pressing the func-
tion key F2 can implement a similar kind of validation. The Cell Edit function
displays a color-coded interpretation of the formula, highlighting its constituent
cells. In linear programming models, this kind of verification might catch a for-
mula in which the range was entered or pasted incorrectl y.
†
Use the Change Constraint option. Another way to verify that ranges are cor-
rectly entered involves the Change Constraint window. In the Model tab,
double-click the icon for a particular constraint entry. Then the LHS’s of the
selected constraints are highlighted in the model when the Change Constraint
window appears. This step can sometimes detect an error in specifying the
location of a constraint, especially in complicated models where constraints
might be arranged separately, at different locations on the worksheet.
2.5.3. Logic
In Chapter 1, we pointed out the distinction between the convergence message and the
optimality message in finding an optimal solution with the nonlinear solver. When we
use the linear solver, that distinction does not arise. If we formulate a model that is
feasible and bounded and if we use the linear solver, then the optimality message
appears every time; we do not need to rerun Solver.
Figure 2.18. Formula Auditing with the trace precedence command.
56 Chapter 2 Linear Programming: Allocation, Covering, and Blending Models
SUMMARY
This chapter has introduced three classes of linear programming models: allocation, covering,
and blending. To some extent, these elementary models allow us to discuss the basic scenarios
that lend themselves to linear programming models, so allocation, covering, and blending
models might well be taken as the “ABC” of model building with linear programming.
Allocation, covering and blending models are also important as building blocks for more com-
plex models because many practical applications are combinations of these structures.
Linearity in both the objective function and constraints is the key structural assumption in
linear programming. In the process of building a linear programming model, it is desirable to
revisit the requirements of proportionality, additivity, and divisibility, to confirm that their prop-
erties apply. Another less prominent assumption is the presumption of certainty in the elements
of a linear programming model. Most of the time, linear programs are applied in situations where
uncertainty can be suppressed without undermining the value of the model. Nevertheless,
advanced forms of linear programming extend to situations where the uncertainty cannot be
avoided. Appendix 4 introduces Stochastic Programming, to suggest how linear programming
can be adapted to problems containing uncertainty.
Classification of linear programming models provides some immediate benefits. When we
are trying to understand someone else’s model, our ability to classify may help us appreciate
either the overall structure of a model or some of its major parts. Also, when we are trying to
develop a model from scratch, we can accelerate the process if we can classify the model or
at least one portion of it. Model building requires that we recognize situations that lend them-
selves to representation in a model. Familiarity with the elementary scenarios that go with allo-
cation, covering, and blending helps us to recognize structure in an actual situation. Finally,
when we are debugging our own model, classification allows us to compare what we have
built with the standard template. That comparison helps us to detect mistakes we may have
made in constraint coefficients and constants or perhaps even in objective function coefficients.
Also included in this chapter were a number of suggestions for debugging that apply throughout
the remainder of the book.
The classification of linear programs is not as precise as, say, biological classification. As
we saw, a linear program can combine types. Although we will encounter additional classes of
models in the next three chapters, we will not attempt to classify every possible linear program.
Instead, the purpose is to appreciate the kinds of situations that lend themselves well to linear
programming. Then, when we encounter similar situations in the world around us, we’ll be
able to think about those situations in terms of a corresponding linear programming structure.
Armed with knowledge of these building blocks, we can analyze new situations by recognizing
familiar structures within them, thus identifying some of the important elements (variables and
constraints) of the eventual model.
EXERCISES
2.1. Brown Furniture Revisited Revisit the Brown Furniture allocation example of this
chapter. As plans are being made for a new quarter, a revised set of figures on resource
availabilities is compiled. The new resource limits are as follows.
Fabrication hours 2000
Assembly hours 1800
Machining hours 1600
Wood supply 9400
Exercises 57
The other data, on profit contributions and resource consumptions, all remain unchanged.
(a) What are the optimal production quantities of chairs, desks and tables?
(b) What is the maximum profit contribution?
(c) Which constraints are binding in the optimal solution?
2.2. Allocating Ingredients The Pizza Man is a local shop that plans to make all of its sales
this Saturday from its sidewalk tables during the town’s holiday parade. On this occasion,
the shop’s owners know that customers will buy by the slice and any kind of pizza offered
will sell. The Pizza Man offers plain, meat, vegetable, and supreme pizzas. Each variety
has its own requirement for sauce, cheese, dough, and toppings (in ounces, as shown in
the table), and each has its own selling price.
Plain Meat Vegetable Supreme Available
Dough 5 5 5 5 200
Sauce 3 3 3 3 90
Cheese 4 3 3 4 120
Meat 0 3 0 2 75
Vegetables 0 0 3 2 40
Price $8 $10 $12 $15
The Pizza Man expects to use its entire stock of ingredients and wishes to maximize rev-
enue from its sales.
(a) What mix of pizzas should be made? (Assume that fractions can be sold.)
(b) What is the maximum sales revenue?
(c) Which ingredients are economically scarce (limit profits)?
2.3. Workforce Scheduling The Operations Manager at the Metropolis National Bank
has a staffing problem. Demand for clerical staff varies throughout the day, but 24-
hour coverage is necessary because the bank handles a number of international trans-
actions. A recent study has shown how many clerical workers are needed each hour in
the course of the day, as shown below. (Hour 1 is from midnight to 1am.)
Hour 1 2 3 4 5 6 7 8 9 10 11 12
Staff 432235669101010
Hour 13 14 15 16 17 18 19 20 21 22 23 24
Staff 12 12 8 6 7 7 7 6 5 4 4 4
Under current labor policies, clerical workers may be assigned to any one of six shifts,
some of which overlap. The shifts and salary costs are as follows.
58 Chapter 2 Linear Programming: Allocation, Covering, and Blending Models
Shift Daily cost
2 am–10 am $160
6 am–2 pm $145
10 am–6 pm $148
2 pm–10 pm $154
6 pm–2 am $156
10 pm–6 am $160
(a) Provide the operations manager with a schedule that will deploy enough staff to meet
the hourly requirements at the minimum daily total cost.
(b) In the optimal schedule, how many hours are overstaffed?
2.4. Selecting a Portfolio A portfolio manager has developed a list of six investment
alternatives for a multiyear horizon. These are: Treasury bills, Common stock,
Corporate bonds, Real estate, Growth funds, and Savings and Loans. These investments
and their various financial factors are described below. In the table, the length represents
the estimated number of years required for the annual rate of return to be realized. The
annual rate of return is the expected rate over the multiyear horizon. The risk coefficient
is a subjective estimate representing the manager’s appraisal of the relative safety of each
alternative, on a scale of 10. The growth potential is also a subjective estimate of the
potential increase in value over the horizon.
Portfolio data
Alternative TB CS CB RE GF SL
Length 4 7 8 6 10 5
Annual return (%) 6 15 12 24 18 9
Risk coefficient 1 5 4 8 6 3
Growth potential (%) 0 18 10 32 20 7
The manager wishes to maximize the annual rate of return on a $3 million portfolio,
subject to the following restrictions.
The weighted average length should not exceed 7 years.
The weighted average risk coefficient should not exceed five.
The weighted average growth potential should be at least 10 percent.
The investment in real estate should be no more than twice the investment in stocks
and bonds (i.e. in CS, CB, and GF) combined.
(a) What is the optimal return (as a percentage) and the optimal allocation of investment
funds?
(b) What is the marginal rate of return? In other words, what would be the return on the
next dollar invested, if there were one more dollar in the portfolio?
(c) For additional investment beyond the original $3 million, how will the optimal
allocation change?
Exercises
59
2.5. Oil Blending An oil company produces three brands of oil: Regular, Multigrade, and
Supreme. Each brand of oil is composed of one or more of four crude stocks, each
having a different lubrication index. The relevant data concerning the crude stocks are
as follows.
Crude Lubrication Cost Supply per day
stock index ($/barrel) (barrels)
1 20 7.10 1000
2 40 8.50 1100
3 30 7.70 1200
4 55 9.00 1100
Each brand of oil must meet a minimum standard for a lubrication index, and each brand
thus sells at a different price. The relevant data concerning the three brands of oil are as
follows.
Minimum Selling Daily
lubrication price demand
Brand index ($/barrel) (barrels)
Regular 25 8.50 2000
Multigrade 35 9.00 1500
Supreme 50 10.00 750
Determine an optimal output plan for a single day, assuming that production can be either
sold or else stored at negligible cost.
The daily demand figures are subject to alternative interpretations. Investigate the
following:
(a) The daily demands represent potential sales. In other words, the model should con-
tain demand ceilings (upper limits). What is the optimal profit?
(b) The daily demands are strict obligations. In other words, the model should contain
demand constraints that are met precisely. What is the optimal profit?
(c) The daily demands represent minimum sales commitments, but all output can be
sold. In other words, the model should permit production to exceed the daily commit-
ments. What is the optimal profit?
2.6. Coffee Blending and Sales Hill-O-Beans Coffee Company blends four component
beans into three final blends of coffee: one is sold to luxury hotels, another to restaurants,
and the third to supermarkets for store-label brands. The company has four reliable bean
supplies: Argentine Abundo, Peruvian Colmado, Brazilian Maximo, and Chilean Saboro.
The table below summarizes the very precise recipes for the final coffee blends, the cost
and availability information for the four components, and the wholesale price per pound
of the final blends. The percentages indicate the fraction of each component to be used in
each blend.
60 Chapter 2 Linear Programming: Allocation, Covering, and Blending Models
Component
(pounds)
Cost per Max. weekly
Hotel Rest Market pound availability
Abundo 20% 35% 10% $0.60 40,000
Colmado 40% 15% 35% $0.80 25,000
Maximo 15% 20% 40% $0.55 20,000
Saboro 25% 30% 15% $0.70 45,000
Wholesale price
per pound
$1.25 $1.50 $1.40
The processor’s plant can handle no more than 100,000 lb per week, and Hill-O-Beans
would like to operate at capacity, if possible. Selling the final blends is not a problem,
although the Marketing Department requires minimum production levels of 10,000,
25,000, and 30,000 lb, respectively, for the hotel, restaurant and market blends.
(a) To maximize weekly profit, how many pounds of each component should be
purchased?
(b) How would the optimal profit change if there were a 1000-lb increase in the avail-
ability of Abundo beans? Colmado? Maximo? Saboro?
2.7. Production Planning for Components Rummel Electronics produces two PC cards, a
modem and a network adapter. Demand for these two products exceeds the amount that
the firm can make, but there are no plans to increase production capacity in the short run.
Instead, the firm plans to use subcontracting.
The two main stages of production are fabrication and assembly, and either step can
be subcontracted for either type of card. However, the company policy is not to subcon-
tract both steps for either product. (That is, if modem cards are fabricated by a subcontrac-
tor, then they must be assembled in house.) Components made by subcontractors must
pass through the shipping and receiving departments, just like components made intern-
ally. At present, the firm has 5200 hours available in fabrication, 3600 in assembly and
3200 in shipping/inspection. The production requirements, in hours per unit, are given
in the following table:
Product/mode Fabrication Assembly Shipping
Modem, made entirely in-house 0.35 0.16 0.08
Network, made entirely in-house 0.47 0.15 0.12
Modem, fabricated by sub – 0.18 0.10
Network, fabricated by sub – 0.16 0.15
Modem, assembled by sub 0.35 – 0.09
Network, assembled by sub 0.47 – 0.14
The direct material costs for the modem cards are $3.25 for manufacturing and $0.50
for assembly; for network cards, the costs are $6.10 and $0.50. Subcontracting the man-
ufacturing operation costs $5.35 for modem cards and $8.50 for network cards.
Subcontracting the assembly operation costs $1.50 for either product. Modem cards
Exercises
61
sell for $20, and network cards sell for $28. The firm’s policy, for each product, is that at
most 40% of the units produced can have subcontracted fabrication, and at most 70% of
the units can have subcontracted assembly.
(a) Determine the production and subcontracting schedule that maximizes profits. How
many units of each product should be sold, in the optimal plan? What total volume
should the subcontractor handle?
(b) Which department capacities limit the manufacturing volume? If 100 hours of over-
time could be scheduled, which department(s) should be allocated the overtime?
Explain.
2.8. Production Planning for Automobiles The Auto Company of America (ACA) pro-
duces four types of cars: subcompact, compact, intermediate, and luxury. ACA also pro-
duces trucks and vans. Vendor capacities limit total production capacity to at most
1,200,000 vehicles per year. Subcompacts and compacts are built together in a facility
with a total annual capacity of 620,000 cars. Intermediate and luxury cars are produced
in another facility with capacity of 400,000; and the truck/van facility has a capacity
of 275,000. ACA’s marketing strategy requires that subcompacts and compacts must con-
stitute at least half of the product mix for the four car types. Profit margins, market poten-
tial, and fuel efficiencies are summarized below.
Profit margin Potential sales Fuel efficiency
Type ($/vehicle) (in 000s) (MPG)
Subcompact 150 600 40
Compact 225 400 34
Intermediate 250 300 15
Luxury 500 225 12
Truck 400 325 20
Van 200 100 25
The Corporate Average Fuel Efficiency (CAFE) standards require an average fleet fuel
efficiency of at least 27 MPG. ACA would like to use a linear programming model to
understand the implications of government and corporate policies on its production plans.
(a) What is the optimal annual profit for ACA?
(b) How much would annual profit drop if the fuel efficiency requirement were raised to
28 MPG?
2.9. Production Planning with Environmental Constraints You are the Operations
Manager of Lovejoy Chemicals, Inc., which produces five products in a common
production facility that will be subject to proposed Environmental Protection
Agency (EPA) limits on particulate emissions. For each product, Lovejoy’s sales poten-
tials (demand levels that Lovejoy can capture) are expected to remain relatively flat
for at least the next five years. Relevant data for each product are as follows (note:
T denotes tons).
62 Chapter 2 Linear Programming: Allocation, Covering, and Blending Models
Sales Variable Particulate
potential costs Revenues emissions
Product (T/year) ($/T) ($/T) (T/T produced)
A 2000 700 1000 0.0010
B 1600 600 800 0.0025
C 1000 1000 1500 0.0300
D 1000 1600 2000 0.0400
E 600 1300 1700 0.0250
Your production facility rotates through the product line because it is capable of produ-
cing only one product at a time. The production rates differ for the various products
due to processing needs. It takes 0.3 hours to make one ton of A, 0.5 hours for B, and
one hour each to make a ton of C, D, or E. The facility can be operated up to 4000
hours each year.
The EPA is proposing a “bubble policy” for your industry. In this form of regulation,
imagine that a bubble encloses the manufacturing facility, and only total particulates that
escape the bubble are regulated. This sort of policy replaces historical attempts by the
EPA to micromanage emissions within a firm, and it allows Lovejoy to make any changes
it wishes, provided the total particulate emissions from its facility are kept below certain
limits. The current proposal is to phase-in strict particulate emissions limits over the next
five years. These limits on total particulate emissions are shown in the table below.
Year 1 2 3 4 5
Allowable
emissions
(T/year)
unlimited 80 60 40 20
One strategy for satisfying these regulations is to adjust the product mix, cutting back on
production of some products if necessary. Lovejoy wishes to explore this strategy before
contemplating the addition of new equipment.
(a) Determine the maximum profit Lovejoy can achieve from its product line in the
coming year (Year 1).
(b) By solving a series of models corresponding to the imposition and tightening of the
emissions limit in future years, determine Lovejoy’s maximum profits in each of
Years 2–5.
(c) Consider the emissions limit that applies in Year 4. Determine how much Lovejoy
should be willing to pay at that time to be allowed emissions of one extra ton of
particulates above the limit.
2.10. Cargo Loading You are in charge of loading cargo ships for International Cargo
Company (ICC) at a major East Coast port. You have been asked to prepare a loading
plan for an ICC freight ship bound for Africa. An agricultural commodities dealer
would like to transport the following products aboard this ship.
Exercises
63
Tons Volume per ton Profit per ton
Commodity available (cu. ft) ($)
1 4000 40 70
2 3000 25 50
3 2000 60 60
4 1000 50 80
You can elect to load any and/or all of the available commodities. However, the ship has
three cargo holds with the following capacity restrictions.
Cargo
hold
Weight capacity
(tons)
Volume capacity
(cu. ft)
Forward 3000 100,000
Center 5000 150,000
Rear 2000 120,000
More than one type of commodity can be placed in the same cargo hold. However,
because of balance considerations, the weight in the forward cargo hold must be within
10 percent of the weight in the rear cargo hold, and the center cargo hold must be between
40 percent and 60 percent of the total weight on board.
(a) What is the maximum profit and the loading plan that achieves it? What is the optimal
total weight to be loaded? What is the optimal total volume to be loaded?
(b) Suppose each one of the cargo holds could be expanded. Which holds and which
forms of expansion (weight or volume) would allow ICC to increase its profits on
this trip, and what is the marginal value of each form of expansion?
2.11. Computer Center Staffing You are the Director of the Computer Center for Gaillard
College and responsible for scheduling the staffing of the center. It is open from 8 am
until midnight. You have monitored the usage of the center at various times of the day
and determined that the following numbers of computer consultants are required.
Time of day
Minimum number of
consultants required
to be on duty
8 am–noon 4
Noon– 4 pm 8
4am–8pm 10
8 am–midnight 6
Two types of computer consultants can be hired: full-time and part-time. The full-time
consultants work for eight consecutive hours in any of the following shifts: morning
(8 am –4 pm), afternoon (noon–8 pm), and evening (4 pm –midnight). Full-time consult-
ants are paid $14 per hour.
64 Chapter 2 Linear Programming: Allocation, Covering, and Blending Models
Part-time consultants can be hired to work any of the four shifts listed in the table.
Part-time consultants are paid $12 per hour. An additional requirement is that during
every time period, at least one full-time consultant must be on duty for every part-time
consultant on duty.
(a) Determine a minimum-cost staffing plan for the center. In your solution, how many
consultants will be paid to work full time and how many will be paid to work part
time? What is the minimum cost?
(b) After thinking about this problem for a while, you have decided to recognize meal
breaks explicitly in the scheduling of full-time consultants. In particular, full-time
consultants are entitled to a one-hour lunch break during their eight-hour shift. In
addition, employment rules specify that the lunch break can start after three hours
of work or after four hours of work, but those are the only alternatives. Part-time con-
sultants do not receive a meal break. Under these conditions, find a minimum-cost
staffing plan. What is the minimum cost?
2.12. Make or Buy A sudden increase in the demand for smoke detectors has left Acme
Alarms with insufficient capacity to meet demand. The company has seen monthly
demand from its retailers for its electronic and battery operated detectors rise to 20,000
and 10,000, respectively, and Acme wishes to continue meeting demand. Acme’s pro-
duction process involves three departments: Fabrication, Assembly, and Shipping. The
relevant quantitative data on production and prices are summarized below.
Monthly hours Hours/unit Hours/unit
Department available (electronic) (battery)
Fabrication 2000 0.15 0.10
Assembly 4200 0.20 0.20
Shipping 2500 0.10 0.15
Variable
cost/unit
$18.80 $16.00
Retail price $29.50 $28.00
The company also has the option to obtain additional units from a subcontractor, who has
offered to supply up to 20,000 units per month in any combination of electronic and bat-
tery operated models, at a charge of $21.50 per unit. For this price, the subcontractor will
test and ship its models directly to the retailers without using Acme’s production process.
(a) What is the maximum profit and the corresponding make/buy levels? (This is a plan-
ning model, and fractional decisions are acceptable.)
(b) Trace the effects of increasing Fabrication capacity by 10 percent. How will the opti-
mal make/buy mix change? How will the optimal profit change?
2.13. Leasing Warehouse Space Cox Cable Company needs to lease warehouse storage
space for five months at the start of the year. It knows how much space will be required
in each month, and it can purchase a variety of lease contracts to meet these needs. For
example, it can purchase one-month leases in each month from January to May. It can
also purchase two-month leases in January through April, three-month leases in
January through March, four-month leases in January and February, or a five-month
Exercises
65