Taylor Introms10 PPT 10

Nonlinear Programming
Chapter 10
Copyright 2010 Pearson Education, Inc. Publishing as Prentice Hall
10-1
Chapter Topics
Nonlinear Profit Analysis Constrained Optimization Solution of Nonlinear Programming Problems with Excel Nonlinear Programming Model with Multiple Constraints Nonlinear Model Examples
10-2
Overview
Problems that fit the general linear programming format but contain nonlinear functions are termed nonlinear programming (NLP) problems.
Solution methods are more complex than linear programming methods.

Determining an optimal solution is often difficult, if not impossible. Solution techniques generally involve searching a solution surface for high or low points requiring the use of advanced mathematics.
10-3
Optimal Value of a Single Nonlinear Function Basic Model

Profit function, Z, with volume independent of price: Z = vp - cf - vcv where v = sales volume p = price cf = unit fixed cost cv = unit variable cost
Add volume/price relationship: v = 1,500 - 24.6p
Figure 10.1 Linear Relationship of Volume to Price

10-4
Optimal Value of a Single Nonlinear Function

With fixed cost (cf = $10,000) and variable cost (cv = $8): Profit, Z = 1,696.8p - 24.6p2 - 22,000
Figure 10.2 The Nonlinear Profit Function

10-5
Optimal Value of a Single Nonlinear Function Maximum Point on a Curve

The slope of a curve at any point is equal to the derivative of the curves function.
The slope of a curve at its highest point equals zero.
Figure 10.3 Maximum profit for the profit function

10-6
Optimal Value of a Single Nonlinear Function Solution Using Calculus

Z = 1,696.8p - 24.6p2 - 2,000
dZ/dp = 1,696.8 - 49.2p =0
p = 1696.8/49.2
= $34.49 v = 1,500 - 24.6p
v = 651.6 pairs of jeans

Z = $7,259.45
Figure 10.4
10-7
Constrained Optimization in Nonlinear Problems Definition

A nonlinear problem containing one or more constraints becomes a constrained optimization model or a nonlinear programming (NLP) model. A nonlinear programming model has the same general form as the linear programming model except that the objective function and/or the constraint(s) are nonlinear. Solution procedures are much more complex and no guaranteed procedure exists for all NLP models.
10-8
Constrained Optimization in Nonlinear Problems Graphical Interpretation (1 of 3)

Effect of adding constraints to nonlinear problem:
Figure 10.5 Nonlinear Profit Curve for the Profit Analysis Model
10-9
Figure 10.6 A Constrained Optimization Model

10-10
Figure 10.7
10-11
Constrained Optimization in Nonlinear Problems Characteristics

Unlike linear programming, solution is often not on the
boundary of the feasible solution space.

Cannot simply look at points on the solution space boundary but must consider other points on the surface of the objective
function.
This greatly complicates solution approaches. Solution techniques can be very complex.
10-12
Western Clothing Problem Solution Using Excel (1 of 3)
Exhibit 10.1
10-13
Exhibit 10.2
10-14
Exhibit 10.3
10-15
Beaver Creek Pottery Company Problem Solution Using Excel (1 of 6)

Maximize Z = $(4 - 0.1x1)x1 + (5 - 0.2x2)x2
subject to: x1 + 2x2 = 40

Where: x1 = number of bowls produced x2 = number of mugs produced 4 0.1X1 = profit ($) per bowl 5 0.2X2 = profit ($) per mug
10-16
Exhibit 10.4
10-17
Exhibit 10.5
10-18
Exhibit 10.6
10-19
Exhibit 10.7
10-20
Exhibit 10.8
10-21
Western Clothing Company Problem Solution Using Excel (1 of 4)

Maximize Z = (p1 - 12)x1 + (p2 - 9)x2
subject to: 2x1 + 2.7x2 6,000 3.6x1 + 2.9x2 8,500 7.2x1 + 8.5x2 15,000
where: x1 = 1,500 - 24.6p1 x2 = 2,700 - 63.8p2 p1 = price of designer jeans p2 = price of straight jeans
10-22
Exhibit 10.9
10-23
Exhibit 10.10
10-24
Exhibit 10.11
10-25
Facility Location Example Problem Problem Definition and Data (1 of 2)

