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