Baker K.R. Optimization Modeling with Spreadsheets

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

Normally, the linear solver does not run on this model because of the presence of the

ABS function, which is nonsmooth. In the output window of the task pane, Solver’s

error message appears when an attempt is made to use the linear solver.

The linearity conditions required by

this Solver engine are not satisfied.

If we invoke the nonlinear solver, the GRG algorithm appears to run, but we can’t tell

whether its solution is a global optimum. In fact, if we use the solution in Figure 8.18

as the starting solution, the nonlinear solver generates the convergence message,

but the solution remains unchanged.

The linearized model requires pairs of auxiliary variables, u

and v

, correspond-

ing to each absolute value calculation. Those variables are deﬁned by a constraint in

the form of equation (8.2).

Minimize z ¼

 v

)

subject to

¼ 1 for j ¼ 1, 2, ...,8

þ u

 v

¼ 0 for k ¼ 1, ...,4

This is a linear program containing six pairs of auxiliary variables as well as the binary

variables.

A worksheet for the linearized problem is shown in Figure 8.19. In the Objective

module, the auxiliary variables appear in cells E14:F19. The objective function

appears in cell J14 with the formula

¼ SUM(E14:F19).

Figure 8.19. Spreadsheet for Example 8.7 with absolute value objective.

326 Chapter 8 Nonlinear Programming

We specify the problem as follows.

Objective: J14 (minimize)

Variable: B7:I10

E14:F19

Constraints: B11:I11 ¼ 1

G14:G19 ¼ 0

B7:I10 ¼ binary

The linear solver produces a solution, which is shown in Figure 8.19, that achieves an

optimal value of 27. Although the objective is quite different than the minimax value

used earlier, the assignment of departments to projects is similar, and the maximum

workload remains minimal at 118. By linearizing the model, Armstrong can be sure

that it has found the optimal solution to its revised formulation.

Solver offers the capability of transforming the use of the ABS function automati-

cally. This transformation would be initiated if we set the Nonsmooth Model

Transformation option to Automatic (or to Always) on the Platform tab in the task

pane. This option is convenient because we can set up the model in an intuitive

fashion, even if it does not satisfy the linearity requirement, and Solver can compen-

sate by performing the necessary transformation. However, the transformation actually

implemented by Solver is not visible to the user, so it’s not possible to know precisely

how the model is transformed. For example, in the case of Example 8.7, the original

model contains 32 variables and 8 constraints. Our transformation, shown in

Figure 8.19, uses 44 variables and 14 constraints. Solver’s automatic transformation

uses 44 variables (38 of which are integer variables) and 44 constraints (not including

the objective function), as reported in the Current Problem section of the Engine tab.

Thus, the details of the automatic transformation may be a bit different than the manual

transformation, but the details of the automatic transformation are not made available

to the user.

SUMMARY

The default choice for a solution algorithm in Solver is the nonlinear solver, also known as the

GRG Nonlinear Engine. The nonlinear solver uses a steepest ascent strategy to search for an

optimal set of decision variables, and it can be invoked for any nonlinear or linear programming

problem. For linear programming problems, however, the linear solver is preferred because it is

numerically stable and produces a comprehensive sensitivity report. For nonlinear problems that

have smooth objective functions, the GRG algorithm is the best choice. Table 8.1 summarizes

the features of the two solution algorithms.

Although it is capable of solving both linear and nonlinear problems, the nonlinear solver

does have its limitations. In general, the GRG algorithm guarantees only that it will ﬁnd a local

optimum. This solution may or may not be a global optimum. If the objective function is con-

cave or convex, and if the constraints form a convex set, then we can be sure that the nonlinear

solver produces a global optimum. Otherwise, we can try alternative starting points as a way of

marshalling evidence about optimality, but there is no foolproof scheme for identifying the

8.5. Linearizations

327

global optimum in general. Solver’s MultiStart option is often a powerful feature in trying to

solve problems with several local optima, but it does not provide any guarantees, either.

Another limitation concerns integer-valued variables. The presence of integer constraints

in an otherwise nonlinear model generally leaves us in a situation where the nonlinear solver

may fail to ﬁnd a global optimum, even to a relaxed problem that is encountered during

Solver’s implementation of branch and bound. This feature renders the GRG algorithm unreli-

