O programaçã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, então 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 só se aplica quando a função objetivo e as restrições são todas combinações lineares das variáveis do problema.
Índice do artigo
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 o limite da região de solução.
3.- Cálculo do gradiente para explorar extremos da função objetivo.
4.- O método de degraus descendentes, para encontrar os pontos de gradiente nulos.
5.- Método modificado dos multiplicadores de Lagrange (com a condição de Karush-Kuhn-Tucker).
Um exemplo de solução com o método gráfico é o que pode ser visto na figura 2:
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)dois + 3 (E - 3)dois
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.
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 dá origem a 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..
Encontre a solução (x, y) que torna a função f (x, y) = xdois + 2 edois ser máximo na região g (x, y) = xdois + Ydois - 1 = 0.
É 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) = xdois + 2 edois - λ (xdois + Ydois - 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, λ.
-Defina cada derivada para zero.
Aqui está a sequência dessas operações:
Uma possível solução deste 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 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 descobrir qual ou quais dessas soluções maximizam a função objetivo, procedemos para substituir em f (x, y):
S1: f (1, 0) = 1dois + 2.0dois = 1
S2: f (-1, 0) = (-1)dois + 2.0dois = 1
S3: f (0, 1) = 0dois + 2,1dois = 2
S4: f (0, -1) = 0dois + vinte e um)dois = 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.
Encontre soluções (x, y) para a função objetivo:
f (x, y) = xdois + 2 edois
Let ser máximo na região g (x, y) = xdois + Ydois - 1 ≤ 0.
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 como única solução (x = 0, y = 0) que pertence ao círculo g (x, y) ≤ 0.
Substituir este valor na função f resulta em:
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 na fronteira da região de solução, para os valores (x = 0, y = 1) e (x = 0, y = -1 ).
Ainda sem comentários