Programação não linear: métodos e exercícios - Ciência - 2023

Contente

oprogramação não linear é o processo de otimização de 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 das restrições, ou se a função para maximizar ou minimizar (chamado Função objetiva), não é expresso como uma combinação linear das variáveis, portanto, temos 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 método bem conhecido não pode ser usado Simplex, que se aplica apenas quando a função objetivo e as restrições são todas combinações lineares das variáveis do problema.

Métodos de programação linear

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

1.- Métodos gráficos.

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

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

4.- O método dos degraus descendentes, para encontrar os pontos nulos do gradiente.

5.- Método modificado dos multiplicadores de Lagrange (com a condição de 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)² + 3 (Y - 3)²

Sabe-se que as quantidades 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

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

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

Primeiro, a região de solução será determinada, que é dada 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 verdade que X + Y ≤ 7, a solução está na metade inferior do plano da linha X + Y = 7.

A região da solução é a intersecção do primeiro quadrante com o meio plano inferior da linha, o que resulta em uma região triangular onde a solução é encontrada. É o mesmo 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 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 dão o valor G máximo, enquanto outras, como G = 92,4, estão fora da zona verde, ou seja, a zona de solução.

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

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

Curiosamente, o lucro máximo ocorre quando a quantidade de vendas do produto Y é zero, enquanto a quantidade do produto X atinge seu 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² + 2a² ser máximo na região g (x, y) = x² + e² – 1 = 0.

Solução

É claramente um problema de programação não linear, uma vez que tanto 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 dos multiplicadores de Lagrange será usado, o que primeiro requer a definição da função de Lagrange L (x, y, λ):

L (x, y, λ) = f (x, y) - λ g (x, y) = x² + 2a² - λ (x² + e² – 1)

Onde λ é um parâmetro denominado Multiplicador de Lagrange.

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

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

-Equalize cada derivada a zero.

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

∂L / ∂x = 2x - 2λx = 0
∂L / ∂y = 4y - 2λy = 0
∂L / ∂λ = - (x² + e² – 1) = 0

Possíveis soluções de sistema

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

Esta solução implica que x = 1 ou x = -1 para a terceira equação a ser satisfeita. Desta forma, 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 de y.

Nesse caso, a única maneira de a primeira equação ser satisfeita é 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 saber qual ou quais dessas soluções maximizam a função objetivo, procedemos para substituir em f (x, y):

S1: f (1, 0) = 1² + 2.0² = 1

S2: f (-1, 0) = (-1)² + 2.0² = 1

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

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

Concluímos que as soluções que maximizam f, quando xey pertencem à circunferência 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 de solução g (x, y) = 0.

- Exercício 3 (gradiente nulo)

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

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

Let ser máximo na região g (x, y) = x² + e² – 1 ≤ 0.

Solução

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

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

Para fazer isso, o gradiente da função f (x, y) deve ser calculado e definido como zero, para encontrar valores extremos na região de solução. Isso é equivalente a calcular as derivadas parciais de f em relação a xey respectivamente e definir 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 este 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 de solução é 2 e ocorre no limite da região de solução, para os valores (x = 0, y = 1) e (x = 0, y = -1) .

Referências

Avriel, M. 2003. Nonlinear Programing. Publicação de Dover.
Bazaraa. 1979. Nonlinear Programing. John Wiley & Sons.
Bertsekas, D. 1999. Nonlinear Programing: 2nd edition. Athena Scientific.
Nocedal, J. 1999. Otimização Numérica. Springer-Verlag.
Wikipedia. Programação não linear. Recuperado de: es.wikipedia.com