able (in the sense of producing a guaranteed global optimum), and the implication is that we

should avoid trying to solve integer nonlinear programming problems with Solver.

Fortunately, in some practical cases, we can transform the most natural formulation into a

linear model. With the transformation, an integer-valued problem can be solved reliably with

the linear solver augmented by the branch and bound procedure. For models that contain

Excel’s MAX, ABS, or IF functions, Solver’s Nonsmooth Model Transformation option can

often provide the linear equivalent of a nonsmooth formulation, although the details of the

model it builds remain opaque.

Finally, because the nonlinear solver is applicable to such a wide variety of optimization

problems (and therefore must accommodate exponents, products, and special functions) we

know of no standard layout that conveniently captures the necessary calculations in the context

of spreadsheets. This feature stands in contrast to the use of the linear solver, where one standard

layout could, in principle, always be used. (Nevertheless, as we have seen in Chapters 3–6, there

are sometimes good reasons for using a few non-standard variations.) The most useful guideline,

as with all spreadsheet models, still seems to be to modularize the spreadsheet and thereby sep-

arate objective function, decision variables, and constraints.

EXERCISES

8.1. Merrill Sporting Goods (Revisited) Revisit Example 8.4, in which the criterion gives

equal weight to each of the retail sites. But in practice, there will be different levels of traf-

ﬁc between the warehouse and the various sites. One way to incorporate this consideration

Table 8.1. Comparison of the Linear and Nonlinear Algorithms

Linear solver Nonlinear solver

Suitable for linear models Suitable for nonlinear models;

can also solve most linear models.

Finds a global optimum each time Finds a local optimum each time.

No guarantee of global optimum,

except in special circumstances.

Ignores initial decision variables Uses initial decision variables in search;

result may depend on starting values.

Finds a feasible solution if one exists May not be able to ﬁnd a feasible

solution when one exists.

Always leads to an optimum, unless

problem is infeasible or unbounded

May generate “convergence” message;

a re-run may be necessary.

Comprehensive sensitivity information

from the Sensitivity Report

Sensitivity Report does not include

allowable ranges.

328 Chapter 8 Nonlinear Programming

is to estimate the number of trips between the warehouse and each retail site and then

weight the distances by the trip volumes. Thus, the original data set has been augmented

with volume data (v

), as listed in the table below.

Site (k) x

1 9 29 12

2 5 50 15

3266820

4397912

541548

6385916

763618

8525820

9817612

10 95 93 24

Now we can use as a criterion the weighted sum of distances between the warehouse and

the retail sites.

(a) What location is optimal for the weighted version of the criterion?

(b) How much of an improvement is achieved by the solution in (a) over the optimal

location for the unweighted version (39.59, 58.43)?

8.2. Curve Fitting for Revenues A large food chain owns a number of pharmacies that

operate in a variety of settings. Some are situated in small towns and are open for only

eight hours a day, ﬁve days per week. Others are located in shopping malls and are

open for longer hours. The analysts on the corporate staff would like to develop a

model to show how a store’s revenues depend on the number of hours that it is open.

They have collected the following information from a sample of stores.

Hours of

operation

Average

revenue

40 $5958

44 6662

48 6004

48 6011

60 7250

70 8632

72 6964

90 11,097

100 9107

168 11,498

(a) Use a linear function to represent the relationship between revenue and operating

hours and ﬁnd the values of the parameters that provide the best ﬁt to the given

data. What revenue does your model predict for 120 hours?

Exercises

329

(b) Suggest a two-parameter nonlinear model for the same relationship and ﬁnd the par-

ameters that provide the best ﬁt. What revenue does your model predict for 120

hours? Which of the models in (a) and (b) do you prefer and why?

8.3. Curve Fitting for Costs Newton Manufacturing Company has reached a stable volume

in the last couple of years and is interested in developing a planning model for its pro-

duction levels, based on aggregate units of output. One element will be a cost model

that describes the relationship of unit cost to production volume. Newton’s capacity is

thought to be around 2500 aggregate units at current equipment and labor force levels,

and it is well known that unit costs tend to rise when output volumes are signiﬁcantly

above or below this ﬁgure. For volumes above this ﬁgure, costs rise due to overtime pre-

miums and to high congestion levels in the plant. For volumes below the nominal ﬁgure,

