PROGRAMAÇÃO NÃO LINEAR: MÉTODOS E EXERCÍCIOS - MATEMÁTICAS - 2025

A programação não linear é o processo de otimização de uma função que depende de diversas 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 a ser maximizada ou minimizada (chamada de função objetivo), não for expressa como uma combinação linear das variáveis, então você tem um problema de programação não linear.

Figura 1. Problema de programação não linear (PNL). onde G é a função (não linear) para otimizar na região verde, determinada pelas restrições. Fonte: F. Zapata.

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 combinações lineares 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 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.- Método de descida por degraus, 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:

Figura 2. Exemplo de um problema não linear com restrições não lineares e sua solução gráfica. Fonte: F. Zapata.

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.

Figura 3. O lucro de uma empresa pode ser modelado matematicamente para encontrar o lucro máximo usando programação não linear. Fonte: Pixabay.

Solução

Neste problema, a função objetivo é não linear, enquanto as desigualdades que definem as restrições o são. Este é 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á no meio plano inferior 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 máximo de G, 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 ² + 2y ² máxima na região g (x, y) = x ² + y ² - 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 Lagrange L (x, y, λ):

L (x, y, λ) = f (x, y) - λ g (x, y) = x ² + 2y ² - λ (x ² + y ² - 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 Lagrange L, em relação a x, y, λ.

-Equalize cada derivada a 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 ² + y ² - 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 é para 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 y ²

Let ser máximo na região g (x, y) = x ² + y ² - 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, ao 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 defini-lo 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

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