Programação não linear · Introdução • Em um problema de PNL, pelo menos a função objetivo...

Programação não linear

Introdução

max ou min z= f(x1, x2,..., xn) s.a: g1(x1,x2,...,xn) <=, =, >= b1

•

•

• ..

gn(x1,x2,...,xn) <=, =, >= b1

x1, x2, ..., xn <=0

Introdução

• Em um problema de PNL, pelo menos a função objetivo ou uma das restrições será representada por uma função não linear das variáveis de decisão.

Introdução

• PNL são difíceis de serem resolvidos, porém, são muito comuns na prática

• Os algoritmos de PNL são mais diversos e mais complexos, comparados aos de programação linear ou programação binária e/ou inteira.

Introdução

• PNL podem ser classificados como:• PNL irrestrita (com uma única variável ou

com múltiplas variáveis)• PNL com restrição (programação

côncava, convexa, quadrática e separável)

Programação Não LinearAplicações

●Problemas de Mix de Produtos em que o “lucro” obtido por produto varia com a quantidade vendida.

●Problemas de Transporte com custos variáveis de transporte em relação à quantidade enviada.

●Seleção de Portfolio com Risco

Introdução

• Geometria da programação não linear

Introdução

• Solução ótima na fronteira das restrições

Introdução

• Solução ótima no interior das restrições

Introdução

• Ótimo local devido à função objetivo

Introdução

• Ótimo local devido às restrições

Problema com uma restrição não linear

Problema com a Função Objetivo não linear

●Considere o Problema de Programação Linear e sua solução gráfica

1

Max Z x x = +3 51 2

1

2x ≤ 122

3x x + ≤2 18 1 2

s r x ≤ 4. .

x x≥ ≥0 01 2,

Programação Não LinearSolução Gráfica

x2

x1

(0;6)(2;6)

(0;0) (4;0)

(4;3)SoluçãoViável

●Considere o Problema e sua solução gráfica.

Max Z x x = +3 51 2

1s.t. x ≤ 4

x x≥ ≥0 01 2,

9 5 21612

22x x+ ≤

Programação Não LinearSolução Gráfica

0

x2

1 2 3 4

4

2

6

0 x1

SoluçãoViável

(2;6)

●A solução ótima:● é a mesma do problema

linear.● continua na fronteira do

conjunto de soluções viáveis.

● não é mais um extremo do conjunto de soluções viáveis, mas poderia ainda ocorrer em um ponto extremo.

Programação Não LinearSolução Gráfica

0

x2

1 2 3 4

4

2

6

0 x1

SoluçãoViável

(2;6)

1

2x ≤ 122

3x x + ≤2 18 1 2

s r x ≤ 4. .

x x≥ ≥0 01 2,

MaxZ= x x x x 126 9 182 131 12

2 22− + −

Programação Não LinearSolução Gráfica

x2

x1

(0;6)(2;6)

(0;0) (4;0)

(4;3)SoluçãoViável

●A função objetivo é uma equação quadrática.

Programação Não LinearSolução Gráfica

( )[ ] ( )[ ]( )[ ] ( )[ ]

Z= x x x x

Z x x x x

Z x x

Para x x

Para

126 9 182 13

912618

1318226

9126

912618

1318213

18226

441 637 9 7 13 7

9 7 13 7

1 12

2 22

2 2

12

1

2

22

2

2

1

2

2

2

1

2

2

2

− + −

−

−

= − −

+

− −

+

− − = − − − −

⇒ − + − Z = 907 171 =

Z = 857 ( )[ ] ( )[ ]( )[ ] ( )[ ]

⇒ − + −

⇒ − + −

221=

Z = 807 =

9 7 13 7

271 9 7 13 7

1

2

2

2

1

2

2

2

x x

Para x x

Max Z = x x x x = 857 126 9 182 131 12

2 22− + −

2

4

4

6

2 x 1

x2

SoluçãoViável

Z = 907

Z = 807Z = 857