costs rise due to inefﬁciencies in production. Analysts at Newton have therefore decided

that some type of quadratic function would be a suitable model for unit costs, and they

have proposed the form ax

þ bx þ c, where x represents the aggregate number of

output units, and the parameters a, b, and c remain to be determined. For this purpose,

the model will be ﬁt as closely as possible to the last 12 months of observed data, as repro-

duced in the table below.

Month

Aggregate

output

Unit

cost

1 2350 $53.35

2 2200 54.60

3 2450 49.62

4 2600 53.62

5 2550 49.69

6 2400 51.18

7 2300 53.25

8 2650 51.91

9 2700 54.23

10 2750 50.06

11 2500 49.08

12 2250 54.46

(a) What values of the three parameters provide the best ﬁt to the data, as measured by the

minimum sum of squared differences?

(b) What does the model in (a) predict as the unit cost for an output of 2500?

8.4. Economic Order Quantity (EOQ) A distributor of small appliances wishes to calcu-

late the optimal order quantity for replenishing its stock of a particular washing machine.

Demand for the $200 machine is stable throughout the year and averages about 1000 units

annually. Each order involvesthe cost of transportation, receiving and inspection, account-

ing for expenses of $500 per order. Holding costs are ﬁgured at 20 percent per year.

(a) What order quantity minimizes the annual replenishment cost?

(b) How does the optimal cost break down into holding and carrying components?

8.5. EOQ for Multiple Products In another location, the distributor of the previous pro-

blem stocks four different items in common warehouse space. Each item is described

330 Chapter 8 Nonlinear Programming

by an annual demand rate, a ﬁxed cost per order, a holding cost per year, a unit purchase

cost and a space requirement. The data in the following table describe the four products.

Item 1 2 3 4

Demand 5000 10,000 30,000 300

Fixed cost 400 700 100 250

Holding cost 50 25 8 100

Purchase cost 500 250 80 1000

Space (sq. ft) 12 25 5 10

(a) Considering each product separately, as if it were independent from the others, what

are the respective economic order quantities? What is the total annual cost of order-

ing, holding, and purchasing across the four products at these order quantities?

(b) What is the minimum total annual cost for the four products if the average space taken

up must be no more than 12,000 square feet?

up must be no more than 12,000 square feet and the number of orders per year must be

no more than 65?

(d) In part (b), with a square-foot limit on storage space, what is the economic value of

more space?

(e) In part (c), what is the economic value of more space?

8.6. Pricing with Dependent Demands Covington Motors is a car dealership that special-

izes in the sales of sport utility vehicles and station wagons. Due to its reputation for qual-

ity and service, Covington has a strong position in the regional market, but demand is

somewhat sensitive to price. After examining the new models, Covington’s marketing

consultant has come up with the following demand curves.

Truck demand ¼ 400  0:014 (truck price)

Wagon demand ¼ 425  0:018 (wagon price)

The dealership’s unit costs are $17,000 for SUVs and $14,000 for wagons. Each SUV

requires 2 hours of prep labor, and each wagon requires 3 hours of prep labor. The current

staff can supply 320 hours of labor.

(a) Determine the proﬁt-maximizing prices for SUVs and Wagons. (Round off any frac-

tional demands.)

(b) What demand levels will result from the prices in (a)?

8.7. Pricing with Interdependent Demands Covington Motors sells sport utility vehicles

and station wagons in a price-sensitive market. Its marketing consultant has rethought the

simple demand curves ﬁrst proposed (in the previous exercise) and now wants to recog-

nize the interaction of the two markets. This gives rise to a revised pair of demand curves

for SUVs and wagons, as shown below.

SUV demand ¼ 300  0:014 (SUV price) þ 0:003 (wagon price)

Wagon demand ¼ 325  0:018 (wagon price) þ 0:005 (SUV price)

Exercises

331

The dealership’s unit costs are $17,000 and $14,000 per unit, respectively. Each

SUV requires 2 hours of prep labor, and each Wagon requires 3 hours of prep labor.

The current staff can supply 320 hours of labor. Covington Motors wants to maximize

its proﬁts from the SUVs and Wagons that it acquires for its stock.

(a) Determine the proﬁt-maximizing prices for SUVs and Wagons. (Ignore the fact that

these prices may induce fractional demands.)

