Estatistica

Disponível somente no TrabalhosFeitos
  • Páginas : 24 (5878 palavras )
  • Download(s) : 0
  • Publicado : 4 de março de 2011
Ler documento completo
Amostra do texto
Problemas de Programação Não-Linear
Tipos de problemas
Para que um problema de programação matemática seja caracterizado como de programação não-linear, ele deve apresentar uma função objetivo não linear, ou pelo menos uma das restrições caracterizada por uma função não linear. Os problemas de programação linear podem ser classificados, de acordo com o número de variáveis e restrições em: a)Problemas mono-variados sem restrição Min f ( x) = 2 x 6 + 3 x 4 − 12 x

b) Problemas multi-variados sem restrição Min
2 f ( x1 , x2 ) = x12 + 2 x2 − 2 x2 − 2 x1 x2

c) Problemas mono-variados com restrição

Min

f ( x) = 3 ( x 2 − 2) 2 ln( x 2 + x + 4)

s.a : 0 ≤ x 2 ≤ 2 d) Problemas multi-variados com restrição
Min z ( x1 , x2 ,..., xn ) = ∑ ∫
j xj 0

c j ( w) dw

s.a :

∑f
krs k

= qrs

∀r , s ∀k , r , s

f krs = ∑ x j δ jrs ,k
j

xj ≥ 0

∀j

Condições de otimalidade
Para que uma solução seja considerada ótima para um problema de programação não-linear, ela deverá satisfazer um conjunto de condições atribuídas a Karush, Kuhn e Tucker. Tais condições, são também conhecidas por condições de KKT. Seja o problema de otimização não linear definido como:Min z = f ( x1 , x2 ,..., xn ) s.a : g i ( x1 , x2 ,..., xn ) ≤ 0 ∀i = 1,..., m (ui )

onde f ( x1 , x2 ,..., xn ) e gi ( x1 , x2 ,..., xn ) são funções diferenciáveis em cada uma das variáveis x j , ∀j = 1,..., n , e seja ui um escalar associado a restrição gi ( x1 , x2 ,..., xn ) . Então,

* * * x* = ( x1 , x2 ,..., xn ) pode ser uma solução ótima para o problema de programação não-linearacima, somente se existem m números u1 , u2 ,...um (conhecidos pelo nome de multiplicadores de Lagrange) que satisfaçam todas as seguintes condições: a)
∇f ( x* ) + ∑ ui ∇g i ( x * ) = 0
i =1 m

b) ui g i ( x* ) = 0 c) d) ui ≥ 0
g i ( x* ) ≤ 0

∀i = 1,..., m

∀i = 1,..., m
∀i = 1,..., m

Se além destas condições a função f ( x1 , x2 ,..., xn ) é convexa e o conjunto de soluções viáveis* * * definido pelas restrições g i ( x1 , x2 ,..., xn ) ≤ 0 é convexo, então x* = ( x1 , x2 ,..., xn ) é o mínimo global ou solução ótima do problema.

Na figura abaixo é ilustrada a condição de otimalidade para um problema de programação não linear, onde a solução ótima é x* ∈ S . Note-se que existem multiplicadores u1 e u2 positivos, e u3 = 0 para os quais as quatro condições de KKT sãosatisfeitas. Além disto, a função objetivo representada pelas curvas de nível tracejadas (verde) e o conjunto solução definido pelo poliedro (azul) são convexas.

∇g1

− ∇f

x2

∇g 2

x*
g1 ≤ 0
g2 ≤ 0

∇f

S

g3 ≤ 0

x1
Definição

Uma função f ( x1 ,..., xn ) é convexa se, e somente se, para quaisquer dois pontos ′ ′ distintos, ( x1 ,..., x′ ) e ( x1′,..., x′′) , tem-se: n n
′′ ′ ′ ′ ′ f [λ ( x1,..., xn ) + (1 − λ ) ( x1′,..., xn′)] ≤ λ f ( x1 ,..., x′ ) + (1 − λ ) f ( x1′,..., x′′) n n

para todo escalar 0 ≤ λ ≤ 1 .■
A convexidade de uma função f também poderá ser verificada através da sua matriz hessiana H (x) que deverá ser semidefinida positiva, isto é, deverá satisfazer a seguinte condição:
v T H ( x) v ≥ 0

[v1

v2

 ∂2 f  ∂x 2 1   ∂2 f  ∂x ∂x... vn ]  2 1   ...   ∂2 f    ∂xn ∂x1

∂2 f ∂x1 ∂x2 ∂2 f 2 ∂x2 ... ∂2 f ∂xn ∂x2

∂2 f   v1  ∂x1 ∂xn     ∂2 f    ...   v2  ∂x2 ∂xn    ≥0    ...  ... ...      2 ∂ f    vn  ... 2 ∂xn   ...

para qualquer vetor vT = [v1 v2 ... vn ] , situação em que a função é convexa. Se esta condição é satisfeita com desigualdade, então a função é dita ser estritamenteconvexa.

Definição
Um conjunto solução S é convexo se, e somente se, para quaisquer dois pontos ′ ′ distintos ( x1 ,..., x′ ) ∈ S e ( x1′,..., x′′) ∈ S e para todo escalar 0 ≤ λ ≤ 1 , tem-se que: n n ′ ′ λ ( x1 ,..., x′ ) + (1 − λ ) ( x1′,..., x′′) ∈ S ■ n n A intersecção de conjuntos convexos também é um conjunto convexo. Para o caso particular de problemas que não possuem restrições, as...
tracking img