Investigação operacional

A pesquisa operacional (PO), ou investigação operacional (IO), é 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, apesar de, às vezes, ser considerada um subcampo das ciências matemáticas. Ela é 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.

Empregando técnicas de outras ciências matemáticas, como modelagem, estatística e otimização, a pesquisa operacional chega a soluções ótimas ou quase ótimas para problemas complexos de tomada de decisão. A PO geralmente se preocupa em determinar os valores extremos de alguma situação do mundo real: o máximo (de lucro, desempenho ou rendimento) ou mínimo (de perda, risco ou custo). Originada em esforços militares antes da Segunda Guerra Mundial, suas técnicas têm crescido para ajudar a resolver problemas encontrados em uma variedade de indústrias.

Visão Geral

A pesquisa operacional (OR) abrange uma ampla gama de técnicas e métodos de resolução de problemas aplicados na busca de uma melhor tomada de decisão e eficiência, como simulação, otimização matemática, teoria das filas e outros modelos de processos estocásticos, processos de decisão de Markov, métodos econométricos, análise envoltória de dados, redes neurais, sistemas especialistas, análise de decisão e o processo de hierarquia analítica.

Quase todas essas técnicas envolvem a construção de modelos matemáticos que tentam descrever o sistema. Devido à natureza computacional e estatística da maioria desses campos, a PO também tem fortes laços com a ciência da computação e análise. Os pesquisadores operacionais que enfrentam um novo problema devem determinar quais dessas técnicas são mais apropriadas, dada a natureza do sistema, os objetivos de melhoria e as restrições de tempo e capacidade de computação.

As principais subdisciplinas da pesquisa operacional atualmente, conforme identificadas pelo periódico "Operations Research" , são:

• Informática e tecnologia de informação
• Meio ambiente, energia e recursos naturais
• Engenharia financeira
• Manufatura, ciência de serviços e gestão da cadeia de suprimentos
• Gerenciamento de receita
• Simulação
• Modelos estocásticos
• Transporte

História

Nas décadas após as duas guerras mundiais, o uso da pesquisa operacional foi difundido para vários campos, passando a ter espaço tanto em empresas privadas, quanto em órgãos governamentais. Hoje, ela tem papel importante em setores como :

• Aeronáutico: auxiliando as companhias aéreas a programar aviões, a estipular preços de passagens e planejar o tamanho das frotas
• Governamental: auxiliando o implemento de planos emergenciais
• Logístico: planejamento

Origens históricas

A pesquisa operacional não tem suas raízes bem definidas, mas é geralmente aceito que teve seu início nos períodos próximos ao início da Segunda Guerra Mundial, quando os britânicos estavam se preparando para guerra. A PO foi oficialmente aplicada pela primeira vez em 1938 na Inglaterra, por um grupo de estudiosos, entre eles, Patrick Blackett, o pai da pesquisa operacional. Ela foi usada inicialmente para fins militares, com o intuito de reposicionar radares britânicos. Os trabalhos iniciais empreenderam o planejamento de defesa de comboios navais, detecção e destruição submarinos, mensuração de ataques a bomba, e diversas atividades logísticas e de planejamento incorporando cenários de risco. As primeiras equipes eram compostas por físicos, matemáticos, fisiologistas, biólogos, astrônomos, químicos e especialistas em comunicação.

Segunda Guerra Mundial

A PO moderna, que conhecemos hoje, nasceu da necessidade dos Aliados na resolução de 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.

A PO foi para os Estados Unidos alguns anos depois de surgir na Inglaterra, em grupos semelhantes aos desenvolvidos na Europa, mantendo o mesmo caráter militar. Nos EUA eles usaram da pesquisa operacional para proteger comboios, procurar inimigos e melhorar a eficácia dos bombardeios. Atualmente, cada ramo das Forças Armadas tem seu próprio grupo de pesquisa operacional, que conta com a participação de militares e civis. Além disso, a Agência Nacional de Segurança também possui seu próprio Centro de Pesquisa Operacional.

