Investigação operacional

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

A Investigação Operacional (IO) ou Pesquisa operacional (PO), é um ramo interdisciplinar da matemática aplicada que faz uso de modelos matemáticos, estatísticos e de algoritmos na ajuda à tomada de decisão. É usada sobretudo para analisar sistemas complexos do mundo real, tipicamente com o objetivo de melhorar ou otimizar a performance.

A PO não é uma ciência em si, mas sim a aplicação da ciência à solução de problemas gerenciais e administrativos, e centra-se no desempenho de sistemas organizados como um todo, em vez de suas partes tomadas separadamente[1].

História[editar | editar código-fonte]

A pesquisa operacional nasceu no teatro de operações durante a II Guerra Mundial, quando os Aliados se viram confrontados com problemas (de natureza logística e de tática e estratégia militar) de grande dimensão e complexidade. Foram criados grupos multidisciplinares de cientistas em que se incluíam matemáticos, físicos e engenheiros, a par de outros oriundos das ciências sociais para apoiar os comandos operacionais na resolução desses problemas. Aplicaram o método científico aos problemas que lhes foram sendo colocados e criaram modelos matemáticos, apoiados em dados e factos, que lhes permitissem perceber os problemas em estudo e ensaiar e avaliar o resultado hipotético de estratégias ou decisões alternativas.

Com o fim do conflito e sucesso obtido, os grupos de cientistas transferiram a nova metodologia na abordagem de problemas para as empresas, confrontadas com problemas decisionais de grande complexidade derivados do crescimento económico que se seguiu. Com a evolução observada na informática criaram-se condições de concretização algoritmica e velocidade de processamento adaptados à imaginação dos profissionais da investigação operacional, e a micro-informática permitiu relacionar directamente os sistemas de informação com os decisores.

Fases[editar | editar código-fonte]

A resolução de um problema, pelo método da Investigação Operacional, segue as seguintes fases[2]:

  • Definição do problema. Nesta fase são definidos os objetivos a serem atingidos, as variáveis envolvidas no problema, e as principais restrições.
  • Construção do modelo matemático. A escolha do modelo depende do tipo de problema a ser resolvido. Os modelos matemáticos mais utilizados, são de programação linear.
  • Solução do modelo. Nesta fase, a solução é encontrada a partir do modelo matemático adotado na resolução do problema.
  • Validação do modelo. O modelo é testado para ver se a solução obtida é condizente com o problema estudado.
  • Implementação da solução. Nesta fase, a solução é convertida em regras práticas para a solução do problema.

Principais modelos de PO[editar | editar código-fonte]

Vários tipos de modelos são usados por analistas de PO. Os principais modelos são apresentados a seguir.

Programação linear[editar | editar código-fonte]

A Programação Linear consiste em métodos para resolver problemas de otimização de uma função objetivo linear, sujeita a restrições (desigualdades) também lineares.

Exemplo:

maximize (maximize o lucro - esta é a "função objetivo")
sujeito a (limite da área total)
(limite do fertilizante)
(limite do insecticida)
(não se pode semear uma área negativa)

Programação inteira[editar | editar código-fonte]

A Programação Inteira é um modelo de Programação Linear no qual as variáveis de decisão são inteiras.

Ao contrário da PL, que pode-se encontrar a solução óptima em um tempo razoável, normalmente os problemas de Programação Inteira são considerados NP-difícil. Se as variáveis forem binárias, ou seja, assumirem somente os valores 0 (zero) ou 1, temos um caso especial da PI, que também é NP-difícil.

Modelos de otimização em redes[editar | editar código-fonte]

Representações de redes são usadas para problemas de diversas áreas, tais como: redes de trasporte, de comunicação, de energia, de produção, de distribuição, de planejamento de projetos, de gerenciamento de recursos, de planejamento financeiro, dentre outras.

Uma rede é formalmente representada por um grafo G = (N, A), onde N é o conjunto de nós (vértices) e A é o conjunto de arcos, tais que cada arco conecta dois nós distintos. Quando faz-se necessário definir sentido de cada arco, a rede é representada por digrafo (grafo orientado).

Exemplos de problemas de otimização em redes:

Programação dinâmica[editar | editar código-fonte]

A programação dinâmica, como o método de dividir e conquistar, resolve problemas combinando as soluções para subproblemas. ( "Programação" neste contexto se refere a um método tabular). Os algoritmos de divisão e conquista particionam o problema em subproblemas, resolvem os subproblemas de forma recursiva, e em seguida, combinam suas soluções para resolver o problema original. Em contrapartida, a programação dinâmica se aplica quando os subproblemas se sobrepõem, isto é, quando os subproblemas compartilham subproblemas. Neste contexto, um algoritmo de divisão e conquista faz mais trabalho do que o necessário, resolvendo repetidamente os subproblemas comuns.

