Programação Não Linear / ensinoeinformacao

Disciplina: Programação Não-Linear

PESQUISA OPERACIONAL

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;

, 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-D. OBSERVAÇÃ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]

Veja Também

Ajuste de Curva
Minimização pelo Critério dos Mínimos Quadrados
Programação Linear
NL(Formato)
Otimização Matemática
Lista de Software de Otimização
Werner Fenchel

Referências

Bertsekas, Dimitri P. (1999). Nonlinear Programming (Second ed.). Cambridge, MA.: Athena Scientific.
Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton, NJ: Princeton University Press. pp. xii+454.
History matching production data and uncertainty assessment with an efficient TSVD parameterization algorithm, http://www.sciencedirect.com/science/article/pii/S0920410513003227

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