Baker K.R. Optimization Modeling with Spreadsheets

Подождите немного. Документ загружается.

limits on particulate emissions. For each product, Lovejoy’s sales potentials (demand

levels that Lovejoy can capture) are expected to remain relatively ﬂat for at least the

next ﬁve years. Relevant data for each product are as follows. (Note: T denotes tons.)

Sales

potential Variable costs Revenues

Particulate

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 has proposed a “bubble policy” for your industry. In this form of regu-

lation, an imaginary 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 ﬁrm, 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

ﬁve 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 proﬁt Lovejoy can achieve from its product line in the

coming year (Year 1). For each future year (Years 2–5), as emissions limits are

imposed and tightened, what will Lovejoy’s proﬁts be?

(b) Describe the qualitative pattern in the solution.

Use the pattern in (b) to determine how much Lovejoy would be willing to pay in

Year 4 to be allowed to emit one extra ton of particulates above the proposed limit.

4.11. Oil Distribution Texxon Oil Distributors, Inc., has three active oil wells in a west Texas

oil ﬁeld. Well 1 has a capacity of 93 thousand barrels per day (TBD), Well 2 can produce

88 TBD and Well 3 can produce 95 TBD. The company has ﬁve reﬁneries along the Gulf

Coast, all of which have been operating at stable demand levels. In addition, three pump

stations have been built to move the oil along the pipelines from the wells to the reﬁneries.

Oil can ﬂow from any one of the wells to any of the pump stations, and from any one of

166 Chapter 4 Sensitivity Analysis in Linear Programs

the pump stations to any of the reﬁneries, and Texxon is looking for a minimum-cost

schedule. The reﬁneries’ requirements are as follows.

Reﬁnery R1 R2 R3 R4 R5

Requirement

(TBD)

30 57 48 91 48

The company’s cost accounting system recognizes charges by the segment of pipeline that

is used. These daily costs are given in the tables below, in dollars per thousand barrels.

To Pump A Pump B Pump C

Well 1 1.52 1.60 1.40

From Well 2 1.70 1.63 1.55

Well 3 1.45 1.57 1.30

To R1 R2 R3 R4 R5

Pump A 5.15 5.69 6.13 5.63 5.80

From Pump B 5.12 5.47 6.05 6.12 5.71

Pump C 5.32 6.16 6.25 6.17 5.87

(a) Determine the least costly way of supplying oil from the wells to the reﬁneries.

(b) Describe the qualitative pattern in the solution.

the same quantity simultaneously. How will the shipping schedule change? How will

the total cost change?

(d) For how much of a change in demand will the pattern in (b) persist?

4.12. 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 & Loans. These investments

and their various ﬁnancial 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 coefﬁcient

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 coefﬁcient 1 5 4 8 6 3

Growth potential (%) 0 18 10 32 20 7

Exercises

167

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 coefﬁcient should not exceed 5.

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, as indicated by the shadow price information in

the Sensitivity Report? Conﬁrm this marginal rate by raising the investment amount

slightly and re-solving the linear program.

4.13. Coffee Blending and Sales Hill-O-Beans Coffee Company blends four component

beans into three ﬁnal 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 ﬁnal coffee blends, the cost

and availability information for the four components, and the wholesale price per pound

of the ﬁnal blends. The percentages indicate the fraction of each component to be used in

each blend.

Cost per Max weekly

Component (lb) 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 pounds per week, and Hill-

O-Beans would like to operate at capacity. There is no problem in selling the ﬁnal blends,

although the Marketing Department requires minimum production levels of 10,000,

25,000, and 30,000 pounds, respectively, for the hotel, restaurant, and market blends.

(a) In order to maximize weekly proﬁt, how many pounds of each component should be

purchased?

(b) What is the shadow price (from the Sensitivity Report) on the availability of Maximo

beans?

of Maximo beans in order to raise total proﬁt?

4.14. 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 ﬁrm can make, but there are no plans to increase production capacity in the

short run. Instead, the ﬁrm plans to use subcontracting.

168 Chapter 4 Sensitivity Analysis in Linear Programs

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 ﬁrm 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 Fab. Asy. Ship.

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

manufacturing 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

sell for $20, and network cards sell for $28. The ﬁrm’s policy, for each product, is that

at most 40 percent of the units produced can have subcontracted fabrication, and at

