Métodos e exercícios de programação não lineares

O 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 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 há um problema de programação não linear.

figura 1. Problema de programação não linear (NLP). em que G é a função (não linear) a 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 método bem conhecido não pode ser usado Simplex, que se aplica apenas quando a função objetiva e as restrições são todas combinação linear das variáveis ​​do problema.

[TOC]

Métodos de programação linear

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

1.- Métodos gráficos.

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

3.- Cálculo do gradiente para explorar as extremidades da função objetiva.

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

5.- Método modificado de 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 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 ganho g de uma determinada empresa depende da quantidade vendida do produto X e da quantidade vendida do produto e, além disso, o ganho é determinado pela seguinte fórmula:

Pode servir a você: Binomial conjugado: como é resolvido, exemplos, exercícios

G = 2 (x - 2)² + 3 (e - 3)²

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

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

Determinar os valores de x e y que produzem o ganho máximo.

Figura 3. O ganho da empresa pode ser modelado matematicamente para encontrar o ganho máximo da 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 são. É um problema de Programação não linear.

Para a solução desse 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 pesquisar no primeiro quadrante do plano XY, mas, além disso, deve -se cumprir que x + y ≤ 7, a solução está no semiplano inferior da linha x + y = 7.

A região da solução é a interseção do primeiro quadrante com o semiplano inferior da linha, que dá origem a uma região triangular onde a solução está localizada. É o mesmo indicado na Figura 1.

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

A elipse é mostrada na Figura 1 para vários valores de G. Um valor mais alto de G, maior ganho.

Existem soluções que pertencem à região, mas não dão o valor máximo 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 pertence à região de solução corresponde a: 

Pode servir a você: probabilidade teórica: como divulgá -lo, exemplos, exercícios

G = 77 (ganho máximo), que ocorre para x = 7 e y = 0. 

Curiosamente, o ganho máximo ocorre quando a quantidade de vendas de produtos e é nulo, enquanto a quantidade de 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² + 2 e² seja 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 a função objetiva 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 de multiplicadores de Lagrange será usado, que primeiro exige definir a função de Lagrange L (x, y, λ):

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

Onde λ é um parâmetro chamado Lagrange multiplicador.

Para determinar os valores extremos da função objetiva f, na região da solução dada pela restrição g (x, y) = 0, essas etapas são seguidas:

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

-Zero cada derivado.

Aqui a sequência dessas operações:

1. ∂l/∂x = 2x - 2λx = 0
2. ∂l/∂y = 4y - 2λy = 0
3. ∂l/∂λ = -(x² + e² - 1) = 0

Possíveis soluções do sistema

Uma possível solução deste sistema é λ = 1 para satisfazer a primeira equação, nesse caso y = 0 para atender ao segundo.

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

S1: (x = 1, y = 0)

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

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

Pode servir a você: Limite de Fermat: O que consiste e exercícios resolvidos

Nesse caso, a única maneira de a primeira equação ser satisfeita é 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 saber qual ou quais dessas soluções maximizam a função objetiva, prossiga 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² + vinte e um)² = 2

Concluímos que as soluções que maximizam f, quando x e y pertencem à circunferência g (x, y) = 0 são s3 e s4.

Os pares de valores (x = 0, y = 1) y (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 a função objetiva:

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

Seja 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 à região interior da circunferência g (x, y) = 0, ou seja, para o círculo g (x, y) ≤ 0. Isso inclui a circunferência e sua região interna.

A solução de fronteira já estava determinada no Exercício 2, mas é necessário explorar a região interna.

Para fazer isso, o gradiente da função f (x, y) deve ser calculado e igual a zero, para procurar valores extremos na região da solução. Isso é equivalente a calcular os derivados parciais de F em relação a X e respectivamente e equalizar zero:

∂f/∂x = 2 x = 0

∂f/∂y = 4 y = 0

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

Substituindo esse valor na função f Resultados:

f (0, 0) = 0

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

 Referências

1. Avriel, m. 2003. Programação não linear. Publicação Dover.
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: é.Wikipedia.com