《数学建模》课程教学资源（PPT讲稿）Chapter 11 非线性规划 Nonlinear Programming

Chapter 11 Nonlinear programming to accompany Operations Research Applications and algorithms 4th edition by Wayne L. winston Copyright(c) 2004 Brooks/Cole, a division of Thomson Learning, Inc

Chapter 11 Nonlinear Programming to accompany Operations Research: Applications and Algorithms 4th edition by Wayne L. Winston Copyright (c) 2004 Brooks/Cole, a division of Thomson Learning, Inc

11. 1 Review of differential calculus ■ The equation lim f(x)=c x→a means that as x gets closer to a(but not equal to a, the value of f(x gets arbitrarily close to C A function f(x )is continuous at a point if lim f()=f(a x→a If f(x)is not continuous at x=a, we say that f(x) is discontinuous or has a discontinuity at a

2 11.1 Review of Differential Calculus ◼ The equation means that as x gets closer to a (but not equal to a), the value of f(x) gets arbitrarily close to c. ◼ A function f(x) is continuous at a point if If f(x) is not continuous at x=a, we say that f(x) is discontinuous (or has a discontinuity) at a. f x c x a = → lim ( ) lim f (x) f (a) x a = →

■ The derivative of a function f(×)atX=a (written f(a] is defined to be lim f(a+Ax)-f(a Ax→>0 △x N-th order Taylor series expansion f(a+h)=f(a)+ fo()h+fo+(p),nl (n+1 ■ The partial derivative of(1,X2…Xn)with respect to the variable xi is written where af f(x1,x1+△x f(x1…,x1…xn) ax Ar 0 △x

3 ◼ The derivative of a function f(x) at x = a (written f’(a)] is defined to be ◼ N-th order Taylor series expansion ◼ The partial derivative of f(x1, x2,…xn) with respect to the variable xi is written x f a x f a x  +  −  → ( ) ( ) lim 0 1 ( 1) 1 ( ) ( 1)! ( ) ! ( ) ( ) ( ) + = + = + + + = + n i n i n i i h n h f p i f a f a h f a i i i n i n x i i x f x x x x f x x x x f x f i  +  − =      → ( ,..., ,..., ) ( ,..., ,... ) lim , where 1 1 0

11.2 Introductory Concepts a general nonlinear programming problem (NLp can be expressed as follows Find the values of decision variables X1 个2rn that maX( or mIn)z=f(X1,X2灬…,Xn) s,t g1(X1,X2x…,Xn)(≤,=,Or≥)b1 st.g2(X1,X2…,X)(≤,=,or≥)b2 9m(X1,X2…,Xn)(≤,=,Or≥)bn

4 11.2 Introductory Concepts ◼ A general nonlinear programming problem (NLP) can be expressed as follows: Find the values of decision variables x1 , x2 ,…xn that max (or min) z = f(x1, x2,…,xn) s.t. g1(x1, x2,…,xn) (≤, =, or ≥)b1 s.t. g2(x1, x2,…,xn) (≤, =, or ≥)b2 . . . gm(x1, x2,…,xn) (≤, =, or ≥)bm

■ As in linear programming f(1,X2…,X) is the NLP's objective function, and g, X1 X2i Xn) (≤,=,or≥)b1…gn(xX1,X2…,Xn)(≤,=,Or≥)bm are the nlps constraints An nlp with no constraints is an unconstrained nlp The feasible region for nLp above is the set of points x1 X2ruXn that satisfy the m constraints in the nlp. a point in the feasible region is a feasible point and a point that is not in the feasible region is an infeasible point

5 ◼ As in linear programming f(x1 , x2 ,…,xn) is the NLP’s objective function, and g1(x1 , x2 ,…,xn) (≤, =, or ≥)b1 ,…gm(x1 , x2 ,…,xn) (≤, =, or ≥)bm are the NLP’s constraints. ◼ An NLP with no constraints is an unconstrained NLP. ◼ The feasible region for NLP above is the set of points (x1 , x2 ,…,xn) that satisfy the m constraints in the NLP. A point in the feasible region is a feasible point, and a point that is not in the feasible region is an infeasible point

If the nlp is a maximization problem then any point x in the feasible region for which f(x)> f(x holds true for all points x in the feasible region is an optimal solution to the NLp NLPs can be solved with lingo Even if the feasible region for an nlp is a convex set he optimal solution need not be a extreme point of the NLps feasible region For any NLP (maximization, a feasible point X (X1, X2,)is a local maximum if fo,,n) sufficiently small e, any feasible point X (X1,X2Xn) having|×1-×l∈(=1,2,…, satisfies f(×)≥f(x)

6 ◼ If the NLP is a maximization problem then any point in the feasible region for which f( ) ≥ f(x) holds true for all points x in the feasible region is an optimal solution to the NLP. ◼ NLPs can be solved with LINGO. ◼ Even if the feasible region for an NLP is a convex set, he optimal solution need not be a extreme point of the NLP’s feasible region. ◼ For any NLP (maximization), a feasible point x = (x1 ,x2 ,…,xn) is a local maximum if for sufficiently small , any feasible point x’ = (x’1 ,x’2 ,…,x’n) having | x1–x’1|< (i = 1,2,…,n) satisfies f(x)≥f(x’). x x

Example 11: Tire Production Firerock produces rubber used for tires by combining three ingredients: rubber, oil, and carbon black, the costs for each are given The rubber used in automobile tires must have d a hardness of between 25 and 35 d an elasticity of at 16 aa tensile strength of at least 12 To manufacture a set of four automobile tires 100 pounds of product is needed the rubber to make a set of tires must contain between 25 and 60 pounds of rubber and at least 50 pounds of carbon black

7 Example 11: Tire Production ◼ Firerock produces rubber used for tires by combining three ingredients: rubber, oil, and carbon black. The costs for each are given. ◼ The rubber used in automobile tires must have  a hardness of between 25 and 35  an elasticity of at 16  a tensile strength of at least 12 ◼ To manufacture a set of four automobile tires, 100 pounds of product is needed. ◼ The rubber to make a set of tires must contain between 25 and 60 pounds of rubber and at least 50 pounds of carbon black

Ex 11-continued ■ Define R= pounds of rubber in mixture used to produce four tires 0= pounds of oil in mixture used to produce four tires C= pounds of carbon black used to produce four tires Statistical analysis has shown that the hardness elasticity and tensile stregth of 100-pound mixture of rubber, oil, and carbon black is Tensile strength= 12.5-.10(0)-.001(0)2 Elasticity=17-+.35R.04(O)-.002(O)2 Hardness=34+.10R+.06(O)-3(C+.001(R)(O)+.005(0)2+.001C2 formulate the nlp whose solution will tell firerock how to minimize the cost of producing the rubber product needed to manufacture a set of automobile tires

8 Ex. 11 - continued ◼ Define: R = pounds of rubber in mixture used to produce four tires O = pounds of oil in mixture used to produce four tires C = pounds of carbon black used to produce four tires ◼ Statistical analysis has shown that the hardness, elasticity, and tensile strnegth of a 100-pound mixture of rubber, oil, and carbon black is Tensile strength = 12.5 - .10(O) - .001(O) 2 Elasticity = 17 - + .35R .04(O) - .002(O) 2 Hardness = 34 + .10R + .06(O) -.3(C) + .001(R)(O) +.005(O) 2+.001C2 ◼ Formulate the NLP whose solution will tell Firerock how to minimize the cost of producing the rubber product needed to manufacture a set of automobile tires

Example 11: Solution ■ After defining ts= Tensile strength E= Elasticity H= Hardness of mixture the Lingo program gives the correct formulation

9 Example 11: Solution ◼ After defining TS = Tensile Strength E = Elasticity H = Hardness of mixture the LINGO program gives the correct formulation

It is easy to use the Excel solver to solve NLPs The process is similar to a linear model For NLPs having multiple local optimal solutions the solver may fail to find the optimal solution because it may pick a local extremum that is not a global extremum. 10

10 ◼ It is easy to use the Excel Solver to solve NLPs. ◼ The process is similar to a linear model. ◼ For NLPs having multiple local optimal solutions, the Solver may fail to find the optimal solution because it may pick a local extremum that is not a global extremum