Programação Não LinearSolução Gráfica

1

2x ≤ 122

3x x + ≤2 18 1 2

s r x ≤ 4. .

x x≥ ≥0 01 2,

Max Z= x x x x 54 9 78 131 12

2 22− + −

Programação Não LinearSolução Gráfica

x2

x1

(0;6)(2;6)

(0;0) (4;0)

(4;3)SoluçãoViável

●A função objetivo é uma equação quadrática

( )[ ] ( )[ ]( )[ ] ( )[ ]

Z= x x x x

Z x x x x

Z x x

Para x x

Para

54 9 78 13

95418

137826

9549

5418

137813

7826

81 117 9 3 13 3

9 3 13 3

1 12

2 22

2 2

12

1

2

22

2

2

1

2

2

2

1

2

2

2

− + −

−

−

= − −

+

− −

+

− − = − − − −

⇒ − + −

⇒

Z = 198 0 =

Z = 189 ( )[ ] ( )[ ]( )[ ] ( )[ ]

9 9 3 13 3

36 9 3 13 3

1

2

2

2

1

2

2

2

=

Z = 162 =

x x

Para x x

− + −

⇒ − + −

Programação Não LinearSolução Gráfica

Solução no interior doconjunto de soluçõesviáveis e não mais na fronteira do conjunto

4

2

6

2 4 x1

x2

SoluçãoViável

3

3

Z = 162Z = 189

Z = 198

222

211 1378954198 xxxx=ZMax −+−=

Programação Não LinearSolução Gráfica

Programação Não Linear●A solução ótima de um problema de programação não linear(NLP), diferentemente de um problema de LP, pode ser qualquer ponto do conjunto de soluções viáveis.

●Isso torna os problemas de NLP muito mais complexos, obrigando os algoritmos de solução a pesquisar todas as soluções viáveis.

Função Côncava e Função Convexa

Função Côncava e Função Convexa

• Uma função f(x) é convexa se um segmento de reta que une dois pontos dessa função está na superfície ou acima dela.

Função Côncava e Função Convexa

• Uma função f(x) é côncava se um segmento de reta que une dois pontos dessa função está na superfície ou abaixo dela.

Função Côncava e Função Convexa

• E se um segmento de reta une mais do que dois pontos de uma função?

Função Côncava e Função Convexa

• Na PNL sem restrições e uma função objetivo côncava, o máximo local é o máximo global.

• Na PNL sem restrições e uma função objetivo convexa, o mínimo local é o mínimo global.

• Isto também se verifica na presença de restrições, se a “região factível” for um conjunto convexo.

Função Côncava e Função Convexa

• Por meio do cálculo da segunda derivada de uma função f(x), representada por: f''(x) ou

pode-se determinar se esta é uma função convexa ou côncava em um conjunto conxexo S.

Função Côncava e Função Convexa

• Se d²f(x)/dx² >=0 (f''(x) >= 0), f(x) é uma função conexa em S

• Se d²f(x)/dx² >0 (f''(x) > 0 ), f(x) é uma função estritamente conexa em S

• Se d²f(x)/dx² <=0 (f''(x) <= 0), f(x) é uma função côncava em S

• Se d²f(x)/dx² < 0 ( f''(x) < 0 ), f(x) é uma função estritamente côncava em S

Função Côncava e Função Convexa

• Se f(x) é uma função linear e, consequantemente d²f(x)/dx² =0 ( f''(x)=0), f(x) é simultaneamente convexa e côncava em S

• Se d²f(x)/dx² (f''(x)) for positivo para alguns valores e negativo para outros, a função não é nem convexa nem côncava.

f''(x)=0

Exercícios• Determinar se as funções a seguir são convexas

(ou estritamente convexas), côncaas (u estritamente côncavas), convexas e côncavas simultaneamente ou nenhuma delas, em um conjunto convexo S.

• f(x)= 2x² + 4x• f(x)= -x² +6• f(x)= 8x + 3• f(x)=x³ + 4x - 10•

