Baker K.R. Optimization Modeling with Spreadsheets
Подождите немного. Документ загружается.
The cost of transportation from each possible warehouse to each representative
has also been determined. Exhibit 7.5 presents the warehouse-to-representative transportation
costs.
Fortunately, there is no question of meeting the customer service requirements policy in the
new region, because any of the warehouses being considered could deliver to any of the eastern
representatives within 24 hours.
296 Chapter 7 Integer Programming: Logical Constraints
Chapter 8
Nonlinear Programming
In Chapter 1, we introduced the optimization capability of Solver with a simple
revenue-maximization problem that illustrated the Generalized Reduced Gradient
(GRG) algorithm, which is Excel’s nonlinear solver. Then, in Chapters 2 – 7, we
focused on linear programming models, solving them with Excel’s linear solver. In
this chapter, we return to the nonlinear solver and examine the types of optimization
problems it can handle.
Taken literally, the term nonlinear programming refers to the formulation and sol-
ution of constrained optimization problems that are anything but linear. However, that
isn’t a wholly accurate assessment of the GRG algorithm’s capability. Two features are
important in this regard. First, in terms of finding solutions, linear programming
models are actually a subset of nonlinear programming models. That is, the GRG
algorithm can be used to solve linear as well as nonlinear programs. However, for
linear programming, we use the linear solver because it is numerically more depend-
able than the GRG algorithm and provides a more extensive sensitivity analysis. The
GRG algorithm provides an abbreviated sensitivity analysis, and it may also have
difficulty locating a feasible solution when one exists. Still, there is nothing wrong,
in principle, with using the GRG algorithm to solve a linear problem.
The second feature to keep in mind is that the GRG algorithm has limitations as a
nonlinear solver. In particular, it is mainly suited to problems in which the constraints
and objective function contain smooth functions. Informally, the definition of a
smooth function would be a function without gaps or kinks. A gap means that the
function is not continuous: if we were to place a pencil on a sketch of the function,
we would not be able to trace the function’s entire graph without lifting up the
pencil at some point. A gap occurs, for example, in a price schedule with a price
break, such as the first function shown on the graph in Figure 8.1. A kink in the func-
tion refers to a sharp corner, where the function comes to a point as it changes direc-
tion. A kink occurs, for example, in the relationship of output to demand, such as the
second function in Figure 8.1. The presence of a nonsmooth function tends to create
problems for the nonlinear solver. That said, the nonlinear solver can successfully be
applied to a large variety of optimization problems, and this chapter illustrates the
major categories.
Optimization Modeling with Spreadsheets, Second Edition. Kenneth R. Baker
# 2011 John Wiley & Sons, Inc. Published 2011 by John Wiley & Sons, Inc.
297
The nonlinear programming problems we address contain decision variables, an
objective function, and usually some constraints. In this respect, they are structurally
similar to linear programs except that their objective functions and/or constraint func-
tions are not linear. We look first at problems that have no constraints, so that we can
focus on the nature of a nonlinear objective function and its implications for the use of
the nonlinear solver. We then look at problems with nonlinear objectives and linear
constraints, and we build on some of the coverage in previous chapters. Finally, we
look at the boundary of linear and nonlinear models, demonstrating how, in some
very special cases, we can transform a nonlinear model into a linear one, so that we
can exploit the advantages of the linear solver.
8.1. ONE-VARIABLE MODELS
By taking a brief look at models with one decision variable, we can begin to appreciate
the optimization task for nonlinear problems. Conceptually, we can think about find-
ing the maximum of a function y ¼ f(x) that we could draw on a graph. Figure 8.2
shows a graphical plot for a hypothetical nonlinear function. The function shown in
Figure 8.1. Examples of nonsmooth functions.
298 Chapter 8 Nonlinear Programming
the graph is a smooth function, that is, a continuous function without breaks or corners.
The nonlinear solver is well suited to this type of function. It is designed to search for
the maximum value of the function and the x-value that achieves it.
With one-variable models, it would be possible to locate the maximum value on a
spreadsheet by using Excel’s Data Table tool. However, even that approach may
require several repetitions, depending on the level of precision desired, and additional
interventions in the spreadsheet would be required for sensitivity analysis. The use of
the nonlinear solver automates the key manual steps. Nevertheless, our main reason for
investigating one-variable problems here is to illustrate how the nonlinear solver works
in a manageable optimization problem.
The algorithm used by Solver for nonlinear models is a steepest ascent method.
Starting from any point on the graph, the procedure looks for the direction in which
the function increases most rapidly and moves in that direction to a new point. This
process repeats from the new point, ultimately stopping at a point where the function
does not increase. From the graph in Figure 8.2, we can see that the stopping point may
depend on the starting point. If we start the search at point A, the search terminates at
point B. Likewise, if we start the search at G, the search terminates at F. Only if we start
the search between points C and E will the procedure terminate at the desired point, D.
This example illustrates a general feature of the nonlinear solver. The steepest
ascent method terminates at a local optimum, which is the best point within a prede-
fined neighborhood. However, there may be a global optimum located some distance
away. The global optimum is the best point anywhere, and that is really the solution we
seek. Unfortunately, there is no guarantee that the nonlinear solver will terminate at the
global optimum; all we can say is that it converges to a local optimum.
These features immediately describe a contrast between the nonlinear and linear
solver. The linear solver, applied to a linear program, always finds a global optimum
(assuming one exists) and does so irrespective of the values of the decision variables
initially placed in the spreadsheet. The nonlinear solver, applied to a general nonlinear
Figure 8.2. Hypothetical nonlinear objective function.
8.1. One-Variable Models 299
program, always finds a local optimum (if one exists) but not necessarily a global opti-
mum. Moreover, its result may depend on the initial values of the decision variables.
An example will serve to illustrate the basic optimization properties.
8.1.1. An Inventory Example
A standard inventory problem involves the tradeoff of ordering costs and carrying
costs. This tradeoff represents a common concern in managing inventories, as in the
example of Crowley Foods.
EXAMPLE 8.1
Crowley Foods
At grocery distributor Crowley Foods, a particular stock item has a stable demand of 5000
cartons during the year. Each time the distributor places an order for a replenishment lot, a
cost of $35 is incurred for receiving, handling, and inspection. This fixed cost is incurred less
frequently as the order quantity increases. The distributor also ties up working capital in inven-
tory and figures its opportunity cost at 10 percent per year, assessed on the average level of
inventory. Each carton costs $30, so the carrying cost incurred annually is $3 per unit. The
annual carrying cost incurred rises as the order quantity increases. Crowley Foods wishes to
select an order quantity that minimizes the combined costs of ordering and inventory. B
In Example 8.1, the order quantity is the only decision variable. If we let x rep-
resent the order quantity, then the number of orders placed per year is 5000/x and
the fixed cost incurred annually is 35(5000/x) ¼ 175,000/x.
Because Crowley Foods can order when stock has fallen essentially to zero, its
inventory level fluctuates between 0 and x, averaging x/2. Therefore, the carrying
cost incurred annually is (0.10)(30)(x/2) ¼ 1.5x.
With demand known to be 5000 per year, the annual purchase cost of 30(5000) ¼
150,000 is constant and independent of the order quantity; therefore, the purchase cost
can be ignored when determining the best order quantity. Crowley’s problem is to find
the order quantity x that minimizes its annual cost of ordering and inventory, or
f (x) ¼ 175,000=x þ 1:5x
Figure 8.3 shows a spreadsheet containing the given parameters, as part of the
optimization model. The spreadsheet contains three modules: decision variables, par-
ameters, and objective function. Cell C4 contains the arbitrary value 100, as an initial
value for the decision variable. To find the best order quantity, we specify the problem
as follows.
Objective: C16 (minimize)
Variable: C4
The model contains no explicit constraints, although it’s convenient to add the
constraint x 1 when using Solver. This modification is helpful because we could
300
Chapter 8 Nonlinear Programming
run into problems in calculating f(x) if we permit x ¼ 0. When we optimize, the con-
vergence message appears in the task pane on the Output tab
Solver has converged to the current
solution. All constraints are
satisfied.
The same message appears along the bottom of the task pane, highlighted in yellow.
The convergence result means that internally Solver has not encountered the compu-
tational evidence needed to identify the solution as a local optimum. In some cases,
this problem can be mitigated by choosing a better initial solution. Normally, when
we encounter this result, we simply re-run the optimization starting from the newly
obtained solution.
If we re-run Solver starting with the new solution, we obtain the optimality
message
Solver found a solution. All
constraints and optimality conditions
are satisfied.
The same message appears along the bottom of the task pane, highlighted in green.
This is the result we want from Solver, and depending on our starting solution, we
may obtain this result on the very first run. It confirms that the minimum total cost
is $1024.70, achieved by ordering in lots of 342.
The fact that the optimality conditions are satisfied indicates that Solver has found
a local optimum. As mentioned earlier, there is no guarantee that this result is also a
global optimum, at least without some additional information about the model. In
other words, Solver itself has no way of determining whether the solution is a
global optimum. So we might ask whether there is additional information we can
bring to bear on this issue. One way is to draw a graph of the objective function.
Figure 8.3 displays such a graph, which provides strong evidence that there is only
Figure 8.3. Spreadsheet model for Example 8.1.
8.1. One-Variable Models 301
one local optimum in this problem and that we have found it. However, a graph will
not always provide conclusive evidence, and graphing is not a technique that general-
izes easily to problems containing several variables.
In this instance, at least, Crowley Foods can minimize its annual inventory-related
costs on this stock item by ordering 342 units at a time, although it wouldn’t be sur-
prising to find that the actual order size is rounded to 350 for convenience. The model
can be used to verify that costs are not very sensitive to small changes in the order
quantity and that, in fact, the annual cost for a quantity of 350 is virtually identical
to the optimal cost.
Another approach to finding a global optimum, rather than a local optimum, is to
try a variety of different starting points. In this example, we can start with several
different order quantities, re-run Solver, and we will come to the same result of 342
each time. This is not a rigorous proof, but it tends to build our confidence that we
have located a global optimum. In other problems, however, this approach could ident-
ify several local optima, leaving the search for a global optimum inconclusive. In other
words, the technique of restarting the procedure from a different initial solution can
reveal that several local optima exist, but it can never prove that there is only one
local optimum. The next example helps to illustrate the behavior of local optima.
8.1.2. A Quantity Discount Example
For a second example, we continue with the inventory example and explore the impli-
cations of a price discount on the purchase of the product being stocked.
EXAMPLE 8.2
A Purchase Discount for Crowley Foods
Instead of the purchase cost remaining constant at $30 per carton, the following price-break
schedule applies to the product that Crowley Foods has been analyzing.
Quantity purchased Unit cost
x 100 $30.00
101 x 500 $29.50
501 x $29.40
Having discovered this discount possibility, Crowley is now considering whether to alter its pur-
chase policy of ordering in replenishment lots of 342.
B
With the possibility of a discount, we must include the annual purchase cost in the
objective function, because the total annual cost depends on the order quantity. The
spreadsheet in Figure 8.4 shows an extension of the first order quantity model that
includes the purchase cost component and the quantity discount structure as well.
The unit cost per carton, which can be $30.00, $29.50, or $29.40, gives rise to an
annual purchase cost that has three different forms. The formula in cell C17 contains
302
Chapter 8 Nonlinear Programming
an IF function, which chooses among the three unit costs according to whether the
purchase quantity in cell C4 qualifies for a price discount, and then the formula com-
putes the total purchase cost. In general, the IF function is nonsmooth, and a structure
we prefer to avoid when using the nonlinear solver. Nevertheless, we proceed here,
because this example illustrates the occurrence of a local optimum in a relatively
simple, one-variable model. We can easily check our results using alternative
methods.
To find the best order quantity, we specify the model as follows.
Objective: C18 (minimize)
Variable: C4
However, depending on the initial value, Solver converges to one of two solutions,
as shown below.
Initial x Final x Objective
x 215 500 $148,100
216 x 499 342 $148,525
500 x 2304 500 $148,100
2305 x 2499 342 $148,525
x 2500 500 $148,100
Evidently, there are two local optima, one at x ¼ 342 and the other (the global opti-
mum) at x ¼ 500. (Figure 8.4 plots the objective function for a range of order quan-
tities in the vicinity of these choices.) Starting values in the neighborhood of 342
converge to 342 as a local optimum. (Somewhat surprisingly, this is also the case
for starting values near 2400.) On the other hand, starting values at or somewhat
above 500 converge to the global optimum, as do relatively small initial values,
Figure 8.4. Spreadsheet model for Example 8.1.
8.1. One-Variable Models 303
below 216. However, once we find one local optimum that is not the global optimum,
we can only wonder how many other local optima there might be. In this instance, the
graph in Figure 8.4 indicates that only two local optima exist.
The results involving local optima also raise another issue: Are there conditions
under which we can be sure that there is only one local optimum? In other words,
are there situations where we can be sure that any local optimum we find is also a
global optimum? The answer is that such conditions can be identified, and in many
practical cases, objective functions will have just one local optimum. We examine
this topic next.
8.2. LOCAL OPTIMA AND THE SEARCH
FOR AN OPTIMUM
From the earlier discussion, we know that the GRG algorithm may generate local
optima instead of global optima in nonlinear optimization problems. This possibility
raises at least two general questions.
1. Can we identify situations in which local optima exist that are not global
optima?
2. Are there situations in which the nonlinear solver guarantees that it has found a
global optimum?
Some theoretical results help answer these questions, but they do not take us very far.
To provide a glimpse of the relevant theory, we first define some terms. An
objective function is convex if a line connecting any two points on its graph lies on
or above the function itself. Similarly, a function is concave if a line connecting any
two points lies on or below the function. Informally, we can think of a convex function
as having a graph that is “bowl” shaped and a concave function as having one that is an
“inverted bowl.” These two concepts are relatively easy to see in two dimensions, as
shown in Figures 8.5 and 8.6, and they hold as well for multidimensional functions.
However, functions exist that are neither convex nor concave, such as the function
in Figure 8.2.
Figure 8.5. A convex function.
304 Chapter 8 Nonlinear Programming
A set of constraints delineates a convex feasible region if a line connecting any
two points in the region lies entirely within the region. Informally, this means that,
in a convex region, any blend (weighted average) of two feasible solutions is also feas-
ible. Figures 8.7 and 8.8 show a two-dimensional illustration of a convex region and a
nonconvex region, respectively, as shaded areas. A set of linear constraints gives rise
to a convex region. Nonlinear constraints may give rise to either convex or nonconvex
regions.
The GRG algorithm is guaranteed to find a global optimum when the objective
function is convex (when minimizing) or concave (when maximizing) if the con-
straints correspond to a convex region of feasible decisions. Although this property
Figure 8.6. A concave function.
Figure 8.7. A convex region.
Figure 8.8. A nonconvex region.
8.2. Local Optima and the Search for an Optimum 305