(b) What sales levels will result from the prices in (a)?

8.8. Allocating an Advertising Budget A regional beer distributor has $125,000 to spend

on advertising in four markets, where each market responds differently to advertising.

Based on observations of the market’s response to several advertising initiatives, the dis-

tributor has estimated the sales response by ﬁtting a curve of the form R ¼ ax

, where R

represents sales revenue and x represents advertising dollars, both measured in thousands.

The estimated demand curves are shown in the table below.

Market Sales revenue

Domestic 66x

0.55

Premium 77x

0.44

Light 88x

0.33

Microbrew 99x

0.22

(a) How should the funds be allocated among the four markets so that the revenue to the

company as a whole will be maximized?

(b) How much would it be worth (in terms of incremental revenue) to raise the amount

available for advertising by $1000?

8.9. Supply Chain Design Muslin Ofﬁce Furniture manufactures a popular line of ﬁling

cabinets and has a very strong competitive position in its market. The company sells its

product to a number of wholesale distributors who, in turn, sell to retail customers. In

this environment, the company faces a demand curve of the following form

¼ 20  0:6P

where P

denotes its selling price and Q

denotes the volume (in thousands) sold at that

price. Muslin also experiences increasing marginal costs of the form 0.8Q

. (This means

that its total cost is 0.8(Q

)

/2.) Increasing marginal costs occur because of quality losses

and congestion on the shop ﬂoor as volume rises.

One of Muslin’s distributors is a subsidiary known as New England Supply. They

represent Muslin’s exclusive distributor in the northeast, and the parent company

allows them to operate as an independent entity, focused on distribution. They buy

ﬁling cabinets from Muslin and sell them to retail customers in the northeast. In that

market, New England Supply faces its own demand curve as follows

¼ 10  0:2P

where P

denotes the retail selling price and Q

denotes the volume (in thousands) sold in

the northeast at that price. New England Supply incurs its own operating costs, in addition

332 Chapter 8 Nonlinear Programming

to the cost of purchasing the product from Muslin, so that its marginal cost function takes

the form P

þ 0.4Q

. This means that its total cost is P

þ 0.4(Q

)

/2.

(a) Suppose that Muslin Ofﬁce Furniture and New England Supply each analyze their

own pricing strategies separately. That is, Muslin ﬁnds its proﬁt-maximizing price.

Then New England Supply, whose cost is inﬂuenced by Muslin’s price, maximizes

its own proﬁts. What is each ﬁrm’s optimal price and how much proﬁt is earned

between the two companies?

(b) Suppose instead that the two ﬁrms make coordinated decisions. In other words, they

choose a pair of prices, one wholesale and one retail, aimed at maximizing the total

proﬁt between the two ﬁrms. What is each ﬁrm’s optimal price in this coordinated

environment? How much proﬁt is earned between the two companies?

8.10. Estimating Beta In ﬁnance it is important to be able to predict the return on a stock

from the return on the market, that is, on a market index such as the S&P 500 index. It

is often hypothesized that a particular prediction equation exists

y ¼

where y is the return on a stock during a time period, x is the return on the market index

during the same time period, and

and

are constants that must be estimated. The value

is of particular interest, because it indicates how closely the returns on a particular

stock tend to follow the returns on the market as a whole.

If our knowledge of the parameters

and

were perfect, then we could predict indi-

vidual stock returns accurately from the behavior of the market. Typically, such knowl-

edge does not exist, and our values of

and

are imperfect. In other words, when we

use them, we encounter errors in our predictions. The best we can do is to choose the esti-

mates

and

in order to make prediction errors close to zero.

Find data on returns for Coca-Cola stock on a monthly basis for the period January 2,

2001 to December 1, 2006, and returns for the S&P 500 index for the same 72 months. Fit

the linear prediction equation to this set of data. Use as a criterion the minimum sum of

squared differences between the actual stock returns and their predicted values. For the

historical data, estimate the parameters of the prediction equation for Coca-Cola stock.

(a) What is the estimated value of

, for Coca-Cola stock?

(b) Repeat the estimation process for Microsoft stock. What do you expect to ﬁnd in

terms of the relationship between the

for Microsoft and the

for Coke?

8.11. Portfolio Model The information on which stocks are evaluated is a series of historical

returns, typically compiled on a monthly basis. This history provides an empirical distri-

