Origem: Wikipédia, a enciclopédia livre. Show
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. Definição[editar | editar código-fonte]Seja n, m e p 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, gi e 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] Exemplos[editar | editar código-fonte]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 ≥ 0x2 ≥ 0x12 + x22 ≥ 1x12 + x22 ≤ 2com uma função objetivo a ser maximizada f(x) = x1 + x2onde 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 x12 − x22 + x32 ≤ 2x12 + x22 + x32 ≤ 10com uma função objetivo a ser maximizada f(x) = x1x2 + x2x3onde x = (x1, x2, x3). Veja também[editar | editar código-fonte]
Referências
Leitura complementar[editar | editar código-fonte]
Ligações externas[editar | editar código-fonte]
Como resolver programação não linear?Métodos para resolver o problema
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.
Quais são os principais métodos de resolução de um problema de Programação Linear?O presente trabalho mostra algumas aplicações da Programação Linear e como ela pode ser usada para resolver problemas. Abordaremos três métodos de resolução de problemas de Programação Linear: 1) o método de Resolução Gráfica; 2) o Método Algébrico; e 3) Método Computacional (usaremos o software Lindo 6.1 e o Excel).
Qual ferramenta pode ser usada para resolver problemas de Programação Linear visto em aula?O GeoGebra é um software de matemática dinâmica para todos os níveis de ensino que reúne Geometria, Álgebra, Gráficos, Planilha de Cálculo, Probabi- lidade, Estatística e Cálculos Simbólicos em um único programa. O LINGO foi desenvolvido para resolver problemas de Programação Linear.
É uma programação baseada em funções lineares utilizada em problemas em que não há restrições?linear (PL) é uma técnica de maximização aplicada em sistemas de equações lineares. B) Trata-se de uma aplicação não matemática utilizada por profissionais para problemas relativos à produção, por exemplo C) É uma programação baseada em funções lineares utilizada em problemas em que não há restrições.
|