Um algoritmo de programação dinâmica resolve cada subproblema apenas uma vez e, em seguida, salva sua resposta em uma tabela, evitando assim a o esforço de recalcular a resposta toda vez que ele resolve cada subproblema.[3]

Programação não-linear[editar | editar código-fonte]

A programação não-linear é aplicada quando o modelo de programação matemática tem função objetivo e/ou restrições não lineares.

Sejam n, m, p inteiros positivos. Seja X um subconjunto de Rn. Sejam f, gi, e hj funções reais em X.

Um problema de minimização não-linear é um problema de optimização na forma:

Os métodos para resolução de problemas de Programação Não-Linear podem ser divididos em 2 grupos:

  1. Modelos sem restrições;
  2. Modelos com restrições.

Simulação discreta[4][editar | editar código-fonte]

A simulação de eventos discretos (SED) modela a operação de um sistema como uma sequência de eventos discretos no tempo. Cada evento ocorre em um determinado instante de tempo e marca uma mudança de estado no sistema. Entre eventos consecutivos, considera-se que o sistema não sofre mudança alguma, assim, a simulação pode saltar diretamente do instante de ocorrência de um evento para o próximo.

Um técnica conhecida para execução de simulações de eventos discretos é o "Método das três fases". Nesta abordagem, a primeira fase sempre avança o relógio para o próximo evento a ocorrer, respeitando a ordem cronológica de eventos (chamados de eventos do tipo A). A segunda fase é a execução de todos os eventos que incondicionalmente ocorrem no instante atual (chamados de eventos do tipo B). A terceira fase é a execução de todos os eventos que condicionalmente ocorrem no tempo atual (chamados eventos do tipo C).

Simulação de Monte Carlo[editar | editar código-fonte]

Designa-se por método de Monte Carlo (MMC) qualquer método de uma classe de métodos estatísticos que se baseiam em amostragens aleatórias massivas para obter resultados numéricos, isto é, repetindo sucessivas simulações um elevado numero de vezes, para calcular probabilidades heuristicamente, tal como se, de fato, se registrassem os resultados reais em jogos de casino (daí o nome). Este tipo de método é utilizado em simulações estocásticas com diversas aplicações em áreas como a física, matemática e biologia. O método de Monte Carlo tem sido utilizado há bastante tempo como forma de obter aproximações numéricas de funções complexas em que não é viável, ou é mesmo impossível, obter uma solução analítica ou, pelo menos, determinística.

Teoria dos jogos[editar | editar código-fonte]

Os modelos de decisão podem ser considerados como um procedimento de tomada de decisão em situações não competitivas, no sentido de não envolver diretamente outras pessoas ou organizações. Os estados ou os cenários que irão acontecer envolvem riscos ou incertezas referentes à previsão do mercado, influência do clima, etc. O tomador de decisão escolhe uma das alternativas de decisão existentes. O decisor tem conhecimento dos cenários possíveis e dos riscos embutidos nesses cenários. Uma situação competitiva ou de conflito acontece quando um estado ou cenário ocorre causado pela decisão tomada por outro participante.

A análise dos problemas de decisão em situações nas quais existem conflitos pode ser efetuada com uso da Teoria dos Jogos, formulada por Von Neumann (Prêmio Nobel) e Morgenstern em 1935.

Associações de PO[editar | editar código-fonte]

  • IFORS – International Federation of Operacional Research Societies
  • EURO – The Association of European Operational Research Societes
  • APDIO – Associação Portuguesa de Investigação Operacional
  • SOBRAPO – Sociedade Brasileira de Pesquisa Operacional

Ver também[editar | editar código-fonte]

Referências

  1. EILON, Samuel. «operations research (industrial engineering) :: History – Britannica Online Encyclopedia». operations research (industrial engineering) :: History – Britannica Online Encyclopedia. Britannica.com. Consultado em 08 Setembro 2016. 
  2. ANDRADE, Eduardo Leopoldino de, "Introdução à pesquisa operacional: métodos e modelos para análise de decisões, 4 Ed.", Rio de Janeiro: LTC, 2009. 202p.
  3. CORMEN, Thomas H. (2009). Introduction to algorithms (Massachussetts: MIT Press). p. 359. 
  4. Hillier, Frederick S.; Lieberman, Gerald J. (2013). Introdução à Pesquisa Operacional (Porto Alegre: McGraw-Hill). pp. 934–945. 

Bibliografia

  • HILLIER, Frederick S.; LIEBERMAN, Gerald J. Introdução à Pesquisa Operacional. 9ª Edição. Porto Alegre: McGraw-Hill. 2013. ISBN: 9788580551181.