Pós-Guerra

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 de decisões 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 algorítmica e velocidade de processamento adaptados à imaginação dos profissionais da investigação operacional, e a microinformática permitiu relacionar diretamente os sistemas de informação com os decisores. Nos Estados Unidos, um dos resultados do desenvolvimento da pesquisa operacional foi o Algoritmo Simplex, desenvolvido na Força Aérea.

Fases

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

• 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. 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

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

Programação linear

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:

Uma área A pode ser semeada por duas culturas (1 e 2). Essas culturas possuem demandas diferentes quanto a fertilizantes e inseticidas. O lucro por área plantada é respectivamente $S_{1}$ e $S_{2}$. Deve-se determinar a área plantada para cada cultura ($x_{1}$ e $x_{2}$) de forma a otimizar o lucro total, sujeito a restrição quanto à quantidade total de fertilizante $F$ e inseticida $P$.

maximize $S_{1}x_{1}+S_{2}x_{2}$		(maximize o lucro - esta é a "função objetivo")
sujeito a	$x_{1}+x_{2}\leq A$	(limite da área total)
	$F_{1}x_{1}+F_{2}x_{2}\leq F$	(limite do fertilizante)
	$P_{1}x_{1}+P_{2}x_{2}\leq P$	(limite do insecticida)
	$x_{1}\geq 0,\,x_{2}\geq 0$	(não se pode semear uma área negativa)

Programação inteira

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

Representações de redes são usadas para problemas de diversas áreas, tais como: redes de transporte, de comunicação, de energia, de produção, de distribuição, de planejamento de projetos, de gerenciamento de recursos, de planejamento financeiro, entre 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 dígrafo (grafo orientado).

Exemplos de problemas de otimização em redes:

• Caminho mínimo;
• Árvore geradora mínima;
• Fluxo em rede;
• Transporte;
• Designação;
• Roteamento de veículos.

Programação dinâmica

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.

Programação não linear

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 Rⁿ. Sejam f, g_i, e h_j funções reais em X.

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

${\begin{aligned}{\text{Min ou Max }}&f(x)\\{\text{sujeito a}}&g_{i}(x)\leq 0{\text{ para cada }}i\in \{1,\dotsc ,m\}\\&h_{j}(x)=0{\text{ para cada }}j\in \{1,\dotsc ,p\}\\&x\in X.\end{aligned}}$

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

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

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 número 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

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.

Problemas abordados

• Método do caminho crítico: mostra visualmente as atividades de um projeto complexo, apresentando de forma clara o tempo necessário para a conclusão de tarefas e rastreia as atividades para que não ocorram possíveis atrasos.
• Planta baixa (de microeletrônicos): projetar o layout do equipamento em uma fábrica ou componentes em um chip de computador para reduzir o tempo de fabricação (reduzindo, portanto, o custo).
• Otimização da rede de telecomunicações: configuração de redes de telecomunicações ou de sistema de energia para manter a qualidade do serviço durante interrupções.
• Problemas de alocação de recursos.
• Análise da localização de instalações.
• Problemas de alocação: Problema da designação; Problema Generalizado de Atribuição (PGA); Problema Quadrático de Alocação (PQA).
• Inferência Bayesiana: aplicação estatística bayesiana à busca por objetos perdidos.
• Roteamento de ônibus: determinar as rotas de ônibus de modo que se precise do menor número de veículos possíveis.
• Gestão da Cadeia de Suprimentos: gerencia os fluxos, de bens, serviços de formas estratégicas visando o menor custo possível, obtendo assim vantagens competitivas e criação de valor para os clientes.
• Gerenciamento da Produção de Projetos: cobre a área que estava fora do alcance do Gerenciamento de Projetos, cuidando de conjuntos complexos de atividades que devem ser feitas em determinada ordem de maneira a minimizar os custos.
• Mensagens eficientes e estratégicas para melhor relacionamento com o cliente.
• Automação: usar de sistemas mecânicos ou eletrônicos para operacionalizar e controlar processos de produção dispensando intervenção direta do homem, agilizando os processos internos de uma organização.
• Globalização: globalização dos processos operacionais para aproveitar as vantagens de materiais, mão de obra, terra ou outros insumos de produtividade mais baratos.
• Transporte: gerenciamento de transporte de carga e sistemas de entrega (exemplo, transporte de carga intermodal).
• Cronograma: equipe de pessoal; etapas de fabricação; tarefas do projeto; tráfego de dados da rede (teoria das filas); eventos esportivos e sua cobertura televisiva;
• Mistura de matérias-primas em refinarias de petróleo;
• Determinar preços ideais, em muitos ambientes de varejo e B2B, dentro das disciplinas da ciência de preços;
• Problema de corte de estoque: corte de itens pequenos de grandes.