Centrally locate a facility that serves several customers or other facilities in order to minimize distance or miles traveled (d) between facility and customers. di = sqrt[(xi - x)2 + (yi - y)2] Where:
(x,y) = coordinates of proposed facility (xi,yi) = coordinates of customer or location facility i

Minimize total miles d = diti Where: di = distance to town i ti =annual trips to town i
10-26
Facility Location Example Problem Problem Definition and Data (2 of 2)
Town Abbeville Benton Clayton Dunnig Eden
Coordinates x y 20 20 10 35 25 9 32 15 10 8
Annual Trips 75 105 135 60 90
10-27
Facility Location Example Problem Solution Using Excel
Exhibit 10.12
10-28
Facility Location Example Problem Solution Map
Figure 10.8 Rescue Squad Facility Location

10-29
Investment Portfolio Selection Example Problem Definition and Model Formulation (1 of 2)

Objective of the portfolio selection model is to:
minimize some measure of portfolio risk (variance in the return on investment)

while achieving some specified minimum return on the total portfolio investment.
10-30
Investment Portfolio Selection Example Problem Definition and Model Formulation (2 of 2)

Minimize S = x12s12 + x22s22 + +xn2sn2 + xixjrijsisj ij where: S = variance of annual return of the portfolio xi,xj = the proportion of money invested in investments i or j si2 = the variance for investment i rij = the correlation between returns on investments i and j si,sj = the std. dev. of returns for investments i and j subject to: r1x1 + r2x2 + + r nxn r m x1 + x2 + xn = 1.0 where: ri = expected annual return on investment i r m = the minimum desired annual return from the portfolio
10-31
Investment Portfolio Selection Example Problem Solution Using Excel (1 of 5)

Stock (xi) Altacam Bestco Com.com Delphi Annual Return (ri) .08 .09 .16 .12 Variance (si) .009 .015 .040 .023
Correlation (rij) .4 .3 .6 .2 .7 .4
10-32
Stock combination (i,j) A,B A,C A,D B,C B,D C,D


Four stocks, desired annual return of at least 0.11. Minimize Z = S = x12(.009) + x22(.015) + x32(.040) + X42(.023) + x1x2 (.4)(.009)1/2(0.015)1/2 + x1x3(.3)(.009)1/2(.040)1/2 + x1x4(.6)(.009)1/2(.023)1/2 + x2x3(.2)(.015)1/2(.040)1/2 + x2x4(.7)(.015)1/2(.023)1/2 + x3x4(.4)(.040)1/2(.023)1/2 + x2x1(.4)(.015)1/2(.009)1/2 + x3x1(.3)(.040)1/2 + (.009)1/2 + x4x1(.6)(.023)1/2(.009)1/2 + x3x2(.2)(.040)1/2(.015)1/2 + x4x2(.7)(.023)1/2(.015)1/2 + x4x3(.4)(.023)1/2(.040)1/2 subject to: .08x1 + .09x2 + .16x3 + .12x4 0.11 x1 + x2 + x3 + x4 = 1.00 xi 0
10-33
Exhibit 10.13
10-34
Exhibit 10.14
10-35
Exhibit 10.15
10-36
Hickory Cabinet and Furniture Company Example Problem and Solution (1 of 2)

Model: Maximize Z = $280x1 - 6x12 + 160x2 - 3x22 subject to: 20x1 + 10x2 = 800 board ft. Where: x1 = number of chairs x2 = number of tables
10-37
Hickory Cabinet and Furniture Company Example Problem and Solution (2 of 2)
10-38
10-39

Taylor Introms10 PPT 10

Uploaded by

Copyright:

Available Formats

Taylor Introms10 PPT 10

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

Taylor Introms10 PPT 10

Uploaded by

Copyright:

Available Formats

Nonlinear Programming

