Disciplina: Programação Não-Linear

PESQUISA OPERAIONAL

Veja a seguir os seguintes conteúdos já disponíveis. Para tomar conhecimento da lista completa dos conteúdos vistos nesta disciplina, clique no ícone "PROGRAMA" acima. OBSERVAÇÃO: Alguns dos assuntos estão divididos em partes as quais podem ser acessadas clicando nos links abaixo.

1) Ementa e/ou Programa da Disciplina Programção Não-Linear

 

2) Introdução

 

3) Métodos de Busca 

    a) HOOKJEEVS (Passo Discreto); e 

    b) Método das BARREIRAS.

 

4) Programação Quadrática

Programação Não-Linear

Em Matemática Aplicada e/ou Pesquisa Operacional, Programação Não-Linear (PNL - Nonlinear Programming), direntemente de Programação Linear, é o processo de resolução de um Problema de Otimização definido por um sistema de igualdades e desigualdades, - geralmente, um Sistema de Equações coletivamente denominado de Restrições sobre um conjunto de variáveis reais cujos valores são desconhecidos, juntamente com uma Função Objetivo a ser maximizada ou minimizada, onde algumas das restrições ou a função objetivo é não-linear. [1] É a Sub-Área da Matemática Aplicada denominada Otimização Matemática que lida com Problemas que Não são Lineares.

Índice

  • 1 Applicabilidade

  • 2 O Problema Geral de Programação Não-Linear (NLP)

  • 3 Possíveis tipos de Conjunto de Restrições

  • 4 Método de Resolução do Problema

  • 5 Exemplos

    • 5.1 2- Exemplo Bi-Dimensional (a Função Objetivo e Restrições envolvem duas Variáveis)

    • 5.1 3- Exemplo Tri-Dimensional (a Função Objetivo e Restrições envolvem três Variáveis)

  • 6 Applicações

  • 7 Veja Também

  • 8 Referências

  • 9 Leitura Adicional

  • 10 Outros Links

Aplicabilidade

Um problema não-convexo típico é a de otimizar os custos de transporte pela escolha de um conjunto de métodos de transporte – os modais, com a rede de transporte envolvendo  vários arcos os quais conectam os nós desta rede  e adicionado a este problema se apresentam restrições de capacidade. Um exemplo seria o transporte de produtos de petróleo dada uma seleção ou combinação de gasodutos, ou escolha de modal ônibus ou automóvel transportando passageiros entre pontos da rede em uma cidade. Devido à peculiaridade de cada problema as Funções Objetivos podem ter pontos de Descontinuidades - isto significa que estas Funções não possuem Derivadas nestes ponto e assim, estes problemas sendo tratados de maneira diferente dos que a Função Objetivo é Diferenciável.

 

Prática da engenharia moderna envolve muito otimização numérica – resolvidos por através dos Métodos dentro da Área denominada de Cálculo Numérico em Computador. Com certas exceções mas importantes como em Circuitos Eletrônicos – Cálculo da Corrente Elétrica em um Circuito que envolve a Resolução de um Sistema de Equações Lineares, problemas de engenharia são, em geral não-lineares, e eles são geralmente muito complexos.

 

Na ciência experimental, uma análise de dados simples (tal como um encaixe com um espectro de soma dos picos de localização conhecida e forma, mas magnitude desconhecida) pode ser feito com métodos lineares, mas, em geral, estes problemas, também, são não-linear.

Normalmente, a pessoa tem um modelo teórico do sistema em estudo com parâmetros e variáveis ​​no mesmo ou um modelo experimental (experimentos) que também podem ter parâmetros desconhecidos. Um tenta encontrar um melhor ajuste numericamente – Ajustar o conjunto de dados a uma determinada Função: Interpolação Polinomial, Modelos de Regressão em Estatística e etc. Neste caso, muitas vezes se deseja certa precisão no resultado, assim como o melhor ajuste propriamente dito. 

O Problema Geral de Programação Não-Linear (NLP - nonlinear programming)

O problema pode ser enunciado com abaixo:

 

                  , para Maximixar a Função f;

 

ou

 

                  , para Minimizar a Função f;

 

onde

 

 

                                      , onde x = (x1, x2,...,xn)

 

Sujeito a (Restrição ou Restrições!)

 

 

 

 

OBSERVAÇÃO: hi são Restrições que envolvem uma ou mais equações com igualdade (es);

                     gi são Restrições que envolvem uma ou mais equações com desigualdade (es).

Possíveis Tipos de Restrições

Existem várias possibilidades para a natureza do conjunto de Restrições, também conhecido como o Conjunto Viável ou Região Viável.

 

Um Problema Inviável (que não possui Solução) é aquele para o qual nenhum conjunto de valores para as variáveis de decisão satisfaz todas as restrições. Isto é, as restrições são mutuamente contraditórias, e não existe solução.

 

Um Problema Viável (que possui Solução) é aquele para o qual existe pelo menos um conjunto de valores para as variáveis de decisão que satisfaçam todas as restrições.

 

Um Problema Ilimitada (que possui infinitas Soluções) é um Problema Viável para o qual a Função Objetivo pode ter valor que ultrapassa qualquer valor finito dado. Assim, não há solução ideal, porque há sempre uma solução viável que dá um valor para a função objetivo melhor do que qualquer dada solução proposta anteriormente.

Métodos para Resolver o Problema de NLP

Se a Função Objetivo f é Linear e a Região definida pelas Restrições é um Polígono, o problema é um Problema de Programação Linear o qual pode ser resolvido usando o bem conhecido Algoritmo Simplex se o número de variáveis é significativamente grande (problemas de Grande Porte) – se o problema tem duas variáveis, então ele pode ser resolvido graficamente sem o apelo computacional.

 