most 70 percent of the units can have subcontracted assembly.

(a) Determine the production and subcontracting schedule that will maximize proﬁts.

How many units of each product should be sold, in the optimal plan? What

volume should the subcontractor handle?

(b) If 100 hours of overtime could be scheduled, which department(s) should be allo-

cated the overtime. (Use the Sensitivity Report to justify your answer.)

4.15. Make/Buy Planning The CammTex Fabric Mill is in the process of deciding on a pro-

duction schedule. It wishes to know how to weave the various fabrics it will produce

during the coming quarter. The sales department has conﬁrmed orders for each of the

15 fabrics that are produced by CammTex. These quarterly demands are given in the

table below. Also tabulated is the variable cost for each fabric. The mill operates continu-

ously during the quarter: 13 weeks, 7 days a week, and 24 hours a day.

There are two types of looms: dobbie and regular. Dobbie looms can make all fab-

rics, and they are the only looms that can weave certain fabrics such as plaids. The pro-

duction rate for each fabric on each type of loom is also given in the table. (If the

production rate is zero, the fabric cannot be woven on that type of loom.) CammTex

has 90 regular looms and 15 dobbie looms.

Fabrics woven at CammTex proceed to the ﬁnishing department in the mill and then

are sold. Any fabrics that are not woven in the mill because of limited capacity will be

subcontracted to an outside producer and sold at the selling price. The cost of purchasing

from the subcontractor is also given in the table.

Exercises

169

Demand Dobbie Regular Mill cost Sub. cost

Fabric (Yd) (Yd/Hr) (Yd/Hr) ($/Yd) ($/Yd)

1 16,500 4.653 0.00 0.6573 0.80

2 52,000 4.653 0.00 0.555 0.70

3 45,000 4.653 0.00 0.655 0.85

4 22,000 4.653 0.00 0.5542 0.70

5 76,500 5.194 5.313 0.6097 0.75

6 110,000 3.767 3.809 0.6153 0.75

7 122,000 4.055 4.185 0.6477 0.80

8 62,000 5.208 5.232 0.488 0.60

9 7500 5.208 5.232 0.5029 0.70

10 69,000 5.208 5.232 0.4351 0.60

11 70,000 3.652 3.733 0.6417 0.80

12 82,000 4.007 4.185 0.5675 0.75

13 10,000 4.291 4.439 0.4952 0.65

14 380,000 5.208 5.232 0.3128 0.45

15 62,000 4.004 4.185 0.5029 0.70

(a) What is minimum total cost of production and purchasing for CammTex?

(b) Construct a table showing how the optimal total cost varies with the number of

Dobbie looms available, in the range 10 – 18.

(d) Use the pattern in (c) to trace the effect on the optimal cost of increasing demand for

fabric 6 by 100 yards.

(e) Repeat (d) for fabric 5.

(f) Repeat (d) for fabric 4.

4.16. Cash Planning A startup investment project needs money to cover its cash ﬂow

needs. The cash income and expenditures for the period January through April are as

follows.

Jan Feb Mar Apr Total

Cash ﬂow ($000) –150 – 450 500 250 150

At the beginning of May all excess cash will be paid out to investors. There are two

ways to ﬁnance the project. One is the possibility of taking out a long-term loan at

the beginning of January. The interest on this loan is 1 percent per month, payable on

the ﬁrst of the month for the next three months. This loan can be as large as $400,000;

the principal is due April 1; and no prepayment is permitted. The alternative is a short-

term loan that can be taken out at the beginning of each month. This loan must be paid

back at the beginning of the following month with 1.2 percent interest. A maximum of

$300,000 may be used for this short-term loan in any month. In addition, there is the

possibility of investing in a money-market fund at the start of each month. This fund

will pay 0.7 percent interest at the beginning of the following month.

170 Chapter 4 Sensitivity Analysis in Linear Programs

Assume the following about the timing of cash ﬂows.

†

For months in which there is a net cash deﬁcit, there must be sufﬁcient funds on

hand at the start of the month to cover the net outﬂow.

†

For months in which there is a net cash surplus, the net inﬂow cannot be used until

the end of the month (i.e., the start of the next month).

(a) What is the maximum amount that can be returned to investors?

(b) Describe the pattern in the optimal solution.

period. That is, if there is a $1000 change in the cash ﬂows for any month, what

