Analogias de problemas clássicos em Pesquisa Operacional

A ciência da Pesquisa Operacional (OR) pretende ser uma alternativa com enorme potencial para a solução de problemas complexos. Tradicionalmente, diferentes tipos de problemas são apresentados usando contextos lúdicos, como:

 

• Problema do caixeiro viajante: encontre a rota mais curta em que o vendedor visita todas as cidades apenas uma vez;
• Problema de coloração: encontre a menor quantidade de cores para colorir um mapa, sem pintar países vizinhos com a mesma cor;
• Problema da rainha: posicione o maior número de rainhas em um tabuleiro de xadrez de forma que elas não possam se atacar;
• Problema da mochila: maximizar o valor de uma mochila de forma que a quantidade de itens carregados nela não ultrapasse o seu limite de peso.

 

Contextualizar esses problemas é eficaz para entender seus conceitos e desafios; no entanto, para muitos alunos, essa contextualização está longe da realidade de um problema de mercado.

 

Para apreciar esses problemas clássicos, mostraremos como o Problema da Mochila pode servir de base para problemas mais complexos.

 

 

O clássico Problema da Mochila 

 

Conforme descrito anteriormente, o problema envolve maximizar o valor de uma mochila de forma que a quantidade de itens colocados não exceda seu limite de peso. Para tomar a decisão que maximiza o valor da mochila, é necessário saber:

 

• A lista de itens;
• O peso de cada item;
• O valor de cada item;
• O limite de peso da mochila.

 

A partir desses dados, podemos definir se cada item faz parte da mochila ou não, considerando que:

 

• O valor da mochila é calculado somando os valores individuais de cada item da mochila;
• O peso da mochila é calculado somando os pesos individuais de cada item dentro da mochila.

 

Esse problema, a princípio, parece ser diretamente aplicável apenas ao vendedor que precisa viajar de avião e cumprir o limite de bagagem de mão. Como isso poderia ajudar uma indústria?

 

Contexto 1

 

Em seu formato clássico, o Problema da Mochila já é capaz de apoiar a decisão do conselho no planejamento de investimentos. Para isso, precisamos apenas (re) contextualizar nossos conceitos:

 

• A lista de itens passa a ser a lista de projetos da empresa;
• O peso de cada item torna-se o custo de implementação do projeto;
• O valor de cada item passa a ser o retorno financeiro esperado do projeto;
• O limite de peso da mochila passa a ser o orçamento disponível.

 

Dessa perspectiva, fica claro como um modelo de otimização como o Problema da Mochila pode ser útil. Pode mostrar o conjunto ideal de projetos que devem ser autorizados para aumentar o retorno na empresa. Este é um problema de alocação de recursos!

 

Contexto 2

 

Outro contexto em que pode ser aplicado é a definição de abastecimento do cliente. Imagine que uma empresa precise alugar uma frota de veículos para distribuir seus produtos. Para a empresa, é importante definir a forma de carregamento dos veículos (destinados a diferentes clientes) para maximizar o seu lucro. Neste caso:

 

• A lista de itens torna-se a lista de produtos;
• O peso de cada item torna-se o peso de cada produto;
• O valor de cada item se torna o preço de cada produto;
• O limite de peso da mochila passa a ser o limite de peso do veículo.

 

Nesse cenário, é importante observar que é fundamental definir:

 

• Quantos veículos alugar (o custo pode ser maior que a receita);
• Qual veículo atende qual cliente (o limite de cada veículo da frota pode ser variar);
• Qual produto será carregado em qual veículo (o preço pago pode variar por cliente).

 

Note que o peso do produto não varia de acordo com o veículo ou cliente.

 

Contexto 2.1

 

O mais comum nas indústrias seria encontrar o Contexto 2 com restrições adicionais. Por exemplo, as equipes podem carregar a frota com taxas diferentes e isso deve ser considerado ao planejar o abastecimento do cliente.

 

Por mais que o caráter operacional da carga seja enfatizado, o cerne do problema continua sendo o Problema da Mochila! As restrições operacionais excluirão apenas algumas das combinações Produto-Veículo-Cliente que anteriormente seriam consideradas possíveis soluções no modelo.

 

No entanto, classificar um problema real em um problema clássico com base em experiência é de grande valia para acelerar sua resolução. Esses problemas já possuem uma importante base teórica e diversas possibilidades tecnológicas para encontrar a melhor solução.

 

Para os fãs da pesquisa operacional, um conselho: dedique um tempo para entender os clássicos para criar valor para o futuro.

 

Autor: Guilherme Martino - Consultor Sênior na Cassotis Consulting

                                      Coautor: Fabio Silva - Gerente Senior na Cassotis Consulting