Programação não linear: métodos e exercícios

Programação não linear: métodos e exercícios

programação não linear  é o processo de otimizar uma função que depende de várias variáveis ​​independentes, que por sua vez estão sujeitas a restrições.

Se uma ou mais restrições, ou se a função a ser maximizada ou minimizada (chamada de função objetivo ), não for expressa como uma combinação linear das variáveis, você terá um problema de programação não linear.

E, portanto, os procedimentos e métodos de programação linear não podem ser usados.

Por exemplo, o conhecido método Simplex não pode ser usado , o que só se aplica quando a função objetivo e as restrições são todas uma combinação linear das variáveis ​​no problema.

Métodos de programação linear

Para problemas de programação não linear, os principais métodos a serem utilizados são: 

1.- Métodos gráficos.

2.- Multiplicadores de Lagrange para explorar a fronteira da região da solução.

3.- Cálculo do gradiente para explorar extremos da função objetivo.

4.- O método de etapas descendentes, para encontrar os pontos de gradiente nulo.

5.- Método modificado dos multiplicadores Lagrange (com a condição Karush-Kuhn-Tucker).

Exemplo de solução com método gráfico

Um exemplo de solução com o método gráfico é o que pode ser visto na figura 2:

Exercícios

– Exercício 1 (método gráfico)

O lucro G de uma determinada empresa depende da quantidade vendida do produto X e da quantidade vendida do produto Y, além disso, o lucro é determinado pela seguinte fórmula:

G = 2 (X – 2) 2 + 3 (Y – 3) 2

Sabe-se que os valores X e Y têm as seguintes restrições:

X≥0; Y≥0 e X + Y ≤ 7

Determine os valores de X e Y que produzem o ganho máximo.

Solução 

Nesse problema, a função objetivo é não linear, enquanto as desigualdades que definem as restrições são. Este é um problema de programação não linear .

Relacionado:  Transformação de Fourier: propriedades, aplicativos, exemplos

Para a solução deste problema, o método gráfico será escolhido.

Primeiro, a região da solução será determinada, o que é dado pelas restrições.

Como X≥0; Y≥0, a solução deve ser encontrada no primeiro quadrante do plano XY, mas como também deve ser cumprido que X + Y ≤ 7, a solução está no meio plano inferior da linha X + Y = 7.

A região da solução é a interseção do primeiro quadrante com o meio plano inferior da linha, o que dá origem a uma região triangular onde a solução é encontrada. É o mesmo que indicado na figura 1.

Por outro lado, o ganho G também pode ser representado no plano cartesiano, pois sua equação é a de uma elipse com um centro (2,3).

A elipse é mostrada na figura 1 para vários valores de G. Quanto maior o valor de G, maior o ganho.

Existem soluções que pertencem à região, mas não fornecem o valor máximo G, enquanto outras, como G = 92,4, estão fora da zona verde, ou seja, da zona de solução.

Então, o valor máximo de G, de modo que X e Y pertencem à região da solução, corresponde a: 

G = 77 (ganho máximo), dado para X = 7 e Y = 0. 

Curiosamente, o lucro máximo ocorre quando a quantidade de vendas do produto Y é nula, enquanto a quantidade do produto X atinge o maior valor possível.

– Exercício 2 (método analítico: multiplicadores de Lagrange) 

Encontre a solução (x, y) que torna a função f (x, y) = x 2 + 2y 2 no máximo na região g (x, y) = x 2 + y 2 – 1 = 0.

Solução

Este é claramente um problema de programação não linear, pois a função objetivo f (x, y) e a restrição g (x, y) = 0 não são uma combinação linear das variáveis ​​x e y.

O método multiplicadores Lagrange será usado, o que primeiro requer a definição da função Lagrange L (x, y, λ):

Relacionado:  Função overjective: definição, propriedades, exemplos

L (x, y, λ) = f (x, y) – λ g (x, y)  = x 2 + 2y 2 – λ (x 2 + y 2 – 1) 

