Programação

Não Linear Restrita

EA 044 Planejamento e Análise

de Sistemas de Produção

DCA-FEEC-Unicamp

2

Tópicos

1-Introdução

2-Modelos convexos

3-Método dos multiplicadores de Lagrange

4-Condições de Karush-Kuhn-Tucker

DCA-FEEC-Unicamp

3

DCA-FEEC-Unicamp

max (min) f (x)

sa x∈D ⊂ Rn

� Modelos de programação não linear

max (min) f (x)

sa x∈D = Rn

restritos

irrestritos

1-Introdução

4

DCA-FEEC-Unicamp

Exemplo: localização e alocação

regiões

distribuidoras

Distribuidores: 17

Regiões: 650 agrupando 24.000 clientes

5

DCA-FEEC-Unicamp

i = distribuidor, i = 1,....,17

j = região, j = 1,...,650

j

hj

kj

i

xi

yj

dj = número de viagens por ano para entregas à j-ésima região

6

DCA-FEEC-Unicamp

650,,1;17,,11,0

650,,1,sa

)()(min

17

1

17

1

650

1

22

KK

K

==≥

==

−+−

∑

∑∑

=

= =

jw

jdw

hyhxw

ij

ijij

i jjijiij

� Ideia: minimizar custo de transporte

– minimizar número de viagens (wij) de i → j

– minimizar distância entre i e j

modelo PNL

7

2-Modelos convexos

DCA-FEEC-Unicamp

Kkcl

Jjbh

Iiag

f

kk

jj

ii

,,1,)x(

,,1,)x(

,,1,)x(sa

)x(min

K

K

K

==

=≤=≥

f(x) convexa, gi(x) côncava ∀i, hj(x) convexa ∀j, lk(x) linear ∀k

8

min ( x1– 3)2 + ( x2 – 3)2

sa 3 x1 + 5 x2 ≤ 155 x1 + 2 x2 ≤ 10

x1, x2 ≥ 0

Exemplo

x1

x2

x*y*

f(x)

h1(x)

h2(x)

3

3

1

1

5

DCA-FEEC-Unicamp

9

DCA-FEEC-Unicamp

Kkcl

Jjbh

Iiag

f

kk

jj

ii

,,1,)x(

,,1,)x(

,,1,)x(sa

)x(max

K

K

K

==

=≤=≥

f(x) côncava, gi(x) côncava ∀i, hj(x) convexa ∀j, lk(x) linear ∀k

10

max 3 w1 – w2 + 8 ln w1

sa 4 w12 – w1 w2 + w2

2 ≤ 100

w1 + w2 = 4

w1, w2 ≥ 0

Exemplo

DCA-FEEC-Unicamp

11

0.5 1 1.5 2 2.5 3 3.5 4

0.5

1

1.5

2

2.5

3

3.5

4

w1

w2

Função objetivo

f(w1, w2) = 3 w1 – w2 +8 ln w1

DCA-FEEC-Unicamp

12

Restrições principais

0.5 1 1.5 2 2.5 3 3.5 4

0.5

1

1.5

2

2.5

3

3.5

4

w1

w2

h(w1, w2) = 4 w12 – w1 w2 + w2

2 ≤ 100

DCA-FEEC-Unicamp

13

130.5 1 1.5 2 2.5 3 3.5 4

0.5

1

1.5

2

2.5

3

3.5

4

w1

w2

l(w1, w2) = w1 + w2 = 4

DCA-FEEC-Unicamp

140 1 2 3 4 5 6

0

0.5

1

1.5

2

2.5

3

3.5

4

w1

w2

l =4

g =100

max 3 w1 – w2 +8 ln w1

sa 4 w12 – w1 w2 + w2

2 ≤ 100

w1 + w2 = 4

w1, w2 ≥ 0

DCA-FEEC-Unicamp

15

Modelos separáveis

� Função f(x1,...,xn) separável se ∑=

=n

jjjn xfxxf

11 )(),,( K

� Modelo separável

Kkcl

Jjbh

Iiag

f

kk

jj

ii

,,1,)x(

,,1,)x(

,,1,)x(sa

)x(max

K

K

K

==

=≤=≥

f, gi, hj, lk são funções separáveis

DCA-FEEC-Unicamp

16

DCA-FEEC-Unicamp

Propriedade de modelos convexos

Se a função objetivo do modelo é convexa e as restrições

produzem um conjunto convexo factível, então toda solução

ótima local é uma solução ótima global.

gi(x) côncava ∀i

hj(x) convexa ∀j

lk(x) linear ∀k

conjunto convexo

f convexa (côncava) função unimodal

17

DCA-FEEC-Unicamp

3-Método dos multiplicadores de Lagrange

mi

bg

f

ii

,,1

)x(sa

)x(min(max)

K== restrições ativas

função Lagrangeana∑ −ν+=ν=

m

iiii gbfL

1)]x([)x()x,(

vi = multiplicador de Lagrange associado à restrição i

18

DCA-FEEC-Unicamp

Pontos estacionários da função Lagrangeana

ibg

jx

fv

x

ggf

ii

j

m

ii

j

im

iii

∀=

∀∂∂=∑

∂∂→∑ ∇ν=∇

==

,*)x(

,)]x*()x*(11

*

(x* , v*) é um ponto estacionário de L(x,v) se ∇L(x*,v*) = 0

Se (x* , v*) é um ponto estacionário de L(x,v) e x* é uma solução ótima

irrestrita de L(x,v), então x* é uma solução ótima do modelo com

restrições de igualdade correspondente.

19

DCA-FEEC-Unicamp

Exemplo

)1,0,0()x(

)0,24,24()x(

)2,8,12()x(

]1[]2424360[46),x(

1

3602424sa

46min

2

1

321

3221123

22

21

3

21

23

22

21

=∇=∇=∇

−+−−+++=

==+++

g

g

xxxf

xvxxvxxxvL

x

xx

xxx

20

DCA-FEEC-Unicamp

10822727246),x(

)2,3,1,9,6(),,,,(

11

3602424

21

824

1224

32123

22

21

*2

*1

*3

*2

*1

3

21

32

21

11

+−−−++=

=

==+===

xxxxxxvL

vvxxx

x

xx

xv

xv

xv

convexa

)2,3,1,9,6(),,,,( *2

*1

*3

*2

*1 =vvxxx ⇒ mínimo de L(x,v)

⇓

⇓

21

Multiplicadores de Lagrange: interpretação

DCA-FEEC-Unicamp

vi = variação valor ótimo f quando bi aumenta de uma unidade

vi = variável dual

ii b

Lv

∂∂=*

� Limitações

– condições de estacionariedade difíceis de resolver

– restrições de desigualdade aumenta a complexidade

– soluções ótimas globais somente para modelos tratáveis

22

DCA-FEEC-Unicamp

4-Condições de Karush-Kuhn-Tucker

� Forma geral PNL diferenciáveis

Eibg

Libg

Gibg

f

ii

ii

ii

∈∀=∈∀≤∈∀≥

,(x)

,(x)

,(x) sa

(x)min(max)

f, gi : funções diferenciáveis

G, L, E : conjuntos de índices

23

Condições das folgas complementares

0(x)][ =−ν iii gb para todas desigualdades i

Restrições nos sinais dos multiplicadores

objetivo i é ≤ i é ≥ i é =

min vi ≤ 0 vi ≥ 0 irrestrito

max vi ≥ 0 vi ≤ 0 irrestrito

DCA-FEEC-Unicamp

24

Condições de Karush-Kuhn-Tucker

Soluções (x, v) satisfazem as condições de KKT se

1. f, gi são funções diferenciáveis

2. condições das folgas complementares

3. restrições no sinais dos multiplicadores

4. restrições primais

5. equação dos gradientes

Ponto de KKT: qualquer x para o qual existe um v que satisfaça

as condições de KKT

∑ ∇=∇i

ii fvg (x)(x)

DCA-FEEC-Unicamp

25

objetivo ∇f (x)∆x > 0 ∇f (x)∆x < 0

min não melhora melhora

max melhora não melhora

∇f (x)∆x = 0 ⇒ necessitamos de mais informação

Característica da direção de busca ∆x

Factibilidade da direção de busca ∆x

==≤≤≥≥

∆∇restriçõestodas0

restrições0

restrições0

(x) ativas

ativas

xgi

(14.23)

(14.24)

DCA-FEEC-Unicamp

26

� As condições de KKT fornecem um teste de primeira ordem para

determinar a ausência de direções factíveis que melhoram o valor

da função objetivo

� Isto é, x é um ponto de KKT se e somente se não existe uma direção

∆x em x que satisfaz as condições de primeira ordem (14.23) e (14.24)

⇓

� Condições KKT são suficientes para ótimo local: x ponto KKT ⇒ x ótimo local

� PNL convexo ⇒ condições de KKT são suficientes para ótimo global

Condições suficientes de KKT

DCA-FEEC-Unicamp

27

� Necessidade: se x é uma solução ótima, então x satisfaz KKT

� Solução ótima local é um ponto de KKT se

– todas as restrições são lineares

– os gradientes de todas as restrições ativas no ponto ótimo local

são linearmente independentes (qualificação de restrição)

Condições necessárias de KKT

DCA-FEEC-Unicamp

28

x1

x2

x*y*

f(x)

g1(x)

g2(x)

3

3

1

1 ∇ f

∇ g1

∇ g2

min ( x1- 3)2 + ( x2 - 3)2

sa 3 x1 + 5 x2 ≤ 15

5 x1 + 2 x2 ≤ 10

x1, x2 ≥ 0

Exemplo

DCA-FEEC-Unicamp

29

min x12 + 4x2

sa ( x1 − 1)2 + x22 ≤ 1

( x1+ 1)2 + x22 ≤ 1

x1

x2

x*

f(x)

g1(x)g2(x)3

3

1

1

∇ f

∇ g1 ∇ g2

Exemplo

DCA-FEEC-Unicamp

30

DCA-FEEC-UnicampProfFernandoGomide

Este material refere-se às notas de aula do curso EA 044 Planejamento e

Análise de Sistemas de Produção da Faculdade de Engenharia Elétrica e de

Computação da Unicamp. Não substitui o livro texto, as referências

recomendadas e nem as aulas expositivas. Este material não pode ser

reproduzido sem autorização prévia dos autores. Quando autorizado, seu

uso é exclusivo para atividades de ensino e pesquisa em instituições sem

fins lucrativos.

Observação