# NON-LINEAR PROGRAMMING (NLP) ¢â‚¬¢ Linear programming, integer programming...

date post

11-Jul-2020Category

## Documents

view

3download

0

Embed Size (px)

### Transcript of NON-LINEAR PROGRAMMING (NLP) ¢â‚¬¢ Linear programming, integer programming...

PROF. DR. VEDAT CEYHAN

NON-LINEAR PROGRAMMING (NLP)

Similarities & differences

Characteristics of NLP

NLP models

One Variable NLP

Multi Variable NLP

Unlimited NLP

Limited NLP

Basic concept

Case studies

2

Similarities & differences

• Linear programming(LP) – Linear target function+ linear constraints

– Continuous variable

• Integer programming (IP) – Linear target function+ linear constraints

– Discrete variable

• Non-linear programming (NLP) – The objective is linear but constraints are non-linear

– Non-linear objectives and linear constraints

– Non-linear objectives and constraints

3

Characteristics of NLP

Solution is difficult

Solution may tie initial point.

Initial point is subjective.

4

• NLP forms: – Non-linear objectives

– Non-linear constraints

– Non-linear objectives and constraints

The main problem is algorithm selection

2min ( -3)

. . x< 3

x

s t

1 2

2 2 1 2

min

. . 4

x x

s t x x

2 1 2

2 2 1 2

min ( 2)

. . 4

x x

s t x x

5

• Constructing model is required for solving optimization problem. Mathematical model is based on determination of variables and defining their functional relationship

• 3 components of mathematical model

– Objective function,

– Constraints

– Non-negativity restriction

6

• Linear programming, integer programming and goal programming assume that objective function and constraints is linear. Not include non-linear expressions such as 1/X2, log X3

• NLP procedures does not produce optimum solution every time in contrary with linear programming (Render ve ark, 2012).

7

Objective function in NLP

• gi(x) ≤ bi constraints

• z = f(x) objective function

We find the vector of x= (x1, x2,…, xn), which produce optimum solution for objective

8

NLP models

• Associated with the number of variable

–One variable or multivariate,

Associated with the presence of restrictions

– restricted or unrestricted

9

NLP models

Constraints: equality

Limited Model

One variable models Constraints: inequality

Unrestricted Model

Constraints: equality

Limited Model

Multivariate models Constraints:inequality Unresticted Model

10

Basic concepts

• Increasing and decreasing function

y=f(x)

x1 and x2 is a random figüre

If the function is f(x1)

Increasing and decreasing function

Increasing function Decreasing function

12

– Local Maximum and Minimum

f(x)’’> f(x)’

f(x)’’< f(x)’ local min. or max

–Gradiant of function

Gradiant function of Z=f(x1,x2,…,xn) is vector of first derivatives.

13

Hessian Matrix

• Hessian matrix is a nxn matrix of second partial derivative of f(x1,x2,…,xn) function

14

In LP, solution region is convex set and optimum solution is one of the corner point

In NLP, it is not necessary that optimum solution is one of the corner point

15

Concave function Convex function

16

Example:

1) Is f(x)= √x function whether convex or concave at [S= 0, ∞)?

f(x)=√x concave function

Since line between two point take place under the curve, the

function is concave. 17

2) Is f(x)=x3 function whether convex or concave at S = R1=(-∞, ∞)?

f(x)=x³ Neither convex nor concave function

18

3) Is f(x)=3x-3 function whether convex or concave at S = R1=(-∞, ∞)?

1

Both convex and concave function

-3

19

One variable unrstricted NLP

• Deal with finding maximum or minimum point of one variable function with no restriction

20

Multivariate unrestricted NLP

• Deal with finding optimum point (x1*,x2*,…,xn*) that is maximum or minimum point of multivariate function of f(x1,x2,…,xn) with no restriction

• Demand function explained by price, preference, income, etc. İs a example for multivariate unrestricted NLP.

21

Restricted NLP

• Examining the colineairty among x1,x2,……,xn that is variables of multivariate function of f(x1,x2,……,xn

• f(x1,x2,……,xn) function,

• g1(x1,x2,……,xn) = b1 • g2(x1,x2,……,xn) =b2 restrictions

• gm(x1,x2,……,xn) =bm

We are looking for point that is maximum or minimum under upper restrictions.

22

Solution

• Lagrange function

L(x1,x2,…………….xn,λ1,λ2,……….λm)= f(x1,x2,……..xn) + i[ bi- gi (x1,x2,………xn)]

23

Example

1 1

2

2 2

1 2

1 2

1 2

1 2

2 2

1 2 1 1 2 2 1 2

1 1 2 1

2

Minimize ( 4) ( 4)

subject to 2 3 6

3 2 12

and , 0

The Lagrangian is:

( 4) ( 4) (6 2 3 ) ( 12 3 2 )

Kuhn Tucker Conditions:

2( 4) 2 3 0 0 and 0

2( 4)

x x

x

C x x

x x

x x

x x

Z x x x x x x

Z x x x Z

Z x

2

1 1

2 2

1 2 2

1 2 1 1

1 2 2 2

28 36 16 1 2 1 213 13 13

3 2 0 0 and 0

6 2 3 0 0 and 0

12 3 2 0 0 and 0

Solution: , , 0,

xy x Z

Z x x Z

Z x x Z

x x

24

Non-linear objective function and linear constraints

25

Case of non-linear objective function and linear constraints

Great Western Appliance firm sell toast machine of Mikrotoaster (X1) and Self-Clean Toaster Oven (X2). Firm gain net profit by $28 per toaster. Profit function is 21X2+0,25

Objective function is non-linear:

Maximum profit =28X1+21X2+0,25

There are two linear constraints

X1+X2 ≤ 1,000 (production capacity)

0.5X1+0.4X2 ≤ 500 (term of sale)

X1, X2 ≥ 0

(Source: Render ve ark., 2012)

26

2. Quadratic programming

Objective function includes terms such as 0,25 and when the restrictions is linear

Quadratic programming problems can be solved by using adjusted simplex algorithms.

(Source: Render and ark., 2012)

27

EXAMPLES

28

WIN QSB for NLP

29

WİN QSB interface

30

WİN QSB EKRANINI TANIYALIM

31

Unrestricted NLP example

• minimum x(sin(3.14159x))

• 0

33

For unrestricted case, enter

“0”

Unrestricted NLP example

34

35

Attention!

Interval of X1

Graphical solution

x=3.5287 Objective function= -3.5144.

36

Example 2:

Objective function:

maximum 2x1 + x2 - 5loge(x1)sin(x2)

Constraints x1x2

38

39

x1=3.3340 ve x2=2.9997 Objective function=8.8166

40

Non-linear function and constraints

41

• In medium size hospital having 200-400 patient bed, Hospicare Corporation, annual profit depend on number of patient(X1) ve number of patient surgeon(X2) bağlıdır.

• Non-linear objective function for Hospicare : $13X1 + $6X1X2 + $5X2 + $1/X2

Constraints;

• 2X1 2+4X2≤90 (nursery capacity)

• X1+X2 3≤75 (X-ray capacity)

• 8X1-2X2≤61 (marketing budget)

42

43

44

45

Example: Pickens Memorial Hospital

Patient demand exceeds capacity of hospital

Objective: Maximum profit

46

Decision variables

M =number of served patient

S = number of served patient for surgery

P = number of served child patient

Profit function When increasing patient, profit increasing non-

linearly.

47

Constraints

• Hospital capacity: Total 200 patient

• X-ray capacity: 560 x-rays per week

• Marketing budget: $100

Recommended

*View more*