would be the dollar change in the amount returned to investors?

(d) Show how the shadow prices in the Sensitivity Report can be used to conﬁrm the

answers in (c).

Case: Cox Cable and Wire Company

Meredith Ceh breathed a sigh of relief. Finally, all the necessary ﬁgures seemed to be correctly in

place, and her spreadsheet looked complete. She was conﬁdent that she could analyze the situ-

ation that John Cox had described, but she wondered if there were other concerns she should be

addressing in her response.

Mr Cox, president of Cox Cable and Wire Company, and grandson of the company’s foun-

der, had asked Meredith to come up with plans to support the preliminary contract he had

worked out with Midwest Telephone Company. The contract called for delivery of 340 reels

of cable during the summer. He was leaving the next day to negotiate a ﬁnal contract with

Midwest and wanted to be sure he understood all of the implications.

According to Mr Cox, he had been looking for a chance to become a supplier to a large

company like Midwest, and this seemed to be the right opportunity. Demand from some of

Cox Cable’s traditional customers had slackened, and as a result there was excess capacity

during the summer. Nevertheless, he wanted to be sure that, from the start, his dealings with

Midwest would be proﬁtable, and he had told Meredith that he was looking for a proﬁtability

target of at least 25 percent. He also wanted her to conﬁrm that there was sufﬁcient capacity

to meet the terms of the contract. He had quickly mentioned a number of other items, but

those were secondary to proﬁtability and capacity.

Background

The Cox Cable and Wire Company sold a variety of products for the telecommunications indus-

try. At its Indianapolis plant, the company purchased uncoated wire in standard gauges,

assembled it into multiwire cables, and then applied various coatings according to customer spe-

ciﬁcation. The plant essentially made products in two basic families—standard plastic and high

quality Teﬂon. The two coatings came in a variety of colors, but these were changed easily by

introducing different dyes into the basic coating liquid.

The production facilities at Indianapolis consisted of two independent process trains (semi-

automated production lines), referred to as the General and National trains, after the companies

that manufactured them. Both plastic-coated and the Teﬂon-coated cable could be produced on

either process train; however, Teﬂon coating was a faster process due to curing requirements.

Planning at Cox Cable was usually done on an annual and then a quarterly basis. The labor

force was determined by analyzing forecast demand for the coming year, although revisions

Case: Cox Cable and Wire Company

171

were possible as the year developed. Then, on a quarterly basis, more speciﬁc machine schedules

were made up. Each quarter the process trains were usually shut down for planned maintenance,

but the maintenance schedules were determined at the last minute, after production plans were in

place, and they were often postponed when the schedule was tight.

Due to recent expansions, there was not much storage space in the plant. Cable could tem-

porarily be stored in the shipping area for the purposes of loading trucks, but there was no space

for cable to be stored for future deliveries. Additional inventory space was available at a nearby

public warehouse.

Meredith had become familiar with all of this information during her ﬁrst week as a

summer intern. At the end of the week, she had met with Mr Cox and he had outlined the

Midwest contract negotiation.

The Contract

The preliminary contract was straightforward. Midwest had asked for the delivery quantities out-

lined in Exhibit 4.1. Prices had also been agreed on, although Mr. Cox had said he wouldn’t be

surprised to ﬁnd Midwest seeking to raise the Teﬂon delivery requirements during the ﬁnal

negotiation.

Meredith had gone ﬁrst to the Production Manager, Jeff Knight, for information about

capacity. Jeff had provided her with data on production times (Exhibit 4.2), which he said

were pretty reliable, given the company’s extensive experience with the two process trains.

He also gave her the existing production commitments for the summer months, showing the

available capacity given in Exhibit 4.3. Not all of these ﬁgures were ﬁxed, he said.

Apparently, there was a design for a mechanism that could speed up the General process

train. Engineers at Cox Cable planned to install this mechanism in September, adding 80

hours per month to capacity. “We could move up our plans, so that the additional 80 hours

would be available to the shop in August,” he remarked. “But that would probably run about

$900 in overtime expenses, and I’m not sure if it would be worthwhile.”

EXHIBIT 4.1

Contract Delivery Schedule

and Prices

Month Plastic Teﬂon

June 50 30

July 100 60

August 50 50

Price $360 $400

EXHIBIT 4.2

