A 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 .
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, λ):
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:
- ∂L / ∂x = 2x – 2λx = 0
- ∂L / =y = 4y – 2λy = 0
- ∂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.
– 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
- Avriel, M. 2003. Programação não linear. Dover Publishing.
- Bazaraa. 1979. Programação não linear. John Wiley & Sons.
- Bertsekas, D. 1999. Programação Não Linear: 2ª edição. Athena Scientific.
- Nocedal, J. 1999. Otimização Numérica. Springer-Verlag.
- Wikipedia. Programação não linear. Recuperado de: es.wikipedia.com