Funções convexas e côncavas com duas variáveis

• Para uma função f(x1, x

2) com 2 variáveis,

determina-se se ela é convexa ou côncava em um conjunto convexo S or meio da matriz Hessiana H que corresponde a uma matriz quadrada 2x2 das derivadas parciais de segunda ordem da função .

Funções convexas e côncavas com duas variáveis

• A classificação, se convexa (esritamente convexa) ou côncava (estritamente côncova), depende dos elementos da diagonal principal de H, além do cálculo do determinante.

Exemplo

Classificação das funções com duas variáveis a partir da matriz H

• Se f(x0 é linear e det (H)=0, a derivada parcial de segunda ordem em relação a x

1 = 0 e em relação a x

2 = 0, a função é

simultaneamente convexa e côncava em S.

• Se Det(H) <0 para alguns valores de x1 e x

2 pertencentes a S,

a função não é nem convexa nem côncava

Exemplo

• f(x1,x

2)=-2x

1²+4x

1x

2+ 3x

1-5x

2- 2x

2²

Exemplo

• f(x1,x

2)=-2x

1²+4x

1x

2+ 3x

1-5x

2- 2x

2²

-4 4= 4 -4

Exemplo• f(x

1,x

2)=-2x

1²+4x

1x

2+ 3x

1-5x

2- 2x

2²

-4 4= 4 -4

Verificar se todos os elementos da diagonal principal de H são todos negativos

det(H)= -4(-4) -(4)(4) =0

Função côncava

Exemplo• f(x

1,x

2)= - 3x

1² + 2x

2² + 2x

1x

2

Exemplo• f(x

1,x

2)= - 3x

1² + 2x

2² + 2x

1x

2

-6 2= 2 4

Exemplo• f(x

1,x

2)= - 3x

1² + 2x

2² + 2x

1x

2

-6 2= 2 4

Verificar se todos os elementos da diagonal principal de H são todos negativos

det(H)= -6(-4) -(2)(2) = -28

A função não é nem convexa nem côncava

Funções Convexas e Côncavas com Múltiplas Variáveis

Funções Convexas e Côncavas com Múltiplas Variáveis

• Para uma função f(x1, x

2, ..., x

n) com n

variáveias, determina-se se ela é convexa ou côncava por meio do cálculo dos determinantes dos menores principais da matriz Hessiana (Det 1x1, 2x2, ..., nxn de H)

Determinante dos menores principais

Determinante dos menores principais

Classificação das funções com mais de duas variávis a partir do cálculo dos determinantes dos

menores principais de H

• Se f(x) é linear e determinantes (H)=0, a função é simultaneamente convexa e côncava em S.

• Se nenhuma das condições foi atendida, a função não é nem convexa nem côncava

Exemplo• f(x

1,x

2,x

3)= 2x

1² + x

2² + 4x

3² - x

1x

2- x

1x

3– x

2x

3

Exemplo• f(x

1,x

2,x

3)= 2x

1² + x

2² + 4x

3² - x

1x

2- x

1x

3– x

2x

3

4 -1 -1= -1 2 -1 -1 -1 8

Exemplo• f(x

1,x

2,x

3)= 2x

1² + x

2² + 4x

3² - x

1x

2- x

1x

3– x

2x

3

4 -1 -1= -1 2 -1 -1 -1 8

Det1=4

Det2=(4)(2)-(-10(-1)=7

Det3=(64-1-1)-(2+2+4)=54

Estritamente convexa

Programação não linear Irrestrita

• Com uma única variável• Com múltiplas variáveis

Programação não linear Irrestrita

• Com uma única variável– Modelo escrito em termos da fnção objetivo– max ou min f(x)

• Seja f(x) uma função diferenciável ou derivável (que tem derivada). Para que uma determinada solução de f(x0 seja ótima (x=x), ela deve satisfazer a seguinte condição df(x*)/dx =0

• x* é també conhecido como ponto estacionário

Programação não linear Irrestrita

• Com uma única variável– para determinar se a solução ótima é um

ponto de máximo, mínimo ou inflexão (quando uma função côncava torna-se convexa ou vice-versa), calcula-se a derivada de primeira ordem, segunda ordem e assim por diante, até a ordem n seja uma constante com sinal positivo, negativo ou nulo.

Programação não linear Irrestrita

• Com uma única variável– Se n é par e f''(x*)>0, x* é um ponto de

mínimo;– Se n é par e f''(x*)<0, x* é um ponto de

máximo;– Se n é ímpar, x* é um ponto de inflexão.

Exemplo

Exemplo

Exemplo

f''(x) <> 0

Ótimo Global

Métodos de solução PNL irrestrita com uma única variável

• Método da bisseção– Método numérico bastante simples – Busca determinar a raiz da função não linear

(f(x)=0)– Convergência muito lenta

Métodos de solução PNL irrestrita com uma única variável

• Método de Newton (ou Newton-Raphson)– Método numérico – Determinar uma função iteração que acelere

a convergência na estimação das raízes de uma função não linear f(x).

– Geralmente mais rápido que o método da bisseção

– Para que a convergência seja satisfatória, o valor inicial estimado deve ser adequado (próximo da raiz)

Métodos de solução PNL irrestrita com múltiplas variáveis

• Métodos de Busca Direta– min ou max uma função com múltiplas

variáveis sem o uso da derivada da função – Convergem mais lentamente que os métodos

que usam derivadas– Método de busca aleatória, método de busca

seccionada, método de Hooke e Jeeves com busca linear, método de rosenbrock e método simplex.

Métodos de solução PNL irrestrita com múltiplas variáveis

• Métodos de Descida ou Métodos Indiretos– Utilizam a primeira e/ou a segunda derivada

da função objetivo para definir as direções de busca.

– Método de Newton, método do quase-Newton, método do Gradiente, método do gradiente conjugado

PNL com restrição

• Dentre os problemas de PNL com restrição, destacam-se: programação côncava, convexa, quadrática e separável

• Multiplicadores de Lagrange• Condições de Karush-Kuhn-Tucker

Programação Dinâmica

Introdução

• Paradigmas de projeto de algoritmos:– Tentativa e erro– Divisão e conquista– Algoritmos gulosos– Algoritmos aproximados– Recursividade– Programação dinâmica

Introdução

• Paradigmas de projeto de algoritmos:– Tentativa e erro (ou busca completa – backtracking)

– Testar de maneira exaustiva todas as possíveis soluções de um determinado problema, até que a solução desejada seja obtida.

Introdução

• Paradigmas de projeto de algoritmos:– Quando não for possível percorrer toda a

árvore de soluções em razão da complexidade do problema, uma alternativa é utilizar algoritmos aproximados ou metaheurísticas.

– Objetivo: encontrar soluções de boa qualidade, muitas vezes, próximas da ótima, com esforço computacional muito menor.

Introdução

• Paradigmas de projeto de algoritmos:– Algoritmos Gulosos (ou míopes) – Escolhem, em cada passo, a melhor decisão

local. Uma vez feitas uma decisão, não tem como ser modificada, independente da qualidade da solução.

Introdução

• Paradigmas de projeto de algoritmos:– Divisão e conquista busca dividir o problema

principal em subproblemas menores e independentes.

– Resolve-se o problema para os subproblemas menores, e as soluções dos subproblemas são combinadas até que se obtenha a solução ótima.

Introdução

• Paradigmas de projeto de algoritmos:– Considerando um determinado procedimento

constituído de diversos estágios. A recursividade ocorre quando um dos passos chama novamente a execução do procedimento, de forma que o processo de repetição acontece a partir desse passo.

–  é a definição de uma subrotina (função ou método) que pode invocar a si mesma.

Introdução

• Paradigmas de projeto de algoritmos:– A programação dinâmica é uma técnica

bastante usada para resolver diversos problemas de otimização, incluindo modelos probabilísticos, problemas lineares ou não lineares, com variáveis discretas ou contínuas.

Programação Dinâmica• Baseada no princípio da otimalidade.• Busca dividir o problema principal em subproblemas

utilizando uma equação recursiva.• Os subproblemas são resolvidos uma única vez e seus

resultados são armazenados em uma tabela, consultando-a cada vez que o subproblema for requerido.

• Em cada passo, considera-se somente as soluções ótimas.

• Diferente da estratégia de divisão e conquista, os subproblemas não são independentes e compartilham informações entre si.

Características de um Problema de Programação Dinâmica

• Estágios: – o problema é dividido em diversos estágios e

um plano de decisões é estabelecido para cada estágio.

Características de um Problema de Programação Dinâmica

• Estados: – cada estágio está associado a um

determinado número de estados. – os estados representam as diversas

condições possíveis que um sistema pode apresentar em um determinado estágio.

– são as informações contidas em cada estágio, necessárias para a tomada de decisões.

Características de um Problema de Programação Dinâmica

• Decisões:– Em cada estágio, a partir das informações

contidas inicialmente, escolhem-se as melhores decisões. As decisões buscam transformar o estado atual em outro estado associado ao estágio seguinte.

Características de um Problema de Programação Dinâmica

• Princípio de Otimalidade de Bellman:– Dado um estado atual, a decisão ótima para cada

estágio seguinte depende somente do estado atual, não importando o que aconteceu anteriormente.

– Exemplo: suponha que o caminho mais curto entre São Paulo e Ubatuba seja conhecido e esse caminho passa necessariamente por São José dos Campos. Consequentemente, o caminho mais curto entre São Paul e Ubatuba deve incluir o caminho mais curto entre São José dos Campos e Ubatuba.

Características de um Problema de Programação Dinâmica

• Processo de solução do tipo backward ou forward:– backward - inicia pelo último estado até

encontrar a solução ótima do estado inicial.– forward –– os dois procedimentos chegam á mesma

solução– Backward – mais eficiente

computacionalmente

Características de um Problema de Programação Dinâmica

• Recursividade:• Utiliza uma equação recursiva ou de

recorrência que identifica a solução ótima para cada estado de um estágio t qualquer, dada a solução ótima para cada estado de estágio seguinte t+1 (backward), ou dada a solução ótima para cada estado do estágio anterior t-1 (forward)

Estado: Um estado é uma configuração do sistema, e é identificado por um rótulo que indica suas propriedades. No problema apresentado na figura, um estado é uma cidade

Estágio: Programação dinâmica diz respeito a sistemas que evoluem de um estado para outro. Um estágio é um passo singular, e corresponde à transição do sistema de um estado para o próximo adjacente. Na figura, o movimento do viajante, de uma cidade para a próxima, corresponde ao estágio. Cada caminho de A para J tem quatro estágios.

Ação: Em cada estado existe um conjunto de ações viáveis, das quais uma deverá ser escolhida e executada. No exemplo da figura 2.1, no estado C existem três ações viáveis: ir para a cidade E, ir para a cidade F ou ir para a cidade G. Resolver o problema de programação dinâmica significa, dado um objetivo, achar a melhor seqüência de ações

Plano: é um conjunto de ações, no qual para cada estado é especificada uma ação. Um plano ótimo é o melhor conjunto de ações considerando o objetivo fixado.

Retorno: é algo que o sistema gera, sobre um estágio ou processo. No problema da figura acima, o retorno é a distância percorrida entre uma cidade e a próxima. O retorno é usualmente, algo do tipo: lucro, custo, distância, consumo de recursos, etc.

Valor do Estado: é uma função dos retornos gerados, quando o sistema evolui de um estado inicial para um estado final, através de um plano dado. No caso do problema da viagem, o valor do estado, para um determinado plano, corresponde à distância desta cidade até a cidade terminal.

O valor de um estado sob um plano ótimo é o valor ótimo.