bution of a stock’s return performance. For stock k in the portfolio, the table below sum-

marizes the monthly returns for ﬁve stocks over a two-year period in the late 1990’s.

Stock Mean

National Computer (NCO) 0.0371

National Chemical (NCH) 0.0145

National Power (NPW) 0.0118

National Auto (NAU) 0.0185

National Electronics (NEL) 0.0217

In addition, the covariance values for the ﬁve stocks are displayed in the following table.

Exercises

333

NCO NCH NPW NAU NEL

NCO 0.0110 20.0004 0.0000 0.0019 0.0013

NCH 20.0004 0.0032 2 0.0002 0.0002 0.0003

NPW 0.0000 20.0002 0.0015 0.0007 20.0002

NAU 0.0019 0.0002 0.0007 0.0051 0.0008

NEL 0.0013 0.0003 20.0002 0.0008 0.0044

(a) Determine the portfolio allocation that minimizes risk (i.e., portfolio variance) for a

portfolio consisting of these ﬁve stocks, subject to maintaining an average return of at

least two percent. What is the minimum variance?

(b) Determine the portfolio allocation that maximizes return for a portfolio consisting of

these ﬁve stocks, subject to maintaining a variance of at most 0.002. What is the opti-

mal return?

the following

Objective ¼ Return  2(Risk)

(d) What is the optimal allocation for this measure of performance?

8.12. Production Smoothing A supplier of raw material has made plans to provide monthly

deliveries to a customer. The customer’s requirements are shown in the following table.

Month 1 2 3 4 5 6 7 8

Units 100 200 300 400 100 100 500 300

The raw material can be processed and prepared for delivery in any volume because part-

time labor can be used, and the labor pool is quite large. However, changes in month-to-

month production volumes can be costly. When production levels increase, costs must be

incurred in acquiring and training new workers. When production levels decrease, costs

are incurred due to layoff policies.

Based on historical data, the cost estimate for increasing production from one month

to the next is $1.50 per unit increase in capacity. In the other direction, reducing pro-

duction from one month to the next incurs a cost of $1.00 per unit reduction in capacity.

The other relevant cost is the cost of inventory: each unit held in stock incurs a cost of

$2.00 per month held.

Entering month 1, the starting inventory is 80 units, and the production level has

been steady at 100 units. To make sure the plans can be extended into the future, inventory

is required to be at least 50 units at the end of the eighth month, and the planned pro-

duction level for month 9 is 200.

What is a minimum-cost production plan for the supplier?

8.13. Political Redistricting Based on the new census information, it is time to redraw the

boundaries of the political districts in the state of Idazona. Each district will have one

representative in the next Congress, and Idazona has been allocated four representatives

based on its share of the national population. The state is made up of nine counties, with

populations (in thousands) shown in the table. (See the state map in Figure 8.20.)

The main requirement in the formation of districts is that they produce equal popu-

lations, or as close to equal as possible. Furthermore, the districts must be composed of

334 Chapter 8 Nonlinear Programming

adjacent counties without splitting any county between two or more districts. Ofﬁcials in

Idazona interpret the requirement to mean that if a district is created from two counties,

then those two counties must share a border. Furthermore, if a district is created from

three counties, then at least one of the counties must be adjacent to the other two. No dis-

trict is permitted to have exactly one county or more than three counties.

Mathematically, ofﬁcials are seeking a districting plan for which the maximum

deviation between a district population and the average district population will be as

small as possible.

What assignment of counties to districts will satisfy the desired conditions?

Case: Delhi Foods

Manisha Patel recently completed her ﬁrst week of work as a summer intern at Delhi Foods.

Earlier this morning, Manisha’s boss, the Director of Marketing, asked her to come up with a

recommendation on the level of marketing expenses (advertising and promotion expenditures)

for a line of frozen Indian dinners as it enters its seventh year in the marketplace. Exhibit 8.1,

which Manisha received from her boss, contains an accounting summary of essential product

costs and revenues in the ﬁrst six years, during which there has been some trial-and-error exper-

imentation with marketing policies. For year seven, the table shows projections for the coming

County 1 2 3 4 5 6 7 8 9

Population 25 23 29 20 22 37 34 21 34

Figure 8.20. State map of ldazona.

Case: Delhi Foods 335