Definição e histórico
Pesquisa Operacional é a disciplina da otimização. Algoritmos diversos são aplicados com finalidade de tornar alguma condição máxima ou mínima dadas restrições que podem ser ambientais ou de recursos. Exemplos de situações em que técnicas elementares estão na produção: gerência de insumos, roteamento de veículos baseados em tempo ou custo, determinação de volumes de estoque e compras, posicionamento geográfico de facilidades, dimensionamento de atendimentos e filas de espera. Segundo Patrícia Belfiore e Luiz Paulo Fávero, sua primeira utilização formalizada ocorreu durante a Segunda Guerra Mundial, época em que George B. Dantzig liderou a equipe que desenvolveu o método Simplex para resolução de problemas de Programação Linear (PL). Os mesmos autores constatam que ainda há muitos profissionais e executivos que tomam suas decisões baseados na experiência empírica e não na análise de dados e técnicas de tomada de decisão.Modelos e Técnicas de Resolução
Problemas de otimização são baseados em uma métrica que deve ser maximizada ou minimizada e restrições que precisam ser obedecidas.
Uma fábrica de móveis que utiliza madeira e metal para criação de mesas e
cadeiras. Cada mesa é vendida por $50 e cada cadeira por $30, sendo que cada cadeira consome 4 unidades de madeira e 3 de metal e uma mesa consome 5 unidades de madeira e 4 de metal. Sabe-se que o orçamento mensal da fábrica é de $600 e as unidades de madeira e metal custam respectivamente $3 e $2. Qual deve ser a produção mensal de mesas e de cadeiras para se obter a maior receita?
Neste exemplo a restrição orçamentária impede a compra de mais de 200 unidades
de madeira ou 400 unidades de metal. Nessas duas condições, o faturamento da
empresa seria zero, pois não há a possibilidade de produzir móveis sem um dos
insumos, então é necessário um ponto médio. Existe a possibilidade de comprar
metade do orçamento madeira e metade em metal. Dessa forma, 100 unidades de
madeira e 150 de metal permitem serem produzidas 25 cadeiras ou 20 mesas,
gerando alguma receita e sobrando um pouco de insumos. Mas… existe outra forma
aplicar o mesmo orçamento obtendo menos sobras e mais dinheiro? Sim, problemas
como esse são resolvíveis, Conseguimos atingir a solução ótima (a melhor que se
consegue seguindo as “regras do jogo”) através de métodos computacionais.
-
Método Simplex
Este método foi desenvolvido na década de 40 e tem o comportamento de percorrer os
pontos do domínio pelas fronteiras das curvas de restrição até encontrar um ponto do
domínio correspondente a uma solução viável e em seguida percorrer nas fronteiras
viáveis as que melhoram a solução até chegar ao ótimo. -
Método dos Multiplicadores de Lagrange
No cálculo de funções de várias variáveis para uma variável, o gradiente é um vetor de
valores encontrados através das derivadas direcionais de cada uma das variáveis. Este
vetor nos dá, para cada ponto do domínio, a direção de maior crescimento da função. Se uma
outra função é a fronteira de uma restrição, quando os gradientes dessas duas funções estão
alinhados, isso é, são iguais exceto por uma multiplicação por constante, encontra-se um
ponto de máximo local. Esse método pode ser aplicado a problemas que não são tratáveis por
PL.
Limites dos métodos citados
No exemplo da fabricante de móveis, podemos determinar que os números de móveis de cada tipo a ser produzido define uma solução. A partir dos valores determinados para essas variáveis, é possível determinar a quantidade de insumos a ser consumida e o valor da receita gerada. Problemas com poucas variáveis de decisão e poucas restrições podem ser calculados por meios manuais ou computacionalmente. Entretanto, quando o número de variáveis de decisão e de restrições se torna grande ou as fronteiras da viabilidade fica mais complexa, torna-se necessária a utlização de métodos mais rebuscados. Para os mais nerds, devo dizer que existem problemas que não podem ser resolvidos por meio de algoritmos precisos independentemente do tempo disponível. Mas, vamos voltar ao nosso foco: os métodos que utilizamos no dia-a-dia. Conforme o número de variáveis a serem encontradas cresce ou as restrições se tornam numerosas ou não são tão simples, torna-se necessário a utilização de inteligências mais sofisticadas, que serão abordadas a frente neste artigo.Ferramentas não lineares
Quando o problema se torna mais complexo ou as instâncias maiores, fica inviável resolvê-lo por meio da computação tradicional e exata. Mas existem formas de encontrar soluções viáveis boas em tempo razoável. A utilização de heurísticas e meta-heurísticas são empregadas neste caso.Referências
Pesquisa Operacional para Cursos de Engenharia, de Patrícia Belfiore e Luiz Paulo Fávero. Pesquisa Operacional, de Hamdy A. Taha.Sugestão de materiais
História da Pesquisa Operacional – Professor Zepka (YouTube) https://www.youtube.com/watch?v=5Wmax7pAGW8&t=3622s