Saltar para o conteúdo

Programação não linear

Origem: Wikipédia, a enciclopédia livre.

Em matemática, programação não linear é o processo de resolução de um problema de otimização definido por um sistema de equações e desigualdades, coletivamente denominadas restrições, através de um conjunto de desconhecido variáveis reais, juntamente com uma função objetivo a ser maximizada ou minimizada, onde algumas das restrições ou a função objetivo são não lineares.[1] É um sub-campo da otimização matemática que lida com problemas que não são lineares.

Seja n, mp números inteiros positivos. Seja X um subconjunto de Rn e f, gi e hj funções reais em X para cada i em {1, ..., m} e cada j em {1, ..., p}, com pelo menos uma dessas funções, f, ge hj sendo não linear.

Um problema de minimização não linear é um problema de otimização da forma:[http://www.ime.unicamp.br/~friedlan/livro.pdf]

Um problema não linear de maximização é definido de forma análoga.

Possíveis tipos de conjunto de restrições

[editar | editar código-fonte]

Existem várias possibilidades para a natureza do conjunto de restrições, também conhecido como conjunto viável região viável.

Um problema inviável é aquele para qual nenhum conjunto de valores para a escolha das variáveis satisfaz todas as restrições. Isto é, as restrições são mutuamente contraditórias, e não existe uma solução; o conjunto viável é o conjunto vazio.

Um problema viável é aquele para o qual existe pelo menos um conjunto de valores para a escolha das variáveis que satisfaz todas as restrições.

Um problema unbounded é viável para o qual a função objetivo pode ser feita para ser melhor do que qualquer valor finito. Assim, não há nenhuma solução ótima, porque há sempre uma solução viável que dá um melhor valor da função objetivo que qualquer solução proposta.

Métodos para resolver o problema

[editar | editar código-fonte]

Se a função objetivo f é linear e o espaço de restrições é um polítopo, o problema é de programação linear, que pode ser resolvido utilizando-se conhecidas técnicas de programação linear, tais como o método simplex.

Se a função objetivo é côncava (problema de maximização), ou convexa (problema de minimização) e o conjunto de restrições é convexo, então o problema é chamado convexo e métodos gerais de otimização convexa podem ser usados na maioria dos casos.

Se a função objetivo é quadrática e as restrições são do tipo linear, técnicas de programação quadrática são utilizadas.[http://www.ime.unicamp.br/~friedlan/livro.pdf 34]

Se a função objetivo é a razão de uma função côncava e uma função convexa (no caso de maximização) e as restrições são convexas, então o problema pode ser transformado em um problema de otimização convexa usando técnicas de programação fracional.

Vários métodos estão disponíveis para a resolução de problemas não convexos. Uma abordagem é a utilização de formulações especiais de problemas de programação linear. Outro método envolve o uso de técnicas branch and bound, onde o programa é dividido em subclasses para ser resolvido com aproximações convexas (problema de minimização) ou lineares que formam um limite inferior sobre o custo global dentro da subdivisão. Com as divisões posteriores, em algum ponto uma solução real será obtida e terá o custo igual ao melhor limite inferior obtido para qualquer uma das soluções aproximadas. Esta solução é ótima, embora possivelmente não seja única. O algoritmo também pode ser interrompido precocemente, com a certeza de que a melhor solução possível está dentro de uma tolerância a partir do melhor ponto encontrado; tais pontos são chamados de ε-ótimos. Encerrando em pontos ε-ótimos é usualmente necessário para garantir encerramento em tempo finito. Isto é especialmente útil para problemas grandes e difíceis e problemas com custos incertos ou valores onde a incerteza pode ser estimada com uma estimação ideal de pontos é normalmente necessário para garantir finito de terminação. Isto é especialmente útil para grandes problemas difíceis e problemas com o incerto custos ou valores, em que a incerteza pode ser estimada com uma fiabilidade apropriada.

Em diferenciabilidade e qualificação de restrições, as condições Karush-Kuhn-Tucker fornecem condições necessárias para que uma solução seja ótima. Sob convexidade, estas condições também são suficientes. Se algumas das funções são não diferenciáveis, versões subdiferenciais das condições Krush-Kuhn-Tucker estão disponíveis.[2]

Exemplo bidimensional

[editar | editar código-fonte]
A tangência da linha com espaço de restrições representa a solução. A linha é a melhor linha de contorno realizável (locus com um determinado valor da função objetivo).

Um problema simples pode ser definido pelas restrições

x1 ≥ 0
x2 ≥ 0
x12 + x22 ≥ 1
x12 + x22 ≤ 2

com uma função objetivo a ser maximizada

f(x) = x1 + x2

onde x = (x1, x2).

Exemplo tridimensional

[editar | editar código-fonte]
A tangência da superfície superior com o espaço de restrições no centro representa a solução.

Outro problema simples pode ser definido pelas restrições

x12x22 + x32 ≤ 2
x12 + x22 + x32 ≤ 10

com uma função objetivo a ser maximizada

f(x) = x1x2 + x2x3

onde x = (x1, x2, x3).

Referências

  1. Bertsekas, Dimitri P. Nonlinear Programing. [S.l.: s.n.] ISBN 1-886529-00-0 
  2. Ruszczyński, Andrzej. Nonlinear Optimization. [S.l.: s.n.] ISBN 978-0691119151. MR 2199043 

Leitura complementar

[editar | editar código-fonte]

Ligações externas

[editar | editar código-fonte]