Production Capabilities, in

Hours per Reel

Process

train Plastic Teﬂon

General 2.0 1.5

National 2.5 2.0

172 Chapter 4 Sensitivity Analysis in Linear Programs

After putting some of this information into her spreadsheet, Meredith spoke with the

plant’s Controller, Donna Malone, who had access to most of the necessary cost data.

Meredith learned that the material in the cables cost $160 per reel for the plastic-coated

cable, and $200 for the Teﬂon-coated cable. Packaging costs were $40 for either type of

cable, and the inventory costs at the public warehouse came to $10 per reel for each month

stored. “That’s if you can get the space,” Donna commented. “It’s a good idea to make reser-

vations a few weeks in advance, otherwise we might ﬁnd they’re temporarily out of space.”

Donna also provided standard accounting data on production costs (Exhibit 4.4). According

to Donna, about half of the production overhead consisted of costs that usually varied with

labor charges, while the rest was depreciation for equipment other than the two process

trains. The machine depreciation charges were broken out separately, as determined at the

time the machinery was purchased. For example, the General process train originally cost

$500,000 and, for tax purposes, had an expected life of ﬁve years, or about 10,000 hours;

hence its depreciation rate of $50 per hour.

The Analysis

Meredith was able to consolidate all of the information she collected into a spreadsheet (Exhibit

4.5).

Making what she felt were reasonable assumptions about relevant cost factors, she was

able to optimize the production plan, and she determined that it should be possible to meet

the 25 percent proﬁtability target. Nevertheless, there seemed to be several factors in it that

were subject to change—things that had come up in her various conversations, such as mainten-

ance, warehousing, and the possibility of modifying the contract. She expected that Mr Cox

would quiz her about all of these factors, and she knew it would be important for her to be pre-

pared for his questions.

EXHIBIT 4.4 Accounting Data for Production

Cost category General National

Machine Depr. $50.00/hr $40.00/hr

Direct labor 16.00 16.00

Supervisor 8.00 8.00

Production Ohd 12.00 12.00

EXHIBIT 4.3 Unscheduled Production Hours

Month General National

June 140 250

July 60 80

August 150 100

The spreadsheet can be found at the book’s website: www.mba.tuck.dartmouth.edu/opt/.

Case: Cox Cable and Wire Company 173

Chapter 5

Linear Programming:

Data Envelopment Analysis

Chapters 2 and 3 examined the basic types of structures that appear in formulations of

linear programs—allocation, covering, blending, and network models. Not every

application of linear programming can be classiﬁed as one of those four types, but

most applications resemble one or more of them. In this chapter, we look at a type

of linear program that has a special application and a special kind of interpretation.

This type is associated with Data Envelopment Analysis, or DEA. For classiﬁcation

purposes, the DEA model is essentially an allocation model, but its unique appli-

cations make it an important type of model to study in its own right.

As the examples in Chapters 2 and 3 indicated, linear programming is typically

used as an ex ante tool in planning, that is, as an aid in choosing among alternative

possible courses of action. In DEA, linear programming is used as an ex post tool,

to evaluate performance that has already been observed. Compared to other linear pro-

gramming applications, DEA is a relative newcomer. The ﬁrst articles on the method-

ology began appearing in the mid-1970s, and researchers have been elaborating the

theory ever since. As recognition of DEA has spread, the technique has been applied

in a variety of settings, such as public schools, courts of law, hospitals, oil and gas pro-

duction, vehicle maintenance, and banking.

The primary elements in a DEA study are a set of decision-making units

(DMUs), along with their measured inputs and outputs. The DMUs may be different

branches of the same large bank, or different hospitals in the same region or different

ofﬁces of the same insurance company, but they should be reasonably homogeneous

and separately managed. In the ideal case, the DMUs have a well deﬁned set of

common inputs and outputs.

The purpose of DEA is to determine which of the DMUs make efﬁcient use of

their inputs and which do not. For the inefﬁcient units, the analysis can actually quan-

tify what levels of improved performance should be attainable. In addition, the analy-

sis indicates where an inefﬁcient DMU might look for benchmarking help as it

searches for ways to improve.

Optimization Modeling with Spreadsheets, Second Edition. Kenneth R. Baker

# 2011 John Wiley & Sons, Inc. Published 2011 by John Wiley & Sons, Inc.

175