Copyright 2010 Pearson Education, Inc. Publishing as Prentice Hall

Copyright 2010 Pearson Education, Inc. Publishing as Prentice Hall

Solution methods are more complex than linear programming methods.

Copyright 2010 Pearson Education, Inc. Publishing as Prentice Hall

Optimal Value of a Single Nonlinear Function Basic Model

Figure 10.1 Linear Relationship of Volume to Price

Optimal Value of a Single Nonlinear Function

Figure 10.2 The Nonlinear Profit Function

Optimal Value of a Single Nonlinear Function Maximum Point on a Curve

Figure 10.3 Maximum profit for the profit function

Optimal Value of a Single Nonlinear Function Solution Using Calculus

v = 651.6 pairs of jeans

Copyright 2010 Pearson Education, Inc. Publishing as Prentice Hall

Constrained Optimization in Nonlinear Problems Definition

Copyright 2010 Pearson Education, Inc. Publishing as Prentice Hall

Constrained Optimization in Nonlinear Problems Graphical Interpretation (1 of 3)

Constrained Optimization in Nonlinear Problems Graphical Interpretation (2 of 3)

Figure 10.6 A Constrained Optimization Model

Constrained Optimization in Nonlinear Problems Graphical Interpretation (3 of 3)

Constrained Optimization in Nonlinear Problems Characteristics

boundary of the feasible solution space.

Copyright 2010 Pearson Education, Inc. Publishing as Prentice Hall

Western Clothing Problem Solution Using Excel (1 of 3)

Western Clothing Problem Solution Using Excel (2 of 3)

Western Clothing Problem Solution Using Excel (3 of 3)

Beaver Creek Pottery Company Problem Solution Using Excel (1 of 6)

subject to: x1 + 2x2 = 40

Copyright 2010 Pearson Education, Inc. Publishing as Prentice Hall

Beaver Creek Pottery Company Problem Solution Using Excel (2 of 6)

Beaver Creek Pottery Company Problem Solution Using Excel (3 of 6)

Beaver Creek Pottery Company Problem Solution Using Excel (4 of 6)

Beaver Creek Pottery Company Problem Solution Using Excel (5 of 6)

Beaver Creek Pottery Company Problem Solution Using Excel (6 of 6)

Western Clothing Company Problem Solution Using Excel (1 of 4)

Copyright 2010 Pearson Education, Inc. Publishing as Prentice Hall

Western Clothing Company Problem Solution Using Excel (2 of 4)

Western Clothing Company Problem Solution Using Excel (3 of 4)

Western Clothing Company Problem Solution Using Excel (4 of 4)

Facility Location Example Problem Problem Definition and Data (1 of 2)

(x,y) = coordinates of proposed facility (xi,yi) = coordinates of customer or location facility i

Facility Location Example Problem Problem Definition and Data (2 of 2)

Town Abbeville Benton Clayton Dunnig Eden

Annual Trips 75 105 135 60 90

Copyright 2010 Pearson Education, Inc. Publishing as Prentice Hall

Facility Location Example Problem Solution Using Excel

Facility Location Example Problem Solution Map

Figure 10.8 Rescue Squad Facility Location

Investment Portfolio Selection Example Problem Definition and Model Formulation (1 of 2)

minimize some measure of portfolio risk (variance in the return on investment)

Copyright 2010 Pearson Education, Inc. Publishing as Prentice Hall

Investment Portfolio Selection Example Problem Definition and Model Formulation (2 of 2)

Investment Portfolio Selection Example Problem Solution Using Excel (1 of 5)

Stock combination (i,j) A,B A,C A,D B,C B,D C,D

Investment Portfolio Selection Example Problem Solution Using Excel (2 of 5)

Investment Portfolio Selection Example Problem Solution Using Excel (3 of 5)

Investment Portfolio Selection Example Problem Solution Using Excel (4 of 5)

Investment Portfolio Selection Example Problem Solution Using Excel (5 of 5)

Hickory Cabinet and Furniture Company Example Problem and Solution (1 of 2)