Onde λ é um parâmetro chamado multiplicador de Lagrange .

Para determinar os valores extremos da função objetivo f, na região da solução dada pela restrição g (x, y) = 0, siga estas etapas:

-Encontre as derivadas parciais da função Lagrange L, com relação a x, y, λ.

– Zere cada derivada para zero.

Aqui está a sequência dessas operações:

  1. ∂L / ∂x = 2x – 2λx = 0
  2. ∂L / =y = 4y – 2λy = 0
  3. ∂L / ∂λ = – (x 2 + y 2 – 1) = 0
Possíveis soluções do sistema

Uma solução possível desse sistema é λ = 1, para que a primeira equação seja satisfeita; nesse caso, y = 0, para que a segunda seja cumprida.

Esta solução implica que x = 1 ou x = -1 para que a terceira equação seja satisfeita. Dessa maneira, duas soluções S1 e S2 foram obtidas:

S1: (x = 1, y = 0)

S2: (x = -1, y = 0).

A outra alternativa é que λ = 2 para que a segunda equação seja satisfeita, independentemente do valor y.

Nesse caso, a única maneira de satisfazer a primeira equação é que x = 0. Considerando a terceira equação, existem apenas duas soluções possíveis, que chamaremos de S3 e S4:

S3: (x = 0, y = 1)

S4: (x = 0, y = -1)

Para descobrir qual ou quais dessas soluções maximizam a função objetivo, procedemos à substituição em f (x, y):

S1: f (1, 0) = 1 2 + 2,0 2 = 1

S2: f (-1, 0) = (-1) 2 + 2,0 2 = 1

S3: f (0, 1) = 0 2 + 2,1 2 = 2

S4: f (0, -1) = 0 2 + 2 (-1) 2 = 2

Concluímos que as soluções que maximizam f, quando x e y pertencem ao círculo g (x, y) = 0 são S3 e S4.

Os pares de valores (x = 0, y = 1) e (x = 0, y = -1) maximizam f (x, y) na região da solução g (x, y) = 0.

Relacionado:  Medidas de tendência central para dados agrupados

– Exercício 3 (gradiente nulo)

Encontre soluções (x, y) para que a função objetivo:

f (x, y) = x 2 + 2 y 2

Seja o máximo na região g (x, y) = x 2 + y 2 – 1 ≤ 0.

Solução

Este exercício é semelhante ao exercício 2, mas a região da solução (ou restrição) se estende à região interior do círculo g (x, y) = 0, ou seja, ao círculo g (x, y) ≤ 0. Isso inclui à circunferência e sua região interna.

A solução na fronteira já foi determinada no exercício 2, mas a região interior ainda precisa ser explorada.

Para isso, o gradiente da função f (x, y) deve ser calculado e igual a zero, para encontrar valores extremos na região da solução. Isso é equivalente ao cálculo das derivadas parciais de f em relação a xey respectivamente e igual a zero:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Este sistema de equações tem a única solução (x = 0, y = 0) que pertence ao círculo g (x, y) ≤ 0.

Substituindo esse valor na função f resulta:

f (0, 0) = 0

Em conclusão, o valor máximo que a função assume na região da solução é 2 e ocorre no limite da região da solução, para os valores (x = 0, y = 1) e (x = 0, y = -1) .

 Referências

  1. Avriel, M. 2003. Programação não linear. Dover Publishing.
  2. Bazaraa. 1979. Programação não linear. John Wiley & Sons.
  3. Bertsekas, D. 1999. Programação Não Linear: 2ª edição. Athena Scientific.
  4. Nocedal, J. 1999. Otimização Numérica. Springer-Verlag.
  5. Wikipedia. Programação não linear. Recuperado de: es.wikipedia.com

Deixe um comentário

Este site usa cookies para lhe proporcionar a melhor experiência de usuário. política de cookies, clique no link para obter mais informações.

ACEPTAR
Aviso de cookies