Se a Função Objetivo é Côncava (Problema de Maximixação) ou Convexa (Problema de Minimização) – lembrando que maximizar f é equivalente a Minimizar (-f), e o Conjunto de Restrições define uma Região Covexa, então o Problema é chamado Convexo e Métodos de Otimização Convexa podem ser usados na maioria dos casos.

 

Se a Função Objetivo f é uma mistura de uma função côncava e uma função convexa (no caso de maximização) e o Conjunto as Restrições definem uma Região (Conjunto Viável) Convexa, e então o problema pode ser transformado para um Problema de Optimização Convexa usando Técnicas de Programação Fracionária.

 

Vários métodos estão disponíveis para resolver problemas convexos. Uma abordagem é a utilização de formulações especiais de Problemas de Programação Linear. Outro método envolve a utilização de Técnicas Branch and Bound, em que o programa é dividido em subclasses (Sub-Problemas menores) a serem resolvidos como convexos (problema de minimização) ou aproximações lineares que formam um limite inferior sobre o valor global dentro da subdivisão. Com divisões subsequentes, em algum momento uma solução real será obtida cujo valo é igual ao melhor limite inferior obtido para qualquer das soluções aproximadas. Esta Solução é um ótimo, embora possivelmente não exclusivamente o único. O algoritmo também pode ser interrompido imediatamente, com a garantia de que a melhor solução possível está dentro de uma tolerância com respeito ao melhor valor encontrado numa iteração k+1 e outro encontrado na iteração k – são os Critério de Parada em que uma diferença entre duas soluções subsequentes não ultrapassa um valor ε (ERRO) previamente estipulado. E Isto é necessário para assegurar a terminação do algoritmo para se obter a Solução com um Número Finito k de Iterações. Isto é especialmente útil para grandes problemas difíceis e problemas com valores estimados, onde a estimativa pode ser obtida com certa confiabilidade.

 

Supondo Diferenciabilidade (possui derivada) e certa Regularidade das Restrições, então as Condições Karush-Kuhn-Tucker (KKT) fornecer condições necessárias para uma solução vir a ser ótima. Se não existe Diferenciabilidade, então ​​versões sob não Diferenciabilidade das condições de Karush-Kuhn-Tucker (KKT) estão disponíveis na literatura. [2]

Exemplos:

1 - Exemplo BidimensionaL (em R²)

Um problema Simples pode ser definido pelas Restrições

x1 ≥ 0

x2 ≥ 0

x1² + x2² ≥ 1

x1² + x2² ≤ 2

 

Com uma Função Objetivo a ser Maximizada

f(x) = x1 + x2

 

onde x = (x1, x2). Resolução do problema 2-D. OBSERVAÇÃO: Página Interativa: você modifica o Problema e a Solução Online lhe é dada!

 

 

 

 

 

 

 

2 - Exemplo Tridimensional (em R³)

Outro Problema Simples pode ser definido pelas Restrições

x1² − x2² + x3² ≤ 2

x1² + x2² + x3² ≤ 10

 

Com uma Função Objetivo a ser Maximizada

f(x) = x1x2 + x2x3

 

onde x = (x1, x2, x3). Resolução do Problema 3-DOBSERVAÇÃO: Página Interativa: você modifica o Problema e a Solução Online lhe é dada!

A intersecção da linha com a Região definida pelas Restrições (O Conjunto Viável) representa a Solução. Esta linha obtida pela equação z = x1+x2 para cada valor fixado da Função Objetivo z=f(x1,x2)=x1+x2. f é Linear e seus valores crescem na direção do vértice superior direito do quadrado.

A interseção da Superfície Superior com a região defendida pelas Restrições (Conjunto Viável) no centro representa a Solução.

Aplicações

Métodos de Otimização Não-Lineares são usados em engenharia, por exemplo, para construir modelos computacionais de reservatórios de petróleo. [3]

Referências

Leitura Suplementar

  • Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. 

  • Bazaraa, Mokhtar S. and Shetty, C. M. (1979). Nonlinear programming. Theory and algorithms. John Wiley & Sons. 

  • Bertsekas, Dimitri P. (1999). Nonlinear Programming: 2nd Edition. Athena Scientific. 

  • Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5. 

  • Luenberger, David G.Ye, Yinyu (2008). Linear and nonlinear programming. International Series in Operations Research & Management Science 116 (Third ed.). New York: Springer. pp. xiv+546. 

  • Nocedal, Jorge and Wright, Stephen J. (1999). Numerical Optimization. Springer. 

  • Jan Brinkhuis and Vladimir Tikhomirov, 'Optimization: Insights and Applications', 2005, Princeton University Press

 

 

Outros Links

Veja a página em Slide

Leitura Complementar: Páginas em Slide!

 

1) Pesquisa Operacional: Programação Não-Linear

Veja a página em Slide

2) Pesquisa Operacional: Programação Não-Linear

    Problemas de Programação Matemática Não-Linear

Texto a ser Editado. Aguardem!

Programas Executáveis Online

Problemas de Otimização em R² e R³

  A partir de 04 Set de 2020

Você é o Visitante de Número

(48) 8410.6510 /  faleconosco@ensinoeinformacao.com  /  Florianópolis - SC - Brasil

  • w-facebook
  • Twitter Clean
  • w-googleplus

® 2003 - 2018 Todos os direitos Reservados, ensinoeinformacao.com

Temos Uma versão desta Revista Especificamente para SmartPhones: Versão mais Enxuta somente com Vídeo Aulas e Eventos