A pesquisa operacional também é amplamente utilizada no governo, onde políticas baseadas em evidências são utilizadas.

Áreas relacionadas

Alguns campos que se correlacionam, segundo o periódico Operations Research and Management Science, com a Pesquisa Operacional são:

• Análise de negócios;
• Ciência da computação;
• Data science/Big Data;
• Análise de decisões;
• Engenharia;
• Engenharia Financeira;
• Previsão;
• Teoria dos Jogos;
• Informação geográfica;
• Teoria dos grafos;
• Engenharia Industrial;
• Controle de inventário;
• Logística;
• Modelos matemáticos;
• Modelos de otimização matemática;
• Probabilidade e estatística;
• Gerenciamento de projetos;
• Análise de políticas;
• Teoria das filas;
• Simulação;
• Modelos de roteamento de transportes;
• Modelos estocásticos;
• Gestão da cadeia de suprimentos;
• Engenharia de sistemas;

Aplicações

As aplicações são inúmeras, como em companhias aéreas, empresas de manufatura, organizações de serviços, ramos militares e governos. A gama de problemas e questões para os quais contribuiu com percepções e soluções é vasta. Vejamos alguns exemplos:

• Agendamento (de companhias aéreas, trens,ônibus, etc.)
• Localização das instalações (decidir a localização mais apropriada para novas instalações)
• Engenharia hidráulica e de Tubulação (gerenciamento do fluxo de água dos reservatórios)
• Serviços de saúde (gestão da informação e da cadeia de abastecimento)
• Teoria dos Jogos (identificar, compreender; desenvolver estratégias adotadas pelas empresas)
• Design Urbano
• Engenharia Computacional (roteamento de pacotes; tempo e análises)
• Engenharia de telecomunicações e dados (roteamento de pacotes)

Pesquisa Operacional e Covid-19

A PO veio como uma ferramenta importante para o enfrentamento da pandemia. Num cenário de escassez de recursos, desde a produção até a administração organizacional, é de suma importância utilizar de metodologias capazes de auxiliarem na tomada de decisões. A pesquisa operacional então se tornou um instrumento na busca por decisões rápidas, estratégicas visando equilibrar a escassez de recursos e minimização de custos.

Sociedades

A Federação Internacional das Sociedades de Pesquisa Operacional (IFORS) é uma organização formada por um conjunto de instituições de pesquisa operacional em todo o mundo, representando aproximadamente 50 sociedades nacionais, entre eles: Brasil, Reino Unido, França, Alemanha, EUA e Coreia do Sul. Os membros constituintes da IFORS formam grupos regionais, como o da Europa, Associação das Sociedades Europeias de Pesquisa Operacional (EURO).

Ver também

• Programação Linear
• Programação Dinâmica
• Teoria dos Grafos
• Simulação Discreta
• Simulação de Monte Carlo
• Teoria dos Jogos
• Meta-Heurísticas
• Otimização Combinatória
• Teoria da Complexidade Computacional

Bibliografia

• HILLIER, Frederick S.; LIEBERMAN, Gerald J. Introdução à Pesquisa Operacional. 9ª Edição. Porto Alegre: McGraw-Hill. 2013. ISBN 9788580551181.
• Taha, Hamdy A., "Operations Research: An Introduction", Pearson, 10th Edition, 2016
• Robert J. Thierauf & Richard A. Grosse, "Decision Making Through Operations Research", John Wiley & Sons, INC, 1970
• Harvey M. Wagner, Principles of Operations Research, Englewood Cliffs, Prentice-Hall, 1969
• R. E. Bellman, Dynamic Programming, Princeton University Press, Princeton, 1957

Ligações externas

• 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